Algorithm Design and Analysis (2019)

基本信息 (General Information)

Level: Graduate

Time & Place: 8:00 – 9:40, Wednesday & 10:00 – 11:40, Friday; Chen Ruiqiu Building 219 & 223.

Instructor:

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

Teaching Assistant:

Name: Wenyi Xu (许文仪)
Email: axelle_xu@126.com
Office: SEIEE 3-328
Phone: 13621744935
Office Hour: 19:00 - 21:00, Monday

Name: Fenglin Yang (杨凤麟)
Email: yangfl@sjtu.edu.cn
Office: SEIEE 3-325
Phone: 13788954353
Office Hour: 19:00 - 21:00, Wednesday

课堂时间 (Course Schedule)

计划日程 (Syllabus)

Week	Date	Lecture Topic	Event	TA
1	Sep.11	Preliminary Instruction and Preliminary	Lab-01	Xu
1	Sep.13	Mid-Autumn Festival
2	Sep.18	Algorithm Design and Analysis Sorting Algorithm, Time Complexity, Space Complexity, etc.		Xu
2	Sep.20	Divide-and-Conquer Mergesort, Selection, Master’s Theorem, etc.	Lab-02	Yang
3	Sep.25	Greedy Approach (1) Interval Scheduling, Interval Partitioning, Minimum Lateness, etc.		Xu
3	Sep.27	Greedy Approach (2) Matroid, Greedy-Max Algorithm, etc.		Yang
4	Sep.29	Dynamic Programming Weighted Interval Scheduling, Segmented Least Squares, Knapsack, RNA Secondary Structure, Sequence Alignment, etc.	Lab-03	Yang
4	Oct.02	National Day Holiday
4	Oct.04	National Day Holiday
5	Oct.09	Graph Algorithms (1) Basic Concepts, Minimum Spanning Tree, Single Source Shortest Paths (Greedy & DP).		Xu
5	Oct.11	Graph Algorithms (2) All-Pair Shortest Paths, Flow Problem, Maximum Flow, Minimum Cut, etc.	Lab-04	Yang
6	Oct.16	Graph Algorithms (3) Flow Problem, Maximum Flow, Minimum Cut, etc.		Xu
6	Oct.18	Turing Machine Computability, Turing Machine, etc.	Lab-05	Yang
7	Oct.23	NP-Completeness (1) NP class, Polynomial time, Reducibility, etc.		Xu
7	Oct.25	NP-Completeness (2) NP class, Polynomial time, Reducibility, NPC, etc.	Lab-06	Yang
8	Oct.30	Approximation (1) Approximation Ratio, Approximation Class, etc.		Xu
9	Nov.06	Approximation (2) Greedy Algorithm, Local Search, etc.	Lab-07	Yang
9	Nov.08	Approximation (3) + Final Review LP+Rounding (Deterministic & Randomized), etc.		Xu

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

Lecture 1: Preliminary

Reading Materials

Syllabus & Grading Policy: Syllabus-Algorithm Design and Analysis.pdf
Slide: Slide01-Prologue.pdf (Print Version: 01-Prologue.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 (Latex Example Source: LatexExample.tex)
Figure Source: Fig-GraphG1.pdf, Fig-GraphG2.pdf
Latex Helper (English) LatexHelper(ENG).pdf (Chinese Version: LatexHelper(CHI).pdf)
Algorithm Package Helper: AlgorithmPackage.pdf
Latex Tutorial: LaTeXTutorial.pdf

Lecture 2: Algorithm Design and Analysis

Reading Materials

Slide: Slide02-AlgorithmAnalysis.pdf (Print Version: 02-AlgorithmAnalysis.pdf)
Pseudo Code: Slide03-Pseudocode-Wikipedia.pdf (URL: https://en.wikipedia.org/wiki/Pseudocode)
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);
* Reference05-AmortizedAnalysis.pdf -- Auxiliary Slides Introducing Aggregate Method of Amortized Analysis.

Lab 1: Algorithm Analysis (Due: 23:59, 09/22/2019)

Lab01-AlgorithmAnalysis: Lab01-AlgorithmAnalysis.pdf
LaTeX Source of Lab01: Lab01-AlgorithmAnalysis.tex
Submission Requirements: SubmissionRequirements.pdf
Lab01-Solution: Lab01-Solution.pdf

Lecture 3: Divide and Conquer

Reading Materials

Slide: Slide04-DivideConquer.pdf (Print Version: 04-DivideConquer.pdf)
Reference: Reference06-DivideConquer.pdf -- Chapter 2 in "Algorithm" by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, McGraw-Hill, 2007.

Lab 2: Divide and Conquer (Due: 10:00am, 09/27/2019)

Lab02-DivideConquer: Lab02-DivideConquer.pdf
LaTeX Source of Lab02: Lab02-DivideConquer.tex
Lab02-Solution: Lab02-Solution.pdf

Lecture 4: 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)

Lecture 5: Matroid

Reading Materials

Slide: Slide06-Matroid.pdf (Print Version: 06-Matroid.pdf)
Reference:
* Reference08-Matroid.pdf -- Chapter 16.4 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.

