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 | ||