CS502 Quiz 2 Mcqs Lecture 1 to 22 Spring 2024

 Aslam U Alaikum!

Dear Students

In this post we are providing you CS502 Quiz 2 Mcqs Lecture 1 to 10 Spring Fall 2024 100% correct or right solution.

CS502 Quiz 2 Mcqs Lecture 1 to 22 Spring 2024 #Mid-Term WITH PROVE ANSWER

Which method is preferable for dealing with chain matrix multiplication?

dynamic programming

Memoization is a part of ________ programming strategy.

Dynamic

A problem exhibits optimal structure if an optimal solution to the problem contains within it optimal solution to__________________.

sub-problems

We can't utilize a divide-and-conquer strategy for Chain Matrix Multiplication because ____________.

We do not know the optimum k              

Dynamic Programming algorithms often use some kind of ___________ to store the results of intermediate sub-problems.

Table

The formula for calculating the Catalan number is ____________.

Cn = (2n)! / ((n + 1)! * n!)

 

In chain matrix multiplication, if there are n items, there are ______ ways in which outer most pair of parentheses can placed.

n-1

Algorithms similar to those for the ______________ problem are used in some speech recognition systems.

edit-distance

Suppose we have 4 matrices A, B , C, D . What is correct expansion of m[1,2] in chain matrix multiplication?

 m[1, 2] = m[1, 2] +m[2, 2] + p0 · p1 · p2

What will be value of the matrices product (A1A2)A3 ? if A1 = 5*3  A2 = 3*7   A3 = 7*2.

88

                

What is the best case time complexity of merge sort?

O(n∗logn)

For n > 1, _______ divides into two halves, sorts the two and then combine them together.

MergeSort

While solving the selection problem in sieve technique we partition input date:

According to pivot

__ is the process of avoiding unnecessary repetitions by writing down the results of a recursive calls and looking them up again if we need them later:

Memorization

Heaps can be stored in arrays without using any pointers; this is due to the ____________ nature of the binary tree, 
left-complete


Sieve Technique can be applied to selection problem? 
True


A heap is a left-complete binary tree that conforms to the ___________ 
heap order


A (an) _________ is a left-complete binary tree that conforms to the heap order 
heap


Divide-and-conquer as breaking the problem into a small number of 
smaller sub problems


In Sieve Technique we do not know which item is of interest 
True


