CS 5800 Analysis of Algorithms Spring 2014

The reading assignments reference the online textbook at http://www.cs.berkeley.edu/~vazirani/algorithms/, and may differ from the printed textbook.

Section 01 DateSection 03 DateTopicReading Assignment
1/81/9Getting Started Chapter 0 and Academic Honesty and Integrity
1/151/16Sorting Algorithms and Recurrence Formulas Sections 2.1, 2.2, 2.3, 2.4
1/221/23Depth-First Search in Graph Structures Sections 3.1, 3.2, 3.3
1/291/30Breadth-First Search and Strongly-Connected Components Sections 3.4, 4.1, 4.2, 4.3; Handout on the Tarjan algorithm
2/12*2/6Shortest Paths in Weighted Graphs Sections 4.4, 4.5, 4.6, 4.7; Handout on pitfalls in algorithm design
2/14*2/20**Greedy Algorithms, Mimimum Spanning Trees, Huffman Encoding Sections 5.1, 5.2
2/192/21*Dynamic Programming Sections 6.1, 6.3, 6.6
2/262/27Linear Programming Section 7.1
3/123/13Network Flows, Simplex Method Sections 7.2, 7.6
3/193/20Monte Carlo Methods The Monte Carlo method
3/263/27NP-Completeness Sections 8.1, 8.2
4/24/3Coping with Hard Problems Section 9.1; Handout
4/94/10General Session for Questions moderated by the TAs
4/164/17Review for Final Exam
4/234/24Final Exam

* Note: Due to the snow emergency on February 5, 2014, the class that would have been held on that date will be held on Wednesday, February 12, 2014, and the class that would have been held on Wednesday, February 12, 2014 will be held on Friday, February 14, 2014 in Shillman 220 (one floor below the usual room).

** Note: Due to the snow emergency on February 13, 2014, the class that would have been held on that date will be held on Thursday, February 20, 2014, and the class that would have been held on Thursday, February 20, 2014 will be held on Friday, February 21, 2014 in the same room as usual.