Algorithms

For Micro Notes by the

1. Asymptotic Notations and Apriori Analysis Student

01. State True / False

1. 100n.logn = O(n.logn)
2. 2n+1 = O(2n)
3. 22n = O(2n)
4. 0<x<y then nx = O(ny)
5. (n+k)m  (nm) (k, m) > 0

6. log n  Olog log n 

7. log n is  (1/n)
2
8. 2n is O(n!)
9. n2 is O(22logn)
10. an  O(nx), a >1, x > 0
2
11. 2log 2 n is O( n2 )

02. Asymptotic Comparisons

01. f(n) = n, g(n) = log n
02. f(n) = n2logn, g(n) = n.log10n
03. f(n) = n3, 0 < n  10,000
= n, n > 10,000
g(n) = n, 0 < n  100
= n3, n > 100

03. Two Packages are available for processing a Data Base having 10x records.
Package ‘A’ takes a times of 10.n.logn while package B takes a time of
0.0001n2 for processing B records. Determine the smallest integer x for
which Package ‘A’ outperforms Package ‘B’.

ACE Engineering Academy Hyderabad|Delhi|Bhopal|Pune|Bhubaneswar| Lucknow|Patna|Bengaluru|Chennai|Vijayawada|Vizag|Tirupati|Kukatpally |Kolkata

 :2: Algorithms

04. Arrange the functions in increasing order of rates if growth For Micro Notes by the
2 n n Student
01. n ; n. log n; n n ; e ; n; 2 ; (1 / n ) .

02. 2n; n3/2; nlogn; nlogn

03. n(1/3); en; n7/4; nlog9n; 1.001n

05. Consider the following functions from positive integers to real numbers:
100
10, n , n , log 2 n , .
n
The CORRECT arrangement of the above functions in increasing order of
asymptotic complexity is:
100
(a) log 2 n , ,10, n , n
n
100
(b) , 10, log 2 n , n , n
n
100
(c) 10, , n , log 2 n , n
n
100
(d) , log 2 n , 10, n , n
n
06. Which of the following is TRUE?
f(n) is O(g(n))
g(n) is NOT O(f(n))
g(n) is O(h(n))
h(n) is O(g(n))

(a) f(n) is O(h(n)) (b) f(n) + h(n) is O(g(n)+h(n))

(c) h(n)  O(f(n)) (d) f(n) . g(n)  O(g(n)). h(n))

07. An element in an Array is called Leader if it is greater than all elements to

the right of it. The Time Complexity of the most efficient Algorithm to print
all Leaders of the given Array of size ‘n’ is _____.

ACE Engineering Academy Hyderabad|Delhi|Bhopal|Pune|Bhubaneswar| Lucknow|Patna|Bengaluru|Chennai|Vijayawada|Vizag|Tirupati|Kukatpally |Kolkata

 :3: Algorithms

08. Consider a Binary Tree where root is at level 1 and each other level ‘i’ of For Micro Notes by the
the binary Tree has exactly ‘i’ nodes. The height of such a binary Tree Student
having ‘n’ nodes is order of ______.

09. Consider the following operation along with EnQueue & DeQueue
operation on queues where ‘k’ is a global parameter.
MultiQueue (Q)
{
m = k;
while ((q is not empty) and (m > 0))
{
DeQueue (q);
m = m – 1;
}
}
What is the worst case time complexity of a sequence of ‘n’ Queue
operations on an initially empty Queue?
(a) O(n) (b) O(n+k)
(c) O(n.k) (d) O(n2)

10. A Queue is implemented using an Array such that EnQueue DeQueue

operations are performed efficiently. Which one of the following statements
is correct for a Queue of size ‘n’.
(a) Both operations can be performed in O(1)
(b) Worst complexity of both operation will be (n)
(c) Worst case time of both operation will be (logn)
(d) Atleast one operation can be performed in O(1) time and the worst case
time for the option will be (n).

ACE Engineering Academy Hyderabad|Delhi|Bhopal|Pune|Bhubaneswar| Lucknow|Patna|Bengaluru|Chennai|Vijayawada|Vizag|Tirupati|Kukatpally |Kolkata

 :4: Algorithms

