Algorithm and Complexity (2021) Class Website
Response.Write("");

 

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
Back to Top     
操作提示信息:    权限不足,请检查是否登录

课堂时间 (Course Schedule)

Back to Top

计划日程 (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

Back to Top

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

Lecture 0: Preliminary

Lecture 1: Algorithm Analysis

Lecture 2: Divide and Conquer

Lecture 3: Sorting Network

Lecture 4: Greedy Strategy

Lecture 5: Matroid

Lecture 6: Dynamic Programming

Lecture 7: Linear Programming

Lecture 8: Amortized Analysis

Lecture 9: Graph Exploration

Lecture 10: Shortest Path

Lecture 11: Network Flow

Lecture 12: Turing Machine

Lecture 13: NP and Reduction

Lecture 14: Final Exam

Back to Top

提交引导 (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.
Back to Top

分组活动说明 (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 Demo

分组活动细节 (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
Back to Top

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

Back to Top

光荣榜 (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编译中的错误 周浩麟
Back to Top

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