1. Reduce problem to smaller instance of same problem.
2. Solve smaller instance
3. Extend solution to obtain solution for original instance.

aka: Inductive / Incremental approach

Implementation: Can be done top-down or bottom-up.

3 Types

1. Decrease by a constant (e.g., one)

• Insertion sort
• TODO

2. Decrease by a constant factor (e.g., half)

• TODO

3. Variable-size decrease

• TODO

Example: Exponentiation

DAG

Directed graph with no directed cycles.

Confirming a DAG

DFS-based

1. Perform DFS traversal
2. Reverse order solves topological sorting problem.
3. If back edge encountered, not a DAG.

Source-Removal

Repeatedly identify and remove a source (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)

Topological Sort

Generating Permutations

Minimal Change Decrease by One

Satisfies problem, though eats a lot of space.

Johnson-Trotter

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
    while the last permutation has a mobile element do
        find its largest mobile element k
        swap k with the adjacent element k points to
        reverse direction of all elements \gt k
        add new permutation to the list

TODO Arrow notation.

A component k is said to mobile if:

• Its points to a number smaller than it.

Example: Order and Mobility

TODO

Example: Applying Johnson-Trotter

TODO

Time efficiency is O(n!) (can’t be helped), but O(1) space.

Generating Subsets

Observations:

• A set of n elements has 2^n subsets
• A binary integer of n digits has 2^n possible values.

Generating a subset cannot be done with a minimal change algorithm because ???.

Binary reflected Gray code

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.

• Every subset must differ from its immediate predecessors by either a addition or deletion of a single element.

Now, we’re moving onto decrease by ???.

Binary Search

Efficient search in a sorted array.

ALGORITHM BinarySearch(A[0..n \text{$-$} 1], K)
    // Iterative binary search
    // Input: TODO
    // Output: TODO
    l \leftarrow 0; r \leftarrow n \text{$-$} 1
    while l \le r do
        m \leftarrow TODO

Decrease by constant factor.

TODO Time efficiency

Thus, the practical time efficiency really comes down to the sorting algorithm.

Exponentiation by Squaring

TODO Copy

In the next chapter, we’ll learn to use the Master Theorem to avoid back substitution.

Fake Coin Problem

TODO naive

We can be even more efficient by splitting into three piles, which makes this a decrease by factor 3 algorithm, resulting in log_3 n

Now, we do variable-size-decrease algorithms.

Euclid’s Algorithm

The size decrease is variable.

TODO Already discussed in intro chapter. What is there to say?

Selection Problem

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.

TODO

s is a pivot.

Ideally, we split into half, though this won’t always happen (variable size decrease).

One-Directional Scan (Lomuto’s Partitioning Algorithm)

TODO

We’ll cover two-directional scan in the next chapter.

From here, we use quick selection to find the kth smallest element.

Tracing Quickselect (Partition-based Algorithm)

TODO

With two partitions, we already found the median, A[4] = 8

Efficiency

Efficiency depends on the partitioning.

Average Case (average split in the middle): TODO

Worst Case: TODO

If you use a more sophisticated algorithm that picks the pivot selection carefully, the worst-case can become O(n).

Binary Search Trees (BSTs)

Property: Inorder traversal of a BST produces a sorted list of keys.

We can make a variable-size-decrease algorithm like so:

ALGORITHM BTS(x,v)
// Searches for node with key equal to v in a BST rooted at node x.
TODO

Worst Case: Heavily unbalanced tree, C(n) = n

Average Case: C(n) \approx 2 \ln n \in \log_2 n

One-Pile Nim

TODO Description

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, TODO.

TODO Graph showing relationship.

We can see that the player moving first wins IIF n is not a multiple of five (more generally, m+1). The winning move is to take n \mod 5 chips every move.

Why: n \mod (m+1) = n \mod 5