Lecture 6: Dynamic Programming

Reading Materials

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

Lab 3: Greedy Strategy (Due: 08:00am, 10/09/2019)

Lab03-GreedyStrategy: Lab03-GreedyStrategy.pdf
LaTeX Source of Lab03: Lab03-GreedyStrategy.tex (Figure: Fig-Q3.pdf)
Lab03-Solution: Lab03-Solution.pdf

Lecture 7: Shortest Path

Reading Materials

Slide: Slide08-ShortestPath.pdf (Print Version: 08-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).

Lecture 8: Network Flow

Reading Materials

Slide: Slide09-NetworkFlow.pdf (Print Version: 09-NetworkFlow.pdf)
Reference: Reference13-NetworkFlow.pdf Chapter 25 in "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition).

Lab 4: Network Flow (Due: 08:00am, 10/23/2019)

Lab04-NetworkFlow: Lab04-NetworkFlow.pdf
LaTeX Source of Lab04: Lab04-NetworkFlow.tex
Test Case: Lab04-TestCase.zip, Lab04-TestCase2.zip (you can choose either one)
Lab04-Solution: Lab04-Solution.pdf

Lecture 9: NP Problem

Reading Materials

Slide: Slide10-TuringMachine.pdf (Print Version: 10-TuringMachine.pdf)
Slide: Slide11-NPReduction.pdf (Print Version: 11-NPReduction.pdf)
Reference:

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

* Reference15-NPReduction.pdf Chapter 8 in "Algorithm Design" by J. Kleinberg, and E. Tardos, Pearson-Addison Wesley, 2005.

Music: The Longest Path (1988).

Lab 5: NP Reduction (Due: 8:00am, 10/30/2019)

Lab05-NPReduction: Lab05-NPReduction.pdf
LaTeX Source of Lab05: Lab05-NPReduction.tex
Lab05-Solution: Lab05-Solution.pdf

Lecture 10: Approximation I

Reading Materials

Slide: Slide12-ApproximationI.pdf (Print Version: 12-ApproximationI.pdf)
Reference: 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.

Lab 6: NP Reduction II (Due: 8:00am, 11/06/2019)

Lab06-NPReductionII: Lab06-NPReductionII.pdf
LaTeX Source of Lab06: Lab06-NPReductionII.tex
Lab06-Solution: Lab06-Solution.pdf

Lecture 11: Approximation II

Reading Materials

Slide: Slide13-ApproximationII.pdf (Print Version: 13-ApproximationII.pdf)
Reference: Reference17-ApproximationII.pdf Chapter 14 in "Approximation Algorithms" by V.Vazirani, Springer-Verlag, 2001.

Lab 7: Approximation(Due: 10:00am, 11/15/2019)

Lab07-Approximation: Lab07-Approximation.pdf
LaTeX Source of Lab07: Lab07-Approximation.tex
Lab07-Solution: Lab07-Solution.pdf

提交引导 (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)

Project Description
- Project01-OnlineRide-HailingPlatform: Project01-OnlineRide-HailingPlatform.pdf
- The project deadline is December 30th. You should submit all materials before 24:00.
- No machine learning.
Related Documents
- Report Template: Project-Template.zip
- The requirements of demo and the time schedule: Requirements of Demo.pdf

分组活动细节 (Group Project Detail)

序号 (No.)	队名 (Team Name)	队员一 (Member 1)	队员二 (Member 2)	队员三 (Member 3)	题目 (Project)	时间 (Time)
1	硬刚队	刘明桓	陈铭城	王文韬
2	HelloWorld队	郑天晴	李思妍	张宇航
3	考试全队	王智恺	汪金奕	杨军港
4	0 ERROR	兰晶	李昊	马丽
5	你有看见我的小熊吗	郭向哲	黄修齐	徐安然
6	Algorithm is All Your Need	晋嘉睿	李江彤	符凯华
7	thinklab	刘贝	杨学	张哲熙
8	Accepted	赵登伟	马钦	张向阳
9	制霸算法233	孙嘉徽	杨兆星	刘艺娟
10	algorithm passing！	常家豪	石佳银	张平
11	名不虚传队	冯宽	龙少聪	郑继来
12	54749110	耿玉晗	向文钊	何远航
13	野比大雄	舒圆鹤	王晓丹	卢广犇
14	起名字好难	王堃	梁京	冷亦君
15	return	徐姚亨	王刘军	王煜林
16	哈士奇	詹诗渊	濮怡萍	王叶舟
17	你的组名	孙随彬	张宗璞	周千寓
18	御坂没有琴	刘炎	吴贺贺	周成鹏
19	哈哈哈	李世博	黄江林	陈孝聪
20	白给	杨晓宇	金义博	李俊彦
21	Coooool	王科	张澍裕	李恺健
22	开开心心_不动脑筋	徐梦遥	方浩树	段子敬
23	锟斤拷	陆佳妮	俞铄点	刘一鸣
24	算法大乱斗	王哲	卢昊桢	张新
25	ele.math	白天	CHRISTOPHE...	陈浩

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

Roster

History Roster

引用材料 (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.