MPCS 55001: Algorithms (Spring 2021)
General information
- Instructor
- Timothy Ng (timng@uchicago.edu)
Office hours: Tuesdays 6:30–7:30 pm Central
- Teaching assistants
- Francesca Falzon
Office hours: Fridays 10:15–11:15 am Central
- Chris Jones
Office hours: Thursdays 9:00–10:00 pm Central
- Links
-
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
This class is being offered remotely and largely asynchronously. There are a number of different ways we'll be communicating about the class.
- Course materials
- Lecture notes and links to lecture videos will be made available via this course webpage. The course website also contains basic information about the course (i.e. you can treat this like a syllabus).
- Discussion and announcements
- We will use Campuswire for course discussion and announcements. Restricted course materials and Zoom meeting information for synchronous sessions will also be posted here.
- Problem sets and grades
- We will use Gradescope for distributing and receiving coursework, such as problem sets and exams. Your grades will also be available here.
Class meetings
Lectures will be asynchronous and provided weekly as a set of videos on Fridays. There will be a synchronous tutorial session on Tuesdays at 5:30 pm Central. These sessions supplement the lecture videos and students are responsible for the material covered in these sessions. The synchronous sessions will be recorded.
Topics
The following is a selection of topics and possible problems that we may 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, edge-disjoint paths
- Intractability
- NP-completeness, NP-complete problems, reductions, dealing with intractability
Text
There is no required textbook and lecture notes will be provided. However, there are a number of useful resources. When in doubt, your primary source should be the lecture notes.
Evaluation
Your computed grade in this course will be determined by the following coursework components.
- An open-book final exam, to be completed during finals week. Let $F$ be the grade earned on the final exam, with $0 \leq F \leq 1$. The weight of the final exam depends on the completion of other coursework.
- Weekly problem sets worth 60% in total. Let $P$ be the average grade earned on problem sets, with $0 \leq P \leq 1$.
- Biweekly personal reflections each worth 1%. Let $R$ be the number of completed reflections.
- Weekly open-book quizzes, worth 5% in total. Let $Q$ be the the grades earned on quizzes, with $0 \leq Q \leq 1$.
There is no midterm exam. Let $S = (60\% \times P) + (1\% \times R) + (5\% \times Q)$. Then your computed grade will be obtained via the following formula:
\[S + (F \times (100\% - S)).\]
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 Fridays and will be due on the following Friday at 9:00 pm (21:00).
- Please ensure that submissions are legible. See this guide for submitting on Gradescope.
- Students will receive a grade and feedback on their initial submission. Students will then have the opportunity to submit a revised submission, which directly addresses the graders' feedback, to earn a higher grade. If no revision is submitted, the grade for the initial submission will be used. You must make an initial submission in order to submit a revision.
Quizzes
The weekly quizzes will be made available with each set of lecture videos. These are open-book short answer quizzes that will be completed online and will be graded automatically. These are meant for you to gauge your understanding of the lecture material.
Lectures
Lectures will be made available on Canvas. Lecture notes for each lecture can be found below.
- Week 0 (March 24)
- Introduction and course Information
- Week 1 (March 29)
- Lecture 1: Stable Matchings (KT 1.1)
- Stable Matching
- Algorithm Analysis
- Lecture 2: Basics of Algorithm Analysis
- Running Time (CLRS 2.2/KT 2.1)
- Efficient Algorithms (CLRS 3.1/KT 2.2)
- Analyzing Gale–Shapley (KT 2.3)
- Week 2 (April 5)
- Lecture 3: Greedy Algorithms
- Greedy algorithms and interval scheduling (KT 4.1/CLRS 16.1)
- Scheduling to minimize lateness (KT 4.2)
- Lecture 4: Shortest Paths (KT 4.4/CLRS 24)
- Dijkstra's algorithm
- Implementation and efficiency
- Week 3 (April 12)
- Lecture 5: Minimum Spanning Trees
- Prim's algorithm (KT 4.5/CLRS 23)
- Kruskal's algorithm (KT 4.6/CLRS 21.1–2, 23)
- Lecture 6: Divide and conquer
- Mergesort (KT 2.1/CLRS 2.3)
- Recurrences and the Master Theorem (KT 2.2/CLRS 4.3–5)
- Week 4 (April 19)
- Lecture 7: More divide and conquer
- Closest pair of points (KT 5.4/CLRS 33.4)
- Integer and Matrix Multiplication (KT 5.5/CLRS 4.2)
- Lecture 8: Quicksort (KT 13.5/CLRS 7)
- Deterministic Quicksort
- Randomized Quicksort
- Week 5 (April 26)
- Lecture 9: Dynamic Programming
- Weighted Interval Scheduling (KT 6.1)
- Dynamic Programming (KT 6.2)
- Lecture 10: More Dynamic Programming
- Knapsack (KT 6.4)
- Edit Distance (KT 6.6)
- Week 6 (May 3)
- Lecture 11: RNA Secondary Structure (KT 6.5)
- Setup
- Solution
- Lecture 12: Shortest Paths, revisited
- Single-destination shortest paths (KT 6.8)
- Bellman–Ford (KT 6.8)
- Negative-weight cycles (KT 6.10)
- Week 7 (May 10)
- Lecture 13: Network Flow
- Maximum Flow (KT 7.1/CLRS 26.1)
- Ford–Fulkerson
- Lecture 14: Applications of Flow
- Minimum Cuts (KT 7.2/CLRS 26.2)
- Bipartite Matching (KT 7.5/CLRS 26.3)
- Week 8 (May 17)
- Lecture 15: Reduction
- Polynomial-Time Reductions (KT 8.1/CLRS 34)
- Packings and Coverings (KT 8.1)
- Lecture 16: More reduction
- Satisfiability (KT 8.2)
- Hamiltonian Cycle (KT 8.5/CLRS 34.5.3)
- Week 9 (May 24)
- Lecture 17: Classification of Problems
- P and NP (KT 8.3)
- NP-completeness (KT 8.4)
- Lecture 18
- Getting over it
- Beyond NP-completeness
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.