Questions about problems that can be solved by combining recursively obtained solutions of subproblems.

learn more… | top users | synonyms

1
vote
1answer
54 views

Dynamic Programming for finding shortest alternating paths between all pairs of vertices in a graph

I'm learning Dynamic Programming (By myself) and in the textbook there is this question: Given two undirected graphs $G_1=(V,E_1)$ and $G_2=(V,E_2)$ over the same set of Vertices $V$ and a weight ...
1
vote
2answers
160 views

Dynamic programming to find the least possible balance of a full binary tree

I am given $n$ positive integers $x_1,x_2,\cdots,x_n$ as input. These are the weights of the leaves in a full binary tree, $x_1$ being the leftmost leaf and $x_n$ the rightmost leaf. The weight of an ...
1
vote
1answer
80 views

Dynamic Programming Subset Sum Problem with twist

Question: You are given an input , which is a sequence of positive integers $w_1, w_2, . . . , w_n$ with parameters $W, ∆. $We wish to find $S ⊆ \{1, 2, . . . , n\}$ such that $\sum_{j \in S} w_j$ is ...
1
vote
1answer
23 views

Black box with O(n) calls

Let's say a procedure called 'decision(x,q)' is available as a 'black box' X is the input set and Q is a real number Q. I need to design an algorithm that reports "yes" if there exists a subset of X ...
4
votes
1answer
455 views

Is CYK still relevant today?

I've come across the CYK algorithm and was wondering, as it's quite old, if it is still relevant today. Is it or an extension of it still being used in compilers (for example), or have other ...
2
votes
1answer
41 views

Solving a dynamic programming problem?

Alex writes down the decimal representations of all natural numbers between and including m and n, (m ≤ n). How many zeroes will he write down? My one friend said to me that this problem can be ...
2
votes
0answers
8 views

Finding maximum information gain subinterval of an array containing points from 2 classes

Suppose we have an $N \times 2$ array $A$ where the two entries $A(k,1)$ and $A(k,2)$ give the number of occurrences of each of two classes at position $k$. Given a sub-interval $I$ of indices between ...
2
votes
0answers
23 views

Training a model to match two time series

Context I have two related time series, I want to learn to produce one from the other. However, they aren't synchronous, and the lag between the two does not revert to the mean, it accumulates. ...
-2
votes
1answer
44 views

Dynamic Programming Approach

when we are trying to solve a problem with dynamic programming. we have to follow some general steps characterize the solution structure Recursively define optimal solution compute the value from ...
4
votes
1answer
100 views

Computing the mode of XOR subsequences

I was confronted with this problem in an online programming challenge and it has been bugging me since: In the problem, you are given a list of 16-bit numbers, say $a_0, a_1, ..., a_n$. An "XOR ...
2
votes
2answers
60 views

Segmenting an English string with no spaces using dynamic programming

Suppose you have a function quality(x) that returns the quality of a sequence of letters x. Given a string such as ...
2
votes
0answers
60 views

Job scheduling problem in O(n log n)

There are $n \leq 10^6$ kinds of cake layers, and for each kind we have a machine capable of baking it in one unit of time and nothing more. Now, a cake is a sequence of layers, more specificly a ...
5
votes
1answer
97 views

Proving optimality of a dynamic programming algorithm

We have a string $s$ containing $n \leq 100$ bits. The move we can make on it is erasing from $s$ some substring $x$, but only if $x$ is directly preceded by $x^R$, where $x^R$ means string $x$ ...
4
votes
1answer
120 views

Maximum sum subset of an array with an extra condition

We are given numbers $n \leq 200$, $k \leq 10$ and an array of $3n$ positive integers not greater than $10^6$. Find the maximum possible sum of a subset of elements of this array, such that in every ...
3
votes
0answers
63 views

Algorithms that are similar to Dynamic TIme Warping

Dynamic time warping (DTW) is an algorithm in time series analysis for measuring similarity between two temporal sequences which may vary in time or speed. Here are some explanations of DTW: Dynamic ...
7
votes
2answers
129 views

Guessing Number Game

I was solving this question. It is as follows Joe picks an integer from the list $1,2,\cdots,N$ with a probability $p_i$ of picking $i$ for all $1\leq i \leq N$. He then gives Jason $K$ attempts ...
-1
votes
1answer
106 views

