Please enable JavaScript.
Coggle requires JavaScript to display documents.
AA考试题型 - Coggle Diagram
AA考试题型
选择题
I/O Efficient Algorithm
Cache-aware and Cache-oblivious Algorithm
计算I/O times
考察tile t的取值范围
Cache aware&oblivious的概念和性能
如何构建Cache-oblivious Algorithm
I/O-efficient Sorting
计算EM-MergeSort的running time 和 I/O time
考察Cache-oblivious下的mergesort的k如何取值
Replacement Policies
LRU and MIN 的概念
Thm5.3的考察
MIN和LRU的优缺点对比
I/O-efficient Data Structure
walk down the BST
B-Tree 概念
Buffer Tree 适用情况和worst case
Priority Queue
Stream Algorithm
Intro to Stream Algorithm
General and Strict Turnstile Model Difference
epsilon-major model
考察No-sublinear的证明
Streaming and Randomization
Median Trick以及其变体
考察特殊情况下k越大成功概率越小
考察特殊情况下我们可以取最大值或者最小值作为合理的取值
Hashing Based Streaming Algorithm
Count-Min Sketch的适用范围：cash-register model可用，general turnstile model不可用
考察Count-Min Sketch的原理
Approximation Algorithm
Load Balancing (Greedy&Ordered Scheduling)
考察证明用到的不等式
考察Approx Algo的guaranteed特性
当m=2, n<=4时都是最优解,n>=5时 (4/3-1/3m)
LP Relaxation
Vertex Cover Problem的概念
考察0/1-LP和relaxed-LP的区别
计算Intergrality Gap
Polynomial-time Approximation Schemes
Def of PTAS and FPTAS
Roles and Impact for Delta
How to proof approximation ratio and running time