wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Numeric Sequences
        
(Message started by: Dudidu on Nov 27th, 2003, 8:46am)
Title: Numeric Sequences
Post by Dudidu on Nov 27th, 2003, 8:46am
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)).
Title: Re: Numeric Sequences
Post by TenaliRaman on Nov 28th, 2003, 3:05am
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,

::[hide]
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
[/hide]::    

This algo might very well be error prone. I gladly invite all criticism over this algorithm.
Title: Re: Numeric Sequences
Post by DH on Nov 28th, 2003, 5:56am
::[hide]

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 .

[/hide]
Title: Re: Numeric Sequences
Post by TenaliRaman on Nov 28th, 2003, 9:09am
hey pretty neat idea. I think we also need to have pointers in the node to get the subsequence.
Title: Re: Numeric Sequences
Post by Dudidu on Nov 30th, 2003, 2:07am
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 ::))):
[hide]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}).[/hide]:
Overlooking this minor problem, this "dynamic programming" algorithm gets it... :D.

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 ;)...)
Title: Re: Numeric Sequences
Post by tseuG on Nov 30th, 2003, 3:14am
   One more approach:

[hide]
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[/hide]
Title: Re: Numeric Sequences
Post by Dudidu on Nov 30th, 2003, 3:40am
tseuG welcome,

on 11/30/03 at 03:14:26, 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 ?
Title: Re: Numeric Sequences
Post by TenaliRaman on Nov 30th, 2003, 3:42am
Dudidu,
Thanks for pointing that out.
And as you say the modification would be minor ::[hide]we have to remove the flag variable and add one more if statement inside the current if statement.[/hide]
Title: Re: Numeric Sequences
Post by Dudidu on Nov 30th, 2003, 4:10am

on 11/30/03 at 03:42:55, TenaliRaman wrote:
And as you say the modification would be minor...
Right, the loop should follow the following (recursive) formula:
[hide] 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...[/hide]
Title: Re: Numeric Sequences
Post by tseuG on Nov 30th, 2003, 4:21am
   oops! LCS needs O(n2) time. Thanks for pointing it out Dudidu. I have modified my post.
Title: Re: Numeric Sequences
Post by Dudidu on Nov 30th, 2003, 8:30am
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)...
Title: Re: Numeric Sequences
Post by tseuG on Nov 30th, 2003, 2:49pm
   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.
Title: Re: Numeric Sequences
Post by Hello on Dec 1st, 2003, 3:48pm

on 11/28/03 at 03:05:04, 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:
      S[N-1] = 1;

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.
Title: Re: Numeric Sequences
Post by Hello on Dec 1st, 2003, 4:07pm

on 12/01/03 at 15:48:55, 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...
Title: Re: Numeric Sequences
Post by DH on Dec 2nd, 2003, 3:36am

on 11/30/03 at 02:07:34, Dudidu wrote:
DH, We haven't heard from you for a long time...


I don't have very much spare time :(


on 11/30/03 at 02:07:34, 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 ).
Title: Re: Numeric Sequences
Post by DH on Dec 2nd, 2003, 3:54am
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.
Title: Re: Numeric Sequences
Post by TenaliRaman on Dec 2nd, 2003, 11:14am
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)
Title: Re: Numeric Sequences
Post by Dudidu on Dec 3rd, 2003, 6:41am
Everybody (TenaliRaman, DH, tseuG and Hello) hi,
I see that many suggestions and comments were posted:

Quote:
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: 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: 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 :P), 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...
Title: Re: Numeric Sequences
Post by Dudidu on Dec 3rd, 2003, 7:22am
Everybody (TenaliRaman, DH, tseuG and Hello) hi again,


Quote:
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: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: we could use a balanced tree of nodes...

Quote:
DH wrote: a balanced binary tree where any given subtree is represented as a contiguous region of the sorted array...

Quote:
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: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...
Title: Re: Numeric Sequences
Post by TenaliRaman on Dec 3rd, 2003, 8:40am
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)
Title: Re: Numeric Sequences
Post by DH on Dec 3rd, 2003, 8:46am
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 > ).
Title: Re: Numeric Sequences
Post by Dudidu on Dec 3rd, 2003, 9:27am

