CS 4104: Data and Algorithm Analysis (Spring 2017)

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

Wenjie Zhuang, (GTA)
Email: kaito@vt.edu
Office Hours: McBryde 106, 11am-1pm Tuesdays and 9am-11am Wednesdays, starting the week of January 30, 2017.
Peter Steele (UTA)
Email: peter707@vt.edu
Office Hours: McBryde 106, 10:30am-1:30pm on Thursdays, and 3pm to 4pm on Fridays, starting the week of January 30, 2017.

Class Meeting Times

Course Description and Syllabus

Homework Assignments

Homework 1, PDF, LaTeX (Assigned on January 30, 2017; due by the start of class on February 6, 2017).
Homework 2, PDF, LaTeX (Assigned on February 8, 2017; due at start of class on February 15, 2017).
Homework 3, PDF, LaTeX (Assigned on February 15, 2017; due at start of class on February 27, 2017, and yes, you have 12 days to work on this assignment).
Homework 4, PDF, LaTeX (Assigned on March 1, 2017; due by 5pm on Friday, March 17, 2017).
Homework 5, PDF, LaTeX (Assigned on March 29, 2017; due at the start of class on April 5, 2017).
Homework 6, PDF, LaTeX (Assigned on April 17, 2017; due at the start of class on April 24, 2017)
Homework 7, PDF, LaTeX (Assigned on April 24, 2017; due at the start of class on May 1, 2017)

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