Spring Semester, 2016
Announcement
- Welcome to the class. Have fun! The important information will be announced here. Please check this webpage often.
General Information
- Level: Graduate
- Time: 12:55pm – 3:40pm, Thursday
- Place: Chen Ruiqiu Building 219 (陈瑞球楼219)
- Instructor:
- Name: Xiaofeng Gao (高晓沨)
- Email: gao-xf(at)cs.sjtu.edu.cn
- Office: Telecom Building 3-543
- Phone: 021-34207407
- Teaching Assistant:
- Name: Zhiyin Chen (陈智殷)
- Email: cknight(at)foxmail.com
- Office: Telecom Building 3-328
- Phone: 021-34207407
- Office Hour: 4:00 - 6:00pm, Wednesday (Week 4, 8, 12, 16)
Course Schedule
|
February 2016 |
|
March 2016 |
|
April 2016 |
||||||||||||||||||
week |
S |
M |
T |
W |
T |
F |
S |
week |
S |
M |
T |
W |
T |
F |
S |
week |
S |
M |
T |
W |
T |
F |
S |
|
|
1 |
2 |
3 |
4 |
5 |
6 |
(2) |
|
|
1 |
2 |
3 |
4 |
5 |
(6) |
|
|
|
|
|
1 |
2 |
|
7 |
8 |
9 |
10 |
11 |
12 |
13 |
(3) |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
(7) |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
14 |
15 |
16 |
17 |
18 |
19 |
20 |
(4) |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
(8) |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
(1) |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
(5) |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
(9) |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
(2) |
28 |
29 |
|
|
|
|
|
(6) |
27 |
28 |
29 |
30 |
31 |
|
|
(10) |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
May 2016 |
|
June 2016 |
|
Total: 18 weeks, 16 classes |
||||||||||||||||||
week |
S |
M |
T |
W |
T |
F |
S |
week |
S |
M |
T |
W |
T |
F |
S |
|
|
|
|
|
|
|
|
(11) |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
(15) |
|
|
|
1 |
2 |
3 |
4 |
|
|
|
Class Day |
||||
(12) |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
(16) |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
|
|
|
|
|
|
|
|
(13) |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
(17) |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
|
|
· |
Holiday |
||||
(14) |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
(18) |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
|
|
|
|||||
(15) |
29 |
30 |
31 |
|
|
|
|
|
26 |
27 |
28 |
29 |
30 |
|
|
|
|
· |
Final Exam Week |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Syllabus
Week |
Date |
Lecture Topic |
HW |
Event |
1 |
Tue.25 |
Syllabus, Preliminary, Introduction to Algorithm Schedule, Grading Policy, Preliminary, Basic Introduction, etc. |
Lab-01 |
|
2 |
Mar.03 |
Data Structure, Math Functions Data Structure, Graph, Disjoint Set, Mathematical Fundamentals, etc. |
Lab-02 |
|
3 |
Mar.10 |
Divide-and-Conquer Mergesort, Selection, Sorting Network, etc. |
Lab-03 |
|
4 |
Mar.17 |
Greedy Approach (1) Activity Selection, Minimum Spanning Tree, Huffman Code, etc. |
Lab-04 |
|
5 |
Mar.24 |
Greedy Approach (2) Interval Partitioning, Task Scheduling, Shortest Path, Cache, Matroid, etc. |
Lab-05 |
|
6 |
Mar.31 |
Dynamic Programming (1) Matrix-Chain, Longest Common Subsequence, 0-1 Knapsack, etc. |
Lab-06 |
|
7 |
Apr.07 |
Dynamic Programming (2) Optimal Substructure, Weighted Interval Scheduling, Sequence Alignment |
|
|
8 |
Apr.14 |
Application. Exercises. Midterm. |
|
Midterm |
9 |
Apr.21 |
Graph Algorithms (1) Single Source Shortest Paths, All-Pairs Shortest Paths, etc. |
Lab-07 |
Project-01 |
10 |
Apr.28 |
Graph Algorithms (2) Maximum Flow, Minimum Cut, etc. |
Lab-08 |
|
11 |
May 07 |
Graph Algorithms (3) Computational Geometry, Real-World Applications |
Lab-09 |
|
12 |
May 14 |
Amortized Analysis Aggregate Analysis, Accounting Method, Potential Method |
Lab-10 |
|
13 |
May 21 |
NP-Completeness (1) NP class, Polynomial time, etc. |
Lab-11 |
|
14 |
May 28 |
NP-Completeness (2) Reducibility, Proofs, etc. |
Lab-12 |
|
15 |
Jun.04 |
Approximation Design (1) Approximation Ratio, Approximation Class, Examples |
Lab-13 |
|
16 |
Jun.11 |
Approximation Design (2) Sequential Algorithm, Local-Search, LP, Primal-Dual Technique, etc. |
|
|
17-18 |
TBD |
Review. Exercises. Tutoring. Final Exam |
|
Final |
Assignments and Readings
Submission:
- English writing only.
- Upload your homework to TA's ftp.
ftp://public.sjtu.edu.cn/
User Name: chenzhiyin
Password: chen328
- Late submission is not accepted.
Lecture 1: Preliminary - Basic Mathematical Objects
- Reading Materials
- Syllabus & Grading Policy: Syllabus-Algorithm.pdf
- Preliminary: Slide01-Prologue.pdf (Print Version: 01-Prologue.pdf)
- References:
* Reference01-Prologue.pdf -- Prologue in "Computability: An Introduction to Recursive Function Theory" by Nigel Cutland, Cambridge University Press, 1980.
* Reference02-Proof.pdf -- Chapter 2 in "Introduction to Languages and the Theory of Computation" by John Martin, McGraw-Hill, 2002.
- Homework 0: Self-Introduction (Due: 1:00pm, 3/01/2016)
- If you can read Chinese, fill in survey online at http://www.sojump.hk/jq/7225857.aspx
- If you cannot, fill in form Lab00-SelfIntroduction.docx
Then upload your answer sheet to TA's ftp (Rename your submission as Lab00-LastNameFirstName.docx).
- Homework 1: Proof (Due: 1:00pm, 3/03/2016)
- Lab01-Proof: Lab01-Proof.pdf
- Latex Source: Lab01-Proof.tex
Please also send the source file to TA for his correction if you use Latex (Upload a folder, rename your submission as Lab01-LastnameFirstname.XXX). - Answer Template: AnswerTemplate.pdf, AnswerTemplate.tex
You can follow the format of the template to complete your work. - Latex Help Document: Chinese.pdf, English.pdf
- Anser Key: Lab01-Solution.pdf
Lecture 2: Algorithm Analysis
- Reading Materials
- Algorithm Analysis: Slide02-AlgorithmAnalysis.pdf (Print Version: 02-AlgorithmAnalysis.pdf)
- Reference:
* Reference03-Introduction.pdf -- Chapter 1 in "Algorithm Design Technique and Analysis" by M. H. Alsuwaiyel, World Scientific, 1999.
- Homework 2: Algorithm Analysis (Due: 1:00pm, 3/10/2016)
- Lab02-Algorithm Analysis: Lab02-AlgorithmAnalysis.pdf
- Latex Source: Lab02-AlgorithmAnalysis.tex
- Answer Key: Lab02-Solution.pdf
Lecture 3: Divide and Conquer
- Reading Materials
- Divide & Conquer : Slide03-DivideConquer.pdf (Print Version: 03-DivideConquer.pdf)
* Reference04-DivideConquer.pdf -- Chapter 2 in "Algorithm" by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, McGraw-Hill, 2007.
* Reference05-SortingNetwork.pdf -- Chapter 27 in "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2002. (2nd Edition) - Stirling's Formula: Wikipage
- Divide & Conquer : Slide03-DivideConquer.pdf (Print Version: 03-DivideConquer.pdf)
- Homework 3: Divide and Conquer (Due: 1:00pm, 3/17/2016)
- Lab03-Divide and Conquer: Lab03-DivideConquer.pdf
- Latex Source: Lab03-DivideConquer.tex
- Answer Key: Lab03-Solution.pdf
- Lab03-Divide and Conquer: Lab03-DivideConquer.pdf
Lecture 4: Greedy Strategy
- Reading Materials
- Greedy Algorithm: Slide04-GreedyAlgorithm.pdf (Print Version: 04-GreedyAlgorithm.pdf)
* Reference06-GreedyAlgorithm.pdf -- Chapter 4.1-4.3, 4.5, 4.7 in "Algorithm Design" by J. Kleinberg, and E. Tardos, Pearson-Addison Wesley, 2005.
- Greedy Algorithm: Slide04-GreedyAlgorithm.pdf (Print Version: 04-GreedyAlgorithm.pdf)
- Homework 4: Greedy Algorithm (Due: 1:00pm, 3/24/2016)
- Lab04-Greedy Algorithm: Lab04-GreedyAlgorithm.pdf
- Latex Source: Lab04-GreedyAlgorithm.tex
- Answer Key: Lab04-Solution.pdf
- Lab04-Greedy Algorithm: Lab04-GreedyAlgorithm.pdf
Lecture 5: Matroid
- Reading Materials
- Matroid: Slide05-Matroid.pdf (Print Version: 05-Matroid.pdf)
Reference:
* Reference07-Matroid.pdf -- Chapter 16.4-16.5 in "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition);
* Chapter 2.1-2.2 in "Design and Analysis of Approximation Algorithms" by D.-Z. Du, K.-I. Ko, and X. D. Hu, Springer, 2012.
- Matroid: Slide05-Matroid.pdf (Print Version: 05-Matroid.pdf)
- Homework 5: Matroid (Due: 1:00pm, 3/31/2016)
- Lab05-Matroid: Lab05-Matroid.pdf
- Latex Source: Lab05-Matroid.tex
- Answer Key: Lab05-Solution.pdf
- Lab05-Matroid: Lab05-Matroid.pdf
Lecture 6-7: Dynamic Programming
- Reading Materials
- Dynamic Algorithm: Slide06-DynamicProgramming.pdf
(Print Version: 06-DynamicProgramming.pdf)
* Reference08-DynamicProgramming.pdf -- Reference: Chapter 6.1-6.7 in "Algorithm Design " by J. Kleinberg, and E. Tardos, Pearson-Addison Wesley, 2005. - Memoization: Wikipedia Page
- Pseudo-polynomial time: Wikipedia Page
- Dynamic Algorithm: Slide06-DynamicProgramming.pdf
- Homework 6: Dynamic Programming (Due: 1:00pm, 4/07/2016)
- Lab06-Dynamic Programming: Lab06-DynamicProgramming.pdf
- Latex Source: Lab06-DynamicProgramming.tex
- Answer Key: Lab06-Solution.pdf
- Lab06-Dynamic Programming: Lab06-DynamicProgramming.pdf
Project: Border Intrusion Detection (Due: 11:59pm, 6/19/2016)
- Project Description:
- Border Intrusion Detection: Project-IntrusionDetection.pdf
- Please submit your project and the code to TA's FTP (Including the .tex file if you use Latex. Compress everything into a single .zip or .rar file and then rename your submission as
Project-LastNameFirstName.XXX).
- Border Intrusion Detection: Project-IntrusionDetection.pdf
- Documents:
- Project-GroupInformation: Project-GroupInfo.pdf
- Project-DemoSchedule: Project-DemoList.pdf
Lecture 8: Graph Algorithms - An Introduction
- Reading Materials
- Brief Introduction: Slide07-GraphAlgorithm.pdf (Print Version: 07-GraphAlgorithm.pdf)
- No homework this week~~~O(∩_∩)O~~~
Lecture 9: Graph Algorithms II
- Reading Materials
- Graph Decomposition: Slide08-BFSDFS.pdf (Print Version: 08-BFSDFS.pdf)
* Reference09-GraphDecomposition.pdf -- Chapter 3, 4 in "Algorithm" by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, McGraw-Hill, 2007. - Minimum Spanning Tree: Refer Slide04-GreedyAlgorithm.pdf (Print Version: 04-GreedyAlgorithm.pdf)
* Reference06-GreedyAlgorithm.pdf -- Chapter 4.5, 4.7 in "Algorithm Design" by J. Kleinberg, and E. Tardos, Pearson-Addison Wesley, 2005. - Single Source Shortest Path: Slide09-ShortestPath.pdf (Print Version: 09-ShortestPath.pdf)
* Reference10-ShortestPath.pdf -- part of Chapter 24 in "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition);
- Graph Decomposition: Slide08-BFSDFS.pdf (Print Version: 08-BFSDFS.pdf)
- Homework 7: Graph Algorithms (Due: 1:00pm, 5/05/2016)
- Lab07-GraphAlgorithms: Lab07-GraphAlgorithms.pdf
- Latex Source: Lab07-GraphAlgorithms.tex
- Answer Key: Lab07-Solution.pdf
- Lab07-GraphAlgorithms: Lab07-GraphAlgorithms.pdf
Lecture 10: Graph Algorithms III
- Reading Materials
- Shortest Path (DP): Slide10-ShortestPathDP.pdf (Print Version: 10-ShortestPathDP.pdf)
* Reference11-ShortestPathDP.pdf -- Chapter 6.8, 6.10 in "Algorithm Design" by J. Kleinberg, and E. Tardos, Pearson-Addison Wesley, 2005. - All-Pair Shortest Path: Slide11-AllPair.pdf (Print Version: 11-AllPair.pdf)
* Reference12-AllPairShortestPath.pdf -- Chapter 25 in "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition); - Network Flow: Slide12-NetworkFlow.pdf (Print Version: 12-NetworkFlow.pdf)
* Reference13-NetworkFlow.pdf -- Chapter 7.1-7.3 in "Algorithm Design" by J. Kleinberg, and E. Tardos, Pearson-Addison Wesley, 2005.
- Shortest Path (DP): Slide10-ShortestPathDP.pdf (Print Version: 10-ShortestPathDP.pdf)
- Homework 8: Path and Flow (Due: 1:00pm, 5/12/2016)
- Lab08-PathAndFlow: Lab08-PathAndFlow.pdf
- Latex Source: Lab08-PathAndFlow.tex
- Answer Keys: Lab08-Solution.pdf
Lecture 11: Amortized Analysis
- Reading Materials
- Amortized Analysis: Slide13-AmortizedAnalysis.pdf (Print Version: 13-AmortizedAnalysis.pdf)
* Reference14-AmortizedAnalysis.pdf --Chapter 17 in "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition);
- Amortized Analysis: Slide13-AmortizedAnalysis.pdf (Print Version: 13-AmortizedAnalysis.pdf)
- Homework 9: Amortized Analysis (Due: 1:00pm, 5/19/2016)
- Lab09-AmortizedAnalysis: Lab09-AmortizedAnalysis.pdf
- Latex Source: Lab09-AmortizedAnalysis.tex
- Answer Keys: Lab09-Solution.pdf
- Lab09-AmortizedAnalysis: Lab09-AmortizedAnalysis.pdf
Lecture 12: Reduction and NP-Completeness
- Reading Materials
- Reduction: Slide14-Reduction.pdf (Print Version: 14-Reduction.pdf)
* Reference15-Reduction.pdf --Chapter 8.1-8.4, 8.9-8.10 in "Algorithm Design" by J. Kleinberg, and E. Tardos, Pearson-Addison Wesley, 2005.
- Reduction: Slide14-Reduction.pdf (Print Version: 14-Reduction.pdf)
- Homework 10: Reduction (Due: 1:00pm, 5/26/2016)
- Lab10-Reduction: Lab10-Reduction.pdf
- Latex Source: Lab10-Reduction.tex
- Answer Keys: Lab10-Solution.pdf
- Lab10-Reduction: Lab10-Reduction.pdf
Lecture 13: Approximation Algorithm I
- Reading Materials
- Approximation Algorithm : Slide15-Approximation.pdf (Print Version: 15-Approximation.pdf)
* Reference16-Approximation.pdf -- Chapter 1.1, 2.1, 2.3 in "Design of Approximation Algorithms " by D. Williamson, and D. Shomoys, Cambridge University Press, 2010.
- Approximation Algorithm : Slide15-Approximation.pdf (Print Version: 15-Approximation.pdf)
- Homework 11: Approximation (Due: 1:00pm, 6/02/2016)
- Lab11-Approximation: Lab11-Approximation.pdf
- Latex Source: Lab11-Approximation.tex
- Answer Keys: Lab11-Solution.pdf
- Lab11-Approximation: Lab11-Approximation.pdf
Lecture 14: Approximation Algorithm II
- Reading Materials
- Approximation Design: Slide16-ApproximationII.pdf (Print Version: 16-ApproximationII.pdf)
* Reference17-ApproximationII.pdf -- Chapter 14 in "Approximation Algorithms" by V. Vazirani, Springer-Verlag, 2001.
- Approximation Design: Slide16-ApproximationII.pdf (Print Version: 16-ApproximationII.pdf)
- No homework this week~~~O(∩_∩)O~~~
- Course Evaluation Survey (Anonymous)
- Please fill out the survey and help me improve my course, Thanks~~~m(_ _)m
- URL: http://www.sojump.com/jq/8587156.aspx
Office Hour for Final: 2:00pm-4:00pm, SEIEE 3-East309, June 15.
Roster and Events
Know your classmates?
Click rouster-2016.html
Back to Top
References
- Algorithm:
- T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms, The MIT Press, 2009
- M. H. Alsuwaiyel, Algorithm Design Technique and Analysis, World Scientific, 1999.
- Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, Algorithm, McGraw-Hill, 2007.
- J. Kleinberg, and E. Tardos, Algorithm Design, Pearson-Addison Wesley, 2005.
- Alfred V. Aho, John E Hopcroft, Jeffery D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.
- Udi Manber, Introduction to Algorithms: A Creative Approach, Addison-Wesley, 1989.
- Henming Zou, The Way of Algorithms, China Machine Press, 2010.
- Computational Complexity:
- Christos Papadimitriou, Computational Complexity, Addison Wesley, 1994.
- Theory of Computational Complexity, by Ding-Zhu Du, and Ker-I Ko, published by John Wiley & Sons, Inc., 2000.
- John Martin, Introduction to Languages and the Theory of Computation, McGraw-Hill, 2002.
- Computational Complexity: A Modern Approach, by Sanjeev Arora and Boaz Barak, Cambridge University Press, 2006.
- Approximation:
- Vijay V. Vazirani, Approximation Algorithms, Springer-Verlag, 2001.
- D.P. Williamson and D.B. Shmoys, The Design of Approximation Algorithms, 2011.
- D.Z Du, K-I. Ko, and X.D. Hu, Design and Analysis of Approximation Algorithms, 2012.
- Acknowledgement:
- Special thanks is given to Prof. Kevin Wayne, Prof. Charles E. Leiserson, Prof. Salah E. Elmaghraby, Prof. Neeraj Mittal, Prof. Ding-Zhu Du, Prof. Yuxi Fu, Prof. Yijia Chen, Prof. Pinyan Lu, Dr. Xiaojuan Cai for sharing their teaching materials.