• Due: 11:59pm Wednesday 28 September (no grace period on this!)
• Notes:
• Unlike PS2, this has no reading, but lots of programming (in Racket). Start soon.
• Unlike previous psets, this contains a solo problem (Problem 1). You can start the solo problem right away.
• You should be able to do almost all the rest of the problems after the Tue. Sep. 20 class.
• The problems needn’t be done in order. Feel free to jump around.
• Submission:
• In your yourFullName CS251 Spring 2016 Folder, create a Google Doc named yourFullName CS251 PS3.
• At the top of your yourFullName CS251 PS3 doc, include your name, problem set number, date of submission, and an approximation of how long each problem part took.
• For all parts of all problems, include all answers (derviations, code, etc.) in your PS2 google doc. Please format your evaluation derivations so that they’re easy to read. Format small-step derivations and Racket code using a fixed-width font, like Courier New. You can use a small font size if that helps.
• For Problem 1 (Solo Problem: Recursive Numeric Functions)
• Be sure that all function definitions in `yourAccountName-ps3-solo-functions.rkt` also appear in your Google Doc (so that I can comment on them)
• Drop a copy of your `yourAccountName-ps3-solo-functions.rkt` in your `~/cs251/drop/ps03` drop folder on cs.wellesley.edu.
• For Problem 3 (Recursive Racket List Functions):
• Be sure that all function definitions in `yourAccountName-ps3-list-functions.rkt` also appear in your Google Doc (so that I can comment on them)
• Drop a copy of your `yourAccountName-ps3-list-functions.rkt` in your `~/cs251/drop/ps03` drop folder on cs.wellesley.edu.

1. Solo Problem: Recursive Numeric Functions (20 points)

This is a solo problem. This means you must complete it entirely on your own without help from any other person and without consulting resources other than course materials or online documentation. You may ask Lyn for clarification, but not for help.

This problem involves the following recursive Racket function `f`:

``````(define f
(lambda (n)
(if (<= n 2)
n
(+ n (f (quotient n 2)) (f (quotient n 3))))))``````
1. (8 points) Use small-step semantics to derive the evaluation of `(f 17)`. To keep the size of your derivation manageable, use the same conventions used in small-step derivations in PS2 Problem 5 Sum Fun. In particular:

• Use the notation λ_f as an abbreviation for the `lambda` expression

``````(lambda (n)
(if (<= n 2)
n
(+ n (f (quotient n 2)) (f (quotient n 3))))))``````
• Use ⇒* to show only the most important steps of the derivation.

Also note that `(quotient a b)` performs an integer division of `a` by `b`. For example `(quotient 11 2)` is `5` and `(quotient 11 4)` is `2`.

2. (1 point) How many times is `f` called in the evaluation of `(f 17)`?

3. (1 point) What is the maximum stack depth (measured in terms of maximum number of nested `+` operations) in the evaluation of `(f 17)`?

4. (5 points) Define a recursive Racket function named `num-f-calls` that takes a single integer argument `n` and returns the number of times that the function `f` is called in the evaluation of `(f n)`. Notes:

• Define the `num-f-calls` function in a new file named `yourAccountName-ps3-solo-functions.rkt` that you create in Dr. Racket.

• `(num-f-calls 17)` should return your answer from part b.

• You should only use Racket language features you used in PS2 or learned in the lectures on Racket expressions and declarations and Racket functions

• Do not attempt to modify the definition of `f` so that it counts the number of times `f` is called by changing the contents of a global variable.

• Instead, write a new recursive function `num-f-calls` that is very much like `f`, but rather than returning the number calculated by `f` instead returns the number of calls to `f` made in that calculation.

5. (5 points) Define a recursive Racket function named `max-depth-f` that takes a single integer argument `n` and returns the maximum stack depth (measured in terms of maximum number of nested `+` operations) in the evaluation of `(f n)`. Notes:

• Add the `max-depth-f` function to your `yourAccountName-ps3-solo-functions.rkt` file.

