Algorithms 1

This course is about more than particular algorithms. The central idea is that algorithmic performance comes from structure: the structure of the problem, the recurrence, the data representation, and the invariant that makes correctness provable.

• Performance comes from structure — of the problem, the recurrence, and the data representation.
• Four things to be able to do: prove correctness by invariant, solve recurrences, pick a structure that improves an operation set, and argue tradeoffs.
• Every algorithm here has an invariant (why it is correct) and a recurrence or count (why it costs what it costs). Know both.

An algorithm is correct if it terminates and returns the right output for every valid input instance. In this course correctness carries as much weight as speed, and most marks are lost by asserting a bound rather than justifying it.

Asymptotic Notation

$f(n) \in O(g(n))$

Upper bound — $f$ grows no faster than $g$.

$f(n) \in \Omega(g(n))$

Lower bound — $f$ grows at least as fast as $g$.

$f(n) \in \Theta(g(n))$

Tight bound — both of the above.

$f(n) \in o(g(n))$

Strictly slower growth.

$f(n) \in \omega(g(n))$

Strictly faster growth.

Cost Models

• For comparison sorts, count key comparisons.
• Ignore fixed-cost arithmetic and control overhead when it only moves constant factors.
• Remember the hidden costs: cache behaviour, pointer chasing, hash computation, equality checks.

Loop Invariants

Where an algorithm contains a loop, correctness is usually proved by naming a property every iteration preserves.

1. Initialisation — true before the loop starts.
2. Maintenance — one iteration preserves it.
3. Termination — on exit, invariant plus stop condition imply correctness.

• Correct = terminates and right output on every valid input.
• $O$ upper, $\Omega$ lower, $\Theta$ tight; $o$ and $\omega$ are the strict versions.
• Comparison sorts are costed in key comparisons; constant factors and control overhead are ignored.
• Loop invariant proof has exactly three parts: initialisation, maintenance, termination. Termination is the invariant plus the negated loop guard.

Recurrences are how divide-and-conquer costs get expressed. Four methods appear in the course, and the exam expects you to pick the cheapest one that works.

Solving Methods

• Substitute and spot a pattern — fastest when the expansion is regular.
• Recursion tree — best when work per level is easy to total.
• Guess and verify — needs a candidate, then induction.
• Master theorem — only for the standard shape below.

Master Theorem

For a recurrence of the form

compare $f(n)$ against $n^{\log_b a}$, the total work done at the leaves of the recursion tree.

• If $f(n)$ is polynomially smaller, the recursive work dominates: $T(n) = \Theta(n^{\log_b a})$.
• If they are the same order, every level costs the same and you pick up a factor of $\log n$: $T(n) = \Theta(n^{\log_b a}\log n)$.
• If $f(n)$ is polynomially larger and the regularity condition $a\,f(n/b) \le c\,f(n)$ holds for some $c < 1$, the non-recursive work dominates: $T(n) = \Theta(f(n))$.

• Four methods: substitution, recursion tree, guess-and-verify, master theorem.
• Master theorem — for $T(n) = a\,T(n/b) + f(n)$, compare $f(n)$ with $n^{\log_b a}$: smaller → recursion dominates; equal → extra $\log n$; larger (plus regularity) → $f(n)$ dominates.
• Three to know cold: $2T(n/2)+\Theta(n) = \Theta(n\log n)$, $T(n/2)+\Theta(1) = \Theta(\log n)$, $2T(n/2)+\Theta(1) = \Theta(n)$.

These are $\Theta(n^2)$ algorithms and they still matter — insertion sort is what the good $\Theta(n \log n)$ sorts drop into once subarrays get small enough that a tight loop beats the recursion overhead.

Insertion Sort

Incremental algorithm: maintain a sorted prefix and insert the next key into the right place by shifting larger elements right.

• Worst and average case: $\Theta(n^2)$. Best case $\Theta(n)$ on already-sorted input.
• Stable and in-place.
• Very good for small arrays because the loop body is tight.

Canonical Invariant

At the start of iteration $j$, the prefix $A[1 \ldots j-1]$ is sorted and contains exactly the original elements from those positions.

Selection Sort

Repeatedly select the smallest remaining item and place it into the next position.

• Cost $\Theta(n^2)$ in every case — it scans the whole remaining array regardless of order.
• Usually not stable unless carefully adapted.
• Can reduce the number of writes compared with insertion sort.

