课程名称 (Course Name)：Algorithm Theory and Analysis

课程代码 (Course Code）：X0335331302M02   

学分/学时 (Credits/Credit Hours)：3/54

开课时间 (Course Term )：春spring

开课学院（School Providing the Course）: 电子信息与电气工程学院  seiee

任课教师（Teacher）: Xiaofeng Gao (gao-xf@cs.sjtu.edu.cn)

课程讨论时数（Course Discussion Hours）: 54 小时(Hours)

课程实验数（Lab Hours）: 10小时(Hours)

课程内容简介(Course Introduction):

This course is an advanced algorithm class for graduate students. It mainly focuses on the design techniques of various algorithms like divide-and-conquer, greedy approach, dynamic programming, graph algorithm, etc; and the analysis methodology of corresponding designs like amortized analysis, time/space complexity, correctness proof, NP-completeness, and approximations.

教学大纲(Course Teaching Outline):

Course Objectives

This course introduces students to the analysis and design of algorithms. Upon completion of this course, students will be able to do the following:

• Analyze the asymptotic performance of algorithms.
• Demonstrate a familiarity with major algorithms and data structures.
• Apply important algorithmic design paradigms and methods of analysis.
• Synthesize efficient algorithms in common engineering design situations.

Course Outcomes

Students who complete the course will have demonstrated the ability to do the following:

• Argue the correctness of algorithms using inductive proofs and loop invariants.
• Analyze worst-case running times of algorithms using asymptotic analysis. Compare the asymptotic behaviors of functions obtained by elementary composition of polynomials, exponentials, and logarithmic functions. Describe the relative merits of worst-, average-, and best-case analysis.
• Analyze algorithms using amortized analysis, when appropriate. Recite analyses of simple algorithms that employ this method of analysis. Describe different strategies for amortized analysis, including the accounting method and the potential method.
• Describe the divide-and-conquer paradigm and explain when an algorithmic design situation calls for it. Recite algorithms that employ this paradigm. Synthesize divide-and-conquer algorithms. Derive and solve recurrences describing the performance of divide-and-conquer algorithms.
• Describe the greedy paradigm and explain when an algorithmic design situation calls for it. Recite algorithms that employ this paradigm. Synthesize greedy algorithms, and analyze them.
• Describe the dynamic-programming paradigm and explain when an algorithmic design situation calls for it. Recite algorithms that employ this paradigm. Synthesize dynamic-programming algorithms, and analyze them.
• Explain the major graph algorithms and their analyses. Employ graphs to model engineering problems, when appropriate. Synthesize new graph algorithms and algorithms that employ graph computations as key components, and analyze them.
• Understand the basic concepts of advanced algorithm design techniques, e.g., approximation algorithms, distributed algorithms, programming skills, and the fundamental methodology to analyze the performance of the algorithm.
• Demonstrate a familiarity with applied algorithmic settings - such as computational geometry, operations research, security and cryptography, parallel and distributed computing, operating systems, and computer architecture - by reciting several algorithms of importance to different fields.

课程进度计划(Course Schedule):

Week	Lecture Topic	HW	Event
1	Syllabus, Preliminary, Introduction to Algorithm Schedule, Grading Policy, Preliminary, Basic Introduction, etc.	Lab-01
2	Data Structure, Math Functions Data Structure, Graph, Disjoint Set, Mathematical Fundamentals, etc.	Lab-02
3	Amortized Analysis Aggregate Analysis, Accounting Method, Potential Method	Lab-03
4	Divide-and-Conquer Mergesort, Selection, Sorting Network, etc.	Lab-04
5	Greedy Approach (1) Activity Selection, Minimum Spanning Tree, Huffman Code, etc.	Lab-05
6	Greedy Approach (2) Interval Partitioning, Task Scheduling, Shortest Path, Cache, Matroid	Lab-06
7	Dynamic Programming (1) Matrix-Chain, Longest Common Subsequence, 0-1 Knapsack, etc.	Lab-07
8	Dynamic Programming (2) Optimal Substructure, Weighted Interval Scheduling, Alignment, etc.
9	Application. Exercises. Midterm.		Midterm
10	Graph Algorithms (1) Single Source Shortest Paths, All-Pairs Shortest Paths, etc.	Lab-08	Project-01
11	Graph Algorithms (2) Maximum Flow, Minimum Cut, etc.	Lab-09
12	Graph Algorithms (3) Computational Geometry, Real-World Applications	Lab-10
13	NP-Completeness (1) NP, NP Completeness, NP Hard, Turing Machine, Verification, etc.	Lab-11
14	NP-Completeness (2) Polynomial time Reduction, Reducibility, Proofs, etc.	Lab-12
15	Approximation Design (1) Approximation Ratio, Approximation Class, Examples	Lab-13
16	Approximation Design (2) Sequential Algorithm, Local-Search, LP, Primal-Dual Technique, etc.
17-18	Review. Exercises. Tutoring. Final Exam		Final

课程考核要求(Course Assessment Requirements)：

The final grade will be derived from your performance on the tests, and assignments. The class participation is shown as follows: