The second midterm will be held in class, Feb. 21, 2018. The test will be closed book. It will cover material on greedy algorithms and dynamic programming ("Unit 2" and "Unit 3").

Previous Test questions

1. Let e be the unique lightest edge in a graph G. Let T be a spanning tree of G such that e ∉ T . Prove using elementary properties of spanning trees (i.e. not the cut property) that T is not a minimum spanning tree of G.

2. A bridge is an edge whose removal disconnects the graph. Prove that any bridge must be in some minimum spanning tree. You may use the cut property in the proof, if you want.

3. Prove that in trees generated by union-by-rank (pseudocode below), no two nodes of rank k share a descendant.

    function UNION(x,y)
        x ← find(x)
        y ← find(y)
        if x! = y then
            if rank[x] > rank[y] then
                parent[y] ← x
            else
                if rank[x] = rank[y] then
                    rank[y] ← rank[y] + 1
                end if
                parent[x] ← y
            end if
        end if
    end function

function FIND (x)
    while x 6 = parent[x] do
        x ← parent[x]
    end while
    return x
end function

function MAKESET (x)
    parent[x] ← x
    rank[x] ← 0
end function

4. Given sequences of integers x[1 … n], y[1 … m], the Longest Common Subsequence problem asks for the longest sequence z₁…zₖ such that the zᵢ occur (in order) in both x[1 … n] and y[1 … m]. Give a dynamic programming algorithm for this problem.

5. Crazy Huffman’s Bulk Barn has a very strange pricing policy. When you check out, the ith item scanned is priced at i * w[i], where w[i] is weight of the item in grams. Prove that to minimize your total bill you should pass the items to the checkout person in decreasing order of weight.

The Fibonacci function is defined by the base cases F(1)=F(2)=1, and the recurrence
F(n)=F(n − 1)+F(n − 2)

(2 marks)

Explain the directed acyclic graph (DAG) of recursive problems that need to be solved. What are the nodes? What are the (directed) edges? What does the direction of the edges mean?
(3 marks)

Give a dynamic programming algorithm to compute F(n)

Prove by induction that in the disjoint-sets data structure created by the pseudocode below, the rank of any root node is at least its height in the corresponding tree.

function Makeset(x)
    parent[x] ← x
    rank[x] ← 0
end function

function find(x)
    while x != parent[x] do
        x ← parent[x]
    end while
    return x
end function

function Union(x,y)
    x ← find(x)
    y ← find(y)
    if x! = y then
        if rank[x] > rank[y] then
            parent[y] ← x
        else
            if rank[x] = rank[y] then
                rank[y] ← rank[y] + 1
            end if
            parent[x] ← y
        end if
    end if
end function

Edit distance measures the number of single character inserts, deletes, and substitutions needed to transform one string into another. Each set of editing operations can be represented as an alignment, i.e. a table where all non-matching positions cost one operation. For example the following alignment costs 5.

exam__ination
_caffeination

(4 marks)

Prove that if we remove any column from an optimal alignment, we have an optimal alignment for the remaining substrings.
(3 marks)

Give a recurrence to find the edit distance.
(2 marks)

Describe the DAG of subproblems for dynamic programming.
(3 marks)

Give an iterative (non-recursive) dynamic programming algorithm to compute edit distance.

Practice assignment questions

Here are some questions from previous assignments

(ex 5.21 from Dasgupta et al.)
- Prove that for any cycle in graph G, there is a minimum spanning tree that does not contain the heaviest edge in that cycle.
- Prove the following MST algorithm is correct
```
  sort the edges according to their weights
  for each edge e ∈ E, in decreasing order of weight :
      if e is part of a cycle of G:
          G = G − e (that is, remove e from G)
  return G
```
- Give a linear time algorithm to check if there is a cycle containing a specific edge e. (This is needed in the algorithm above)
- Analyze the running time of the new MST algorithm.
Describe and analyze a dynamic programming algorithm to find an optimal binary search tree for a given set of integers.