;; Don't forget to load long-sent early!!
(define-macro (utime form)
(let* ((t1 (butlast (exec "precisetime")))
(r (eval form))
(t2 (butlast (exec "precisetime"))))
(- t2 t1)))
;;
;; TODAY:
;; o Homework grading
;; o Start SPACE Complexity
;; o Recap Complexity
;;
;; HOMEWORK and PROJECT1:
;; o HW1.1 and 1.2 are graded -- 'glookup'
;; o Regrading sessions:
;; o Sign up in lab
;; o <50% : Half hour session
;; o 51-90% : 15 Minutes
;; o Prepare by looking at solutions.
;; o Ta Doing Homework:
;; o Who would come??
;; o Changes to Proj1 (very minor) on website.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; SPACE COMPLEXITY
;;
;; o Roughly: How does the memory required by
;; a process vary with the size of the input?
;;
;; o New terms:
;; o RECURSIVE Process:
;; Has a chain of deferred operations that
;; require memory to 'remember' them
;; o ITERATIVE Process:
;; No such chain.
;;
;; o NOTE: Recursive process != Recursive proc.
;;
;; o Can use same Theta bounds as with TIME:
;;
;; Choice 1: LINEAR SPACE
(define (1+ x) (+ 1 x))
(define (count sent)
(if (empty? sent)
0
(1+ (count (bf sent)))))
;; Process:
(count '(hello my name is jimmy pop))
(1+ (count '(my name is jimmy pop)))
(1+ (1+ (count '(name is jimmy pop))))
(1+ (1+ (1+ (count '(is jimmy pop)))))
(1+ (1+ (1+ (1+ (count '(jimmy pop))))))
(1+ (1+ (1+ (1+ (1+ (count '(pop)))))))
(1+ (1+ (1+ (1+ (1+ (1+ (count '())))))))
(1+ (1+ (1+ (1+ (1+ (1+ 0))))))
(1+ (1+ (1+ (1+ (1+ 1)))))
(1+ (1+ (1+ (1+ 2))))
(1+ (1+ (1+ 3)))
(1+ (1+ 4))
(1+ 5)
6
;; o A recursive process.
;;
;; o Roughly requires one "1+" invocation to
;; be remembered for each word in original
;; sentence.
;;
;; o Called LINEAR Space
;; Choice 2: CONSTANT Space
(define (count sent)
(define (count-help sent count-so-far)
(if (empty? sent)
count-so-far
(count-help (bf sent) (1+ count-so-far))))
(count-help sent 0))
(count '(hello my name is jimmy pop))
(count-help '(hello my name is jimmy pop) 0)
(count-help '(my name is jimmy pop) 1)
(count-help '(name is jimmy pop) 2)
(count-help '(is jimmy pop) 3)
(count-help '(jimmy pop) 4)
(count-help '(pop) 5)
(count-help '() 6)
6
;; o An iterative process.
;;
;; o Regardless of the size of the input,
;; count-help requires the same amount of
;; memory.
;;
;; o Called CONSTANT Space
;;
;; o Note: TIME != SPACE
;; Choice 3: POLYNOMIAL Space
;; Choice 4: EXPONENTIAL Space
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Peer Instruction 2: Think of a simple
;; algorithm that runs in a time other
;; than what we've seen and other than
;; in the reader ...
;;
;; Nah-
;;
;;
;; Re-write product using only HOP!
(define (prepend-every wd sent)
(if (empty? sent)
'()
(se (word wd '- (first sent))
(prepend-every wd (bf sent)))))
(prepend-every 'foo '(1 2 3))
(define (product se1 se2)
(if (empty? se1)
'()
(se (prepend-every (first se1) se2)
(product (bf se1) se2))))
(product '(1 2 3) '(a b c))
;;
;;
;; notice: Just two composed everys:
;;
;;
(define (prepend-every wd sent)
(every (lambda (y) (word wd '- y)) sent))
(define (product se1 se2)
(every (lambda (x) (prepend-every x se2))
se1))
(product '(a b c) '(1 2 3))
;; So, hook em up:
(define (product se1 se2)
(every (lambda (x)
(every (lambda (y)
(word x '- y))
se2))
se1))
(product '(a b c) '(1 2 3))
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Improvements in efficiency:
;;
;; o Not really important in 61a
;; o Example to get the feeling:
(define (pascal row col)
(cond ((= col 1) 1)
((= col row) 1)
(else (+ (pascal (- row 1) (- col 1))
(pascal (- row 1) col)))))
(pascal 7 4)
(+ (pascal 6 3)
(pascal 6 4))
(+ (+ (pascal 5 2)
(pascal 5 3))
(+ (pascal 5 3)
(pascal 5 4)))
(+ (+ (+ (pascal 4 1)
(pascal 4 2))
(+ (pascal 4 2)
(pascal 4 3)))
(+ (+ (pascal 4 2)
(pascal 4 3))
(+ (pascal 4 3)
(pascal 4 4))))
;; ...
;; What is the TIME complexity?
;; What is the SPACE complexity
(pascal 7 4)
(+ (pascal 6 3)
(pascal 6 4))
(+ (+ (pascal 5 2)
(pascal 5 3))
(pascal 6 4))
(+ (+ (+ (pascal 4 1)
(pascal 4 2))
(pascal 5 3))
(pascal 6 4))
;; o Roughly: For each N, interpreter has to
;; remember 2 additions and 2 recursive calls.
;;
;; o LINEAR SPACE!
;; o Why is Pascal so slow?
;;
;; o How can we improve it?
;; 1. Compute row-by-row from top
;; 2. Remember values once we compute them
;; Recap TIME COMPLEXITY
;; o Finding BigTheta bounds for various functions
;; o Finding g such that f is bounded from above
;; and below by g.
;; o g is very important
;; o c1, c2, N are not (as much)
;;
;; o Classes for g:
;; g(x) = 1 : BTheta(1) : Constant Time
;; g(x) = x : BTheta(N) : Linear Time
;; g(x) = x^2 : BTheta(N^2) : Quadratic Time
;; g(x) = 2^x : BTheta(2^N) : Exponential Time
;;
;; o Note: This N is not the N is the definition.
;; Complexity FAMILIES:
Easy
----
1
log n
sqrt(n)
N
Examples: Searching, selecting, mapping, etc.
Medium
------
N log N
N^2
N^c
Examples: Sorting, matrix multiply,
Intractible:
------------
x^n
n!
n^n
Examples: The np-hard class, TSP.