Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
1
vote
1answer
45 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
73 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
75 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
35 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
66 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
-3
votes
0answers
39 views
Finding a better algorithm for a problem [closed]
Interval scheduling.
Job j starts at sj and finishes at fj
What is the best way to solve this?
4
votes
1answer
102 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
85 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
42 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
33 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
50 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
73 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
167 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
159 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
164 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
212 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
95 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
165 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
182 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
254 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
117 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
135 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
76 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
350 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
81 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
497 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
134 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
144 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
96 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
528 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
140 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
691 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
201 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
245 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
505 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
269 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
472 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
210 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
111 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
167 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
240 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
325 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
466 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
170 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
167 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. ...
8
votes
2answers
1k views
dynamic programming exercise on cutting strings
I have been working on the following problem from this book.
A certain string-processing language offers a primitive operation which splits a string into two
pieces. Since this operation ...
