CS502- Fundamentals of Algorithms

Solved MCQS Dec 09,2012

From Midterm Papers

Solved By Rabia Rauf

( Marks: 1 ) - Please choose one

1.Random access machine or RAM is a/an
Machines build by Al-Khwarizmi
Mechanical machine
Electronics machine
Mathematical model (lec#2 pg#10)

2._______________ is a graphical representation of an algorithm

Σ notation
Θ notation
Flowchart( refrence cls10 chapter no1)
Asymptotic notation

3. A RAM is an idealized machine with ______________ random-access memory.

256MB
512MB
an infinitely large (page#10)
100GB

4.What type of instructions Random Access Machine (RAM) can execute? Choose best
Algebraic and logic
Geometric and arithmetic
Arithmetic and logic(page#10)
Parallel and recursive

5.What will be the total number of max comparisons if we run brute-force maxima
algorithm with n elements.
*n 2
n
2
*n
*n
*n 8
Answe is option 3

6. What is the solution to the recurrence T(n) = T(n/2)+n.

O(logn) (not sure)
O(n)
Solved By Rabia Rauf
O(nlogn)
O( n 2 )

7. 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( n 2 )

8. 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 (lec#9)

9. What is the total time to heapify?

(Olog n) (page#43)
(n log n)
( n 2 log n)
( log 2 n)

10.When we call heapify then at each level the comparison performed takes time
It will take (1)
Time will vary according to the nature of input data
It can not be predicted
It will take (log n)

11.In Quick sort, we don’t have the control over the sizes of recursive calls
True(page#49)
False
Less information to decide
Either true or false

Solved By Rabia Rauf

12.Is it possible to sort without making comparisons?
Yes (pge#57)
No
Question No: 13 ( Marks: 1 ) - Please choose one
If there are 𝛉 n 2 entries in edit distance matrix then the total running
(1)
( n 2 ) (pg#84)
(n)
(n log n)

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

15.The Knapsack problem belongs to the domain of _______________ problems.

Optimization (pg#91)
NP Complete
Linear Solution
Sorting

16.Suppose we have three items as shown in the following table, and suppose the
capacity of the knapsack is 50 i.e. W = 50.
The optimal solution is to pick
item value weight
1 60 10
2 100 20
3 120 30

Items 1 and 2
Items 1 and 3
Items 2 and 3
None of these

17 - What type of instructions Random Access Machine (RAM) can execute? Choose best
answer
1. Algebraic and logic
2. Geometric and arithmetic
3. Arithmetic and logic (rep)
4. Parallel and recursive
Correct Choice : 3 From Lectuer # 1

18 - Random access machine or RAM is a/an

1. Machine build by Al-Khwarizmi
2. Mechanical machine
3. Electronics machine
Solved By Rabia Rauf
4. Mathematical model (rep)
Correct Choice : 4 From Lectuer # 1

19- _______________ is a graphical representation of an algorithm

1. Segma Notation
2. Thita Notation
3. Flowchart (rep)
4. Asymptotic notation
Correct Choice : 3 From Lectuer # 2

20 - 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/2
3. n
4. n^8
Correct Choice : 1 From Lectuer # 3

21 - 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

22 - 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

23 - 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

24 - Which sorting algorithm is faster

1. O (n log n)
2. O n^2
3. O (n) (pg#26)
4. O n^3
Correct Choice : 3 From Lectuer # 5

Solved By Rabia Rauf

25 - 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 greater
4. None of others
Correct Choice : 1 From Lectuer # 6

26 - 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

27- - 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

28 - 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

29 - For the Sieve Technique we take time

1. T(nk) . (pg#34)
2. T(n / 3)
3. n^2
4. n/3
Correct Choice: 1 From Lectuer # 10

30 - Sieve Technique applies to problems where we are interested in finding a single item
from a larger set of _____________
1. n items (pg#34)
2. phases

Solved By Rabia Rauf

3. pointers
4. constant
Correct Choice : 1 From Lectuer # 10

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

1. FALSE
2. TRUE(pg#34)
Correct Choice : 2 From Lectuer # 10

32 - For the sieve technique we solve the problem,

1. recursively (pg#34)
2. mathematically
3. accurately
4. precisely
Correct Choice : 1 From Lectuer # 10

33 - For the Sieve Technique we take time

1. Tθ(nk) (pg#34)
2. T(n / 3)
3. n^2
4. n/3
Correct Choice : 1 From Lectuer # 10

34 - 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
Correct Choice : 4 From Lectuer # 10

35- 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

36 - The analysis of Selection algorithm shows the total running time is indeed ________in
n,
1. arithmetic
2. geometric
3. linear (pg#37)
4. orthogonal
Correct Choice : 3 From Lectuer # 10

Solved By Rabia Rauf

 37- The reason for introducing Sieve Technique algorithm is that it illustrates a very
important special case of,
1. divide-and-conquer (pg#34)
2. decrease and conquer
3. greedy nature
4. 2-dimension Maxima
Correct Choice : 1 From Lectuer # 10

38 - The sieve technique works in ___________ as follows

1. phases (pg#34)
2. numbers
3. integers
4. routines
Correct Choice : 1 From Lectuer # 10

39 - A (an) _________ is a left-complete binary tree that conforms to the heap order
1. heap (pg#40)
2. binary tree
3. binary search tree
. array
Correct Choice : 1 From Lectuer # 11

40 - For the heap sort, access to nodes involves simple _______________ operations.
1. arithmetic (pg#41)
2. binary
3. algebraic
4. logarithmic
Correct Choice : 1 From Lectuer # 11

41 - 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 (pg#39)
Correct Choice : 1 From Lectuer # 11

42 - For the heap sort we store the tree nodes in

1. level-order traversal (pg#40)
2. in-order traversal
3. pre-order traversal
4. post-order traversal
Correct Choice : 1 From Lectuer # 11

43 - 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)

Solved By Rabia Rauf

3. log n (pg#37)
4. n / 2 + n / 4
Correct Choice : 3 From Lectuer # 11
44 - In which order we can sort?
1. increasing order only
2. decreasing order only
3. increasing order or decreasing order (pg#39)
4. both at the same time
Correct Choice : 3 From Lectuer # 11

46 - One of the clever aspects of heaps is that they can be stored in arrays without using
any _______________.
1. pointers (pg#40)
2. constants
3. variables
4. functions
Correct Choice : 1 From Lectuer # 1

47 - Slow sorting algorithms run in,

1. O(n^2) (pg#39)
2. O(n)
3. O( log n)
4. O(n log n)

48- What is the total time to heapify?

1. ?(log n) (pg#43)
2. ?(n log n)
3. ?(n^2 log n)
4. ?(log^2n)
Correct Choice : 1 From Lectuer # 12

49 - 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 Lecture # 12

50 - 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

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

1. No of inputs

Solved By Rabia Rauf

2. Arrangement of elements in array
3. Size o elements
4. Pivot element (pg#49)
Correct Choice : 4 From Lectuer # 13

52- 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

53 - Is it possible to sort without making comparisons?

1. Yes (pg#57)
2. No
Correct Choice : 1 From Lectuer # 15

54 - Merge sort is stable sort, but not an in-place algorithm

1. TRUE (pg#54)
2. FALSE
Correct Choice : 1 From Lectuer # 15

55 - In counting sort, once we know the ranks, we simply _________ numbers to their final positions in an
output array.
1Delete
2 copy
3 Mark
4 arrange
Correct Choice : 2 From Lectuer # 15
1.
56 - 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 (pg#54)
4. None of the above
Correct Choice : 3 From Lectuer # 15
2.
57 - 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 (pg#57)
Correct Choice : 4 From Lectuer # 15
3.
58 - In stable sorting algorithm.
1. If duplicate elements remain in the same relative position after sorting
2. One array is used
3. More than one arrays are required

Solved By Rabia Rauf

 4. Duplicating elements not handled
Correct Choice : 1 From Lectuer # 15
4.
59 - One example of in place but not stable algorithm is
1. Merger Sort
2. Quick Sort
3. Continuation Sort
4. Bubble Sort
Correct Choice : 2 From Lecture # 15
5.
60 - One example of in place but not stable algorithm is
1. Merger Sort
2. Quick Sort (pg#54)
3. Continuation Sort
4. Bubble Sort
Correct Choice : 2 From Lecture # 15

61- One of the clever aspects of heaps is that they can be stored in arrays without using
any _______________.
1. pointers (rep)
2. constants
3. variables
. functions
Correct Choice : 1 From Lecture # 15

62 - Quick sort is
1. Stable & in place
2. Not stable but in place (pg#54)
3. Stable but not in place
4. Some time stable & some times in place

63 - Quick sort is
1. Stable & in place
2. Not stable but in place (rep)
3. Stable but not in place
4. Some time stable & some times in place
Correct Choice : 2 From Lectuer # 15

64 - Which may be a stable sort?

1. Merger
2. Insertion
3. Both above (pg#54)
4. None of the above
Correct Choice : 3 From Lectuer # 15

67 - Which of the following sorting algorithms is stable?

(i) Merge sort,
(ii) Quick sort,

Solved By Rabia Rauf

(iii) Heap sort,
(iv) Counting Sort.
1. Only i
2. Only ii
3. Both i and ii
4. Both iii and iv
Correct Choice : 1 From Lectuer # 15

68 Mergesort is a stable algorithm but not an in-place algorithm.

1. TRUE (pg#54)
2. FALSE
Correct Choice : 1 From Lectuer # 16

69 - Memorization is?
1. To store previous results for future use
2. To avoid this unnecessary repetitions by writing down the results of recursive
calls and looking them up again if we need them later (pg#74)
3. To make the process accurate
4. None of the above
Correct Choice : 2 From Lectuer # 16

70 - Dynamic programming algorithms need to store the results of intermediate

sub-problems.
1. TRUE (pg#75)
2. FALSE
Correct Choice : 1 From Lectuer # 17

71 - Dynamic programming uses a top-down approach.

1. TRUE
2. FALSE
Correct Choice : 2 From Lectuer # 17

73- The edit distance between FOOD and MONEY is

1. At most four (pg#76)
2. At least four
3. Exact four
4. Wrong
Correct Choice : 1 From Lectuer # 17

74- The edit distance between FOOD and MONEY is

1. At most four
2. At least four
3. Exact four
4. Wrong
Correct Choice : 1 From Lectuer # 17

75 - If there are O (n^2) entries in edit distance matrix then the total running time is
1. O (1)

Solved By Rabia Rauf

2. O (n^2) (rep)
3. O (n)
4. O (n log n)
Correct Choice : 2 From Lectuer # 18

76 - A p x q matrix A can be multiplied with a q x r matrix B. The result will be a p x r matrix

C. There are (p . r) total entries in C and each takes _________ to compute.
1. O (q) (pg#84)
2. O (1)
3. O (n^2)
4. O (n^3)
Correct Choice : 1 From Lectuer # 19

77 - For Chain Matrix Multiplication we can not use divide and conquer approach because,
1. We do not know the optimum k (rep)
2. We use divide and conquer for sorting only
3. We can easily perform it in linear time
4. Size of data is not given
Correct Choice : 1 From Lectuer # 19

78 - A p x q matrix A can be multiplied with a q x r matrix B. The result will be a p x r matrix

C. There are (p . r) total entries in C and each takes _________ to compute.
1. O (q) (rep)
2. O (1)
3. O (n^2)
4. O (n^3)
Correct Choice : 1 From Lectuer # 19

79 - The Knapsack problem belongs to the domain of _______________ problems.

1. Optimization rep
2. NP Complete
3. Linear Solution
4. Sorting
Correct Choice : 1 From Lectuer # 21

80 The codeword assigned to characters by the Huffman algorithm have the property that
no codeword is the postfix of any other.
1. TRUE
2. FALSE
Correct Choice : 2 From Lectuer # 22

81 - The greedy part of the Huffman encoding algorithm is to first find two nodes with
larger frequency.
1. TRUE
2. FALSE
Correct Choice : 2 From Lectuer # 22

Solved By Rabia Rauf

82 - An optimization problem is one in which you want to find,
1. Not a solution
2. An algorithm
3. Good solution
4. The best solution
Correct Choice : 4 From Lectuer # 22

83- 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 (rep)

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

85- Sieve Technique can be applied to selection problem?

True ( pg#35)
False

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

increasing order only
decreasing order only
heap order (pg40)
(log n) order

87- A (an) _________ is a left-complete binary tree that conforms to the heap order
heap ( pg#40)
binary tree
binary search tree
array

88- Divide-and-conquer as breaking the problem into a small number of

Select correct option:
pivot
Sieve
smaller sub problems (pg27)
Selection

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

Select correct option:

True (rep)
False

Solved By Rabia Rauf

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

16
10
32
31 (not sure)

91- 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 (pg37)
exponent

92- 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 (rep)
exponent

93-In inplace sorting algorithm is one that uses array for storage :
1. An additional array
2. No additional array (rep)
3. Both of the above
4. More then one array of one dimension.

94-The running time of quick sort depends heavily on the selection of.
1. No of inputs
2. Arrangement of element in array
3.Size Of element
4. Pivot element rep

95-For the sieve technique we solve the problem.

Recursively rep
mathematically
precisely
accurately

96-The sieve technique works in ___________ as follows

Phases rep

Solved By Rabia Rauf

numbers
integers
routines

97-Slow sorting algorithms run in,

T(n^2) rep
T(n)
T( log n)

98-A (an) _________ is a left-complete binary tree that conforms to the heap order
Heap rep
binary tree
binary search tree
array

99-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 rep
exponent

100-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 (pg#37)
n/2+n/4

101-In which order we can sort?

Select correct option:
increasing order only
decreasing order only
increasing order or decreasing order (rep)
both at the same time

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

103-Analysis of Selection algorithm ends up with,

θ(n) rep
T(1 / 1 + n)
T(n / 2)
T((n / 2) + n)

Solved By Rabia Rauf

104-Memorization is?
1. To store previous results for future use
2. To avoid this unnecessary repetitions by writing down the results of
recursive calls and looking them up again if we need them later (rep)
3. To make the process accurate
4. None of the above

105-Which sorting algorithm is faster

1. O (n log n)
2. O n^2
3. O (n) rep
4. O n^3

106-Quick sort is
1. Stable & in place
2. Not stable but in place (rep)
3. Stable but not in place
4. Some time stable & some times in place

107-One example of in place but not stable algorithm is

1. Merger Sort
2. Quick Sort rep
3. Continuation Sort
4. Bubble Sort

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

1. Large
2. Medium
3. Small rep
4. Not Known

109-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 rep

110-In stable sorting algorithm.

1. If duplicate elements remain in the same relative position after sorting rep
2. One array is used
3. More than one arrays are required
4. Duplicating elements not handled

111-Which may be a stable sort?

1. Merger
2. Insertion
3. Both above rep
4. None of the above

Solved By Rabia Rauf

112-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 rep
4. None of the above

113-Counting sort has time complexity of ?

1. O(n)
2. O(n+k)
3. O(nlogn)
4. O(k)

114-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 rep

115-Divide-and-conquer as breaking the problem into a small number of

pivot
Sieve
smaller sub problems rep
Selection

116-The analysis of Selection algorithm shows the total running time is indeed ________in n,
arithmetic
geometric
linear pg#37
orthogonal

117-How many elements do we eliminate in each time for the Analysis of Selection algorithm?
n / 2 elements (pg#37)
(n / 2) + n elements
n / 4 elements
2 n elements

118-Sieve Technique can be applied to selection problem?

True rep
FALSE

119- For the heap sort we store the tree nodes in

level-order traversal rep
in-order traversal
pre-order traversal
post-order traverse

120-In RAM model instructions are executed

Solved By Rabia Rauf

One after another pg#10
Parallel
Concurrent
Random

121-In selection algorithm, becausewe eliminate a constant fraction of the array with each phase, we get
the
Convergent geometric series rep
Divergent geometric series
None of these

122-Due to left-complete nature of binary tree, heaps can be stored in

Link list
Structure
Array
None of above

123-If algorithm A has running time 7n2 + 2n + 3 and algorithm B has running time 2n2, then
Both have same asymptotic time complexity rep
A is asymptotically greater
B is asymptotically greater
None of others

124-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

125-Execution of the following code fragment

int Idx;
for (Idx = 0; Idx < N; Idx++)
{
cout << A[Idx] << endl;
}
is best described as being
O(N)
O(N2)
O(log N)
O(N log N)

126-The edit distance between FOOD and MONEY is

At most four rep
At least four

Solved By Rabia Rauf

Exact four

127-Consider the following recurrence relation

Then T(5) is
25
75
79

128-How much time merger sort takes for an array of numbers?

T(n^2)
T(n) (pg#29)
T(log n)
T(n log n)

129-Divide-and-Conquer is as breaking the problem into a small number of

Smaller Sub Problems rep
Pivot
Sieve
Solutions.

130-The Sieve Sequence is a special case where the number of smaller subproblems is just____.
4
Many
1
Few

131-How many elements do we eliminate each time for the Analysis of Selection
Algorithm?
(n / 2)+n Elements
n / 2 Elements
n / 4 Elements
2 n Elements
132-We do sorting to?
Keep elements in random position
Keep the algorithm run in linear order
Keep Elements in Ascending or Descending Order rep
Keep the algorithm run in (log n) order

133-Sorting is one of the few problems where provable ____ bounds exit on how fast we can sort?
Upper
Average
Log n
Lower rep

134-In the analysis of Selction Algorithm, we eliminate the constant fraction of the array with each phase, we
get convergent _____ series in the analysis.

Solved By Rabia Rauf

Geometric rep
Linear
Arithmetic
None of above

135-For the Sieve technique we take time?

T (n/3)
T𝛉 (n k)
N^2
n/3

136-For the sieve technique we solve the problem

Recursively
Randomly
Mathematically
Precisely

137-The recurrence relation of Tower of Hanoi is T(n) = 1 if n = 1 and 2T(n-1)

if n >1. In order to move a tower of 5 rings from one peg to another how
many ring moves are required?
16
10
32 (Not Confirm)
31

138-An optimization problem is one in which you want to find,

►Not a solution
►An algorithm
►Good solution
►The best solution rep

139-Search technique is used to find the

►Maximum two solutions
►Minimum two solutions
►Sorting solution

140-What type of instructions Random access machine can execute?

Geometric and arithmetic
Algebraic and logic
Arithmetic and logic rep
Parallel and recursive

141-Due to left complete nature of binary tree, the heap can be stored in
• Arrays rep
• Structures
• Link Lis
• Stack

Solved By Rabia Rauf

142-What type of instructions Random Access Machine (RAM) can execute?
Algebraic and logic
Geometric and arithmetic
Arithmetic and logic rep
Parallel and recursive

143-For Chain Matrix Multiplication we can not use divide and conquer approach
because,
We do not know the optimum k
We use divide and conquer for sorting only rep
We can easily perform it in linear time
Size of data is not given

144-We do sorting to,

Select correct option:
keep elements in random positions
keep the algorithm run in linear order
keep the algorithm run in (log n) order
keep elements in increasing or decreasing order rep

145-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

146-Sieve Technique can be applied to selection problem?

True Page 35
False
147-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

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

Heap Page 40
binary tree
binary search tree
array

149-Divide-and-conquer as breaking the problem into a small number of

pivot
Sieve

Solved By Rabia Rauf

smaller sub problems Page 34
Selection

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

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

152-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
exponent

153-For the heap sort, access to nodes involves simple _______________operations.:

Arithmetic Page 41
binary
algebraic
logarithmic
154-For the sieve technique we solve the problem,
Recursively Page 34
mathematically
precisely
accurately

155-The sieve technique works in ___________ as follows

Phases Page 34
numbers
integers
routines

156-Slow sorting algorithms run in,

O(n2) Page 39
T(n^2)
T(n)
T( log n)

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

Solved By Rabia Rauf

158-In the analysis of Selection algorithm, we eliminate a constant fraction of the array with each phase;
we get the convergent _______________ series in the analysis,
linear
arithmetic
geometric
exponent

159-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
160- The sieve technique is a special case, where the number of sub problems is just
5
many
1 Page 34
few

161-In which order we can sort?

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

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

163-Analysis of Selection algorithm ends up with,

(n) pg#37
T(1 / 1 + n)
T(n / 2)
T((n / 2) + n)

164-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 rep

165-Divide-and-conquer as breaking the problem into a small number of

pivot
Sieve
smaller sub problems rep

Solved By Rabia Rauf

Selection
166-The analysis of Selection algorithm shows the total running time is indeed ________in n,
Arithmetic
geometric
linear Page 37
orthogonal

167-How many elements do we eliminate in each time for the Analysis of Selection algorithm?
n / 2 elements rep
(n / 2) + n elements
n / 4 elements
2 n elements

168-Sieve Technique can be applied to selection problem?

True
False
169-For the heap sort we store the tree nodes in
level-order traversal Page 40
in-order traversal
pre-order traversal
post-order traversal

170-One of the clever aspects of heaps is that they can be stored in arrays without using
any_______________.
pointers rep
constants
variables
functions

171-For the heap sort we store the tree nodes in

level-order traversal rep
in-order traversal
pre-order traversal
post-order traversal

172-. The sieve technique works in ___________ as follows

Phases Page 34
numbers
integers
routines

173- 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 rep
exponent

Solved By Rabia Rauf

174-. 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

175-. 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 rep
n/2+n/4
176-. In which order we can sort?
increasing order only
decreasing order only
increasing order or decreasing order rep
both at the same time

177-. In Sieve Technique we do not know which item is of interest

True
False
178-. For the sieve technique we solve the problem,
recursively
mathematically
precisely

179-. Divide-and-conquer as breaking the problem into a small number of

pivot
Sieve
smaller sub problems
Selection

180-Divide-and-Conquer is as breaking the problem into a small number of

· Smaller Sub Problems
· Pivot
· Sieve
· Solutions

181-Analysis of Selection Sort ends up with

· T(n) Page 37
· T(1/1+n)
· T(n/2)
· T((n/2) +n)
182-How many elements do we eliminate each time for the Analysis of Selection Algorithm?
· (n / 2)+n Elements
· n / 2 Elements
· n / 4 Elements

Solved By Rabia Rauf

· 2 n Elements

183-A heap is a left-complete binary tree that conforms to the ?

· Increasing Order
· Decreasing order
· Heap Order
· (nlog n) order

184-The Sieve Sequence is a special case where the number of smaller sub problems is just_ .· 4
· Many
·1
· Few

185-Heaps can be stored in arrays without using any pointers this is due to the of the binary tree?
· Tree Nodes
· Right-Complete Nature
· Left-Complete Nature
· Tree Leaves

186-For the Heap Sort access to nodes involves simple _ operations:

· Geometric
· Linear
· Arithmetic
· Algebraic

187-The Analysis of Selection Sort shows that the total running time is indeed in n?
· Geometric
· Linear
· Arithmetic
· Algebraic

188-For the sieve technique we solve the problem

· Recursively
· Randomly
· Mathematically
· Precisely

189-How much time merger sort takes for an array of numbers?

· T(n^2)
· T(n) Page 30
· T(log n)
· T(n log n)

190-Divide-and-Conquer is as breaking the problem into a small number of

· Smaller Sub Problems rep
· Pivot
· Sieve
· Solutions

Solved By Rabia Rauf

191-Analysis of Selection Sort ends up with
· (n) rep
· T(1/1+n)
· T(n/2)
· T((n/2) +n)

192-How many elements do we eliminate each time for the Analysis of Selection Algorithm?
· (n / 2)+n Elements
· n / 2 Elements
· n / 4 Elements
· 2 n Elements

193-A heap is a left-complete binary tree that conforms to the ?

· Increasing Order
· Decreasing order
· Heap Order
· (nlog n) order

194-The Sieve Sequence is a special case where the number of small er sub problems is just_ .
·4
· Many
·1
· Few

195-Heaps can be stored in array s without using any pointers this is due to the of the binary tree?
· Tree Nodes
· Right-Complete Nature
· Left-Complete Nature
· Tree Leaves

196-For the Heap Sort access to nodes involves simple _ operations:

· Geometric
· Linear
· Arithmetic rep
· Algebraic

The Analysis of Selection Sort shows that the total running time is indeed in n?
· Geometric
· Linear pg#37
· Arithmetic
· Algebraic

For the sieve technique we solve the problem

· Recursively rep
· Randomly
· Mathematically
· Precisely

Solved By Rabia Rauf

How much time merger sort takes for an array of numbers?
· T(n^2)
· T(n)
· T(log n)
· T(n log n)

Go0d Luck

Solved By Rabia Rauf

 CS502- Fundamentals of Algorithms
Solved MCQS May- 24 - 2013
From Midterm Papers

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)

1
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

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

Question No: 7 ( Marks: 1 ) - Please choose one

Consider the following code:
For(j=1; j<n;j++)
For(k=1; k<15;k++)
For(l=5; l<n; l++)
{
Do_something_constant();
}
What is the order of execution for this code.
► O(n)
► O(n3)
► O(n2 log n)
► O(n2)

Question No: 8 ( Marks: 1 ) - Please choose one

What is the total time to heapify?
► Ο(log n) rep
► Ο(n log n)
► Ο(n2 log n)
► Ο(log2 n)

3
 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)

4
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 these

5
 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)

►false

6
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:
2
►Ο (log n)
►Ο (n log n)
2
►Ο (n 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 log2 n)
►O(3)
►O( log2 ( log2 n ))
►O ( log2 n)

Question No: 1 ( Marks: 1 ) - Please choose one

In RAM model instructions are executed

►One after another (Page 10)

►Parallel
►Concurrent
►Random

7
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)

False

8
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)

9
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

10
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:

11
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&Y

12
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)

13
 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
accurately

14
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
routines

15
 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)
exponent
16
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
functions

17
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^3

18
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 above

19
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)

20
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 max

21
 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)

22
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)

23
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)
Randomly

24
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

25
 CS502 – Design & Analysis of Algorithms Midterm
2013

1. The word Algorithm comes from the name of the Muslim author _______________
Abu Ja’far Mohammad ibn Musaal-Khowarizmi or Al-Khwarizmi
Khwarizm
Kheva
Uzbekistan
2. In order to say anything meaningful about our algorithms, it will be important for us to
settle on a ___________.
C++ program
Java program
Pseudo program
Mathematical model of computation pg 10
3. A RAM is an idealized machine with ______________ random-access memory.
256MB
512MB
an infinitely large pg 10
100GB
4. Which formula is used for calculating worst case running time?
Tworst (n) = max |I |= n T ( I )

Tworst (n) = max |I | =1 T ( I )

1 Tworst ( n ) = max |I | =1 T ( n )
Tworst (n) = max |I |= n T (n)

[Type the company name]

 CS502 – Design & Analysis of Algorithms Midterm
2013
5. Divide-and-conquer involves breaking the problem into a small number of
Sieve
pivot
Sub problems pg 34
Selection
6. 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 pg 37
harmonic
7. One of the clever aspects of heaps is that they can be stored in arrays without using any
_______________.
Pointers pg 40
constants
variables
functions
8. Quick sort can work well in virtual memory environment.
It is true
It is false
Sorting is not performed in virtual memory environment
Either true or false
9. What is common between Bubble sort, Insertion sort, Selection sort, Quick sort, and
Heap sort?
All are in-place algorithms pg 54
All are stable algorithms
None of these
All are unstable algorithms
10. Counting sort algorithm sorts in
Θ(n + k)
Θ(n - k)
Θ(n)
Θ(k)
11. If there are Θ (n2) entries in edit distance matrix then the total running time is
Θ (1)
Θ (n2) pg 84
Θ (n)
Θ (n log n)
12. A product of matrices is _____________ if it is either single matrix or the product of two
matrix products, surrounded by parentheses.
Fully parenthesized
2 Partially parenthesized
Not parenthesized
None of the options
13. Time complexity of chain matrix multiplication is Θ (n3) and space complexity is
Θ (n2)

[Type the company name]

 CS502 – Design & Analysis of Algorithms Midterm
2013
Θ (n3)
Θ (n log n)
Θ (log n)
14. Suppose we have three items as shown in the following table, and suppose the capacity
of the knapsack is 50 i.e. W = 50.
Item Value Weight
1 60 10
2 100 20
3 120 30
The optimal solution is to pick
Items 1 and 2
Items 1 and 3
Items 2 and 3
None of these
15. Dynamic programming algorithms
Store the results of end points
Store the problems statment
Do not store the subproblem results
Do store the results of intermediate subproblems pg 75
16. Algorithm’s essential elements are
Step wise solution
Stepwise solution and finite time
Step wise solution finite inputs
Stepwise approach in which time and memory does not matter.
17. Suppose we have an algorithm that carries out N2 operations for an input of size N. Let
us say that a computer takes 1 microsecond (1/1000000 second) to carry out one
operation. How long does the algorithm run for an input of size 3000?
90 seconds
9 seconds
0.9 seconds
0.09 seconds
18. What is the solution to the recurrence T(n) = T(n/2)+n, T(1) = 1?
O(logn)
O(n) 37
O(nlogn)
O(n2)
19. Which of the following is true?
The worst case time complexity of the quick sort is NlogN
The best case time complexity of the merge sort is logN
The worst case time complexity of the selection sort is N^2
The worst case time complexity of the merge sort is logN
3 20. In Quick Sort, partition algorithm partitions the array into ________ sub arrays.
2
3 pg 46
1

[Type the company name]

 CS502 – Design & Analysis of Algorithms Midterm
2013
4

Q # 01: In order to say anything meaningful about our algorithms, it will be important for
us to settle on a ___________.

C++ program

Java program

Pseudo program

Mathematical model of computation

Q # 03: Divide-and-conquer involves breaking the problem into a small number of

Pivot

Sub problems

Selection

Sieve

Q # 04: For the heap sort, access to nodes involves simple _______________ operations.

Arithmetic 41

binary

algebraic

logarithmic
Q # 05: If a sorting algorithm solely based on comparisons of keys in the array then it is
impossible to sort more efficiently than

Ω (n lg n)

Θ (n lg n)

Ο (n lg n)

None of these
Q # 06: The comparison based algorithm defines a(n) __________.

decision tree 54

array

linked list

stack

Q # 07: The main shortcoming of counting sort is that it is useful for

Small Integers 71

Small characters

Floats

None of these
Q # 08: Memoization is a process

To avoid unnecessary repetitions by writing down the results of recursive
calls and looking them again if needed later 74

To avoid repeated data by writing down the results of input array and looking them
4 again if needed later.

None of these

All options are correct
Q # 09: Matrix multiplication is

An associative but not commutative operation 85

[Type the company name]

 CS502 – Design & Analysis of Algorithms Midterm
2013

An associative and commutative operation

Not associative but commutative operation

Neither associative nor commutative operation
Q # 10: We can find the product A x B of matrices A and B, only if they are compatible
which means,

No of Columns of A must be equal to No of Rows of B

No of Columns of A must be equal to No of Columns of B

No of Rows of A must be equal to No of Rows of B

Order of A must be equal to order of B
Q # 11: A product of matrices is _____________ if it is either single matrix or the product of
two matrix products, surrounded by parentheses.

Fully parenthesized

Partially parenthesized

Not parenthesized

None of the options
Q # 12: Merge sort requires

Extra storage 54

No need of extra storage

Sometimes requires extra storage

Extra time than other sorting algorithms
Q # 13: Heap sort is

In place and stable

Out place and stable

Out place but not stable

In place but not stable 54
Q # 14: Worst case running time of Quick Sort algorithm for an array with n elements is?
2

n
n
2

n

n
8

n

Q # 15: Which of the following is calculated with Big O notation?

Medium bounds

Lower bounds

Upper bounds 25

Both upper and lower bound
Q # 16: Which of the following is calculated with Big Theta notation?

Lower bounds 25

Upper bounds
5
Both upper and lower bound

Medium bounds
Q # 17: Identify the maximal points in given set, according to 2-D maxima (the points that
are NOT dominated by other points).

[Type the company name]

 CS502 – Design & Analysis of Algorithms Midterm
2013
{( 2,5) , ( 4, 4 ) , ( 4,11) , ( 5,1) , ( 7, 7 ) , ( 7,13) , ( 9,10 ) , (11,5) , (12,12 ) , (13,3) , (14,10 ) , (15,7 )}

{( 7,13) , (12,12 ) , (14,10 ) , (15, 7 )} 20

{( 7, 7 ) , ( 7,13) , ( 9,10 ) , (11,5) , (14,10 )}

{( 2,5) , ( 4, 4 ) , ( 4,11) , ( 5,1) , (14,10 )}
{( 4, 4 ) , ( 4,11) , ( 7,13) , ( 9,10 )(14,10 )}


n

∑n
i =1

Q # 18: is equal to,

n(n+1)

n(n)

n(n+1)/3

n+1

Q # 19:
What is the running time of the above sorting algorithm in worst case?
Θ ( n2 )

39
Θ ( n3 )


Θ ( n log n )


Θ ( log n )

Q # 20: The reason for introducing Sieve Technique algorithm is that it illustrates a very
important special case of_____________

Divide-and-conquer 34

Decrease and conquer
6

Greedy nature

2-dimension Maxima

MIDTERM EXAMINATION

[Type the company name]

 CS502 – Design & Analysis of Algorithms Midterm
2013

Q # 01: Random access machine or RAM is a/an

Machine build by Al-Khwarizmi

Mechanical machine

Electronics machine

Mathematical model 10

What is common between Bubble sort, Insertion sort, Selection sort, Quick sort, and Heap
sort?
All are in-place algorithms (pg54)
All are stable algorithms
None of these
All are unstable algorithms

In order to say anything meaningful about our algorithms, it will be important for us to
settle on a ___________.
C++ program
Java program
Pseudo program
Mathematical model of computation (pg10)
Q # 04: In which order we can sort?

increasing order or decreasing order 39

both at the same time

increasing order only

decreasing order only
Q # 05: For the heap sort we store the tree nodes in

level-order traversal 40

in-order traversal

pre-order traversal

post-order traversal
Q # 06: Quick sort procedure was invented by

Hoare in 1960

Sedgewick

Mellroy

Coreman
Q # 07: For sorting algorithms which one is the efficient algorithm having running time?

O(n2)

O(n log n) not sure

O(n2 log n)

O(n3)
Q # 08: When a recursive algorithm revisits the same problem over and over again, we say
7 that the optimization problem has _______________ sub-problems.

Overlapping

Over costing

Optimized

None of these

[Type the company name]

 CS502 – Design & Analysis of Algorithms Midterm
2013
Q # 09: A problem exhibits ___________ if an optimal solution to the problem contains within
it optimal solution to sub-problems.

Optimal structure 92

Efficient structure

Inefficient structure

Unknown behavior
Q # 10: A p × q matrix A can be multiplied with a q × r matrix B. The result will be a p × r
matrix C. There are (p . r) total entries in C and each takes _________ to compute.

(q) 84

(1)

(n2)

(n3)
Q # 11: Dynamic programming is

Other name of rescursion

Other name of divide and conquer

Recursion without repetition 75

Recurrence development technique
Q # 12: Dynamic programming algorithms

Store the results of end points

Store the problems statement

Do not store the subproblem results

Do store the results of intermediate subproblems 75
Q # 13: The worst case running time of the algorithm given below is,

Θ ( n6 )


 2n 
Θ n 6 

 

Θ ( n2 )

14 page

8 Θ ( 2n lg 6 )


Q # 14: Due to left-complete nature of binary tree, heaps can be stored in

Arrays 40

Structures

[Type the company name]

 CS502 – Design & Analysis of Algorithms Midterm
2013

Link list

Stack

QNo.1 What is heap and what is heap order? (Mark2)

Answer:- The heap is the section of computer memory where all the variables created or
initialized at runtime are stored. The heap order property: in a (min) heap, for every node
X, the key in the parent is smaller than or equal to the key in X.
QNo.2 Quick sort such that sort the array in to non-increasing order? (Mark2)
Answer:- Quick sorting, an array A[1..n] of n numbers We are to reorder these elements
into increasing (or decreasing) order. More generally, A is an array of objects and we sort
them based on one of the attributes - the key value. The key value need not be a number. It
can be any object from a totally ordered domain. Totally ordered domain means that for
any two elements of the domain, x and y, either x < y, x = y or x > y.
QNo.3 Draw the cost table for chain multiplication problem with initial
states(Mark3)
Answer:- Cost table for chain multiplication problem in initial stage is the diagonal entries
(all m [i, i]) filled with zeros and rest of the table entries are empty which are to be filled in
next steps of the table calculation. (A1)(A2A3A4 . . .An) or (A1A2)(A3A4 . . .An) or
(A1A2A3)(A4 . . .An) . . . . . . or (A1A2A3A4 . . .An−1)(An)
QNo.4 we can avoid unnecessary repetitions for recursive calls? (Mark3)
Answer:- We can avoid these unnecessary repetitions by writing down the results of
recursive calls and looking them up again if we need them later. This process is called
memorization.
Worst case for edit distance algorithm? What is the simple change that can change
the worst case time ?
Answer:- Analysis of DP edit distance There are (n2 ) entries in the matrix. Each entry
E(i,j) takes (1) time to compute. The total running is 2 (n ) Recursion clearly leads to the
same repetitive call pattern that we saw in Fibonnaci sequence. To avoid this, we will use
the DP approach. We will build the solutionb bottom-up. We will use the base case E(0,j) to
fill first row and the base case E(I,0) to fill first column. We will fill the remaining E matrix
row by row.
Q:Describe an efficient algorithm to find the median of a set of 106 integers; it is
known that there are fewer than 100 distinct integers in the set.
Solution:- Step1:Start Step2:Find the 100 distinct numbers among 10^6 integers.
9
Step3:Sort the 100 distinct numbers Step4:Count the distinct numbers Step5: if count is
odd,middle number is the median Step6:if count is even,add the middle two numbers then
divide by 2,the result is the median Step5:End number.
What is the formula for generating Catalan numbers?

[Type the company name]

 CS502 – Design & Analysis of Algorithms Midterm
2013
Solution Equation (22) is a recurrence relation. C_(n+1) = C_n * [2(2n+1)] / (n+2) we have
the values of n in one column and the values of C_n in another, then to put this formula in
Excel, on the (n+1)-th row just replace C_n and n with the appropriate cells from the
previous row.
What are Catalan numbers? Give the formula.
Catalan numbers form a sequence of natural numbers that occur in various counting
problems, often involving recursively defined objects Formula is C(n) = 2n Cn / (n+1)
Q-Write a pseudo code Fibonacci With memorization? -- (3)
Sol: MEMOFIB(n) 1 if (n < 2) 2 then return n 3 if (F[n] is undefined) 4 then F*n+
MEMOFIB(n − 1) + MEMOFIB(n − 2) 5 return F[n]
Q – Write Down the steps of Dynamic programming (5)
Dynamic programming is essentially recursion without repetition. Developing a dynamic
programming
algorithm generally involves two separate steps:  Formulate problem recursively. Write
down a formula for the whole problem as a simple combination of answers to smaller sub
problems.  Build solution to recurrence from bottom up. Write an algorithm that starts
with base cases and works its way up to the final solution. Dynamic programming
algorithms need to store the results of intermediate sub problems. This is often but not
always done with some kind of table. We will now cover a number of examples of problems
in which the solution is based on dynamic programming strategy.
Q: How we build heap
Sol:We build a max heap out of the given array of numbers A[1..n]. We repeatedly extract
the maximum item from the heap. Once the max item is removed, we are left with a hole at
the root.
Q:Write Pseudo code for KNAPSACK algorithm? 5 marks
Solution: KNAPSACK (n, W) 1 for w=0,W 2 do V[0,w]0 3 for i=0,n 4 do V[i,0]0 5 for
w=0,W 6 do if(wi w i v +V[i-1,w- i w ]>V[i-1,w]) 7 then V[I,w] i v +V[i-1,w] 8 else
V[i,w]V[i-1,w] The time complexity is clearly O(n,W), it must be cautioned that as n and W
get large, both time and space complexity become significant.
Q:Spelling correction in edit distance? 3 marks
Sol:A better way to display this editing process is to place the words with the other: S D I M
D M, M A - T H S, A - R T - S
THE FIRST WORD HAS AGAP FOR EVERY INSERTION (1)AND THE SECOND WORD HAS A
GAP FOR EVERY DELETION (D). MATHES (M) DO NOT COUNT. THE EDIT TRANSCRIPT IS
DEFINED AS A STRING OVER THE ALPHABETM,S,I,d THAT DESCRIBES A
TRANSFORMATION OF ONE STRING INTO OTHER. FOR EXAMPLE S D I M D M
1+1+1+0+1+0+=4
Q: Differentiate b/w Bubble sort, insertion sort and selection sort? 3 marks
SOLUTION:Bubble sort: scan the array. Whenever two consecutive items are found that
are out of order, swap them. Repeat until all consecutive items are in order. Insertion sort:
assume that A*1…i-1] have already been sorted. Insert A[i] into its properposition in this
10 sub array. Create this position by shifting all larger elements to the right. Selection sort:
Assume that A[1..i-1] contain the i-1 smallest elements in sorted order. Find the smallest in
A*i….n+ swap it with A*i+.
Write down the steps of dynamic programming strategy. (2 marks)

[Type the company name]

 CS502 – Design & Analysis of Algorithms Midterm
2013
Solution: Developing a dynamic programming algorithm generally involves two separate
steps: 1_formulate problem recursively. Write down a formula for the whole problem as a
simple combination of answers to smaller sub problems. 2_ Build solution to recurrence
from bottom up:
Q: Solve the recursion problem. (5marks.)
Solution: Recursion clearly leads to the same repetitive call pattern that we saw in
Fibonnaci sequence. To avoid this, we will use the DP approach. We will build the solution
bottom-up. We will use the base case E(0,j) to fill first row and the base case E(I,0) to fill
first column. We will fill the remaining E matrix row by row.If we trace through the
recursive calls to MemoFib, we find that array F[] gets filled from bottom up…i.e., first F*2+,
then F*3+, and so on, upto F[n]. we can replace recursion with a simple for-loop that just
fills up the array F[] in that order. • We are given an array of n elements of x1 , x2 ,x3 , ,,,,xn,
Q: Suggest best sorting algorithm of order On. (5 marks).
Solution:The main shortcoming of counting sort is that it is useful for small integers, i.e.,
1…k where k is small. If this were a million more, the size of the rank array would also be a
million. Radix sort provides a nice work around this limitation by sorting numbers one
digit at a time.
Q: What are the two steps generally involved while developing dynamic
programming algorithm.
Solution: Developing a dynamic programming algorithm generally involves two separate
steps:
Q: How we build heap? (2)
Solution: We build a max heap out of the given array of numbers A[1..n]. We repeatedly
extract the maximum item from the heap. Once the max item is removed, we are left with a
hole at the root.
What are the applications of edit distance technique? Name any three (3)
Solution: 1. Spelling Correction 2. Plagiarism Detection 3. Computational Molecular
Biology 4. Speech recognition.
What is the worst case running time for the bucket sort? What simple change is
required in the algorithm to preserve its linear expected running time and makes it
worst case time Θ(n log n) (5)
Solution: The worst case for bucket sort occurs when the all inputs falls into single bucket,
for example. Since we use insertion sort for sorting buckets and insertion sort as a worst
case of O(n2). the worst case runtime for bucket sort is O(n2). By using an algorithm with
worst case runtime of O(nlgn) instead of insertion sort for sorting buckets, we can ensure
that worst case is O(nlgn) without affecting the average case behavior.
Given an unordered list of n x0, x1, x2, …, xn and elements is common, if there are
atleast n/5 copies of it.We want to identify all the common numbers in our list. Give
O(n log n) to solve the problem. (5)
Solution:We define R n to be the set of ordered n-tuples of real numbers, Rn := {(x1, x2 . . .
xn) : x1, . . . , xn ∈ R}.The elements of Rn are called vectors. Given a vector x = (x1, . . . , xn),
11 the numbers x1, . . . , xn are called the components of x. You are already quite familiar with
Rnfor small values of n.
Q: Find the out cost A1=5 x 4 A2= 4 x 6 A3= 6x2 (2 marks)
Solution:-((A1A2)A3) = (5 · 4 · 6) + (5 · 6 · 2)= 180 (A1(A2A3)) = (4 · 6 · 2) + (5 · 4 · 2) =
88

[Type the company name]

 CS502 – Design & Analysis of Algorithms Midterm
2013
Q: How to construct an optimal solution for o/1 knapsack problem?
Sol: Construction of optimal solution: Construct an optimal solution from computed
information. Let us try this: If items are labelled 1, 2, . . . , n, then a subproblem would be to
find an optimal solution for S k = items labelled 1, 2, . . . , k This is a valid subproblem
definition. The question is: can we describe the final solution S n in terms of subproblems S
k ? Unfortunately, we cannot do that. Here is why. Consider the optimal solution if we can
choose items 1 through 4 only. Solution Items chosen are 1, 2, 3, 4 Total weight: 2 + 3 + 4 +
5 = 14 Total value: 3 + 4 + 5 + 8 = 20 Now consider the optimal solution when items 1
through 5 are available
Q: Effect of calling max heap
Solution:-The smallest key is in the root in a min heap; in the max heap, the largest is in the
root.
Q: Suggest the criteria for measuring algorithms. Also discuss the issues need to be
discussed in the algorithm design.
Solutions:- In order to design good algorithms, we must first agree the criteria for
measuring algorithms. The emphasis in this course will be on the design of efficient
algorithm, and hence we will measure algorithms in terms of the amount of computational
resources that the algorithm requires. These resources include mostly running time and
memory. Depending on the application, there may be other elements that are taken into
account, such as the number disk accesses in a database program or the communication
bandwidth in a networking application
Q: Write the STABLE OR IN-PLACE of QUICK, HEAP, COUNTING, MERGE Sorts. [5
MARKS]
Answer: In-place Stable In-place Stable
------------------- Merge sort Bubble sort Bubble sort
Quick sort ------------------- Insertion sort Insertion sort
Heap sort ------------------- Selection sort --------------------
------------------- Counting sort

Q: Define MEMOIZATION? [2 MARKS]

Answer: We can avoid unnecessary repetition by write down the recursive calls and look
them when we need.
Define worst case and average case of Quick sort?
Answer: Worst case: We maximize over all possible values of q, means the selection of
pivot q which gives the maximum (worst) time for sorting. The worst case running time is
O (n2). Average case: Average case analysis of quick sort, the average is computed over all
possible random choices of the pivot index q. The average case running time for quick sort
is . (n log n).
Q-We can avoid unnecessary repetitions for recursive calls?( I thnk how can we ...)
[PAGE 74]
12 Answer: By using Fibonacci Sequence We can avoid this unnecessary repetition by writing
down the results of recursive calls and looking them up again if we need them later. This
process is called memoization.
Spelling correction in edit distance? 3 marks

[Type the company name]

 CS502 – Design & Analysis of Algorithms Midterm
2013
Answer: Spelling Correction: If a text contains a word that is not in the dictionary, a
'close' word, i.e. one with a small edit distance, may be suggested as a correction. Most
word processing applications, such as Microsoft Word, have spelling checking and
correction facility. When Word, for example, finds an incorrectly spelled word, it makes
suggestions of possible replacements.
Q-What is Bubble sort? Answer: Bubble sort: Scan the array. Whenever two consecutive
items are found that are out of order, swap them. Repeat until all consecutive items are in
order.
Q-What is the worst case running time for the Quick sort? What simple change is
required in the algorithm to preserve its linear expected running time and makes it
worst case time .(n log n).
Answer Worst case running time is O (n). The simple change which can change the running
time of the edit distance
Algorithm is the number of entries n2.
Q: In edit distance what is the simple change that can change the worst case time?
Ans: The simple change which can change the running time of edit distance algorithm is the
number of entries n2,or you can say the term n. In other words you can say the length of
the strings determine the running time of the computation.
Q:Define the worst case of edit distance algorithm?
Answer: The worst case running time of edit distance DP algorithm is O (n2), which is the
number of entries in the table n2 as each entry need constant time to compute.
Q:Average-case Analysis of Quicksort
Answer: Average case analysis of Quick sort: The running time of Quick sort depends on
the selection of pivot q which is done randomly. For average case analysis of quick sort,
average is computed over all possible random choices of the pivot index q. The average
case running time for quick sort is. (N log n).
Q: Worst case Analysis of Quick sort?
Answer: Worst case analysis of Quick sort: For worst case we maximize over all possible
values of q, means the selection of pivot q which gives the maximum (worst) time for
sorting. The chances are that the pivot values q=1 (start) or n (end) or n/2 (middle)
happens to give maximum time values. The worst case running time is O (n2).
Q: What is radix sort and explain it with examples.
Answer: Radix sort: In linear time sorting, counting sort is used for the numbers in the
range 1 to k where k is small and it is based on determining the rank of each number in
final sorted array. But it is useful only for small integers i.e., 1...k where k is small. But if k
were very large, then the size of the rank array formed would also be very large which is
not efficient. So solution for such cases is the Radix sort which works by sorting one digit at
a time. Example:
841 84[1] 8[4]1 [1]85
185 37[3] 3[7]3 [3]73
373 18[5] 1[8]5 [8]41
13 Q: Essential constraint for the counting sort.
Answer: Essential constraint for the counting sort is that numbers to be sorted must be
small integers i.e., 1...k where k is small.
Q: Better appropriate to cope with chain matrix multiplication.

[Type the company name]

 CS502 – Design & Analysis of Algorithms Midterm
2013
Answer: Better appropriate to cope with chain matrix multiplication is to do its Dynamic
Programming formulation. It is breaking up the problem into sub problems, solving and
string and then combining solutions to those sub problems to solve the global problem.
Q: Heapify procedure and Build Heap explain in simple words with example.
Answer: If an element in the Heap is not at its proper place means it is violating the Heap
Order, the Heapify procedure is used to fix it and place it at its proper position. In Heapify,
we recursively swap the element with its larger one child and stop at a stage when this
element is larger than both of its children or it becomes the leaf node.
Build Heap procedure is used for building Heap from any list and it is done by applying the
Heapify procedure on each element starting from bottom and going upward to the root.
Starting is done at second last level as the leaf nodes have no children so already in heap
order.
Q: Difference between worst case \Average cases Analysis of Quicksort explain in
simple words with example.
Answer: The running time of Quick sort depends on the selection of pivot q which is done
randomly. For worst case we maximize over all possible values of q, means the selection of
pivot q which gives the maximum (worst) time for
Sorting. The chances are that the pivot values q=1 (start) or n (end) or n/2 (middle)
happen to give maximum time values. The worst case running time is O (n2). For average
case analysis of quick sort, the average is computed over all possible random choices of the
pivot index q. The average case running time for quick sort is. (n log n).
Q: Edit Distance in Speech Recognition.
Answer: Algorithm is similar to those for the edit-distance problem is used in some speech
recognition systems. Find a close match between a new utterance and one in library of
classified utterance.
Q: What is sorting? Describe slow running sorting algorithms. 5 marks
Answer: Sorting is the process of arranging items in sequence. Slow running sorting
algorithms: [PAGE 39]
There are a number of well-known slow O(n2) sorting algorithms. 1. Bubble sort: Scan the
array. Whenever two consective item are found that are out of order, swap them. Repeat
until all consecutive items are in order.
2. Insertion sort: 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. 3.
Selection sort: Assume that A[1.i-1] contain the i-1 smallest element in A[i.n] swap it with
A[i].
Q: What is Catalan Numbers and write their formula. 3 marks
Answer: The Catalan numbers are famous functions in combinatrics.
Formula:

Slow Bubble sort: Insertion sort Selection sort: O(n2)

14 Fast Quicksort Merge sort Heap sort O(n log n)
Fastest Count Radix Bucket Ω(n log n)
Lower Bounds for Sorting: The best we have seen so far is O(n log n) algorithms for
sorting. Is it possible to do better than O(n log n)? If a sorting algorithm is solely based on

[Type the company name]

 CS502 – Design & Analysis of Algorithms Midterm
2013
comparison of keys in the array then it is impossible to sort more efficiently than (n log n)
time. All algorithms we have seen so far are comparison-based sorting algorithms. Consider
sorting three numbers a1, a2, and a3. There are 3! = 6 possible combinations:
(a1, a2, a3), (a1, a3, a2) , (a3, a2, a1)
(a3, a1, a2), (a2, a1, a3) , (a2, a3, a1)
One of these permutations leads to the numbers in sorted order. The comparison based
algorithm defines a decision tree. Here is the tree for the three numbers.
Q: Following is the cost table for chain matrix multiplication problem with initial
state. Mark the cells with question mark “?” which are updated after first iteration
Ans: m[1, 2] = m[1, 1] +m[2, 2] + p0 · p1 · p2 = 0 + 0 + 5 · 4 · 6 = 120
m[2, 3] = m[2, 2] +m[3, 3] + p1 · p2 · p3 = 0 + 0 + 4 · 6 · 2 = 48
m[3, 4] = m[3, 3] +m[4, 4] + p2 · p3 · p4 = 0 + 0 + 6 · 2 · 7 = 84
m[4, 5] = m[4, 4] +m[5, 5] + p3 · p4 · p5 = 0 + 0 + 2 · 7 · 3 = 42
Q: Why do we analyze the average case performance of a randomized algorithm and
not its worst case performance?
Average case performance :The analysis of the algorithm’s performance is the same for
all inputs.In this case the average is computed over all possible random choices that the
algorithm might make for the choice of the pivot index in the second step of the QuickSort
procedure. worst case performance is a recursive program, it is natural to use a
recurrence to describe its running time. But unlike MergeSort, where we had control over
the sizes of the recursive calls, here we do not. It depends on how the pivot is chosen.
Suppose that we are sorting an array of size n, A[1 : n], and further suppose that the pivot
that we select is of rank q, for some q in the range 1 to n. It takes _(n) time to do the
partitioning and other overhead, and we make two recursive calls. The first is to the
subarray A[1 : q − 1] which has q − 1 elements, and the other is to the subarray A[q + 1 : n]
which has n − q elements. So if we ignore the _(n) (as usual) we get the recurrence: T(n) =
T(q − 1) + T(n − q) + n
Q: Suggest and describe modifications of the implementation of “QuickSort” that will
improve its performance.
Ans:The running time of quicksort depends heavily on the selection of the pivot. If the rank
of the pivot is very large or very small then the partition (BST) will be unbalanced. Since
the pivot is chosen randomly in our algorithm, the expected running time is O(n log n). The
worst case time, however, is O(n2). Luckily, this happens rarely.

15

[Type the company name]

 CS502 – Design & Analysis of Algorithms Midterm
2013

Algorithm: Informal Definition: An algorithm is any well-defined computational

procedure that takes some values, or set of values, as input and produces some value, or set
of values, as output. An algorithm is thus a sequence of computational steps that transform
the input into output.
Algorithms, Programming: A good understanding of algorithms is essential for a good
understanding of the most basic element of computer science: programming. Unlike a
program, an algorithm is a mathematical entity, which is independent of a specific
programming language, machine, or compiler.
A RAM is an idealized machine with an infinitely large random-access memory.
Instructions are
executed one-by-one (there is no parallelism).
2-dimension maxima: Let us do an example that illustrates how we analyze algorithms.
Suppose you want to buy a car. You want the pick the fastest car. But fast cars are
expensive; you want the cheapest. You cannot decide which is more important: speed or
price. Definitely do not want a car if there is another that is both faster and cheaper. We say
that the fast, cheap car dominates the slow, expensive car relative to your selection criteria.
So, given a collection of cars, we want to list those cars that are not dominated by any other.
Here is how we might model this as a formal problem.
• Let a point p in 2-dimensional space be given by its integer coordinates, p = (p.x, p.y). A
point p is said to be dominated by point q if p.x _ q.x and p.y _ q.y. • Given a set of n points, P
= {p1, p2, . . . , pn} in 2-space a point is said to be maximal if it is not
dominated by any other point in P.
Running Time Analysis: The main purpose of our mathematical analysis will be
measuring the execution time. We will also be concerned about the space (memory)
required by the algorithm. The running time of an implementation of the algorithm would
depend upon the speed of the computer, programming language, optimization by the
compiler etc. Although important, we will ignore these technological issues in our analysis.
To measure the running time of the brute-force 2-d maxima algorithm, we could count the
number of steps of the pseudo code that are executed or, count the number of times an
element of P is accessed or, the number of comparisons that are performed.
Worst-case time is the maximum running time over all (legal) inputs of size n. Let I denote
16 an input instance, let |I| denote its length, and let T(I) denote the running time of the
algorithm on input I. Then Tworst(n) = max |I|=n T(I)

[Type the company name]

 CS502 – Design & Analysis of Algorithms Midterm
2013
Average-case time 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 being the probabilities: Tavg(n) =X |I|=n p(I)T(I)
We will almost always work with worst-case time. Average-case time is more difficult to
compute; it is difficult to specify probability distribution on inputs. Worst-case time will
specify an upper limit on the running time. Worst-case running time is _(n2). This is called
the symptotic growth rate of the function.
Sorting takes _(n log n); we will show this later when we discuss sorting. The for loop
executes ntimes. The inner loop (seemingly) could be iterated (n − 1) times. It seems we
still have an n(n ‫ סּ‬1) or ‫(סּ‬n2) algorithm.
Asymptotic Notation: You may be asking that we continue to use the notation _() but have
never defined it. Let’s remedy this
now. Given any function g(n), we define _(g(n)) to be a set of functions that asymptotically
equivalent
to g(n). Formally: _(g(n)) = {f(n) | there exist positive constants c1, c2 and n0 such that 0 _
c1g(n) _ f(n) _ c2g(n) for all n _ n0}
Lower bound: f(n) grows asymptotically at least as fast as n2. For this, need to show that
there exist positive constants c1 and n0, such that f(n) _ c1n2 for all n _ n0. Consider the
reasoning
f(n) = 8n2 + 2n − 3 _ 8n2 − 3 = 7n2 + (n2 − 3) _ 7n2 Thus c1 = 7. We implicitly assumed that
2n _ 0 and n2 − 3 _ 0 These are not true for all n but if n _ p3, then both are true. So select n0
_ p3. We then have f(n) _ c1n2 for all n _ n0.
Upper bound: f(n) grows asymptotically no faster than n2. For this, we need to show that
there exist positive constants c2 and n0, such that f(n) _ c2n2 for all n _ n0. Consider the
reasoning f(n) = 8n2 + 2n − 3 _ 8n2 + 2n _ 8n2 + 2n2 = 10n2
The O-notation is used to state only the asymptotic upper bounds.
The Ω-notation allows us to state only the asymptotic lower bounds.
Divide: the problem into a small number of pieces
Conquer: solve each piece by applying divide and conquer to it recursively
Combine: the pieces together into a global solution.
• (Divide:) split A down the middle into two subsequences, each of size roughly n/2
• (Conquer:) sort each subsequence by calling merge sort recursively on each.
• (Combine:) merge the two sorted subsequences into a single sorted list.
Sieve Technique The reason for introducing this algorithm is that it illustrates a very
important special case of
divide-and-conquer, which I call the sieve technique. We think of divide-and-conquer as
reaking the problem into a small number of smaller subproblems, which are then solved
recursively. The sieve technique is a special case, where the number of subproblems is just
1.
Selection Algorithm:It is easy to see that the rank of the The rank of the pivot x is q − p + 1
in A[p..r]. Let rank x = q − p + 1. If k = rank x then the pivot is kth smallest. If k < rank x then
17 search A[p..q − 1] recursively. If k > rank x then search A[q + 1..r] recursively. Find element
of rank (k − q) because we eliminated q smaller elements in A.
A heap is a left-complete binary tree that conforms to the heap order. The heap order
property: in a (min) heap, for every node X, the key in the parent is smaller than or equal to
the key in X. In other words, the parent node has key smaller than or equal to both of its

[Type the company name]

 CS502 – Design & Analysis of Algorithms Midterm
2013
children nodes. Similarly, in a max heap, the parent has a key larger than or equal both of
its children Thus the smallest key is in the root in a min heap; in the max heap, the largest is
in the root.
An in-place sorting algorithm is one that uses no additional array for storage. A sorting
algorithm is stable if duplicate elements remain in the same relative position after sorting.
Theorem 1: Any comparison-based sorting algorithm has worst-case running time (n log
n).
Edit Distance
The words “computer” and “commuter” are very similar, and a change of just one letter, p-
¿m, will change the first word into the second. The word “sport” can be changed into “sort”
by the deletion of the ‘p’, or equivalently, ‘sort’ can be changed into ‘sport’ by the insertion
of ‘p’. The edit distance of two strings, s1 and s2, is defined as the minimum number of
point mutations required to change s1 into s2, where a point mutation is one of: • change a
letter, • insert a letter or • delete a letter For example, the edit distance between FOOD and
MONEY is at most four:
FOOD −! MOOD −! MONfD −! MONED −! MONEY
Constructing the Optimal Solution
The algorithm for computing V[i, j] does not keep record of which subset of items gives the
optimal solution. To compute the actual subset, we can add an auxiliary boolean array
keep[i, j] which is 1 if we decide to take the ith item and 0 otherwise. We will use all the
values keep[i, j] to determine the optimal subset T of items to put in the knapsack as
follows:
• If keep[n,W] is 1, then n 2 T. We can now repeat this argument for keep[n − 1,W − wn].
• If kee[n,W] is 0, the n 62 T and we repeat the argument for keep[n − 1,W].

18

[Type the company name]