# ALGORITHMS |Gate-2008| Previous Year Questions| Set-10

ALGORITHMS |Gate-2008|

1. 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 : [GATE – 2008]

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

1. The subset-sum problem is defined as follows: Given a set S of n positive integers and a positive integer W, determine whether there is a subset of S Whose elements sum to An algorithm Q solves this problem in O(nW) time. Which of the following statements is false? [GATE – 2008]

a. Q solves the subset-sum problem in polynomial time when the input is encoded in unary
b. Q solves the subset-sum problem in polynomial time when the input is encoded in binary
c. The subset sum problem belongs to the class NP
d. The subset sum problem is NP-hard

ALGORITHMS |Gate-2008|

1. Dijkstra’s single source shortest path algorithm when run from vertex in the above graph, computes the correct shortest path distance to : [GATE – 2008]

a. only vertex a
b. only vertices a, e, f, g, h
c. only vertices a, b, c, d
d. all the vertices