CS5114 Theory of Algorithms
Calendar and Coursenotes: Spring 2010
This page will show what we cover each day, including the course notes covered in class.
Reading assignments are also posted for each week. The intention is that you will have finished the reading for that week by the end of the week (that is, typically you would be expected to read material after the associated lecture). However, some folks like to read it before the lecture, so I will try to get it up by the beginning of the week if I can.
- Week 1: Course Introduction, Induction
-
Wednesday, January 20: Course introduction, Induction
Reading Assignment: Manber Chapters 1 and 2, Shaffer material on induction
Class notes for today.
-
Wednesday, January 20: Course introduction, Induction
- Week 2: Algorithm Analysis, Sums, Recurrences
-
Monday, January 25: Wrap up Induction; Algorithm Analysis
Reading Assignment: Manber Sections 3.1-3.3;
Shaffer material on Algorithm Analysis
Class notes through today. -
Wednesday, January 27: Sums and Recurrences
Reading Assignment: Manber Sections 3.4-3.7;
Shaffer material on Analysis Techniques
Class notes through today. - Thursday, January 28: Homework 1 due
-
Monday, January 25: Wrap up Induction; Algorithm Analysis
-
Week 3: Design of Algorithms
-
Monday, February 1: Design of Algorithms
Reading Assignment: Manber Sections 5.3, 5.5
Class notes through today. -
Wednesday, February 3: Design of Algorithms
Reading Assignment: Manber Sections 5.6, 5.8, 5.9
Class notes through today. - Thursday, February 4: Homework 2 due
-
Monday, February 1: Design of Algorithms
-
Week 4: Design of Algorithms; Sorting
-
Monday, February 8: Dynamic Programming
Reading Assignment: Manber Sections 5.10-5.12
Shaffer material on Dynamic Programming
Class notes through today. -
Wednesday, February 10: Sorting -- Quadratic sorts, Quicksort, Mergsort
Reading Assignment: Shaffer material on Sorting
Class notes for today. -
Thursday, February 11: Homework 3 due
-
Monday, February 8: Dynamic Programming
-
Week 5: Sorting, External Sorting
-
Monday, February 15: Sorting -- Heapsort, Radix Sort, Sorting lower bound
Reading Assignment: Manber Section 6.4
Class notes through today. -
Wednesday, February 17: External Sorting
Reading Assignment: Shaffer material on External Sorting
Class notes through today. -
Thursday, February 18: Homework 4 due
-
Monday, February 15: Sorting -- Heapsort, Radix Sort, Sorting lower bound
-
Week 6: Midterm; Sequences
- Monday, February 22: Midterm up through External Sorting
-
Wednesday, February 24: String match, algorithms on sequences
Class notes for today.
Reading Assignment: Shaffer material on Lower Bounds (including Min and Max, 2nd Best problems and Adversary Arguments
Manber Sections 6.5 and 6.7 -
Thursday, February 25: Homework 5 due
-
Week 7: Randomized Algorithms; Graphs
-
Monday, March 1: Randomized Algorithms
Class notes for today.
-
Wednesday, March 3: Graphs and Graph Algorithms: Traversals
Class notes for today.
Reading Assignment: Manber Chapter 7 through Section 7.4. -
Thursday, March 4: Homework 6 due
-
Monday, March 1: Randomized Algorithms
-
Week 8: Graphs
-
Monday, March 15: Shortest Paths and MCST algorithms
Class notes for today.
Reading Assignment: Manber Sections 7.5-7.7; Shaffer material on Graph Algorithms
-
Wednesday, March 17: Matching and Network Flow
Class notes for today.
Reading Assignment: Manber Sections 7.10-7.11.
-
Thursday, March 18: Homework 7 due
-
Monday, March 15: Shortest Paths and MCST algorithms
-
Week 9: Computational Geometry
-
Monday, March 22: Point in Polygon, Convex Hull
Class notes for today.
-
Wednesday, March 24: Intro to reduction; closest points; sweepline algorithm
Class notes for today
Reading Assignment: Manber Chapter 8
-
Thursday, March 25: Homework 8 due
-
Monday, March 22: Point in Polygon, Convex Hull
-
Week 10: Reductions and NP-completeness
-
Monday, March 29: Reductions
Class notes for today.
Reading Assignment: Manber Chapter 10
Section 17.1 from Shaffer material on Reductions and NP-completness
-
Wednesday, March 31: Introduction to NP-completeness
Class notes for today.
Reading Assignment: Shaffer material on Reductions and NP-completness
-
Thursday, April 1: Homework 9 due
-
Monday, March 29: Reductions
-
Week 11: NP-Completeness
-
Monday, April 5: NP-completeness
Class notes for today.
Reading Assignment: Handout: Some NP-complete problems
- Wednesday, April 7: CLASS CANCELLED
-
Thursday, April 8: Homework 10 due
-
Monday, April 5: NP-completeness
-
Week 12: Coping with NP-Completeness; Numeric Problems
-
Monday, April 12: Coping with NP-completeness
Class notes for today.
-
Wednesday, April 14: Numeric Problems
Class notes for today.
-
Thursday, April 15: Homework 11 due
-
Monday, April 12: Coping with NP-completeness
-
Week 13: Fast Fourier Transform; Parallel Algorithms
-
Monday, April 19: Fast Fourier Transform
Class notes for today.
-
Wednesday, April 21: Parallel Algorithms
Class notes for today.
-
Thursday, April 12: Homework 12 due
-
Monday, April 19: Fast Fourier Transform
-
Week 14: Parallel Algorithms
-
Monday, April 26: Parallel Algorithms
Class notes for today.
-
Wednesday, April 28: Parallel Algorithms
Class notes for today.
-
Complete class notes for the semester.
-
Thursday, April 29: Homework 13 due
-
Monday, April 26: Parallel Algorithms
-
Week 15: We are done!
-
Monday, May 3: CLASS CANCELLED
-
Wednesday, May 5: CLASS CANCELLED
-
Thursday, May 6: Homework 14 due
-
Monday, May 3: CLASS CANCELLED
- Final Exam: Monday, May 10 at 2:05-4:05
Go to the CS5114 Homepage.