The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
Google Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged dynamicprogramming
+1
vote
0
answers
1
Dynamic Programming(Cormen)
Why we need to do topdown and bottomup these 2 approach in dynamic programming? I know bottomup has better overhead. Then why not bottom up used everywhere? Both have time complexity $O(n^{2})$ right? Plz analysis these two algo for more clearity topdown bottomup
asked
20 hours
ago
in
Algorithms
by
srestha
Veteran
(
91.8k
points)

11
views
algorithms
dynamicprogramming
0
votes
0
answers
2
selfdoubt
While solving the problem of longest match subsequence we use the concept of dynamic programming which further uses tabulation. For given 2 strings we can create a table using 2D matrix but how we'll draw the same table for 3 or more number of strings?
asked
Aug 10
in
Algorithms
by
AIkiran01
(
163
points)

21
views
algorithms
dynamicprogramming
+1
vote
1
answer
3
#Algorithms Time Complexity Analysis of Multistage Graph using Bottom Up Dynamic Programming
asked
Jun 3
in
Algorithms
by
iarnav
Loyal
(
7.9k
points)

93
views
algorithms
dynamicprogramming
0
votes
0
answers
4
Recursion Tree
What is the max height of recursion tree of recurrence $c(100,50)$? here, the recursive function is defined as $c(n,k) = c(n1,k1) + c(n,k1)$ terminating condition $c(n,n) = 1, c(n,0) = 1$.
asked
Apr 28
in
Algorithms
by
hacker16
Active
(
2.7k
points)

66
views
algorithms
recursion
dynamicprogramming
+1
vote
0
answers
5
Counting No of Trees  College Exam
Want help with part (a). Other parts can be done accordingly. According to the solution, I understand how to find the limits of the sum, but why is there a factor of 2 with T(k) * T(nk1), according to my understanding it should not be there ... ) is the count of right subtrees, so there are only T(k)*T(nk1) possibilities for each k, sum over the limits
asked
Mar 25
in
Algorithms
by
Yash Khanna
(
271
points)

69
views
binarytree
algorithms
dynamicprogramming
permutationsandcombinations
0
votes
0
answers
6
Dynamic programmingtabulation method bottom up
asked
Feb 22
in
Algorithms
by
Surajit
Active
(
3.1k
points)

128
views
dynamicprogramming
+6
votes
5
answers
7
GATE201831
Assume that multiplying a matrix $G_1$ of dimension $ p \times q$ with another matrix $G_2$ of dimension $q \times r$ requires $pqr$ scalar multiplications. Computing the product of $n$ matrices $G_1G_2G_3 \dots G_n$ can be done by ... scalar multiplications, the explicitly computed pairs is/are $F_1F_2$ and $F_3F_4$ only $F_2F_3$ only $F_3F_4$ only $F_2F_2$ and $F_4F_5$ only
asked
Feb 14
in
Algorithms
by
gatecse
Boss
(
18.1k
points)

2k
views
gate2018
algorithms
dynamicprogramming
+1
vote
0
answers
8
ace test
I got 206???
asked
Jan 21
in
Algorithms
by
Deepak Mokili
(
307
points)

108
views
acetestseries
algorithms
dynamicprogramming
merging
graphtheory
optimalmergepattern
+1
vote
0
answers
9
Dynamic programming
Consider the following recursive function which is used by dynamic programming: T(n)= 0 ;if n<1 = 1;if n=1 =T(n1)+T(n2)+1 ;if n>1 Assume for every function call T(i) it checks the table first, if its value is already ... of n' so that overflow cannot occur ________. (Assume system allocate 4 byte to each stack entry which is sufficient for storing required data.)
asked
Jan 20
in
Algorithms
by
VS
Loyal
(
8.9k
points)

132
views
algorithms
dynamicprogramming
+3
votes
0
answers
10
gatebook test  Algorithm design paradigms
asked
Jan 10
in
Algorithms
by
junk_mayavi
Active
(
3.9k
points)

