The solution to the recurrence $T(n)=T(n/6)+T(7n/9)+O(n)$ is $O(n)$. (Assume $T(n)=1$ for $n$ smaller than some constant $c$ )

Suppose that a randomized algorithm A has expected running time $\Theta (n^2 )$ on any input of size $n$. Then it is possible for some execution of algorithm A to take $\Omega (3^n )$ time.

In external sorting, the sorting is done by reading all the data into memory, sorting it there, and then writing it back out to disk.

Let $n$ denote the alphabet size. Huffman’s greedy algorithm requires at most $\log_2 n$ bits to encode a single symbol.

Consider the following variant of the knapsack problem. You are given $k$ identical knapsacks and $n$ items of different sizes. The profit of each item is equal to its size. Your goal is to select items and fill the knapsacks as much as possible subject to the capacity constraints. A greedy approach always packs the largest remaining item as long as there is enough room. As bin packing, if more than one knapsacks have room for the current item, one may use any packing rule (Next Fit, First Fit, and Best Fit). No matter what rule you apply, for any $k\geq 1$, the approximation ratio of the greedy algorithm is always 2.

When proving the amortized bound of a Merge operation in skew heaps, the potential of a skew heap is defined to be the total number of right heavy nodes. Then we can prove that, in an $N$-node skew heap, the amortized cost for a Merge operation is exactly ​​$2\lfloor\log_2N\rfloor+1$.

There are many solutions to the 5-Queens Problem, and there are $8$ solutions that at least one queen is placed in a corner of the chessboard.

There exists an AVL tree of depth 6 (the depth of the root is 0) containing 31 nodes.

The following problem is in co-NP.

Given a positive integer $k$, is $k$ a prime number?

The time complexity of merging two leftist heap can be as bad as $\Omega(N)$, where $N$ is the number of elements in the heap.

The Random Sampling algorithm can find the maximum among $n$ elements in $O(1)$ time and $O(n)$ work. The probability of not finishing within this time and work complexity is $O(\frac{1}{n^c})$ for some positive constant $c$. 

For any undirected graph $G$, the weight of its maximum cut is at least half of the total edge weight.

Consider the two ways to implement distributed indexing. File-partitioned index is always better than the term-partitioned index.

Given a set $S$ of $n$ numbers and a number $k$ between $1$ and $n$, consider the function $Select(S, k)$ that returns the $k$-th largest element in S. We uniformly at random choose an element $a_i$ in S, the "splitter", and form the sets $S^{-}$ with items smaller than $a_i$ and the set $S^{+}$ with items larger than $a_i$. We can then determine which of $S^{-}$ or $S^{+}$ contains the $k$-th largest element, and iterate only on this one.  We say that the algorithm is in phase $j$ when the size of the set under consideration is at most $n(3/4)^j$ but greater than $n(3/4)^{j+1}$.

Select the statement that is not correct.

Consider the maximum cut problem. Let $V$ be the set of vertices, let $n = |V|$, and let $W$ be the total edge weight. We have already learned a $(2+\epsilon)$-approximation local search algorithm that needs $O(\frac{n}{\epsilon} \log W)$ flips. In the following, we are trying to further reduce the number of flips by starting the algorithm with a good initial solution. Note that each vertex $v$ naturally forms a cut $(\{v\}, V - \{v\})$. Let $(\{v^*\}, V - \{v^*\})$ be the one with the largest weight among all such cuts. If we start the $(2+\epsilon)$-approximation local search algorithm with $(\{v^*\}, V - \{v^*\})$, how many flips do we need in the worst case?

Consider a bipartite graph $G(A,B,E)$. (Recall that a graph $G$ is bipartite if the vertex set of $G$ can be partitioned into $A$ and $B$ such that all the edges of $G$ has one endpoint in $A$ and the other in $B$.) A matching on $G$ is a subset $M$ of $E$, such that no two edges in $M$ have a common vertex. A vertex cover is a subset $C$ of $V$, where every edge in $E$ must have at least one endpoint in $C$. Denote by $|S|$ the cardinality of a set $S$. Which of the following statements is false?

Insert {7, 15, 9, 11, 5, 8, 13, 18} into an initially empty 2-3 tree (with splitting), and then delete 7. Which one of the following statements is FALSE about the resulting tree?

We are given $n$ jobs $J_1, J_2, . . . , J_n$ (where job $i$ is associated with deadlines $d_i$ and processing times $t_i$) to be scheduled on a single machine. The lateness of job $i$ is defined as $L_i = \max(0, f_i - d_i)$, where $f_i$ is the completion time of job $i$. Our goal is to schedule all jobs such that $L = \max_i L_i$ is minimized.
The following greedy algorithms first sort jobs in some orders, then process the jobs in that order. Which of the following greedy algorithms always return an optimal schedule?

