;; 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)))
;;
;; Week 2.1: EFFICIENCY and GROWTH
;;
;; o Processes: Recursion vs. Iteration
;; o Orders of Growth
;; o Time complexity
;; o Space complexity
;; Terms:
;; o Procedure : The formal "howto" for doing something
;; o Process : The actual steps an interpreter takes to
;; do something
;; o We say:
;; "A procedure generates/evolves a process"
;;
;; So, This is a procedure:
(define (1+ x) (+ 1 x))
(define (count sent)
(if (empty? sent)
0
(1+ (count (bf sent)))))
;; ... while this is the process generated
;; by 'count' on the input '(hello my name is jimmy pop):
(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
;;
;; Today, we'll discuss the general forms of PROCEDURES
;; in terms of the TIME and SPACE requirements of the
;; PROCESSES they generate.
;;
;; First, TIME:
;; o Roughly: For a given PROCEDURE, how will the time
;; of the PROCESS it generates vary as a function of
;; the size of the input?
;; o Mathematically:
;; f is BigTheta(g) iff
;; For some non-zero constants c1, c2, and n,
;; For all x > n,
;; c1 * g(x) <= f(x) <= c2 * g(x)
;; o In English:
;; Past a certain input size, f(x) is sandwiched by
;; c1*g(x) from below and c2*g(x) from above.
;; o Graphically:
;;
;; NOTE: 'x' can refer to the actual argument itself,
;; or the size of the argument (in characters or digits)
;;
;; NOTE: The bound expressed in the lecture notes is
;; actually 'Big Oh' -- big theta without the lower
;; bound.
;;
;; Examples:
(define (by-ones a b)
(if (> a b)
(se)
(se a (by-ones (+ 1 a) b))))
(define 10-sent (by-ones 1 10))
(define 33-sent (by-ones 1 33))
(define 34-sent (by-ones 1 34))
(define 50-sent (by-ones 1 50))
(define 100-sent (by-ones 1 100))
(define 1000-sent (by-ones 1 1000))
;;
;; How can the running time vary?
;;
;; Choice 1: CONSTANT TIME
;; o If the running time of the process
;; is independent of the size of the input
(define (second sent)
(first (bf sent)))
(utime (second 10-sent))
(utime (second 33-sent))
(utime (second 50-sent))
(utime (second 100-sent))
(utime (second 1000-sent))
;;
;; o The running time of second doesn't change
;; with the size of the sentence.
;;
;; o second is BigTheta(1):
;; set c1=
;; c2=
;; N=
;;
;; o BigTheta(1) has a special name: CONSTANT TIME
;;
;; o first, bf, are constant time algorithms.
;;
;;
;; Choice 2: Linear Time.
;; o If the running time grows at the same pace
;; as the size of the input
(define (square x) (* x x))
(define (squares sent)
(if (empty? sent)
(se)
(se (square (first sent))
(squares (bf sent)))))
(utime (squares 10-sent))
(utime (squares 33-sent))
(utime (squares 34-sent))
(utime (squares 50-sent))
(utime (squares 100-sent))
(utime (squares 1000-sent))
;;
;; o For each element in the sentence, we do one
;; 'square' and one recursive call.
;;
;; o squares is BigTheta(N):
;; set c1=
;; c2=
;; N=
;;
;; o BigTheta(N) has a special name: LINEAR TIME
;;
;; o last, butlast, every, keep,
;; are constant time algorithms.
;;
;;
;; Choice 3: POLYNOMICAL TIME
;; o When we have some sort of matrix of operations
;;
;; Example: cartesian product
(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 '(a b c) '(1 2 3))
(utime (product 10-sent 10-sent))
(utime (product 33-sent 33-sent))
(utime (product 34-sent 34-sent))
(utime (product 50-sent 50-sent))
;; o roughly quadratic:
;; access each element of se1 once, and,
;; for each of those access each element of se2 once
;; -- each of those accesses costs 1
;; size 1-> 1 access,
;; size 2-> 4 accesses,
;; size 3-> 9 accesses
;;
;; o BigTheta(N^2) has a special name: QUADRATIC TIME
;; o Subset of more general POLYNOMIAL TIME (where c>1)
;;
;; o Most sorting and matrix-y procedures are poly.
;;
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Peer Instruction 1:
;;
;; Closer definition of accumulate:
(define (second sent) (first (bf sent)))
(define (accumulate func sent)
(cond ((= (count sent) 0) (func))
((= (count sent) 1) (func (first sent)))
((= (count sent) 2) (func (first sent) (second sent)))
(else (func (first sent) (accumulate func (bf sent))))))
;; Write every in terms of accumulate:
;; o To help you out: |sent| >= 2
;;(define (every func sent)
;; (accumulate ...)
(define (every func sent)
(accumulate (lambda (x y) (se (func x) y)) sent))
(define square (lambda (x) (* x x)))
(every square '(1 2 3 4)) ;; Rats!!
;;
;; What is wrong?
;;
(define (every func sent)
(accumulate (lambda (x y) (se (func x) y))
(se (butlast sent) (func (last sent)))))
(every square '(1 2 3 4)) ;; OK!!
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Choice 4: EXPONENTIAL TIME
;;
;; o Arises in complicated problems.
;;
;; o To simply, we'll use BigO rather than
;; BigTheta
(define (fib n)
(if (< n 2)
1
(+ (fib (- n 1)) (fib (- n 2)))))
(utime (fib 15))
(utime (fib 20))
(utime (fib 21))
(utime (fib 22))
;;
;; o Fib N costs roughly about twice as much as fib N-1:
;; fib 20 = X accesses
;; fib 21 ~= 2 X accesses
;; fib 22 ~= 2*fib21 ~= 4X accesses
;;
;; o BigO(Y^N) is called general EXPONENTIAL TIME
;;
;; o Tons of problems are exponential
;;
;;
;; COMPLEX RUNNING TIMES:
;;
;; What is the running time of every?
(define (every fn sent)
(if (empty? sent)
sent
(se (fn (first sent))
(every fn (bf sent)))))
;; Well, ...
(every (lambda (x) (* x 2)) 10-sent)
(every (lambda (x) (by-ones 1 x)) 10-sent)
;; In first case, fn is T(1) -> every = T(N)*T(1)
;; (T(N) 'absorbs' T(1) in constant!)
;;
;; In second case, fn is T(N) -> every = T(N)*T(N)
;; Absorption again? No!
;; T(N*N) = T(N^2)
;; In general, every = T(N*fn)