Please read the instructions carefully. You have to use the companion answer sheet (which is a llable PDF le) to type/select your answers to the questions described here. Hand-written assignment (or photo of it) will not be graded. Submit the lled PDF le of the answer sheet on Gradescope, following the link on Canvas. You should name your le using the format CSE310-HW06-LastName-FirstName.pdf. Make sure that your submission can be viewed clearly on gradescope for auto-grading. Adobe Acrobat Reader can be found at https://get.adobe.com/reader/.
Q1 (26 points: 24 + 2) Given two sequences X=<C,B,B,A> and Y=<D,C,A,C,B,A>, you need to use dynamic programming to compute a longest common subsequence of X and Y.
(a) On the answer sheet, answer questions regarding the values of m[i, j].
(b) On the answer sheet, write the LCS computed.
Q2 (14 points: 2 + 6 + 6) Suppose that we are using hashing with open addressing, where the (linear) probing sequence is de ned by
h0(k) = k mod 13
and
h(k; i) = (h0(k) + i) mod 13:
The following questions all refer to the hash table in the following.
j
0
1
2
3
4
5
6
7
8
9
10
11
12
T [j]
10
DELETED
9
DELETED
DELETED
8
7
6
5
4
3
2
1
(a) What is the load factor of the hash table at the top of this page? Write your answer on the answer sheet as a fraction.
(b) What are the cells (the j values) probed when performing Hash-Insert(T, 25) to the hash table at the top of this page.
(c) What are the cells (the j values) probed when performing Hash-Delete(T, 8) to the hash table at the top of this page.
Q3 (10 points: 4 + 6) The following problems are concerned with hashing.
p
(a) Let A = 25 , and the table size be m = 16384. For k = 654321, what is the hash value h(k) if you are using the multiplication method?
(b) Suppose you are using chaining (with a linked list) for collision resolution. Assume that the table size is m and the number of elements in the table is n. What is the worst-case time complexity for insertion? What is the worst-case time complexity for searching? What is the worst-case time complexity for deletion?
2
