Introduction to Algorithm Assignment 1 Solution

   

  1. For each function $f(n)$ and time $t$ in the following table, determine the largest size n of a problem that can be solved in time $t$, assuming that the algorithm to solve the problem takes $f(n)$ microseconds.

Solution:

  1 second 1 minute 1 hour 1 day 1 month 1 year 1 century
$lgn$ $2^{10^6}$ $2^{6 \times 10^{7}}$ $2^{3.6 \times 10^{9}}$ $2^{8.64 \times 10^{10}}$ $2^{2.59 \times 10^{12}}$ $2^{3.15 \times 10^{13}}$ $2^{3.15 \times 10^{15}}$
$\sqrt{n}$ $10^{12}$ $3.6 \times 10 ^{15}$ $1.3 \times 10^{19}$ $7.46 \times 10^{21}$ $6.72 \times 10^{24}$ $9.95 \times 10^{26}$ $9.95 \times 10^{30}$
$n$ $10^6$ $6 \times 10 ^{7}$ $3.6 \times 10 ^{9}$ $8.64 \times 10 ^{10}$ $2.59 \times 10 ^{12}$ $3.15 \times 10 ^{13}$ $3.15 \times 10 ^{15}$
$nlgn$ $6.24 \times 10 ^{4}$ $2.8 \times 10 ^{6}$ $1.33 \times 10 ^{8}$ $2.76 \times 10 ^{9}$ $7.19 \times 10 ^{10}$ $7.98 \times 10 ^{11}$ $6.86 \times 10 ^{13}$
$n^2$ $1000$ $7745$ $60000$ $293938$ $1609968$ $5615692$ $56156922$
$n^3$ $100$ $391$ $1532$ $4420$ $13736$ $31593$ $146645$
$2^n$ $19$ $25$ $31$ $36$ $41$ $44$ $51$
$n!$ $9$ $11$ $12$ $13$ $15$ $16$ $17$

   

  1. Give asymptotic upper and lower bounds for $T(n)$ in each of the following recurrences. Assume that $T(n)$ is constant for $n \le 2$. Make your bounds as tight as possible, and justify your answers.

a. $T(n)=2T(n/2)+n^4$.

Solution: $\Theta(n^4)$

b. $T(n)=T(7n/10)+n$.

Solution: $\Theta(n)$

c. $T(n)=16T(n/4)+n^2$.

Solution: $\Theta(n^2 \lg n)$

d. $T(n)=7T(n/3)+n^2$.

Solution: $\Theta(n^2)$

e. $T(n)=7T(n/2)+n^2$.

Solution: $\Theta(n^{\lg 7})$

f. $T(n)=2T(n/4)+\sqrt{n}$.

Solution: $\Theta(\sqrt{n}\lg n)$

g. $T(n)=T(n-2)+n^2$.

Solution: $\Theta(n^3)$

   

  1. Indicate, for each pair of expressions $(A,B)$ in the table below, whether $A$ is $O$, $o$, $\Omega$, $\omega$, or $\Theta$ of $B$. Assume that $k \le 1$, $\epsilon > 0$, and $c > 1$ are constants. Your answer should be in the form of the table with “yes” or “no” written in each box.

Solution:

$A$ $B$ $O$ $o$ $\Omega$ $\omega$ $\Theta$
$\lg^kn$ $n^\epsilon$ yes yes no no no
$n^k$ $c^n$ yes yes no no no
$\sqrt{n}$ $n^{\sin n}$ no no no no no
$2^n$ $2^{n/2}$ no no yes yes no
$n^{\lg c}$ $c^{\lg n}$ yes no yes no yes
$\lg(n!)$ $\lg(n^n)$ yes no yes no yes

   

  1. When RANDOMIZED-QUICKSORT runs, how many calls are made to the random-number generator RANDOM in the worst case? How about in the best case? Give your answer in terms of $\Theta$-notation.

Solution:

Worst: $T(n)=T(n-1)+\Theta(1)=\Theta(n)$

Best: $T(n)=2T(n/2)+\Theta(1)=\Theta(n)$

   

  1. Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n)=2T(n-1)+1$. Use the substitution method to verify your answer.

Solution:

\[\begin{array}{lll} T(n) & = & \displaystyle \sum\_{i=0}^{n - 1}(2^i) + \Theta(2^n) \\\\ & = & \displaystyle \frac{2^n-1}{2-1} + \Theta(2^n) \\\\ & = & \displaystyle 2^n - 1 + \Theta(2^n) \\\\ & = & \displaystyle \Theta(2^n) \\\\ \end{array}\]

   

  1. Show that there is no comparison sort whose running time is linear for at least half of the $n!$ inputs of length $n$. What about a fraction of $1/n$ of the inputs of length $n$? What about a fraction $1/2^n$?

