1.1 Definition of algorithm 1.2 Insertion sort and merge sort 1.3 Running time and asymptotic analysis 1.4 Θ-notation, Ω-notation, and O-notation 1.5 Recurrences 1.6 Substitution, recursion-tree method, and master method

⚫外排序 ⚫关系操作的执行 ⚫查询优化 ⚫一个典型的关系查询优化器

3.1 Definition of data structure 3.2 Stacks 3.3 Queues 3.4 Linked lists 3.5 Trees 3.6 Postfix expression 3.7 Infix to postfix conversion

5.1 Dictionary problem 5.2 Hash functions 5.3 Collisions resolution by chaining 5.4 Open addressing 5.5 Probing strategies: linear, quadratic, and double hashing 5.6 Analysis of open addressing

2.1 关系模型的基本概念 2.2 关系代数 2.3 关系演算 2.4 关系代数表达式的优化 2.5 关系逻辑

7.1 Introduction to amortized analysis 7.2 Aggregate method 7.3 Accounting method 7.4 Potential method 7.5 Dynamic tables

9.1 Activity-selection problem 9.2 Introduction to greedy solution 9.3 Steps of the greedy strategy 9.4 Knapsack problem 9.5 Huffman code

11.1 String matching problem 11.2 Naive string-matching algorithm 11.3 Rabin-Karp algorithm 11.4 Finite automaton 11.5 Knuth-Morris-Pratt algorithm

• 计数设备：用于计数系统 • 多道分析器：用于能量分析系统、时间分析系统

《数据库系统》参考书籍：《Database Management Systems》2nd Ed（Raghu Ramakrishnan / Johannes Gehrke）