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:
- 1 - Constant
- log n - Logarithmic (no non-constant difference between log_2(n) vs. log_3(n))
- n - Linear
- n^2 - Quadratic
2n - Exponential (could have different exponential such as 3n)
Dr Scheme + Lisp discussion:
In the code from the previous class, each time you call add you are actually calling {{{(lambda(x y)
- ..(add...)
}}}
We talked about two different ways to do this:
Option 1:
- (add (decrement x) (increment y)))
(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:
Alternative is (increment (add( x (decrement y))):
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:
- Type of Data Structure
- You only access one end: FI,FO - First In, Last Out
- Effectively you pile stuff on top of it and then unpack it afterwards
- Very easy to build with a list structure
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]
Empty Set is '(), null, nil depending on Scheme implementation.
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.
- A pair is a totally legitimate data structure.
(cons 2 3) prints as (2. 3)
(1 2 3) is equivalent to (1.(2.(3.())))
Scheme is smart enough to convert the .( into " "
(car (cdr L)) --> (cadr L)
- cadar cddr cadr also exist
"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
- X
- add_one
- subtract_one
- Y
- add_one
- subtract_one
- Compare_to_0
If I want to compare Y to O
Y < 0, then increment Y & increment Y.
Y = 0, then return X.
Y > 0, then decrement Y & increment X.
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.