Algorithm and Complexity (2019)

基本信息 (General Information)

Level: Undergraduate

Time & Place: 10:00 – 11:40, Monday & 16:00 – 17:40, Thursday, Dong Zhong Yuan 4-401 (东中院4-401)

Instructor:

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

Teaching Assistant:

Name: Jiahao Fan (范佳豪)
Email: nathan1108@163.com
Office: SEIEE 3-309
Phone: 13962245020
Office Hour: 19:00 - 21:00, Monday

Name: Mingran Peng (彭铭燃)
Email: Mickeypeng@sjtu.edu.cn
Office: SEIEE 3-129
Phone: 13818643767
Office Hour: 19:00 - 21:00, Thursday

课堂时间 (Course Schedule)

计划日程 (Syllabus)

Week	Date	Lecture Topic	Event	TA
1	Feb.25	Algorithm Design and Analysis Sorting Algorithm, Time Complexity, Space Complexity, etc.		彭铭燃
1	Feb.28	Amortized Analysis Aggregate Analysis, Accounting Method, Potential Method, Dynamic Table, etc.	Lab-01	彭铭燃
2	Mar.04	Divide-and-Conquer (1) Mergesort, Selection, Master’s Theorem, etc.		范佳豪
2	Mar.07	Divide-and-Conquer (2) Sorting Network, etc.	Lab-02	范佳豪
3	Mar.11	Greedy Approach (1) Interval Scheduling, Interval Partitioning, Minimum Lateness, etc.		彭铭燃
3	Mar.14	Greedy Approach (2) Matroid, Greedy-Max Algorithm, etc.	Lab-03	彭铭燃
4	Mar.18	Dynamic Programming (1) Weighted Interval Scheduling, Segmented Least Squares, Knapsack, etc.		范佳豪
4	Mar.21	Dynamic Programming (2) RNA Secondary Structure, Sequence Alignment, etc.	Lab-04	范佳豪
5	Mar.25	Linear Programming Basic Form, Duality Theory, Simplex Algorithm, etc.	Lab-05	范佳豪
6	Apr.04	Midterm Exam	Midterm
7	Apr.08	Graph Algorithms (1) Basic Concepts, Minimum Spanning Tree, Searching and Exploration, etc.		彭铭燃
7	Apr.11	Graph Algorithms (2) Single Source Shortest Paths (Greedy & DP), etc.	Lab-06	彭铭燃
8	Apr.15	Graph Algorithms (3) All-Pair Shortest Paths, Flow Problem, etc.		彭铭燃
8	Apr.18	Graph Algorithms (4) Maximum Flow, Minimum Cut, etc.	Lab-07	彭铭燃
9	Apr.22	Turing Machine Computability, Turing Machine, etc.		范佳豪
9	Apr.25	NP-Completeness (1) NP class, Polynomial time, etc.		范佳豪
10	Apr.28	NP-Completeness (2) Reducibility, Proofs, etc.		彭铭燃
10	Apr.29	NP-Completeness (3) Reducibility, Proofs, etc.	Lab-08	彭铭燃
11	May.6	Approximation (1) Approximation Ratio, Approximation Class, etc.		范佳豪
11	May.9	Approximation (2) Greedy Algorithm, Local Search, etc.	Lab-09	范佳豪
12	May.13	Approximation (3) LP+Rounding (Deterministic & Randomized), etc.		彭铭燃
12	May.16	Randomized Algorithm (1) Max-3SAT Approximation, Universal Hashing, etc.	Lab-10	彭铭燃
13	May.20	Randomized Algorithm (2) Load Balancing, Exercises, etc.		范佳豪
13	May.23	Online Algorithm Competitive Ratio, Online Packing-Covering Framework, Basic Algorithms, etc.		范佳豪

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

Lecture 0: Preliminary

Reading Materials

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

Lab 0: Proof (Due: 10:00, 02/25/2019)

