UNB/ CS/ David Bremner/ teaching/ cs3383/ tests/ Class Test 2

The second midterm will be held in class, November 18. The test will be closed book.

Topics

Greedy Algorithms

Union Find

Dynamic programming

Sample exam questions

Here are some sample questions from previous exams. These are all on topics that could show up in the second midterm.

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 != 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 a sequence of nonzero integers, the longest alternating subsequence is the longest subsequence such that succesive elements of the subsequence change sign. For example given the sequence

  1, 7, −3, −4, 5, 7, −9,

a (non-unique) longest alternating subsequence is 7, −3, 5, −9. We interested here in computing the length of the longest alternating subsequence.

This question has a solution.

Practice assignment questions

Here are some questions from previous assignments

  1. (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.

  2. A vertex cover of graph G=(V,E) is S⊆V such that every edge in E has at least one endpoint in S. Observe that for a given node u∈V, either we choose u for our vertex cover, or all neighbours of u. Derive a dynamic programming algorithm for minimum vertex cover in a rooted tree, as follows.

    • What are the recursive subproblems to be solved?
    • What is the recursive function that defines the a problem terms of the smaller subproblems?
    • What are the base cases?
    • Explain the DAG structure of the subproblems.
    • Give a DAG based dynamic programming algorithm for this problem.
  3. Describe and analyze a dynamic programming algorithm to find an optimal binary search tree for a given set of integers, given a frequency for each key.

    This question is discussed in solution.