The recurrence relation of Tower of Hanoi is given below T(n)={1 if n=1 and 2T(n-1) if n >1 In order to move a tower of 5 rings from one peg to another, how many ring moves are required? 
32

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, 

geometric 

For the heap sort, access to nodes involves simple _______________ operations. 
arithmetic


For the sieve technique we solve the problem,
recursively


The sieve technique works in ___________ as follows
phases
 

Slow sorting algorithms run in,
T(n^2)


A (an) _________ is a left-complete binary tree that conforms to the heap order
heap


In the analysis of Selection algorithm, we make a number of passes, in fact it could be as many as,

T(n / 2)


The sieve technique is a special case, where the number of sub problems is just

1


In which order we can sort?

increasing order or decreasing order


Analysis of Selection algorithm ends up with,

T((n / 2) + n)

The analysis of Selection algorithm shows the total running time is indeed ________in n,

linear 


How many elements do we eliminate in each time for the Analysis of Selection algorithm? 
n / 2 elements 


For the heap sort we store the tree nodes in 
level-order traversal 

One of the clever aspects of heaps is that they can be stored in arrays without using any _______________. 
pointers

Divide-and-conquer as breaking the problem into a small number of 
smaller sub problems

How much time merge sort takes for an array of numbers? 

T(n log n)

The reason for introducing Sieve Technique algorithm is that it illustrates a very important special case of, 
divide-and-conquer

The number of nodes in a complete binary tree of height h is
2^(h+1) – 1

Sieve Technique applies to problems where we are interested in finding a single item from a larger set of _____________
n items

Memorization is?

To avoid this unnecessary repetitions by writing down the results of recursive calls and looking them up again if we need them later

 Which sorting algorithm is faster

O (n+k)

 Quick sort is
Not stable but in place

One example of in place but not stable algorithm is

Quick Sort

 In Quick Sort Constants hidden in T(n log n) are

Small

Continuation sort is suitable to sort the elements in range 1 to k

K is small

 In stable sorting algorithm.
If duplicate elements remain in the same relative position after sorting

 Which may be a stable sort?
None of the above

 An in place sorting algorithm is one that uses ___ arrays for storage
No Additional Array

We do sorting to,

keep elements in increasing or decreasing order 

In Sieve Technique we donot know which item is of interest
True

 Sorting is one of the few problems where provable ________ bonds exits on how fast we can sort,
lower

The reason for introducing Sieve Technique algorithm is that it illustrates a very important special case of,
divide-and-conquer

Analysis of Selection algorithm ends up with,
T(n)

In in-place sorting algorithm is one that uses arrays for storage :

No additioanal array

Which sorting algorithn is faster :

O(nlogn)

The running time of quick sort depends heavily on the selection of

Pivot elements

Which may be stable sort:

Both of above


For the Sieve Technique we take time
T(nk)

In the analysis of algorithms __ plays an important role :

GROWTH RATE

If matrix A of dimension 2x4 is multiplied with a matrix B of dimension 4x3 then the dimension of resultant matrix will be :

2x3

In average-case time the probability of seeing input is denoted by _

p(1)

While applying the sieve technique to selection sort how to choose a pivot element

Randomly

Number of __ of pseudo code are counted to measure the running time:

STEPS

___overcomes the limitations of _ by working as per positional notations of numbers :

bubble sort , radix sort

If matrix A of dimension pxq is multiply with matrix B of dimension qxr then the dimension resultant matrix is _

 pxr

__ is in-place sorting algorithm :

bubble sort

Dynamic programming  algorithms often use some kind of _ to store the results of intermediate sub-problems :

table

 

Sorting is performed on the basis of :

computational resources

In heap sort algorithm (using max heap) when everytime maximum element is removed from top

 We are left with a hole 

Sorting Algorithms having O _______ running time are considered to be slow ones.

(n^2)

Insertion sort is an efficient algorithm for sorting a ____________ number of elements.

Small

The sieve technique works where we have to find _________ item(s) from a large input.

Single

In ____________ we have to find the rank of an element from the given input.

Selection problem 

While solving the Selection problem, in the Sieve technique, we partition the input data ___________.

According to Pivot

In a max heap (for Heap Sort algorithm), when the maximum element is removed from the top, we replace it with ___________ leaf in the tree.

Last

While sorting, the ordered domain means for any two input elements x and y _________ satisfies only.

x < y

In the Heap Sort algorithm, the first step is to _________.

Call Build-Heap procedure

The total number of arguments passed to the merge sort algorithm is _________.

2

 1. For the sieve technique we solve the problem,

Recursively (Handsouts Page 35 Line 4)
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 (Handsouts Page 39 Line 6)

3. The reason for introducing Sieve Technique algorithm is that it illustrates a very
important special case of,
divide-and-conquer (handsouts page 34 )
decrease and conquer
greedy nature
2-dimension Maxima
4. In Sieve Technique we don’t know which item is of interest
True (handsouts page 34)
False5. 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 (handsouts page 37)
n / 2 + n / 4
6. Divide-and-conquer as breaking the problem into a small number of pivot
Sieve
smaller sub problems (handouts page 27)
Selection
7. A heap is a left-complete binary tree that conforms to the
increasing order only
decreasing order only
heap order (handouts page 40)
(log n) order
8. Slow sorting algorithms run in, T(n^2)
T(n)
T(log n)
T(n log n) (handsouts page 40)
9. One of the clever aspects of heaps is that they can be stored in arrays
without using any .
pointers (handsouts page 40)
constants
variables
functions
10. Sorting is one of the few problems where provable bonds exits on how fast
we can sort,
upper
lower (handsouts page 39)
average log n
2nd
11. For the sieve technique we solve the problem,
mathematically
precisely
accurately
recursively (handsouts page 35)
12. Sieve Technique can be applied to selection problem?
true (handsouts page 35)
false
13. How much time merge sort takes for an array of numbers? (n^2)
T(n)
T(log n)
T(n log n) (handouts page 30)14. For the Sieve Technique we take time
T(nk) (handouts page 34)
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 ( page 39 Repeat)
18. In which order we can sort?
increasing order only
decreasing order only
increasing order or decreasing order Repeat
both at the same time
19. A heap is a left-complete binary tree that conforms to the
increasing order only
decreasing order only
heap order (page 40)
(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 (page 37)
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 (page 40)
(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) (page 30)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 (page 37)
exponent
25. Sieve Technique applies to problems where we are interested in finding a single item
from a larger set of
n items (page 34)
phases
pointers
constant
26. A (an) is a left-complete binary tree that conforms to the heap order
heap (page 40)
binary tree
binary search tree
array
27. The sieve technique works in as follows
phases (page 34)
numbers
integers
routines
29. For the heap sort, access to nodes involves simple operations.
arithmetic (page 41)
binary
algebraic
logarithmic
30. The analysis of Selection algorithm shows the total running time is indeed
in n
arithmetic
geometric
linear (page 37)
orthogonal
For the heap sort, access to nodes involves simple operations. Select
correct option:
Arithmetic (page 41)
binary
algebraic
logarithmic
In Sieve Technique we do not know which item is of interest
True (page 34)
FalseHowmuch time merge sort takes for an array of numbers?
T(n^2) T(n)
T( log n)
T(n log n) (page 30)
For the heap sort we store the tree nodes in
level-order traversal (page 40)
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 (page 40)
constants
variables
functions
Sorting is one of the few problems where provable bonds exits on how fast we
can sort,
upper
lower (page 39)
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 Repeat
(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 Repeat
n / 2 + n / 4
The reason for introducing Sieve Technique algorithm is that it illustrates a very
important special case of,
divide-and-conquer (page 34)
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 Repeat
orthogonalThe sieve technique works in as follows
Phases Repeat
numbers
integers
routines
Sorting is one of the few problems where provable bonds exits on how fast we
can sort,
upper
lower Repeat
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 Repeat
n / 2 + n / 4
For the Sieve Technique we take time
T(nk) Repeat
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 Repeat
binary tree
binary search tree array
For the heap sort we store the tree nodes in
level-order traversal Repeat
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 Repeat
exponent
One of the clever aspects of heaps is that they can be stored in arrays without using any
.
Pointers Repeat
constants
variables
functionsAnalysis of Selection algorithm ends up with,
T(n) (page 37)
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 Repeat
Orthogonal
Question No. 1 Marks : 1
Consider the following pairs of functions
I. f(x) = x2 + 3x+7 g(x) = x2 + 10
IIf(x) = x2log(x) g(x) = x3
IIIf(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 Sure
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) Sure
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 Sure
A is asymptotically greater
Bis 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 Ref (Merge sort and counting sort are stable algorithms)
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 (Not Sure)
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 (Not Sure)
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 (Sure)
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) (Sure)
O(nk+1)
None of the above
1. For the Sieve Technique we take time
>T(nk) (page 34)
>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 (page 34)
>phases
>pointers
>constant
3. graphical representation of algorithm.
> Asymptotic
>. Flowchart (rep)
4. who invented the quick sort
Hoare (1961, 1962) (click here)5. function is given like 4n^4+ 5n^3+n what is the run time of
this
>theata(n^4) (click here )
>theata(n^3)
>theata(4n^4+ 5n^3) >
theata(4n^4+ 5n^3)
6. main elements to a divide-and-conquer
>Divide
>conquer
>combine
ALL of above (page27 )
8.T(n)={4 if n=1, otherwise T(n/5)+3n^ what is the answer if n=5
Answer is 79 (not sure)
8. Merge sort is a stable algorithm but not an in-place algorithm.
>True (page 54 )
>false
9. Counting sort the numbers to be sorted are in the range 1 to k where k is small.
>True (page 57)
>False
1Total time for heapify is:
2
Ο (log n)
Ο (n log n)
2
Ο (n log n)
Ο (log n) (page 43)
2 Solve the recurrence using iteration method and also find time complexity (Θ
notation)
T (n) = C + O (1) + T (n-1)
T (1) =1 and C is a constant.
3 If an algorithm has a complexity of
logcomplexity
n + nlog
2
n + n. we could say that it has
2
O(n)
O( n log n) 2
O(3)
O(log
2
(log2
n ))
O ( log2
n) (Not sure>click here)4.In RAM model instructions are executed
One after another
Parallel
Concurrent
Random (page10)
5.In selection algorithm, because we eliminate a constant fraction of the array with
each phase, we get the
Convergent geometric series (page 37)
Divergent geometric series
None of these
6. Due to left-complete nature of binary tree, heaps can be stored in
Link list
Structure
Array (page 40)
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 ref (Page 10)
Question No: 2 ( Marks: 1 ) – Please choose one
is a graphical representation of an algorithm
_ S notation
_Q notation
_ Flowchart ref (http://www.edrawsoft.com/flowchart.php)
_ 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 ref (Page 10)
_ 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 ref (Page 10)
_ Parallel and recursiveQuestion No: 5 ( Marks: 1 ) – Please choose one
What will be the total number of max comparisons if we run brute-force maxima
algorithm with n elements?
n
n
2
2
n ref(Page 12) there are two loops
n
8
n
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) ref(ref book page # 33)
_ 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) ref (there are 3 nested for loops so it’s order isO(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 (Not Sure)Question No: 9 ( Marks: 1 ) – Please choose one
What is the total time to heapify?
_ _(log n) ref (Page # 43)
_ _(n log n)
_ _(n2 log n)
_ _(log2 n)
Question No: 10 ( Marks: 1 ) – Please choose one
When we call heapify then at each level the comparison performed takes time
It will take  (1) ref (Page # 43)
Time will vary according to the nature of input data
It can not be predicted
It will take  (log 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 ref (page # 49)
_ False
_ Less information to decide
_ Either true or false
Question No: 12 ( Marks: 1 ) – Please choose one
Isit possible to sort without making comparisons?
_ Yes ref (page # 57)
_ No
Question No: 13 ( Marks: 1 ) – Please choose one
If there are _ (n2) entries in edit distance matrix then the total running time is
(1)
(n2)
(n)
(n log n)
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 ref (page # 86)
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 ref (page # 91)
NPComplete
Linear Solution
SortingQ 1
Total time for heapify is:
(log2 n)
(n log n)
(n2 log n)
(log n) (page 43) repeat
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) (page 106)
3)O(3)
4)O( log2( log2n )) 5)O ( log2n)
Q 4
Due to left-complete nature of binary tree, heaps can be stored in Link list
Structure
Array (page 40) repeat
None of above
Q5
In selection algorithm, because we eliminate a constant fraction of the array with each
phase, we get the
Convergent geometric series (page 37)
Divergent geometric series None of these
Q#6
In RAM model instructions are executed
One after another (page 10)
Parallel
Concurrent
Random
Qus 7
Consider the following pairs of functions
I. f(x) = x + 3x+7 g(x) = x + 1022
IIf(x) = x2log(x) g(x) = x3
IIIf(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) sure 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 (see page 24)
A is asymptotically greater
B
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
ThenT(2) is
? 36 not sure
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
Q13
The appropriate big ? classification of the given function. f(n) = 4n2 + 97n + 1000 is
? (n)
? (2n)
? (n2)
? (n2 log n)
Q14
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
Q15
Consider the C++ program segment given below: for ( i=0 ; i < n; i++) {
for(j = 1,sum=a[0]; j < = i; j++) Sum+=a[j];
Cout<< “The sum for sub-array is<< sum;
}
The running time of the above algorithm is
n.
n log n .
log n .
n2.
Q16
Consider the following pairs of functions
I. f(x) = (x3 + x2 + x + 1)4 g(x) = (x4 +x3 + x2+ x + 1)3
IIf(x) = 22x g(x) = 2x 2
IIIf(x) = 2x + 3 g(x) = 2x + 7
IV f(x) = log(x2 + 1) g(x) = log( x)
Which of the pairs of functions f and g are asymptotic?
Only I
Only III
Both I and II
Both III and IV
Question No. 5
Dynamic programming uses a top-down approach.
? True click here
? False
Question No. 6
The edit distance between FOOD and MONEY is
At most four (page 76)
At least four
Exact four
Question No. 7
Consider the following recurrence relation
4 if n = 1 T n( ) =?
T n + 2
n if n is divisible by 5 ( n/ 5) 3
ThenT(5) is
25 Not sure
75
79
None of the aboveQuestion No. 10
Execution of the following code fragment int i = N;
while (i > 0)
{
int Sum = 0; int j;
for(j = 0; j < N; j++) Sum++;
cout << Sum << end; i–;
} is best described as being
O(N) Sure
O(N2)
O(log N) O(N
log N) Question
No. 11
It is impossible to design a sorting algorithm based on comparison of keys whose worst
case run time is in O(n).
? True
? False (page 55)
Question No. 12
Consider the following recurrence relation
5 if n = 1
T n( ) =? + if n is even
? 2 ( / 2) 3 Then T(8) is
61
29
13
None of the above Not sure
Question No. 13
Themerge sort algorithm involves the following steps.
Recursively sort the 1st and 2nd halves separately
Merge the two-sorted halves into a sorted group.
If the number of items to sort is 0 or 1, return.
Which is the correct order of instructions in merge sort algorithm?
? (i),(ii),(iii)
? (ii),(iii),(i)
? (iii),(ii),(i)
? (iii),(i),(ii) (page 27)
Qus14
iterfib achieve an exponential speedup over the original recursive algorithm
True (page 75)
False
Q What type of instructions Random access machine can execute?
Choose best answer.
Geometric and arithmetic
Algebraic and logic
Parallel and recursiveQ Due to left complete nature of binary tree, the heap can be stored in
• Arrays (page 40)
• Structures
• Link Lis
• Stack
Q What type of instructions Random Access Machine (RAM) can execute? Choose
best
answer
Algebraic and logic
Geometric and arithmetic
Arithmetic and logic rep(Page 10)
Parallel and recursive
Q For Chain Matrix Multiplication we can not use divide and conquer approach
because,
We do not know the optimum k (page 86)
We use divide and conquer for sorting only
We can easily perform it in linear time
Size of data is not given
Q knapsack problem is called a “0-1” problem, because
?????????????????????
Each item must be entirely accepted or rejected (page 92)
?????????????????????
???????????????????????
Q word Algorithm comes from the name of the muslim author:
Abu Ja’far Mohammad ibn Musaal-Khowarizmi. (page 7)
Q al-Khwarizmi’s work was written in a book titled
al Kitab al-mukhatasar fi hisab al-jabr wa’l-muqabalah (page 7)
Q What is the total time to heapify?
• O(log n) (page 43)
• O(n log n)
• O(n2 logn)
• O(log2n)
1. For the sieve technique we solve the problem,
recursively (page 34)
mathematically
precisely
accurately2.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 (page 39)
3.the reason for introducing Sieve Technique algorithm is that it illustrates a very
important special case of,
divide-and-conquer (Page 34)
decrease and conquer
greedy nature
2-dimension Maxima
4.In Sieve Technique we do not know which item is of interest
True (page 34)
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 (page 37)
n / 2 + n / 4
6. Divide-and-conquer as breaking the problem into a small number of
pivot
Sieve
Smaller subproblems (page 34)
Selection
7. A heap is a left-complete binary tree that conforms to the
increasing order only
decreasing order only
heap order (page 40)
(log n) order
8. Slow sorting algorithms run in,
T(n^2) (page 39)
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 (page 40)
constants
variables
functions10. Sorting is one of the few problems where provable bonds exits on how
fast we can sort,
upper
lower (page 39)
average
log n
2nd
11. For the sieve technique we solve the problem,
mathematically
precisely
accurately
recursively (page 34) Repeat
12. Sieve Technique can be applied to selection problem?
true (page 34)
false
13. How much time merge sort takes for an array of numbers?
(n^2)
T(n)
T( log n)
T(n log n) (page 40)
14. For the Sieve Technique we take time
T(nk) (page 34)
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 (page 40)
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 (page 36)
(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 (page 39) Repeat18.In which order we can sort?
increasing order only
decreasing order only
increasing order or decreasing order
both at the same time
19. A heap is a left-complete binary tree that conforms to the
increasing order only
decreasing order only
heap order (page 40)
(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 (page 37) Repeat
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 (page 40) Repeat
(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) (page 40) repeat
23. One of the clever aspects of heaps is that they can be stored in arrays without
using any .
pointers (page 40) Repeat
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 (page 37)
exponent
25. Sieve Technique applies to problems where we are interested in finding a single
item from a larger set of
n items (page 34)
phases
pointers
constant26. A (an) is a left-complete binary tree that conforms to the
heap order
heap ref (page # 40)
binary tree
binary search tree
array
27.The sieve technique works in as follows
phases ref (page # 34)
numbers
integers
routines
28. For the sieve technique we solve the problem,
recursively ref (page #35)
mathematically
precisely
accurately
29. For the heap sort, access to nodes involves simple
operations.
arithmetic ref (page # 40)
binary
algebraic
logarithmic
30.The analysis of Selection algorithm shows the total running time is
indeed in n,\
arithmetic
geometric
linear ref(page # 37)
orthogonal
For the sieve technique we solve the problem,
Select correct option:
recursively ref (page # 35)
mathematically
precisely
accurately
For the heap sort, access to nodes involves simple
operations.
Select correct option:
arithmetic ref (page # 40)
binary
algebraic
logarithmicWe 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 ref (page # 40)
constants
variables
A (an) is a left-complete binary tree that conforms to the heap
order
Select correct option:
heap rep
binary tree
binary search tree
array
The analysis of Selection algorithm shows the total running time is indeed
in n,
Select correct option:
arithmetic rep
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 ref (page # 34)
phases
pointers
constant
Divide-and-conquer as breaking the problem into a small number of
Select correct option:
pivot
Sieve
smaller sub problems ref (page # 34)
Selection
In Sieve Technique we do not know which item is of interest
Select correct option:
True ref (page # 34)
FalseHow 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) ref (page # 40)
For the heap sort we store the tree nodes in
Select correct option:
level-order traversal ref (page # 40)
in-order traversal
pre-order traversal
post-order traversal
1.For the heap sort we store the tree nodes in
level-order traversal (page 40)
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 (page40)
constants
variables
functions
3. Sorting is one of the few problems where provable bonds exits on
how fast we can sort,
upper
lower (page39)
average
log n
4.A (an) is a left-complete binary tree that conforms to the heap
order
heap (page40)
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 (page34)
phases
pointers
constant6.How much time merge sort takes for an array of numbers?
T(n^2)
T(n)
T( log n)
T(n log n) (page40)
7. A heap is a left-complete binary tree that conforms to the
increasing order only
decreasing order only
heap order (page40)
(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 (page 37)
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 (page34)
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 (page37)
orthogonal
1.The sieve technique works in as follows
phases (page34)
numbers
integers
routines
2.Sorting is one of the few problems where provable bonds exits on
how fast we can sort,
Select correct option:
upper
lower (rep 39)
average
log n
3.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)
log n (rep 37)
n / 2 + n / 44.For the Sieve Technique we take time
Select correct option:
T(nk) (page34)
T(n / 3)
n^2
n/3
5.A (an) is a left-complete binary tree that conforms to the
heap order
Select correct option:
heap (page 40)
binary tree
binary search tree
array
6.For the heap sort we store the tree nodes in
Select correct option:
level-order traversal (rep 40)
in-order
traversal preorder
traversal
post-order traversal
7.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,
Select correct option:
linear
arithmetic
geometric (rep37)
exponent
8.One of the clever aspects of heaps is that they can be stored in arrays
without using any .
Select correct option:
pointers (rep40)
constants
variables
functionsSorting is one of the few problems where provable bonds exits
on how fast we can sort,
Select correct option:
upper
lower (page 39)
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)(page 39)
log n
n / 2 + n / 4
For the Sieve Technique we take time
Select correct option:
T(nk) (page 34
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 (page 40)
binary tree
binary search
tree array
For the heap sort we store the tree nodes in
Select correct option:
level-order traversal (page 40)
in-order traversal
pre-order
traversal postorder
traversalIn the analysis of Selection algorithm, we eliminate a constant fraction of
the array with each phase; we get the convergent series in
the analysis,
Select correct option:
linear
arithmetic
geometric (page 37)
exponent
One of the clever aspects of heaps is that they can be stored in arrays
without using any .
Select correct option:
pointers (page 40)
constants
variables
functions
Analysis of Selection algorithm ends up with,
Select correct option:
T(n) repeat
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,
Select correct option:
arithmetic
geometric
linear (page 39)
orthogonal

 

1
CS502- Fundamentals of Algorithms
Solved MCQS
From Midterm Papers
May- 24 – 2013
MC100401285 Moaaz.pk@gmail.com Mc100401285@vu.edu.pk PSMD01
MIDTERM EXAMINATION
Fall 2011
CS502- Fundamentals of Algorithms
Question No: 1 ( Marks: 1 ) – Please choose one
Due to left complete nature of binary tree, the heap can be stored in
► Arrays (Page 40)
► Structures
► Link Lis
►Stack
Question No: 1 ( Marks: 1 ) – Please choose one
What type of instructions Random Access Machine (RAM) can execute?
►Algebraic and logic
►Geometric and arithmetic
►Arithmetic and logic (Page 10)
►Parallel and recursive
Question No: 1 ( 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 (Page 86)
►We use divide and conquer for sorting only
►We can easily perform it in linear time
►Size of data is not given
Question No: 1 ( Marks: 1 ) – Please choose one
What is the total time to heapify?
► Ο(log n) (Page 43)
► Ο(n log n)
► Ο(n2
log n)
► Ο(log2
n)2
Question No: 1 ( Marks: 1 ) – Please choose one
word Algorithm comes from the name of the muslim author ____________
►Abu Ja’far Mohammad ibn Musa al-Khowarizmi.
Question No: 1 ( Marks: 1 ) – Please choose one
al-Khwarizmi’s work was written in a book titled _______________
►al Kitab al-mukhatasar fi hisab al-jabr wa’l-muqabalah
MIDTERM EXAMINATION
Spring 2010
CS502- Fundamentals of Algorithms
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 (Page 10)

Question No: 2 ( Marks: 1 ) – Please choose one
_______________ is a graphical representation of an algorithm
► notation
► notation
► Flowchart Click here for detail
► 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 (Page 10)
► 100GB

3
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 (Rep)
► Parallel and recursive

Question No: 5 ( Marks: 1 ) – Please choose one
What will be the total number of max comparisons if we run brute-force maxima algorithm with n elements?
►
►
► (Page 14)
►

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) (Page 37)
► O(nlogn)
► O(n
2
)

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(n
3
)
► O(n
2
log n)
► O(n2
)
Question No: 8 ( Marks: 1 ) – Please choose one
What is the total time to heapify?
► Ο(log n) rep
► Ο(n log n)
► Ο(n2
log n)
► Ο(log2
n)

2
n
2
n
n
8 n4
Question No: 9 ( 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: 10 ( Marks: 1 ) – Please choose one
When we call heapify then at each level the comparison performed takes time
► It will take Θ (1) (Page 43)
► Time will vary according to the nature of input data
► It can not be predicted
► It will take Θ (log 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 (Page 40)
► 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 (Page 57)
► No

Question No: 13 ( Marks: 1 ) – Please choose one
If there are Θ (n2
) entries in edit distance matrix then the total running time is
► Θ (1)
► Θ (n2
) Click here for detail
► Θ (n)
► Θ (n log n)
5
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 (Page 86)
► 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 (Page 91)
► NP Complete
► Linear Solution
► Sorting

Question No: 16 ( Marks: 1 ) – Please choose one
Suppose we have three items as shown in the following table, and suppose the capacity of the knapsack is 50
i.e. W = 50.
Item Value Weight
1 60 10
2 100 20
3 120 30
The optimal solution is to pick
► Items 1 and 2
► Items 1 and 3
► Items 2 and 3 (correct)
► None of these6
MIDTERM EXAMINATION
Spring 2010
CS502- Fundamentals of Algorithms
Question No: 1 ( Marks: 1 ) – Please choose one
For the Sieve Technique we take time
► T(nk) (Page 34)
►T(n / 3)
►n^2
►n/3
Question No: 1 ( Marks: 1 ) – Please choose one
Sieve Technique applies to problems where we are interested in finding a single item
from a larger set of _____________
Select correct option:
►n items (Page 34)
►phases
►pointers
►constant
Question No: 1 ( Marks: 1 ) – Please choose one
______________ graphical representation of algorithm.
►asymptotic
►Flowchart (rep)
Question No: 1 ( Marks: 1 ) – Please choose one
who invented the quick sort
►C.A.R. Hoare Click here for detail
Question No: 1 ( Marks: 1 ) – Please choose one
main elements to a divide-and-conquer
►Divide, conquer, combine (Page 27)
Question No: 1 ( Marks: 1 ) – Please choose one
Mergesort is a stable algorithm but not an in-place algorithm.
►True (Page 54)
►false7
Question No: 1 ( Marks: 1 ) – Please choose one
Counting sort the numbers to be sorted are in the range 1 to k where k is small.
►True (Page 57)
►False
MIDTERM EXAMINATION
Spring 2007
CS502- Fundamentals of Algorithms
Question No: 1 ( Marks: 1 ) – Please choose one
Total time for heapify is:
►Ο (log
2
n)
►Ο (n log n)
►Ο (n
2
log n)
►Ο (log n) Rep
Question No: 1 ( Marks: 1 ) – Please choose one
If an algorithm has a complexity of log
2
n + nlog
2
n + n. we could say that it has complexity
►O(n)
►O( n log
2
n)
►O(3)
►O( log
2
( log
2
n ))
►O ( log
2
n)
Question No: 1 ( Marks: 1 ) – Please choose one
In RAM model instructions are executed
►One after another (Page 10)
►Parallel
►Concurrent
►Random 8
Question No: 1 ( Marks: 1 ) – Please choose one
In selection algorithm, because we eliminate a constant fraction of the array with each phase, we get the
►Convergent geometric series (Page 37)
►Divergent geometric series
►None of these
Question No: 1 ( Marks: 1 ) – Please choose one
Due to left-complete nature of binary tree, heaps can be stored in
►Link list
►Structure
►Array (Page 40)
►None of above
CS609- System Programming
Midterm Quizzes (Quiz No.1 & 2)
Quiz No.1 (04 – MAY – 2013)
Question No: 1 ( Marks: 1 ) – Please choose one
The time assumed for each basic operation to execute on RAM model of computation is—–
Infinite
Continuous
Constant (Page 10)
Variable
Question No: 1 ( Marks: 1 ) – Please choose one
If the indices passed to merge sort algorithm are not equal, the algorithm may return immediately.
True
False (Page 28)
Question No: 1 ( Marks: 1 ) – Please choose one
Brute-force algorithm uses no intelligence in pruning out decisions.
True (Page 18)
False9
Question No: 1 ( Marks: 1 ) – Please choose one
In analysis, the Upper Bound means the function grows asymptotically no faster than its largest term.
True (Page 24)
False
Question No: 1 ( Marks: 1 ) – Please choose one
For small values of n, any algorithm is fast enough. Running time does become an issue when n gets large.
True (Page 14)
Fast
Question No: 1 ( Marks: 1 ) – Please choose one
The array to be sorted is not passed as argument to the merge sort algorithm.
True
False
Question No: 1 ( Marks: 1 ) – Please choose one
In simple brute-force algorithm, we give no thought to efficiency.
True (Page 11)
False

Question No: 1 ( Marks: 1 ) – Please choose one
The ancient Roman politicians understood an important principle of good algorithm design that is plan-sweep
algorithm.
True
False (Page 27) [Divide and Conquer]
Question No: 1 ( Marks: 1 ) – Please choose one
In 2d-space a point is said to be ________if it is not dominated by any other point in that space.
Member
Minimal
Maximal (Page 11)
Joint
Question No: 1 ( Marks: 1 ) – Please choose one
An algorithm is a mathematical entity that is dependent on a specific programming language.
True
False (Page 7)10
Question No: 1 ( Marks: 1 ) – Please choose one
The running time of an algorithm would not depend upon the optimization by the compiler but that of an
implementation of the algorithm would depend on it.
True (Page 13)
False
Question No: 1 ( Marks: 1 ) – Please choose one
F (n) and g (n) are asymptotically equivalent. This means that they have essentially the same __________ for
large n.
Results
Variables
Size
Growth rates (Page 23)
Question No: 1 ( Marks: 1 ) – Please choose one
8n2 + 2n – 3 will eventually exceed c2*(n) no matter how large we make c2.
True (Page 25)
False
Question No: 1 ( Marks: 1 ) – Please choose one
If we associate (x, y) integers pair to cars where x is the speed of the car and y is the negation of the price. High
y value for a car means a ________ car.
Fast
Slow
Expensive
Cheap (Page 11)
Question No: 1 ( Marks: 1 ) – Please choose one
The function f(n)= n(logn+1)/2 is asymptotically equivalent to n log n. Here Upper Bound means the function
f(n) grows asymptotically ____________ faster than n log n.
More
Quiet
Not (Page 24)
At least
Question No: 1 ( Marks: 1 ) – Please choose one
After sorting in merge sort algorithm, merging process is invoked.
Select correct option:
True (Page 28)
False 11
Question No: 1 (Marks: 1) – Please choose one
Asymptotic growth rate of the function is taken over_________ case running time.
Select correct option:
Best
Average
Worst (Page 14)
Normal
Question No: 1 (Marks: 1) – Please choose one
In analysis of f (n) =n (n/5) +n-10 log n, f (n) is asymptotically equivalent to ________.
n
2n
n+1
n2 (Page 23)
Question No: 1 (Marks: 1 ) – Please choose one
Algorithm is concerned with…….issues.
Macro
Micro
Both Macro & Micro (Page 8)
Normal
Question No: 1 (Marks: 1) – Please choose one
We cannot make any significant improvement in the running time which is better than that of brute-force
algorithm.
True
False (Page 18)
Question No: 1 ( Marks: 1 ) – Please choose one
In addition to passing in the array itself to Merge Sort algorithm, we will pass in _________other arguments
which are indices.
Two (Page 28)
Three
Four
Five
Question No: 1 ( Marks: 1 ) – Please choose one
Consider the following Algorithm: Fun(n){ if (n=1) return 1 else return (n * Fun(n-1)) } Recurrence for the
above algorithm is:12
nT(n-1)+1
2T(n-1)+1
T(n-1)+cn
T(n-1)+1
Question No: 1 ( Marks: 1 ) – Please choose one
In analysis, the Lower Bound means the function grows asymptotically at least as fast as its largest term.
True (Page 24)
False
Question No: 1 ( Marks: 1 ) – Please choose one
Efficient algorithm requires less computational…….
Memory
Running Time
Memory and Running Time (Page 9)
Energy
Question No: 1 ( Marks: 1 ) – Please choose one
The O-notation is used to state only the asymptotic ________bounds.
Two
Lower
Upper (Page 25)
Both lower & upper
Question No: 1 ( Marks: 1 ) – Please choose one
For the worst-case running time analysis, the nested loop structure containing one “for” and one “while” loop,
might be expressed as a pair of _________nested summations.
1
2 (Page 16)
3
4
Question No: 1 ( Marks: 1 ) – Please choose one
Before sweeping a vertical line in plane sweep approach, in start sorting of the points is done in increasing
order of their _______coordinates.
X (Page 18)
Y
Z
X & Y13
Question No: 1 ( Marks: 1 ) – Please choose one
Brute-force algorithm for 2D-Maxima is operated by comparing ________ pairs of points.
Two
Some
Most
All (Page 18)
Question No: 1 ( Marks: 1 ) – Please choose one
The function f(n)=n(logn+1)/2 is asymptotically equivalent to nlog n. Here Lower Bound means function f(n)
grows asymptotically at ____________ as fast as nlog n.
Normal
Least (Page 23)
Most
All
Question No: 1 ( Marks: 1 ) – Please choose one
The definition of Theta-notation relies on proving ___________asymptotic bound.
One
Lower
Upper
Both lower & upper (Page 25) rep
Question No: 1 ( Marks: 1 ) – Please choose one
In plane sweep approach, a vertical line is swept across the 2d-plane and _______structure is used for holding
the maximal points lying to the left of the sweep line.
Array
Queue
Stack (Page 18)
Tree
Question No: 1 ( Marks: 1 ) – Please choose one
Algorithm analysts know for sure about efficient solutions for NP-complete problems.
Select correct option:
True
False (Page 9)14
Quiz No.1 (2012)
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
The number of nodes in a complete binary tree of height h is
2^(h+1) – 1 (Page 40)
2 * (h+1) – 1
2 * (h+1)
((h+1) ^ 2) – 1
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
The analysis of Selection algorithm shows the total running time is indeed ________in n,
arithmetic
geometric
linear (Page 37)
orthogonal
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
A (an) _________ is a left-complete binary tree that conforms to the heap order
heap (Page 40)
binary tree
binary search tree
array
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Analysis of Selection algorithm ends up with,
T(n) (Page 37)
T(1 / 1 + n)
T(n / 2)
T((n / 2) + n)
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
For the sieve technique we solve the problem,
recursively (Page 34)
mathematically
precisely
accurately15
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
A heap is a left-complete binary tree that conforms to the ___________
increasing order only
decreasing order only
heap order (Page 40)
(log n) order
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
In which order we can sort?
increasing order only
decreasing order only
increasing order or decreasing order (Page 39)
both at the same time
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Divide-and-conquer as breaking the problem into a small number of
pivot
Sieve
smaller sub problems (Page 34)
Selection
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
For the heap sort we store the tree nodes in
level-order traversal (Page 40)
in-order traversal
pre-order traversal
post-order traversal
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
The sieve technique works in ___________ as follows
Phases (Page 34)
numbers
integers
routines16
CS502 – Fundamentals of Algorithms
Quiz No.1 12-11-2012
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
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
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Heaps can be stored in arrays without using any pointers; this is due to the ____________ nature of the binary
tree,
left-complete (Page 40)
right-complete
tree nodes
tree leaves
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Sieve Technique can be applied to selection problem?
True (Page 35)
False
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
In Sieve Technique we do not know which item is of interest
True (Page 34)
False
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
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 (Page 37)
exponent17
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
For the heap sort, access to nodes involves simple _______________ operations.
arithmetic (Page 41)
binary
algebraic
logarithmic
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Slow sorting algorithms run in,
T(n^2) (Page 39)
T(n)
T( log n)
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
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 (Page 37)
n / 2 + n / 4
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
The sieve technique is a special case, where the number of sub problems is just
5
many
1 (Page 34)
few
Question No: 1 of 10 (Marks: 1) – Please choose one
How many elements do we eliminate in each time for the Analysis of Selection algorithm?
(n / 2)+n elements
(n / 2) elements (Page 37)
n / 4 elements
2 n elements
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
One of the clever aspects of heaps is that they can be stored in arrays without using any _______________.
pointers (Page 40)
constants
variables
functions18
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
How much time merge sort takes for an array of numbers?
T(n^2)
T(n)
T( log n)
T(n log n) (Page 40)
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
The reason for introducing Sieve Technique algorithm is that it illustrates a very important special case of,
divide-and-conquer (Page 34)
decrease and conquer
greedy nature
2-dimension Maxima
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
In Sieve Technique we do not know which item is of interest
True (Page 34) rep
False
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Theta asymptotic notation for T (n) :
Set of functions described by: c1g(n)Set of functions described by c1g(n)>=f(n) for c1 s
Theta for T(n)is actually upper and worst case comp (Not sure)
Set of functions described by:
c1g(n)
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Memoization is?
To store previous results for future use
To avoid this unnecessary repetitions by writing down the results of recursive calls and looking them up
again if we need them later (page 74)
To make the process accurate
None of the above
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Which sorting algorithm is faster
O (n log n) Page 26
O n^2
O (n+k)
O n^319
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Quick sort is
Stable & in place
Not stable but in place (Page 54)
Stable but not in place
Some time stable & some times in place
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
One example of in place but not stable algorithm is
Merger Sort
Quick Sort (Page 54)
Continuation Sort
Bubble Sort
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Cont sort is suitable to sort the elements in range 1 to k
K is Large
K is not known
K may be small or large
K is small (Page 57)
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
In place stable sorting algorithm.
If duplicate elements remain in the same relative position after sorting (Page 54)
One array is used
More than one arrays are required
Duplicating elements not handled
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Which may be a stable sort?
Merger
Insertion (Page 54)
Both above
None of the above
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
An in place sorting algorithm is one that uses ___ arrays for storage
Two dimensional arrays
More than one array
No Additional Array (Page 54)
None of the above20
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Sieve Technique applies to problems where we are interested in finding a single item from a larger set of
_____________
n items (Page 34)
phases
pointers
constant
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Sorting is one of the few problems where provable ________ bonds exits on how fast we can sort,
upper
lower (Page 39)
average
log n
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Counting sort has time complexity:
O(n) (Page 58)
O(n+k)
O(k)
O(nlogn)
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
The running time of quick sort depends heavily on the selection of
No of inputs
Arrangement of elements in array
Size o elements
Pivot elements (Page 49)
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Which may be stable sort:
Bubble sort
Insertion sort
Both of above (Page 54)21
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
One Example of in place but not stable sort is
Quick (Page 54)
Heap
Merge
Bubble
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
In Quick Sort Constants hidden in T(n log n) are
Large
Medium
Small Click here for detail
Not Known
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Quick sort is based on divide and conquer paradigm; we divide the problem on base of pivot element and:
There is explicit combine process as well to conquer the solution.
No work is needed to combine the sub-arrays, the array is already sorted
Merging the sub arrays
None of above. (Page 51)
Ref: – random choices for the pivot element and each choice have an equal probability of 1/n of occurring. So
we can modify the above recurrence to compute an average rather than a max22
CS501 – Quiz No.2 (Spring 2013)
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
A point p in 2-dimensional space is usually given by its integer coordinate(s)____________
p.x only
p.y only
p.x & p.z
p.x & p.y (Page 10)
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
In ____________ we have to find rank of an element from given input.
Merge sort algorithm
Selection problem (Page 34)
Brute force technique
Plane Sweep algorithm
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
In Heap Sort algorithm, if heap property is violated _________
We call Build heap procedure
We call Heapify procedure
We ignore
Heap property can never be violated
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Upper bound requires that there exist positive constants c2 and n0 such that f(n) ____ c2n for all n <= n0(ye
question ghalat lag raha hai mujhae
Less than
Equal to or Less than (Page 25)
Equal or Greater than
Greater than
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
A RAM is an idealized algorithm with takes an infinitely large random-access memory.
True
False (Page 10)23
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
_________ is one of the few problems, where provable lower bounds exist on how fast we can sort.
Searching
Sorting (Page )
Both Searching & Sorting
Graphing
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Floor and ceiling are ____________ to calculate while analyzing algorithms.
Very easy
Usually considered difficult (Page 31)
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
In Heap Sort algorithm, the maximum levels an element can move upward is _________
Theta (log n) (Page 43)
Order (log n)
Omega (log n)
O (1) i.e. Constant time
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
A point p in 2-dimensional space is usually given by its integer coordinate(s)____________
p.x only p.y
only p.x & p.z
p.x & p.y (Page 17)
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
In Heap Sort algorithm, the total running time for Heapify procedure is ____________
Theta (log n) (Page 43)
Order (log n)
Omega (log n)
O (1) i.e. Constant time
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Algorithm is a mathematical entity, which is independent of a specific machine and operating system.
True
False (Page 7)24
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
While Sorting, the ordered domain means for any two input elements x and y _________ satisfies only.
x < y
x > y
x = y
All of the above (Page 39)
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Quick sort is best from the perspective of Locality of reference.
True (Page 9)
False
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Sorting can be in _________
Increasing order only
Decreasing order only
Both Increasing and Decreasing order (Page 39)
Random order
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
In Heap Sort algorithm, we build _______ for ascending sort.
Max heap (Page 41)
Min heap
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
In Sieve Technique, we know the item of interest.
True
False (Page 34)
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
While solving Selection problem, in Sieve technique we partition input data __________
In increasing order
In decreasing order
According to Pivot (Page 35)
Randomly25
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
In pseudo code, the level of details depends on intended audience of the algorithm.
True (Page 12)
False
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
The sieve technique works where we have to find _________ item(s) from a large input.
Single (Page 34)
Two
Three
Similar
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
If the indices passed to merge sort algorithm are ________,then this means that there is only one element to
sort.
Small
Large
Equal (Page 28)
Not Equal

 

Comments at pak.nchd@gmail.com || Back to TOP || BETA File Version v 2.2.1 published for Midterm only
CS502-Funda. Of Algorithm by M Ishfaq Pg No.1
CS502 – Fundamentals of Algorithms
File Version Update: (Dated: 28-Nov-2011)
 MCQs GIGA File (Done)
 My Composed MCQs from Lecture 1_to12 Included
 Someone Collection of MCQz from Lecture 1 to 22 Also
included in this file.
THIS FILE IS SHARED IN
BETA MEAN THAT ONLY
MCQS COLLECTION IS
SHARED WITH YOU ALL.
Final Version of File is in Progress and will be shared as soon as it
get completed.
KEEP
SHARING
Disclaimer: There might be some human errors, if you find please let me know at
pak.nchd@gmail.com , duplication of data may be possible but at least
possible level.Comments at pak.nchd@gmail.com || Back to TOP || BETA File Version v 2.2.1 published for Midterm only
CS502-Funda. Of Algorithm by M Ishfaq Pg No.2
Current paper of Cs502 Fall 2011
28 november 2011
Shared by Anum Arshed (Thanks to her)
Mcqs past paper men say koi aik 2 hi tha bs
20 MCQs most about running time and worst case time of algorithms.
1. Worst case for edit distance algorithm? What is the simple
change that can change the worst case time ? 5 marks
2. Write Pseudo code for KNAPSACK algorithm? 5 marks
3. Spelling correction in edit distance? 3 marks
4. Differentiate b/w Bubble sort, insertion sort and selection sort?
3 marks
5. Average case and worst case time for quick sort? 2 marks
Another Paper,
1. Suggest and describe modifications of the implementation of quick
sort that will improve its performance. (05 marks)
2. Complete given cost table. (05 marks)
3. Why do we analyze the average case performance of a randomized
algorithm and not its worse case performance. (03 marks)
4. Why value in row of a dynamic programming table of knapsack is
always non-decreasing? (03 marks)
5. How we build heap? (02 marks)
6. Find cost of (A1(A2A3)). (02 marks)
THANKS TO THESE WHO SHARED AND SHARING NOWComments at pak.nchd@gmail.com || Back to TOP || BETA File Version v 2.2.1 published for Midterm only
CS502-Funda. Of Algorithm by M Ishfaq Pg No.3
Table of Content
FILE VERSION UPDATE: (DATED: 30-NOV-2011)………………………………………………………………………………………………………. 1
CURRENT PAPER OF CS502 FALL 2011………………………………………………………………………………………………………………………… 2
THANKS TO THISE WHO SHARED AND SHARING NOW ………………………………………………………………………………………………… 2
TABLE OF CONTENT ………………………………………………………………………………………………………………………………………………… 3
MCQZ …………………………………………………………………………………………………………………………………………………………………… 4
MCQZ (SET-1) FROM LECTURE 1 TO 12 …………………………………………………………………………………………………………………………. 4
MCQZ (SET-2) LECTURE WISE MCQS …………………………………………………………………………………………………………………………… 25
MCQZ (SET-3)…………………………………………………………………………………………………………………………………………………….. 35
MCQZ (SET-4)…………………………………………………………………………………………………………………………………………………….. 36
MCQZ (SET-5)…………………………………………………………………………………………………………………………………………………….. 37
MCQZ (SET-6)…………………………………………………………………………………………………………………………………………………….. 38
MCQZ (SET-7)…………………………………………………………………………………………………………………………………………………….. 39
MCQZ (SET-8)…………………………………………………………………………………………………………………………………………………….. 41
MCQZ (SET-9)…………………………………………………………………………………………………………………………………………………….. 42
MCQZ (SET-10) …………………………………………………………………………………………………………………………………………………… 44
MCQZ (SET-11) …………………………………………………………………………………………………………………………………………………… 46
MCQZ (SET-12) …………………………………………………………………………………………………………………………………………………… 47
MCQZ (SET-13) …………………………………………………………………………………………………………………………………………………… 51
MCQZ (SET-14) …………………………………………………………………………………………………………………………………………………… 53
MCQZ (SET-15) …………………………………………………………………………………………………………………………………………………… 55
MCQZ (SET-16) …………………………………………………………………………………………………………………………………………………… 56
MCQZ (SET-17) …………………………………………………………………………………………………………………………………………………… 57
MCQZ (SET-18) …………………………………………………………………………………………………………………………………………………… 60
MCQZ (SET-19) …………………………………………………………………………………………………………………………………………………… 62
MCQZ (SET-20) …………………………………………………………………………………………………………………………………………………… 64
MCQZ (SET-21) …………………………………………………………………………………………………………………………………………………… 67
MCQZ (SET-22) …………………………………………………………………………………………………………………………………………………… 68
MCQZ (SET-23) …………………………………………………………………………………………………………………………………………………… 70
MCQZ (SET-24) …………………………………………………………………………………………………………………………………………………… 72
MCQZ (SET-26) FROM 2004 PAPER …………………………………………………………………………………………………………………………… 73
MCQZ (SET-27) FROM 2004 PAPER…………………………………………………………………………………………………………………………… 75
MCQZ (SET-28) FROM 2007 PAPER …………………………………………………………………………………………………………………………… 76
=========================================================>=======Comments at pak.nchd@gmail.com || Back to TOP || BETA File Version v 2.2.1 published for Midterm only
CS502-Funda. Of Algorithm by M Ishfaq Pg No.4
MCQz
MCQz (Set-1) From Lecture 1 to 12
This is my Own Compilation from Handouts………(Author: Muhammad Ishfaq)
Questions
Question No: 1 The word Algorithm comes from the name of the muslim author
________________
A. Ibne-ul Hasem
B. Abu Ja’far Mohammad ibn Musa alKhowarizmi
C. Jaber Bin Hayan
D. None
Correct Option : B
Question No: 2 Abu Ja’far Mohammad ibn Musa al-Khowarizmi was born in
the eighth century at Khwarizm (Kheva), in_______________
A. Iraq
B. Uzbekistan
C. Turkey
Correct Option : B
Question No: 3 Al-Khwarizmi died _________ C.E.___
A. around 900
B. around 700
C. around 840
Correct Option : C
Question No: 4 Al-Khwarizmi’s work was written in a book titled al Kitab almukhatasar
fi hisab al-jabr wa’l-muqabalah (The Compendious
Book on Calculation by Completion and Balancing)___
A. True
. False
Correct Option : A
Question No: 5 An _________ is thus a sequence of computational steps that
transform the input into output.___
A. Data Structure
B. Data ProcessComments at pak.nchd@gmail.com || Back to TOP || BETA File Version v 2.2.1 published for Midterm only
CS502-Funda. Of Algorithm by M Ishfaq Pg No.5
C. Algorithm
D. none
Correct Option : C
Question No: 6 Like a program, an algorithm is a mathematical entity, which is
not independent of a specific programming language, machine,
or compiler.___
A. True
B. False
Correct Option : B
Question No: 7 ________ of the courses in the computer science program deal
with efficient algorithms and data structures,___
A. None
B. Many
C. Some
Correct Option : B
Question No: 8 Compilers, operating systems, databases, artificial intelligence,
computer graphics and vision, etc. use algorithm.____________
A. False
B. True
Correct Option : B
Question No: 9 This course will consist of following major section(s). Select
Correct Option
1.The first is on the mathematical tools necessary for the
analysis of algorithms. This will focus on asymptotics,
summations, recurrences.
2- The second element will deal with one particularly important
algorithmic problem: sorting a list of numbers.
3-The third of the course will deal with a collection of various
algorithmic problems and solution techniques.
4- Finally we will close this last third with a very brief
introduction to the theory of NP-completeness.
A. 1-2
B. 1-2-3
C. 1-3-4Comments at pak.nchd@gmail.com || Back to TOP || BETA File Version v 2.2.1 published for Midterm only
CS502-Funda. Of Algorithm by M Ishfaq Pg No.6
D. All
Correct Option : D
Question No: 10 NP-complete problem are those for which ______ algorithms are
known, but no one knows for sure whether efficient solutions
might exist___
A. efficient
B. no efficient
C. none
Correct Option : B
Question No: 11 Analyzig algorithms in terms of the amount of computational
resources that the algorithm requires. These resources include
mostly ______________
A. running time
B. memory
C. running time and memory
D. none
Correct Option : C
Question No: 12 Ideally this model should be a reasonable abstraction of a
standard generic single-processor machine. We call this model
a _____.
A. RAM Memory
B. ROM Memory
C. random access machine or RAM
Correct Option : C
Question No: 13 A RAM is an idealized machine with___
A. an infinitely large random-access memory.
B. with Instructions are executed one-by-one
(there is no parallelism)
C. single processor machine
D. all
Correct Option : D
Question No: 14 We assume that in RAM machine , each basic operation takes
the ________ constant time to execut.
A. sameComments at pak.nchd@gmail.com || Back to TOP || BETA File Version v 2.2.1 published for Midterm only
CS502-Funda. Of Algorithm by M Ishfaq Pg No.7
B. different
Correct Option : A
Question No: 15 A point p in 2-dimensional space be given by its integer
coordinates, p = (p.x, p.y).___
A. true
B. false
Correct Option : A
Question No: 16 A point p is not said to be dominated by point q if q.x ≤ p.x and
q.y ≤ p.y.___
A. true
B. false
Correct Option : A
Question No: 17 Given a set of n points, P = {p1, p2, . . . , pn} in 2-space a point
is said to be _________ if it is not dominated by any other point
in P.
A. maximal
B. mininal
C. average
Correct Option : A
Question No: 18 Brute-force algorithm is defined as ,It is a very general problemsolving
technique that consists of systematically enumerating
all possible candidates for the solution and checking whether
each candidate satisfies the problem’s statement.s
___
A. false
B. true
Correct Option : B
Question No: 19 There are no formal rules to the syntax of the pseudo code.___
A. true
B. false
Correct Option : A
Question No: 20 From the figure select the correct statement.___Comments at pak.nchd@gmail.com || Back to TOP || BETA File Version v 2.2.1 published for Midterm only
CS502-Funda. Of Algorithm by M Ishfaq Pg No.8
A. Point (4,11) dominate (7, 7)
B. Point (7,13) dominate (9.10)
C. Point (7,13) dominate (7, 7)
D. Point (13,3) dominate (9,10)
Correct Option : C
Question No: 21 Worst-case time is the maximum running time over all (legal)
inputs of size n is given in figure where I denote an input
instance, let |I| denote its length, and let T(I) denote the
running time of the algorithm on input I.___
A. false
B. true
Correct Option : B
Question No: 22 ______________ is the average running time over all inputs of
size n. Let p(I) denote the probability of seeing this input. The
average-case time is the weighted sum of running times with
weights.___
A. Worst-case time
B. Average-case time
C. none
Correct Option : B
Question No: 23 When n is large, n^2 term will be much larger than the n term
and will dominate the running time.___
A. true
B. falseComments at pak.nchd@gmail.com || Back to TOP || BETA File Version v 2.2.1 published for Midterm only
CS502-Funda. Of Algorithm by M Ishfaq Pg No.9
Correct Option : A
Question No: 24 We will say that the worst-case running time is Θ(n^2). This is
called _________________
A. the asymptotic growth rate of the function.
B. itteration growth rate of the function.
C. recursive growth rate of the function.
D. none
Correct Option : A
Question No: 25 Given a finite sequence of values a1, a2, . . . , an, their sum a1
+ a2 + . . . + an is expressed in
summation notation as (click figure to see)___
A. true
B. false
Correct Option : A
Question No: 26 If c is a constant then (see figure..)___
A true
B. false
Correct Option : A
Question No: 27 Formule in figure is___
A. correct
B. wrong
Correct Option : A
Question No: 28 Figure shows ___
A. Arithmetic seriesComments at pak.nchd@gmail.com || Back to TOP || BETA File Version v 2.2.1 published for Midterm only
CS502-Funda. Of Algorithm by M Ishfaq Pg No.10
B. HArmonic series
C. Geometric series
D. none
Correct Option : A
Question No: 29 Figure shows,___
A. Arithmatic series
B. Quadratic series
C. Harmonic series
D. Geometric series
Correct Option : B
Question No: 30 Figure shows …….. and If 0 < x < 1 then this is Θ(1), and if x >
1, then this is Θ(x^n).___
A. Quadratic series
B. Arithmatic series
C. Geometric series
D. Harmonic series
Correct Option : C
Question No: 31 For n ≥ 0 , figure shows …___
A. Geometric series
B. Quadratic series
C. Arithmetic series
D. Harmonic series
Correct Option : D
Question No: 32 We write out the loops as summations and then solve the Comments at pak.nchd@gmail.com || Back to TOP || BETA File Version v 2.2.1 published for Midterm only
CS502-Funda. Of Algorithm by M Ishfaq Pg No.11
summations. ___
A. true
B. false
Correct Option : A
Question No: 33 A point p is said to dominated by point q if p.x ≤ q.x and p.y ≤
q.y___
A. true
B. false
Correct Option : A
Question No: 34 We introduced a brute-force algorithm that ran in _________
A. Θ(n) time
B. Θ(n^2) time
C. Θ(nlogn) time
D. Θ(n^3) time
Correct Option : B
Question No: 35 The problem with the brute-force algorithm is that it uses
________ in pruning out decisions.___
A. intelligence
B. no intelligence
Correct Option : B
Question No: 36 This follows from the fact that dominance relation is
____________
A. symmetric.
B. transitive.
C. non-transitive.
Correct Option : B
Question No: 37 This approach of solving geometric problems by sweeping a line
across the plane is called ___________
A. plane sweep.
B. brute force.
Correct Option : A
Question No: 38 Sorting takes ___________ time.___
A. Θ(n)Comments at pak.nchd@gmail.com || Back to TOP || BETA File Version v 2.2.1 published for Midterm only
CS502-Funda. Of Algorithm by M Ishfaq Pg No.12
B. Θ(n^2)
C. Θ(n log n)
D. none
Correct Option : C
Question No: 39 Plane-sweep Algorithm, the inner while-loop _______ execute
more than n times over the entire course of the algorithm.___
A. can
B. cannot
Correct Option : B
Question No: 40 The runtime of entire plane-sweep algorithm is Θ(n log n)___
A. true
B. false
Correct Option : A
Question No: 41 For n = 1, 000, 000, if plane-sweep takes 1 second, the bruteforce
will take about ___
A. 14 hours
B. 14 minutes
Correct Option : A
Question No: 42 If n is not very large, then almost any algorithm _____ be
fast.___
A. may
B. may be not
C. will
D. none
Correct Option : C
Question No: 43 Given any function g(n), we define Θ(g(n)) to be a set of
functions that asymptotically equivalent to g(n). Formally:___
A. true
B. false
Correct Option : AComments at pak.nchd@gmail.com || Back to TOP || BETA File Version v 2.2.1 published for Midterm only
CS502-Funda. Of Algorithm by M Ishfaq Pg No.13
Question No: 44 This is written as “f(n) E Θ(g(n))” That is, f(n) and g(n) are
asymptotically equivalent. This means that they have
essentially the _______ growth rates for large n. ___
A. different
B. same
Correct Option : B
Question No: 45 All given function are all asymptotically equivalent. As n
becomes large, the dominant (fastest growing) term is some
constant times n^2.___
A. true
B. false
Correct Option : A
Question No: 46 Lower bound f(n) = 8n2 + 2n − 3 grows asymptotically at least
as fast as n^2,___
A. true
B. false
Correct Option : A
Question No: 47 Upper bound f(n) grows no faster asymptotically than n^2,___
A. true
B. false
Correct Option : A
Question No: 48 Figure does not show Asymptotic Notation Example___
A. true
B. false
Correct Option : B
Question No: 49 The ____________ is used to state only the asymptotic upper
bounds.___Comments at pak.nchd@gmail.com || Back to TOP || BETA File Version v 2.2.1 published for Midterm only
CS502-Funda. Of Algorithm by M Ishfaq Pg No.14
A. theta notation
B. O-notation
C. Ω-notation
Correct Option : B
Question No: 50 The ________allows us to state only the asymptotic lower
bounds.___
A. Ω-notation
B. O-notation
Correct Option : A
Question No: 51 The three notations:
___
A. true
B. false
Correct Option : A
Question No: 52 Limit rule for Θ-notation:___
A. true
B. false
Correct Option : A
Question No: 53 The limit rule for O-notation is ___
A. true
B. false
Correct Option : A
Question No: 54 limit rule for Ω-notation:___Comments at pak.nchd@gmail.com || Back to TOP || BETA File Version v 2.2.1 published for Midterm only
CS502-Funda. Of Algorithm by M Ishfaq Pg No.15
A. true
B. false
Correct Option : A
Question No: 55 Here is a list of common asymptotic running times:
• Θ(1): Constant time; can’t beat it!
• Θ(log n): Inserting into a balanced binary tree; time to find an
item in a sorted array of length n using binary search.
• Θ(n): About the fastest that an algorithm can run.
• Θ(n log n): Best sorting algorithms.
• Θ(n2), Θ(n3): Polynomial time. These running times are
acceptable when the exponent of n is small or n is not to large,
e.g., n ≤ 1000.
• Θ(2n), Θ(3n): Exponential time. Acceptable only if n is small,
e.g., n ≤ 50.
• Θ(n!), Θ(nn): Acceptable only for really small n, e.g. n ≤ 20___
A. true
B. false
Correct Option : A
Question No: 56 Ancient Roman politicians followed an important principle of
good algorithm design known as Divide and Conquer
Strategy.___
A. true
B. false
Correct Option : A
Question No: 57 The main elements to a divide-and-conquer solution are___
A. Divide: the problem into a small number of
pieces
B. Conquer: solve each piece by applying divide
and conquer to it recursively
C. Combine: the pieces together into a global
solution
D. All of the above.
Correct Option : D
Question No: 58 The merge sort algorithm works by ________
A. (Divide:) split A down the middle into two
subsequences, each of size roughly n/2Comments at pak.nchd@gmail.com || Back to TOP || BETA File Version v 2.2.1 published for Midterm only
CS502-Funda. Of Algorithm by M Ishfaq Pg No.16
B. (Conquer:) sort each subsequence by calling
merge sort recursively on each.
C. (Combine:) merge the two sorted subsequences
into a single sorted list.
D. All of the above.
Correct Option : D
Question No: 59 MERGE-SORT( array A, int p, int r)
1 if (p < r)
2 then
3 q ← (p + r)/2
4 MERGE-SORT(A, p, q) // sort A[p..q]
5 MERGE-SORT(A, q + 1, r) // sort A[q + 1..r]
6 MERGE(A, p, q, r) // merge the two pieces___
A. true
B. false
Correct Option : A
Question No: 60 The iteration method does not turn the recurrence into a
summation___
A. false
B. true
Correct Option : A
Question No: 61 Define the ______ of an element to be one plus the number of
elements that are smaller. ___
A. Rank
B. Degree
Correct Option : A
Question No: 62 Thus, the rank of an element is its final position if the set is
A. sorted.
B. unsorted.
C. unchanged.
D. same
Correct Option : A
Question No: 63 The minimum is of rank ____ and the maximum is of rank Comments at pak.nchd@gmail.com || Back to TOP || BETA File Version v 2.2.1 published for Midterm only
CS502-Funda. Of Algorithm by M Ishfaq Pg No.17
___.___
A. 0 , 1
B. 0 , n
C. 1 , n
D. none
Correct Option : C
Question No: 64 Test___
A. Choice 1
B. Choice 2
C. Choice 3
D. None
Correct Option : D
Question No: 65 Floor and ceilings ________ a pain to deal with.___
A. are not
B. are
C. sometime
D. none
Correct Option : B
Question No: 66 Iteration _______ powerful technique for solving recurrences___
A. is a not a
B. might be
C. is a very
Correct Option : C
Question No: 67 Merge of two lists of size m/2 to a list of size m takes Θ(m) time,
which we will just write as m.___
A. True
B. False
Correct Option : A
Question No: 68 The figure is a___Comments at pak.nchd@gmail.com || Back to TOP || BETA File Version v 2.2.1 published for Midterm only
CS502-Funda. Of Algorithm by M Ishfaq Pg No.18
A. Selection sort Recurrence Tree
B. Merge sort Recurrence Tree
C. Both
D. None
Correct Option : A
Question No: 69 Define the ______ of an element to be one plus the number of
elements that are smaller.___
A. degree
B. rank
C. frequency
D. weight
Correct Option : B
Question No: 70 The rank of an element is its final position if the set is sorted___
A. true
B. false
Correct Option : A
Question No: 71 Consider the set: {5, 7, 2, 10, 8, 15, 21, 37, 41}. The rank of
each number is its position in the sorted order.
For example, rank of 8 is ______ , one plus the number of
elements ________ 8 which is 3___
A. 3 , equal to
B. 4 , greater then
C. 3 , smaller then
D. 4 , smaller thenComments at pak.nchd@gmail.com || Back to TOP || BETA File Version v 2.2.1 published for Midterm only
CS502-Funda. Of Algorithm by M Ishfaq Pg No.19
Correct Option : D
Question No: 72 Given a set A of n distinct numbers and an integer k, 1 ≤ k ≤ n,
output the element of A of rank k.This problem is of type
______________
A. Merge Sort
B. Selection Sort
C. Maximal
Correct Option : B
Question No: 73 If n is odd then the median is defined to be element of rank
______.___
A. n
B. n-1
C. (n+1)/2
D. n/2
Correct Option : C
Question No: 74 When n is even, for median , there are two choices: ___
A. n/2
B. (n + 1)/2
C. n/2 and (n + 1)/2.
D. none
Correct Option : C
Question No: 75 Medians are useful as a measures of the ____________ of a set
A. mode
B. average
C. probability
D. central tendency
Correct Option : D
Question No: 76 Central tendency of a set is useful when the distribution of
values is __________.___
A. skewed
B. not skewed
C. highly skewedComments at pak.nchd@gmail.com || Back to TOP || BETA File Version v 2.2.1 published for Midterm only
CS502-Funda. Of Algorithm by M Ishfaq Pg No.20
D. straight
Correct Option : C
Question No: 77 The median income in a community is a more meaningful
measure than average. Suppose 7 households have monthly
incomes 5000, 7000, 2000, 10000, 8000, 15000 and 16000. In
sorted order, the incomes are 2000, 5000, 7000, 8000, 10000,
15000, 16000. The median income is 8000; median is element
with rank 4: (7 + 1)/2 = 4. The average income is 9000.
Suppose the income 16000 goes up to 450,000. The median is
still 8000 but the average goes up to 71,000. Clearly, the
average is not a good representative of the majority income
levels.___
A. Above statement is true
B. Above statement is false
Correct Option : A
Question No: 78 Sorting requires _________ time___
A. Θ(log n)
B. Θ(n*2 log n)
C. Θ(n log n)
D. Θ(n)
Correct Option : C
Question No: 79 In particular, is it possible to solve the selections problem in
Θ(n) time?___
A. no.
B. yes.
C. yes. However, the solution is far from obvious
Correct Option : C
Question No: 80 A very important special case of divide-and-conquer, which I
call the sieve technique.___
A. false
B. true
Correct Option : B
Question No: 81 We think of divide-and-conquer as breaking the problem into a
small number of bigger sub-problems, which are then solved
recursively.___
A. trueComments at pak.nchd@gmail.com || Back to TOP || BETA File Version v 2.2.1 published for Midterm only
CS502-Funda. Of Algorithm by M Ishfaq Pg No.21
B. false
Correct Option : A
Question No: 82 The sieve technique is a special case, where the number of subproblems
is _____ .___
A. 3
B. 2
C. just 1
D. 0
Correct Option : C
Question No: 83 In particular “large enough” means that the number of items is
at least some fixed constant fraction of n (e.g. n/2, n/3). ___
A. true
B. false
Correct Option : A
Question No: 84 The following figure shows a partitioned array:___
A. true
B. false
Correct Option : A
Question No: 85 Sieve example: select 6th smallest element is shown in fig___
A. true
B. false
Correct Option : A
Question No: 86 Ideally, x (pivot) should have a rank that is neither too large or
too small.___
A. true
B. falseComments at pak.nchd@gmail.com || Back to TOP || BETA File Version v 2.2.1 published for Midterm only
CS502-Funda. Of Algorithm by M Ishfaq Pg No.22
Correct Option : A
Question No: 87 In sorting, we are given an array A[1..n] of n numbers We are to
reorder these elements into increasing (or decreasing) order.___
A. false
B. true
Correct Option : B
Question No: 88 More generally, A is an array of objects and we sort them based
on one of the attributes – the key value.___
A. true
B. false
Correct Option : A
Question No: 89 There are a number of well-known _________ O(n^2) sorting
algorithms.___
A. fast
B. slow
Correct Option : B
Question No: 90 Scan the array. Whenever two consecutive items are found that
are out of order, swap them. Repeat until all consecutive items
are in order. It is called ______________
A. Insertion sort
B. Bubble sort
C. Selection sort
D. none
Correct Option : B
Question No: 91 Assume that A[1..i − 1] have already been sorted. Insert A[i] into
its proper position in this sub array. Create this position by
shifting all larger elements to the right.It is called
________________
A. Bubble sort
B. Selection sort
C. Merge sort
D. none
Correct Option : D
Question No: 92 Assume that A[1..i − 1] contain the i − 1 smallest elements in
sorted order. Find the smallest element in A[i..n] Swap it with Comments at pak.nchd@gmail.com || Back to TOP || BETA File Version v 2.2.1 published for Midterm only
CS502-Funda. Of Algorithm by M Ishfaq Pg No.23
A[i].It is called _____________
A. Selection sort
B. Insertion sort
C. Merge sort
D. Bubble sort
Correct Option : A
Question No: 93 Assume that A[1..i − 1] have already been sorted. Insert A[i] into
its proper position in this sub array. Create this position by
shifting all larger elements to the right.___
A. Selection sort
B. Bubble sort
C. Merge sort
D. Insertion sort
Correct Option : D
Question No: 94 In the worst case time _________ run in Θ(n2)___
A. Bubble sort
B. Selection sort
C. Insertion sort
D. All of the above
Correct Option : D
Question No: 95 A __________ is a left-complete binary tree that conforms to the
heap order.___
A. BST
B. AVL Tree
C. Perfect tree
D. Heap
Correct Option : D
Question No: 96 The heap order property stated that in a ___________ , for every
node X, the key in the parent is smaller than or equal to the
key in X.___
A. (max) heap
B. (min) heapComments at pak.nchd@gmail.com || Back to TOP || BETA File Version v 2.2.1 published for Midterm only
CS502-Funda. Of Algorithm by M Ishfaq Pg No.24
Correct Option : B
Question No: 97 In a _______ heap, the parent has a key larger than or equal
both of its children ___
A. (max) heap
B. (min) heap
Correct Option : A
Question No: 98 Thus the smallest key is in the root in a_________ ;
in the _________the largest is in the root.___
A. max heap, min heap
B. min heap , max heap
C. max heap , max heap
D. min heap , min heap
Correct Option : B
Question No: 99 The number of nodes in a complete binary tree of height h is___
A. true
B. false
Correct Option : A
Question No: 100 h in terms of n is___
A. true
B. false
Correct Option : A
Question No: 101 One of the clever aspects of ________ is that they can be stored
in arrays without using any pointers___
A. lists
B. BST trees
C. heaps
Correct Option : C
Question No: 102 We store the tree nodes in level-order traversal in heap sort___
A. trueComments at pak.nchd@gmail.com || Back to TOP || BETA File Version v 2.2.1 published for Midterm only
CS502-Funda. Of Algorithm by M Ishfaq Pg No.25
B. false
Correct Option : A
Question No: 103 Access to nodes involves simple arithmetic operations:shown in
below
left(i) : returns 2i, index of left child of node i.
right(i) : returns 2i + 1, the right child.
parent(i) : returns bi/2c, the parent of i.___
A. false
B. true
Correct Option : B
Question No: 104 The root is at position 1 of the array.___
A. true
B. false
Correct Option : A
Question No: 105 There is one principal operation for maintaining the heap
property.___
A. Heapify Procedure
B. none
Correct Option : A
Question No: 106 It is called Heapify. (In other books it is sometimes called sifting
down.) ___
A. true
B. false
Correct Option : A

The sequence of merge sort algorithm is:

• Divide Combine-Conquer

• Conquer-Divide-Combine

• c. Divide-Conquer-Combine             Page 27

• Combine-Divide-Conquer

 In ______ Knapsack Problem, limitation is that an item can either be put in the bag or not. Fractional items are not allowed.

• 0

• 1

• 0/1                                                                                Page 91

• Fractional

 In Selection algorithm, we assume pivot selection takes theta _______ running time.

• a. n                                                                     Page – 36

• n2

• n3

• log (n)

 In Heap Sort algorithm (using max heap), when every time maximum elements removed from top ________.

• We call merge Sort Algorithm

• it becomes Order n2 Algorithm

• Divide and Conquer strategy helps us

• d. We are left with a hole                      Page – 41

 If matrix A of dimension p x q is multiply with matrix B of dimension q x r, then each entry in resultant matrix takes _______ time.

• a. O (q)                                                                          Page – 84

• O (1)

• O (p x q)

• O (q x r)

 _________ is a method of solving a problem in which we check all possible solutions to the problem to find the solution we need.

• Plane-Sweep Algorithm

• Sorting Algorithm

• c. Brute-Force Algorithm                      google

• Greedy approach

 The worst case running time of Quick sort algorithm _____.

• Cannot be quadratic

• b. Is quadratic    

• ls always Exponential

• Is linear

 In max heap (for Heap Sort algorithm), when every time maximum element is removed from top we replace it with _____ leaf in the tree.

• second last

• b. Last                                                                           Page -41

• First

• Any

 Quick sort algorithm was developed by –

• AlferdAho

• Sedgewick

• John Vincent Atanasoff

• d. Tony Hoare                                                     – Google wikipedia

 If Matrix-A has dimensions “3×2” and Matrix-B has dimensions “2×3”, then multiplication of Matrix-A and Matrix-B will result a new Matrix-C having dimensions.

• 3×2

• 2×3

• 2×2

• d. 3×3            

 For comparison-based sorting algorithms, it is possible to sort more efficiently than Omega n log(n) time.

• Always

• ·        Sometimes not
• NOT           Pg 54
• Sometimes

 Dynamic Programming approach is usually useful in solving optimization problems.

• True                                 

• False

 In Sorting the key value or attribute_____ from an ordered domain.

• Must be                        page 39

• Not always

• May be

• Occasionally

 Result of asymptotical analysis of n(n -3) and 4n*n is that _______

• n(n-1) is asymptotically Less

• n(n-1) is asymptotically Greater

• Both are asymptotically Not equivalent

• Both are asymptotically Equivalent       page 23  (4n*n= 4n2)

 Floor and ceiling are ______ to calculate while analyzing algorithms

• Very easy

• 3rd Option is missing
  • Usually considered difficult

• 4th Option is missing

 _____ of reference is an important fact of current processor technology.

• Defining

• Assigning
  • Locality   pg-8

• Formality

 In max-heap, largest element is stored at root node. Where is the smallest element stored?

• Right Node

• Leaf Node           Not sure

• Middle Node

• Left Node

 In average-case time analysis of Quick sort algorithm, the most balanced case for partition is when we divide the list of elements into _.

• Equal no. of pieces as of input elements

• Single piece exactly

• Two nearly equal pieces

• Three nearly equal pieces

 Which of the following is calculated with Big O notation?

• Medium bounds

• Upper bounds                                    Page – 25

• Lower bounds

• Both upper and lower bounds

 Edit distance algorithm based on ________ strategy

• Greedy

•  Dynamic Programming                         Page – 81

• Divide and Conquer

• Searching

 In Heapsort Algorithm, total time taken by heapify procedure is ________

• O (log n)                                                                      Page-43

• O (log2 n)

• O (n log n)

• O (n2 log n)

 Al-Khwarizmi was a/an _______

• Artist

• Astronomer
  • Mathematication p-7

• Khalifah

 When matrix A of 5x3is multiply with metric B of 3×4 then the number of multiplication required is: Not found exactly

• 15

• 12

• 36

• 60     Not Found exactly but as per formula at page 84,

 Pseudo code of algorithms are to be read by _______.

• People                                                          Page -12

• RAM

• Computer

• Compiler

 The sieve technique is a special case, where the number of sub-problems is Just

_________

•  1                                                                          P-34

• 2

• 3

• 4

When a recursive algorithm revisits the same problem over and over again, we say that the optimization problem has ________ sub-problems.

• Overlapping                          – Google Search

• Over costing

• Optimized

• Three

Sieve technique is very important special case of Divide-and-Conquer strategy.

• False
  • True

In order to say anything meaningful about our algorithms, it will be important for us to settle on a ______.

• Java Program

• C++ Program
  • Mathematically model of computation

• Pseudo program

Merge sort is based on _______.

• Brute-force

• Plan-sweep
  • Divide and Conquer

• Axis-sweep

 What time does Merge Sort algorithm take in order to sort an array of ‘n’ numbers?

• (n)

• (log n)

• (n^2)

• d. (n log n) Google Search 31. In Heap Sort

 algorithm, the first step is to ___________.

• Call Build-Heap procedure Page – 46

• Sort the array in descending order

• Call Heapify procedure

• Find the number of input elements

The definition of theta-notation relies on proving ________ asymptotic bound.

• One

• Lower

• Upper

•  Both lower & upper                    Page – 25

In merge sort algorithm, to merge two lists of size n/2 to a list of size n, takes

_______ time.

• Theta (n)                                                                     Page – 32

• Theta log(n)

• Theta log2(n)

• Theta n log(n)

 We can make _______ recursive calls in Fibonacci Sequence.

• Infinite

• Finite                       google

• Only one

• Zero

 Following is NOT the application of Edit Distance problem.

• Speech recognition

• Spelling Correction

• Ascending Sort                                                                 Page – 76

•  Computational Molecular Biology

In plane sweep approach, a vertical line is swept across the 2d-plane and structure is used for holding the maximal points lying to the left of the sweep line.

• Array

• Queue

• Stack                                                                                              Page – 18

• Tree

When a heapify procedure is applied to the root node to restore the heap, then at each level, the comparison performed takes time:

• It will take (log n).

• It can not be predicted

•  It will take O (1).                                                               Page – 43

• Time will vary according to the nature of input data.

_____ time is the maximum running time over all legal inputs.

• Worst-case                                                                             Page – 13

• Average-case

• Best-case

• Good-case

Efficient algorithm requires less computational…

• Memory

• Running Time

• Memory and Running Time                               Page – 9

• Energy

For average-case time analysis of Quick sort algorithm, Pivot selection is on average basis from ______

• half of the input values

• all possible random values               Page – 50

• Pivot is input separately

• values greater than 5

Selection algorithm takes theta ______

• (n2)

• (n)                                                                                                        Page – 37

• log(n)

• n log(n)

Recurrence can be described in terms of a tree.

• Yes                                                                                                    Page – 31

• No

Time complexity of Dynamic Programming based algorithm for computing the minimum cost of Chain Matrix Multiplication is ______

• Log n

• n

• n^2 (n square)

• d. n^3 (n cube)                                                   Page -90

The Iteration method is used for ______

• Solving Recurrence relations                                        Page 31

• Merging elements in Merge sort

• Comparing sorting algorithms only

• Dividing elements in Merge sort

In 3-Dimensional space, a point P has ______ coordinate(s).

• (X, Y)

• (X, 0)

• (0, Y)

• (X,Y, Z)

Chain matrix multiplication problem can be solved through ______ strategy.

• Dynamic programming                                                           Page – 85

• Greedy

• Divide and conquer

• Sorting

Merge sort have running time….running time of Heap sort. Not found exactly

• Greater than

• Less than                                                  Google

• Equal to

• Different than

Median is not useful measure of central tendency of given input set especially when the distribution of values is highly skewed.

• True

•  False                                                              Page – 34

We do not need to mathematically prove that for comparison-based sorting algorithms always takes Omega nlog (n) time.

• True                                  Google

• False

The Omega-notation allows us to state only the asymptotic ______ bounds.

• Middle

• Lower                                                 Page 25

• Upper

• Both lower & upper

Both lower & upperSorting can be in ________

• Increasing order only

• Decreasing order only

• Both Increasing and Decreasing order 
  • Random order

Radix sort performs sorting the numbers _______ digit (s) at a time.

• One                                                                                   Page – 71

• Two

• Three

• All

Quicksort is a/an ______ and ________ sorting algorithm.

• Not in place, not stable one

• In place , not stable one                                        Page – 54

• In place , stable one

• Not in place , stable one

Consider three matrices X,Y,Z of dimensions 1×2, 2×3,3×4 respectively. The number of multiplications of (XY) Z is:

• 18                        As per lecture slides

• 32

• 24

• 30

In Fibonacci Sequence, unnecessary repetitions do not exist at all.

• True

• False                                                             Page – 74

 It is not a Fibonacci sequence .                     1,1,1,2,3,5,8,13,21,34,55,…..

•  True                                                                                Page – 73

• False

Heap sort is a/ an ______ and ________ sorting algorithem.

• Not in place, not stable one

•  In place , not stable one                                       Page – 54

• In place , stable one

• Not in place , stable one

Identify the True Statement

• The knapsack problem does not belong to the domain of optimization problems.

• The knapsack problem belongs to the domain of optimization

problems.                                                 Page – 91

• The Knapsack problem cannot be solved by using dynamic programming

• The knapsack problem is optimally solved by using brute force algorithm.

In Dynamic Programming, our approach is to _________

• Develop the solution in a top-down fashion

• Express the problem non-recursively

• Build the solution in a bottom-up fashion     Page – 75

• Input several sub-problems simultaneously

Counting sort is suitable to sort the elements in range 1 to K;

• K is large

• K is small                                                                  Page – 57

• K may be large or small

• None

We can multiply two matrices A and B only when they are compatible which means

• Number of columns in A must be equal to number of rows in B.

it seems Correct as per page 84

• Number of columns in A must be equal to number of columns in B
• Number of rows and columns do not matter

• Number of rows in A must be equal to number of rows in B

Matrix multiplication is a (n) ________ operation.

• Commutative

• Associative                                                            Page 85

• Neither commutative nor associative

• Commutative but not associative

In Dynamic Programming approach, solution is modified / changed

• Always once

• At each stage                                      google and wikipedia

• Only for specific problems

• At 4th stage only

In Knapsack problem, the goal is to put items in the Knapsack such that the value of the items is __________ subject to weight limit of knapsack.

• Minimized

• Decreased

• Maximized                                                               Page – 91

• None of the given options

An in-place sorting algorithm is one that ________ uses additional array for storage.

• Always

• Permanently

•  Does not                                                                   Page – 54

• Sometime

Memoization is a part of Dynamic Programming Strategy.

• True                                                                                  Page – 74

• False

If matrix A of dimension 2×4 is multiply with matrix B of dimension 4×3, then

the dimension of resultant matrix is      Not found exactly

• 2×4

• 4×3

• 3×4

• 2×3                     It seems correct as per second last Para of page 84

In Dynamic Programming approach, we do not store the solution to each sub-problem in case if it reappears.

• True
• False                                                                                                               Page – 75

Dynamic Programming is a problem-solving approach in which___

• Problem is solved in Zero time

• Solution is developed only at final stage

• Both are correct

•  Both are incorrect                                  google

In Fibonacci sequence, each term is calculated by____ previous__ terms.

• Subtracting, Two

• Adding, Three

• Adding, Two                                          Page – 73

• Multiplying, Two

Selection sort is not an in-place sorting algorithm.

• True                                                                                  Page – 54

• False

If there are θ (n2) entries in edit distance matrix then the total running time is:

• θ (n)

• θ (1)

•  θ (n2)                                                                              Page – 84
  • θ (n logn)

The only way to convert a string of i characters into the empty string is with i deletions, represented as

• E(0.j) =j

• E(i.j) = 1

• E(0.i) = j

• E (i.0)=I                                                         Page – 78

Dynamic programming formulation of the matrix chain multiplication problem will store the solutions of each sub problem in an

• Array

• Variable
• Table                                                                                                               Page – 86

• class

We can use the optimal substructure property to devise a formulation of the edit distance problem.

• Selective

• Optimum

• Iterative

• Recursive                                                                                 Page – 78

Sorting is performed on the basis of ___________.

• Computational resources

• Asymptotic notation

• Summation

• Some key value of attribute                              page- 39

 In Heap Sort algorithm, we call Build-heap procedure ____________.

• Only once                                                                 page 46

• Twice

• Thrice

• As many times as we need

Radix sort is not a non-comparative integer sorting algorithm.

• True                                                  Google Search

• False

In the statement “output P[1].x, P[1].y”, the number of times elements of P are accessed is _______.

• 1

• b. 2                                     page 14

• 3

• 4

The main purpose of mathematical analysis is measuring the ______ required by the algorithm.

• Inputs & outputs
• Space
• Execution TIME page 13

• Execution time and memory

_______ provides us more accurate result when input values are not closer with each other

• Mode
  • Average
  • Median  P-34

• Mean

The process of ______ ends when you are left with such tiny pieces remaining that it is trivial to solve them.

• Brute-force

• Plan-sweep

• Divide and Conquer

• Axis-sweep

__________ overcomes the limitations of _______ by working as per positional notations of numbers.

• Counting sort, Radix sort
  • Radix sort, Counting sort

 Memorization is a part of Dynamic Programming strategy.

• False
  • True

Rank of an element can be defined as ___________.

• One minus the number of elements that are smaller

• Two plus the number of elements that are greater

• One plus the number of elements that are smaller P-34

• Two minus the number of elements that are smaller

If the time complexity of an algorithm is given by O (1), then its time complexity would be

• Polynomial

• Exponential

• Constant                                    – Wikipedia

• Average

Quick sort is a recursive algorithm.

• True         
• False

The asymptotic growth of n(n+1)/2 is:

• O(n2)   As the n^2 term has the largest contribution, the Big-O complexity is O(n^2)
  • O(n)

• O(n+2)

• O(n log n)

Approach of solving geometric problems by sweeping a line across the plane is called _____ sweep.

• Line

• Plane              Page 18

• Cube

• Box

As per algorithm of Dynamic Programing, we need to store

• First sub-problem only

• Best solution only

• Intermediate sub-problems                               Pg:75

• Final solution only

In Sieve technique, we solve the problem

• In recursive manner                    Pg:34

• Non recursively

• Using Merge Sort algorithm

• Using Brute force technique

One of the limitation in 0/1 knapsack is that an item can either be ________ in the bag or not.

• Use

• Put                                                                                     Pg:91

• Move

• Store

Which one is not passed as parameter in Quick sort algorithm?

• End of the array

• Middle of the array

• Array (containing input elements)                           Google

• Start of the array

In the analysis of Selection algorithm, we get the convergent _________

• Harmonic

• Linear

• Arithmetic

• Geometric                                                                Pg:37

A Random Access Machine (RAM)is an idealized machine withrandom access memory.

• Infinite large                                          Pg:10

• 512 MB

• 256 MB

• 2 GBs

While analyzing Selection algorithm, we make a number of passes, in fact it could be as many as

• n(n+1)

• log(n)                                                                              Pg:37

• n/3

• n/4

In Random Access Machine (RAM), instructions are executed in

• Parallel

• Batch

• One by One                                                            Pg:10

• Multiple times

In selection problem, the rank of an element will be its ________ position

• First

• final                                                                                   Pg:34

• Second last

• Last

The worst-case running time of Merge sort is _____ in order to sort an array of n elements.

• O(log n)

• O(n)

• O(n log n)                                  page 40 and google

• O(n)

f(n) and g(n) are asymptotically equivalent. This means that they have essentially the same ______.

• Results

• Variables

• Growth Rates

• Size

An algorithm is a mathematical entity. Which is independent of _______.

• Programming language

• Machine and Programming language

• Programing Language Compiler and Machine

• Compiler and Programming language

In Quick sort algorithm, Pivots form ___

• Stack

• Queue

• Graph
  • Binary Search Tree

Counting sort is suitable for sorting the elements within range 1 to P. where

• P is large

• P is very large

• P is undetermined
  • P is Small

In asymptotical analysis of n'(5 2)-3, as n becomes large, the dominant (fastest growing) term is some constant times

• n_1

• n

• n+1

• n*n p-23

___ Items are not allowed in the 0/1  knapsack.

• Lighter

• Whole

• Weighty
• Fractional

Fibonacci Sequence was named on ______, a famous mathematician in 12th Century.

• Fred Brooks

• Grady Booch

• Leonardo Pisano

• Edgar F. Codd

In Heap Sort algorithm, we build _____ for ascending sort.

• Min heap
  • Max Heap pg-41

Bubble sort is not an in-place sorting algorithm.

1. True

b. False

P-54

In partition algorithm, the subarray ______ has elements which are greater than pivot element x.

• A[p…r]

• A[p…q-1]

• A[q]
  • S[q+1…r]

In Heap Sort algorithm, if heap property is violated

• We call Heapify procedure

• We ignore

• Heap property can never be violated

• We call Build Heap procedure

______ is not a characteristic of Random Access Machine.

• Assigning a value to a variable

• Locality of reference

• Single-Processor      P-10

• Executing an arithmetic instruction

The only way to convert an empty string into a sting of j characters is by doing j insertions, represented as ______

• E(i,j) = 1

• E(I,0) = I

•  E(0,j) = j                      page 78

• E(1,j)= j

In Selection problem, the Sieve technique works in __________.

• Non-recursive manner

• Constant time

• Phases         page 34

• One complete go

Algorithm is a sequence of computational steps that —- the input into output.

• Merge

• Assign

• Transform                page 7

• Integrate

If pj dominates pi and pi dominates ph then pj also dominates ph, it means dominance relation is

• Transitive                  page 18

• Non Transitive

• Equation

• Symbolic

To find maximal points in brute-force algorithm each point of the space is compared against ______ of that space.

• One other point

• All other points                       page 11

• Few other points

• Most of the other points

In the following code the statement “cout<<j;”executes ——— times. for (j=1; j<=5; j = j+2)

cout<<j;

• 5 times

• 2 times

• 3 times

• 0 times

In merge sort algorithm, we split the array around the ______ index q.

• Mid                     page 17

• Exiting
  • Entring

• Summing

In Selection problem, the Sieve technique _________.

• Add some more input items each time

• Do not work recursively

• Do not uses Divide and Conquer approach

• Eliminates undesired data items each time

Consider three matrices X, Y, Z of dimensions 1 x 2, 2 x 3, 3 x 4 respectively. The number of multiplications of X(YZ) is .

• 16

• 32

• 26

• 32                      page 84

In Heap Sort algorithm, the total running time for Heapify procedure is

_______

• Theta (log n)

• Order (log n)

• Omega (log n)

• O(1) i.e. Constant time

The sieve technique works where we have to find_______ items(s) from a large input.

• Single               page 34

• Two

• Three

• Similar

In Dynamic Programming based solution of Knapsack Problem, if we decide to take an object i , then we gain______

• W(Total Weight of Knapsack)

• V (Total Value of all items)

•  vi (Value of object i)                      page 93

• Nome of the given option

While Sorting, the order domain means for any two input elements x and y

_______ satisfies only.

• x < y                             page 39

• x > y

• x = y

• All of the above

For solving Selection problem, we introduced Sieve technique due to

_______

• Using Decrease and Conquer strategy        page 34

• Avoiding to sort all input data

• Eliminating Rank of an element

• Using Brute-force approach

________ is one of the few problems, where provable lower bounds exist on how fast we can sort.

• Searching

• Sorting                                page 38

• Both Searching & sorting

• Growing

In plane sweep approach, a vertical line is swept across the 2d-plane from_____.

• Right to Left

• Left to Right               page 18

• Top to Bottom

• Bottom to top

In generating Fibonacci sequence, we can avoid unnecessary repetitions by

_____ process.

• Tokenization

• Memorization               page 43

• Randomization

• Memorization

For _________ values of n, any algorithm is fast enough.

• Medium

• Large
• Small                                             page 14

• Infinity

Dynamic programming comprises of _______.

• Recursion only

• Repetition only

• Recursion with Repetition

• No Repetition but Recursion                 page 75

The function f(n)=n(logn+1)/2 is asymptotically equalient t nlog n :Here Lower Bound means function f(n) grows asymptotically at __ as fast as nlog n.

• Least                                   page 23

• Normal

• Most

• At

Counting sort has time complexity.

• O(n+k)

• O(n)                                   page 58

• O(k)

• O(nlogn)

Due to left complete nature of binary tree, the heap can be stored in

• Array                                page 40

• Structures

• Link List

• Stack

Single item from a larger set of ________.

• Constant

• Pointers

• Phases

•  n items                           page 34

In the clique cover problem, for two vertices to be in the same group, they must be ______ each other.

• Apart from

• Far from

• Near to

• Adjacent to                                 page 76

How much time merge sort takes for an array of numbers?

• T(n^2)

• T(n)

• T(log n)

• T(n log n)                                    page 40

In in-place sorting algorithm is one that uses arrays for storage.

• No additional array                                   page 54

• An additional array

• Both of above may be true according to algorithm

• More than 3 arrays of one dimension

Brute-force algorithm for 2D-Maxima is operated by comparing ______

pairs of points.

• Two

• Some

• Most

•  All                   page 18

While Sorting, the ordered domain means for any two input elements x and y ____ satisfies only.

• x > y

• x < y

• x = y

• All of the above                    page 38

Quick sort is.

• Not stable but in place                          page 54

• Stable but not in place
  • Stable & in Place

• Some time stable & some times in place

Which may be a stable sort?

• Merger

• Insertion

• Both above                        page 54

• None of the above

                For the Sieve Technique we take time.

• T(nk)                         page 34

• IT(n / 3)

• n^2

• n/3

Continuation sort is suitable to sort the elements in range 1 to k.

• K is Large

• K is not known

• K may be small or large

• K is small                       page 54

Asymptotic growth rate of the function is taken over ______ case running time. .

• Worst                        page 14

• Average
  • Best

• Normal

The sieve technique is a special case, where the number of sub problems is just.

• 5

• Many

• 1                 page 34

• Few

In Quick sort, we don’t have the control over the sizes of recursive calls.

• True                 page 49

• False

• Less information to decide

• Ether true or false

Before sweeping a vertical line in plane sweep approach, in start sorting of the points is done in increasing order of their _____ coordinates. .

• Y

• Z
• X

• X , Y

Random access machine or RAM is a/an.

• Machine build by Al-Khwarizmi

• Mechanical machine

•  Mathematical model                    page 10

• Electronics machine

The Huffman codes provide a method of encoding data inefficiently when coded using ASCII standard.

• True

• False                                        page 99

A heap is a left-complete binary tree that confirms to the ________.

• increasing order only

• decreasing order only

•  heap order                      page 40

• log n order

If we associate (x, y) integers pair to cars where x is the speed of the car and y is the negation of the price. High y value for a car means a ________ car.

1. Fast

• Slow

• Expensive

• Cheap

Which one of the following sorting algorithms is the fastest?

• Merge sort

• Quick sort

• Insertion sort

• Heap sort

Quick sort algorithm divide the entire array into ________ sub arrays.

• 2

• 3

• 4

• 5

In brute force algorithm, we measure running time T(n) based on ________.

• Worst-case time and best-case time
• Worst-case time and average-case time                          page 46
• Average-case time and best-case time

• Best-case time and staring-case time

For 2D Maxima problem. Plane Sweep algorithm first of all _________.

• Sorts all points

• Delete some points

• Output the elements

• Pushes all points on stack

There are ________ entries in the Edit Distance Matrix

• ϴ (n)

•  ϴ (n2)                        page 84

• ϴ (n+2)

• ϴ (n + 100)

Which symbol is used for Omega notation?

• (O)

• (ϴ)

• (Ω)

• (@)

Selection sort is a ______ sorting algorithm

• In-place                                 page 54

• Not In-Place

• Stable

• in-partition

In Dynamic Programming based solution of knapsack problem, to compute entries of ‘V’, we will imply a(n) ______ approach.

• Subjective

• Inductive

• Brute Force

• Combination

We do not need to prove comparison-based sorting algorithms by mathematically. It always takes _________ time.

• Big Oh nlog(n)

• Omega nlog(n)            NOT SURE

• Omega n(n^2)

• Theta nlog(n)

Merge sort is a/an _______ and ________ sorting algorithm

• Not in-place, not stable one

• In-place, not stable one

• In-place, stable one

• Not in-place, stable one                      page 54

Cubic function will ________ a quadratic function.

• Prove

• be equal to

• overtake                     Page 25

• find

Insertion sort is a _________ sorting algorithm

• Unstable

•  In-place       Page 54

• Not In-Place

• in-partition

To check whether a function grows faster or slower than the other function, we use some asymptotic notations, which is ________.

• Big-oh notation

• Theta notation

• Omega notation

• All of the given

Asymptotic growth of 8n^2 + 2n – 3 is:

• Θ(n^2 + n)

• Θ (n^2)                      page 14

• Θ(8n^2)

• Θ(8n^2 + 2n)

In the analysis of algorithms, _________ plays an important role.

• text analysis

• time

• growth rate

• money

In inductive approach of knapsack problem, we consider 2 cases, _______

Or ________.

• Median, Mode

• Recursive, Iterative

•  Leave object, Take object  page 93

• Sequentially. Parallel

Random Access Machine (RAM) can execute _________ instructions

• only logical

• parallel

• only arithmetic

• logical and arithmetic

Using _______ algorithm, efficiency is not given much importance

• Greedy

• Merge sort

• Processing                            

• Brute Force

Bubble sort takes theta _________ in the worst case

• (n2)                    page 39

• (n)

• log(n)

• nlog(n)

If matrix A of dimension p × q is multiply with matrix B of dimension q × r, then dimension of resultant matrix is:

• q × r

• r × p
• P x r
• P x q

Dynamic Programing algorithms often use some kind of ________ to store the results of intermediate sub-problems

• variable

• stack
• Table

• loop

________________ is in-place sorting algorithm.

• Bubble sort             (Page 54)

• Merge sort

• Linear search

• Binary Search

Which one of the following problems can be solved using dynamic problem?

• Bubble sort problem

• Matrix chain multiplication problem      page 85

• Greedy search problem

• Fractional knapsack problem

In chain matrix multiplication, solutions of the sub-problems are stored in a

_________.

• Array

• Table               page 86

• Tree

• Link list

What is the average running time of a quick sort algorithm?

• O(n^2)

• O(n)

•  O(n log n) (Page 49)

• O(log n)

Sorting Algorithms having O _______ running time are considered to be slow ones.

• (n)

• (n^2)            (Page 39)

• (nlog(n))

• (log(n))

While solving Selection problem, in Sieve technique we partition input data

________

• In increasing order

• In decreasing order

• According to Pivot

• Randomly

________ is the process of avoiding unnecessary repetitions by writing down the results of recursive calls and looking them up again if we need them later.

• Loop
  • Memoization                   page 74

• Recursion

• Function

In average-case time the probability of seeing input is denoted by _______.

• p{I}

• p[I]

• p<i>

• p(i)                                 page 13

While applying the Sieve technique to selection sort, how to choose a pivot element.

• Through mean

• Linear

• Randomly                   page 35

• Sequentially

Number of _______ of the pseudo code are counted to measure the running time.

• Inputs

• Outputs

• Steps              page 13

• Pages

Developing a dynamic programming algorithm generally involves ______

separate steps.

• One

• Two                             page 75

• Three

• Four

8n^2+2n+3 will exceed c28(n), no matter how large we make _____.

• n

• 2n

• c2                           page 25

• this quadratic equation

The running time of quick sort algorithm_________.

• Is impossible to compute

• Has nothing to do with pivot selection

• Is Random upon each execution

• Greatly influenced by the selection of pivot    page 49

_________ involves breaking up the problem into sub problems whose solutions can be combined to solve the global problem.

• Complexity Theory

• Dynamic programming solution

•  Divide and Conquer Strategy          page 34

• Greedy Algorithms

In _____________ we have to find rank of an element from given input.

• Merge sort algorithm

• Selection problem                 page 34

• Brute force technique

• Plane Sweep algorithm

How many steps are involved to design the dynamic programming strategy?

• 2

• 3

• 1

•  4                                     page 92

In Bucket sort, if there are duplicates then each bin can be replaced by a

•  Linked list         page 69

• Hash table
  • Stack

• Heap

In merge sort algorithm, we split the array ______ to find index q.

• from end
• from start
• midway   page 28

• both from start or end

Find the maximum value of the items which can carry using knapsack Knapsack weight capacity = 50.

Item  Weight Value

11070

22020

33080

470  200

• 280

• 100

• 90

• 200

In 2-d maxima problem a point p is said to be dominated by point q if

_________.

• p.x <= q.x

• bp.x <= q.x and p.y <= q.y                   page 17

• p.y <= q.y

• p.x >= q.x and p.y >=q.y

Sorting can be in ______________.

• Increasing order only

• Decreasing order only

• Both increasing and decreasing order

• Random order

Recurrence can be described in terms of _______________.

• Array

• Linear

• Tree                                  page 31

• Graph

The brute-force algorithm for 2D-Maxima runs in order O(__) time.

• n

• n(log n)

• n*n                            page 18

• n3

In plane sweep approach of solving geometric problems, a _________ is swept across the plane.

• Line                        page 18

• Plane

• Cube

• Box

Which of the following is calculated with Big Omega notation?

1. Medium bounds

• Upper bounds

c. Lower bounds                     Page – 25

• Both upper and lower bounds

_________ is always based on divide and conquer strategy.

• Bubble sort

• Selection sort

• Pigeon sort

• Quick sort                 page 46

If a matrix has three rows and two columns, then dimensions of matrix will be:

• 3×2

• 2×3

• 3×3

• 2×2

Asymptotic notations are used to describe _______ of an algorithm.

• Length

• running time                  google

• size

• compile time

Catalan numbers are related the number of different ______ on ‘n’ nodes.

• Arrays

• linked lists

• binary trees            page 85

• functions

Applying the sieve technique to selection problem, ________ element is picked from array.

• Output

• Total

• Input

• Pivot                page 35

Dynamic Programming approach is usually useful in solving _______

problems.

•  Optimization                       google

• Array

• Normal

• Loop

In recursive formulation of knapsack Problem: V [0, j] = ________ for j>=0

• -1

•  0                 page 93

• 1

• 2

________ is a linear time sorting algorithm.

• Merge sort

• Radix sort                          page 71

• Quick sort

• Bubble sort

Quick sort is one of the _____ sorting algorithm.

• Fastest         page 19

• Slowest

• Major

• Average

The time assumed for each basic operation to execute on RAM model of computation is _____.

• Infinite

• Continuous

• Constant                    page 10

• Variable

In Sieve Technique, we know the item of interest.

• True
• False

While analyzing algorithms, _______ and _______ usually considered difficult to calculate.

•  Floor, ceiling       google

• Row, Column
  • Finite, Infinite

• Graph, Tree

While analysis of the brute-force maxima algorithm, an array sorted in the reverse order is the type of _________ case input.

• Best

• Worst              page 14

• Somewhat bad

• Average

_________ is not useful measure of central tendency of given input set especially when the distribution of values is highly skewed.

• Mean

• Mode

• Average

• Median         page 34

In asymptotical analysis of n(n-3) and 4n*n, as n becomes large, the dominant (fastest growing) term is some constant times _______.

• n+1

• n-1

• n

• n*n                     page 23

In addition to passing in the array itself to Merge Sort algorithm, we will pass in other arguments which are indices.

• Three
• Two

• Four

• Five

In 2d-maximal problem, a point is said to be if it is not dominated by any other point in that space.

• Member

• Minimal
  • Maximal

• Joint

Counting sort assumes that the numbers to be sorted are in the range

________.

1. K to n where n is large

• K to n where k is small
  • 1 to k where k is small

• k to n where n is small

Insertion sort is an efficient algorithm for sorting a __________ number of elements

• Small

• Extra large
  • Large

• Medium

If the indices passed to merge sort algorithm are _________ then this means that there is only one element to sort.

• Small                                page 28

• Large

• Equal

• Not Equal

In Knapsack Problem, each item must be entirely accepted or rejected, is called ______ problem.

• Linear
• Fractional
• 0-1

• Optimal

If the time complexity of an algorithm is O(n). then it is called _______ time complexity.

• Linear                                                            Wikipedia

• Constant

• Average

• Exponential

In the case of _________ analysis does not depend upon on the distribution of input.

• Merge sort

• Insertion sort
  • Quick Sort

• Heap sort

We can use the ___________ Property to devise a recursive formulation of the edit distance problem.

• Small substructure

• Algorithmic

• Real

• Optimal substructure                         page 78

The following sequence is called ____________

• 1,2,3,5,8,13,21,34,55,…..
  • Fibonacci sequence                   page 73

• Optimal sequence
  • Optimize Sequence

• Overlapping sequence

Which one sorting algorithm is best suited to sort an array of 2 million elements?

• Bubble sort

• Insert sort

• Merge sort

• Quick sort

• Ridx Sort    page 71

We can improve the performance of quick sort if we could be able to _,__________.

• Select two or more pivots              page 34

• Skip any sub-array completely
  • Skit Input elements somehow

• Eliminate recursive calls

The problem with the brute-force algorithm is that is uses ________ in pruning out de

• Worst-case time

• No intelligence                        page 18

• Outside looping

• Artificial intelligence

In chain matrix multiplication, the order of the matrices __________.

• Can be changed

•  Can not be changed                      page 85

• is equal

• is reverse

In quick sort algorithm, we choose pivot___________.

• Always the smallest element

• Greater than 5

• Randomly                  page 35

• Less than 5

• In Heap Sort algorithm. Heapify procedure is ________ in nature.

• Recursive

•  Non-Recursive                 page 43

• Fast

• Slow

When matrix A of 5x 3 is multiplied with matrix B of 3 x 4 then the number of multiplications required will be ___________.

• 15

• 12

• 36

• 60

An algorithm is said to be correct if for every ______ instance, it halts with the correct ______.

• Input, Output                       page 13

• Design, Analysis

• Value, Key

• Key, Analysis

In chain matrix multiplication, table is filled _________ to find the multiplication of matrix.

• row wise

• column wise

• diagonally

• bottom-to-up         page 86

If we have an equation 8n2+7f*n + 5f + 6 then is large, ________ term will be muchxxxxxxxthe n term and will dominate the running time.

• f g (n)

• g (n) * 2

• n * 2                  page 23

• f (n)

For quick sort algorithm. Partitioning takes theta ________.

• (n)

• log(n)

• n log (n)

• n2log (n)

In Heap Sort algorithm, the maximum levels an element can move upward is

_______

• Theta (log n)          page 43

• Big-ch (log n)

• Omega (log n)

• 0 (1) i.e. Constant time

_______ programming is essentially recursion without repetition.

• Array
• Fast
• Dynamic

• n (log n)

There are no hard formal rules to the syntax of the ________ code.

1. Basic

• Programming

• Pseudo

• Assembly

In Heap Sort algorithm, to remove the maximum element every time.

• We call Build-Heap procedure

• Heap Sort algorithm terminates without result

• We call heapify procedure

• Nothing happens

Which process is used for avoiding unnecessary repetitions and looking them up again if we need them later.

• Greedy Approach

• Memoization                      page 74

• Divide and conquer

• Recursion

The worst-case running time of Quick sort is _________ in order to sort an array of n element.

• O(n log n)                       page 49

• O(n)

• O(n2)
  • O(log n)

Boolean operation is a _________ operation on an idealized RAM model of computation.

• Advance
• String
• Basic

• Normal

In chain matrix multiplication, if there are n items, there are ________ ways in which outer most pair of parentheses can placed.

• n^2

• 2n

• n+1

• d. n-1           page 85

The number of nodes in a complete binary tree of height h is:

• * (h+1) – 1

• * (h+1)
• b. 2^(h+1) – 1                             page 40

• ((h+1)^2) – 1

 

Consider the following Algorithm: Fun(n){ if (n=1) return 1 else return (n * Fun(n-1)) } Recurrence for the above algorithm is:

nT(n-1)+1

2T(n-1)+1

T(n-1)+cn

T(n-1)+1

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

Brute-force algorithm uses no intelligence in pruning out decisions.

True

False

f(n) and g(n) are asymptotically equivalent. This means that they have essentially the same __________ for large n.

Results

Variables

Size

Growth rates

In analysis, the Lower Bound means the function grows asymptotically at least as fast as its largest term.

True

False

Efficient algorithm requires less computational…….

Memory

Running Time

Memory and Running Time

Energy

The O-notation is used to state only the asymptotic ________bounds.

Two

Lower

Upper

Both lower & upper

For the worst-case running time analysis, the nested loop structure containing one “for” and one “while” loop, might be expressed as a pair of _________nested summations.

1 (not confirm )

2

3

4

 

The time assumed for each basic operation to execute on RAM model of computation is—–

Infinite

Continuous

Constant          (p10)

Variable

 

If the indices passed to merge sort algorithm are not equal, the algorithm may return immediately.

True

False    (p28)

 

Brute-force algorithm uses no intelligence in pruning out decisions.

True     (p18)

False

 

In analysis, the Upper Bound means the function grows asymptotically no faster than its largest term.

True     (p24)

False

 

For small values of n, any algorithm is fast enough. Running time does become an issue when n gets large.

True     (p14)

Fast

 

The array to be sorted is not passed as argument to the merge sort algorithm.

True

False    (p28)

 

In simple brute-force algorithm, we give no thought to efficiency.

True     (p11)

False

Heaps can be stored in arrays without using any pointers; this is due to the ___ nature of the binary tree,
Left-complete   (p40) 

right-complete

tree nodes

tree leaves

One of the clever aspects of heaps is that they can be stored in arrays without using any______
Pointers (p40)

constants

variables

functions

How much time merge sort takes for an array of numbers?

T(n^2)

T(n)

T( log n)

T(n log n)      (p40)

 

 

+++++++++++++++++++++++++

Question # 1 of 10 ( Start time: 01:57:15 PM)

The ancient Roman politicians understood an important principle of good algorithm design that is plan-sweep algorithm.

Select correct option:

True

False   (p27)     [Divide and Conquer]

 

Question # 2 of 10 ( Start time: 01:58:29 PM)

In 2d-space a point is said to be ________if it is not dominated by any other point in that space.

Select correct option:

Member

Minimal

Maximal        (p11)

Joint

 

Question # 3 of 10 ( Start time: 01:59:45 PM)

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)

 

Question # 4 of 10 ( Start time: 02:00:46 PM)

An algorithm is a mathematical entity that is dependent on a specific programming language.

Select correct option:

True

False        (p7)

 

 

 

 

 

Question # 5 of 10 ( Start time: 02:01:59 PM)

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

 

Question # 6 of 10 ( Start time: 02:03:12 PM)

The running time of an algorithm would not depend upon the optimization by the compiler but that of an implementation of the algorithm would depend on it.

Select correct option:

True

False       (p13)

 

Question # 7 of 10 ( Start time: 02:04:02 PM)

f(n) and g(n) are asymptotically equivalent. This means that they have essentially the same __________ for large n.

Select correct option:

Results

Variables

Size

Growth rates           (p23)

 

Question # 8 of 10 ( Start time: 02:04:56 PM)

8n2 + 2n – 3 will eventually exceed c2*(n) no matter how large we make c2.

Select correct option:

True    (p25)

False

 

Question # 9 of 10 ( Start time: 02:05:45 PM)

If we associate (x, y) integers pair to cars where x is the speed of the car and y is the negation of the price. High y value for a car means a ________ car.

Select correct option:

Fast

Slow

Expensive

Cheap          (p11)

 

Question # 10 of 10 ( Start time: 02:06:58 PM)

For the sieve technique we solve the problem,

Select correct option:

recursively

mathematically

precisely

accurately

 

+++++++++++++++++++

 

Question # 1 of 10
Analysis of Selection algorithm ends up with,
Select correct option:
T(n)    (p37)
T(1 / 1 + n)
T(n / 2)
T((n / 2) + n)

Question # 2 of 10
The function f(n)= n(logn+1)/2 is asymptotically equivalent to n log n. Hre Upper Bound means the function f(n) grows asymptotically ____________ faster than n log n.
Select correct option:
More
Quiet
Not    (p24)
At least

Question # 3 of 10
The running time of an algorithm would not depend upon the optimization by the compiler but that of an implementation of the algorithm would depend on it.
Select correct option:
True
False    (p7)

Question # 4 of 10 ( Start time: 03:26:18 PM )     Total Marks: 1
After sorting in merge sort algorithm, merging process is invoked.
Select correct option:
=True    (p27)
False

Question # 5 of 10
Asymptotic growth rate of the function is taken over_________ case running time.
Select correct option:
Best
Average
Worst (p14 Note sure)
Normal

Question # 6 of 10
In analysis of f(n)=n(n/5)+n-10 log n, f(n) is asymptotically equivalent to ________.
Select correct option:
n
2n
n+1
=    n2    (p23)

Question # 7 of 10
f(n) and g(n) are asymptotically equivalent. This means that they have essentially the same __________ for large n.
Select correct option:
Results
Variables
Size
=    Growth rates    (p23)

Question # 8 of 10
Algorithm is concerned with…….issues.
Select correct option:
Macro
Micro
Both Macro & Micro (p8)
Normal

Question # 9 of 10
We can not make any significant improvement in the running time which is better than that of brute-force algorithm.
Select correct option:
True
False

Question # 10 of 10
In addition to passing in the array itself to Merge Sort algorithm, we will pass in _________other arguments which are indices.
Select correct option:
Two    (p28)
Three
Four
Five

+++++++++++++

Consider the following Algorithm: Fun(n){ if (n=1) return 1 else return (n * Fun(n-1)) } Recurrence for the above algorithm is:

nT(n-1)+1

2T(n-1)+1

T(n-1)+cn

T(n-1)+1

 

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

 

Brute-force algorithm uses no intelligence in pruning out decisions.

True

False

 

f(n) and g(n) are asymptotically equivalent. This means that they have essentially the same __________ for large n.

Results

Variables

Size

Growth rates

 

In analysis, the Lower Bound means the function grows asymptotically at least as fast as its largest term.

True

False

 

Efficient algorithm requires less computational…….

Memory

Running Time

Memory and Running Time

Energy

 

The O-notation is used to state only the asymptotic ________bounds.

Two

Lower

Upper

Both lower & upper

 

For the worst-case running time analysis, the nested loop structure containing one “for” and one “while” loop, might be expressed as a pair of _________nested summations.

1 (not confirm )

2

3

4

 

Question # 1 of 10 ( Start time: 06:18:58 PM ) Total Marks: 1
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

Question # 2 of 10 ( Start time: 06:19:38 PM ) Total Marks: 1
Heaps can be stored in arrays without using any pointers; this is due to the ____________ nature of the binary tree,
Select correct option:

left-complete p=40
right-complete
tree nodes
tree leaves

Question # 3 of 10 ( Start time: 06:20:18 PM ) Total Marks: 1
Sieve Technique can be applied to selection problem?
Select correct option:

True p=35
False

Question # 4 of 10 ( Start time: 06:21:10 PM ) Total Marks: 1
A heap is a left-complete binary tree that conforms to the ___________
Select correct option:

increasing order only
decreasing order only
heap order p=40
(log n) order

Question # 5 of 10 ( Start time: 06:21:39 PM ) Total Marks: 1
A (an) _________ is a left-complete binary tree that conforms to the heap order
Select correct option:

heap p=40
binary tree
binary search tree
array

Question # 6 of 10 ( Start time: 06:22:04 PM ) Total Marks: 1
Divide-and-conquer as breaking the problem into a small number of
Select correct option:

pivot
Sieve
smaller sub problems  p=34
Selection

Question # 7 of 10 ( Start time: 06:22:40 PM ) Total Marks: 1
In Sieve Technique we do not know which item is of interest
Select correct option:

True p=34
False

Question # 8 of 10 ( Start time: 06:23:26 PM ) Total Marks: 1
The recurrence relation of Tower of Hanoi is given below T(n)={1 if n=1 and 2T(n-1) if n >1 In order to move a tower of 5 rings from one peg to another, how many ring moves are required?
Select correct option:

16
10
32 p=30
31

Question # 9 of 10 ( Start time: 06:24:44 PM ) Total Marks: 1
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,
Select correct option:

linear
arithmetic
geometric p=37
exponent

Question # 10 of 10 ( Start time: 06:25:43 PM ) Total Marks: 1
For the heap sort, access to nodes involves simple _______________ operations.
Select correct option:
arithmetic p=41
binary
algebraic
logarithmic

For the sieve technique we solve the problem,
Select correct option:
recursively
mathematically
precisely
accurately
The sieve technique works in ___________ as follows
Select correct option:
phases
numbers
integers
routines
Slow sorting algorithms run in,
Select correct option:
T(n^2)
T(n)
T( log n)
A (an) _________ is a left-complete binary tree that conforms to the heap order
Select correct option:
heap
binary tree
binary search tree
array

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,
Select correct option:
linear
arithmetic
geometric
exponent

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

The sieve technique is a special case, where the number of sub problems is just
Select correct option:
5
many
1
few

In which order we can sort?
Select correct option:
increasing order only
decreasing order only
increasing order or decreasing order
both at the same time

The recurrence relation of Tower of Hanoi is given below T(n)={1 if n=1 and 2T(n-1) if n >1 In order to move a tower of 5 rings from one peg to another, how many ring moves are required?
Select correct option:
16
10
32
31

Analysis of Selection algorithm ends up with,
Select correct option:
T(n)
T(1 / 1 + n)
T(n / 2)
T((n / 2) + n)

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 

Divide-and-conquer as breaking the problem into a small number of
Select correct option:

pivot
Sieve
smaller sub problems
Selection

The analysis of Selection algorithm shows the total running time is indeed ________in n,
Select correct option:

arithmetic
geometric
linear
orthogonal

How many elements do we eliminate in each time for the Analysis of Selection algorithm?
Select correct option:

n / 2 elements
(n / 2) + n elements
n / 4 elements
2 n elements

 Reply

Message

Permalink Reply by + M.Tariq Malik on May 3, 2013 at 9:45pm

Sieve Technique can be applied to selection problem?
Select correct option:

True
false

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

 

 

One of the clever aspects of heaps is that they can be stored in arrays without using any _______________.
Select correct option:
pointers
constants
variables
functions

 

A (an) _________ is a left-complete binary tree that conforms to the heap order
Select correct option:
heap
binary tree
binary search tree
array

 

Divide-and-conquer as breaking the problem into a small number of
Select correct option:
pivot
Sieve
smaller sub problems
Selection

Heaps can be stored in arrays without using any pointers; this is due to the ____________ nature of the binary tree,
Select correct option:
left-complete
right-complete
tree nodes
tree leaves

For the sieve technique we solve the problem,
Select correct option:
recursively
mathematically
precisely
accurately

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

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

How many elements do we eliminate in each time for the Analysis of Selection algorithm?
Select correct option:
n / 2 elements
(n / 2) + n elements
n / 4 elements
2 n elements

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)

The reason for introducing Sieve Technique algorithm is that it illustrates a very important special case of,
Select correct option:
divide-and-conquer
decrease and conquer
greedy nature
2-dimension Maxima

 

Question # 1 of 10 ( Start time: 08:17:23 AM ) Total M a r k s: 1
The number of nodes in a complete binary tree of height h is
Select correct option:
2^(h+1) – 1
2 * (h+1) – 1
2 * (h+1)
((h+1) ^ 2) – 1

Question # 2 of 10 ( Start time: 08:18:46 AM ) Total M a r k s: 1
A (an) _________ is a left-complete binary tree that conforms to the heap order
Select correct option:
heap
binary tree
binary search tree
array

Question # 3 of 10 ( Start time: 08:19:38 AM ) Total M a r k s: 1
In Sieve Technique we do not know which item is of interest
Select correct option:
True
False

Question # 4 of 10 ( Start time: 08:20:33 AM ) Total M a r k s: 1
Heaps can be stored in arrays without using any pointers; this is due to the
____________ nature of the binary tree,
Select correct option:
left-complete
right-complete
tree nodes
tree leaves

Question # 5 of 10 ( Start time: 08:21:59 AM ) Total M a r k s: 1
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

Question # 6 of 10 ( Start time: 08:23:01 AM ) Total M a r k s: 1
For the sieve technique we solve the problem,
Select correct option:
recursively
mathematically
precisely
accurately
Theta asymptotic notation for T (n) :
Select correct option:
Set of functions described by: c1g(n)Set of functions described by c1g(n)>=f(n) for c1 s
Theta for T(n)is actually upper and worst case comp
Set of functions described by:
c1g(n)
Question # 8 of 10 ( Start time: 08:24:39 AM ) Total M a r k s: 1
The sieve technique is a special case, where the number of sub problems is just
Select correct option:
5
many
1
few

Question # 9 of 10 ( Start time: 08:25:54 AM ) Total M a r k s: 1
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

Question # 10 of 10 ( Start time: 08:26:44 AM ) Total M a r k s: 1
The sieve technique works in ___________ as follows
Select correct option:
phases
numbers
integers
routines

 

Memorization is?

To store previous results for future use

To avoid this unnecessary repetitions by writing down the results of recursive calls and looking them up again if we need them later

To make the process accurate

None of the above

 

Question # 2 of 10 Total M a r k s: 1

Which sorting algorithm is faster

O (n log n)

O n^2

O (n+k)

O n^3

 

Quick sort is

Stable & in place

Not stable but in place

Stable but not in place

Some time stable & some times in place

 

One example of in place but not stable algorithm is

Merger Sort

Quick Sort

Continuation Sort

Bubble Sort

 

In Quick Sort Constants hidden in T(n log n) are

Large

Medium

Small

Not Known

 Reply

Message

Permalink Reply by + M.Tariq Malik on May 3, 2013 at 9:45pm

Continuation sort is suitable to sort the elements in range 1 to k

K is Large

K is not known

K may be small or large

K is small

 

In stable sorting algorithm.

If duplicate elements remain in the same relative position after sorting

One array is used

More than one arrays are required

Duplicating elements not handled

 

Which may be a stable sort?

Merger

Insertion

Both above

None of the above

 

An in place sorting algorithm is one that uses ___ arrays for storage

Two dimensional arrays

More than one array

No Additional Array

None of the above

 

Continuing sort has time complexity of ?

O(n)

O(n+k)

O(nlogn)

O(k)

 

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

 

 

In Sieve Technique we donot know which item is of interest

 

True

False

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

 

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

 

 

 

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

 

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

 

Question # 9 of 10 ( Start time: 07:45:36 AM ) Total Marks: 1

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

 

 

Sorting is one of the few problems where provable ________ bonds exits on

how fast we can sort,

Select correct option:

upper

lower

average

log n

 

single item from a larger set of _____________

Select correct option:

n items

phases

pointers

constant

 

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,

Select correct option:

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,

Select correct option:

divide-and-conquer

decrease and conquer

greedy nature

2-dimension Maxima

 

The sieve technique works in ___________ as follows

Select correct option:

phases

numbers

integers

routines

For the Sieve Technique we take time

Select correct option:

T(nk)

T(n / 3)

n^2

n/3

 

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

 

Analysis of Selection algorithm ends up with,

Select correct option:

T(n)

T(1 / 1 + n)

T(n / 2)

T((n / 2) + n)

 

Quiz Start Time: 07:23 PM
Time Left 90
sec(s)
Question # 1 of 10 ( Start time: 07:24:03 PM ) Total M a r k s: 1
In in-place sorting algorithm is one that uses arrays for storage :
Select correct option:
An additional array
No additioanal array
Both of above may be true according to algorithm
More than 3 arrays of one dimension.

 

Time Left 89
sec(s)
Question # 2 of 10 ( Start time: 07:25:20 PM ) Total M a r k s: 1
Which sorting algorithn is faster :
Select correct option:
O(n^2)
O(nlogn)
O(n+k)
O(n^3)

In stable sorting algorithm:
Select correct option:
One array is used
In whcih duplicating elements are not handled.
More then one arrays are required.
Duplicating elements remain in same relative posistion after sorting.

Counting sort has time complexity:
Select correct option:
O(n)
O(n+k)
O(k)
O(nlogn)
Counting sort is suitable to sort the elements in range 1 to k:
Select correct option:
K is large
K is small
K may be large or small
None
Memorization is :
Select correct option:
To store previous results for further use.
To avoid unnecessary repetitions by writing down the results of recursive calls and looking them again if needed later
To make the process accurate.
None of the above

 

The running time of quick sort depends heavily on the selection of
Select correct option:
No of inputs
Arrangement of elements in array
Size o elements
Pivot elements

Which may be stable sort:
Select correct option:
Bubble sort
Insertion sort
Both of above

In Quick sort algorithm, constants hidden in T(n lg n) are
Select correct option:
Large
Medium
Not known
small

 

Quick sort is
Select correct option:
Stable and In place
Not stable but in place
Stable and not in place
Some time in place and send some time stable

 

 

For the Sieve Technique we take time

T(nk)

T(n / 3)

n^2

n/3

 

The sieve technique is a special case, where the number of sub problems is just

Select correct option:

5

Many

1

Few

 Reply

Message

Permalink Reply by + M.Tariq Malik on May 3, 2013 at 9:45pm

The reason for introducing Sieve Technique algorithm is that it illustrates a very important special case of,

Select correct option:

divide-and-conquer

decrease and conquer

greedy nature

2-dimension Maxima

 

Which may be stable sort:
Select correct option:
Bubble sort
Insertion sort
Both of above
Selection sort

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,
Select correct option:
linear
arithmetic
geometric
exponent

In Quick sort algorithm, constants hidden in T(n lg n) are
Select correct option:

Large
Medium
Not known
small

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)

Counting sort has time complexity:
Select correct option:

O(n)
O(n+k)
O(k)
O(nlogn)

In which order we can sort?
Select correct option:

increasing order only
decreasing order only
increasing order or decreasing order
both at the same time

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

Quick sort is based on divide and conquer paradigm; we divide the problem on base of pivot element and:
Select correct option:

There is explicit combine process as well to conquer the solution.
No work is needed to combine the sub-arrays, the array is already sorted
Merging the sub arrays
None of above.

Sorting is one of the few problems where provable ________ bonds exits on how fast we can sort,
Select correct option:

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,

T(n)

T(n / 2)

log n

n / 2 + n / 4

Quick sort is based on divide and conquer paradigm; we divide the problem on base of

pivot element and:

There is explicit combine process as w ell to conquer

No w ork is needed to combine the sub-arrays, the a

Merging the subarrays

None of above

The number of nodes in a complete binary tree of height h is

2^(h+1) – 1

2 * (h+1) – 1

2 * (h+1)

((h+1) ^ 2) – 1

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

Which sorting algorithn is faster :

O(n^2)

O(nlogn)

O(n+k)

O(n^3)

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

Slow sorting algorithms run in,

T(n^2)

T(n)

T( log n)

T(n log n)

One of the clever aspects of heaps is that they can be stored in arrays without using any

_______________.

Pointers

Constants

Variables

Functions

Counting sort is suitable to sort the elements in range 1 to k:

K is large

K is small

K may be large or small

None

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

Question # 2 of 10 ( Start time: 06:19:38 PM ) Total Marks: 1
Heaps can be stored in arrays without using any pointers; this is due to the ____________ nature of the binary tree,
Select correct option:

left-complete
right-complete
tree nodes
tree leaves

Question # 3 of 10 ( Start time: 06:20:18 PM ) Total Marks: 1
Sieve Technique can be applied to selection problem?
Select correct option:

True
False

Question # 4 of 10 ( Start time: 06:21:10 PM ) Total Marks: 1
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

Question # 5 of 10 ( Start time: 06:21:39 PM ) Total Marks: 1
A (an) _________ is a left-complete binary tree that conforms to the heap order
Select correct option:

heap
binary tree
binary search tree
array

Question # 6 of 10 ( Start time: 06:22:04 PM ) Total Marks: 1
Divide-and-conquer as breaking the problem into a small number of
Select correct option:

pivot
Sieve
smaller sub problems
Selection

Question # 7 of 10 ( Start time: 06:22:40 PM ) Total Marks: 1
In Sieve Technique we do not know which item is of interest
Select correct option:

True
False

 Reply

Message

Permalink Reply by + M.Tariq Malik on May 3, 2013 at 9:45pm

Question # 8 of 10 ( Start time: 06:23:26 PM ) Total Marks: 1
The recurrence relation of Tower of Hanoi is given below T(n)={1 if n=1 and 2T(n-1) if n >1 In order to move a tower of 5 rings from one peg to another, how many ring moves are required?
Select correct option:

16
10
32
31

Question # 9 of 10 ( Start time: 06:24:44 PM ) Total Marks: 1
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,
Select correct option:

linear
arithmetic
geometric
exponent

Question # 10 of 10 ( Start time: 06:25:43 PM ) Total Marks: 1
For the heap sort, access to nodes involves simple _______________ operations.
Select correct option:
arithmetic
binary
algebraic
logarithmic

For the sieve technique we solve the problem,
Select correct option:
recursively
mathematically
precisely
accurately
The sieve technique works in ___________ as follows
Select correct option:
phases
numbers
integers
routines
Slow sorting algorithms run in,
Select correct option:
T(n^2)
T(n)
T( log n)
A (an) _________ is a left-complete binary tree that conforms to the heap order
Select correct option:
heap
binary tree
binary search tree
array

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,
Select correct option:
linear
arithmetic
geometric
exponent

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

The sieve technique is a special case, where the number of sub problems is just
Select correct option:
5
many
1
few

In which order we can sort?
Select correct option:
increasing order only
decreasing order only
increasing order or decreasing order
both at the same time

The recurrence relation of Tower of Hanoi is given below T(n)={1 if n=1 and 2T(n-1) if n >1 In order to move a tower of 5 rings from one peg to another, how many ring moves are required?
Select correct option:
16
10
32
31

Analysis of Selection algorithm ends up with,
Select correct option:
T(n)
T(1 / 1 + n)
T(n / 2)
T((n / 2) + n)

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

Divide-and-conquer as breaking the problem into a small number of
Select correct option:

pivot
Sieve
smaller sub problems
Selection

The analysis of Selection algorithm shows the total running time is indeed ________in n,
Select correct option:

arithmetic
geometric
linear
orthogonal

How many elements do we eliminate in each time for the Analysis of Selection algorithm?
Select correct option:

n / 2 elements
(n / 2) + n elements
n / 4 elements
2 n elements

Sieve Technique can be applied to selection problem?
Select correct option:

True
false

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

One of the clever aspects of heaps is that they can be stored in arrays without using any _______________.
Select correct option:
pointers
constants
variables
functions

A (an) _________ is a left-complete binary tree that conforms to the heap order
Select correct option:
heap
binary tree
binary search tree
array

Divide-and-conquer as breaking the problem into a small number of
Select correct option:
pivot
Sieve
smaller sub problems
Selection

Heaps can be stored in arrays without using any pointers; this is due to the ____________ nature of the binary tree,
Select correct option:
left-complete
right-complete
tree nodes
tree leaves

For the sieve technique we solve the problem,
Select correct option:
recursively
mathematically
precisely
accurately

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

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

How many elements do we eliminate in each time for the Analysis of Selection algorithm?
Select correct option:
n / 2 elements
(n / 2) + n elements
n / 4 elements
2 n elements

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)

The reason for introducing Sieve Technique algorithm is that it illustrates a very important special case of,
Select correct option:
divide-and-conquer
decrease and conquer
greedy nature
2-dimension Maxima

Question # 1 of 10 ( Start time: 08:17:23 AM ) Total M a r k s: 1
The number of nodes in a complete binary tree of height h is
Select correct option:
2^(h+1) – 1
2 * (h+1) – 1
2 * (h+1)
((h+1) ^ 2) – 1

Question # 2 of 10 ( Start time: 08:18:46 AM ) Total M a r k s: 1
A (an) _________ is a left-complete binary tree that conforms to the heap order
Select correct option:
heap
binary tree
binary search tree
array

Question # 3 of 10 ( Start time: 08:19:38 AM ) Total M a r k s: 1
In Sieve Technique we do not know which item is of interest
Select correct option:
True
False

Question # 4 of 10 ( Start time: 08:20:33 AM ) Total M a r k s: 1
Heaps can be stored in arrays without using any pointers; this is due to the
____________ nature of the binary tree,
Select correct option:
left-complete
right-complete
tree nodes
tree leaves

 Reply

Message

Permalink Reply by + M.Tariq Malik on May 3, 2013 at 9:46pm

Question # 5 of 10 ( Start time: 08:21:59 AM ) Total M a r k s: 1
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

Question # 6 of 10 ( Start time: 08:23:01 AM ) Total M a r k s: 1
For the sieve technique we solve the problem,
Select correct option:
recursively
mathematically
precisely
accurately
Theta asymptotic notation for T (n) :
Select correct option:
Set of functions described by: c1g(n)Set of functions described by c1g(n)>=f(n) for c1 s
Theta for T(n)is actually upper and worst case comp
Set of functions described by:
c1g(n)

Question # 8 of 10 ( Start time: 08:24:39 AM ) Total M a r k s: 1
The sieve technique is a special case, where the number of sub problems is just
Select correct option:
5
many
1
few

Question # 9 of 10 ( Start time: 08:25:54 AM ) Total M a r k s: 1
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

Question # 10 of 10 ( Start time: 08:26:44 AM ) Total M a r k s: 1
The sieve technique works in ___________ as follows
Select correct option:
phases
numbers
integers
routines

Memorization is?

To store previous results for future use

To avoid this unnecessary repetitions by writing down the results of recursive calls and looking them up again if we need them later

To make the process accurate

None of the above

Question # 2 of 10 Total M a r k s: 1

Which sorting algorithm is faster

O (n log n)

O n^2

O (n+k)

O n^3

Quick sort is

Stable & in place

Not stable but in place

Stable but not in place

Some time stable & some times in place

One example of in place but not stable algorithm is

Merger Sort

Quick Sort

Continuation Sort

Bubble Sort

In Quick Sort Constants hidden in T(n log n) are

Large

Medium

Small

Not Known

Continuation sort is suitable to sort the elements in range 1 to k

K is Large

K is not known

K may be small or large

K is small

In stable sorting algorithm.

If duplicate elements remain in the same relative position after sorting

One array is used

More than one arrays are required

Duplicating elements not handled

Which may be a stable sort?

Merger

Insertion

 Both above

None of the above

An in place sorting algorithm is one that uses ___ arrays for storage

Two dimensional arrays

More than one array

No Additional Array

None of the above

Continuing sort has time complexity of ?

O(n)

O(n+k)

O(nlogn)

O(k)

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

In Sieve Technique we donot know which item is of interest

True

False

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

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

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

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

Question # 9 of 10 ( Start time: 07:45:36 AM ) Total Marks: 1

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

Sorting is one of the few problems where provable ________ bonds exits on

how fast we can sort,

Select correct option:

upper

lower

average

log n

single item from a larger set of _____________

Select correct option:

n items

phases

pointers

constant

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,

Select correct option:

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,

Select correct option:

divide-and-conquer

decrease and conquer

greedy nature

2-dimension Maxima

The sieve technique works in ___________ as follows

Select correct option:

phases

numbers

integers

routines

For the Sieve Technique we take time

Select correct option:

T(nk)

T(n / 3)

n^2

n/3

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

Analysis of Selection algorithm ends up with,

Select correct option:

T(n)

T(1 / 1 + n)

T(n / 2)

T((n / 2) + n)

Quiz Start Time: 07:23 PM
Time Left 90
sec(s)
Question # 1 of 10 ( Start time: 07:24:03 PM ) Total M a r k s: 1
In in-place sorting algorithm is one that uses arrays for storage :
Select correct option:
An additional array
No additional array
Both of above may be true according to algorithm
More than 3 arrays of one dimension.

Time Left 89
sec(s)
Question # 2 of 10 ( Start time: 07:25:20 PM ) Total M a r k s: 1
Which sorting algorithn is faster :
Select correct option:
O(n^2)
O(nlogn)
O(n+k)
O(n^3)

In stable sorting algorithm:
Select correct option:
One array is used
In which duplicating elements are not handled.
More then one arrays are required.
Duplicating elements remain in same relative posistion after sorting.

Counting sort has time complexity:
Select correct option:
O(n)
O(n+k)
O(k)
O(nlogn)

Counting sort is suitable to sort the elements in range 1 to k:
Select correct option:
K is large
K is small
K may be large or small
None

Memorization is :
Select correct option:
To store previous results for further use.
To avoid unnecessary repetitions by writing down the results of recursive calls and looking them again if needed later
To make the process accurate.
None of the above

The running time of quick sort depends heavily on the selection of
Select correct option:
No of inputs
Arrangement of elements in array
Size o elements
Pivot elements

Which may be stable sort:
Select correct option:
Bubble sort
Insertion sort
Both of above

In Quick sort algorithm, constants hidden in T(n lg n) are
Select correct option:
Large
Medium
Not known
small

Quick sort is
Select correct option:
Stable and In place
Not stable but in place
Stable and not in place
Some time in place and send some time stable

For the Sieve Technique we take time

T(nk)

T(n / 3)

n^2

n/3

The sieve technique is a special case, where the number of sub problems is just

Select correct option:

5

Many

1

Few

The reason for introducing Sieve Technique algorithm is that it illustrates a very important special case of,

Select correct option:

divide-and-conquer

decrease and conquer

greedy nature

2-dimension Maxima

Quick sort is

Select correct option:

Stable and In place

Not stable but in place

Stable and not in place

Some time in place and send some time stable

Memoization is :

Select correct option:

To store previous results for further use.

To avoid unnecessary repetitions by writing down the results of

recursive calls and looking them again if needed later

To make the process accurate.

None of the above

One Example of in place but not stable sort is

Quick

Heap

Merge

Bubble

The running time of quick sort depends heavily on the selection of

Select correct option:

No of inputs

Arrangement of elements in array

Size o elements

Pivot elements

 

Question # 9 of 10 ( Start time: 07:39:07 PM ) Total M a r k s: 1

In Quick sort algorithm,constants hidden in T(n lg n) are

Select correct option:

Large

Medium

Not known

Small

 

 Reply

Message

Permalink Reply by Manza Ali BSCS 8 on May 4, 2013 at 2:28pm

Today Quiz

Attachments:

 CS 502 today Quiz.doc, 34 KB

 Reply

 

Permalink Reply by + M.Tariq Malik on May 5, 2013 at 10:16am

Manza Ali thanks for sharing ur quiz 

 Reply

Message

Permalink Reply by + M.Tariq Malik on May 5, 2013 at 10:16am

BS100400183 : Manza Ali

Question # 1 of 10 ( Start time: 01:57:15 PM)

 

Total Marks: 1

The ancient Roman politicians understood an important principle of good algorithm design that is plan-sweep algorithm.

Select correct option:

True

False

BS100400183 : Manza Ali

Question # 2 of 10 ( Start time: 01:58:29 PM)

 

Total Marks: 1

In 2d-space a point is said to be ________if it is not dominated by any other point in that space.

Select correct option:

Member

Minimal

Maximal

Joint

BS100400183 : Manza Ali

 

 

 

Question # 3 of 10 ( Start time: 01:59:45 PM)

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)

BS100400183 : Manza Ali

Question # 4 of 10 ( Start time: 02:00:46 PM)

 

An algorithm is a mathematical entity that is dependent on a specific programming language.

Select correct option:

True not sure

False

BS100400183 : Manza Ali

 

 

 

Question # 5 of 10 ( Start time: 02:01:59 PM)

 

Total Marks: 1

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

BS100400183 : Manza Ali

Question # 6 of 10 ( Start time: 02:03:12 PM)

 

Total Marks: 1

The running time of an algorithm would not depend upon the optimization by the compiler but that of an implementation of the algorithm would depend on it.

Select correct option:

True

False not sure

BS100400183 : Manza Ali

 

 

 

Question # 7 of 10 ( Start time: 02:04:02 PM)

Total Marks:

f(n) and g(n) are asymptotically equivalent. This means that they have essentially the same __________ for large n.

Select correct option:

Results

Variables

Size

Growth rates

BS100400183 : Manza Ali

Question # 8 of 10 ( Start time: 02:04:56 PM)

 

Total Marks: 1

8n2 + 2n – 3 will eventually exceed c2*(n) no matter how large we make c2.

Select correct option:

True

False

BS100400183 : Manza Ali

Quiz Start Time: 01:57 PM

Question # 9 of 10 ( Start time: 02:05:45 PM)

 

Total Marks: 1

If we associate (x, y) integers pair to cars where x is the speed of the car and y is the negation of the price. High y value for a car means a ________ car.

Select correct option:

Fast

Slow

Expensive

Cheap

BS100400183 : Manza Ali

Question # 10 of 10 ( Start time: 02:06:58 PM)

 

Total Marks: 1

For the sieve technique we solve the problem,

Select correct option:

recursively

mathematically

precisely

accurately

 

Question #

The ancient Roman politicians understood an important principle of good algorithm design that is plan-sweep algorithm.

Select correct option:

True

False     (p27)     [Divide and Conquer]

 

Question #

In 2d-space a point is said to be ________if it is not dominated by any other point in that space.

Select correct option:

Member

Minimal

Maximal              (p11)

Joint

 

Question #

An algorithm is a mathematical entity that is dependent on a specific programming language.

Select correct option:

True

False     (p7)

 

Question #

The running time of an algorithm would not depend upon the optimization by the compiler but that of an implementation of the algorithm would depend on it.

True

False     (p13)

 

Question #

f(n) and g(n) are asymptotically equivalent. This means that they have essentially the same __________ for large n.

Results

Variables

Size

Growth rates     (p23)

 

Question #

8n2 + 2n – 3 will eventually exceed c₂(n) no matter how large we make c2.

True       (p25)

False

 

Question #

If we associate (x, y) integers pair to cars where x is the speed of the car and y is the negation of the price. High y value for a car means a ________ car.

Fast

Slow

Expensive

Cheap   (p11)

 Reply

 

Permalink Reply by Awais (MCS) on May 4, 2013 at 3:45pm

One more Current Solve Quiz lec 1 to 8

Question # 1 of 10
Analysis of Selection algorithm ends up with,
Select correct option:
T(n)    (p37)
T(1 / 1 + n)
T(n / 2)
T((n / 2) + n)

Question # 2 of 10
The function f(n)= n(logn+1)/2 is asymptotically equivalent to n log n. Hre Upper Bound means the function f(n) grows asymptotically ____________ faster than n log n.
Select correct option:
More
Quiet
Not    (p24)
At least

Question # 3 of 10
The running time of an algorithm would not depend upon the optimization by the compiler but that of an implementation of the algorithm would depend on it.
Select correct option:
True
False    (p7)

Question # 4 of 10 ( Start time: 03:26:18 PM )     Total Marks: 1
After sorting in merge sort algorithm, merging process is invoked.
Select correct option:
=True    (p27)
False

Question # 5 of 10
Asymptotic growth rate of the function is taken over_________ case running time.
Select correct option:
Best
Average
Worst (p14 Note sure)
Normal

Question # 6 of 10
In analysis of f(n)=n(n/5)+n-10 log n, f(n) is asymptotically equivalent to ________.
Select correct option:
n
2n
n+1
=    n2    (p23)

Question # 7 of 10
f(n) and g(n) are asymptotically equivalent. This means that they have essentially the same __________ for large n.
Select correct option:
Results
Variables
Size
=    Growth rates    (p23)

Question # 8 of 10
Algorithm is concerned with…….issues.
Select correct option:
Macro
Micro
Both Macro & Micro (p8)
Normal

Question # 9 of 10
We can not make any significant improvement in the running time which is better than that of brute-force algorithm.
Select correct option:
True
False

Question # 10 of 10
In addition to passing in the array itself to Merge Sort algorithm, we will pass in _________other arguments which are indices.
Select correct option:
Two    (p28)
Three
Four
Five

 

Cs502 Solved MCQS for MidTerm
Including Current Quizes
Question # 1
Word Algorithm comes from the name of the Muslim author:
Abu Ja’far Mohammad ibn Musaal-Khowarizmi. (p7)
Question # 2
Al-Khwarizmi’s work was written in a book titled
al Kitab al-mukhatasar fi hisab al-jabr wa’l-muqabalah (p7)
Question # 3
Analysis of Selection algorithm ends up with,
Select correct option:
T(n) (p37) T(1 / 1 + n) T(n / 2) T((n / 2) + n)
Question # 4
The function f(n)= n(logn+1)/2 is asymptotically equivalent to n log n. Hre Upper Bound means the function f(n)
grows asymptotically ____________ faster than n log n.
Select correct option:
More Quiet Not (p24) At least
Question # 5
The running time of an algorithm would not depend upon the optimization by the compiler but that of an
implementation of the algorithm would depend on it.
Select correct option:
True False (p7)
Question # 6
After sorting in merge sort algorithm, merging process is invoked.
Select correct option:
True (p27) False
Question # 7
Asymptotic growth rate of the function is taken over_________ case running time.
Select correct option:
Best
Average
Worst (p14)
Normal
Question # 8
In analysis of f(n)=n(n/5)+n-10 log n, f(n) is asymptotically equivalent to ________.
n
2n
n+1
n
2
(p23)
26 May 2013Question # 9
f(n) and g(n) are asymptotically equivalent. This means that they have essentially the same ______ for large n.
Results Variables Size Growth rates (p23)
Question # 10
Algorithm is concerned with _____ issues.
Macro Micro 1 Both Macro & Micro (p8) Normal
Question # 11
We can not make any significant improvement in the running time which is better than that of brute-force
algorithm.
True False (p18, p92)
Question # 12
In addition to passing in the array itself to Merge Sort algorithm, we will pass in _________other arguments which
are indices.
Two (p28) Three Four Five
Question # 13
For the worst-case running time analysis, the nested loop structure containing one “for” and one “while” loop,
might be expressed as a pair of _________nested summations.
1 (p14 ) 2 3 4
Question # 14
The O-notation is used to state only the asymptotic ________bounds.
Two Lower Upper (p25) Both lower & upper
Question # 15
Which of the following is calculated with big O notation?
Lower bounds Upper bounds (p25)
Both upper and lower bound Medium bounds
Question # 16
The Ω-notation allows us to state only the asymptotic ________ bounds.
Lower (p25) Upper
Both upper and lower bound Medium bounds
Question # 17
The time assumed for each basic operation to execute on RAM model of computation is _____
Infinite Continuous Constant (p10) Variable
Question # 18A
If the indices passed to merge sort algorithm are not equal, the algorithm may return immediately.
True False (p28)
Question #18B
If the indices passed to merge sort algorithm are ________,then this means that there is only one element to
sort.
Small Large Equal (p28) Not EqualQuestion # 19
Brute-force algorithm uses no intelligence in pruning out decisions.
True (p18) False
Question # 20
In analysis, the Lower Bound means the function grows asymptotically at least as fast as its largest term.
True (p24) False
Question # 21
In analysis, the Upper Bound means the function grows asymptotically no faster than its largest term.
True (p24) False
Question # 22
For small values of n, any algorithm is fast enough. Running time does become an issue when n gets large.
True (p14) Fast
Question # 23
The array to be sorted is not passed as argument to the merge sort algorithm.
True False (p28)
Question # 24
In simple brute-force algorithm, we give no thought to efficiency.
True (p11) False
Question # 25
The ancient Roman politicians understood an important principle of good algorithm design that is plan-sweep
algorithm.
True False (p27) [Divide and Conquer]
Question # 26
In 2d-space a point is said to be ________if it is not dominated by any other point in that space.
Select correct option:
Member Minimal Maximal (p11) Joint
Question # 27
An algorithm is a mathematical entity that is dependent on a specific programming language.
Select correct option:
True False (p7)
Question # 28
The running time of an algorithm would not depend upon the optimization by the compiler but that of an
implementation of the algorithm would depend on it.
True False (p13)
Question # 29
8n2
+ 2n – 3 will eventually exceed c2(n) no matter how large we make c2.
True (p25) False
Question # 30If we associate (x, y) integers pair to cars where x is the speed of the car and y is the negation of the price. High y
value for a car means a ________ car.
Fast Slow Expensive Cheap (p11)
Question # 31
The running time of quick sort depends heavily on the selection of:
No of inputs Arrangement of elements in array
Size of elements Pivot element (p49)
Question # 32
Which sorting algorithm is faster?
O(n^2) O(nlogn) O(n+k) (p58) O(n^3)
Question # 33
Q knapsack problem is called a “0-1” problem, because
Each item must be entirely accepted or rejected (p92)
Question # 34
Which statement is true?
Select correct option:
If a dynamic-programming problem satisfies the optimal-substructure property, then a locally optimal solution is
globally optimal.
If a greedy choice property satisfies the optimal-substructure property, then a locally optimal solution is globally
optimal.
Both of above (p77, p98) None of above
Question # 35
Merge sort is stable sort, but not an in-place algorithm
True (p54) False

Question # 36
In counting sort, once we know the ranks, we simply ______ numbers to their final positions in an output array.
Delete copy (p57) Mark arrange
Question # 37
Dynamic programming algorithms need to store the results of intermediate sub-problems. True (p75) False
Question # 38
A p × q matrix A can be multiplied with a q × r matrix B. The result will be a p × r matrix C. There are (p . r) total
entries in C and each takes _________ to compute.
O (q) O (1) (p84) O (n2
) O (n3
)
Question # 39
Due to left-complete nature of binary tree, heaps can be stored in
Link list Structure Array (p40) None of above
Question # 40
Efficient algorithm requires less computational _____
Memory Running Time Memory and Running Time EnergyQuestion # 41
Merge sort makes two recursive calls. Which statement is true after these recursive calls finish, but before the
merge step?
The array elements form a heap
Elements in each half of the array are sorted amongst themselves
Elements in the first half of the array are less than or equal to elements in the second half of the array
None of the above
Question # 42
Who invented Quick sort procedure?
Hoare Sedgewick Mellroy Coreman
Question # 43
Merge sort requires extra array storage. True (p54) False
o Mergesort is a stable algorithm but not an in-place algorithm. It requires extra array storage.
Question # 44
In which order we can sort?
Increasing order only decreasing order only
Increasing order or decreasing order both at the same time
Question # 45
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 (p37) n / 2 + n / 4
Question # 46
How much time merge sort takes for an array of numbers?
T(n^2) T(n) T( log n) T(n log n) (p40)
Question # 47A
Sieve Technique applies to problems where we are interested in finding a single item from a larger set of ___
n items (p34) phases pointers constant
Question # 47B
The sieve technique works in phases as follows. It applies to problems where we are interested in finding
a single item from a larger set of n items. (p34)
Question # 47C
The sieve technique works where we have to find _________ item(s) from a large input.
Single (p34) Two Three Similar
Question # 48
The sieve technique works in ___________ as follows
Phases (p34) numbers integers routines
Question # 49
For the heap sort, access to nodes involves simple _______________ operations.
Arithmetic (p41) binary algebraic logarithmic
Question # 50The analysis of Selection algorithm shows the total running time is indeed _________in n,
Arithmetic geometric linear (p39) orthogonal
Question # 51
Slow sorting algorithms run in,
T(n^2) (p39) T(n) T( log n) T(n log n)
Question # 52
A heap is a left-complete binary tree that conforms to the
Increasing order only decreasing order only heap order (log n) order
Question # 53
For the heap sort we store the tree nodes in
Level-order traversal (p40) in-order traversal pre-order traversal post-order traversal
Question # 54A
In Sieve Technique we do not know which item is of interest True (p34) False
Question # 54B
In Sieve Technique, we know the item of interest.
True False (p34)
Question # 55
Divide-and-conquer as breaking the problem into a small number of
Pivot Sieve smaller sub problems (p34) Selection
Question # 56
For the sieve technique we solve the problem,
Recursively (p34) mathematically precisely accurately
Question # 57
The reason for introducing Sieve Technique algorithm is that it illustrates a very important special case of,
Divide-and-conquer (p34) decrease and conquer greedy nature 2-dimension Maxima
Question # 58
Sorting is one of the few problems where provable _____ bonds exits on how fast we can sort,
Upper Lower (p39) Average log n
Question # 59
Sieve Technique can be applied to selection problem? True (p35) False
Question # 60
One of the clever aspects of heaps is that they can be stored in arrays without using any______
Pointers (p40) constants variables functions
Question # 61
Heaps can be stored in arrays without using any pointers; this is due to the ___ nature of the binary tree,
Left-complete (p40) right-complete tree nodes tree leaves
Question # 62How many elements do we eliminate in each time for the Analysis of Selection algorithm?
n / 2 elements (p36) (n / 2) + n elements n / 4 elements 2 n elements
Question # 63
The sieve technique is a special case, where the number of sub problems is just
5 Many 1 (p34) few
Question # 64
For the Sieve Technique we take time
T(nk) (p34) T(n / 3) n^2 n/3
Question # 65
The number of nodes in a complete binary tree of height h is
Select correct option:
2
^(h+1)
– 1
2 * (h+1) – 1
2 * (h+1)
((h+1) ^ 2) – 1
Question # 66
Random access machine or RAM is a/an _____
Machine build by Al-Khwarizmi Mechanical machine
Electronics machine Mathematical model (p10)
Question # 67
Analysis of Selection algorithm ends up with,
T(n)
T(1 / 1 + n)
T(n / 2)
T((n / 2) + n)
Question # 68
Continuation sort is suitable to sort the elements in range 1 to k
1. K is Large 2. K is not known 3. K may be small or large 4. K is small (p57)
Question # 69
Counting sort is suitable to sort the elements in range 1 to k:
K is large K is small (p57) K may be large or small None
Question # 70
Continuing sort has time complexity of?
1. O (n) (p58) 2. O(n+k) 3. O(nlogn)
Question # 71
Counting sort has time complexity:
O (n) (p58) O(n+k) O(k) O(nlogn)
Question # 72
Memoization is _____:
-To store previous results for further use. -To avoid unnecessary repetitions by writing down the results of recursive calls and looking them again if
needed later. (p74)
-To make the process accurate -None of the above
Question # 73
In Quick sort algorithm, constants hidden in T(n lg n) are:
Large Medium Not known Small (Ref)
Question # 74
Quick sort is based on divide and conquer paradigm; we divide the problem on base of pivot element and:
There is explicit combine process as well to conquer the solution.
No work is needed to combine the sub-arrays, the array is already sorted
Merging the subarrays None of above.
Question # 75
In RAM model instructions are executed _____
One after another (p10) Parallel Concurrent Random
Question # 76
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 (p37) exponent
Question # 77
________ is a graphical representation of an algorithm
Σ notation Θnotation Flowchart (Ref) Asymptotic notation
Question # 78
A RAM is an idealized machine with ______ random-access memory.
256MB 512MB An infinitely large (p10) 100GB

Question # 79
What type of instructions Random Access Machine (RAM) can execute? Choose best answer
Algebraic and logic Geometric and arithmetic
Arithmetic and logic (p10) Parallel and recursive

Question # 80
What will be the total number of max comparisons if we run brute-force maxima algorithm with n elements?
n
2
(p14) 2n/n n 8n

Question # 81
What is the solution to the recurrence T(n) = T(n/2)+n .
O(logn) O(n) O(nlogn) O(n2)

Question # 82
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 # 83
Consider the following Algorithm: Fun(n){ if (n=1) return 1 else return (n * Fun(n-1)) } Recurrence for the above
algorithm is:
nT(n-1)+1
2T(n-1)+1
T(n-1)+cn
T(n-1)+1
Question # 84
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 # 85
What is the total time to heapify?
Ο(log n) (p43) Ο(n log n) Ο(n2 log n) Ο(log2 n)

Question # 86
When we call heapify then at each level the comparison performed takes time
It will take Θ (1) (p43)
Time will vary according to the nature of input data
It cannot be predicted
It will take Θ (log n)
Question # 87
In Quick sort, we don’t have the control over the sizes of recursive calls
-True (p49) -False -Less information to decide -Either true or false

Question # 88
Is it possible to sort without making comparisons? Yes (p57) No

Question # 89
If there are Θ (n2) entries in edit distance matrix then the total running time is Θ (1) Θ (n
2
) (p84) Θ (n) Θ (n log n)

Question # 90
For Chain Matrix Multiplication we cannot use divide and conquer approach because,
We do not know the optimum k (p86)
We use divide and conquer for sorting only
We can easily perform it in linear time
Size of data is not given

Question # 91
The Knapsack problem belongs to the domain of _______________ problems.
Optimization (p91) NP Complete Linear Solution Sorting

Question # 92
Suppose we have three items as shown in the following table, and suppose the capacity of the knapsack is 50 i.e.
W = 50.
Item Value Weight
1 60 10
2 100 20
3 120 30
The optimal solution is to pick
Items 1 and 2
Items 1 and 3
Items 2 and 3
None of these
Question # 93
Theta asymptotic notation for T (n):
Select correct option:
Set of functions described by: c1g(n)<=f(n) for c1 some constant and n=n0
Set of functions described by c1g(n)>=f(n) for c1 some constant and n=n0
Theta for T(n)is actually upper and worst case complexity of the code
Set of functions described by: c1g(n)<=f(n)<=c2g(n) for c1 and c2 some constants and n=n0
Question # 94
A (an) ______ is a left-complete binary tree that conforms to the heap order.
Heap (page 40) Binary tree Binary search tree Array
Question # 95
A heap is a left-complete binary tree that conforms to the _________
increasing order only decreasing order only heap order (p40) (log n) order
Question # 96
Consider the following Algorithm: Fun(n){ if (n=1) return 1 else return (n * Fun(n-1)) } Recurrence for the above
algorithm is: Select correct option:
nT(n-1)+1
2T(n-1)+1
T(n-1)+cn
T(n-1)+1Question # 97
The recurrence relation of Tower of Hanoi is given below T(n)={1 if n=1 and 2T(n-1) if n >1 In order to move a
tower of 5 rings from one peg to another, how many ring moves are required?
Select correct option: 16 10 32 (p30) 31
Question # 98
In Quick Sort Constants hidden in T(n log n) are
1. Large 2. Medium 3. Small (Reference) 4. Not Known
Question # 99
In stable sorting algorithm:
One array is used
In which duplicating elements are not handled.
More than one arrays are required.
Duplicating elements remain in same relative position after sorting. (p54)
Question # 100
In in-place sorting algorithm is one that uses arrays for storage:
An additional array
No additional array (p54)
Both of above may be true according to algorithm
More than 3 arrays of one dimension
Question # 101
Which may be a stable sort?
1. Merger 2. Insertion 3. Both above (p54) 4. None of the above
Question # 102
An in place sorting algorithm is one that uses ________ arrays for storage
1. Two dimensional arrays 2. More than one array
3. No Additional Array (p54) 4. None of the above
Question # 103
Quick sort is _____
Stable and In place Not stable but in place (p54)
Stable and not in place Sometime in place and sometime stable
Question # 104
One Example of in place but not stable sort is
Quick (p54) Heap Merge Bubble
Question # 105
Which may be stable sort?
Bubble sort Insertion sort both of above (p54)
Question # 106
Merge sort is stable sort, but not an in-place algorithm True (p54) False
An in-place sorting algorithm is one that uses no additional array for storage. A sorting algorithm is stable if
duplicate elements remain in the same relative position after sorting. (p54)Bubble sort, insertion sort and selection sort are in-place sorting algorithms.
Bubble sort and insertion sort can be implemented as stable algorithms but selection sort cannot (without
significant modifications).
Mergesort is a stable algorithm but not an in-place algorithm. It requires extra array storage.
Quicksort is not stable but is an in-place algorithm.
Heapsort is an in-place algorithm but is not stable.
Question # 107
8n2
+ 2n − 3 grows asymptotically at least as fast as n
2
.
Question # 108
Given a set of points P = {p1, p2, . . . , pn} in 2-space, output the set of maximal points of P, i.e.,
those points pi such that pi is not dominated by any other point of P.
True (p11) False
Question # 109
While Sorting, the ordered domain means for any two input elements x and y ______ satisfies only.
x < y
x > y
x = y
All of the above (p34)
Question # 110
Brute-force algorithm for 2D-Maxima is operated by comparing ______ pairs of points.
Two Some Most All (p18)
Question # 111
Merge sort is based on ____
Brute-force Plan-sweep Axis-sweep Divide and Conqer (p27)
Question # 112
In the statement “if (P[i].x < P[j].x) & (P[i].y < P[j].y)”, the number of times elements of P are accessed is ____
1 2 3 4 (p14)
Question # 113
Al-Khawarizmi was a/an….
Artist Mathematician Astronomer KhalifahQuestion # 114
In Sorting the key value or attribute ____ from an ordered domain.
Must be Not always
ü The key value need not be a number. It can be any object from a totally ordered domain. (p39)
Question # 115
In Selection problem, the Sieve technique works in ____
Non-recursive manner Constant time
Phases (p34) One complete go
Question # 116
In max heap (for Heap Sort algorithm), when every time maximum element is removed from top we replace it with
____ leaf in the tree.
Second last Last (p41) First Any
Question # 117
If input “n” is odd, the median will be ____
(n+1)/2 (p34) n/2
Question # 118
The function f(n)= n(logn+1)/2 is asymptotically equivalent to n log n. Hre Upper Bound means the function f(n)
grows asymptotically ______ faster than n log n.
More Quiet Not (p23) At least
Question # 119
In asymptotical analysis of n(n – 3) and 4n*n, as n becomes large, the dominant (fastest growing) term is some
constant times ____.
n+1
n-1
n
n*n (p23)
Question # 120
In asymptotical analysis of n*(5 + 2)-3 , as n becomes large, the dominant (fastest growing) term is some constant
times ____.
n+1
n-1
n
n*n
Question # 121
A point p in 2-dimensional space is usually given by its integer coordinate(s)____________
Select correct option:
p.x only
p.y only
p.x & p.z
p.x & p.y (p10)
Question # 122Algorithm analysts know for sure about efficient solutions for NP-complete problems.
True False (p9)
Question # 123
In ____________ we have to find rank of an element from given input.
Select correct option:
Merge sort algorithm Selection problem (p34)
Brute force technique Plane Sweep algorithm
Question # 124
In Heap Sort algorithm, if heap property is violated _________
Select correct option:
We call Build heap procedure We call Heapify procedure (p41)
We ignore Heap property can never be violated
Question # 125
Upper bound requires that there exist positive constants c2 and n0 such that f(n) ____ c2n for all n <= n0
Select correct option:
Less than
Equal to or Less than (p25 => for all n >= n0)
Equal or Greater than
Greater than
Question # 126
A RAM is an idealized algorithm with takes an infinitely large random-access memory.
True False (p10 => A RAM is an idealized machine)
Question # 127
In simple brute-force algorithm, we give no thought to efficiency.
True (p11) False
Question # 128
_________ is one of the few problems, where provable lower bounds exist on how fast we can sort.
Select correct option:
Searching Sorting (p39)
Both Searching & Sorting Graphing
Question # 129
The total no of arguments passed to merge sort algorithm is _______
2
3 (p28 => Array itself + two indices)
4
5
Question # 130
While solving Selection problem, in Sieve technique we partition input data __________
In increasing order In decreasing order According to Pivot (p35) Randomly
Question # 131
The number of accesses to any element of space is not counted for the running time calculation of algorithm. True False
Question # 132
In merge sort algorithm, to merge two lists of size n/2 to a list of size n, takes ___________ time.
Theta (n) (p30) Theta log(n) Theta log2(n) Theta nlog(n)
Question # 133
In Heap Sort algorithm, Heapify procedure is ____________ in nature.
Recursive (p43) Non-Recursive
Question # 134
In Heap Sort algorithm, we call Build-heap procedure _________
Only once Twice Thrice As many times as we need
Question # 135
In merge sort algorithm, we split the array around the _________ index q.
Entring Mid (p28) Exiting Summing
Question # 136
The Iteration method is used for ______
Comparing sorting algorithms only Solving Recurrence relations (p31)
Merging elements in Merge sort Dividing elements in Merge sort
Question # 137
Rank of an element can be defined as ______
One minus the number of elements that are smaller
Two plus the number of elements that are greater
One plus the number of elements that are smaller (p34)
Two minus the number of elements that are smaller
Question # 138
f(n) is a set of functions such that there exist positive constants c1, c2 and n0 such that 0 <= c1g(n) <= f(n) <=
c2g(n) for all n >= n0 Then f(n) is asymptotically ______ g(n).
Select correct option:
Less than Greater than
Equivalent to (p23) Not equivalent to
Question # 139
Floor and ceiling are ____________ to calculate while analyzing algorithms.
Select correct option:
Very easy Usually considered difficult (p31)
Question # 140
In Heap Sort algorithm, the maximum levels an element can move upward is _________
Select correct option:
Theta (log n) (p43) Order (log n) Omega (log n) O (1) i.e. Constant time
Question # 141
In Heap Sort algorithm, the total running time for Heapify procedure is ____________Select correct option:
Theta (log n) Order (log n) (p43) Omega (log n) O (1) i.e. Constant time
Question # 142
For the worst-case running time analysis, the nested loop structure containing one “for” and one “while” loop,
might be expressed as a pair of _________nested summations.
Select correct option:
1 2 (p14) 3 4
Question # 143
In pseudo code, the level of details depends on intended audience of the algorithm.
True (p12) False
Final Term MCQS
Question # 1
A dense undirected graph is:
Select correct option:
A graph in which E = O (V2
) (Reference)
A graph in which E = O (V)
A graph in which E = O (log V)
All items above may be used to characterize a dense undirected graph
Question # 2
What algorithm technique is used in the implementation of Kruskal solution for the MST?
Greedy Technique (p142)
Divide-and-Conquer Technique
Dynamic Programming Technique
The algorithm combines more than one of the above techniques
Question # 16
A digraph is strongly connected under what condition?
A digraph is strongly connected if for every pair of vertices u, v e V, u can reach v .
A digraph is strongly connected if for every pair of vertices u, v e V, u can reach v and vice versa. (p135)
A digraph is strongly connected if for at least one pair of vertex u, v e V, u can reach v and vice versa.
A digraph is strongly connected if at least one third pair of vertices u, v e V, u can reach v and vice versa.
Question # 17
The relationship between number of back edges and number of cycles in DFS is,
Both are equal
Back edges are half of cycles
Back edges are one quarter of cycles
There is no relationship between no. of edges and cycles (p131)
Question # 18
Suppose that a graph G = (V,E) is implemented using adjacency lists. What is the complexity of a breadth-first
traversal of G? Select correct option:
O(|V |^2)
O(|V | |E|) O(|V |^2|E|)
O(|V | + |E|) (p116)
Question # 19
Forward edge is?
Select correct option:
(u, v) where u is a proper descendent of v in the tree.
(u, v) where v is a proper descendent of u in the tree. (p129)
(u, v) where v is a proper ancestor of u in the tree.
(u, v) where u is a proper ancestor of v in the tree.
Question # 20
Back edge is?
Select correct option:
(u, v) where v is an ancestor of u in the tree. (p128)
(u,v) where u is an ancestor of v in the tree.
(u, v) where v is an predecessor of u in the tree.
None of above
Question # 21
Cross edge is?
(u, v) where u and v are not ancestor of one another
(u, v) where u is ancestor of v and v is not descendent of u.
(u, v) where u and v are not ancestor or descendent of one another (p129)
(u, v) where u and v are either ancestor or descendent of one another.
Question # 22
If you find yourself in maze the better traversel approach will be?
Select correct option:
BFS
BFS and DFS both are valid (p119)
Level order
DFS

Question # 23
In digraph G=(V,E) ;G has cycle if and only if
Select correct option:
The DFS forest has forward edge.
The DFS forest has back edge (p131)
The DFS forest has both back and forward edge
BFS forest has forward edge
Question # 24
What is generally true of Adjacency List and Adjacency Matrix representations of graphs?
Select correct option:
Lists require less space than matrices but take longer to find the weight of an edge (v1,v2)
Lists require less space than matrices and they are faster to find the weight of an edge (v1, v2) (p116)
Lists require more space than matrices and they take longer to find the weight of an edge (v1, v2)
Lists require more space than matrices but are faster to find the weight of an edge (v1, v2)Question # 5
There is relationship between number of back edges and number of cycles in DFS
Select correct option:
Both are equal.
Cycles are half of back edges.
Cycles are one fourth of back edges.
There is no relationship between back edges and number of cycle (p131)
Question # 6
You have an adjacency list for G, what is the time complexity to compute Graph transpose G^T.?
Select correct option:
(V+E) (Reference)
V.E
V
E
Question # 7
Dijkstra’s algorithm:
Has greedy approach to find all shortest paths
Has both greedy and dynamic approach to find all shortest paths
Has greedy approach to compute single source shortest paths to all other vertices (p154)
Has both greedy and dynamic approach to compute single source shortest paths to all other vertices.
Question No: 25
Although it requires more complicated data structures, Prim’s algorithm for a minimum spanning tree is better
than Kruskal’s when the graph has a large number of vertices.
True False
Question No: 26
If a problem is in NP, it must also be in P.
True False (p178) unknown
Question No: 27
If a problem is in NP-complete, it must also be in NP.
True False
Question No: 28
Maximum number of vertices in a Directed Graph may be |V2
|
True False

Question No: 29
The Huffman algorithm finds a (n) _____________ solution.
Optimal (Reference) Non-optimal Exponential Polynomial

Question No: 30
The Huffman algorithm finds an exponential solution True False (Reference)

Question No: 31
The Huffman algorithm finds a polynomial solution True False (Reference)
Question No: 32 The codeword assigned to characters by the Huffman algorithm have the property that no codeword is the postfix
of any other. True False
Question No: 33
The codeword assigned to characters by the Huffman algorithm have the property that no codeword is the prefix
of any other. True (p101) False
Prefix Property:
The codewords assigned to characters by the Huffman algorithm have the property that no codeword is a prefix of
any other:
Question No: 48
Non-optimal or greedy algorithm for money change takes____________
O(k) (p99) O(kN) O(2k) O(N)
Question No: 49
The Huffman codes provide a method of encoding data inefficiently when coded using ASCII standard.
True False (p99)
o The Huffman codes provide a method of encoding data efficiently.
Question No: 50
Using ASCII standard the string “abacdaacacwe” will be encoded with __________ bits
Select correct option:
64
128
96 (p101 12×8=96)
120
Question No: 51
Using ASCII standard the string abacdaacac will be encoded with __________ bits.
80 (p99) 160 320 100
o Consider the string “ abacdaacac”. if the string is coded with ASCII codes, the message length would be10
× 8 = 80 bits.
Question No: 52
Using ASCII standard the string abacdaacac will be encoded with 160 bits. True False (p99)
Question No: 53
Using ASCII standard the string abacdaacac will be encoded with 320 bits. True False (p99)
Question No: 54
Using ASCII standard the string abacdaacac will be encoded with 100 bits. True False (p99)
Question No: 55
Using ASCII standard the string abacdaacac will be encoded with 32 bytes. True False (p99)
Question No: 56
The greedy part of the Huffman encoding algorithm is to first find two nodes with smallest frequency.
True (p100) FalseQuestion No: 57
The greedy part of the Huffman encoding algorithm is to first find two nodes with character frequency.
True False (p100)
Question No: 58
The greedy part of the Huffman encoding algorithm is to first find two nodes with larger frequency.
True False
Question No: 59
Dijkestra’s single source shortest path algorithm works if all edges weights are non-negative and there are negative
cost cycles. True False

Question No: 60
Dijkestra s single source shortest path algorithm works if all edges weights are non-negative and there are no
negative cost cycles. True (p159) False
Question No: 61
Dijkestra s single source shortest path algorithm works if all edges weights are negative and there are no negative
cost cycles. True False
Question No: 62
Floyd-Warshall algorithm is a dynamic programming algorithm; the genius of the algorithm is in the clever
recursive formulation of the shortest path problem. True (p162) False
Question No: 63
Floyd-Warshall algorithm, as in the case with DP algorithms, we avoid recursive evaluation by generating a table
for dij
(k)
True (p164) False
Question No: 64
The term coloring came from the original application which was in map drawing. True (p173) False
The term “coloring” came from the original application which was in architectural design. True False
Question No: 65
In the clique cover problem, for two vertices to be in the same group, they must be _____ each other.
Apart from Far from Near to Adjacent to (p176)
Question No: 66
In the clique cover problem, for two vertices to be in the same group, they must be adjacent to each other.
True False
Question No: 67
In the clique cover problem, for two vertices to be in the same group, they must be apart from each other.
True False (p176)
Question No: 68
The difference between Prims algorithm and Dijkstra s algorithm is that Dijkstra s algorithm uses a different key.
True (p156) FalseQuestion No: 69
The difference between Prim s algorithm and Dijkstra s algorithm is that Dijkstra s algorithm uses a same key.
True False (p156)
Question No: 70
You have an adjective list for G, what is the time complexity to computer graph transpose G^T.?
(V + E ) (p138)
Question No: 71
Given an adjacency list for G, it is possible to compute G T
in Θ(V + E) time.
It takes O(log V) to extract a vertex from the priority queue.
Question No: 72
Overall time for Kruskal is Θ(E log E) = Θ(E log V) if the graph is sparse. (p149) True

Question No: 73
An optimization problem is one in which you want to find,
Not a solution
An algorithm
Good solution
The best solution

Question No: 74
Although it requires more complicated data structures, Prim’s algorithm for a minimum spanning tree is better than
Kruskal’s when the graph has a large number of vertices.
True False

Question No: 75
If a graph has v vertices and e edges then to obtain a spanning tree we have to delete
v edges.
v – e + 5 edges
v + e edges.
None of these

Question No: 76
Huffman algorithm uses a greedy approach to generate an antefix code T that minimizes the expected length B (T)
of the encoded string. True False (p102)
Question No: 77
Huffman algorithm uses a greedy approach to generate a postfix code T that minimizes the expected length B (T)
of the encoded string. True False (p102)
Question No: 78
Huffman algorithm uses a greedy approach to generate a prefix code T that minimizes the expected length B (T) of
the encoded string. True (p102) False
Question No: 79
Bellman-Ford allows negative weights edges and negative cost cycles. True False (p159)
o Bellman-Ford allows negative weights edges and no negative cost cycles.Question No: 80
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
Question No: 81
After partitioning array in Quick sort, pivot is placed in a position such that
Values smaller than pivot are on left and larger than pivot are on right (Ref)
Values larger than pivot are on left and smaller than pivot are on right
Pivot is the first element of array
Pivot is the last element of array
Question No: 82
Dynamic programming algorithms need to store the results of intermediate sub-problems.True False
Question No: 83
Which statement is true?
If a dynamic-programming problem satisfies the optimal-substructure property, then a locally optimal solution is
globally optimal.
If a greedy choice property satisfies the optimal-substructure property, then a locally optimal solution is
globally optimal.
Both of above None of above
Question No: 84
What general property of the list indicates that the graph has an isolated vertex?
There is Null pointer at the end of list.
The Isolated vertex is not handled in list.
Only one value is entered in the list.
There is at least one null list.
Question No: 85
Depth first search is shortest path algorithm that works on un-weighted graphs.True False (p153)
o The breadth-first-search algorithm is a shortest-path algorithm that works on un-weighted graphs.
Question No: 86
Which is true statement?
Select correct option:
Breadth first search is shortest path algorithm that works on un-weighted graphs (p153)
Depth first search is shortest path algorithm that works on un-weighted graphs.
Both of above are true.
None of above are true.
Question # 9
Which is true statement in the following?
Kruskal algorithm is multiple source technique for finding MST.
Kruskal’s algorithm is used to find minimum spanning tree of a graph, time complexity of this algorithm is O(EV)
Both of above Kruskal’s algorithm (choose best non-cycle edge) is better than Prim’s (choose best tree edge) when the
graph has relatively few edges.
Question # 11
Kruskal’s algorithm (choose best non-cycle edge) is better than Prim’s (choose best tree edge) when the graph has
relatively few edges.
True False
Question # 8
What is the time complexity to extract a vertex from the priority queue in Prim’s algorithm?
Select correct option:
O (log E)
(V)
(V+E)
O (log V) (p152)
(1) In Prim’s algorithm, the additional information maintained by the algorithm is the length of the shortest edge
from vertex v to points already in the tree.
a) True b) False c) unknown
(2) Although it requires more complicated data structures, Prim’s algorithm for a minimum spanning tree is better
than Kruskal’s when the graph has a large number of vertices.
a) True b) False c) unknown
(3) If a problem is NP-complete, it must also be in NP.
a) True b) False c) unknown
(4) Which statement is true?
(i) The running time of Bellman-Ford algorithm is T (VE)
(ii) Both Dijkstra’s algorithm and Bellman-Ford are based on performing repeated relaxations
(iii) The 0-1 knapsack problem is hard to solve
Only i Only iii Both i and iii All of these
5) Which of the following arrays represent descending (max) heaps?
i. [10,7,7,2,4,6] ii. [10,7,6,2,4,7]
iii. [10,6,7,2,4,6] iv. [6,6,7,2,4,10]
Only ii Only iv Both ii and iv Both i and iii
6. Which of the following statement(s) is/are correct?
(a) O(n log n + n2) = O(n2). (b) O(n log n + n2) = O(n2 log 2n)
(c) O(c n2) = O(n2) where c is a constant. (d) O(c n2) = O(c) where c is a constant.
(e) O(c) = O(1) where c is a constant.
Only (a) & (e) Both (c) and (e)
7. Which of the shortest path algorithms would be most appropriate for finding paths in the graph with negative
edge weights and cycles?
i.Dijkstra’s Algorithm
ii. Bellman-Ford Algorithm
iii. Floyd Warshall Algorithm
Only ii Only iii Both ii & iii9. Suppose we have two problems A and B .Problem A is polynomial-time reducible and problem B is NPcomplete.
If we reduce problem A into B then problem A becomes NP-complete Yes No
12. Edge (u, v) is a forward edge if
u is a proper descendant of v in the tree
v is a proper descendant of u in the tree
None of these
14. If, in a DFS forest of digraph G = (V, E), f[u] = f[v] for an edge (u, v) ? E then the edge is called
Back edge Forward edge Cross Edge Tree Edge None of these
16. Best and worst case times of an algorithm may be same. True False
17. Can an adjacency matrix for a directed graph ever not be square in shape? Yes No
Question No: 44
Consider the following Huffman Tree. The binary code for the string TEA is:
10 00 010
011 00 010
10 00 110
11 10 110
Question No: 45
Can an adjacency matrix for a directed graph ever not be square in shape? Yes No
o No. since we want to describe the relationship between each node and each other node, we need precisely
n^2 matrix entries.
Question No: 34
Shortest path problems can be solved efficiently by modeling the road map as a graph. True False

Question No: 35
Dijkstra’s algorithm is operates by maintaining a subset of vertices. True False
String Encoding
TEA 10 00 010
SEA 011 00 010
TEN 10 00 110

Question # 1
Word Algorithm comes from the name of the Muslim author:
Abu Ja’far Mohammad ibn Musaal-Khowarizmi. (p7) 

Question # 2
Al-Khwarizmi’s work was written in a book titled
al Kitab al-mukhatasar fi hisab al-jabr wa’l-muqabalah (p7) 

Question # 3
Analysis of Selection algorithm ends up with,
Select correct option:
  T(n)    (p37) 
T(1 / 1 + n)
T(n / 2)
T((n / 2) + n)

Question # 4
The function f(n)= n(logn+1)/2 is asymptotically equivalent to n log n. Hre Upper Bound means the function f(n) grows asymptotically ____________ faster than n log n.
Select correct option:
More
Quiet
  Not  (p24) 
At least

Question # 5
The running time of an algorithm would not depend upon the optimization by the compiler but that of an
implementation of the algorithm would depend on it.
Select correct option:
True
  False  (p7) 

Question # 6
After sorting in merge sort algorithm, merging process is invoked.
Select correct option:
  True  (p27) 
False

Question # 7
Asymptotic growth rate of the function is taken over_________ case running time.
Select correct option:
Best
Average
  Worst     (p14 Note sure) 
Normal

Question # 8

In analysis of f(n)=n(n/5)+n-10 log n, f(n) is asymptotically equivalent to ________.
Select correct option:
n
2n
n+1
  n2  (p23) 

Question # 9

f(n) and g(n) are asymptotically equivalent. This means that they have essentially the same __________ for larg n.
Select correct option:
Results
Variables
Size
  Growth rates   (p23) 

Question # 10
Algorithm is concerned with…….issues.
Select correct option:
Macro
Micro
  Both Macro & Micro   (p8) 
Normal

Question # 11
We can not make any significant improvement in the running time which is better than that of brute-force
algorithm.
Select correct option:
True
False 

Question # 12
In addition to passing in the array itself to Merge Sort algorithm, we will pass in _________other arguments which
are indices.
Select correct option:
  Two  (p28) 
Three
Four
Five

Question # 13
For the worst-case running time analysis, the nested loop structure containing one “for” and one “while” loop,
might be expressed as a pair of _________nested summations.
1   (p14 ) 
2
3
4

Question # 14

The O-notation is used to state only the asymptotic ________bounds.
Two
Lower
Upper   (p25) 
Both lower & upper

Question # 15
Efficient algorithm requires less computational…….
Memory
Running Time
Memory and Running Time 
Energy

Question # 16
Consider the following Algorithm: Fun(n){ if (n=1) return 1 else return (n * Fun(n-1)) } Recurrence for the above
algorithm is:
nT(n-1)+1
2T(n-1)+1
T(n-1)+cn
T(n-1)+1 

Question # 17
The time assumed for each basic operation to execute on RAM model of computation is—–
Infinite
Continuous
Constant  (p10) 
Variable

Question # 18
If the indices passed to merge sort algorithm are not equal, the algorithm may return immediately.
True
False  (p28) 

Question # 19
Brute-force algorithm uses no intelligence in pruning out decisions.
True  (p18)    
False

Question # 20
In analysis, the Lower Bound means the function grows asymptotically at least as fast as its largest term.
True    
False

Question # 21
In analysis, the Upper Bound means the function grows asymptotically no faster than its largest term.
True  (p24)    
False

Question # 22
For small values of n, any algorithm is fast enough. Running time does become an issue when n gets large.
True  (p14)    
Fast

Question # 23
The array to be sorted is not passed as argument to the merge sort algorithm.

True
False  (p28) 

Question # 24
In simple brute-force algorithm, we give no thought to efficiency.
True  (p11)    
False

Question # 25
The ancient Roman politicians understood an important principle of good algorithm design that is plan-sweep
algorithm.
Select correct option:
True
False  (p27)  
[Divide and Conquer]

 

1:-Median is not useful measure of central tendency of given input set especially when the distribution of values is highly skewed.

1:-True

2:-False

2:-For small values of n, any algorithm is fast enough. Running time does become an issue when n gets large.

True

Fast

3:-A RAM is an idealized algorithm with takes an infinitely large random-access memory.

True

False

4:-In the statement “output P[i].x, P[i].y”, the number of times elements of P are accessed is _____________

1

2

3

4

5:-A point p is said to be dominated by point q if p.x = q.x & p.y = q.y

True

False     not sure

6:-In Selection algorithm, we assume pivot selection takes theta __________ running time.

n

n2

n3

log(n)

7:-The sieve technique works where we have to find _________ item(s) from a large input.

Single

Two\

Three

Similar

8:-While Sorting, the ordered domain means for any two input elements x and y _________ satisfies only.

x < y

x > y

x = y

All of the above

 

9:-In Selection problem, the Sieve technique works in ___________

Non-recursive manner

Constant time

Phases

One complete go

10:-The sieve technique is a special case, where the number of sub-problems is just ________

1

2

3

4

 

he array to be sorted is not passed as argument to the merge sort algorithm.

Select correct option:

True

False*

 

Question # 2 of 10 ( Start time: 09:21:49 PM )      Total Marks: 1

In pseudo code, the level of details depends on intended audience of the algorithm.

Select correct option:

True*

False

 

 

Question # 3 of 10 ( Start time: 09:23:11 PM )      Total Marks: 1

In Selection problem, the Sieve technique ___________

Select correct option:

Adds some more input items each time

Do not work recursively

Do not uses Divide and Conquer approach

Eliminates undesired data items each time*

 

 

 

Question # 4 of 10 ( Start time: 09:24:20 PM )      Total Marks: 1

In Sorting the key value or attribute __________ from an ordered domain.

Select correct option:

Must be*

Not always

 

 

Question # 5 of 10 ( Start time: 09:24:56 PM )      Total Marks: 1

In analysis, the Lower Bound means the function grows asymptotically at least as fast as its largest term.

Select correct option:

True*

False

 

 

Question # 6 of 10 ( Start time: 09:25:53 PM )      Total Marks: 1

In Sieve Technique, we know the item of interest.

Select correct option:

True

False*

 

 

Question # 7 of 10 ( Start time: 09:27:11 PM )      Total Marks: 1

In selection problem, the rank of an element will be its _________ position if we sort the input data.

Select correct option:

first

final*

Second last

Last

 

 

Question # 8 of 10 ( Start time: 09:28:41 PM )      Total Marks: 1

……..of reference is an important fact of current processor technology.

Select correct option:

Defining

Assigning

Formality

Locality*

 

 

Question # 9 of 10 ( Start time: 09:31:00 PM )    Total Marks: 1

In the analysis of Selection algorithm, we get the convergent ______________ series.

Select correct option:

Harmonic

Linear

Arithmetic

Geometric*

 

Question # 10 of 10 ( Start time: 09:29:34 PM )  Total Marks: 1

f(n) is a set of functions such that there exist positive constants c1, c2 and n0 such that 0 <= c1g(n) <= f(n) <= c2g(n) for all n _ n0 Then f(n) is asymptotically _____________ g(n).

Select correct option:

Less than*

 Reply

Message

Permalink Reply by + M.Tariq Malik on December 3, 2013 at 10:19pm

Note:- ” * ” Shows correct Answer here

Question # 10 of 10 ( Start time: 09:09:52 PM )  Total Marks: 1

Before sweeping a vertical line in plane sweep approach, in start sorting of the points is done in increasing order of their _______coordinates.

Select correct option:

X*

Y

Z

X & Y

 

 

 

Question # 1 of 10 ( Start time: 09:12:05 PM )  Total Marks: 1

To find maximal points in brute-force algorithm, each point of the space is compared against ________of that space.

Select correct option:

One other point

All other points*

Few other points

Most of the other points

 

 

Question # 2 of 10 ( Start time: 09:12:57 PM )  Total Marks: 1

The O-notation is used to state only the asymptotic ________bounds.

Select correct option:

Two

Lower

Upper*

Both lower & upper

 

Question # 3 of 10 ( Start time: 09:13:11 PM )  Total Marks: 1

In Sorting the key value or attribute __________ from an ordered domain.

Select correct option:

Must be*

Not always

 

 

Question # 4 of 10 ( Start time: 09:13:39 PM )  Total Marks: 1

In analysis, the Upper Bound means the function grows asymptotically no faster than its largest term.

Select correct option:

True*

False

 

 

Question # 5 of 10 ( Start time: 09:13:58 PM )  Total Marks: 1

Approach of solving geometric problems by sweeping a line across the plane is called ________sweep.

Select correct option:

Line

Plane*

Cube

Box

 

 

Question # 6 of 10 ( Start time: 09:14:14 PM )  Total Marks: 1

If pj dominates pi and pi dominates ph then pj also dominates ph. It means dominance relation is ___________

Select correct option:

Transitive*

Non Transitive

Equation

Symbolic

 

 

Question # 7 of 10 ( Start time: 09:14:49 PM )  Total Marks: 1

In plane sweep approach, a vertical line is swept across the 2d-plane from__________.

Select correct option:

Right to Left

Left to Right*

Top to Bottom

Bottom to Top

 

 

 

Question # 8 of 10 ( Start time: 09:15:09 PM )  Total Marks: 1

_________ is one of the few problems, where provable lower bounds exist on how fast we can sort.

Select correct option:

Searching

Sorting*

Both Searching & Sorting

Graphing

 

 

Question # 9 of 10 ( Start time: 09:15:34 PM )  Total Marks: 1

Median is not useful measure of central tendency of given input set especially when the distribution of values is highly skewed.

Select correct option:

True

False*

 

 

Question # 10 of 10 ( Start time: 09:15:53 PM )  Total Marks: 1

Asymptotic growth rate of the function is taken over_________ case running time.

Select correct option:

Best

Average*

Worst

Normal

 Reply

Message

Permalink Reply by + M.Tariq Malik on December 3, 2013 at 10:19pm

Question # 1 of 10 ( Start time: 09:02:33 PM )  Total Marks: 1

Sorting is performed on the basis of __________

Select correct option:

Computational resources

Asymptotic notation

Summation

Some key value or attribute

Answer:-   4

 

 

Question # 2 of 10 ( Start time: 09:05:42 PM )  Total Marks: 1

Approach of solving geometric problems by sweeping a line across the plane is called ________sweep.

Select correct option:

Line

Plane

Cube

Box

Ans… 2

 

Question # 3 of 10 ( Start time: 09:06:20 PM )  Total Marks: 1

While Sorting, the ordered domain means for any two input elements x and y _________ satisfies only.

Select correct option:

x < y

x > y

x = y

All of the above

Ans.  4

 

 

Question # 4 of 10 ( Start time: 09:06:43 PM )  Total Marks: 1

In Selection problem, the Sieve technique ___________

Select correct option:

Adds some more input items each time

Do not work recursively

Do not uses Divide and Conquer approach

Eliminates undesired data items each time

Ans 4

 

Question # 5 of 10 ( Start time: 09:07:12 PM )  Total Marks: 1

In the statement “if (P[i].x < P[j].x) & (P[i].y < P[j].y)”, the number of times elements of P are accessed is _____________

Select correct option:

1

2

3

4  *

 

Question # 6 of 10 ( Start time: 09:07:36 PM )  Total Marks: 1

The sieve technique works where we have to find _________ item(s) from a large input.

Select correct option:

Single

Two

Three*

Similar

 

 

 

Question # 7 of 10 ( Start time: 09:08:13 PM )  Total Marks: 1

Quick sort is best from the perspective of Locality of reference.

Select correct option:

True*

False

 

 

Question # 8 of 10 ( Start time: 09:08:37 PM )  Total Marks: 1

The O-notation is used to state only the asymptotic ________bounds.

Select correct option:

Two

Lower

Upper*

Both lower & upper

 

 

Question # 9 of 10 ( Start time: 09:08:59 PM )  Total Marks: 1

_________ is one of the few problems, where provable lower bounds exist on how fast we can sort.

Select correct option:

Searching

Sorting*

Both Searching & Sorting

Graphing

 

 

Question # 10 of 10 ( Start time: 09:09:52 PM )  Total Marks: 1

Before sweeping a vertical line in plane sweep approach, in start sorting of the points is done in increasing order of their _______coordinates.

Select correct option:

X*

Y

Z

X & Y

 

 

 

 

 Reply

Message

Permalink Reply by + M.Tariq Malik on December 3, 2013 at 10:20pm

Question # 1 of 10 ( Start time: 01:57:15 PM)

The ancient Roman politicians understood an important principle of good algorithm design that is plan-sweep algorithm.

Select correct option:

True

False   (p27)     [Divide and Conquer]

 

Question # 2 of 10 ( Start time: 01:58:29 PM)

In 2d-space a point is said to be ________if it is not dominated by any other point in that space.

Select correct option:

Member

Minimal

Maximal        (p11)

Joint

 

Question # 3 of 10 ( Start time: 01:59:45 PM)

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)

 

Question # 4 of 10 ( Start time: 02:00:46 PM)

An algorithm is a mathematical entity that is dependent on a specific programming language.

Select correct option:

True

False        (p7)

 

 

 

 

 

Question # 5 of 10 ( Start time: 02:01:59 PM)

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

 

Question # 6 of 10 ( Start time: 02:03:12 PM)

The running time of an algorithm would not depend upon the optimization by the compiler but that of an implementation of the algorithm would depend on it.

Select correct option:

True

False       (p13)

 

Question # 7 of 10 ( Start time: 02:04:02 PM)

f(n) and g(n) are asymptotically equivalent. This means that they have essentially the same __________ for large n.

Select correct option:

Results

Variables

Size

Growth rates           (p23)

 

Question # 8 of 10 ( Start time: 02:04:56 PM)

8n2 + 2n – 3 will eventually exceed c2*(n) no matter how large we make c2.

Select correct option:

True    (p25)

False

 

Question # 9 of 10 ( Start time: 02:05:45 PM)

If we associate (x, y) integers pair to cars where x is the speed of the car and y is the negation of the price. High y value for a car means a ________ car.

Select correct option:

Fast

Slow

Expensive

Cheap          (p11)

 

Question # 10 of 10 ( Start time: 02:06:58 PM)

For the sieve technique we solve the problem,

Select correct option:

recursively

mathematically

precisely

accurately

 

+++++++++++++++++++

 

Question # 1 of 10
Analysis of Selection algorithm ends up with,
Select correct option:
T(n)    (p37)
T(1 / 1 + n)
T(n / 2)
T((n / 2) + n)

Question # 2 of 10
The function f(n)= n(logn+1)/2 is asymptotically equivalent to n log n. Hre Upper Bound means the function f(n) grows asymptotically ____________ faster than n log n.
Select correct option:
More
Quiet
Not    (p24)
At least

Question # 3 of 10
The running time of an algorithm would not depend upon the optimization by the compiler but that of an implementation of the algorithm would depend on it.
Select correct option:
True
False    (p7)

Question # 4 of 10 ( Start time: 03:26:18 PM )     Total Marks: 1
After sorting in merge sort algorithm, merging process is invoked.
Select correct option:
=True    (p27)
False

Question # 5 of 10
Asymptotic growth rate of the function is taken over_________ case running time.
Select correct option:
Best
Average
Worst (p14 Note sure)
Normal

Question # 6 of 10
In analysis of f(n)=n(n/5)+n-10 log n, f(n) is asymptotically equivalent to ________.
Select correct option:
n
2n
n+1
=    n2    (p23)

Question # 7 of 10
f(n) and g(n) are asymptotically equivalent. This means that they have essentially the same __________ for large n.
Select correct option:
Results
Variables
Size
=    Growth rates    (p23)

Question # 8 of 10
Algorithm is concerned with…….issues.
Select correct option:
Macro
Micro
Both Macro & Micro (p8)
Normal

Question # 9 of 10
We can not make any significant improvement in the running time which is better than that of brute-force algorithm.
Select correct option:
True
False

Question # 10 of 10
In addition to passing in the array itself to Merge Sort algorithm, we will pass in _________other arguments which are indices.
Select correct option:
Two    (p28)
Three
Four
Five

+++++++++++++

Consider the following Algorithm: Fun(n){ if (n=1) return 1 else return (n * Fun(n-1)) } Recurrence for the above algorithm is:

nT(n-1)+1

2T(n-1)+1

T(n-1)+cn

T(n-1)+1

 

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

 

Brute-force algorithm uses no intelligence in pruning out decisions.

True

False

 

f(n) and g(n) are asymptotically equivalent. This means that they have essentially the same __________ for large n.

Results

Variables

Size

Growth rates

 

In analysis, the Lower Bound means the function grows asymptotically at least as fast as its largest term.

True

False

 

Efficient algorithm requires less computational…….

Memory

Running Time

Memory and Running Time

Energy

 

The O-notation is used to state only the asymptotic ________bounds.

Two

Lower

Upper

Both lower & upper

 

For the worst-case running time analysis, the nested loop structure containing one “for” and one “while” loop, might be expressed as a pair of _________nested summations.

1 (not confirm )

2

3

4

+++++++++++++++++

 Reply

Message

Permalink Reply by + M.Tariq Malik on December 3, 2013 at 10:20pm

Question # 1 of 10
Analysis of Selection algorithm ends up with,
Select correct option:
T(n)    (p37)
T(1 / 1 + n)
T(n / 2)
T((n / 2) + n)

Question # 2 of 10
The function f(n)= n(logn+1)/2 is asymptotically equivalent to n log n. Hre Upper Bound means the function f(n) grows asymptotically ____________ faster than n log n.
Select correct option:
More
Quiet
Not    (p24)
At least

Question # 3 of 10
The running time of an algorithm would not depend upon the optimization by the compiler but that of an implementation of the algorithm would depend on it.
Select correct option:
True
False    (p7)

Question # 4 of 10 ( Start time: 03:26:18 PM )     Total Marks: 1
After sorting in merge sort algorithm, merging process is invoked.
Select correct option:
=True    (p27)
False

Question # 5 of 10
Asymptotic growth rate of the function is taken over_________ case running time.
Select correct option:
Best
Average
Worst (p14 Note sure)
Normal

Question # 6 of 10
In analysis of f(n)=n(n/5)+n-10 log n, f(n) is asymptotically equivalent to ________.
Select correct option:
n
2n
n+1
=    n2    (p23)

Question # 7 of 10
f(n) and g(n) are asymptotically equivalent. This means that they have essentially the same __________ for large n.
Select correct option:
Results
Variables
Size
=    Growth rates    (p23)

Question # 8 of 10
Algorithm is concerned with…….issues.
Select correct option:
Macro
Micro
Both Macro & Micro (p8)
Normal

Question # 9 of 10
We can not make any significant improvement in the running time which is better than that of brute-force algorithm.
Select correct option:
True
False

Question # 10 of 10
In addition to passing in the array itself to Merge Sort algorithm, we will pass in _________other arguments which are indices.
Select correct option:
Two    (p28)
Three
Four
Five

+++++++++++++

 Reply

Message

Permalink Reply by + M.Tariq Malik on December 3, 2013 at 10:20pm

The array to be sorted is not passed as argument to the merge sort algorithm.

Select correct option:

True

False*

 

Question # 2 of 10 ( Start time: 09:21:49 PM )      Total Marks: 1

In pseudo code, the level of details depends on intended audience of the algorithm.

Select correct option:

True*

False

 

 

Question # 3 of 10 ( Start time: 09:23:11 PM )      Total Marks: 1

In Selection problem, the Sieve technique ___________

Select correct option:

Adds some more input items each time

Do not work recursively

Do not uses Divide and Conquer approach

Eliminates undesired data items each time*

 

 

 

Question # 4 of 10 ( Start time: 09:24:20 PM )      Total Marks: 1

In Sorting the key value or attribute __________ from an ordered domain.

Select correct option:

Must be*

Not always

 

 

Question # 5 of 10 ( Start time: 09:24:56 PM )      Total Marks: 1

In analysis, the Lower Bound means the function grows asymptotically at least as fast as its largest term.

Select correct option:

True*

False

 

 

Question # 6 of 10 ( Start time: 09:25:53 PM )      Total Marks: 1

In Sieve Technique, we know the item of interest.

Select correct option:

True

False*

 

 

Question # 7 of 10 ( Start time: 09:27:11 PM )      Total Marks: 1

In selection problem, the rank of an element will be its _________ position if we sort the input data.

Select correct option:

first

final*

Second last

Last

 

 

Question # 8 of 10 ( Start time: 09:28:41 PM )      Total Marks: 1

……..of reference is an important fact of current processor technology.

Select correct option:

Defining

Assigning

Formality

Locality*

 

 

Question # 9 of 10 ( Start time: 09:31:00 PM )    Total Marks: 1

In the analysis of Selection algorithm, we get the convergent ______________ series.

Select correct option:

Harmonic

Linear

Arithmetic

Geometric*

 

Question # 10 of 10 ( Start time: 09:29:34 PM )  Total Marks: 1

f(n) is a set of functions such that there exist positive constants c1, c2 and n0 such that 0 <= c1g(n) <= f(n) <= c2g(n) for all n _ n0 Then f(n) is asymptotically _____________ g(n).

Select correct option:

Less than*

Greater than

Equivalent to

Not equivalent to

 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

 

1
CS502- Fundamentals of Algorithms
Solved MCQS
From Midterm Papers
May- 24 – 2013
MC100401285 Moaaz.pk@gmail.com Mc100401285@vu.edu.pk PSMD01
MIDTERM EXAMINATION
Fall 2011
CS502- Fundamentals of Algorithms
Question No: 1 ( Marks: 1 ) – Please choose one
Due to left complete nature of binary tree, the heap can be stored in
► Arrays (Page 40)
► Structures
► Link Lis
►Stack
Question No: 1 ( Marks: 1 ) – Please choose one
What type of instructions Random Access Machine (RAM) can execute?
►Algebraic and logic
►Geometric and arithmetic
►Arithmetic and logic (Page 10)
►Parallel and recursive
Question No: 1 ( 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 (Page 86)
►We use divide and conquer for sorting only
►We can easily perform it in linear time
►Size of data is not given
Question No: 1 ( Marks: 1 ) – Please choose one
What is the total time to heapify?
► Ο(log n) (Page 43)
► Ο(n log n)
► Ο(n2
log n)
► Ο(log2
n)2
Question No: 1 ( Marks: 1 ) – Please choose one
word Algorithm comes from the name of the muslim author ____________
►Abu Ja’far Mohammad ibn Musa al-Khowarizmi.
Question No: 1 ( Marks: 1 ) – Please choose one
al-Khwarizmi’s work was written in a book titled _______________
►al Kitab al-mukhatasar fi hisab al-jabr wa’l-muqabalah
MIDTERM EXAMINATION
Spring 2010
CS502- Fundamentals of Algorithms
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 (Page 10)

Question No: 2 ( Marks: 1 ) – Please choose one
_______________ is a graphical representation of an algorithm
► notation
► notation
► Flowchart Click here for detail
► 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 (Page 10)
► 100GB

SQ3
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 (Rep)
► Parallel and recursive

Question No: 5 ( Marks: 1 ) – Please choose one
What will be the total number of max comparisons if we run brute-force maxima algorithm with n elements?
►
►
► (Page 14)
►

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) (Page 37)
► O(nlogn)
► O(n
2
)

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(n
3
)
► O(n
2
log n)
► O(n2
)
Question No: 8 ( Marks: 1 ) – Please choose one
What is the total time to heapify?
► Ο(log n) rep
► Ο(n log n)
► Ο(n2
log n)
► Ο(log2
n)

2
n
2
n
n
8 n4
Question No: 9 ( 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: 10 ( Marks: 1 ) – Please choose one
When we call heapify then at each level the comparison performed takes time
► It will take Θ (1) (Page 43)
► Time will vary according to the nature of input data
► It can not be predicted
► It will take Θ (log 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 (Page 40)
► 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 (Page 57)
► No

Question No: 13 ( Marks: 1 ) – Please choose one
If there are Θ (n2
) entries in edit distance matrix then the total running time is
► Θ (1)
► Θ (n2
) Click here for detail
► Θ (n)
► Θ (n log n)
5
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 (Page 86)
► 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 (Page 91)
► NP Complete
► Linear Solution
► Sorting

Question No: 16 ( Marks: 1 ) – Please choose one
Suppose we have three items as shown in the following table, and suppose the capacity of the knapsack is 50
i.e. W = 50.
Item Value Weight
1 60 10
2 100 20
3 120 30
The optimal solution is to pick
► Items 1 and 2
► Items 1 and 3
► Items 2 and 3 (correct)
► None of these6
MIDTERM EXAMINATION
Spring 2010
CS502- Fundamentals of Algorithms
Question No: 1 ( Marks: 1 ) – Please choose one
For the Sieve Technique we take time
► T(nk) (Page 34)
►T(n / 3)
►n^2
►n/3
Question No: 1 ( Marks: 1 ) – Please choose one
Sieve Technique applies to problems where we are interested in finding a single item
from a larger set of _____________
Select correct option:
►n items (Page 34)
►phases
►pointers
►constant
Question No: 1 ( Marks: 1 ) – Please choose one
______________ graphical representation of algorithm.
►asymptotic
►Flowchart (rep)
Question No: 1 ( Marks: 1 ) – Please choose one
who invented the quick sort
►C.A.R. Hoare Click here for detail
Question No: 1 ( Marks: 1 ) – Please choose one
main elements to a divide-and-conquer
►Divide, conquer, combine (Page 27)
Question No: 1 ( Marks: 1 ) – Please choose one
Mergesort is a stable algorithm but not an in-place algorithm.
►True (Page 54)
►false7
Question No: 1 ( Marks: 1 ) – Please choose one
Counting sort the numbers to be sorted are in the range 1 to k where k is small.
►True (Page 57)
►False
MIDTERM EXAMINATION
Spring 2007
CS502- Fundamentals of Algorithms
Question No: 1 ( Marks: 1 ) – Please choose one
Total time for heapify is:
►Ο (log
2
n)
►Ο (n log n)
►Ο (n
2
log n)
►Ο (log n) Rep
Question No: 1 ( Marks: 1 ) – Please choose one
If an algorithm has a complexity of log
2
n + nlog
2
n + n. we could say that it has complexity
►O(n)
►O( n log
2
n)
►O(3)
►O( log
2
( log
2
n ))
►O ( log
2
n)
Question No: 1 ( Marks: 1 ) – Please choose one
In RAM model instructions are executed
►One after another (Page 10)
►Parallel
►Concurrent
►Random 8
Question No: 1 ( Marks: 1 ) – Please choose one
In selection algorithm, because we eliminate a constant fraction of the array with each phase, we get the
►Convergent geometric series (Page 37)
►Divergent geometric series
►None of these
Question No: 1 ( Marks: 1 ) – Please choose one
Due to left-complete nature of binary tree, heaps can be stored in
►Link list
►Structure
►Array (Page 40)
►None of above
CS609- System Programming
Midterm Quizzes (Quiz No.1 & 2)
Quiz No.1 (04 – MAY – 2013)
Question No: 1 ( Marks: 1 ) – Please choose one
The time assumed for each basic operation to execute on RAM model of computation is—–
Infinite
Continuous
Constant (Page 10)
Variable
Question No: 1 ( Marks: 1 ) – Please choose one
If the indices passed to merge sort algorithm are not equal, the algorithm may return immediately.
True
False (Page 28)
Question No: 1 ( Marks: 1 ) – Please choose one
Brute-force algorithm uses no intelligence in pruning out decisions.
True (Page 18)
False9
Question No: 1 ( Marks: 1 ) – Please choose one
In analysis, the Upper Bound means the function grows asymptotically no faster than its largest term.
True (Page 24)
False
Question No: 1 ( Marks: 1 ) – Please choose one
For small values of n, any algorithm is fast enough. Running time does become an issue when n gets large.
True (Page 14)
Fast
Question No: 1 ( Marks: 1 ) – Please choose one
The array to be sorted is not passed as argument to the merge sort algorithm.
True
False
Question No: 1 ( Marks: 1 ) – Please choose one
In simple brute-force algorithm, we give no thought to efficiency.
True (Page 11)
False

Question No: 1 ( Marks: 1 ) – Please choose one
The ancient Roman politicians understood an important principle of good algorithm design that is plan-sweep
algorithm.
True
False (Page 27) [Divide and Conquer]
Question No: 1 ( Marks: 1 ) – Please choose one
In 2d-space a point is said to be ________if it is not dominated by any other point in that space.
Member
Minimal
Maximal (Page 11)
Joint
Question No: 1 ( Marks: 1 ) – Please choose one
An algorithm is a mathematical entity that is dependent on a specific programming language.
True
False (Page 7)10
Question No: 1 ( Marks: 1 ) – Please choose one
The running time of an algorithm would not depend upon the optimization by the compiler but that of an
implementation of the algorithm would depend on it.
True (Page 13)
False
Question No: 1 ( Marks: 1 ) – Please choose one
F (n) and g (n) are asymptotically equivalent. This means that they have essentially the same __________ for
large n.
Results
Variables
Size
Growth rates (Page 23)
Question No: 1 ( Marks: 1 ) – Please choose one
8n2 + 2n – 3 will eventually exceed c2*(n) no matter how large we make c2.
True (Page 25)
False
Question No: 1 ( Marks: 1 ) – Please choose one
If we associate (x, y) integers pair to cars where x is the speed of the car and y is the negation of the price. High
y value for a car means a ________ car.
Fast
Slow
Expensive
Cheap (Page 11)
Question No: 1 ( Marks: 1 ) – Please choose one
The function f(n)= n(logn+1)/2 is asymptotically equivalent to n log n. Here Upper Bound means the function
f(n) grows asymptotically ____________ faster than n log n.
More
Quiet
Not (Page 24)
At least
Question No: 1 ( Marks: 1 ) – Please choose one
After sorting in merge sort algorithm, merging process is invoked.
Select correct option:
True (Page 28)
False 11
Question No: 1 (Marks: 1) – Please choose one
Asymptotic growth rate of the function is taken over_________ case running time.
Select correct option:
Best
Average
Worst (Page 14)
Normal
Question No: 1 (Marks: 1) – Please choose one
In analysis of f (n) =n (n/5) +n-10 log n, f (n) is asymptotically equivalent to ________.
n
2n
n+1
n2 (Page 23)
Question No: 1 (Marks: 1 ) – Please choose one
Algorithm is concerned with…….issues.
Macro
Micro
Both Macro & Micro (Page 8)
Normal
Question No: 1 (Marks: 1) – Please choose one
We cannot make any significant improvement in the running time which is better than that of brute-force
algorithm.
True
False (Page 18)
Question No: 1 ( Marks: 1 ) – Please choose one
In addition to passing in the array itself to Merge Sort algorithm, we will pass in _________other arguments
which are indices.
Two (Page 28)
Three
Four
Five
Question No: 1 ( Marks: 1 ) – Please choose one
Consider the following Algorithm: Fun(n){ if (n=1) return 1 else return (n * Fun(n-1)) } Recurrence for the
above algorithm is:12
nT(n-1)+1
2T(n-1)+1
T(n-1)+cn
T(n-1)+1
Question No: 1 ( Marks: 1 ) – Please choose one
In analysis, the Lower Bound means the function grows asymptotically at least as fast as its largest term.
True (Page 24)
False
Question No: 1 ( Marks: 1 ) – Please choose one
Efficient algorithm requires less computational…….
Memory
Running Time
Memory and Running Time (Page 9)
Energy
Question No: 1 ( Marks: 1 ) – Please choose one
The O-notation is used to state only the asymptotic ________bounds.
Two
Lower
Upper (Page 25)
Both lower & upper
Question No: 1 ( Marks: 1 ) – Please choose one
For the worst-case running time analysis, the nested loop structure containing one “for” and one “while” loop,
might be expressed as a pair of _________nested summations.
1
2 (Page 16)
3
4
Question No: 1 ( Marks: 1 ) – Please choose one
Before sweeping a vertical line in plane sweep approach, in start sorting of the points is done in increasing
order of their _______coordinates.
X (Page 18)
Y
Z
X & Y13
Question No: 1 ( Marks: 1 ) – Please choose one
Brute-force algorithm for 2D-Maxima is operated by comparing ________ pairs of points.
Two
Some
Most
All (Page 18)
Question No: 1 ( Marks: 1 ) – Please choose one
The function f(n)=n(logn+1)/2 is asymptotically equivalent to nlog n. Here Lower Bound means function f(n)
grows asymptotically at ____________ as fast as nlog n.
Normal
Least (Page 23)
Most
All
Question No: 1 ( Marks: 1 ) – Please choose one
The definition of Theta-notation relies on proving ___________asymptotic bound.
One
Lower
Upper
Both lower & upper (Page 25) rep
Question No: 1 ( Marks: 1 ) – Please choose one
In plane sweep approach, a vertical line is swept across the 2d-plane and _______structure is used for holding
the maximal points lying to the left of the sweep line.
Array
Queue
Stack (Page 18)
Tree
Question No: 1 ( Marks: 1 ) – Please choose one
Algorithm analysts know for sure about efficient solutions for NP-complete problems.
Select correct option:
True
False (Page 9)14
Quiz No.1 (2012)
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
The number of nodes in a complete binary tree of height h is
2^(h+1) – 1 (Page 40)
2 * (h+1) – 1
2 * (h+1)
((h+1) ^ 2) – 1
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
The analysis of Selection algorithm shows the total running time is indeed ________in n,
arithmetic
geometric
linear (Page 37)
orthogonal
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
A (an) _________ is a left-complete binary tree that conforms to the heap order
heap (Page 40)
binary tree
binary search tree
array
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Analysis of Selection algorithm ends up with,
T(n) (Page 37)
T(1 / 1 + n)
T(n / 2)
T((n / 2) + n)
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
For the sieve technique we solve the problem,
recursively (Page 34)
mathematically
precisely
accurately15
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
A heap is a left-complete binary tree that conforms to the ___________
increasing order only
decreasing order only
heap order (Page 40)
(log n) order
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
In which order we can sort?
increasing order only
decreasing order only
increasing order or decreasing order (Page 39)
both at the same time
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Divide-and-conquer as breaking the problem into a small number of
pivot
Sieve
smaller sub problems (Page 34)
Selection
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
For the heap sort we store the tree nodes in
level-order traversal (Page 40)
in-order traversal
pre-order traversal
post-order traversal
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
The sieve technique works in ___________ as follows
Phases (Page 34)
numbers
integers
routines16
CS502 – Fundamentals of Algorithms
Quiz No.1 12-11-2012
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
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
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Heaps can be stored in arrays without using any pointers; this is due to the ____________ nature of the binary
tree,
left-complete (Page 40)
right-complete
tree nodes
tree leaves
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Sieve Technique can be applied to selection problem?
True (Page 35)
False
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
In Sieve Technique we do not know which item is of interest
True (Page 34)
False
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
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 (Page 37)
exponent17
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
For the heap sort, access to nodes involves simple _______________ operations.
arithmetic (Page 41)
binary
algebraic
logarithmic
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Slow sorting algorithms run in,
T(n^2) (Page 39)
T(n)
T( log n)
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
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 (Page 37)
n / 2 + n / 4
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
The sieve technique is a special case, where the number of sub problems is just
5
many
1 (Page 34)
few
Question No: 1 of 10 (Marks: 1) – Please choose one
How many elements do we eliminate in each time for the Analysis of Selection algorithm?
(n / 2)+n elements
(n / 2) elements (Page 37)
n / 4 elements
2 n elements
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
One of the clever aspects of heaps is that they can be stored in arrays without using any _______________.
pointers (Page 40)
constants
variables
functions18
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
How much time merge sort takes for an array of numbers?
T(n^2)
T(n)
T( log n)
T(n log n) (Page 40)
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
The reason for introducing Sieve Technique algorithm is that it illustrates a very important special case of,
divide-and-conquer (Page 34)
decrease and conquer
greedy nature
2-dimension Maxima
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
In Sieve Technique we do not know which item is of interest
True (Page 34) rep
False
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Theta asymptotic notation for T (n) :
Set of functions described by: c1g(n)Set of functions described by c1g(n)>=f(n) for c1 s
Theta for T(n)is actually upper and worst case comp (Not sure)
Set of functions described by:
c1g(n)
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Memoization is?
To store previous results for future use
To avoid this unnecessary repetitions by writing down the results of recursive calls and looking them up
again if we need them later (page 74)
To make the process accurate
None of the above
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Which sorting algorithm is faster
O (n log n) Page 26
O n^2
O (n+k)
O n^319
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Quick sort is
Stable & in place
Not stable but in place (Page 54)
Stable but not in place
Some time stable & some times in place
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
One example of in place but not stable algorithm is
Merger Sort
Quick Sort (Page 54)
Continuation Sort
Bubble Sort
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Cont sort is suitable to sort the elements in range 1 to k
K is Large
K is not known
K may be small or large
K is small (Page 57)
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
In place stable sorting algorithm.
If duplicate elements remain in the same relative position after sorting (Page 54)
One array is used
More than one arrays are required
Duplicating elements not handled
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Which may be a stable sort?
Merger
Insertion (Page 54)
Both above
None of the above
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
An in place sorting algorithm is one that uses ___ arrays for storage
Two dimensional arrays
More than one array
No Additional Array (Page 54)
None of the above20
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Sieve Technique applies to problems where we are interested in finding a single item from a larger set of
_____________
n items (Page 34)
phases
pointers
constant
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Sorting is one of the few problems where provable ________ bonds exits on how fast we can sort,
upper
lower (Page 39)
average
log n
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Counting sort has time complexity:
O(n) (Page 58)
O(n+k)
O(k)
O(nlogn)
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
The running time of quick sort depends heavily on the selection of
No of inputs
Arrangement of elements in array
Size o elements
Pivot elements (Page 49)
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Which may be stable sort:
Bubble sort
Insertion sort
Both of above (Page 54)21
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
One Example of in place but not stable sort is
Quick (Page 54)
Heap
Merge
Bubble
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
In Quick Sort Constants hidden in T(n log n) are
Large
Medium
Small Click here for detail
Not Known
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Quick sort is based on divide and conquer paradigm; we divide the problem on base of pivot element and:
There is explicit combine process as well to conquer the solution.
No work is needed to combine the sub-arrays, the array is already sorted
Merging the sub arrays
None of above. (Page 51)
Ref: – random choices for the pivot element and each choice have an equal probability of 1/n of occurring. So
we can modify the above recurrence to compute an average rather than a max22
CS501 – Quiz No.2 (Spring 2013)
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
A point p in 2-dimensional space is usually given by its integer coordinate(s)____________
p.x only
p.y only
p.x & p.z
p.x & p.y (Page 10)
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
In ____________ we have to find rank of an element from given input.
Merge sort algorithm
Selection problem (Page 34)
Brute force technique
Plane Sweep algorithm
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
In Heap Sort algorithm, if heap property is violated _________
We call Build heap procedure
We call Heapify procedure
We ignore
Heap property can never be violated
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Upper bound requires that there exist positive constants c2 and n0 such that f(n) ____ c2n for all n <= n0(ye
question ghalat lag raha hai mujhae
Less than
Equal to or Less than (Page 25)
Equal or Greater than
Greater than
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
A RAM is an idealized algorithm with takes an infinitely large random-access memory.
True
False (Page 10)23
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
_________ is one of the few problems, where provable lower bounds exist on how fast we can sort.
Searching
Sorting (Page )
Both Searching & Sorting
Graphing
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Floor and ceiling are ____________ to calculate while analyzing algorithms.
Very easy
Usually considered difficult (Page 31)
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
In Heap Sort algorithm, the maximum levels an element can move upward is _________
Theta (log n) (Page 43)
Order (log n)
Omega (log n)
O (1) i.e. Constant time
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
A point p in 2-dimensional space is usually given by its integer coordinate(s)____________
p.x only p.y
only p.x & p.z
p.x & p.y (Page 17)
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
In Heap Sort algorithm, the total running time for Heapify procedure is ____________
Theta (log n) (Page 43)
Order (log n)
Omega (log n)
O (1) i.e. Constant time
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Algorithm is a mathematical entity, which is independent of a specific machine and operating system.
True
False (Page 7)24
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
While Sorting, the ordered domain means for any two input elements x and y _________ satisfies only.
x < y
x > y
x = y
All of the above (Page 39)
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Quick sort is best from the perspective of Locality of reference.
True (Page 9)
False
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
Sorting can be in _________
Increasing order only
Decreasing order only
Both Increasing and Decreasing order (Page 39)
Random order
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
In Heap Sort algorithm, we build _______ for ascending sort.
Max heap (Page 41)
Min heap
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
In Sieve Technique, we know the item of interest.
True
False (Page 34)
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
While solving Selection problem, in Sieve technique we partition input data __________
In increasing order
In decreasing order
According to Pivot (Page 35)
Randomly25
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
In pseudo code, the level of details depends on intended audience of the algorithm.
True (Page 12)
False
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
The sieve technique works where we have to find _________ item(s) from a large input.
Single (Page 34)
Two
Three
Similar
Question No: 1 of 10 ( Marks: 1 ) – Please choose one
If the indices passed to merge sort algorithm are ________,then this means that there is only one element to
sort.
Small
Large
Equal (Page 28)
Not Equal