Recent questions tagged dynamic-programming

6. Which one of the following is an optimal substructure property?If $S$ is an optimal solution, then the components of $S$ are not necessarily optimalIf $S$ is an optima...

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...

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...

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 ...

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...

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

We are given a sequence of $n$ positive numbers $a_{1}, a_{2}, \ldots, a_{n}$ and a fixed number $k>0$. We want to find a pair of numbers $a_{i}$ and $a_{j}$ such that $j...

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...

At the end of it's 5th Successful season,The siruseri Permier league is planning to give an award to most improved bowler over 5 years . For this an important Index will ...

The weight of a sequence $a_0,a_1, \dots, a_{n-1}$ of real numbers is defined as $a_0+a_1/2+ \dots + a_{n-1}/2^{n-1}$. A subsequence of a sequence is obtained by deleting...

Four Matrices $M_1, M_2, M_3$ and $M_4$ of dimensions $ p \times q, \:\:q \times r, \:\:r \times s$ and $s \times t$ respectively can be multiplied in several ways with d...

An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array $A[0:n-1]$ is given below.Let $L_i$, denote the length of the long...

Suppose you want to move from $0$ to $100$ on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a pre-s...

Consider two strings $A$ = "qpqrr" and $B$ = "pqprqrp". Let $x$ be the length of the longest common subsequence (not necessarily contiguous) between $A$ and $B$ and let $...

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 ...

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...