Design and Analysis of Algorithms (EI6303)

Spring Semester 2021

for graduates, school of software


Instructor

Guoqiang Li

Teaching Assistant

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

Time

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

Place

311, Xia Yuan

Office hour

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


References

[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.


Lectures

Mar. 23
Lecture 1. Introduction.
[handout]

Mar. 24
Lecture 2. Graph Algorithms, Revisited I.
[handout]

Mar. 30
Lecture 3. Graph Algorithms, Revisited II.
[handout]

Mar. 31
Lecture 4. Graph Algorithms, Revisited III.
[handout]

Apr.  6
Lecture 5. Graph Algorithms, Revisited IV.
[handout]

Apr.  7
Lecture 6. NP Problems I.
[handout]

Apr. 13
Lecture 7. NP Problems II.
[handout]

Apr. 14
Lecture 8. NP Problems III.
[handout]

Apr. 20
Lecture 9. NP Problems IV.
[handout]

Apr. 21
Lecture 10. Networks I.
[handout]

Apr. 27
Lecture 11. Networks II.
[handout]

Apr. 28
Lecture 12. Networks III.
[handout]

May  4
Lecture 13. Networks IV.
[handout]

May  5
Lecture 14. Linear Programming I.
[handout]

May 11
Lecture 15. Linear Programming II.
[handout]

May 12
Lecture 16. Linear Programming III.
[handout]

May 18
Lecture 17. Approximation Algorithms I.
[handout]

May 19
Lecture 18. Approximation Algorithms II.
[handout]

May 25
Lecture 19. Approximation Algorithms III.
[handout]

May 26
Lecture 20. Linear Programming IV.
[handout]

June  1
Lecture 21.Approximation Algorithms IV.
[handout]

June  2
Exercise I.

June  8
Exercise II.

June  9
Lecture 22. Conclusion.


Materials

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


Homework


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