Algorithm and Complexity (2021)

基本信息 (General Information)

Level: Undergraduate

Time & Place: 10:00 - 11:40, Tuesday, Dong Shang Yuan 102 (东上院102) & Friday, Shang Yuan 317 (上院317)

Instructor:

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

Name: Lei Wang
Email: wanglei_hb(at)sjtu.edu.cn
Office: Telecom Building 3-337

Teaching Assistant:

Name: Haolin Zhou (周浩麟)
Email: koziello@sjtu.edu.cn
Office: TBD
Phone: 18516186177

Name: Yihao Xie (谢以豪)
Email: crystalys@sjtu.edu.cn
Office: TBD
Phone: 13621817615

课堂时间 (Course Schedule)

计划日程 (Syllabus)

Week	Date	Lecture Topic	Event	Instructor	TA
1	Feb. 23	Course Introduction and Preliminary Introduction of This Class, Basic Concepts, Function, Set, Proof, etc.	Lab-00	X. Gao	H. Zhou
1	Feb. 26	Algorithm Design and Analysis (1) Computation and Complexity, Elementary Examples for Algorithm Analysis	Lab-01	X. Gao	H. Zhou
2	Mar. 02	Algorithm Design and Analysis (2) Sorting, Searching, and Selection (Deterministic & Randomized)		X. Gao	H. Zhou
2	Mar. 05	Divide-and-Conquer (1) Mergesort, Selection, Master’s Theorem, etc.	Lab-02	X. Gao	H. Zhou
3	Mar. 09	Divide-and-Conquer (2) Sorting Network, Zero-One Principle, etc.		X. Gao	H. Zhou
3	Mar. 12	Greedy Approach (1) Interval Scheduling, Interval Partitioning, Minimum Lateness, etc.	Lab-03	X. Gao	H. Zhou
4	Mar. 16	Greedy Approach (2) Independent System, Matroid, etc.		X. Gao	H. Zhou
4	Mar. 19	Greedy Approach (3) Matroid Example: Greedy-Max Algorithm, etc.	Lab-04	X. Gao	H. Zhou
5	Mar. 23	Dynamic Programming (1) Basic Dynamic Programming, etc.		X. Gao	H. Zhou
5	Mar. 26	Dynamic Programming (2) Weighted Interval Scheduling, Segmented Least Squares, Knapsack, etc.	Lab-05	X. Gao	H. Zhou
6	Mar. 30	Dynamic Programming (3) & Linear Programming (1) RNA Secondary Structure, Sequence Alignment, Basic Form, etc.		X. Gao	H. Zhou
6	Apr. 02	Linear Programming (2) Basic Form, Duality Theory, Simplex Algorithm, etc.	Lab-06	X. Gao	H. Zhou
7	Apr. 06	Amortized Analysis (1) Aggregate Method, Accounting Method, Potential Method.		L. Wang	Y. Xie
7	Apr. 09	Amortized Analysis (2) Potential Method, Dynamic Table.	Lab-07	L. Wang	Y. Xie
8	Apr. 13	Graph Algorithms (1) Basic Concepts, Eulerian Cycle, Minimum Spanning Tree, DFS & BFS.		L. Wang	Y. Xie
8	Apr. 16	Graph Algorithms (2) DFS & BFS, Single Source Shortest Paths (Dijkstra Path), Heap.	Lab-08	L. Wang	Y. Xie
9	Apr. 20	Graph Algorithms (3) Single Source Shortest Paths (Bellman-Ford), All-Pair Shortest Paths, etc.		L. Wang	Y. Xie
9	Apr. 23	Graph Algorithms (4) All-Pair Shortest Paths, Flow Problem, Maximum Flow, etc.	Lab-09	L. Wang	Y. Xie
9	Apr. 25	Turing Machine Computability, Turing Machine, Variation, Computable & Decidable, etc.		L. Wang	Y. Xie
10	Apr. 27	Computational Complexity (1) Basic Concepts, P Class, NP Class, etc.		L. Wang	Y. Xie
11	Apr. 30	Computational Complexity (2) NP Reducibility, Proofs, Circuit Set etc.	Lab-10	L. Wang	Y. Xie
11	May. 04	National Holiday
11	May. 07	Computational Complexity (3) Karp Reduction, Hamiltonian Circle Reduction, Proofs, etc.		L. Wang	Y. Xie
12	May. 11	Computational Complexity (4) 3D-Matching Reduction, 3-Color Reduction, Proofs, etc.	Lab-11	L. Wang	Y. Xie
12	May. 14	Computational Complexity (5) & Final Review Reducibility Examples, Proofs, Co-NP, etc.		L. Wang	Y. Xie
13	May.25	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 (present in Chinese)

