Orders of growth. O and Theta notation. Recursive factorial requires Theta(n) time and space, iterative factorial requires Theta(n) time, but only Theta(1) space (assuming that an integer can fit into a single register -- a questionable assumption!).
Fibonacci requires Theta(Phi^n) by the traditional algorithm, but only Theta(n) (again, ignoring the complexity of adding large integers) by the iterative rule.
Exercise 1.14, 1.15
Exponentiation. Standard recursive approach. Fast exp. Theta(log n) operations.
Exercise 1.16, 1.17
If time and interest permit, I recommend that you do 1.19 for your personal enjoyment and edification.
SICP 1.2.5, 1.2.6: GCD. Euclid's algorithm. Lame's theorem. Testing for primality: Divisor search (sqrt n bounded), Fermat test. Expmod.
Exercise 1.21, 1.25, 1.26
In class, I assigned 1.23, not having noticed that it required use of the a timing primative, and not having investigated DrScheme to determine whether it supports a timing primative. Well, it does.
(time <expr>)
evaluates <expr>, returning the value, while displaying elapsed system and wall-clock time in milliseconds. N.B., on the Mac, the underlying clock has a granularity of about 17 milliseconds.
Anyway, the problems that involve timing -- 1.22, 1.23, 1.24 -- are not required, although they are recommended for your general edification.
There will be no class on Friday, October 8th.