Homework 3 Optional Problems

Prove that the worst-case expected running time of every randomized comparison-based sorting algorithm is Ω⁡(𝑛⁢log⁡𝑛). (Here the worst-case is over inputs, and the expectation is over the random coin flips made by the algorithm.)?

ANSWER: TBD

Suppose we modify the deterministic linear-time selection algorithm by grouping the elements into groups of 7, rather than groups of 5. (Use the “median-of-medians” as the pivot, as before.) Does the algorithm still run in 𝑂⁡(𝑛) time? What if we use groups of 3?

ANSWER: The median for odd number of elements is the middle element, for even number it’s the first of 2 middle elements. For example, the median of 5 elements is the 3rd element, and it’s also the 3rd for 6 elements. Therefore, the median is the ⌈𝑘2⌉ element for all 𝑘 ≥ 1. Consider the following array:

x x x x x x
x x x x x x x
x x x X x x x
x x x x x x x
x x x x x x

𝑛 =32,𝑚 =5,𝑘 =⌈𝑛𝑚⌉ =7,⌈𝑘/2⌉ =4,number of elements >𝑋 =8,number of elements <𝑋 =11

At least half of the ⌈𝑛5⌉ groups contribute at least 3 elements that are greater than 𝑋, except for the one group that has fewer than 5 elements if 5 does not divide 𝑛 exactly, and the one group containing 𝑋 itself. Discounting these two groups, it follows that the number of elements greater than 𝑋 is at least 3⁢(⌈12⁢⌈𝑛5⌉⌉ −2). It follows from the definition of ceiling that this expression ≥3⁢𝑛10 −6. Similarly, at least 3⁢𝑛10 −6 elements are smaller than 𝑋. Thus, in the worst case, the size of the subarray in the recursive SELECT call is (𝑛 −(3⁢𝑛10 −6)) =7⁢𝑛10 +6.

Therefore, the recurrence relation is: 𝑇⁡(𝑛)≤𝑇⁡(⌈𝑛5⌉)+𝑇⁡(7⁢𝑛10+6)+𝑂⁡(𝑛)≤𝑇⁡(𝑛5)+𝑇⁡(7⁢𝑛10+6)+𝑂⁡(𝑛)

This recurrence is one of the following generic form: 𝑇⁡(𝑛) ≤∑𝑘𝑖=1𝑇⁡(𝑎𝑖⁢𝑛) +𝑂⁡(𝑛),𝑤⁢ℎ⁡𝑒⁢𝑟⁢𝑒⁢∑𝑘𝑖=1𝑎𝑖 ≤1

