Design and Analysis of Algorithms
Course Code
AI2615
Session
Spring 2021
Instructor(s)
Chihao Zhang, Assistant Professor (tenure-track)
John Hopcroft Center for Computer Science
Shanghai Jiao Tong University
Description
The course is mainly about the design and analysis of discrete algorithms. The topics I am going to talk about are divided into two parts. In part I, I will introduce traditional methods for designing algorithms, including greedy method, divide-and-conquer method, dynamic programming, and many classic combinatorial algorithms on graphs. I will also introduce reductions for proving NP-hardness. Part II of the course will cover some advanced tools for algorithm analysis and design. For example, I will talk about the use of linear programming and semi-definite programming to design approximation algorithms and the use of some probabilistic tools to design efficient randomized algorithms.