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

learn more… | top users | synonyms

0
votes
0answers
26 views

Utility Maximizing Challenging Assignment Problem

There is a grid of size MxN. M~20000 and N~10. So M is very huge. So one way is to look at this is N grid blocks of size M placed side by side. Next assume that there are K number of users who each ...
0
votes
1answer
51 views

Algorithm to compute a recursive function on a given set

I am working on a property of a given set of natural numbers and it seems difficult to compute. There is a function 'fun' which takes two inputs, one is the cardinal value and another is the set. If ...
2
votes
1answer
40 views

Going deeper with pseudo-polynomial time algorithm for set partitioning

If I have a set of (edit) positive integers, and I'm sure that the pseudo-polynomial time algorithm for partitioning the problem will not give me an answer - what would I do next? To illustrate this ...
0
votes
1answer
27 views

Shortest path in a matrix

I am trying to solve this problem, and i have tried multiple methods, but i must be missing something, here is the problem: Given a matrix MxN. Find the shortest path from (1,1) to (M,N), where each ...
-1
votes
1answer
31 views

Problem on Dynamic Programming

A company is planning a party for its employees. A fun rating is assigned to every employee. The employees are organized into a strict hierarchy, i.e. a tree rooted the president. There is one ...
5
votes
1answer
165 views

Solving road trip problem in linear time

Consider the following problem: You are on a road trip, and there are $n$ cities along a road, labeled $1$ to $n$. Conveniently, these cities all lie on a single road, and the distance between ...
0
votes
0answers
43 views

Dynamic programming for counting knapsack solutions

Suppose the usual dynamic programming algorithm for the knapsack problem. If we swap the max with an addition, does the modified algorithm compute all the solutions with benefit $\leq W$? I ...
-2
votes
1answer
68 views

Algorithm to decide the Kleene Star of a Language A

Assume $f$ decides a language $A$ in $O(g(n))$ time, where $n$ is the length of the input string. How to write a recursive algorithm to decide $A^*$ (recursive)? Moreover, can an $O(n^2g(n))$ ...
0
votes
0answers
13 views

Regarding number of iterations in Value Iteration

In value iteration for single goal problem, does the number of iterations it takes for the convergence to terminate dependent on grid world size, or discount factor or threshold set or none of the ...
0
votes
0answers
24 views

Dynamic programming in the direction of path planning

I have been doing literature survey for a dynamic programming project. And I have found several good references of research work in the fields of learning and control viz. reinforcement learning and ...
1
vote
2answers
197 views

Dynamic Programming - Print all paths from (0,0) to (n,n) in Grid/Lattice

I'm trying to write an algorithm to print all the paths from point (0,0) to (n,n) in a grid. The only possible moves are right and up. Also, you can't move below the diagonal y=x. e.g if you're at ...
1
vote
1answer
64 views

Longest Common Subsequence Via Dynamic Programming

I read the wikipedia page on the Longest Common Subsequence problem to understand the LCS Table approach, but it seems to result in different solutions given different orders of the original ...
4
votes
1answer
60 views

Why is the running time of edit distance with memoization $O(mn)$?

I understand without memoization it is going to be $O(3^{\max\,\{m,n\}})$ because every call results in extra three calls: thus we end up having a call tree with three children for each node, with ...
-1
votes
1answer
72 views

Dynamic Programming - Adding up N Integers

I'm studying for a final and the professor gave us a practice problem to prepare, but it's extremely difficult and I've been hacking at it for hours with no luck. Here it is: It's driving me ...
0
votes
0answers
65 views

Dynamically weighted priority queue?

Elements are stored in a single dynamic data-structure $D$ Element ranks are computed by: $\forall i \in n\quad f(i,\ x_i+1) : x_i \in \mathbb{Z^+}$ The function $f$ is weighting based on the value ...
1
vote
2answers
85 views

Find the coins required which sum to S

Given a list of $N$ coins, their values $V_1, V_2, \cdots , V_N$, and a parameter of a total sum $S$. Find the coins the sum of which is S (we can use each coin at most once). I was recently studying ...
3
votes
1answer
216 views

What is a naive method?

I was researching dynamic programming and read the following: Often when using a more naive method, many of the subproblems are generated and solved many times. What is a naive method?
2
votes
2answers
202 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
202 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
157 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
31 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
475 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
63 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
13 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
28 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
57 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
327 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
132 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
101 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
171 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
169 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
77 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
154 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
107 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
57 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
495 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
55 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
63 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
91 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
442 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
253 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
309 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
31 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. ...
6
votes
1answer
118 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
45 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
316 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
710 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
284 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
395 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
58 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 ...