# Dynamic Programming · Algorithms · GATE CSE

Start Practice## Marks 1

GATE CSE 2016 Set 2

The Floyd-Warshall algorithm for all-pair shortest paths computation is based on

GATE CSE 2015 Set 1

Match the following:
List 1
(P) Prim’s algorithm for minimum spanning tree
(Q) Floyd-Warshall algorithm for all pairs shortest paths
(R) Mergesort
(S)...

GATE CSE 2011

An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array A[0:n−1] is given below.
Let Li, denote the l...

GATE CSE 2004

The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of

GATE CSE 1998

Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph?

## Marks 2

GATE CSE 2022

Let G(V, E) be a directed graph, where V = {1, 2, 3, 4, 5} is the set of vertices and E is the set of directed edges, as defined by the following adja...

GATE CSE 2021 Set 2

Consider the following directed graph:
Which of the following is/are correct about the graph?
...

GATE CSE 2021 Set 1

Consider the following undirected graph with edge weights as shown:
The number of minimum-weight spanning trees of the graph is ______
...

GATE CSE 2021 Set 1

Let G = (V, E) be an undirected unweighted connected graph. The diameter of G is defined as:
diam(G) = $$\displaystyle\max_{u, x\in V}$$ {t...

GATE CSE 2021 Set 1

Define Rn to be the maximum amount earned by cutting a rod of length n meters into one or more pieces of integer length and selling them. For i > 0...

GATE CSE 2018

Assume that multiplying a matrix $${G_1}$$ of dimension $$p \times q$$ with another matrix $${G_2}$$ of dimension $$q \times r$$ requires $$pqr$$ scal...

GATE CSE 2016 Set 2

Let $${A_1},{A_2},{A_3},$$ and $${A_4}$$ be four matrices of dimensions $$10 \times 5,\,\,5 \times 20,\,\,20 \times 10,$$ and $$10 \times 5,\,$$ respe...

GATE CSE 2015 Set 2

Given below are some algorithms, and some algorithm design paradigms.
.tg {border-collapse:collapse;border-spacing:0;border-color:#999;}
.tg td{font...

GATE CSE 2014 Set 2

Consider two strings A = “qpqrr” and B = “pqprqrp”. Let x be the length of the longest common subsequence (not necessarily contiguous) between A and B...

GATE CSE 2011

Four matrices M1, M2, M3 and M4 of dimensions p $$\times$$ q, q $$\times$$ r, r $$\times$$ s and s $$\times$$ t respectively can be multiplied is seve...

GATE CSE 2009

A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and ...

GATE CSE 2009

A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and ...

GATE CSE 2008

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1 ,a2 ,a3 ,…,an} and positive integer W, is there a subset of ...

GATE CSE 2008

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1 ,a2 ,a3 ,…,an} and positive integer W, is there a subset of ...

GATE CSE 2008

Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program is erroneous.
1. f(int Y[10],...

GATE CSE 2008

Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program is erroneous.
1. f(int Y[10],...

GATE CSE 1996

A binary search tree is generated by inserting in order the following integers:
50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24
The number of nodes in th...

GATE CSE 1991

Obtain the optimal binary search tree with equal probabilities for the
identifier set (a1, a2, a3) = ( if, stop, while)...