1. 算法本质
   1. 算法本质上可以看做是在一个解空间当中的搜索问题
   2. 学习一项知识，必须问自己三个重要问题：1. 它的本质是什么。2. 它的第一原则是什么。3. 它的知识结构是怎样的。
2. 算法的学习方法
   1. 【Better Explained】
      1. 所谓“正儿巴经”学习算法，意即开始对算法思想的本质进行归根究底的过程、对思维方法论进行归纳抽象的过程、对各种解题技巧进行一般化的过程、通过不断练习来让记忆内隐化的过程..
      2. 你的理解，记忆，以及学习的效率都会得到质的提高：
         1. 这个算法的本质是什么？
         2. 为什么这种解法是对的？
         3. 为什么那种解法是错的？
         4. 为什么这种解法不是最优的？
         5. 证明为什么没有更优的解法。
   2. 学习与记忆
      1. 学习——本质上是个体力活
         1. 将外界（书本上的）知识转化为外显记忆
            1. 【Better Explained】
            2. The Art of Learning A Journey in the Pursuit of Excellence
         2. 通过不断练习，将外显记忆转化为内隐记忆
            1. 【Better Explained】
            2. 把时间当作朋友
            3. 将关于思维方法的知识转化为内隐记忆从而不知不觉就遵循
            4. 将关于事实知识（例如“定理”、“性质”）的提取线索们转化为内隐记忆从而看到XX就能想到YY
   3. 知其所以然
      1. 问题
         1. 算法书都是欧几里德式的，这完全把人类大脑创造发明的步骤给反过来了。看起来是阳关大道，实际上神鬼难行。
         2. 答案&做法到底是怎么来的，从问题到答案之间经历了怎样的思维过程。
      2. 思考一个问题的过程中有两种思维形
         1. 【Better Explained】
            1. 很大的试错成分（好听一点叫“探索”）
         2. 联想
         3. 演绎&归纳
      3. 忽略思考本身，才是本末倒置
         1. 【Better Explained】
            1. 对于不断学习的我们来说，忽视到达解的那个过程实际上却变成了舍本逐末。【要知道，你不是为了解一道题！】
            2. 如果问题求解是一部侦探小说，那么算法只是结局而已，而思考过程才是情节。【代码敲出来，能用多长时间，你说是吧】
         2. 一来思维的漫长繁杂的过程已经在大脑里面淡化得差不多了
         3. 二来，思考过程是我们的空气和水，而“鱼是最后一个感觉到水的”
         4. 三来，由于我们的目标是问题的解，解才是我们为之兴奋和狂喜的东西，而不是求解的过程，过程只是过程，目的才是目的。
         5. 其四：感到介绍思维过程是不相干的【对于传授知识的人】
      4. 思维过程远胜于问题的解决方案
         1. 内隐化
         2. 跨情境运用
         3. 对问题解的更多记忆提取线索
            1. 【Better Explained】
            2. 譬如你知道堆(heap)是怎样由朴素的决策树演化而来的，它又是为了解决什么问题的，你即便忘记了具体的细节，也可以自己推导出来。
            3. 譬如你知道KMP算法的本质在于消除回溯，至于如何消除回溯却并不是那么难以推导的，所以即便忘了也可以借助于大脑的逻辑演绎能力再现出来。
            4. 譬如你知道Tarjan算法其实只是从后序遍历经过两个优化调整而来的（其中并査集的使用其实只是优化手段——为了能够迅速判断祖先节点是谁——而非算法本质——当然，算法设计的主要任务本来就是通过问题条件中蕴含的知识来“消除冗余计算”和“避免不必要计算”，所以你也可以说并査集的使用是关乎本质的，只不过，知道了为什么需要引入并査集，就会强烈地感觉到一切是顺理成章的了），那这个出了名的绕人的算法也就不那么难以理解和记忆了。
            5. 譬如你知道排序的本质，就能够对什么是最优排序，为什么它是最优排序有深刻的认识。四两拨千斤。
            6. 没有一个本质层面上的关联，算法只是一堆离散的机械步骤【亚里士多德：学习即联接】
            7. 知道算法是怎样一步步被推导【产生】出来的，就拥有了大量的记忆提取线索：对算法发现过程中的任何一个关键步骤（尤其是本质）的回忆都可能使我们能够自己动手推导出剩余的内容。
         4. 包含了多得多的知识
            1. 记背后的思想，却有助于解决一类问题。
         5. 重在分析推理，而不是联想
            1. 不知道问题的本质是什么，就需要靠联想、类比来领路探索。只不过，养成优先从问题的本质入手进行考察的好习惯绝对是有更大的好处的。
      5. 深入理解一个算法的来龙去脉前因后果，从一个算法中领悟尽量深刻的东西
         1. 寻找该算法的原始出处
         2. 原始出处将的不给力
            1. 网上找找，牛人讲得未必比经典教材上的差
         3. 牛人不给力
            1. 自己来喽
            2. 为什么要这样（为什么这是好的）？
            3. 为什么不是那样（有其它做法吗？有更好的做法吗？）？
            4. 这样做是最好的吗？（为什么？能证明吗？）
            5. 这个做法跟其它的什么做法有本质联系吗？
            6. 这个跟这个的区别是什么？
            7. 问题的本质是什么？
            8. 这个做法的本质又是什么？
            9. 到底本质上是什么东西导致了这个做法如此..？
            10. 与这个问题类似的还有其它问题吗？（同样或类似的做法也适用吗？）等等。
         4. 总结
      6. TopLanguage主题讨论“今天我们思考”的索引
   4. 知其所以然（续）
      1. 【Better Explained】
         1. 看定理必看证明
         2. 看一个问题的解法，必然要看解法所诞生的过程
            1. 背后是否隐藏着更具一般性的解决问题的思路和原则。
      2. 三件事情
         1. Dark time 很有效
         2. 在你懂的时侯反问自己：你真的懂了吗
            1. 你是否有一种“哦，原来是这样啊，这下再也不可能忘记了”的感觉。
         3. 记录只是学习和思考的副作用
            1. 只要还在学习和思考，就必然会有新的记录，博客会不断更新
      3. 知道怎么做是从正确（高效）解法得到的，而知道为什么必须得那样做则往往是从错误（低效）的解法当中得到的。
