Algorithm Design and Analysis (2022) Class Website

 

Algorithm Design and Analysis (2022)

基本信息 (General Information)

Level: Graduate
Time & Place: 10:00 – 11:40, Tuesday, Xia Yuan (下院) 106 & 10:00 – 11:40, Thursday, Dong Zhong Yuan (东中院) 2-103
Instructor:
  • Name: Xiaofeng Gao
  • Email: gao-xf(at)cs.sjtu.edu.cn
  • Office: Telecom Building 3-543
  • Phone: 021-34207407
Teaching Assistant:
  • Name: Jiale Zhang (张嘉乐)
  • Email: zhangjiale100@sjtu.edu.cn
  • Office: SEIEE 3-328
  • Phone: 13968002986
  • Office Hour: 20:30 - 22:30, Monday
  • Name: Yang Luo (罗旸)
  • Email: luoyang_sjtu@foxmail.com
  • Office: Online
  • Phone: 13983337297
  • Office Hour: 20:30 - 22:30, Wednesday
Back to Top 　　　　

课堂时间 (Course Schedule)

Back to Top

计划日程 (Syllabus)

Week

Date

Lecture Topic

Event

TA

1

Sept. 13

Course Introduction

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

Zhang

1

Sept. 15

Complexity

Complexity, Algorithm analysis, etc.

Luo

2

Sept. 20

Sorting and Searching (1)

Sorting, Searching, Mergesort, etc.

Lab01

Zhang

2

Sept. 22

Sorting and Searching (2) & Divide-and-Conquer (1)

Selection, Master’s Theorem, etc.

Zhang

3

Sept. 27

Divide-and-Conquer (2) & Greedy Approach (1)

MergeSort, Multiplication, Interval Scheduling, etc.

Luo

3

Sept. 29

Greedy Approach (2)

Interval Partitioning, Minimum Lateness, etc.

Lab02

Luo

4

Oct. 08

Greedy Approach (3) & Online Algorithm

Optimal Caching, Coin Changing, Competitive Ratio, etc.

Luo

4

Oct. 09

Dynamic Programming (1)

Basic Dynamic Programming, etc.

Luo

5

Oct. 11

Dynamic Programming (2)

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

Zhang

5

Oct. 13

Dynamic Programming (3)

RNA Secondary Structure, etc.

Lab03

Zhang

6

Oct. 18

Dynamic Programming (4)

Hirschberg's Alignment Algorithm, etc.

Zhang

6

Oct. 20

Graph Algorithms (1)

Graph Basics, Minimum Spanning Tree, etc.

Luo

7

Oct. 25

Graph Algorithms (2)

Searching and Exploration, Single Source Shortest Paths, etc.

Lab04

Zhang

7

Oct. 27

Graph Algorithms (3)

Single Source Shortest Paths, All-Pair Shortest Paths, etc.

Luo

8

Nov.1

Graph Algorithms (4)

Flow Problem, Maximum Flow, Minimum Cut, etc.

Project

Zhang

8

Nov.3

Advanced Algorithm Design

Approximation Algorithms, Online Algorithms, etc.

Luo

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: Advanced Algorithm Design

Final Exam

    • Final Exam Information

      • Time: Nov. 29, 2022 (Tuesday) 10:00 am-12:00 am

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

    • Exam Survey:

      • Majority (85%) of the class voted for 11/29/2022.

    • 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/2022 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/03/2022 (including a report, all source code and data)  
    • Demo Day: 12/04/2022 9:30am-17:30pm 

分组活动细节 (Group Project Detail)

序号
(No.)		 队名
(Team Name)		 队员 一
(Member 1)		 队员 二
(Member 2)		 队员 三
(Member 3)		 题目
(Project)		 时间
(Time)
1 算法课 叶恒宇 李翰奇 范金庸 Case01 12:20pm-12:40pm
2 TopK 曾宏虹 李茹玥 彭正元 Case02 17:20pm-17:40pm
3 一般路过算法队 薛春宇 李泽浩 殷浩 Case03 10:40am-11:00am
4 Algoreat 李超然 吴昀泽 王元泽 Case04 10:10am-10:40am
5 YYDS 师博雅 郑一凡 武照渊 Case05 09:30am-09:50am
6 迪杰斯特拉认为都AC队 陶新昊 王然 鲁凌霄 Case06 18:00pm-18:20pm
7 126 陈欣祺 鲁昱 王一达 Case07 18:20pm-18:40pm
8 65472 石润晗 唐铄 胡瀚文 Case08 16:40pm-17:00pm
9 红鲤鱼与绿鲤鱼与驴 王维鹏 肖红丽 张力允 Case09 11:00am-11:20am
10 PUZZLE 曾智霖 张宇航 萧诺芊 Case10 11:20am-11:40am
11 对不队 马达 刘洗萌 陈星宇 Case11 09:10am-09:30am
12 Gödel Group 李嘉森 丁榕 王琦 Case12 09:50am-10:10am
13 想不到有意思名字队 张诗璠 王涛 张洗月 Case13 18:40pm-19:00pm
14 奕悟 李嘉鸿 贺知行 林少雄 Case14 11:40am-12:00am
15 第x小队 刘佳雯 英卡尔·波拉提 唐叶辉 Case15 17:40pm-18:00pm
16 ResNet 袁博泰 杨龚轶凡 聂晨 Case16 17:00pm-17:20pm
Back to Top

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


Roster

Class Attendance Pictures

History Roster
Back to Top

光荣榜 (Honor Roll)

序号
(Number)		 姓名
(Name)		 加分时间
(Time)		 加分原因
(Reason)		 加分人
(Recorder)
1 贺知行 9/13/2022 第一节课第一位回答问题"what is algorithm” 张嘉乐
2 李嘉森 9/20/2022 指正Slide03授课中分析二分搜索时间复杂度问题 张嘉乐
3 叶恒宇 9/20/2022 指出Lab01中的错误 张嘉乐
4 张宇航 10/9/2022 课上主动讲解Quiz2的解题思路 罗旸
5 范金庸 10/13/2022 完善Lab03第二题定义范围 罗旸
6 郑一凡 10/25/2022 Best Lab01 张嘉乐
7 鲁昱 10/25/2022 Best Lab01 张嘉乐
8 李茹玥 10/25/2022 Best Lab01 张嘉乐
9 王琦 10/25/2022 指出Shortest Path 课件中Dijkstra拼写问题 张嘉乐
10 贺知行 10/25/2022 指正Lab04第三题例图中有向边问题 张嘉乐
11 李嘉森 10/31/2022 Best Lab02 罗旸
12 吴昀泽 10/31/2022 Best Lab02 罗旸
13 李嘉鸿 10/31/2022 Best Lab02 罗旸
14 林少雄 10/31/2022 Best Lab03 罗旸
15 薛春宇 10/31/2022 Best Lab03 罗旸
16 陶新昊 10/31/202 Best Lab03 罗旸
17 陶新昊 11/06/2022 指出Project中拼车约束定义不够规范的问题 罗旸
18 刘佳雯 11/08/2022 指出Project路径长度计算中符号错误 张嘉乐
19 陶新昊 11/27/2022 Best Lab04 张嘉乐
20 石润晗 11/27/2022 Best Lab04 张嘉乐
21 王琦 11/27/2022 Best Lab04 张嘉乐
22 聂晨 11/28/2022 发现Project中路径距离计算特例 罗旸
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