dsa-cpp

Implementation of some data structures and algorithms

Data structures

• Dynamic array
• Linked list
• Queue
• Stack
• Binary heap
• Hash map
• Graph
• Union find
• Deterministic finite automaton
• Binary search tree

Algorithms

• Arrays
  • Sorting
    • Insertion sort
    • Selection sort
    • Bubble sort
    • Heap sort
    • Merge sort
    • Quick sort
    • Counting sort
    • Radix sort
  • Searching
    • Linear search
    • Binary search
  • Closest pair
  • Element uniqueness
  • Mode
  • Max/min
• Numbers
  • Fast exponentiation
  • Digit counter
  • GCD/LCM
• Graph
  • BFS
  • DFS
  • Dijkstra
  • Bellman-Ford
  • Floyd-Warshall
  • Prim
  • Kruskal
  • Topological sorting
  • Single source shortest path in DAGs
  • Connected components
  • Is bipartite check

---

TODO(optimistically):

• Add more tests
• Self-balancing BSTs
• Linear algebra(with adjustable field)
• Hash map with linear probing
• A*
• Cycle detection
• Edge classification
• DP
• Median in O(n) time
• PICK algorithm
• More sorting algorithms like Cocktail sort, Shell sort etc.