Notes: Monday 23 February 2004

Schedule

• Now: Exam 1
• 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.
• Friday, 5 March: Problem Set 5 (note: you have 2 extra days for PS5 from the original course schedule)
• Before 15 March: Read rest of GEB part I (Chapters 2-4 and 6-9, in addition to Chapters 1 and 5 you have already read).

Notes Upper bound O ("big-oh"): f(x) is O (g (x)) means there is a positive constant c such that c * f(x) < g(x) for all but a finite number of x values.

• x² is O (x²) — c = .5 works fine
• x² is O (x³) — c = 1 works fine
• x³ is not O (x²) — for any choice of c, once x gets big enough c * x³ > x²
  
• Time to do TuttleSort for a list of length n is O (n²) — the value of c depends on how fast our computer is

Lower bound Ω ("omega"): f(x) is Ω (g (x)) means there is a positive constant c such that c * f(x) > g(x) for all but a finite number of x values.

• x² is Ω (x²) — c = 2 works fine
• x² is not Ω (x³) — for any choice of c, once x gets big enough c * x² < x³
• x³ is Ω (x²) — for any choice of c, once x gets big enough c * x³ > x²
  
• Time to do TuttleSort for a list of length n is Ω (n²) — the value of c depends on how fast our computer is.

Tight bound Θ ("theta"): f(x) is Θ (g (x)) means that f(x) is O(g (x)) and f(x) is Ω (g (x)).

• x² is Θ (x²) since x² is O (x²) and x² is Ω (x²).
• x² is not Θ (x³) since x² is not Ω (x³)
• x³ is not Θ (x²) since x³ is not O (x²)
• Time to do Tuttlesort for a list of length n is Θ (n²) since it is O (n²) and Ω (n²).

Sorting Code Download: sorting.ss

(define (insertel cf el lst)
  (if (null? lst) (list el)
      (if (cf el (car lst))
	  (cons el lst)
	  (cons (car lst) (insertel cf el (cdr lst))))))

(define (insertsort cf lst)
  (if (null? lst) null
      (insertel cf (car lst) 
		(insertsort cf (cdr lst)))))

(define (filter f lst)
  (insertl (lambda (el rest) (if (f el) (cons el rest) rest))
	   lst null))

(define (quicksort cf lst)
  (if (null? lst) lst
      (append (quicksort cf (filter (lambda (el) (cf el (car lst))) (cdr lst)))
	      (list (car lst))
	      (quicksort cf (filter (lambda (el) (not (cf el (car lst)))) (cdr lst))))))

(define (sublist lst start end)
  (if (= start 0)
      (if (= end 0) null
          (cons (car lst) (sublist (cdr lst) start (- end 1))))
      (sublist (cdr lst) (- start 1) (- end 1))))

(define (first-half lst) (sublist lst 0  (floor (/ (+ 1 (length lst)) 2))))
(define (second-half lst)
  (sublist lst (floor (/ (+ 1 (length lst)) 2)) (length lst)))

(define (insertelh cf el lst)
  (if (null? lst) 
      (list el)
      (let ((fh (first-half lst))
	    (sh (second-half lst)))
	(if (cf el (car fh)) (append (cons el fh) sh)
	    (if (null? sh) (append fh (list el))
		(if (cf el (car sh))
		    (append (insertelh cf el fh) sh)                        
		    (append fh (insertelh cf el sh))))))))

(define (insertsorth cf lst)
  (if (null? lst) null
      (insertelh cf (car lst) (insertsorth cf (cdr lst)))))

(define (make-tree left el right) (list left el right))
(define (get-left tree) (first tree))
(define (get-element tree) (second tree))
(define (get-right tree) (third tree))
 
(define (insertel-tree cf el tree)
  (if (null? tree) (make-tree null el null)
      (if (cf el (get-element tree))
          (make-tree (insertel-tree cf el (get-left tree))
		     (get-element tree)
		     (get-right tree))
          (make-tree (get-left tree)
		     (get-element tree)
		     (insertel-tree cf el (get-right tree))))))

(define (extract-elements tree)
  (if (null? tree) null
      (append (extract-elements (get-left tree))
              (cons (get-element tree)
                    (extract-elements (get-right tree))))))

(define (insertsort-tree cf lst)
  (define (insertsort-worker cf lst)
    (if (null? lst) null
        (insertel-tree cf (car lst) 
                       (insertsort-worker cf (cdr lst)))))
  (extract-elements (insertsort-worker cf lst)))

I am also the student whose 6th grade home-room teacher wrote, "Less social involvement and more academic diligence is in order".
Neil deGrasse Tyson's Speech at the State Department to winners of the Presidential Awarded for Excellence in Mathematics and Science Teaching