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:
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.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.; 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) ...) ... ])) |
(f (+ 15 x)) (g y) |
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))) |
A naive program for computing fib
(lifted directly from the definition) runs in exponential time, i.e. the running time for (fib n)
is proportional to K*b**n
for some constants K
and b
). It is easy to write a program that computes (fib n)
in time proportional to n
. Your challenge is to write a program that computes (fib n)
in log time assuming that all multiplications and additions take constant time, which is unrealistic for large n
. More precisely, your program should compute (fib n)
using only O(
log
n)
addition and multiplication operations (less than K *
log
n
operations for some constant K
).
Hints: assume n = 2**m
. Derive a recurrence for fib 2**(m+1)
in terms of fib 2**m
and fib 2**(m-1)
. Initially write a program that works when n
is a power of 2. Then refine it to a program that works for all n
.
Note: in some definitions of fib
, fib(0) = 0
which slightly changes the recurrence equations but does not affect asymptotic complexity.