Algorithm Design and Analysis (2020)

基本信息 (General Information)

Level: Graduate

Time & Place: 10:00 – 11:40, Wednesday & Friday; Dong Zhong Yuan 2-106 (东中院 2-106)

Instructor:

Name: Xiaofeng Gao
Email: gao-xf(at)cs.sjtu.edu.cn
Office: Telecom Building 3-543
Phone: 021-34207407

Teaching Assistant:

Name: Runbo Ni (倪润博)
Email: 1098877273@qq.com
Office: SEIEE 3-328
Phone: 15821175671
Office Hour: 20:00 - 22:00, Thursday

Name: Jiadong Chen (陈家栋)
Email: chenjiadong998@sjtu.edu.cn
Office: SEIEE 3-328
Phone: 13262526383
Office Hour: 20:00 - 22:00, Wednesday

课堂时间 (Course Schedule)

计划日程 (Syllabus)

Week	Date	Lecture Topic	Event	TA
1	Sept. 09	Course Introduction Introduction of This Class, Basic Concepts, Proof, etc.		Chen
1	Sept. 11	Complexity Time / Space Complexity, Algorithm analysis, etc	Lab01	Chen
2	Sept. 18	Sorting and Searching Sorting, Searching, and Selection.		Chen
3	Sept. 23	Divide-and-Conquer Mergesort, Selection, Master’s Theorem, etc.	Lab02	Chen
3	Sept. 25	Greedy Approach (1) Interval Scheduling, Interval Partitioning, Minimum Lateness, etc.		Chen
4	Sept. 30	Greedy Approach (2) More Examples on Greedy Approach, etc.	Lab03	Ni
4	Oct. 02	National Holiday
5	Oct. 07	National Holiday
5	Oct. 09	Greedy Approach (3) + Dynamic Programming (1) More Examples on Greedy Approach, Basic Dynamic Programming, etc.		Chen
6	Oct.14	Dynamic Programming (2) Weighted Interval Scheduling, Segmented Least Squares, Knapsack, etc.	Lab04	Ni
6	Oct.16	Graph Algorithms (1) Graph basic, Minimum Spanning Tree, Searching and Exploration, etc.		Chen
7	Oct. 21	Graph Algorithms (2) Single Source Shortest Paths (Greedy & DP), All-Pair Shortest Paths, etc.	Lab05	Ni
7	Oct. 23	Graph Algorithms (3) Flow Problem, Maximum Flow, Minimum Cut, etc.		Chen
8	Oct. 28	NP-Completeness (1) Turing Machine, Computable & Decidable, etc.	Lab06	Ni
8	Oct. 30	NP-Completeness (2) NP class, Polynomial time, Reducibility, Proofs, etc.		Ni
9	Nov. 4	Approximation (1) Approximation Ratio, Approximation Class, etc.	Lab07	Ni
9	Nov. 6	Approximation (2) Greedy Algorithm, Local Search, etc.		Ni
12	Nov. 25	Final exam

作业与课后阅读 (Assignments and Readings)

Lecture 0: Preliminary

Reading Materials

Syllabus & Grading Policy: Syllabus-AlgorithmTheory.pdf
Slide for Prologue: Slide01-Prologue.pdf (Print Version: 01-Prologue.pdf)
Slide for Symbols: Slide02-Symbols.pdf (Print Version: 02-Symbols.pdf)
Reference:
* Reference01-Set.pdf Appendix B.1-B.3 of "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition);
* Reference02-Proof.pdf Chapter 2.1 of "Introduction to Languages and the Theory of Computation" by John Martin, McGraw-Hill, 2002.

Latex Tutorial

Latex Example: LatexExample.pdf (Source: LatexExample.tex, Fig-GraphG1.pdf, Fig-GraphG2.pdf)
Latex Helper: LatexHelper(ENG).pdf (Chinese Version: LatexHelper(CHI).pdf)
Algorithm Package Helper: AlgorithmPackage.pdf
Latex Tutorial: LaTeXTutorial.pdf
AlgorithmSample: AlgorithmSample.pdf (Source: AlgorithmSample.tex)
VariableSample: VariableSample.pdf (Source: VariableSample.tex)

Lecture 1: Algorithm Analysis

Reading Materials

