• Submission Guideline: Upload your homework file (hw2_[your student id].doc or hw2_[your student id].hwp) to online Uclass classroom. You are allowed to write down your answers either in Korean or English at your convenience.
• Deadline: 23:59 PM, Wednesday, November 6, 2024

Please feel free to leave your questions about homework problems in the online Ed Discussion platform.

1. You use a hash function $h$ to hash $n$ distinct keys into an array $T$ of length $m$. Assuming independent uniform hashing, what is the expected number of collisions? More precisely, what is the expected cardinality of ${\{ {\{k_1, k_2 }\} : k_1 \ne k_2 \textrm{ and }h(k_1) = h(k_2) }\}$?

2. Consider inserting the keys $10, 22, 31, 4, 15, 28, 17, 88, 59$ into a hash table of length $m = 11$ using open addressing. Illustrate the result of inserting these keys using linear probing with $h(k, i) = (k + i) \mod m$ and using double hashing with $h_1(k) = k$ and $h_2(k) = 1 + (k \mod (m - 1))$.

3. Consider a hash table with 9 slots and the hash function $h(k) = k \mod 9$. Demonstrate what happens upon inserting the keys $5, 28, 19, 15, 20, 33, 12, 17, 10$ with collisions resolved by chaining.

4. Suppose that we use an open-addressed hash table of size $m$ to store $n \le m / 2$ items.

   a. Assuming uniform hashing, show that for $i = 1, 2, \ldots, n$, the probability is at most $2^{-k}$ that the $i$th insertion requires strictly more than $k$ probes.

   b. Show that for $i = 1, 2, \ldots, n$, the probability is $O(1 / n^2)$ that the $i$th insertion requires more than $2\lg n$ probes.

   Let the random variable $X_i$ denote the number of probes required by the $i$th insertion. You have shown in part (b) that $\Pr {\{ X_i ; 2\lg n }\} = O(1 / n^2)$. Let the random variable $X = \max_{1 \le i \le n} X_i$ denote the maximum number of probes required by any of the $n$ insertions.

   c. Show that $\Pr {\{ X ; 2\lg n }\} = O(1 / n)$.

   d. how that the expected length $\text E[X]$ of the longest probe sequence is $O(\lg n)$.

5. Show, by means of a counterexample, that the following “greedy” strategy does not always determine an optimal way to cut rods. Define the density of a rod of length $i$ to be $p_i / i$, that is, its value per inch. The greedy strategy for a rod of length $n$ cuts off a first piece of length $i$, where $1 \le i \le n$, having maximum density. It then continues by applying the greedy strategy to the remaining piece of length $n - i$.

6. Give an $O(n)$-time dynamic-programming algorithm to compute the nth Fibonacci number. Draw the subproblem graph. How many vertices and edges are in the graph?

7. Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is $\langle 5, 10, 3, 12, 5, 50, 6 \rangle$.

8. Give a recursive algorithm $\text{MATRIX-CHAIN-MULTIPLY}(A, s, i, j)$ (algorithm in 26 page of Week 6) that actually performs the optimal matrix-chain multiplication, given the sequence of matrices $\langle A_1, A_2, \ldots ,A_n \rangle$, the $s$ table computed by $\text{MATRIX-CHAIN-ORDER}$, and the indices $i$ and $j$. (The initial call would be $\text{MATRIX-CHAIN-MULTIPLY}(A, s, 1, n)$.)

def matrix_chain_multiply(arr, s, i, j):
    """
    Args:
      arr: The array of matrices.
      s: The table computed by MATRIX-CHAIN-ORDER.
      i: The left index of the array.
      j: The right index of the array.

    Returns:
      marix: The result of the matrix chain multiplication.
    """
    
    # Implement the function here!!
    #
    #

    return matrix

9. Determine the cost and structure of an optimal binary search tree for a set of $n = 7$ keys with the following probabilities.

10. What is an optimal Huffman code for the following set of frequencies, based on the first $8$ Fibonacci numbers?

Can you generalize your answer to find the optimal code when the frequencies are the first $n$ Fibonacci numbers?