Design and Analysis of Algorithms (EI6303)

Spring Semester 2021

for graduates, school of software


Guoqiang Li

Teaching Assistant

Minyu Chen: minkow (AT) sjtu (DOT) edu (DOT) cn


10:00am - 11:40am every Tuesday and Wednesday, 5-16th week


311, Xia Yuan

Office hour

Wed. 14:00-17:00 at 3203 Building of Software


[DPV07] Algorithms
by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, 2007.

[KT05] Algorithm Design
by Jon Kleinberg, Eva Tardos, 2005.

[CLRS09] Introduction to Algorithms
by T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, 2009.

[Vaz04] Approximation Algorithms
by Vijay V. Vazirani, 2004.

[WS11] The Design of Approximation Algorithms
by D.P. Williamson and D.B. Shmoys, 2011.
[an offical copy]

[MR95] Randomized Algorithms
by Rajeev Motwani, Prabhakar Raghavan, 1995.


Mar. 23
Lecture 1. Introduction.

Mar. 24
Lecture 2. Graph Algorithms, Revisited I.

Mar. 30
Lecture 3. Graph Algorithms, Revisited II.

Mar. 31
Lecture 4. Graph Algorithms, Revisited III.

Apr.  6
Lecture 5. Graph Algorithms, Revisited IV.

Apr.  7
Lecture 6. NP Problems I.

Apr. 13
Lecture 7. NP Problems II.

Apr. 14
Lecture 8. NP Problems III.

Apr. 20
Lecture 9. NP Problems IV.

Apr. 21
Lecture 10. Networks I.

Apr. 27
Lecture 11. Networks II.

Apr. 28
Lecture 12. Networks III.

May  4
Lecture 13. Networks IV.

May  5
Lecture 14. Linear Programming I.

May 11
Lecture 15. Linear Programming II.

May 12
Lecture 16. Linear Programming III.

May 18
Lecture 17. Approximation Algorithms I.

May 19
Lecture 18. Approximation Algorithms II.

May 25
Lecture 19. Approximation Algorithms III.

May 26
Lecture 20. Linear Programming IV.

June  1
Lecture 21.Approximation Algorithms IV.

June  2
Exercise I.

June  8
Exercise II.

June  9
Lecture 22. Conclusion.


Lecture notes on Approximability of Optimization Problems
by Madhu Sudan @ MIT

Lecture notes on Optimization and Algorithmic Paradigms
by Luca Trevisan @ Stanford

Lecture notes on Approximation Algorithms
by Yuval Rabani @ Cornell

Lecture notes on Linear Programming and Combinatorial Optimization
by Avner Magen @ Toronto

Lecture notes on Randomized Algorithms
by Luca Trevisan @ Berkeley

Sketching Algorithms for Big Data


Guoqiang Li
Last modified: Saturday, Jan. 18, 2020.