Class Update:
| Date | Topic | Slides | Assignments | Notes |
| 1/9 | Syllabus, Algorithm Examples | Available in D2L | ||
| 1/12 | Computational Tractability, big O | Available in D2L | ||
| 1/17 | Graphs | Available in D2L | ||
| 1/19 | Greedy alg | Available in D2L | ||
| 1/24 | Greedy: single link clustering | Available in D2L | ||
| 1/26 | Divide & conquer, Binary search | Available in D2L | ||
| 1/31 | VLSI Design via Divide and Conquer, Fibonacci Number | Available in D2L | ||
| 2/2 | Fibonacci Number Calcuation via Golden Ratio Equations,Matrix Multiplication with only 7/8 fraction of the original time Median & seletion, | |||
| 2/7 | video on Fibonacci Number, median selection | Available in D2L | ||
| 2/9 | Dynamic Programming | |||
| 2/14 | Dynamic Programming | |||
| 2/16 | Review for Exam I | |||
| 2/21 | Exam 1 (In Class, online, 75 minutes) | |||
| 2/23 | Dynamic Programming | |||
| 2/28 | Recitation on Exam 1, introduction to net flow | |||
| 3/2 | Max flow min cut | |||
| 3/7 | Max flow min cut | |||
| 3/9 | More on net flow | |||
| 3/14 | Capacity Scaling | |||
| 3/16 | Review for Exam 2, sample exam | |||
| 3/21 | Exam 2 (In Class, online, 75 minutes) | |||
| 3/23 | Presentation of Term Project | |||
| 3/28 | Recitation of Exam 2 | |||
| 3/30 | Shotest augmenting path | |||
| 4/11 | Quiz, Intractability | |||
| 4/13 | Approximation Algorithms | |||
| 4/18 | Approximation Alg | |||
| 4/20 | Randomized algorithm | |||
| 4/25 | Review | |||
| 4/27 | Final Exam. | |||
Instructor: Xue Chen (Email: xuechen1989@ustc.edu.cn) and
Xiaohua Xu (Email: xiaohuaxu@ustc.edu.cn)
TA: (update soon)
Class Time: Thursday 09:45-12:10 (week 2-18)
Location: GT103
Office Hour: Xue Chen (Every Wednesday 16:00-17:30 in Room 1410 of Library of the west campus or talk after the class; extra appointments are available by email)
Xiaohua Xu (update soon)
Description
The class covers classic and modern algorithmic ideas that are central to many areas of Computer Science. We will discuss three concepts of algorithms --- randomized algorithms, approximation algorithms, and online algorithms. The focus is on the most powerful paradigms and techniques of how to design algorithms and analyze their performance. Besides advanced algorithmic techniques, we will also explore a variety of applications.
(Tentative) Course outline
- Randomized Algorithms:
- Hash and its applications: Power of 2 choices, cuckoo hashing, bloom filters and heavy hitters.
- Random Walk: Martingale, page-rank, counting and MCMC.
- Karger's min-cut algorithm and a simple max-cut algorithm.
- Approximation Algorithms:
- Randomized numerical linear algebra: matrix sketch, sparsification.
- Linear programming and semi-definite programming
- Load balancing
- Center Selection
- Online Algorithms
- Weighted majority algorithm
- Multi-armed Bandit
Course requirement
Except COMP6001P (Design and Analysis of Algorithms), we will assume some mathematical maturity. The class is based on theoretical ideas and is proof-heavy. You are expected to be able to read and write formal mathematical proofs. Some familiarity with algorithms, combinatorics and probability theory will be assumed as well.
Grading
10% participation, 50% homework, 20% midterm exam, and 20% final exam.
Both exams are in class (in week 10 and week 18 separately). Final is cumulative (covering all material).
Homework
We will have one problem set every two weeks, posted on www.bb.ustc.edu.cn. Please submit the electronic version of your solution on www.bb.ustc.edu.cn.
We strongly recommend students to type their answers in Latex. Here is a template https://staff.ustc.edu.cn/~xuechen1989/temp_hw.tex and a LaTex reference http://tug.ctan.org/info/lshort/english/lshort.pdf.
Homework Policies
All coursework is to be done independently WITHOUT reading any published literature or websites besides the class text and notes. Plagiarizing the homework will be penalized by maximum negative credit and cheating on the exam will earn you a 0 in the course.
Collaboration policy: While you shall first think about the problems on your own, you are encouraged to collaborate on homework. However, you MUST write up your own solutions. You should also state the names of those you collaborated with on the first page of your submission. Homework that appears overly similar will be considered to violate the honor code.
Late policy: Each homework set will be due on Thursday before the class. For each day late 20% points of that homework are discounted, after the third day no more submissions are allowed.
Text and references
There is no required textbook. Lecture notes or slides will be available.
Similar courses with notes offered at Harvard, Columbia, Wisconsin-Madison.
You may find these books helpful in some topics:
- Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, MIT press
- Probability and Computing (Randomized Algorithms and Probabilistic Analysis) by Michael Mitzenmacher and Eli Upfal, Cambridge University Press
- Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan. Cambridge University Press, 1995