Mininun changes required in a directed graph to make path from 1 to n

i have a directed graph. Basically, i have to find how many edges i need to change to opposite direction to make a path between 1 and n. So, i tried solving it by making the graph undirected and ...
0
votes
1answer
54 views

State of variables in dynammic programming [closed]

I would like to know what a state variable is in simple words, and I need to give a lecture about it. I have chosen the Longest Common Subsequence problem I found a similar question but it has no ...
1
vote
2answers
195 views

Edit distance (Levenshtein-Distance) algorithm explanation

I want to calculate the edit distance (aka Levenshtein-Distance) between two words: «solo» and «oslo». According to this site we'll get the result matrix: What I don't understand is: In case of ...
3
votes
1answer
47 views

Does FACTORING have optimal substructure or analog to it?

Is there any approach to FACTORING that can leverage optimal substructure allowing the problem to be decomposed into smaller subproblems? That is, perhaps being unnecessarily verbose, until an easily ...
1
vote
0answers
46 views

Palstar algorithm Dynamic Programming getting the result [closed]

I recently started to read abour dynamic programming, and I am doing an exercise on it. The problem to solve: Given a String, find the least amount of palindromes it can be split into, and print out ...
2
votes
1answer
89 views

Arrangement of numbers in a grid

I have a $n \times m$ matrix $M$ and a permutation of sequence $P$ of numbers from $1$ to $n$. I have to fill the matrix using numbers $1$ to $n \times m$ in such a way that for each row $i$, the ...
1
vote
2answers
249 views

Proof of an Optimal substructure in Dynammic Programming?

Could someone please explain how exactly the proof of optimal substructure property in dynamic programing problems works?, they usually say that " let's say the global optimal solution is A, and B is ...
2
votes
2answers
209 views

How Dynamic programming can be used for Coin Change problem?

As far as I can unserstand Dynamic programming stands simply for memoization (which is a fancy name for lazy evaluation or plain "caching"). Now, I read that there is we can reduce complexity of ...
0
votes
1answer
168 views

Dynamic Programming Solution to 0,1 KnapSack Problem

I am trying to understand the DP solution to the basic knapsack problem.However even after reading through a variety of tutorials ,its still beyond my comprehension.I am taking an algorithmics course ...
-2
votes
1answer
24 views

why negative cycle exists if we can relax the edges one more time after running the Bellman Ford Algorithm

We know Bellman Ford is an algorithm to find the negative cycle. And here is the algorithm for Bellman Ford Input: Given a graph G(V,E) and w(e) is weight Output: Return Yes if negative cycle exists. ...
5
votes
1answer
85 views

How do I reconstruct the forest of syntax trees from the Earley vector?

Using the Earley vector as a recognizer is quite straightforward: when the end of the string is reached, you just have to check for a completed axiomatic production started at position 0. If you have ...
1
vote
0answers
42 views

Dynamic Programming - Seemingly unnecessary recursion?

I am working on my thesis on revenue management. I have been over the following problem multiple times now, but I fail to see where my mistake is. This example is based on The Theory and Practice of ...
3
votes
1answer
193 views

Fast algorithm for matrix chain multiplication in special case

An exercise from the book Foundations of Algorithms Using Java Pseudocode: Write an efficient algorithm that will find an optimal order for multiplying $n$ matrices $A_1 \times A_2 \times \ldots ...
5
votes
1answer
294 views

Maximum sub-matrix sum

Given a $n\times m$ matrix $A$ of integers, find a sub-matrix whose sum is maximal. If there is one row only or one column only, then this is equivalent to finding a maximum sub-array. The 1D version ...
1
vote
1answer
184 views

How to modify Bellman-Ford algorithm for this specific Minimum Cost Flow problem?

I'm trying to design an algorithm for the following optimization problem. Suppose that $G=(V, E)$ is a digraph where $V$ and $E$ are sets of vertices and edges of $G$, respectively. $|V| = n$ and $|E| ...
2
votes
2answers
300 views

The Gas Station Problem - fast implementation

Recently I was asking about the algorithm to solve The Gas Station Problem and I got useful answer. Unfortunately solution with transforming a graph to complete graph and then preparing another one to ...
1
vote
0answers
53 views

Algorithm for keeping the Maximum and allowing Splits of Strings/sequences

