Algorithms & Data Structures

Overview

This skill covers the foundational principles of algorithmic thinking, drawn primarily from Donald Knuth's The Art of Computer Programming (TAOCP). It provides guidance on analyzing algorithm efficiency, understanding complexity classes, and choosing the right algorithmic approach for a given problem.

Canonical Reference

Volume	Title	Covers
TAOCP Vol. 1	Fundamental Algorithms	Data structures, mathematical foundations, information structures
TAOCP Vol. 2	Seminumerical Algorithms	Random numbers, arithmetic, floating-point
TAOCP Vol. 3	Sorting and Searching	Sorting, searching, comparison of methods
TAOCP Vol. 4A	Combinatorial Algorithms, Part 1	Combinatorial generation, backtracking, constraint satisfaction
TAOCP Vol. 4B	Combinatorial Algorithms, Part 2	Satisfiability, graph algorithms

Big-O Notation

Big-O describes the upper bound of an algorithm's growth rate as input size increases. It characterizes the worst-case behavior and allows comparison between algorithms independent of hardware.

Common Complexity Classes

Notation	Name	Example
O(1)	Constant	Hash table lookup, array index access
O(log n)	Logarithmic	Binary search, balanced BST lookup
O(n)	Linear	Linear search, single array traversal
O(n log n)	Linearithmic	Mergesort, Heapsort, efficient comparison sorts
O(n^2)	Quadratic	Bubble sort, insertion sort (worst case), nested loops
O(2^n)	Exponential	Recursive Fibonacci (naive), subset enumeration

Growth Rate Comparison

n        O(1)   O(log n)  O(n)     O(n log n)  O(n^2)      O(2^n)
1        1      0         1        0           1           2
10       1      3.3       10       33          100         1,024
100      1      6.6       100      664         10,000      ~1.27 x 10^30
1,000    1      10        1,000    10,000      1,000,000   ~1.07 x 10^301
10,000   1      13.3      10,000   133,000     100,000,000 (infeasible)

Space vs Time Tradeoffs

Every algorithm makes a tradeoff between how much memory it uses and how fast it runs. Key principles:

• Caching / Memoization: Use extra space to store computed results and avoid redundant work (trades space for time).
• In-place algorithms: Minimize space usage at the cost of potentially more complex logic or slower execution (trades time for space).
• Lookup tables: Precompute results and store them for O(1) access (trades space for time).
• Compression: Reduce space at the cost of encoding/decoding time (trades time for space).

Strategy	Space	Time	Example
Memoized recursion	O(n) extra	Avoids recomputation	DP Fibonacci
In-place sort	O(1) extra	May be slower	Heapsort vs Mergesort
Hash table	O(n) extra	O(1) average lookup	Two-sum problem
Bit manipulation	O(1) extra	Constant factor overhead	Flags, compact sets

Amortized Analysis

Amortized analysis averages the cost of operations over a sequence, even when individual operations may be expensive. It provides a tighter bound than worst-case analysis for data structures that occasionally restructure.

• Aggregate method: Total cost of n operations divided by n.
• Accounting method: Assign different charges to different operations; overcharges on cheap operations "pay" for expensive ones.
• Potential method: Define a potential function on the data structure state; amortized cost = actual cost + change in potential.

Example: Dynamic array (ArrayList) doubling. Individual insertions are O(1) amortized even though resizing copies all elements, because resizing happens infrequently (the cost of copying is spread across the insertions that preceded it).

Choosing Algorithms by Problem Type

Problem Type	Recommended Approach	Sub-Skill
Ordering elements	Comparison sort (Quicksort, Mergesort) or linear sort (Radix)	sorting-searching
Finding elements	Binary search, hash-based lookup	sorting-searching
Storing/retrieving structured data	Choose appropriate data structure by access pattern	data-structures
Shortest path / connectivity	Graph algorithms (BFS, DFS, Dijkstra)	graph-algorithms
Optimization with overlapping subproblems	Dynamic programming	dynamic-programming
Enumerating configurations / constraint solving	Backtracking, branch and bound	combinatorial
String matching	KMP, Rabin-Karp, suffix structures	sorting-searching
Scheduling / ordering dependencies	Topological sort	graph-algorithms
Minimum spanning tree	Prim's, Kruskal's	graph-algorithms
Subset/permutation generation	Combinatorial generation	combinatorial

Algorithm Analysis Checklist

When evaluating or selecting an algorithm:

1. Identify the problem class -- Is it a searching, sorting, graph, optimization, or enumeration problem?
2. Determine input constraints -- What is the expected input size? Are there special properties (sorted, sparse, bounded range)?
3. Analyze time complexity -- What is the worst-case, average-case, and best-case behavior?
4. Analyze space complexity -- How much auxiliary memory is required?
5. Consider stability and determinism -- Does order preservation matter? Is randomness acceptable?
6. Evaluate practical constants -- Two O(n log n) algorithms may differ significantly in constant factors and cache behavior.
7. Benchmark with real data -- Asymptotic analysis is a starting point; real-world performance depends on data distribution and hardware.

Best Practices

• Start with the simplest correct algorithm, then optimize if profiling shows a bottleneck.
• Know the standard library -- most languages provide well-optimized sorting, searching, and data structure implementations.
• Prefer algorithms with good average-case behavior for general use; consider worst-case guarantees for safety-critical systems.
• Understand amortized costs before concluding that an operation is "slow" based on a single invocation.
• Reference Knuth's TAOCP for rigorous analysis and historical context on any fundamental algorithm.