Algorithm and Complexity (2020)

基本信息 (General Information)

Level: Undergraduate

Time & Place: 10:00 – 11:40, Monday & Thursday, Xia Yuan 413 (下院413)

Instructor:

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

Teaching Assistant:

Name: Yiming Liu (刘一鸣)
Email: lucien@sjtu.edu.cn
Office: SEIEE 3-328
Phone: 13262779116
Office Hour: 9:00 - 11:00, Tuesday

Name: Shuodian Yu (俞铄点)
Email: timplex233@sjtu.edu.cn
Office: SEIEE 3-328
Phone: 18721659971
Office Hour: 19:00 - 21:00, Monday

课堂时间 (Course Schedule)

计划日程 (Syllabus)

Week	Date	Lecture Topic	Event	TA
1	Mar.02	Algorithm Design and Analysis (1) Introduction of This Class, Basic Concepts, Time / Space Complexity, etc.	Lab-00	俞铄点
1	Mar.05	Algorithm Design and Analysis (2) Sorting, Searching, and Selection (Deterministic & Randomized)	Lab-01	俞铄点
2	Mar.09	Divide-and-Conquer (1) Mergesort, Selection, Master’s Theorem, etc.		刘一鸣
2	Mar.12	Divide-and-Conquer (2) Sorting Network, etc.	Lab-02	刘一鸣
3	Mar.16	Greedy Approach (1) Interval Scheduling, Interval Partitioning, Minimum Lateness, etc.		俞铄点
3	Mar.19	Greedy Approach (2) Independent System, Matroid, etc.	Lab-03	俞铄点
4	Mar.23	Greedy Approach (3) Matroid Example: Greedy-Max Algorithm, etc.		刘一鸣
4	Mar.26	Dynamic Programming (1) Basic Dynamic Programming, etc.	Lab-04	刘一鸣
5	Mar.30	Dynamic Programming (2) Weighted Interval Scheduling, Segmented Least Squares, Knapsack, etc.		俞铄点
5	Apr.02	Dynamic Programming (3) & Linear Programming (1) RNA Secondary Structure, Sequence Alignment, Basic Form, etc.	Lab-05	俞铄点
6	Apr.06	National Holiday
6	Apr.09	Linear Programming (2) Basic Form, Duality Theory, Simplex Algorithm, etc.	Lab-06	刘一鸣
7	Apr.13	Amortized Analysis (1) Aggregate Analysis, Accounting Method, etc.		俞铄点
7	Apr.16	Amortized Analysis (2) Potential Method, Dynamic Table, etc.	Lab-07	俞铄点
8	Apr.20	Graph Algorithms (1) Basic Concepts, Minimum Spanning Tree, etc.		刘一鸣
8	Apr.23	Graph Algorithms (2) Searching and Exploration.	Lab-08	刘一鸣
9	Apr.26	Graph Algorithms (3) Single Source Shortest Paths (Greedy & DP), All-Pair Shortest Paths, etc.		俞铄点
9	Apr.27	Graph Algorithms (4) Flow Problem, Maximum Flow, Minimum Cut, etc.		俞铄点
9	Apr.30	Turing Machine (1) Computability, Turing Machine, etc.	Lab-09	俞铄点
10	May.04	National Holiday		刘一鸣
10	May.07	Turing Machine (2) Turing Machine Variation, Computable & Decidable, etc.	Lab-10	刘一鸣
11	May.11	NP-Completeness (1) NP class, Polynomial time, etc.		俞铄点
11	May.14	NP-Completeness (2) Reducibility, Proofs, etc.	Lab-11	俞铄点
12	May.18	NP-Completeness (3) Reducibility Examples, Proofs, etc.		刘一鸣
12	May.21	NP-Completeness (4) Reducibility Examples, Proofs, etc.		刘一鸣
13	TBD	Final Exam

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

Lecture 0: Preliminary

Reading Materials

Syllabus & Grading Policy: Syllabus-AlgorithmComplexity.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)

Video Record

Video for Preliminary: Video01-Preliminary.mp4
Video for Symbols: Video02-Symbols.mp4
Video for Proof: Video03-Proof.mp4
Video for Lab00: Video04-Lab00.mp4

Lab 0: Proof (Due: 10:00am, 03/02/2020)

