Algorithm Design and Analysis (2021) Class Website

 

Algorithm Design and Analysis (2021)

基本信息 (General Information)

Level: Graduate
Time & Place: Time & Place: 10:00 – 11:40, Wednesday & Friday; Dong Shang Yuan 315
Instructor:
  • Name: Xiaofeng Gao
  • Email: gao-xf(at)cs.sjtu.edu.cn
  • Office: Telecom Building 3-543
  • Phone: 021-34207407
Teaching Assistant:
  • Name: Jiadong Chen (陈家栋)
  • Email: chenjiadong998@sjtu.edu.cn
  • Office: SEIEE 3-328
  • Phone: 13262526383
  • Office Hour: 20:00 - 22:00, Wednesday
  • Name: Yue Ma (马悦)
  • Email: ma_yue@sjtu.edu.cn
  • Office: SEIEE 3-328
  • Phone: 18369189801
  • Office Hour: 18:00 - 20:00, Thursday
  • Name: Yangyang Bao (鲍阳阳)
  • Email: byy_sjtu@sjtu.edu.cn
  • Office: Software Building 5208
  • Phone: 15202837706
  • Office Hour: 20:00 - 22:00, Tuesday
  • Name: Wanghua Shi (石望华)
  • Email: s-whua@sjtu.edu.cn
  • Office: SEIEE 3-239
  • Phone: 15918404969
  • Office Hour: 20:00 - 22:00, Friday
  • Name: Zhen Sun (孙振)
  • Email: zhensun@sjtu.edu.cn
  • Office: Micro-Electronics Building 301
  • Phone: 18880978788
  • Office Hour: 20:00 - 22:00, Monday
Back to Top     

课堂时间 (Course Schedule)

Back to Top

计划日程 (Syllabus)

Week

Date

Lecture Topic

Event

TA

1

Sept. 15

Course Introduction

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

Chen

1

Sept. 17

Complexity

Complexity, Algorithm analysis, etc.

Bao

2

Sept. 22

Sorting and Searching

Sorting, Searching, Mergesort, Selection, etc.

Lab01

Ma

2

Sept. 24

Divide-and-Conquer

Multiplication, MergeSort, Master’s Theorem, etc.

Chen

3

Sept. 29

Greedy Approach (1)

Interval Scheduling, Interval Partitioning, Minimum Lateness, etc.

Lab02

Ma

3

Oct. 01

National Holiday

4

Oct. 06

National Holiday

4

Oct. 08

Greedy Approach (2)

More Greedy Example, Counter Examples, etc.

Bao

5

Oct. 13

Dynamic Programming (1)

Basic Dynamic Programming, Weighted Interval Scheduling, etc.

Chen

5

Oct. 15

Dynamic Programming (2)

Segmented Least Squares, Knapsack, RNA Secondary Structure, etc.

Lab03

Ma

6

Oct. 20

Graph Algorithms (1)

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

Bao

6

Oct. 22

Graph Algorithms (2)

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

Chen

7

Oct. 27

Graph Algorithms (3)

Flow Problem, Maximum Flow, Minimum Cut, etc.

Lab04

Ma

7

Oct. 29

Approximation (1)

Approximation Ratio, Approximation Class, etc.

Bao

8

Nov. 03

Approximation (2)

Greedy Algorithm, Local Search, etc.

Chen

8

Nov. 05

Approximation (3)

Randomized Rounding, Online Algorithm, etc.

Chen

Back to Top

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

Lecture 0: Preliminary

Lecture 1: Algorithm Analysis

Lecture 2: Divide and Conquer

Lecture 3: Greedy Algorithm

Lecture 4: Dynamic Programming

Lecture 5: Graph Algorithm

Lecture 6: Approximation Algorithm

Final Exam

    • Final Exam Information

      • Time: Nov. 19, 2021 (Friday) 10:00 am-12:00 am

      • Location: ExamOrganization.xlsx

      • Question types: Problems may include Multiple Choices, True or False, Questions and Answers.

      • Notice: English only, close note, close book, individual test

    • Exam Survey:

      • Please vote for your favorite final exam date in WeChat group (before 14:00, 11/03/2021), otherwise we consider that you accept any of the four selections for final exam.

      • Majority (95%) of the class voted for 11/19/2021.

    • Photo

      • 班级合影

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 members before 10:00am 10/08/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.  
  • Project Description
  • Organization and Deadline
    • Report Submission Deadline: 23:59, 12/11/2021 (including all sources and data)  
    • Potential Demo Day: 12/12/2021 (To Be Decided)  

分组活动细节 (Group Project Detail)

