Algorithms Cheatsheet

Cheatsheet Content

### Big O Notation - **O(1) - Constant Time:** Operations don't depend on input size. E.g., array element access. - **O(log n) - Logarithmic Time:** Reduces problem size by a constant factor. E.g., binary search. - **O(n) - Linear Time:** Time grows proportionally with input size. E.g., linear search. - **O(n log n) - Log-linear Time:** Common in efficient sorting algorithms. E.g., merge sort, quicksort. - **O(n^2) - Quadratic Time:** Nested loops. E.g., bubble sort, insertion sort. - **O(2^n) - Exponential Time:** Brute-force solutions. E.g., traveling salesman (naive). - **O(n!) - Factorial Time:** Extremely slow. E.g., permutations. #### Common Growth Rates $O(1) ### Sorting Algorithms #### 1. Bubble Sort - **Time Complexity:** Worst: $O(n^2)$, Avg: $O(n^2)$, Best: $O(n)$ - **Space Complexity:** $O(1)$ - **Concept:** Repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. #### 2. Selection Sort - **Time Complexity:** Worst: $O(n^2)$, Avg: $O(n^2)$, Best: $O(n^2)$ - **Space Complexity:** $O(1)$ - **Concept:** Finds the minimum element from the unsorted part and puts it at the beginning. #### 3. Insertion Sort - **Time Complexity:** Worst: $O(n^2)$, Avg: $O(n^2)$, Best: $O(n)$ - **Space Complexity:** $O(1)$ - **Concept:** Builds the final sorted array (or list) one item at a time. It iterates through the input elements and removes one element per iteration, finds the place within the sorted list, and inserts it there. #### 4. Merge Sort - **Time Complexity:** Worst: $O(n \log n)$, Avg: $O(n \log n)$, Best: $O(n \log n)$ - **Space Complexity:** $O(n)$ - **Concept:** Divide and Conquer. Divides an unsorted list into n sublists, each containing one element, then repeatedly merges sublists to produce new sorted sublists until there is only one sublist remaining. #### 5. Quick Sort - **Time Complexity:** Worst: $O(n^2)$, Avg: $O(n \log n)$, Best: $O(n \log n)$ - **Space Complexity:** $O(\log n)$ (average for recursion stack) - **Concept:** Divide and Conquer. Picks an element as a pivot and partitions the array around the picked pivot. #### 6. Heap Sort - **Time Complexity:** Worst: $O(n \log n)$, Avg: $O(n \log n)$, Best: $O(n \log n)$ - **Space Complexity:** $O(1)$ - **Concept:** Uses a binary heap data structure. It turns the input array into a max heap, then repeatedly extracts the maximum element and rebuilds the heap. ### Searching Algorithms #### 1. Linear Search - **Time Complexity:** Worst: $O(n)$, Avg: $O(n)$, Best: $O(1)$ - **Concept:** Checks each element in the list sequentially until a match is found or the list ends. #### 2. Binary Search - **Time Complexity:** Worst: $O(\log n)$, Avg: $O(\log n)$, Best: $O(1)$ - **Prerequisite:** The list must be sorted. - **Concept:** Repeatedly divides the search interval in half. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. ### Data Structures Overview #### 1. Arrays - **Concept:** Fixed-size collection of elements of the same data type, stored in contiguous memory locations. - **Access:** $O(1)$ by index. - **Insertion/Deletion:** $O(n)$ (if not at end). #### 2. Linked Lists - **Concept:** Collection of nodes where each node contains data and a reference (link) to the next node in the sequence. - **Types:** Singly, Doubly, Circular. - **Access:** $O(n)$. - **Insertion/Deletion:** $O(1)$ (if position is known). #### 3. Stacks (LIFO) - **Concept:** Last In, First Out. Operations: `push` (add), `pop` (remove), `peek` (view top). - **Time Complexity:** All $O(1)$. #### 4. Queues (FIFO) - **Concept:** First In, First Out. Operations: `enqueue` (add), `dequeue` (remove), `front` (view front). - **Time Complexity:** All $O(1)$. #### 5. Trees - **Concept:** Hierarchical data structure with a root node and children nodes. - **Binary Tree:** Each node has at most two children. - **Binary Search Tree (BST):** Left child = children; min-heap: parent ### Graph Algorithms #### 1. Breadth-First Search (BFS) - **Concept:** Explores all the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. Uses a queue. - **Time Complexity:** $O(V+E)$ (V = vertices, E = edges). - **Applications:** Shortest path on unweighted graphs, connectivity. #### 2. Depth-First Search (DFS) - **Concept:** Explores as far as possible along each branch before backtracking. Uses a stack (or recursion). - **Time Complexity:** $O(V+E)$. - **Applications:** Cycle detection, topological sorting, connected components. #### 3. Dijkstra's Algorithm - **Concept:** Finds the shortest paths between nodes in a graph, from a single source node to all other nodes, where edge weights are non-negative. Uses a min-priority queue. - **Time Complexity:** $O(E \log V)$ or $O(E + V \log V)$ with a Fibonacci heap. - **Applications:** GPS navigation, network routing. #### 4. Bellman-Ford Algorithm - **Concept:** Finds shortest paths from a single source vertex to all other vertices in a weighted digraph. Can handle negative edge weights and detect negative cycles. - **Time Complexity:** $O(VE)$. - **Applications:** Network routing (e.g., RIP protocol). #### 5. Floyd-Warshall Algorithm - **Concept:** Finds shortest paths between all pairs of vertices in a weighted graph. Can handle negative edge weights, but not negative cycles. - **Time Complexity:** $O(V^3)$. - **Applications:** Finding transitive closure, shortest paths in dense graphs. #### 6. Minimum Spanning Tree (MST) - **Concept:** A subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. - **Prim's Algorithm:** Builds an MST by adding edges one by one into a growing tree. Uses a min-priority queue. $O(E \log V)$ or $O(E + V \log V)$. - **Kruskal's Algorithm:** Builds an MST by adding edges in increasing order of weight, as long as they don't form a cycle. Uses a Disjoint Set Union (DSU) data structure. $O(E \log E)$ or $O(E \log V)$. ### Dynamic Programming (DP) - **Concept:** Method for solving complex problems by breaking them down into simpler subproblems. It stores the results of subproblems to avoid recomputing them (memoization or tabulation). - **Characteristics:** 1. **Optimal Substructure:** Optimal solution to the problem contains optimal solutions to subproblems. 2. **Overlapping Subproblems:** The same subproblems are solved multiple times. - **Approach:** - **Memoization (Top-down):** Recursive solution with caching. - **Tabulation (Bottom-up):** Iterative solution building up from base cases. - **Example:** Fibonacci sequence, Knapsack problem, Longest Common Subsequence. #### Example: Fibonacci (Tabulation) ```python def fibonacci(n): if n ### Greedy Algorithms - **Concept:** Makes the locally optimal choice at each stage with the hope of finding a global optimum. It does not always yield the globally optimal solution. - **Characteristics:** 1. **Greedy Choice Property:** A globally optimal solution can be arrived at by making a locally optimal (greedy) choice. 2. **Optimal Substructure:** Similar to DP. - **Applications:** Activity selection problem, Huffman coding, Kruskal's/Prim's algorithms for MST. #### When to Use Greedy vs. DP - **Greedy:** If a problem has the greedy choice property and optimal substructure, a greedy algorithm *might* work. Simpler and often faster. - **DP:** If optimal substructure exists but the greedy choice property does not (i.e., making a local optimal choice doesn't guarantee a global optimum), DP is usually required. ### Backtracking - **Concept:** Algorithmic technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point of time (backtracking) and trying other alternatives. - **Applications:** N-Queens problem, Sudoku solver, finding all permutations/combinations. #### General Structure ```python def solve(current_state): if is_solution(current_state): add_to_results(current_state) return for choice in possible_choices(current_state): make_choice(current_state, choice) solve(current_state) # Recursive call undo_choice(current_state, choice) # Backtrack ``` ### Divide and Conquer - **Concept:** Algorithmic paradigm that solves a problem by: 1. **Divide:** Breaking the problem into smaller subproblems of the same type. 2. **Conquer:** Solving these subproblems recursively. 3. **Combine:** Combining the solutions of the subproblems to solve the original problem. - **Characteristics:** Subproblems are independent. - **Applications:** Merge Sort, Quick Sort, Binary Search, Strassen's matrix multiplication. #### Master Theorem (for recurrence relations like $T(n) = aT(n/b) + f(n)$) - **Case 1:** If $f(n) = O(n^{\log_b a - \epsilon})$ for some $\epsilon > 0$, then $T(n) = \Theta(n^{\log_b a})$. - **Case 2:** If $f(n) = \Theta(n^{\log_b a} \log^k n)$ for $k \ge 0$, then $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$. - **Case 3:** If $f(n) = \Omega(n^{\log_b a + \epsilon})$ for some $\epsilon > 0$, AND $af(n/b) \le cf(n)$ for some constant $c ### Complexity Classes #### 1. P (Polynomial Time) - **Concept:** Class of decision problems solvable in polynomial time by a deterministic Turing machine. Problems for which a fast (polynomial time) algorithm exists. - **Examples:** Sorting, searching, shortest path. #### 2. NP (Non-deterministic Polynomial Time) - **Concept:** Class of decision problems for which a given solution (or certificate) can be verified in polynomial time by a deterministic Turing machine. Problems where it's easy to check a solution, but hard to find one. - **Examples:** Satisfiability (SAT), Traveling Salesman Problem (decision version), Subset Sum. - **P vs NP:** One of the seven Millennium Prize Problems. It is unknown whether P = NP. #### 3. NP-Complete (NPC) - **Concept:** Problems in NP to which every other problem in NP can be reduced in polynomial time. If an NP-complete problem can be solved in polynomial time, then all problems in NP can be solved in polynomial time (P=NP). These are considered the "hardest" problems in NP. - **Examples:** Boolean Satisfiability (SAT), Clique Problem, Vertex Cover, 3-SAT. #### 4. NP-Hard - **Concept:** Problems that are "at least as hard as" the hardest problems in NP. A problem H is NP-hard if for every problem L in NP, there is a polynomial-time reduction from L to H. NP-hard problems do not necessarily have to be in NP (i.e., they don't have to be decision problems, or verifiable in polynomial time). - **Examples:** Traveling Salesman Problem (optimization version), Halting Problem.