Assignment 23

Due Date Mon 4/17 at 11:59pm

Possible Points 60 extra credit points

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. Be warned the length of the exercise description is in no way correlated with level of difficulty.

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)))

Exercise 3 Recall the definition of a graph from assignment 18. Design the function same-shape?, which is similar to same-graph?, but is far less restrictive, as it doesn’t care about the names given to the nodes of the graphs. Otherwise, it should function the same way. You may assume the list of nodes in the graph and all of the lists returned by the neighbor function contain no duplicates.

To illustrate, here are some check-expects:

(check-expect (same-shape? (make-graph '(a b)

(lambda (x)

(cond

[(symbol=? x 'a) '(a b)]

[(symbol=? x 'b) '(a)])))

(make-graph '(b a)

(lambda (x)

(cond

[(symbol=? x 'b) '(a b)]

[(symbol=? x 'a) '(b)]))))

#true)

(check-expect (same-shape? (make-graph '(a b)

(lambda (x)

(cond

[(symbol=? x 'a) '(a)]

[(symbol=? x 'b) '()])))

(make-graph '(b a)

(lambda (x)

(cond

[(symbol=? x 'b) '(a)]

[(symbol=? x 'a) '()]))))

#false)

(check-expect (same-shape? (make-graph '(a b c)

(lambda (x)

(cond

[(symbol=? x 'a) '(a b c)]

[(symbol=? x 'b) '(a c)]

[(symbol=? x 'c) '(c)])))

(make-graph '(g f e)

(lambda (x)

(cond

[(symbol=? x 'e) '(e f g)]

[(symbol=? x 'f) '(e g)]

[(symbol=? x 'g) '(g)]))))

#true)