Notes: Monday 26 January 2004

Schedule

• Wednesday, 28 January (needed for PS2): Read SICP, 1.3
• Monday, 2 February: Problem Set 2
• Wednesday, 4 February: Read SICP, 2.1 and 2.2 (through page 127). You don't need to read the example section 2.2.4, but probably don't want to miss the footnote on page 127 about William Barton Rogers, MIT's founder, who left UVa after too many students were rioting outside his pavillion.
• Before 10 March: Read rest of GEB part I (Chapters 2-4 and 6-9, in addition to Chapters 1 and 5 you have already read). There will be no more specific reading assignments from GEB until end of Spring Break (there will be other reading assignments from SICP). By March 10th, you will be expected to have read all of Part I (through page 272) of GEB. I recommend reading about a Chapter a week, but if you prefer to read it all over Spring Break that is fine too.

Recursive Definitions

1. Be optimistic.
   • Assume you can solve it.
   • If you could, how would you solve a bigger problem.
2. Think of the simplest version of the problem, something you can already solve. (This is the base case.)
3. Combine them to solve the problem.

(define (find-closest goal numbers)
   (if (= 1 (length numbers))
       (first numbers)
       (if (< (abs (- goal (first numbers)))
	      (abs (- goal 
		      (find-closest goal (rest numbers)))))
           (first numbers)
           (find-closest goal (rest numbers))))

Languages

How can we compare notations for describing languages?

What is the difference between RTN and BNF?

Music and Recursion

Song ::= Verse VBBD VBBD Better Coda
VBBD ::= Verse Bridge Bridge Dadada (ends on C)
Coda ::= F Eb Bb F Coda
Note: the Coda has no base case, and should continue forever (time permitting).

Challenge Problem
Define a Scheme procedure that can produce the INT and Gplot graphs from GEB Chapter 5. Hint: you may need to think about curves differently from PS2. (A solution is worth two gold stars.)

Links

• Listen to Bach's Little Harmonic Labyrinth (MIDI file); More GEB Music from VCU course
• GNU's Not Unix (GOD Over Djinn-like acronym)
• The Story of Benoit B. Mandelbrot and the Geometry of Chaos

Hofstadter's Law: It always takes longer than you expect, even when you take Hofstadter's Law into account.
CS200 Law: Problem Sets always take longer than you expect, even when you take the CS200 Law into account.