Complexity, Priority Queues, and Quicksort

Exercise 1: Runtime complexity (14 points)

a) Suppose that you observe the following running times for a program with an input of size N.

N	Time
5,000	0.2 seconds
10,000	1.2 seconds
20,000	3.9 seconds
40,000	16.0 seconds
80,000	63.9 seconds

Estimate the running time of the program (in seconds) on an input of size N = 200,000.

b) For each of the following functions, give the best matching order of growth of the running time.

A. log N B. N C. N log N D. N^2 E. N^3 F. 2^N G. 3^N H. N!

def f1(N):
    x = 0
    for i in range(N):
        x += 1
    return x

def f2(N):
    x = 0
    for i in range(N):
        for j in range(i):
            x += f1(j)
    return x

def f3(N):
    if N == 0:
        return 1
    x = 0
    for i in range(N):
        x += f3(N - 1)
    return x

def f4(N):
    if N == 0:
        return 0
    return f4(N // 2) + f1(N) + f1(N) + f1(N) + f4(N // 2)

def f5(N):
    if N == 0:
        return 1
    return f6(N - 1) + f6(N - 1) + f6(N - 1)

def f6(N):
    x = 0
    while N > 0:
        x += 1
        N = N // 2
    return x

Exercise 2: Priority Queue (25 points)

1. Suppose that the sequence P R I O * R * * I * T * Y * * * Q U E * * * U * E (where a letter means insert and an asterisk means remove-the-maximum) is applied to an initially empty priority queue. Give the sequence of letters returned by the remove-the-maximum operations.
2. Explain how to use a priority queue to implement the stack presented in the lecture.
3. A 3-heap is an array representation of a complete ternary tree, where the key in each node is greater than or equal to the keys in each of its children. Perform a delete-the-maximum operation on the following 3-heap, using 1-based indexing.

Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
Heap	--	88	33	77	66	10	30	25	23	60	75	14	21	50	9	7

Include the resulting 3-heap in your submission and clearly mark which entries changed during the operation.

Exercise 3: Quicksort (10 points)

1. Show, in the style of the trace given with partition(), how that method partitions the array {E, A, S, Y, Q, U, E, S, T, I, O, N}.
2. Show, in the style of the quicksort trace given in the lecture, how quicksort sorts the array {E, A, S, Y, Q, U, E, S, T, I, O, N}. For this exercise, ignore the initial shuffle.