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 x^{4}.
What should ((compose (lambda (x) (+ x 1)) (lambda (x) (* x 2)))
3) evaluate to?
Define a procedure ntimes that takes two operands: a
procedure p and a number n, and produces the composition of the
procedure with itself n times.
For example, ((ntimes (lambda (x) (+ x 1)) 5) 7) should
evaluate to 12 and ((ntimes (lambda (x) (* x 2)) 0)
4) should evaluate to 4.
Measuring Work
Upper bound O ("bigoh"): 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^{2} is O (x^{2}) — c =
.5 works fine

x^{2} is O (x^{3}) — c =
1 works fine

x^{3} is not O (x^{2}) — for any
choice of c, once x gets big enough c * x^{3} >
x^{2}

Time to do simplesort for a list of length n is O (n^{2}) — 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^{2} is Ω (x^{2}) — c =
2 works fine

x^{2} is not Ω (x^{3}) — for
any choice of c, once x gets big enough c *
x^{2} < x^{3}

x^{3} is Ω (x^{2}) — for any
choice of c, once x gets big enough c * x^{3} >
x^{2}

Time to do simplesort for a list of length n is Ω (n^{2}) — 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)).
 x^{2} is Θ (x^{2}) since
x^{2} is O (x^{2}) and x^{2} is
Ω (x^{2}).

x^{2} is not Θ (x^{3}) since
x^{2} is not Ω (x^{3})

x^{3} is not Θ (x^{2})
since x^{3} is not O (x^{2})

Time to do simplesort for a list of length n is Θ
(n^{2}) since it is O (n^{2})
and Ω (n^{2}).
Lecture Code
(define (simplesort cf lst)
(if (null? lst) lst
(let ((best (findbest cf lst)))
(cons best (simplesort cf (delete lst most))))))
(define (findbest 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 homeroom 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 ("");
?>