An overview of algorithms, their importance in computer science, characteristics of good algorithms, and common algorithm design techniques.
Introduction to Algorithms – Study Notes
| Aspect | Description |
|---|---|
| Definition | A finite, well‑defined sequence of steps that transforms an input into an output. |
| Key Properties | • Finiteness – must terminate. • Determinism – each step is unambiguous. • Input/Output – operates on given data and produces results. • Effectiveness – every operation is basic enough to be performed mechanically. |
| Analogy | Recipe for a dish, blueprint for a building, or a set of instructions for a robot. |
| Paradigm | Core Idea | Typical Problems |
|---|---|---|
| Brute Force | Try every possibility. | Small search spaces, verification. |
| Divide & Conquer | Split problem → solve sub‑problems → combine. | Merge sort, quicksort, binary search. |
| Greedy | Make locally optimal choice at each step. | Minimum spanning tree (Kruskal, Prim), Huffman coding. |
| Dynamic Programming | Break into overlapping sub‑problems; store results (memoization). | Shortest paths (Bellman‑Ford, Floyd‑Warshall), knapsack, edit distance. |
| Backtracking | Incrementally build solutions, backtrack on conflicts. | N‑Queens, Sudoku, subset sum. |
| Randomized | Use random choices to simplify or speed up. | Quickselect, Monte Carlo methods, randomized quicksort. |
| Recursive | Function calls itself with smaller input. | Tree traversals, factorial, Fibonacci (with memoization). |
| Class | Typical Example | Growth |
|---|---|---|
| O(1) | Access array element | Constant |
| O(log n) | Binary search | Logarithmic |
| O(n) | Linear scan | Linear |
| O(n log n) | Merge sort | Linearithmic |
| O(n²) | Bubble sort | Quadratic |
| O(2ⁿ) | Exhaustive subset search | Exponential |
| O(n!) | Permutation generation | Factorial |
| Symbol | Meaning |
|---|---|
| O(f(n)) | Upper bound (≤ c·f(n) for large n) |
| Ω(f(n)) | Lower bound (≥ c·f(n) for large n) |
| Θ(f(n)) | Tight bound (both O and Ω) |
| **o |