Instance Simplification¹1. For example, simplifying a graph or transforming an array into a sorted array.: Transform to simpler instance of same problem.

Representation Change²2. e.g., representing a polynomial by its coefficients vs. its roots, or storing elements in an AVL tree vs. a list.: Different representation of same instance.

Problem Reduction: Transform a problem into a different problem for which an algorithm is already known.

More on Presorting

Sorting is important for lots of algorithms, which means the efficiency of the sort is super important.

Aside — Factoid: The fastest comparison sorting algorithm in the world is O(n \log n)

Taxonomy of Searching Algorithms

Binary Search Tree

Suppose we implement a dictionary with a BST.

• Searching: Straightforward
• Insertion: Search for key, insert where search terminate.
• Deletion: Three cases
  1. Delete key at leaf (simple)
  2. Delete key at node with single child (easy, just connect child to parent)
  3. Delete key at node with two children (harder, replace with inorder successor)

Recall — Efficiency depends on tree’s height.

Efficiency:

• All 3 operations have worst-case O(n) and avg-case O(\log n)

Recall — BST works worst on unbalanced trees. This is problematic if our operations gradually make our tree worse.

Solutions:

• AVL
• red-black
• 2-3
• 2-3-4
• B-trees

Binary Balanced Tree

AVL Trees

AVL Tree: BST in which, for every node, balance factor is at most 1.

• Balance Factor³3. left height - right height.: Difference between height of left and right subtrees.

Note — Height of empty tree defined as -1.

Balance Factor Examples:

• 0 : Both same
• -1 : Right subtree is heavier
• 1 : Left subtree is heavier

Rotations

When adding a new node to a BST, we can balance the addition via one of the four rotations.

1. Single Right Rotation (LL): Applied when left child is left-heavy.
2. Single Left Rotation (RR): Applied when right child is right-heavy.
3. Double Left-Right Rotation (LR): Applied when left child is right-heavy. It’s a left rotation on the child followed by a right rotation on the parent.
4. Double Right-Left Rotation (RL): Applied when right child is left-heavy. It’s a right rotation on the child followed by a left rotation on the parent.

Analysis — AVL Trees guarantee \Theta(\log n) time for search, insertion, and deletion.

Multiweight Balanced Tree

Multiweight Search Trees

MST is a search tree that allows more than one key in the same node of the tree.

• Still must follow search key properties.

Note — Lets us overcome some of the issues with binary search trees.

2-3 Tree

Search tree that may have 2-nodes and 3-nodes.

• Must be height-balanced (all leaves on same level).
• Constructed by successive insertion of keys given, following rules.

Insertion

• Add nodes as usual, simply growing 2-nodes to 3-nodes.
• If you stop at a 3-node, replace it with two 2-nodes, promoting the middle value to be the parent.

Why? — Not as fast, but easier to keep balanced.

• In, you unbalance a binary tree when you add height to one path significantly more than other possible paths.
• On 2-3, you can only add height when creating a new root, which adds a unit of height to all paths simultaneously.

Analysis — Search, insertion, and deletion are \Theta (\log n)

Heaps and Heapsort

Heap: Binary tree with keys at its nodes (one key per node) such that it is essentially complete.

Definition — Essentially Complete: All levels full except possibly last level, where only some rightmost keys may be missing.

Note — Remember: This is a binary tree, not a binary search tree! The property is parents are bigger than children, so it’s ordered top-down, but not left-right.

Note — Important:

• Root is the largest element.
• Any subtree is also a heap.
• Easily represented as array.

Heap as Array

We can represent heaps as arrays by storing elements in level-order.

Note — Accesses:

• Left Child of Node j: 2j
• Right Child of Node j: 2j + 1
• Parent of Node: \lfloor j/2 \rfloor
• Parental nodes are in the first half of the array.

Priority Queue

Note — Heaps are really good at representing priority queues.

A data structure for maintaining a set of elements, each with an associated key (priority). The standard operations are insert, and extract maximum/minimum.

Heap Construction

Note — AVL and 2-3 we’ve done top-down, but heap we can do two methods.

Bottom-Up: Put everything in and then fix it.

Top-Down: Construct by successively inserting elements into an initially empty heap.

Note — Which is Better? Top-down is more straightforward, especially for inserting a new key; but bottom-up is more efficient.

Bottom-Up

1. Initialize structure with keys in order given.
2. Starting at last (rightmost) parental node, fix the heap rooted at it.
   • If not a heap, keep exchanging it with its largest child until it becomes one.
3. Repeat previous step for preceding parental node.

ALGORITHM HeapBottomUp(H[1..n])
    // Constructs a heap from elements of a given array
    // Input: An array H[1..n] of orderable items
    // Output: A heap H[1..n]
    for i \leftarrow \lfloor n/2 \rfloor down to 1 do
        k \leftarrow i; v \leftarrow H[k]
        heap \leftarrow false
        while not heap and 2*k \le n do
            j \leftarrow 2*k
            if j \lt n // there are two children
                if H[j] \lt H[j+1] j \leftarrow j \text{$+$} 1
            if v \ge H[j]
                heap \leftarrow true
            else
                H[k] \leftarrow H[j]; k \leftarrow j
        H[k] \leftarrow v

Analysis — Parental node at level i does at most 2(h-i) comparisons. Thus, efficiency of bottom-up construction \Theta(n).

Top-Down

1. Insert elemnt at last position in heap.
2. Compare with parent and exchange if needed.
3. Continue comparing new element with nodes up the tree.

Analysis — Although it looks more straightforward, efficiency ends up being O(n \log n).

Heapsort

Strategy:

1. Delete root (note the value).
2. Reconstruct heap so that root is max again.
3. Do step 1 again.

Algorithm:

1. Build heap
2. Remove root (exchange with last (rightmost) leaf).
3. Fix-up heap (excluding last leaf).
4. Repeat Steps 2 and 3 until only one node left.

ALGORITHM Heapsort(A[1..n])
    // Sorts an array using Heapsort
    // Input: Array A[1..n]
    // Output: Array A[1..n] sorted in nondecreasing order
    HeapBottomUp(A[1..n])
    for i \leftarrow n down to 2 do
        swap(A[1], A[i]) // remove root and place at the end
        // fix the heap of size i-1 (sifting down the new root)
        k \leftarrow 1; v \leftarrow A[1]; heap \leftarrow false
        while not heap and 2*k \le i \text{$-$} 1 do
            j \leftarrow 2*k
            if j \lt i \text{$-$} 1 and A[j] \lt A[j+1] j \leftarrow j \text{$+$} 1
            if v \ge A[j] heap \leftarrow true
            else A[k] \leftarrow A[j]; k \leftarrow j
        A[k] \leftarrow v

Analysis — Creation of heap is \Theta (n), root removal portion is O(n \log n), so efficiency class is \Theta( n \log n). Space complexity is O(1).

Problem Reduction

Solve problem by transforming it into differnt problem for which an algorithm is already available.

Note — To be of practical value, the combined time of the transformation and solving of the reduced problem should be smaller than solving the problem as by another method.

Examples:

• We could get lcm via gcd.
• Path counting in graphs using matrix multiplication.

Least Common Multiple

We know:

\text{lcm}(m,n) = \frac{m \times n}{\gcd(m,n)}

Thus, we could just use an efficient method like Euclid’s algorithm to quickly get LCM.

Counting Paths in a Graph

The number of paths of length k between vertex i and j in a graph is the element at position i,j in the k-th power of the adjacency matrix. We reduce path counting to matrix multiplication.