Lab00-Proof: Lab00-Proof.pdf
LaTeX Source of Lab00: Lab00-Proof.tex
Submission Requirements: Submission Requirements.pdf
Lab00-Solution: Lab00-Solution.pdf
Best Labs: Lab00-HongjieFang.pdf, Lab00-LongyuanGe.pdf, Lab00-XinyuXu.pdf.

Lecture 1: Algorithm Analysis

Reading Materials

Slide: Slide02-AlgorithmAnalysis.pdf (Print Version: 02-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).

Video Record

Video for Computation Theory (1): Video05-ComputationTheory(1).mp4
Video for Computation Theory (2): Video06-ComputationTheory(2).mp4
Video for Computation Theory (3): Video07-ComputationTheory(3).mp4
Video for Count: Video08-Count.mp4
Video for Complexity Style: Video09-ComplexityStyle.mp4
Video for Linear Search: Video10-LinearSearch.mp4
Video for Binary Search: Video11-BinarySearch.mp4
Video for Linear Sorting Algorithm: Video12-LinearSorting.mp4
Video for Recursive Sorting Algorithm: Video13-RecursiveSorting.mp4

Lab 1: Algorithm Analysis (Due: 10:00am, 03/12/2020)

Lab01-AlgorithmAnalysis: Lab01-AlgorithmAnalysis.pdf
LaTeX Source of Lab01: Lab01-AlgorithmAnalysis.tex
Lab01-Solution: Lab01-Solution.pdf
Best Labs: Lab01-ZheXie.pdf, Lab01-YulongHui.pdf, Lab01-HongjieFang.pdf.

Poster and In-Class Quiz

- Poster for Algorithm Analysis
- Quiz on 03/02/2020
- Quiz on 03/05/2020

Lecture 2: Divide and Conquer

Reading Materials

Slide: Slide03-DivideConquer.pdf (Print Version: 03-DivideConquer.pdf)
Reference: Reference05-DivideConquer.pdf Chapter 2 of "Algorithm" by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, McGraw-Hill, 2007.
Reference: 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).

Video Record

Video for Divide and Conquer (1): Video14-DivideConquer(1).mp4
Video for Divide and Conquer (2): Video15-DivideConquer(2).mp4
Video for Divide and Conquer (3): Video16-DivideConquer(3).mp4

Poster，In-Class Quiz and In-Class Note

- Poster for Divide and Conquer
- Quiz on 03/09/2020
- Deduction of Master's Theorem

Lecture 3: Sorting Network

Reading Materials

Slide: Slide04-SortingNetwork.pdf (Print Version: 04-SortingNetwork.pdf)
Reference: Reference07-SortingNetwork.pdf Chapter 27 of "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2002. (2nd Edition).

Tkinter Tutorial

Official Documentation: Tkinter - Python interface to Tcl/Tk
Tkinter Tutorial: TkinterTutorial.pdf
Sorting Network: Code-SortingNetwork.rar

Video Record

Video for Sorting Network (1): Video17-Sorting Network(1).mp4
Video for Sorting Network (2): Video18-Sorting Network(2).mp4
Video for Sorting Network (3): Video19-Sorting Network(3).mp4
Video for Tkinter Tutorial: Video20-Tkinter Tutorial.mp4

Lab 2: Divide and Conquer (Due: 10:00am, 03/19/2020)

Lab02-DivideConquer: Lab02-DivideConquer.pdf
LaTeX Source of Lab02: Lab02-DivideConquer.tex
Lab02-Solution: Lab02-Solution.pdf
Best Labs: Lab02-ShengyuanHou.pdf, Lab02-HongjieFang.pdf, Lab02-SiyuanBian.pdf.

Different Visualization Tools (Click picture to download source code):

- Zehao Wang (C)
- Letian Peng (Matlab)
- Mengshi Chen (AutoCad)
- Hongjie Fang (python)

Lecture 4: Greedy Strategy

Reading Materials

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

Video Record

Video for Interval Scheduling: Video21-Interval Scheduling.mp4
Video for Interval Partitioning: Video22-Interval Partitioning.mp4
Video for Scheduling to Minimize Lateness: Video23-Scheduling to Minimize Lateness.mp4
Video for Optimal Caching: Video24-Optimal Caching.mp4
Video for Coin Change: Video25-Coin Change.mp4

