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

 

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

课堂时间 (Course Schedule)

Back to Top

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

范佳豪

Back to Top

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

Lecture 0: Preliminary

Lecture 1: Algorithm Analysis

Lecture 2 : Amortized Analysis

Lecture 3: Divide and Conquer

Lecture 4: Sorting Network

Lecture 5: Greedy Strategy

Lecture 6: Matroid

Lecture 7: Dynamic Programming

Lecture 8: Linear Programming

Lecture 9: Graph Exploration

Lecture 10: Shortest Path

Lecture 11: NetworkFlow

Lecture 12: Turing Machine

Lecture 13: NP and Reduction

Lecture 14: Approximation Algorithm I

Lecture 15: Approximation Algorithm II

Lecture 16: Randomized Algorithm

Lecture 17: Online Algorithm

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)

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

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

Back to Top

光荣榜 (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) 彭铭燃
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