wu :: forums
« wu :: forums - find the sequence »

Welcome, Guest. Please Login or Register.
Oct 31st, 2024, 3:45pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: Grimbal, Icarus, william wu, towr, SMQ, Eigenray, ThudnBlunder)
   find the sequence
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: find the sequence  (Read 3859 times)
Sam
Newbie
*





   


Posts: 30
find the sequence  
« on: Sep 19th, 2005, 4:09am »
Quote Quote Modify Modify


 
Given any arbitrary array of size n containing random no.s .How will u find the longest monotonically increasing sequence . A monotonically sequence is one which may not  
be contiguous and can contain any arbitrary increasing seq.
 
e.g if the array is  
 
4,1,5,7,8,3,4,5,1,6,-2
 
The longest monotonically increasing seq. is 1,3,4,5,6
Give the optimized  solution.
IP Logged
Neelesh
Junior Member
**





   


Gender: male
Posts: 147
Re: find the sequence  
« Reply #1 on: Sep 19th, 2005, 4:28am »
Quote Quote Modify Modify

The longest monotonically increasing subsequence can be obtained by dynamic programming. solution is essentially same as the solution of LCS : In this case we sort the original sequence and find LCS of the two (original and sorted)
Order : n2
Refer CLR for  the exact algorithm. Another post on the same forum discusses LCS.
 
HOWEVER -
CLR also mentions that there is an O(n log n) algo to find longest monotonically increasing subsequence. (CLRS Edition 2, Problem 15.4-6)  
 
 
I donot know how.
 
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: find the sequence  
« Reply #2 on: Sep 19th, 2005, 4:29am »
Quote Quote Modify Modify

The easiest approach (or at least the first one that comes to mind) would be dynamic programming; O(n2) I think
 
Do you want strictly increasing? (Not that it makes a very big difference).
« Last Edit: Sep 19th, 2005, 4:33am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Re: find the sequence  
« Reply #3 on: Sep 19th, 2005, 9:06am »
Quote Quote Modify Modify

on Sep 19th, 2005, 4:28am, Neelesh wrote:
CLR also mentions that there is an O(n log n) algo to find longest monotonically increasing subsequence. (CLRS Edition 2, Problem 15.4-6)  

 
The O(nlogn) algorithm works as follows:
 
Let the array be A[1...n] i.e elements are A[1], A[2], .. , A[n], assume all are distinct.  
 
(If they are not distinct we just consider the number to be the ordered pair (A[j],j) and do a lexicographic comparison)
 
Idea is to maintain for each k, the smallest element  A[ik] such that the maximum length monotone subsequence that ends at A[ik] is of length k.
 
We can show A[ik] < A[ik+1]
 
Assume A[ik] >  A[ik+1]
if ik+1 < ik then we have a sequence of length k+1 ending at A[ik]
 
So assume ik+1 > ik
Let p1, ..., pk+1 = A[ik+1] be a sequence of length k+1 ending at A[ik+1]. Consider pk. Clearly the max length subsequence ending at pk is k. Also pk < A[ik+1] < A[ik] which contradicts that A[ik] is the smallest element which ends a max length k subsequence.
 
Thus A[ik] < A[ik+1]
 
Assume that we have maintained i1, i2, ... , im for the array A[1], A[2]..., A[n-1].
 
Consider adding A[n].
 
Find out where A[n] lies in the (sorted list) A[i1], A[i2], ... , A[im]  
 
If A[it+1] > A[n] > A[it] set it+1 = n.
 
If A[n] > A[im] set im+1 = n
 
If A[n] < A[i1] set i1 = n
 
 
Note that we can maintain the ik's (and A[ik]'s) using a balanced binary tree, which gives an O(nlogn) algorithm if we start at A[1] and starting adding elements A[2], A[3] etc..
 
(insertion in balanced binary tree is O(logn), we insert at max n elements)
IP Logged
Sam
Newbie
*





   


Posts: 30
Re: find the sequence  
« Reply #4 on: Sep 19th, 2005, 9:11pm »
Quote Quote Modify Modify

Hi Aryabhatt,
 
Can u explain your sol. with an  example .
IP Logged
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Re: find the sequence  
« Reply #5 on: Sep 21st, 2005, 12:56pm »
Quote Quote Modify Modify

ok let us consider
 
1 8 2 7 3 6 4 5
 
Longest increasing is 1 2 3 4 5.
 
Start off with A[1] = 1.
For this array we get i1 = 1.
 
Now add A[2] to the list
since A[2] > A[i1]  
we get i2 = 2.
 
So the tree now contains 1 and 8.
Not we try to insert 2 into the tree.
 
2 lies between 1 and 8.
so we set i2 = 3.
The tree now has 1, 2.
Now we insert. A[4] = 7.
Since 7 > 2  
we set i3 = 7.
 