on 12/03/03 at 08:40:08, 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) !
Title: Re: Numeric Sequences
Post by Dudidu on Dec 3rd, 2003, 9:42am

on 12/03/03 at 08:46:57, 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 ;D ! 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: [hide] I'm looking for an algorithm that is better then [smiley=subo.gif](n log(n))[/hide]).
Title: Re: Numeric Sequences
Post by TenaliRaman on Dec 3rd, 2003, 10:55am
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.

::[hide]
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
[/hide]::

i could very well be wrong if so please do point them out.
Title: Re: Numeric Sequences
Post by Hello on Dec 3rd, 2003, 2:18pm

on 12/03/03 at 06:41:05, 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 :P), 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 12/03/03 at 11:14:05, 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.
Title: Re: Numeric Sequences
Post by Dudidu on Dec 3rd, 2003, 10:45pm

on 12/03/03 at 10:55:04, 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.
TenaliRaman Bravo ;D!
This kind of a greedy algorithm (that chooses the local maximums/minimums) gets it !


Quote:
You are incorrect here, printing takes O(n).
You're right ! (Sorry, I didn't pay enough attention :-[).

P.S. I'm thinking of a "follower", but still unable to find (an appropriate) one - if someone can come up with an idea...
Title: Re: Numeric Sequences
Post by Dudidu on Jan 7th, 2004, 1:38am
After quite a long time (as you can see) I have a "follower":

You are given a sequence of numbers A = a1, a2, a3, ... an.
3) Devise an algorithm to find a sub-sequence S of A such that:
  • the sum of elements in the sub-sequence is minimal.
  • a1 and an are in the sub-sequence.
  • the "distance" between any two consecutive elements in the sub-sequence is [le] 2.
Explaination: we are looking for a sub-sequence ai1, ai2, ... aik such that i1 = 1, ik = n and [forall]1[le]j<k (ij+1 - ij) [le] 2.
Title: Re: Numeric Sequences
Post by DH on Jan 16th, 2004, 7:16am

on 01/07/04 at 01:38:59, Dudidu wrote:
After quite a long time (as you can see) I have a "follower":

You are given a sequence of numbers A = a1, a2, a3, ... an.
3) Devise an algorithm to find a sub-sequence S of A such that:
  • the sum of elements in the sub-sequence is minimal.
  • a1 and an are in the sub-sequence.
  • the "distance" between any two consecutive elements in the sub-sequence is [le] 2.
Explaination: we are looking for a sub-sequence ai1, ai2, ... aik such that i1 = 1, ik = n and [forall]1[le]j<k (ij+1 - ij) [le] 2.


After a long time I finally have some spare time.

::[hide]

Assuming we have a solution for A1 A2 .... AN-2 and also for A1 A2 ... AN-1 we can compute the solution to our problem in O(1) time so the solution can be computed ( "from scratch" )in O(N) time using dynamic programming.

[/hide]
Title: Re: Numeric Sequences
Post by Dudidu on Jan 18th, 2004, 12:42am

on 01/16/04 at 07:16:28, DH wrote:
Assuming we have a solution for ... and also for ... we can compute the solution ... using dynamic programming.
DH welcome again,
Your answer is in the right direction !
But can you please state what is/are the "base solution/s" and how do you calculate the next step (in the dynamic programming) ?
Title: Re: Numeric Sequences
Post by DH on Jan 18th, 2004, 2:39am

on 01/18/04 at 00:42:49, Dudidu wrote:
DH welcome again,
Your answer is in the right direction !
But can you please state what is/are the "base solution/s" and how do you calculate the next step (in the dynamic programming) ?


::
n -> number of numbers in the sequence
v -> the numbers

[hide]
min[0]=v[0];
min[1]=v[0]+v[1];
link[1]=0;

for (i=2;i<n;i++)
{
  if (min[i-1]<min[i-2])
  {
     min[i]=min[i-1]+v[i];
     link[i]=i-1;
  }
  else
  {
     min[i]=min[i-2]+v[i];
     link[i]=i-2;
  }
}

using the link vector we can compute the solution

[/hide]
Title: Re: Numeric Sequences
Post by Dudidu on Jan 18th, 2004, 2:47am

on 01/18/04 at 02:39:31, DH wrote:
...<HIDE>...
Well done, DH :D !
It's correct.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board