CMSC451: Design and Analysis of Computer Algorithms
CMSC451 is a traditional upperlevel 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:
 divide and conquer
 greedy algorithms
 dynamic programming
 graph algorithms (search, matchings, network flow)
 approximation algorithms
 randomized algorithms
 computational intractability
 algorithm design in other models of computation (parallel, quantum)
Location: CSI 2117
Section 0101 (Aravind Srinivasan): TuTh, 11am – 12:15pm
Section 0201 (Laxman Dhulipala): MW, 2pm – 3:15pm
News
 Please join the Piazza forum for this course and check
that you can access Gradescope well in advance of the
due date of the first assignment.
Schedule
 1. T/TH: August 30; M/W: August 29 — Course Overview and Introduction
 Textbook Reading: Chapter 1 of Kleinberg and Tardos
 Understanding Science Through the Computational Lens by Richard Karp (link)
 Chapter 20 of Mathematics + Computation by Avi Wigderson (link)
 Short Reference Guide for 451 by Dave Mount (link)
 2. T/Th: September 1; M/W: August 31 — Example: Stable Matching [A1 out on 8/30]
 Textbook Reading: Chapter 1 of Kleinberg and Tardos
 Stable matching: Theory, evidence, and practical design (Nobel Prize Citation) (link)
 The Power of the DigiComp II by Scott Aaronson (link)
 A Stable Marriage Requires Communication by Gonczarowski et al. (link)
 3. T/Th: September 6; M/W: September 7 — Math Background
 Textbook Reading: 2.1–2.4 of Kleinberg and Tardos
 Short Reference Guide for 451 by Dave Mount (link)
 Additional Notes on Induction (link)
 4. T/Th: September 8; M/W: September 12 — BreadthFirst Search, Bipartiteness, Connectivity
 Textbook Reading: 3.1–3.5 of Kleinberg and Tardos
 5. T/Th: September 13; M/W: September 14 — DFS, Topological Sorting [A1 due Sep 14, A2 out]
 Textbook Reading: 3.6 of Kleinberg and Tardos
 6. T/Th: September 15; M/W: September 19 — More Graph Algorithms
 Textbook Reading: Chapter 3 of Kleinberg and Tardos
 Additional Notes on Graphs (link)
 7. T/Th: September 20; M/W: September 21 — Greedy Algorithms: Shortest Paths and MSTs
 Textbook Reading: 4.1, 4.4, 4.5 of Kleinberg and Tardos
 8. T/Th: September 22; M/W: September 26 — Greedy Algorithms: Scheduling
 Textbook Reading: 4.2 of Kleinberg and Tardos
 9. T/Th: September 27; M/W: September 28 — DivideandConquer: Closest Points [A2 due Sep 28, A3 out]
 Textbook Reading: 5.1, 5.2, 5.4 of Kleinberg and Tardos
 10. T/Th: September 29; M/W: October 3 — DivideandConquer: Polynomial Multiplication and FFT
 Textbook Reading: 5.5, 5.6 of Kleinberg and Tardos
 11. T/Th: October 4; M/W: October 5 — DivideandConquer: Parallel Algorithms
 12. T/Th: October 6; M/W: October 10 — Dynamic Programming: Weighted Interval Scheduling
 Textbook Reading: 6.1, 6.2 of Kleinberg and Tardos
 13. T/TH: October 11; M/W: October 12 — Dynamic Programming: Knapsack [A3 due Oct 12, A4 out]
 Textbook Reading: 6.4 of Kleinberg and Tardos
 14. T/Th: October 13; M/W: October 17 — Dynamic Programming: Sequence Alignment
 Textbook Reading: 6.6 of Kleinberg and Tardos
 15. T/Th: October 18; M/W: October 19 — Dynamic Programming: NegativeWeight Shortest Paths
 Textbook Reading: 6.8 of Kleinberg and Tardos
 16. T/Th: October 20; M/W: October 24 — Dynamic Programming Continued [A4 due Oct 24]
 Textbook Reading: Chapter 6 of Kleinberg and Tardos
 T/Th: October 25; M/W: October 26 — Midterm
 Make sure to attend your section’s exam (T/Th is Section 101, M/W is Section 201)
 17. T/Th: October 27; M/W: October 31 — Network Flow: FordFulkerson [A5 out Oct 31]
 Textbook Reading: 7.1, 7.2 of Kleinberg and Tardos
 18. T/Th: November 1; M/W: November 2 — Network flow: Bipartite Matching
 Textbook Reading: 7.5 of Kleinberg and Tardos
 19. T/Th: November 3; M/W: November 7 — Complexity: P, NP, reductions
 Textbook Reading: 8.1, 8.2 of Kleinberg and Tardos
 20. T/Th: November 8; M/W: November 9 — NPcompleteness
 Textbook Reading: 8.3, 8.4 of Kleinberg and Tardos
 21. T/Th: November 10; M/W: November 14 — NPcomplete Problems [A5 due Nov 14, A6 out]
 Textbook Reading: 8.5–8.8 of Kleinberg and Tardos
 22. T/Th: November 15; M/W: November 16 — Approximation Algorithms: Load Balancing
 Textbook Reading: 11.1 of Kleinberg and Tardos
 23. T/Th: November 17; M/W: November 21 — Approximation Algorithms: Set Cover
 Textbook Reading: 11.3 of Kleinberg and Tardos
 24. T/Th: November 22; M/W: Recorded — Randomized Algorithms: MinCut
 Textbook Reading: 13.2 of Kleinberg and Tardos

