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

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
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
0
votes
0
answers
1
Dynamic Programming basics
Can any one explain whats happening in side the green area due to dynamic programming ?
asked
Jan 13
in
Programming
by
Nandkishor3939
Junior
(
791
points)

53
views
dynamicprogramming
algorithms
programming
+1
vote
0
answers
2
self doubt
Is there any shortcut or Trick to get min number of multiplication faster? I mean if we could know the right split.
asked
Dec 8, 2018
in
Algorithms
by
Nivedita Singh
(
35
points)

47
views
algorithms
dynamicprogramming
matrixchainordering
0
votes
0
answers
3
homework
Main disadvantage of direct mapping is that cache his ratio decreases sharply it two or more frequently used blocks map on to same region. For two level memory hierarchy cache and main memory, WRITE THROUGH results in more write cycles to main emeory then WRITE BACK. is it true or false ? with reasons ? thank you in advance
asked
Nov 17, 2018
in
CO & Architecture
by
deepanshu sharma 3
(
135
points)

18
views
dynamicprogramming
0
votes
0
answers
4
Fibonacci number time complexity
Consider the following code segment to find the $n^{th}$ Fibonacci number: Fib(n) { if(n==0) {return 0;} if(n==1) {return 1;} else { return(Fib(n1) + Fib(n2)); } } The time complexity of the above code and time complexity of the same problem solved using dynamic programming is______ $A)O(n^{2}),O(n)$ $B)O(2^{n}),O(n)$ $C)O(2^{n}),O(n^{2})$ $D)$None of the above
asked
Nov 13, 2018
in
Algorithms
by
Lakshman Patel RJIT
Boss
(
26.8k
points)

71
views
algorithms
greedyalgorithm
dynamicprogramming
0
votes
0
answers
5
Backtracking part of Algo
Is Backtracking Branch and Bound part of Gate syllabus?
asked
Oct 22, 2018
in
Algorithms
by
sripo
Active
(
1.3k
points)

30
views
algorithms
dynamicprogramming
syllabus
usergate2019
0
votes
0
answers
6
homework
I need to find the tight bound of the Fibonacci sequence in dynamic programming (using theta). I only know the bound using big O is O(n). Any idea how to do it?
asked
Oct 10, 2018
in
Algorithms
by
Mariela Prasetyo
(
13
points)

37
views
dynamicprogramming
timecomplexity
0
votes
2
answers
7
dynamic prgramming
Given a two dimensional array A with n rows and k columns initialized to 1 . what is the time complexity of the function f(A,m,m)? int f(int **a,int n,int k) { if ((n<=k)(k<=1)) return 1; if(a[n][k]==1) a[n][k]=f(a,n1,k)+f(a,n1,k1); return a[n][k]; } a)theta(m) b)theta(m^2) c)theta(2^m) d)O(1) }
asked
Sep 16, 2018
in
Algorithms
by
balaganesh
(
141
points)

38
views
dynamicprogramming
algorithms
0
votes
0
answers
8
Dynamic Programming Preparation for Gate
How to prepare for Dynamic Programming topic in DAA for GATE exam?
asked
Sep 9, 2018
in
Algorithms
by
dan31
(
497
points)

69
views
algorithms
dynamicprogramming
gate
+1
vote
0
answers
9
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
Aug 17, 2018
in
Algorithms
by
srestha
Veteran
(
106k
points)

47
views
algorithms
dynamicprogramming
0
votes
0
answers
10
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, 2018
in
Algorithms
by
AIkiran01
(
209
points)

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

343
views
algorithms
dynamicprogramming
0
votes
0
answers
12
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, 2018
in
Algorithms
by
hacker16
Active
(
2.8k
points)

96
views
algorithms
recursion
dynamicprogramming
+1
vote
0
answers
13
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, 2018
in
Algorithms
by
Yash Khanna
(
317
points)

84
views
binarytree
algorithms
dynamicprogramming
permutationsandcombinations
0
votes
0
answers
14
Dynamic programmingtabulation method bottom up
Just practicing some general problems on dynamic programming.Problem is I am unable to think of tabulation or bottom up approach for most of the new type of problems other than common ones.I am trying to get the naive recursion first ... at this moment let me know how to get some idea of tabulating easily?..For example take coin exchange problem.
asked
Feb 22, 2018
in
Algorithms
by
Surajit
Active
(
3.2k
points)

203
views
dynamicprogramming
+8
votes
5
answers
15
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 parenthesizing in different ... , 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, 2018
in
Algorithms
by
gatecse
Boss
(
18.3k
points)

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

134
views
acetestseries
algorithms
dynamicprogramming
merging
graphtheory
optimalmergepattern
+1
vote
0
answers
17
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, 2018
in
Algorithms
by
VS
Loyal
(
9.9k
points)

159
views
algorithms
dynamicprogramming
+3
votes
0
answers
18
gatebook test  Algorithm design paradigms
Select the wrong statement from the following given options. a. Dynamic programming is applicable when subproblems are not independent. b. Divide and conquer algorithm does more work than necessary repeatedly solving the common subproblems c. ... exactly once and saves the result into a table. d. Longest path problem has optimal substructure property.
asked
Jan 10, 2018
in
Algorithms
by
junk_mayavi
Active
(
4.2k
points)

137
views
algorithms
testseries
dynamicprogramming
0
votes
1
answer
19
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.4k
points)

264
views
dynamicprogramming
algorithms
+1
vote
1
answer
20
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
(
8.8k
points)

483
views
algorithms
greedyalgorithm
dynamicprogramming
0
votes
2
answers
21
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
(
5.1k
points)

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

114
views
algorithms
dynamicprogramming
+1
vote
1
answer
23
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
(
5.1k
points)

460
views
dynamicprogramming
algorithms
matrixchainordering
+2
votes
2
answers
24
CLRS DivideandConquer Strassens's algorithm
Do we need to study the Strassens's algorithm in detail like proof or working of that algorithm or we just need to know the time complexity of the algorithm because I can't find it's explanation anywhere?
asked
Oct 9, 2017
in
Algorithms
by
Manasi Srivastava
(
79
points)

236
views
algorithms
divideandconquer
dynamicprogramming
+1
vote
3
answers
25
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
(
2.1k
points)

1.1k
views
algorithms
dynamicprogramming
0
votes
0
answers
26
DYNAMIC PROGRAMMING
asked
Sep 17, 2017
in
Algorithms
by
Parshu gate
Active
(
5.1k
points)

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

86
views
dynamicprogramming
algorithms
Page:
1
2
3
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
PSU's
Decidability Slides
AAI JE IT results out! Adv no 02/2018
Graph Theory Slides for GATECSE
Generating Function Useful Link
Follow @csegate
Gatecse
Recent questions tagged dynamicprogramming
Recent Blog Comments
Thank you, lots of things got clear!
Guys this is getting out of hand now. You see...
47,005
questions
51,325
answers
177,508
comments
66,668
users