113
views
algorithms
testseries
dynamicprogramming
0
votes
1
answer
11
Dynamic programming
Which of the following statement(s) is/are correct? P: For a dynamic programming algorithm, computing all values in a bottomup fashion is asymptotically faster than using recursion Q: The running time of a dynamic programming algorithm is always Θ(P) where P is the number of subproblems.( Marks: 0.66 ) I mark only P is true. Answer neither P and Q
asked
Dec 26, 2017
in
Algorithms
by
sunil sarode
Active
(
1.3k
points)

217
views
dynamicprogramming
algorithms
+1
vote
1
answer
12
Greedy vs Dynamic
Unlike greedy algorithms, dynamic programming method always provide correct/optimal solution. Is the above statement correct?
asked
Dec 13, 2017
in
Algorithms
by
Tuhin Dutta
Loyal
(
7.9k
points)

405
views
algorithms
greedyalgorithm
dynamicprogramming
–1
vote
1
answer
13
Matrix multiplications
Let A1, A2, A3, A4, A5 be five matrices of dimensions 2×3, 3×5, 5×2, 2×4, 4×3 respectively. The minimum number of scalar multiplications required to find the product A1 A2 A3 A4 A5 using the basic matrix multiplication method is_____
asked
Dec 10, 2017
in
Algorithms
by
Parshu gate
Active
(
4.9k
points)

394
views
matrixchainordering
dynamicprogramming
algorithms
0
votes
1
answer
14
Dynamic programming
asked
Dec 5, 2017
in
Algorithms
by
Parshu gate
Active
(
4.9k
points)

93
views
algorithms
dynamicprogramming
+1
vote
1
answer
15
Matrix chain multiplication
Which of the following is the recurrence relation for the matrix chain multiplication problem where p[i1]*p[i] gives the dimension of the i^th matrix? dp[i,j]=1 if i=j dp[i,j]=min{dp[i,k]+dp[k+1,j]} dp[i,j]=1 if i=j dp[i,j]=min{dp[i,k]+dp[k+1,j]}+p[i1]*p[k]*p[j] dp[i,j]= ... dp[i,j]=min{dp[i,k]+dp[k+1,j]} dp[i,j]=0 if i=j dp[i,j]=min{dp[i,k]+dp[k+1,j]}+p[i1]*p[k]*p[j]
asked
Nov 27, 2017
in
Algorithms
by
Parshu gate
Active
(
4.9k
points)

308
views
dynamicprogramming
algorithms
matrixchainordering
+2
votes
2
answers
16
CLRS DivideandConquer Strassens's algorithm
asked
Oct 9, 2017
in
Algorithms
by
Manasi Srivastava
(
79
points)

207
views
algorithms
divideandconquer
dynamicprogramming
+1
vote
3
answers
17
Matrix Chain
Total no. of ways to perform matrix multiplication having 7 matrices is ? Total no. of ways to by which we could parenthesize 7 matrices is ? Does the above two questions are different or same ? Plz explain the answer.
asked
Oct 1, 2017
in
Algorithms
by
ashwina
Active
(
2k
points)

889
views
algorithms
dynamicprogramming
0
votes
0
answers
18
DYNAMIC PROGRAMMING
asked
Sep 17, 2017
in
Algorithms
by
Parshu gate
Active
(
4.9k
points)

136
views
algorithms
dynamicprogramming
graphtheory
0
votes
0
answers
19
dynamic programming
asked
Sep 17, 2017
in
Algorithms
by
Parshu gate
Active
(
4.9k
points)

