25. Sieve Technique applies to problems where we are interested in finding a single item from a larger set of _____________
n items
phases
pointers
constant
26. A (an) _________ is a left-complete binary tree that conforms to the heap order
heap
binary tree
binary search tree
array
27. The sieve technique works in ___________ as follows
phases
numbers
integers
routines
28. For the sieve technique we solve the problem,
recursively
mathematically
precisely
accurately
29. For the heap sort, access to nodes involves simple _______________ operations.
arithmetic
binary
algebraic
logarithmic
30. The analysis of Selection algorithm shows the total running time is indeed ________in n,\
arithmetic
geometric
linear
orthogonal
For the sieve technique we solve the problem,
Select correct option:
recursively
mathematically
precisely
accurately
For the heap sort, access to nodes involves simple _______________ operations.
Select correct option:
arithmetic
binary
algebraic
logarithmic
We do sorting to,
Select correct option:
keep elements in random positions
keep the algorithm run in linear order
keep the algorithm run in (log n) order
keep elements in increasing or decreasing order
One of the clever aspects of heaps is that they can be stored in arrays without using any _______________.
Select correct option:
pointers
constants
variables
A (an) _________ is a left-complete binary tree that conforms to the heap order
Select correct option:
heap
binary tree
binary search tree
array
The analysis of Selection algorithm shows the total running time is indeed ________in n,
Select correct option:
arithmetic
geometric
linear
orthogonal
Sieve Technique applies to problems where we are interested in finding a single item from a larger set of _____________
Select correct option:
n items
phases
pointers
constant
Divide-and-conquer as breaking the problem into a small number of Select correct option:
pivot
Sieve
smaller sub problems
Selection
In Sieve Technique we do not know which item is of interest
Select correct option:
True
False
How much time merge sort takes for an array of numbers? Select correct option:
T(n^2)
T(n)
T( log n)
T(n log n)
For the heap sort we store the tree nodes in Select correct option:
level-order traversal
in-order traversal
pre-order traversal
post-order traversal
1.For the heap sort we store the tree nodes in
level-order traversal
in-order traversal
pre-order traversal
post-order traversal
2.One of the clever aspects of heaps is that they can be stored in arrays without using any _______________.
pointers
constants
variables
functions
3. Sorting is one of the few problems where provable ________ bonds exits on how fast we can sort,
upper
lower
average
log n
4.A (an) _________ is a left-complete binary tree that conforms to the heap order
heap
binary tree
binary search tree
array
5. Sieve Technique applies to problems where we are interested in finding a Single item from a larger set of _____________
n items
phases
pointers
constant
6.How much time merge sort takes for an array of numbers?
T(n^2)
T(n)
T( log n)
T(n log n)
7. A heap is a left-complete binary tree that conforms to the ___________
increasing order only
decreasing order only
heap order
(log n) order
8. In the analysis of Selection algorithm, we make a number of passes, in fact it could be as many as,
T(n)
T(n / 2)
log n
__________n / 2 + n / 4
9.The reason for introducing Sieve Technique algorithm is that it illustrates a very important special case of,
divide-and-conquer
decrease and conquer
greedy nature
2-dimension Maxima
10.The analysis of Selection algorithm shows the total running time is indeed ________in n,
arithmetic
geometric
linear
orthogonal
1.The sieve technique works in ___________ as follows
phases
numbers
integers
routines
1. For the sieve technique we solve the problem,
Recursively
mathematically
precisely
accurately
2. We do sorting to,
keep elements in random positions
keep the algorithm run in linear order
keep the algorithm run in (log n) order
keep elements in increasing or decreasing order
3. The reason for introducing Sieve Technique algorithm is that it illustrates a very
important special case of,
divide-and-conquer
decrease and conquer
greedy nature
2-dimension Maxima
4. In Sieve Technique we don’t know which item is of interest
True
False
5. In the analysis of Selection algorithm, we make a number of passes, in fact it could
be as many as,
T(n)
T(n / 2)
log n
n / 2 + n / 4
6. Divide-and-conquer as breaking the problem into a small number of pivot
Sieve
smaller sub problems
Selection
7. A heap is a left-complete binary tree that conforms to the ___________
increasing order only
decreasing order only
heap order
(log n) order
8. Slow sorting algorithms run in, T(n^2)
T(n)
T( log n)
T(n log n)
9. One of the clever aspects of heaps is that they can be stored in arrays
without using any _______________.
pointers
constants
variables
functions
10. Sorting is one of the few problems where provable ________ bonds exits on how fast we can sort,
upper
lower
average log n
2nd
11. For the sieve technique we solve the problem,
mathematically
precisely
accurately
recursively
12. Sieve Technique can be applied to selection problem?
true
false
13. How much time merge sort takes for an array of numbers? (n^2)
T(n)
T( log n)
T(n log n)
14. For the Sieve Technique we take time
T(nk)
T(n / 3) n^2
n/3
15. Heaps can be stored in arrays without using any pointers; this is due to the ____________ nature of the binary tree,
left-complete Repeat
right-complete tree nodes
tree leaves
16. How many elements do we eliminate in each time for the Analysis of Selection algorithm?
n / 2 elements
(n / 2) + n elements
n / 4 elements 2 n elements
17. We do sorting to,
keep elements in random positions
keep the algorithm run in linear order
keep the algorithm run in (log n) order
keep elements in increasing or decreasing order
18. In which order we can sort?
increasing order only
decreasing order only
increasing order or decreasing order
19. A heap is a left-complete binary tree that conforms to the ___________
increasing order only
decreasing order only
heap order
(log n) order
20. In the analysis of Selection algorithm, we make a number of passes, in fact it could be as many as,
T(n)
T(n / 2)
log n
n / 2 + n / 4
21. A heap is a left-complete binary tree that conforms to the ___________
increasing order only
decreasing order only
heap order
(log n) order
22. How much time merge sort takes for an array of numbers? T(n^2)
T(n)
T( log n)
T(n log n)
24. n the analysis of Selection algorithm, we eliminate a constant fraction of the array
with each phase; we get the convergent _______________ series in the analysis,
linear
arithmetic
geometric
exponent
25. Sieve Technique applies to problems where we are interested in finding a single item from a larger set of _____________
n items
phases
pointers
constant
26. A (an) _________ is a left-complete binary tree that conforms to the heap order
heap
binary tree
binary search tree
array
27. The sieve technique works in ___________ as follows
phases
numbers
integers
routines
29. For the heap sort, access to nodes involves simple _______________ operations.
arithmetic
binary
algebraic
logarithmic
30. The analysis of Selection algorithm shows the total running time is indeed ________in n
arithmetic
geometric
linear
orthogonal
For the heap sort, access to nodes involves simple _______________ operations. Select correct option:
Arithmetic
binary
algebraic
logarithmic
In Sieve Technique we do not know which item is of interest
True
False
How much time merge sort takes for an array of numbers?
T(n^2) T(n)
T( log n)
T(n log n)
For the heap sort we store the tree nodes in
level-order traversal
in-order traversal pre-order traversal
post-order traversal
One of the clever aspects of heaps is that they can be stored in arrays without using any _______________.
Pointers
constants
variables
functions
Sorting is one of the few problems where provable ________ bonds exits on how fast we can sort,
upper
lower
average log n
A heap is a left-complete binary tree that conforms to the ___________ Select correct option:
increasing order only
decreasing order only
heap order
(log n) order
In the analysis of Selection algorithm, we make a number of passes, in fact it could be as many as,
T(n)
T(n / 2)
log n
n / 2 + n / 4
The reason for introducing Sieve Technique algorithm is that it illustrates a very important special case of,
divide-and-conquer
decrease and conquer
greedy nature
2-dimension Maxima
The analysis of Selection algorithm shows the total running time is indeed ________in n, Select correct option:
arithmetic
geometric
linear
orthogonal
The sieve technique works in ___________ as follows
Phases
numbers
integers
routines
Sorting is one of the few problems where provable ________ bonds exits on how fast we can sort,
upper
lower
average
log n
In the analysis of Selection algorithm, we make a number of passes, in fact it could be as many as,
Select correct option:
T(n)
T(n / 2)
log n
n / 2 + n / 4
For the Sieve Technique we take time
T(nk)
T(n / 3)
n^2
n/3
A (an) _________ is a left-complete binary tree that conforms to the heap order Select correct option:
heap
binary tree
binary search tree array
For the heap sort we store the tree nodes in
level-order traversal
in-order traversal
pre-order traversal
post-order traversal
In the analysis of Selection algorithm, we eliminate a constant fraction of the array with
each phase; we get the convergent _______________ series in the analysis,
linear
arithmetic
geometric
exponent
One of the clever aspects of heaps is that they can be stored in arrays without using any _______________.
Pointers
constants
variables
functions
Analysis of Selection algorithm ends up with,
T(n)
T(1 / 1 + n)
T(n / 2)
T((n / 2) + n)
The analysis of Selection algorithm shows the total running time is indeed ________in n
arithmetic
geometric
Linear
orthogonal
Question No. 1 Marks : 1
Consider the following pairs of functions
I . f(x) = x2 + 3x+7 g(x) = x2 + 10
II f(x) = x2log(x) g(x) = x3
III f(x) = x4 + log(3×8 +7) g(x) = (x2 +17x +3)2
Which of the pairs of functions f and g are asymptotic?
Only I
Only II
Both I and III
None of the above
Question No. 2 Marks : 1
Execution of the following code fragment
int Idx;
for (Idx = 0; Idx < N; Idx++)
{
cout << A[Idx] << endl;
}
is best described as being
O(N)
O(N2)
O(log N)
O(N log N)
Question No. 3 Marks : 1
If algorithm A has running time 7n2 + 2n + 3 and algorithm B has running time 2n2,
then
Both have same asymptotic time complexity
A is asymptotically greater
B is asymptotically greater
None of others
Question No. 4 Marks : 1
Which of the following sorting algorithms is stable?
(i) Merge sort,
(ii) Quick sort,
(iii) Heap sort,
(iv) Counting Sort.
Only i
Only ii
Both i and ii
Both iii and iv
Question No. 1 Marks : 5
The following subroutine computes for a given number N. compute(N)
{
If (N==1)
return 2
else
return compute(N – 1) * compute(N – 1)
}
What category of algorithmic solutions best characterizes the approach taken in this subroutine (algorithm)?
Search and traversal
Divide-and-conquer
Greedy algorithm
Dynamic Programming
Question No. 1
Assume that a given algorithm has a runtime C that depends on the size N of its input
according to the following two formulas:
0 1
( )
( 1) 2
if N
C N
C N if N
=
= − + > 2
Which of the following functions C(N) describes the runtime of the algorithm?
C(N) = N – 1
C(N) = (N – 1)2
C(N) = log2 N
C(N) = 2(N – 1)
Question No. 7
Let us say we have an algorithm that carries out N2 operations for an input of size
N. Let us say that a computer takes 1 microsecond (1/1000000 second) to carry out one operation.How long does the algorithm run for an input of size 3000?
90 seconds
9 seconds
0.9 seconds
0.09 seconds
Question No. 8
Consider the following polynomial
aknk+ak-1nk-1+………….a0 .
What is the Big -O representation of the above polynomial?
O(kn)
O(nk)
O(nk+1)
None of the above
1. For the Sieve Technique we take time
> T(nk)
>T(n / 3)
>n^2 >n/3
2. Sieve Technique applies to problems where we are interested in finding a single item from a larger set of _____________
Select correct option:
>n items
>phases
>pointers
>constant
6. main elements to a divide-and-conquer
>Divide
>conquer
>combine
ALL of above
8.T(n)={4 if n=1, otherwise T(n/5)+3n^ what is the answer if n=5
79
80
90
150
8. Merge sort is a stable algorithm but not an in-place algorithm.
>True
>false
9. Counting sort the numbers to be sorted are in the range 1 to k where k is small.
>True
>False
1Total time for heapify is:
Ο (log 2 n)
Ο (n log n)
Ο (n2 log n)
Ο (log n)
4.In RAM model instructions are executed
One after another
Parallel
Concurrent
Random
5.In selection algorithm, because we eliminate a constant fraction of the array with each phase, we get the
Convergent geometric series
Divergent geometric series
None of these
6. Due to left-complete nature of binary tree, heaps can be stored in
Link list
Structure
Array
None of above
Question No: 1 ( Marks: 1 ) – Please choose one Random access machine or RAM is a/an
_ Machine build by Al-Khwarizmi
_ Mechanical machine
_ Electronics machine
_ Mathematical model
Question No: 2 ( Marks: 1 ) – Please choose one
_______________ is a graphical representation of an algorithm
_ S notation
_Q notation
_ Flowchart
_ Asymptotic notation
Question No: 3 ( Marks: 1 ) – Please choose one
A RAM is an idealized machine with ______________ random-access memory.
_ 256MB
_ 512MB
_ an infinitely large
_ 100GB
Question No: 4 ( Marks: 1 ) – Please choose one
What type of instructions Random Access Machine (RAM) can execute? Choose best answer
_ Algebraic and logic
_ Geometric and arithmetic
_ Arithmetic and logic
_ Parallel and recursive
Question No: 6 ( Marks: 1 ) – Please choose one
What is the solution to the recurrence T(n) = T(n/2)+n .
_ O(logn)
_ O(n)
_ O(nlogn)
_ O(n2)
Question No: 7 ( Marks: 1 ) – Please choose one Consider the following code:
For(j=1; j<n;j++)
For(k=1; k<15;k++)
For(l=5; l<n; l++)
{
Do_something_constant();
}
What is the order of execution for this code.
_ O(n)
_ O(n3)
_ O(n2 log n)
_ O(n2)
Question No: 8 ( Marks: 1 ) – Please choose one Consider the following Algorithm:
Factorial (n){
if (n=1)
return 1
else
return (n * Factorial(n-1))
Recurrence for the following algorithm is:
_ T(n) = T(n-1) +1
_ T(n) = nT(n-1) +1
_ T(n)= T(n-1) +n
_ T(n)=T(n(n-1)) +1
Question No: 9 ( Marks: 1 ) – Please choose one What is the total time to heapify?
_ _(log n)
_ _(n log n)
_ _(n2 log n)
_ _(log2 n)
Question No: 11 ( Marks: 1 ) – Please choose one
In Quick sort, we don’t have the control over the sizes of recursive calls
_ True
_ False
_ Less information to decide
_ Either true or false
Question No: 12 ( Marks: 1 ) – Please choose one
Is it possible to sort without making comparisons?
_ Yes
_ No
Question No: 14 ( Marks: 1 ) – Please choose one
For Chain Matrix Multiplication we can not use divide and conquer approach because,
We do not know the optimum k
We use divide and conquer for sorting only
We can easily perform it in linear time
Size of data is not given
Question No: 15 ( Marks: 1 ) – Please choose one
The Knapsack problem belongs to the domain of _______________ problems.
Optimization
NP Complete
Linear Solution
Sorting
Q 1
Total time for heapify is:
(log2 n)
(n log n)
(n2 log n)
(log n)
Q2:_
If an algorithm has a complexity of log2n + nlog2n + n. we could say that it has complexity
1)O(n)
2)O( n log2n)
3)O(3)
Q5
In selection algorithm, because we eliminate a constant fraction of the array with each phase, we get the
Convergent geometric series
Divergent geometric series None of these
Q#6
In RAM model instructions are executed
One after another
Parallel
Concurrent
Random
Qus 7
Consider the following pairs of functions
I . f(x) = x + 3x+7 g(x) = x + 1022
II f(x) = x2log(x) g(x) = x3
III f(x) = x + log(3x +7) g(x) = (x48 2 +17x +3)2
Which of the pairs of functions f and g are asymptotic?
Only I not sure
Only II
Both I and III
None of the above
Q8
Execution of the following code fragment int Idx; for (Idx = 0; Idx < N; Idx++)
{
cout << A[Idx] << endl;
}
is best described as being
O(N)
O(N2)
O(log N)
O(N log N)
Q9
If algorithm A has running time 7n2 + 2n + 3 and algorithm B has running time 2n2, then
Both have same asymptotic time complexity
A is asymptotically greater
B is asymptotically greater
None of others
Question No. 10
Which of the following sorting algorithms is stable? Merge sort,
Quick sort,
Heap sort,
Counting Sort.
Only i
Only ii
Both i and ii
Both iii and iv
“Counting sort and merge sort are both stable algorithms “
Q11
Consider the following recurrence relation
2 if n = 0 T n( ) =?
6 (T n – 1) otherwise
Then T(2) is
36
72
12
None of the above
Q12
Let us say we have an algorithm that carries out N2 operations for an input of size N. Let us say that a computer takes 1 microsecond (1/1000000 second) to carry out one
operation. How long does the algorithm run for an input of size 3000?
? 90 seconds
? 9 seconds
? 0.9seconds
? 0.09 seconds
Q What is the total time to heapify?
• O(log n)
• O(n log n)
• O(n2 logn)
• O(log2n)
1. For the sieve technique we solve the problem,
recursively
mathematically
precisely
accurately
2. We do sorting to,
keep elements in random positions
keep the algorithm run in linear order
Keep the algorithm run in (log n) order
keep elements in increasing or decreasing order
3. the reason for introducing Sieve Technique algorithm is that it illustrates a very important special case of,
divide-and-conquer
decrease and conquer
greedy nature
2-dimension Maxima
4. In Sieve Technique we do not know which item is of interest
True
False
5. In the analysis of Selection algorithm, we make a number of passes, in fact it could be as many as,
T(n)
T(n / 2)
log n
n / 2 + n / 4
6. Divide-and-conquer as breaking the problem into a small number of
pivot
Sieve
Smaller subproblems
Selection
7. A heap is a left-complete binary tree that conforms to the ___________
increasing order only
decreasing order only
heap order
(log n) order
8. Slow sorting algorithms run in,
T(n^2)
T(n)
T( log n)
T(n log n)
9. One of the clever aspects of heaps is that they can be stored in arrays without using any _______________.
pointers
constants
variables
functions
10. Sorting is one of the few problems where provable ________ bonds exits on how fast we can sort,
upper
lower
average
log n
11. For the sieve technique we solve the problem,
mathematically
precisely
accurately
recursively
12. Sieve Technique can be applied to selection problem?
true
false
13. How much time merge sort takes for an array of numbers?
(n^2)
T(n)
T( log n)
T(n log n)
14. For the Sieve Technique we take time
T(nk)
T(n / 3)
n^2
n/3
15. Heaps can be stored in arrays without using any pointers; this is due to the ____________ nature of the binary tree,
left-complete
right-complete
tree nodes
tree leaves
16. How many elements do we eliminate in each time for the Analysis of Selection algorithm?
n / 2 elements
(n / 2) + n elements
n / 4 elements
2 n elements
17. We do sorting to,
keep elements in random positions
keep the algorithm run in linear order
keep the algorithm run in (log n) order
keep elements in increasing or decreasing order
19. A heap is a left-complete binary tree that conforms to the ___________
increasing order only
decreasing order only
heap order
(log n) order
20. In the analysis of Selection algorithm, we make a number of passes, in fact it could be as many as,
T(n)
T(n / 2)
log n
n / 2 + n / 4
21. A heap is a left-complete binary tree that conforms to the ___________
increasing order only
decreasing order only
heap order
(log n) order
22. How much time merge sort takes for an array of numbers?
T(n^2)
T(n)
T( log n)
T(n log n)
23. One of the clever aspects of heaps is that they can be stored in arrays without using any _______________.
pointers
constants
variables
functions
24. n the analysis of Selection algorithm, we eliminate a constant fraction of the
array with each phase; we get the convergent _______________series in the analysis,
linear
arithmetic
geometric
exponent