1. Implement selection sort using the C/C++programming language and the array data structure (use an array of type int and of size at least 15). Here is the pseudocode.

Note: You can either have the size of the array as an input and then user-input each element. Or you can hard-code the array into your source code (make sure the size is at least 15). Also, make sure you start with an unsorted array and you output (using a for loop and printf) the resulting sorted array. The for loop limits are inclusive i.e. <= instead of <.

Input: Array A[n]

for i = 0 to n-2

min = i for j = i+1 to n-1

if( A[j] < A[min])

min = j

end if

end for

if( min != i) swap A[i] and A[min]

end if

end for

2. What is the worst-case time complexity of selection sort (in big-O notation)? Make sure to justify your answer (explain how you deduced it).

3. Show that 2^3 +7^2 +3+1=(^3)

4. Show that 1 + 3 + 3^2 + 3^3 + + 3^ = (3^)