Algorithm Design and Analysis (2020) Class Website
Response.Write("");

 

Algorithm Design and Analysis (2020)


权限不足,请检查是否登录

基本信息 (General Information)

Level: Graduate
Time & Place: 10:00 – 11:40, Wednesday & Friday; Dong Zhong Yuan 2-106 (东中院 2-106)
Instructor:
  • Name: Xiaofeng Gao
  • Email: gao-xf(at)cs.sjtu.edu.cn
  • Office: Telecom Building 3-543
  • Phone: 021-34207407
Teaching Assistant:
  • Name: Runbo Ni (倪润博)
  • Email: 1098877273@qq.com
  • Office: SEIEE 3-328
  • Phone: 15821175671
  • Office Hour: 20:00 - 22:00, Thursday
  • Name: Jiadong Chen (陈家栋)
  • Email: chenjiadong998@sjtu.edu.cn
  • Office: SEIEE 3-328
  • Phone: 13262526383
  • Office Hour: 20:00 - 22:00, Wednesday
Back to Top     
操作提示信息:    权限不足,请检查是否登录

课堂时间 (Course Schedule)

Back to Top

计划日程 (Syllabus)

Week

Date

Lecture Topic

Event

TA

1

Sept. 09

Course Introduction

Introduction of This Class, Basic Concepts, Proof, etc.

Chen

1

Sept. 11

Complexity

Time / Space Complexity, Algorithm analysis, etc

Lab01

Chen

2

Sept. 18

Sorting and Searching

Sorting, Searching, and Selection.

Chen

3

Sept. 23

Divide-and-Conquer

Mergesort, Selection, Master’s Theorem, etc.

Lab02

Chen

3

Sept. 25

Greedy Approach (1)

Interval Scheduling, Interval Partitioning, Minimum Lateness, etc.

Chen

4

Sept. 30

Greedy Approach (2)

More Examples on Greedy Approach, etc.

Lab03

Ni

4

Oct. 02

National Holiday

5

Oct. 07

National Holiday

5

Oct. 09

Greedy Approach (3) + Dynamic Programming (1)

More Examples on Greedy Approach, Basic Dynamic Programming, etc.

Chen

6

Oct.14

Dynamic Programming (2)

Weighted Interval Scheduling, Segmented Least Squares, Knapsack, etc.

Lab04

Ni

6

Oct.16

Graph Algorithms (1)

Graph basic, Minimum Spanning Tree, Searching and Exploration, etc.

Chen

7

Oct. 21

Graph Algorithms (2)

Single Source Shortest Paths (Greedy & DP), All-Pair Shortest Paths, etc.

Lab05

Ni

7

Oct. 23

Graph Algorithms (3)

Flow Problem, Maximum Flow, Minimum Cut, etc.

Chen

8

Oct. 28

NP-Completeness (1)

Turing Machine, Computable & Decidable, etc.

Lab06

Ni

8

Oct. 30

NP-Completeness (2)

NP class, Polynomial time, Reducibility, Proofs, etc.

Ni

9

Nov. 4

Approximation (1)

Approximation Ratio, Approximation Class, etc.

Lab07

Ni

9

Nov. 6

Approximation (2)

Greedy Algorithm, Local Search, etc.

Ni

12

Nov. 25

Final exam

Back to Top

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

Lecture 0: Preliminary

Lecture 1: Algorithm Analysis

Lecture 2: Divide and Conquer

Lecture 3: Greedy Strategy

Lecture 4: Dynamic Programming

Lecture 5: Graph Exploration

Lecture 6: Shortest Path

Lecture 7: Network Flow

Lecture 8: NP Complexity

Lecture 9: Approximation Algorithm

Final Exam

    • Final Exam Information

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)

  • Grouping
    • Projects should be done in teams of 3 (3 and 3 only).  
    • Students who have enrolled in this course should make up their team and submit the team information on the homepage by 10 am 09/23/2020. Enrolled students who have not submitted their team information by the deadline will be partitioned into random groups.  
    • Unregistered students should make their team only with unregistered students if they wish to participate in the course project.  
  • Project Description
    • Project-Data-AnalyticJobScheduling:   Project-Data-AnalyticJobScheduling.pdf
    • Project Report Submission Deadline: 23:59, 12/18/2020 (including all sources and data) 
    • Project Demo Schedule: 12/19/2020  
  • Related Document

分组活动细节 (Group Project Detail)

