Recent questions tagged dynamic-programming / GATE Overflow for GATE CSE

1 votes

0 answers

121

MadeEasy Subject Test: Algorithms - Dynamic Programming

debanjan sarkar

266 views

debanjan sarkar asked Dec 20, 2016

0 votes

2 answers

122

travelling salesman problem
Question - 14 question is what is the approch to solve it by dynamic programming ?

Question - 14 question is what is the approch to solve it by dynamic programming ?

priyanka gautam-piya

2.7k views

priyanka gautam-piya asked Dec 15, 2016

0 votes

1 answer

123

Ace Test Series: Algorithms - Dynamic Programming
the given answer is 10200 but i am getting 20100

the given answer is 10200 but i am getting 20100

tejas dadhe

461 views

tejas dadhe asked Dec 13, 2016

0 votes

0 answers

124

MadeEasy Test Series: Algorithms - Dynamic Programming
#plz check??

#plz check??

Hradesh patel

249 views

Hradesh patel asked Dec 12, 2016

0 votes

1 answer

125

Matrix Multiplication
Matrix multiplication is associative and matrix chain multiplication uses following matrices A1 is 30×35 A2 is 35×15 A3 is 15×5 A4 is 5×10 A5 is 10×20 A6 is 20×25 Find the minimum number of multiplications required to compute A1 A2 A3 A4A5A6

Matrix multiplication is associative and matrix chain multiplication uses following matricesA1 is 30×35A2 is 35×15A3 is 15×5A4 is 5×10A5 is 10×20A6 is 20×25Find the...

Rohan Mundhey

1.6k views

Rohan Mundhey asked Nov 11, 2016

2 votes

0 answers

126

Virtual Gate Test Series: Algorithms - Directed Graph

Hradesh patel

618 views

Hradesh patel asked Oct 6, 2016

2 votes

1 answer

127

GATE Overflow | Algorithms | Test 1 | Question: 16
The Matrix Chain-Product dynamic programming Algorithm runs in _______ linear time exponential time quadratic time cubic time

The Matrix Chain-Product dynamic programming Algorithm runs in _______linear timeexponential timequadratic timecubic time

Bikram

343 views

Bikram asked Oct 4, 2016

3 votes

2 answers

128

UGC NET CSE | August 2016 | Part 3 | Question: 31
Consider the problem of a chain <$A_{1} , A_{2} , A_{3},A_{4}$> of four matrices. Suppose that the dimensions of the matrices $A_{1} , A_{2} , A_{3}$ and $A_{4}$ are $30 \times 35, 35 \times 15, 15 \times 5$ ... minimum number of scalar multiplications needed to compute the product $A_{1}A_{2}A_{3}A_{4}$ is ____. $14875$ $21000$ $9375$ $11875$

Consider the problem of a chain <$A_{1} , A_{2} , A_{3},A_{4}$ of four matrices. Suppose that the dimensions of the matrices $A_{1} , A_{2} , A_{3}$ and $A_{4}$ are $30 \...

makhdoom ghaya

2.4k views

makhdoom ghaya asked Oct 1, 2016

1 votes

0 answers

129

Recurrence relation and probability
N rooms are there and they are numbered from 1 to N. A person P is in charge of room allocation and allocates these rooms inthe following way: Each query ask for two consecutive rooms. P selects two consecutive rooms out of the vacant ... selects (2,3) Seconds query onwards can not be processed. because although 1,4 are vacant, these rooms are not consecutive.

N rooms are there and they are numbered from 1 to N.A person P is in charge of room allocation and allocates these rooms inthe following way: Each query ask for two conse...

dd

516 views

dd asked Aug 22, 2016

1 votes

2 answers

130

UGC NET CSE | June 2016 | Part 3 | Question: 36
A triangulation of a polygon is a set of $T$ chords that divide the polygon into disjoint triangles. Every triangulation of $n$ vertex convex polygon has ____ chords and divides the polygon into ____ triangles $n-2, n-1$ $n-3, n-2$ $n-1, n$ $n-2, n-2$

A triangulation of a polygon is a set of $T$ chords that divide the polygon into disjoint triangles. Every triangulation of $n$ vertex convex polygon has ____ chords and ...

go_editor

2.3k views

go_editor asked Aug 20, 2016

3 votes

2 answers

131

UGC NET CSE | December 2013 | Part 3 | Question: 37
The longest common subsequence of the sequences $X=<A, B, C, B, D, A, B>$ and $Y=<B, D, C, A, B, A>$ has length $2$ $3$ $4$ $5$

