## CS535 Midterm

CS Midterm代考 In Binomial heaps, suppose the merge rule is modifed to allow for k −1 trees of a given rank, and when the merge is applied k trees…

1. In Binomial heaps, suppose the merge rule is modifed to allow for k 1 trees of a given rank, and when the merge is applied k trees are merged into one. A merge of k trees can be done by connecting k 1 of them as children of the root node of one of them. What is the structure of the trees in this case. What is the bound on the largest rank when n nodes are present in the heap. What is the amortized bound on insertions and deletions.(25 pts) CS Midterm代考
1. (a) Terminal Spanning Trees: Given a graph G = (V, E) with distinct edge weights and a subset of nodes U, show how to fifind a minimum spanning tree with all the nodes in U as leaves of the tree. If such a tree does not exist your algorithm must discover that. Is this tree a MST, prove  or disprove.(15 pts)

(b) Let T be a MST in a weighted graph G. Given a connected subgraph H show that T H is a subgraph of a MST of H.(15 pts)

1. ### Let M = (S, I) be a matroid. Prove that the subset system M = (S − S0 , I0 ), S0 ⊂ S, where CS Midterm代考

I0 = {I0 |I0 ∈ I, I0 S S0 }

is a matroid.

(20 pts)  