Algorithm and Complexity (2018) Class Website

 

Algorithm and Complexity (2018)

基本信息 (General Information)

Level: Undergraduate
Time & Place: 16:00 - 17:40, Monday & Thursday, Xia Yuan 213 (下院213)
Instructor:
  • Name: Xiaofeng Gao
  • Email: gao-xf(at)cs.sjtu.edu.cn
  • Office: Telecom Building 3-543
  • Phone: 021-34207407
Teaching Assisstant:
  • Name: Jiahao Fan (范佳豪)
  • Email: nathan1108@163.com
  • Office: SEIEE 3-309
  • Phone: 13962245020
  • Office Hour: 19:00 - 21:00, Monday
  • Name: Xinyu Wu (吴昕宇)
  • Email: wuxinyu@sjtu.edu.cn
  • Office: SEIEE 1-445
  • Phone: 18217266182
  • Office Hour: 19:00 - 21:00, Thursday
Back to Top     

课堂时间 (Course Schedule)

Back to Top

计划日程 (Syllabus)

Week

Date

Lecture Topic

Event

TA

1

Feb.26

Syllabus, Preliminary, Introduction to Algorithm

Schedule, Grading Policy, Preliminary, Pseudo Code, Proof, etc.

1

Mar.01

Algorithm Design and Analysis

Sorting Algorithm, Time Complexity, Space Complexity, etc.

Lab-01

2

Mar.05

Divide-and-Conquer (1)

Mergesort, Selection, Master’s Theorem, etc.

2

Mar.08

Divide-and-Conquer (2)

Sorting Network

Lab-02

3

Mar.12

Greedy Approach (1)

Interval Scheduling, Interval Partitioning, Minimum Lateness, etc.

3

Mar.15

Greedy Approach (2)

Matroid, Greedy-Max Algorithm

Lab-03

4

Mar.19

Dynamic Programming (1)

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

Lab-04

4

Mar.22

Dynamic Programming (2) + Amortized Analysis (1)

RNA Secondary Structure, Sequence Alignment, Aggregate Analysis, etc.

5

Mar.26

Amortized Analysis (2)

Accounting Method, Potential Method, Dynamic Table

Lab-05

5

Mar.29

Linear Programming (1)

Basic Form, Duality Theory, Simplex Algorithm

6

Apr.02

Linear Programming (2) + Course Review

Interior Point Algorithm, Midterm Review, Applications, etc.

Lab-06

6

Apr.05

National Holiday

7

Apr.09

Midterm Exam

Midterm

7

Apr.12

Graph Algorithms (1)

Basic Concepts, Minimum Spanning Tree, Searching and Exploration, etc.

Lab-07

9

Apr.26

Graph Algorithms (2)

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

Lab-08

10

Apr.28

Graph Algorithms (3)

All-Pair Shortest Paths, Flow Problem

10

May.03

Graph Algorithms (4)

Maximum Flow, Minimum Cut, etc

Lab-09

11

May.07

Turing Machine

Computability, Turing Machine, etc.

11

May.10

NP-Completeness (1)

NP class, Polynomial time, etc.

Lab-10

12

May.14

NP-Completeness (2)

Reducibility, Proofs, etc.

12

May.17

Approximation (1)

Approximation Ratio, Approximation Class, Greedy Algorithm, etc.

Lab-11

13

May.21

Approximation (2)

Local Search, LP+Rounding (Deterministic, Randomized)

13

May.24

Randomized Algorithm (1)

Max-3SAT Approximation, Universal Hashing

Lab-12

14

May.28

Randomized Algorithm (2) + Final Review

Load Balancing, Exercises, Review, etc.

Back to Top

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

Lecture 1: Introduction to Algorithm

Lecture 2: Algorithm Analysis

Lecture 3: Divide and Conquer

Lecture 4: Sorting Network

Lecture 5: Greedy Strategy

Lecture 6: Matroid

Lecture 7: Dynamic Programming

Lecture 8: Amortized Analysis

Lecture 9: Linear Programming

Lecture 10: Simplex Algorithm

Lecture 11: Solving Linear Programming in Practice

Lecture 12: Graph Exploration

Lecture 13: Shortest Path

Lecture 14: Network Flow

Lecture 15: Turing Machine

Lecture 16: NP and Reduction

Lecture 17: Approximation Algorithm I

Lecture 18: Approximation Algorithm II

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

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


History Roster

  • Roster-2016 (未开放)
  • Roster-2015 (未开放)
  • Roster-2014 (未开放)
  • Roster-2013 (未开放)
Back to Top

光荣榜 (Honor Roll)

