Submit a single .pdf for the written problems and .java codes for the coding problems to me via email by the date of the deadline (11:59 pm)
1. [Written 10pt] How to exchange numeric values of two variables, say, u and v, without using any extra storage?
2. [Written 10pt] Assuming that the set of possible list values is {a, b, c, d}, sort the following list in alphabetical order by the distribution-counting algorithm: b,c,d,c,b,a,a,b.
3. [Written 10pt] Design a one-line algorithm for sorting any array of size n whose values are n distinct integers from 1 to n.
4. [Written 15pt] For the input 30, 20, 56, 75, 31, 19 and hash function h(K) = K mod 11.
a. Construct the open hash table.
b. Find the largest number of key comparisons in a successful search in this table.
c. Find the average number of key comparisons in a successful search in this table assuming each key will be randomly selected with prob. of 1/6 (i.e., equal probability).
5. [Written 15pt] For the input 30, 20, 56, 75, 31, 19 and hash function h(K) = K mod 11.
a. Construct the closed hash table (with linear probing).
b. Find the largest number of key comparisons in a successful search in this table.
c. Find the average number of key comparisons in a successful search in this table assuming each key will be randomly selected with prob. of 1/6 (i.e., equal probability).
6. [Written 15pt] Draw the B-tree obtained after inserting 30 and then 31 in the B-tree in Figure 7.8. Assume that a leaf cannot contain more than three items.