CS 4104 Data and Algorithm Analysis
Instructor for CS 4104 at Virginia Tech (Summer 2025) — design and analysis of efficient algorithms.
Instructor: Zhongdong Liu
Term: Summer
Location: Virginia Tech (Online)
Course Overview
I was the Instructor for CS 4104 Data and Algorithm Analysis at Virginia Tech in Summer 2025. The course gives students an understanding of the principles and techniques used in the design and analysis of efficient algorithms, emphasizing critical thinking, problem-solving, and rigorous analysis. Core topics span Greedy Algorithms, Divide and Conquer, Dynamic Programming, and Network Flow, taught through a selection of classic algorithms.
Role: Instructor (full responsibility for lectures, course design, assessments, and TA supervision)
Term: Summer 2025
Delivery: Online (synchronous, Tue & Thu)
Teaching assistants supervised: 2
Prerequisites
CS 3114 (Data Structures and Algorithms, grade of C or better), plus MATH 3134 (Applied Combinatorics and Graph Theory) or MATH 3034 (Introduction to Proofs).
Textbooks
- Algorithm Design, Jon Kleinberg and Éva Tardos, Addison-Wesley, 2005. (Required)
- Introduction to Algorithms, 3rd ed., Cormen, Leiserson, Rivest, and Stein, MIT Press, 2009. (Supplemental)
Assessment
- Homework — 70%. 6–7 problem sets typeset in LaTeX. Each algorithm answer required pseudocode, a proof of correctness/optimality, and a running-time analysis. Assignments were due every two weeks.
- Comprehensive final exam — 30%.
Schedule
| Week | Date | Topic | Materials |
|---|---|---|---|
| 1 | Course Overview & Introduction (Ch. 1) Course logistics, stable matching, and representative algorithmic problems. | ||
| 2 | Algorithm Analysis (Ch. 2) Asymptotic notation, common running times, and analyzing efficiency. | ||
| 3 | Graphs (Ch. 3) Graph representations, BFS/DFS, connectivity, and topological order. | ||
| 4–5 | Greedy Algorithms (Ch. 4) Interval scheduling, shortest paths, minimum spanning trees, and exchange-argument proofs. | ||
| 6–7 | Divide and Conquer (Ch. 5) Recurrences and the master method, mergesort, counting inversions, and closest pair. | ||
| 8–9 | Dynamic Programming (Ch. 6) Weighted interval scheduling, subset sums/knapsack, sequence alignment, and shortest paths. | ||
| 10–11 | Network Flow (Ch. 7) Max-flow/min-cut, Ford–Fulkerson, bipartite matching, and flow applications. | ||
| 12 | Final Examination Comprehensive final exam. |