Dynamic Programming · Algorithms · GATE CSE

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

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)...

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...

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

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

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...

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

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...

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...

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...

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

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...

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...

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 ...

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 ...

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 ...

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 ...

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],...

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],...

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...

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