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

Overview of course through the lens of finding a majority element

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