CS 5114: Theory of Algorithms (Spring 2013)

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.

Videos of the lectures are available. Each lecture's video will usually be available two business days after the lecture.
Date Topic Reading Homework
Tue, Jan 22, 2013 Introduction and Course Logistics
Thu, Jan 24, 2013 Analysis of Algorithms Chapter 2.1-2.4
Tue, Jan 29, 2013 Heaps and Priority Queues Chapter 2.5 Homework 1 assigned
Thu, Jan 31, 2013 Greedy Algorithms for Scheduling Chapter 4.1-4.2
Read Chapter 3 for useful review on graphs.
Tue, Feb 5, 2013 Class cancelled Homework 1 due
Thu, Feb 7, 2013 Greedy Graph Algorithms Chapter 4.4-4.6
Tue, Feb 12, 2013 Greedy graph algorithms, same lecture as previous class Homework 2 assigned
Thu, Feb 14, 2013 Greedy graph algorithms, same lecture as previous class
Tue, Feb 19, 2013 Applications of MSTs Chapter 4.7 and exercise 9 in Chapter 4 Homework 2 due
Homework 3 assigned
Thu, Feb 21, 2013 Divide and Conquer Chapter 5.1-5.2
Tue, Feb 26, 2013 Divide and Conquer Algorithms Chapter 5.3-5.5 Homework 3 due
Homework 4 assigned
Thu, Feb 28, 2013 Divide and Conquer Algorithms, same lecture as previous class
Tue, Mar 5, 2013 Dynamic Programming Chapter 6.1-6.3 Homework 4 due
Thu, Mar 7, 2013 Dynamic Programming, same lecture as previous class Chapter 6.5
Tue, Mar 19, 2013 Dynamic Programming, same lecture as the class on Mar 5 Chapter 6.5 Midterm examination assigned
PDF, LaTeX
Thu, Mar 21, 2013 Dynamic Programming, same lecture as the class on Mar 5 Chapter 6.6, 6.8
Tue, Mar 26, 2013 Discussion of midterm examination Midterm examination due
Thu, Mar 28, 2013 Network Flow Chapter 7.1-7.3
On the history of the transportation and maximum flow problems
Tue, Apr 2, 2013 Network Flow, same lecture as the previous class Homework 5 assigned
Thu, Apr 4, 2013 Network Flow, same lecture as the previous class
Tue, Apr 9, 2013 Applications of Network Flow Chapter 7.5-7.6 Homework 5 due
Homework 6 assigned
Thu, Apr 11, 2013 Applications of Network Flow, same lecture as the previous class Chapter 7.7-7.8, 7.10
Tue, Apr 16, 2013 Applications of Network Flow, same lecture as the previous class Homework 6 due
Thu, Apr 18, 2013 NP and Computational Intractability Chapter 8.1-8.2
Tue, Apr 23, 2013 NP and Computational Intractability, same lecture as previous class Chapter 8.3-8.4
Thu, Apr 25, 2013 NP-Complete Problems Chapter 8.5-8.7 Homework 7 assigned
Tue, Apr 30, 2013 NP-Complete Problems, same lecture as the previous class Chapter 8.8-8.10
Thu, May 2, 2013 Coping with NP-completeness Chapter 10.1-10.2
Tue, May 7, 2013 Coping with NP-completeness, same lecture as the previous class Chapter 11.1, 11.3 Homework 7 due
Wed, May 8, 2013 Final examination assigned
Wed, May 15, 2013 Final examination due
Last modified: Thu Feb 7 12:02:49 EST 2013