For Micro Notes by the

Time Complexity Framework for Recursive Algorithms Student

11. Algorithm What (n)

{
if (n = 1) return;
else
{
What (n – 1);
B(n);
}
}

12. Algorithm A(n)

{
if (n = 2) return;
else
  
return A n ;
}

13. Algorithm Do_It (n)

{
if (n = 1) return;
else
return (Do_It (n – 1) + Do_It (n – 1));
}

14. Algorithm A(n)

{
if (n = 2) return;
else
    
return A n  A n ;
}

ACE Engineering Academy Hyderabad|Delhi|Bhopal|Pune|Bhubaneswar| Lucknow|Patna|Bengaluru|Chennai|Vijayawada|Vizag|Tirupati|Kukatpally |Kolkata

 :5: Algorithms

For Micro Notes by the

15. Algorithm Recur (n) Student
{
if (n = 1) return;
else
{
recur(n/2);
recur(n/2);
B(n);
}
}

16. T(n) = 2, n = 2
 
 n .T n  n , n>2
T(n) = 2 , n=2

17. The given diagram represents the flowchart of recursive algorithm A(n).
Assume that all statements except for the recursive calls have order(1) time
complexity. Then the best case & worst case time of this algorithm is
________.

Start

T(n/2) A(n/2)

yes
Return A(n/2) A(n/2) A(n/2) Return

0(1)
A(n/2)

A(n/2)

Return A(n/2) A(n/2) A(n/2) Return

ACE Engineering Academy Hyderabad|Delhi|Bhopal|Pune|Bhubaneswar| Lucknow|Patna|Bengaluru|Chennai|Vijayawada|Vizag|Tirupati|Kukatpally |Kolkata

 :6: Algorithms

For Micro Notes by the

18. void abc(char *s) Student
{
if(*s ! = ‘\0’)
{
printf(“%c”,*s);
abc(s + 1);
abc(s+1);
}
}

ACE Engineering Academy Hyderabad|Delhi|Bhopal|Pune|Bhubaneswar| Lucknow|Patna|Bengaluru|Chennai|Vijayawada|Vizag|Tirupati|Kukatpally |Kolkata

 :7: Algorithms

For Micro Notes by the

Running Times of Program Segments with Loops: Student

19. for i ← 1 to n
c = c + 1;

20. for i ← 1 to n
for j ← 1 to n/2
c = c + 1;

21. for i ← 1 to n
for j ← 1 to n/4
for k ← 1 to n
break;

22. for (i= 1; i < = n; + + i)

for (j = 1; j < = n; + + j)
for (k = n/2, k < = n; k + = n/2)
c = c + 1;

23. i = 1;
while (i < = n)
{
i = i * 2;
}

24. i = n;
while (i > 0)
{
i = i/2;
}

ACE Engineering Academy Hyderabad|Delhi|Bhopal|Pune|Bhubaneswar| Lucknow|Patna|Bengaluru|Chennai|Vijayawada|Vizag|Tirupati|Kukatpally |Kolkata

 :8: Algorithms

25. k = 1; i = 1; For Micro Notes by the

while (k < = n) Student
{
i++;
k=k+i;
}

26 for (i = 1; i < = n; ++i)

for (j = 1; j < n; j = 2 * j)
c + c + 1;

27. m = 2n
for (i = 1; i < = n; + + i)
for (j = 1; j < = m; j = 2 * j)
c=c+1

28. for i ← 1 to n
for j ← i to n

29. f n    O(n )
i 1

30. i = n;
while (i > 0)
{
j = 1;
while (j < = n)
{
j = 2 * j;
}
i = i/2;
}

ACE Engineering Academy Hyderabad|Delhi|Bhopal|Pune|Bhubaneswar| Lucknow|Patna|Bengaluru|Chennai|Vijayawada|Vizag|Tirupati|Kukatpally |Kolkata

 :9: Algorithms

31. int fun (int n) For Micro Notes by the

{ Student
int i, j, p, q = 0 ;
for (i = 1; i < = n ; + + i)
{
p = 0;
for (j = n; j > 1; j = j/2)
+ + p;
for (k = 1; k < p; k = k * 2)
+ + q;
}
return (q);
}

