Tagged Questions
3
votes
1answer
62 views
Calculating the complexity of Levenshtein Edit Distance
I have been looking at this simple python implementation of Levenshtein Edit Distance for all day now.
def lev(a, b):
"""Recursively calculate the Levenshtein edit distance between two strings, a ...
0
votes
1answer
39 views
k-means in dynamic programming complexity?
We all know that the k-means algorithm: which has a complexity of O( n * K * I * d ) Where:
n = number of points
K = number of clusters
I = number of iterations
d = number of attributes
but my ...
4
votes
2answers
133 views
Algorithm without dynamic programming,less efficient solution
There is a problem asked in contest. I already solved this problem with dynamic programming and its complexity O(n^2). But i am looking for solution with less efficient way. What will be the ...
2
votes
2answers
105 views
Independence property of sub problems for dynamic programming techniques to apply
Two criteria for an algorithm to be solved by dynamic programming technique is
Sub problems should be independent.
Sub problems should overlap .
I think I understand what overlapping means . It ...
3
votes
5answers
301 views
algorithm to find ten integers>0 that sum to 2011 but their reciprocals sum to 1
find ten integers>0 that sum to 2011 but their reciprocals sum to 1
e.g.
x1+x2+..+x10 = 2011
1/x1+1/x2+..+1/x10 = 1
I found this problem here ...
3
votes
1answer
287 views
Dynamic Programming to Minimize Sum of Squares
I have this question on a practise exam, and have no idea how to solve it, so I'm very scared for the final. Anyways, finding that this problem has an answer would be relieving and would help me ...
0
votes
1answer
394 views
Complexity for top-down dynamic programming algorithms [closed]
I am able to write recursive functions for most of the dynamic programming problems. But finding time complexity for top-down DP solutions is rather difficult. I couldn't find any good tutorial on ...
1
vote
4answers
2k views
Partition Problem.
An algorithm interview question:
You are given an array which consists
of numbers with between 0 and 5 digits.
Write a function which will return whether the array can be divided
into 2 ...
14
votes
9answers
848 views
algorithm to find longest non-overlapping sequences
I am trying to find the best way to solve the following problem. By best way I mean less complex.
As an input a list of tuples (start,length) such:
[(0,5),(0,1),(1,9),(5,5),(5,7),(10,1)]
Each ...
12
votes
1answer
2k views
Why is the knapsack problem pseudo-polynomial?
I know that Knapsack is NP-complete while it can be solved by DP. They say that the DP solution is pseudo-polynomial, since it is exponential in the "length of input" (i.e. the numbers of bits ...
23
votes
6answers
2k views
Challenging dynamic programming problem
This is a toned down version of a computer vision problem I need to solve. Suppose you are given parameters n,q and have to count the number of ways of assigning integers 0..(q-1) to elements of ...
2
votes
2answers
651 views
Interesting variation to the subset sum problem
An interesting variation of the subset sum problem was presented to me by a friend from work:
Given a set S of positive integers, of size n, and integers a and K, is there a subset R (of the set S) ...
2
votes
2answers
279 views
Amazing families of algorithms over implicit graphs
Dynamic programming is, almost by definition, to find a shortest/longest path on an implicit dag.
Every DP algorithm just does this.
An Holographic algorithm can be loosely described as something ...
