Notes: Monday 16 February 2004

Schedule

• Now: Problem Set 4
• Monday, 23 February: Exam 1 (will be handed out on Friday, 20 February)
• Before Wednesday, 25 February's class: Read Neil DeGrasse Tyson, Science's Endless Golden Age. Neil DeGrasse Tyson is an astrophysicist who is director of the Rose Center for Earth and Space in New York. This short essay explains how what we know about the universe depends on orders of growth and Moore's law, and what skateboards, pierced belly buttons, and tattoos have to do with scientific progress.

Notes On Grounds Sorting

(define (insertl lst f stopval) 
   (if (null? lst) 
       stopval 
       (f (car lst) (insertl (cdr lst) f stopval)))) 

(define (find-best-hand lst)
  (if (null? lst)



(define (sort cf lst)
  (if (null? lst) lst
      (let ((best (find-best cf lst)))
        (cons best (sort cf (delete lst best))))))

;;; Evaluates to the list parameter with exactly one instance of el removed.
(define (delete lst el)
  (if (null? lst) (error "Element not found!")
      (if (eq? (car lst) el)
          (cdr lst)
          (cons (car lst) (delete (cdr lst) el)))))

Measuring Work

How do computer scientists measure work?

When are orders of growth a better way to measure work than clock time?

When is clock time a better way to measure work than orders of growth?

If our simple sort has expected work Θ(n²) and it takes 5 seconds to sort a list of length 1000, how long would you expect it to take to sort a list of length 4000?

Assuming Moore's Law continues to hold (computing power per dollar doubles every 18 months), if the longest list we can use simple sort to sort today is length 6000, how long a list should we be able to sort using the same code on the new lab machines in 2008?

The progress of invention and discovery of improvement and application is so rapid,
unceasing and continuous, that it would require a volume many times the size of the present,
to record, even in a summary fashion, all that transpires of scientific interest in the course of a single year.

David A. Wells, Annual of Scientific Discovery, 1852. (Quoted in Neil DeGrasse Tyson's essay.)