ISI2014-PCB-CS-3b

1 vote
337 views
Let $G = (V, E)$ be an undirected weighted graph with all edge weights being positive. Design an efficient algorithm to find the maximum spanning tree of $G$.

1 Answer

3 votes

Sorry, I'm not able to upload the protrait version of the image .

It is just some changes in the Minimum spanning tree algo.Correct me if I'm wrong.

0
It’s greedy right?

Related questions

1 vote
1 answer
1
189 views
Assume you have a chocolate bar containing a number of small identical squares arranged in a rectangular pattern. Our job is to split the bar into small squares by breaking along the lines between the squares. We obviously want to do it with the minimum number of ... n, m as inputs and print the line numbers along the length and the breadth according to your strategy of breaking the chocolate.
11 votes
1 answer
2
751 views
Let $H_1$ and $H_2$ be two complete binary trees that are heaps as well. Assume $H_1$ and $H_2$ are max-heaps, each of size $n$. Design and analyze an efficient algorithm to merge $H_1$ and $H_2$ to a new max-heap $H$ of size $2n$.
1 vote
1 answer
3
214 views
Let $A$ and $B$ be two arrays, each containing $n$ distinct integers. Each of them is sorted in increasing order. Let $C = A \cup B$. Design an algorithm for computing the median of $C$ as efficiently as you can.
1 vote
0 answers
4
310 views
A heavily loaded $1$ km long, $10$ Mbps token ring network has a propagation speed of $200$ meter per micro-second. Fifty stations are uniformly spaced around the ring. Each data packet is $256$ bits long, including $32$ bits of header. The token is of $8$ bits. What is the effective data rate of the network assuming the stations always have packets to transmit?