The goal of this course is to help you become better prepared to tackle algorithm design for "real-world" problems. This includes (1) being familiar with fundamental resource-allocation problems and solutions, (2) understanding algorithmic techniques and the tradeoffs involved in designing correct, efficient, and implementable algorithms, (3) understanding challenges in algorithm design for selfish users, and (4) knowing how to model and abstract messy real- world problems into clean problems that can be attacked using known paradigms or specific algorithms.
Hopefully, you will gain a greater appreciation of the beauty and elegance of algorithms as well as where they are used in the real world. Specifically, we will study problems arising in production planning, operating systems, media-on-demand systems, networks, and more. This is the tentative list of topics :
| Introduction and Review: Graphs, Complexity classes. | |
|---|---|
| Stable matching | |
| Scheduling Theory. | |
| Facility Location | |
| Packing Problems | |
| Algorithmic Game Theory |
chenmuge#at#pku.edu.cnundergrad course in algorithms, data structures.
3 homework assignments: 30%, final exam: 70%
| Date | Topic | Hours | |
| July. 3 | Introduction | 3 | |
| July. 4 | Stable matching + Scheduling Theory (1) | 3 | |
| July. 5 | Scheduling Theory (2) +Homework 1 | 3 | |
| July. 6 | Scheduling + Facility Location(1) | 3 | |
| July. 7 | Facility Location(2) | 3 | |
| July. 10 | Packing Problems+ Homework 2 | 3 | |
| July. 11 | Algorithmic Game Theory (1) | 3 | |
| July. 12 | Algorithmic Game Theory (2) | 3 | |
| July. 13 | Algorithmic Game Theory (3)+Homework 3 | 3 | |
| July. 14 | Summary | 3 | |
| July. 15 | Final Exam | 2 | solutions |