Unanswered Questions
260 questions with no upvoted or accepted answers
12
votes
1
answer
5k
views
Finding the longest repeating subsequence
Given a string $s$, I would like to find the longest repeating (at least twice) subsequence. That is, I would like to find a string $w$ which is a subsequence (doesn't have to be a contiguous) of $s$ ...
- 280k
9
votes
0
answers
784
views
How can the shortest traveling salesman tour be found in $O(2^n poly(n))$ time and less than exponential space?
I'm stuck on problem 9.4 from The Nature of Computation which reads:
Dynamic Salesman. A naive search algorithm for TSP takes $O(n!)$ time to check all tours. Use dynamic programming to reduce this ...
- 1,058
8
votes
0
answers
647
views
Chained operations on sequences with two operators
Given a binary expresion tree, with addition and multiplication operations, how can we optimize it's evaluation?
Can we learn from matrix chain multiplication? A generalization of matrix chain ...
CommunityBot
- 1
6
votes
0
answers
97
views
Scheduling tasks on a graph with assistance
This is a follow-up to a question that I recently posted here: Completing tasks on a graph. In that question, I posted the following:
Consider a graph $G = (V, E)$, where $V = \{0, 1, 2, \ldots, n\}$. ...
CommunityBot
- 1
6
votes
1
answer
124
views
A dynamic program to decide whether the solution is in a given range
In the subset sum problem, the input is a list of positive integers $x_1,\ldots,x_n$ and an integer $T$, and the goal is to decide whether there is a subset of sum exactly $T$.
The problem can be ...
- 6,188
5
votes
0
answers
457
views
Count Wildcard Parenthesizations of a String
Let $\Sigma = \{ (, ), ? \}$ be an alphabet. For a given string $s \in \Sigma^*$, we denote by $f(s)$ the number of ways to replace each symbol $?$ either with $($ or with $)$ such that $s$ is ...
- 73.1k
5
votes
0
answers
180
views
Sequence Alignment with Skips
In my thesis I am working on a problem connected with sequence alignment, in particular, I deal with the Dynamic Time Warping (DTW) algorithm (see this for more), which is used to evaluate the ...
5
votes
1
answer
1k
views
2D version of LeetCode house robber problem
The house robber problem of leetcode can be described as followed :
A robber enters a colony of houses numbered from 1 to n. Every house has a number printed on the top of it. That number is the ...
CommunityBot
- 1
4
votes
0
answers
157
views
Find a dynamic programming solution that minimize the sum of the diameters of two clusters?
I asked a question at this link, where I suggested a greedy algorithm for this problem:
Suppose given $2n$ points in the plane and we want partition points into two clusters $C_1$ , $C_2$ such that ...
- 83
4
votes
0
answers
227
views
Assign n people to m rooms of different sizes, such that noone is alone
I'm looking for an efficient way to assign n people to m rooms in a very specific way.
INPUT:
The program receives two sets of people (set of males and set of females), as well as a set of available ...
D.W.♦
- 167k
4
votes
0
answers
290
views
Maximum weight independent set in a King's graph
I would like to find a maximum weight independent set in a finite section of a King's graph.
For an $m\times n$ King's graph where $n \ll m$, we can use an $O(2^{2n} m)$ bitmask dynamic programming ...
- 141
4
votes
0
answers
121
views
What is the relationship between the Markov property and optimal substructure?
Dynamic programming can only be applied to problems with optimal substructure.
The Markov property (e.g. in Markov Decision Processes, MDPs) means that the distribution of one state $x_{k+1}$ only ...
D.W.♦
- 167k
4
votes
0
answers
1k
views
can we solve dynamic knapsack problem using Memoization approach?
As we know Dynamic programming has two techniques.
Bottom up dynamic programming approach.
Top down memoization approach
Normally dynamic knapsack problem is solved using Bottom up dynamic programming ...
- 239
4
votes
0
answers
608
views
Does the Longest Common Subsequence problem reduce to its binary version?
I am working on a problem regarding the Longest Common Subsequence (LCS) of two strings, and I was wondering if there is any reduction from the general case of LCS to its binary version, i.e. by ...
- 73.1k
4
votes
0
answers
1k
views
When not to use dynamic programming
I was reading about dynamic programming and I understood that we should not be using dynamic programming approach if the optimal solution of a problem does not contain the optimal solution of the ...
