CMSC 27200: Theory of Algorithms (Spring 2020)

General information

Instructor: Timothy Ng (timng@uchicago.edu)
Office hours: MWF 9:30-10:30 am, MW 2:30-3:30 pm Central
Teaching assistants: Akshima (akshima@uchicago.edu)
Office hours: Wednesdays 4:30-5:30 pm Central; Aritra Sen (aritrasen@uchicago.edu)
Office hours: Thursdays 4:30-5:30 pm Central
Course webpage: https://cs.uchicago.edu/~timng/272/s20/

Overview

This course is about the design and analysis of algorithms. Students will be introduced to the basics of algorithms analysis, several algorithm design paradigms, and problems for which there are no known efficient algorithms. Each of these topics will be illustrated by studying problems and the best known algorithms for solving these problems.

Communication

There are a number of different ways we'll be communicating about the course.

Canvas: We'll use Canvas for announcements, confidential materials (lecture videos, solutions, grades), and dtnks to the other tools below.
Piazza: For most communication and discussion, we will be using Piazza.
Gradescope: Assignment submission and grading will be handled via Gradescope.
Zoom: For office hours and discussions and tutorials among smaller groups, we'll be using Zoom.
Email: For confidential concerns, please e-mail me.

Other than email, all of these tools will be accessible through Canvas.

Topics

The following is a selection of possible topics and problems that we'll cover.

Analyzing algorithms: Stable matching, sorting, models of computation, asymptotics
Greedy algorithms: Coin changing, interval scheduling, minimizing lateness, shortest paths, minimum spanning trees
Divide and conquer: Mergesort, counting inversions, quicksort, selection, recurrences, integer multiplication, matrix multiplication
Dynamic programming: Weighted interval scheduling, knapsack, RNA secondary structure, sequence alignment, shortest paths
Network flow: Max-flow min-cut, Ford-Fulkerson, bipartite matching
Intractability: NP-completeness, NP-complete problems, reductions, dealing with intractability

Text

This course does not follow one particular text too closely. Many lectures will be based on the following two books,

[KT] Kleinberg and Tardos. Algorithm Design (2005)
[CLRS] Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms, 3rd ed. (2009)

Either of these two textbooks will serve you well. CLRS is available electronically through the course reserves at the UChicago Library. You can access the course reserves through Canvas.

Evaluation

Your computed grade in this course will be determined by the following:

the average grade of eight problem sets, denoted $P$,
the grade of a final examination, denoted $F$,
the completion of $R$ reflections,

and computed via the following formula: $$(50\% \times P) + (100\% - (50\% \times P)) \times F + (1\% \times R).$$

Lectures

Lectures will be made available on Canvas. Lecture notes for each lecture can be found below.

1. Introduction and Stable Matchings
  1. Introduction,
  2. Stable Matching (KT 1.1)
  3. Gale-Shapley
  4. Analysis
  5. Optimality
2. Basics of Algorithm Analysis
  1. Models of computation (CLRS 2.2)
  2. Worst-case analysis (CLRS 2.2/KT 2.1)
  3. Asymptotic analysis (CLRS 3.1/KT 2.2)
  4. Efficiency and polynomial time (KT 2.1)
  5. Analyzing Gale-Shapley (KT 2.3)
1. Greedy Algorithms and Scheduling
  1. Greedy Algorithms
  2. Scheduling (KT 4.1/CLRS 16.1)
  3. A greedy strategy for scheduling
  4. Greedy stays ahead
  5. Minimizing lateness (KT 4.2)
  6. A greedy strategy for minimizing lateness
  7. Exchange arguments
2. Single-Source Shortest Paths
  1. Graphs and Shortest Paths (KT 4.4/CLRS 24.0)
  2. Dijkstra's algorithm (KT 4.4/CLRS 24.3)
  3. Correctness
  4. Efficiency, graph representations (KT 3.3/CLRS 22.1)
  5. Priority queues (KT 2.5/CLRS 6.5)
  6. Implementation
1. Minimum Spanning Trees
  1. Minimum spanning trees (KT 4.5/CLRS 23)
  2. Prim's algorithm
  3. Kruskal's algorithm
  4. The Union-Find problem (KT 4.6/CLRS 21)
