Description
Question 1: Setting Up and Solving Recurrences
Consider the python-like pseudocode below
def div_and_conquer_fun(a):
# a is an array of size n
n = length(a)
if n == 0:
return 0
if n == 1:
return a[1]
# 1. Divide into 3 parts
a1 = a[1 ... n//3]
a2 = a[n//3+1 ... 2*n//3]
a3 = a[2*n//3+1 ... n]
# note // denotes integer division a//b := floor(a/b)
(b1, b2) = coalesce_arrays_into_two(a1, a2, a3)
# note b1, b2 are arrays of size n//4 each.
c1 = div_and_conquer_fun(b1)
c2 = div_and_conquer_fun(b2)
return c1 + c2 // Theta (1) time- The algorithm first divides an array of size n into 3 roughly equal parts.
- Next, it uses the function
coalesce_arrays_into_two(a1, a2, a3)that runs in Θ(n)Θ(n) time, returning two arraysb1andb2of size n4n4 each. - The function is then recursively called on
b1andb2. - Finally, the result is summed up and returned.
Write down a recurrence relation for the running time of the divide and conquer function above. Use master method to solve the recurrence: write down which case of the master method and the result.
YOUR ANSWER HERE
Question 2(a): Counting Dominances
Suppose you are given two sorted arrays aa and bb of the sizes mm and nn, respectively. A “dominance” of aa over bb is a pair of indices (i,j)(i,j) such that a[i]>b[j]a[i]>b[j]. Note that ii is an index of array aa and jj must be an index of array bb.
Write a brute force algorithm that counts the number of dominances of aa over bb that runs in Θ(n2)Θ(n2) time.
#Answer 2(a):
def count_dominances_brute_force(a, b):
# YOUR CODE HERE
raise NotImplementedError()
Question 2(b): Counting Dominances
However, the brute force algorithm is suboptimal. Design a Θ(n)Θ(n) algorithm to count the number of dominances. Do this by modifying the merge algorithm we studied as part of merge sort. Instead of merging the two sorted arrays, count the number of dominances.
#Answer 2(b):
def count_dominances(a, b):
# YOUR CODE HERE
raise NotImplementedError()Question 2(c): Counting Dominances
Explain the logic behind your solution to Question 2(b) briefly (5 lines).
YOUR ANSWER HERE
Question 3(a): Finding a Fixed Point.
A fixed point of an array AA, if it exists, is an index ii such that A[i]=iA[i]=i. Given a sorted array AA of distinct integers, return the index of the fixed point if one exists, or otherwise, return -1 to signal that no fixed point exists. Your algorithm must be as efficient as possible.
#Answer 3(a)
def find_fixed_point(a):
# YOUR CODE HERE
raise NotImplementedError()Question 3(b):
Explain your solution to the problem briefly and derive its running time complexity.
YOUR ANSWER HERE
Question 3(c): Finding a Fixed Point Again.
Given a sorted array AA of distinct natural numbers, return the index of the fixed point if one exists, or otherwise, return -1 to signal that no fixed point exists. Your algorithm must be as efficient as possible.
#Answer 3(c)
def find_fixed_point_natural(a):
# YOUR CODE HERE
raise NotImplementedError()Question 3(d)
Explain your solution to the problem briefly and derive its running time complexity. (Hint: Your algorithm should be quicker than your algorithm for part (a).)
YOUR ANSWER HERE
Testing your solutions — Do not edit code beyond this point
# This code runs 5 test cases on your two algorithms
def test_count_dominances(func):
a1 = [ 5, 7, 10]
b1 = [ 1, 2, 3]
n1 = 9
a2 = [ 6, 10, 15, 21]
b2 = [ 4, 19, 25, 32]
n2 = 5
a3 = [ 6, 10, 15, 21]
b3 = []
n3 = 0
a4 = [ 1, 3, 5, 7, 9, 11, 13]
b4 = [ 2, 4, 6, 8, 10]
n4 = 20
a5 = [1, 3, 5, 6, 7, 9, 11, 13]
b5 = [2, 4, 6, 6, 6, 8, 10]
n5 = 30
problems = [(a1, b1, n1), (a2, b2, n2), (a3, b3, n3), (a4, b4, n4), (a5, b5, n5)]
num_passed = 0
for (a, b, n) in problems:
res = func(a, b)
if res == n:
num_passed = num_passed + 1
else:
print('FAILED: a = ', a, 'b = ', b, ' expected = ', n, 'your code = ', res)
print('--- Done ---')
print ('Num tests = ', len(problems))
print ('Num passed = ', num_passed)print('Testing brute force:')
test_count_dominances(count_dominances_brute_force)print('Testing modified merge algorithm:')
test_count_dominances(count_dominances)from random import sample
def compare_brute_force_vs_fast():
a = sorted( sample (range(60), 20) )
b = sorted( sample (range(60), 20) )
n1 = count_dominances_brute_force(a, b)
n2 = count_dominances(a, b)
if n1 != n2:
print('Disparity observed between two algorithms:', a, b, n1, n2)
return False
return True
print('Comparing the two implementations.')
num_passed = 0
total = 100
for i in range(total):
if compare_brute_force_vs_fast():
num_passed = num_passed + 1
print(' -- all tests done -- ')
print(' passed = ', num_passed, ' out of ', total)print(find_fixed_point([-10, -5, -2, 2, 3, 5, 7, 10, 15, 25, 35, 78, 129]))def find_fixed_point_very_naive(a):
n = len(a)
for i in range(0, n):
if a[i] == i:
return i
return -1def test_find_fixed_point_code(n_tests, test_size):
n_passed = 0
for i in range(0, n_tests):
a = sorted( sample( range(-10 * n_tests, 10 * n_tests ), test_size))
j = find_fixed_point(a)
if j >= 0 and a[j] != j:
print(' Code failed for input: ', a, 'returned : ', j, 'expected:', find_fixed_point_very_naive(a))
elif j < 0:
assert j == -1, 'Your code returns an illegal negative number: have you implemented it yet?'
k = find_fixed_point_very_naive(a)
if k >= 0:
print('Code failed for input', a)
print('Your code failed to find a fixed point')
print('However, for j = ', k, 'a[j] =', a[k])
else:
n_passed = n_passed + 1
else:
n_passed = n_passed + 1
return n_passed
n_tests = 10000
n_passed = test_find_fixed_point_code(10000, 10)
print(' num tests = ', n_tests)
print(' num passed = ', n_passed)print('Test: expected answer = 5, your answer = ', find_fixed_point([-10, -5, -2, 2, 3, 5, 7, 10, 15, 25, 35, 78, 129])) def test_find_fixed_point_natural_code(n_tests, test_size):
n_passed = 0
for i in range(0, n_tests):
a = sorted( sample( range(0, 10 * n_tests ), test_size))
j = find_fixed_point_natural(a)
if j >= 0 and a[j] != j:
print(' Code failed for input: ', a, 'returned : ', j, 'expected:', find_fixed_point_very_naive(a))
elif j < 0:
assert j == -1, 'Your code returns an illegal negative number: have you implemented it yet?'
k = find_fixed_point_very_naive(a)
if k >= 0:
print('Code failed for input', a)
print('Your code failed to find a fixed point')
print('However, for j = ', k, 'a[j] =', a[k])
else:
n_passed = n_passed + 1
else:
n_passed = n_passed + 1
return n_passed
n_tests = 10000
n_passed = test_find_fixed_point_natural_code(10000, 10)
print(' num tests = ', n_tests)
print(' num passed = ', n_passed)print('Test: expected answer = 0, your answer = ', find_fixed_point_natural([0,1, 2, 3, 5, 7, 10, 15, 25, 35, 78, 129]))