• Both $\Theta(n^2)$ worst case, both in-place. Insertion sort is stable, selection sort is not.
• Insertion sort best case $\Theta(n)$ on sorted input — why it is the small-array fallback inside faster sorts.
• Selection sort best case is still $\Theta(n^2)$: it always scans the whole remainder. It does fewer writes.
• Insertion sort invariant: at the start of iteration $j$, $A[1 \ldots j-1]$ is sorted and holds exactly those original elements.

Merge Sort

Classic divide-and-conquer: split in half, recursively sort both halves, then merge.

• Stable: yes.
• Guaranteed worst case $\Theta(n \log n)$ — no bad inputs.
• Memory behaviour matters: textbook merge sort uses extra space; the slides note bottom-up merge sort can be in-place.

Quicksort

Partition around a pivot, then recursively sort the two sides.

• Best case: balanced split every time, $\Theta(n \log n)$.
• Any constant-ratio split still gives $\Theta(n \log n)$ — a 99:1 split is asymptotically fine.
• Worst case: constant-and-rest split every time, $\Theta(n^2)$.
• Expected case $\Theta(n \log n)$ with sensible or random pivots.
• In-place in the standard array partition variants; not stable in that form.

Partition Correctness

The slides prove PARTITION with the invariant that elements left of the boundary $i$ are $\le$ pivot, elements between $i+1$ and $j-1$ are $>$ pivot, and the pivot itself is preserved at the end until the final swap.

Pivot Strategy Tradeoffs

• Naive last or first element — vulnerable to sorted or adversarial input.
• Random input shuffling — makes all orderings roughly equally likely.
• Random pivot — removes the dependence on input order.
• Median-of-three — lowers the probability of an extreme pivot.
• Three-way partition — important when many duplicate keys occur.
• Median-of-medians — deterministic good pivot, stronger worst-case guarantee, larger constants.

• Merge sort — $2T(n/2)+\Theta(n) = \Theta(n\log n)$ guaranteed, stable, usually not in-place.
• Quicksort — expected $\Theta(n\log n)$, worst $\Theta(n^2)$, in-place, not stable. Any constant-ratio split is still $\Theta(n\log n)$.
• PARTITION invariant: left of $i$ is $\le$ pivot, from $i+1$ to $j-1$ is $>$ pivot, pivot swapped into place at the end.
• Pivot choices, weakest to strongest: fixed → shuffle → random → median-of-three → median-of-medians. Three-way partition for many duplicates.

A binary heap is a semi-structured array representation of a nearly-complete binary tree.

Heap Properties

1. Structural — complete except possibly the bottom level, which fills left to right.
2. Ordering — in a max-heap, a parent key is at least each child key; symmetrically for min-heaps.

Array Mapping

The tree needs no pointers because position encodes structure:

Main Operations

• REHEAPIFY — $O(\log n)$.
• FULL-HEAPIFY — $\Theta(n)$, not $\Theta(n \log n)$.
• EXTRACT-MAX or EXTRACT-MIN — $O(\log n)$.
• PEEK — $O(1)$.
• INSERT, key increase and decrease — $O(\log n)$.

Heapsort

1. Build a max-heap from the array in $\Theta(n)$.
2. Repeatedly swap the root with the final item in the heap region.
3. Shrink the heap by one and reheapify the root.

Total cost $O(n \log n)$. It is in-place but not stable.

• Two properties: structural (complete, fills left to right) and ordering (parent $\ge$ children in a max-heap).
• Array mapping: $\mathrm{LEFT}(i)=2i$, $\mathrm{RIGHT}(i)=2i+1$, $\mathrm{PARENT}(i)=\lfloor i/2 \rfloor$ — no pointers needed.
• FULL-HEAPIFY is $\Theta(n)$, not $\Theta(n\log n)$. Most nodes are near the bottom and cheap to fix. This is the single most examined trap in the topic.
• PEEK $O(1)$; reheapify, extract and insert all $O(\log n)$.
• Heapsort: build max-heap $\Theta(n)$, then repeatedly swap-root-and-shrink. $O(n\log n)$, in-place, not stable.

Comparison sorting has an $\Omega(n \log n)$ lower bound — a decision tree with $n!$ leaves has height at least $\log_2(n!) = \Omega(n \log n)$. To beat it you must stop comparing and start using structure in the keys themselves.

Counting Sort

For keys drawn from a bounded integer range $[0 \ldots k]$.

• Time $\Theta(n + k)$ — linear only while $k = O(n)$.
• Stable, provided the output fill runs right to left as in CLRS and the slides.
• Not comparison-based.
• Usually not in-place, because of the output array $B$ and the count array $C$.

Radix Sort

Sort by digits from least significant to most significant, using a stable sort at each pass.

