Please enable JavaScript.
Coggle requires JavaScript to display documents.
AA大题 - Coggle Diagram
AA大题
DAG
已知的题型
- 计算每个node的level值，这个值由root到该点的最长路径决定
- undirected graph的填色问题，确保每两个相邻点的颜色不一样
-
- 计算independent set数量满足某个条件的问题
- 把undrected graph通过index排序由低到高变为DAG
- 构造合理的f函数，同时满足IO次数和local特点
- 解释为什么f函数是local的，以及IO次数是SORT(1+|N_in(v_i)|)
- 说明我们可以计算f函数在SORT(|v|+|E|)内
-
LP-rounding
-
-
-
-
已知题型
- 在固定数量的小组里面满足特定条件（>=1或者2，3）
-
Cache-aware&oblivious
-
设计Cache-aware算法
-
-
-
- 切记内层的IO是O(M/B)，然后乘以n/t*层数
设计Cache-oblivious算法
-
-
-
- 写出算法的公式，然后用树来计算base case的总IO，加上总overhead，如果有的话
- 切记处理matrix的时候，t得加个平方，另外overhead也是t^2/B
FPTAS
- Assign normalized 之后的weight
- 定义新的图，里面的研究对象被normalized之后的数值替代
-
-
-
- 将running time里的研究对象替换为新的normalized之后的
-
-
-
-