• Links and books
• Analyzing algorithms
• Sorting
  • Insertion sort
    • Correctness
    • Analysis
  • Merge Sort
    • Correctness
• Recurrences
  • Master Theorem
• Maximum-Subarray Problem
  • Description
  • Divide and Conquer
  • Improvement with Dynamic Programming
• Matrix multiplication
  • Naive Algorithm
  • Divide-and-Conquer algorithm
    • Pseudocode and analysis
  • Strassen’s Algorithm for Matrix Multiplication
    • Notes about Strassen
• Heaps and Heapsort
  • Heaps
    • Max-Heapify
    • Building a heap
  • Heapsort
  • Priority queues
    • Finding maximum element
    • Extracting maximum element
    • Increasing a value
    • Inserting into the heap
  • Summary
• More data structures
  • Stacks
  • Queues
  • Linked Lists
    • Search
    • Insertion
    • Deletion
    • Summary
  • Binary search trees
    • Querying a binary search tree
      • Searching
      • Maximum and minimum
      • Successor
    • Printing a binary search tree
      • Inorder
      • Preorder
      • Postorder
    • Modifying a binary seach tree
      • Insertion
      • Deletion
    • Summary
  • Summary
• Dynamic Programming
  • Top-down with memoization
  • Bottom-up
  • Rod cutting problem
    • Structural Theorem
    • Algorithm
    • Extended algorithm
  • When can dynamic programming be used?
  • Matrix-chain multiplication
    • Optimal substructure theorem
  • Longest common subsequence
    • Theorem
  • Optimal binary search trees
• Graphs
  • Representation
  • Traversing / Searching a graph
    • Breadth-First Search (BFS)
    • Depth-first search (DFS)
  • Classification of edges
  • Parenthesis theorem
  • White-path theorem
  • Topological sort
    • Lemma: When is a directed graph acyclic?
  • Strongly connected component
    • Lemma
    • Magic Algorithm
• Flow Networks
  • Ford-Fulkerson Method
    • Residual network
  • Cuts in flow networks
    • Net flow across a cut
    • Capacity of a cut
    • Minimum cut
    • Max-flow min-cut theorem
  • Time for finding max-flow (or min-cut)
  • Bipartite matching
    • Why does it work?
  • Edmonds-Kart algorithm
    • Lemma
• Data structures for disjoint sets
  • Application: Connected components
  • Implementation: Linked List
  • Implementation: Forest of trees
• Minimum Spanning Trees (MST)
  • Prim’s algorithm
    • Implementation
  • Kruskal’s algorithm
    • Implementation
  • Summary
• Shortest Path Problem
  • Problem variants
  • Bellman-Ford algorithm
    • Detecting negative cycles
  • Dijkstra’s algorithm
• Probabilistic analysis and randomized algorithms
  • Motivation
  • Probabilistic Analysis: The Hiring Problem
    • Lemma
    • Multiple Coin Flips
    • Solving the Hiring Problem
    • Bonus trivia
  • Birthday Lemma
  • Hash functions and tables
    • Hash tables
    • Collisions
    • Running times
    • Examples of Hash Functions
• Quick Sort
  • Why always n log n?
  • Linear time sorting
• Review of the course
  • Growth of functions
  • Sorting

Links and books

• Course homepage
• Introduction to Algorithms, Third edition (2009), T. Cormen, C. Lerserson, R. Rivest, C. Stein (book on which the course is based)
• The Art of Computer Programming, Donald Knuth (a classic)

Analyzing algorithms

We’ll work under a model that assumes that:

• Instructions are executed one after another
• Basic instructions (arithmetic, data movement, control) take constant O(1) time
• We don’t worry about numerical precision, although it is crucial in certain numerical applications

We usually concentrate on finding the worst-case running time. This gives a guaranteed upper bound on the running time. Besides, the worst case often occurs in some algorithms, and the average is often as bad as the worst-case.

Sorting

The sorting problem’s definition is the following:

• Input: A sequence of $n$ numbers $(a_1,a_2,\dots ,a_n)$
• Output: A permutation (reordering) $(a_1^{\prime },a_2^{\prime },\dots ,a_n^{\prime })$ of the input sequence in increasing order

Insertion sort

This algorithm works somewhat in the same way as sorting a deck of cards. We take a single element and traverse the list to insert it in the right position. This traversal works by swapping elements at each step.

1
2
3
4
5
6
7
8
9
10
11
12

def insertion_sort(A, n):
    # We start at 2 because a single element is already sorted.
    # The upper bound in range is exclusive, so we set it to n+1
    for j in range(2, n+1):
        key = A[j]
        # Insert A[j] in to the sorted sequence A[1..j-1]
        i = j-1
        while i > 0 and A[i] > key:
            # swap
            A[i+1] = A[i]
            i = i-1
        A[i+1] = key

Correctness

Using induction-like logic.

Loop invariant: At the start of each iteration of the “outer” for loop — the loop indexed by j — the subarray A[1, ..., j-1] consists of the elements originally in A[1, ..., j-1] but in sorted order.

We need to verify:

• Initialization: We start at j=2 so we start with one element. One number is trivially sorted compared to itself.
• Maintenance: We’ll assume that the invariant holds at the beginning of the iteration when j=k. The body of the for loop works by moving A[k-1], A[k-2] ansd so on one step to the right until it finds the proper position for A[k] at which points it inserts the value of A[k]. The subarray A[1..k] then consists of the elements in a sorted order. Incrementing j to k+1 preserves the loop invariant.
• Termination: The condition of the for loop to terminate is that j>n; hence, j=n+1 when the loop terminates, and A[1..n] contains the original elements in sorted order.