Slide: Slide03-AlgorithmAnalysis.pdf (Print Version: 03-AlgorithmAnalysis.pdf)
Reference:
* Reference03-AlgorithmAnalysis.pdf Chapter 1 in "Algorithm Design Technique and Analysis" by M. H. Alsuwaiyel, World Scientific, 1999;
* Reference04-Summation.pdf Appendix A of "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition).
Profile of Alonzo Church AlonzoChurch.pdf The profile is from https://mathshistory.st-andrews.ac.uk/Biographies/Church/.

Lab 1: Algorithm Analysis (Due: 10:00 am, 09/18/2020)

Lab01-AlgorithmAnalysis: Lab01-AlgorithmAnalysis.pdf
LaTeX Source of Lab01: Lab01-AlgorithmAnalysis.tex
Lab01-Solution: Lab01-Solution.pdf
Best Labs: Lab01-Haolin.pdf, Lab01-Shengyuan.pdf, Lab01-Xianglong.pdf
Alternative average complexity analysis of Quick Sort: QuickSort-Sichen.pdf

Poster and In-Class Quiz

- Poster
- Quiz1-1
- Quiz1-2
- Quiz1-3

Lecture 2: Divide and Conquer

Reading Materials

Slide: Slide04-DivideConquer.pdf (Print Version: 04-DivideConquer.pdf)
Reference:
* Reference05-DivideConquer.pdf Chapter 2 of "Algorithm" by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, McGraw-Hill, 2007.
* Reference06-MasterTheorem.pdf Chapter 4.4-4.6 of "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition).

Lab 2: Divide and Conquer (Due: 10:00 am, 09/30/2020)

Lab02-DivideConquer.pdf: Lab02-DivideConquer.pdf
LaTeX Source of Lab02: Lab02-DivideConquer.tex
Code Source: Code-Range.cpp
Figure Source: Fig-RecurrenceTree.vsdx (You can modify this figure and save as a .pdf figure file to insert into your .tex file)
Lab02-Solution: Lab02-Solution.pdf
Best Labs: Lab02-Muyang.pdf, Lab02-Xianglong.pdf

Poster and In-Class Quiz

- Poster for Divide and Conquer
- Quiz2-1

Lecture 3: Greedy Strategy

Reading Materials

Slide: Slide05-GreedyAlgorithm.pdf (Print Version: 05-GreedyAlgorithm.pdf)
Reference: Reference07-GreedyAlgorithm.pdf Chapter 4.1-4.3 in "Algorithm Design" by J. Kleinberg, and E. Tardos, Pearson-Addison Wesley, 2005.
Movie: Wall Street (1987)

Lab 3: Greedy strategy (Due: 10:00 am, 10/14/2020)

Lab03-Greedy: Lab03-Greedy.pdf
LaTeX Source of Lab03: Lab03-Greedy.tex
Lab02-Solution: Lab03-Solution.pdf
Best Labs: Lab03-Shengwei.pdf, Lab03-Renjie.pdf, Lab03-Xinyu.pdf, Lab03-Haoyi.pdf

Poster for Greedy Strategy

- Poster for Greedy Algorithm
- Quiz2-2

Lecture 4: Dynamic Programming

Reading Materials

Slide: Slide06-DynamicProgramming.pdf (Print Version: 06-DynamicProgramming.pdf)
Refererence: Reference08-DynamicProgramming.pdf Reference: Chapter 6.1-6.7 in "Algorithm Design" by J. Kleinberg, and E. Tardos, Pearson-Addison Wesley, 2005.

Lab04: Dynamic Programming (Due: 10:00 am, 10/21/2020)

Lab04-DynamicProgramming: Lab04-DynamicProgramming.pdf
Latex source of Lab04: Lab04-DynamicProgramming.tex
Figure source of Lab04: Subsquare.jpg
Code source of Lab04: Code-SCC.cpp, SCC.in, Code-Egg.cpp
Lab04-solution: Lab04_Solution.pdf
Best Labs: Lab04-Mingze.pdf, Lab04-Shangyu.pdf, Lab04-Yunkai.pdf

Poster for Dynamic Programming

- Poster for Dynamic Programming
- Mingze Li

Lecture 5: Graph Exploration

Reading Materials

