Written Assignment

Q 1 - Sort all the functions below in increasing order of asymptotic (big-O) growth. If some have the same asymptotic growth, then be sure to indicate that. As usual, lg means base 2.

5n

5n4

4lg(n)

n2

nn

55n2

100n3

4lg( lg( n))

Q1 - Sort all the functions below in increasing order of asymptotic (big-O) growth. If some have the same asymptotic growth, then be sure to indicate that. As usual, lg means base 2.

The sorted functions in increasing order of asymptotic (big-O) growth are:

1. 4lg(lg(n))
2. 4lg(n)
3. 5n
4. nn (same asymptotic growth as 100n^3, but it's convention to write it separately)
5. 100n^3
6. n^2
7. 5n^4
8. 5^(5n^2)

Q 2 - Consider sorting n numbers stored in array A by first finding the smallest element of A and exchanging it with the element in A[1]. Then find the second smallest element of A, and exchange it with A[2]. Continue in this manner for the first n_1 elements of A. Write pseudocode for this algorithm, which is known as selection sort.

Q2 - Pseudocode for Selection Sort:

SelectionSort(A):

    n = length(A)

    for i = 0 to n-2:

        minIndex = i

        for j = i+1 to n-1:

            if A[j] < A[minIndex]:

                minIndex = j

        swap A[i] and A[minIndex]

Q 3 - What loop invariant does this algorithm maintain?

Q3 - The loop invariant maintained by the selection sort algorithm is that after the ith iteration of the outer loop (0-based indexing), the first i elements of the array A are sorted in ascending order.

Q 4 - Why does it need to run for only the first n - 1 elements, rather than for all n elements?

Q4 - The algorithm needs to run for only the first n - 1 elements because after the (n-1)st element is placed in its correct position, the nth element will automatically be in the correct position. Therefore, no swapping is required for the last element, resulting in unnecessary iterations.

Q 5 - Give the best-case and worst-case running times of selection sort in, ? - notation. Write, compile, and run your selection sort algorithms in Java or Python. Include your Java IDE or Python IDLE source code and screenshots of your output.

Q5 - The best-case and worst-case running times of selection sort in ?-notation are both O(n^2).

Here's an example implementation of selection sort in Python:

def selection_sort(arr):

    n = len(arr)

    for i in range(n - 1):

        min_index = i

        for j in range(i + 1, n):

            if arr[j] < arr[min_index]:

                min_index = j

        arr[i], arr[min_index] = arr[min_index], arr[i]

# Example usage

arr = [64, 25, 12, 22, 11]

selection_sort(arr)

print("Sorted array:", arr)

Output:

Sorted array: [11, 12, 22