- Work in pairs
- Switch roles often
- Follow the design recipe for
every problem.

## Generative Recursion Warm-up

Exercise 1:Design the function,power, that computes the first number to the power of the second number, usingmultiplication(i.e., youcannotuseexpt).;; power : Number Number -> Number ;; Compute n^m using '*' (define (power n m) ...) (power 2 5) ;==> 32The straight forward (iterative) solution works, but it's actaully not that fast. Remember these rules?

Well, we can use these ideas to write a (x^{y+1}=x^{y}*x

x^{y}=x^{y/2}*x^{y/2}much) faster algorithm for thepowerfunction.

Exercise 2:Writefast-powerthat uses the relationships mentioned above.Hint: You don't want to deal with fractional powers, since those are hard to compute. What do you want to do if you need to raise something to an odd power, then?Here's a bit of test code for your functions. The

time"function" is used to print the amount of time it takes DrScheme to evaluate an expression.

;; do-times : Number (X -> X) -> X ;; Returns a function that applies the given function N times (define (do-times n func) (cond [(= n 1) func] [else (local [(define n-1 (do-times (sub1 n) func))] (lambda (x) (func (n-1 x))))])) ;; Time your functions with 2^(2^(2^(2^2))) ;; We name the results so they don't get printed out... ((do-times 4 (lambda (s) (string-append "2^(" s ")"))) "2") (define p1 (time ((do-times 4 (lambda (n) (power 2 n))) 2))) (define p2 (time ((do-times 4 (lambda (n) (fast-power 2 n))) 2)))When you run the timings should notice a huge difference... if not, are you doing anything twice that you don't need to? Are you sure you have only whole numbers?

You should notice a huge difference... if not, are you doing anything twice that you don't need to? Are you sure you have only whole numbers?

Ask your friendly TA/Tutor if you can't figure it out.

Exercise 3:Design the function,change, that takes a list of Numbers (the values of coins in decreasing order) and computes a list of numbers that is the number of each coin needed to make the given amount of change (incents) using a reasonably small number of coins. So(0 0 0 82)is not an acceptable answer to the second example.

Hint: Usequotientandremainder. Also, study the first example... what does it tell you?

Note:Your solution probably will always use as few coins as possible in American currency. However, there are possible coinage systems that it'll be suboptimal for. Sadly, a general solution is rather slow and complicated.;; change : Number [listof Number] -> [listof Number] ;; Compute the number of each coin in 'coins' to be given ;; for the 'amt' of change needed ('amt' is in cents) (define (change amt coins) ...) (change 0 '(25 10 5 1)) ;==> '(0 0 0 0) (change 82 '(25 10 5 1)) ;==> '(3 0 1 2) (change 60 '(25 10 5 1)) ;==> '(2 1 0 0)## The Dragon Fractal...

For the next part of the lab you will be designing functions to draw (and iterate) an interesting fractal design called theDragon. This was used on the headings of chapters in the bookJurassic Park(if anyone is old enough to remember that...).We start off building a simple line drawing program. Then we'll combine pieces into the fractal's (generative) recursion.

First, a direction (Dir) is a String, one of:"left","right","up", or"down"

Exercise 4:Write the function,rotate-dir, that rotates a givenDir90 degreescounter-clockwise. (rotate to theleft). What are the four cases ofDirand what should you return?;; rotate-dir : Dir -> Dir ;; Rotate the given direction to the 'left' (counter-clockwise) (define (rotate-dir dir) ...)

Exercise 5:Write the function,rotate-dirs, that rotates all theDirs in a[listof Dir].Hint: Which loop function can you use?;; rotate-dirs : [listof Dir] -> [listof Dir] ;; Rotate all the given Dirs to the 'left' (counter-clockwise) (define (rotate-dirs lod) ...)

Exercise 6:Write the function,move-posn, that returns aPosnthat is the result of moving the givenPosnin the givenDir-ection, the given amount,amt.;; move-posn : Posn Dir Number -> Posn ;; Return the adjusted position (as a Posn) of the given Posn ;; moving the given amount in the given direction (define (move-posn posn dir amt) ...)

Exercise 7:Write the function,Here's some interactive stuff to test your functions... use the arrow keys to create a path (adraw-dirs, that draws lines given a list of directions (in order) starting at the givenPosninto the given scene.Hint: Use structural recursion here, and choose some constant amount formove-posn(say 5). You can uselineto create the lines, or there is another function in theimage.ssteachpack that adds a line to a given scene fromx1/y1tox2/y2, which for our purposes has the following contract:Here's the header for your function...`;; add-line : Scene Number Number Number Number Color -> Scene`

;; draw-dirs : [listof Dir] Posn Scene -> Scene ;; Draw lines following the given directions starting at posn into ;; the given Scene (any color you choose). (define (draw-dirs lod posn scn) ...)[listof Dir]). You can hitRto rotate all the points to the left.;; Screen Size... (define W 400) (define H 400) ;; Draw wrapper (define (draw w) (local ((define lst (reverse w))) (draw-dirs lst (/ W 2) (/ H 2) (empty-scene W H)))) ;; Key Handler (define (key w k) (cond [(or (key=? k "left") (key=? k "right") (key=? k "up") (key=? k "down")) (cons k w)] [(key=? k "r") (rotate-dirs w)] [else w])) ;; A World is a [Listof Dir] (big-bang empty (on-key key) (on-draw draw))

