Note — aka: Inductive / Incremental approach
Note — Implementation: Can be done top-down or bottom-up.
Example: Exponentiation
Directed graph with no directed cycles11. Used extensively to model scheduling, prerequisites, and dependency resolution..
Repeatedly identify and remove a source22. vertex with no incoming edges. and edges going out of it, until no vertex is left (is a DAG), or there is no source (isn’t a DAG). If all vertices are successfully removed, the order in which they are removed yields a topological sort.
The problem of finding an ordering of vertices in a DAG such that for every directed edge uv, vertex u comes before v in the ordering. This can be solved by either the DFS-based approach (reversing the pop order) or the Source-Removal approach.
Satisfies problem, though eats a lot of space. Each permutation is generated from its predecessor by swapping two adjacent elements.
We could also associate a direction with each component k in a permutation and save space.
ALGORITHM JohnsonTrotter(n)// Generates permutations with Johnson-Trotter algorithm// Input: Positive integer n// Output: List of all permutation of {1, ..., n}initialize first permutation with 1 2 ... n, all pointing leftwhile the last permutation has a mobile element dofind its largest mobile element kswap k with the adjacent element k points toreverse direction of all elements \gt kadd new permutation to the list
Arrow notation is used to represent the direction each number is looking.
A component k is said to be mobile if:
In \underleftarrow{3} \underleftarrow{1} \underrightarrow{2}, 3 is mobile because it points to 1, but 1 is not mobile, and 2 is not mobile.
Starting with \underleftarrow{1} \underleftarrow{2} \underleftarrow{3}:
Analysis — Time efficiency is O(n!) (can’t be helped, as there are n! permutations), but O(n) space for the state.
Observations:
Generating a subset cannot be done with a simple minimal change algorithm because changing an element might affect multiple bits.
A more challenging quesetion is whether there exists a minimal-change algortihm for generating bit strings so that every one of them differs from its immediate predecessor by a single bit.
The Binary Reflected Gray Code33. Widely used in error correction and digital communication systems. generates these strings recursively by taking the n-1 strings, reflecting them, and prepending 0s to the first half and 1s to the reflected half.
Now, we’re moving onto decrease by a constant factor.
Efficient search in a sorted array.
ALGORITHM BinarySearch(A[0..n-1], K)// Iterative binary search// Input: Sorted array A[0..n-1] and search key K// Output: Index of K in A, or -1 if not foundl \leftarrow 0; r \leftarrow n \text{$-$} 1while l \le r dom \leftarrow \lfloor(l \text{$+$} r) / 2\rfloorif K = A[m] return melse if K \lt A[m] r \leftarrow m \text{$-$} 1else l \leftarrow m \text{$+$} 1return -1
Searching for K=7 in A = [1, 3, 5, 7, 9].
Note — Decrease by constant factor.
Analysis — Time efficiency is O(\log n) worst-case. Space complexity is O(1).
Thus, the practical time efficiency really comes down to the sorting algorithm.
Compute a^n. If n is even, a^n = (a^{n/2})^2. If n is odd, a^n = (a^{(n-1)/2})^2 \times a. This decreases the exponent by a factor of 2 each step, resulting in \Theta(\log n) multiplications instead of n.
In the next chapter, we’ll learn to use the Master Theorem to avoid back substitution.
Given n identically looking coins, one is fake and lighter. Use a balance scale to find it.
Naive approach is weighing one against another, which is \Theta(n).
We can be even more efficient by splitting into three piles. Weigh pile 1 against pile 2. If they balance, the fake is in pile 3. Otherwise, the fake is in the lighter pile. This makes this a decrease by factor 3 algorithm, resulting in \Theta(\log_3 n) weighings.
Now, we do variable-size-decrease algorithms.
The size decrease is variable.
Euclid’s algorithm decreases the problem size from n to m \bmod n, which is a variable decrease at each step. Already discussed in intro chapter.
Input: Set S of n elements.
Output: kth smallest element of S.
Finding the minimum is pretty trivial.
Now, what if we want median?
One solution is to used a sorting-based algorithm and grab the median trivially.
An even more efficient solution uses array partitioning.
We choose a pivot element p, partition the array such that elements \le p are on the left, and elements \ge p are on the right. If the pivot ends up at position s, and s = k-1, we found the element. If s > k-1, we search the left part. If s < k-1, we search the right part.
s is a pivot.
Ideally, we split into half, though this won’t always happen (variable size decrease).
Lomuto’s algorithm maintains a pointer s that keeps track of the boundary between elements smaller than the pivot and the rest of the array. It scans from left to right, swapping elements smaller than the pivot to the front boundary.
Note — We’ll cover two-directional scan in the next chapter.
From here, we use quick selection to find the kth smallest element.
If we apply Lomuto’s partition and look for the median in an array of size n, we recursively partition the relevant half until the pivot lands exactly on index \lfloor n/2 \rfloor.
With two partitions, we already found the median, A[4] = 8
Analysis —
- Average Case: O(n) because we eliminate a constant fraction of the array on average each time.
- Worst Case: O(n^2) if the array is already sorted and we pick the first/last element as pivot, resulting in a size decrease of only 1 each time.
Note — If you use a more sophisticated algorithm that picks the pivot selection carefully, the worst-case can become O(n).
Property: Inorder traversal of a BST produces a sorted list of keys.
We can make a variable-size-decrease algorithm like so:
ALGORITHM BST_Search(x, v)// Searches for node with key equal to v in a BST rooted at node x.// Input: Root node x of a BST and a search key v// Output: Node with key v, or nullif x = null return nullif v = x.key return xelse if v \lt x.key return BST_Search(x.left, v)else return BST_Search(x.right, v)
Analysis —
- Worst Case: Heavily unbalanced tree, C(n) = n \in \Theta(n)
- Average Case: C(n) \approx 2 \ln n \in \Theta(\log n)
There is a pile of n chips. Two players take turns removing 1 to m chips. The player who removes the last chip wins.
Let’s work backwards from a winning state to figure out the winning (or losing) strategy.
We want to get in the state where the pile is m+1 and it’s the other person’s turn. At the point, any removal the person does guarantees your win.
Suppose the current state is 2m+1 and it’s your turn. At this state, removing m coins will get you in the aforementioned winning state.
Now, suppose the current state is 2m+2 and it’s your turn. At this state, you can remove m+1 coins (which is illegal if >m, wait). The general rule is you always leave a multiple of m+1 chips for your opponent.
We can see that the player moving first wins IIF n is not a multiple of m+1. The winning move is to take n \bmod (m+1) chips every move.
Why? — n \bmod (m+1) ensures the remaining pile is a multiple of m+1.