Slide: Slide07-GraphAlgorithm.pdf (Print Version: 07-GraphAlgorithm.pdf)
Slide: Slide08-BFSDFS.pdf (Print Version: 08-DFSBFS.pdf)
Reference: Reference09-GraphDecomposition.pdf Chapter 3, 4 in "Algorithm" by S.Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, McGraw-Hill, 2007.

Poster for Graph Algorithm

- Poster for Graph Exploration
- Quiz3-1
- Quiz3-2
- Quiz3-3

Lecture 6: Shortest Path

Reading Materials

Slide: Slide09-ShortestPath.pdf (Print Version: 09-ShortestPath.pdf)
Reference:

        * Reference10-ShortestPath.pdf Chapter 24 in "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition);

      * Reference11-ShortestPathDP.pdf Chapter 6.8, 6.10 in "Algorithm Design" by J. Kleinberg, and E. Tardos, Pearson-Addison Wesley, 2005;

        * Reference12-AllPairShortestPath.pdf Chapter 25 in "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition);

        * Reference13-Heaps.pdf, Reference14-FibonacciHeaps.pdf Slide for Heap in Data Structure Class from Kevin Wayne @ Princeton;

  * Reference15-AmortizedAnalysis.pdf Chapter 17 in "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition).

Lab05: Graph Exploration (Due: 10:00 am, 10/29/2020)

Lab05-GraphExploration: Lab05-GraphExploration.pdf
Latex source of Lab05: Lab05-GraphExploration.tex
Figure source of Lab05: ArticulationPoint.jpg, LowestCommonAncestor.png, GridShortestPath.jpg
Lab05-Solution: Lab05-Solution.pdf
Best Labs: Lab05-Yi.pdf, Lab05-Ruiming.pdf, Lab05-Xueyuan.pdf

Lecture 7: Network Flow

Reading Materials

Slide: Slide10-NetworkFlow.pdf (Print Version: 10-Network Flow.pdf)
Demo: Slide11-GraphAlgorithmDemo.pdf
Slide: Slide12-AmortizedAnalysis.pdf (Print Version: 12-Amortized Analysis.pdf )
Reference: Reference16-NetworkFlow.pdf Chapter 25 in "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition).

Lab06: Graph Exploration (Due: 10:00 am, 11/04/2020)

Lab06-Network Flow: Lab06-NetworkFlow.pdf
Latex source of Lab06: Lab06-NetworkFlow.tex
Figure source of Lab06: Fig-MultiStack.pdf
Lab06-Solution: Lab06-Solution.pdf
Best Labs: Lab06-Junqin.pdf, Lab06-Shangyu.pdf, Lab06-Xueyuan.pdf

Lecture 8: NP Complexity

Reading Materials

Slide: Slide13-TuringMachine.pdf (Print Version: 13-TuringMachine.pdf)
Slide: Slide14-NPReduction.pdf (Print Version: 14-NPReduction.pdf)
Pseudo code tutorial: Tutorial_Pseudocode.pdf
Reference:

* Reference17-TuringMachine.pdf Chapter 1 in "Computational Complexity: A Modern Approach", by Sanjeev Arora and Boaz Barak, Cambridge University Press, 2006.

* Reference18-NPReduction.pdf Chapter 8 in "Algorithm Design" by J. Kleinberg, and E. Tardos, Pearson-Addison Wesley, 2005.
Music: The Longest Path (1988)

Lab07: NP Reduction (Due: 10:00 am, 11/11/2020)

Lab07-NPReduction: Lab07-NPReduction.pdf
Latex source of Lab07: Lab07-NPReduction.tex
Lab07-Solution: Lab07-Solution.pdf
Best Labs: Lab07-Xinyu.pdf, Lab07-Xueyuan.pdf, Lab07-Ranhao.pdf, Lab07-Yi.pdf

- Poster for Turing Machine
- Poster for NP and Reduction

Lecture 9: Approximation Algorithm

Reading Materials

Slide: Slide15-ApproximationBasics (Print Version: 15-ApproximationBasics.pdf)
Reference: Reference19-Approximation.pdf Chapter 1.1, 2.1, 2.3 in "Design of Approximation Algorithms " by D. Williamson, and D. Shomoys, Cambridge University Press, 2010.