Analysis

• Best case: The array is already sorted, and we can do $\Theta \left(n\right)$
• Worst case: The array is sorted in reverse, so $j=t_j$ and the algorithm runs in $\Theta \left(n^2\right)$:

Merge Sort

Merge sort is a divide-and-conquer algorithm:

• Divide the problem into a number of subproblems that are smaller instances of the same problem
• Conquer the subproblems by solving them recursively. Base case: If the subproblems are small enough, just solve them by brute force
• Combine the subproblem solutions to give a solution to the original problem

Merge sort can be implemented recursively as such:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

def merge_sort(A, p, r):
    if p < r: # Check for base case
        q = math.floor((p + r) / 2) # Divide
                                    # q is the index at which we split the list
        merge_sort(A, p, q) # Conquer
        merge_sort(a, q+1, r) # Conquer
        merge(A, p, q, r) # Combine

def merge(A, p, q, r):
    n1 = q - p + 1 # Size of the first half
    n2 = r - q # Size of the second half
    let L[1 .. n1 + 1] and R[1 .. n2 + 1] be new arrays
    for i = 1 to n1:
        L[i] = A[p + i - 1]
    for j = 1 to n2:
        R[j] = A[q + j]
    L[n1 + 1] = infinity # in practice you could use sys.maxint
    R[n2 + 1] = infinity
    i = 1
    j = 1
    for k = p to r:
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1

In the merge function, instead of checking whether either of the two lists that we’re merging is empty, we can just add a sentinel to the bottom of the list, with value ∞. This works because we’re just picking the minimum value of the two.

This algorithm works well in parallel, because we can split the lists on separate computers.

Correctness

Assuming merge is correct, we can do a proof by strong induction on $n=r-p$.

• Base case, $n=0$: In this case $r=p$ so A[p..r] is trivially sorted.
• Inductive case: By induction hypothesis merge_sort(A, p, q) and merge_sort(A, q+1, r) successfully sort the two subarrays. Therefore a correct merge procedure will successfully sort A[p..q] as required.

Recurrences

Let’s try to provide an analysis of the runtime of merge sort.

• Divide: Takes contant time, i.e., $D\left(n\right)=\Theta \left(1\right)$
• Conquer: Recursively solve two subproblems, each of size $n/2$, so we create a problem of size $2T\left(n/2\right)$ for each step.
• Combine: Merge on an n-element subarray takes $\Theta \left(n\right)$ time, so $C\left(n\right)=\Theta \left(n\right)$

Our recurrence therefore looks like this:

Trying to substitue $T\left(n/2\right)$ multiple times yields $T\left(n\right)=2^{k}T\left(n/2^k\right)+kcn$. By now, a qualified guess would be that $T\left(n\right)=\Theta \left(n\log n\right)$. We’ll prove this the following way:

All-in-all, merge sort runs in $\Theta \left(n\log n\right)$, both in worst and best case.

For small instances, insertion sort can still be faster despite its quadratic runtime; but for bigger instances, merge sort is definitely faster.

However, merge sort is not in-place, meaning that it does not operate directly on the list that needs to be sorted, unlike insertion sort.

Master Theorem

Generally, we can solve recurrences in a black-box manner thanks to the Master Theorem:

The 3 cases correspond to the following cases in a recursion tree:

1. Leaves dominate
2. Each level has the same cost
3. Roots dominate

Maximum-Subarray Problem

Description

You have the prices that a stock traded at over a period of n consecutive days. When should you have bought the stock? When should you have sold the stock?

The naïve approach of buying at the all-time lowest and selling at the all-time highest won’t work, as the lowest price might occur after the highest.

We describe the problem as follows:

• Input: An array A[1..n] of price changes
• Output: Indices i and j such that A[i..j] has the greatest sum of any nonempty, contiguous subarray of A, along with the sum of the values in A[i..j]

Note that the array A could be price changes prices on each day, the two problems are equivalent (and can be converted into each other in linear time). In the first case, profit is sum(A[i..j]), while in the second the profit is A[j] - A[i]. We will be talking about this problem in the first form, with the price changes.

We can also decide to allow or disallow buying and selling on the same day, which would give us 0 profit. In other words, this would be disallowing empty maximum subarrays. We’ll first see a variant which disallows it, and then a variant which allows it.

Divide and Conquer

• Divide the subarray into two subarrays of as equal size as possible: Find the midpoint mid of the subarrays, and consider the subarrays A[low..mid] and A[mid+1..high]
  • This can run in $\Theta \left(1\right)$
• Conquer by finding maximum subarrays of A[low..mid] and A[mid+1..high]
  • Recursively solve two subproblems, each of size $n/2$, so $2T\left(n/2\right)$
• Combine: Find a maximum subarray that crosses the midpoint, and use the best solution out of the three (that is, left, midpoint and right).
  • The merge is dominated by find_max_crossing_subarray so $\Theta \left(n\right)$

The overall recursion is $T\left(n\right)=2T\left(n/2\right)+\Theta \left(n\right)$, so the algorithm runs in $\Theta \left(n\log n\right)$.

In pseudo-code the algorithm is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

def find_maximum_subarray(A, low, high):
    if high == low: # base case: only one element
        return (low, high, A[low])
    else:
        mid = math.floor((low + high)/2)
        (l_low, l_high, l_sum) = find_maximum_subarray(A, low, mid)
        (r_low, r_high, r_sum) = find_maximum_subarray(A, mid+1, high)
        (x_low, x_high, x_sum) = find_max_crossing_subarray(A, low, mid, high)

        # Find the best solution of the three:
        if l_sum >= r_sum and l_sum >= x_sum:
            return (l_low, l_high, l_sum)
        elif r_sum >= l_sum and r_sum >= x_sum:
            return (r_low, r_high, r_sum)
        else:
            return (x_low, x_high, x_sum)

