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

## Topics

### Greedy Algorithms

- Huffman codes
- optimality condition
- algorithm

- Minimum spanning tree
- spanning trees
- cut property
- swapping edges
- Kruskal's Algorithm
- Prim's Algorithm

- Greedy scheduling
- optimality condition

### Union Find

- Union by Rank
- 3 properties
`O(log(n)`

height

- Path Compression
- 3 properties
- Amortized analysis will
*not*be this test, but it may be on the final.

- Union by Weight
`O(log(n))`

height

### Dynamic programming

- recursive functions
- subproblem DAG
- topological sort
- "best" path in DAG

## 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.

What are the subproblems?

Give a recurrence suitable for a dynamic programming algorithm.

This question has a solution.

## 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.

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.

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.