Q1 Compare the average behavior of insertion sort for n elements with that of the n insertions into an initially-empty straight array implementation of a priority queue, described in problem 4.

Q2 Suppose Quicksort always splits the array given into 20% and 80% parts. Draw a recurrence tree for this situation, and compute its complexity.

Q3 Using the Poisson distribution for hashing modeling, find the number of colliding records for a case where r = 1200 and n = 1600. The number of records being hashed is r and the number of slots in the hashtable is n.

Q4 Radix Sort is a sorting procedure where the n keys being sorted are never compared to each other. Each number to be sorted has the same number of digits, d, and the base of the numbers, referred to as the radix is r. The radix sort goes as follows: In each of the d iterations (1..d) the numbers are placed in lists numbered 0 through r-1, according to the value of the dth least significant digit. After a pass, all lists are merged so that all elements in list 0 are followed by all elements in list 1, followed by all elements in list 2, ... with all elements in list r-1 at the end. The process repeats for all digits from least significant (right-most) to the most significant (left-most).

Recall a number is base r has digits 0 .. r-1.

a.Use the sequence of numbers below in base r = 3, and show each iteration result of the radix sort.

201 200 121 011 001 022 002 222 111 110

b. Analyze the complexity of radix sort for n numbers in base r, with d digits.