Poster and In-Class Quiz

- Poster for Greedy Algorithm
- Quiz on 03/16/2020

Lecture 5: Matroid

Reading Materials

Slide: Slide06-Matroid.pdf (Print Version: 06-Matroid.pdf)
Reference:

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

* Reference10-GreedyMax.pdf 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.

Video Record

Video for Matroid: Video26-Matroid.mp4
Video for u(F)&v(F): Video27-u(F)&v(F).mp4
Video for Greedy-Max (1): Video28-Greedy Max(1).mp4
Video for Greedy-Max (2): Video29-Greedy Max(2).mp4
Video for Disjoint Path Matroid: Video30-Disjoint Path Matroid.mp4
Video for Task Scheduling Problem (1): Video31-Task Scheduling Problem(1).mp4
Video for Task Scheduling Problem (2): Video32-Task Scheduling Problem(2).mp4

Lab 3: Greedy Strategy (Due: 10:00am, 03/26/2020)

Lab03-GreedyStrategy: Lab03-GreedyStrategy.pdf
LaTeX Source of Lab03: Lab03-GreedyStrategy.tex
Lab03-Solution: Lab03-Solution.pdf
Best Labs: Lab03-FutaoWei.pdf, Lab03-YulongHui.pdf, Lab03-HongjieFang.pdf

Poster and Proof for Disjoint Path Matroid (by Hongjie Fang)

- Poster for Matroid
- Proof for Disjoint Path Matroid

Lecture 6: Dynamic Programming

Reading Materials

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

Video Record

Video for Dynamic Program (1): Video33-Dynamic Program(1).mp4
Video for Dynamic Program (2): Video34-Dynamic Program(2).mp4
Video for Knapsack Problem: Video35-Knapsack Problem.mp4
Video for RNA Secondary Structure: Video36-RNA Secondary Structure.mp4
Video for String Similarity: Video37-String Similarity.mp4
Video for Hirschberg's Alignment Algorithm (1): Video38-Hirschberg's Alignment Algorithm(1).mp4
Video for Hirschberg's Alignment Algorithm (2): Video39-Hirschberg's Alignment Algorithm(2).mp4

Lab 4: Matroid (Due: 10:00am, 04/02/2020)

Lab04-Matroid: Lab04-Matroid.pdf
LaTeX Source of Lab04: Lab04-Matroid.tex
Lab04-Solution: Lab04-Solution.pdf
Best Labs: Lab04-YetongZhou.pdf, Lab04-ShengchaoHu.pdf, Lab04-HongjieFang.pdf

Poster and In-Class Quiz

- Poster for Dynamic Programming
- Quiz on 03/30/2020
- Result of the Quiz

Lecture 7: Dynamic Programming Practice

Lab 5: Dynamic Programming (Due: 10:00am, 04/09/2020)

Lab05-DynamicProgramming: Lab05-DynamicProgramming.pdf
LaTeX Source of Lab05: Lab05-DynamicProgramming.tex
Test Case: Lab05-TestCase.zip
Lab05-Solution: Lab05-Solution.pdf, Lab05-Solution.zip
Best Labs: Lab05-YongwenSu.pdf, Lab05-ChenyangWu.pdf, Lab05-HongjieFang.pdf

Lecture 8: Linear Programming

Reading Materials

Slide: Slide08-LinearProgramming.pdf (Print Version: 08-Linear Programming.pdf)
Reference:
* Reference12-LinearProgramming.pdf Chapter 29.1 in "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition);
* Chapter 7.4 in "Algorithms" by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, McGraw-Hill, 2007.
* Reference13-SimplexAlgorithm.pdf Chapter 29.3 in "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition).
* Reference14-ModelFormulation.pdf Chapter 12.3-12.4 in "Introduction to Operations Research" by Frederick S. Hillier, Gerald J. Lieberman, Tata McGraw-Hill Education, 2015. (10th Edition)

CPLEX Tutorial

Get CPLEX from IBM ILOG CPLEX Optimization Studio (jbox)
Get official documentation from IBM Knowledge Center

CPLEX Tutorial: CPLEXTutorial.pdf, Model_Building_in_Mathematical_Programmi.pdf

Video Record

