In the bin packing problem, suppose that the maximum size of the items is bounded from above by $\alpha < 1$. Now let's apply the Next Fit algorithm to pack a set of items $L$ into bins with capacity 1. Let $NF(L)$ and $OPT(L)$ denote the numbers of bins used by algorithms Next Fit and the optimal solution. Then for all $L$, we have $NF(L) < \rho \cdot OPT(L) + 1$ for some $\rho$. Which one of the following statements is FALSE?

After splaying at node 2 in the given tree, which of the following statements about the resulting tree is FALSE?

Two spam mail detection systems are tested on a dataset with 10000 ordinary mails and 2000 spam mails. System A detects 300 ordinary mails and 1600 spam mails, and system B detects 315 ordinary mails and 1800 spam mails. If our primary concern is to keep the important mails safe, which of the following is correct?

After inserting 1 into the red-black tree given in the figure, which node(s) will keep its/their color(s) unchanged?

The Online Hiring Algorithm ( hire only once ) is described as the following:

int OnlineHiring ( EventType C[ ], int N, int k )
{
    int Best = N;
    int BestQ = -INFINITY ;
    for ( i=1; i<=k; i++ ) {
        Qi = interview( i );
        if ( Qi > BestQ )   BestQ = Qi;
    }
    for ( i=k+1; i<=N; i++ ) {
        Qi = interview( i );
        if ( Qi > BestQ ) {
            Best = i;
            break;
        }
    }
    return Best;
}

Assume that the quality input C[ ] is uniformly random.
When $N$ = 271 and $k$ = 90, the probability of hiring the $N$th candidate is__.

Given the following game tree, the red node will be pruned with α-β pruning algorithm if and only if __.

How many of the following sorting methods use(s) Divide and Conquer algorithm?

• Heap Sort
• Insertion Sort
• Merge Sort
• Quick Sort
• Selection Sort
• Shell Sort

Which one of the following statements is FALSE?

When measure the performance of parallel algorithm, we often use work load ($W(n)$) and worst-case running time ($T(n)$). How many evaluation metrics are asymptotically equivalent to $W(n)$ and $T(n)$?

• $P(n) = W(n)/T(n)$ processors and $T(n)$ time (on a PRAM)
• $W(n)/p$ time using any number of $p \geq W(n)/T(n)$ processors (on a PRAM)
• $W(n)/p + T(n)$ time using any number of $p$ processors (on a PRAM)

Suppose that the replacement selection is applied to generate longer runs with a priority queue of size 5. Given the sequence of numbers { 17, 2, 6, 57, 51, 86, 5, 94, 43, 54, 39, 87, 29}, the longest run contains ____ numbers.

Merge the two given skew heaps. Which one of the following statements is FALSE?

Givien two $n\times n$ matrices $A$ and $B$. Let's consider the following Divide and Conquer idea to do matrix multiplication $C = A \cdot B$.

Divide each matrix into four $\frac{n}{2}\times\frac{n}{2}$ submatrics as follows:

$\begin{bmatrix} C_1 & C_2 \\ C_3 & C_4\end{bmatrix}$ = $\begin{bmatrix} A_1 & A_2 \\ A_3 & A_4 \end{bmatrix} \cdot \begin{bmatrix} B_1 & B_2\\ B_3 & B_4 \end{bmatrix}$

We define $P_1, P_2, \cdots ,P_7$ as follows:

$P_1 = A_1\cdot(B_2-B_4)$

$P_2 = (A_1+A_2)\cdot B_4$

$P_3 = (A_3+A_4)\cdot B_1$

$P_4 = A_4\cdot(B_3-B_1)$

$P_5 = (A_1+A_4)\cdot(B_1+B_4)$

$P_6 = (A_2-A_4)\cdot(B_3+B_4)$

$P_7 = (A_1-A_3)\cdot(B_1+B_2)$

Here all the matrix multiplications are done recursively. Then each part of $C$ can be calculated by simple additions and subtractions among $P_1, P_2, \cdots ,P_7$.

Which of the following is the closest to the actual time complexity?

Delete the minimum number from the given leftist heap. Which one of the following statements is TRUE?

Which of the following binomial trees can represent a binomial queue of size 78?

Which one of the following statements is FALSE?

Given a set of activities $S = \{ a_1, a_2, \cdots , a_n \}$. Each $a_i$ takes place during a time interval $[s_i, f_i)$.
If an instance $S$ given as the following, the maximum-size of mutually compatible activities is __.

Which one of the following statements is FALSE?

After inserting 0 into the 2-3 tree given in the figure, how many of the following statements are FALSE?

(S1) The tree grows higher;

(S2) 2 and 4 are in the same interior node;

(S3) the root node still contains 9 only;

(S4) the interior node containing 12 keeps unchanged.

There are $n$ jobs, and each job $j$ has a processing time $t_j$. We will use a local search algorithm to partition the jobs into two groups A and B, where set A is assigned to machine $M_1$ and set B to $M_2$. The time needed to process all of the jobs on the two machines is $T_1 = \sum_{j\in A} t_j$, $T_2 = \sum_{j\in B} t_j$. The problem is to minimize $|T_1 - T_2|$.

Local search: Start by assigning jobs $1, \ldots, n/2$ to $M_1$, and the rest to $M_2$.
The local moves are to move a single job from one machine to the other, and we only move a job if the move decreases the absolute difference in the processing times. Which of the following statement is true?

Insert 28, 23, 54, 61, 98, 37 into an initially empty AVL tree first. Then immediately insert one of the following keys. Which one will cause an RL rotation?