Design and Analysis of Algorithms (EI6303)
Spring Semester 2021
for graduates, school of software
Guoqiang Li
Minyu Chen: minkow (AT) sjtu (DOT) edu (DOT) cn
10:00am - 11:40am every Tuesday and Wednesday, 5-16th week
311, Xia Yuan
Wed. 14:00-17:00 at 3203 Building of Software
[DPV07] Algorithms
[KT05] Algorithm Design
[CLRS09] Introduction to Algorithms
[Vaz04] Approximation Algorithms
[WS11] The Design of Approximation Algorithms
[MR95] Randomized Algorithms
Mar. 23 Mar. 24 Mar. 30 Mar. 31 Apr. 6 Apr. 7 Apr. 13 Apr. 14 Apr. 20 Apr. 21 Apr. 27 Apr. 28 May 4 May 5 May 11 May 12 May 18 May 19 May 25 May 26 June 1 June 2 June 8 June 9
Lecture notes on Approximability of Optimization Problems
Lecture notes on Optimization and Algorithmic Paradigms
Lecture notes on Approximation Algorithms
Lecture notes on Linear Programming and Combinatorial Optimization
Lecture notes on Randomized Algorithms
Sketching Algorithms for Big Data Guoqiang Li Teaching Assistant
Time
Place
Office hour
References
by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, 2007.
by Jon Kleinberg, Eva Tardos, 2005.
by T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, 2009.
by Vijay V. Vazirani, 2004.
by D.P. Williamson and D.B. Shmoys, 2011.
[an offical copy]
by Rajeev Motwani, Prabhakar Raghavan, 1995.
Lectures
Lecture 1. Introduction.
[handout]
Lecture 2. Graph Algorithms, Revisited I.
[handout]
Lecture 3. Graph Algorithms, Revisited II.
[handout]
Lecture 4. Graph Algorithms, Revisited III.
[handout]
Lecture 5. Graph Algorithms, Revisited IV.
[handout]
Lecture 6. NP Problems I.
[handout]
Lecture 7. NP Problems II.
[handout]
Lecture 8. NP Problems III.
[handout]
Lecture 9. NP Problems IV.
[handout]
Lecture 10. Networks I.
[handout]
Lecture 11. Networks II.
[handout]
Lecture 12. Networks III.
[handout]
Lecture 13. Networks IV.
[handout]
Lecture 14. Linear Programming I.
[handout]
Lecture 15. Linear Programming II.
[handout]
Lecture 16. Linear Programming III.
[handout]
Lecture 17. Approximation Algorithms I.
[handout]
Lecture 18. Approximation Algorithms II.
[handout]
Lecture 19. Approximation Algorithms III.
[handout]
Lecture 20. Linear Programming IV.
[handout]
Lecture 21.Approximation Algorithms IV.
[handout]
Exercise I.
Exercise II.
Lecture 22. Conclusion.
Materials
by Madhu Sudan @ MIT
by Luca Trevisan @ Stanford
by Yuval Rabani @ Cornell
by Avner Magen @ Toronto
by Luca Trevisan @ Berkeley
Homework
Last modified: Saturday, Jan. 18, 2020.