GATE CS Algorithms questions

Practise Algorithms questions for GATE CS. Explore official PYQs and original subject-wise quizzes, check answers and view available solutions. Free, no sign-in.

Compare greedy choices, dynamic-programming states and graph algorithms. Identify the input size before analysing the time and space complexity of each solution.

20 on this page

SubjectTopicYearType

How many minimum spanning trees does the following graph have? Draw them. (Weights are assigned to edges).

A language with string manipulation facilities uses the following operations head(s): first character of a string tail(s): all but exclude the first character of a string concat(s1, s2): s1s2 For the string "

acbc

" what will be the output of concat(head(s), head(tail(tail(s))))

Assume that

X

and

Y

are non-zero positive integers. What does the following Pascal program segment do? while X <> Y do if X > Y then X := X - Y else Y := Y - X; write(X);

For merging two sorted lists of sizes

m

and

n

into a sorted list of size

m+n

, we require comparisons of

In the following Pascal program segment, what is the value of X after the execution of the program segment? X := -10; Y := 20; If X > Y then if X < 0 then X := abs(X) else X := 2*X;

Merge sort uses:

Consider the following two functions:

g_1(n) = \begin{cases} n^3 \text{ for } 0 \leq n \leq 10,000 \\ n^2 \text{ for } n > 10,000 \end{cases}

g_2(n) = \begin{cases} n \text{ for } 0 \leq n \leq 100 \\ n^3 \text{ for } n > 100 \end{cases}

Which of the following is true?

Which of the following statements is false?

Algorithm design technique used in quicksort algorithm is?

The recurrence relation that arises in relation with the complexity of binary search is:

\displaystyle \sum_{1\leq k\leq n} O(n)

, where

O(n)

stands for order

n

is:

What does the following code do? var a, b: integer; begin a:=a+b; b:=a-b; a:=a-b; end;

Which of the following problems is not

\text{NP}

-hard?

Following algorithm(s) can be used to sort

n

in the range

[1\ldots n^3]

O(n)

time

Consider the following Pascal function: Function X(M:integer):integer; Var i:integer; Begin i := 0; while i*i < M do i:= i+1 X := i end The function call

X(N)

, if

N

is positive, will return

Kruskal’s algorithm for finding a minimum spanning tree of a weighted graph

G

with

n

vertices and

m

edges has the time complexity of:

The minimum number of comparisons required to sort

5

elements is ______

The complexity of comparison based sorting algorithms is:

A language uses an alphabet of six letters,

\left\{a, b, c, d, e, f\right\}

. The relative frequency of use of each letter of the alphabet in the language is as given below: …

A hash table with ten buckets with one slot per bucket is shown in the following figure. The symbols

S1

S7

initially entered using a hashing function with linear probing. The maximum number of comparisons needed in searching an item that is not present is