abhi1988srivastava
BAN USER- 0 Answers Ford Fulkerson : Backedge conditions
Hi,
- abhi1988srivastava December 11, 2013
I was going through Ford Fulkerson and there was a condition for back edge but I did not understand what is the condition for considering back edge? I can go on and on if I can consider back edge all the time.
Please some one can verify when to consider back edge..I know if there is residual capacity in the graph , I can continue but till when ?
Regards
Abhinav| Flag | PURGE - 0 Answers Ford Fulkerson : Backedge conditions
Hi,
- abhi1988srivastava December 11, 2013
I was going through Ford Fulkerson and there was a condition for back edge but I did not understand what is the condition for considering back edge? I can go on and on if I can consider back edge all the time.
Please some one can verify when to consider back edge..I know if there is residual capacity in the graph , I can continue but till when ?
Regards
Abhinav| Flag | PURGE - 0 Answers Ford Fulkerson : Backedge conditions
Hi,
- abhi1988srivastava December 11, 2013
I was going through Ford Fulkerson and there was a condition for back edge but I did not understand what is the condition for considering back edge? I can go on and on if I can consider back edge all the time.
Please some one can verify when to consider back edge..I know if there is residual capacity in the graph , I can continue but till when ?
Regards
Abhinav| Flag | PURGE - 0 Answers Increasing Digital Subsequence Problem
Hi,
- abhi1988srivastava October 30, 2013
I was going through the Jeff Erikson notes on Dynamic programming and got stuck with one of the questions in the exercise. Here my pasting the complete question :
Let D[1.. n] be an array of digits, each an integer between 0 and 9. An digital subsequence of
D is an sequence of positive integers composed in the usual way from disjoint substrings of D.
For example, 3,4,5,6,8,9,32,38,46,64,83,279 is an increasing digital subsequence of the first
several digits of :
3 , 1, 4 , 1, 5 , 9, 2, 6 , 5, 3, 5, 8 , 9 , 7, 9, 3, 2 , 3, 8 , 4, 6, 2, 6, 4 , 3, 3, 8, 3 , 2, 7, 9
The length of a digital subsequence is the number of integers it contains, not the number of digits;the preceding example has length 12.
Describe and analyze an efficient algorithm to compute the longest increasing digital subsequence of D.
I thought of starting it with LIS restrircing to single digit number and adding 1 to it but how to compare for range of values like comparing for two k digits.
(restricting to single digit):
DS(i) = 1+ max{DS(j)} where j<=9 and A[i]>A[j]
Please help.
Regards
Abhinav| Flag | PURGE - 4 Answers Previous large element
Hi ,
- abhi1988srivastava September 02, 2013
Given a sequence of n numbers, {a1; a2; · · · ; an}, for each element
ai
, 1 ≤ i ≤ n, nd the index of the rightmost element inside {a1; a2; · · · ; ai1} whose value is
strictly larger than ai
. If no element is larger than ai then output 0. In other words, nd for
each i
pi = max{j|0 ≤ j < i; aj > ai};
in which assume a0 = ∞
algorithm should work in O(n).
How to proceed?
What I thought : it seems to me as a upper triangular matrix and finding max for each column..
Correct me if I am wrong but how to do in O(n)?
Regards
Abhinav| Flag | PURGE
I am not sure..but isn't the problem of Knapsack. :)
- abhi1988srivastava October 30, 2013