3. Mathematic
   1. The foundation concept
      1. Number Power Logarithms
   2. Discrete Mathematics
      1. Mathematical induction
   3. Concrete Mathematic
      1. Sums
      2. Integer Functions
      3. Number Theory
      4. Binomial Coefficients
      5. Special Numbers
         1. Harmonic Numbers
         2. Fibonacci numbers
      6. Generating Functions
      7. Asymptotics
   4. Combinatorics
      1. Permutations and Combinations
4. Algorithms Analysis
   1. 要分析一个算法的好坏，首先弄清它的解空间的结构，然后分析它是怎么来探索这个解空间的。
   2. 【Better Explained】
      1. 【1】解空间
      2. 【2】算法探索这个解空间方面的行为决定了它的效率高低。
      3. 排序算法
         1. 解空间N！——n个元素的全排列
         2. 探索解空间的行为
            1. 基于比较的排序
            2. Quick sort
            3. 一次比较操作最多有两个结果，a>b或a<b，既然只有两种结果，那么最多只能将解空间进行2分，如果每次都能完美的2分，那么找到那个唯一点最终需要的步骤就是log(n!) = O(nlogn)。
      4. 01背包问题
         1. 解空间的大小是2^n——每个item是否选取（0，1）的序列
         2. 有种O(nw)的算法我还没看懂
5. Computer Science
   1. Loop invariant
      1. Initialization: It is true prior to the first iteration of the loop.
      2. Maintenance: If it is true before an iteration of the loop, it remains true before the next iteration.
      3. Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.
