Homework 1

Download the corresponding ipynb file here: hw-1.ipynb.

Selection Sort

Consider sorting n numbers stored in array A[0:n-1] by first finding the smallest element of A[0:n-1] and exchanging it with the element in A[0]. Then find the smallest element of A[1:n-1], and exchange it with A[1]. Then find the smallest element of A[2:n-1], and exchange it with A[2]. Continue in this manner for the first (n-1) elements of A.

Exercise 1 (2 points) Why does it need to run for only the first (n-1) elements, rather than for all n elements?

Solution. The algorithm SELECTION-SORT works by keeping a sorted subarray A[0:i-1] and the unclean subarray A[i:n-1]. While incrementing i, this property is maintained by first finding the smallest element of A[i:n-1] and exchanging it with A[i] so that A[0:i] becomes sorted and A[i+1:n-1] unclean. This is done repeatedly for i=0 to i=n-2.

When i becomes n-2, then A[0:n-3] is sorted and A[n-2:n-1] (just two elements!) is unclean. Note that all the elements of A[0:n-3] are no bigger than these two elements at this point. If A[n-2:n-1] is already sorted, we are done. If not, i.e., A[n-2]>A[n-1], then the inner for-loop exchanges them after finding the smallest of the two. Hence, the entire array becomes sorted.

Exercise 2 (2 points) Describe the worst-case input for the algorithm.

Solution. There are two ways to argue about this.

  1. Note that for any input array, the running time is still quadratic. Therefore, there is no best- or worst-case input to SELECTION-SORT.

  2. Let us not think in terms of big-O notation, rather think of the worst input in terms of economizing on computational steps. The worst-case input is an array of numbers in decreasing order. In this case, id, the index of the smallest element of A[i:n-1], gets updated for each iteration of the inner for-loop (line #7).

Exercise 3 (3 points) Give the worst-case running time of selection sort in terms of the input size n. Try to be as thorough as possible.

Solution. The short answer is the worst-case running time is quadratic.

Long Answer: In order to simplify the calculations, we can safely assume that the constants c_i’s are all 1.

Line Cost Times
2 1 n (checking i)
4 1 n-1
5 1 \sum_{i=0}^{n-2}(n-i)
6 1 \sum_{i=0}^{n-2}(n-i-1)
7 1 \sum_{i=0}^{n-2}(n-i-1)
9 1 \sum_{i=0}^{n-2}(n-i-1)
11 1 (n-1)
12 1 (n-1)

So, \begin{align*} T(n) &=4n - 3 + \sum_{i=0}^{n-2}\left[(n-i) + 3(n-i-1)\right] \\ &=4n - 3 + \sum_{i=0}^{n-2}\left[4n-4i-3\right] \\ &=4n - 3 + \left[\sum_{i=0}^{n-2}4n- \sum_{i=0}^{n-2}4i- \sum_{i=0}^{n-2}3\right] \\ &=4n - 3 + \left[4n\cdot(n-1)- 4\cdot\frac{(n-2)(n-1)}{2} - 3\cdot(n-1)\right] \\ &=4n - 3 + (n-1)\left[4n- 2(n-2) - 3\right] \\ &=4n - 3 + (n-1)(2n+1) \\ &=4n - 3 + (2n^2 -n -1) \\ &=2n^2 + 3n -4. \end{align*} We now know that T(n) is O(n^2).

Exercise 4 (3 points) Implement SELECTION-SORT in Python.

Solution. 

# Implement the algorithm in Python
def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        id = i
        for j in range(id + 1, n):
            if arr[j] < arr[id]:
                id = j
        arr[i], arr[id] = arr[id], arr[i]

Median

Exercise 5 (5 points) Write a Python program to find the median of two sorted arrays of different sizes. I am looking for not the most efficient algorithm, but something that’s correct, bug-free, and well-documented.

Solution. 

def median(arr1, arr2): # Since the input bounds are not mentioned. I'm not considering the edge cases for the arrays being [].
    m, n = len(arr1), len(arr2)
    i, j = 0, 0
    sorted_ = []
    while i < m and j < n:
        if arr1[i] < arr2[j]:
            sorted_.append(arr1[i])
            i += 1
        else:
            sorted_.append(arr2[j])
            j += 1
    while i < m:
        sorted_.append(arr1[i])
        i += 1
    while j < n:
        sorted_.append(arr2[j])
        j += 1
    mid = (m+n) // 2
    return sorted_[mid] if (m+n) % 2 == 1 else (sorted_[mid-1]+sorted_[mid]) / 2

Exercise 6 (5 points) Analyze the time complexity of your algorithm using a table.

Solution. Only the first while loop will affect the time for different inputs.

Best Case: When min of one array is greater than the max of other array, the first while loop will run for less no of times, which in turn reduces the no of comparisons made inside that loop. This will run for either len(arr1) times or len(arr2) times.

Worst Case: When both the arrays have the same elements the first loop will run for len(arr1)+len(arr2)-1 times which will result in more comparisons inside the loop.

Line Number Best Case Worst Case
Line 1: For both best and worst cases, function declaration takes constant time. c1 c1
Line 2: In both the cases, it takes constant amount of time to get the lengths of both the arrays. c2 c2
Line 3: In both the cases, the two assignments for i, j will take constant time. c3 c3
Line 4: In both the cases, Creating and assigning an empty list will take constant time. c4 c4
Line 5: In the best case, the while loop runs for m or n times. In the worst case it runs for m+n-1 times. (m or n)*c5 (m+n-1)*c5
Line 6: It takes constant time for comparison but it will run for same number of times as line 5 (m or n)*c6 (m+n-1)*c6
Line 7: In best case, if arr2 has larger elements, appending will run for m times else 0 times. (m or 0)*c7 ((m+n)/2)*c7
Line 8: Same as the above line, but increment operation time differs. (m or 0)*c8 ((m+n)/2)*c8
Line 9: In best case, if arr2 has larger elements,loop will run for 0 times else n times. (0 or n)*c9 ((m+n)/2)*c9
Line 10: Same as the line 9 with difference in the increment operation time. (0 or n)*c10 ((m+n)/2)*c10
Line 11: In best case second while loop runs for m times or 0 times. In worst case it will take m-i or 0 times. (m or 0)*c11 (m-i or 0)*c11
Line 12&13: Same as line 11 (m or 0)*c13 (m-i or 0)*c13
Line 14: In best case second while loop runs for n times or 0 times. In worst case it will take n-j or 0 times. (0 or n)*c14 (n-j or 0)*c14
Line 15&16: Same as line 14 (0 or n)*c16 (0 or n-j)*c16
Line 17: Integer division and assignment takes constant time for both cases c17 c17
Line 18: return statement with median calculation takes constant time irrespective of the size of the arrays c18 c18

On a high level, the first loop runs for either m or n or m+n-1 times. And the other two loops run for either n or m or 1 time. And all the other operations takes constant time. So in total all these cases results in order of m + n time where m, n are lengths of arrays m and n.

Therefore the time taken in both the cases is in \mathcal{O}(m+n).