CMSC 451: Design and analysis of computer algorithms (Spring 2018)

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.

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.

Time: Tuesday/Thursday, 11:00 am–12:15 pm
Location: CHE 2110

Andrew Childs (amchilds@umd.edu)
Office hours: Tuesday 12:30–1:30 pm (AVW 3225), Wednesday 3:00–4:00 pm (ATL 3100F); also available by appointment

	Email	Office hours (in AVW 4101/4103)
Aditya Acharya	adach@umd.edu	Tuesday 4:00–6:00 pm
Katherine Chase	kmchase@umd.edu	Wednesday 10:30–11:30 am
Aounon Kumar	aounon@umd.edu	Monday 11:00 am–noon, Wednesday 2:00–3:00 pm

We will use Piazza for class announcements and online discussion. This is the best way to quickly get help from classmates, the TAs, and the instructor. Rather than emailing questions to the teaching staff, we strongly encourage you to post questions to Piazza at https://piazza.com/umd/spring2018/cmsc451/home.

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).

Your final grade will be determined as follows:

Assignments	25% (lowest assignment grade will be dropped)
Midterm exam	25%
Final exam	50%

There will be 5–7 homework assignments during the course. Assignments will be made available on the campus ELMS at https://myelms.umd.edu. You should submit completed assignments through the ELMS in PDF format, either as a typeset document or a clear scan of handwritten solutions, by the start of class on the due date. The system will not accept submissions after the deadline, and since solutions will be posted on the course website promptly, late assignments will not be accepted. However, the 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 the ELMS, and grades will also be recorded there.

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.

The class will include both a midterm exam and a comprehensive final exam. Both exams will be given in class. The midterm exam will be held on Thursday, March 15, from 11:00 am--12:15 pm. The final exam will be held on Saturday, May 12, from 8:00--10:00 am (as scheduled by the registrar).

The following is list of topics is tentative and subject to change:

• Introduction and mathematical background
• Graph algorithms: connectivity, bipartiteness, topological sorting
• Greedy algorithms: shortest paths, minimum spanning trees, scheduling
• Divide-and-conquer algorithms: geometric algorithms, fast Fourier transform
• Dynamic programming: weighted interval scheduling, knapsack, sequence alignment, shortest paths
• Network flows: Ford-Fulkerson algorithm, applications
• NP-completeness: P and NP, reductions, the Cook-Levin theorem
• Approximation algorithms: load balancing, set cover
• Randomized algorithms: minimum cut, game tree evaluation
• Quantum algorithms: quantum circuits, Deutsch and Simon problems, factoring

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.

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.