Please note: All HW assignments are giving you opportunities to learn and to verify the concepts from the topics in the lectures. They are for individual work only. You cannot consult with any other people and cannot copy or receive answers from any people (students or tutors for example) or internet. You are not allowed to work as a team. Usually, some questions may have different correct solutions with the same concept. Cheating will not be tolerated.

Questions and Answers not put in order or no staple of HW submission will not be accepted and counted as 0 points

1. (14%) Below is the pseudo code for Quicksort that we talked about in class. As usual with recursive functions on arrays, we see the array indices p and r as arguments. Quicksort(a, p, r) sorts the part of the array between p and r inclusively. The initial call (that is, to sort the entire array) is Quicksort(A, 0, n – 1).

1/3 a). Let A = {3, 6, 1, 5, 8, 2, 4, 7, 3}, and assume we call Quicksort(A, 0, 8). Show what happens during the first invocation of Partition. What is the value of q returned, and what are the two recursive calls made?

b). What is the running time of Quicksort when all elements of array A have the same value?

c). Briefly sketch why the running time of Quicksort is Ѳ(n 2 ) when the array A contains distinct elements and is sorted in decreasing order.

2. (10%) Draw a Decision Tree to show paths of the number of comparisons to sort the array A{3,1,2} using Insertion Sort.

3. (6%) Here is an array which has just been partitioned by the first step of Quicksort:

2, 0, 1, 3, 4, 7, 6, 5, 8 Which of these elements could have been the pivot? (if there are more than one possibility, list them all)

4. (10%) Sort the following array using radix sort with base 10. For each digit, show the array C used to count and order after sorting each digit.

{751, 543, 689, 264, 837, 160, 239, 937, 592, 961, 799, 885, 393, 177, 236, 364, 412,747}

5. (10%) Illustrate and show how to sort the array A = [6,8,3,1,7,4,4,5,3,2,7,1,8,5,3] using Bucket sort.

6. (10%) Given an array of n different English words and all in lower case with different length. Suggest an algorithm and approach for sorting the words in alphabetic order in O(n) time. Write your pseudo code to solve the problem.

2/3 7. (10%)Suppose you have an array of a million English vocabulary Strings to sort, but you happen to know that there are only four different varieties of Strings in it: “Family”, “Hero”, “Monkey”, and “Together”. You want to sort this vocabulary array to put all the “Family” words first, then all the “Hero”, then all the “Monkey”, then all the “Together” words. How would you do it? You could use merge sort or Quicksort and get a runtime proportional to N log N, where N is ~one million. Can you do better? Adjust your answer by illustrating how to sort it.

8.(10%) Show and explain how to sort n integer numbers in the range 0 to (n 8 -1) in O(n) time?

9. (20%) Use Counting Sort algorithm to sort the array A[5, 5, 0, 6, 2, 0, 1, 3, 2, 6, 1, 4, 2, 4]. You must show each intermediate result of array C and array B step by step. (To receive full points, you must show each intermediate result of array C and array B.)