Skip to main content
Share Your Experience: Take the 2024 Developer Survey
6 votes

The Dyck Language Correction Problem

The generalized problem, concerning Dyck($s$), for $s$ distinct pairs of parenthesis, was studied by Barna Saha in a paper entitled The Dyck Language Edit Distance Problem in Near-linear Time B. Saha, ...
Yossi Gil's user avatar
  • 531
4 votes

Reference for automatically deriving dynamic programming algorithms from recursive algorithms?

There's actually two questions here! The transformation you ask about is called the tupling transformation. Basically, if your recursive calls follow a fixed pattern of overlap, a memo-table can be ...
Neel Krishnaswami's user avatar
4 votes
Accepted

Longest stack-sortable subsequence

There's a polynomial-time dynamic programming algorithm in section 3.2 of https://ajc.maths.uq.edu.au/pdf/28/ajc_v28_p225.pdf (Albert et al, "Longest subsequences in permutations", Australas. J. ...
David Eppstein's user avatar
3 votes

Ordering of sub problems in dynamic programming

This is not a research level question. In any case DP is obtained by memoizing a recursion. If you start with an instance $I$ then the recursion generates several subproblems. You can obtain a ...
Chandra Chekuri's user avatar
3 votes

Is the knapsack variant with small profit and unlimited repetition of items NP-hard?

The problem (unbounded Knapsack with small profits) has a polynomial-time algorithm. Theorem 1. For unbounded Knapsack with integer profits $(p_1,\ldots,p_n)$, there is an algorithm running in time ...
Neal Young's user avatar
  • 10.8k
3 votes
Accepted

Minimizing the gaps with incremental capacity

Here's a poly-time dynamic-programming algorithm. Lemma 1. The problem in the post has a poly-time dynamic-programming algorithm. Proof sketch. Fix an input $(\zeta, c)$ over time slots $\{1,2,\ldots, ...
Neal Young's user avatar
  • 10.8k
3 votes

Sources that prove solving 2-SAT with DP takes linear time

It is a very basic exercise for undergraduate/graduate courses in Theoretical computer Science, and I think books avoid giving the solution so that students do not copy it without understanding. Here ...
J..y B..y's user avatar
  • 2,776
3 votes

The Dyck Language Correction Problem

If by "edit operations" you mean single character insertions, deletions, and substitutions then I believe a greedy algorithm works. Let $x_i$ be the number of ] minus the number of [ in the ...
Whosyourjay's user avatar
2 votes

Box stacking problem, and variants

If you model a box as a point $(b_1,b_2, \ldots, b_d)$, and you define the dominance relationship $p \prec q$ $\iff$ $p_i < q_i$, for all $i$, then you are looking for the longest chain in this ...
Sariel Har-Peled's user avatar
2 votes

A dominate vector subset sum problem

It's hard for $k\ge 2$ by a reduction from Partition. Let's first look at $k = 3$. Suppose that the input to Partition is the numbers $x_1, \ldots, x_n$, and their sum is $S$. For each $i$ create a ...
Sasho Nikolov's user avatar
2 votes

Beating naive dynamic programming: examples similar to integer partitions?

One nice example is the Hamiltonian Path problem is easily solvable in $O(2^n(n+m))$ time (Bellman, 1962) by dynamic programming over vertex subsets. In 2010 Björklund gave an algorithm running in ...
daniello's user avatar
  • 3,266
2 votes

Counting words of length $n$ in an inherently ambiguous CFG?

It seems that this problem is NP-hard, if both the grammar and $n$ (in unary notation) are considered to be parts of the input. There is a classical construction that is used to show that universality ...
Kaban-5's user avatar
  • 245
2 votes

Dynamic programming and shortest path problem

Here's a less formal answer that I hope nonetheless addresses the spirit of the question. Many standard dynamic-programming algorithms are easily seen to be equivalent to shortest-path (or longest-...
Neal Young's user avatar
  • 10.8k
1 vote

Max weight travel on a graph with deadline

Since you specifically ask later about the version of the problem in which the given path is restricted in how many times it visits each vertex/edge, I assume that the original version of the problem ...
Mikhail Rudoy's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible