Problem Set 9

This is the honors version of Problem Set 9.

Purpose This problem set concerns the use of accumulators to solve various problems, especially those relating to graphs.

Finger Exercises HtDP/2e: 264, 265, 266, 267, 268, 276, 279, 282, 321, 323

Problem 1 Design the function make-palindrome which consumes a String and constructs a palindrome by mirroring it around the last letter (if there is one). For example, (make-palindrome "fundies") should produce "fundieseidnuf" and (make-palindrome "") should produce "".

Problem 2 Design the function is-palindrome? which determines if a String is a palindrome. Note that there are palindromes that don’t look like the ones produced by make-palindrome, such as "abba".

Problem 3 Design a data definition for a network of Twitter users. A Twitter user should have a handle (or name) and tweeps (or followers).

Problem 4 Create an interesting example of a Twitter network, where interesting means it has at least 5 users and there are people who follow each other.

Problem 5 Design the function any-friends? and determines if any two people in the network follow each other.

Problem 6 Design the function most-followers that outputs a list of handles of the people in a Twitter network with the most followers. The number of followers a person has should only be computed once.

Problem 7 Design the function can-see-tweets? that determines if one Twitter user can see the tweets of another. A Twitter user can see the tweets of another if they follow them or if they follow someone who can see their tweets (and then, in theory, retweet). Beware of cycles!

For this set of problems, use the following data definition for graphs.

Problem 8 Design the function same-graph?

; same-graph? : [Graph X] [Graph X] -> Boolean

; Determines whether g1 and g2 have the same nodes,

; and each node in g1 has the same neighbors as that node in g2.

; Both graphs must have the same node=? function.

(define (same-graph? g1 g2) ...)

; Example tests

(check-expect  (same-graph? (make-graph '(a) (lambda (x) '()) symbol=?)

(make-graph '() (lambda (x) '()) symbol=?))

false)

(check-expect (same-graph? (make-graph '(a) (lambda (x) '()) symbol=?)

(make-graph '(a) (lambda (x) '()) symbol=?))

true)

(check-expect (same-graph? (make-graph '(b) (lambda (x) '()) symbol=?)

(make-graph '(a) (lambda (x) '()) symbol=?))

false)

(check-expect (same-graph? (make-graph '(a b) (lambda (x) '()) symbol=?)

(make-graph '(b a) (lambda (x) '()) symbol=?))

true)

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

(lambda (x)

(cond

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

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

symbol=?)

(make-graph '(a b)

(lambda (x)

(cond

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

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

symbol=?))

false)

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

(lambda (x)

(cond

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

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

symbol=?)

(make-graph '(a b)

(lambda (x)

(cond

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

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

symbol=?))

true)

Take special note of the last test. It implies the ordering of the list returned by a graph’s neighbors is irrelevant. What helper function will you need to write?

Problem 9 Design the following function and use same-graph? to test it.

; reverse-edge-graph : [Graph X] -> [Graph X]

; Build a graph with the same nodes as g, but with reversed edges.

; That is, if g has an edge from a to b then the result graph will

; have an edge from b to a.

(define (reverse-edge-graph g) ...)

Problem 11 Design the function find-paths.

; find-paths : [Graph X] X X -> [Listof [Listof X]]

; Find all of the paths in the graph from src to dest

(define (find-paths g src dest) ...)

Note that input graphs may contain cycles. Make sure that your code can handle cycles in the graph and doesn’t loop forever. Below are some tests to clarify what we expect.

They are not given as check-expects for a specific reason: while the order of the elements in a path is obviously crucial, the order of the paths returned when there is more than one path is irrelevant. Be sure you test in a flexible enough way that the check-expect should pass independent of the order of the list of paths returned by find-paths but still makes sure the paths themselves are in the right order.

(define G1

(make-graph '(A B C D E F G)

(lambda (n)

(cond [(symbol=? n 'A) '(B E)]

[(symbol=? n 'B) '(E F)]

[(symbol=? n 'C) '(D)]

[(symbol=? n 'D) '()]

[(symbol=? n 'E) '(C F A)]

[(symbol=? n 'F) '(D G)]

[(symbol=? n 'G) '()]))

symbol=?))

(find-paths G1 'C 'C) -> '((C)) ; src = dest

(find-paths G1 'C 'G) -> '() ; no paths from 'C to 'G

(find-paths G1 'A 'B) -> '((A B))

(find-paths G1 'E 'G) -> '((E F G)  (E A B F G))

(find-paths G1 'B 'G) -> '((B E F G)  (B F G))

(find-paths G1 'A 'G) -> '((A B E F G) (A B F G) (A E F G))

Sometimes same-graph? is too restrictive. Sometimes we’re just curious if two graphs have the same shape. Your task is to design the function same-shape?, which determines if two [Graph X] with the same node=? function have the same shape.

With the above two functions, same-shape will be a relatively short function. permutations will test your recursion skills, whereas rename will test your higher-order programming skills.

Enjoy!