CS502 - Fundamentals of Algorithms VU Online Quiz MCQs

CS502 Fundamentals of Algorithms
Question # 1 of 10 ( Start time: 09:46:15 PM ) Total Marks: 1
In Selection algorithm, we assume pivot selection takes theta __________ running time.
Select correct option:
n     ( answer)
n2
n3
log(n)


Question # 2 of 10 ( Start time: 09:47:10 PM ) Total Marks: 1
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.
Select correct option:
Normal
Least
Most   ( answer)
All


Question # 3 of 10 ( Start time: 09:48:39 PM ) Total Marks: 1
While solving Selection problem, in Sieve technique we choose pivot ___________
Select correct option:
Minimum element
Maximum element
Randomly   ( answer)
Average element


Question # 4 of 10 ( Start time: 09:49:25 PM ) Total Marks: 1
Asymptotic growth rate of the function is taken over_________ case running time.
Select correct option:
Best
Average
Worst   ( answer)
Normal


Question # 5 of 10 ( Start time: 09:50:00 PM ) Total Marks: 1
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
3
4   ( answer) not cnfrm


Question # 6 of 10 ( Start time: 09:51:26 PM ) Total Marks: 1
8n2 + 2n - 3 will eventually exceed c2*(n) no matter how large we make c2.
Select correct option:
True  ( answer)
False


Question # 7 of 10 ( Start time: 09:52:37 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    ( answer)


In ____________ we have to find rank of an element from given input.
Select correct option:
Merge sort algorithm
Slection problem   ( answer)
Brute force technique
Plane Sweep algorithm


Question # 9 of 10 ( Start time: 09:54:47 PM ) Total Marks: 1
In addition to passing in the array, the other arguments passed to Merge Sort algorithm are indices of the _________ array that we are to sort.
Select correct option:
First
Sub   ( answer)
Main & Sub
Sub & Main


Question # 10 of 10 ( Start time: 09:56:10 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    ( answer)
Joint
May 9, 2014


CHIEF ADMIN
+Komple"Chief Admin
CS502 Fundamentals of Algorithms Quiz No. 1, File 3
Question # 1 of 10 ( Start time: 10:09:04 PM ) Total Marks: 1
If input “n” is odd, the median will be _________
Select correct option:
(n+1)/ 2 (Answer)
n/2


Question # 2 of 10 ( Start time: 10:09:04 PM ) Total Marks: 1
When writing pseudo code, those _______are omitted that detract from the main ideas of the algorithm.
Select correct option:
Essentials
Details (Answer)
Summaries
Inputs


Question # 3 of 10 ( Start time: 10:10:55 PM ) Total Marks: 1
Recurrence can be described in terms of a tree.
Select correct option:

Yes (Answer)
No


Question # 4 of 10 ( Start time: 10:11:52 PM ) Total Marks: 1
In RAM computation model, RAM stands for Random Access Model.
Select correct option:
True

False (Answer)


Question # 5 of 10 ( Start time: 10:12:24 PM ) Total Marks: 1
An algorithm is a mathematical entity that is dependent on a specific programming language.
Select correct option:
True

False (Answer)


Question # 6 of 10 ( Start time: 10:13:39 PM ) Total Marks: 1
Rank of an element can be defined as ____________
Select correct option:
One minus the number of elements that are smaller
Two plus the number of elements that are greater
One plus no of elements that are smaller (Answer)
Two minus the number of elements that are smaller


Question # 7 of 10 ( Start time: 10:14:37 PM ) Total Marks: 1
After sorting in merge sort algorithm, merging process is invoked.
Select correct option:

True (Answer)
False


Question # 8 of 10 ( Start time: 10:15:09 PM ) Total Marks: 1
Algorithm is a mathematical entity, which is independent of a specific machine and operating system.
Select correct option:

True (Answer)
False


Question # 9 of 10 ( Start time: 10:15:39 PM ) Total Marks: 1
Sieve technique is very important special case of Divide-and-Conquer strategy.
Select correct option:
True (Answer)
False


Question # 10 of 10 ( Start time: 10:16:09 PM ) Total Marks: 1
For small values of n, any algorithm is fast enough. Running time does become an isuue when n gets large.
Select correct option:
True (Answer)
Fast

May 9, 2014


CHIEF ADMIN
+Komple"Chief Admin
CS502 Fundamentals of Algorithms Quiz No. 1,  File 5





