sample2

‎

1. Quicksort (Divide and Conquer)

Consider the following variation on randomized quicksort.

def quicksort(A,p,q):
    if p>=q:
        return

    n = q - p + 1

    bad = True
    while bad:
        r = partition(A,p,q,randrange(p,q+1))
        k = r - p
        bad = (k < n//4) or (k > 3*n//4)

    quicksort(A,p,r-1)
    quicksort(A,r+1,q)

For quicksort and partition, the parameters \(p\) and \(q\) denote the first and last index of the range to be sorted or partitioned.
The last parameter of partition is the index of the element to be used as a pivot, and the returned value is the position of the pivot in the partitioned array.
partition takes \(\Theta(n)\) time.
randrange(p,q+1) takes constant time, and returns a random number from \(p\) to \(q\).

1.1. Recurrence.

Define appropriate indicator random variables and use those to define a recurrence upper bounding the (random) running time of quicksort.

1.2. Bound

Use your recurrence to bound the expected running time of quicksort

2. Huffman (Greedy)

In a Huffman tree \(T\), \(f_i\) and \(d_i\) are the frequency and depth of symbol \(i\), and the cost of \(T\) defined as

\begin{equation} \mathrm{cost}(T) = \sum_{i=1}^n f_i d_i\,. \end{equation}

Prove that in any minimum cost Huffman tree, the symbol with smallest frequency is at maximum depth in the tree.

3. MST (Greedy)

Let \(G\) be a connected, undirected graph. A \emph{bridge} is an edge \(e=(u,v)\) in graph \(G\) such that every path in \(G\) from \(u\) to \(v\) contains \(e\). Let \(e^*\) be a (not necessarily unique) maximum weight edge in graph \(G\). In the following questions use only elementary properties of graphs.

3.1. Bridge

Prove that if \(e^*\) is a bridge, it is in every minimum spanning tree of \(G\).

3.2. Non-bridge

Prove that if \(e^*\) is not a bridge, there exists some minimum spanning tree \(T\) of \(G\) such that \(e^* \notin T\).