|
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.
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!.
Write a procedure (remove! key table) that removes the record associated with key from the given table. If the table does not contain a record corresponding to the key your procedure should return #f.
> (define T (make-table)) > (insert! 'a 1 T) > (insert! 'b 2 T) > T (*table* (b . 2) (a . 1)) > (remove! 'b T) > T (*table* (a . 1)) > (remove! 'a T) > T (*table*)
Write a version of map that works on tables called (table-map f table). This procedure should return a table with the same keys as the input table, but with f applied to each argument.
> (define T (make-table)) > (insert! (quote a) (list 1 2 3) T) > (insert! (quote b) (list) T) > (insert! (quote c) (list 4 5) T) > T (*table* (c 4 5) (b) (a 1 2 3)) > (table-map length T) (*table* (c . 2) (b . 0) (a . 3)) > (table-map null? T) (*table* (c . #f) (b . #t) (a . #f))
Many implementations of Scheme have a builtin in procedure (map! f lst) that is analogous to map, but instead of returning a new list with f applied to each element, it uses set-car! to make these changes on the input list. Write this procedure, it should work as follows.
> (define lst1 (list 1 4 9 16)) > (map sqrt lst1) (1 2 3 4) > lst1 (1 4 9 16) ;; unchanged by map > (map! sqrt lst1) () > lst1 (1 2 3 4) ;; changed by map!
> (define T (make-table)) > (insert! (quote a) (list 1 2 3) T) > (insert! (quote b) (list) T) > (insert! (quote c) (list 4 5) T) > T (*table* (c 4 5) (b) (a 1 2 3)) > (table-map! length T) > T (*table* (c . 2) (b . 0) (a . 3)) > (table-map! 1+ T) > T (*table* (c . 3) (b . 1) (a . 4))
> (define T (make-table)) > (insert! 'a 4 T) > (insert! 'b 5 T) > (insert! 1 10 T) > (insert! 2 'foo T) > T (table (2 . foo) (1 . 10) (b . 5) (a . 4)) > (table-filter number? T ) (table (2 . foo) (1 . 10))
(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))))))))
(fib 30)
and
(memo-fib 30)
.
Did you notice a difference in the time to compute them? 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
.
memo-fib
.
What is the largest number for which you can compute memo-fib
?
Is this much larger than what you found for fib
?
memo-fib
computes the nth Fibonacci number in
a number of steps proportional to n instead of being exponential in n
as for fib
.
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.