Question # 1 of 10 ( Start time: 10:37:05 PM ) Total Marks: 1
Pseudo code of algorithms are to be read by ___________.
Select correct option:
People ok
RAM
Computer
Compiler


Question # 2 of 10 ( Start time: 10:37:35 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 ok


Question # 3 of 10 ( Start time: 10:38:54 PM ) Total Marks: 1
After sorting in merge sort algorithm, merging process is invoked.
Select correct option:
True ok
False


Question # 4 of 10 ( Start time: 10:39:19 PM ) Total Marks: 1
In the statement “output P[i].x, P[i].y”, the number of times elements of P are accessed is _____________
Select correct option:
1
2 ok
3
4


Question # 5 of 10 ( Start time: 10:39:42 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 ok
Second last
Last


Question # 6 of 10 ( Start time: 10:40:03 PM ) Total Marks: 1
........of reference is an important fact of current processor technology.
Select correct option:
Defining
Assigning
Formality
Locality ok


Question # 7 of 10 ( Start time: 10:40:39 PM ) Total Marks: 1
In Selection problem, the Sieve technique works in ___________
Select correct option:
Non-recursive manner
Constant time
Phases ok
One complete go


Question # 8 of 10 ( Start time: 10:41:07 PM ) Total Marks: 1
Brute-force algorithm for 2D-Maxima is operated by comparing ________ pairs of points.
Select correct option:
Two
Some
Most
All ok


Question # 9 of 10 ( Start time: 10:42:21 PM ) Total Marks: 1
Floor and ceiling are ____________ to calculate while analyzing algorithms.
Select correct option:
Very easy
Usually considered difficult ok


Question # 10 of 10 ( Start time: 10:42:58 PM ) Total Marks: 1
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 ok
At least


Question # 1 of 10 ( Start time: 10:51:54 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 # 2 of 10 ( Start time: 10:52:29 PM ) Total Marks: 1
Al-Khwarizmi was a/an.......
Select correct option:
Artist
Mathematician ok
Astronomer
Khalifah


Question # 3 of 10 ( Start time: 10:52:56 PM ) Total Marks: 1
In merge sort algorithm, we split the array around the _________ index q.
Select correct option:
Entring
Mid ok
Exiting
Summing


Question # 4 of 10 ( Start time: 10:54:06 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 ok
Both Searching & Sorting
Graphing


Question # 5 of 10 ( Start time: 10:55:29 PM ) Total Marks: 1
In asymptotical analysis of n*(5 + 2) – 3 , as n becomes large, the dominant (fastest growing) term is some constant times ________
Select correct option:
n_1
n
n+1
n*n


Question # 6 of 10 ( Start time: 10:56:41 PM ) Total Marks: 1
The total running time for Selection algorithm is ___________
Select correct option:
Quadratic
Linear ok
Geometric
Exponential


Question # 7 of 10 ( Start time: 10:57:12 PM ) Total Marks: 1
When writing pseudo code, those _______are omitted that detract from the main ideas of the algorithm.
Select correct option:
Essentials
Details ok
Summaries
Inputs


Question # 8 of 10 ( Start time: 10:57:35 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 ok


Question # 9 of 10 ( Start time: 10:57:58 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 ok
False


 In asymptotical analysis of n(n - 3) and 4n*n, as n becomes large, the dominant (fastest growing) term is some constant times________.
Select correct option:
n+1
n-1
n                     ok
n*n

CS502 Fundamentals of Algorithms Quiz No. 1,  File 7





Question # 1 of 10 ( Start time: 11:04:26 PM ) Total Marks: 1
In merge sort algorithm, we split the array around the _________ index q.
Select correct option:
Entring
Mid    ok
Exiting
Summing


Question # 2 of 10 ( Start time: 11:04:41 PM ) Total Marks: 1
___________ provides us more accurate result when input values are not closer with each other.
Select correct option:
Average
Median ok


Question # 3 of 10 ( Start time: 11:05:30 PM ) Total Marks: 1
Recurrence can be described in terms of a tree.
Select correct option:
Yes ok
No


Question # 4 of 10 ( Start time: 11:05:51 PM ) Total Marks: 1
The time assumed for each basic operation to execute on RAM model of computation is__________
Select correct option:
Infinite ok
Continuous
Constant
Variable


Question # 5 of 10 ( Start time: 11:06:17 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 ok
Non Transitive
Equation
Symbolic