def find_max_crossing_subarray(A, low, mid, high):
    # Find a maximum subarray of the form A[i..mid]
    l_sum = - infinity # Lower-bound sentinel
    sum = 0
    for (i = mid) downto low:
        sum += A[i]
        if sum > l_sum:
            l_sum = sum
            l_max = i

    # Find a maximum subarray of the form A[mid+1..j]
    r_sum = - infinity # Lower-bound sentinel
    sum = 0
    for j = mid to high:
        sum += A[j]
        if sum > r_sum:
            r_sum = sum
            r_max = j

    # Return the indices and the sum of the two subarrays
    return (l_max, r_max, l_sum + r_sum)

Improvement with Dynamic Programming

The divide-and-conquer $O\left(n\log n\right)$ algorithm can be improved to $O\left(n\right)$, which is optimal. This algorithm is known as Kadane’s algorithm. For the sake of simplicity, we won’t keep track of indices in this variant, but we could extend it to do so (see Wikipedia article). Also note that we will be looking at the variant of the problem which allows empty maximum subarrays (but it can be easily adapted to disallow it, see Wikipedia article).

1
2
3
4
5
6
7

def find_max_subarray(A: List[int]) -> int:
    best_sum = 0
    current_sum = 0
    for x in A:
        current_sum = max(0, current_sum + x)
        best_sum = max(best_sum, current_sum)
    return best_sum    

This is a “simple” example of dynamic programming, which we’ll talk more about later. It is “simple” because we don’t actually need memoization, as each subproblem only needs to be computed once. But it can still be useful to think of it in DP terms. We can describe the DP recursion as follows, where the $r$ array contains the sum of the maximum subarray ending at $j$ (or in terms of our stock market analogy, the profit made if we sell on day $j$):

Let’s try to get an intuitive sense for what the recursion says. To compute the maximum subarray ending at $j$, we can either extend the max subarray ending at $j-1$ to include day $j$, or if that makes us lose money, we can say that the best way to sell on day $j$ is to also buy on day $j$ (which gives us 0 profit).

Why is this valid? The above recursion has an important property: $r\left[j\right]$ holds the maximum over all $i\in \{0,\dots ,j\}$ of the sum $A\left[i\right]+\cdots +A\left[j\right]$. In other words, it holds the max sum for a subarray starting anywhere before $j$ (or at $j$) and ending at $j$.

By returning the max value contained in $r$, we then have the maximum subarray.

The recursion also nicely shows that each index in the recursion only uses the index before, which gives us an easy way to construct a bottom-up variant of the algorithm. We can translate the recursion to the loop invariant that is true for Kadane’s algorithm: at the beginning of step $j$, current_sum holds the value of the maximum subarray ending at $j-1$.

This is all an exercise in how to think of this problem, because if we are given the list of prices rather than the list of changes, it may be more intuitive to see how we can solve this:

1
2
3
4
5
6
7

def find_max_profit(prices: List[int]) -> int:
    min_price = float("inf")
    max_profit = 0
    for price in prices:
        min_price = min(price, min_price)
        max_profit = max(max_profit, price - min_price)
    return max_profit

Matrix multiplication

• Input: Two $n\times n$ (square) matrices, $A=\left(a_{ij}\right)$ and $B=\left(b_{ij}\right)$
• Output: $n\times n$ matrix $C=\left(c_{ij}\right)$ where $C=A\cdot B$.

Naive Algorithm

The naive algorithm simply calculates $c_{ij}={\sum }_{k=1}^n{a}_{ik}{b}_{kj}$. It runs in $\Theta \left(n^3\right)$ and uses $\Theta \left(n^2\right)$ space.

We can do better.

Divide-and-Conquer algorithm

• Divide each of A, B and C into four $n/2\times n/2$ matrices so that:

• Conquer: We can recursively solve 8 matrix multiplications that each multiply two $n/2\times n/2$ matrices, since:
  • $C_{11}=A_{11}{B}_{11}+A_{12}{B}_{21},C_{12}=A_{11}{B}_{12}+A_{12}{B}_{22}$.
  • $C_{21}=A_{21}{B}_{11}+A_{22}{B}_{21},C_{22}=A_{21}{B}_{12}+A_{22}{B}_{22}$.
• Combine: Make the additions to get to C.
  • $C_{11}=A_{11}{B}_{11}+A_{12}{B}_{21}$ is $\Theta \left(n^2\right)$.

Pseudocode and analysis

1
2
3
4
5
6
7
8
9
10

def rec_mat_mult(A, B, n):
    let C be a new n*n matrix
    if n == 1:
        c11 = a11 * b11
    else partition A, B, and C into n/2 * n/2 submatrices:
        C11 = rec_mat_mult(A[1][1], B[1][1], n/2) + rec_mat_mult(A[1][2], B[2][1], n/2)
        C12 = rec_mat_mult(A[1][1], B[1][2], n/2) + rec_mat_mult(A[1][2], B[2][2], n/2)
        C21 = rec_mat_mult(A[2][1], B[1][1], n/2) + rec_mat_mult(A[2][2], B[2][1], n/2)
        C22 = rec_mat_mult(A[2][1], B[1][2], n/2) + rec_mat_mult(A[2][2], B[2][2], n/2)
    return C