6. Algorithms http://en.wikipedia.org/wiki/List_of_algorithms
   1. Combinatorial algorithms
      1. General combinatorial algorithms
      2. Graph algorithms
         1. Graph drawing
         2. Network theory
         3. Routing
         4. Search
         5. Subgraphs
      3. Tree traversal
         1. Depth-first Traversal
            1. Preorder traversal
            2. Visit the root.
            3. Traverse the left subtree.
            4. Traverse the right subtree.
            5. Inorder(symmetric) traversal
            6. Traverse the left subtree.
            7. Visit the root.
            8. Traverse the right subtree.
            9. Postorder traversal
            10. Traverse the left subtree.
            11. Traverse the right subtree.
            12. Visit the root.
         2. Breadth-first Traversal
            1. Level order traversal
      4. Sequence algorithms
         1. Approximate matching
         2. Item search
         3. Merging
         4. Permutations
         5. Sequence alignment
         6. Subsequences
         7. Substrings
         8. Sorting algorithm http://en.wikipedia.org/wiki/Sorting_algorithm
            1. Insertion sorts
            2. 【Better Explained】
            3. 本质
            4. 打桥牌
            5. 一边抓牌，一边码牌
            6. 对于insertion sort 改进 主要从 减少比较和移动 两方面
            7. Insertion sort
            8. 本质
            9. 一边抓牌，一边码牌
            10. 原始出处
            11. 也许是来自于打扑克的灵感吧
            12. Binary insertion sort
            13. 本质
            14. Insertion sort in which the proper location for the next item is found with a binary search.
            15. 原始出处
            16. insertion sort 改进 ，减少比较次数
            17. Shell sort
            18. 本质
            19. Shell sort exploits the fact that insertion sort works efficiently on input that is already almost sorted.
            20. 所以 就得先大概排一下 input data，怎么排？类似于 playing golf，一开始需要一次远距离转移，之后每次递减，直到小鸟球。交换未必完美，我想你知道老鹰球？
            21. 历史出处
            22. devised by Donald Shell in 1959，应该说同时减少了比较和移动
            23. List insertion sort
            24. 本质
            25. 附加的数组链表记录顺序【不是移动 】，之后用这个order 重排 原始数组i,cur，next
            26. 关于重排序：有两条线1.i是按照原始的数组前进的。cur和next 是按照附加数组内定的order 前进 。本质上就是为了指定交换的对象而已
            27. List insertion sort 的本质是一边抓牌，一边码牌，只不过码牌有点绕
            28. 历史出处
            29. TAOCP ，insertion sort 的改进版 ，减少移动次数
            30. Exchange Sorts
            31. 【Better Explained】
            32. 本质
            33. Systematically interchange pairs of elements that are out of order until no more such pairs exit
            34. 系统的交换乱序的items，直到排好了
            35. Topic
            36. exchange selection
            37. Bubble sort
            38. 本质
            39. for each pair of indices, swap the items if out of order
            40. 最大的被移动的最后是效果，结果。不是本质。
            41. Two properties of the correct implementation of bubblesort:
            42. If there are no exchanges, then the sorting is complete .
            43. Each next pass ends at the last swap of the previous pass.
            44. merge exchange
            45. parallel sort
            46. partition exchange
            47. quicksort
            48. 本质
            49. divide and conquer
            50. pivot ，reorder ， partition
            51. 历史出处
            52. Hoare developed the algorithm in order to sort the words to be translated
            53. Distribution sorts
            54. Radix sort
            55. 本质
            56. sorts strings letter by letter
            57. 一个字母一个字母的排
            58. 所有待排数据格式化成相同字符宽度，从LSD到MSD，每次只 按一位 的大小 排序 整个元素
            59. 历史出处
            60. Radix sort dates back as far as 1887 to the work of Herman Hollerith on tabulating machines.
            61. Counting sort
            62. 本质
            63. 本质上已经不是传统的排序了，将存储方式的转换。
            64. 是一个取巧的诡计
            65. only for integer 有重复的
            66. 历史出处
            67. The algorithm was first used by Harold H. Seward in 1954
            68. Bucket sort
            69. 本质
            70. divide and conquer
            71. partition an array into a number of buckets. Each bucket is then sorted individually .
            72. Selection sorts
            73. 【Better Explained】
            74. 本质
            75. Repeated Selection
            76. 不是重复，是反复
            77. Selection sort
            78. 本质
            79. repeated selection
            80. pick the smallest 【maximum 】of the remaining elements, and exchange it with the first【last】 item of the remaining elements
            81. 历史出处
            82. Heapsort
            83. 本质
            84. repeated selection
            85. convert the list into a heap, keep removing the largest element from the heap and adding it to the end of the list
            86. 本质仍是，不断的选择 pick ，只是 选择的地方换了，变得更利于 pick，当然，首先你需要把 数组链表转换成——heap
            87. 建堆，不是我们现在应该关心的，他不是本质。
            88. Merge sorts
            89. 【Better Explained】
            90. 本质
            91. divide and conquer &merge
            92. partition ，sort...until can't partition ,then merge
            93. Merge sort
            94. 本质
            95. divide and conquer & merge
            96. partition ，sort...until can't partition ,then merge
            97. sort the first and second half of the list separately, then merge the sorted lists
            98. 历史出处
            99. Merge sort was invented by John von Neumann in 1945.
            100. Strand sort
            101. 本质
            102. divide and conquer & merge
            103. extract sorted list from raw list,then merge it with the previous extracted list
            104. 历史出处
            105. 对于大半排好序的链表，strand sort 表现很好
   2. ETC
      1. Computational mathematics
         1. Abstract algebra
         2. Computer algebra
         3. Geometry
         4. Number theoretic algorithms
         5. Numerical algorithms
            1. Elementary and special functions
            2. Geometric
            3. Interpolation and extrapolation
            4. Linear algebra
            5. Monte Carlo
            6. Numerical integration
            7. Root finding
         6. Optimization algorithms
      2. Computational science
         1. Astronomy
         2. Bioinformatics
         3. Geoscience
         4. Linguistics
         5. Medicine
         6. Physics
         7. Statistics
      3. Computer science
         1. Computer architecture
         2. Computer architecture
         3. Computer graphics
         4. Cryptography
         5. Digital logic
         6. Machine learning and statistical classification
         7. Programming language theory
            1. Parsing
         8. Quantum algorithms
         9. Theory of computation and automata
      4. Information theory and signal processing
         1. Coding theory
            1. Error detection and correction
            2. Lossless compression algorithms
            3. Lossy compression algorithms
         2. Digital signal processing
            1. Image processing
      5. Software engineering
         1. Database algorithms
         2. Distributed systems algorithms
         3. Memory allocation and deallocation algorithms
         4. Operating systems algorithms
            1. Disk scheduling
            2. Networking
            3. Process synchronization
            4. Scheduling
