Course Topics

Course introduction and objectives
How to be an A student
Review of logs and other functions
Summing geometric and arithmetic series
Useful formulae
Order notation
Divide and conquer 
Sorting (bubble sort, insertion sort, merge sort)
Solving recurrences (several different approaches)
Recurrences for (searching on a binary tree, computing $a^n$, binary search) 
Repeated doubling
Matrix multiplication (iterative, divide-and-conquer,  improvements such as Strassen)
Circuit Addition (Upper and lower bounds, nonunique representation)
Using induction to prove that we have the correct solution to a recurrences
More mathematical preparation for linear-time selection
Quicksort
W.h.p analysis
Randomized and deterministic Linear-time selection
Dynamic programming (knapsack problem, edit distance,  edit distance with small space, finding line breaks in a document, etc)
Shortest Paths (in a dag, singlesource, all pairs)
Handouts for: Minimum spanning trees (Prims, Kruskalls, Borovka)
Viewing DP as path-finding in a DAG.
Amortization (how it helps hashing, weight-balanced search trees)
2-3 trees other trees
Skip lists
van Emde Boas Trees
Karp-Rabin string matching
Computing to achieve cache-and I/O-efficiency
B-trees
Matrix multiplication 
Blocking and Space filling curves
Cache-oblivious algorithms
Multi-way mergesort
Write optimization
NP-completeness and hardness
Reductions