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