Quiz 04

Consider the following code, which takes in a list of integers and moves all of the odd numbers to the front and all of the even numbers to the end, in-place.

Remember that the \(\%\) operator computes the remainder of division. For example \(5 \% 2 = 1\) and \(4 \% 2 = 0\). This can be used to check if a number is even; if \(x \% 2 = 0\), then x is even.

def separate_odd_from_even(numbers):
    """Moves the odd numbers to the front, in-place."""
    n = len(numbers)

    def swap(i, j):
        numbers[i], numbers[j] = numbers[j], numbers[i]

    odd_barrier = 0
    even_barrier = n - 1

    while odd_barrier < even_barrier:
        if numbers[odd_barrier] % 2 == 0:
            # the number is even
            swap(odd_barrier, even_barrier)
            even_barrier -= 1
        else:
            # the number is odd
            odd_barrier += 1

Consider this code which partitions a list in a special way:

def is_even(i):
    """Returns True if i is even, False otherwise."""
    return i % 2 == 0

def mystery_partition(numbers):
    def swap(i, j):
        numbers[i], numbers[j] = numbers[j], numbers[i]

    barrier_ix = 0
    for i in range(len(numbers)):
        if is_even(numbers[i]):
            swap(i, barrier_ix)
            if numbers[barrier_ix] > numbers[0]:
                swap(0, barrier_ix)
            barrier_ix += 1

Which of the following loop invariants are true for this code? Select all that apply.

Note: any statement about an empty set or list is considered to be automatically true.

True or False: quickselect requires the input array to be sorted in order to function correctly.

True or False: in order to guarantee that its output is correct, quickselect must be called on a sorted list.

Which of the following are properties of Quicksort? Select all that apply.

Recall the partition operation from quickselect. Which of the following arrays could have been partitioned at least once? Select all that apply.

Which of the following arrays could have been partitioned at least once? (Select all that apply)

Hint: there are three.

The code for quickselect is shown below. It is the same as the code provided in lecture, except that it contains an added print statement.

import random 
def quickselect(arr, k, start, stop):
    """Finds kth order statistic in numbers[start:stop])"""
    print("hello world!") # <--- here is the print
    pivot_ix = random.randrange(start, stop)
    pivot_ix = partition(arr, start, stop, pivot_ix)
    pivot_order = pivot_ix + 1
    if pivot_order == k:
        return arr[pivot_ix]
    elif pivot_order < k:
        return quickselect(arr, k, pivot_ix + 1, stop)
    else:
        return quickselect(arr, k, start, pivot_ix)

Suppose quickselect(arr, 3, 0, 10) is called with arr = [5, 2, 8, 3, 1, 6, 9, 7, 4, 0].

Suppose a quickselect is being performed on an array. In the middle of the quickselect, you are told that the array has been partitioned exactly twice thus far, and that the third order and sixth order statistics have been identified as a result. Which one of the following arrays is partitioned in this manner?

Suppose quickselect is used on an array of size 11 to find the median. The median is located as the second element of the array (at index 1), but the rest of the array is sorted in descending order. If we change the behavior of quickselect so that the pivot index is no longer random, instead always choosing start as the pivot index (pivot_ix = start), how many calls to quickselect will need to be made to find the median? Assume that quickselect is using the in_place_partition algorithm from lecture. You may also assume that for the first call of quickselect start = 0 and stop = len(arr).

True or False: the below is a binary search tree.

Consider the following binary search tree:

How many comparisons does it take to query 3? That is, how many times is 3 compared to another number during a query?

Consider the following binary search tree:

Where should we insert 49 ?

Draw the binary search tree that results from inserting the following nodes into an initially empty tree, in the order given: 5, 3, 1, 8, 4, 2, 6.

Solution

Suppose the numbers 41, 32, and 40 are inserted (in that order) into the below binary search tree. Draw where the new nodes will appear.

Suppose the numbers 41, 32, and 33 are inserted (in that order) into the below binary search tree. Draw where the new nodes will appear.

Define the largest gap in a collection of numbers (also known as its range) to be greatest difference between two elements in the collection (in absolute value). For example, the largest gap in \(\{4, 9, 5, 1, 6\}\) is 8 (between 1 and 9).

Suppose a collection of \(n\) numbers is stored in a balanced binary search tree. What is the time complexity required of an efficient algorithm to calculate the largest gap in the collection? State your answer as a function of \(n\) in asymptotic notation.

Define the largest gap in a collection of numbers to be the largest difference between two distinct elements in the collection (in absolute value). For example, the largest gap in \(\{4, 9, 1, 6\}\) is 8 (between 1 and 9).

Suppose a collection of \(n\) numbers is stored in a balanced binary search tree. What is the time complexity required for an efficient algorithm to calculate the largest gap of the numbers in the BST? State your answer as a function of \(n\) in asymptotic notation.

Suppose a collection of \(n\) numbers is stored in a balanced binary search tree. What is the time complexity required of an efficient algorithm to calculate the mean of the collection? State your answer as a function of \(n\) in asymptotic notation.

Define the smallest gap in a collection of numbers to be the smallest difference between two distinct elements in the collection (in absolute value). For example, the smallest gap in \(\{4, 9, 1, 6\}\) is 2 (between 4 and 6).

Suppose a collection of \(n\) numbers is stored in a balanced binary search tree. What is the time complexity required for an efficient algorithm to calculate the smallest gap of the numbers in the BST? State your answer as a function of \(n\) in asymptotic notation.

Consider the following .insert() method for a binary search tree:

def insert(self, new_key):
    # assume new_key is unique
    current_node = self.root
    parent = None

    # find place to insert the new node
    while current_node is not None:
        parent = current_node
        if current_node.key < new_key:
            current_node = current_node.right
        else: # current_node.key > new_key
            current_node = current_node.left

    # create the new node
    new_node = Node(key=new_key, parent=parent)

    # if parent is None, this is the root. Otherwise, update the
    # parent's left or right child as appropriate
    if parent is None:
        self.root = new_node
    elif parent.key < new_key:
        parent.right = new_node
    else:
        parent.left = new_node

Let's say we want to insert a new number \(x\) into a binary search tree.Define height_left as the height of the left half of the binary tree (the root and everything to the left of it), and height_right as the height of the right side. For this problem, measure height as the number of nodes on the longest path starting at the root (so a tree consisting of only a root has height 1). Let height_left be greater than height_right. In the worst case, how many iterations of the while loop of .insert() will need to be completed?

Suppose bst is a binary search tree with \(n\) nodes constructed in the following way:

bst = BinarySearchTree()
for i in range(n):
    if i % 2 == 0:
        bst.insert(i)

What is the time complexity of the following code?

for i in range(n):
    bst.query(i)

Suppose a collection of unique numbers is stored in a balanced binary search tree, and that each node in the tree has been given a .size attribute which contains the number of nodes in the subtree rooted at that node. What is the time complexity required of an efficient algorithm for computing the number of elements in the collection which are larger than some threshold, \(t\)?