Assignment 9

Due Date Tues 3/27 at 9pm

Purpose To demonstrate grasp of the course material by solving extremely difficult problems.

Graded Exercises

This entire assignment is extra credit. Not doing it will have no negative impact on your grade. Extra credit will be assigned per-exercise, so completing only some of the exercises is fine.

Exercise 1 Design cartesian-product, which takes a list of lists and returns a list of lists. The following test should pass:

(check-expect (cartesian-product '((0 1 2)  (3 4)))

'((0 3) (0 4) (1 3) (1 4) (2 3) (2 4)))

Given the lists '(0 1 2) and '(3 4), the function outputs a list of lists, each element of which contains two elements, where the first element came from the first list and the second came from the second list. The output is also in an order such that everything beginning with 0 comes first, and everything ending with 3 comes before all that ends with 4, provided the first element is equal. Now, for a more formal specification...

The cartesian product of lists L-1, L-2... L-n is defined as a list of lists where each inner list is of size n, where the kth element of a, a list in the output sequence, is from L-k. It is ordered in such a way that, if L-1 is the list x-1, x-2, x-3...x-y, all output lists beginning with x-1 appear before x-2, appear before x-3, etc. Then, within all lists that begin with x-1, the ordering is defined the same way, except with L-2 taking the part of L-1, and so on.

Here’s another example to illustrate:

(check-expect (cartesian-product '((a b) (red green blue) (hutt putt)))

'((a red hutt)

(a red putt)

(a green hutt)

(a green putt)

(a blue hutt)

(a blue putt)

(b red hutt)

(b red putt)

(b green hutt)

(b green putt)

(b blue hutt)

(b blue putt)))