数据结构代写 | CS 234 Spring 2020 — Assignment 5

这个作业是完成哈希表相关的数据结构
CS 234 Spring 2020 — Assignment 5

W1. (5 marks) You are given a positive integer n of the form n = 2h − 1, for some integer h ≥ 1. Give an example
of an array of length n where the following method of building a heap
step 1. Place the new key at the first free leaf
step 2. The heap-order property might be violated: perform a bubble-up,
uses Ω(n log(n)) element comparisons. Justify your answer.
W2. (5 marks) Suppose we have an array A of numbers such that A[i] = ai + b with a > 0 and b as real numbers.
Show that interpolation search for a target k which is in the array, achives a runtime O(1).
W3. (a) (5 marks) Let the array A contain the following keys: [3, 1, 4, 1, 17, 26, 6, 5, 9, 5, 98, 2, 6, 10]. Show the
array after each Bubble-Down call during the Heapify operation (there will be 7 such arrays). Specifically,
use the algorithm that processes the array from right to left (applying Bubble-Down procedure for each
index in the array that corresponds to an internal node of the heap), until the entire array forms a
(min-)heap, using the procedure showed in lectures.
(b) (5 marks) If we modify the Heapify operation to fix up the heap from left to right (rather than right to
left), while still applying the Bubble-Down procedure at each step (i.e. for each internal node of the heap),
would the resulting array produce a heap? If not, give an example of an array A (or a corresponding
binary tree) that would not generate a heap after applying this version of Heapify. Justify your answer.
W4. (5 marks) Consider a self-organizing heuristic which alternates between Move-To-Front and Transpose. Precisely, to organize the list after the i’th access, the accessed item is moved to front if i is odd and is swapped
with its previous item if i is even. For example, for a sequence initially ordered as [A,B,C,D], if D is searched
first and C is search second, the algorithm proceeds by moving D to the front and then swapping C with B,
resulting in [D,A,C,B].
Consider a sequence of n keys, k1, k2, . . . , kn, where n is an odd integer. Describe the sequence of n searches
that results in the maximum cost and compute the cost of performing these n searches.
W5. (5 marks) Assume that we have a hash table of size N = 5, we use the hash function f(x) = x mod 5, and
we use separate chaining for collision resolution. Demonstrate the insertion of the keys 0, 1, 2, . . . , 12 into the
(initially empty) hash table (in that order). You just need to draw the state of the hash table after all insertions
are done. Justify your answer briefly.
W6. (12 marks) Consider a hash table dictionary possible keys U = {0, 1, 2, . . . , 25} and size M = 5. If items with
keys k = 17, 10, 20, 13 are inserted in that order, draw the resulting hash table if we resolve collisions using:
(a) Chaining with h(k) = (k + 2) mod 5.
(b) Linear probing with h(k) = (k + 2) mod 5
(c) Double hashing with h1(k) = (k + 2) mod 5 and h2(k) = 1 + (k mod 4).
(d) Identify a serious problem with the choice of hash functions h2(k) = bk/5c.
W7. (3 marks) Assume that we have a hash table of size 6 and that our keys are selected uniformly at random from
the set A = {1, 2, 3, . . . , 600}. Consider the following two hash functions:
h1(k) = k mod 6,
h2(k) = 2k mod 6.
Which hash function is better? Justify your answer.