CS 5114: Theory of Algorithms (Spring 2009)

CS 5114 is a traditional introduction to the theory of algorithms for computer science graduate students. It covers methods to construct algorithms and to analyze algorithms mathematically for correctness and efficiency (e.g., running time and space used). The course starts with definitions of algorithmic efficiency, discusses powerful paradigms for algorithm design, defines the theory of NP-completeness, and presents current approaches for coping with intractability, including approximation and randomized algorithms. The course provides a foundation for research in the design and analysis of algorithms itself or on problems with significant algorithmic content.

Instructor

Teaching Assistant

Class Meeting Times and Contact Info:

Course Description and Syllabus

Homework Assignments

Schedule

This schedule is subject to continuous change throughout the semester. Please refer to this webpage for the most up-to-date information, for reading assignments, and for homeworks.
All chapters below refer to the textbook, "Algorithm Design" by Kleinberg and Tardos, unless specified otherwise.
Date Topic Reading Homework
Tue, Jan 20, 2009 Introduction and Course Logistics
Thu, Jan 22, 2009 Class cancelled
Tue, Jan 27, 2009 Analysis of Algorithms Chapter 2.1-2.4
Thu, Jan 29, 2009 Heaps and Priority Queues Chapter 2.5 Homework 1 assigned
Read Chapter 3 for useful review on graphs.
Tue, Feb 3, 2009 Greedy Algorithms for Scheduling Chapter 4.1-4.2
Thu, Feb 5, 2009 Greedy Graph Algorithms Chapter 4.4-4.6 Homework 1 due
Homework 2 assigned
Tue, Feb 10, 2009 Greedy graph algorithms, same lecture as previous class
Thu, Feb 12, 2009 Greedy graph algorithms, same lecture as previous class Homework 2 due
Homework 3 assigned
Tue, Feb 17, 2009 Applications of MSTs Chapter 4.7 and exercise 9 in Chapter 4
Thu, Feb 19, 2009 Divide and Conquer Chapter 5.1-5.2 Homework 3 due
Tue, Feb 24, 2009 Divide and Conquer, same lecture as previous class
Discussion of homework 2
Chapter 5.3-5.5
Thu, Feb 26, 2009 Divide and Conquer Algorithms Chapter 5.3-5.5 Homework 4 assigned
Tue, Mar 3, 2009 Divide and Conquer Algorithms , same lecture as previous class
Thu, Mar 5, 2009 Dynamic Programming Chapter 6.1-6.3 Homework 4 due
Tue, Mar 17, 2009 Dynamic Programming, same lecture as previous class Chapter 6.5
Thu, Mar 19, 2009 Dynamic Programming, same lecture as the class on Mar 5 Chapter 6.5 Midterm examination assigned
PDF, LaTeX
Tue, Mar 24, 2009 Dynamic Programming, same lecture as the class on Mar 5 Chapter 6.6, 6.8
Thu, Mar 26, 2009 Discussion of midterm examination Midterm examination due
Homework 5 assigned
Tue, Mar 31, 2009 Network Flow Chapter 7.1-7.3
On the history of the transportation and maximum flow problems
Thu, Apr 2, 2009 Network Flow, same lecture as the previous class Homework 5 due
Tue, Apr 7, 2009 Applications of Network Flow Chapter 7.5-7.6
Thu, Apr 9, 2009 Applications of Network Flow, same lecture as the previous class Chapter 7.7-7.8, 7.10 Homework 6 assigned
Tue, Apr 14, 2009 Class cancelled
Thu, Apr 16, 2009 University holiday
Tue, Apr 21, 2009 NP and Computational Intractability Chapter 8.1-8.2 Homework 6 due
Thu, Apr 23, 2009 NP and Computational Intractability, same lecture as previous class Chapter 8.3-8.4
Tue, Apr 28, 2009 NP-Complete Problems Chapter 8.5-8.7
Thu, Apr 30, 2009 NP-Complete Problems, same lecture as the previous class Chapter 8.8-8.10 Practice Homework 7 assigned
Tue, May 5, 2009 Coping with NP-completeness Chapter 10.1-10.2 Final examination assigned
PDF, LaTeX
Last modified: Tue May 5 11:24:41 EDT 2009