Week 6: Exercises

1. Average Partition Size

In quicksort, suppose that use Hoare partitioning and choose pivot elements randomly. In each partition operation, let f be the size of the smaller partition, as a fraction of the number of elements being partitioned in that step. What value do you think f will have, on average? Perform experiments to determine whether your intuition is correct.

2. Incomplete Partitioning

Consider the Hoare partitioning function for quicksort that we saw in the lecture:

def partition(a, lo, hi):
    p = a[randrange(lo, hi – 1)]  # choose random pivot  

    i = lo
    j = hi - 1

    while True:
        # Look for two elements to swap.
        while a[i] < p:
            i += 1
        while a[j] > p:
            j -= 1

        if j <= i:             # nothing to swap
            return j + 1 
        
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1

Suppose that we remove the last two lines from the function above. Show that the function will no longer behave correctly with this change. Specifically, give an example of an input array on which the function will fail.

3. Lost Car

You are standing on a straight road that goes infinitely far in both directions. You remember that you parked your car somewhere on this road, but you don't know how far away it is or in which direction it is.

1. Describe an algorithm that you can use to find your car 100% of the time.

2. Let D be the distance from the start point to your car. What is your algorithm's best-case and worst-case asymptotic running time, as a function of D?

3. Give an exact upper and lower bound on your algorithm's running time, as a function of D.