CMSC451: Design and Analysis of Computer Algorithms

CMSC451 is a traditional 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:

Location: CSI 2117

Section 0101 (Aravind Srinivasan): TuTh, 11am – 12:15pm

Section 0201 (Laxman Dhulipala): MW, 2pm – 3:15pm

News

Schedule

The required textbook is Algorithm Design by Kleinberg and Tardos. We may also occasionally use, among others, the following excellent publicly-available 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.

Course Format and Grading

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:

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

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: Tuesday and Thursday 5–6pm

Kishen Gowda. Office hours: Tuesday and Friday 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