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…
- 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代考
- (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)
-
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)
- Given a set of points A in 2-dimensions, suppose we know an algorithm Best-fifit (A) which gives the best-fifit straight line-segment through the set of points A. The line-segments starts and ends at the x-cordinate of the fifirst and last points (by x-cordinate order)in the set A. The algorithm also returns a real value EA, the error made in the points not being on the straight line. Instead of 1 line approximating the point, Mr. X suggest that we construct piece-wise linear segments to reduce the error and better approximate the point set. Given a larger set of 2-d points S we would like to construct a sequence of at most k line segments to best fifit all the points. The total error is the sum of the error made by each of the line-segments. Design a method to create this sequence of k straight line segments so as to minimize the total error. Assume that the method Best-fifit (A) is known. Ignore the error in connecting together the line segments in-between. CS Midterm代考
(25 pts)
