Algorithm: Analysis and Theory (2018) Class Website

 

Algorithm: Analysis and Theory (2018)

基本信息 (General Information)

Level: Graduated
Time & Place: 10:00 am -- 11:40 am, Monday & Thursday, Dong Shang Yuan 309 (东上院309)
Instructor:
  • Name: Xiaofeng Gao
  • Email: gao-xf(at)cs.sjtu.edu.cn
  • Office: Telecom Building 3-328
  • Phone: 021-34207407
Teaching Assisstant:
  • Name: Jiaxi Liu (刘家玺)
  • Email: jsxzljx@163.com
  • Office: SEIEE 3-328
  • Phone: 34207407
  • Office Hour: 19:00 - 21:00, Monday
  • Name: Mingding Liao(廖铭鼎)
  • Email: md-liao@foxmail.com
  • Office: SEIEE 3-328
  • Phone: 34207407
  • Office Hour: 18:00 - 20:00, Tuesday
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.

Lab-03

3

Mar.15

Greedy Approach (2)

Matroid, Greedy-Max Algorithm

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, Minimum Cut, etc

10

May 03

Turing Machine

Computability, Turing Machine, etc.

Lab-09

11

May 07

NP-Completeness (1)

NP class, Polynomial time, etc.

11

May 10

NP-Completeness (2)

Reducibility, Proofs, etc.

Lab-10

12

May 14

NP-Completeness (3) + Approximation (1)

Reducibility, Proofs, etc; Approximation Ratio, etc

12

May 17

Approximation (2)

Approximation Ratio, Approximation Class, Greedy Algorithm, etc.

Lab-11

13

May 21

Approximation (3)

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

Max Cut, 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

    • Reading Materials

      • Slide: Slide06-Matroid.pdf (Print Version: 06-Matroid.pdf)

      • Reference: 

        Reference08-Matroid.pdf  Chapter 16.4 in "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition);  
        Chapter 2.1-2.2 in "Design and Analysis of Approximation Algorithms" by D.-Z. Du, K.-I. Ko, and X. D. Hu, Springer, 2012.

Lecture 7: Dynamic Programming

Lecture 8: Amortized Analysis

Lecture 9: Linear Programming

Lecture 10: Solving Linear Programming in Practice

Lecture 11: Graph Algorithms

Lecture 12: Shortest Path

Lecture 13: Network Flow

Lecture 14: Turing Machine

Lecture 15: NP Reduction

Lecture 16: Approximation

Lecture 17: Approximation II

Lecture 18: Randomized Algorithm

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)

  • Project Description
  • Project Template
    • Please use this latex template for your project:   Project-Template.zip
    • Before you submit your project, compress everything (tex file, pdf file, code file and so on) in to a single zip or rar file and rename your submissions as Project-LastNameFirstName.XXX  
    • Selection link and more details about the projects will be available later.  
  • Project Selection Time
    • The project selection link will be available at 20:00, 2018/04/04 

分组活动细节 (Group Project Detail)

序号
(No.)
队名
(Team Name)
队员 一
(Member 1)
队员 二
(Member 2)
队员 三
(Member 3)
题目
(Project)
时间
(Time)
1 CHAOS 张鹏程 宋晗 SYED MUZAMIL HUSSAIN SHAH NAQVI Project 02: Logistic Network 2018-4-4 20:04:30
2 Three Single Dogs 夏宇晨 刘永志 肖贺军 Project 02: Logistic Network 2018-4-4 20:03:21
3 1DUTCH & 2PAK MUHAMMAD JAHANZEB KHAN USMAN ALI MICHIEL VAN VELDHUIZEN Project 01: Touring Plan 2018-4-4 20:43:46
4 K&W MUHAMMAD HASSAN 刘雨桐 Project 01: Touring Plan 2018-4-4 20:03:36
5 Rockets 方品 王晓晨 赵一 Project 02: Logistic Network 2018-4-4 20:31:03
6 328 吴关昊 王超 吴齐天 Project 01: Touring Plan 2018-4-4 20:03:11
7 ZFW 吴昕宇 周浩 范佳豪 Project 02: Logistic Network 2018-4-4 20:03:27
8 JONAS ARNE LEO WINDMULLER 宋道涵 卢倩倩 Project 01: Touring Plan 2018-4-4 20:16:08
9 CCC 陈昕鑫 晁佳欢 崔炜皞 Project 02: Logistic Network 2018-4-4 20:03:20
10 Θ(n) 张君鹏 陈人望 吕洪涛 Project 02: Logistic Network 2018-4-4 20:04:00
11 Infinity 顾振兴 王鹏宇 蒋希坤 Project 02: Logistic Network 2018-4-4 20:28:32
12 AA&T Squad MUHAMMAD NAVEED RIAZ RIAZ ALI MARTIN PAUTY Project 02: Logistic Network 2018-4-4 20:15:33
13 SGANG JEROME WAN REMY BONNET SEBASTIAN WALTER Project 02: Logistic Network 2018-4-4 20:41:18
14 fishman 杨释心 肖弼 周逸伦 Project 01: Touring Plan 2018-6-14 00:05:21
15 iCAT newbies 许晓童 齐雨飞 张衍 Project 01: Touring Plan 2018-6-13 23:09:13
16 GreenTea BILAL KORIR ALIZA GHULAM MUSTAFA 蒋健巍 Project 01: Touring Plan 2018-4-5 00:30:37
Back to Top

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

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.
  • Other References: 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.
  • Other References: 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.
  • Other References: 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