The solution to the above is given by: 𝑇⁡(𝑛) ={𝑂⁡(𝑛)if ∑𝑘𝑖=1𝑎𝑖<1𝑂⁡(𝑛⁢log⁡𝑛)if ∑𝑘𝑖=1𝑎𝑖=1

Since 15 +710 =910 <1,𝑇⁡(𝑛) =𝑂⁡(𝑛)

Similarly, for 𝑚 =7, the number of elements greater than 𝑋 is at least: 4⁢(⌈12⁢⌈𝑛7⌉⌉ −3) ≥2⁢𝑛7 −8

Therefore, the recurrence relation is 𝑇⁡(𝑛) ≤𝑇⁡(𝑛7) +𝑇⁡(5⁢𝑛7 +8) +𝑂⁡(𝑛)

Since 17 +57 =67 <1,𝑇⁡(𝑛) =𝑂⁡(𝑛)

For 𝑚 =3, the number of elements greater than 𝑋 is at least: 2⁢(⌈12⁢⌈𝑛3⌉⌉ −2) ≥𝑛3 −4

Therefore, the recurrence relation is 𝑇⁡(𝑛) ≤𝑇⁡(𝑛3) +𝑇⁡(2⁢𝑛3 +4) +𝑂⁡(𝑛)

Since 13 +23 =1,𝑇⁡(𝑛) =𝑂⁡(𝑛⁢log⁡𝑛)

Given an array of n distinct (but unsorted) elements 𝑥1,𝑥2,...,𝑥𝑛 with 𝑤1,𝑤2,...,𝑤𝑛 such that ∑𝑘𝑖=1𝑤𝑖 =𝑊, a weighted median is an element 𝑥𝑘 for which the total weight of all elements with value less than 𝑥𝑘 is at most 𝑊2, and also the total weight of elements with value larger than 𝑥𝑘 is at most 𝑊2. Observe that there are at most two weighted medians. Show how to compute all weighted medians in 𝑂⁡(𝑛) worst-case time.

ANSWER: The weighted-median algorithm works as follows. If 𝑛 ≤2, we just return the brute-force solution. Otherwise, we proceed as follows (the pseudocode handles the special case of two medians, this description only applies to finding the lower/only weighted median). We find the actual median 𝑥𝑘 of the n elements and then partition around it. Then compute the total weights of the two halves. If the weights of the two halves are each ≤𝑊2, then the weighted median is 𝑥𝑘. Otherwise, the weighted (lower) median should be in the half with total weight exceeding 𝑊2. The total weight of the “lighter” half is added to the weight of 𝑥𝑘, and the search continues with the heavier half.

WEIGHTED-MEDIAN(x, w, n)
if n == 1
    return x[1]
else if n == 2
    // lower and upper weighted medians
    if w[1] == w[2]
        return {x[1], x[2]}
    else if w[1] < w[2]
        return {x[2]}
    else
        return {x[1]}
else
    // using randomized linear-time selection
    find the median x[k] of X = {x[1], x[2], ..., x[n]}
    // using the O(n) partition algorithm from QuickSort
    partition the set X around x[k]
    // using linear scan
    compute W[L] = sum(x[i] < x[k]) w[i]
    	and W[R] = sum(x[i] > x[k]) w[i]
    // x[k] = lower weighted median
    if W[L] < W/2 and W[R] == W/2      // (1)
        return {x[k], x[k + 1]}
    // x[k] = upper weighted median
    else if W[L] == W/2 and W[R] < W/2 // (2)
        return {x[k - 1], x[k]}
     // x[k] = weighted median
    else if W[L] ≤ W/2 and W[R] ≤ W/2  // (3)
        return {x[k]}
    // by definition of weighted median,
    // it must be on the heavier side
    else if W[L] > W/2                 // (4)
        w[k] = w[k] + W[R]
        X' = {x[i] ∈ X: x[i] ≤ x[k]}
        return WEIGHTED-MEDIAN(X')
    else                               // (5)
        w[k] = w[k] + W[L]
        X' = {x[i] ∈ X: x[i] ≥ x[k]}
        return WEIGHTED-MEDIAN(X')

Example 1:

x = {1, 2, 3, 4, 5}, w = {.15, .1, .2, .3, .25}, n = 5
W = 1, W/2 = .5
Iteration 1:
    k = 3, x[3] = 3, w[3] = .2, W[L] = .25, W[R] = .55
    Case 5
    recurse with x = {3, 4, 5}, w = {.45, .3, .25}, n = 3
Iteration 2:
    k = 2, x[2] = 4, w[2] = .3, W[L] = .45, W[R] = .25
    Case 3
    return {4}

Example 2:

x = {1, 2, 3, 4}, w = {.49, .01, .25, .25}, n = 4
W = 1, W/2 = .5
Iteration 1:
    k = 2, x[2] = 2, w[2] = .01, W[L] = .49, W[R] = .50
    Case 1
    return {2, 3}

We showed in an optional video lecture that every undirected graph has only polynomially (in the number n of vertices) different minimum cuts. Is this also true for directed graphs? Prove it or give a counterexample.

ANSWER: TBD

For a parameter 𝛼 ≥1, an 𝛼-minimum cut is one for which the number of crossing edges is at most 𝛼 times that of a minimum cut. How many 𝛼-minimum cuts can an undirected graph have, as a function of 𝛼 and the number 𝑛 of vertices? Prove the best upper bound that you can.

ANSWER: 𝑛2⁢𝛼. Proof TBD.