# Tag Info

35

The main confusion lies in the difference between "size" and "value". "Polynomial Time" implies polynomial w.r.t the size of input. "Pseudopolynomial Time" implies polynomial w.r.t the value of the input. It can be shown (below) that this is equivalent to being exponential w.r.t the size of the input. In other words: Let $N_{size}$ represent the size of ...

29

Dynamic programming gives you a way to think about algorithm design. This is often very helpful. Memoization and bottom-up methods give you a rule/method for turning recurrence relations into code. Memoization is a relatively simple idea, but the best ideas often are! Dynamic programming gives you a structured way to think about the running time of your ...

17

A dynamic programming algorithm will examine all possible ways to solve the problem and will pick the best solution. This statement is just plain wrong. Dynamic programming recurrences do (often) consider all possible ways to split the given problem instance into smaller instances according to some scheme. However, it will not combine all solutions to all ...

16

It's not a technical term with a precise meaning, it is just the English word "naive". In a computer science context, the word usually means something like "one of the things you would think of first, but without realizing a less obvious but important fact". For instance, if one knows the definition of Fibonacci numbers is $\mathrm{Fib}(n) = \mathrm{Fib}(n-... 14 The different dimensions are independent. What you can do is compute, for each dimension j, how many different walks there are in just that dimension which take$t$steps. Let us call that number$W(j,t)$. From your question, you already know how to compute these numbers with dynamic programming. Now, it's easy to count the number of walks that take$t_i$... 12 When we say polynomial or exponential, we mean polynomial or exponential in some variable.$nW$is polynomial in$n$and$W$. However, we usually consider the running time of an algorithm as a function of the size of the input. This is where the argument about$\log W$comes in. Ignoring the values of the items for the moment (and considering only their ... 12 The longest path problem does have optimal substructure, and this can be used to improve the trivial$O(n!)$algorithm to an$\tilde{O}(2^n)$algorithm. First we have to generalize the problem: Generalized longest path: Given a graph$G=(V,E)$, two vertices$s,t \in V$, and a set of vertices$A \subseteq V \setminus \{s,t\}$, find the longest path in$G$... 11 Your understanding of dynamic programming is correct (afaik), and your question is justified. I think the additional design space we get from the kind of recurrences we call "dynamic programming" can best be seen in comparison to other schemata of recursive approaches. Let's pretend our inputs are arrays$A[1..n]$for the sake of highlighting the concepts. ... 10 The basic idea is: Try out all cut positions as first choice, solve the respective parts recursively, add the cost and choose the minimum. In formula:$\qquad \displaystyle \operatorname{mino}(s, C) = \begin{cases} |s| &, |C| = 1 \\ |s| + \min_{c \in C} \left[ \begin{align}&\operatorname{mino}(s_{1,c}, \{c' \in C \mid c' < c\})\ \\ +\...

10

There is no (one) formal definition of "optimal substructure" (or the Bellman optimality criterion) so you can not possibly hope to (formally) prove you have it. You should do the following: Set up your (candidate) dynamic programming recurrence. Prove it correct by induction. Formulate the (iterative, memoizing) algorithm following the recurrence.

10

Summary: the memoization technique is a routine trick applied in dynamic programming (DP). In contrast, DP is mostly about finding the optimal substructure in overlapping subproblems and establishing recurrence relations. Warning: a little dose of personal experience is included in this answer. Reading suggestion: If this answer looks too long to you, just ...

9

Dynamic programming is useful is your recursive algorithm finds itself reaching the same situations (input parameters) many times. There is a general transformation from recursive algorithms to dynamic programming known as memoization, in which there is a table storing all results ever calculated by your recursive procedure. When the recursive procedure is ...

9

Actually, there is nothing special in the name "dynamic programming"; the technique itself is just about smartly unwinding recursion. See this question and look at @Jeffe answer, in which is reported that Belman choose that name to be intentionally distracting.

9

Very nice question! You are twice right: Propagating the number of items in the knapsack does not lead to optimal solutions. One solution consists of adding a third dimension. This is rather simple but it is necessary to take some facts into account when doing so. Note however that it is not the only alternative In the following, I am assuming that you ...

9

Dynamic Programming is clever as it reuses computation, while brute force doesn't. Suppose to solve, f(6), you need to solve 2 sub-problems which both call f(3). The brute force method will calculate f(3) twice thereby wasting effort while dynamic programming will call it once, save the result in case future computations need to use it. In many problems, ...

9

I am using terminology and notations from Earley's paper. It is possible that the description you read is different. It seems frequent that general CF parsing algorithms are first presented in the form of a recognizer, and then the information management needed to actually build parse trees and parse forests is sort of added as an afterthought. One reason ...

9

The picture should say more than words.

9

A generalization of this class of problems is widely studied. See, e.g., this paper for a survey. In your particular case, the problem can be easily solved without any asymptotic change in the computational complexity. Run the binary search three times. At least two of the three results must be equal to the hidden number. Return the majority result. There ...

8

If you just seek to speed up your recursive algorithm, memoisation might be enough. This is the technique of storing results of function calls so that future calls with the same parameters can just reuse the result. This is applicable if (and only if) your function does not have side effects and does only depend on its parameters (i.e. not on some state). ...

8

You can do it in $O(N \log N)$ time and $O(N)$ space. Instead of finding the billboards that you want to keep, find the billboards that you want to get rid of. You need to find the minimum cost set of billboards such that there is no gap of more than $K$ between two billboards. Do this by constructing a table where the $i$th entry is the minimum cost to ...

8

The key to understanding a dynamic programing problem is understanding the recursive definition and this can be daunting. For this problem we start with n objects labeled 1 to n. We define $O(K,W)$ to be the optimal value for the first k items with a total weight W, we need to be able to define this in terms of subproblems now since without that, dynamic ...

8

CYK is still relevant, afaik, as the simplest example of a family of general parsing algorithm based on dynamic programming, ranging over all parsing technique (that I know of) and many syntactic formalisms. There is a simpler general parsing algorithm (below), but where the dynamic programming (DP) aspect is no longer visible. as things are defined more ...

7

As Bartek commented, you are missing a base case. You can compute large values of $T$ in several ways: Bartek's suggestion: Use an array to store all the entries computed so far. You can optimize the previous method, dramatically reducing the memory needed: store only the last $4$ entries of the array at each point in time. Use matrix powering. There are ...

7

Actually, I don't believe your proposed solution is correct. An example where you might need this case | # | | # # #| | # # #| | # # #| might be | 1 2 1 1| | 2 1 1 1| | 1 1 1 2| | 1 1 2 1| The optimal solution consists of all 2s, while there are only 1s in the corners; therefore, you cannot find an optimal solution just by starting at the ...

7

What you describe is a linear program. You can use the following formulation: Let $x_i$ be the $i$th element. The variables are $d_1,\ldots, d_{n-1}$, where $d_i$ denotes difference between $x_{i+1}$ and $x_i$. You require $d_i\ge 0$. If two elements $x_i,x_j$ should be at least within some distance $\ell^-_{ij}$, then you set  d_i+d_{i+1}+\cdots +d_{j-1}...

7

Try choosing a random assignment.

7

A well-known example is the Held-Karp dynamic programming approach to solving the traveling salesman problem (TSP), running in $O(n^22^n)$ time and $O(n2^n)$ space. For more, see these notes.

7

Suppose that the rectangle to be tiled has 3 rows and $n$ columns. □□□...□ □□□...□ □□□...□ 123...n Consider a tiling of this rectangle using 2$\times$1 dominos. There are two basic options: All tiles touching the $n$th column are horizontal. There must be 3 of them, and if you remove them, you get a tiling of a rectangle of size $3\times(n-2)$. □□□...⧆⧆ ...

7

For that recurrence to make sense, $V$ can only be the array that contains the coin values; that is, $V=\{C_1, C_2, ..., C_m\}$. Whenever confronted with a new dynamic programming problem, you should always try to understand how optimal solutions are structured in terms of optimal solutions for smaller subproblems (cf. optimal substructure). This will help ...

7

Here is the fastest algorithm. I bet. The idea of the algorithm can be seen from the one-line explanation between step 4 and step 5 below. Input: $e_1,\cdots,e_n\in E$, where $n\ge 3$. Output: $p_1, \cdots, p_n$, where $p_j=e_1\cdots e_{j-1}e_{j+1}\cdots e_n$, the product of all input elements except $e_j$. Procedure: Allocate array $p_1, p_2,\cdots, p_n$ ...

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