Homework 3 (Due Friday 2/5/2010 at 10:00am)

Submit your .ss and .txt files via OWL-Space. You will need to use the "Intermediate Language Level" to do Problem 18.1.15. You may use this language for the entire assignment if you choose.

Required problems:

• 14.2.4
  Note: Be sure to compare list searching with tree searching, as the problem states.
• 16.3.3
  • 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 is in addition to the size
    of its data.
• 17.1.2
• 17.6.1
  Do the problem as specified in the book.

*Extra Credit: 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 mergeshould be recursive (call itself) and it may need to deviate slightly from
the structural recursion template.

• 17.7.1
  Note: Make sure you understand section 14.4 before working on this problem. Use
  this data definition as a starting point:

         ; 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 (that is,
  expressions like

  (* (f (+ 15 x)) (g x))

  ). Be sure to include a function
  template with your solution.

• 18.1.5, parts 1, 4, & 5
• 18.1.15

Optional problem for extra credit:

• 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 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.

Access Permissions: (Please don't edit)

• Set ALLOWTOPICCHANGE = Main.TeachersComp210Group