• `(max-depth-f 17)` should return your answer from part c.

• You should only use Racket language features you used in PS2 or learned in the lectures on Racket expressions and declarations and Racket functions

• The `max` function is especially useful here.

• Do not attempt to modify the definition of `f` so that it determines the stack depth by changing the contents of a global variable.

• Instead, write a new recursive function `max-depth-f` that is very much like `f`, but rather than returning the number calculated by `f` instead returns the maximum stack depth in that calculation.

2. Box-and-pointer diagrams (10 points)

Consider the following box-and-pointer diagram for the list structure named `a`:

1. For each of the numbers 1 through 6, write a Racket expression that uses `car` and `cdr` to extract that number from `a`.

2. Write down the printed representation for a (i.e., what would be returned by the Racket interpreter for evaluating `a`?).

3. Write a Racket definition of the form `(define a`expr`)`, where expr is an expression using `cons`, `list`,
and the numbers 1 through 6 (but no `quote` or quotation) to create the structure depicted in the diagram. (Once you have defined `a` in this way, you may test your expressions from part (a).)

3. Recursive Racket List Functions (70 points)

In PS2, you wrote some recursive Racket functions that manipulate numbers. Here, you will continue to practice defining recursive Racket functions, but now you focus on functions that manipulate Racket lists. Unlike list and array data structures in many other languages, which are most naturally processed with loops, the linked-list recursively-defined nature of Racket lists make them natural candidates for recursive processing.

For each of the following Racket function specifications, write and test a recursive function that satisfies that specification. In all of your definitions, you should use the following recursive problem solving strategy:

• For which argument(s) is the function so simple that the answer can be returned immediately? This is the base case.

• For the other case(s) (known as the recursive case(s)), use divide/conquer/glue:

• divide: make one or more subproblems that are smaller instances of the given problem;

• conquer: assume that the recursive function you’re defining simply works and returns the correct answer on all of the smaller problems.

• glue: combine the result(s) of the recursive function call(s) with information in the original problem to create the correct result for the whole problem.

Notes:

• For this problem, you should use Dr. Racket to create a single file named `yourAccountName-ps3-list-functions.rkt` that contains all the functions (including helper functions) that you define for this problem.

• In your definitions, unless otherwise instructed, you should not introduce any recursive helper functions. (But you can define nonrecursive helper functions).

• If the following error message pops up during the testing of one of your functions, it mostly likely means that you have an infinite recursion that doesn’t reach its base case and runs out of memory due to a stack depth that cannot fit into available memory.

1. (5 points) Define a function `map-remainder` that takes two arguments (an integer `divisor` and a list `ints` of integers) and returns an integer list the same length as `ints` in which every element is remainder of dividing the corresponding element of `ints` by `divisor`.

`````` > (map-remainder 2 (list 16 23 42 57 64 100))
'(0 1 0 1 0 0)
> (map-remainder 3 (list 16 23 42 57 64 100))
'(1 2 0 0 1 1)
> (map-remainder 5 (list 16 23 42 57 64 100))
'(1 3 2 2 4 0)
> (map-remainder 17 (list 16 23 42 57 64 100))
'(16 6 8 6 13 15)``````
2. (5 points) Define a function `filter-divisible-by` that takes two arguments (an integer `divisor` and a list `ints` of integers) and returns a new integer list containing all the elements of `ints` that are divisible by `divisor`. Use `divisible-by?` from above to determine divisibility.

`````` > (filter-divisible-by 2 (list 16 23 42 57 64 100))
'(16 42 64 100)
> (filter-divisible-by 3 (list 16 23 42 57 64 100))
'(42 57)
> (filter-divisible-by 4 (list 16 23 42 57 64 100))
'(16 64 100)
> (filter-divisible-by 5 (list 16 23 42 57 64 100))
'(100)
> (filter-divisible-by 17 (list 16 23 42 57 64 100))
'()``````
3. (5 points) Define a function `contains-multiple?` that takes an integer `m` and a list of integers `ns` that returns `#t` if `m` evenly divides at least one element of the integer list `ns`; otherwise it returns `#f`. Use `divisible-by?` from above to determine divisibility.