32. for (i = 1; i < = n; + + i)

{
j = 1;
while (j < = n)
j = 2 * j;
for (k = 1; k < = n; + + k)
c = c + 1;
}

k
33. n  22
for (i = 1; i < = n; + + i)
{
j = 2;
while (j < = n)
{
j = j * j;
pf(“*”);
}
}

ACE Engineering Academy Hyderabad|Delhi|Bhopal|Pune|Bhubaneswar| Lucknow|Patna|Bengaluru|Chennai|Vijayawada|Vizag|Tirupati|Kukatpally |Kolkata

 : 10 : Algorithms

34. A: Array [1 ……n] of binary; For Micro Notes by the

f(m) =  (m) Student
count: integer;
count = 1;
for i = 1 to n
{
if (A[i] = = 1) count + +;
else
{
f(count);
count = 1;
}
}

35. Assume that Merge Sort takes 30sec to Sort 64 elements in worst case. What
is the approximate number of elements that can be Sorted in the Worst Case
using Merge Sort using 6 minutes?

ACE Engineering Academy Hyderabad|Delhi|Bhopal|Pune|Bhubaneswar| Lucknow|Patna|Bengaluru|Chennai|Vijayawada|Vizag|Tirupati|Kukatpally |Kolkata

 : 11 : Algorithms

2. Greedy Method For Micro Notes by the

Student

36. Consider the weights and values of items listed below. Note that there is
only one unit of each item.
Item Weight Value
number (in Kgs) (in Rupees)
1 10 60
2 7 28
3 4 20
4 2 24

The task is to pick a subset of these items such that their total weight is no
more than 11 Kgs and their total value is maximized. Moreover, no item
may be split. The total value of items picked by an optimal algorithm is
denoted by Vopt. A greedy algorithm sorts the items by their value-to-weight
ratios in descending order and packs them greedily, starting from the first
item in the ordered list. The total value of items picked by the greedy
algorithm is denoted by Vgreedy. The value of Vopt – Vgreedy is____ .

37. We are given 9 tasks T1, T2…., T9. The execution of each task requires
one unit of time. We can execute one task at a time. Each task T1 has a
profit P i and a deadline di , Profit Pt is earned if the task is completed
before the end of the Deadline.

Task T1 T2 T3 T4 T5 T6 T7 T8 T9
Profit 15 20 30 18 18 10 23 16 25
Deadline 7 2 5 3 4 5 2 7 3

a. Are all tasks completed in the schedule that gives maximum profit?
(a) All tasks are completed
(b) T1 and T6 are left out
(c) T1 and T8 are left out
(d)T4 and T6 are left out
ACE Engineering Academy Hyderabad|Delhi|Bhopal|Pune|Bhubaneswar| Lucknow|Patna|Bengaluru|Chennai|Vijayawada|Vizag|Tirupati|Kukatpally |Kolkata
 : 12 : Algorithms

For Micro Notes by the

Student
b. What is the maximum profit earned?
(a) 147 (b) 165 (c) 167 (d) 175

38. The characters ‘a’ to ‘h’ have the set of frequencies based on the first 8
Fibonacci numbers as follows :

a:1, b:1, c:2, d:3, e:5, f:8, g:13, h:21

A Huffman code is used to represent the characters. What is the
sequence of characters corresponding to the following code?

110111100111010

(a) fdheg (b) ecgdf

(c) dchfg (d) fehdg

39. A message is made up entirely of characters from the set X = {P, Q, R, S,

T}. The table of probabilities for each of the characters is shown below:

Character Probability
P 0.22
Q 0.34
R 0.17
S 0.19
T 0.08
Total 1.00

If a message of 100 characters over X is encoded using Huffman coding,

then the expected length of the encoded message in bits is _________.

40. Consider a Graph whose vertices are points in a plane with integer
co-ordinates (x, y) where 1  x  n, 1  y  n, n > 2 is an integer. 2 vertices
<x1, y1> & <x2, y2> are adjacent iff |x1 – x2|  1 & |y1 – y2|  1. The cost of
such an edge is given by the distance between them. Compute the weight of
min cost Spanning Tree of such graph for a value of n.

