Data and Algorithm Analysis
As offered at VT (Summer '24)
About the Course
This course emphasizes understanding data structures and algorithms from an analytical perspective rather than an implementation standpoint. The concepts developed in this course enable discussion of algorithm efficiency and allow comparisons between algorithms in terms of space and runtime requirements. Analytical methods are used to describe both theoretical and practical performance bounds.
Overall, the course introduces key paradigms for algorithm design, explores constraints that affect problem solvability, and presents the theory of NP-completeness as a means to understand intractable problems.
Course Outline
Below is the tentative schedule for the course. It may be adjusted as the semester progresses. Students are expected to supplement lectures with careful study of the relevant sections of the textbook.
| Lecture | Topic | Reading |
|---|---|---|
| 1 | Introduction and Course Logistics (Slides, Lecture Note) | |
| 2 | Stable Matching (Slides) | Chapter 1 |
| 3 | Algorithm Analysis: Runtime and Proof of Correctness (Slides, Lecture Note) | Chapter 2 |
| 4 | Algorithm Analysis: Rate of Growth (Same slides as Lecture 3) | |
| 5 | Graphs (Slides) | Chapter 3 |
| 6 | Greedy Algorithms for Scheduling Problems (Slides) | Chapter 4 |
| 7–9 | Continued: Greedy Algorithms (Same slides as Lecture 6) | |
| 10–12 | Divide and Conquer (Slides) | Chapter 5 |
| 13–15 | Dynamic Programming (Slides) | Chapter 6 |
| 16 | Network Flow (Slides) | Chapter 7 (Sections 7.1 & 7.2) |
| 17–18 | NP and Computational Intractability (Slides) | Chapter 8 |
Textbook
- Algorithm Design by Jon Kleinberg and Éva Tardos. Addison-Wesley, 2006. ISBN: 0321295358.
Additional Reference
- Introduction to Algorithms (Fourth Edition) by Cormen, Leiserson, Rivest, and Stein. MIT Press, 2022. ISBN: 9780262046305.
Reading
Reading assignments will be announced on the class webpage. Students are strongly encouraged to complete the readings before class sessions.
Grading
Homework will be assigned every two to three weeks. There will be a midterm and a comprehensive final exam. All assignments and exams are due by midnight on the specified deadline.
Grading Breakdown
- 20% Midterm Exam (Take-home)
- 30% Final Exam (Take-home)
- 50% Homework
Homework and Exam Policies
- Each homework will include multiple problems and will be due approximately one week after being posted.
- Homework and exams will be posted on the class Canvas page. Submissions must be made via Canvas.
- All submissions must be typeset (LaTeX is recommended). Handwritten solutions will not be accepted.
- Late submissions will not be graded unless prior approval is obtained from the instructor.
- Some homework problems may be challenging; start early and utilize TA office hours.
- Regrade requests must be submitted within one week of receiving the graded assignment.
| Homework/Exam | LaTeX Source |
|---|---|
| Homework 1 | Starter |
| Homework 2 | Starter |
| Homework 3 | Starter |
| Homework 4 | Starter |
| Midterm | Starter |
| Final | Starter |