search
Log In

Recent questions tagged dynamic-programming

0 votes
3 answers
2
Which of the following standard algorithms is not Dynamic Programming based? Bellman-Ford Algorithm for single source shortest path Floyd Warshall Algorithm for all pairs shortest paths $0-1$ Knapsack problem Prim’s Minimum Spanning Tree
asked Mar 30, 2020 in Algorithms Lakshman Patel RJIT 1.1k views
1 vote
1 answer
4
Consider the following statements : a) The running time of dynamic programming algorithm is always θ (p) where p is number of subproblems b)when a recurrence relation has cyclic dependency, it is impossible to use that recurrence relation (unmodified) in a correct dynamic program c) For a dynamic ... of the statement(s) is/are true 1) only b and a 2)only b 3) only b and c 4)only b and d
asked Dec 22, 2019 in Algorithms Sanjay Sharma 1.3k views
1 vote
1 answer
5
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 based on the ... programming, 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 gatecse 300 views
3 votes
3 answers
6
Consider the following steps: $S_1$: Characterize the structure of an optimal solution $S_2$: Compute the value of an optimal solution in bottom-up 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 Arjun 1.7k views
0 votes
0 answers
7
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 karan25gupta 345 views
0 votes
2 answers
8
What advantage does top down approch have over bottom up approach in case of dynamic programming??
asked Mar 26, 2019 in Algorithms Doraemon 377 views
0 votes
1 answer
9
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 gmrishikumar 907 views
0 votes
0 answers
10
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 Nandkishor3939 201 views
0 votes
2 answers
11
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 Gupta731 286 views
2 votes
0 answers
12
Can any one explain whats happening in side the green area due to dynamic programming ?
asked Jan 13, 2019 in Programming Nandkishor3939 222 views
1 vote
1 answer
13
Consider two sequences $X$ and $Y$ : $X=<0, 1, 2, 1, 3, 0, 1>$ $Y=<1, 3, 2, 0, 1, 0>$ The length of longest common subsequence between $X$ and $Y$ is $2$ $3$ $4$ $5$
asked Jan 2, 2019 in Unknown Category Arjun 1.2k views
2 votes
2 answers
14
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 Nivedita Singh 539 views
0 votes
0 answers
15
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 adityaaswal 231 views
0 votes
0 answers
16
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 Shamim Ahmed 172 views
0 votes
0 answers
17
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 deepanshu sharma 3 100 views
0 votes
2 answers
18
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(n-1) + Fib(n-2)); } } 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 Lakshman Patel RJIT 663 views
0 votes
0 answers
19
Is Backtracking Branch and Bound part of Gate syllabus?
asked Oct 22, 2018 in Algorithms sripo 407 views
0 votes
0 answers
20
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 Mariela Prasetyo 102 views
0 votes
2 answers
21
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,n-1,k)+f(a,n-1,k-1); return a[n][k]; } a)theta(m) b)theta(m^2) c)theta(2^m) d)O(1) }
asked Sep 16, 2018 in Algorithms balaganesh 134 views
1 vote
0 answers
22
1 vote
0 answers
23
1 vote
1 answer
24
Why we need to do top-down and bottom-up these 2 approach in dynamic programming? I know bottom-up 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 top-down bottom-up
asked Aug 17, 2018 in Algorithms srestha 212 views
0 votes
0 answers
25
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 AIkiran01 102 views
3 votes
2 answers
26
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 talha hashim 779 views
2 votes
2 answers
28
Time complexity of Multistage Graph is O(n2) or O(V2) but then some people says it's O(E). So, from O(V2) to O(E) are they taking about dense/complete graphs in which number of edges |E| = |V2|? Kindly help!
asked Jun 3, 2018 in Algorithms iarnav 2.4k views
1 vote
1 answer
29
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 Greedy algorithm (multiply matrix ... . Person 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 Ayesha_S 416 views
...