Fall 2023
Time and Locations
Tuesday/Thursday, 3:30pm – 4:45pm, IRB 0318
Instructor
Laxman Dhulipala (IRB 5150); Office hours Tuesday/Thursday 5 – 6pm
Teaching Assistants
Sharmila Dupalla. Office hours: Wednesday 5–6pm, Friday 5–6pm
Kishen Gowda. Office hours: Monday 3–4pm, Thursday 6–7pm
Sam Lee. Office hours: Monday 5–6pm, Friday 4–5pm
Peter Li. Office hours: Wednesday 3–5pm
Richard Wen. Office hours: Wednesday 5–7pm
Xinchen Yang. Office hours: Friday 12–2pm
Office hours will be held in the open work area near IRB 5136 and 5165. You can find a map here.
You can find the calendar with the office hours timings
here,
and also find this information below.
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:
You will also learn how to implement algorithms efficiently in practice as part of this course, using some tools from the competitive programming world.
Prerequisites: You should be comfortable with algorithm design and analysis (e.g., you should be comfortable with the material from CMSC351). Prior experience implementing some basic algorithms and data structures is helpful.
| Date | Topic |
|---|---|
| Aug 29 (Tu) | Introduction and Basics (Correctness, Efficiency Analysis) |
| Aug 31 (Th) | Computational Models and Lower Bounds |
| Sep 05 (Tu) | Amortized Analysis [HW1 Out] |
| Sep 07 (Th) | Amortization and Hashing |
| Sep 12 (Tu) | Perfect Hashing |
| Sep 14 (Th) | Streaming (Count-Min Sketch) |
| Sep 19 (Tu) | Graphs 1: BFS and DFS [HW1 Due] |
| Sep 21 (Th) | Divide and Conquer: Closest Pair [Hw2 Out] |
| Sep 26 (Tu) | Graphs 2: DFS and SCC |
| Sep 28 (Th) | Data Structures: Range Query |
| Oct 03 (Tu) | Greedy: Interval Scheduling |
| Oct 05 (Th) | Dynamic Programming 1 [HW3 Due, HW4 Out] |
| Oct 10 (Tu) | Dynamic Programming 2 |
| Oct 12 (Th) | Midterm |
| Oct 17 (Tu) | Flows 1: Ford-Fulkerson |
| Oct 19 (Th) | Flows 2: Max-Flow Min-Cut Theorem |
| Oct 24 (Tu) | Flows 3: Shortest Augmenting Paths |
| Oct 26 (Th) | Flows 4: Blocking Flows (Dinic’s) [HW3 Due Monday, HW 4 Out] |
| Oct 31 (Tu) | LP 1: LP Basics |
| Nov 02 (Th) | LP 2: Duality |
| Nov 07 (Tu) | Complexity 1: Reductions, P and NP |
| Nov 09 (Th) | Complexity 2: NP-Completeness |
| Nov 14 (Tu) | Complexity 3: NP-Completeness; Reductions [HW4 Due, HW5 Out] |
| Nov 16 (Th) | Approximation 1: Classic Examples |
| No class! | |
| Thanksgiving break | |
| Nov 28 (Tu) | Approximation 2: Set Cover |
| Nov 30 (Th) | Online Algorithms [HW5 Due, HW6 Out (short)] |
| Dec 05 (Tu) | Parallelism |
| Dec 07 (Th) | Life After your Degree [HW6 Due] |
| Dec 19 (Tu) | Final exam (Takehome) |
Your lowest homework grade will be dropped. You can submit homeworks up to four days late, with a 5% penalty per day. Late homeworks will not be accepted beyond four days so that we can release solutions in a timely manner.
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.