序号
(No.)
队名
(Team Name)
队员 一
(Member 1)
队员 二
(Member 2)
队员 三
(Member 3)
题目
(Project)
时间
(Time)
1 JWW 王锡淮 王欣洲 季炜丹
2 CF 阳展韬 张晗 张萌
3 return_0; 胡澄洋 张志伟 张令
4 ZZL 张昊 罗凯艺 曾博义
5 toonaive 王纪科 唐品 刘博
6 416 陈成 王自睿 王克
7 你要不要吧 孟令统 杨士玄 罗宏宇
8 toosimple 刘海峰 戴杰 邓沛岩
9 三不沾 孔德鋆 闫妍 韩泽北
10 [ 100%] 魏冰心 黄耕酉 赵梓涵
11 CLRS 王凯旋 张少锋 刘昊林
12 你说的都队 余鹏 赵研 刘娜铭
13 NoBug 施宏建 付振洋 王志杰
14 np-easy 冯明泉 吴姝姝 戚振林
15 FatalError 廖兆和 刘伟 杜雨衡
16 不要卷 竺正邦 陈竞潇 马平川
17 X 万芯蔚 周昕逸 汤吉学
18 哒咩哒咩 黄亮猛 蔡讯 吕皓鑫
19 test 何一夫 关威 张逸
20 冰可乐 汤鸿 李文杰 蔡明昕
21 while(1) 张永翔 谭霖峰 田文新
22 TBD 伊康平 李蕴哲 徐帆
23 O(MyGod) 舒子曦 俞子越 柳清源
24 TODO 赵立帆 张炜创 霍达
25 passion 唐健 任为 肖林
26 523 兰焜耀 李春晖 周威
27 取什么名字好呢 王兴宇 钱苏澄 雍耀光
28 占位符 张平越 宦旭 李明杰
29 320 龚勋 万梓煜 杨宁
30 野指针 张锦洋 曹隽逸 许文强
31 O(原来是这样) 胡钊萍 余萌迪 李鼎
32 算法小分队 何志威 吴浩南 燕恒旭
33 青年近卫军 李广鹏 邓喻丰 魏天鹏
34 O(1/n) 李威 亢虎权 陈睿
35 蒙的全队 朱文辉 吴凡 韩昕驰
36 三块腹肌 雷文辉 赵啸威 郑光浩
37 1111111 曹景煜 许峰 张思成
38 汤烫烫 祝志豪 吴俊琪 廖昊然
39 交我算 刘洪瑞 吉斌 王塬夫
40 hithot 张婉茹 惠一锋 沙拉依丁·斯热吉丁
41 测试 陈聪涌 顾家源
42 rm -rf /* 段佳昂 张智超 赵峒
43 你的组名 伍鸿秋 黄世远 段皓铧
Back to Top

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

Back to Top

光荣榜 (Honor Roll)

序号
(Number)
姓名
(Name)
加分时间
(Time)
加分原因
(Reason)
加分人
(Recorder)
1 李文杰 09/24/2021 指出Lab01中的错误 陈家栋
2 王锡淮 10/08/2021 Best Lab for Lab01-AlgorithmAnalysis 陈家栋
3 戚振林 10/08/2021 Best Lab for Lab01-AlgorithmAnalysis 陈家栋
4 万梓煜 10/08/2021 Best Lab for Lab01-AlgorithmAnalysis 陈家栋
5 柳清源 09/29/2021 指出Lab02中的错误 鲍阳阳
6 李明杰 10/21/2021 Best Lab for Lab02-AlgorithmDesign 鲍阳阳
7 冯明泉 10/21/2021 Best Lab for Lab02-AlgorithmDesign 鲍阳阳
8 邓沛岩 10/21/2021 Best Lab for Lab02-AlgorithmDesign 鲍阳阳
9 阳展韬 11/02/2021 Best Lab for Lab03-DynamicProgramming 孙振
10 王自睿 11/02/2021 Best Lab for Lab03-DynamicProgramming 孙振
11 赵研 11/02/2021 Best Lab for Lab03-DynamicProgramming 孙振
12 伊康平 11/02/2021 Best Lab for Lab03-DynamicProgramming 孙振
13 冯明泉 10/29/2021 指出Lab04中的错误 鲍阳阳
14 段佳昂 11/15/2021 Best Lab for Lab04-GraphAlgorithm 鲍阳阳
15 王欣洲 11/15/2021 Best Lab for Lab04-GraphAlgorithm 鲍阳阳
16 杜雨衡 11/15/2021 Best Lab for Lab04-GraphAlgorithm 鲍阳阳
17 余萌迪 11/16/2021 指出Slide03里二分搜索平均复杂性分析的k设置错误 陈家栋
18 冯明泉 11/16/2021 指出Slide12里任务分配里机器选择的错误 陈家栋
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