The whole recursion formula is $T\left(n\right)=8\cdot T\left(n/2\right)+\Theta \left(n^2\right)=\Theta \left(n^3\right)$. So we did all of this for something that doesn’t even beat the naive implementation!!

Strassen’s Algorithm for Matrix Multiplication

What really broke the Divide-and-Conquer approach is the fact that we had to do 8 matrix multiplications. Could we do fewer matrix multiplications by increasing the number of additions?

Spoiler Alert: Yes.

There is a way to do only 7 recursive multiplications of $n/2\times n/2$ matrices, rather than 8. Our recurrence relation is now:

Strassen’s method is the following:

Note that when our matrix’s size isn’t a power of two, we can just pad our operands with zeros until we do have a power of two size. This still runs in $\Theta \left(n^{{\log }_2\left(7\right)}\right)$.

Notes about Strassen

• First to beat $\Theta \left(n^3\right)$ time
• Faster methods are known today: Coppersmith and Winograd’s method runs in time $O\left(n^{2.376}\right)$, which has recently been improved by Vassilevska Williams to $O\left(n^{2.3727}\right)$.
• How to multiply matrices in best way is still a big open problem
• The naive method is better for small instances because of hidden constants in Strassen’s method’s runtime.

Heaps and Heapsort

Heaps

A heap is a nearly complete binary tree (meaning that the last level may not be complete). In a max-heap, the maximum element is at the root, while the minimum element takes that place in a min-heap.

We can store the heap in a list, where each element stores the value of a node:

• Root is A[1]
• Left(i) is 2i
• Right(i) is 2i + 1
• Parent(i) is floor(i/2)

The main property of a heap is:

In a heap, all nodes satisfy the heap property. Note that this does not mean that a heap is fully ordered. It has some notion of order, in that children are smaller or equal to their parent, but no guarantee is made about values in the left subtree compared to those in the right subtree.

A good way to understand a heap is to say that if you pick a path through the heap from root to leaf and traverse it, you are guaranteed to see numbers in decreasing order for a max-heap, and increasing order for a min-heap.

The height of a node is the number of edges on a longest simple path from the node down to a leaf. The height of the heap is therefore simply the height of the root, $O\left(\log n\right)$.

Max-Heapify

It’s a very important algorithm for manipulating heaps. Given an i such that the subtrees of i are heaps, it ensures that the subtree rooted at i is a heap satisfying the heap property. The outline is as follows:

• Compare A[i], A[Left(i)], A[Right(i)]
• If necessary, swap A[i] with the largest of the two children to preserve heap property.
• Continue this process of comparing and swapping down the heap, until the subtree rooted at i is a max-heap.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

def max_heapify(A: List[int], i: int, n: int):
    """
    Modifies `A` in-place so that the node at `i` roots a heap.

    A : List in which the left and right children of `i` root heaps 
        (but `i` may not)
    i : Index of the node which we want to heapify
    n : Length of `A`
    """
    l = Left(i)
    r = Right(i)

    # Pick larger of left (if it exists) and parent:
    if l <= n and A[l] > A[i]:
        largest = l
    else:
        largest = i
    
    # Pick larger of right (if it exists) and current largest:
    if r <= n and A[r] > A[largest]:
        largest = r
    
    # If the root isn't already the largest, swap the root with the
    # largest:
    if largest != i:
        swap A[i] and A[largest]
        max_heapify(A, largest, n)

This runs in $\Theta \left(\text{height of}i\right)=O\left(\log n\right)$ and uses $\Theta \left(n\right)$ space.

What may be surprising is that we only recurse when the node at i isn’t the largest; but remember that A is already such that the left and right subtrees of i already satisfy the heap property; they are already the roots of heaps. If i is larger than both left and right, then we preserve the heap property. If not, we may have to recursively modify one subtree to preserve the property.

Building a heap

Given an unordered array A of length n, build_max_heap outputs a heap.

1
2
3
4
5
6
7
8
9

def build_max_heap(A: List[int], n: int):
    """
    Modifies `A` in-place so that `A` becomes a heap.

    A : List of numbers
    n : Length of `A`
    """
    for i = floor(n/2) downto 1:
        max_heapify(A, i, n)

This procedure operates in-place. We can start at $\lfloor \frac{n}{2}\rfloor$ since all elements after that threshold are leaves, so we’re not going to heapify those anyway. Note that the node index i decreases, meaning that we’re generally going upwards in the tree. This is on purpose, as max_heapify may go back downwards in order to push small elements down to the bottom of the heap.

We have $O\left(n\right)$ calls to max_heapify, each of which takes $O\left(\log n\right)$ time, so we have $O\left(n\log n\right)$ in total. However, we can give a tighter bound: the time to run max_heapify is linear in the height of the node it’s run on. Hence, the time is bounded by:

Which is $\Theta \left(n\right)$, since:

See the slides for a proof by induction.

Heapsort

Heapsort is the best of both worlds: it’s $O\left(n\log n\right)$ like merge sort, and sorts in place like insertion sort.

• Starting with the root (the maximum element), the algorithm places the maximum element into the correct place in the array by swapping it with the element in the last position in the array.
• “Discard” this last node (knowing that it is in its correct place) by decreasing the heap size, and calling max_heapify on the new (possibly incorrectly-placed) root.
• Repeat this “discarding” process until only one node (the smallest element) remains, and therefore is in the correct place in the array

1
2
3
4
5

def heapsort(A, n):
    build_max_heap(A, n)
    for i = n downto 2:
        exchange A[1] with A[i]
        max_heapify(A, 1, i-1)

