CS 4104: Data and Algorithm Analysis (Fall 2009)

This course emphasizes the understanding of data structures and algorithms from an analytical perspective rather than from an implementation standpoint. It covers methods to construct algorithms and to analyze algorithms mathematically for correctness and efficiency (i.e., running time and space used). The course starts with definitions of algorithmic efficiency, discusses powerful paradigms for algorithm design, and defines the theory of NP-completeness as a means to understand intractable problems.

Instructor

T. M. Murali

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

Teaching Assistant

Class Meeting Times and Contact Info:

CS4104_91844@listserv.vt.edu

Course Description and Syllabus

Homework Assignments

Homework 1 (Assigned on August 31, 2009; due at start of class on September 7, 2009).
Homework 2 (PDF, LyX, LaTeX, Assigned on September 9, 2009; due at start of class on September 16, 2009).
Homework 3 (PDF, LyX, LaTeX, Assigned on September 16, 2009; due at start of class on September 23, 2009).
Homework 4 (PDF, LyX, LaTeX, Assigned on September 28, 2009; due at start of class on October 5, 2009).
Homework 5 (PDF, LyX, LaTeX, Assigned on October 5, 2009; due at start of class on October 12, 2009).
Homework 6 (PDF, LyX, LaTeX, Assigned on November 2, 2009; due at start of class on November 9, 2009).
Homework 7 (PDF, LyX, LaTeX, Assigned on November 20, 2009; due at start of class on December 2, 2009).

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 homework assigments. Murali will send email to the listserv as soon as a homework is assigned.
All chapters below refer to the textbook, "Algorithm Design" by Kleinberg and Tardos, unless specified otherwise.

Date	Topic	Reading	Homework
Mon, Aug 24, 2009	Introduction and Course Logistics
Wed, Aug 26, 2009	Analysis of Algorithms	Chapter 2.1-2.4
Mon, Aug 31, 2009	Heaps and Priority Queues	Chapter 2.5	Homework 1 assigned
Wed, Sep 2, 2009	Graphs and graph traversal	Chapter 3.1-3.3
Mon, Sep 7, 2009	Graphs and graph traversal, same lecture as the previous class		Homework 1 due
Wed, Sep 9, 2009	Implementing BFS and DFS, same lecture as the previous class Linear-time graph algorithms	Chapter 3.4-3.5	Homework 2 assigned
Mon, Sep 14, 2009	Greedy Algorithms for Scheduling	Chapter 4.1-4.2
Wed, Sep 16, 2009	Greedy Algorithms for Scheduling, same lecture as previous class Greedy Graph Algorithms	Chapter 4.4-4.6	Homework 2 due Homework 3 assigned
Mon, Sep 21, 2009	Greedy graph algorithms, same lecture as the last class.
Wed, Sep 23, 2009	Greedy graph algorithms, same lecture as the last class.		Homework 3 due
Mon, Sep 28, 2009	An Application of MSTs	Chapter 4.7	Homework 4 assigned
Wed, Sep 30, 2009	Divide and Conquer	Chapter 5.1-5.2
Mon, Oct 5, 2009	Divide and Conquer Algorithms	Chapter 5.3-5.5	Homework 4 due Homework 5 assigned
Wed, Oct 7, 2009	Divide and Conquer Algorithms, same lecture as previous class
Mon, Oct 12, 2009	Review for midterm examination		Homework 5 due Midterm examination assigned PDF, LaTeX, LyX
Wed, Oct 14, 2009	Dynamic Programming	Chapter 6.1-6.3
Mon, Oct 19, 2009	Dynamic Programming, same lecture as previous class	Chapter 6.5
Wed, Oct 21, 2009	Dynamic Programming, same lecture as the class on Oct 14	Chapter 6.5	Midterm examination due
Mon, Oct 26, 2009	Dynamic Programming, same lecture as the class on Oct 14	Chapter 6.6, 6.8
Wed, Oct 28, 2009	Dynamic Programming, same lecture as the class on Oct 14
Mon, Nov 2, 2009	Discussion of solutions to the midterm examination		Homework 6 assigned Solutions to the midterm examination
Wed, Nov 4, 2009	Network Flow	Chapter 7.1-7.3 On the history of the transportation and maximum flow problems
Mon, Nov 9, 2009	Network Flow, same lecture as the previous class		Homework 6 due
Wed, Nov 11, 2009	Class cancelled
Mon, Nov 16, 2009	Applications of Network Flow	Chapter 7.5-7.6, 7.10
Wed, Nov 18, 2009	Applications of Network Flow, same lecture as the previous class		Homework 7 assigned (on Nov 20)
Mon, Nov 23, 2009	Thanksgiving break
Wed, Nov 27, 2009	Thanksgiving break
Mon, Nov 30, 2009	NP and Computational Intractability	Chapter 8.1-8.2
Wed, Dec 2, 2009	NP-Complete Problems	Chapter 8.3-8.4	Homework 7 due Final examination assigned PDF, LyX, LaTeX
Mon, Dec 7, 2009	Review for final examination
Wed, Dec 9, 2009	Class cancelled
Mon, Dec 14, 2009	5pm, final examination due

Last modified: Thu Dec 3 10:15:39 EST 2009