The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
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
Recent questions tagged dynamicprogramming
+1
vote
0
answers
1
CMI2019B7
A college professor gives several quizzes during the semester, with negative marking. He has become bored of the usual "Best $M$ out of $N$ quizzes" formula to award marks for internal assessment. Instead, each student will be evaluated ... , the score the professor needs to award each student. Describe the space and time complexity of your dynamic programming algorithm.
asked
Sep 13, 2019
in
Algorithms
by
gatecse
Boss
(
17.5k
points)

57
views
cmi2019
algorithms
dynamicprogramming
descriptive
nongate
+3
votes
2
answers
2
UGCNETJune2019II68
Consider the following steps: $S_1$: Characterize the structure of an optimal solution $S_2$: Compute the value of an optimal solution in bottomup fashion Which of the following step(s) is/are common to both dynamic programming and greedy algorithms? Only $S_1$ Only $S_2$ Both $S_1$ and $S_2$ Neither $S_1$ nor $S_2$
asked
Jul 2, 2019
in
Algorithms
by
Arjun
Veteran
(
431k
points)

210
views
ugcnetjune2019ii
optimalsolution
dynamicprogramming
greedyalgorithm
0
votes
0
answers
3
self doubt *0/1 knapsack problem*
In 0/1 knapsack problem ,suppose if maximum weight is given as W and we are asked to find out max profit then * IS IT NECESSARY THAT THE TOTAL WEIGHT SHOULD BE EXACTLY EQUAL TO W OR IT CAN BE LESS THAN W AS WELL????
asked
Apr 17, 2019
in
Algorithms
by
karan25gupta
(
445
points)

89
views
algorithms
dynamicprogramming
knapsack
0
votes
2
answers
4
self doubt
What advantage does top down approch have over bottom up approach in case of dynamic programming??
asked
Mar 26, 2019
in
Algorithms
by
Doraemon
Junior
(
791
points)

194
views
dynamicprogramming
0
votes
1
answer
5
A Different Kind of Question on Longest Common Subsequence
Consider two strings A = "anandarmy" and B = "algorithms". Let ‘y’ be the length of the longest common subsequence (not necessarily contiguous) between A and B and let ‘x’ be the number of such longest common subsequences between A and B. Then 2x+3y = _________.
asked
Jan 22, 2019
in
Algorithms
by
gmrishikumar
Active
(
2.2k
points)

173
views
algorithms
longestcommonsubsequence
dynamicprogramming
0
votes
0
answers
6
Dynamic programming
My answer came out to be 13: because when we will compute T(13) { as we are using Dynamic programming , it will have to compute value of T(12),T(11),…...T(2) only once(as it will store it and reuse it) so the stack size will be 1 (for T(13))+11 (for T(12),T(11),…...T(2)) = 12…...(48/4) } will any one help me out
asked
Jan 22, 2019
in
Algorithms
by
Nandkishor3939
Active
(
1.3k
points)

91
views
algorithms
dynamicprogramming
programming
0
votes
2
answers
7
Gateforum Test Series: Algorithms  Dynamic Programming
Given a text array $T[1…..n]$ and a pattern array $P[1….m]$ such that T and P are character taken from alphabet $\sum$, $\sum={a,b,c,…..z}$. String matching problem is to find all the occurence of P in T. A pattern occur with shift s in T if $P[1…..m]=T[s+1,…...s+m]$. Consider $T=bacacbaacacac$ $P=cac$ The sum of the value of all s is ________
asked
Jan 14, 2019
in
Algorithms
by
Gupta731
Active
(
4.8k
points)

117
views
gateforumtestseries
algorithms
dynamicprogramming
+2
votes
0
answers
8
Dynamic Programming basics
Can any one explain whats happening in side the green area due to dynamic programming ?
asked
Jan 13, 2019
in
Programming
by
Nandkishor3939
Active
(
1.3k
points)

104
views
dynamicprogramming
algorithms
programming
0
votes
2
answers
9
MadeEasy Test Series: Algorithms  Dynamic Programming
Let the difference between the maximum possible profit for $0/1$ knapsack and fractional knapsack with capacity $20$ be $X$. What is the value of $X$ Item a b c d e f g h i j Profit 7 10 3 3 26 19 18 17 5 4 Weight 3 5 2 1 12 10 9 9 4 1 How to solve for $0/1$ knapsack for the maximum profit in the faster way ???
asked
Dec 23, 2018
in
Algorithms
by
jatin khachane 1
Loyal
(
7.5k
points)

182
views
madeeasytestseries
algorithms
dynamicprogramming
+1
vote
1
answer
10
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
(
29
points)

