 Problem Set 10h  
Due date: 12/5 @ 11:59pm Programming Language: Intermediate Student Language with lambda
AccumulatorsDesign the following functions using an accumulator. Exercise 1: ;; posnsum : [Listof Posn] > Posn ;; Compute a posn whose x coordinate is the sum of the x coordinates in ps ;; and whose y coordinates is the sum of the y coordinates in ps (define (posnsum ps) ...) Exercise 2: ;; A Digit is a Number in the range [09] ;; digits>num : [Listof Digit] > Number ;; Compute the number represented by the list of digits (define (digits>num ds) ...) ;; Examples: (digits>num (list 1 2 3)) > 123 (digits>num empty) > 0 Exercise 3: Using the following data definition for a family tree, design the function below using an accumulator. ;; A FamilyTree is either: ;;  empty ;;  (makenode String FamilyTree FamilyTree) (definestruct node (name mom dad)) ;; second? : FamilyTree > Boolean ;; Determine if any child has the same name as an ancestor of theirs. (define (second? ft) ...) GraphsFor this set of problems, use the following data definition for graphs. ;; A [Graph X] is: ;; (makegraph [Listof X] [X > [Listof X]] [X X > Boolean]) (definestruct graph (nodes neighbors node=?)) Exercise 4:
Design the function ;; findpaths : [Graph X] X X > [Listof [Listof X]] ;; Find all of the paths in the graph from src to dest (define (findpaths 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. (define G1 (makegraph '(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=?)) (checkexpect (findpaths G1 'C 'C) (list (list 'C))) ; src = dest (checkexpect (findpaths G1 'C 'G) empty) ; no paths from 'C to 'G (checkexpect (findpaths G1 'A 'B) (list (list 'A 'B))) (checkexpect (findpaths G1 'E 'G) (list (list 'E 'F 'G) (list 'E 'A 'B 'F 'G))) (checkexpect (findpaths G1 'B 'G) (list (list 'B 'E 'F 'G) (list 'B 'F 'G))) (checkexpect (findpaths G1 'A 'G) (list (list 'A 'B 'E 'F 'G) (list 'A 'B 'F 'G) (list 'A 'E 'F 'G))) Exercise 5:
Design the function ;; samegraph? : [Graph X] [Graph X] > Boolean ;; Determine whether g1 and g2 have the same nodes, ;; and each node in g1 has the same neighbors as that node in g2. ;; Assume that both graphs have the same node equality function ;; and that this node equality function is symmetric. (define (samegraph? g1 g2) ...) ;; Examples (samegraph? (makegraph '() (lambda (x) '()) symbol=?) (makegraph '() (lambda (x) '()) symbol=?)) > true (samegraph? (makegraph '(a) (lambda (x) '()) symbol=?) (makegraph '() (lambda (x) '()) symbol=?)) > false (samegraph? (makegraph '(a) (lambda (x) '()) symbol=?) (makegraph '(a) (lambda (x) '()) symbol=?)) > true (samegraph? (makegraph '(b) (lambda (x) '()) symbol=?) (makegraph '(a) (lambda (x) '()) symbol=?)) > false (samegraph? (makegraph '(a b) (lambda (x) '()) symbol=?) (makegraph '(b a) (lambda (x) '()) symbol=?)) > true (samegraph? (makegraph '(a b) (lambda (x) (cond [(symbol=? x 'a) '(b)] [(symbol=? x 'b) '()])) symbol=?) (makegraph '(a b) (lambda (x) (cond [(symbol=? x 'b) '(a)] [(symbol=? x 'a) '()])) symbol=?)) > false (samegraph? (makegraph '(a b) (lambda (x) (cond [(symbol=? x 'a) '(a b)] [(symbol=? x 'b) '()])) symbol=?) (makegraph '(a b) (lambda (x) (cond [(symbol=? x 'a) '(b a)] [(symbol=? x 'b) '()])) symbol=?)) > true Exercise 6:
Design the following function and use ;; reverseedgegraph : [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 (reverseedgegraph g) ...) Exercise 7: Design the following function. ;; undirected? : [Graph X] > Boolean ;; Determine if each edge in g has a matching edge going the opposite direction (define (undirected? g) ...) RacketBot — Racket as a Chat User

last updated on Sun Dec 2 14:52:34 EST 2012  generated with Racket 