| Date | Assignment | Reading | Subject |
|---|---|---|---|
| Jan. 28 | HW1 | Administrivia, syllabus, what's an algorithm, what's efficiency? | |
| Jan. 30 | Problems and instances, problem size, factors affecting efficiency | ||
| Feb. 1 | Problems and instances, problem size, factors affecting efficiency | ||
| Feb. 4 | pp. 3-16 | Measuring algorithms; ignoring constant factors & small n's | |
| Feb. 6 | HW1 due; HW2 | pp. 16-26 | Review of math techniques, big-O notation |
| Feb. 8 | pp. 27-32 | Basic data structures | |
| Feb. 8 | Deadline to add courses | ||
| Feb. 11 | Abstract data types vs. implementations | ||
| Feb. 13 | Discuss homework | ||
| Feb. 15 | pp. 33-39 | Numerical programming, error propagation, selection sort with different data structures | |
| Feb. 18 | pp. 40-50 | Sorting algorithms; using sorting to solve other problems | |
| Feb. 20 | Hash tables and hashing functions | ||
| Feb. 22 | HW2 due | Heapsort and Mergesort; mention lower bounds | |
| Feb. 22 | Deadline to drop courses | ||
| Feb. 25 | pp. 53-62 | Quicksort; Memoization and dynamic programming | |
| Feb. 27 | Discuss homework and big-O notation | ||
| Mar. 1 | HW3 | pp. 62-75 | Applications of dynamic programming |
| Mar. 4 | pp. 75-80 | Divide-and-conquer algorithms (and dynamic programming) | |
| Mar. 6 | Recurrence relations and divide-and-conquer algorithms | ||
| Mar. 8 | The Master Method for solving recurrence relations | ||
| Mar. 11 | HW3 due | Analyzing algorithms with the Master Method | |
| Mar. 13 | Improving algorithms with the Master Method; integer multiplication; mentioned FFT's and applications to multiplication and music | ||
| Mar. 15 | pp. 81-92 | Graphs, graph problems, adjacency-matrix representation | |
| Mar. 18 | Review for midterm exam | ||
| Mar. 20 | Midterm exam | ||
| Mar. 22 | Discuss midterm exam | ||
| Mar. 25-29 | Spring break: no classes | ||
| Apr. 1 | Deadline to withdraw from courses | ||
| Apr. 1 | HW4, in part | Discuss homework & dynamic programming | |
| Apr. 3 | Adjacency-list representation; MST, connectedness, reachability problems | ||
| Apr. 5 | pp. 81-92 | Depth-first and breadth-first search; reachability, shortest paths, and connectedness | |
| Apr. 8 | HW4, the rest | pp. 90-95 | More fun with DFS and BFS; classifying edges |
| Apr. 10 | pp. 95-102 | Minimum spanning trees and shortest paths | |
| Apr. 12 | pp. 102-113 | Applications of graph algorithms | |
| Apr. 15 | pp. 100-101 | Dijkstra's Algorithm for shortest paths | |
| Apr. 17 | Analyzing Dijkstra's algorithm, with various data structures for various variables | ||
| Apr. 19 | p. 102 | Floyd-Warshall's algorithm | |
| Apr. 22 | HW4 due | pp. 115-125 | Backtracking: mouse in a maze |
| Apr. 24 | pp. 125-134 | Heuristic techniques: local search, simulated annealing, neural nets, genetic algorithms | |
| Apr. 26 | pp. 139-141 | Problem reductions to show something is easy | |
| Apr. 29 | pp. 141-143 | Problem reductions to show something is hard | |
| 1-May | pp. 143-144 | P and NP; more reductions; hard vs. complete | |
| 3-May | pp. 144-147 | NP-completeness of SAT | |
| 6-May | The polynomial hierarchy; space-bounded classes; parallel complexity classes NC1, AC0, NC | ||
| 8-May | Catch up and review for final | ||
| 10-May | Catch up and review for final | ||
| 15-May | Final exam, 8:00-10:00 | ||