Introduction to Algorithm Assignment 2

   

  • 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, June 5, 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) }\}$?

   

  1. 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))$.

   

  1. 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.

   

  1. 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)$.

   

  1. 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$.

   

  1. 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?

   

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

   

  1. 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

   

  1. Determine the cost and structure of an optimal binary search tree for a set of $n = 7$ keys with the following probabilities.
\[\begin{array}{c|cccccccc} i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline p_i & & 0.04 & 0.06 & 0.08 & 0.02 & 0.10 & 0.12 & 0.14 \\ q_i & 0.06 & 0.06 & 0.06 & 0.06 & 0.05 & 0.05 & 0.05 & 0.05 \end{array}\]

   

  1. What is an optimal Huffman code for the following set of frequencies, based on the first $8$ Fibonacci numbers?
\[a:1 \quad b:1 \quad c:2 \quad d:3 \quad e:5 \quad f:8 \quad g:13 \quad h:21\]

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