Algorithm Study Guide

📖 Core Concepts Algorithm: A finite, precise sequence of instructions that transforms an initial state & input into a correct output, then halts. Key Properties: Deterministic or randomized transition between well‑defined states. Termination after a finite number of steps. Heuristic vs. Algorithm: Heuristics are rule‑of‑thumb methods for ill‑defined problems; algorithms guarantee a correct answer for their defined problem class. Execution Model: State → (instruction) → Next state, repeating until a final state is reached. Representations: Natural language (ambiguous), pseudocode (clear, language‑independent), flowcharts (graphical), programming language (executable). Complexity: Time – asymptotic growth of steps, expressed with Big‑O (e.g., $O(n)$). Space – amount of extra memory beyond input, also expressed with Big‑O. 📌 Must Remember An algorithm must terminate; infinite loops are not algorithms. Big‑O describes upper‑bound growth; $O(n)$ means time grows linearly with input size $n$. $O(1)$ space means constant extra memory regardless of $n$. Divide‑and‑Conquer = split → solve sub‑problems → combine. Dynamic Programming = store overlapping sub‑problem results to avoid recomputation. Monte Carlo = correct answer with high probability; Las Vegas = always correct, runtime probabilistic. Structured programming constructs: sequence, conditional, loop (while‑do). 🔄 Key Processes Algorithm Execution Initialize state & input → evaluate current instruction → update state → repeat until halt. Divide‑and‑Conquer Divide the problem → Conquer each piece (often recursively) → Combine solutions. Dynamic Programming Identify overlapping sub‑problems → define recurrence → fill table (bottom‑up) or memoize (top‑down). Proof of Correctness (Induction) Base case: show correctness for smallest input. Inductive step: assume true for $k$, prove for $k+1$ (or for recursion depth). 🔍 Key Comparisons Algorithm vs. Heuristic Algorithm: guarantees correct result, finite steps. Heuristic: may be faster, no guarantee of optimality or correctness. Monte Carlo vs. Las Vegas Monte Carlo: bounded error probability, deterministic runtime. Las Vegas: always correct, runtime may vary (often expected polynomial). Pseudocode vs. Flowchart Pseudocode: textual, easy to modify, language‑agnostic. Flowchart: visual, great for seeing control flow, less precise for complex logic. ⚠️ Common Misunderstandings “Big‑O is the exact runtime” – it’s an asymptotic upper bound, not a precise count. “If an algorithm runs fast on my laptop, it’s efficient” – empirical speed depends on hardware; only formal analysis yields machine‑independent guarantees. “Randomized algorithms are unreliable” – Monte Carlo algorithms have provably high success probability; Las Vegas always succeed. 🧠 Mental Models / Intuition State Machine View: Picture the algorithm as a board game where each move (instruction) changes the board (state) until you reach the “win” square (output). Overlapping Sub‑Problems: Think of climbing a staircase where each step builds on the previous ones; storing each step’s cost prevents re‑climbing the same stairs. Randomized Algorithms: Imagine rolling a die to decide which path to explore; the probability analysis tells you you’ll likely find the treasure quickly. 🚩 Exceptions & Edge Cases Randomized algorithms may have worst‑case exponential time even if expected time is polynomial. Space complexity can change dramatically if the algorithm must keep the entire input (e.g., counting sort $O(n)$ space vs. in‑place quicksort $O(\log n)$). Heuristics can be exact for certain inputs; never assume they are always approximate. 📍 When to Use Which Choose Divide‑and‑Conquer when sub‑problems are independent and can be solved recursively (e.g., mergesort, quicksort). Choose Dynamic Programming when sub‑problems overlap and you can store intermediate results (e.g., shortest path, knapsack). Monte Carlo is ideal when an approximate answer is acceptable and you need guaranteed runtime (e.g., primality testing). Las Vegas is preferable when correctness is non‑negotiable but you can tolerate variable runtime (e.g., randomized quicksort). Pseudocode for exam explanations; flowchart when you need to visualize branching logic quickly. 👀 Patterns to Recognize Recursive call + combine step → likely a divide‑and‑conquer algorithm. Table‑filling or memoization → dynamic programming. “Repeat until success with probability ≥ p” → Monte Carlo pattern. “While loop with random choice of next state” → Las Vegas pattern. Linear scan with constant extra variables → $O(n)$ time, $O(1)$ space. 🗂️ Exam Traps Confusing $O(n)$ time with $O(1)$ space – watch the wording; space often includes input storage. Choosing “algorithm” for a heuristic description – if the method lacks guaranteed correctness, it’s a heuristic, not an algorithm. Assuming deterministic runtime for randomized algorithms – Monte Carlo runs in fixed time; Las Vegas does not. Misidentifying overlapping sub‑problems – if sub‑problems are independent, DP adds unnecessary overhead; divide‑and‑conquer is better. Neglecting termination – any proposed “algorithm” that can loop forever is invalid.