Algorithm and Complexity (2022) Class Website

 

Algorithm and Complexity (2022)

基本信息 (General Information)

Level: Undergraduate
Time & Place: 10:00 am - 12:45 pm, Wednesday, Shang Yuan 107 (上院107)
Instructor:
  • Name: Xiaofeng Gao
  • Email: gao-xf(at)cs.sjtu.edu.cn
  • Office: Telecom Building 3-543
  • Phone: 021-34207407
Teaching Assistant:
  • Name: Wanghua Shi (石望华)
  • Email: s-whua@sjtu.edu.cn
  • Office: SEIEE 3-239
  • Phone: 15918404969
  • Office Hour: 20:00 - 22:00, Friday
  • Name: Hongjie Fang (方泓杰)
  • Email: galaxies@sjtu.edu.cn
  • Office: Online
  • Phone: 18259025398
  • Office Hour: 20:00 - 22:00, Friday
  • Name: Jialin Lyu (吕佳霖)
  • Email: 1349105776@qq.com
  • Office: Online
  • Phone: 19821917048
  • Office Hour: 20:00 - 22:00, Friday
Back to Top 　　　　

课堂时间 (Course Schedule)

Back to Top

计划日程 (Syllabus)

Week

Date

Lecture Topic

Event

TA

1

Feb. 16

Course Introduction and Preliminary

Introduction of This Class, Basic Concepts, Time / Space Complexity, etc.

H. Fang

2

Feb. 23

Algorithm Design and Analysis

Computation and Complexity, Sorting, Searching, and Selection.

Lab-01

W. Shi

3

Mar. 2

Divide-and-Conquer

Mergesort, Selection, Master’s Theorem, Sorting Network, Zero-One Principle, etc.

H. Fang

4

Mar. 9

Greedy Approach (1)

Interval Scheduling, Interval Partitioning, Minimum Lateness, etc.

Lab-02

W. Shi

5

Mar. 16

Greedy Approach (2)

Optimal Caching, Coin Charging, etc.

H. Fang

6

Mar. 23

Matroid (1)

Independent System, Matroid, Example: Greedy-Max Algorithm, etc.

Lab-03

H. Fang

7

Mar. 30

Matroid (2)

Min-Max Conversion, Unit-Time Interval Scheduling, etc.

W. Shi

8

Apr. 6

Dynamic Programming (1)

Weighted Interval Scheduling, RNA Secondary Structure, etc.

Project

W. Shi

9

Apr. 13

Dynamic Programming (2) & Linear Programming

String Similarity, Duality Theory, Simplex Algorithm, etc.

Lab-04

H. Fang

10

Apr. 20

Amortized Analysis

Aggregate Analysis, Accounting Method, Potential Method, etc.

J. Lv

11

Apr. 27

Graph Algorithms (1)

Basic Concepts, MST, DFS, BFS, etc.

Lab-05

J. Lv

12

May. 4

International Workers' Holiday

13

May. 11

Graph Algorithms (2)

SSSP (Greedy & DP), All-Pair Shortest Paths, Flow Problem, etc.

H. Fang

14

May. 18

Graph Algorithms (3) & NP-Completeness (1)

Maximum Flow, Minimum Cut, P and NP class, etc.

H. Fang

15

May. 25

NP-Completeness (2)

Reduction, Proofs.

Lab-06

J. Lv

16

Jun. 1

NP-Completeness (3)

Reduction Examples.

H. Fang

Back to Top

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

Lecture 0: Preliminary

Lecture 1: Algorithm Analysis

Lecture 2: Divide and Conquer

Lecture 3: Greedy Strategy

Lecture 4: Programming

Lecture 5: Amortized Analysis

Lecture 6: Graph Algorithm

Lecture 7: NP and Reduction

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 11:59pm 03/09/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
  • Project Demo
    • Time: 9:30am-11:30am, 05/29/2022 
    • Fang's Tecent Meeting Room: 928-181-770; Psd: 230829  
    • Lyu's Tecent Meeting Room: 871-320-280; Psd: 381349  

分组活动细节 (Group Project Detail)

序号
(No.)		 队名
(Team Name)		 队员 一
(Member 1)		 队员 二
(Member 2)		 队员 三
(Member 3)		 助教
(TA)		 时间
(Time)
1 啊对对队 肖真然 叶梓淳 龙马彪 Fang 09:30-09:45
2 双王流 刘立伟 王虹霖 王梓先 Lyu 09:30-09:45
3 做的全队 刘楷 黄正翔 单榕 Fang 09:45-10:00
4 这个做的队 张忠睿 张真 张昊琰 Lyu 09:45-10:00
5 算法小分队1 姚一航 裴禹乔 沈嘉路 Fang 10:00-10:15
6 跟算法做队 张伟伦 李知恒 张兆祥 Lyu 10:00-10:15
7 苟全性命于乱世 周迅 李腾 夏贤贤 Fang 10:15-10:30
8 啥队 薛雨滢 苏畅 陈彦宁 Lyu 10:15-10:30
9 对不队 郭潇 高然 赵智游 Fang 10:30-10:45
10 swag bad 闫泉林 卫雨禾 甘梓言 Lyu 10:30-10:45
11 算法小分队2 杨尚霏 白忱枫 黄霖 Fang 10:45-11:00
12 算法小分队3 邱以中 陳博謙 馮予讀 Lyu 10:45-11:00
13 算法小分队4 金子童 杨宇轩 刘嘉欣 Fang 11:00-11:15
14 算法小分队5 张杰 张露 蒋圩淏 Lyu 11:00-11:15
15 算法小分队6 张曦燃 姚元祺 解金洋 Fang 11:15-11:30
16 算法小分队7 彭乾煜 王凯俊 池天骏 Lyu 11:15-11:30
Back to Top

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


Roster

Class Attendance Pictures

History Roster

Class Project Pictures

Back to Top

光荣榜 (Honor Roll)

序号
(Number)		 姓名
(Name)		 加分时间
(Time)		 加分原因
(Reason)		 加分人
(Recorder)
1 金子童 02/16/2022 课堂书写Minimal Counterexample Principle例题 方泓杰
2 张忠睿 02/16/2022 课堂帮助书写Minimal Counterexample Principle例题 方泓杰
3 张曦然 02/23/2022 课堂上黑板做题目分析算法复杂度（Binary Search） 石望华
4 单榕 02/23/2022 课堂上黑板做题目分析算法复杂度（Linear Search） 石望华
5 刘楷 03/02/2022 课堂上黑板画n=16排序网络 方泓杰
6 王虹霖 03/07/2022 在线上课回答问卷星Quiz1 石望华
7 杨尚霏 03/26/2022 Lab04-Q4 给出了更低复杂度的实现方法 石望华
8 李腾 03/30/2022 在线课堂回答拟阵例题 石望华
9 杨尚霏 04/18/2022 指出作业Lab04-Q3题目中的错误 吕佳霖
10 叶梓淳 04/20/2022 指出作业Lab04-Q1题目中的错误 吕佳霖
11 邱以中 06/20/2022 指出期末考试选择题第9题的错误 吕佳霖
12 杨尚霏 06/20/2022 Lab05作业中正确求解第3题和第4题 吕佳霖
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