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
; Your name(s) here.
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.
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
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.
- (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
(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
(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
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