MPCS 55001: Algorithms (Spring 2022)

General information

Instructor

Timothy Ng (timng@uchicago.edu)
Office hours: See Ed.

Teaching assistants

See Ed.

Class meetings

Tuesdays 5:30–8:30 pm, RY 251

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

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

Course materials: Lecture notes 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 Ed Discussion for course discussion and announcements. Restricted course materials and Zoom meeting information (if any) will also be posted here.
Coursework and grades: We will use Gradescope for distributing and receiving coursework. Your grades will also be available here.

Lectures

Lectures are often the first point at which students will be exposed to new ideas and material. Lectures comprise a significant part of the learning students will do in the course and will cover material that is necessary for success in the course. However, lectures alone may not be sufficient for all students. It is not expected that students will master the material learned in lecture without significant review, inquiry, and practice outside of lecture.

Office hours

Office hours are times when the course staff are available for you. The instructor and teaching assistants will have scheduled office hours in-person and/or online. While most students use this as an opportunity to ask about coursework, you're free to ask about or discuss things that are related directly or indirectly with the course.

Course materials and objectives

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

Analyzing algorithms: Models of computation, asymptotics, data structures, data representation
Greedy algorithms: Interval scheduling, minimizing lateness, shortest paths, minimum spanning trees
Divide and conquer: Mergesort, recurrences, integer and matrix multiplication, closest pair of points
Randomization: Probabilistic analysis, cuts, Quicksort, selection, hashing
Dynamic programming: Weighted interval scheduling, knapsack, RNA secondary structure, sequence alignment, shortest paths
Intractability: Hardness, NP-completeness, NP-complete problems, reductions, dealing with intractability

Upon completion of this course, students should be able to:

Design algorithms for solving problems using one of several algorithmic design paradigms.
Prove that an algorithm is correct.
Analyze the computational complexity of an algorithm, for various measures of computational compleixty like time and space.
Describe measures of computational complexity and efficiency with respect to those measures.
Determine and prove whether a problem is likely to be solvable via an efficient algorithm.

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.

Lectures are primarily based on [KT] Kleinberg and Tardos. Algorithm Design (2005).
A very good secondary reference, which some lectures are based on, is [CLRS] Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, 3rd edition (2012). CLRS is a classic and is available through the UChicago Library.
Another reference is Jeff Erickson. Algorithms (2019). This text is freely available and covers much of the material we'll need, so it offers a nice alternate take.

Evaluation

Your computed grade in this course will be determined by the following coursework components.

Weekly problem sets worth 40% in total. Let $P$ be the average grade earned on problem sets, with $0 \leq P \leq 1$.
Two examinations, worth 60% in total.
- A closed-book midterm exam worth at most 20%, to be completed in-class in Week 5. Let $M$ be the grade earned on the midterm exam, with $0 \leq M \leq 1$.
- A closed-book final exam worth at least 40%, to be completed during finals week. Let $F$ be the grade earned on the final exam, with $0 \leq F \leq 1$.
Biweekly personal reflections each worth 1%. Let $R$ be the number of completed reflections.