78
views
dynamicprogramming
algorithms
0
votes
0
answers
20
Floydwarshall for longest path problem
I have few doubts related to Longest distance problem. From Wikipedia > The NPhardness of the unweighted longest path problem can be shown using a reduction from the Hamiltonian path problem: a graph G has a ... normal algorithm as asked in (https://stackoverflow.com/questions/42500120/floydwarshallforlongestdistanceforundirectedgraph)
asked
Sep 8, 2017
in
Algorithms
by
Chhotu
Boss
(
10.7k
points)

350
views
graphalgorithms
dynamicprogramming
0
votes
1
answer
21
dynamic programming
asked
Aug 26, 2017
in
Algorithms
by
set2018
Loyal
(
7.8k
points)

129
views
algorithms
dynamicprogramming
+2
votes
1
answer
22
Longest Common Subsequence
For finding longest common subsequence(LCS), standard sources mention that the recursive procedure consisting of the recursive tree occupies O(m+n) space( WITHOUT applying Dynamic Programming). I am unable to understand why is space occupied O(m+n)? Consider the tree of LCS(3,3). ... value of2^ k = O(m+n) and hence, space should be k=log(m+n). What's wrong with my logic?
asked
May 17, 2017
in
Algorithms
by
Bongbirdie
Junior
(
701
points)

403
views
algorithms
longestcommonsubsequence
dynamicprogramming
+1
vote
4
answers
23
difference between dynamic programming and divide and conquer technique is
asked
Apr 17, 2017
in
Algorithms
by
LavTheRawkstar
Active
(
5.1k
points)

3.7k
views
divideandconquer
algorithms
dynamicprogramming
programming
+1
vote
2
answers
24
Dynamic Programming
Find an optimal parenthesization of a matrixchain product whose sequence of dimensions <5,10,3,12,5,50,6>.
asked
Mar 21, 2017
in
Algorithms
by
saurabh rai
Boss
(
12.3k
points)

246
views
algorithms
dynamicprogramming
+3
votes
2
answers
25
What is the general idea to approach to problems in Dynamic Programming ?
asked
Jan 6, 2017
in
Algorithms
by
Dulqar
Active
(
2.8k
points)

328
views
algorithms
dynamicprogramming
+2
votes
1
answer
26
Made Easy Test Series
asked
Jan 3, 2017
in
Algorithms
by
Lucky sunda
Active
(
4.5k
points)

252
views
madeeasytestseries
algorithms
dynamicprogramming
+1
vote
2
answers
27
virtual gate
asked
Dec 30, 2016
in
Algorithms
by
firki lama
Junior
(
873
points)

247
views
virtualgate
testseries
dynamicprogramming
matrixchainordering
+3
votes
1
answer
28
TIFR2016A7
Let $S$ be the $4 \times 4$ square grid $\{(x, y): x, y \in \{0, 1, 2, 3\} \}$. A $monotone \: \: path$ in this grid starts at $(0, 0)$ and at each step either moves one unit up or one unit right. For example, fromthe point $(x, y)$ one can in one ... )$ bt $z$. How many distinct monotone paths are there to reach point $(3, 3)$ starting from $(0, 0)$? $2z+6$ $3z+6$ $2z+8$ $3z+8$ $3z+4$
asked
Dec 27, 2016
in
Others
by
jothee
Veteran
(
99.8k
points)

83
views
tifr2016
permutationsandcombinations
dynamicprogramming
+1
vote
3
answers
29
Find shortest path
asked
Nov 27, 2016
in
Algorithms
by
Rakesh K
Active
(
1.8k
points)

573
views
graphalgorithms
shortestpath
algorithms
graphtheory
dynamicprogramming
multistagegraph
+3
votes
1
answer
30
Divide and conquer+Dynamic
asked
Oct 8, 2016
in
Algorithms
by
Rahul Jain25
Boss
(
11.5k
points)

440
views
divideandconquer
dynamicprogramming
algorithms
Page:
1
2
next »
Quick search syntax
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
Recent Posts
Schedule for GATE 2019
GATE 2019 official website
Correct way of preparation
Right process to start solving MCQs in Comp.Sc.
UGC NET JULY 2018 Results
Follow @csegate
Gatecse
Recent questions tagged dynamicprogramming
Recent Blog Comments
Books are there but don't think any will leave ...
Sir i have placed the order Details are PAYMENT ...
Sir i am placing order for gate overflew book ...
Yes, their tracking system is incomplete. ...
India post don't update the tracking details. No ...
38,084
questions
45,574
answers
132,084
comments
49,062
users