Course Home | Course Policies | Homework | Schedule & Lecture Notes

CS 314: Algorithms
Fall 2013

Erin Chambers
Contact Info: echambe5 - at -
Office: 011 Ritter Hall
Office Hours: Monday 2-3pm, Thursday 9-10am, or by appointment

Here is this semester's tentative schedule; we will update it as the semester progresses. The listed sections refer to the course textbook; all notes come from Jeff Erickson's algorithms notes.

Dynamic Programming, Sec. 1
Date Topic Reading Lecture Notes Problem session (if any)
Monday, Aug. 26 Syllabus, big-O review Intro to algorithms Lecture Notes  
Wednesday, Aug. 28 Review: Big-O, Induction Intro to algorithms Lecture Notes  
Friday, Aug. 30 Review: Recurrences, Recursion Recurrence packet
Recursion chapter
Lecture Notes  
Wednesday, Sept. 4 Recursive algorithms Recurision chapter, Sec. 1.2, 1.3, 1.7
Lecture Notes  
Friday, Sept. 6 Recursive Algorithms Recurision chapter, Sec. 4
Recusive Backtracking, Sec. 2
Lecture Notes  
Monday, Sept. 9 No class due to illness Dynamic Programming, Section 1  
Wednesday, Sept. 11 Dynamic Programming: LIS Recusive Backtracking, Sec. 3 Lecture Notes  
Friday, Sept. 13 Dynamic Programming: Edit distance Section 5.5 Lecture Notes  
Monday, Sept. 16 Dynamic Programming:
Independant Set in trees
Section 4.2
Section 5.7
Lecture Notes  
Wednesday, Sept. 18 Problem Session: Dynamic Programming Worksheet
Friday, Sept. 20 Greedy Algorithms: Scheduling classes Section 7.2 Lecture Notes  
Monday, Sept. 23 Greedy: EDF scheduling Lecture Notes
Wednesday, Sept. 25 Greedy: Huffman codes Section 7.4 Lecture Notes
Friday, Sept. 27 Problem Session: Greedy algorithms Worksheet
Monday, Sept. 29 Graphs: DFS/BFS Graph theory notes Lecture Notes
Wednesday, Oct. 2 Graphs: MST MST notes Lecture Notes
Friday, Oct. 4 Impelmenting MST: Union Find Union Find notes Lecture Notes
Monday, Oct. 7 Shortest paths trees Reading Lecture Notes
Wednesday, Oct. 9 Problem session day Worksheet
Friday, Oct. 11 Flows and cuts Notes
Monday, Oct. 14 Computing flows Reading
Wednesday, Oct. 16 Review for midterm
Friday, Oct. 18 Midterm exam
Wednesday, Oct. 23 Flow Applications Reading Lecture Notes
Friday, Oct. 25 Network flow Lecture Notes Worksheet
Monday, Oct. 28 Uncomputability and hardness Reading Lecture Notes
Wednesday, Oct. 30 NP-Hardness Reading
An allegory to read
Lecture Notes
Friday, Nov. 1 NP-Hardness Reading Lecture Notes
Monday, Nov. 4 More reductions Reading
Online guide
Lecture Notes
Wednesday, Nov. 6 NP-Hardness Worksheet
Friday, Nov. 8 Approximation Reading

Additional reading
Lecture Notes
Monday, Nov. 11 More Approximation Reading
Lecture Notes
Wednesday, Nov. 13 More Approximation Lecture Notes
Friday, Nov. 15 No class
Reading assignment on LP
Chapter 7.1
Monday, Nov. 18 Linear Programs Chapter 7.1
Additional reading
Lecture Notes
Wednesday, Nov. 20 Linear Programming: Duality Chapter 7.4
Additional reading
Lecture Notes
Friday, Nov. 22 LP: Simplex Chapter 7.6
Additional reference
Lecture Notes
Monday, Nov. 25 Work day (extra credit) ICPC test program at SLU Go(Relians) Again
Monday, Dec. 2 Number Theory Algorithms Lecture Notes
Wednesday, Dec. 4 RSA Lecture Notes