Question # 6 of 10 ( Start time: 11:06:46 PM ) Total Marks: 1
Selection algorithm takes theta __________
Select correct option:
(n2)
(n) ok
log(n)
nlog(n)


Question # 7 of 10 ( Start time: 11:07:28 PM ) Total Marks: 1
Algorithm analysts know for sure about efficient solutions for NP-complete problems.
Select correct option:
True
False ok


Question # 8 of 10 ( Start time: 11:08:12 PM ) Total Marks: 1
Brute-force algorithm uses no intelligence in pruning out decisions.
Select correct option:
True ok
False


Question # 9 of 10 ( Start time: 11:08:52 PM ) Total Marks: 1
In RAM computation model, RAM stands for Random Access Model.
Select correct option:
True
False ok


Question # 10 of 10 ( Start time: 11:09:10 PM ) Total Marks: 1
For solving Selection problem, we introduced Sieve technique due to __________
Select correct option:
Using Decrease and Conquer strategy
Avoiding to sort all input data
Eliminating Rank of an element
Using Brute-force approach

CS502 Fundamentals of Algorithms Quiz No. 1,  File 8






Question # 1 of 10 ( Start time: 11:25:00 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 # 3 of 10 ( Start time: 11:26:39 PM ) Total Marks: 1
The number of accesses to any element of space is not counted for the running time calculation of algorithm.
Select correct option:
True
False


Question # 4 of 10 ( Start time: 11:28:01 PM ) Total Marks: 1
Quick sort is best from the perspective of Locality of reference.
Select correct option:
True ok
False


Question # 5 of 10 ( Start time: 11:28:34 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 ok


Question # 6 of 10 ( Start time: 11:28:56 PM ) Total Marks: 1
___________ provides us more accurate result when input values are not closer with each other.
Select correct option:
Average
Median ok


Question # 7 of 10 ( Start time: 11:29:28 PM ) Total Marks: 1
The brute-force algorithm for 2D-Maxima runs in order O(___) time.
Select correct option:
n
n(log n)
n*n ok
n3


Question # 8 of 10 ( Start time: 11:30:58 PM ) Total Marks: 1
Rank of an element can be defined as ____________
Select correct option:
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 ok
Two minus the number of elements that are smaller


Question # 9 of 10 ( Start time: 11:31:29 PM ) Total Marks: 1
In pseudo code, the level of details depends on intended audience of the algorithm.
Select correct option:
True ok
False


Question # 10 of 10 ( Start time: 11:32:03 PM ) Total Marks: 1
In Sieve technique, we solve the problem _________
Select correct option:
In recursive manner
Non recursively
Using Merge Sort algorithm
Using Brute force technique

CS502 Fundamentals of Algorithms Quiz No. 1 , File 9







Question # 3 of 10 ( Start time: 11:25:20 PM ) Total Marks: 1
When writing pseudo code, those _______are omitted that detract from the main ideas of the algorithm.
Select correct option:
Essentials
Details
Summaries
Inputs


Question # 4 of 10 ( Start time: 11:26:29 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


Question # 5 of 10 ( Start time: 11:27:11 PM ) Total Marks: 1
If the indices passed to merge sort algorithm are ________,then this means that there is only one element to sort.
Select correct option:
Small
Large
Equal
Not Equal


Question # 6 of 10 ( Start time: 11:27:46 PM ) Total Marks: 1
Algorithm is a sequence of computational steps that .....the input into output.
Select correct option:
Merge
Assign
Transform
Integrate


Question # 7 of 10 ( Start time: 11:28:27 PM ) Total Marks: 1
Merge sort is based on___________.
Select correct option:
Brute-force
Plan-sweep
Axis-sweep
Divide and Conquer


Question # 8 of 10 ( Start time: 11:29:00 PM ) Total Marks: 1
The sequence of merge sort algorithm is:
Select correct option:
Divide-Combine-Conquer
Conquer-Divide-Combine
Divide-Conquer-Combine
Combine-Divide-Conquer


Question # 9 of 10 ( Start time: 11:29:30 PM ) Total Marks: 1
In ____________ we have to find rank of an element from given input.
Select correct option:
Merge sort algorithm
Selection problem
Brute force technique
Plane Sweep algorithm


Question # 10 of 10 ( Start time: 11:30:18 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

