Reference no: EM132951740

CSC 226 Algorithms And Data Structures - University of Victoria

Question 1. Write an in-place version of the linear selection algorithm, using subarrays of size 7 for the median of medians selection. Use the linearSelect(S,k) algorithm in slides 4 and 5 of lecture 18 and the inPlaceQuickSort(S,a,b) algorithm in the Goodrich and Tamassia textbook (page 255) as your guideline for writing this algorithm. The algorithm should have the following heading,

Algorithm inPlaceLinearSelect(S,a,b,k)
Input: An array, S, of distinct elements; integers a and b with a ≤ b; and integer k ∈ [a + 1, b + 1]
Output: The kth smallest element of S

Question 2. Consider the experiment of tossing a fair coin four times,
a. What is sample space associated with this experiment? Label a heads h and a tails T.
b. Let ?? be the event that heads are flipped first. What is Pr(A)?
c. Let B be the event that exactly two heads and two tails are flipped (in any order). What is Pr(B)?
d. Let ?? and B be as defined above, what is Pr(A ∩ B)?
e. Let X be the number of heads flipped. What is the expected value of X?

Question 3. Suppose you would like to sort n music files using a comparison-based sorting algorithm (i.e. no bucket sort), but you only have an old, unreliable computer, which you have nicknamed "Rustbucket". Every time Rustbucket compares two music files, x and y, there is an independent 50- 50 chance that it has an internal disk fault and returns the value -1, instead of the correct result of 1 for true or 0 for false, to the question, "x ≤ y?" Otherwise, Rustbucket correctly performs every other kind of operation (including comparisons not involving music files.) Describe an efficient algorithm that can use Rustbucket to sort n music files correctly and show that your algorithm has expected running time that is O(n log n).

Question 4. Draw the 11-item hash table resulting from hashing the keys 12, 44, 13, 88, 23 94, 11, 39, 20, 16, and 5, using hash function h(k) = (2k + 5) mod 11, assuming collisions are handled by each of the following:
a. Separate chaining.
b. Linear probing.
c. Quadratic probing.
d. Double hashing using the secondary hash function h′(k) = 7 - (k mod 7).

Question 5. Give a pseudocode description for performing insertion, searching, removal from a hash table that uses quadratic probing to resolve collisions where we use a special marker to represent deleted elements. You may use the pseudocode given on page 201 of the Goodrich and Tamassia book (attached to this assignment) as a template for your pseudocode. Note, you will not use the Shift(i) method.