Computer Algorithms Syllabus (Spring 2009)
Week Contents Homeworks
1 Prologue
  - Enter Fibonacci
  - Big-O notation		 HW #1
2 Algorithms with numbers
 - Basic arithmetic
 - Modular arithmetic
 - Primality testing
 - Cryptography
 - Universal hashing		 　
3 Divide-and-conquer algorithms
 - Multiplication
 - Recurrence relations
 - Mergesort
 - Medians
 - Matrix multiplication
 - The fast Fourier transform		 　
4 Decompositions of graphs
 - Why graphs?
 - Depth First search in undirected graphs
 - Depth First search in directed graphs
 - Strongly connected components		 　
5 Paths in graphs
 - Distances
 - Breadth First search
 - Lengths on edges
 - Dijkstra's algorithm
 - Priority queue implementations
 - Shortest paths in the presence of negative edges
 - Shortest paths in dags		 HW #2
6 Greedy algorithms
 - Minimum spanning trees
 - Huffman encoding
 - Horn formulas
 - Set cover		 　
7 Dynamic programming
 - Shortest paths in dags, revisited
 - Longest increasing subsequences
 - Edit distance
 - Knapsack
 - Chain matrix multiplication
 - Shortest paths
 - Independent sets in trees		 　
8 Mid-Term Exam 　
9 Linear programming and reductions
 - An introduction to linear programming
 - Flows in networks
 - Bipartite matching
 - Duality
 - Zero-sum games
 - The simplex algorithm
 - Postscript: circuit evaluation		 HW #3
10 NP-complete problems
 - Search problems
 - NP-complete problems
 - The reductions		 　
11 Coping with NP-completeness
 - Intelligent exhaustive search
 - Approximation algorithms
 - Local search heuristics		 　
12 Quantum algorithms
 - Qubits, superposition, and measurement
 - The plan
 - The quantum Fourier transform
 - Periodicity
 - Quantum circuits
 - Factoring as periodicity
 - The quantum algorithm for factoring		 　
13 Final Project Presentation 　
14 Final Project Presentation 　
15 Final Project Presentation