The longest common subsequence of the sequences $X=<A, B, C, B, D, A, B>$ and $Y=<B, D, C, A, B, A>$ has length$2$$3$$4$$5$

go_editor

5.7k views

go_editor asked Jul 28, 2016

0 votes

1 answer

132

UGC NET CSE | September 2013 | Part 3 | Question: 39
The number of possible paranthesizations of a sequence of n matrices is O(n) $\theta$(n Ig n) $\Omega(2^n)$ None of the above

The number of possible paranthesizations of a sequence of n matrices isO(n)$\theta$(n Ig n)$\Omega(2^n)$None of the above

go_editor

1.3k views

go_editor asked Jul 24, 2016

2 votes

2 answers

133

Maximum Continuous Sum in an Array
Given an array of $n$ elements find the maximum continuous sum in it. For example consider the below array of $n=6$. 23 4 -10 2 15 1 Answer is 35.

Given an array of $n$ elements find the maximum continuous sum in it. For example consider the below array of $n=6$.23 4 -10 2 15 1Answer is 35.

Arjun

3.1k views

Arjun asked Jul 3, 2016

5 votes

1 answer

134

Optimal Substructure

geet.m

685 views

geet.m asked Jun 29, 2016

2 votes

3 answers

135

CMI2013-B-06b
Your final exams are over and you are catching up on watching sports on TV. You have a schedule of interesting matches coming up all over the world during the next week. You hate to start or stop watching a match midway, so your aim is ... dynamic programming to compute the maximum number of complete matches you can watch next week. Analyze the worse-case complexity of your algorithm.

Your final exams are over and you are catching up on watching sports on TV. You have a schedule of interesting matches coming up all over the world during the next week. ...

Arjun

1.7k views

Arjun asked Jun 8, 2016

3 votes

1 answer

136

CMI2015-B-07
There is a thin, long and hollow fibre with a virus in the centre. The virus occasionally becomes active and secretes some side products. The fibre is so thin that new side products secreted by the virus push the old products ... a single virus could possibly have produced the given sequence. Use dynamic programming, checking smaller subsequences before checking bigger subsequences.

There is a thin, long and hollow fibre with a virus in the centre. The virus occasionally becomes active and secretes some side products. The fibre is so thin that new si...

go_editor

511 views

go_editor asked May 27, 2016

2 votes

1 answer

137

CMI2014-B-05
At the end of its fifth successful season, the Siruseri Premier League is planning to give an award to the Most Improved Batsman over the five years. For this, an Improvement Index will be computed for each batsman. This is defined as the longest ... to compute the Improvement Index for a batsman with an overall sequence of $n$ scores. Analyze the complexity of your algorithm.

At the end of its fifth successful season, the Siruseri Premier League is planning to give an award to the Most Improved Batsman over the five years. For this, an Improve...

go_editor

532 views

go_editor asked May 27, 2016

1 votes

1 answer

138

What is the time complexity of Binary Knapsack?
I was reading some of the notes (made easy and ACE) and noticed that some teacher have taught that time complexity for Binary Knapsack O(2^(n/2)). which can not be reduced further. but What I have seen here that in ... techniques? Put some light, Am I missing something. Should I stop seeing those notes which people have posted over the internet.

I was reading some of the notes (made easy and ACE) and noticed that some teacher have taught that time complexity for Binary Knapsack O(2^(n/2)). which can not be reduc...

rude

2.6k views

rude asked May 23, 2016

1 votes

0 answers

139

CMI2012-B-06
A certain string-processing language offers a primitive operation which splits a string into two pieces. Since this operation involves copying the original string, it takes $n$ units of time for a string of length $n$, regardless of the location of the cut. Suppose, now ... pieces. You may assume that all m locations are in the interior of the string so each split is non-trivial.

A certain string-processing language offers a primitive operation which splits a string into two pieces. Since this operation involves copying the original string, it tak...

go_editor

1.4k views

go_editor asked May 23, 2016

33 votes

2 answers

140

GATE CSE 2008 | Question: 81
The subset-sum problem is defined as follows. Given a set of $n$ positive integers, $S = \{ a_1, a_2, a_3, \dots , a_n \}$, and positive integer $W$, is there a subset of $S$ whose elements sum to $W$? A dynamic program for solving this problem uses a $\text{2-dimensional}$ ... that there is a subset whose elements sum to $W$? $X[1, W]$ $X[n, 0]$ $X[n, W]$ $X[n-1, n]$