Solution:

\[\begin{array}{rll} \displaystyle \frac{n!}{2} &\le& 2^h \\\\ h &\ge& \displaystyle \lg \left (\frac{n!}{2} \right ) \\\\ &=& (\lg n!) - 1 \\\\ &=& \Omega(n \lg n) - 1 \\\\ &=& \Omega(n \lg n)\\\\ \end{array}\] \[\begin{array}{rll} \displaystyle \frac{n!}{n} &\le& 2^h \\\\ h &\ge& \displaystyle \lg \left (\frac{n!}{n} \right ) \\\\ &=& (\lg n!) - \lg n \\\\ &=& \Omega(n \lg n) - \lg n \\\\ &=& \Omega(n \lg n)\\\\ \end{array}\] \[\begin{array}{rll} \displaystyle \frac{n!}{2^n} &\le& 2^h \\\\ h &\ge& \displaystyle \lg \left (\frac{n!}{2^n} \right ) \\\\ &=& (\lg n!) - n \\\\ &=& \Omega(n \lg n) - n \\\\ &=& \Omega(n \lg n)\\\\ \end{array}\]

All of them have the lower-bound $\Omega(n \lg n)$.

   

  1. Suppose that the splits at every level of quicksort are in the proportion $1-\alpha$ to $\alpha$, where $0 < \alpha \le 1/2$ is a constant. Show that the minimum depth of a leaf in the recursion tree is approximately $-\lg n / \lg \alpha$ and the maximum depth is approximately $-\lg n/\lg(1-\alpha)$. (Don’t worry about integer round-off.)

Solution:

Let $x$ be the minimum depth,

\[\begin{array}{rll} n\alpha^x &\le& 1 \\\\ \alpha^x &\le& n^{-1} \\\\ x &\ge& \log\_\alpha{n^{-1}} \\\\ x &\ge& -\lg n / \lg \alpha \\\\ \end{array}\]

Let $y$ be the maximum depth,

\[\begin{array}{rll} n(1-\alpha)^y &\le& 1 \\\\ (1-\alpha)^y &\le& n^{-1} \\\\ y &\ge& \log\_{(1-\alpha)}{n^{-1}} \\\\ y &\ge& -\lg n / \lg (1-\alpha) \\\\ \end{array}\]

   

  1. Use Strassen’s algorithm to compute the matrix product

$\begin{pmatrix} 1 & 3 \\ 7 & 5 \end{pmatrix}\begin{pmatrix} 6 & 8 \\ 4 & 2 \end{pmatrix}$.

Show your work.

Solution:

$S_1 = B_{12} - B_{22} = 8 - 2 = 6$

$S_2 = A_{11} + A_{12} = 1 + 3 = 4$

$S_3 = A_{21} + A_{22} = 7 + 5 = 12$

$S_4 = B_{21} - B_{11} = 4 - 6 = -2$

$S_5 = A_{11} + A_{22} = 1 + 5 = 6$

$S_6 = B_{11} + B_{22} = 6 + 2 = 8$

$S_7 = A_{12} - A_{22} = 3 - 5 = -2$

$S_8 = B_{21} + B_{22} = 4 + 2 = 6$

$S_9 = A_{11} - A_{21} = 1 - 7 = -6$

$S_{10} = B_{11} + B_{12} = 6 + 8 = 14$

$P_1 = A_{11} \cdot S_1 = 1 \times 6 = 6$

$P_2 = S_{2} \cdot B_{22} = 4 \times 2 = 8$

$P_3 = S_{3} \cdot B_{11} = 12 \times 6 = 72$

$P_4 = A_{22} \cdot S_4 = 5 \times -2 = -10$

$P_5 = S_{5} \cdot S_6 = 6 \times 8 = 48$

$P_6 = S_{7} \cdot S_8 = -2 \times 6 = -12$

$P_7 = S_{9} \cdot S_{10} = -6 \times 14 = -84$

$C_{11} = P_5 + P_4 - P_2 + P_6 = 48 - 10 - 8 - 12 = 18$

$C_{12} = P_1 + P_2 = 8 + 6 = 14$

$C_{21} = P_3 + P_4 = 72 - 10 = 62$

$C_{22} = P_5 + P_1 - P_3 - P_7 = 48 + 6 - 72 + 84 = 66$

