CMSC 451: Design and analysis of computer algorithms (Fall 2019, Sections 0101 and 0201)

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 there is any material that seems unfamiliar, please see the instructor or a teaching assistant as soon as possible to discuss it.

Coordinates

Instructor

Andrew Childs (amchilds@umd.edu)
Office hours: Monday 3–4 pm and Thursday 11 am–noon, ATL 3100F; also available by appointment

Teaching assistants

EmailOffice hours (in AVW 1120)
Aditya Acharya adach@umd.edu Monday 4–6 pm
Aranya Banerjee abanerj3@terpmail.umd.edu Wednesday noon–1 pm
Dan Hofman dhofman@cs.umd.edu Tuesday 9:30–11:30 am
Aounon Kumar aounon@umd.edu Monday 2–3 pm, Wednesday 11 am–noon
Nishant Rodrigues ngrodrig@cs.umd.edu Monday noon–1 pm, Wednesday 2–3 pm
Jue Xu juexu@terpmail.umd.edu Tuesday/Thursday 12:40–1:40 pm
William Xu wxuxu@terpmail.umd.edu Tuesday 11 am–noon, Thursday 10–11 am
Jiejun Zhang jzhang40@terpmail.umd.edu Wednesday 10–11 am

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 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 use any other online forum for course 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 35% (lowest assignment grade will be dropped)
Midterm exam 20%
Final exam 45%

Assignments

There will be approximately six homework assignments during the course. Assignments will be made available on Piazza and should be submitted to Gradescope. Please check that you are able to upload solutions by making a test submission well in advance of the first assignment deadline. Please submit completed assignments in PDF format, either as a typeset document or a clear scan of handwritten solutions. Assignments are due by 1:30 pm on the due date. The system will not accept submissions after the deadline, and late assignments will not be accepted under any circumstances. You can replace a submission as many times as you like before the deadline, and only the final version will be graded. Your lowest assignment grade will be dropped.

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, and grades will also be recorded there. If you think a problem has been graded incorrectly, you may submit a regrade request on Gradescope. Regrade requests must be submitted within three days after an assignment is returned and should include a detailed justification. The course staff will carefully review your solution and could raise or lower your score.

You are encouraged to discuss homework problems with your peers, with the TA, and with the course instructor. However, your solutions should be based on your own understanding and should be written independently. For each assignment, you must either include a list of students in the class with whom you discussed the problems, or else state that you did not discuss the assignment with your classmates.

Exams

The class will include a midterm exam and a comprehensive final exam. The midterm exam will be held on Thursday, October 10, at the regular class time and place (IRB 0318). The final exam for both sections of the course will be held on Monday, December 16, from 6:30–8:30 pm (as scheduled by the registrar). The final exam will be held in ARC 0204.

Topics

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

Course policies and academic accommodations

You should be familiar with the University of Maryland course policies.

As mentioned above, extensions to assignment due dates will not be granted for any reason, so that all students can have timely access to solutions. In circumstances that justify an excused absence, appropriate accommodations will be made, in accordance with the course-related policies described at the above link.

Any student eligible for and requesting reasonable academic accommodations due to a disability is asked to provide, to the instructor during office hours, a letter of accommodation from the Accessibility and Disability Service (ADS) 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 and its faculty take this feedback seriously, and appreciate your input. Toward the end of the semester, please go to www.courseevalum.umd.edu to complete your evaluation.

Web Accessibility