ACE Engineering Academy Hyderabad|Delhi|Bhopal|Pune|Bhubaneswar| Lucknow|Patna|Bengaluru|Chennai|Vijayawada|Vizag|Tirupati|Kukatpally |Kolkata

 : 13 : Algorithms

41. Consider the following Graph whose Minimum Cost Spanning Tree marked For Micro Notes by the
with edge values has a weight of 36. Minimum possible sum of all edges of Student
the graph G is _____. (Assume that all edges have distinct cost).

B 15
E
4
A 2 F

9 6
C D

42. Consider a graph with ‘n’ vertices n > 2. The vertices are numbered V1 to
Vn. Two vertices Vi & Vj are adjacent iff 0 < | i – j|  2. The weight of such
an edge is i + j. The weight of minimum cost Spanning Tree of such a graph
for a value of n is _______.

43. Consider a complete weighted Graph with n vertices numbered V1 to Vn.

Two vertices Vi & Vj having edge between them has a cost value of 2|i – j|.
The weight of minimum cost Spanning Tree of such a graph is _______.

44. Let G be a complete undirected graph with 4 vertices and edge weights are
{1, 2, 3, 4, 5, 6}. The maximum possible weight that a minimum weight
Spanning Tree can have is _______.

45. Let G be a connected undirected graph of 100 vertices and 300 edges. The
weight of a minimum spanning tree of G is 500. When the weight of each
edge of G is increased by five, the weight of a minimum spanning tree
becomes_______.

46. Consider the following undirected graph G:

4 x

1 3

4 5

ACE Engineering Academy Hyderabad|Delhi|Bhopal|Pune|Bhubaneswar| Lucknow|Patna|Bengaluru|Chennai|Vijayawada|Vizag|Tirupati|Kukatpally |Kolkata

 : 14 : Algorithms

For Micro Notes by the

Choose a value for x that will maximize the number of minimum weight Student
spanning trees (MWSTs) of G. The number of MWSTs of G for this value
of x is_____.

47. Let w be the minimum weight among all edge weights in an undirected
connected graph. Let ‘e’ be a specific edge of weight ‘w’. Which of the
following is False?
i. There is a minimum Spanning Tree containing ‘e’ always.
ii. Every minimum Spanning Tree has an edge of weight ‘w’.
iii. ‘e’ is present in every minimum Spanning Tree.
iv. If ‘e’ is not present in a minimum Spanning Tree named ‘T’ then there
will be a cycle formed by adding ‘e’ to T.

48. G = (V, E) is an undirected simple graph in which each edge has a distinct
weight, and e is a particular edge of G. Which of the following statements
about the minimum spanning trees (MSTs) of G is/are TRUE?
I. If e is the lightest edge of some cycle in G, then every MST of G
includes e
II. If e is the heaviest edge of some cycle in G, then every MST of G
excludes e
(a) I only (b) II only
(c) both I and II (d) neither I nor II

49. Applying Dijkstra’s Algorithm over the given Graph, Which path is reported
from ‘S’ to ‘T’;

ACE Engineering Academy Hyderabad|Delhi|Bhopal|Pune|Bhubaneswar| Lucknow|Patna|Bengaluru|Chennai|Vijayawada|Vizag|Tirupati|Kukatpally |Kolkata

 : 15 : Algorithms

50. Let G be a weighted connected undirected graph with distinct positive edge For Micro Notes by the
weights. If every edge weight is increased by the same value, then which of Student

the following statements is/are true?

1. Minimum spanning Tree of the graph does not change.
2. Shortest path between any pair of vertices does not change.

51. Consider the weighted undirected graph with 4 vertices, where the weight of
edge {i,j} is given by the entry Wij in the matrix W.
0 2 8 5
2 0 5 8 
W
8 5 0 x
 
5 8 x 0
The largest possible integer value of x, for which at least one shortest path
between some pair of vertices will contain the edge with weight x is _____.

52. Let G = (V, E) be any connected undirected edge-weighted graph. The

