Givien two matrices and , the time complexity of the simple matrix multiplication is . Now let's consider the following Divide and Conquer idea:
Divide each matrix into four submatrics as follows:
=
We recursively calculate each block of as and so on. This can reduce the time complexity of the simple calculation. ~@
Recall the discussion about the Maximum Finding Problem (that is, to find the maximum among numbers in an array), Common CRCW memory strategy is used to assure for the parallel algorithm. Actually, we can also apply Arbitrary CRCW memory strategy to keep time complexity. Now let us consider a new memory strategy, namely the Concurrent Read Owner Write (CROW). It means that each memory has an official "owner". Only the "owner" can write to the corresponding memory. Then there is no parallel algorithm that can solve the problem with using CROW memory strategy. ~@
Consider a state-flipping algorithm for the Maximum-Cut problem. We say that partitions and are neighbors under the -flip rule if can be obtained from by moving at most nodes from one side of the partition to the other. If is a local optimum under the -flip rule, it is also a local optimum under the -flip rule for every .
~@
In the bin packing problem, suppose that the maximum size of the items is bounded from above by . Now let's apply the Next Fit algorithm to pack a set of items into bins with capacity 1. Let and denote the numbers of bins used by algorithms Next Fit and the optimal solution. Then for all , we have for some . 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 = 271 and = 90, the probability of hiring the 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?
Which one of the following statements is FALSE?
When measure the performance of parallel algorithm, we often use work load () and worst-case running time (). How many evaluation metrics are asymptotically equivalent to and ?
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 matrices and . Let's consider the following Divide and Conquer idea to do matrix multiplication .
Divide each matrix into four submatrics as follows:
=
We define as follows:
Here all the matrix multiplications are done recursively. Then each part of can be calculated by simple additions and subtractions among .
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 . Each takes place during a time interval .
If an instance 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 jobs, and each job has a processing time . We will use a local search algorithm to partition the jobs into two groups A and B, where set A is assigned to machine and set B to . The time needed to process all of the jobs on the two machines is , . The problem is to minimize .
Local search: Start by assigning jobs to , and the rest to .
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?
The function DeleteRoot
is to delete the root of a subtree with index Ind
from a binomial queue H
. The rest of the subtree is then stored as a new binomial queue and returned.
BinQueue DeleteRoot( BinQueue H, int Ind )
{
BinTree OldRoot, SubTree;
BinQueue NewBinQ;
int i;
OldRoot = H->TheTrees[Ind];
SubTree = OldRoot->LeftChild;
free(OldRoot);
NewBinQ = Initialize();
NewBinQ->CurrentSize = (3分);
for ( (3分) ) {
NewBinQ->TheTrees[i] = SubTree;
SubTree = SubTree->NextSibling;
NewBinQ->TheTrees[i]->NextSibling = NULL;
}
return NewBinQ;
}
CYLL has an integer-typed variable whose initial value is 1. The variable can be updated in each step by applying either of the two operations:
Multiply the variable by a fixed integer :
Add an integer () to the number:
Given two integers and as inputs, can you help CYLL to decide the minimum number of steps required before she obtains the number as the variable value?
int FindMinSteps(int N, int K);
Here () is the target number and () is the multiplication factor, which are integers as described in the problem specification.
The function is expected to return the minimum number of steps before the variable reaches value . (See the sample input/output for a concrete example.)
#include <stdio.h>
int FindMinSteps(int N, int K);
int main()
{
int N, K;
scanf("%d%d", &N, &K);
printf("%d", FindMinSteps(N, K));
return 0;
}
/* Implement the 'FindMinSteps' function here */
101 2
6
step 1:
step 2:
step 3:
step 4:
step 5:
step 6:
Note that this is not the only way to reach 101 in 6 steps, however, we care about the minumum number of steps, which is unique, rather than how you reach there.