Final Exam

Final Exam Information

Time: Nov. 25, 2020 (Wednesday) 9:50 am-11:50 am
Location: ExamOrganization.xlsx
Notice: English only

提交引导 (Submission Guidelines)

请登录右上角的JAccount进行作业提交，登录后可以下载课件、提交作业。
Please log in by JAccountat the top right corner to download course materials and submit your homework.
作业只能提交一个文档，如果有多个文档请放在一个文件夹里，将其压缩成.rar或.zip文件。作业可以多次提交，每次上传版本会覆盖原来版本。可通过点击右上方“Check Hw.”一栏查看作业提交、成绩与反馈情况（建议下载检查上传版本)。
You can only submit ONE document for each homework. If there are multiple documents, please put them inside a folder, and compress it in the form of .rar or .zip You can submit homework multiple times, while the original submitted version will be covered by the latest submitted one. You can click on “Check Hw.”at the top right corner to check the homework submission, grade, and feedback.(Suggestion: You can download your submitted homework to check it.)
若已登录的情况下提示权限不足，请刷新或者注销后重新登录，若仍权限不足，请及时与助教联系。如出现无法提交、不懂操作、系统Bug等情况请与助教及时联系。
If it shows that you do not have access after you log in, please refresh the webpage or re-log in again. If it still does not work, please contact teaching assistants in time. If you have other problems, e.g., you cannot or don’t know how to submit your homework, or find Bugs please contact your teaching assistants in time.

分组活动说明 (Group Project Description)

Grouping
- Projects should be done in teams of 3 (3 and 3 only).
- Students who have enrolled in this course should make up their team and submit the team information on the homepage by 10 am 09/23/2020. Enrolled students who have not submitted their team information by the deadline will be partitioned into random groups.
- Unregistered students should make their team only with unregistered students if they wish to participate in the course project.
Project Description
- Project-Data-AnalyticJobScheduling: Project-Data-AnalyticJobScheduling.pdf
- Project Report Submission Deadline: 23:59, 12/18/2020 (including all sources and data)
- Project Demo Schedule: 12/19/2020
Related Document
- Project-ToyData: ToyData.xlsx
- Project-Template: Project-Template.zip
- Project-Demo Arrangement: CS7310-Demo Arrangement.pdf

分组活动细节 (Group Project Detail)

序号 (No.)	队名 (Team Name)	队员一 (Member 1)	队员二 (Member 2)	队员三 (Member 3)	题目 (Project)	时间 (Time)
1	很有精神	何云帆	王子豪	章润廷	电院3-404	15:15-15:30
2	54749110	程章	刘学渊	李兴	电院3-414	14:30-14:45
3	虎保健	袁健	冯二虎	何保祥	电院3-414	13:45-14:00
4	三人行	李奇之	简相永	吕相龙	电院3-414	16:45-17:00
5	🐂🍺	黄俊钦	侍硕	杨培灏	电院3-414	13:30-13:45
6	梦韵庄	蔚梦航	庄严	郑韵锴	电院3-414	16:15-16:30
7	RXP	潘达汉	任雨阳	徐奕	电院3-404	13:30-13:45
8	奥力给	黎楚萱	柴纶	贺昊	电院3-404	15:00:15:15
9	污渍永远滴神	刘思辰	李明泽	黄晟原	电院3-414	16:00-16:15
10	扫地僧	花一帆	冯传恒	张志龙	电院3-404	16:15-16:30
11	做大做强	胡浩颐	陈仁杰	陈家栋	电院3-414	14:00-14:15
12	Turing-Church	王鸿蒙	李子通	田子申	电院3-414	17:15-17:30
13	回到起点	冯思远	王翰竟	冯冬辉	电院3-414	15:00:15:15
14	长风破浪	缪新元	李博闻	袁诗景	电院3-414	17:45-18:00
15	大佬求带	刘洪铭	尹远航	陈运忠	电院3-414	14:45-15:00
16	鱼鱼鱼	俞经纬	涂彦伦	谢瑜璋	电院3-404	17:15-17:30
17	算法真难	栾广强	魏豪	张舒来	电院3-404	13:45-14:00
18	楼上隔壁老王	王旭航	雷佳乐	孔芮	电院3-414	17:00-17:15
19	/remake	苏星宇	鲁瑞明	景梦圆	电院3-404	17:45-18:00
20	真不错	王欣宇	周云松	韩冰	电院3-404	17:30-17:45
21	阿果拉	胡飘	刘宽	王昭博	电院3-414	16:30-16:45
22	开心就好对不队	阚诺文	曹迈达	顾扬	电院3-404	16:45-17:00
23	长风破浪的师弟师妹们	孙嘉伟	鲁新钰	曾益	电院3-404	16:00-16:15
24	正常合理	沈逸飞	张倬胜	周子祎	电院3-414	17:30-17:45
25	思算巧法	黄高昂	梁爽	邓雨昂	电院3-404	17:00-17:15
26	隐藏的第四人	李雪嫣	郭政一	崔玉芳	电院3-414	14:15-14:30
27	不想做project	贾冉昊	王靖楠	郭萌涵	电院3-404	14:15-14:30
28	你的名字	赵义成	凌家曜	马悦	电院3-404	14:45-15:00
29	PSG	周浩麟	魏天天	易沐阳	电院3-404	14:00-14:15
30	彼得罗巴甫洛夫斯克	郑承宇	张剑清	罗统億	电院3-404	14:30-14:45
31	想个名字	奚彧	孙泽堃	王师溟	电院3-414	15:15-15:30
32	LastNotLeast	林耘丰	陈鹭	李姚	电院3-404	18:00-18:15
33	O(1)	刘尚育	邢睿	李泱丞	电院3-404	16:30-16:45

