1.	Algorithm Analysis
a.	Formal definition: T(N) = O(f(N)) if there are positive constants c and n_0 such that T(N) <= cf(N) when N >= n_0/
b.	Formal definition: T(N) = omega(f(N)) if there are positive constants c and n_0 such that T(N) >= cf(N) when N >= n_0/
c.	Formal definition: T(N) = theta(f(N)) if and only if T(N) = O(f(N)) and T(N) = omega(f(N))/
d.	Informal definition: O(f(N)) sets the upper-bound on T(N).
e.	Informal definition: omega(f(N)) sets the lower-bound on T(N).
f.	Informal definition: theta(f(N)) is the average runtime.
g.	Typical growth rates: C < log(N) < log^2(N) < N < Nlog(N) < N^2 < N^3 < 2^N/

2.	Recurrence Relations
a.	Page 276 and page 287 provide a recurrence relation analysis.

3.	Sorting Algorithms
a.	Heap sort: O(NlogN), theta(NlogN), omega(NlogN). Builds a minimum heap, and pulls out the minimum value and places it at the end of a list. Inserting into a min heap is O(logN).
b.	Insertion sort: O(N^2), theta(N^2), omega(N). Remove an element from input list and insert it correctly into a sorted list.
c.	Selection sort:O(N^2), theta(N^2), omega(N^2). Find the minimum value in the list, place it in the lowest position. Continue doing this, moving up in position.
d.	Bubble sort: O(N^2), theta(N^2), omega(NlogN). Has the same upper and lower bounds as quicksort, but a slower average run time. Compare two elements, swapping if a < b, continue up the list. Repeat.
e.	Merge sort: O(NlogN), theta(NlogN), omega(N). Split the list in half. Call mergesort on each one recursively, and then merge them back together in order.
f.	Quick sort: O(N^2), theta(NlogN), omega(NlogN). Has same upper and lower bounds as bubblesort, but a faster average run time. Pick an element, partition the list into two partitions, one above the pivot and the other containing elements below. Recursively call this on each partition.

4.	Shortest Path
a.	Greedy algorithm: At each stage, it picks the best available option at the time.
b.	Read pp. 354-356 in the book. Basically you can just make a quick table (as illustrated in the book), work through each node until the table is complete, and then find the quickest route from A to B by analyzing the table.

5.	C++
a.	Read chapter 1 in the book if you feel you need a review on C++.

6.	AVL Trees
a.	In-order: Left, root, right.
b.	Pre-order: Root, left, right.
c.	Post-order: Left, right, root.
d.	Building: when building an AVL tree from a an input list, place the first number in the root. Following numbers are inserted in the same manner as a binary tree, i.e. smaller values move down the left side of the tree, and greater values move down the right side of the tree. After inserting the entire list, search the tree for imbalances and rotate appropriately. Alternatively, you can balance it at each insertion.
e.	Examining for imbalances: To get the balance of a node, b = #rightnodes - #leftnodes.
f.	Rotating: Know how to rotate AVL trees in pictorial form.