# Algorithm ## ALGORITHMS |Gate-1994| Previous Year Questions| Set-14

ALGORITHMS |Gate-1994| FORTRAN implementation do not permit recursion because : [GATE – 1994] a. they use static allocation for variablesb. they use dynamic allocation for variablesc. stacks are not available on all machinesd. it is not possible to implement recursion on all machines Answer : a) The recurrence relation that arises in relation with the … ## ALGORITHMS |Gate-1995| Previous Year Questions| Set-13

ALGORITHMS |Gate-1995| Merge sort uses : [GATE – 1995] a. Divide and conquer strategyb. Backtracking approachc. Heuristic searchd. Heuristic search Answer : a) For merging two sorted lists of sizes m and n into a sorted list of size m+n, we required comparisons of : [GATE – 1995] a. O(m)b. O(n)c. O(m+n)d. O(logm+logn) Answer : c) … ## ALGORITHMS |Gate-2008| Previous Year Questions| Set-10

ALGORITHMS |Gate-2008| 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) + … ## ALGORITHMS |Gate-2012| Previous Year Questions| Set-9

ALGORITHMS |Gate-2012| Assuming P ≠ NP, which of the following is TRUE? [GATE – 2012] a. NP-complete = NPb. NP-complete ∩ P = ∅c. NP-hard = NPd. P = NP-complete Answer : b) Let W(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size … ## ALGORITHMS |Gate-2013| Previous Year Questions| Set-8

ALGORITHMS |Gate-2013| 1. Which one of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort? [GATE – 2013] a. O(log n)b. O(n)c. O(n log n)d. O(n2) Answer : b) 2. Which one of the following is the tightest upper bound that represents the … ## ALGORITHMS |Gate-2015| Previous Year Questions| Set-6

ALGORITHMS |Gate-2015| 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. [GATE – 2015] a. T(n) = 2T(n/2) + cnb. T(n) = T(n – 1) + T(1) …