博文

Stepping_Oline_Judge_BFS

图片
Lintcode--Leetcode： Base + Senior BFS-- level order traversal 经典模板： 总结：使用queue作为维护每一层节点，并由上一层拓展到下一层的数据结构： 遍历一个节点所在层，队尾加入 队首pop，加入pop节点的儿子们，由x层拓展到x+1层。size动态变化。 连通块Connected Component问题： 图的表示：邻接表 lintcode: https://www.jiuzhang.com/solution/connected-component-in-undirected-graph/ Similar leetcode： https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/description/ Lintcode--Leetcode： Base + Senior BFS in Binary Tree 经典模板： 总结：使用queue作为维护每一层节点，并由上一层拓展到下一层的数据结构： 遍历一个节点所在层，队尾加入 队首pop，加入pop节点的儿子们，由x层拓展到x+1层。size动态变化。 连通块Connected Component问题： 图的表示：邻接表 lintcode: https://www.jiuzhang.com/solution/connected-component-in-undirected-graph/ Similar leetcode： https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/description/ 图中的bfs： 图和矩阵中，节点之间是双向关系，所以需要一个boolean矩阵，记录是否访问过，防止节点重复进入queue。 图和矩阵的bfs，for循环在外部 对比： 右边，bfs in graph, 相当于只做了一层的遍历 ...
发表评论
继续阅读

Sorting Algorithms Summary

Sorting Algorithms Summary Comparison-based Sorting: 4 Decision Tree Model: for study the limit of comparison-based sorting Prove: The lower bound of running time for any c-based sorting algorithm is nlogn --> omega(nlogn), both of Heap Sort and Merge Sort are almost the best of them. 1. Insertion sort: worst case theta(n^2) suitable for the small size of input data in-place sorting: 除待排序数组本身，仅有常数个元素需要存储 2. Merge sort: theta(nlogn) non-in-place sorting 3. Heap sort: O(nlogn) in-place sorting 4. Quicksort: in-place sorting worst case theta(n^2) expected running time theta(nlogn) in the real situation, it is faster than Heap Sort 与insertion sort类似，二者code紧凑，运行时间隐含常数系数很小 Suitable for the Large size of input data Non-Comparison-based Sorting  --it may break the lower bound of nlogn. 1. 计数排序 Counting Sort 假定输入元素值均在集合{0，1，2，..., k}内，用数组索引作为确定相对次序的工具 running time: theta(k+n) k = O(n), linear time 2. 基数排序 Radix Sort 扩展计数排序的适用范围 n个整数，每个整数d位数字，每个数...
发表评论
继续阅读

forward one paragraph to open my July

"  如果在几年前，别人告诉我说，生活需要自律，我肯定会笑掉大牙。因为我就是那种认为人生一定要活的很随性很尽兴的人之一，自律真是太痛苦了，甚至我也不觉得自律有什么好的，觉得聪明才更重要。 慢慢的我的想法就改变了，因为开始发现在每一个不自律的行为之后，都会带给你一个更大的痛苦。 忍不住吃了好几顿垃圾食品，之后皮肤就会变糟，身体开始变胖，不得不重新开始节食和运动。 控制不住情绪大发脾气，伤害了身边的人，人际关系也开始变得更糟。 把工作拖到 Deadline ，做出来的东西质量并不怎么样，然后陷入我原本可以做的更好的懊悔当中。 所以啊，及时享乐，不懂得延迟满足感，当时的开心随时可以引爆之后的小型炸弹，你的生活中会因此出现一个又一个需要被填补的坑。而反观我身边过得很好的朋友，他们并不一定比平常人更聪明，但都早早地养成了自律的品质。 现在才意识到这一点的我，时常觉得自己成熟的太晚。前几天看到一篇文章中的一段话，觉得特别好，默默记在手机备忘录上了 —— “ 康德说，自律使我们与众不同。 自律令我们活得更高级。 也正是自律，使我们获得更自由的人生。 他的推理是这样的： 假如我们像动物一样，听从欲望，逃避痛苦，我们并不是真的自由行动。 为什么不是？ 因为我们成了欲望和冲动的奴隶。 我们不是在选择，而是在服从。 但人之所以为人，就在于，人不是被欲望主宰，而是自我主宰。 ” 衷心希望，我从现在开始可以成为自我主宰类型的人。"
发表评论
继续阅读

8 Link Analysis

图片
Pagerank—link analysis  Early web search: extract keywords-->queries match -->page ranked by  occurrences of keywords Term Spam: (TS) Disguise a page as sth it is not about  Pagerank: vs TS Rank pages by linkage too How many pages point to a page= # incoming links => importance Link spam (fade incoming pointers) Manually identify some important pages and assign them page ranks , then let ranks propagate to other nodes. Random surfer model  Random surfer start from any page follow its outgoing links randomly   来，去，都是随机的 Pagerank = Prob ( a random surfer lands on the page ) More robust than manual approach , a collective voting scheme Limiting distribution  Graph is strongly connected , a node can reach any other node in the graph But cannot have dead end & spider traps A--->B, C, D;    B--->A, D,(A,D->C);     C--->A(->B,C,D);   ...
发表评论
继续阅读

1 Map reduce problems

图片
PROBLEMS Join   Matrix multiplication 2 / 1 phase  Matrix vector multiplication  POINTS Map reduce input output Memory requirement  Reducer size  Communication cost P1 Join:  R ( A , B )  S ( A , C )   1. Map r ( a , b ) => ( a , ( 'R' , b ));  s ( a , c ) => ( a , ( 'S' , c ))   2. Reduce ( a , [( 'R' , b ), ( 'S' , c1 ), ( 'S' , c2 )]) => ( a , ( b , c1 )), ( a , ( b , c2 ))   Dangling tuples: Key with values from only 1 relation  ( a , [( 'R' , b )]) => left dangling ; ( a , [( 'S' , c )]) => right dangling  P2 Matrix-multiplication  C mXn = A mXp B pXn  2 phase: a. phase1  product  Map : Extract key from A ’ s c , B ’ s r A [ i , k ] => ( k , ( 'A' , i , A [ i , k ])) ; B [ k , j ] => ( k , ( 'B' , j , B [ k , j ]))   Communication cost : mp + np  Reduce...
发表评论
继续阅读