Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
1
vote
0answers
164 views
Closed form for a dynamic programming recurrence [closed]
I am looking for a closed form for the the following recurrence:
$$
D(z,k,l) = \begin{cases}
(z-l) D(z-1,z,z-2-l) + (l+1) D(z-1,z,z-3-l), & k = z+1, \\
(z-l) D(z-1,k-2,l) + (l+1) D(z-1,k-2,l+1), ...
2
votes
1answer
162 views
Trouble understanding this dynamic programming solution
Here is the question:
I have a given tree with n nodes. The task is to find the number of subtrees of the given tree with outgoing edges to its complement less than or equal to a given number K.
for ...
1
vote
1answer
54 views
Find longest common subsequence in limited space
Given three strings $x$, $y$, and $z$ over an arbitrary finite alphabet, I need to determine their longest common subsequence (LCS).
Example: A longest common subsequence of ...
3
votes
2answers
77 views
MAX 10-SAT Algorithm
The MAX k-SAT problem is:
“Given a set of clauses C1,…,Ck, each of length k, over a set of
variables x1,…,xn, find a truth assignment that satisfies as many of
the clauses as possible.”
I'm ...
4
votes
1answer
78 views
Issues with using greedy algorithm (Interval scheduling variant)
I am trying to solve a problem of finding incompatible jobs set using greedy algorithm. However, I am not sure if greedy algorithm can solve this problem or I need to perform another approach.
I have ...
2
votes
1answer
49 views
Confusion related to time complexity of dynamic programming algorithm for knapsack problem
I have this confusion related to the time complexity of the algorithm solving the knapsack problem using dynamic programming
I didn't get how the time complexity of the algorithm came out to be ...
4
votes
1answer
69 views
Find the longest subsequence of two strings
I want to know which is the best way to find the longest common subsequence of two strings
4
votes
1answer
105 views
Sorting Problem
I have come across the following problem.
You have $N$ registers, numbered $1,2,\dots, N$, each of which can hold an integer value. You
are given the initial values of the registers, which have the ...
0
votes
0answers
21 views
DP Recurrence Relation Finding [duplicate]
How do people find the DP Recurrence relation while solving contest problems (like in SPOJ, topcoder etc.)
I have read Cormen and many other algorithms book. But they just explain only one or two of ...
2
votes
1answer
100 views
How to master Dynamic Programming? [duplicate]
I am having hard times learning Dynamic Programming.
I looked around the web and found many tutorials with examples.
Each time I tried to figure out how to solve a new problem before looking at the ...
0
votes
1answer
46 views
Proving correctness of the algorithm for convex polygon minimum cost triangulation
I have read many solutions for the minimum cost of triangulation problem and intuitively get the idea , however I am struggling to figure out how to prove it formally. I kind of feel that it has to be ...
3
votes
1answer
36 views
Select optimal subintervals from array
I have an input array and I have to select an indefinite number of intervals from it so that the "profit" is maximal and I have exactly T elements selected in total, where T is given. Profit means the ...
1
vote
1answer
51 views
Time Complexity Upper Bound of Memoized DP Problems
I find it fairly easy to generate an upper bound for nearly any iterative solution (e.g. look at the limits on each loop, etc.), and can oftentimes create an upper bound for normal recursive ...
0
votes
1answer
74 views
Confusion related to dynamic programming [closed]
I was going through this dynamic programming problem. However, I have a confusion
In the third picture, having the black border, I didn't get how the
For each, we try each string of the k ...
1
vote
2answers
173 views
Count unhappy numbers in a large interval
An unhappy number is a number that is not happy, i.e., a number $n$ such that iterating this sum-of-squared-digits map starting with n never reaches the number 1.
For example, $23\rightarrow ...
1
vote
0answers
215 views
Activity Selection in Dynamic Programming
I'm trying to write pseudocode for the Activity Selection Problem in dynamic programming as opposed to Greedy Algorithm. The recurrence I have is:
...
-6
votes
1answer
165 views
Maximizing profit
Problem:
Given 11 numbers
{N1,N2,N3,N4,N5,N6,N7,N8,N9,N10,N11}
where
N1:amount of profit from product A
N2:amount of profit from Product B
N3:amount of ...
3
votes
3answers
225 views
Finding all solutions to subset sum for integers with bounded weights
Suppose I have the set of weights $W = \{w_1,w_2,\ldots,w_{50}\}$ where each $1 \le w_i \le 60$ is an integer. I am interested in determining all subsets (not just one, and not just the number of ...
0
votes
2answers
98 views
Broken stick problem
We have a broken stick. For every part, we know it's length. Our task is to connect all parts (glue them), that we will use as small amount of glue as possible.
The amount of glue need to connect ...
4
votes
1answer
168 views
Smallest string length to contain all types of beads
I read this question somewhere, and could not come up with an efficient answer.
A string of some length has beads fixed on it at some given arbitrary distances from each other. There are $k$ ...
4
votes
1answer
185 views
Find maximum distance between elements given constraints on some
I have a list of numbered elements 1 to N that fit into positions on a number line starting with 1. I also have constraints for these elements:
The element 1 is in position 1, and element N must be ...
3
votes
2answers
257 views
Modified paths Counting in a Rectangle
I was solving the following problem. But I am not able to think of an efficient algorithm for this modified version of problem. The problem statement is:
We are given K Rectangles. The dimensions ...
1
vote
1answer
124 views
String similarity problem
We are given two strings $x=x_1,x_2,x_3,\ldots,x_m$ and $y=y_1,y_2,y_3,\ldots,y_n$ over some finite alphabet.
We consider the problem of converting $x$ to $y$. Using the following operations:
...
4
votes
2answers
144 views
Fuzzy string matching algorithm with allowed events?
I want to be able to locate a substring in a string allowing for a specified number of mismatches, insertions and deletions - and at the same time know how many mismatches, insertions and deletions ...
1
vote
1answer
56 views
Minimum cost subset of sensors covering targets
I have a dynamic programming problem:
If I have a set of sensors covering targets (a target might be
covered by mutiple sensors) how can I find the minimum cost subset of
sensors covering all ...
0
votes
0answers
79 views
Recursive relation help for dynamic programming 2D plane algorithm
Consider a straight highway in the plane which can be modelled by a horizontal strip in the plane. A finite set T of targets are located on the highway, and a finite set S of wireless sensors are ...
7
votes
0answers
358 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 ...
3
votes
0answers
86 views
Best a-little-advanced examples of dynamic programming, polynomial reduction and approximation algorithm
I was offered by a professor to give some tutoring in his course of Algorithm Design, based on Kleinberg and Tardos' book. He suggested me to prepare two exercise on dynamic programming, one exercise ...
1
vote
2answers
525 views
Dynamic programming: Knapsack with repetition, Find the number of redundant machines
I have just started to learn Dynamic Programming, and so far I have studied the few basic concepts; longest common subsequent problem, edit distance problem and the knapsack problem. I have attempted ...
1
vote
1answer
135 views
Memoized Palindrome Subsequence
I am trying to find the maximum palindrome sub-sequence and after going through some tutorials, I came up with a memoized version.But I am not sure about the runtime.I want to know if the following ...
6
votes
2answers
153 views
Dynamic programming algorithms with log in the run-time
Most of the classic examples of dynamic programming algorithms have run-times such as $n$ or $n^2$. Are there any natural examples with a $O(n \log n)$ run-time?
2
votes
1answer
108 views
Levenstein distance and dynamic time warp
I am not sure how to draw parallel between the Wagner–Fischer algorithm and dtw algo.
In both case we want to find the distance of each index combination (i,j).
In Wagner–Fischer, we initiate the ...
1
vote
1answer
568 views
Inventory planning problem solved through dynamic programming
I am working on problem (15-11) Inventory planning from Introduction to Algorithms (CLRS, 3rd Ed).
15-11: Inventory Planning, p.411
The Rinky Dink Company makes machines that resurface ice ...
3
votes
1answer
141 views
Adjacent house , dynamic programming problem
I have to be honest this is a homework problem, but I just need to discuss this with some one. The problem is there is a row of n houses, with different profit e.g profit1 for house 1, it can be ...
-2
votes
1answer
75 views
Regarding the height of a recursion tree on dynamic programming
I am trying to understand dynamic programming and I am watching this mit video. If you guys could take some time out , can you refer to the slide on 41:36 . Why is the height m+n. I just don't get it ...
1
vote
1answer
705 views
How can I improve my Algorithm?
This is a problem from Interview Street in Dynamic Programming section.
https://www.interviewstreet.com/challenges/dashboard/#problem/4f2c2e3780aeb
Billboards(20 points)
ADZEN is a very ...
3
votes
1answer
207 views
Maximum Schedulable Set Zero-Lateness Deadline Scheduling
This is a homework problem for my introduction to algorithms course.
Recall the scheduling problem from Section 4.2 in which we sought to
minimize the maximum lateness. There are $n$ jobs, each ...
-1
votes
1answer
271 views
How to do Fairy Chess problem in O(N^3)?
https://www.interviewstreet.com/challenges/dashboard/#problem/4f1c88e0dec8a
Fairy Chess (35 Points)
You have a $N \times N$ chess board. An $S$-leaper is a chess piece which can move from ...
2
votes
2answers
540 views
Dynamic Programming Solution for Optimal Matrix Chain Multiplication Order
I have been thinking about why the dynamic programming approach to finding the optimal matrix chain order is better than a brute force approach that finds the optimal order by exploring all nested ...
3
votes
3answers
134 views
Optimize a linear recurrence
$$\begin{align*}
T[1] &= 1 \\
T[2] &= 2 \\
T[i] &= T[i-1] + T[i-3] + T[i-4] & \text{for \(i \gt 2\)} \\
\end{align*}$$
I have to calculate $T[N]$, but $N$ is too big ($\approx ...
2
votes
2answers
277 views
Dynamic programming table for finding similar substrings is too large
Substring Diff
Given two strings of length $n$, $P = p_1\dots p_n$ and $Q = q_1 \dots q_n$, we define $M(i, j, L)$ as the number of
mismatches between $p_i \dots p_{i+L-1}$ and $q_j \dots ...
6
votes
2answers
484 views
Dynamic programming with large number of subproblems
Dynamic programming with large number of subproblems. So I'm trying to solve this problem from Interview Street:
Grid Walking (Score 50 points)
You are situated in an $N$-dimensional grid at ...
4
votes
2answers
213 views
Problem contest with matrix and DP
I found this problem while I was reading an ACM problem and it is about dynamic programming. The problem says that you have a square matrix $n\times n$ filled with 1's or 0's, like this:
...
6
votes
1answer
120 views
Micro-optimisation for edit distance computation: is it valid?
On Wikipedia, an implementation for the bottom-up dynamic programming scheme for the edit distance is given. It does not follow the definition completely; inner cells are computed thus:
...
6
votes
2answers
168 views
Maximum number of points that two paths can reach
Suppose we are given a list of $n$ points, whose $x$ and $y$ coordinates are all non-negative. Suppose also that there are no duplicate points. We can only go from point $(x_i, y_i)$ to point $(x_j, ...
4
votes
2answers
283 views
Efficiently calculating minimum edit distance of a smaller string at each position in a larger one
Given two strings, $r$ and $s$, where $n = |r|$, $m = |s|$ and $m \ll n$, find the minimum edit distance between $s$ for each beginning position in $r$ efficiently.
That is, for each suffix of $r$ ...
2
votes
2answers
330 views
How to use dynamic programming to solve this?
Here is the question: suppose we are given x cents, the amount we want to pay, and a 6-tuple (p, n, d, q, l, t) that represents respectively the number of pennies, nickels, dimes, quarters, loonies ...
9
votes
2answers
512 views
When can I use dynamic programming to reduce the time complexity of my recursive algorithm?
Dynamic programming can reduce the time needed to perform a recursive algorithm. I know that dynamic programming can help reduce the time complexity of algorithms. Are the general conditions such that ...
2
votes
2answers
174 views
Is it possible to use dynamic programming to factor numbers
Let's say I am trying to break all the numbers from 1 to N down into their prime factors. Once I have the factors from 1 to N-1, is there an algorithm to give me the factors of 1 to N using dynamic ...
6
votes
2answers
190 views
Maximise sum of “non-overlapping” numbers in square array - help with proof
A question was posted on Stack Overflow asking for an algorithm to solve this problem:
I have a matrix (call it A) which is nxn. I wish to select a subset
(call it B) of points from matrix A. ...
