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

Teaching Assistant

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 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