[algogeeks] Re: Can you guys help me how to approach this problem !!!
I kinda need the worst case also to be in nlogn. Any ideas guys ? -- Vinod On Dec 2, 11:02 pm, Geoffrey Summerhayes wrote: > On Dec 2, 10:42 am, Geoffrey Summerhayes wrote: > > > > > It's a binary tree, [ 7 3 4 1 2 6 5 8] has children > > [ 7 3 4 1 2 6 5] and [ 3 4 1 2 6 5 8], all the way > > down to [ 7 3] [3 4] [4 1] ... > > > If you start at the bottom keeping track of min and max > > for each node, if max-min == node length - 1 the node > > if conseq. then it's just a matter of combining node > > together and working up the tree > > Darn! > > Total steps= n*n/2 - n/2 > > Anybody have a math trick? > > -- > Geoff -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Can you guys help me how to approach this problem !!!
On Dec 2, 10:42 am, Geoffrey Summerhayes wrote: > > It's a binary tree, [ 7 3 4 1 2 6 5 8] has children > [ 7 3 4 1 2 6 5] and [ 3 4 1 2 6 5 8], all the way > down to [ 7 3] [3 4] [4 1] ... > > If you start at the bottom keeping track of min and max > for each node, if max-min == node length - 1 the node > if conseq. then it's just a matter of combining node > together and working up the tree Darn! Total steps= n*n/2 - n/2 Anybody have a math trick? -- Geoff -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Can you guys help me how to approach this problem !!!
On Dec 2, 6:45 am, Vinoth Kumar wrote: > These are the steps for the O(n^2) solution > > n=length of A > for each subarray A[i,j] where j>i > min=min(A[i,j]) > max=max(A[i,j]) > if(max - min==size (A[i,j]) print A[i,j] > > min[A[i,j]]=min( A[j], min(A[i,j-1]) > similar one for max > > Note: > A[i,j] = A[i],A[i+1]A[j] > > I was wondering how to do the same problem in O(nlogn) > It's a binary tree, [ 7 3 4 1 2 6 5 8] has children [ 7 3 4 1 2 6 5] and [ 3 4 1 2 6 5 8], all the way down to [ 7 3] [3 4] [4 1] ... If you start at the bottom keeping track of min and max for each node, if max-min == node length - 1 the node if conseq. then it's just a matter of combining node together and working up the tree -- Geoff -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Recaman's sequence
Hi, Well Recaman's sequence is defined by: a(0) = 0 a(k) = a(k-1) - k, k>0, a(k) new term in series or else a(k-1) + k So sequence is 0, 1, 3,6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, My approach used memoization using map in c++ (giving O(n) time and memory for generating sequence), but I somehow feel that there can be a better approach to check if a term already exists in the sequence. Any suggestion would be gratefully acknowledged. Regards, Tushar -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Can you guys help me how to approach this problem !!!
check this if How To Install Dreamweaver CS3 In Ubuntu Hardyhttp://eaziweb.blogspot.com/2009/12/how-to-install-dreamweaver-cs3-in.html Regards Shahzeb Farooq Chohan Software Engineer Cogilent Solutions Get your new Email address! Grab the Email name you've always wanted before someone else does! http://mail.promotions.yahoo.com/newdomains/aa/ -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Can you guys help me how to approach this problem !!!
check this if How To Install Dreamweaver CS3 In Ubuntu Hardyhttp://eaziweb.blogspot.com/2009/12/how-to-install-dreamweaver-cs3-in.html Regards Shahzeb Farooq Chohan Software Engineer Cogilent Solutions Get your new Email address! Grab the Email name you've always wanted before someone else does! http://mail.promotions.yahoo.com/newdomains/aa/ -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Can you guys help me how to approach this problem !!!
These are the steps for the O(n^2) solution n=length of A for each subarray A[i,j] where j>i min=min(A[i,j]) max=max(A[i,j]) if(max - min==size (A[i,j]) print A[i,j] min[A[i,j]]=min( A[j], min(A[i,j-1]) similar one for max Note: A[i,j] = A[i],A[i+1]A[j] I was wondering how to do the same problem in O(nlogn) -- Vinod On Wed, Dec 2, 2009 at 11:48 AM, ranjmis wrote: > Vinod. Can you please mention steps for the O(n^2) solution that you > have thought of. > > On Dec 2, 9:50 am, Vinoth Kumar wrote: > > No need for the code guys. > > Can u give me a algo or pseudo code for this problem. > > I can think of a soln of O(n^2) but i need a algo for O(nlogn) > > > > > > > > On Wed, Dec 2, 2009 at 2:06 AM, NickLarsen wrote: > > > That doesn't quite get it, try the input [ 7 3 4 2 1 6 5 8] and your > > > idea would miss [3 4 2] > > > > > On Dec 1, 10:10 am, sharad kumar wrote: > > > > find out the subseq which are consecttive > > > > concatenate them at each level to get the entire set. > > > > > > On Tue, Dec 1, 2009 at 12:03 PM, Vinoth Kumar > > > > wrote: > > > > > > > Given an array A which holds a permutation of 1,2,...,n. A > sub-block A > > > > > [i..j] of an array A > > > > > is called a valid block if all the numbers appearing in A[i..j] are > > > > > consecutive numbers (may not be in order. > > > > > > > Given an array A= [ 7 3 4 1 2 6 5 8] > > > > > the valid blocks are [3 4], [1,2], [6,5], [3 4 1 2], [3 4 1 2 6 5], > [7 > > > > > 3 4 1 2 6 5], [7 3 4 1 2 6 5 8] > > > > > > > Give an O( n log n) algorithm to count the number of valid blocks. > > > > > > > -- Vinod > > > > > > > -- > > > > > > > You received this message because you are subscribed to the Google > > > Groups > > > > > "Algorithm Geeks" group. > > > > > To post to this group, send email to algoge...@googlegroups.com. > > > > > To unsubscribe from this group, send email to > > > > > algogeeks+unsubscr...@googlegroups.com > > > > > > > > > > > . > > > > > For more options, visit this group at > > > > >http://groups.google.com/group/algogeeks?hl=en. > > > > > -- > > > > > You received this message because you are subscribed to the Google > Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to algoge...@googlegroups.com. > > > To unsubscribe from this group, send email to > > > algogeeks+unsubscr...@googlegroups.com > > > > > > . > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en. > > > > -- > > Cheers, > > Vinod > > -- > > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Can you guys help me how to approach this problem !!!
You guy check this solution. It is expected to be run in O(n lg n) for random permutation in average time. For worst case, I think we can improve it for that. Let's do an example firstly. 7 3 4 1 2 6 5 8 For *1*, it self is a block. Let's count the blocks containing *1* firstly. If a block with size more than 1 contains *1*, it will contains *2*. Now check *2*, it is not beside *1*, so no block with size=2 contains *1*. Let's check *3*', the minimum position for (1,2,3) is 1 (with 0 based index), and maximum position for (1,2,3) is 4. Because 4-1+1 = 4>3, no block with sizeo=3 contains *1*. Let's check *4*, the minimum position for (1,2,3,4) is 1, and maximum position is 4. The window size is 4-1+1 = 4. We find a block with size=4 and it contains *1*. By continuing this process, we will get the number of blocks containing number *1* and more important is the time we need is linear time: O(n). Now, we have checked all blocks including number *1*. So from now on, we do not need number *1* anymore. It means we can split the list into two [7 3 4] and [2 6 5 8] and repeat the above process again & again. If the permutation is really random, the above process is very similar as the QuickSort process and then we know the whole process cost O(n lg n) time. However, for worst case like [1 2 3 4 ... n], it performs very bad. The time complexity is linear with the number of blocks and so it is not good in worst case. I.e. the above algorithm need O(n^2) time for such worst case. Hope other guys can solve the worst case in O(n lg n) time. Thanks On Tue, Dec 1, 2009 at 2:33 PM, Vinoth Kumar wrote: > Given an array A which holds a permutation of 1,2,...,n. A sub-block A > [i..j] of an array A > is called a valid block if all the numbers appearing in A[i..j] are > consecutive numbers (may not be in order. > > Given an array A= [ 7 3 4 1 2 6 5 8] > the valid blocks are [3 4], [1,2], [6,5], [3 4 1 2], [3 4 1 2 6 5], [7 > 3 4 1 2 6 5], [7 3 4 1 2 6 5 8] > > Give an O( n log n) algorithm to count the number of valid blocks. > > > -- Vinod > > -- > > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Question with Dijkstra algorithm
Hi. I have implement Dijktsras algo too find shortest path in directed weighted graph with positive edge weights. Now trying to implement A* using a heuristic that is related to geometric distance. In my book it says to implement A* in same way as Dijkstra except for changing the edge cost function in following way: if c : E ---> positive numbers is original cost function from edges to positive numbers and f : V --- > positive numbers is an estimate of distance from nodes in graph to the goal node then run Dijkstra with the following cost function new_cost : E ---> positive numbers defined for edge e = (a,b) as new_cost(e) = c(e) + f(b) - f(a). Now if f is admissiable and is always lower bound for true cost then this should work, but it dosnt. Do I need to change more ? So sum up: Enough just to run Dijkstra and use new edge-cost when relaxing edges without no other change ? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
