Date  Assignment  Reading  Subject 

Jan. 22  Administrivia, email, Web, languages, what is efficiency?  
Jan. 24  Problems & instances, best/worst/average case  
Jan. 27  Ignoring constant factors  
Jan. 29  bigO, littleO, theta, bigOmega, littleOmega  
Jan. 31  Deadline to add courses  
Jan. 31  Pseudocode, 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.13.2  Bubble sort  
Feb. 21  Insertion, selection, & tree sorts  
Feb. 24  section 3.3  Lower bound on adjacentexchange 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. 1721  Spring Break  no classes  
Mar. 24  section 5.1  Polynomials; String matching  
Mar. 26  sections 5.15.2  String matching  
Mar. 28  sections 5.15.2  String matching  
Mar. 28  Deadline to withdraw from courses  
Mar. 31  section 6.16.2  What is a graph? What is a graphtheoretic problem?  
Apr. 2  section 6.16.2  graphs and their representations  
Apr. 4  HW2 due  section 6.3  traversing graphs 
Saturday Apr. 5 
section 6.4  Minimum spanning trees; DijkstraPrim 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.17.3  parallel computing  
Apr. 16  section 7.67.7  parallel matrix and graph algorithms  
Apr. 18  Passover & Good Friday  no classes  
Apr. 21  sections 8.18.2  Nondeterminism and NP; problem reductions  
Apr. 23  sections 8.38.4  More examples, implications  
Apr. 25  I'm out of town at a conference  
Apr. 28  coNP, complexity hierarchy  
Apr. 30  Parallel complexity; NC and related classes  
May 2  HW3 due  sections 9.19.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:3012:30 