Fall 2013

Contact Info: echambe5 - at - slu.edu

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.

DateTopicReadingLecture NotesProblem 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 chapterLecture 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. 2Lecture 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 treesSection 4.2

Section 5.7Lecture 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 readLecture Notes Friday, Nov. 1 NP-Hardness Reading Lecture Notes Monday, Nov. 4 More reductions Reading

Online guideLecture Notes Wednesday, Nov. 6 NP-Hardness Worksheet Friday, Nov. 8 Approximation Reading

Additional readingLecture Notes Monday, Nov. 11 More Approximation Reading

Lecture Notes Wednesday, Nov. 13 More Approximation Lecture Notes Friday, Nov. 15 No class

Reading assignment on LPChapter 7.1 Monday, Nov. 18 Linear Programs Chapter 7.1

Additional readingLecture Notes Wednesday, Nov. 20 Linear Programming: Duality Chapter 7.4

Additional readingLecture Notes Friday, Nov. 22 LP: Simplex Chapter 7.6

Additional referenceLecture 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