Author |
Topic: Numeric Sequences (Read 3829 times) |
|
Dudidu
Full Member
Posts: 227
|
|
Numeric Sequences
« on: Nov 27th, 2003, 8:46am » |
Quote Modify
|
You are given a sequence of numbers A = [langle]a1, a2, a3, ... an[rangle]. 1) A monotonically increaing sequence is a subsequence S = [langle]s1, s2, s3, ... sk[rangle] = [langle]ai1, ai2, ai3, ... aik[rangle] such that 1[le]i1<i2<...<ik[le]n and s1<s2<...<sk. Devise an algorithm to find the longest monotonically increaing sequence (in a given sequence). 2...) Will be submitted later (dependent on the progress in (1)).
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Numeric Sequences
« Reply #1 on: Nov 28th, 2003, 3:05am » |
Quote Modify
|
I have an O(n2) time algorithm (which is a slight modification of the string matching algorithm i had used for my LZ77 program once). But seeing your earlier post it seems you might be looking for a O(nlnn) algorithm. But anyways i will put what i have, :: consider three arrays seq[n],len[n] and pre[n]. 1>the seq stores the numbers of the given sequence. 2>len[i] stores the length of the length of the longest subsequence ending with seq[i] 3>pre[i] stores the index of the number preceding it in subsequence. first assume that our sequence is stored in seq and initialise len with 1's and pre with -1's. Now the algorithm, int flag = 0; len[0] = 1; pre[0]=-1; for(i = 1; i < n; i++) { ....for(j = i-1; j >= 0 && !flag; j--) ....{ .........if(seq[i]>seq[j]) .........{ ..............len[i] += len[j]; ..............pre[i] = j; ..............flag = 1; .........} ....} ....flag=0; } now all we have to do is to check the len array for the max number and follow the pre array to determine the subsequence :: This algo might very well be error prone. I gladly invite all criticism over this algorithm.
|
« Last Edit: Nov 28th, 2003, 3:13am by TenaliRaman » |
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
DH
Newbie
Gender:
Posts: 19
|
|
Re: Numeric Sequences
« Reply #2 on: Nov 28th, 2003, 5:56am » |
Quote Modify
|
:: The algo can be modified so that it will run in O(n*log n) time. Just use a binary search tree to keep the numbers ( as the key ) and the associated lengths ( as additional info ). Also each node will store the maximum length from the respective subtree. Updating this structure is done in O(log(n)) time .
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Numeric Sequences
« Reply #3 on: Nov 28th, 2003, 9:09am » |
Quote Modify
|
hey pretty neat idea. I think we also need to have pointers in the node to get the subsequence.
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Numeric Sequences
« Reply #4 on: Nov 30th, 2003, 2:07am » |
Quote Modify
|
TenaliRaman hi, I have looked at your algorithm and it has a little problem (that, of course, can be easily fixed (its up to you )): If you run your algorithm on the sequence seq[] = {2, 3, 1, 4} you'll get len[] = {1, 2, 1, 2} (instead of {1, 2, 1, 3}).: Overlooking this minor problem, this "dynamic programming" algorithm gets it... . Quote:it seems you might be looking for a O(nlnn) algorithm... |
| You are right (but devising this O(n2) algorithm is a very good move in the direction of finding an O(n logn) algorithm) ! DH, We haven't heard from you for a long time... Quote:use a binary search tree... |
| Can you be more specific how this should be done ? (Are you sure that binary search trees are to be used ? maybe you meant somekind of balanced binary search trees ...)
|
« Last Edit: Nov 30th, 2003, 2:09am by Dudidu » |
IP Logged |
|
|
|
tseuG
Junior Member
Gender:
Posts: 62
|
|
Re: Numeric Sequences
« Reply #5 on: Nov 30th, 2003, 3:14am » |
Quote Modify
|
One more approach: Sort A. Let this new array be named B. --> O(n logn) Find the longest common subsequence between A and B --> O(n2) This LCS is the required longest monotonically increasing sequence The whole operation can thus be done in O(n2) time
|
« Last Edit: Nov 30th, 2003, 12:04pm by tseuG » |
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Numeric Sequences
« Reply #6 on: Nov 30th, 2003, 3:40am » |
Quote Modify
|
tseuG welcome, on Nov 30th, 2003, 3:14am, tseuG wrote:...Find the longest common subsequence between A and B --> O(n)... |
| I do not understand how you can find the longest common subsequence (LCS) between A and B in O(n) So... can you spacify how ?
|
« Last Edit: Nov 30th, 2003, 3:40am by Dudidu » |
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Numeric Sequences
« Reply #7 on: Nov 30th, 2003, 3:42am » |
Quote Modify
|
Dudidu, Thanks for pointing that out. And as you say the modification would be minor ::we have to remove the flag variable and add one more if statement inside the current if statement.
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Numeric Sequences
« Reply #8 on: Nov 30th, 2003, 4:10am » |
Quote Modify
|
on Nov 30th, 2003, 3:42am, TenaliRaman wrote:And as you say the modification would be minor... |
| Right, the loop should follow the following (recursive) formula: len[k] = max { len[j] + 1 | 0 [le] j < k and seq[k] > seq[j] } which reflects a sub-loop on all the indexes j which are smaller then k, an 'if statment' to check for monotonically and another 'if statment' to check for maximality...
|
« Last Edit: Nov 30th, 2003, 4:13am by Dudidu » |
IP Logged |
|
|
|
tseuG
Junior Member
Gender:
Posts: 62
|
|
Re: Numeric Sequences
« Reply #9 on: Nov 30th, 2003, 4:21am » |
Quote Modify
|
oops! LCS needs O(n2) time. Thanks for pointing it out Dudidu. I have modified my post.
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Numeric Sequences
« Reply #10 on: Nov 30th, 2003, 8:30am » |
Quote Modify
|
A "follower": 2) A complete bi-monotone sequence is a subsequence S = [langle]s1, s2, s3, ... sk[rangle] = [langle]ai1, ai2, ai3, ... aik[rangle] such that 1[le]i1<i2<...<ik[le]n and s1>s2, s2<s3, s3>s4, and so on (interleaving </>). Devise an algorithm to find the longest complete bi-monotone sequence (in a given sequence). P.S. I'm still waiting for someone to explain how (1) can be done in O(n logn)...
|
|
IP Logged |
|
|
|
tseuG
Junior Member
Gender:
Posts: 62
|
|
Re: Numeric Sequences
« Reply #11 on: Nov 30th, 2003, 2:49pm » |
Quote Modify
|
The crux of part 1 is to find the largest element which is smaller than the element in consideration and also having the longest sequence behind it. For the array 2 3 1 4 , when we are dealing with 4, the element we want is 3. For the array 7 1 2 3 4 8, when we are dealing with 8, the element we want is 4, not 7. And we need to do it in O(log n) time. We could augment a balanced BST (like a red-black tree or an AVL tree) to do this. One way is: Keep inserting the elements of the array into a BBST. Store two pointers with each node. One of them(lm) points to the element in the left subtree with the longest sequence behind it and another(rm) points the analogous element in the right tree. insert(item, tree) { if(item > tree.item) if(tree.lm heads a longer seq than tree.rm) { insert item in tree.right with len field = (tree.lm)+1 traverse back to the node tree, updating the rm's. } else insert recursively in tree.right. else insert recursively in the tree.left } We do two traversals, one down and one up each taking O(logn ) time. Updating fields, like the length of sequence headed by the element at the current node, appropriately based on the fields of tree.parent, tree.left, tree.right, lm and rm takes constant time.
|
|
IP Logged |
|
|
|
Hello
Guest
|
on Nov 28th, 2003, 3:05am, TenaliRaman wrote:I have an O(n2) time algorithm (which is a slight modification of the string matching algorithm i had used for my LZ77 program once). |
| Your solution is probably is probably pretty much the same as mine, you just lost me in all those arrays, so I can't tell. Here's a simpler version using just one array S[i] that records the length of the longest increasing subsequence that starts with A[i]: Initialiaze: Code: Main loop: Code: for (i = N-2; i>=0; --i) { S[i] = 1; for (j = i+1; j<N; ++j) { if (A[j]>A[i] && S[j] + 1 > S[i] { S[i] = S[j] + 1; } } } |
| After this is done the max length, as well as the largest sequence can be extracted from S: Code: maxlen = s[0]; max_ix = 0; for (i = 1; i<N; ++i) if (S[i] > maxlen) { maxlen = S[i]; max_ix = i; } } /* to print the longest seq, traverse S*/ printf ("%d ", A[max_ix]) for (i = max_ix +1, j = max_ix; i<N; ++i) { if (A[i] > A[j] && S[i] == S[j] - 1) { printf("%d ", A[i]); j = i; if (S[j] == 1) break; } } printf("\n"); |
| The runtime is N(N-1)/2, is O(N^2). To make it O(Nlog(N)), it was previously suggested that we could use a balanced tree of nodes {A[k], S[k], L[k]}, where A[k] is the key, S[k] is the same as above, and L[k] is the longest subsequence length of the subtree = max S[j] of the subtree. It was suggested above by DH.
|
|
IP Logged |
|
|
|
Hello
Guest
|
on Dec 1st, 2003, 3:48pm, Hello wrote: Main loop: Code: for (i = N-2; i>=0; --i) { S[i] = 1; for (j = i+1; j<N; ++j) { if (A[j]>A[i] && S[j] + 1 > S[i] { S[i] = S[j] + 1; } } } |
| |
| It seems to me that for the bi-monotone version all you'll need to do is to replace the condition of "if" to use ">" if S[j] is even or "<" if S[j] odd or vice versa; also you'll need to progress "i" in the other direction (1..N), which will make it a little harder to recover the longest sequence...
|
|
IP Logged |
|
|
|
DH
Newbie
Gender:
Posts: 19
|
|
Re: Numeric Sequences
« Reply #14 on: Dec 2nd, 2003, 3:36am » |
Quote Modify
|
on Nov 30th, 2003, 2:07am, Dudidu wrote: DH, We haven't heard from you for a long time... |
| I don't have very much spare time on Nov 30th, 2003, 2:07am, Dudidu wrote: Can you be more specific how this should be done ? (Are you sure that binary search trees are to be used ? maybe you meant somekind of balanced binary search trees ...) |
| yeap , I meant balanced binary tree . In this case we can sort the numbers ( O(nlg(n)) ) and we get a balanced binary tree where any given subtree is represented as a contiguous region of the sorted array ( the root being the node in the middle ).
|
|
IP Logged |
|
|
|
DH
Newbie
Gender:
Posts: 19
|
|
Re: Numeric Sequences
« Reply #15 on: Dec 2nd, 2003, 3:54am » |
Quote Modify
|
For the bi-monotone case the algorithm must compute the longest odd sequence and the longest even sequence that end with a given element. This can be done O(nlg(n)) using the same approach as the one used for problem 1.More exactly we can keep 2 balanced binary trees one for the odd seqences and one for the even sequences.
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Numeric Sequences
« Reply #16 on: Dec 2nd, 2003, 11:14am » |
Quote Modify
|
why the need to sort you simply take the sequence as it is and keep building an AVL tree and as we go on building the AVL tree we can keep filling the len and pre fields inside the node. In this entire algo, since we at the max only traverse the depth of the tree and that too n times, it gives an efficiency of O(nlgn)
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Numeric Sequences
« Reply #17 on: Dec 3rd, 2003, 6:41am » |
Quote Modify
|
Everybody (TenaliRaman, DH, tseuG and Hello) hi, I see that many suggestions and comments were posted: Quote:tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: The crux of part 1 is to find the largest element which is smaller... |
| This isn't absolutly correct since actually we do not care if it is the "largest element which is smaller", we're just looking for some element that is smaller and has the property that the longest sequence is behind it. Quote:tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: insert(item, tree){...} |
| tseuG, to be honest I do not understand how this works ... If you could state the invariant that this tree satisfies it would help. Quote:Hello wrote: Hello wrote: Hello wrote: Hello wrote: Hello wrote: Hello wrote: Hello wrote: Hello wrote: Hello wrote: Hello wrote: Hello wrote: Hello wrote: Hello wrote: Hello wrote: Code:... |
| I've looked at your code and it seems to be correct (). However, it is much more complicated then TenaliRaman's code (e.g. you calculate the maximal length in a backward fashion ), moreover, the printing is done in a less efficient way (i.e. it takes you O(n2) while in TenaliRaman's code it would take only O(n) since he uses somekind of a "back-pointers" array). More comments will follow later...
|
« Last Edit: Dec 3rd, 2003, 6:41am by Dudidu » |
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Numeric Sequences
« Reply #18 on: Dec 3rd, 2003, 7:22am » |
Quote Modify
|
Everybody (TenaliRaman, DH, tseuG and Hello) hi again, Quote:DH wrote: DH wrote: DH wrote: DH wrote: DH wrote: DH wrote: DH wrote: DH wrote: DH wrote: DH wrote: DH wrote: DH wrote: DH wrote: DH wrote: we can sort the numbers (O(nlg(n)))... |
| As TenaliRaman already asked - why should we sort the numbers / How this helps ? Quote:TenaliRaman wrote: TenaliRaman wrote: TenaliRaman wrote: TenaliRaman wrote: TenaliRaman wrote: TenaliRaman wrote: TenaliRaman wrote: TenaliRaman wrote: TenaliRaman wrote: TenaliRaman wrote: TenaliRaman wrote: TenaliRaman wrote: TenaliRaman wrote: TenaliRaman wrote: keep building an AVL tree and as we go on building the AVL tree we can keep filling the len and pre fields inside the node. |
| Quote:Hello wrote: Hello wrote: Hello wrote: Hello wrote: Hello wrote: Hello wrote: Hello wrote: Hello wrote: Hello wrote: Hello wrote: Hello wrote: Hello wrote: Hello wrote: Hello wrote: we could use a balanced tree of nodes... |
| Quote:DH wrote: DH wrote: DH wrote: DH wrote: DH wrote: DH wrote: DH wrote: DH wrote: DH wrote: DH wrote: DH wrote: DH wrote: DH wrote: DH wrote: a balanced binary tree where any given subtree is represented as a contiguous region of the sorted array... |
| Quote:tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: tseuG wrote: augment a balanced BST... |
| O.K, we know that we need to use somekind of a balanced tree (e.g AVL, reb-black, 2-3...) to get the desired O(nlog(n)) complexity. So my question to everybody (that suggests a solution in this form) is assuming that you have a tree (of your choice) that hold k elements and you insert a new element - how do you calculate the longest (monotonically...) sequence that ends with this element (e.g. the "len" of the element) ? Quote:DH wrote: DH wrote: DH wrote: DH wrote: DH wrote: DH wrote: DH wrote: DH wrote: DH wrote: DH wrote: DH wrote: DH wrote: DH wrote: DH wrote: For the bi-monotone case the algorithm must compute the longest odd sequence and the longest even sequence that end with a given element... |
| Sorry, but I don't see the point (how this produces the desired sequence) . Moreover, what do you mean by "longest odd/even sequence" - do you mean a subsequence that has a odd/even number of elements or a sequence that "uses" only numbers from odd/even places at the original sequence or etc... ? Waiting for your answers...
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Numeric Sequences
« Reply #19 on: Dec 3rd, 2003, 8:40am » |
Quote Modify
|
its pretty easy (i think!) consider the nodes to have the following fields, struct node { struct node *left; struct node *right; struct node *pre; int len; } now consider my last algo, we have an if loop which executes on seq[i]>seq[j]. Which means that the len and pre fields are updated when seq[i]>seq[j]. Hence during creation of the tree, we would be updating the len and pre fields of the nodes of the tree only when we are moving right(moving to the right means the current insertion node value is greater than the node through which we are moving right). All this thing would be done during insertion and hence in O(nlgn) time. now we have to search the node with max len field and follow the pre pointers. (i think this works, but i might very well be wrong. So all criticism are welcomed)
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
DH
Newbie
Gender:
Posts: 19
|
|
Re: Numeric Sequences
« Reply #20 on: Dec 3rd, 2003, 8:46am » |
Quote Modify
|
so many replies and so little time IMHO an AVL tree is so much more complicated ( and thus slower to code and debug ) than sorting the numbers and using divide et impera to build a balanced search tree. Quote: O.K, we know that we need to use somekind of a balanced tree (e.g AVL, reb-black, 2-3...) to get the desired O(nlog(n)) complexity. So my question to everybody (that suggests a solution in this form) is assuming that you have a tree (of your choice) that hold k elements and you insert a new element - how do you calculate the longest (monotonically...) sequence that ends with this element (e.g. the "len" of the element) ? |
| For each node we must compute the length of longest monotonical sequence ending with a node from the respective subtree. When inserting a new element into the balanced search tree we will travel a certain path. If the number that is inserted is greater than the current node in the path then compare the current maximum length ( for the number that is inserted ) with the maximum length from the left subtree ( the one that holds numbers smaller than the current node in the path ) and update the maximum length for the inserted number if necessary ( sorry for the poor wording ). At the end of the path we get the maximum length of a monotonical sequence ending with the current number.We use this length to update the tree. Quote: Sorry, but I don't see the point (how this produces the desired sequence) . Moreover, what do you mean by "longest odd/even sequence" - do you mean a subsequence that has a odd/even number of elements or a sequence that "uses" only numbers from odd/even places at the original sequence or etc... ? |
| By odd and even I am referring to the length of the sequence. The point is that if we split the sequences into odd and even when computing them we know what is the relation between the last 2 numbers ( < or > ).
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Numeric Sequences
« Reply #21 on: Dec 3rd, 2003, 9:27am » |
Quote Modify
|
on Dec 3rd, 2003, 8:40am, TenaliRaman wrote:consider the nodes to have the following fields... now consider my last algo, we have an if loop which executes on seq[i]>seq[j]...we would be updating the len and pre fields of the nodes of the tree only when we are moving right... |
| TenaliRaman hi, It seems that your answer is correct ! (I'm assuming that you meant that the node struct has a value field, the right moves will be calculated based on this value and the len is based on (i.e. maximum of) all the left children of the nodes in the path to the inserted elements tree position (although you didn't write this explicitly )). Tuck into the (2)nd problem (since it hasn't been answered yet) !
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Numeric Sequences
« Reply #22 on: Dec 3rd, 2003, 9:42am » |
Quote Modify
|
on Dec 3rd, 2003, 8:46am, DH wrote:When inserting a new element into the balanced search tree we will travel a certain path. If the number that is inserted is greater than the current node in the path then compare the current maximum length ( for the number that is inserted ) with the maximum length from the left subtree ( the one that holds numbers smaller than the current node in the path ) and update the maximum length for the inserted number if necessary. |
| DH, your answer is also correct ! well done ! Quote:...if we split the sequences into odd and even when computing them we know what is the relation between the last 2 numbers ( < or > )... |
| I still don't see how does it help us to get the longest bi-monotone sequence ? Nevertheless leave it ! the next hint will change the prospective of everyone about this problem (hint: I'm looking for an algorithm that is better then [smiley=subo.gif](n log(n))).
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Numeric Sequences
« Reply #23 on: Dec 3rd, 2003, 10:55am » |
Quote Modify
|
I had an algo on (2) but it was O(n) and that scared me and made me think that it is wrong but your last hint has put faith in me so i am putting it here. :: consider the sequence, a[1],a[2],a[3],.......................a[n] WLOG, assume that, a[1],...,a[p] is continuously increasing sequence a[p],...,a[q] is continuously decreasing sequence a[q],...,a[r] is continuously increasing sequence and so on ... i.e the sequence has alternating increasing and decreasing sequence (note that these increasing and decreasing sequences could very well be of length '1' only) then the longest bi-monotone sequence that we are looking for would be a[p],a[q],a[r],...... this sequence can easily be achieved by a linear scan. for example, consider the sequence 4,5,3,2,6,7 4,5 (increasing sequence) gives 5 5,3,2 (decreasing sequence) gives 2 2,6,7 (increasing sequence) gives 7 so the longest bi-monotone sequence we are looking for is 5,2,7. another example, 5,4,2,3,7,6 5 (increasing sequence) gives 5 5,4,2 (decreasing sequence) gives 2 2,3,7 (increasing sequence) gives 7 7,6 (decreasing sequence) gives 6 so the longest bi-monotone sequence is 5,2,7,6 another (quite interesting) example, 5,4,6,3,7,2 5 (increasing sequence) gives 5 5,4 (decreasing sequence) gives 4 4,6 (increasing sequence) gives 6 6,3 (decreasing sequence) gives 3 3,7 (increasing sequence) gives 7 7,2 (decreasing sequence) gives 2 so the longest bi-monotone sequence is 5,4,6,3,7,2 :: i could very well be wrong if so please do point them out.
|
« Last Edit: Dec 3rd, 2003, 11:19am by TenaliRaman » |
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Hello
Guest
|
on Dec 3rd, 2003, 6:41am, Dudidu wrote:I've looked at your code and it seems to be correct (). However, it is much more complicated then TenaliRaman's code (e.g. you calculate the maximal length in a backward fashion ), moreover, the printing is done in a less efficient way (i.e. it takes you O(n2) while in TenaliRaman's code it would take only O(n) since he uses somekind of a "back-pointers" array). |
| You are incorrect here, printing takes O(n). on Dec 3rd, 2003, 11:14am, TenaliRaman wrote:I had an algo on (2) but it was O(n) and that scared me and made me think that it is wrong but your last hint has put faith in me so i am putting it here. |
| It seems to me you nailed it, sir. Very nice.
|
|
IP Logged |
|
|
|
|