Video for Linear Programming: Video40-Linear Programming.mp4
Video for CPLEX Tutorial: Video41-CPLEX Tutorial.mp4
Video for Standard Form of LP: Video42-Standard Form of LP.mp4
Video for Other Programming: Video43-Other Programming.mp4
Video for Duality: Video44-Duality.mp4
Video for Simplex Method (1): Video45-Simplex Method.mp4
Video for Simplex Method (2): Video46-Simplex Method.mp4

Lab 6: Linear Programming (Due: 10:00am, 04/16/2020)

Lab06-LinearProgramming: Lab06-LinearProgramming.pdf
LaTeX Source of Lab06: Lab06-LinearProgramming.tex
Lab06-Solution: Lab06-Solution.pdf
Best Labs: Lab06-ZiqiZhao.pdf, Lab06-YaoSu.pdf, Lab06-HongjieFang.pdf

Poster

- Poster for Linear Programming
- Quiz on 04/09/2020
- Result of the Quiz

Lecture 9: Amortized Analysis

Reading Materials

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

Video Record

Video for Amortized Analysis (1): Video47-Amortized Analysis(1).mp4
Video for Three Methods: Video48-Three Methods.mp4
Video for Dynamic Table (1): Video49-Dynamic Table(1).mp4
Video for Dynamic Table (2): Video50-Dynamic Table(2).mp4

Lab 7: Amortized Analysis (Due: 10:00am, 04/23/2020)

Lab07-Amortized Analysis: Lab07-AmortizedAnalysis.pdf
LaTeX Source of Lab07: Lab07-AmortizedAnalysis.tex, Fig-MultiStack.pdf
Lab07-Solution: Lab07-Solution.pdf
Best Labs: Lab07-HongjieFang.pdf, Lab07-ZheXie.pdf, Lab07-ShiquWu.pdf

Poster and In-Class Quiz

- Poster for Amortized Analysis
- Quiz on 04/16/2020
- Result of the Quiz

Lecture 10: Graph Exploration

Reading Materials

Slide: Slide10-GraphAlgorithm.pdf (Print Version: 10-GraphAlgorithm.pdf)
Slide: Slide11-BFSDFS.pdf (Print Version: 11-BFSDFS.pdf)
Learn Borüvka Algorithm from Wikipedia
Reference: Reference16-GraphDecomposition.pdf Chapter 3, 4 in "Algorithm" by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, McGraw-Hill, 2007.

Video Record

Video for Algorithm on Graph: Video51-Algorithm on Graph.mp4
Video for DFS Undirected Graphs: Video52-DFS Undirected Graphs.mp4
Video for DFS Directed Graphs: Video53-DFS Directed Graphs.mp4
Video for BFS: Video54-BFS.mp4

Lab 8: Graph Exploration (Due: 10:00am, 04/30/2020)

Lab08-GraphExploration: Lab08-GraphExploration.pdf
LaTeX Source of Lab08: Lab08-GraphExploration.tex, Fig-Definition.pdf
Lab08-Solution: Lab08-Solution.pdf
Best Labs: Lab08-HongjieFang.pdf, Lab08-JinyiXiang.pdf, Lab08-YetongZhou.pdf

Poster and In-Class Quiz

- Poster for Graph Exploration
- Quiz on 04/23/2020
- Quiz on 04/23/2020

Lecture 11: Shortest Path

Reading Materials

Slide: Slide12-ShortestPath.pdf (Print Version: 12-ShortestPath.pdf)
Reference:
* Reference17-ShortestPath.pdf Chapter 24 in "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition);
* Reference18-ShortestPathDP.pdf Chapter 6.8, 6.10 in "Algorithm Design" by J. Kleinberg, and E. Tardos, Pearson-Addison Wesley, 2005;
* Reference19-AllPairShortestPath.pdf Chapter 25 in "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition);
* Reference20-Heaps.pdf, Reference21-FibonacciHeaps.pdf Slide for Heap in Data Structure Class from Kevin Wayne @ Princeton.

Video Record

Video for Introduction to Shortest Path: Video55-Introduction to Shortest Path.mp4
Video for Dijkstra Algorithm: Video56-Dijkstra Algorithm.mp4
Video for Bellman-Ford Algorithm (1): Video57-Bellman-Ford Algorithm.mp4
Video for Bellman-Ford Algorithm (2): Video58-Bellman Ford.mp4
Video for All-Pair Shortest Paths: Video59-All-Pair Shortest Paths.mp4