25. T/Th: November 24; M/W: November 28 — Randomized Algorithms: Game Tree Evaluation [A6 due Nov 28, Final Practice out]

26. T/Th: November 29; M/W: November 30 — Quantum Algorithms

27. T/Th: December 1; M/W: December 5 — TBA

28. T/Th: December 6; M/W: December 7 — TBA
 29. T/Th: December 8; M/W: December 12 — Final Review
Textbook and Related Resources
The required textbook is Algorithm Design by Kleinberg and Tardos.
We may also occasionally use, among others, the following excellent publiclyavailable resources:
We will sometimes add links to other useful resources which provide
additional context or further investigation of the problems discussed
in lecture to the Schedule.
We thank the authors for these very helpful resources.
There will be a combination of written homeworks (about six), a
midterm exam, and a comprehensive final exam.
All homework is to be done individually, but discussions with
classmates are encouraged: just list the classmates you discussed the
assignment with.
Please ensure that you typeset your homework in LaTeX. You can find
many templates online, and here is one.
There are two sections of the course, one taught by Aravind and the
other by Laxman. We will use the same homeworks for both sections, but
the content of the midterm and final exam will be different.
Therefore, we recommend attending the lectures for your section.
Final grades will be calculated as:
 35% homework (lowest homework dropped)
 25% midterm
 40% final
Homeworks are to be turned in at the start of class on the due date.
Since homework solutions will be handed out on the day the homework is
due, no late homeworks will be accepted. You can discuss homeworks
with other students, but with no help from the Web or other sources.
Assignments are to be written up independently by each student,
regardless of collaboration. If you have questions, please talk to the
TA or the Instructor. It is your responsibility to make sure that you
pick up all homeworks and handouts. All course information and
handouts will be available on Piazza and Canvas.
Course Organization
 Announcements, discussion, and assignments posted on Piazza
 Assignment submission and feedback on Gradescope
 Office hours inperson; details below.
Prerequisites
CMSC 351. You should be familiar with discrete mathematics (induction,
sets, combinatorics, probability), data structures (lists, queues,
stacks, graphs, heaps), sorting algorithms, and some basic graph
algorithms (Dijkstra’s algorithm, minimum spanning trees, graph
search). If you have any questions about the background material,
please reach out to the instructors.
Mask Policy
We will follow the masking and health guidelines laid out by
the University. Note that masking is still recommended: “Effective
Monday, August 29, wearing a mask will not be required while indoors
in most situations, including classrooms. However, wearing a KN95
mask is recommended while indoors for added protection.”
Our Pledge to the Students
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.
Instructors
Aravind Srinivasan. Office hours: Tuesday and Thursday 2–3PM, Location: IRB 4164, additionally by appointment
Laxman Dhulipala. Office hours: Monday and Wednesday 3:30–4:30PM, Location: IRB 5150, additionally by appointment
Teaching Assistants
Unless announced otherwise, hours will be held in IRB 2207 Open Area (the open area across from IRB 2207).
Dhruva Sahrawat. Office hours: Wednesday and Saturday 12–1pm, Location: Zoom (please see Piazza)
Keivan Rezaei. Office hours: Wednesday and Friday 9–10am
Kishen Gowda. Office hours: Tuesday and Thursday 4–5pm
Yunheng Han. Office hours: Monday and Friday 1–2pm
Academic Accomodations for Disabilities
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.
Web accessibility