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

## CS150 Notes 10 (14 September 2005)

#### Upcoming Assignments

Notes
Define a procedure compose that takes two operands that are procedures (that take one operand) and evaluates to a procedure that is the composition of the two operands.

For example, (compose square square) should produce a procedure that take input x and produces x4.

What should ((compose (lambda (x) (+ x 1)) (lambda (x) (* x 2))) 3) evaluate to?

Define a procedure n-times that takes two operands: a procedure p and a number n, and produces the composition of the procedure with itself n times.

For example, ((n-times (lambda (x) (+ x 1)) 5) 7) should evaluate to 12 and ((n-times (lambda (x) (* x 2)) 0) 4) should evaluate to 4.

#### Measuring Work

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.
• x2 is O (x2) — c = .5 works fine
• x2 is O (x3) — c = 1 works fine
• x3 is not O (x2) — for any choice of c, once x gets big enough c * x3 > x2
• Time to do simplesort for a list of length n is O (n2) — 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.
• x2 is Ω (x2) — c = 2 works fine
• x2 is not Ω (x3) — for any choice of c, once x gets big enough c * x2 < x3
• x3 is Ω (x2) — for any choice of c, once x gets big enough c * x3 > x2
• Time to do simplesort for a list of length n is Ω (n2) — the value 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)).
• x2 is Θ (x2) since x2 is O (x2) and x2 is Ω (x2).
• x2 is not Θ (x3) since x2 is not Ω (x3)
• x3 is not Θ (x2) since x3 is not O (x2)
• Time to do simplesort for a list of length n is Θ (n2) since it is O (n2) and Ω (n2).
Lecture Code
```(define (simple-sort cf lst)
(if (null? lst) lst
(let ((best (find-best cf lst)))
(cons best (simple-sort cf (delete lst most))))))

(define (find-best cf lst)
(insertl (lambda (c1 c2) (if (cf c1 c2) c1 c2))
lst (car lst)))

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

(define (insertone cf el lst)
(if (null? lst) (list el)
(if (cf el (car lst)) (cons el lst)
(cons (car lst) (insertone cf el (cdr 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 Award for Excellence in Mathematics and Science Teaching

"); print ( \$res[\$first] ) ; print (""); ?>