weights of the edges in E are positive and distinct. Consider the following
statements:
(I) Minimum Spanning Tree of G is always unique.
(II) Shortest path between any two vertices of G is always unique.
Which of the above statements is/are necessarily true?
(a) (I) only (b) (II) only
(c) both (I) and (II) (d) neither (I) nor (II)

ACE Engineering Academy Hyderabad|Delhi|Bhopal|Pune|Bhubaneswar| Lucknow|Patna|Bengaluru|Chennai|Vijayawada|Vizag|Tirupati|Kukatpally |Kolkata

 : 16 : Algorithms

3. Components For Micro Notes by the

Student

53. A DFS is performed on DAG. Which of the following is true for all edges
(u, v) in the graph?
(a) d[u] < d[v] (b) d[u] < f[v]
(c) f[u] < f[v] (d) f[u] > f[v]

54. Consider a DFT of an undirected graph having ‘n’ vertices. In the traversal,
k edges are marked as Tree edges then the number of connected components
in the graph is given by
(a) k (b) k + 1 (c) n – k (d) n – k – 1

ACE Engineering Academy Hyderabad|Delhi|Bhopal|Pune|Bhubaneswar| Lucknow|Patna|Bengaluru|Chennai|Vijayawada|Vizag|Tirupati|Kukatpally |Kolkata

 : 17 : Algorithms

4. Heap For Micro Notes by the

Student

55. Valid binary Max-Heap

(a) <25, 12, 16, 13, 10, 8, 14> (b) <25, 14, 16, 13, 10, 8, 12>
(c) <25, 14, 13, 16, 10, 8, 12> (d) <25, 14, 12, 13, 10, 8, 16>

56. Valid 3-ary maximum Heap Array representation

(a) <1, 3, 5, 6, 8, 9> (b) <9, 6, 3, 1, 8, 5>
(c) <9, 3, 6, 8, 5, 1> (d) <9, 5, 6, 8, 3, 1>

57. To the valid Heap of Q55 insert elements < 7 2 10 4 > . Indicate the
resultant Heap in Array.

58. Level order traversal of a binary max Heap generates: <10, 8, 5, 3, 2>
Insert: <1 & 7> ; What is the resultant Level order Traversal?

59. In a binary max-Heap with n elements, the smallest element can be found in
time of ______.

60. Given binary Heap with ‘n’ elements & it is required to insert ‘n’ more
elements not necessarily one after another into this Heap. Total time
required for this operation is:
(a) O(n2) (b) nlogn (c) n (d) n2logn

61. Given binary Heap in Array with the smallest at the root, the 7th smallest
element can be found in time complexity of ______.

62. Consider binary Heap in an Array with n elements it is desired to insert an

element into the Heap if a binary search is performed along the path from
newly inserted element to the root then the no. of comparison made is order
of _________.

63. The approximate no. of elements that can be Sorted in O(logn) time using
Heap Sort is ________.

ACE Engineering Academy Hyderabad|Delhi|Bhopal|Pune|Bhubaneswar| Lucknow|Patna|Bengaluru|Chennai|Vijayawada|Vizag|Tirupati|Kukatpally |Kolkata

 : 18 : Algorithms

64. Given logn Sorted lists each having n/logn elements. The time For Micro Notes by the
complexity to merge the given list into a single Sorted list, using Heap data Student
structure is _____.

65. An operator delete(i) for a binary heap data structure is to be designed to

delete the item in the i-th node. Assume that the heap is implemented in an
array and i refers to the i-th index of the array. If the heap tree has depth d
(number of edges on the path from the root to the farthest leaf), then what is
the time complexity to re-fix the heap efficiently after the removal of the
element?
(a) O(1) (b) O(d) but not O(1)
d
(c) O(2 ) but not O(d) (d)O(d2d) but not O(2d)

66. The minimum number of interchanges needed to convert the array into a
max-heap is
89, 19, 40, 17, 12, 10, 2, 5, 7, 11, 6, 9, 70
(a) 0 (b) 1 (c) 2 (d) 3

