[FrontPage] [TitleIndex] [WordIndex

Theta and Orders of Growth

For all x > n0 g(x) is theta(f(x)) iff there exists c1,c2 such that c1*f(x) <= g(x) <= c2*f(x)

g(x) is O(f(x)) if g(x) <= c f(x) (for some constant c) g(x) is Omega(f(x)) if c f(x) <= g(x) (for some constant c)

Orders of Growth that we care about:

Dr Scheme + Lisp discussion:

In the code from the previous class, each time you call add you are actually calling {{{(lambda(x y)

}}}

We talked about two different ways to do this:

Option 1:

(add 5 4) --> (add 6 3) --> (add 7 2) --> (add 8 1) --> (add 9 0)

Each time, the value of the previous expression is the same as the value of the subsequent one.

Option 2:

In this case, (add 5 4) --> (increment (add 5 3)) --> (increment (add 5 2)) --> (increment (add 5 1)) --> (increment (add 5 0)) In this case all of the operations are pending. They're waiting for another operation to finish and then incrementing the returned value.

If I have nothing to do once I get the result back, then I don't need to exist any longer. Scheme is smart enough to realize this and replace original operation with its offspring. Thus the first option is more effiecnt.

Option 1 allows the stack to be 1 regardless of the size of y because each operation replaces the previous one. Output of last operation can be passed directly to calling function.

In contrast Option 2 would require a stack of size ~y.

Brief overview of Stack:

Fencepost error if you end up being off by +/- 1 in indexing. Order of Growth doesn't care about +/- 1, so Lynn doesn't really care about it. Contrast with a math course in which precision matters.

Top S --> returns top element of the stack

To code a Stack you need: {{{pop Empty ->error pop (push x S) --> S top (push x S) --> x}}}

cons cell

_ (first)

_ (rest)

{{{(first (cons a b)) --> a (rest (cons a b)) --> b}}}

(cons 1 (cons 2 ( cons 3 '())))
Inside computer this is represented as:
[1][-->] --> [2][-->]-->[3][nil]

cons 2 3 would require a special case exception so that you know to read the cdr as a value instead of a pointer to the rest of the set. That is why improper lists exist because you might actually want to be able todo it.

"Authentic" Lisp Names for first and rest.

Lisp was originally designed on a computer with 4 registers. One was used to contain information, the other was used as a pointer to the rest of the data.
first == car (Contents of Address Register)
rest == cdr (Contents of Decrement Register) - "could'er"

Class Assignment

Build a Scheme program that increments all the items in a list.

Sample Solution:

(define incrementlist
  (lambda (L)
    (if (empty? L)
        ()
        (cons (+ 1 (car L)) (incrementlist(cdr L)))
        )
    )
  )

Scheme has procedure called "Map" which maps a procedure onto a list. (map _ L) --> new list with p(x) for each x in L. Example:

(define incList (lambda (L)  
  (map (lambda(x)(+ 1 x)) L)))

This will apply (lambda(x)(+ 1 x)) to L.

(define map
  (lambda (p L)
    (if (empty? L)
        L
        (cons (p (car L))
              (map p (cdr L))))))

Procedures are first-class objects. They can be passed around, they can be returned, created, or modified.

Next Steps for Course

If I want to compare Y to O

This is a finite state machine with 6 possible operations. We're going to show that we can't push pending operations onto the stack.

(define cons
  (lambda (a d)
    (lambda (c)
      (c a d))))

(define car
  (lambda (x)
    (x lambda (a d) a)))

It is possible to represent any data structure as a procedure.


2013-07-17 10:43