Complete self-introduction (top-right button)
Learn pseudocode from Wikipedia
Lab00-Proof: Lab00-Proof.pdf
LaTeX Source of Lab00: Lab00-Proof.tex
Lab00-Solution: Lab00-Solution.pdf
Best Labs: Lab00-WeiqiFeng.pdf, Lab00-YitianMa.pdf, Lab00-YuhaoLu.pdf.

Lecture 1: Algorithm Analysis

Reading Materials

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

Lecture 2 : Amortized Analysis

Reading Materials

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

Lab 1: Algorithm Analysis (Due: 16:00, 03/07/2019)

Lab01-AlgorithmAnalysis: Lab01-AlgorithmAnalysis.pdf
LaTeX Source of Lab01: Lab01-AlgorihtmAnalysis.tex
Lab01-Solution: Lab01-Solution.pdf (release at 22:00)
Best Labs: Lab01-WeiqiFeng.pdf, Lab01-GuofengYang.pdf, Lab01-BinghaoChen.pdf.

Lecture 3: Divide and Conquer

Reading Materials

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

Lecture 4: 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.py

Lab 2: Divide and Conquer (Due: 16:00, 03/14/2019)

Lab02-DivideConquer: Lab02-DivideConquer.pdf
LaTeX Source of Lab02: Lab02-DivideConquer.tex
Figure Source: Fig-Transposition.pdf
Code Source: Code-Pairs.cpp
Submission Requirements: SubmissionRequirements.pdf
Lab02-Solution: Lab02-Solution.pdf
Best Labs: Lab02-TianyaoShi.pdf, Lab02-YanhengWang.pdf, Lab02-YitianMa.pdf.

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

Lecture 6: 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);
* 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 3: Greedy Strategy (Due: 16:00, 03/21/2018)

Lab03-GreedyStrategy: Lab03-GreedyStrategy.pdf
LaTeX Source of Lab03: Lab03-GreedyStrategy.tex
Lab03-Solution: Lab03-Solution.pdf
Best Labs: Lab03-Yitian Ma.pdf, Lab03-Yunjia Xi.pdf, Lab03-Xiangyu Liu.pdf.

Lecture 7: Dynamic Programming

Reading Materials

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

Lab 4: Dynamic Programming (Due: 16:00, 03/28/2019)

Lab04-DynamicProgramming: Lab04-DynamicProgramming.pdf
LaTeX Source of Lab04: Lab04-DynamicProgramming.tex
Code Source: Code-SequenceAlignment.cpp
Lab04-Solution: Lab04-Solution.pdf
Best Labs: Lab04-BowenZhang.pdf, Lab04-YuWu.pdf, Lab04-ChenzhengyiLiu.pdf.

Lecture 8: Linear Programming

Reading Materials

Slide: Slide09-LinearProgramming.pdf (Print Version: 09-Linear Programming.pdf)
Reference:
* Reference11-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.
* Reference12-SimplexAlgorithm.pdf Chapter 29.3 in "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition).

CPLEX Tutorial

Get CPLEX from IBM ILOG CPLEX Optimization Studio
Get official documentation from IBM Knowledge Center
CPLEX Tutorial: CPLEXTutorial.pdf

Lab 5: Linear Programming (Due: 10:00, 04/01/2019)

Lab05-LinearProgramming: Lab05-LinearProgramming.pdf
LaTeX Source of Lab05: Lab05-LinearProgramming.tex
Lab05-Solution: Lab05-Solution.pdf
Best Labs: Lab05-GuohangLiu.pdf, Lab05-WeitongOu.pdf, Lab05-KounianhuaDu.pdf.

Lecture 9: 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: Reference13-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

Lab 6: Graph Exploration (Due: 16:00, 04/18/2019)

Lab06-GraphExploration: Lab06-GraphExploration.pdf
LaTeX Source of Lab06: Lab06-GraphExploration.tex
Code Source: Code-SCC.cpp
Graph Information: scc.in
Lab06-Solution: Lab06-Solution.pdf
Best Labs: Lab06-XinranChen.pdf, Lab06-WeiqiFeng.pdf, Lab06-GuohangLiu.pdf.
Best Visualization:

- Chang Liu
- Xinran Chen
- Tianrui Kong
- Hongzhou Liu
- Jiaqi Zeng
- LongXiang Liu

Lecture 10: Shortest Path

Reading Materials

Slide: Slide12-ShortestPath.pdf (Print Version: 12-ShortestPath.pdf)
Reference:
* Reference14-ShortestPath.pdf Chapter 24 in "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition);
* Reference15-ShortestPathDP.pdf Chapter 6.8, 6.10 in "Algorithm Design" by J. Kleinberg, and E. Tardos, Pearson-Addison Wesley, 2005;
* Reference16-AllPairShortestPath.pdf Chapter 25 in "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition).

Lecture 11: NetworkFlow

Reading Materials

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

Lab 7: Network Flow (Due: 16:00, 04/25/2019)

Lab07-NetworkFlow: Lab07-NetworkFlow.pdf
LaTeX Source of Lab07: Lab07-NetworkFlow.tex
Lab07-Solution: Lab07-Solution.pdf
Best Labs: Lab07-YangchenXiao.pdf, Lab07-YanhengWang.pdf, Lab07-YitianMa.pdf.

Final Exam Date: https://www.wjx.cn/jq/38025587.aspx (Close on 20:00, 04/21/2019). The most voted date will become the final exam date. Not vote means you are ok for every choice.

Lecture 12: Turing Machine

Reading Materials

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

Lecture 13: NP and Reduction

Reading Materials

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

Microsoft Visio Tutorials

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

Lab 8: Computational Complexity (Due: 16:00, 05/09/2019)

Lab08-ComputationalComplexity: Lab08-ComputationalComplexity.pdf
LaTeX Source of Lab08: Lab08-ComputationalComplexity.tex
Lab08-Solution: Lab08-Solution.pdf
Best Labs: Lab08-ChenxiaoYang.pdf, Lab08-BowenZhang.pdf, Lab08-BinghaoChen.pdf.

Lecture 14: Approximation Algorithm I

Reading Materials

Slide: Slide16-ApproximationI.pdf (Print Version: 16-ApproximationI.pdf)
Reference: Reference20-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 9: Approximation Algorithm (Due: 16:00, 05/16/2019)

Lab09-ApproximationAlgorithm: Lab09-ApproximationAlgorithm.pdf
LaTeX Source of Lab09: Lab09-ApproximationAlgorithm.tex
Lab09-Solution: Lab09-Solution.pdf
Best Labs: Lab09-GuohangLiu.pdf, Lab09-BowenZhang.pdf, Lab09-SiqiShao.pdf.

Lecture 15: Approximation Algorithm II

Reading Materials

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

Lecture 16: Randomized Algorithm

Reading Materials

Slide: Slide18-RandomizedAlgorithm.pdf (Print Version: 18-RandomizedAlgorithm.pdf)
References:
* Lecture 19 of CS 38: Introduction to Algorithms by Chris Umans, California Institute of Technology;
* CPSC 536N: Randomized Algorithms by Nicholas Harvey, University of British Columbia;
* CSE525: Randomized Algorithms and Probabilistic Analysis by James R. Lee, University of Washington.

Lab 10: Approximation & RandomizedAlgorithm (Due: 16:00, 05/27/2019)

Lab10-Approximation&RandomizedAlgorithm: Lab10-Approximation&RandomizedAlgorithm.pdf
LaTeX Source of Lab09: Lab10-Approximation&RandomizedAlgorithm.tex
Lab10-Solution: Lab10-Solution.pdf
Best Labs: Lab10-YuhaoLu.pdf, Lab10-YunhaoZhang.pdf, Lab10-JianweiZhang.pdf.

Lecture 17: Online Algorithm

Reading Materials

