Home

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.

 
 
© John Hopcroft Center for Computer Science, Shanghai Jiao Tong University
分享到

地址:上海市东川路800号上海交通大学软件大楼专家楼
邮箱:jhc@sjtu.edu.cn 电话:021-54740299
邮编:200240