Consider the Knapsack Problem. How many of the following statements are true?
Consider eight characters with the following frequencies. (We normalize the frequencies so that they sum to 1.)
Symbol | Frequency |
---|---|
A | 0.11 |
B | 0.11 |
C | 0.11 |
D | 0.11 |
E | 0.14 |
F | 0.14 |
G | 0.14 |
H | 0.14 |
What is the average encoding length of an optimal prefix code?
Consider the hiring problem. Assume that the n candidates arrive in random order, and that no two candidates have the same performance. Let k be some even number (偶数) in the range [1,n]. We use the following algorithm:
interview the first k candidates, but hire none of them for candidates i = k+1 to n if candidate i is better than at least half of the first k candidates hire candidate i
It is easy to see that the above algorithm may hire more than one candidates. How many candidates will be hired in expectation?
A Hamiltonian Cycle (or Circuit) in a graph is a cycle that visits every vertex exactly once and returns to the starting vertex. Finding a Hamiltonian Cycle is a well-known NP-complete problem. Let’s consider the following two new variants of the Hamiltonian problems:
P1) Long Cycle problem: A Long Cycle in a graph G is a cycle that goes through at least half of the vertices of G.
P2) Hamiltonian Path problem: A graph G has a Hamiltonian path from s to t if there is an s to t path that visits all of the vertices of G exactly once.
Which of the following statements is correct?
In the Activity Selection Problem, we are given a set of activities S={a1,a2,…,an} that wish to use a resource. Each ai takes place during a time interval [si,fi). Activities ai and aj are compatible if si≥fj or sj≥fi (i.e. their time intervals do not overlap). Our goal is to select a maximum-size subset of mutually compatible activities.
We propose a greedy rule “Shortest-First” that select the interval which is the shortest (but not overlapping the already chosen intervals). What is the approximation ratio of the greedy algorithm for the activity selection problem?
Insert 2,9,5,6,1,8, and 3 one by one into an initially empty Splay tree. Which one of the following statements is TRUE about the resulting tree?
Merge the two leftist heaps in the figure. How many of the following statements is/are FALSE ?
There are 100000 documents in the document collection. The statistic data for one query is shown in the following table.
Relevant | Irrelevant | |
---|---|---|
Retrieved | 10000 | 40000 |
Not Retrieved | 30000 | 20000 |
Which one of the following statements about the statistics is True?
The Traveling Salesman Problem (TSP) is a classic problem: given a set of cities and the distances between each pair of cities, the goal of TSP is to find the shortest cycle that visits each city exactly once and returns to the starting city.
The 2-opt method is a local search algorithm used to solve the TSP. Specifically, the searching strategy is as follows:
(1) Starting at a feasible solution to the TSP (a valid cycle which visits each city exactly once and returns to the starting city).
(2) In each iteration, the current cycle is denoted as P. The neighboring solution P′ is obtained by a 2-opt move. The 2-opt move contains the following steps:
i) Choosing two non-adjacent edges (i,i+1) and (j,j+1) from the cycle;
ii) Removing these two edges, and replacing them with new edges (i,j) and (i+1,j+1), forming a new cycle P′.
If the new cycle obtained by the 2-opt move is shorter than the current cycle, updating the current cycle as the new cycle.
(3) Repeating the step (2) until no further improvement can be made by applying 2-opt moves.
Here is an illustration of a 2-opt move.
Which of the following statements is true?
In the theory of parallel algorithms using PRAM, which one of the following statements is FALSE?
Consider two parallel algorithms for the same problem, with a total of Wi(n) operations in Ti(n) time (i=1,2). If W1(n)=O(n), T1(n)=O(n), and W2(n)=O(nlogn), T2(n)=O(logn). Then:
Suppose we have 4 types of fruit for 3 monkeys. Each monkey has its favorite types of fruit, and the matrix gives the corresponding relations between the monkeys and fruits -- that is, tij=1 means the ithe monkey loves the jth type of fruit, or 0 means the opposite. Use backtracking to find a way to send each monkey its favorite fruit, with the following restrictions:
Which one of the following game trees corresponds to a backtracking process?
Note: the black nodes are the ones being pruned, and the white ones are never visited. The nodes with a flag correspond to the solution.
There are four basic operations on red-black trees that perform structural modifications: node insertions, node deletions, rotations, and color changes. We shall prove that any sequence of m RB-INSERT and RB-DELETE operations on an initially empty red-black tree causes O(m) structural modifications in the worst case. We count the structural modifications in each step (e.g. Case 1 in RB-DELETION) as one unit operation (cost = 1).
We define the weight of each node based on its state, and the potential of the Red-Black Tree T is represented by the following function:
Φ(T)=∑x∈Tg(x)
where g(x) is calculated for all nodes x∈T of the Red-Black Tree.
We define the weight of a red node x as g(x)=0.
For black nodes, which of the following definitions work?
Suppose that replacement selection is applied in external sorting to generate longer runs with a priority queue of size 4. Given the sequence of numbers {51, 94, 37, 92, 14, 63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100}. How many of the following states are TRUE?
4 runs will be generated
14 is in the first runs
The length of the longest run is 9
90 is in the last runs
If a binomial queue consists of 3 trees, which of the following numbers can NOT be its number of nodes?
A key advantage of binomial queue is that its amortized time cost of insertion is O(1). To prove this argument, a key observation is that if inserting one new key in the queue takes time cost c, it will lead to increasing m trees in the queue, where m equals to
What is the tightest solution to the recurrent function T(n)=2T(n/2)+nlogn?
How many of the following arguments are TRUE?
In comparison to dynamic programming, divide-and-conquer algorithms are usually more suitable for problems with highly overlapping sub-problems.
In the divide-and-conquer solution to the “closest pair of points in the plane” problem, sorting the points in both X and Y axes at the beginning of the whole algorithm is essential to achieve the O(nlogn) time complexity.
Consider the view point of treating function T(n)=aT(n/b)+nc as a recursion tree. If T(n)=O(nc), then the time cost is dominated by the root of the tree.
Suppose a red-black tree T contains N(N≥2) internal nodes, we denote the height of T as h(T) and the black-height of T as bh(T). Which of the following statements must be FALSE (assume the height of an empty tree is 0)?
Merge the two skew heaps in the following figure. How many of the following statements is/are FALSE?