2. Divide and Conquer
  1. Sorting
  2. Mergesort (KT 5.1/CLRS 2.3)
  3. Analyzing Mergesort
  4. Closest pairs of points on a plane (KT 5.4/CLRS 33.4)
  5. Efficiently implementing closest pairs
1. Multiplication
  1. The Master Theorem for Recurrences (KT 5.2/CLRS 4.5)
  2. Multiplication
  3. Fast integer multiplication (KT 5.5)
  4. Fast matrix multiplication (CLRS 4.2)
2. Quicksort
  1. Quicksort (KT 13.5/CLRS 7)
  2. Randomization
  3. Expected running time
1. Dynamic Programming
  1. Dynamic Programming (KT 6.1/CLRS 15)
  2. The Weighted Interval problem
  3. Memoization
  4. Iterating over subproblems (KT 6.2)
2. Knapsack
  1. The Knapsack problem (KT 6.4)
  2. Recurrence and Subproblems
  3. Algorithm
3. Sequence Alignment
  1. The Edit Distance (KT 6.6)
  2. Recurrence and Subproblems
  3. Algorithm
1. Shortest paths, revisited
  1. Single-destination Shortest Paths (KT 6.8)
  2. Recurrence and Subproblems
  3. The Bellman-Ford algorithm
  4. Successors
  5. Negative Cycles (KT 6.9)
2. Network Flow
  1. Network flow (KT 7.1/CLRS 26.1-2)
  2. Residual graphs
  3. Augmentation
  4. The Ford-Fulkerson algorithm
  5. Termination and running time
1. Minimum Cuts
  1. Cuts (KT 7.2/CLRS 26.2)
  2. Minimum cuts
  3. Max-flow min-cut
2. Bipartite Matching
  1. Matchings (KT 7.5/CLRS 26.3)
  2. Bipartite matching
3. Disjoint Paths
1. Intractability
  1. Intractability and Reductions (KT 8.1/CLRS 34)
  2. Independent Set and Vertex Cover
2. More Reductions
  1. Set Cover (KT 8.1)
  2. Satisfiability (KT 8.2)
3. Classification of Problems
  1. Polynomial Time and Verification (KT 8.3/CLRS 34.1-2)
  2. NP-completeness (KT 8.4/CLRS 34.3)
1. Even more Reductions
  1. Proving NP-completeness
  2. 3-SAT is NP-complete (KT 8.4/CLRS 34.4)
  3. Hamiltonian Cycle (KT 8.5/CLRS 34.5.3)
  4. Undirected Hamiltonian Cycle and Traveling Salesman (KT 8.5/CLRS 34.5.4)
  5. Subset Sum (KT 8.8/CLRS 34.5.5)
2. What else is there?
  1. Getting over it
  2. Beyond NP-completeness

Problem sets

Students are expected to write up solutions to problem sets individually, but may work together. Be sure to acknowledge your collaborators and any sources beyond course materials that you may have used.
Problem sets will be posted on Wednesdays and will be due on the following Wednesday at 8:00 pm (20:00) Central.
We will be using Gradescope for assignment submission. Gradescope is accessible from Canvas. You should be automatically enrolled in Gradescope. If you aren't enrolled in Gradescope, please let me know immediately.
Please ensure that submissions are legible. See this guide for submitting on Gradescope.
Late submissions will be accepted for 24 hours after the deadline.

Problem set 1: Due Wednesday April 15
Problem set 2: Due Wednesday April 22
Problem set 3: Due Wednesday April 29
Problem set 4: Due Wednesday May 6
Problem set 5: Due Wednesday May 13
Problem set 6: Due Wednesday May 20
Problem set 7: Due Wednesday May 27
Problem set 8: Due Wednesday June 3

Spring Quarter 2020 Recording Policy

The University has a policy regarding recordings of course material for this quarter.

Academic integrity

It is your responsibility to be familiar with the University’s policy on academic honesty. Instances of academic dishonesty will be referred to the Office of the Provost for adjudication. Following the guidelines above on collaboration and citation should be sufficient, but if you have any questions, please ask me.

Accessibility

Students with disabilities who have been approved for the use of academic accommodations by Student Disability Services (SDS) and need reasonable accommodation to participate fully in this course should follow the procedures established by SDS for using accommodations. Timely notifications are required in order to ensure that your accommodations can be implemented. Please meet with me to discuss your access needs in this class after you have completed the SDS procedures for requesting accommodations.