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

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
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.
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$.
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.
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?