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. It’s extremely helpful for the graders if you include your name and your partner’s name in the team name. Unfortunately, you cannot use the same team name for multiple assignments. You can append the homework number to your team name if you wish. (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 integers that returns a subset of the integers 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
subset-sum’s feasible check is particularly simple: any number is feasible. For example, suppose
n is 4,
'(5 2 -1). 5 is feasible even though it’s greater than 4 because
'(5 -1) is a valid solution.
Hint 2: The structure of the subset sum problem is also simpler than the others we’ve looked at. If
n is 0, then
empty is a valid solution. Otherwise, if
nums is empty, then there is no solution. Otherwise,
nums starts with some value
x and we can ask the questions:
- Is there a subset of the rest of
nums that sums to
- Is there a subset of the rest of
nums that sums to
Hint 3: Because of the implications of hints 1 and 2 don’t actually need to build the partial solution
sofar. It’s enough to answer one or both of the questions in hint 2 and if the answer to either is yes, return the appropriate result list by consing
x onto the result in one case and not doing so in the other.
(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
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 curr) is a prefix of
(list x1 x2 ... xn) and then if
(list curr x1) is a prefix of
(list x2 x3 ... xn) and then if
(list curr x1 x2) is a prefix of
(list x3 x4 ... xn) and so forth. You may want to use the
list-prefix? standard library function.
Hint 2: If we change feasible to take two lists rather than a list
sofar and a number
curr, we can simplify the implementation of
feasible since it then becomes a check if one list is a prefix of the other list and if not, recursing appropriately. This means you’ll want to call
(feasible sofar (list curr)) as part of your backtracking procedure.
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