The Archive of Interesting Code: TODO List

Below is a list of all of the algorithms and data structures that I'm hoping to some day code up. This list will grow as I learn of more algorithms to try out, and will shrink as I start crossing them off. Usually, it grows more than it shrinks. :-)

I've marked in bold the entries on this list that I'm really hoping to get implemented sometime soon. These are usually algorithms I've been reading up on more recently, or which build off of other algorithms/data structures I've coded up. Some of the descriptions here are vague (such as "Linear-Time MST with Integer Weights") where I know that an algorithm exists meeting the description but don't know enough about the problem to be any more specific. If you see anything along those lines, I'd really appreciate an email with either a clarification or a pointer to a particular paper.

  1. Aho-Corasick Algorithm
  2. Bignum
  3. Reference-Counted Smart Pointer
  4. Array Deque
  5. Tarjan's SCC Algorithm
  6. Fixed-Point Iteration
  7. Soft Heap
  8. Bidirectional Map
  9. Bloom Filter
  10. Perceptron Learning
  11. Link/Cut Tree
  12. AA tree
  13. Dynamic Perfect Hash Table
  14. Hindley-Milner Type Inference
  15. Rope
  16. UCT Algorithm
  17. GADDAG
  18. Longest Path Algorithm
  19. A* Search
  20. Binary Decision Diagram
  21. Propositional Network
  22. Zero-Suppressed Binary Decision Diagram
  23. Polynomial Interpolation
  24. Huffman Encoding
  25. Burrows-Wheeler Transform
  26. Quicksort
  27. Simplex Algorithm
  28. Expander Graph Generator
  29. QR Factorization
  30. Cholesky Factorization
  31. Singular Value Decomposition
  32. Timsort
  33. Goldberg's Shortest Path Algorithm
  34. Seam Carving
  35. Gaussian Elimination
  36. B Tree
  37. Edmonds's Matching w/ Union-Find
  38. Boruvka's MST Algorithm
  39. Karger-Klein-Tarjan Randomized MST
  40. Linear-Time MST Verification
  41. PageRank
  42. Alpha-Beta Pruning
  43. Chess Bitboard
  44. HSL-to-RGB Conversion
  45. Fast Fourier Transform
  46. Marriage-before-Conquest Algorithm
  47. Chan's Algorithm
  48. Karger's Min-Cut Algorithm
  49. Graph Coloring
  50. Brodal Queue
  51. Christofides Algorithm
  52. Red-Black Tree
  53. Trie
  54. Minimum-Cost Arborescence
  55. Radix Tree
  56. Lancosz Iteration
  57. Arnoldi Iteration
  58. Suffix Tree (Ukkonen's algorithm)
  59. Suffix Array
  60. 2-3 Finger Tree
  61. Selection Sort
  62. Insertion Sort
  63. Binary Search
  64. Simulated Annealing
  65. Interval Tree
  66. kd-Tree
  67. Quadtree / Octree
  68. Random-Restart Hill Climbing
  69. Boosted Decision Tree
  70. Support Vector Machine
  71. LR(1) Parser Generator
  72. LALR(1) Parser Generator
  73. SLR(1) Parser Generator
  74. Earley Parser
  75. CYK Parser
  76. Value Iteration
  77. Policy Iteration
  78. Set Cover Approximation
  79. Delta Debugging Algorithm
  80. Hough Transform
  81. Tiered Vector
  82. Brodnik Tiered Vector
  83. Multidimensional Array
  84. B+ Tree
  85. Sparse Array
  86. Memory-Adaptive Merge
  87. Ellipsoid Method for LP
  88. BSP Tree
  89. Pairing Heap
  90. Fusion Tree
  91. Quadedge
  92. Winged-Edge
  93. Horn Clause SAT
  94. Chazelle's MST Algorithm
  95. Push-Relabel Max Flow Algorithm
  96. Knapsack Problem with Dynamic Programming
  97. Order Statistic Tree
  98. Linear-Time MST with Integer Weights
  99. Polygon Triangulation
  100. Brodal Fast Join Trees
  101. Gale-Shapley Algorithm
  102. Maximum-Weight Matching
  103. Chained Hashing
  104. Linear Hashing
  105. Quadratic Hashing
  106. Robin Hood Hashing
  107. Bentley-McIlroy 3-Way Merge
  108. Sideways Heap
  109. Deterministic Skiplist
  110. Left-Leaning Red-Black Tree
  111. Leftist Heap
  112. Fenwick Tree
  113. Apostilico-Giancarlo String Matching
  114. Electrical Circuit Solver
  115. Dinic's Algorithm
  116. Fleury's Algorithm
  117. Hopcroft-Karp Algorithm
  118. Planarity Testing
  119. Thorup Queue (Priority Queue from Sorting Algorithm)
  120. PQ Tree
  121. SPQR Tree
  122. Skew heap
  123. Pagoda
  124. Bitap algorithm
  125. Min-Max heap
  126. LZW compression
  127. Static perfect hash table
  128. Hungarian algorithm
  129. Hirschberg's algorithm
  130. AKS primality test
  131. Bootstrapped skew binomial queue (Brodal and Okasaki)
  132. Hood-Melville queue
  133. Boyer-Moore algorithm
  134. Double-array trie
  135. GSAT
  136. Scaling Dijkstra's algorithm
  137. Count-Min Sketch
  138. Subset construction

Back