Professor:
Aaron Roth
TAs:
Natalie Collina,
Ira Globus-Harris,
Georgy Noarov, Amithab Arumugam, Alexander Go, Adarsh Rao,
Adam Weidman, Saurabh Shah, Olivia Gottlieb, Jared Asch, Cindy Jiang, Colin Hosking, Alexandra Tanner, Arnav Aggarwal.
Meeting Time: Monday/Wednesday 3:30-5:00
Room: Town 100
Overview: In this course, we will survey the field of algorithm design, with an eye towards theory. Our goal will be to design and analyze algorithms for solving
problems of different sorts, whose solutions are non-obvious. We will see various techniques for discrete optimization problems (greedy methods, divide and conquer methods, dynamic programming,
and flow based methods), as well as for continuous optimization problems (gradient descent, linear programming, and multiplicative weights).
Prerequisites: This will be a
mathematically rigorous
theory
course for advanced undergraduates. Students should have taken (at least) CIS 120, 160, and 262, and be comfortable with rigorous proofs and asymptotic notation.
Goals and Grading: The goal of
this course is to give students a rigorous introduction to the design and analysis of algorithms. Grading will be based on participation on Piazza (5%), problem sets (45%), two
midterms (15% each), and a final exam (20%).
Textbook:We won't be following a textbook very closely. Two textbooks that contain most of the material we will be covering and will be useful references are:
Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, and
Algorithm Design by Kleinberg and Tardos.
Office Hours and Discussion:
Office Hours: See Piazza
We will be using Piazza to discuss class material, answer questions, and make announcements. The Piazza page for CIS 320 is
piazza.com/upenn/fall2021/cis320/home.
Students are encouraged to ask questions about the material on Piazza so that everyone can benefit and contribute to their answers.
Topics Covered:
- Introduction to the Analysis of Algorithms
- Sorting
- Divide and Conquer
- Dynamic Programming
- Greedy Algorithms
- Max Flow
- Online Optimization: Multiplicative Weights
- Zero Sum Games and the Minimax Theorem
- Machine Learning: Boosting
- Machine Learning: Online Prediction and Calibration
- Linear Programming
- NP Completeness