Now... We need to generate the fractal. Here's the pattern; the blue number is the number of iterations run.The algorithm takes a [listof Dir]and aNumberthat is theiterationsleft to be done. (To start the algorithm off we will pass it the list'(down), and the number of iterations we want).It goes like this:

- If
iteris 0, then leave the list alone- Otherwise, return a new list modified as follows:

- Rotate all the
Dirs from the old list- Reverse the rotated list (remember
(reverse ...)?)- Append the new reversed/rotated list on the end of the old list
- Recurse on the new list, and with one less
iter

Exercise 8:Write the function,Test your function out, starting with the listjurassicthat is a Scheme version of the algorithm above. You can use local todefineeach step separately, then it will be clear that your function follows the specification.;; jurassic: [listof Dir] Number -> [listof Dir] ;; Compute the next iteration of the Jurassic Fractal, given a [listof Dir] ;; and the number of iterations left. (define (jurassic lod iter) ...)'(down), using it to generate a[listof Dir]and draw it usingdraw-dirs.When you know it works, remove (or comment out) the old

big-bangcode and replace it with this:Hit the up/down arrows to in/de-crease the number of iterations run. Try changing the the color/size of the steps and other stuff to create better drawings.(define (draw w) (local ((define lst (jurassic '(down) w))) (draw-dirs lst (/ W 2) (/ H 2) (empty-scene W H)))) ;; Key Handler (define (key w k) (cond [(key=? k "up") (add1 w)] [(and (> w 0) (key=? k "down")) (sub1 w)] [else w])) ;; A World is a Number ;; interp: number of iterations (big-bang 0 (on-key key) (on-draw draw))## Graphs : An Introduction

A

Graphin computer science and mathematics is a general structure withVertices(orNodes) andEdges.One of the ways to represent a graph is as

Here's a possible data definition forAdjacency Lists, which tells us which Vertices are immediately adjacent a given Vertex.DirectedGraphs:;; A Graph is a [listof Adj] ;; An Adj is: ;; (make-adj String [listof String]) ;; where the String is the Vertex name, and the [listof String] ;; represents the Vertex's "outgoing" edges (define-struct adj (name edges)) ;; So... the following graph (define example-1 (list (make-adj 'X '(Y)) (make-adj 'Y '(Z)) (make-adj 'Z '()))) ;; Represents: X --> Y --> ZUse it in the following exercises...

Exercise 9:Write a quick template for functions that take Graphs.

Exercise 10:Write some Graph examples. In particular, write a representation of the graph in the image below. Each Vertex needs an adj...

Exercise 11:Write the functionedges, that returns the outgoing edges of a given Vertex. Raise anerrorif the Vertex name is not found.;; edges : Graph String -> [listof String] ;; Find the edges for the given Vertex name (define (edges g sym) ...)

Exercise 12:Here's a version ofFinally, we get tocontains?... write some tests for it and give it a nice general contract.;; contains? : ??? ;; Does the given list contain the given element based on the ;; comparison function? (define (contains? lox x same?) (ormap (lambda (x2) (same? x x2)) lox))Depth First Search(DFS). Below is a simple implementation, that returns the list of Vertex names from a Graph in DFS order, which is close to atopological sort, but here we don't include all the Vertices in the graph, and a few other minor differences.On my representation of the image above this call will return:;; DFS : Graph String -> [listof String] ;; Do a depth first search of a graph, return the topological ;; ordering of the Vertices, starting from 'start' (define (DFS g start) (DFS-help g start '())) ;; DFS-help : Graph String [listof String] -> [listof String] ;; Do a depth first search of a graph, ignoring Vertices that have ;; been seen already (define (DFS-help g next seen) (cond [(contains? seen next string=?) '()] [else (local [(define newseen (cons next seen)) (define (func n ret) (append ret (DFS-help g n (append ret newseen)))) (define rec (foldr func '() (edges g next)))] (cons next rec))]))Corresponding to the DFS of the green edges below. Note that changing the order of the edges changes the order of the results, but not the set of Vertices returned.(DFS example 'A) ;==> '(A B E C D))

Exercise 13:Write the functionreachable?, that determines whether or not there is a path between a pair of Vertices,n1andn2. I.e., if there is a path fromn1 -> n2or fromn2 -> n1.;; reachable? Graph String String -> Boolean ;; Is either Vertex reachable from the other? (define (reachable? g n1 n2) ...)

Challenge 1:Write the functionfully-connected?, that determines whether or not every Vertex in a Graph is reachable from every other Vertex.Hint: Loop it up!;; fully-connected? Graph -> Boolean (define (fully-connected? g) ...)

Challenge 2:TheDFSfunction is a little too specialized. In particular we don't know what the DFS path was from the starting Vertex to any other Vertex in the result list.Modify the

DFS/DFS-helpfunctions to return a[listof (list String [listof String])], where you return a list of the Vertex, together with the path from the start Vertex.