Lecture 12: Network Flow

Reading Materials

Slide: Slide13-NetworkFlow.pdf (Print Version: 13-NetworkFlow.pdf),
Demo: Slide14-GraphAlgorithmDemo.pdf
Reference: Reference22-NetworkFlow.pdf Chapter 25 in "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition).

Gephi Tutorial

Get Gephi from Official Website
Gephi Tutorial: GephiTutorial.pdf

Video Record

Video for Network Flow: Video60-Network Flow.mp4
Video for Ford-Fulkerson Algorithm: Video61-Ford-Fulkerson Algorithm.mp4
Video for Gephi Tutorial: Video62-Gephi Tutorial.mp4

Lab 9: Network Flow (Due: 10:00am, 05/07/2020)

Lab09-Network Flow: Lab09-NetworkFlow.pdf
LaTeX Source of Lab09: Lab09-NetworkFlow.tex
Data Source of Lab09: SCC.cpp, SCC.in, MCMF.in
Lab09-Solution: Lab09-Solution.pdf
Best Labs: Lab09-HongjieFang.pdf, Lab09-ShengyiHua.pdf, Lab09-YichiZhang.pdf

Best Visualization

- Shengyi Hua (1)
- Hongjie Fang
- Yetong Zhou
- Shengyi Hua (2)
- Chang Liu
- Yichi Zhang

Lecture 13: Turing Machine

Reading Materials

Slide: Slide15-TuringMachine.pdf (Print Version: 15-TuringMachine.pdf)
Reference: Reference23-TuringMachine.pdf Chapter 1 in "Computational Complexity: A Modern Approach", by Sanjeev Arora and Boaz Barak, Cambridge University Press, 2006.

Video Record

Video for Effective Procedure: Video63-Effective Procedure.mp4
Video for Turing Machine: Video64-Turing Machine.mp4
Video for TM-Variation & TM-Computation: Video65-TM-V&C.mp4
Video for Computable and Decidable: Video66-Computable and Decidable.mp4

Lab 10: Turing Machine (Due: 10:00am, 05/14/2020)

Lab10-Turing Machine: Lab10-TuringMachine.pdf
LaTeX Source of Lab10: Lab10-TuringMachine.tex, Fig-Access.pdf, Fig-Broadcast.pdf, Fig-Conflict.pdf
Lab10-Solution: Lab10-Solution.pdf
Best Labs: Lab10-HongjieFang.pdf, Lab10-XingliWang.pdf, Lab10-ZhengChen.pdf

Poster and In-Class Quiz

- Poster for Turing Machine
- Quiz on 04/30/2020
- Answers from Chunyu Xue (upper) and Yao Su (lower)

Lecture14: NP and Reduction

Reading Materials

Slide: Slide16-NPReduction.pdf (Print Version: 16-NPReduction.pdf)
Reference: Reference24-NPReduction.pdf Chapter 8 in "Algorithm Design" by J. Kleinberg, and E. Tardos, Pearson-Addison Wesley, 2005.
Music: The Longest Path (1988)

Video Record

Video for Computational Complexity: Video67-Computational Complexity.mp4
Video for Definition of NP: Video68-Definition of NP.mp4
Video for Polynomial-Time Reductions: Video69-Polynomial-Time Reductions.mp4
Video for Basic Reduction Strategies: Video70-Basic Reduction Strategies.mp4
Video for Definition of NP-Complete: Video71-Definition of NP-Complete.mp4
Video for Reduction via Gadgets: Video72-Reduction via Gadgets.mp4
Video for Team Project: Video73-Team Project.mp4
Video for NP Directed Hamilton Cycle: Video74-NP Directed Hamilton Cycle.mp4
Video for Longest Path & TSP: Video75-Longest Path & TSP.mp4
Video for 3D-Matching: Video76-3D-Matching.mp4
Video for 3D-matching (2): Video77-3D-matching (2).mp4
Video for 3-COLOR: Video78-3-COLOR.mp4
Video for Numerical Problems: Video79-Numerical Problems.mp4
Video for co-NP and the Asymmetry of NP: Video80-co-NP and the Asymmetry of NP.mp4