`````` > (contains-multiple? 5 (list 8 10 14))
#t
> (contains-multiple? 3 (list 8 10 14))
#f
> (contains-multiple? 5 null)
#f``````
4. (5 points) Write a function `all-contain-multiple?` that takes an integer `n` and a list of lists of integers `nss` (pronounced “enziz”) and returns `#t` if each list of integers in `nss` contains at least one integer that is a multiple of `n`; otherwise it returns `#f`. Use `contains-multiple?` in your definition of `all-contain-multiple?`.

`````` > (all-contain-multiple? 5 (list (list 17 10 2) (list 25) (list 3 8 5)))
#t
> (all-contain-multiple? 2 (list (list 17 10 2) (list 25) (list 3 8 5)))
#f
> (all-contain-multiple? 3 null)
#t ; said to be "vacuously true"; there is no counterexample!``````
5. (5 points) Define a function `map-cons` that takes any value `x` and an n-element list `ys` and returns an n-element list of all pairs `'(x . y)` where `y` ranges over the elements of `ys`. The pair `'(x . y)` should have the same relative position in the resulting list as `y` has in `ys`.

`````` > (map-cons 17 (list 8 5 42 23))
'((17 . 8) (17 . 5) (17 . 42) (17 . 23))
> (map-cons 3 (list (list 1 6 2) (list 4 5) (list) (list 9 6 8 7)))
'((3 1 6 2) (3 4 5) (3) (3 9 6 8 7))
> (map-cons 42 null)
'()``````
6. (10 points) Define a function `my-cartesian-product` that takes two lists `xs` and `ys` and returns a list of all pairs `'(x . y)` where `x` ranges over the elements of `xs` and `y` ranges over the elements of `ys`. The pairs should be sorted first by the `x` entry (relative to the order in `xs`) and then by the `y` entry (relative to the order in `ys`).

`````` > (my-cartesian-product (list 1 2) (list "a" "b" "c")) ; yes, Racket has string values
'((1 . "a") (1 . "b") (1 . "c") (2 . "a") (2 . "b") (2 . "c"))
> (my-cartesian-product (list 2 1) (list "a" "b" "c"))
'((2 . "a") (2 . "b") (2 . "c") (1 . "a") (1 . "b") (1 . "c"))
> (my-cartesian-product (list "c" "b" "a") (list 2 1))
'(("c" . 2) ("c" . 1) ("b" . 2) ("b" . 1) ("a" . 2) ("a" . 1))
> (my-cartesian-product (list "a" "b") (list 2 1))
'(("a" . 2) ("a" . 1) ("b" . 2) ("b" . 1))
> (my-cartesian-product (list 1) (list "a"))
'((1 . "a"))
> (my-cartesian-product null (list "a" "b" "c"))
'()``````

Notes:

• We ask you to name your function `my-cartesian-product` because Racket already provides a similar (but slightly different) `cartesian-product` function (which you cannot use, of course).
• Use the `map-cons` function from above as a helper function in your `cartesian-product` definition.
• Racket’s `append` function is helpful here.
7. (10 points) Assume that the elements of a list are indexed starting with 0. Define a function `alts` that takes a list `xs` and returns a two-element list of lists, the first of which has all the even-indexed elements (in the same relative order as in `xs`) and the second of which has all the odd-indexed elements (in the same relative order as in `xs`).

`````` > (alts (list 7 5 4 6 9 2 8 3))
'((7 4 9 8) (5 6 2 3))
> (alts (list 5 4 6 9 2 8 3))
'((5 6 2 3) (4 9 8))
> (alts (list 4 6 9 2 8 3))
'((4 9 8) (6 2 3))
> (alts (list 3))
'((3) ())
> (alts null)
'(() ())``````

Notes:

• An earlier version of this problem mentioned using Racket’s `foldr` function to solve it. That was a bug in the problem description! Do not use `foldr` to define `alts` in PS3; instead use regular list recursion based on the divide/conquer/glue strategy. (You will use `foldr` to define `alts` in PS4.).

• There is no need to treat even-length and odd-length cases differently, nor is there any need to treat the singleton list specially.

• Racket’s `let` construct for declaring local names is helpful for avoiding unnecessarily recalculating the recursive call.

8. (10 points) Define a function `inserts` that takes a value `x` and an n-element list `ys` and returns an n+1-element list of lists showing all ways to insert a single copy of `x` into `ys`.

`````` > (inserts 3 (list 5 7 1))
'((3 5 7 1) (5 3 7 1) (5 7 3 1) (5 7 1 3))
> (inserts 3 (list 7 1))
'((3 7 1) (7 3 1) ( 7 1 3))
> (inserts 3 (list 1))
'((3 1) (1 3))
> (inserts 3 null)
'((3))
> (inserts 3 (list 5 3 1))
'((3 5 3 1) (5 3 3 1) (5 3 3 1) (5 3 1 3))``````

Notes:

• The `map-cons` function from above is useful here.
• Think very carefully about the base case and the combination function for the recursive case.
9. (15 points) Define a function `my-permutations` that takes as its single argument a list `xs` of distinct elements (i.e., no duplicates) and returns a list of all the permutations of the elements of `xs`. The order of the permutations does not matter.

`````` > (my-permutations null)
'(())
> (my-permutations (list 4))
'((4))
> (my-permutations (list 3 4))
'((3 4) (4 3)) ; order doesn't matter
> (my-permutations (list 2 3 4))
'((2 3 4) (3 2 4) (3 4 2) (2 4 3) (4 2 3) (4 3 2))
> (my-permutations (list 1 2 3 4))
'((1 2 3 4) (2 1 3 4) (2 3 1 4) (2 3 4 1)
(1 3 2 4) (3 1 2 4) (3 2 1 4) (3 2 4 1)
(1 3 4 2) (3 1 4 2) (3 4 1 2) (3 4 2 1)
(1 2 4 3) (2 1 4 3) (2 4 1 3) (2 4 3 1)
(1 4 2 3) (4 1 2 3) (4 2 1 3) (4 2 3 1)
(1 4 3 2) (4 1 3 2) (4 3 1 2) (4 3 2 1))``````

Notes:

• We ask you to name your function `my-permutations` because Racket already provides the same function named `permutations` (which you cannot use, of course).
• In this problem, you are allowed to use one or more recursive helper functions.
• Although the specification allows the permuted elements to be listed in any order, the above examples show an order that works particularly well with the divide/conquer/glue strategy. In particular, study the above examples carefully to understand (1) the recursive nature of `my-permutations` and (2) why the `inserts` function from above is helpful to use when defining `my-permutations`.
• In the example `(my-permutations (list 1 2 3 4))`, the 24 results would normally be printed by Racket in 24 separate lines, but here they have been formatted to strongly sugggest a particular solution strategy.

Extra Credit: Permutations in the Presence of Duplicates (15 points)

This problem is optional. You should only attempt it after completing all the other problems.

Define a version of the `my-permutations` function named `my-permutations-dup` that correctly handles lists with duplicate elements. That is, each permutation of such a list should only be listed once in the result. You should not generate duplicate permutations and then remove them; rather, you should just not generate any duplicates to begin with. As before, the order of the permutations does not matter.

``````    > (my-permutations-dup (list 2 1 2))
'((1 2 2) (2 1 2) (2 2 1)) ; order doesn't matter
> (my-permutations-dup (list 1 2 1 2 2))
'((1 1 2 2 2) (1 2 1 2 2) (1 2 2 1 2) (1 2 2 2 1)
(2 1 1 2 2) (2 1 2 1 2) (2 1 2 2 1)
(2 2 1 1 2) (2 2 1 2 1) (2 2 2 1 1)) ; order doesn't matter ``````