The problem is as follows: Given $k$ strings of size $n$, propose a data structure to support the following operations: Return the maximum of a string. Given an index $i$, and $2$ strings $a$ and ...
0
votes
1answer
45 views

Finding dynamic programing algorithm

I got a matrix of integers of size $3\times n$. Of each one of the three rows, for each column I got to choose one number, with the restriction that, for each $i$, the numbers chosen in the $i$th and ...
0
votes
2answers
111 views

Maximum Value Contiguous Subsequence [closed]

I have stumbled upon this problem online: Given a sequence of n real numbers A(1) ... A(n), determine a contiguous subsequence A(i)... > A(j) for which the sum of elements in the subsequence is ...
0
votes
1answer
80 views

Zigzag subsequence [closed]

As part of a homework assignment I'm asked to describe an O(mn) algorithm to find the length of the longest zig-zag sub sequence. The overall topic for this assignment is dynamic programming. As ...
0
votes
1answer
53 views

Dynamic programming rectangular grid [closed]

You are given a 40x40 grid. Each point of the grid is either 0 or 1. You are also given an infinite amount of 1x40 rectangular slabs. How to find out the minimum number of slabs required to cover all ...
0
votes
1answer
133 views

Help with a dynamic programming solution to a pipe cutting problem

I'm trying to complete a problem where I have to design and implement a dynamic programming solution to the following problem You have to cut a metal pipe into several pieces. To do so, you bring ...
3
votes
3answers
346 views

Can't understand why the DP Subset Sum algorithm is not polynomial

I can not understand why the dynamic programming algorithm for the Subset Sum, is not polynomial. Even though the sum to find 'T' is greater than the total sum of the 'n' elements of the set , the ...
1
vote
1answer
92 views

Studying Skiena. War Story: What’s Past is Prolog

I am reading The Algorithm Design Manual, 2nd Edition. The book gives an example task and then explains how to solve it step by step. (The task and solution is detailed here) But I don't follow one ...
1
vote
1answer
179 views

Knapsack problem, partition problem, or in general dynamic algorithm with negative numbers allowed [closed]

How to think about dynamic algorithms which allows negative integers in input (where it's problematic, because obviously it's not always the case)? Examples: Partition Problem with negative numbers ...
8
votes
6answers
2k views

How is Dynamic programming different from Brute force

I was reading up on Dynamic Programming when I came across the following quote A dynamic programming algorithm will examine all possible ways to solve the problem and will pick the best ...
1
vote
1answer
188 views

Dynamic programming VS Greedy Algroithms [closed]

I have two True or False questions in my practice test that are related but I am unsure about: ...
1
vote
1answer
24 views

Explain BadNeighbors problem statement

I was solving a problem on topcoder http://community.topcoder.com/stat?c=problem_statement&pm=2402&rd=5009 . There is one example : ...
5
votes
3answers
163 views

Are there dynamic programming examples that run in exponential time?

Are there dynamic programming examples that run in exponential time? Every example that I've seen so far constructs the top half of a matrix in a bottom-up fashion ($n^2$) from the base case and ...
3
votes
2answers
160 views

minimizing the summed cardinality of set unions

this optimization problem, I am working on, is kind of making me crazy. ;) Given is a list o of sets (with finite cardinality) of strictly positive integer values ...
0
votes
1answer
67 views

Updating maximum sum subrectangle in a sparse matrix when one element is changed

I have an m x n matrix which is sparse with N non-zero entries. A modified version of Kadane's 2-d algorithm can find the maximum sum subrectangle in O(m N log n) time, which beats traditional ...
1
vote
1answer
118 views

Minimum number that cannot be formed by any subset of an array

We have an array of Integers, $A[]$ and we have to find the minimum number that is not the sum of a subset of array using the elements from $L$ to $R$ indices. I was thinking of using coin change DP ...
3
votes
1answer
145 views

Viterbi algorithm recursive justification

I have a question regarding recursion in Viterbi algorithm. Define $\pi(k; u; v)$ which is the maximum probability for any sequence of length $k$, ending in the tag bigram $(u; v)$. The base case ...
-1
votes
1answer
119 views

Finding number of maximum independent sets in tree, using dynamic programming

I'm quite stuck trying to answer this. The problem of finding the size of the maximum independent set in a tree using dynamic programming is well documented and many solutions are around. I've been ...