Skip to content

Instantly share code, notes, and snippets.

@ASRagab
Last active May 10, 2024 21:16
Show Gist options
  • Save ASRagab/8e158a6f7fb4351b0289fcc86d6f9f1f to your computer and use it in GitHub Desktop.
Save ASRagab/8e158a6f7fb4351b0289fcc86d6f9f1f to your computer and use it in GitHub Desktop.
Algos and Data Structures

Topics

Algos

  1. Baby Gin Problem
  2. Lexicographic–Order
  3. Johonson-Trotter
  4. Minimum-exchange Requirement
  5. Knapsack Problem and Fractional Knapsack Method
  6. Huffman coding
  7. Change Reducing Problem
  8. Meeting Room Scheduling
  9. Divide and Conquer
  10. Merge Sort
  11. Quick sort
  12. Hoare Partition
  13. Lomuto Partition
  14. Binary Search
  15. Power Set
  16. Backtracking
  17. Maze Finding
  18. State Space Tree
  19. 8-Queens Problem
  20. Power Set
  21. Disjoint Sets
  22. Expression of Linked List
  23. Minimum Spanning Tree
  24. Prim Algorithm
  25. Kruskal Algorithm
  26. Shortest Path
  27. Dijkstra Algorithm
  28. Bellman-Ford Algorithm
  29. Floyd-Warshall Algorithm
  30. Karp–Rabin
  31. KMP(Knuth-Morris-Pratt)
  32. Boyer-Moore
  33. Compression
  34. Run-Length Encoding
  35. Huffman Coding
  36. Lampel-Ziv-Welch Encoding
  37. Arithmetic Coding
  38. Fibonacci Number
  39. Pigeon Hole Principle
  40. Memoization
  41. Binomial Theorem
  42. Pascal's Triangle
  43. Search of State Space Tree
  44. Pruning (Backtracking)
  45. Best-First Search
  46. Dynamic Programming
  47. Longest Increasing Sequence
  48. All Pairs Shortest Path
  49. Weighted directed graph
  50. Floyd-Warshall Algorithm
  51. Traveling Salesman Problem
  52. Vertex Cover
  53. Independence Set
  54. Clique
  55. Graph Coloring
  56. Set Cover
  57. Longest Path
  58. Hamiltonian Cycle
  59. Bin Packing
  60. Job Scheduling
  61. Approximation Algorithm
  62. Simulated Annealing
  63. GCD
  64. Euclid Algorithm
  65. LCM

Data Structures


Sequential

Array-Like

  1. Bit array
  2. Bit field
  3. Bitboard
  4. Bitmap
  5. Circular buffer
  6. Control table
  7. Image
  8. Dope vector
  9. Dynamic array
  10. Gap buffer
  11. Hashed array tree
  12. Heightmap
  13. Lookup table
  14. Matrix
  15. Parallel array
  16. Sorted array
  17. Sparse matrix
  18. Iliffe vector
  19. Variable-length array
  20. Jagged Arrays

List-Like

  1. Doubly linked list
  2. Array list
  3. Linked list
  4. Self-organizing list
  5. Skip list
  6. Unrolled linked list
  7. VList
  8. Conc-Tree list
  9. Xor linked list
  10. Zipper
  11. Doubly connected edge list
  12. Difference list
  13. Free list
  14. Circular Linked List

Tree-Like

Binary Trees

  1. AA tree
  2. AVL tree
  3. Binary search tree
  4. Binary tree
  5. Cartesian tree
  6. Left-child right-sibling binary tree
  7. Order statistic tree
  8. Pagoda
  9. Randomized binary search tree
  10. Red–black tree
  11. Rope
  12. Scapegoat tree
  13. Self-balancing binary search tree
  14. Splay tree
  15. T-tree
  16. Tango tree
  17. Threaded binary tree
  18. Top tree
  19. Treap
  20. WAVL tree
  21. Weight-balanced tree

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
  11. AList

Heaps

  1. Heap
  2. Binary heap
  3. Weak heap
  4. Binomial heap
  5. Fibonacci heap
  6. AF-heap
  7. Leonardo Heap
  8. 2-3 heap
  9. Soft heap
  10. Pairing heap
  11. Leftist heap
  12. Treap
  13. Beap
  14. Skew heap
  15. Ternary heap
  16. D-ary heap
  17. Brodal queue

Trees

  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
  10. X-fast trie
  11. Y-fast trie
  12. Merkle Tree
  13. Ctrie

Multiway Trees

  1. Ternary tree
  2. K-ary tree
  3. And–or tree
  4. (a,b)-tree
  5. Link/cut tree
  6. SPQR-tree
  7. Spaghetti stack
  8. Disjoint-set data structure
  9. Fusion tree
  10. Enfilade
  11. Exponential tree
  12. Fenwick tree
  13. Van Emde Boas tree
  14. Rose tree

Space-Partitioning Trees

  1. Segment tree
  2. Interval tree
  3. Range tree
  4. Bin
  5. K-d tree
  6. Implicit k-d tree
  7. Min/max k-d tree
  8. Relaxed k-d tree
  9. Adaptive k-d 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. Bounding volume hierarchy
  27. BSP tree
  28. Rapidly exploring random tree

Application-specfic trees

  1. Abstract syntax tree
  2. Parse tree
  3. Decision tree
  4. Alternating decision tree
  5. Minimax tree
  6. Expectiminimax tree
  7. Finger tree
  8. Expression tree
  9. Log-structured merge-tree
  10. Lexicographic Search Tree

Hashes

  1. Bloom filter
  2. Count-Min sketch
  3. Distributed hash table
  4. Double Hashing
  5. Dynamic perfect hash table
  6. Hash array mapped trie
  7. Hash list
  8. Hash table
  9. Hash tree
  10. Hash trie
  11. Koorde
  12. Prefix hash tree
  13. Rolling hash
  14. MinHash
  15. Quotient filter
  16. Ctrie

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. Directed graph
  10. Directed acyclic graph
  11. Propositional directed acyclic graph
  12. Multigraph
  13. Hypergraph

Others

  1. Lightmap
  2. Winged edge
  3. Doubly connected edge list
  4. Quad-edge
  5. Routing table
  6. Symbol table
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment