Spring 2026
Time and Locations
Tuesday/Thursday, 9:30am – 10:45am, IRB 0318 (Section 201)
Tuesday/Thursday, 11:00am – 12:15pm, IRB 0318 (Section 301)
Instructor
Laxman Dhulipala (IRB 5150); Office hours Thursdays 1:00–2:00pm
Teaching Assistants
Quinten De Man. Office hours: TBD
Kishen Gowda. Office hours: TBD
Peter Li. Office hours: TBD
Richard Wen. Office hours: TBD
Zhongqi Wang. Office hours: TBD
Office hours will be held in the open work area near IRB 5136 and 5165.
CMSC451 is an upper-level course focused on the design and analysis of algorithms. The course presents fundamental techniques for designing efficient algorithms, proving their correctness, and analyzing their performance. Topics we will cover include:
Prerequisites: You should be comfortable with algorithm design and analysis (e.g., you should be comfortable with the material from CMSC351).
| Date | Topic | Notes |
|---|---|---|
| Jan 27 (Tu) | Introduction, Asymptotics, and Selection | |
| Jan 29 (Th) | Computational Models and Lower Bounds | [HW1 Out] |
| Feb 03 (Tu) | Amortized Analysis | |
| Feb 05 (Th) | Hashing 1: Universal and Perfect Hashing | |
| Feb 10 (Tu) | Hashing 2: Streaming | |
| Feb 12 (Th) | Homework 1 Writing Session | [HW2 Out] |
| Feb 17 (Tu) | Graphs 1: Representations, Basic algorithms | |
| Feb 19 (Th) | Graphs 2: SCC | |
| Feb 24 (Tu) | Graphs 3: Biconnectivity | |
| Feb 26 (Th) | Homework 2 Writing Session | [HW3 Out] |
| Mar 03 (Tu) | Divide and Conquer | |
| Mar 05 (Th) | Range Query Data Structures | |
| Mar 10 (Tu) | Dynamic Programming 1: Knapsack, Edit Distance | |
| Mar 12 (Th) | Dynamic Programming 2: APSP and LIS | |
| Mar 17 (Tu) | No class: Spring Break | |
| Mar 19 (Th) | No class: Spring Break | |
| Mar 24 (Tu) | Dynamic Programming 3: Negative-Weight SSSP | |
| Mar 26 (Th) | Homework 3 Writing Session | [HW4 Out] |
| Mar 31 (Tu) | Midterm 1 | |
| Apr 02 (Th) | Flows 1: Ford-Fulkerson | |
| Apr 07 (Tu) | Flows 2: Max-Flow Min-Cut Theorem | |
| Apr 09 (Th) | Flows 3: Bipartite Matching and Edmonds Karp | |
| Apr 14 (Tu) | HW4 Writing Session | [HW5 Out] |
| Apr 16 (Th) | Flows 4: Dinic’s Algorithm | |
| Apr 21 (Tu) | Linear Programming 1: Basics | |
| Apr 23 (Th) | Linear Programming 2: 2D-LP / Duality | |
| Apr 28 (Tu) | Complexity 1: P vs NP and Reductions | |
| Apr 30 (Th) | HW5 Writing Session | |
| May 05 (Tu) | Complexity 2: NP-Completeness | |
| May 07 (Th) | Complexity 3: Coping with NP Completeness | |
| Finals Week | Final Exam Window (May 11–18, exact date TBD by registrar) |
This semester we are trying something new with “writing sessions”. Here, you will write up a subset of the problems given on the homework in class using pen and paper. We will only grade this subset of handwritten problems to determine your grade for that homework. Each writing session is expected to take 1 hour, but we will give you the full class period to complete it.
If you cannot make it to a writing session for a good reason (e.g., conference travel, proof of sickness), you can make it up by completing it during office hours within one week of the writing session. Please coordinate with the TA/instructor whose office hours you will be attending to complete the homework writing.
As in prior semesters, the grading policy is very flexible.
First, your lowest homework grade will be dropped.
To compute your overall grade, we will first assign you a numerical score [0, 1] that satisfies the following:
max {(hw x hwscore) + (midterm x midtermscore) + (final x finalscore)} such that
{0.1 <= midterm <= 0.3},
{0.1 <= hw <= 0.7},
{0.1 <= final <= 0.35}, and
{hw + midterm + final = 1}
hwscore, midtermscore, and finalscore are your raw scores for each of these categories in [0, 1]. The homework score will be computed by summing up the points and dividing by the total (and ignoring the dropped homework).
Basically we will find the best multipliers to maximize your score, subject to the constraints above and calculate your raw number grade. The cutoffs to turn this into a letter grade may then be adjusted (only more generously) to assign your final letter grade.
Any student eligible for and requesting reasonable academic accommodations due to a disability is requested to provide, to the instructor in office hours, a letter of accommodation from the Office of Disability Support Services (DSS) within the first two weeks of the semester.
Your education is very important to us, and we respect each of you regardless of how you do in the class. Our expectations of you are that you attend class and pay full attention, and give enough time to the course. We strongly encourage you to ask questions in class, and to come to the office hours (the instructors’ or the TAs’) with any further questions. We can have a very enjoyable educational experience if you pay attention in class, give sufficient time to our course, and bring any difficulties you have promptly to our attention. We look forward to our interaction both inside and outside the classroom.