• build_max_heap: $O\left(n\right)$
• for loop: $n-1$ times
• Exchange elements: $O\left(1\right)$
• max_heapify: $O\left(\log n\right)$

Total time is therefore $O\left(n\log n\right)$.

Priority queues

In a priority queue, we want to be able to:

• Insert elements
• Find the maximum
• Remove and return the largest element
• Increase a key

A heap efficiently implements priority queues.

Finding maximum element

This can be done in $\Theta \left(1\right)$ by simply returning the root element.

1
2

def heap_maximum(A):
    return A[1]

Extracting maximum element

We can use max heapify to rebuild our heap after removing the root. This runs in $O\left(\log n\right)$, as every other operation than max-heapify runs in $O\left(1\right)$.

1
2
3
4
5
6
7
8

def heap_extract_max(A, n):
    if n < 1: # Check that the heap is non-empty
        error "Heap underflow"
    max = A[1]
    A[1] = A[n] # Make the last node in the tree the new root
    n = n - 1 # Remove the last node of the tree
    max_heapify(A, 1, n) # Re-heapify the heap
    return max

Increasing a value

1
2
3
4
5
6
7
8
9

def heap_increase_key(A, i, key):
    if key < A[i]:
        error "new key is smaller than current key"
    A[i] = key
    # Traverse the tree upward comparing new key to parent and swapping keys 
    # if necessary, until the new key is smaller than the parent's key:
    while i > 1 and A[Parent(i)] < A[i]:
        exchange A[i] with A[Parent(i)]
        i = Parent(i)

This traverses the tree upward, and runs in $O\left(\log n\right)$.

Inserting into the heap

1
2
3
4

def max_heap_insert(A, key, n):
    n = n + 1 # Increment the size of the heap
    A[n] = - infinity # Insert a sentinel node in the last pos
    heap_increase_key(A, n, key) # Increase the value to key

We know that this runs in the time for heap_increase_key, which is $O\left(\log n\right)$.

Summary

• Heapsort runs in $O\left(n\log n\right)$ and is in-place. However, a well implemented quicksort usually beats it in practice.
• Heaps efficiently implement priority queues:
  • insert(S, x): $O\left(\log n\right)$
  • maximum(S): $O\left(1\right)$
  • extract_max(S): $O\left(\log n\right)$
  • increase_key(S, x, k): $O\left(\log n\right)$

More data structures

Stacks

Stacks are LIFO (last-in, first out). It has two basic operations:

• Insertion with push(S, x)
• Delete operation with pop(S)

We can implement a stack using an array where S[1] is the bottom element, and S[S.top] is the element at the top.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def stack_empty(S):
    if S.top = 0:
        return true
    else return false

def push(S, x):
    S.top = S.top + 1 # Increment the pointer to the top
    S[S.top] = x # Store element

def pop(S):
    if stack_empty(S):
        error "underflow"
    else
        S.top = S.top - 1 # Decrement the pointer to the top
        return S[S.top + 1] # Return what we've removed

These operations are all $O\left(1\right)$.

Queues

Queues are FIFO (first-in, first-out). They have two basic operations:

• Insertion with enqueue(Q, x)
• Deletion with dequeue(Q)

Again, queues can be implemented using arrays with two pointers: Q[Q.head] is the first element, Q[Q.tail] is the next location where a newly arrived element will be placed.

1
2
3
4
5
6
7
8
9
10
11
12
13

def enqueue(Q, x):
    Q[Q.tail = x]
    # Now, update the tail pointer:
    if Q.tail = Q.length: # Q.length is the length of the array
        Q.tail = 1 # Wrap it around
    else Q.tail = Q.tail + 1

def dequeue(Q):
    x = Q[Q.head]
    # Now, update the head pointer
    if Q.head = Q.length:
        Q.head = 1
    else Q.head = Q.head + 1

Notice that we’re not deleting anything per se. We’re just moving the boundaries of the queue and sometimes replacing elements.

Positives:

• Very efficient
• Natural operations

Negatives:

• Limited support: for example, no search
• Implementations using arrays have fixed capacity

Linked Lists

Let’s take a look at the operations in linked lists.

Search

1
2
3
4
5

def list_search(L, k):
    x = L.head
    while x != nil and x.key != k:
        x = x.next
    return x

This runs in $O\left(n\right)$. If no element with key k exists, it will return nil.

Insertion

1
2
3
4
5
6

def list_insert(L, x):
    x.next = L.head
    if L.head != nil:
        L.head.prev = x
    L.head = x # Rewrite the head pointer
    x.prev = nil

This runs in $O\left(1\right)$. This linked list doesn’t implement a tail pointer, so it’s important to add the element to the start of the list and not the end, as that would mean traversing the list before adding the element.

Deletion

1
2
3
4
5
6

def list_delete(L, x):
    if x.prev != nil:
        x.prev.next = x.next
    else L.head = x.next
    if x.next != nil:
        x.next.prev = x.prev

This is $O\left(1\right)$.

Summary

• Insertion: $O\left(1\right)$
• Deletion: $O\left(1\right)$
• Search: $O\left(n\right)$

Search in linear time is no fun! Let’s see how else we can do this.

Binary search trees

The key property of binary search trees is:

• If y is in the left subtree of x, then y.key < x.key
• If y is in the right subtree of x, then y.key >= x.key

The tree T has a root T.root, and a height h (not necessarily log(n), it can vary depending on the organization of the tree).

Querying a binary search tree

All of the following algorithms can be implemented in $O\left(h\right)$.

