Advanced Algorithms

Title Advanced Algorithms (55005)
Quarter Autumn 2017
Instructor Amitabh Chaudhary (amitabh@cs.uchicago.edu)
Website

Syllabus
The study of algorithms is becoming increasingly significant as datasets used in computations grow in size; and is consistently voted as the single most useful subject in a computer science curriculum. This course in advanced algorithms covers topics from contemporary algorithms for students who have already taken a rigorous first course in algorithms.
 
The course begins with an in-depth study of computational intractability and NP-completeness, and follows it by studying practical algorithms for intractable problems: approximation algorithms and those based on local search. It then looks at how the power of random choices can be harnessed to avoid worst-case situations. The resulting randomized algorithms have been crucial in the success of modern computer systems. The next topic is amortized analysis, an advanced technique used to analyze situations in which algorithms maybe expensive in some of their operations, but are provably efficient over a sequence of operations.
 
Other topics are chosen based on student interest from among online algorithms, fast Fourier transforms, multithreaded algorithms, and computational geometry.
 
During 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, 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
 
The primary textbooks are---

  • Algorithm Design by Jon Kleinberg and Eva Tardos, 1st edition, ISBN 0-321-29535-8.
  • Introduction to Algorithms by Thomas H. Cormen, Charles E.Leiserson, Ronald L.Rivest, and Clifford Stein, 3rd edition.
Every student is expected to have a copy; readings and assignments refer to the textbook.  Supplementary materials are provided when required.
 
  
TENTATIVE SCHEDULE

  • Week 1: Polynomial-Time Reductions, NP-Complete Problems
  • Week 2: PSPACE
  • Week 3: Approximation Algorithms
  • Week 4: Midterm I, Metropolis Algorithm, Simulated Annealing
  • Week 5: Randomized Algorithms, Min Cut, Caching
  • Week 6: Load Balancing, Packet Routing
  • Week 7: Midterm II, Computational Geometry
  • Week 8: Amortized Analysis
  • Week 9: Online Algorithms
  • Week 10: Final
  • Week 11: Fast Fourier Transforms
 
Prerequisites (Courses)

This course requires a strong command of discrete mathematics, including discrete probability, and introductory algorithms.

For discrete mathematics, students should have taken MPCS 50103 Mathematics for Computer Science: Discrete Mathematics and obtained a B+ or higher, or passed the corresponding placement exam.

For introductory algorithms, students should have taken MPCS 55001 Algorithms and obtained a B+ or higher, or passed the corresponding placement exam.

If you believe you have an exceptional case or have other questions, please email the instructor.

Prerequisites (Other)

Satisfies

Core Theory
High Performance Computing Specialization

Time

Thursday 5:30-8:30 pm

Location

Ryerson 277