Spring 2010

Contact Info: echambe5 - at - slu.edu

Office: 011 Ritter Hall

Office Hours: Monday 10-11:30am, Thursday 1-2pm

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

DateTopicReadingLecture NotesProblem session (if any)Jan 11 Syllabus, big-O review Any discrete math book Lecture 1 Jan 13 Induction Any discrete math book Lecture 2 Jan 15 Recurrences Recurrences Lecture 3 Jan 18 No class - MLK day Jan 20 Heaps (and pseudocode) Section 2.5 Lecture 4 Jan 22 Intro to graphs Chapter 3.1

Graph notesLecture 5 Jan 25 Breadth First Search Chapter 3.2

Graph notesLecture 6 Jan 27 Depth First Search Chapter 3.3, 3.4

Graph notesLecture 7 Jan 29 Divide and Conquer:

Subset SumDivide and Conquer Notes, Sec. 2.2 Lecture 8 Feb 1 Divide and Conquer:

Counting inversionsChapter 5.2-5.3 of book Lecture 9 Feb 3 Divide and Conquer:

Closest Pair of PointsChapter 5.4 of book Lecture 10 Feb 5 Divide and Conquer:

MultiplicationLecture Notes on Recursion, Sections 1.7 and 1.8 Lecture 11 Feb 8 Greedy Algorithms:

Interval SchedulingChapter 4.1 of book

Lecture Notes on Greedy Algorithms, Section 4.2Lecture 12 Feb 10 Greedy Algorithms:

Processor SchedulingChapter 4.2 of book Lecture 13 Feb 12 Greedy Algorithms:

Huffman codesLecture Notes on Greedy Algorithms, Section 4.4 Lecture 14 Feb 15 Greedy Algorithms:

Huffman codes

Shortest PathsLecture Notes on Greedy Algorithms, Section 4.4 Lecture 15 Feb 17 Greedy Algorithms:

Shortest PathsChapter 4.4 of book Lecture 16 Feb 19 Greedy Algorithms:

Minimum Spanning TreesChapter 4.5 of book Lecture 17 Feb 22 Union-Find Union Find notes

Chapter 4.6 of textLecture 18 Feb 24 Dynamic Programming: Intro Chapter 6.1 of book

Dynamic Programming Notes, Sec. 3.1-3.4Lecture 19 Feb 26 Dynamic Programming:

Edit DistanceSec. 3.5 of Dynamic Programming Notes Lecture 20 March 1 DP: Longest Increasing Subsequence Sec. 3.9.2 of Dynamic Programming Notes Lecture 21 March 3 DP: Independent Set Sec. 3.7 of Dynamic Programming Notes Lecture 22 March 5 DP: Subset Sum

The Halting ProblemSec. 3.9.1 of Dynamic Programming Notes Lecture 23 March 15 Problem Session Day Worksheet March 17 Review Session in class March 19 Midterm March 22 Recap of midterm

P versus NPNP-Hardness Notes, Sec. 1-3

Chapter 8 of bookLecture 24 March 24 Satisfiability and Reductions NP-Hardness Notes, Sec. 4-5

Chpater 8 of bookLecture 25 March 26 More reductions NP-Hardness Notes

Chpater 8 of bookLecture 26 March 29 Graph reductions NP-Hardness Notes

Chapter 8 of bookLecture 27 March 31 Work day on reductions NP-Hardness Notes

Chpater 8 of bookWorksheet April 2 No class Off for Good Friday April 5 No class Off for Easter Monday April 7 Approximation: Minimizing makespan Approximation Notes

Chapter 11.1 of bookLecture 28 April 9 Approximation: Vertex Cover Approximation Notes Lecture 29 April 12 Approximation: TSP Approximation Notes Lecture 30 April 14 Network Flow: Part 1 Chapter 7 of text

Max Flow NotesLecture 31 April 16 Network Flow: Part 2 Chapter 7 of text

Max Flow AlgorithmsLecture 32 April 19 Network Flow Applications Chapter 7 of text Lecture 33 April 21 Circulations Chapter 7 of text Lecture 34 April 23 More Network Flow applications Chapter 7 of text Lecture 35