MPCS 55003 Intermediate Algorithms (Autumn 2024)

Section 1
Instructor(s) Chaudhary, Amitabh (amitabh)
Location Ryerson 177
Meeting Times Tuesday 2pm - 3:20pm
Thursday 2pm - 3:20pm
Fulfills Core Theory

Syllabus

Description

The study of algorithms is considered at the heart of computer science, and is consistently voted as the single most useful subject in a computer science curriculum.  This course covers topics in design and analysis of algorithms for students who have already taken a course in introductory algorithms.
 
The primary themes are dynamic programming, network flows, computational intractability and NP-completeness, approximation algorithms, linear programming, and randomized algorithms.  All of these algorithmic techniques have a wide range of practical applications, particularly in modern computer systems and large-scale data analysis.  This course focuses on some of the more advanced applications, and includes a few fairly complex proofs.
 
Throughout the course, students practice how to take a real-world problem, formulate the algorithmic problem at its core, identify an appropriate design technique, describe unambiguously the resulting algorithm, and finally, prove its correctness and analyze its running time.  The problems are drawn from a variety of application areas, including computer systems and networks, artificial intelligence, computer vision, data mining, and computational biology.
 
Evaluation

  • Readings and Participation: 5%
  • Assignments: 15%
  • Two Midterm Examinations: 22.5% each
  • Final Examination: 35%  
Readings and Participation: Students are assigned readings before each class that introduce the topic covered in class. These allow the class to move at a faster pace and cover deeper concepts. Readings may include questions to test understanding. Further, students are expected to participate actively in class discussions and on Piazza.
    
Assignments: Assignments are due every week and are designed to test the understanding of the covered concepts and algorithms, and to build upon them to solve problems.
 
Assignments may be submitted up to 24 hours late with a 10% penalty.  In case of extraordinary circumstances (illness, etc.), please email the instructor before the deadline for an extension, and provide documentation (doctor's note, etc.) in the next class.
 
Examinations: Students appear for three in-class examinations, two midterms and one final.
 
Books and Resources
 
The primary textbook is 
  • Algorithm Design by Jon Kleinberg and Eva Tardos, 1st edition, ISBN 0-321-29535-8.
Every student is expected to have a copy; readings and assignments refer to the textbook. Supplementary materials are provided when required.
 
Schedule
 
The tentative schedule is --- 
  • Week 1: Introduction, Huffman codes, Data Compression
  • Week 2: Dynamic Programming, Weighted Interval Scheduling
  • Week 3: Network Flows, Survey Design, Image Segmentation
  • Week 4: Midterm 1, NP-Complete Problems
  • Week 5: PSPACE, Games in Polynomial Space
  • Week 6: NP-Hard Problems on Trees
  • Week 7: Midterm 2, Linear Programming
  • Week 8: LP-Duality, Approximation Algorithms
  • Week 9: Metropolis Algorithm, Simulated Annealing
  • Week 10: Final Exam
  • Week 11:  Randomized Algorithms, Min Cut, Caching

Office Hours and Support
 
The preferred method of asking questions and seeking instructor/ TA help is through the course site on Piazza.  To meet with the instructor email him for an appointment, or catch him after class.
 
Academic Integrity
 
Students are expected to strictly follow the academic integrity policy of The University of Chicago, and the academic honesty guidelines of MPCS.

In brief, students are supposed to work on assignments and in examinations strictly on their own.  They can (are even encouraged to) discuss concepts relevant to assignments, but no notes or other record of the discussion should be kept or used in answering the assignments.
 

Course Prerequisites

A PASS on the Math Placement Exam AND previous Algorithms coursework as shown on verified transcripts.

The prior course in introductory algorithms must cover---
-- Basic time and space complexity of algorithms, asymptotic order of growth, and solving recurrences.
-- Basic graph definitions, breadth-first and depth-first search, and topological ordering.
-- Greedy algorithms, shortest paths in a graph, and minimum spanning trees.
-- Divide and conquer algorithms, sorting and median selection algorithms.
-- Basic data structures, arrays, linked lists, balanced trees, and heaps.

If your prior course doesn't cover just one or two of the above topics, you may be allowed to take the course if you are committed to learning those on your own. In that case, or if you have other questions, please email the instructor. In you email include the exact topics covered in your prior course, and a copy of your transcript.

The following books are recommended to brush up on the prerequisite
material---
-- Discrete Mathematics and Its Applications by Kenneth Rosen.
-- Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

Other Prerequisites

This class CANNOT be taken if you have taken MPCS 55501 Algorithms.

This course requires competency in Unix and Linux. New students must attend the MPCS Unix Bootcamp during orientation. Continuing students who previously attended the MPCS Unix Bootcamp have covered the required material. Continuing students who did not attend the MPCS Unix Bootcamp may review the UChicago CS Student Resource Guide here: https://uchicago-cs.github.io/student-resource-guide/.

Overlapping Classes

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

  • MPCS 50103-2 -- Mathematics for Computer Science: Discrete Mathematics
  • MPCS 55001-1 -- Algorithms

Eligible Programs

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)