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

T. M. Murali

Please include "CS 5114" in the subject line of all email messages that you send me.

Teaching Assistant

Class Meeting Times and Contact Info:

CS5114_11910@listserv.vt.edu

Course Description and Syllabus

Homework Assignments

Homework 1 (Assigned on January 29, 2009; due at start of class on February 5, 2009).
Homework 2 (Assigned on February 5, 2009; due at start of class on February 12, 2009).
Homework 3 (Assigned on February 12, 2009; due at start of class on February 19, 2009).
Homework 4 (Assigned on February 26, 2009; due at start of class on March 5, 2008).
Homework 5 (Assigned on March 26, 2009; due at start of class on April 2, 2009)
Homework 6 (Assigned on April 9, 2009; due at start of class on April 21, 2009)
Practice Homework 7 (Assigned on April 30, 2009. Do not turn in solutions. This homework is only for practice.)

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