序号
(Number)
姓名
(Name)
加分时间
(Time)
加分原因
(Reason)
加分人
(Recorder)
1 孙雪涵 2018-03-05 指正PPT错误(Slide03) 范佳豪
2 何宇乔 2018-03-08 Sorting Network课堂演示(n=16) 范佳豪
3 周思远 2018-03-08 指正Lab01-Solution错误 吴昕宇
4 闫嘉昆 2018-03-12 上课回答问题(Greedy Strategy) 范佳豪
5 万俊成 2018-03-12 给出Lab01-Q2中Best Case一种合理证明(已上传至Lecture 2下) 吴昕宇
6 陈诧姹 2018-03-16 Lab01-Top 3 Best Homework 吴昕宇
7 查凯文 2018-03-16 Lab01-Top 3 Best Homework 吴昕宇
8 左思成 2018-03-16 Lab01-Top 3 Best Homework 吴昕宇
9 郭洪一 2018-03-16 Lab02-Top 3 Best Homework 范佳豪
10 孙建华 2018-03-16 Lab02-Top 3 Best Homework 范佳豪
11 左思成 2018-03-16 Lab02-Top 3 Best Homework 范佳豪
12 宋嘉逸 2018-03-23 指正Lab03-Solution错误 吴昕宇
13 陈俊池 2018-03-26 均摊分析课堂演示(Table-Delete) 范佳豪
14 李铭飞 2018-03-26 指正PPT错误(Slide09) 范佳豪
15 张熠帆 2018-03-27 Lab03-Top 3 Best Homework 吴昕宇
16 严傲阳 2018-03-27 Lab03-Top 3 Best Homework 吴昕宇
17 张豪祺 2018-03-27 Lab03-Top 3 Best Homework 吴昕宇
18 张熠帆 2018-03-28 Lab04-Top 3 Best Homework 范佳豪
19 查凯文 2018-03-28 Lab04-Top 3 Best Homework 范佳豪
20 傅彦钧 2018-03-28 Lab04-Top 3 Best Homework 范佳豪
21 奚彬涵 2018-03-29 纠正上课错误(Independent Set) 范佳豪
22 龚政 2018-04-02 指正PPT错误(Slide10) 吴昕宇
23 薛寒 2018-04-07 Lab05-Top 3 Best Homework 吴昕宇
24 闫嘉昆 2018-04-07 Lab05-Top 3 Best Homework 吴昕宇
25 孙雪涵 2018-04-07 Lab05-Top 3 Best Homework 吴昕宇
26 陈家栋 2018-04-12 Depth First Search课堂演示 吴昕宇
27 孙雪涵 2018-04-12 Breadth First Search课堂演示 吴昕宇
28 周思远 2018-04-16 Lab06-Top 3 Best Homework 范佳豪
29 龚政 2018-04-16 Lab06-Top 3 Best Homework 范佳豪
30 陈诧姹 2018-04-16 Lab06-Top 3 Best Homework 范佳豪
31 郑宏锴 2018-05-03 指正PPT错误(Slide13) 范佳豪
32 闫嘉昆 2018-05-03 Turing Machine课堂演示 范佳豪
33 叶金标 2018-05-04 Lab07-Top 3 Best Homework 吴昕宇
34 曹宏键 2018-05-04 Lab07-Top 3 Best Homework 吴昕宇
35 薛寒 2018-05-04 Lab07-Top 3 Best Homework 吴昕宇
36 严傲阳 2018-05-07 Lab08-Top 3 Best Homework 范佳豪
37 左思成 2018-05-07 Lab08-Top 3 Best Homework 范佳豪
38 余宏翔 2018-05-07 Lab08-Top 3 Best Homework 范佳豪
39 胡方 2018-05-07 纠正上课错误(Domain Conversion) 范佳豪
40 梁若凡 2018-05-14 NP规约课堂演示(3-SAT到3D-MATCHING) 吴昕宇
41 查凯文 2018-05-17 Lab09-Top 3 Best Homework 吴昕宇
42 孙雪涵 2018-05-17 Lab09-Top 3 Best Homework 吴昕宇
43 孙晨鸽 2018-05-17 Lab09-Top 3 Best Homework 吴昕宇
44 郭洪一 2018-05-24 上课回答问题(Approximation Algorithm) 范佳豪
45 高奕丰 2018-05-27 Lab10-Top 3 Best Homework 范佳豪
46 徐咏晴 2018-05-27 Lab10-Top 3 Best Homework 范佳豪
47 李文浩 2018-05-27 Lab10-Top 3 Best Homework 范佳豪
48 张豪祺 2018-05-28 LP-Rounding课堂演示 吴昕宇
49 傅彦钧 2018-06-06 Lab11-Top 3 Best Homework 吴昕宇
50 梁若凡 2018-06-06 Lab11-Top 3 Best Homework 吴昕宇
51 朱晨旭 2018-06-06 Lab11-Top 3 Best Homework 吴昕宇
52 陈继森 2018-06-06 Lab12-Top 3 Best Homework 范佳豪
53 吴仁杰 2018-06-06 Lab12-Top 3 Best Homework 范佳豪
54 曹宏键 2018-06-06 Lab12-Top 3 Best Homework 范佳豪
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