| Date | Assignment | Reading | Subject |
|---|---|---|---|
| Jan. 22 | Administrivia, e-mail, Web, languages, what is efficiency? | ||
| Jan. 24 | Problems & instances, best/worst/average case | ||
| Jan. 27 | Ignoring constant factors | ||
| Jan. 29 | big-O, little-O, theta, big-Omega, little-Omega | ||
| Jan. 31 | Deadline to add courses | ||
| Jan. 31 | Pseudo-code, counting operations, math review | ||
| Feb. 3 | chap. 1 | Divide and conquer, recurrence relations | |
| Feb. 5 | chap. 1 | Solving recurrence relations | |
| Feb. 7 | Class cancelled due to weather | ||
| Feb. 10 | General method for solving recurrence relations | ||
| Feb. 12 | chap. 2 | Analyzing searching & selection algorithms | |
| Feb. 14 | Analyzing searching & selection algorithms | ||
| Feb. 14 | Deadline to drop courses | ||
| Feb. 17 | Class cancelled due to weather | ||
| Feb. 19 | sections 3.1-3.2 | Bubble sort | |
| Feb. 21 | Insertion, selection, & tree sorts | ||
| Feb. 24 | section 3.3 | Lower bound on adjacent-exchange sorts; Shell sort; Bucket sort |
|
| Feb. 26 | HW1 | section 3.4 | Bucket & radix sorts |
| Feb. 28 | section 3.5 | Heaps and heapsort | |
| Mar. 3 | sections 3.6 & 3.8 | Merge sort & external sorting | |
| Mar. 5 | section 3.7 | Quick sort | |
| Mar. 7 | section 4.1 | Polynomials | |
| Mar. 10 | HW1 due | section 4.2 | Matrices |
| Mar. 12 | section 4.3 | Linear equations | |
| Mar. 14 | HW2 | section 4.3 | Matrix operations |
| Mar. 17-21 | Spring Break -- no classes | ||
| Mar. 24 | section 5.1 | Polynomials; String matching | |
| Mar. 26 | sections 5.1-5.2 | String matching | |
| Mar. 28 | sections 5.1-5.2 | String matching | |
| Mar. 28 | Deadline to withdraw from courses | ||
| Mar. 31 | section 6.1-6.2 | What is a graph? What is a graph-theoretic problem? | |
| Apr. 2 | section 6.1-6.2 | graphs and their representations | |
| Apr. 4 | HW2 due | section 6.3 | traversing graphs |
| Saturday Apr. 5 |
section 6.4 | Minimum spanning trees; Dijkstra-Prim and Kruskal algorithms | |
| Apr. 7 | section 6.5 | shortest paths | |
| Apr. 9 | section 9.3 | Dynamic programming | |
| Apr. 11 | HW3 | section 9.3 | Practice with dynamic programming |
| Apr. 14 | sections 7.1-7.3 | parallel computing | |
| Apr. 16 | section 7.6-7.7 | parallel matrix and graph algorithms | |
| Apr. 18 | Passover & Good Friday -- no classes | ||
| Apr. 21 | sections 8.1-8.2 | Nondeterminism and NP; problem reductions | |
| Apr. 23 | sections 8.3-8.4 | More examples, implications | |
| Apr. 25 | I'm out of town at a conference | ||
| Apr. 28 | co-NP, complexity hierarchy | ||
| Apr. 30 | Parallel complexity; NC and related classes | ||
| May 2 | HW3 due | sections 9.1-9.2 | Approximating difficult problems; probabilistic algorithms |
| May 5 | Unsolvability, the Halting Problem, computability hierarchy | ||
| May 7 | Catch up & review | ||
| May 9 | Catch up & review; I may be at another conference | ||
| May 12 | Final exam, 10:30-12:30 | ||