# Algorithms subject in GATE

## ALGORITHMS |Gate-1993| Previous Year Questions| Set-15

ALGORITHMS |Gate-1993| The root directory of a disk should be placed : [GATE – 1993] a. at a fixed address in main memoryb. at a fixed location on the diskc. anywhere on the diskd. at a fixed location on the system diske. anywhere on the system disk Answer : b) Consider a simple connected graph …

## 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-2004| Previous Year Questions| Set-12

ALGORITHMS |Gate-2004| 1. 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 …

## ALGORITHMS |Gate-2005| Previous Year Questions| Set-11

ALGORITHMS |Gate-2005| The numbers 1, 2, …. n are inserted in a binary search tree in some order. In the resulting tree, the right subtree of the root contains p nodes. The first number to be inserted in the tree must be : [GATE – 2005] a. pb. p+1c. n-pd. n-p+1 Answer : c) In …

## 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-2014| Previous Year Questions| Set-7

ALGORITHMS |Gate-2014| 1. There are 5 bags labeled 1 to 5.  All the coins in a given bag have the same weight.  Some bags have coins of weight 10 gm, others have coins of weight 11 gm.  I pick 1, 2, 4, 8, 16 coins respectively from bags 1 to 5.  Their total weight comes …

## 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) …