Then your computed grade will be obtained via the following formula: \[(40\% \times P) + (20\% \times M) + (F \times (60\% - (20\% \times M)) + (1\% \times R).\]

Problem sets

Problem sets will be posted on Tuesdays and will be due on the following Tuesday at 5:00 pm (17:00). Problem sets will be distributed and submitted via Gradescope. Please ensure that submissions are legible. See this guide for submitting on Gradescope.

Collaboration and citation

Students are expected to write up solutions to problem sets individually, but may work together. The work that you hand in is expected to be your own. Be sure to acknowledge your collaborators and any sources beyond course materials that you may have used.

If you choose to work with others, you must list your collaborators. You may only work with other students in the class. Your collaboration should be to a degree that your writeups are substantially different. It is not acceptable that solutions are largely copies of each other.
You should not look up solutions to assigned problems, online or otherwise. This includes question and answer forums, homework websites, and other publicly available materials from other courses in the department or at other institutions. Be aware that if you can find a solution online, the course staff can too.
If you use a source beyond course materials, the source must be a published source—either a book or journal article—and full citation must be given. If you are not sure whether your source is a published source, it probably isn't.

How solutions are graded

Your solutions on problem sets and exams are judged on the following basis:

Validity. Your solution will be judged on its correctness. This includes whether a method was applied correctly, calculations are correct, and proof steps follow the rules of logic. In particular, for algorithm design problems, one must show that the algorithm is correct (i.e. it correctly computes what it was claimed to compute) and efficient (i.e. it meets the necessary complexity constraints).
Presentation. Your solution will be judged on its presentation as it relates to readability and fluency. A solution may be correct, but is unable to communicate this fact to the reader. A readable solution should guide the reader through the argument, providing the appropriate explanation and justification. By fluency, we mean the correct use of the language of mathematics. This includes the proper use of established terminology and notation. Algorithms are typically expressed as pseudocode. Note that solutions expressed as actual code will be considered to have poor readability. Pseudocode should be intelligible to someone who has minimal programming knowledge.

Grading for problem sets is based on the overall quality of the solution. Clearly, solutions need to be valid in order to be evaluated highly, but a completely valid solution that is not readable will still be evaluated poorly. Furthermore, grades are assigned as a qualitative evaluation of the work and not a quantitative accounting of the work. This appears as a 4-point scale on Gradescope.

4 (Excellent). The solution is correct and readable. The solution may have a few trivial flaws in logic or presentation that can be easily corrected.
3 (Good). The solution is generally correct and readable and has a some minor flaws in logic or presentation. Understanding of the problem has been demonstrated. The solution and presentation can be improved quickly with a few suggestions.
2 (Borderline). The solution could be correct and readable but has a major flaw in logic or presentation. There is evidence that there is some understanding of the problem. The solution and presentation can be improved with some substantial revisions.
1 (Needs revision). It is not clear that the problem was understood and/or the presentation of the solution is heavily flawed. The solution should be revised with some guidance.
0 (Incomplete). The solution was not submitted or is clearly incomplete.

The assigned grade is the grader’s judgement of whether the solution meets the standards of the class. In addition to the assigned grade, the grader is expected to provide detailed feedback, addressing specific flaws in the submitted work that can and should be improved in future work.

Resubmission

Part of the learning process is identifying and correcting mistakes. After your submissions have been graded and returned to you, you will have the opportunity to use the feedback you receive to revise and resubmit your work.

Please follow the instructions for resubmission carefully. An assignment on Gradescope will be available for resubmissions of the problem set. There are a lot of different assignments on Gradescope, so please read carefully and make sure you’re submitting to the correct one. To prepare your resubmission, you should include:

the first page of the graded copy of the submission, which contains a summary of the grading (described below) and indicating clearly which solutions are being resubmitted, and
your revised solution for problems you wish to resubmit,
a response to the grader for each problem you wish to resubmit, indicating explicitly how you have implemented the grader’s feedback.

To get a copy of your graded problem set, use the Download Graded Copy button. The first page of this document is an outline of the grading. Include this page in your resubmission and use it to refer to the graders’ feedback in your response. If you have questions about a grader’s comments, you should contact the course staff by making a post visible only to course staff on Ed.

Only complete solutions may be resubmitted. The point of this process is to allow you to incorporate the feedback you receive from grading. Incomplete solutions will have no actionable feedback, defeating the purpose of resubmission.
You do not need to resubmit the entire problem set if you only want to resubmit a solution for one problem.
You do not need to resubmit any part of the problem set if you are satisfied with your grade.
If you resubmit part of the problem set, for all problems you are not resubmitting, please select the grading summary page for that problem.
Your resubmissions will be graded by the same grader.

Regrade requests

You may submit a regrade request in the event of an error by the grader. That is, if the feedback provided by the grader is a factual error, you may request a review of the grading. Please indicate the source of the error in this case.

We will not consider regrade requests concerning disagreement with a grader’s evaluation of your work. In such cases, you should consider the feedback that was given and apply it towards revision and resubmission of your work.

Lectures

Lecture notes for each lecture can be found below.

March 29

Lecture 1: Introduction to algorithms (KT 2.1–2.2, 3.1–3.3)

April 5

Lecture 2: Greedy Algorithms I (KT 4.1, 4.2, 4.4)

April 12

Lecture 3: Greedy Algorithms II (KT 4.5–4.6), Divide and Conquer I (KT 5.1–5.2)

April 19

Lecture 4: Divide and Conquer II (KT 5.4–5.5, 13.5)

April 26

Midterm Exam

Lecture 5: Randomization (KT 13.2, 13.6)

May 3

Lecture 6: Dynamic Programming I (KT 6.1–6.2, 6.4, 6.6)

May 10

Lecture 7: Dynamic Programming II (KT 6.5, 6.8)

May 17

Lecture 8: Computational Intractability I (KT 8.1–8.2, 8.5, 8.8)

May 24

Lecture 9: Computational Intractability II (KT 8.3–8.4)

May 31

Final Exam

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 the instructor.

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.