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

This class will be held virtually, with no in-person meetings. In lieu of traditional lectures, we will have a combination of asynchronous lecture videos (which will present new course content) and live class meetings (where the instructor will answer questions, present examples, and discuss problems). Lecture videos will be made available on Canvas (also referred to as ELMS) each Monday and Wednesday to cover material that will be discussed in a live class meeting on Zoom the following day. We will reevaluate this format as the semester progresses and may make adjustments.

Note that another section of 451 is being offered this semester. The two sections will be very similar, but not identical. You are responsible for the material covered in the section in which you are registered.

- Lecture videos available Monday/Wednesday on Canvas
- Live class meetings
*Tuesday/Thursday, 2:00–3:15 pm*on Zoom (meeting link on Canvas) - Announcements/discussion on Piazza
- Assignment/exam problems/solutions on Canvas
- Assignment/exam submissions on Gradescope
- Office hours on Zoom (times listed below; meeting links on Canvas)

Andrew Childs (amchilds@umd.edu)

Office hours: Tuesday 10–11 am, Thursday noon–1 pm (Zoom link on Canvas)

Office hours: Tuesday 10–11 am, Thursday noon–1 pm (Zoom link on Canvas)

Office hours (Zoom links on Canvas) | ||
---|---|---|

Aditya Acharya | adach@umd.edu | Monday 10–11 am, Wednesday 4–5 pm |

Vikram Amin | vamin@umd.edu | Tuesday/Thursday 11 am–noon |

Dan Hofman | dhofman@cs.umd.edu | Monday 3–5 pm |

Aounon Kumar | aounon@umd.edu | Monday 11 am–noon, Wednesday 3–4 pm |

Eric Li | lieric@terpmail.umd.edu | Tuesday noon–1 pm |

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 use any other online forum for course discussion without prior permission of the instructor.

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 | 40% |

Midterm exam | 25% |

Final exam | 35% |

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 in place for Fall 2020), the remaining assignments will be reweighted. Students who complete less than half of the coursework should expect to withdraw.

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 avilable 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 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 TAs, and with the course instructor. However, your solutions should be based on your own understanding and should be written independently. You may not look at 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.

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 any other resources (in particular, internet access is not allowed). You will take the exams at home, working alone. You will be asked to sign an honor pledge indicating that you have followed the exam guidelines.

You will take the midterm exam during the scheduled class time on Tuesday, October 13. You will take the final exam at the registrar-scheduled time of 10:30 am–12:30 pm on Saturday, December 19. Both exams will be made available on Canvas half an hour before the scheduled start times and will be due on Gradescope half an hour after their scheduled end times.

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

- Introduction and mathematical background
- Graph algorithms: connectivity, bipartiteness, topological sorting
- Greedy algorithms: shortest paths, minimum spanning trees, scheduling
- Divide-and-conquer algorithms: mergesort, closest points, integer multiplication
- 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’s problem

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