序号
(No.)
队名
(Team Name)
队员 一
(Member 1)
队员 二
(Member 2)
队员 三
(Member 3)
题目
(Project)
时间
(Time)
1 很有精神 何云帆 王子豪 章润廷 电院3-404 15:15-15:30
2 54749110 程章 刘学渊 李兴 电院3-414 14:30-14:45
3 虎保健 袁健 冯二虎 何保祥 电院3-414 13:45-14:00
4 三人行 李奇之 简相永 吕相龙 电院3-414 16:45-17:00
5 🐂🍺 黄俊钦 侍硕 杨培灏 电院3-414 13:30-13:45
6 梦韵庄 蔚梦航 庄严 郑韵锴 电院3-414 16:15-16:30
7 RXP 潘达汉 任雨阳 徐奕 电院3-404 13:30-13:45
8 奥力给 黎楚萱 柴纶 贺昊 电院3-404 15:00:15:15
9 污渍永远滴神 刘思辰 李明泽 黄晟原 电院3-414 16:00-16:15
10 扫地僧 花一帆 冯传恒 张志龙 电院3-404 16:15-16:30
11 做大做强 胡浩颐 陈仁杰 陈家栋 电院3-414 14:00-14:15
12 Turing-Church 王鸿蒙 李子通 田子申 电院3-414 17:15-17:30
13 回到起点 冯思远 王翰竟 冯冬辉 电院3-414 15:00:15:15
14 长风破浪 缪新元 李博闻 袁诗景 电院3-414 17:45-18:00
15 大佬求带 刘洪铭 尹远航 陈运忠 电院3-414 14:45-15:00
16 鱼鱼鱼 俞经纬 涂彦伦 谢瑜璋 电院3-404 17:15-17:30
17 算法真难 栾广强 魏豪 张舒来 电院3-404 13:45-14:00
18 楼上隔壁老王 王旭航 雷佳乐 孔芮 电院3-414 17:00-17:15
19 /remake 苏星宇 鲁瑞明 景梦圆 电院3-404 17:45-18:00
20 真不错 王欣宇 周云松 韩冰 电院3-404 17:30-17:45
21 阿果拉 胡飘 刘宽 王昭博 电院3-414 16:30-16:45
22 开心就好对不队 阚诺文 曹迈达 顾扬 电院3-404 16:45-17:00
23 长风破浪的师弟师妹们 孙嘉伟 鲁新钰 曾益 电院3-404 16:00-16:15
24 正常合理 沈逸飞 张倬胜 周子祎 电院3-414 17:30-17:45
25 思算巧法 黄高昂 梁爽 邓雨昂 电院3-404 17:00-17:15
26 隐藏的第四人 李雪嫣 郭政一 崔玉芳 电院3-414 14:15-14:30
27 不想做project 贾冉昊 王靖楠 郭萌涵 电院3-404 14:15-14:30
28 你的名字 赵义成 凌家曜 马悦 电院3-404 14:45-15:00
29 PSG 周浩麟 魏天天 易沐阳 电院3-404 14:00-14:15
30 彼得罗巴甫洛夫斯克 郑承宇 张剑清 罗统億 电院3-404 14:30-14:45
31 想个名字 奚彧 孙泽堃 王师溟 电院3-414 15:15-15:30
32 LastNotLeast 林耘丰 陈鹭 李姚 电院3-404 18:00-18:15
33 O(1) 刘尚育 邢睿 李泱丞 电院3-404 16:30-16:45
Back to Top

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

Back to Top

光荣榜 (Honor Roll)

序号
(Number)
姓名
(Name)
加分时间
(Time)
加分原因
(Reason)
加分人
(Recorder)
1 黄晟原 2020/09/25 Best Lab for Lab01 倪润博
2 周浩麟 2020/09/25 Best Lab for Lab01 倪润博
3 吕相龙 2020/09/25 Best Lab for Lab01 倪润博
4 刘思辰 2020/09/25 Shared the calculation of quick sort algorithm's average complexity with linearity of expection 倪润博
5 刘尚育 2020/09/25 Corrected the value of "pair" in the derivation of time complexity of merge sort on the blackboard 倪润博
6 易沐阳 2020/10/19 Best Lab for Lab02 倪润博
7 吕相龙 2020/10/19 Best Lab for Lab02 倪润博
8 吕胜炜 2020/10/19 Best Lab for Lab03 倪润博
9 陈仁杰 2020/10/19 Best Lab for Lab03 倪润博
10 王欣宇 2020/10/19 Best Lab for Lab03 倪润博
11 胡浩颐 2020/10/19 Best Lab for Lab03 倪润博
12 李明泽 2020/10/27 Best Lab for Lab04 陈家栋
13 郑韵锴 2020/10/27 Best Lab for Lab04 陈家栋
14 刘尚育 2020/10/27 Best Lab for Lab04 陈家栋
15 鲁瑞明 2020/10/30 Best Lab for Lab05 倪润博
16 曾益 2020/10/30 Best Lab for Lab05 倪润博
17 刘学渊 2020/10/30 Best Lab for Lab05 倪润博
18 刘学渊 2020/11/08 Best Lab for Lab06 陈家栋
19 黄俊钦 2020/11/08 Best Lab for Lab06 陈家栋
20 刘尚育 2020/11/08 Best Lab for Lab06 陈家栋
21 刘学渊 2020/11/17 Best Lab for Lab07 倪润博
22 曾益 2020/11/17 Best Lab for Lab07 倪润博
23 贾冉昊 2020/11/17 Best Lab for Lab07 倪润博
24 王欣宇 2020/11/17 Best Lab for Lab07 倪润博
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