CS 4104: Data and Algorithm Analysis (Spring 2014)

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" and a brief topic in the subject line of all email messages that you send me.

Teaching Assistants

Sorour Ekhtiari Amiri (GTA)
Email: esorour@vt.edu
Office Hours: 9am-11am, Tuesdays and Thursdays, McBryde 106
Brendan Avent (UTA)
Email: bavent@vt.edu
Office Hours: 10am-12pm, Fridays, McBryde 106

Class Meeting Times and Contact Info:

Homework Assignments

Homework 1, PDF, LaTeX (Assigned on January 29, 2014; due by the start of class on February 10, 2014).
Homework 2, PDF, LaTeX (Assigned on February 17, 2014; due at start of class on February 26, 2014).
Homework 3, PDF, LaTeX (Assigned on February 26, 2014; due at start of class on March 5, 2014).
Homework 4, PDF, LaTeX (Assigned on March 5, 2014; due at start of class on March 19, 2014).
Homework 5, PDF, LaTeX (Assigned on April 2, 2014; due by 11:55pm on April 11, 2014) --
Homework 6, PDF, LaTeX (Assigned on April 14, 2014; due by 11:55pm on April 23, 2014)
Homework 7, PDF, LaTeX (Assigned on April 23, 2014; due by 11:55pm on May 6, 2014)

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
Wed, Jan 22, 2014	Introduction and Course Logistics
Mon, Jan 27, 2014	Analysis of Algorithms	Chapter 2.1-2.4
Wed, Jan 29, 2014	Heaps and Priority Queues	Chapter 2.5	Homework 1 assigned
Mon, Feb 3, 2014	Heaps and Priority Queues, same lecture as the previous class
Wed, Feb 5, 2014	Graphs and graph traversal	Chapter 3.1-3.3
Mon, Feb 10, 2014	Graphs and graph traversal, same lecture as the previous class		Homework 1 due
Wed, Feb 12, 2014	Class cancelled by university
Mon, Feb 17, 2014	Linear-time graph algorithms	Chapter 3.4-3.5	Homework 2 assigned
Wed, Feb 19, 2014	Greedy Algorithms for Scheduling	Chapter 4.1-4.2
Mon, Feb 24, 2014	Greedy Algorithms for Scheduling, same lecture as the previous class	Chapter 4.1-4.2
Wed, Feb 26, 2014	Greedy Graph Algorithms	Chapter 4.4-4.6	Homework 2 due Homework 3 assigned
Mon, Mar 3, 2014	Greedy Graph Algorithms, same lecture as the previous class
Wed, Mar 5, 2014	Greedy Graph Algorithms, same lecture as the class on Feb 26		Homework 3 due Homework 4 assigned
Mon, Mar 17, 2014	Divide and Conquer	Chapter 5.1-5.2	Homework 4 due
Wed, Mar 19, 2014	Divide and Conquer Algorithms	Chapter 5.3-5.5	Midterm examination assigned PDF, LaTeX
Mon, Mar 24, 2014	Divide and Conquer Algorithms same lecture as the previous class Dynamic Programming	Chapter 6.1-6.3
Wed, Mar 26, 2014	Dynamic Programming, same lecture as the previous class	Chapter 6.1-6.3	Midterm examination due
Mon, Mar 31, 2014	Dynamic Programming, same lecture as the previous class	Chapter 6.5, 6.8
Wed, Apr 2, 2014	Dynamic Programming, same lecture as the previous class Network Flow	Chapter 7.1-7.3 On the history of the transportation and maximum flow problems	Homework 5 assigned
Mon, Apr 7, 2014	Network Flow, same lecture as the previous class
Wed, Apr 9, 2014	Network Flow, same lecture as the previous class		Homework 5 due
Mon, Apr 14, 2014	Applications of Network Flow	Chapter 7.5-7.6	Homework 6 assigned
Wed, Apr 16, 2014	Applications of Network Flow, same lecture as the previous class	Chapter 7.6
Mon, Apr 21, 2014	Applications of Network Flow, same lecture as the previous class	Chapter 7.10
Wed, Apr 23, 2014	NP and Computational Intractability	Chapter 8.1-8.2	Homework 6 due Homework 7 assigned
Mon, Apr 28, 2014	NP and Computational Intractability, same lecture as previous class NP-Complete Problems	Chapter 8.3-8.4 Chapter 8.5
Wed, Apr 30, 2014	NP-Complete Problems, same lecture as the previous class	Chapter 8.6-8.7
Mon, May 5, 2014	Coping with NP-completeness	Chapter 10.1-10.2	Homework 7 due
Mon, May 5, 2014	Final examination assigned PDF, LaTeX
Wed, May 7, 2014	Coping with NP-completeness, same lecture as the previous class	Chapter 11.1, 11.3
Tue, May 13, 2014	Final examination due

Last modified: Tue Jan 21 12:02:49 EST 2014