MPCS 55001 Algorithms (Autumn 2024)

Syllabus PDF: Please look at the attached syllabus (Spring 2024 version) for full details about the class. There may be small changes in this iteration of the class.

Course Description:

This course is an introduction to the fundamental techniques used to design algorithms for a wide range of problems. You will learn how to use these basic heuristics to design algorithms to solve these classic problems efficiently, as well as to tackle variants of these problems that may arise in various applications. Through this process you will gain familarity with the most important and common algorithms which we will study as examples that make use of these basic algorithm design techniques.

You will also learn to think about the time and space complexity of algorithms and will learn how to reason about asymptotic complexity. We will not only see how to design algorithms, but how to reason about them and prove that they work, as well as prove guarantees about their runtime.

Learning Objectives:

• To provide students with understanding of, and practice in using the most fundamental design tools in an algorithmist's toolkit (greedy, divide and conquer, dynamic programming, using randomization, how to think about algorithms on graphs, reductions, etc.)
  
  
• To provide students familiarity with the most commonly used fundamental algorithms (searching, sorting, median finding, and some of the most common example applications of all the techniques mentioned above. Also fundamental graph algorithms like BFS, DFS, shortest path finding, minimum spanning tree computation, etc)
  
  
• To give students an understanding of time and space complexity of algorithms. Specifically: the asymptotic runtime of an algorithm.
  
  
• To enable students to reason about algorithms and their run time. Specifically, how to prove the correctness of, as well as runtime guarantees about, the algorithms that we study in this class as well as novel algorithms that you might encounter.
  
  
• To provide students experience not only in designing algorithms, but also in expressing these algorithms in plain English/ easy to read pseudocode, at an appropriate level of detail.

Course Contents:

This list of topics is tentative and we will probably cover only a subset of the more advanced topics. Please check the syllabus for a detailed course schedule.

• Algorithms, pseudocode and runtime: What is an algorithm? How to express algorithms in pseudocode/ regular English with an appropriate level of detail. How to reason about the correctness of algorithms as well as their run time. 
  
  
• Asymptotic complexity: Big-O, Omega and Theta. Solving recurrences by substitution (induction). Recursion trees. The Master Theorem.
• Recursion: The fundamental idea of recursive agorithms. Some examples such as the tower of Hanoi problem. Examples of the Divide and Conquer heuristic (Merge sort, Quick sort, Median finding in linear time, finding the closest pair of points in the plane, Karatsuba's algorithms for multiplication).
  
  
• Dynamic Programming: Examples: Rod cutting problems, Longest common subsequence, Knapsack.
  
  
• Greedy algorithms: Examples: Interval Scheduling, Huffman Codes
  
  
• A brief introduction to randomized algorithms and approximation algorithms: basic notions and some introductory examples. The notion of expected run time, high probability bounds and approximation ratios.
  
  
• Graph Algorithms: Breadth First Search, Depth First Search, directed acyclic graphs and topological sort. Decomposing any graph into a directed acyclic graph of its strongly connected components. Minimum spanning trees. Prim's and Kruskal's algorithm for computing minimum spanning trees.  Shortest path finding: Dijkstra's, Bellman-Ford and Floyd-Warshall algorithms. Depending on time: max flow min cut theorem and computing matchings in graphs.
  
  
• Algorithmic Complexity: Computability, complexity, complexity classes. P and NP. Reductions both as a tool for proving hardness but also as an invaluable algorithm design tool.
  
  
• Special topics depending on time: Possible topics include computation with privacy (cryptography, e.g. secure multi-party computation) or designing algorithms when agents may have selfish motives to act in their own best interest (algorithmic game theory and mechanism design).
  
  

Course Activities:

• Classes: Classes will typically consist of a lecture on the topic interspersed with problem solving/ related activities.
• Office Hours: Regular office hours will be held by the course instructor as well as TAs. Attendance is optional but highly reccomended.
• Problem Solving Sessions: Regular problem solving sessions will be held for the purpose of giving the students guided problem solving practice. Attendance is optional but highly reccomended.
  
  

Course Materials:

The class is intended to be self contained. Complete lecture notes will be provided for all the lectures. All problems in the problem sets will also be stated in full.

The course textbook is Introduction to Algorithms (Third Edition) by T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein (ISBN 9780262-033848).

We will also refer to the textbook Algorithm design (First Edition) by Jon Kleinberg and Eva Tardos (ISBN 978-0321295354).

 
Evaluation:

The course grade will be based on weekly homeworks, a midterm and a final exam. Homework will be focussed on written exercises where you must design an algorithm to solve a problem, express the algorithm clearly, prove it's correctness and then prove a suitable bound on it's asymptotic time complexity. There may be occasional programming exercises. 

We will adopt a specifications grading framework: that is you will be provided detailed instructions for each task on the homework, as well as an opportunity to resubmit your homework after receiving feedback. The homework will be graded qualitatively. The final letter grade will depend upon how many of the homework problems you satisfactorily complete (including after the opportunity to revise your work) and the exam score (which will take into account both midterm and final scores). More details can be found on the syllabus.


Prerequisites: 

The main prerequistite is some mathematical maturity (in particular a good understanding of the material covered in the discrete mathematics course). No knowledge of algorithms is assumed. Some basic programming experience (in any modern programming language) may be useful. 

MPCS 50103 Discrete Math (Immersion Math) OR a passing score on the MPCS Math Placement exam. Core Programming (completed or concurrently taking) or a Core Waiver for programming.

Non-MPCS, MSCAPP or MACSS students should review our MPCS Course Request Policy: https://masters.cs.uchicago.edu/page/course-requests

This class is scheduled at a time that conflicts with these other classes:

• MPCS 51205-1 -- Topics in Software Engineering
• MPCS 55003-1 -- Intermediate Algorithms

MS in Computational Analysis in Public Policy (Year 2) MS in Molecular Engineering MA in Computational Social Science (Year 2) Bx/MS in Computer Science (Option 3: Profesionally-oriented - Non-CS Majors) Masters Program in Computer Science Masters Program in Computer Science (new) Placement: Pass I Masters Program in Computer Science (new) Placement: Pass I + II Masters Program in Computer Science (new) Placement: Pass I + II (w/ Advanced) Masters Program in Computer Science (Immersion)