Algorithm Design and Analysis - 算法设计与分析

Undergraduate course, Peking University, School of Electronics Engineering and Computer Science, 2018

This course is an introductory undergraduate course on the design and analysis of algorithms.

Content

This course covers a wide range of computer algorithms, including divide-and-conquer, dynamic programming, greedy algorithms, branch and bound, NP completeness, randomized algorithms, approximation algorithms and sorting.

Note: The course is taught in Chinese.

本课程仅使用中文授课

课程要求

先修课程:

Introduction to Computation (A)

Discrete Mathematics and Structures

中文简介:

本课程从算法设计出发,系统的介绍了算法设计的一般方法和常用模式,并围绕算法的正确性、算法的复杂度和问题的复杂度等问题,介绍了算法证明的基本方法,算法分析的数学基础和常用技巧,问题复杂度分析的基础理论等知识。主要内容包括:算法证明、渐进分析和递归式求解等算法分析基础,递归、分治、贪心、动态规划和回溯等常用算法设计方法,NP完全性和多项式规约等计算复杂度理论,近似算法、随机算法、局部搜索、并行算法以及在线算法等高级算法设计方法及相关分析方法等。