a checklist for data structures and algorithms

dsa checklist.md

Searching and Sorting

---

• insertion sort
• selection sort
• bubble sort
• heap sort
• Quick Sort - in place
• Merge Sort
• Binary Search
• linear search
• jump search
• interpolation search

Graph algorithms

---

• Breadth First Search (BFS)
• Depth First Search (DFS)
• Shortest Path from source to all vertices Dijkstra
• Shortest Path from every vertex to every other vertex Floyd Warshall
• All pair shortest path Bellman Ford
• Minimum Spanning tree Prim
• Minimum Spanning tree Kruskal
• Topological Sort - kahn’s algorithm
• Johnson’s algorithm
• Articulation Points (or Cut Vertices) in a Graph
• Bridges in a graph - tarjans
• Strongly connected component - kosaraju, tarjan
• cycles in directed graph - DFS, tricolor dfs, topological sort
• cycles in undirected graph - dfs,

Dynamic programming

---

• Longest Common Subsequence
• Longest Increasing Subsequence
• Kadane’s Algorithm
• Edit Distance
• Minimum Partition
• Ways to Cover a Distance
• Longest Path In Matrix
• Subset Sum Problem
• Optimal Strategy for a Game
• 0-1 Knapsack Problem
• Assembly Line Scheduling
• Order Statistics
• KMP algorithm
• Rabin karp
• Z’s algorithm
• Aho Corasick String Matching
• Counting Sort
• Manacher’s algorithm: Part 1, Part 2 and Part 3

Number theory and Other Mathematical

---

• Sieve of Eratosthenes
• Sieve of Atkin
• Segmented Sieve
• Wilson’s Theorem
• Prime Factorisation
• Pollard’s rho algorithm
• Basic and Extended Euclidean algorithms
• Euler’s Totient Function
• Modular Exponentiation
• Modular Multiplicative Inverse
• Chinese remainder theorem Introduction
• Chinese remainder theorem and Modulo Inverse Implementation
• Counting Inversions
• Counting Inversions using BIT
• logarithmic exponentiation
• Square root of an integer - newton’s algorithm
• Heavy light Decomposition , this and this
• Matrix Rank
• Gaussian Elimination to Solve Linear Equations
• Hungarian algorithm

Geometrical and Network Flow Algorithms

---

• Convex Hull
• Graham Scan
• Line Intersection
• Interval Tree
• Matrix Exponentiation and this
• Maxflow Ford Furkerson Algo and Edmond Karp Implementation
• Min cut
• Stable Marriage Problem
• Hopcroft–Karp Algorithm for Maximum Matching
• Dinic’s algorithm

Data Structures

---

• linked list - single,
• double ended queue
• circular linked list
• stack
• binary search tree
• B+ tree
• Binary Indexed Tree or Fenwick tree
• Segment Tree (RMQ, Range Sum and Lazy Propagation)
• K-D tree (See insert, minimum and delete)
• Union Find Disjoint Set (Cycle Detection and By Rank and Path Compression)
• Tries
• Suffix array (this, this and this)
• Sparse table
• Suffix automata
• Suffix automata II
• LCA and RMQ