\[\begin{pmatrix} 18 & 14 \\\\ 62 & 66 \end{pmatrix}\]

   

  1. Let $A[1..n]$ be an array of n distinct numbers. If $i < j$ and A[i] > A[j], then the pair $(i, j)$ is called an inversion of A.

a. List the five inversions of the array $\left \langle 2, 3, 8, 6, 1 \right \rangle$.

Solution:

  • $(2, 1)$
  • $(3, 1)$
  • $(8, 6)$
  • $(8, 1)$
  • $(6, 1)$

b. What array with elements from the set $\{1,2,\cdots,n\}$ has the most inversions? How many does it have?

Solution:

  • Most: $\{n,n-1,\cdots,1\}$
  • How many: $\frac{n(n-1)}{2}$

c. What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.

Solution:

Equal

d. Give an algorithm that determines the number of inversions in any permutation on $n$ elements in $\Theta(n \lg n)$ worst-case time. (Hint: Modify merge sort.)

Solution:

def count_inversion_sub(arr, l, r):
    if l >= r:
        return 0
    mid = (l + r) // 2
    cnt = count_inversion_sub(arr, l, mid) + count_inversion_sub(arr, mid+1, r)
    arr_l = [arr[i] for i in range(l, mid+1)]
    arr_l.append(1e100)
    arr_r = [arr[j] for j in range(mid+1, r+1)]
    arr_r.append(1e100)
    i, j = 0, 0
    for k in range(l, r+1):
        if arr_l[i] <= arr_r[j]:
            arr[k] = arr_l[i]
            i += 1
        else:
            arr[k] = arr_r[j]
            j += 1
            cnt += len(arr_l) - i - 1
    return cnt


def count_inversion(arr):
    return count_inversion_sub(arr, 0, len(arr) - 1)

   

  1. Answer the following questions and write the python programs to justify your answers.

a. You are given an array of integers, where different integers may have different numbers of digits, but the total number of digits over all the integers in the array is $n$. Show how to sort the array in $O(n)$ time.

Solution:

Suppose the number of integers which have $b_i$ digits is $n_i$, divide the integers into different buckets using counting sort, the integers in the same bucket have the same $b_i$, then use radix sort in each bucket:

\[\sum\_{i} b\_i n\_i = n\]

therefore the algorithm is $O(n)$.

def counting_sort(a, m):
    b = [0 for _ in range(len(a))]
    k = 10
    c = [0 for _ in range(k)]
    for s in a:
        c[ord(s[m]) - ord('0')] += 1
    for i in range(1, k):
        c[i] += c[i - 1]
    for i in range(len(a) - 1, -1, -1):
        c[ord(a[i][m]) - ord('0')] -= 1
        b[c[ord(a[i][m]) - ord('0')]] = a[i]
    return b


def radix_sort(a):
    for m in range(len(a[0]) - 1, -1, -1):
        a = counting_sort(a, m)
    return a


def count_and_divide(a):
    a = map(str, a)
    b = [0 for _ in range(len(a))]
    k = 0
    for s in a:
        k = max(k, len(s))
    c = [0 for _ in range(k + 1)]
    for s in a:
        c[len(s)] += 1
    for i in range(1, k + 1):
        c[i] += c[i - 1]
    r = c[:]
    for i in range(len(a) - 1, -1, -1):
        c[len(a[i])] -= 1
        b[c[len(a[i])]] = a[i]
    for i in range(k + 1):
        if c[i] < r[i]:
            b[c[i]:r[i]] = radix_sort(b[c[i]:r[i]])
    return map(int, b)

b. You are given an array of strings, where different strings may have different numbers of characters, but the total number of characters over all the strings is $n$. Show how to sort the strings in $O(n)$ time. (Note that the desired order here is the standard alphabetical order; for example, $a < ab < b$.)

Solution:

Sort the strings by their first characters with counting-sort, then divide the strings by their first characters, repeat the process in each new group. Since each character is used only once for sorting, the amortized running time is $O(n)$.

def get_key(s, i):
    if i >= len(s):
        return 0
    return ord(s[i]) - ord('a') + 1


def counting_sort(a, p=0):
    k = 27
    b = ['' for _ in range(len(a))]
    c = [0 for _ in range(k)]
    for s in a:
        c[get_key(s, p)] += 1
    for i in range(1, k):
        c[i] += c[i - 1]
    r = c[:]
    for i in range(len(a) - 1, -1, -1):
        c[get_key(a[i], p)] -= 1
        b[c[get_key(a[i], p)]] = a[i]
    for i in range(1, k):
        if c[i] < r[i]:
            b[c[i]:r[i]] = counting_sort(b[c[i]:r[i]], p+1)
    return b