MPCS 55001 — Problem Set 3

Instructions

This problem set is due on Wednesday April 29, 2020 at 20:00 Central, to be submitted on Gradescope. Each problem is worth 10 marks in total.

Problems

1. Either give a proof or provide a counterexample for the following statements.
   1. If a graph $G$ has distinct edge weights, then $G$ has a unique minimum spanning tree.
   2. If a graph $G$ has a unique minimum spanning tree, then $G$ has distinct edge weights.
2. Consider the following ingenious idea for a new algorithm for computing the minimum spanning tree: What if we combined Prim's and Kruskal's algorithms together? The algorithm is as follows.
   1. Put every vertex in its own tree, like in Kruskal's algorithm.
   2. For each tree, choose minimum weight edge that leaves the tree, like Prim's algorithm.
   3. Join the trees using the chosen edges. Two trees may select the same edge.
   4. Repeat starting from step 2 until there is only one tree.
   Assume the graph has distinct edge weights. Would this algorithm actually work? Give a proof or counterexample.
3. Consider the following algorithm, which takes as input an array $A$ of $n$ integers.

       \begin{algorithm}
       \begin{algorithmic}
       \PROCEDURE{algorithm3}{$A$}
           \IF{$|A| == 1$}
               \RETURN{$(A[1],A[1])$}
           \ELIF{$|A| == 2$}
               \IF{$A[1] \leq A[2]$}
                   \RETURN{$(A[1],A[2])$}
               \ELSE
                   \RETURN{$(A[2],A[1])$}
               \ENDIF
           \ELSE
               \STATE $m = \left\lfloor \frac n 2 \right\rfloor$
               \STATE $A_1 = A[1,\dots,m]$
               \STATE $A_2 = A[m+1,\dots,n]$
               \STATE $(\min_1, \max_1) = $ algorithm3($A_1$)
               \STATE $(\min_2, \max_2) = $ algorithm3($A_2$)
               \STATE $\min = \min(\min_1,\min_2)$
               \STATE $\max = \max(\max_1,\max_2)$
               \RETURN{$(\min,\max)$}
           \ENDIF
       \ENDPROCEDURE
       \end{algorithmic}
       \end{algorithm}
   

   1. What does this algorithm do? Prove its correctness.
   2. What is this algorithm's running time? Give a proof of this.