Page History

...

Submit your .ss file via OWL-Space. You will need to use the "Intermediate Student" language to do Problem 18.1.15. If you want to use explicit lambda notation (anywhere the right hand side of a define statement), you will need to use the "Intermediate Student with lambda" language. You may use either intermediate level language for the entire assignment if you choose.

Required problems:

1. Wiki Markup14.2.4 \ [20 pts.\] *
   Note*: Be sure to compare list searching with tree searching, as the problem states. Wiki Markup
2. 16.3.3 \ [20 pts.\] *
   Notes*:
   1. Test every function thoroughly (5+ examples).
   2. Be sure to include definitions for both variations of du-dir. The final sentence should read "storing a file or a directory in a dir structure costs 1 storage unit." In other words, given a dir structure, each directory entry (a file or a directory) contained therein costs 1 unit of storage for the bookkeeping data. For a file, this bookkeeping overhead is in addition to the size of its data.
3. Wiki Markup17.1.2 \ [20 pts.\]unmigrated-wiki-markup
4. 17.6.1 \ [20 pts.\]
   Do the problem as specified in the book. *
   Extra Credit* \ [10 pts.\]: This problem can be solved more elegantly than the solution implied in the book. For the extra credit solution _ignore_ the book's guidance on "writing functions that consume two complex inputs" in 17.5 and follow the guidance given in class on how to write a function that processes multiple inputs. Select _one_ input as primary (the choice may be _arbitrary_ in some cases). If you need to deconstruct a second argument, do it in a _auxiliary_ function. Use only _one_ design template in each function. Hint for solving this problem: only your auxiliary function, which has a contract and purpose statement almost identical to {{merge}}, should be recursive (call itself directly or indirectly) and it may need to deviate slightly from the structural recursion template. The top level {{merge}} function is _not_ recursive. *
   Note* If you do the extra credit version of this problem, you do not need to write a solution as specified in the book. Wiki Markup
5. 17.7.1 \ [10 pts.\]
   Note: Make sure you understand section 14.4 before working on this problem. Use this data definition (which includes division an subtraction in addition to multiplication and addition) as a starting point:

   Code Block

   ; An expression is one of: ; - a number ; - a symbol ; - (make-mul e1 e2) where e1 and e2 are expressions ; - (make-add e1 e2) where e1 and e2 are expressions ; - (make-div e1 e2) where e1 and e2 are expressions ; - (make-sub e1 e2) where e1 and e2 are expressions ; given (define-struct mul (left right)) (define-struct add (left right)) (define-struct div (left right)) (define-struct sub (left right)) ; Examples ; 5 ; 'f ; (make-mul 5 3) ; (make-add 5 3) ; (make-div 5 3) ; (make-sub 5 3) ; Template for processing an expression #| ; exp-f : exp -> ... (define (exp-f ... a-exp ...) (cond [(number? exp) ... ] [(symbol? exp) ... ] [(mul? exp) ... (exp-f ... (mul-left exp) ...) ... (exp-f ... (mul-right exp) ...) ... ] [(add? exp) ... (exp-f ... (add-left exp) ...) ... (exp-f ... (add-right exp) ...) ... ] [(div? exp) ... (exp-f ... (div-left exp) ...) ... (exp-f ... (div-right exp) ...) ... ] [(sub? exp) ... (exp-f ... (sub-left exp) ...) ... (exp-f ... (sub-right exp) ...) ... ]))

   You are required to extend this definition to include applications, which are expressions like

   Code Block
   (f (+ 15 x)) (g y)

   Be sure to include a function template with your solution.unmigrated-wiki-markup
6. 18.1.5, parts 1, 4, & 5 \ [5 pts.\]
7. Wiki Markup18.1.15 \ [5 pts.\]

Wiki Markup*Optional problem for extra credit:* \ [50 pts\]
The fibonacci function fib is defined by the following rules (in Scheme notation):

(fib 0) = 1
(fib 1) = 1
(fib (+ n 1)) = (+ (fib n) (fib (- n 1)))

...