67. An array of integers of size n can be converted into a heap by adjusting the
heaps rooted at each internal node of the complete binary tree starting at
the node (n–1)/2 and doing this adjustment up to the root node(root node
is at index 0) in the order (n–1)/2, (n–3)/2,...., 0. The time required to
construct a heap in this manner is
(a) O(log n) (b) O(n)
(c) O(n log log n) (d) O(n log n)

68. An array X of n distinct integers is interpreted as a complete binary tree. The

index of the first element of the array is 0. If only the root node does not
satisfy the heap property, the algorithm to convert the complete binary tree
into a heap has the best asymptotic time complexity of
(a) O(n) (b) O(log n)
(c) O(n log n) (d) O(n log log n)

ACE Engineering Academy Hyderabad|Delhi|Bhopal|Pune|Bhubaneswar| Lucknow|Patna|Bengaluru|Chennai|Vijayawada|Vizag|Tirupati|Kukatpally |Kolkata

 : 19 : Algorithms

69. Consider a complete binary tree where the left and right subtrees of the root For Micro Notes by the
are max-heaps. The lower bound for the number of operations to convert the Student
tree to a heap is
(a)  (log n) (b)  ( n)
(c)  (n log n) (d)  (n2)

70. Consider a max heap, represented by the array:

40, 30, 20, 10, 15, 16, 17, 8, 4.

Array 1 2 3 4 5 6 7 8 9
index

Value 40 30 20 10 15 16 17 8 4

Now consider that a value 35 is inserted into this heap. After insertion,
the new hope is
(a) 40, 30, 20, 10, 15, 16, 17, 8, 4, 35
(b) 40, 35, 20, 10, 30, 16, 17, 8, 4, 15
(c) 40, 30, 20, 10, 35, 16, 17, 8, 4, 15
(d) 40, 35, 20, 10, 15, 16, 17, 8, 4, 30

ACE Engineering Academy Hyderabad|Delhi|Bhopal|Pune|Bhubaneswar| Lucknow|Patna|Bengaluru|Chennai|Vijayawada|Vizag|Tirupati|Kukatpally |Kolkata

 : 20 : Algorithms

5. Sorting Techniques For Micro Notes by the

Student

71. Which of the following Sorting algorithms has lowest worst case
complexity?
i. Bubble Sort ii. Merge Sort
iii. Quick Sort iv. Selection Sort

72. Which of the following in place Sorting algorithm needs minimum number
of swaps?
(a) Selection Sort (b) Insertion Sort
(c) Heap Sort (d) Quick Sort

73. What would be the worst case complexity of Insertion Sort if the inputs are
restricted to permutation of 1 to n with at most ‘n’ Inversions?

74. Let ‘S’ be a Sorted Array of ‘n’ integers and T(n) denote the time taken for
the most efficient algorithm to determine if there are 2 elements in the Array
with the sum <1000.
(a) T(n) is O(1) (b) n  T(n)  n logn
(c) Tn   n C 2 (d) nlogn  Tn   n C 2

75. The traditional Insertion Sort to Sort an Array of n elements uses linear
search to identify the position where an element is to be inserted into already
Sorted part of the Array, if instead binary search is used to identify the
position of newly inserted element then the worst case complexity will be
order of ________.

76. In using Quick Sort suppose the central element of the Array is always
chosen as the Pivot then the worst case complexity of the Quick Sort may
be_____.

77. The Median on Array of size n can be found in O(n) time. If Median is
selected as Pivot, then the worst case complexity of Quick Sort is ______.

ACE Engineering Academy Hyderabad|Delhi|Bhopal|Pune|Bhubaneswar| Lucknow|Patna|Bengaluru|Chennai|Vijayawada|Vizag|Tirupati|Kukatpally |Kolkata

 : 21 : Algorithms

78. In applying Quick Sort to an unsorted list if (n/4)th Smallest element is For Micro Notes by the
selected as Pivot with a time complexity of O(n), then the Time Complexity Student
of Quick Sort will be______.

