University of Virginia Computer Science
CS150: Computer Science, Fall 2005
 (none)
9 September 2005

CS150 Notes 8 (9 September 2005)

Upcoming Assignments

Schedule Update: Problem Set 4 will be handed out on Monday, September 19 and due on Monday, September 26. Exam 1 will be handed out on Friday, September 30 and due on Wednesday, October 5. (There is no class on October 3, which is Reading Day.)

Recursive Definitions

  1. Be optimistic.
  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 PS3. (A solution is worth two gold stars.)

Links

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

"); print ( $res[$first] ) ; print (""); ?>
CS 150: Computer Science
University of Virginia
 evans@virginia.edu
Using these Materials