CSPB 3104 Assignment 2

CSPB 3104 Assignment 2

$30.00

Download Details:

  • Name: Problem-Set-2-Divide-And-Conquer-amh9w1.zip
  • Type: zip
  • Size: 13.01 KB
Category:

Description

5/5 - (1 vote)

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
  1. The algorithm first divides an array of size n into 3 roughly equal parts.
  2. Next, it uses the function coalesce_arrays_into_two(a1, a2, a3) that runs in Θ(n) time, returning two arrays b1 and b2 of size n4 each.
  3. The function is then recursively called on b1 and b2.
  4. 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 a and b of the sizes m and n, respectively. A “dominance” of a over b is a pair of indices (i,j) such that a[i]>b[j]. Note that i is an index of array a and j must be an index of array b.

Write a brute force algorithm that counts the number of dominances of a over b that runs in Θ(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) 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 A, if it exists, is an index i such that A[i]=i. Given a sorted array A 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 A 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 -1
def 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]))

Related products