7. Data structures http://en.wikipedia.org/wiki/List_of_data_structures
   1. Data types
      1. Primitive types
         1. Boolean
         2. Char
         3. Double
         4. Float
         5. int
         6. String
      2. Composite types
         1. Record (also called tuple or struct)
         2. Union
         3. Tagged union
            1. 我理解为 enum
      3. Abstract data types
         1. Container
         2. Deque
         3. Map/Associative array/Dictionary
         4. Multimap
         5. Multiset
         6. Priority queue
         7. Queue
         8. Set
         9. Stack
         10. String
         11. Tree
         12. Graph
         13. Hash
   2. Trees
      1. Binary trees
         1. AA tree
         2. AVL tree
         3. Binary search tree
            1. 【Better Explained】
            2. Properties
            3. The left subtree of a node contains only nodes with keys less than the node's key.
            4. The right subtree of a node contains only nodes with keys greater than the node's key.
            5. Both the left and right subtrees must also be binary search trees.
            6. Operations
            7. Searching
            8. Insertion
            9. Deletion
            10. Traversal
            11. Sort
         4. Binary tree
         5. Cartesian tree
         6. Randomized binary search tree
         7. Red-black tree
            1. 【Better Explained】
            2. Requirements
            3. A node is either red or black.
            4. The root is black.
            5. (This rule is sometimes omitted from other definitions. Since the root can always be changed from red to black but not necessarily vice-versa this rule has little effect on analysis.)
            6. All leaves are black.
            7. Both children of every red node are black.
            8. Every simple path from a given node to any of its descendant leaves contains the same number of black nodes.
            9. 历史出处
            10. Robert Sedgewick
            11. Left-Leaning Red-Black Trees
            12. I need to see it more and more.
         8. Rope
         9. Scapegoat tree
         10. Self-balancing binary search tree
         11. Splay tree
         12. T-tree
         13. Tango tree
         14. Threaded binary tree
         15. Top tree
         16. Treap
         17. Van Emde Boas tree
         18. Weight-balanced tree
      2. B-trees
         1. B-tree
         2. B+ tree
         3. B*-tree
         4. B sharp tree
         5. Dancing tree
         6. 2-3 tree
         7. 2-3-4 tree
         8. Queap
         9. Fusion tree
         10. Bx-tree
      3. Heaps
         1. Heap
         2. Binary heap
         3. Binomial heap
         4. Fibonacci heap
            1. AF-heap
         5. 2-3 heap
         6. Soft heap
         7. Pairing heap
         8. Leftist heap
         9. Treap
         10. Beap
         11. Skew heap
         12. Ternary heap
         13. D-ary heap
         14. [edit]
      4. Tries
         1. Trie
         2. Radix tree
         3. Suffix tree
         4. Suffix array
         5. Compressed suffix array
         6. FM-index
         7. Generalised suffix tree
         8. B-trie
         9. Judy array
      5. Multiway trees
         1. Ternary search tree
         2. And–or tree
         3. (a,b)-tree
         4. Link/cut tree
         5. SPQR-tree
         6. Spaghetti stack
         7. Disjoint-set data structure
         8. Fusion tree
         9. Enfilade
         10. Exponential tree
         11. Fenwick tree
      6. Space-partitioning trees
         1. Segment tree
         2. Interval tree
         3. Range tree
         4. Bin
         5. Kd-tree
         6. Implicit kd-tree
         7. Min/max kd-tree
         8. Adaptive k-d tree
         9. Kdb tree
         10. Quadtree
         11. Octree
         12. Linear octree
         13. Z-order
         14. UB-tree
         15. R-tree
         16. R+ tree
         17. R* tree
         18. Hilbert R-tree
         19. X-tree
         20. Metric tree
         21. Cover tree
         22. M-tree
         23. VP-tree
         24. BK-tree
         25. Bounding interval hierarchy
         26. BSP tree
         27. Rapidly-exploring random tree
      7. Application-specific trees
         1. Syntax tree
         2. Abstract syntax tree
         3. Parse tree
         4. Decision tree
         5. Alternating decision tree
         6. Minimax tree
         7. Expectiminimax tree
         8. Finger tree
   3. Linear data structures
      1. Arrays
         1. Array
         2. Bidirectional map
         3. Bit array
         4. Bit field
         5. Bitboard
         6. Bitmap
         7. Circular buffer
         8. Control table
         9. Image
         10. Dynamic array
         11. Gap buffer
         12. Hashed array tree
         13. Heightmap
         14. Lookup table
         15. Matrix
         16. Parallel array
         17. Sparse array
         18. Sparse matrix
         19. Iliffe vector
         20. Variable-length array
      2. Lists
         1. The operations of linear lists
            1. 【1】Search
            2. 【2】Insert
            3. 【3】Delete
            4. 【】
         2. Doubly linked list
         3. Linked list
         4. Self-organizing list
         5. Skip list
         6. Unrolled linked list
         7. VList
         8. Xor linked list
         9. Zipper
         10. Doubly-connected edge list
   4. Hashes
      1. Bloom filter
      2. Distributed hash table
      3. Hash array mapped trie
      4. Hash list
      5. Hash table
      6. Hash tree
      7. Hash trie
      8. Koorde
      9. Prefix hash tree
   5. Graphs
      1. Graph
      2. Adjacency list
      3. Adjacency matrix
      4. Graph-structured stack
      5. Scene graph
      6. Binary decision diagram
      7. Zero suppressed decision diagram
      8. And-inverter graph
      9. Propositional directed acyclic graph
      10. Directed graph
      11. Multigraph
   6. Other
      1. Lightmap
      2. Winged edge
      3. Quad-edge
      4. Routing table
      5. Symbol table