Algorithm Gate Previous Year Questions

Consider the following recurrence:

a) f(2ⁿ–1)=2ⁿ–1
b) f(2ⁿ)=1
c) f(5⋅2ⁿ)=2ⁿ⁺¹+1
d) f(2ⁿ+1)=2ⁿ+1

Which one of the following statements is TRUE for all positive functions f (n) ?

a) f(n²)=θ(f(n)²),when f(n) is a polynomial
b) f(n²)=o(f(n)²)
c) f(n²)=O(f(n)²),when f(n) is a exponential
d) f(n²)=Ω(f(n)²)

Let P be an array containing n integers. Let t be the lowest upper bound on the number of comparisons of the array elements, required to find the minimum and maximum values in an arbitrary array of n elements. Which one of the following choices is correct?

a) t>2n−2
b) t>3⌈n/2⌉ and t≤2n−2
c) t>n and t≤3⌈n/2⌉
d) t>⌈log2(n)⌉ and t≤n

Consider the following three functions.
f1 = 10ⁿ
f2 = n^logn
f3 = n^√n
Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?

a) f3,f2,f1
b) f2,f1,f3
c) f1,f2,f3
d) f2,f3,f1

What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order ?

a) Θ(n)
b) Θ(nlogn)
c) Θ(n²)
d) Θ(1)

What is the worst case time complexity of inserting n² elements into an AVL-tree with n elements initially ?

a) Θ(n⁴)
b) Θ(n²)
c) Θ(n²log(n))
d) Θ(n³)

For parameters a and b, both of which are ω(1), T(n)=T(n^1/a)+1, and T(b)=1. Then T(n) is

a) Θ(log_alog_bn)
b) Θ(log_abn)
c) Θ(log_blog_an)
d) Θ(log₂log₂n)

The number of permutations of the characters in LILAC so that no character appears in its original position, if the two L’s are indistinguishable, is ________ .

Consider a sequence of 14 elements: A = [-5, -10, 6, 3, -1, -2, 13, 4, -9, -1, 4, 12, -3, 0]. The subsequence sum ∑^j_k=iA[k]. Determine the maximum of S(i,j), where 0 ≤ i ≤ j < 14. (Divide and conquer approach may be used)

An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is _________.

There are n unsorted arrays: A₁, A₂, ....,A_n. Assume that n is odd. Each of A₁, A₂, ...., A_n contains n distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of A₁ ,A₂, ....,A_n is ________ .

a) Ο(n)
b) Ο(n²)
c) Ο(n log n)
d) Ω(n²log n)

Consider the following table

a) P-(ii), Q-(iii), R-(i)
b) P-(iii), Q-(i), R-(ii)
c) P-(ii), Q-(i), R-(iii)
d) P-(i), Q-(ii), R-(iii)

Consider the following functions from positives integers to real numbers

10, √n, n, log₂n, 100/n.

The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:

a) log₂n, 100/n,10, √n, n,
b) 100/n,10,log₂n, √n, n,
c) 10,100/n, √n,log₂n,n
d) 100/n,log₂n, 10,√n, n,

Consider the following intermediate program in three address code

a) p₁ = a - b
q₁ =p₁ * c
p₁= u * v
q₁ =p₁ + q₁

b) p₃= a - b
q₄= p₃* c
p₄= u * v
q₅ =p₄+ q₄

c) p₁ = a - b
q₁=p₂ * c
p₃= u * v
q₂= p₄ + q₃

d) p₁ = a - b
q₁= p * c
p₂= u * v
q₂= p + q

Let A₁, A₂, A₃, and A₄ be four matrices of dimensions 10 x 5, 5 x 20, 20 x 10, and 10 x 5, respectively. The minimum number of scalar multiplications required to find the product A₁ A₂A₃A₄ using the basic matrix multiplication method is______________.

Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex t at a distance four from the root. If t is the n-th vertex in this BFS traversal, then the maximum possible value of n is ________

N items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed.

An algorithm performs the following operations on the list in this order: Θ(N) delete, O(log N) insert, O(log N) find, and Θ(N) decrease-key What is the time complexity of all these operations put together

a) O(Log²N)
b) O(N)
c) O(N²)
d) Θ(N² Log N)

The Floyd-Warshall algorithm for all-pair shortest paths computation is based on

a) Greedy paradigm.
b) Divide-and-Conquer paradigm.
c) Dynamic Programming paradigm.
d) neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm.

Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE ?

I. Quicksort runs in Θ(n²) time
II. Bubblesort runs in Θ(n²) time
III. Mergesort runs in Θ(n) time
IV. Insertion sort runs in Θ(n) time

a) I and II only
b) I and III only
c) II and IV only
d) I and IV only

The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:

a) Θ(n log n), Θ(n log n) and Θ(n²)
b) Θ(n²), Θ(n²2) and Θ(n Log n)
c) Θ(n²), Θ(n log n) and Θ(n log n)
d) Θ(n²), Θ(n log n) and Θ(n²)

Consider two decision problems Q₁, Q₂ such that Q₁ reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to Q₂. Then which one of the following is consistent with the above statement?

a) Q₁ is in NP, Q₂ is NP hard
b) Q₂ is in NP, Q₁ is NP hard
c) Both Q₁ and Q₂ are in NP
d) Both Q₁ and Q₂ are in NP hard

Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n ( ≥ 2) numbers? In the recurrence equations given in the options below, c is a constant.

a) T(n)=2T(n/2)+cn
b) T(n)=T(n–1)+T(0)+cn
c) T(n)=2T(n–2)+cn
d) T(n)=T(n/2)+cn

Match the following

a) P-iii, Q-ii, R-iv, S-i
b) P-i, Q-ii, R-iv, S-iii
c) P-ii, Q-iii, R-iv, S-i
d) P-ii, Q-i, R-iii, S-iv

Let P be a QuickSort Program to sort numbers in ascending order using 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