where $d$ is the number of digits and $k$ is the digit range. Stability at each pass is what makes the earlier passes survive the later ones — with an unstable inner sort the algorithm is simply wrong.

Bucket Sort

For values uniformly distributed over a known interval such as $[0,1)$.

• Average case $\Theta(n)$ — under the uniformity assumption.
• Worst case $\Theta(n^2)$ if the buckets become highly uneven.

Stability

A stable sort preserves the relative order of items with equal keys. It matters directly for radix sort, and indirectly wherever a sort is applied on top of an earlier ordering.

• Comparison sorting is $\Omega(n\log n)$ — decision tree with $n!$ leaves. Beating it requires assumptions about the keys.
• Counting sort $\Theta(n+k)$, stable, not in-place. Linear only while $k = O(n)$.
• Radix sort $\Theta(d(n+k))$, least significant digit first, requires a stable inner sort or it is wrong.
• Bucket sort $\Theta(n)$ average under uniformity, $\Theta(n^2)$ worst.

The $i$th order statistic is the $i$th smallest element. The selection problem asks for it without fully sorting.

Quickselect

The same partition idea as quicksort, but recurse only into the side containing the target rank.

• Expected $\Theta(n)$; worst case with bad pivots $\Theta(n^2)$.
• Much faster in practice than sorting when only one rank is needed.

Median-of-Medians

Deterministic pivot selection guaranteeing a useful ratio split.

1. Group the elements in fives.
2. Sort each group and take its median.
3. Recursively select the median of those medians.
4. Use that as the pivot.

This guarantees at least about $3n/10 - 6$ elements on each side, so the recursion is

The two recursive terms sum to strictly less than $n$, which is exactly why the total collapses to linear.

Quicksort with Median-of-Medians

If distinct keys allow the true median to be used at every step, quicksort gets a guaranteed balanced split and therefore $\Theta(n \log n)$ worst-case time. The tradeoff is much larger constants — it is a proof device more than a practical sort.

• Quickselect — partition, recurse into one side only. Expected $\Theta(n)$, worst $\Theta(n^2)$.
• Median-of-medians — groups of five, medians of groups, recursively select their median, use as pivot. Guarantees roughly $3n/10$ either side.
• $T(n) = T(\lceil n/5\rceil) + T(7n/10+6) + \Theta(n) = \Theta(n)$; linear because $1/5 + 7/10 < 1$.
• Quicksort with MoM pivots is $\Theta(n\log n)$ worst case, but the constants make it impractical.

• Incremental — grow a partial solution; needs cheap local maintenance.
• Divide and conquer — independent subproblems.
• Dynamic programming — overlapping subproblems plus optimal substructure.
• Greedy — greedy-choice property plus optimal substructure.
• D&C against DP is decided by overlap, not by whether it recurses.

DP is for optimisation problems with optimal substructure and overlapping subproblems. Both conditions are required: without substructure the recurrence is invalid, without overlap you have gained nothing over plain recursion.

Canonical Workflow

1. Characterise the structure of an optimal solution.
2. Write a recurrence for the value of an optimal solution.
3. Compute the values by memoisation or bottom-up filling.
4. If needed, reconstruct the actual solution from the table.

Top-Down against Bottom-Up

Example Style

The slides use a rod-cutting and VM-hosting optimisation example. The naive recursive version is exponential because it recomputes the same suffix problems repeatedly; memoisation collapses it to polynomial time by making each distinct subproblem cost once.

• Needs both optimal substructure and overlapping subproblems.
• Workflow: characterise the optimal structure → write the value recurrence → memoise or tabulate → reconstruct if asked.
• Top-down solves only what is needed but uses the stack; bottom-up avoids the stack but may compute unused entries.
• Signal: the same parameter values recurring in the recursion tree.

A greedy algorithm picks one locally optimal move and commits to it immediately. That is only valid when local optimality is globally safe, which has to be proved, not assumed.

What Must Be True

1. There is a meaningful greedy first move.
2. There always exists an optimal solution that starts with that greedy move — the greedy-choice property.
3. After making that move, the remaining subproblem is itself optimally solvable — optimal substructure.

Good and Bad Examples

• Fractional bag-filling by value density — greedy works, because a fraction of the best item is always available.
• Rod cutting and VM hosting — greedy fails, because the locally best first cut can destroy global optimality.
• Activity selection — greedy works, because the earliest-finishing choice leaves the most room for later ones.

Activity Selection

After sorting activities by finishing time, repeatedly choose the earliest-finishing compatible activity. The goal is maximum cardinality, not maximum occupied time — a common misreading that produces a different and wrong algorithm.

• Requires the greedy-choice property (some optimal solution starts with the greedy move) and optimal substructure.
• Works: fractional bag-filling by density, activity selection by earliest finish time.
• Fails: rod cutting — the best first cut can destroy global optimality.
• Activity selection maximises the number of activities, not the time occupied.
• Prove it by exchange: swap an optimal solution's first move for the greedy one and show it is no worse.

Pointers

Pointers are runtime references to objects by base address. They are what make dynamic structures such as linked lists and trees possible. NIL denotes the absence of a target.

Stacks

LIFO structure supporting PUSH and POP. Arrays give bounded-capacity stacks easily; linked lists give unbounded ones cleanly.

Queues

FIFO structure, typically implemented with circular arrays or linked lists.

Linked Lists

• Singly linked — cheaper, but deletion and backward context are awkward.
• Doubly linked — easier deletion and bidirectional traversal, at the cost of an extra pointer per node.
• Cyclic variants simplify end cases by removing NIL from the ends.

Rooted Trees

Nodes may carry parent pointers, fixed or variable arity, and child lists. The choice of representation changes the complexity of the operations, which is the general lesson: representation is a performance decision, not a formatting one.

• Stack LIFO, queue FIFO; both do their core operations in $O(1)$.
• Singly linked is cheaper; doubly linked buys easy deletion and reverse traversal for one extra pointer; cyclic forms remove NIL end cases.
• Representation choice — parent pointers, arity, child lists — is what sets the operation costs.

A BST stores key and payload pairs so that every key in the left subtree is strictly smaller and every key in the right subtree is strictly larger.

Supported Operations

• SEARCH, INSERT, DELETE.
• MINIMUM, MAXIMUM.
• PREDECESSOR, SUCCESSOR.

Performance

• Expected cost on a random-shaped tree $O(\log n)$.
• Worst case $O(n)$, when the tree degenerates into a chain.

Key Structural Points

• No duplicate keys, if you want the classical clean guarantees.
• PREDECESSOR and SUCCESSOR need parent pointers in the textbook implementation.
• Deletion is the subtle operation: the zero-child, one-child and two-child cases all differ, and the two-child case replaces the node with its successor.

• BST property: left subtree strictly smaller, right subtree strictly larger.
• $O(\log n)$ expected on random shape, $O(n)$ worst case when it degenerates to a chain.
• Deletion has three cases — zero, one and two children; the two-child case promotes the successor.
• PREDECESSOR and SUCCESSOR need parent pointers in the textbook form.
• Sorted insertion order is the degenerate case, which is the whole motivation for balancing.

B-Trees

Designed for disk-based settings, where following a pointer can cost millions of CPU cycles. The goal is to minimise tree height, because height is the number of expensive accesses.

B-Tree of Minimum Degree T

• Non-root internal nodes store between $T-1$ and $2T-1$ keys.
• A node with $t$ keys has $t+1$ children.
• All leaves sit at the same depth.
• Separator keys partition the child key ranges.

Height is $O(\log_T N)$, hence $O(\log N)$ search, insert and delete.

B-Tree Insert and Delete

• Insert by splitting full nodes, ideally pre-emptively on the way down, so no second pass is needed.
• Delete by redistributing from siblings or merging with them, preserving minimum and maximum occupancy.
• The root is special: splitting it increases the height, and losing its last key reduces it. This is why B-trees stay perfectly balanced.

Red-Black Trees

RB trees are BSTs with colour constraints that enforce approximate balance.

Properties

1. Each node is red or black.
2. The root is black.
3. Leaves are black sentinel nodes.
4. A red node has black children — no two reds in a row.
5. Every path from a node down to its descendant leaves contains the same number of black nodes.

Together these bound the height at $2\log_2(n+1)$, giving $O(\log n)$ worst-case operations. Properties 4 and 5 are the load-bearing pair: equal black-height fixes a floor, and no-two-reds stops any path exceeding twice it.

2-3-4 Tree Isomorphism

The slides connect RB trees explicitly to B-trees of minimum degree 2 — 2-3-4 trees. This is conceptually important: a red node encodes a key fused into its black parent's node, so an RB tree is a 2-3-4 tree drawn with binary links.

Rotations

Local restructuring that preserves the global key order, used inside the balancing logic for RB insert and delete.

• B-trees minimise height because height counts disk accesses. Non-root nodes hold $T-1$ to $2T-1$ keys, a node with $t$ keys has $t+1$ children, all leaves at equal depth. Height $O(\log_T N)$.
• Insert by splitting full nodes on the way down; delete by redistributing or merging. Only root split and root collapse change the height.
• Red-black — root black, leaves black sentinels, no red node has a red child, equal black-height on every downward path. Height $\le 2\log_2(n+1)$, so $O(\log n)$ worst case.
• An RB tree is a 2-3-4 tree (B-tree of degree 2) in binary form: red nodes are keys fused into their black parent.
• Rotations restructure locally while preserving key order.

