Homework 5: Backtracking and environments

Due: 2021-07-13 at 23:59

This assignment has two parts. The first part is practice working with backtracking. The second part is the first part of the MiniScheme interpreter project.

Your implementations will be in several files. The start of each file should be

#lang racket
; Your name(s) here.

Preliminaries

Click on the assignment link. If you’re working with a partner, one partner should create a new team. The second partner should click the link and choose the appropriate team. (Please don’t choose the wrong team, there’s a maximum of two people and if you join the wrong one, you’ll prevent the correct person from joining.)

Once you have accepted the assignment and created/joined a team, you can clone the repository on your computer by following the instruction and begin working. But before you do, read the entire assignment and be sure to check out the expected coding style from the first homework.

Be sure to ask any questions on Piazza.

Submission

To submit your homework, you must commit and push to GitHub before the deadline.

Your repository should contain the following files

It may also a .gitignore file which tells Git to ignore files matching patterns in your working directory.

Any additional files you have added to your repository should be removed from the main branch. (You’re free to make other branches, if you desire, but make sure main contains the version of the code you want graded.)

Make sure you put your name (and your partner’s name if you’re working with one) as a comment at the top of each file.

Part 1. Backtracking

Your implementations of the following functions in this part should all be placed in a single Racket file named hw5.rkt. For this part, tests have been provided for you in the tests.rkt file.

You may use the solution to any exercise as a helper function in subsequent exercises and you may also write stand-alone helper functions.

For each function, write the function.

  1. (25 points) Write a solution to the subset sum problem. This means you should write a procedure (subset-sum n nums) where n is an integer and nums is a list of numbers that returns a subset of the numbers in the list nums whose values sum to n. If no subset of nums does this, the function should return #f.
    • (subset-sum 23 '(2 10 5 7 3 8 6)) returns '(10 5 8) or '(2 10 3 8) or any other subset of '(2 10 5 7 3 8 6) that sums to 23.
    • (subset-sum 23 '(2 10 5 7)) returns #f.
  2. (25 points) A “no-repeat” sequence is a sequence containing only the digits 1, 2, and 3 that does not contain two identical adjacent subsequences. For example '(2 1 3 1 2 1) is a no-repeat sequence, but '(1 2 3 3 2 1) is not (because 3 is a repeated subsequence of length 1), and '(1 2 3 2 3 1) is not (because the subsequence '(2 3) is repeated in adjacent spots.

    Write a procedure (no-repeat n) that returns a no-repeat sequence of length n. Hint: This is very similar to the n-queens problem. The backtracking is actually straightforward; the more difficult part is writing a function (feasible sofar curr) that says that if sofar is a no-repeat sequence, then (cons curr sofar) is also one. Since we know sofar is a no-repeat sequence, we only need to check subsequences starting with x. Suppose sofar is the sequence (list x1 x2 ... xn). You need to check if (list x) is a prefix of (list x1 x2 ... xn) and then if (list x x1) is a prefix of (list x2 x3 ... xn) and then if (list x x1 x2) is a prefix of (list x3 x4 ... xn) and so forth. You may want to use the list-prefix? standard library function.

Part 2. Interpreter environment

For this part, read parts 1, 2, and 3 of the MiniScheme project. Your task is to implement the procedure described in part 3. You should implement that in env.rkt (35 points) and the tests in env-tests.rkt (15 points).

In future homeworks, you will use your env.rkt and env-tests.rkt.

Finishing up

Make sure you commit and push. And make sure your name is in all of the files you submit. Your friendly graders thank you.