Calendar of topics

CSC 344, Spring 2007

Last modified:

Date Assignment Reading Subject
Jan 24 Introduction; problems and algorithms
Jan 26 Preface, 1.1 Sample problems; pseudocode, analysis, and proofs
Jan 29 1.2, exercises More sample problems
Jan 31 HW1 2.1-2.2 Efficiency, scaling, worst-case, best-case, average-case, asymptotic notation
Feb 02 2.3-2.4 Implementation, data structures, common running times
Feb 05 2.5, exercises Priority queues and heaps
Feb 06 Last day to add classes
Feb 07 3.1-3.2 Graphs
Feb 09 3.1-3.2 Graphs
Feb 12 3.3-3.4 BFS, DFS, and bipartiteness
Feb 14 3.3-3.4 BFS, DFS, and bipartiteness
Feb 16   3.5-3.6, exercises Student presentations
Feb 19 HW1 due Dr. Bloch out sick
Feb 20 Last day to drop classes
Feb 21 Student presentations
Feb 23 Dr. Bloch out sick
Feb 26 HW2 Review graph theory; student presentations
Feb 28 4.1 Greedy algorithms; interval scheduling
Mar 02 4.2 Proving optimality
Mar 05 4.4 Shortest paths
Mar 07 4.5 Minimum spanning trees
Mar 09 4.6-4.7, exercises Union/Find data structure, Clustering
Mar 12 Discuss homework; student presentations
Mar 14 Discuss homework; student presentations
Mar 16 HW2 due 5.1-5.2 Mergesort and recurrences
Mar 19 HW3 5.3-5.4 Two more applications of divide & conquer
Mar 21 5.5-5.6 Multiplication & FFT
Mar 23 6.1-6.2 Dynamic programming & memoization
Mar 26 6.3-6.4 Multiway choices, extra parameter
Mar 27 Last day to withdraw from classes
Mar 28 6.5-6.6 Dynamic programming over intervals
Mar 30 HW4 6.8-6.9, exercises Shortest paths again
Apr 02 Spring break
Apr 04
Apr 06
Apr 09 HW3 due Student presentations
Apr 11 7.1-7.3 Max flow, min cut
Apr 13 7.5 Bipartite matching
Apr 16 13.1 Randomization
Apr 18 13.5 Randomized median and quicksort
Apr 20 I'm out of town at a conference
Apr 23 13.6 Hashing
Apr 25 HW4 due; HW5 Student presentations
Apr 27 Problems and programs again; impossibility
Apr 30 Recursive, r.e., co-r.e., reducibility, completeness
May 02 8.1-8.3 Polynomial reducibility, NP and SAT
May 04 8.4-8.5 Example NP-complete problems
May 07 HW5 due Student presentations; catch up and review
May 09 Emergency/Study Day
May 11 344 final exam, 10:30-12:30