CS 4104: Data and Algorithm Analysis (Spring 2016)

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

Teaching Assistants

Class Meeting Times and Contact Info:

Course Description and Syllabus

Homework Assignments

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