A priority queue maintains a dynamic set and supports repeated access to the extreme-priority item.

Operations

• MINIMUM and MAXIMUM
• EXTRACT-MIN and EXTRACT-MAX
• INSERT
• DECREASE-KEY and INCREASE-KEY

The heap wins on peeking at the extremum and on constant factors. An RB tree may be preferable when richer dictionary-like operations — search by arbitrary key, ordered traversal, predecessor and successor — are needed alongside the queue behaviour.

• Operations: peek, extract, insert, and increase or decrease key.
• Heap — peek $O(1)$, everything else $O(\log n)$. Better constants.
• RB tree — all $O(\log n)$, but also gives search, ordered traversal, predecessor and successor.
• Choose on what else you need, not on the queue operations alone.

Hash tables implement the dictionary operations INSERT, SEARCH and DELETE in expected near-constant time, provided the hash function and load-factor management behave.

Hashing Issues

• Range reduction — hash values usually need reducing modulo the table size.
• Performance — real hash functions can be expensive to compute.
• Collisions — unavoidable, by the pigeonhole principle.
• Entropy and selectivity — similar or low-entropy keys can cluster badly.

Chaining

Table entries point to linked lists. With load factor $\alpha = n / m$ for $m$ slots, operations take expected $O(1 + \alpha)$ time under simple uniform hashing.

Variants from the Slides

• Append, or replace an existing binding.
• Keep the lists sorted by key.
• Push on the head with tombstone-style logical deletion.
• Push on the head and delete from the list, giving stack-like behaviour per key.

Open Addressing

Store items directly in table slots and resolve collisions with a probe sequence.

Probe Schemes

Linear probing

Simple and cache-friendly, but suffers primary clustering — occupied runs grow and merge.

Quadratic probing

Avoids primary clustering; keys with the same initial slot still follow the same path, which is secondary clustering.

Double hashing

The best of the three: the step size itself depends on the key, so colliding keys diverge immediately.

Deletion in Open Addressing

You cannot simply clear a slot, because a later search would stop at the gap and miss items further along the probe sequence. A marker or tombstone is required.

Resizing

Manage both live keys and tombstones. Rehash into a larger, same-sized or smaller table depending on occupancy and marker count — a table full of tombstones needs rehashing even though it holds few keys.

• Dictionary operations in expected $O(1)$ — conditional on the hash function and the load factor, not free.
• Chaining — expected $O(1+\alpha)$ where $\alpha = n/m$.
• Open addressing — linear probing (primary clustering), quadratic probing (secondary clustering), double hashing (best; step depends on the key).
• Deletion needs tombstones — clearing a slot breaks later probe sequences.
• Resizing must account for tombstones as well as live keys.

• Guaranteed $\Theta(n\log n)$: merge sort, heapsort, quicksort with MoM pivots.
• Stable: insertion, merge, counting; radix if its inner sort is.
• In-place: insertion, selection, heapsort, quicksort.
• Both stable and guaranteed: merge sort — at the cost of memory.
• Both in-place and guaranteed: heapsort — at the cost of stability.

What Strong Answers Usually Include

• The right asymptotic bound, with best, worst and expected case clearly distinguished.
• The invariant or structural property that makes the algorithm correct.
• The recurrence, and the method used to solve it.
• The data-structure property that enables the runtime — not just a list of operations.
• The tradeoff: memory, stability, in-place behaviour, worst-case robustness, or constant factors.

Common Mistakes

• Claiming BUILD-HEAP is $\Theta(n \log n)$ rather than $\Theta(n)$.
• Forgetting that any constant-ratio quicksort split is still $\Theta(n \log n)$.
• Using DP where subproblems do not overlap, or greedy without proving the greedy-choice property.
• Treating BST average-case behaviour as though it were a worst-case guarantee.
• Forgetting tombstones in open-addressing deletion.
• Calling a sort stable without checking its behaviour on equal keys.

• Answer with: the bound (case-distinguished), the invariant, the recurrence and its method, the enabling structural property, and the tradeoff.
• Traps: BUILD-HEAP is $\Theta(n)$; constant-ratio quicksort splits are still $\Theta(n\log n)$; BST average case is not a guarantee; open addressing needs tombstones; check stability on equal keys.
• State why the structure forces the runtime, not just what the runtime is.