CS240 Assignment 2 | Q2,3,4 Solution

Problem 2 [1+6 = 7 marks]

In the minimum spanning tree problem, the input is a set of n points, with arbitrary co- ordinates, in the plane. The output is a set of segments that connect these points to form a connected tree, called spanning tree. The goal is to form a spanning tree in which the total length of segments in the tree is minimum. For example, consider the set of points
fA = (0; 0);B = (0; 2);C = (2; 0);D = (1; 2);E = (􀀀3; 0); F = (􀀀2;􀀀2)g; the minimum spanning tree is formed by segments f(A;B); (A;C); (A;E); (B;D); (E; F)g (see Figure 1).

a) What is the length of minimum spanning tree in Figure 1? Note the change in the tree (the previously posted one was not a minimum spanning tree). We will accept correct solutions for any of the posted trees.
b) Assume an algorithm A solves the minimum spanning tree problem. Prove that A has a time complexity of
(n log n). Note that we do not make any assumption (e.g., integer coordinates) for the points that de ne the minimum spanning tree problem.

[Hint: Consider a problem that is known to have
(n log n) complexity and show that the minimum spanning tree problem cannot have a solution with better complexity.] In other words, you can assume, in the contrary, that there is a minimum
spanning tree algorithm that runs in o(n log n). You use that algorithm as a black box to solve a problem P that is known to have  (n log n) complexity in o(n log n) (hence, a contradiction). The black-box returns minimum span-ning tree in the form of a rooted tree; the root is the rst point (at index 0) in the array of input-points. In this example, assuming point B is the rst point in the array, the output will be (B ! A); (B ! D); (A ! C); (A !
F); (F ! E).

A
B
C
D
E
F

Figure 1: An example of minimum spanning tree of n = 6 points.

Problem 3 [4+2+2+4 = 12 marks]
Let A be an array of n distinct integers. An inversion is a pair of indices (i; j) such that
i < j and A[i] > A[j].
a) Determine the maximum number (imax) and minimum number (imin) of inversions in
an array of n distinct integers. Characterize what the arrays that attain these maxima
and minima look like.
b) Given a pair of distinct indices (i; j), show that the probability that (i; j) is an inversion is 1=2 (the average is computed over all n! permutations of the n integers in A).
c) Determine the average number (iavg) of inversions in an array of n distinct integers.
The average is computed over all n! permutations of the n integers in A (you might use the result in part (b) in your proof).
d) Suppose a sorting algorithm is only allowed to exchange adjacent elements. Show that its worst-case and average-case complexity is  (n2) (you might use the result in the previous parts in your proof).

Problem 4 [3+3+5 = 11 marks]
Consider the selection problem for an array of n distinct integers, i.e., given an integer k n of numbers, we would like to report the value of the k'th smallest number. The following randomized algorithm selects a random index and checks whether its entry is the desired value. If it is, it returns the index; otherwise, it recursively calls itself. Recall that random(n) returns an integer from the set of f0; 1; 2; : : : ; n 􀀀 1g uniformly and at random.
random-select(A; n; k)
1: i   random(n)
2: if A[i] is the k'th smallest item then
3: return A[ i ]
4: else
5: return random-select(A; n, k).
6: end if
In your answers below, be as precise as possible. You may use order notation when
appropriate. Brie
y justify your answers.
a) What is the best-case running time of random-select?
b) What is the worst-case running time of random-select?
c) Let T(n) be the expected running time of random-select. Write down a recurrence for
T(n) and then solve it.