Lab 11: NP Reduction (Due: 10:00am, 05/21/2020)

Lab11-NP Reduction: Lab11-NPReduction.pdf
LaTeX Source of Lab11: Lab11-NPReduction.tex
Lab11-Solution: Lab11-Solution.pdf
Best Labs: Lab11-ZiqiZhao.pdf, Lab11-HaotianXue.pdf, Lab11-HongjieFang.pdf

Poster

- Poster for NP and Reduction
- Reduction from 3-SAT to 3D-MATCHING (n=2)
- Reduction from 3-SAT to 3D-MATCHING (n=3)

Lecture 15: Final Exam

Materials

Organization And Rules: FinalExam-OrganizationAndRules(Chinese).pdf, FinalExam-OrganizationAndRules(Eng).pdf
Answer Template: FinalExam-答题模板.doc, FinalExam-AnswerTemplate.doc

提交引导 (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
- Each group can have at most 3 persons.
- Please find your group member before 10:00am 04/30/2020 in our class.
- If you haven't found your group member by this ddl, then by default we consider that you choose random grouping.
Project Description
- Project-BusBooking: Project-BusBooking.pdf
- Project Report Submission Deadline: 23:59, 06/15/2020 (including all sources and data)
- Project Demo Schedule: Week 16 (TBD)
- Project-DemoDescription: Project-DemoDescription.pdf
Related Document
- Project-DataAssignment: Project-DataAssignment.pdf
- Project-DataField: Project-DataField.pdf
- Project-Template: Project-Template.zip

分组活动细节 (Group Project Detail)

序号 (No.)	队名 (Team Name)	队员一 (Member 1)	队员二 (Member 2)	队员三 (Member 3)	成都数据 (Data 1)	海口数据 (Data 2)
1	蒜法带师	方泓杰	颜培深	薛春宇	2016/11/5	2017/10/11-10/14
2	爱卿	葛龙渊	郝宏坤	王星力	2016/11/17	2017/8/25-8/28
3	Huskies	薛昊天	卞思沅	刘一凡	2016/11/6	2017/10/7-10/10
4	9-9-6	罗旸	韦福韬	向谨溢	2016/11/7	2017/10/3-10/6
5	专业团队	刘畅	胡胜超	谢哲	2016/11/8	2017/9/30-10/2
6	不知叫什么好	武晨洋	林少雄	苏勇文	2016/11/9	2017/9/26-9/29
7	不会起名字队	侯晟元	陈牧遥	谢泽宇	2016/11/10	2017/9/22-9/25
8	Intrepid Charming Modeling	彭乐天	姚迪熙	李洪旭	2016/11/11	2017/9/18-9/21
9	anl.sjtu.edu.cn	卓建衡	华晟驿	闫家硕	2016/11/12	2017/9/14-9/17
10	Algo Team 1	KAR CHUN T...	CHANYOUNG ...	TAKEHIRO M...	2016/11/13	2017/9/10-9/13
11	1145141919810	王政栋	郑东林	姚以真	2016/11/14	2017/9/6-9/9
12	名字真难取	穆凡	唐嘉璇	杨涵章	2016/11/15	2017/9/2-9/5
13	上流社会	张靖炜	方志成	周烨彤	2016/11/16	2017/8/29-9/1
14	乌兹，永远滴神	曹俊翔	李森	吴仕渠	2016/11/4	2017/10/15-10/18
15	美很	赵梓淇	惠宇龙	魏逸飞	2016/11/18	2017/8/21-8/24
16	algiaorithm队	陈铮	白骐硕	贺知行	2016/11/19	2017/8/17-8/20
17	奥利给	汤学涵	严秉昊	陈梦实	2016/11/20	2017/8/13-8/16
18	不做完project不起名字	温一帆	朱佳栋	林超	2016/11/21	2017/8/9-8/12
19	Deep♂Dark♂Fantasy♂	陈冲	黎学丞	张振东	2016/11/22	2017/8/5-8/8
20	Hello World	徐昕宇	王泽浩	刘旭	2016/11/23	2017/8/1-8/4
21	老师让我起个好名字	张一弛	焦壮壮	黄中钰	2016/11/24	2017/7/28-7/31
22	名字不重要	王翊辰	黄霖	龚玲禾	2016/11/25	2017/7/24-7/27
23	邪王真眼是最强的	刁义嘉	陈思远	周轾	2016/11/26	2017/7/20-7/23
24	Not Today	ELIZAVETA ...	LUDOVIC TA...	YERNUR KAS...	2016/11/27	2017/7/16-7/19
25	取名癌晚期患者	田书翰	沈嘉辰	高文轩	2016/11/28	2017/7/12-7/15
26	算法小分队1	沈君陶	赵翔宇	白忱枫	2016/11/29	2017/7/8-7/11
27	算法小分队2	霍达	付益聪	AKBOTA KUA...	2016/11/30	2017/7/4-7/7

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

Roster

Class Attendance Pictures

History Roster

光荣榜 (Honor Roll)

序号 (Number)	姓名 (Name)	加分时间 (Time)	加分原因 (Reason)	加分人 (Recorder)
1	韦福韬	2020/02/22	指正Slide01-Proof中Proper Subset和Strict Subset的定义	高晓沨
2	方泓杰	2020/02/22	指正Slide01-Proof中强数学归纳法示例P(n)的指代	高晓沨
3	黄中钰	2020/02/24	指正Slide02-AlgorithmAnalysis中Bubble Sort的时间复杂度分析	高晓沨
4	方泓杰	2020/02/24	指正Slide02-AlgorithmAnalysis伪代码数组起始项、撰写渐进复杂度表格	高晓沨
5	苏勇文	2020/02/25	指正Slide02-AlgorithmAnalysis中LinearSearch的伪代码	俞铄点
6	方泓杰	2020/03/02	课堂回答Quiz问题 (Algorithm Analysis)	俞铄点
7	赵梓淇	2020/03/05	课堂回答Quiz问题 (Algorithm Analysis)	俞铄点
8	刘一凡	2020/03/07	指正Lab01中关于log的定义 (log默认为log_2，lg默认为log_10)	俞铄点
9	薛春宇	2020/03/10	分享主定理推导笔记	刘一鸣
10	方泓杰	2020/03/12	Best Lab for Lab00-Proof	刘一鸣
11	葛龙渊	2020/03/12	Best Lab for Lab00-Proof	刘一鸣
12	徐昕宇	2020/03/12	Best Lab for Lab00-Proof	刘一鸣
13	谢哲	2020/03/19	Best Lab for Lab01-AlgorithmAnalysis	俞铄点
14	惠宇龙	2020/03/19	Best Lab for Lab01-AlgorithmAnalysis	俞铄点
15	方泓杰	2020/03/19	Best Lab for Lab01-AlgorithmAnalysis	俞铄点
16	方泓杰	2020/03/20	证明 Disjoint Path Matroid正确性，并写出完整证明过程	刘一鸣
17	王泽浩	2020/03/20	提出Disjoint Path Matroid证明思路	刘一鸣
18	卓建衡	2020/03/20	提出Disjoint Path Matroid证明思路	刘一鸣
19	姚迪熙	2020/03/20	提出Disjoint Path Matroid证明思路	刘一鸣
20	黄中钰	2020/03/20	提出Disjoint Path Matroid证明思路	刘一鸣
21	方泓杰	2020/03/26	Best Lab for Lab02-DivideConquer	刘一鸣
22	侯晟元	2020/03/26	Best Lab for Lab02-DivideConquer	刘一鸣
23	卞思沅	2020/03/26	Best Lab for Lab02-DivideConquer	刘一鸣
24	方泓杰	2020/04/02	Best Lab for Lab03-GreedyStrategy	俞铄点
25	韦福韬	2020/04/02	Best Lab for Lab03-GreedyStrategy	俞铄点
26	惠宇龙	2020/04/02	Best Lab for Lab03-GreedyStrategy	俞铄点
27	周烨彤	2020/04/09	Best Lab for Lab04-Matroid	刘一鸣
28	胡胜超	2020/04/09	Best Lab for Lab04-Matroid	刘一鸣
29	方泓杰	2020/04/09	Best Lab for Lab04-Matroid	刘一鸣
30	薛春宇	2020/04/09	指出Slide08-Linear Programming中ILP里整数和自然数使用混淆的错误	刘一鸣
31	王星力	2020/04/09	指出Slide07-Dynamic Programming中斜边权值的错误	刘一鸣
32	KAR CHUN TEONG	2020/04/09	课堂回答Quiz问题 (Linear Programming)	刘一鸣
33	苏勇文	2020/04/16	Best Lab for Lab05-DynamicProgramming	俞铄点
34	武晨洋	2020/04/16	Best Lab for Lab05-DynamicProgramming	俞铄点
35	方泓杰	2020/04/16	Best Lab for Lab05-DynamicProgramming	俞铄点
36	方泓杰	2020/04/23	Best Lab for Lab06-LinearProgramming	刘一鸣
37	苏尧	2020/04/23	Best Lab for Lab06-LinearProgramming	刘一鸣
38	赵梓淇	2020/04/23	Best Lab for Lab06-LinearProgramming	刘一鸣
39	彭乐天	2020/04/23	课堂回答Quiz问题 (BFSDFS)	刘一鸣
40	杨涵章	2020/04/23	指正Lab08中1.c无向图Dist关系	刘一鸣
41	焦壮壮	2020/04/28	指正lab06第二题答案的问题	刘一鸣
42	方泓杰	2020/04/30	Best Lab for Lab07-Amortized Analysis	俞铄点
43	吴仕渠	2020/04/30	Best Lab for Lab07-Amortized Analysis	俞铄点
44	谢哲	2020/04/30	Best Lab for Lab07-Amortized Analysis	俞铄点
45	郝宏坤	2020/04/30	课堂回答Quiz问题 (Turing Machine)	俞铄点
46	方泓杰	2020/05/07	Best Lab for Lab08-GraphExploration	刘一鸣
47	向谨溢	2020/05/07	Best Lab for Lab08-GraphExploration	刘一鸣
48	周烨彤	2020/05/07	Best Lab for Lab08-GraphExploration	刘一鸣
49	卓建衡	2020/05/14	课堂回答Hamilton Cycle问题 (NP Reduction)	俞铄点
50	方泓杰	2020/05/14	课堂回答Hamilton Cycle问题 (NP Reduction)	俞铄点
51	华晟驿	2020/05/14	Best Lab for Lab09-NetworkFlow	俞铄点
52	张一弛	2020/05/14	Best Lab for Lab09-NetworkFlow	俞铄点
53	方泓杰	2020/05/14	Best Lab for Lab09-NetworkFlow	俞铄点
54	陈铮	2020/05/25	Best Lab for Lab10-TuringMachine	刘一鸣
55	王星力	2020/05/25	Best Lab for Lab10-TuringMachine	刘一鸣
56	方泓杰	2020/05/25	Best Lab for Lab10-TuringMachine	刘一鸣
57	方泓杰	2020/05/31	Best Lab for Lab11-NPReduction	俞铄点
58	薛昊天	2020/05/31	Best Lab for Lab11-NPReduction	俞铄点
59	赵梓淇	2020/05/31	Best Lab for Lab11-NPReduction	俞铄点
60	薛昊天	2020/06/16	绘制n=3, k=3时3D-MATCHING下的规约	俞铄点
61	方泓杰	2020/06/16	绘制n=3, k=3时3D-MATCHING下的规约	俞铄点
62	卞思沅	2020/06/16	绘制n=3, k=3时3D-MATCHING下的规约	俞铄点
63	黄中钰	2020/06/16	绘制n=3, k=3时3D-MATCHING下的规约	俞铄点
64	颜培深	2020/06/16	绘制n=3, k=3时3D-MATCHING下的规约	俞铄点
65	焦壮壮	2020/06/16	绘制n=3, k=3时3D-MATCHING下的规约	俞铄点
66	苏勇文	2020/06/17	视频组字幕制作校对	俞铄点
67	李洪旭	2020/06/17	视频组字幕制作校对	俞铄点
68	姚迪熙	2020/06/17	视频组字幕制作校对	俞铄点
69	龚玲禾	2020/06/17	视频组视频剪辑	俞铄点
70	颜培深	2020/06/17	视频组视频剪辑	俞铄点
71	张振东	2020/06/17	视频组视频剪辑	俞铄点
72	黎学丞	2020/06/19	指正 Slide16-NPReduction中的错误	刘一鸣

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