Searching

1
2
3
4
5
6
7

def tree_search(x, k):
    if x == None or k == x.key:
        return x
    if k < x.key:
        return tree_search(x.left, k)
    else:
        return tree_search(x.right, k)

Maximum and minimum

By the key property, the minimum is in the leftmost node, and the maximum in rightmost.

1
2
3
4
5
6
7
8
9

def tree_minimum(x):
    while x.left != None:
        x = x.left
    return x

def tree_maximum(x):
    while x.right != None:
        x = x.right
    return x

Successor

The successor or a node x is the node y such that y.key is the smallest key that is strictly larger than x.key.

There are 2 cases when finding the successor of x:

1. x has a non-empty right subtree: x’s successor is the minimum in the right subtree
2. x has an empty right subtree: We go left up the tree as long as we can (until node y), and and x’s successor is the parent of y (or y if it is the root)

1
2
3
4
5
6
7
8

def tree_successor(x):
    if x.right != None:
        return tree_minimum(x.right)
    y = x.parent
    while y != None and x == y.right:
        x = y
        y = y.parent
    return y

In the worst-case, this will have to traverse the tree upward, so it indeed runs in $O\left(h\right)$.

Printing a binary search tree

Let’s consider the following tree:

Inorder

• Print left subtree recursively
• Print root
• Print right subtree recursively

1
2
3
4
5

def inorder_tree_walk(x):
    if x != None:
        inorder_tree_walk(x.left)
        print x.key
        inorder_tree_walk(x.right)

This would print:

1, 2, 3, 4, 5, 6, 7, 8, 9 10, 11, 12

This runs in $\Theta \left(n\right)$.

Preorder

• Print root
• Print left subtree recursively
• Print right subtree recursively

1
2
3
4
5

def inorder_tree_walk(x):
    if x != None:
        print x.key
        inorder_tree_walk(x.left)
        inorder_tree_walk(x.right)

This would print:

8, 4, 2, 1, 3, 6, 5, 12, 10, 9, 11

Postorder

• Print left subtree recursively
• Print right subtree recursively
• Print root

1
2
3
4
5

def inorder_tree_walk(x):
    if x != None:
        inorder_tree_walk(x.left)
        inorder_tree_walk(x.right)
        print x.key

This would print:

1, 3, 2, 5, 6, 4, 9, 11, 10, 12, 8

Modifying a binary seach tree

The data structure must be modified to reflect the change, but in such a way that the binary-search-tree property continues to hold.

Insertion

• Search for z.key
• When arrived at Nil insert z at that position

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

def tree_insert(T, z):
    # Search phase:
    y = None
    x = T.root
    while x != None:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y

    # Insert phase
    if y == Nil:
        T.root = z # Tree T was empty
    elsif z.key < y.key:
        y.left = z
    else:
        y.right = z

This runs in $O\left(h\right)$.

Deletion

Conceptually, there are 3 cases:

1. If z has no children, remove it
2. If z has one child, then make that child take z’s position in the tree
3. If z has two children, then find its successor y and replace z by y

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

# Replaces subtree rooted at u with that rooted at v
def transplant(T, u, v):
    if u.parent == Nil: # If u is the root
        T.root = v
    elsif u == u.parent.left: # If u is to the left
        u.parent.left = v
    else: # If u is to the right
        u.parent.right = v 
    if v != Nil: # If v isn't the root
        v.parent = u.parent

# Deletes the subtree rooted at z
def tree_delete(T, z):
    if z.left == Nil: # z has no left child
        transplant(T, z, z.right) # move up the right child
    if z.right == Nil: # z has just a left child
        transplant(T, z, z.left) # move up the left child
    else: # z has two children
        y = tree_minimum(z.right) # y is z's successor
        if y.parent != z:
            # y lies within z's right subtree but not at the root of it
            # We must therefore extract y from its position
            transplant(T, y, y.right)
            y.right = z.right
            y.right.parent = y
        # Replace z by y:
        transplant(T, z, y)
        y.left = z.left
        y.left.parent = y

Summary

• Query operations: Search, max, min, predecessor, successor: $O\left(h\right)$
• Modifying operations: Insertion, deletion: $O\left(h\right)$

There are efficient procedures to keep the tree balanced (AVL trees, red-black trees, etc.).

Summary

• Stacks: LIFO, insertion and deletion in $O\left(1\right)$, with an array implementation with fixed capacity
• Queues: FIFO, insertion and deletion in $O\left(1\right)$, with an array implementation with fixed capacity
• Linked Lists: No fixed capcity, insertion and deletion in $O\left(1\right)$, supports search but $O\left(n\right)$ time.
• Binary Search Trees: No fixed capacity, supports most operations (insertion, deletion, search, max, min) in time $O\left(h\right)$.

Dynamic Programming

The main idea is to remember calculations already made. This saves enormous amounts of computation, as we don’t have to do the same calculations again and again.

There are two different ways to implement this:

Top-down with memoization

Solve recursively but store each result in a table. Memoizing is remembering what we have computed previously.

As an example, let’s calculate Fibonacci numbers with this technique:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def memoized_fib(n):
    let r = [0...n] be a new array
    for i = 0 to n:
        r[i] = - infinity # Initialize memory to -inf
    return memoized_fib_aux(n, r)

def memoized_fib_aux(n, r):
    if r[n] >= 0:
        return r[n]
    if n == 0 or n == 1:
        ans = 1
    else ans = memoized_fib_aux(n-1, r) + memoized_fib_aux(n-2, r)
    r[n] = ans
    return r[n]