学生名册与课堂记录 (Roster and Event)

Roster

History Roster

光荣榜 (Honor Roll)

序号 (Number)	姓名 (Name)	加分时间 (Time)	加分原因 (Reason)	加分人 (Recorder)
1	黄晟原	2020/09/25	Best Lab for Lab01	倪润博
2	周浩麟	2020/09/25	Best Lab for Lab01	倪润博
3	吕相龙	2020/09/25	Best Lab for Lab01	倪润博
4	刘思辰	2020/09/25	Shared the calculation of quick sort algorithm's average complexity with linearity of expection	倪润博
5	刘尚育	2020/09/25	Corrected the value of "pair" in the derivation of time complexity of merge sort on the blackboard	倪润博
6	易沐阳	2020/10/19	Best Lab for Lab02	倪润博
7	吕相龙	2020/10/19	Best Lab for Lab02	倪润博
8	吕胜炜	2020/10/19	Best Lab for Lab03	倪润博
9	陈仁杰	2020/10/19	Best Lab for Lab03	倪润博
10	王欣宇	2020/10/19	Best Lab for Lab03	倪润博
11	胡浩颐	2020/10/19	Best Lab for Lab03	倪润博
12	李明泽	2020/10/27	Best Lab for Lab04	陈家栋
13	郑韵锴	2020/10/27	Best Lab for Lab04	陈家栋
14	刘尚育	2020/10/27	Best Lab for Lab04	陈家栋
15	鲁瑞明	2020/10/30	Best Lab for Lab05	倪润博
16	曾益	2020/10/30	Best Lab for Lab05	倪润博
17	刘学渊	2020/10/30	Best Lab for Lab05	倪润博
18	刘学渊	2020/11/08	Best Lab for Lab06	陈家栋
19	黄俊钦	2020/11/08	Best Lab for Lab06	陈家栋
20	刘尚育	2020/11/08	Best Lab for Lab06	陈家栋
21	刘学渊	2020/11/17	Best Lab for Lab07	倪润博
22	曾益	2020/11/17	Best Lab for Lab07	倪润博
23	贾冉昊	2020/11/17	Best Lab for Lab07	倪润博
24	王欣宇	2020/11/17	Best Lab for Lab07	倪润博

引用材料 (Reference)

Textbooks
- T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms, MIT Press, 2009.
- J. Kleinberg, and E. Tardos, Algorithm Design, Pearson-Addison Wesley, 2005.
- S. Dasgupta, C. Papadimitriou, U. Vazirani, Algorithm, McGraw-Hill, 2007.
Algorithm
- M. H. Alsuwaiyel, Algorithm Design Technique and Analysis, World Scientific, 1999.
- 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, 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.