Fall 2026
Time and Locations
Tuesday/Thursday, 9:30am – 10:45am, CSI 2117
Instructor
Laxman Dhulipala (IRB 5150); Office hours: TBD
Teaching Assistants
Kishen Gowda. Office hours: TBD
Quinten De Man. Office hours: TBD
Peter Li. Office hours: TBD
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).
Note: The date of the final exam is TBD based on when the registrar schedules our 9:30 timeslot on Tu/Th. Will update the date here once we find out.
| Date | Topic | Notes |
|---|---|---|
| Sep 01 (Tu) | Lecture 01: Selection | |
| Sep 03 (Th) | Lecture 02: More Selection and Lower Bounds | |
| Sep 08 (Tu) | Lecture 03: Amortization | [HW1 Out] |
| Sep 10 (Th) | Lecture 04: Universal Hashing | |
| Sep 15 (Tu) | Lecture 05: Hashing Wrapup and Streaming Algorithms | |
| Sep 17 (Th) | Lecture 06: Streaming Wrapup and Graphs 1 | |
| Sep 22 (Tu) | Lecture 07: Graphs 2: BFS and DFS | |
| Sep 24 (Th) | Homework 1 Writing Session | [HW2 Out] |
| Sep 29 (Tu) | Lecture 08: Graphs 3: SCCs and Kosaraju’s algorithm | |
| Oct 01 (Th) | Lecture 09: Divide and Conquer | |
| Oct 06 (Tu) | Lecture 10: Range Queries and Parallel Prefix Sum | |
| Oct 08 (Th) | Lecture 11: Greedy Algorithms | |
| Oct 13 (Tu) | No class (Fall Break) | |
| Oct 15 (Th) | Homework 2 Writing Session | [HW3 Out] |
| Oct 20 (Tu) | Lecture 12: Dynamic Programming 1 | |
| Oct 22 (Th) | Lecture 13: Dynamic Programming 2 | |
| Oct 27 (Tu) | Midterm | |
| Oct 29 (Th) | Lecture 14: Max Flow 1 | |
| Nov 03 (Tu) | Lecture 15: Max Flow 2 | |
| Nov 05 (Th) | Homework 3 Writing Session | [HW4 Out] |
| Nov 10 (Tu) | Lecture 16: Max Flow 3 | |
| Nov 12 (Th) | Lecture 17: Reductions 1 | |
| Nov 17 (Tu) | Lecture 18: Reductions 2 | |
| Nov 19 (Th) | Lecture 19: Reductions 3 | |
| Nov 24 (Tu) | Homework 4 Writing Session | [HW5 Out] |
| Nov 26 (Th) | No class (Thanksgiving Recess) | |
| Dec 01 (Tu) | Lecture 20: Reductions 4 and Approximation Algorithms | |
| Dec 03 (Th) | Lecture 21: Approximation Algorithms 2 (TSP) | |
| Dec 08 (Tu) | Homework 5 Writing Session (homework 5 will be short) | |
| Dec 10 (Th) | Lecture 22: Randomized Algorithms | |
| Finals Week | Final Exam (Exact date TBD based on registrar schedule for 9:30 Tu/Th timeslot) |
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 also include some (mild) extensions of the released homework problems to prevent rote memorization. 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.