CMSC 451: Design and analysis of computer algorithms (Spring 2024, Section 0101)

Overview

This course presents fundamental techniques for designing efficient computer algorithms, proving their correctness, and analyzing their performance. Topics to be covered include graph algorithms, greedy algorithms, divide-and-conquer algorithms, dynamic programming, network flow algorithms, computational intractability, approximation algorithms, randomized algorithms, and quantum algorithms.

Prerequisites

CMSC 351. Students are expected to be familiar with basic programming (loops, pointers, structures, recursion), discrete mathematics (proof by induction, sets, permutations, combinations, probability), calculus (manipulation of logarithms, differentiation, integration), data structures (lists, stacks, queues, trees, graphs, heaps), sorting algorithms (MergeSort, QuickSort, HeapSort), and graph algorithms (minimum spanning trees, Dijkstra's algorithm). If any of this material seems unfamiliar, please see the instructor or a teaching assistant as soon as possible to discuss it.

Coordinates

Instructor

Andrew Childs (amchilds@umd.edu)
In-person office hour: Tuesday, noon–1 pm, ATL 3359 (enter QuICS suite through ATL 3100, turn left to enter wing 3, then turn right)
Zoom office hour: Wednesday, 2–3 pm (Zoom link provided on Canvas)

Teaching assistants

EmailOffice hours
Aditya Acharya adach@umd.edu Tuesday, 4–5 pm, AVW 4160
Thursday, 4–5 pm, Zoom
Quinten De Man deman@umd.edu Monday, 11 am–noon, AVW 4160
Wednesday, 9:30–10:30 am, AVW 4160
Allen Du adu1@umd.edu Wednesday, 3:30–4:30 pm, AVW 4160

Piazza

We will use Piazza for class announcements and discussion. You should sign yourself up for the course Piazza page as soon as possible. This is the best way to stay up to date on what is happening in the course and to quickly get help from classmates, TAs, and the instructor. Instead of emailing questions to the teaching staff, please post questions on Piazza. Please do not send messages to the course staff using the Canvas messaging system, and do not use any other online forum for course-wide discussion without prior permission of the instructor.

Texts

Primary: Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson (2006).

Supplemental: Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, and Clifford Stein, Introduction to Algorithms, MIT Press (1990).

Evaluation

Your final grade will be determined as follows:

Assignments 40%
Midterm exam 20%
Final exam 40%

Your lowest assignment grade will be dropped. If you are unable to complete an exam or assignment by its deadline due to an excused absence (as per the UMD course policies), the remaining assignments will be reweighted. Students who complete less than half of the coursework should expect to withdraw.

Assignments

There will be five homework assignments during the course. Assignments will be made available on Canvas and should be submitted using Gradescope. Please check that you are able to upload solutions by making a test submission well in advance of the first assignment deadline, and make sure your account is associated with the correct section of the course. Please submit completed assignments as PDF files, either as a typeset document or a clear scan of handwritten solutions, by the deadline stated on the assignment. Gradescope will not accept submissions after the deadline, and late assignments will not be accepted under any circumstances so that solutions can be made available promptly. You can replace a submission as many times as you like before the deadline (only the final version will be graded), so you are encouraged to make early submissions.

Your answers to the assignment problems should be written neatly and concisely, and you should always aim to present the simplest possible solution. Your assignment grades will be based on both correctness and clarity. Graded assignments will be available on Gradescope. If you think a problem has been graded incorrectly, you may submit a regrade request on Gradescope. Regrade requests must be submitted within three business days after an assignment is returned and should include a detailed justification.

You are encouraged to discuss homework problems with your peers, with the TAs, and with the course instructor. However, your solutions should be based on your own understanding and should be written independently. You should not read solutions for the same or similar problems to the ones you are assigned until after your assignment has been submitted. For each assignment, you will be asked to state that you have followed these guidelines, and to include a list of students in the class with whom you discussed the problems.

Exams

The class will include a midterm exam and a comprehensive final exam. You may consult textbooks and notes during the exams, but you cannot use electronic devices or any other resources.

You will take the midterm exam during the scheduled class time on Thursday, March 7. You will take the final exam at the registrar-scheduled time of 10:30 am–12:30 pm on Wednesday, May 15. Both exams will be held in the regular lecture room, IRB 0318.

Topics

We plan to cover the following topics (possibly with minor changes):

Course policies and academic accommodations

We will follow the standard University of Maryland course policies. You should be familiar with them.

Any student eligible for and requesting reasonable academic accommodations due to a disability is asked to provide, to the instructor by email, a letter of accommodation from the Accessibility and Disability Service office within the first two weeks of the semester.

If you plan to observe any holidays during the semester that are not listed on the university calendar, please provide a list of these dates by the end of the first two weeks of the semester.

Course evaluations

Student feedback is an important part of evaluating instruction. The Department of Computer Science takes this feedback seriously and appreciates your input. Toward the end of the semester, please go to www.courseevalum.umd.edu to complete your evaluation.

Web Accessibility