Let Σ be a set of at least two characters, each having a frequency. In any optimal prefix-free code for Σ, at least two characters have the same coding length.
Let T(n) be the running time of quicksort on an input of size n. We already know that T(n) is a random variable whose value depends on the random choices of quicksort, and that the expectation of T(n) is O(nlogn). Is the following statement true or false? The minimum possible value of T(n) can be as small as Θ(n), and the maximum possible value can be as large as Θ(n2).
If NP = co-NP, then P = NP.
We have an approximation algorithm ALG for a minimization problem X. For any given ε>0, the approximation ratio of ALG is 1+ε and the running time is O(31/εn2), where n is the input size of the problem X. Then the algorithm ALG is an FPTAS.
Insert 2,9,5,6,1,8, and 3 one by one into an initially empty AVL tree. Then the postorder traversal sequence of the resulting tree must be {1,3,2,6,9,8,5}.
For a leftist heap, the NPL of each node is 1 greater than the NPL of its right child.
In the dynamic indexing situation, the main index is usually updated when a new document comes to the document collection.
There are two statements about Local Search:
Only one of the statements above is correct.
Priority CRCW allows concurrent access for both reads and writes, while the processor with the smallest number has the highest priotity.
The time taken to backtrack -- that is, to recover the previous state of a solution is relatively hard (that is, no definite polynomial-time method works) to estimate during backtracking.
In amortized analysis, the change in potential should be negative for low-cost operations and positive for high-cost operations.
Given 2000 runs and 10 tapes. If simple k-way merge is used, the minimum number of passes required is 5 (runs generation pass is not counted).
The recurrent equation T(n)=nT(n/2)+n can be solved by the master theorem.