CS161: Design and Analysis of Algorithms

算法复杂度分析（Big Oh，Omega，Theta），递归关系和主方法。包括随机算法，分治策略，贪婪算法，hasing，堆，图算法和搜索算法（包括盲搜索和A *搜索）。各种排序算法的实现，时间与空间复杂度，稳定性等，二叉树的前中后序遍历的非递归与递归实现（已知前中序遍历，求后序遍历等），树的基本概念（如高度等），二分查找及其实现，图论算法（包括图的邻接表与邻接矩阵的表示，深度优先遍历与宽度优先遍历等（这里有可能拓展到二叉树中），最短路径等），

Prerequisite

• Mathematical Foundations of Computing

• Introduction to Probability for Computer Scientists

Readings

• 算法导论
• 算法

Knowledge points

• 线性表、数组、链表
• 栈与队列
• 树、二叉树、多叉树实现和遍历方式，AVL树实现以及插入删除过程、红黑树（了解定义即可）
• 图，以及图的实现方式、遍历
• B树、B+树
• 堆
• 散列函数和散列表
• 排序算法：冒泡、插入、快速、希尔、堆排、基数、归并等
• 字符串匹配算法：KMP
• 常见算法思想：递归、枚举、递推、分治、贪心、动态规划等