東京大学情報理工学系研究科コンピュータ科学専攻 2019年2月実施問題2

Author

Description

Consider the Java program below to sort an array $A$ in an ascending order. $M$, $N$, and $K$ are positive integers, and $A$ is an array of $N$ nonnegative integers where $0 \leq A[i] < M$ for all $i \in \{0, \dots, N-1\}$.
In this program, list is a class of an integer list with the following methods:

lst.size(): returns the number of elements in the list lst.
lst.get(i): returns the element at the $i$-th position in the list lst (the position number starts from 0).
lst.insert(i, x): inserts $x$ to the list lst at the $i$-th position.

$B$ is an array of size $K$, whose elements are all initialized to empty lists. Suppose that the execution time of each of the above methods is constant. You can ignore overflow errors.

void mysort(int M, int N, int K, int[] A, list[] B) {
    for (int i = 0; i < N; i++) {
        int m = A[i] * K / M;
        int j = 0;
        for (; j < B[m].size(); j++) {
            if (A[i] <= B[m].get(j)) {
                break;
            }
        }
        B[m].insert(j, A[i]);
    }
    int i = 0;
    for (int m = 0; m < K; m++) {
        for (int j = 0; j < B[m].size(); j++) {
            A[i] = [ blank X ];
            i = i + 1;
        }
    }
}

Answer the following questions:

(1) Answer an appropriate expression to fill the blank $\boxed{\ \ X\ \ }$.

(2) Let $C$ be the number of times the line $6$ is executed. Answer the largest value of $C$ in terms of $N$ and $K$. Also, answer the expected value of $C$ in terms of $N$ and $K$, assuming that $A[i]$ is distributed independently uniformly randomly over the set $\{0, \ldots, M-1\}$. Suppose that $K \ll M$ for this question.

(3) Explain how the expected running time of this program varies when $K$ changes, assuming that $A[i]$ is distributed independently uniformly randomly.

(4) Discuss advantages and disadvantages of this algorithm in comparison to the quicksort algorithm.

Kai

Setting of the problem: we got $N$ element and $K$ buckets.

(1)

1	`B[m].get(j)`

(2)

The input sequence might be in an increasing order and all elements might fall into one bucket. Thus, line $6$ will be executed:

\[ C = 0 + 1 + \cdots + (n-1) = \frac{n(n-1)}{2} \]

times. Note that it has to be an increasing order, because items are being inserted at the beginning of a bucket. If we wanna do evil, we must make every item traverse the whole bucket, until the end. It is possible when every inserted item is bigger than any element in the bucket, that is, input sequence is of increasing order.

(3)

Let $n_i$ denote size of $i$-th bucket. Line $6$ is de facto an insertion sort, which means that $i$-th~bucket will be sorted in $O(n^2)$. Total running time will be to:

$$ C = \sum_{i=1}^{K} O(n_i^2) $$ Taking expectation:

\[ \mathbb{E}(C) = \mathbb{E}[\sum_{i=1}^{K} O(n_i^2)] = \sum_{i=1}^{K} \mathbb{E}[O(n_i^2)] = \sum_{i=1}^{K} O(\mathbb{E}[n_i^2]) \]

What is $[\mathbb{E}n_i^2]$? Note that, by definition $Var(X) = \mathbb{E}[X^2] - (\mathbb{E}X)^2$ for any random variable $X$. Let $X_{i,j}$ be an indicator random variable:

\[ X_{i,j} = \begin{cases} 1 & \text{element $j$ went to bucket $i$} \\ 0 & \text{otherwise} \end{cases} \]

\[ n_i = \sum_{j=1}^{N} X_{i, j} \]

Since we have $K$ buckets and every of them is equally likely, probability of "going to bucket $i$" is $\frac{1}{K}$. Thus, expectation of $n_i$ is:

\[ \mathbb{E}(n_i) = \sum_{j=1}^{N} \mathbb{E}(X_{i, j}) = \frac{N}{K} \]

We can also notice, that, $n_i$ is just a binomial random variable with expectation $np$ and variance $np(1-p)$. Here a trial is mapping an item into bucket, and the success is placing it into $i$-th bucket. There are $n=N$ trials and probability of success if $\frac{1}{K}$.

\[ \begin{aligned} \mathbb{E}[n_i^2] = Var[n_i] + (\mathbb{E}[n_i])^2 &= N\frac{1}{K}(1-\frac{1}{K}) + (\frac{N}{K})^2 \\ &= \frac{N^2 + NK - N}{K^2} \end{aligned} \]

Finally:

\[ \begin{aligned} \mathbb{E}[C] = O(\sum_{i=1}^{K}\mathbb{E}[n_i^2]) = O(\sum_{i=1}^{K} \frac{N^2 + NK - N}{K^2}) = O(\frac{N^2}{K} + N) \end{aligned} \]

The following contribute to total expected running time:

finding a bucket for each element $O(N)$
sorting each bucket, $O(\frac{N^2}{K} + N)$
for each bucket, getting its content: $O(K\frac{N}{K}) = O(N)$

Total running time:

\[ O(\frac{N^2}{K} + 3N) \]

When $K$ is $O(N)$, then we get $O(N)$ expected running time. When $K$ is $O(1)$, then the running time is $O(N^2)$.

(4)

BS is stable, QS isn't
BS isn't in-place, QS is
BS runs $O(N)$ expected, QS is $O(NlogN)$
BS has upper limit on keys, QS hasn't

東京大学 情報理工学系研究科 コンピュータ科学専攻 2019年2月実施 問題2