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

Back