Amortized analysis is a technique to provide an upper bound on the actual cost of a sequence of operations
Consider the randomized quicksort. We have proved that it runs in time in expectation even for the worst input. Is the following statement true of false?
There exists some good inputs on which the expected running time of randomized quicksort is where is the input size.
Recall that, to solve the closest pair problem, the first step of the divide-and-conquer algorithm divides the point set into and according to the x-coordinate. Is the following statement true of false?
In the combine step of this algorithm, it is always able to find the closest pair with one point in and the other in .
Suppose that the internal memory can handle records at a time. We use replacement selection algorithm to generate a long run on the following sequence {81, 94, 11, 96, 12, 80, 17, 98, 28, 58, 41, 75, 15}, then 98 belongs to the first run.
There exists an on-line algorithm for the bin packing problem that uses at most 3/2 the optimal number of bins for any instance.
Starting from the following configuration of a Hopfield Neural Network, the state-filpping algorithm will terminiate at a stable configuration after at most 32 iterations.
For the Activity Selection Problem, we can get the optimal solution by selecting the interval which starts earliest.
Stop words should be ignored when creating inverted file indices, since they appear rarely in articles, and are not useful for indexing.
For the Turnpike reconstruction algorithm of points, assuming that the distance set is maintained as an AVL tree, the running time is if no backtracking happens.
A problem is NP-complete if and only if it is in and there is no polynomial time algorithms for it.
When we solve the summation problem via designing the parallel algorithms, we shorten the asymptotic time complexity but take more asymptotic work loads comparing with the sequential algorithms.
After deleting 12 from the following red-black tree, 13, 14, 15 and 17 will change its color.
After merging two Leftist Heaps H1 and H2 of different NPL's, the NPL of the resulted Leftist Heap will be no more than max(NPL of H1, NPL of H2)
Given a set of 20000 emails in the mailbox, our task is to retrieve the spam emails from this set. The statistic data for a spam filter's performance are shown in the following table. The precision of this filter is: ___.
Category | Actual True Spam | Actual False Spam |
---|---|---|
Retrieved True Spam | 3000 | 6000 |
Retrieved False Spam | 5000 | 6000 |
Scheduling Job Problem: There are jobs and identical machines (running in parallel) to which each job may be assigned. Each job must be processed on one of these machines for time units without interruption. Each machine can process at most one job at a time. The aim is to complete all jobs as soon as possible; that is, if job completes at a time (the schedule starts at time ), then we wish to minimize . The length of an optimal schedule is denoted as .
Local Search Algorithm: Start with any schedule; consider the job that finishes last; check whether or not there exists a machine to which it can be reassigned that would cause this job to finish earlier. If so, transfer job to this other machine. The local search algorithm repeats this procedure until the last job to complete cannot be transferred. An illustration of this local move is shown in following figure.
Which of the following statement is false?
You have 20 identical cores on which you want to schedule some jobs. Each job has a processing time . If is the set of jobs assigned to core , let the load be . Now, you want to partition the jobs among the cores to minimize the load of the most-loaded core.
We design a greedy algorithm that picks any unassigned job, and assign it to the core with the least current load.
What is the approximation ratio of the greedy algorithm? (Choose the smallest bound that applies.)
When deleting node 6 from the following Leftist Heap, which statement is False for the resulted priority queue?
Delete the minimum number from the binomial queue given in the following figure. Which one of the following statements must be FALSE? (Note that you can merge any two of carry, T1 and T2 when all of them are not none)
For the game tree shown below, for which values of the dashed branch with the scissors will be pruned by - pruning? (Assume that the nodes are evaluated left to right)
A Huffman tree with 61 nodes is the optimal coding tree for characters. What a conclusion can we make for ?
Which one of the following statements about the Maximum Finding is False?
Recall that in the merge sort, we divide the input list into two groups of equal size, sort them recursively, and merge them into one sorted list. Now consider a variant of the merge sort. In this variant, we divide the input list into groups of equal size, where is the input size. What is the worst case running time of this variant? (You may use the fact that merging sorted lists takes where is the total number of elements in these lists.)
Consider the hiring problem. Assume that the candidates arrive in random order, and that no two candidates have the same performance. Let be some fixed parameter in the range . 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 all the first k candidates
hire candidate i
How many candidtes will be hired in expectation?
Consider the following pseudo-code.
strange():
if then return
strange()
strange()
for to :
for to :
print()
strange()
strange()
What is the running time of this pseudo-code? Your answer should be as tight as possible. (You may assume that is a power of 2.)
A -nodes AVL tree performs insertion or deletion in the worst case that costs , , respectively, where are constants. Now, we start from an empty tree, perform a sequence of insertions or deletions in the AVL tree. To analysis the amortized cost per insertion or deletion, we define a potential function . What is the amortized cost per insertion or deletion?
How many of the following statements are correct?
To perform Insert
on a B+ tree of order M, a node with M+1 keys will be split into 2 nodes.
After inserting consequentially into an initially empty B+ tree of order 3, how many split operations have occurred in total?
After deleting 7 from the given splay tree, which of the following statements about the resulting tree is impossible?
We have 4 tapes for 3-way external merge sorting. How shall we distribute 31 runs into 3 tapes, such that the total number of passes is minimized.
After Inserting 12 into the following Skew Heap, which of the following statements is correct for the resulted Skew Heap?
Which of the following binomial trees can represent a binomial queue of size 167?
Which one of the following statements about the Ranking problem is TRUE? (Assume that both arrays contain elements)
There are (=8) characters whose frequencies are the first (=8) Fibonacci numbers. How many of the following statements about the Huffman Coding is/are correct?
(1) No more than 2 characters have the same code length.
(2) For any (), the maximum length of the codes is .
(3) The minimum length of codes is 2.
You have items and a knapsack with a capacity of . The weight of the -th item is and the value is . Suppose the number of each item is infinite, calculate the maximum sum of value if the total weight of the items does not exceed the capacity of the knapsack. All numbers are in the range of .
#include<bits/stdc++.h>
using namespace std;
int f[1010],w[1010],v[1010],n,W;
int main()
{
scanf("%d%d",&n,&W);
for(int i=1;i<=n;i++)
scanf("%d%d",&w[i],&v[i]);
for(int i=1;i<=n;i++)
for(int j=w[i];j<=W;j++)
(3分)
printf("%d\n",(3分));
return 0;
}
An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.
Now given a sequence of insertions, you are supposed to build the AVL tree. Then given a sequence of statements about the structure of the resulting tree, you are supposed to tell if they are correct or not. A statment is one of the following:
(1) A is the root
(2) A and B are siblings
(3) A is the parent of B
(4) A is the left child of B
(5) A is the right child of B
Tree Build_AVL ( int input[ ], int n );
int Judge ( Tree T, int type, int A, int B );
The function Build_AVL
is supposed to build an AVL tree according to the input sequence.
Here Tree
is defined as the following:
typedef struct TNode *Tree;
struct TNode {
int key; //key of the node
int height; //height of the subtree with this node as the root
Tree left, right; //pointing to the left and right children of this node
};
The array input
contains n
(a positive integer) distinct keys to be inserted in order into an initially empty AVL tree. The root pointer of the resulting tree is supposed to be returned by Build_AVL
.
The function Judge
is supposed to test if a given statement for an AVL tree T
is correct or not, and return 1
if the result is true, or 0
otherwise. The parameter type
is an integer in [1, 5], which gives the index of a statement, as listed in the problem description; and A
and B
are the corresponging key values. For type 1, the value of B
can be ignored. It is guaranteed that both A
and B
in the statements are in the tree.
#include <stdio.h>
#include <stdlib.h>
typedef struct TNode *Tree;
struct TNode {
int key; //key of the node
int height; //height of the subtree with this node as the root
Tree left, right; //pointing to the left and right children of this node
};
Tree Build_AVL ( int input[ ], int n );
int Judge ( Tree T, int type, int A, int B );
int main()
{
int n, *input;
int m, type, A, B, i;
Tree T;
scanf("%d", &n);
input = (int *)malloc(sizeof(int) * n);
for (i=0; i<n; i++) scanf("%d", &input[i]);
T = Build_AVL(input, n);
scanf("%d", &m);
for (i=0; i<m; i++) {
scanf("%d %d", &type, &A);
if (type != 1) scanf("%d", &B);
if (Judge(T, type, A, B)) printf("Yes\n");
else printf("No\n");
}
return 0;
}
/* Your function will be put here */
3
88 70 61
8
1 70
1 61
2 61 88
2 88 70
3 88 70
3 70 61
4 88 70
5 88 70
Yes
No
Yes
No
No
Yes
No
Yes
5
88 70 61 96 120
7
1 70
2 96 88
3 96 120
4 88 70
4 88 96
5 120 96
5 88 70
Yes
No
Yes
No
Yes
Yes
No
6
88 70 61 96 120 90
8
1 70
1 88
2 90 61
3 70 61
3 96 70
4 90 96
5 90 88
5 96 88
No
Yes
No
Yes
No
Yes
No
Yes
7
88 70 61 96 120 90 65
7
1 88
2 96 70
2 61 70
3 61 65
4 65 88
4 70 88
5 70 65
Yes
No
Yes
No
Yes
No
Yes