CS 5114: Theory of Algorithms

Fall 2007

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_11787@listserv.vt.edu

Course Description and Syllabus

Homework Assignments

Homework 1 (Assigned on January 28, 2008; due at start of class on February 4, 2008).
Homework 2 (Assigned on February 4, 2008; due at start of class on February 11, 2008).
Homework 3 (Assigned on February 20, 2008; due at start of class on February 27, 2008).
Homework 4 (Assigned on February 27, 2008; submit by email (PDF only) or in my office (hardcopy) by 5pm on March 5, 2008).
Homework 5 (Assigned on March 26, 2008; due at start of class on April 2, 2008)
Homework 6 (Assigned on April 9, 2008; due at start of class on April 23, 2008)

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
Mon, Jan 14, 2008	Introduction and Course Logistics
Wed, Jan 16, 2008	Analysis of Algorithms	Chapter 2.1-2.4
Mon, Jan 21, 2008	Martin Luther King's birthday, no class.
Wed, Jan 23, 2008	Heaps and Priority Queues	Chapter 2.5
Read Chapter 3 for useful review on graphs.
Mon, Jan 28, 2008	Greedy Algorithms for Scheduling	Chapter 4.1-4.3	Homework 1 assigned
Wed, Jan 30, 2008	Greedy Graph Algorithms	Chapter 4.4-4.6
Mon, Feb 4, 2008	Greedy graph algorithms, same lecture as previous class		Homework 1 due Homework 2 assigned
Wed, Feb 6, 2008	Greedy graph algorithms, same lecture as previous class
Mon, Feb 11, 2008	Applications of MSTs	Chapter 4.7 and exercise 9 in Chapter 4	Homework 2 due
Wed, Feb 13, 2008	Divide and Conquer	Chapter 5.1-5.2
Mon, Feb 18, 2008	Divide and Conquer Algorithms	Chapter 5.3-5.5
Wed, Feb 20, 2008	Divide and Conquer Algorithms, same lecture as previous class	Chapter 5.3-5.5	Homework 3 assigned
Mon, Feb 25, 2008	Dynamic Programming	Chapter 6.1-6.3
Wed, Feb 27, 2008	Dynamic Programming, same lecture as previous class	Chapter 6.5	Homework 3 due Homework 4 assigned
Wed, Mar 5, 2008	Spring break. No class.		Homework 4 due.
Mon, Mar 10, 2008	Review for midterm examination		Midterm examination assigned PDF, LaTeX
Wed, Mar 12, 2008	Class cancelled
Mon, Mar 17, 2008	Dynamic Programming, same lecture as the class on February 25	Chapter 6.6, 6.8	Midterm examination due
Wed, Mar 19, 2008	Dynamic Programming, same lecture as the class on February 25
Mon, Mar 24, 2008	Network Flow	Chapter 7.1-7.3 On the history of the transportation and maximum flow problems
Wed, Mar 26, 2008	Network Flow, same lecture as the previous class		Homework 5 assigned
Mon, Mar 31, 2008	Applications of Network Flow	Chapter 7.5-7.6
Wed, Apr 2, 2008	Applications of Network Flow, same lecture as the previous class	Chapter 7.7-7.8, 7.10	Homework 5 due
Mon, Apr 7, 2008	NP and Computational Intractability	Chapter 8.1-8.2
Wed, Apr 9, 2008	NP and Computational Intractability, same lecture as previous class	Chapter 8.3-8.4	Homework 6 assigned
Mon, Apr 14, 2008	NP-Complete Problems	Chapter 8.5-8.7
Wed, Apr 16, 2008	University holiday
Mon, Apr 21, 2008	NP-Complete Problems, same lecture as the previous class	Chapter 8.8-8.10
Wed, Apr 23, 2008	Coping with NP-completeness	Chapter 10.1-10.2	Homework 6 due
Mon, Apr 28, 2008	Coping with NP-completeness
Wed, Apr 30, 2008	Coping with NP-completeness		Final examination assigned PDF, LaTeX

Last modified: Thu Mar 27 00:45:30 EDT 2008