137
views
algorithms
dynamicprogramming
matrixchainordering
0
votes
0
answers
11
MadeEasy Subject Test 2019: Algorithms  Dynamic Programming
Let G = (V,E) be a directed graph.Each edge of G is represented as (i,j) with length l[i,j].If there is no edge from i to j then l[i,j] = (IMAGE ATTACHED)
asked
Dec 1, 2018
in
Algorithms
by
adityaaswal
(
195
points)

140
views
madeeasytestseries
algorithms
dynamicprogramming
0
votes
0
answers
12
MadeEasy Test Series : Algorithms  Dynamic Programming
Which of the following procedure is suitable to find longest path from given vertex to any other vertex in Directed Acyclic Graph? Answer: Dynamic Programming. Why Greedy Algorithm cant be applied here?
asked
Nov 26, 2018
in
Algorithms
by
Shamim Ahmed
Active
(
2.5k
points)

84
views
madeeasytestseries
algorithms
dynamicprogramming
0
votes
0
answers
13
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 and Architecture
by
deepanshu sharma 3
(
83
points)

33
views
dynamicprogramming
0
votes
1
answer
14
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
Veteran
(
59.3k
points)

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

79
views
algorithms
dynamicprogramming
syllabus
usergate2019
0
votes
0
answers
16
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
(
9
points)

57
views
dynamicprogramming
timecomplexity
0
votes
2
answers
17
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
(
131
points)

66
views
dynamicprogramming
algorithms
+1
vote
0
answers
18
Ace Test Series: Algorithms  Dynamic Programming OBST
Consider an OBST with n=4, p[1..4]={3,3,1,1} q[0..4]={2,3,1,1,1} Cost of OBST=___? Pls give the solution for this question.
asked
Sep 10, 2018
in
Algorithms
by
Nidhi Budhraja
(
205
points)

88
views
acetestseries
algorithms
dynamicprogramming
+1
vote
0
answers
19
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
Junior
(
883
points)

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

86
views
algorithms
dynamicprogramming
0
votes
0
answers
21
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
(
119
points)

57
views
algorithms
dynamicprogramming
+2
votes
2
answers
22
MadeEasy Test Series: Algorithms  Dynamic Programming
Consider two strings A = “abbaccda” and B = “abcaa” consider "x"be length of the longest common subsequence between A and B and “y” be the number of distinct such longest common subsequences between A and B. Then 10x+ 2y is ________.
asked
Aug 1, 2018
in
Algorithms
by
talha hashim
Loyal
(
5.6k
points)

218
views
algorithms
dynamicprogramming
madeeasytestseries
+1
vote
1
answer
23
Ace Test Series: Algorithms  Dynamic Programming OBST
asked
Jun 29, 2018
in
Algorithms
by
Na462
Loyal
(
7k
points)

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

1.1k
views
algorithms
dynamicprogramming
+1
vote
1
answer
25
MadeEasy Test Series: Algorithms  Dynamic Programming
Consider two Person (Person X, Person Y). Person X who was given a problem to calculate A1 A2 A3 with dimension 3 100, 100 2 and 2 2 in minimum multiplication. Person X is the knows only ... Y solved the same problem using Dynamic algorithm with M2multiplications. How many number of multiplications saved by Person Y than Person X?
asked
Jun 2, 2018
in
Algorithms
by
Ayesha_S
(
25
points)

182
views
madeeasytestseries
algorithms
dynamicprogramming
0
votes
0
answers
26
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.7k
points)

144
views
algorithms
recursion
dynamicprogramming
+1
vote
0
answers
27
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
(
431
points)

107
views
binarytree
algorithms
dynamicprogramming
permutationandcombination
0
votes
0
answers
28
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.7k
points)

340
views
dynamicprogramming
+14
votes
5
answers
29
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_1F_2$ and $F_4F_5$ only
asked
Feb 14, 2018
in
Algorithms
by
gatecse
Boss
(
17.5k
points)

5.3k
views
gate2018
algorithms
dynamicprogramming
+1
vote
1
answer
30
MadeEasy Test Series 2018: Algorithms  Dynamic Programming
The number of balance parenthesis possible with 5pairs of parenthesis _________. [ Assume ( ) and (( )) is balance parenthesis but not ) ( ]
asked
Jan 29, 2018
in
Algorithms
by
Sumaiya23
Active
(
1.7k
points)

427
views
algorithms
dynamicprogramming
counting
madeeasytestseries
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
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Calculus Important Points
Management Trainee Recruitment COAL INDIA 2020
Follow @csegate
Recent questions tagged dynamicprogramming
Recent Blog Comments
Has anyone else challenged the questions on...
@nkg_master9  For getting selected for the...
Nowhere it's mentioned.
@bond  Is it mentioned that you have to score at...
I think cutoff won't cross 85
50,737
questions
57,385
answers
198,549
comments
105,365
users