# CSC 344 Spring 2013 Calendar

Jan 25 Stable Matching problem; proving termination, correctness, efficiency
Jan 28 Interval Scheduling problem; brute force and greedy algorithms; sorting algorithms
Jan 30 Interval Scheduling, continued
Feb 01 Shaffer 1, CLRS 1, How to get hired at Google Independent set, facility location, etc.
Feb 05 Last day to add classes
Feb 04 Shaffer 2, CLRS 2 Mathematical preliminaries; discuss pre-test if necessary
Feb 06 Shaffer 3 Asymptotic analysis
Feb 08 HW1 CLRS 3 More on asymptotic analysis
Feb 11 CLRS 4 Divide-and-conquer algorithms
Feb 13 Shaffer 7.1-7.4 Some sorting algorithms
Feb 15 Shaffer 5.5 and 7.6; CLRS 6 Heaps and heap-sort
Feb 18 HW1 due Present & discuss HW1
Feb 20 Last day to drop classes
Feb 20 Shaffer 7.5, CLRS 7 Present & discuss HW1
Feb 22 Shaffer 7.8-7.9, CLRS 8.1 Present & discuss HW1
Feb 25 Shaffer 7.7, CLRS 8 Present & discuss HW1; lower bounds proofs
Feb 27 HW2 Shaffer 7.7, CLRS 8 Why you can't sort in linear time, and how to do it
Mar 01 CLRS 9 Not quite sorting
Mar 04 Shaffer 16.1, CLRS 15.1 Dynamic programming
Mar 06 CLRS 15.2-15.3 More dynamic-programming examples
Mar 08 CLRS 15.4-15.5 More dynamic-programming examples
3/11-3/17 Spring break
Mar 18 HW2 due Present & discuss HW2
Mar 20 Present & discuss HW2
Mar 22 Present & discuss HW2
Mar 25 Present & discuss HW2
Mar 27 Last day to withdraw from classes
Mar 27 Present & discuss HW2
Mar 29 Shaffer 5.6, CLRS 16.1-16.3 Greedy algorithms; Huffman codes
Apr 01 Shaffer 11.1-11.3, CLRS 22 Graph basics: nodes, edges, paths, Eulerian paths, degrees
Apr 03 CLRS 22 More on graphs: list and matrix representations, breadth-first and depth-first search
Apr 05 CLRS 22 More on graphs: properties of breadth-first and depth-first search
Apr 08 CLRS 22 More on graphs: applications of breadth-first and depth-first search
Apr 10 Research day: no classes
Apr 12 Return & discuss homework 1
Apr 15 Shaffer 11.5, CLRS 23 Minimum spanning trees
Apr 17 Shaffer 11.5, CLRS 23 Minimum spanning trees
Apr 19 HW3 Shaffer 11.4, CLRS 24-24.3 Single-source shortest paths
Apr 22 HW2 resubmission due CLRS 26.1-26.3 Maximum flow problems
Apr 24 Computability, decidability, and semidecidability
Apr 26 Shaffer 17.3 Uncomputability
Apr 29 Shaffer 17.1 Problem reductions and uncomputability; completeness; Rice's theorem?
May 01 CLRS 34.1-34.2 Polynomial-time computability, decidability, and semidecidability
May 03 Shaffer 17.2; CLRS 34.3-34.5 Polynomial-time reductions; NP and NP-completeness
May 06 HW3 due Present & discuss HW3
May 08 Present & discuss HW3
May 9-10 emergency make-up days
May 17 present & discuss, 10:30 AM-12:30 PM