Homework 3 (Due Monday 2/7/2011 at 10:00am)
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:
Wiki Markup |
---|
14.2.4 \[20 pts.\]
*Note*: Be sure to compare list searching with tree searching, as the problem states. |
Wiki Markup |
---|
16.3.3 \[20 pts.\]
*Notes*: |
- Test every function thoroughly (5+ examples).
- 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.
Wiki Markup |
---|
17.1.2 \[20 pts.\] |
Wiki Markup |
---|
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 |
---|
17.7.1 \[10 pts.\]
Note: Make sure you understand section 14.4 before working on this problem. Use this data definition as a starting point: |
Code Block |
---|
; expression
; 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
|
You are required to extend this definition to include applications, which are expressions like Code Block |
---|
(f (+ 15 x))
(g x)
|
Be sure to include a function template with your solution. Wiki Markup |
---|
18.1.5, parts 1, 4, & 5 \[5 pts.\] |
Wiki Markup |
---|
18.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): |
Code Block |
---|
(fib 0) = 0
(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
.