;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; Sample Final Problems Written by the CS3 TAs ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;; ;;; QUESTION 1 (aj) ;;;;;;;;;;;;;; ;;deep recursion problem ;COUNT-SUBLISTS takes a list as an argument and returns the number of ;sublists (lists within lists) in the input list. ;(count-sublists '(cs3 is cool)) ==> 0 ;(count-sublists '((cs3) is (cool))) ==> 2 ;(count-sublists '(((cs3 is) really) ((cool)))) ==> 4 ;Fill in the blanks in the following definition of COUNT-SUBLISTS: (define (count-sublists L) (cond ((null? L) __________) ((list? __________) ______________________________ (else ______________________________))) ;solution: (define (count-sublists L) (cond ((null? L) 0) ((list? (car L)) (+ 1 (count-sublists (car L))(count-sublists (cdr L)))) (else (count-sublists (cdr L))))) ;;;;;;;;;;;;;; ;;; QUESTION 2 (aj) ;;;;;;;;;;;;;; ;;Tail Recursion/Recursion with Lists Question ;The function FILL-IN-THE-BLANKS takes two equal length lists: a list ;with "blanks" and a list of words. It returns the result of ;replacing each blank in the first list with the corresponding word in ;the second list. ;(fill-in-the-blanks '(i like blank and blank) ; '(pizza 12 chips you dip)) ; ==> (i like chips and dip) Fill in the blanks in FILL-IN-THE-BLANKS so that it correctly works as described. (Note: No joke intended, this was originally gonna be a 'fix the bug' question.) (define (fill-in-the-blanks blanks-list word-list) (fill-helper _______________ _______________ _______________)) (define (fill-helper blanks-list word-list list-so-far) (cond ((null? blanks-list) ____________________) ((equal? (car blanks-list) 'blank) (fill-helper ______________________________ ______________________________ ______________________________)) (else (fill-helper ______________________________ ______________________________ ______________________________)))) ;SOLUTION: (define (fill-in-the-blanks blanks-list word-list) (fill-helper blanks-list word-list '())) (define (fill-helper blanks-list word-list list-so-far) (cond ((null? blanks-list) list-so-far) ((equal? (car blanks-list) 'blank) (fill-helper (cdr blanks-list) (cdr word-list) (append list-so-far (list (car word-list))))) (else (fill-helper (cdr blanks-list) (cdr word-list) (append list-so-far (list (car blanks-list))))))) ;;;;;;;;;;;;;; ;;; QUESTION 3 (ac) ;;;;;;;;;;;;;; Suppose you have a bunch of points on a plane. You can represent a point by a distinct letter. A point can be linked to another point by having the pair (source, destination). For example, the pair (a, b) means that you can get from a to b, but NOT VICE VERSA. Each link is unidirectional. Given, a list of links, we would like to determine if there is a path from a certain source point to a certain destination point. For example, given the list '((b c) (a b) (c d) (d z)), it is possible to go from a to d (by first going through (a b), then (b c), then (c d). Write a function pathposs that returns #t if there is a path from the source point to the destination point, and false otherwise. We have defined helper functions for you : (define (direct-path-exists paths src dest) (not (null? (filter (lambda (x) ( and (equal? (car x) src) (equal? (cadr x) dest))) paths)))) (define (pairs-starting-with paths src) (filter (lambda (link) (equal? (car link) src)) paths)) (define (remove-starting-with paths src) (filter (lambda (link) (not (equal? (car link) src))) paths)) (define (get-destinations paths) (map cadr paths)) THE SOLUTION (define (pathposs paths src dest) (cond ((null? paths) #f) ((direct-path-exists paths src dest) #t) ((null? (pairs-starting-with paths src)) #f) (else (not (null? (filter (lambda (mid-node) (pathposs (remove-starting-with paths src) mid-node dest)) (get-destinations paths))))))) ;;;;;;;;;;;;;; ;;; QUESTION 4 (cr) ;;;;;;;;;;;;;; (define (reference nums letters) (accumulate word (every (lambda (n) (item n letters)) nums))) (define (arg1 num letters) (display num) (newline) (display letters) (newline) (reference (+ 3 num) letters)) (define (something n) (cond ((number? n) #t) ((word? n) (display n) n) (else #f))) (define (lastcs3question x y) (if (= y 0) (begin (newline) 'finished!) (begin (and (something 42) (something '(a)) (something 'something)) (or (something x) (something y) (something x)) (lastcs3question (bf x) (- y 1))))) Write out exactly what you would see if you typed the following line in. You may simply write "procedure" if Scheme is asked to display a procedure and "error" if Scheme would give an error. (lastcs3question (arg1 431529 'alews) (count (arg1 431529 'alews))) ;;; ANSWER 431529 alews 431529 alews weaseleaselaselselell finished! ;;;;;;;;;;;;;; ;;; QUESTION 5 (dr) ;;;;;;;;;;;;;; Biologists around the distant planet Narn have recently discovered a new form of life in one of the many pools that dot the surface. They've found that the creatures have a kind of DNA that's a little more twisted than our own. For lack of a better imagination, they've termed it, Alien DNA, or "A-DNA" for short. Unlike human DNA, A-DNA is a tree structure that can represent several different strands at the same time. For example: a / | \ a t g | / \ g c a is a piece of A-DNA that represents 4 different linear strands of human DNA: ( (a a g) (a t) (a g c) (a g a) ) A strand is a path from the root of the tree, down to the leaves. Write a program, untwist-a-dna, that takes an A-DNA tree, and returns back a list of all strands in that tree. ;;;;;; Solution: ;;; Given a tree of alien dna, returns a list of all possible strands ;;; of that tree. (define (untwist-a-dna dna-tree) (if (leaf? dna-tree) (list (list (datum dna-tree))) ;; Tricky, but necessary base ;; case. (let ((head (datum dna-tree)) (children-strands (mappend unravel-alien-dna (children dna-tree)))) (map (lambda (strand) (cons head strand)) children-strands)))) ;;; Returns a mapping append of F on L. This combines the operation of ;;; mapping, and appending the results all together. Particularly useful ;;; if the function returns a list. ;;; ;;; For example: ;;; (mappend (lambda (x) (list x x)) '(1 2 3)) ;;; ==> '(1 1 2 2 3 3) (define (mappend function L) (apply append (map function L))) ;;;;;; ;;;;;;;;;;;;;; ;;; QUESTION 6 (pa) ;;;;;;;;;;;;;; In the mightly land of Scheme lived a good King emeschay and his supporters. The society was composed of a hierarchical system lords over the knights over the soldiers. One day King emeschay decided that he was fed up with royalty and decided to turn over his power to democracy. So he declared all men to be equal..... this led to a redefinition of society .... STEP 1 help King emeschay by trnaslating his hierarchy tree into a list (king emeschay) | ---------------------------------- | | (lord ripley) (lord cromwell) | ------------------------- | | (knight lawrence) (kinght livermoore) | ---------------------------- | | (soldier smith) (soldier smith) ;; Note -- this is a deep-recursion question, not a tree question. ;; this hierarchy tree wasn't necessarily constructed using the ;; tree interface (define *kingdom* '((king emeschay) ((lord ripley) ((knight lawrence) (soldier smith) (soldier smith)) (knight livermoore) ((lord cromwell))))) Step 2: make all men equal HINT -- YOU WILL NEED THEM TO PERFORM TWO ACTIONS 1. TO FLATTEN THE LIST 2. TO REMOVE ALL TITLES INDEPENDENTLY BOTH ARE QUITE EASY .... BUT THE PROBLEM REQUIRES YOU TO PUT THEM TOGETHER. Example: : (make-all-men-equal *kingdom*) ==> (emeschay ripley lawrence smith smith livermoore cromwell) ;; the order doesn't matter above (define (make-all-men-equal tree) ) (define (flatten-list deep-l) ) ;;;;;;;;;;;;;; ;;; QUESTION 7 (am) ;;;;;;;;;;;;;; ;; This problem concerns binary trees -- assume you use the make-tree ;; constructor but always have 0 or 2 children at each node. (define (Rbranch L) (cadr L)) (define (Lbranch L) (caddr L)) (define (bare-branch? L) (null? L)) (define (balanced-tree? T) (balanced-childred? (Rbranch T) (Lbranch T))) (define (balanced-children? b1 b2) (if (and (bare-branch? b1) (bare-branch? b2)) #t (and (balanced-tree? b1) (balanced-tree? b2))))) a) I decide to make a call to balanced-tree?. It goes like this: (balanced-tree? '(a (b (c () ()) ()) (d () ()))) It should return #f, but instead my program crashes. where should I make a change so that it doesn't crash? b) I run a different call: (balanced-tree? '(a (b () ()) (c (d () ()) (e () ())) and it returns #t. In a sentence or two, describe why the program isn't working and what you WOULD make a change to the program if you had to. ANSWERS: a) (define (balanced-children? b1 b2) (cond ((and (bare-branch? b1) (bare-branch? b2)) #t) ((or (bare-branch? b1) (bare-branch? b2)) #f) (else (and (balanced-tree? b1) (balanced-tree? b2))))) b) It doesn't work because we're only checking if each individual tree is balanced. Not if the two balance each other. ;;;;;;;;;;;;;; ;;; QUESTION 8 (ch) ;;;;;;;;;;;;;; (define (cat arg (cond ((= n 0) 'puppy) ((odd? n) (display arg) (cat arg (- n 1))) (else (display arg) (newline) (cat arg (- n 1)) 'frog))) A) Show exactly what is displayed to the screen for (cat 'mouse 1) B) Show exactly what will be displayed for (cat 'mouse 2) C) How many times will "puppy", "frog", and "mouse" appear for (cat 'mouse 20) ? puppy________ frog_________ mouse________ D) How many lines would be printed on the screen for (cat 'mouse 20) ? ANSWERS : (cat 'mouse 1) mousepuppy : (cat 'mouse 2) mouse mousefrog : (cat 'mouse 20) mouse mousemouse mousemouse mousemouse mousemouse mousemouse mousemouse mousemouse mousemouse mousemouse mousefrog (for even n (+ 1 (/ n 2)) lines are printed) ;;;;;;;;;;;;;; ;;; QUESTION 9 (ch) ;;;;;;;;;;;;;; (define (mystery x y) (if (= x 1) (helper y) (cons (mystery (- x 1) y) (helper (- y 1))))) (define (helper n) (if (= n 1) (cons nil nil) (cons nil (helper (- n 1))))) A) What does (mystery 2 2) return? ANS: ((() ()) ()) B) Draw the box-and-pointer diagram for (mystery 3 3) ANS: C) Describe what the box-and-pointer diagram would look like for (mystery 100 100) ANS: 100 rows by 100 columns (a filled in square) ;;;;;;;;;;;;;;; ;;; QUESTION 10 (ch) ;;;;;;;;;;;;;;; Two functions are given (Version A and Version B), only one of which would be used on the exam (two are presented for choice only) Sample calls: (deep-same-shape '(dog) '(cat dog)) ;#f (deep-same-shape '(dog) '(cat)) ;#t (deep-same-shape '(dog) '((cat))) ;#f (deep-same-shape '(a (b ((c)) d)) '(e (f ((g)) h))) ;#t (deep-same-shape '((a very) big (cat)) '((in) my (hat))) ;#f (deep-same-shape '(1 (2 (3)) 4) '(5 6 (7 (((8))) 9))) ;#f Version I (define (deep-same-shape L1 L2) 1 (cond ((not (equal? (length L1) (length L2))) #f) 2 ((and (null? L1) (null? L2)) #t) 3 ((or (list? L1) (list L2)) 4 (and (deep-same-shape (car L1) (car L2)) 5 (deep-same-shape (cdr L1) (cdr L2)))) 6 (else #f))) Version II (define (deep-same-shape L1 L2) 1 (cond ((not (equal? (length L1) (length L2))) #f) 2 ((and (and (null? L1) (null? L2)) 3 (and (not (list? L1)) (not (list? L2)))) 4 #f) 5 (else (and (deep-same-shape (car L1) (car L2)) 6 (deep-same-shape (cdr L1) (cdr L2)))))) A) (deep-same-shape '((cs3) is (great)) '((stanfurd) is (not))) results in an error, change one line so that it returns #f (which still isn't correct) ANS: Version I : line 3 should be ((and (list? L1) (list L2)) Version II: line 2 should be ((or (and (null? L1) (null? L2)) B) Assume you've made the change in A), now make one additional change so that the code will return #t for the above call and work for all cases. ANS: Version I : line 6 should be (else #t) Version II: line 4 should be #t) ;;;;;;;;;;;;;;; ;;; QUESTION 11 (dg) ;;;;;;;;;;;;;;; Assume you are given a primitive (draw-square Cx Cy r) ...which draws a square centered at Cx and Cy with sides of length 2r (r is the distance from the center to the nearest edge -- r makes more semantic sense if the procedure is draw-circle). You want to write a procedure square-corner which takes a center, a r and a level, and creates a fractal whose base case (level = 1) is a square. At every recursive level after that, you want to first draw a square, then place four 1/2-sized reduced recursive-calls to square on the outside corners of your current square so that the corners line up. Example: (square-corner 0 0 100 1) +----+ | | | | | | | | +----+ (square-corner 0 0 100 2) +--+ +--+ | | | | | | | | +--+----+--+ | | | | | | | | +--+----+--+ | | | | | | | | +--+ +--+ A) Draw the result of calling square-corner with level = 3 B) Write square-corner C) How many squares are drawn with level = 4 ?