Advanced Algorithms
Course Code
EI374
Session
Spring 2019
Instructor(s)
Chihao Zhang, Assistant Professor (tenure-track)
John Hopcroft Center for Computer Science
Shanghai Jiao Tong University
Description
The course is offered to advanced undergraduates who already took the course “Introduction to algorithms”, especially for those who are interested in algorithms and want to know more modern topics.
This year, the course is mainly about the design and analysis of approximation algorithms, and also includes some modern topics on algorithm design. We will emphasis on the use of tools like linear programming and positive semi-definite programming. These tools are fundamental and useful in many areas of computer science.
The main purpose of the course is twofold. 1) The students can learn some basic ideas in the design and analysis of approximation algorithms to extend their “algorithmic toolkit” when facing problems in practice. Moreover, students can learn to treat algorithms rigorously. 2) For students who are interested in algorithm research, the course will introduce some research topics.
本课程是给高年级本科生开设的“第二门”算法课，主要面向的对象是学过算法课程后对这一领域比较感兴趣，又希望了解一些比较前沿知识的同学。
今年，这门课的主要内容是关于近似算法的设计与分析和一些比较新的算法课题介绍，特别是对于线性规划、半正定规划等工具的使用。这些工具在计算机科学的各个方向都是非常基本且实用的。
课程的目标有两个：1. 通过对常用近似算法设计工具的介绍，让学生能够掌握基本的设计和分析近似算法的思路，从而丰富自己在遇到实际问题中时的“武器库”。更重要的，是培养学生严格思考与分析算法的能力。2. 通过对于前沿课题的介绍，展示算法之美，激发学生对于理论计算机科学的兴趣。