Description
Question 1
Answer the following questions about heaps.
1(a) Write down an algorithm to find the third smallest element in a minheap with more than 33 elements. You may write pseudocode or english description of the algorithm’s steps. What is the running time complexity on a heap of size nn? * Assume all elements in the heap are distinct *
YOUR ANSWER HERE
1(b) We wish to find the largest element in a min-heap represented by array A[1],…,A[n]A[1],…,A[n]. Show using a series of examples for n=7n=7 that any element starting from A[⌈n2⌉],…,A[n]A[⌈n2⌉],…,A[n] can be the largest element. Your answer should be in the form of 4 min heaps.
YOUR ANSWER HERE
Question 2
Suppose you have an array A of n distinct elements.
The following pseudocode finds the k biggest values of A:
Biggest(A, k): \\returns an array of the k biggest values of A
mergesort(A)
return A[n-k, n]2(a) What is the complexity of the above algorithm and why?
YOUR ANSWER HERE
2(b) Now suppose that the order of the array was important. Design and implement an algorithm that returns an array of the k largest elements of A in their original order, and it should run in Θ(nk)Θ(nk) time.
For example, BiggestInOrder([0,5,1,3,4], 3) should return [5,3,4].
def BiggestInOrder(A, k):
# YOUR CODE HERE
raise NotImplementedError()2(c) If we don’t care about the original ordering, then we can use a heap to design an algorithm that runs faster than the one in part (b). Design and implement an algorithm that returns an array of the k largest elements of A using a heap.
def BiggestOutOfOrder(A, k):
# YOUR CODE HERE
raise NotImplementedError()2(d) What is the complexity of your algorithm for part (c)?
YOUR ANSWER HERE
Testing your solutions — Do not edit code beyond this point
from random import sample, randint
def testBiggestInOrder(n_tests, test_size):
n_passed = 0
n_failed = 0
for i in range(0, n_tests):
a = sample( range(-10 * n_tests, 10 * n_tests ), test_size)
k = randint(1, len(a))
kbiggest = BiggestInOrder(a.copy(), k)
if len(kbiggest) != k:
if n_failed < 10:
print(' Code returns the wrong sized array!')
n_failed += 1
continue
if sorted(kbiggest) != sorted(a)[-k:]:
if n_failed < 10:
print(' Code did not return the ', k, ' biggest elements!')
print(' Code returned ', sorted(kbiggest), ' but we wanted ', sorted(a)[-k:], ' of ', a)
n_failed +=1
continue
currIndex = 0
inOrder = True
for j in range(0, len(kbiggest)):
for l in range(currIndex, len(a)):
if kbiggest[j] == a[l]:
currIndex = l
break
if l == len(a) - 1:
inOrder = False
if inOrder == False:
if n_failed < 10:
print(' Code failed for input: ', a, 'returned : ', kbiggest, 'last correct index: ', currIndex)
else:
n_passed = n_passed + 1
return n_passed
n_tests = 10000
n_passed = testBiggestInOrder(10000, 10)
print(' num tests = ', n_tests)
print(' num passed = ', n_passed)from random import sample, randint
def testBiggestOutOfOrder(n_tests, test_size):
n_passed = 0
n_failed = 0
for i in range(0, n_tests):
a = sample( range(-10 * n_tests, 10 * n_tests ), test_size)
k = randint(1, len(a))
kbiggest = BiggestOutOfOrder(a.copy(), k)
if len(kbiggest) != k:
if n_failed < 10:
print(' Code returns the wrong sized array!')
n_failed += 1
continue
if sorted(kbiggest) != sorted(a)[-k:]:
if n_failed < 10:
print(' Code did not return the ', k, ' biggest elements!')
print(' Code returned ', sorted(kbiggest), ' but we wanted ', sorted(a)[-k:], 'where a is', a)
n_failed += 1
continue
n_passed = n_passed + 1
return n_passed
n_tests = 10000
n_passed = testBiggestOutOfOrder(10000, 10)
print(' num tests = ', n_tests)
print(' num passed = ', n_passed)
