Description

• This course mainly introduces the basics of Randomized Algorithms, Approximation Algorithms, and Distributed Algorithms, so that students can develop algorithmic thinking and the ability to analyze the efficiency of algorithms, and find different approaches for dealing with challenging computational problems.​

(Tentative) Topics

Randomized algorithms

• Probability review and concentration bounds
• Las Vegas Algorithms, e.g., randomized quick sort
• Monte Carlo Algorithms, e.g., primality testing, and matrix multiplication
• Some other basic randomized algorithms

Approximation algorithms

• NP-completeness, computational complexity reduction, Cook's theorem, etc
• Basics of approximation of optimization problems
• Basic algorithms: approximation algorithms for graph coloring, multi-machine scheduling, packing, traveling salesman, vertex cover, and maximum independent set problems

Distributed algorithms

• Basics of distributed computing models
• Basics of distributed algorithms: synchronous and asynchronous network models, leader election, spanning tree construction, broadcast, breadth/depth-first search, shortest path, maximum independent set, and other distributed algorithms

Prerequisites

• Basic algorithms and data structures, discrete probability, graph theory, and linear algebra

Grading

• Homework (30%): 6 assignments
• Participation (5%)
• Closed book midterm exam (30%)
• Closed book final exam (35%)

Homework

• An assignment will be posted on BB (www.bb.ustc.edu.cn) every two weeks. You can directly upload your solution to BB. We highly recommend using Latex for answering your homework（Here is a reference on how to use Latex).
• Homework late policy. Full credit will be given for solutions turned in on (or before) the due date. 80% credit will be given for one-day (24-hour) late. 60% credit will be given for two-day (48-hour) late. 40% credit will be given for three-day (72-hour) late. NO credit will be given after three days.

Academic Integrity

• Homework Completion Principle: Students are encouraged to discuss and work in groups on homework problems. However students must state the people they discussed with in the acknowledgement section of their written assignment. Students are not allowed to take detailed notes in any group discussion that will appear verbatim in assignment write-ups. Every student has to turn in answers that are written solely by himself/herself. This course will have zero tolerance for plagiarism. If mutual plagiarism is found, both the plagiarist and the plagiarized will have their grades canceled. Please take the initiative to prevent your homework from being plagiarized by others.

References

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. Third Edition. The MIT Press. 2009.
• J. Kleinberg, E. Tardos. Algorithm Design. Addison Wesley, 2005.
• Rajeev Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, New York (NY), 1995.
• M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. CambridgeUniversity Press, New York (NY), 2005.
• Vazirani, Vijay V. Approximation Algorithms. Berlin: Springer, 2003.
• Williamson, David P.; Shmoys, David B. The Design of Approximation Algorithms, Cambridge University Press, 2011.
• N. Lynch. Distributed Algorithms. Morgan Kaufmann Publishers,1996.