This runs in $\Theta \left(n\right)$.

Bottom-up

Sort the subproblems and solve the smaller ones first. That way, when solving a subproblem, we have already solved the smaller subproblems we need.

As an example, let’s calculate Fibonacci numbers with this technique:

1
2
3
4
5
6
7

def bottom_up_fib(n):
    let r = [0 ... n] be a new array
    r[0] = 1
    r[1] = 1
    for i = 2 to n:
        r[i] = r[i-1] + r[i-2]
    return r[n]

This is also $\Theta \left(n\right)$.

Rod cutting problem

The instance of the problem is:

• A length $n$ of a metal rods
• A table of prices $p_i$ for rods of lengths $i=1,\dots ,n$

The objective is to decide how to cut the rod into pieces and maximize the price.

There are $2^{n-1}$ possible solutions (not considering symmetry), so we can’t just try them all. Let’s introduce the following theorem in an attempt at finding a better way:

Structural Theorem

If:

• The leftmost cut in an optimal solution is after $i$ units
• An optimal way to cut a solution of size $n-i$ is into rods of sizes $s_1,s_2,\dots ,s_k$

Then, an optimal way to cut our rod is into rods of size $i,s_1,s_2,\dots ,s_k$.

Essentially, the theorem say that to obtain an optimal solution, we need to cut the remaining pieces in an optimal way. This is the optimal substructure property. Hence, if we let $r\left(n\right)$ be the optimal revenue from a rod of length $n$, we can express $r\left(n\right)$ recursively as follows:

Algorithm

Let’s try to implement a first algorithm. This is a direct implementation of the recurrence relation above:

1
2
3
4
5
6
7

def cut_rod(p, n):
    id n == 0:
        return 0
    q = -inf
    for i = 1 to n:
        q = max(q, p[i] + cut_rod(p, n-i))
    return q

But implementing this, we see that it isn’t terribly efficient — in fact, it’s exponential. Let’s try to do this with dynamic programming. Here, we’ll do it in a memoized top-down approach.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def memoized_cut_rod(p, n):
    let r[0..n] be a new array
    Initialize all entries to -infinity
    return memoized_cut_rod_aux(p, n, r)

def memoized_cut_rod_aux(p, n, r):
    if r[n] >= 0: # if it has been calculated
        return r[n]
    if n == 0:
        q = 0
    else:
        q = - infinity
        for i = 1 to r:
            q = max(q, p[i] + memoized_cut_rod_aux(p, n-i, r))
    r[n] = q
    return q

Every problem needs to check all the subproblems. Thanks to dynamic programming, we can just sum them instead of multiplying them, as every subproblem is computed once at most. As we’ve seen earlier on with insertion sort, this is:

The total time complexity is $O\left(n^2\right)$. This is even clearer with the bottom up approach:

1
2
3
4
5
6
7
8
9

def bottom_up_cut_rod(p, n):
    let r[0..n] be a new array
    r[0] = 0
    for j = 1 to n:
        q = - infinity
        for i = 1 to j:
            q = max(q, p[i]+ r[j -1])
        r[j] = q
    return r[n]

There’s a for-loop in a for-loop, so we clearly have $\Theta \left(n^2\right)$.

Top-down only solves the subproblems actually needed, but recursive calls introduce overhead.

Extended algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

def extended_bottom_up_cut_rod(p, n):
    let r[0..n] and s[0..n] be new arrays
    # r[n] will be the price you can get for a rod of length n
    # s[n] the cuts of optimum location for a rod of length n
    r[0] = 0
    for j = 1 to n:
        q = -infinity
        for i to j:
            if q < p[i] + r[j-i]: # best cut so far?
                q = p[i] + r[j-i] # save its price
                s[j] = i # and save the index!
    r[j] = q
    return (r, s)

def print_cut_rod_solution(p, n):
    (r, s) = extended_bottom_up_cut_rod(p, n)
    while n > 0:
        print s[n]
        n = n - s[n]

When can dynamic programming be used?

• Optimal substructure
  • An optimal solution can be built by combining optimal solutions for the subproblems
  • Implies that the optimal value can be given by a recursive formula
• Overlapping subproblems

Matrix-chain multiplication

• Input: A chain $(A_1,A_2,\dots ,A_n)$ of $n$ matrices, where for $i=1,2,\dots ,n$, matrix $A_i$ has dimension $p_{i-1}\times p_i$.
• Output: A full parenthesization of the product $A_1{A}_2\dots A_n$ in a way that minimizes the number of scalar multiplications.

We are not asked to calculate the product, only find the best parenthesization. Multiplying a matrix of size $p\times q$ with one of $q\times r$ takes $pqr$ scalar multiplications.

We’ll have to use the following theorem:

Optimal substructure theorem

If:

• The outermost parenthesization in an optimal solution is $(A_1{A}_2\dots A_i)(A_{i+1}{A}_{i+2}\dots A_n)$
• $P_L$ and $P_R$ are optimal pernthesizations for $A_1{A}_2\dots A_i$ and $A_{i+1}{A}_{i+2}\dots A_n$ respectively

Then $\left(\right(P_L)\cdot (P_R\left)\right)$ is an optimal parenthesization for $A_1{A}_2\dots A_n$

See the slides for proof.

Essentially, to obtain an optimal solution, we need to parenthesize the two remaining expressions in an optimal way.

Hence, if we let $m[i,j]$ be the optimal value for chain multiplication of matrices $A_i,\dots ,A_j$ (meaning, how many multiplications we can do at best), we can express $m[i,j]$ recursively as follows:

That is the minimum of the left, the right, and the number of operations to combine them.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def matrix_chain_order(p):
    n = p.length - 1
    let m[1..n, 1..n] and s[1..n, 1..n] be new tables
    for i = 1 to n: # Initialize all to 0
        m[i, i] = 0
    for l = 2 to n: # l is the chain length
        for i = 1 to n - l + 1:
            j = i + l - 1
            m[i, j] = infinity
            for k = i to j - 1:
                q = m[i, k] + m[k+1, j] + p[i-1]p[k]p[j]
                if q < m[i, j]:
                    m[i, j] = q # store the number of multiplications
                    s[i, j] = k # store the optimal choice
    return m and s

The runtime of this is $\Theta \left(n^3\right)$.

To know how to split up $A_i{A}_{i+1}\dots A_j$ we look in s[i, j]. This split corresponds to m[i, j] operations. To print it, we can do:

1
2
3
4
5
6
7
8

def print_optimal_parens(s, i, j):
    if i == j:
        print "A_" + i
    else:
        print "("
        print_optimal_parens(s, i, s[i, j])
        print_optimal_parens(s, s[i, j]+1, j)
        print ")"

Longest common subsequence

• Input: 2 sequences, $X=(x_1,\dots ,x_m)$ and $Y=(y_1,\dots ,y_n)$
• Output: A subsequence common to both whose length is longest. A subsequence doesn’t have to be consecutive, but it has to be in order.

Theorem

Let $Z=(z_1,z_2,\dots ,z_k)$ be any LCS of $X_i$ and $Y_j$

1. If $x_i=y_j$ then $z_k=x_i=y_j$ and $Z_{k-1}$ is an LCS of $X_{i-1}$ and $Y_{j-1}$
2. If $x_i\ne y_j$ then $z_k\ne x_i$ and $Z$ is an LCS of $X_{i-1}$ and $Y_j$
3. If $x_i\ne y_j$ then $z_k\ne y_i$ and $Z$ is an LCS of $X_i$ and $Y_{j-1}$

If $c[i,j]$ is the length of a LCS of $X_i$ and $Y_i$, then:

Using this recurrence, we can fill out a table of dimensions $i\times j$. The first row and the first colum will obviously be filled with 0s. Then we traverse the table row by row to fill out the values according to the following rules.

1. If the characters at indices i and j are equal, then we take the diagonal value (above and left) and add 1.
2. If the characters at indices i and j are different, then we take the max of the value above and that to the left.

Along with the values in the table, we’ll also store where the information of each cell was taken from: left, above or diagonally (the max defaults to the value above if left and above are equal). This produces a table of of numbers and arrows that we can follow from bottom right to top left:

The diagonal arrows in the path correspond to the characters in the LCS. In our case, the LCS has length 4 and it is ABBA.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

def lcs_length(X, Y, m, n):
    let b[1..m, 1..n] and c[0..m, 0..n] be new tables
    # Initialize 1st row and column to 0
    for i = 1 to m:
        c[i, 0] = 0
    for j = 0 to n:
        c[0, j] = 0
    for i = 1 to m:
        for j = 1 to n:
            if X[i] = Y[j]:
                c[i, j] = c[i-1, j-1] + 1
                b[i, j] = "↖" # up left
            elsif c[i-1, j] >= c[i, j-1]:
                c[i, j] = c[i-1, j]
                b[i, j] = "↑" # up
            else:
                c[i, j] = c[i, j-1]
                b[i, j] = "←" # left
    return b, c


def print_lcs(b, X, i, j):
    if i == 0 or j == 0:
        return
    if b[i, j] == "↖": # up left
        print-lcs(b, X, i-1, j-1)
        print X[i]
    elsif b[i, j] == "↑": # up
        print-lcs(b, X, i-1, j)
    elsif b[i, j] == "←": # left
        print-lcs(b, X, i, j-1)

The runtime of lcs-length is dominated by the two nested loops; runtime is $\Theta (m\cdot n)$.

The runtime of print-lcs is $(O\left)\right(n)$, where $n=i+j$.

Optimal binary search trees

Given a sequence of keys $K=(k_1,k_2,\dots ,k_n)$ of distinct keys, sorted so that $k_1<k_2<\cdots <k_n$. We want to build a BST. Some keys are more popular than others: key $K_i$ has probability $p_i$ of being searched for. Our BST should have a minimum expected search cost.

The cost of searching for a key $k_i$ is ${\text{depth}}_T\left(k_i\right)+1$ (we add one because the root is at height 0 but has a cost of 1). The expected search cost would then be:

Optimal BSTs might not have the smallest height, and optimal BSTs might not have highest-probability key at root.

Let $e[i,j]$ denote the expected search cost of an optimal BST of $k_i\dots k_j$.

With the following inputs:

We can fill out the table as follows:

To compute something in this table, we should have already computed everything to the left, and everything below. We can start out by filling out the diagonal, and then filling out the diagonals to its right.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def optimal_bst(p, q, n):
    let e[1..n+1, 0..n] be a new table
    let w[1..n+1, 0..n] be a new table
    let root[1..n, 1..n] be a new table
    for i = 1 to n + 1:
        e[i, i-1] = 0
        w[i, i-1] = 0
    for l = 1 to n:
        for i = 1 to n - l + 1:
            j = i + l - 1
            e[i, j] = infinity
            w[i, j] = w[i, j-1] + p[j]
            for r = i to j:
                t = e[i, r-1] + e[r+1, j] + w[i, j]
                if t < e[i, j]:
                    e[i, j] = t
                    root[i, j] = r
    return (e, root)