Design and Analysis of Algorithms (EI6303)

Spring Semester 2021

for graduates, school of software

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

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.

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

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
*