Slide: Slide19-OnlineAlgorithm.pdf (Print Version: 19-OnlineAlgorithm.pdf)
References: CS369: Topics in Analysis of Algorithms by Serge Plotkin, Stanford University.

提交引导 (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-PackageDelivery: Project01-PackageDelivery.pdf
- Project01-Data: Project01-Data.zip
- Project02-SupplyChain: Project02-SupplyChain.pdf
- Project02-Data: Project02-Data.zip
- Project03-TourRecommendation: Project03-TourRecommendation.pdf
- Project03-Data: Project03-Data.zip
Related Documents
- Project-BidRule (English): Project-BidRule (English).pdf
- Project-BidRule (Chinese): Project-BidRule (Chinese).pdf
- Bidding Entrance: https://www.wjx.top/jq/37485305.aspx
- (Close at 20:00, 04/14/2019)
- Report Template: Project-Template.zip

分组活动细节 (Group Project Detail)

序号 (No.)	队名 (Team Name)	队员一 (Member 1)	队员二 (Member 2)	队员三 (Member 3)	题目 (Project)
1	在线求组名	李桐	汪佳卉	卢肇	Project01-PackageDelivery
2	车友会	陈麒麟	丁方玉	刘宏洲	Project01-PackageDelivery
3	Day Day Up	符殊源	陈欣然	李京星	Project02-SupplyChain
4	空白对照组	邵昱铭	朱睿	丁榕	Project01-PackageDelivery
5	SandSculpture	李垚暄	吴匡锦	史天尧	Project02-SupplyChain
6	Cane Corso	马意湉	万芯蔚	郭雪菲	Project03-TourRecommendation
7	占座三人组	付昊源	冯伟琪	赵屹然	Project02-SupplyChain
8	代码敲不队	王鑫凯	何山	宋清莹	Project03-TourRecommendation
9	大三元	李荣强	卢淑文	詹云帆	Project03-TourRecommendation
10	ProMonkeys	聂良旭	李泓録	张米志鹏	Project01-PackageDelivery
11	Trible Bloom	刘畅畅	倪睿杰	王鹤翔	Project02-SupplyChain
12	Amadeus	陈屹扬	杨子腾	杨国峰	Project02-SupplyChain
13	all_accepted	杨宝琛	张昀浩	秦思远	Project01-PackageDelivery
14	RLC Oscillation	罗嘉鸣	陈鸣阳	吴捷健	Project02-SupplyChain
15	0Error	李岩松	张博文	刘相宇	Project01-PackageDelivery
16	白给	陆昱昊	王彦恒	张嘉羽	Project02-SupplyChain
17	BAD GANG	刘国航	刘陈正轶	张宇澄	Project03-TourRecommendation
18	Navigator	宦旭	杨晨晓	曾嘉祺	Project03-TourRecommendation
19	梅西他哥领衔	宣朱佐肯	尹吉	石家诚	Project01-PackageDelivery
20	bald girls	欧阳煜	高若彤	吴雨	Project03-TourRecommendation
21	Curious Cobb	孔天睿	戴诚杰	田雪飞	Project03-TourRecommendation
22	Mediterranean	岑鑫鑫	张健伟	王子霄	Project02-SupplyChain
23	ghost in the shell	刘畅	陈炳昊	刘伟	Project03-TourRecommendation
24	drop table group;	王俊杰	严谊凯	覃文韬	Project01-PackageDelivery
25	Schrodinger's Cats	徐博闻	陈奕廷	程云龙	Project02-SupplyChain
26	BetaCat	季元彦	宋昱龙	程嘉淦	Project03-TourRecommendation
27	O(1)	丁雨成	杜蔻年华	张佳乐	Project01-PackageDelivery
28	blur	西云佳	欧伟彤	邵斯绮	Project02-SupplyChain
29	憂鬱的臺灣烏龜	严铖	李熠阳	刘龙祥	Project03-TourRecommendation
30	random	闫鸿宇	蔡静怡	魏熙锴	Project01-PackageDelivery

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

Roster

Class Attendance Pictures

History Roster

光荣榜 (Honor Roll)

序号 (Number)	姓名 (Name)	加分时间 (Time)	加分原因 (Reason)	加分人 (Recorder)
1	刘畅畅	2019-02-28	指正PPT错误（Slide03）	范佳豪
2	王彦恒	2019-03-02	指正Lab01错误	彭铭燃
3	吴捷健	2019-03-02	指正PPT错误（Slide03）	范佳豪
4	冯伟琪	2019-03-02	Best Labs (Lab00)	范佳豪
5	马意湉	2019-03-02	Best Labs (Lab00)	范佳豪
6	陆昱昊	2019-03-02	Best Labs (Lab00)	范佳豪
7	冯伟琪	2019-03-06	指正PPT错误（Slide04）	范佳豪
8	冯伟琪	2019-03-14	Best Labs (Lab01)	彭铭燃
9	陈炳昊	2019-03-14	Best Labs (Lab01)	彭铭燃
10	杨国峰	2019-03-14	Best Labs (Lab01)	彭铭燃
11	史天尧	2019-03-17	Best Labs (Lab02)	范佳豪
12	王彦恒	2019-03-17	Best Labs (Lab02)	范佳豪
13	马意湉	2019-03-17	Best Labs (Lab02)	范佳豪
14	丁榕	2019-03-17	Matroid课堂演示	范佳豪
15	马意湉	2019-03-27	Best Labs (Lab03)	彭铭燃
16	刘相宇	2019-03-27	Best Labs (Lab03)	彭铭燃
17	西云佳	2019-03-27	Best Labs (Lab03)	彭铭燃
18	张博文	2019-04-01	Best Labs (Lab04)	范佳豪
19	吴雨	2019-04-01	Best Labs (Lab04)	范佳豪
20	刘陈正轶	2019-04-01	Best Labs (Lab04)	范佳豪
21	刘国航	2019-04-03	Best Labs (Lab05)	范佳豪
22	欧伟彤	2019-04-03	Best Labs (Lab05)	范佳豪
23	杜蔻年华	2019-04-03	Best Labs (Lab05)	范佳豪
24	季元彦	2019-04-08	Graph Exploration课堂演示	范佳豪
25	宦旭	2019-04-17	指正PPT错误（Slide08）	彭铭燃
26	陈炳昊	2019-04-17	指正PPT错误（Slide12）	彭铭燃
27	邵昱铭	2019-04-29	NP and Reduction课堂演示	范佳豪
28	陈麒麟	2019-04-29	Turing Machine课堂演示	范佳豪
29	李桐	2019-04-29	Turing Machine课堂演示	范佳豪
30	陈欣然	2019-05-24	Best Labs (Lab06)	彭铭燃
31	冯伟琪	2019-05-24	Best Labs (Lab06)	彭铭燃
32	刘国航	2019-05-24	Best Labs (Lab06)	彭铭燃
33	杨晨晓	2019-05-24	Best Labs (Lab07)	彭铭燃
34	王彦恒	2019-05-24	Best Labs (Lab07)	彭铭燃
35	马意湉	2019-05-24	Best Labs (Lab07)	彭铭燃
36	杨晨晓	2019-05-24	Best Labs (Lab08)	彭铭燃
37	张博文	2019-05-24	Best Labs (Lab08)	彭铭燃
38	陈炳昊	2019-05-24	Best Labs (Lab08)	彭铭燃
39	刘国航	2019-05-24	Best Labs (Lab09)	范佳豪
40	张博文	2019-05-24	Best Labs (Lab09)	范佳豪
41	邵斯绮	2019-05-24	Best Labs (Lab09)	范佳豪
42	陆昱昊	2019-06-24	Best Labs (Lab10)	彭铭燃
43	张昀浩	2019-06-24	Best Labs (Lab10)	彭铭燃
44	张健伟	2019-06-24	Best Labs (Lab10)	彭铭燃

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