Sale!

# ALGORITHMS AND DATA STRUCTURES II ASSIGNMENT 2

\$29.00

Category:

1. Starting with an empty tree, construct a red-black tree by inserting the following keys in
the order given: 2; 1; 4; 5; 9; 3; 6; 7. If an insertion causes the tree to violate the properties
of a red-black tree, then perform the necessary restructuring.
2. Prove that the height of a red-black tree with N nodes is at most 2 log N.
3. Consider the following Reverse-Delete algorithm: Remove edges in the decreasing order of
weight skipping those whose removal would disconnct the graph. Prove that this algorithm
always outputs the MST. You can assume that the edge weights are distinct.
4. Prove that if all the edges of a graph G have distinct weights, the MST of G is unique.
5. A minimum bottleneck spanning tree (MBST) of a weighted, undirected graph G is a
spanning tree in which the edge of maximum weight is as small as possible. Give a counter
example to show that a MBST of G is not always a MST of G. ALGORITHMS AND DATA STRUCTURES II ASSIGNMENT 2
\$29.00
Hello
Can we help?