Design Algorithm Analysis GATE CS and IT previous year questions with Answer

Ques 21 Gate 2016 Set-2

---

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

See Answer Video Solution

Ques 22 Gate 2016 Set-1

---

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

See Answer Video Solution

Ques 23 Gate 2015 Set-2

---

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

See Answer Video Solution

Ques 24 Gate 2015 Set-1

---

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

See Answer Video Solution

Ques 25 Gate 2015 Set-1

---

Match the following

(P) Prim’s algorithm for minimum spanning tree	(i) Backtracking
(Q) Floyd-Warshall algorithm for all pairs shortest paths	(ii) Greedy method
(R) Mergesort	(iii) Dynamic programming
(S) Hamiltonian circuit	(iv) Divide and conquer

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

See Answer Video Solution

Ques 26 Gate 2014 Set-1

---

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

See Answer Video Solution