01What Are Algorithms?
An algorithm is a finite sequence of well-defined steps that takes an input and produces an output, solving a specified problem.
A good algorithm is correct (it produces the right output for every valid input), terminates (it finishes in finite time), and is efficient (it uses time and memory economically). Algorithms are independent of programming languages: the same procedure can be expressed in Python, C or pseudocode.
Correctness is usually argued with a loop invariant — a statement that is true before and after every iteration and that, at the end, implies the result is correct.
02Understanding Data Structures
A data structure is a way of organizing data in memory so that particular operations are efficient. No structure is best for everything; each trades the speed of some operations against others.
| Structure | Access by index | Search | Insert | Delete |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Linked list | O(n) | O(n) | O(1) at known node | O(1) at known node |
| Hash table | — | O(1) | O(1) | O(1) |
| Balanced binary search tree | — | O(log n) | O(log n) | O(log n) |
| Binary heap | — | O(n) | O(log n) | O(log n) for the minimum |
Hash table costs are averages; in the worst case, when many keys collide, operations degrade to O(n).
03Arrays and Linked Lists
An array stores elements in one contiguous block of memory, so the address of element i can be computed directly. That gives constant-time access and excellent cache behaviour, which is why numerical codes store vectors and matrices in arrays. Inserting in the middle, however, requires shifting every later element.
A linked list stores each element in a node that points to the next. Insertion and deletion at a known position only change pointers, but reaching the i-th element means following i links.
04Stacks and Queues
A stack is last-in, first-out (LIFO): push adds to the top, pop removes from the top. Stacks underlie function calls, expression evaluation and depth-first search. A queue is first-in, first-out (FIFO): enqueue at the back, dequeue at the front. Queues model waiting lines, buffer network packets and drive breadth-first search.
05Trees and Graphs
A tree is a hierarchy of nodes with a single root and no cycles. In a binary search tree, every node's left subtree holds smaller keys and its right subtree larger keys, so a search discards one subtree at each step. Self-balancing variants such as red–black trees and AVL trees keep the height logarithmic.
A graph is a set of vertices connected by edges, which may be directed or weighted. Graphs model road networks, social connections, dependencies between tasks and finite-element meshes. They are stored as adjacency lists (efficient for sparse graphs) or adjacency matrices (efficient for dense graphs).
06Sorting Algorithms
| Algorithm | Best | Average | Worst | Extra space | Stable |
|---|---|---|---|---|---|
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
Any sort that works only by comparing elements needs Ω(n log n) comparisons in the worst case. Counting sort and radix sort avoid this bound by exploiting the structure of integer keys.
07Searching Algorithms
Linear search examines items one by one and works on any list in O(n) time. Binary search requires sorted data and runs in O(log n):
function binary_search(A, target):
lo = 0; hi = length(A) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2 # avoids integer overflow
if A[mid] == target: return mid
if A[mid] < target: lo = mid + 1
else: hi = mid - 1
return NOT_FOUND
On graphs, breadth-first search finds shortest paths by number of edges, and Dijkstra's algorithm finds shortest paths when edge weights are non-negative.
08Time and Space Complexity
Complexity analysis counts how the resources an algorithm uses grow with input size n. Time complexity counts basic operations; space complexity counts additional memory. Analysts distinguish the worst case (a guarantee), the average case (expected behaviour under an input distribution) and the amortized cost (average over a sequence of operations, as with a dynamic array that occasionally doubles its capacity).
09Big O Notation
Big O gives an asymptotic upper bound: f(n) = O(g(n)) if there are constants c > 0 and n0 such that f(n) ≤ c·g(n) for all n ≥ n0. Big Omega (Ω) gives a lower bound, and Big Theta (Θ) a tight bound.
Big O ignores constant factors, which can matter in practice: for small inputs, an O(n²) insertion sort often beats an O(n log n) merge sort, which is why many library sorts switch to insertion sort for short runs.
10Algorithm Design Techniques
- Divide and conquer: split the problem, solve the parts recursively, combine (merge sort, fast Fourier transform).
- Dynamic programming: store solutions to overlapping subproblems instead of recomputing them (sequence alignment, shortest paths).
- Greedy algorithms: make the locally best choice at each step; correct only when the problem has the right structure (Kruskal's minimum spanning tree).
- Backtracking and branch-and-bound: explore candidate solutions systematically and prune branches that cannot succeed.
- Randomized algorithms: use random choices to achieve good expected performance (randomized quicksort, Monte Carlo methods).
11Applications in Scientific Computing
Scientific codes depend on specialized algorithms and structures: sparse matrix formats that store only non-zero entries, the fast Fourier transform that reduces an O(n²) transform to O(n log n), spatial trees that accelerate particle simulations, and graph partitioning that divides a mesh among processors. See computational science for how these fit into simulation.
12Algorithm Performance Evaluation
Asymptotic analysis predicts growth; measurement confirms real behaviour. Sound empirical evaluation:
- tests a range of input sizes and input types, including worst cases;
- repeats runs and reports variation, not a single timing;
- fixes and reports hardware, compiler and settings;
- compares against a strong, fairly tuned baseline;
- publishes code and inputs so results can be reproduced.
13Original Educational Examples
Example 1 — Counting pairs
To check whether any two numbers in a list sum to a target, a nested loop compares every pair in O(n²). Storing seen values in a hash set reduces this to O(n) expected time:
function has_pair_with_sum(values, target):
seen = empty set
for x in values:
if (target - x) in seen: return true
add x to seen
return false
Example 2 — Memoized Fibonacci
The naive recursive Fibonacci recomputes the same values exponentially many times. Remembering results turns it into a linear-time algorithm — the essence of dynamic programming.
memo = {0: 0, 1: 1}
function fib(n):
if n not in memo:
memo[n] = fib(n-1) + fib(n-2)
return memo[n]
Further reading
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). MIT Press.
- Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.
- Kleinberg, J., & Tardos, É. (2006). Algorithm Design. Pearson/Addison-Wesley.