CSPB 3104 Assignment 2 solved

CSPB 3104 Assignment 2 solved

$30.00

Original Work ?

Download Details:

  • Name: Problem-Set-2-Divide-And-Conquer-y5l88c.zip
  • Type: zip
  • Size: 13.01 KB
Category: You will Instantly receive a download link upon Payment||Click Original Work Button for Custom work
Share This

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)Θ(n) time, returning two arrays b1 and b2 of size n4n4 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Β 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 -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