CPS 330: Design and Analysis of Algorithms
Duke University, Summer 2021: June 28 - August 8 (Term 2)

Instructor: Kevin Sun (please call me Kevin)

Lecture: Mon/Tue/Wed/Thu, 1:00 pm - 2:30 pm

Recitation: Tue/Thu, 2:45 pm - 4:00 pm

Location: Zoom (links on Piazza)

Office Hours: see Piazza

Email: ksun@cs.duke.edu

  • There may be changes to the syllabus as the course progresses, but I will attempt to make these changes relatively small. My goal is to make the course interesting, challenging, and enjoyable.

  • If you are enrolled in this course, please make sure you have access to Sakai, Piazza, and Gradescope.

Course Description

Algorithms form the basis of modern society. How do map applications calculate the fastest route to a destination? What is the best way to transport cargo across a road network? How do medical students get matched to the hospitals? In this course, we will explore abstractions of these problems (and many others), and, of course, algorithmic solutions that solve these problems. By working with abstractions, we will be able to prove mathematical guarantees about the nature of these solutions, as well as the amount of time and space that the algorithms require.

Prerequisites

Familiarity in discrete mathematics (at the level of CPS 230) is strongly recommend for this course. If you're not sure about your background, I recommend reading a few pages of [DPV] and/or my notes (see below) to gauge your understanding. These are the primary resources for the course, so there's no need to fully digest everything, but they shouldn't look impenetrable either. Feel free to email me to discuss further.

Learning Outcomes

1. Use a given algorithm to solve concrete problem instances.

2. Analyze the correctness and runtime complexity of a given algorithm.

3. Design and analyze an algorithm for a previously unseen problem.

4. Describe NP-Hard reductions for unseen problems, and prove their correctness.

Resources

The textbook Algorithms by Dasgupta, Papadimitriou, Vazirani (abbreviated as [DPV]) is strongly recommended for this course. I am also a big fan of the following:

  • [Eri]: Algorithms by Jeff Erickson (freely available at algorithms.wtf)

  • [KT]: Algorithm Design by Kleinberg and Tardos (freely available slides)

  • [CLRS]: Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein

I also have my own notes, which are like a (very) condensed version of these textbooks.

Grading

  • Homework (30%): There will be two assignments per week. Assignments must be formatted using LaTeX and submitted via Gradescope. A 10% penalty will be applied to assignments that are not formatted using LaTeX. For each assignment, you may work in groups of 2-3, but you must submit individually and cite each other as collaborators. The lowest homework grade will be dropped.

  • Quizzes (30%): At the beginning of recitation on Tuesdays, there will be a 30-minute quiz. We will discuss the solutions to the quiz immediately after it's been submitted. There may also be various other quizzes throughout the term. The lowest quiz grade will be dropped.

  • Final (30%): There are two options for the final exam: a 30-minute oral exam, or a 3-hour written exam. The oral exam will be conducted live via Zoom, while the written exam must be typed and submitted on Gradescope.

  • Participation, attendance, surveys (10%): There will be many opportunities to participate in both lectures and recitations. You can also earn participation credit at my office hours. Furthermore, I am always interested in your feedback about the course, and I will send surveys to collect it.

Attendance

All of the relevant links can be found on Piazza.

  • Lectures: The lectures will be an interactive, expanded version of the course notes. Attendance will not be taken. However, because student participation will be a major component of lectures, the lectures will not be recorded. For the same reason, recitation and office hours will not be recorded either.

  • Recitation: Attendance will be taken at both recitations. On Tuesdays, the first 30 minutes are devoted to the quiz, and the remaining time will be review. The Thursday recitations are dedicated to solving problems in groups.

  • Office Hours: Attending office hours is not required, but it's an easy way to earn participation credit.

If you cannot attend a recitation, please let me know via email as soon as possible.

Schedule (tentative)

The schedule below gives an overview of the topics we'll study in this course.

  • Week 1 (6/28-7/2): course intro, breadth-first search (BFS), depth-first search (DFS)

  • Week 2 (7/5-7/9): greedy algorithms, dynamic programming (DP)

  • Week 3 (7/12-7/16): shortest paths, maximum flows

  • Week 4 (7/19-7/23): linear programming (LP), LP applications

  • Week 5 (7/26-7/30): NP-completeness, reductions

  • Week 6 (8/2-8/6): approximation algorithms, miscellaneous, review

Academic Integrity

You are expected to follow the academic dishonesty policies, and uphold the Duke Community Standard. This means you should avoid discussing the course material with anyone other than your fellow classmates and the instructor. In particular, you shouldn't search for solutions online, or consult solutions from previous semesters or other institutions. Doing so deprives you of the opportunity to genuinely improve your problem solving abilities, which is the primary goal of this course. Violations will be reported to the Office of Student Conduct.

Regret clause: If you submit anything that you believe violates academic integrity, you may invoke this clause by informing the instructor via email within 48 hours. We'll then meet to discuss the situation, and how we'll proceed. By coming forward and taking responsibility, any potential consequences will likely be reduced. However, repeated violations will still be reported. (inspired by CS50 at Harvard)