79. Consider the Quicksort algorithm. Suppose there is a procedure for finding
a pivot element which splits the list into two sub lists each of which contains
at least one-fifth of the elements. Let T(n) be the number of comparisons
required to sort n elements. Then
(a) T(n)  2T(n/5)+n (b) T(n)  T(n/5)+T(4n/5)+n
(c) T(n)  2T(4n/5)+n (d) T(n)  2T(n/2)+n

80. Which one of the following in place sorting algorithms needs the minimum
number of swaps?
(a) Quick sort (b) Insertion sort
(c) Selection sort (d) Heap sort

81. If one uses straight two-way merge sort algorithm to sort the following
elements in ascending order:
20, 47, 15, 8, 9, 4, 40, 30, 12, 17
then the order of these elements after second pass of the algorithm is:
(a) 8, 9, 15, 20, 47, 4, 12, 17, 30, 40
(b) 8, 15, 20, 47, 4, 9, 30, 40, 12, 17
(c) 15, 20, 47, 4, 8, 9, 12, 30, 40, 17
(d) 4, 8, 9, 15, 20, 47, 12, 17, 30, 40

82. You have n lists, each consisting of m integers sorted in ascending order.
Merging these lists into a single sorted list will take time:
(a) O(nm log m) (b) O(mn log m)
(c) O(m + n) (d) O(mn)

83. If we use Radix Sort to sort n integers in the range (nk/2, nk], for some
k > 0 which is independent of n, the time taken would be
(a) (n) (b) (kn)
(c) (n log n) (d) (n2)
ACE Engineering Academy Hyderabad|Delhi|Bhopal|Pune|Bhubaneswar| Lucknow|Patna|Bengaluru|Chennai|Vijayawada|Vizag|Tirupati|Kukatpally |Kolkata
 : 22 : Algorithms

For Micro Notes by the

Student

84. The worst case running times of Insertion sort, Merge sort and Quick sort,
respectively are:
(a) (n log n), (n log n) and (n2)
(b) (n2), (n2) and (n log n)
(c) (n2), (n log n) and (n log n)
(d) (n2), (n log n) and (n2)

85. Let P be a quick sort program to sort numbers in ascending order.

Let t1 and t2 be the time taken by the program for the inputs [1 2 3 4]
and [5 4 3 2 1], respectively. Which of the following holds?
(a) t1= t2 (b) t1 > t
(c) t1< t2 (d) t1= t2 = 5 log 5

86. Let P be a Quick Sort Program to sort numbers in ascending order suing the
first element as pivot. Let t1 and t2 be the number of comparisons made by
P for the inputs {1, 2, 3, 4, 5} and {4, 1, 5, 3, 2} respectively.
Which one of the following holds?
(a) t1 = 5 (b) t1 < t2
(c) t1 > t2 (d) t1 = t2

87. Quick-sort is run on two inputs shown below to sort in ascending order
taking first element as pivot
i. 1, 2, 3….n
ii. n, n1, n 2,…,2,1
Let C1 and C2 be the number of comparisons made for the inputs (i) and
(ii) respectively. Then,
(a) C1 < C2 (b) C1 > C2
(c) C1 = C2 (d) We cannot say anything for arbitrary n

ACE Engineering Academy Hyderabad|Delhi|Bhopal|Pune|Bhubaneswar| Lucknow|Patna|Bengaluru|Chennai|Vijayawada|Vizag|Tirupati|Kukatpally |Kolkata

 : 23 : Algorithms

88. Following algorithm(s) can be used to sort n in the range [1..n3] in O(n) time For Micro Notes by the
(a) Heap sort (b) Quick sort Student
(c) Merge sort (d) Radix sort

89. For merging two sorted lists of sizes m and n into a sorted list of
size m+n, we require comparisons of
(a) O(m) (b) O(n)
(c) O(m+n) (d) O(log m+ log n)

90. Give the correct matching for the following pairs:

(A) O(log n) (P) Selection sort
(B) O(n) (Q) Insertion sort
(C) O(n log n) (R) Binary search
(D) O(n2) (S) Merge sort

ACE Engineering Academy Hyderabad|Delhi|Bhopal|Pune|Bhubaneswar| Lucknow|Patna|Bengaluru|Chennai|Vijayawada|Vizag|Tirupati|Kukatpally |Kolkata