1.) For question 1, consider the given array of integers, and assume that we are sorting elements in ascending (increasing) order.

(Part- A.)

Show the array 17, 10, 15, 13, 4, 12, 7, 9, 16, 8, 5, 14, 3 after each pass of the Insertion sort (after placing each element from the unsorted part of the list into the sorted part of the list). Underline the sorted part of the list. (Note- The first pass has already been done for you.)

17, 10, 15, 13, 4, 12, 7, 9, 16, 8, 5, 14, 3 (Original array)

10, 17, 15, 13, 4, 12, 7, 9, 16, 8, 5, 14, 3 (After the first pass)

(Part- B.)

Show the array 17, 10, 15, 13, 4, 12, 7, 9, 16, 8, 5, 14, 3 after each pass of the Bubble sort (bubbling up the smallest element to the top). Show the result after each pass. (Note- The first pass has already been done for you.)

17, 10, 15, 13, 4, 12, 7, 9, 16, 8, 5, 14, 3 (Original array)

3, 17, 10, 15, 13, 4, 12, 7, 9, 16, 8, 5, 14 (After the first pass)

(Part- C.)

Show intermediate steps of sorting the array 17, 10, 15, 13, 4, 12, 7, 9, 16, 8, 5, 14, 3 with Merge Sort. Show the result after each recursive call to Merge Sort.

17, 10, 15, 13, 4, 12, 7, 9, 16, 8, 5, 14, 3 (Original array)

10, 17, 15, 13, 4, 12, 7, 9, 16, 8, 5, 14, 3 (After we merged 10 and 17)

(Part- D.)

Show intermediate steps of sorting the array 17, 10, 15, 13, 4, 12, 7, 9, 16, 8, 5, 14, 3 with Quick Sort. Show the result after picking a pivot for each sublist and arranging the list in such a way that all elements pivot are on the left side of the pivot, and all elements = pivot are on the right. Pick the middle element of a sublist as the pivot.

17, 10, 15, 13, 4, 12, 7, 9, 16, 8, 5, 14, 3 (Original array)

2.) Give running times for each of the following functions:

(Part- A.)

int func1(int n) { int s = 0; int i = n; while ( i >= 0 ) { int j = n*n; while ( j >= 1) { j = j / 2; s = s + i*j; } i = i - 4; } return s; }

(Part- B.)

//Note: function func2 calls the function func1 defined in question 5 (Part- A.) int func2(int n) { int res = func1(n*n); if (res > 1000) { for (int k =0; k < n; k++) { res += func1(n); } } return res; }

6.) Consider the following recursive function:

int recursive1(int n) { if (n > 1) { return 2 * recursive1(n-1); } else { return n; } }

(Part- A.) Describe what the function computes

(Part- B.) Give a recurrence relation that describes the running time of this recursive function (give both base and recursive cases)

(Part- C.) Solve the recurrence relation to get running time by using the repeated substitution method