CSci 1901: Lab 11, April 5

Game Project
If you are interested in the game project discussed in class, please sign up on the sheet your TA will pass around. Any questions may be referred to Richard.


Lab 11 Template

Review the table procedures, insert!, assoc, and lookup from the book before starting this lab. You will need to understand them to write similar table procedures for this lab. You should also review set-car! and set-cdr!.

Bonus Questions

[This is from Exercise 3.27 from the textbook] Memoization (also called tabulation) is a technique that enables a procedure to record, in a local table, values that have previously been computed. This technique can make a vast difference in the performance of a program. A memoized procedure maintains a table in which values of previous calls are stored using as keys the arguments that produced the values. When the memoized procedure is asked to compute a value, it first checks the table to see if the value is already there and, if so, just returns that value. Otherwise, it computes the new value in the ordinary way and stores this in the table. As an example of memoization, recall from section 1.2.2 the exponential process for computing Fibonacci numbers:
(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1)) (fib (- n 2))))))
We define the memoizer as
(define (memoize f)
  (let ((table (make-table)))
       (lambda (x)
	       (let ((previously-computed-result (lookup x table)))
		    (or previously-computed-result
			(let ((result (f x)))
			     (insert! x result table)
			     result))))))
The memoized version of the fibonacci procedure is
(define memo-fib
  (memoize (lambda (n)
		   (cond ((= n 0) 0)
			 ((= n 1) 1)
			 (else (+ (memo-fib (- n 1))
				  (memo-fib (- n 2))))))))
  1. 1 Bonus Point Using the code above compute (fib 30) and (memo-fib 30). Did you notice a difference in the time to compute them?
  2. 1 Bonus Point Now compute fib for increasingly larger numbers. Stop when the computation takes approximatively more than 1 minute. Write down the largest number for which you computed fib.
  3. 1 Bonus Point Repeat the same process as in the previous step but this time using memo-fib. What is the largest number for which you can compute memo-fib? Is this much larger than what you found for fib?
  4. 1 Bonus Point Explain why memo-fib computes the nth Fibonacci number in a number of steps proportional to n instead of being exponential in n as for fib.
  5. 1 Bonus Point Would memo-fib still work if we had simply defined memo-fib to be (memoize fib)? Why or why not? explain your reasoning.

Congratulations on completing Lab 11!
Lab 11 total: 10 pts

Copyright: © 2006 by the Regents of the University of Minnesota
Department of Computer Science and Engineering. All rights reserved.
Comments to: Maria Gini
Changes and corrections are in red.