For the result of accessing the keys 4 and 7 in order in the splay tree given in the figure, which one of the following statements is FALSE?

We have a binary counter of $k$ bits. Each time we conduct an increment on the counter: $x\equiv x+1(\text{mod} \ 2^k)$ and the cost of the increment is the number of bits we need to flip. For example, when $k=3$, currently we have $x=010$, after increment we have $x=011$. Then this increment costs 1 because only 1 bit flips after increment. If we conduct the increment again, $x=100$. Then this increment costs 3 because we flip 3 bits. Now we conduct $n$ consecutive increments and estimate the total cost. Which of the following statements are TRUE?

1. If the inital value of the counter is 0, the total cost is $O(n)$

2. If the inital value of the counter is 0, the total cost is $O(n\log k)$

3. If $n=\Omega(k)$, the total cost is $O(n)$

4. If $n=\Omega(k)$, the total cost is $O(n\log k)$

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

The recurrence is $T(n)=aT(n/b)+O(n^c)$ . If we considering the Binary Search as divide and conquer, what are the values of $a$, $b$ and $c$？

Which of the following is a disadvantage of external sorting.

Consider three languages $X$, $Y$ and $Z$, all in NP. Suppose that $X\leq_{p} Y$, $Y\leq_{p} Z$. Which one in the following is correct?

Delete the minimum number from the given binomial queues in the following figure. Which one of the following statements must be FALSE?

There are $N$ different numbers. What's the minimum time complexity to find the $K$-th largest number with parallel algorithms? (No need to worry about access conflicts)

We are given $n$ items that are arranged in a row. From left to right, the size of items are $s_1, s_2, \ldots, s_n$, where $0< s_i \leq 1$. In addition, we require that each bin can only contain contiguous block of items with total size at most 1. That is, if items $i$ and $j$ are in the same bin, then all items between $i$ and $j$ should also be in this bin. Our goal is to pack all these items in the fewest number of bins. We adopt the classical bin packing algorithms to solve this problem, which of the following statement is true?

Merge the two skew heaps in the following figure. How many of the following statements is/are FALSE?

• the null path length of 8 is the same as that of 12
• 18 is the left child of 12
• 21 is the right child of 10

Delete the minimum number from the given skew heap. Which one of the following statements is FALSE?

When solving a problem with input size $N$ by divide and conquer, if at each stage the problem is divided into $7$ sub-problems of equal size $N/3$, and the conquer step takes $O(logN)$ to form the solution from the sub-solutions, then the overall time complexity is __.

There is an array $A$, $A[i]=i (1\leq i\leq 1024)$. If we use Balanced Binary Trees Parallel Algorithm to calculate the Prefix-Sum of $A$. Define $C(h,i)=\sum_{k=1}^\alpha A(k)$, where $(0,\alpha)$ is the rightmost descendant leaf of node $(h,i)$. Node $(h,i)$ indicates the $i$-th node in height $h$. For example, the root is node $(10,1)$ and leaves are node $(0,i)\ 1\leq i\leq 1024$. The value of $C(2,233)$ is

Below are the statistic data for one query. What are the precision and the recall for this query?

Which of the following statements about the turnpike reconstructionis problem is true:

Given a sequence of K values $\{a​_1​​, a_2, \dots, a​_K​​\}$(not necessarily integers). A continuous subsequence is defined to be$\{a_i, a_{​i+1}​​, \dots, a_j​​\}$ where $1≤i≤j≤K$. The maximum subsequence is the subsequence that has the largest product of its elements. For example, given sequence $\{ 2, 3, 0.5, -2, 4 \}$, its maximum subsequence is $\{ 2, 3 \}$. The largest product is therefore $6$.

Now you are supposed to find the largest product of the continuous subsequence. Hint: consider the optimal substructure of both the maximum and minimum product using your knowledge of dynamic programming.

Function Interface:

double MaxSequence(double nums[], int n);

where nums is an array of integers with n elements.

Judge Program:

#include <stdio.h>
#include <math.h>
#define MAXN 60000
#define max(x,y) ((x) > (y) ? (x) : (y))
#define min(x,y) ((x) < (y) ? (x) : (y))

double MaxSequence(double nums[], int n);

int main()
{
    double nums[MAXN];
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) scanf("%lf", &nums[i]);
    printf("%.2f", MaxSequence(nums, n));
    return 0;
}
/* Your function will be put here */

Sample Input:

5
2 3 0.5 -2 4

Sample Output:

6.00