Tree now has 1, 2, 7.
We insert A[5] = 3.
Since 2 < 3 < 7
we set i3 = 5
Tree now has 1, 2, 3
 
Now insert A[6] = 6.
 
since 6 > 3.
we set i4 = 6
 
Tree now has 1,2,3,6.
 
Now insert A[7] = 4.
since 3 < 4 < 6
we set i4 = 7
 
Tree now is 1,2,3,4.
 
When we insert A[8] = 5.
we set i5 = 8.
 
The final tree now has 1,2,3,4,5.
 
Note that in this case walking the tree gave you the right sequence, but that need not be true for all sequences. The algorithm I gave gives the length of the longest sequence, you will have to modify it to get the exact sequence.
IP Logged
ji ryang chung
Guest

Email

Re: find the sequence  
« Reply #6 on: Oct 2nd, 2005, 8:18pm »
Quote Quote Modify Modify Remove Remove

What if A = {3, 6, 1}?
 
Isn't that like follows?
 
     initially, i1 = 1, A[i1] = 3
     A[2] = 6 > A[i1]   => i2 = 2
     A[3] = 1 < A[i1](= 3)   => i1 = 3Huh
 
I think the answer should be {3, 6}, right?
IP Logged
ji ryang chung
Guest

Email

Re: find the sequence  
« Reply #7 on: Oct 2nd, 2005, 8:30pm »
Quote Quote Modify Modify Remove Remove

I got it. Never mind the previous posting.
What we need is the longest subsequence, so tracking back the A[i] with the largest subscript will do.
Thanks for your tip, Aryabhatta!
IP Logged
dav
Newbie
*





   


Gender: male
Posts: 47
Re: find the sequence  
« Reply #8 on: Dec 7th, 2005, 2:39am »
Quote Quote Modify Modify

Hi  Guys,
     Could you guys please help me in solving this problem
 
   Iam trying to solve using dynamic programming.
 
a[] = {8,1,7,5,6}
b[]={1,5,6,7,8}
 
 
Assume there is  array which stores the values:-  D[m+1][n+1]
 
for i : 1 to m do
D[i][0] = 0
 
for i : 1 to n do
D[0][j] = 0
 
for i : 1 to m do
for j: 1 to n do  
 
if(a[i] < b[j])  
{
   ----
}
else
{
  ----
}
   
Please any body help me in doing this.
IP Logged
dav
Newbie
*





   


Gender: male
Posts: 47
Re: find the sequence  
« Reply #9 on: Dec 7th, 2005, 2:51am »
Quote Quote Modify Modify

Hi Aryabhatt,  
 
What if A ={8,1,7,5,6}
IP Logged
dav
Newbie
*





   


Gender: male
Posts: 47
Re: find the sequence  
« Reply #10 on: Dec 7th, 2005, 11:54pm »
Quote Quote Modify Modify

Hi Guys,
     I got the solution it same as LCS.  Previously iam trying to do comparing the elements using "<". Now i got the solution
IP Logged
Ved
Junior Member
**





   


Gender: male
Posts: 53
Re: find the sequence  
« Reply #11 on: Dec 9th, 2011, 9:48pm »
Quote Quote Modify Modify

Since 7 > 2  
we set i3 = 7.  
should be
Since 7 > 2  
we set i3 = 4.  
on Sep 21st, 2005, 12:56pm, Aryabhatta wrote:
ok let us consider
 
1 8 2 7 3 6 4 5
 
Longest increasing is 1 2 3 4 5.
 
Start off with A[1] = 1.
For this array we get i1 = 1.
 
Now add A[2] to the list
since A[2] > A[i1]  
we get i2 = 2.
 
So the tree now contains 1 and 8.
Not we try to insert 2 into the tree.
 
2 lies between 1 and 8.
so we set i2 = 3.
The tree now has 1, 2.
Now we insert. A[4] = 7.
Since 7 > 2  
we set i3 = 7.
 
Tree now has 1, 2, 7.
We insert A[5] = 3.
Since 2 < 3 < 7
we set i3 = 5
Tree now has 1, 2, 3
 
Now insert A[6] = 6.
 
since 6 > 3.
we set i4 = 6
 
Tree now has 1,2,3,6.
 
Now insert A[7] = 4.
since 3 < 4 < 6
we set i4 = 7
 
Tree now is 1,2,3,4.
 
When we insert A[8] = 5.
we set i5 = 8.
 
The final tree now has 1,2,3,4,5.
 
Note that in this case walking the tree gave you the right sequence, but that need not be true for all sequences. The algorithm I gave gives the length of the longest sequence, you will have to modify it to get the exact sequence.

IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

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