FoundationsData Structures & Algorithms
Algorithms
Summary of basic algorithms: Sorting, Searching, Graph, Dynamic Programming
Algorithms (Quick Summary)
1. Searching
- Linear Search: Searching one by one
O(n) - Binary Search: Data must be sorted, repeatedly divided in half
O(log n)
2. Sorting
- Bubble / Insertion / Selection Sort: Simple sorting, nested loops
O(n^2)(used in practice when data is very small) - Merge Sort: Divide and combine (Divide & Conquer), always
O(n log n)but takesO(n)space - Quick Sort: Random Pivot and partition, average
O(n log n), spaceO(log n), but worst caseO(n^2)
3. Graph Traversal (Graphs/Trees)
- BFS (Breadth-First Search): Broad search, spreads layer by layer using a Queue. Suitable for finding the Shortest Path on unweighted graphs.
- DFS (Depth-First Search): Deep search, dives to the end and backtracks using a Stack or Recursion. Suitable for solving mazes or cycle detection.
4. Shortest Path
- Dijkstra: Finds shortest path with positive weights
O(E log V)(when using a Priority Queue) - Bellman-Ford: Supports graphs with negative weights
O(VE) - Floyd-Warshall: Finds shortest path for all pairs of nodes
O(V^3)
5. Algorithmic Paradigms
- Greedy: Chooses the path that looks best currently (Local Optimum) hoping for the global best (e.g., Coin Change for some currencies, Dijkstra, Huffman Coding)
- Dynamic Programming (DP): Remembers subproblem results (Memoization/Tabulation) to avoid recalculating. Used for problems with Overlapping Subproblems (e.g., Fibonacci, Knapsack)