Video for Preliminary: Video01-Preliminary.mp4
Video for Symbols: Video02-Symbols.mp4

Lab 0: Proof (Due: 10:00am, 02/26/2021)

Self-Introduction: Please log in to the course website with Jaccount, click the name button in the upper right corner, complete the self-introduction and upload a personal photo.
Pre-class survey (in Chinese): Please complete the pre-class survey to help us adjust the course content, address: https://www.wjx.cn/vm/Q2AGKFA.aspx.
Lab00-Proof: Lab00-Proof.pdf
LaTeX Source of Lab00: Lab00-Proof.tex
Submission Requirements: SubmissionRequirements.pdf
Lab00-Solution: Lab00-Solution.pdf
Best Labs: Lab00-JunboWang.pdf, Lab00-ZenanLi.pdf, Lab00-ZilongLi.pdf.
If you cannot read Chinese, please contact TA.

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

Lab 1: Algorithm Analysis (Due: 10:00am, 03/05/2021)

Lab01-AlgorithmAnalysis: Lab01-AlgorithmAnalysis.pdf
LaTeX Source of Lab01: Lab01-AlgorithmAnalysis.tex
Lab01-Solution: Lab01-Solution.pdf
Best Labs: Lab01-JunboWang.pdf, Lab01-QinweiYangi.pdf, Lab01-XinhaoZheng.pdf.

Poster and In-Class Quiz

- Poster for Algorithm Analysis
- Quiz on 03/05/2021
- Quiz on 03/05/2021

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:00am, 03/12/2021)

Lab02-DivideConquer: Lab02-DivideConquer.pdf
LaTeX Source of Lab02: Lab02-DivideConquer.tex
Figure Source: Fig-Transposition.pdf (You need to compile .tex file and .pdf figure file together)
Code Source: Code-Range.cpp
Additional Figure Source: Fig-RecurrenceTree.vsdx, Fig-RecurrenceTree.pptx (You can choose to modify one of these figure sources and save as a .pdf figure file to insert into your .tex file)
Lab02-Solution: Lab02-Solution.pdf
Best Labs: Lab02-QiLiu.pdf, Lab02-HaoyiYou.pdf, Lab02-RenyangGuan.pdf.

Poster and In-Class Note

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

Lecture 3: Sorting Network

Reading Materials

Slide: Slide05-SortingNetwork.pdf (Print Version: 05-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

Microsoft Visio Tutorials

Official Tutorial from Microsoft: A Beginner's Guide to Visio
Another version from Tutorials Point: Microsoft Visio Tutorial.pdf

Implementation of Transposition Network (Click picture to download source code):

- Qinwei Yang (n=13)
- Beichen Yu (n=20)
- Chenxin Mao (n=30)

Lecture 4: Greedy Strategy

Reading Materials

Slide: Slide06-GreedyAlgorithm.pdf (Print Version: 06-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)

Lab 3: Greedy Strategy (Due: 10:00am, 03/19/2021)

Lab03-GreedyStrategy: Lab03-GreedyStrategy.pdf
LaTeX Source of Lab03: Lab03-GreedyStrategy.tex
Code Source: Code-SetCover.cpp
Lab03-Solution: Lab03-Solution.pdf
Best Labs: Lab03-ZilongLi.pdf, Lab03-RenyangGuan.pdf, Lab03-YutianLiu.pdf.

Poster，In-Class Quiz and Least Action Principle (by Zifeng Liu)

- Poster for Greedy Strategy
- Quiz on 03/16/2021
- Least Action Principle

Lecture 5: Matroid

Reading Materials

Slide: Slide07-Matroid.pdf (Print Version: 07-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.

Lab 4: Matroid (Due: 10:00am, 03/26/2020)

Lab04-Matroid: Lab04-Matroid.pdf
LaTeX Source of Lab04: Lab04-Matroid.tex
Lab03-Solution: Lab04-Solution.pdf
Best Labs: Lab04-XudongLu.pdf, Lab04-YanjieZe.pdf, Lab04-ZhenyuTang.pdf.

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

- Poster for Matroid
- Deduction of Master's Theorem

Lecture 6: Dynamic Programming

Reading Materials

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

Lab 5: Dynamic Programming (Due: 10:00am, 04/02/2021)

Lab05-DynamicProgramming: Lab05-DynamicProgramming.pdf
LaTeX Source of Lab05: Lab05-DynamicProgramming.tex
Code Source: Code-OBST.cpp, Code-DTW.cpp
Lab03-Solution: Lab05-Solution.pdf
Best Labs: Lab05-YanjieZe.pdf, Lab05-XinhaoZheng.pdf, Lab05-ZihangXu.pdf

Poster and In-Class Quiz

- Poster for Dynamic Programming
- Q1 of Quiz on 04/02/2021
- Q2 of Quiz on 04/02/2021

Lecture 7: Linear Programming

Reading Materials

Slide: Slide09-LinearProgramming.pdf (Print Version: 09-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

Lab 6: Linear Programming (Due: 10:00am, 04/09/2021)

Lab06-LinearProgramming: Lab06-LinearProgramming.pdf
LaTeX Source of Lab06: Lab06-LinearProgramming.tex
Code Source: Code-SequenceAlignment.cpp, FactoryPlanning.dat
Lab06-Solution: Lab06-Solution.pdf, FactoryPlanning.mod, Code-SequenceAlignment-Solution.cpp
Best Labs: Lab06-YanjieZe.pdf, Lab06-XinhaoZheng.pdf, Lab06-BeichenYu.pdf

Poster and In-Class Quiz

- Poster for Linear Programming
- Q3 of Quiz on 04/02/2021

Lecture 8: Amortized Analysis

Reading Materials

Slide: Slide10-AmortizedAnalysis.pdf (Print Version: 10-AmortizedAnalysis.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)

Lab 7: Amortized Analysis (Due: 10:00am, 04/16/2021)

Lab07-AmortizedAnalysis: Lab07-AmortizedAnalysis.pdf
LaTeX Source of Lab07: Lab07-AmortizedAnalysis.tex, Fig-MultiArray.pdf
Lab07-Solution: Lab07-Solution.pdf
Best Labs: Lab07-XinhaoZheng.pdf, Lab07-YutianLiu.pdf, Lab07-JianxingQin.pdf

Poster and In-Class Quiz

- Poster for Amortized Analysis
- Quiz on 04/13/2021

Lecture 9: Graph Exploration

Reading Materials

Slide: Slide11-GraphAlgorithm.pdf (Print Version: 11-GraphAlgorithm.pdf)
Slide: Slide12-BFSDFS.pdf (Print Version: 12-DFSBFS.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.

Gephi Tutorial

Get Gephi from Official Website
Gephi Tutorial: GephiTutorial.pdf
Video for Gephi Tutorial: GephiTutorial.mp4

Lab 8: GraphExploration (Due: 10:00am, 04/23/2021)

Lab08-GraphExploration: Lab08-GraphExploration.pdf
LaTeX Source of Lab08: Lab08-GraphExploration.tex, Fig-Maze.pdf
Code Source of Lab08: SCC.cpp, SCC.in
Lab08-Solution: Lab08-Solution.pdf
Best Labs: Lab08-ZilongLi.pdf, Lab08-QiLiu.pdf, Lab08-XiwenTeoh.pdf

Poster and In-Class Quiz

- Poster for Graph Exploration
- Quiz on 04/16/2021

Lecture 10: Shortest Path

Reading Materials

Slide: Slide13-ShortestPath.pdf (Print Version: 13-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.

Best Visualization in Lab 08:

- Qi Liu
- Renyang Guan
- Siyuan Wang
- Wendi Chen
- Xinhao Zheng
- Yanjie Ze

Lecture 11: Network Flow

Reading Materials

Slide: Slide14-NetworkFlow.pdf (Print Version: 14-NetworkFlow.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).

Lab 9: Network Flow (Due: 10:00am, 04/30/2021)

Lab09-GraphExploration: Lab09-NetworkFlow.pdf
LaTeX Source of Lab09: Lab09-NetworkFlow.tex, Fig-EscapeProblem.pdf
Lab09-Solution: Lab09-Solution.pdf
Best Labs: Lab09-ChenyangLe.pdf, Lab09-HaoyiYou.pdf, Lab09-RujiaZhang.pdf

Lecture 12: 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.

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

Lab10-Turing Machine: Lab10-TuringMachine.pdf
LaTeX Source of Lab10: Lab10-TuringMachine.tex
Lab10-Solution: Lab10-Solution.pdf
Best Labs: Lab10-QiLiu.pdf, Lab10-PengTang.pdf, Lab10-ChenxinMao.pdf

Poster and In-Class Quiz

- Poster for Turing Machine
- Quiz on 04/27/2021
- Answers from Zilong Li (upper) and Jiaqi Pan (lower)

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

Lab 11: NP Reduction (Due: 10:00am, 05/18/2021)

Lab11-NP Reduction: Lab11-NPReduction.pdf
LaTeX Source of Lab11: Lab11-NPReduction.tex
Lab11-Solution: Lab11-Solution.pdf
Best Lab: Lab11-ZenanLi.pdf, Lab11-JiachenZhu.pdf, Lab11-ZiruiLiu.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 14: Final Exam

Materials

Organization And Rules: FinalExam-OrganizationAndRules.pdf

Final Exam Information

Time: May. 25, 2021 (Tuesday) 10:00 am-12:00 am
Location: ExamOrganization.xlsx
Notice: English only

Class Photo

- 合照

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

Form Your Team
- Please find your group member before 10:00am 04/02/2021 in our class.
- If you haven't found your group member by this ddl, then by default we consider that you choose random grouping.
Default
- Project-Data-AnalyticJobScheduling: Project-Data-AnalyticJobScheduling.pdf
- Project Report Submission Deadline: 23:59, 05/28/2021 (including all sources and data)
- Project Demo Schedule: 05/30/2021
Related Document
- Project-ToyData: ToyData.xlsx
- Project-Template: Project-Template.zip
Project Demo
- Choose a project demo time (Deadline: 2:00pm, 05/28/2021): https://shimo.im/sheets/7Ac8Hkg7rQMFmKca/
- If your group hasn't choose demo time, then by default we consider that your group chooses random time.
- Project Demo Arrangement: ProjectDemoArrangement.pdf

分组活动细节 (Group Project Detail)

序号 (No.)	队名 (Team Name)	队员一 (Member 1)	队员二 (Member 2)	队员三 (Member 3)	分组 (Group)	时间 (Time)
1	nnmmd	李泽楠	方天宬	窦铱明	3-404	12:30-12:45
2	队名叫这因为只能起这么长	迮炎杰	管仁阳	刘祺	3-414	15:30-15:45
3	NULL; DROP DATABASE	杨钦崴	毛晨昕	张杰易	3-404	15:15-15:30
4	shining	汤振宇	王俊博	金凌啸	3-404	15:45-16:00
5	OPT Solution	李昕然	唐鹏	黄奎源	3-404	14:30-14:45
6	rand()	余北辰	潘家琦	高然	3-414	13:30-13:45
7	VOID：BML	郑心浩	刘雨田	叶航宇	3-404	14:45-15:00
8	127.0.0.1	陈文浩	游灏溢	陈文迪	3-414	12:45-13:00
9	堆栈溢出	张曦文	张壮联	朱文韬	3-414	14:45-15:00
10	FT Group	秦健行	梁卓人	张亦昕	3-414	15:15-15:30
11	Autobaseline	杨晴	陆徐东	刘俊涵	3-404	13:30-13:45
12	hello world	李婉婷	林心怡	黄卉妍	3-404	15:00:15:15
13	一个好名字	黄婧靖	都繁荣	许天一	3-414	15:00:15:15
14	MATRIX	张皓然	钟博子韬	王思源	3-404	13:00-13:15
15	代码生产大队	张子殷	黄含清	徐子航	3-414	13:45-14:00
16	哔哩哔哩	韩陶然	魏龙轩	李子龙	3-404	15:30-15:45
17	是时候该想出来了	陈畅	徐薪	芮仁婷	3-404	13:45-14:00
18	return -1	林宇欣	黄度	王超玥	3-414	16:00-16:15
19	Happy?	许贤	乐辰阳	朱家琛	3-414	14:30-14:45
20	请PSG.LGD挑选英雄	丁悠然	唐珂	张汝嘉	3-404	13:15-13:30
21	GKD	胡屹垚	刘余猛	刘梓睿	3-414	13:00-13:15
22	nameless	鲍永翔	章艺久	陈彦宁	3-414	15:45-16:00
23	123	白忱枫	付益聪	张轩恺	3-404	16:00-16:15
24	算法小分队3	李超	沈翔宇	汤志豪	3-414	12:30-12:45
25	算法小分队4	朱子翔	郭潇	盛弘毅	3-404	12:45-13:00

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

Roster

Class Attendance Pictures

History Roster

Class Project Pictures

光荣榜 (Honor Roll)

序号 (Number)	姓名 (Name)	加分时间 (Time)	加分原因 (Reason)	加分人 (Recorder)
1	王俊博	03/10/2021	Best Lab for Lab00-Proof	周浩麟
2	李子龙	03/10/2021	Best Lab for Lab00-Proof	周浩麟
3	李泽楠	03/10/2021	Best Lab for Lab00-Proof	周浩麟
4	王俊博	03/16/2021	Best Lab for Lab01-Algorithm Analysis	周浩麟
5	杨钦崴	03/16/2021	Best Lab for Lab01-Algorithm Analysis	周浩麟
6	郑心浩	03/16/2021	Best Lab for Lab01-Algorithm Analysis	周浩麟
7	刘祺	03/17/2021	Best Lab for Lab02-Divide and Conquer	周浩麟
8	管仁阳	03/17/2021	Best Lab for Lab02-Divide and Conquer	周浩麟
9	游灏溢	03/17/2021	Best Lab for Lab02-Divide and Conquer	周浩麟
10	李子龙	03/26/2021	Best Lab for Lab03-Greedy Strategy	周浩麟
11	管仁阳	03/26/2021	Best Lab for Lab03-Greedy Strategy	周浩麟
12	刘雨田	03/26/2021	Best Lab for Lab03-Greedy Strategy	周浩麟
13	迮炎杰	03/29/2021	Best Lab for Lab04-Matroid	周浩麟
14	陆徐东	03/29/2021	Best Lab for Lab04-Matroid	周浩麟
15	汤振宇	03/29/2021	Best Lab for Lab04-Matroid	周浩麟
16	郑心浩	04/05/2021	Best Lab for Lab05-Dynamic Programming	周浩麟
17	迮炎杰	04/05/2021	Best Lab for Lab05-Dynamic Programming	周浩麟
18	徐子航	04/05/2021	Best Lab for Lab05-Dynamic Programming	周浩麟
19	迮炎杰	04/14/2021	Best Lab for Lab06-Linear Programming	周浩麟
20	郑心浩	04/14/2021	Best Lab for Lab06-Linear Programming	周浩麟
21	余北辰	04/14/2021	Best Lab for Lab06-Linear Programming	周浩麟
22	毛晨昕	04/17/2021	指出lab08中的题干歧义	谢以豪
23	郑心浩	04/17/2021	指出lab08中的题干歧义	谢以豪
24	毛晨昕	04/30/2021	指出lab10中的题干错误	谢以豪
25	郑心浩	04/30/2021	Best Lab for Lab07-Amortized Analysis	谢以豪
26	刘雨田	04/30/2021	Best Lab for Lab07-Amortized Analysis	谢以豪
27	秦健行	04/30/2021	Best Lab for Lab07-Amortized Analysis	谢以豪
28	李子龙	05/04/2021	Best Lab for Lab08-Graph Exploration	谢以豪
29	刘祺	05/04/2021	Best Lab for Lab08-Graph Exploration	谢以豪
30	张曦文	05/04/2021	Best Lab for Lab08-Graph Exploration	谢以豪
31	乐辰阳	05/12/2021	Best Lab for Lab09-Network Flow	谢以豪
32	游灏溢	05/12/2021	Best Lab for Lab09-Network Flow	谢以豪
33	窦铱明	05/12/2021	Best Lab for Lab09-Network Flow	谢以豪
34	刘祺	05/19/2021	Best Lab for Lab10-Turing Machine	谢以豪
35	唐鹏	05/19/2021	Best Lab for Lab10-Turing Machine	谢以豪
36	毛晨昕	05/19/2021	Best Lab for Lab10-Turing Machine	谢以豪
37	李泽楠	05/21/2021	Best Lab for Lab11-NP Reduction	谢以豪
38	朱家琛	05/21/2021	Best Lab for Lab11-NP Reduction	谢以豪
39	刘梓睿	05/21/2021	Best Lab for Lab11-NP Reduction	谢以豪
40	陆徐东	05/29/2021	指出lab04解答中的错误	周浩麟
41	杨晴	05/29/2021	指出lab05解答中的错误	周浩麟
42	唐鹏	05/29/2021	指出lab10解答中的错误	周浩麟
43	李泽楠	05/31/2021	指出lab00编译中的错误	周浩麟

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