[SOLVED] Cspb 3104 assignment 4

Question 1

Your professor has the brilliant idea of using heaps to select the pivot in the quicksort algorithm as follows:

• Heapify the array aa.
• Choose a leaf element at random (i.e, an element in A[⌈n2⌉],…,A[n]A[⌈n2⌉],…,A[n] ) and use it as a pivot.
• Apply Lomuto’s partitioning.

  If this scheme is used in quicksort, what is the worst case complexity of the resulting algorithm?

YOUR ANSWER HERE

Question 2a: Move Negatives To Left

You are given an input array aa with negative and positive numbers. Write an algorithm that partitions the array so that the negative numbers are moved to the left hand side and positive numbers to the right hand side. However, the relative ordering between the negative numbers should not be altered. However you may alter the ordering amongst the positive numbers.

Input: array a with positive and negative numbers. Size = n.

Output: partitioned array a, index j such that a[0],…,a[j−1]a[0],…,a[j−1] are negative and a[j],…,a[n−1]a[j],…,a[n−1] are positive.

Note since arrays are passed by reference in python, you just need to return j

Constraints: must be done in place. Relative ordering between negative elements unchanged.

Example:

Input array a = [-2, 3, -1, 4, 5, -3, -4, -1, -2, 5]

Output array a = [-2, -1, -3, -4, -1, -2, 3, 5, 5, 4]

Output j = 6

def move_negatives_to_left(a):
    # YOUR CODE HERE
    raise NotImplementedError()

2(b): Give the running time of your solution and briefly explain the logic by clearly writing down the loop invariants that hold during the operation of your algorithm and why these invariants lead to the correct result.

YOUR ANSWER HERE

Question 3: Median of Median Selection.

In the class, we analyzed an approach for pivot selection that used median of 5 medians. Here we explore what happens with median of 3 medians.

1. Divide the input array aa of size n into n3n3 groups of 33 elements each.
2. Calculate the median of each group of 3 to create a new array a^a^ of these medians.
3. Recursively apply the algorithm to find the median of a^a^. Let it be mm.
4. Use mm as the pivot element to partition the original array aa.

3(a) How many elements in the array aa are guaranteed to be less than the chosen pivot mm? How many are guaranteed to be greater? Assume all elements in the array aa are distinct.

YOUR ANSWER HERE

3(b) If mm computed using the median of 3 medians were used to partition the array aa for a quickselect algorithm that is used to find the median of an array aa, write down the recurrence for T(n)T(n), the time taken to find the median of an array of size nn using the quick select algorithm with the median of 3 medians trick.

YOUR ANSWER HERE

3(c) The celebrated “Akra-Bazzi” method shows that the recurrence S(n)=S(αn)+S((1−α)n)+Θ(n)S(n)=S(αn)+S((1−α)n)+Θ(n) with base case S(1)=Θ(1)S(1)=Θ(1) has solution S(n)=Θ(nlog(n))S(n)=Θ(nlog⁡(n)). Use this to show that median of 3 medians trick fails to achieve a linear time algorithm for quickselect. (Note However, as we saw in the lecture, median of 5 medians works to provide Θ(n)Θ(n) deterministic selection algorithm or Θ(nlog(n))Θ(nlog⁡(n)) quicksort that does not depend on randomization in any way).

YOUR ANSWER HERE

Question 4: Detective Work on Pre-Order Traversal of a BST

An BST with integer keys in each node is traversed using pre-order traversal and the keys in each node are presented in the order they are visited as an array aa of nn elements — a:[a[1],…,a[n]]a:[a[1],…,a[n]]. Assume that the elements of this array are all distinct.

4(a) Describe an algorithm to reconstruct the tree in pseudocode. What is the complexity of your algorithm?

Hint: First identify the root of the tree. Next, how do we identify which elements of the array belong to the left subtree of the root, and which elements to the right subtree? Once that is done, can you recursively perform the reconstruction.

Note that you will learn how to build trees properly in your CSPB 2270 class. Here, assume a pseudocode function called build_tree(n, T1, T2) that build a tree with root node n and subtrees T1, T2 and returns it.

YOUR ANSWER HERE

4(b) Describe an algorithm that converts the array obtained using the pre-order traversal of a BST into an array representing the post-order traversal without reconstructing the tree. Hint: Use the previous part but now instead of reconstructing the tree, think of how pre and post order traversals differ.

YOUR ANSWER HERE

Testing your solutions — Do not edit code beyond this point

import random

def unequalArrays(a, b):
    n = min(len(a), len(b))
    for j in range(n):
        if a[j] != b[j]:
            return True
    if len(a) != len(b):
        return True
    return False

def test_move_negatives(a):
    b = [e for e in a if e < 0]
    j0 = len(b)
    j = move_negatives_to_left(a)
    res = True
    if j != j0:
        print('Failed: input =', a)
        print('Failed: expected value j = ', j0, ' Your code obtained j = ', j)
        res = False
    if unequalArrays(b, a[0:j]):
        if res:
            print('Failed: input =', a)
        print('Failed: the LHS portion should be = ', b)
        print('t Your code returned: ', a[0:j])
        res = False
    return res

def createRandomArray(n):
    a = []
    for i in range(n):
        j = random.randint(-1000,1000)
        if j == 0: 
            j = 1
        a.append(j)
    return a

nPassed = 0
nTests = 10000
for i in range(0, nTests):
    a = createRandomArray(9)
    res = test_move_negatives(a)
    if res: 
        nPassed = nPassed + 1
print('Num Tests = ', nTests, ' Passed = ', nPassed)