The subset-sum problem is defined as follows. Given a set of $n$ positive integers, $S = \{ a_1, a_2, a_3, \dots , a_n \}$, and positive integer $W$, is there a subset of...

go_editor

10.2k views

go_editor asked Apr 23, 2016

47 votes

3 answers

141

GATE CSE 2009 | Question: 54
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 $Y[n]$ of lengths $m$ and $n$, respectively with indexes of $X$ and $Y$ starting from $0$. We wish to find the length of ... $L[M, N]$. $L[p, q]$ needs to be computed before $L[r, s]$ if either $p<r$ or $q < s$.

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 $Y[n]$ of lengths ...

go_editor

14.5k views

go_editor asked Apr 23, 2016

2 votes

1 answer

142

In how many ways a rook can go from SouthEast to northwest corner of 8×8 chess board if travels only upwards or left?

Chetana Tailor

2.3k views

Chetana Tailor asked Apr 10, 2016

42 votes

7 answers

143

GATE CSE 2016 Set 2 | Question: 38
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$, respectively. The minimum number of scalar multiplications required to find the product $A_{1}A_{2}A_{3}A_{4}$ using the basic matrix multiplication method is _________.

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$, respectively. The minimum number of scala...

Akash Kanase

22.7k views

Akash Kanase asked Feb 12, 2016

21 votes

4 answers

144

GATE CSE 2016 Set 2 | Question: 14
The Floyd-Warshall algorithm for all-pair shortest paths computation is based on Greedy paradigm. Divide-and-conquer paradigm. Dynamic Programming paradigm. Neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm.

The Floyd-Warshall algorithm for all-pair shortest paths computation is based onGreedy paradigm.Divide-and-conquer paradigm.Dynamic Programming paradigm.Neither Greedy no...

Akash Kanase

7.3k views

Akash Kanase asked Feb 12, 2016

1 votes

1 answer

145

MadeEasy Test Series: Algorithms - Dynamic Programming
Given an array of n numbers, give an algorithm for finding a contiguous subsequence A(i) ...A(j) for which the sum of elements is maximum. Eg. [-2, 11, -4, 13, -5, 2] → 20 If dynamic programming approach is used then what is time complexity and space complexity? (a ... b.) O(n), O(n) (c.) O(n3), O(n) (d.) O(n2), O(1) Given answer is option (b.)

Given an array of n numbers, give an algorithm for finding a contiguous subsequence A(i) ...A(j) for which the sum of elements is maximum.Eg. [-2, 11, -4, 13, -5, 2] → ...

Utk

1.2k views

Utk asked Jan 11, 2016

4 votes

1 answer

146

Dynamic programming
Given an array which contains both positive and negative integers in it and asked to design an algorithm to find the maximum sum which does not contain two consecutive numbers.What is the time comlexity of efficient algorithm A) Θ(nlogn) B) Θ(n) C) Θ(n2) D) Θ(n2logn)

Given an array which contains both positive and negative integers in it and asked to design an algorithm to find the maximum sum which does not contain two consecutive nu...

Aditi Tiwari

1.2k views

Aditi Tiwari asked Dec 22, 2015

0 votes

2 answers

147

finding pair of an element in the array such that diff will be given no.

venky.victory35

729 views

venky.victory35 asked Dec 19, 2015

1 votes

1 answer

148

Travelling salesman problem vs. Minimum cost spanning tree vs. Shortest path
i want to understand these better.... please explain someone. Travelling salesman problem vs. Minimum cost spanning tree vs. Shortest path Also I was just wondering if there was any relation of TSP to GOOGLE' ... ) and there is no better solution other than dynamic programming. So do they use dynamic programming only?

i want to understand these better....please explain someone.Travelling salesman problem vs. Minimum cost spanning tree vs. Shortest pathAlso I was just wondering if there...

Aspi R Osa

935 views

Aspi R Osa asked Dec 15, 2015

2 votes

2 answers

149

longest common subsequence
For X= BDCABA and Y=ABCBDAB find length of lcs and no of such lcs..(solve it using table method)

For X= BDCABA and Y=ABCBDAB find length of lcs and no of such lcs..(solve it using table method)

Pooja Palod

9.3k views

Pooja Palod asked Dec 1, 2015

0 votes

1 answer

150

max subarray problem
What does find max subarray return when all elements of array are negative?

What does find max subarray return when all elements of array are negative?

Pooja Palod

502 views

Pooja Palod asked Oct 9, 2015

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true