CS502- Design and Analysis of Algorithms

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
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)
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
=========================================================>
MCQz (Set-2) Lecture wise MCQs
Correct Choice : 4 From Lectuer # 1
3 – _______________ is a graphical representation of an algorithm
1. Segma Notation
2. Thita Notation
3. Flowchart
4. Asymptotic notation
Correct Choice : 3 From Lectuer # 2
4 – What will be the total number of max comparisons if we run brute-force maxima
algorithm with n elements?
1. n^2
2. n^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.26
3. n
4. n^8
Correct Choice : 1 From Lectuer # 3
5 – function is given like 4n^4+ 5n^3+n what is the run time of this
1. theata(n^4)
2. theata(n^3)
3. theata(4n^4+ 5n^3)
4. theata(4n^4+ 5n^3)
Correct Choice : 1 From Lectuer # 4
6 – Consider the following
code: For(j=1; j
7 – Execution of the following code fragment
int i = N; while (i > 0)
2
{ int Sum = 0; int j;
for (j = 0; j Sum++;
cout
8 – 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?
1. 90 seconds
2. 9 seconds
3. 0.9 seconds
4. 0.09 seconds
Correct Choice : 2 From Lectuer # 4
9 – The appropriate big thita classification of the given function. f(n) = 4n2 + 97n + 1000
is
1. ?(n)
2. O(2^n)
3. O(n^2)
4. O(n^2logn)
Correct Choice : 3 From Lectuer # 4
10 – The appropriate big ? classification of the given function. f(n) = 4n2 + 97n + 1000 is
1. ?(n)
2. O(2^n)
3. O(n^2)
4. O(n^2logn)
Correct Choice : 3 From Lectuer # 4
11 – Which sorting algorithm is faster
1. O (n log n)
2. O n^2
3. O (n+k)
4. O n^3
Correct Choice : 3 From Lectuer # 5
12 – If algorithm A has running time 7n^2 + 2n + 3 and algorithm B has running time
2n^2,then
1. Both have same asymptotic time complexity
2. A is asymptotically greater
3. B is asymptotically greaterComments 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.27
4. None of others
Correct Choice : 1 From Lectuer # 6
14 – What is the solution to the recurrence T(n) = T(n/2)+n .
1. O(logn)
2. O(n)
3. O(nlogn)
4. O(n^2)
Correct Choice : 1 From Lectuer # 8
15 – How much time merge sort takes for an array of numbers?
1. (n^2)
2. T(n)
3. T( log n)
4. T(n log n)
Correct Choice : 2 From Lectuer # 8
17 – Consider the following Algorithm:
Factorial (n){ if (n=1)
return 1 else return (n *
Factorial(n-1))
} Recurrence for the following algorithm is:
1. T(n) = T(n-1) +1
2. T(n) = nT(n-1) +1
3. T(n)= T(n-1) +n
4. T(n)=T(n(n-1)) +1
Correct Choice : 4 From Lectuer # 9
18 – For the Sieve Technique we take time
1. T(nk) .
2. T(n / 3) 4
3. n^2
4. n/3
Correct Choice : 1 From Lectuer # 10
20 – Sieve Technique applies to problems where we are interested in finding a single item
from a larger set of _____________
1. n items
2. phases
3. pointers
4. constant
Correct Choice : 1 From Lectuer # 10
22 – In Sieve Technique we do not know which item is of interest
1. FALSE
2. TRUE
3.
4.
Correct Choice : 2 From Lectuer # 10
23 – For the sieve technique we solve the problem,
1. recursively
2. mathematically
3. accurately
4. precisely
Correct Choice : 1 From Lectuer # 10Comments 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.28
24 – For the Sieve Technique we take time
1. T(nk)
2. T(n / 3)
3. n^2
4. n/3
Correct Choice : 1 From Lectuer # 10
25 – How many elements do we eliminate in each time for the Analysis of Selection
algorithm?
1. n / 2 elements
2. (n / 2) + n elements
3. n / 4 elements
4. n elements
5
Correct Choice : 4 From Lectuer # 10
26 – Sieve Technique applies to problems where we are interested in finding a single item
from a larger set of _____________
1. n items
2. phases
3. pointers
4. constant
Correct Choice : 1 From Lectuer # 10
27 – Sieve Technique can be applied to selection problem?
1. TRUE
2. FALSE
3.
4.
Correct Choice : 1 From Lectuer # 10
28 – The analysis of Selection algorithm shows the total running time is indeed ________in
n,
1. arithmetic
2. geometric
3. linear
4. orthogonal
Correct Choice : 3 From Lectuer # 10
29 – The reason for introducing Sieve Technique algorithm is that it illustrates a very
important special case of,
1. divide-and-conquer
2. decrease and conquer
3. greedy nature
4. 2-dimension Maxima
Correct Choice : 1 From Lectuer # 10
30 – The sieve technique works in ___________ as follows
1. phases
2. numbers
3. integers
4. routines
Correct Choice : 1 From Lectuer # 10
31 – The sieve technique works in ___________ as follows
1. phases 6Comments 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.29
2. numbers
3. integers
4. routines
Correct Choice : 1 From Lectuer # 10
32 – A (an) _________ is a left-complete binary tree that conforms to the heap order
1. heap
2. binary tree
3. binary search tree
4. array
Correct Choice : 1 From Lectuer # 11
34 – For the heap sort, access to nodes involves simple _______________ operations.
1. arithmetic
2. binary
3. algebraic
4. logarithmic
Correct Choice : 1 From Lectuer # 11
37 – We do sorting to,
1. keep elements in random positions
2. keep the algorithm run in linear order
3. keep the algorithm run in (log n) order
4. keep elements in increasing or decreasing order
Correct Choice : 1 From Lectuer # 11
42 – For the heap sort we store the tree nodes in
1. level-order traversal
2. in-order traversal
3. pre-order traversal
4. post-order traversal
Correct Choice : 1 From Lectuer # 11
7
44 – In the analysis of Selection algorithm, we make a number of passes, in fact it could
be as
many as,
1. T(n)
2. T(n / 2)
3. log n
4. n / 2 + n / 4
Correct Choice : 3 From Lectuer # 11
45 – In the analysis of Selection algorithm, we make a number of passes, in fact it could
be as
many as,
1. T(n)
2. T(n / 2)
3. log n
4. n / 2 + n / 4
Correct Choice : 3 From Lectuer # 11
46 – In which order we can sort?
1. increasing order only
2. decreasing order only
3. increasing order or decreasing orderComments 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.30
4. both at the same time
Correct Choice : 3 From Lectuer # 11
47 – One of the clever aspects of heaps is that they can be stored in arrays without using
any _______________.
1. pointers
2. constants
3. variables
4. functions
Correct Choice : 1 From Lectuer # 11
49 – Slow sorting algorithms run in,
1. O(n^2)
2. O(n)
3. O( log n)
4. O(n log n)
Correct Choice : 1 From Lectuer # 11
50 – What is the total time to heapify?
1. ?(log n)
2. ?(n log n)
3. ?(n^2 log n)
4. ?(log^2n)
Correct Choice : 1 From Lectuer # 12
-When we call heapify then at each level the comparison performed takes time It will take
O (1)
1. Time will vary according to the nature of input data
2. It can not be predicted
3. It will take O (log n)
4. None of the Given
Correct Choice : 3 From Lectuer # 12
53 – After partitioning array in Quick sort, pivot is placed in a position such that
1. Values smaller than pivot are on left and larger than pivot are on right
2. Values larger than pivot are on left and smaller than pivot are on right
3. Pivot is the first element of array
4. Pivot is the last element of array
Correct Choice : 2 From Lectuer # 13
54 – The running time of quick sort depends heavily on the selection of
1. No of inputs
2. Arrangement of elements in array
3. Size o elements
4. Pivot element
Correct Choice : 4 From Lectuer # 13
55 – In Quick Sort Constants hidden in T(n log n) are
1. Large
2. Medium
3. Small
4. Not Known
Correct Choice : 3 From Lectuer # 14
9
56 – In Quick Sort Constants hidden in T(n log n) are
1. LargeComments 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.31
2. Medium
3. Small
4. Not Known
Correct Choice : 3 From Lectuer # 14
57 – Is it possible to sort without making comparisons?
1. Yes
2. No
3.
4.
Correct Choice : 1 From Lectuer # 15
58 – Merge sort is stable sort, but not an in-place algorithm
1. TRUE
2. FALSE
3.
4.
Correct Choice : 1 From Lectuer # 15
59 – In counting sort, once we know the ranks, we simply _________ numbers to their
final positions in an output array.
1. Delete
2. Copy
3. Mark
4. arrange
Correct Choice : 2 From Lectuer # 15
60 – 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
4. None of the above
Correct Choice : 3 From Lectuer # 15
61 – Continuation/counting 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
10
Correct Choice : 4 From Lectuer # 15