exactly ! But the point is.... Though i did it in o(n), still the constant will be too high to use.(practically the bst solution will work better for n<10^20
So can we do better?? On 4/14/10, Dave <[email protected]> wrote: > Sure, we can build a heap. But what's the point. Already, an O(n) > solution has been identified, using the median of medians algorithm. A > heap would be O(n ln k). > > Dave > > On Apr 14, 4:25 am, Ashish Mishra <[email protected]> wrote: >> can't we build a min-heap (kinda opposite of max-heap) ?? >> >> On Wed, Apr 14, 2010 at 8:42 AM, Rohit Saraf >> <[email protected]>wrote: >> >> >> >> > Not linear in worst case >> >> > On 4/13/10, souri datta <[email protected]> wrote: >> > > what about the algorithm which mimics the Quick Sort and deals with >> > > only >> > one >> > > partition( as in Coremen) ? >> >> > > On Tue, Apr 13, 2010 at 9:11 AM, Rohit Saraf < >> > [email protected]> >> > > wrote: >> >> > >> So tell me something else which works in O(n) >> >> > >> On 4/12/10, souri datta <[email protected]> wrote: >> > >> > Why only median of median? >> >> > >> > On Mon, Apr 12, 2010 at 7:51 PM, Rohit Saraf >> > >> > <[email protected]> >> > >> > wrote: >> >> > >> >> Find the kth element using order statistics - O(n) <> As far as >> > >> >> i >> > >> >> know , >> > >> >> u will have to use median of medians selection algorithm for >> > >> >> this... >> > >> >> Rest is fine.. >> >> > >> >> -------------------------------------------------- >> > >> >> Rohit Saraf >> > >> >> Second Year Undergraduate, >> > >> >> Dept. of Computer Science and Engineering >> > >> >> IIT Bombay >> > >> >>http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >> >> > >> >> On Mon, Apr 12, 2010 at 3:20 PM, souri datta < >> > [email protected]> >> > >> >> wrote: >> >> > >> >>> Steps: >> > >> >>> 1. Find the kth element using order statistics - O(n) >> > >> >>> 2. In one pass over the array, get all the elems less than the >> > >> >>> kth >> > >> >>> element. >> >> > >> >>> Let me know if this is not correct. >> >> > >> >>> On Mon, Apr 12, 2010 at 1:57 PM, Rohit Saraf >> > >> >>> <[email protected]> wrote: >> >> > >> >>>> I have already given an O(n) solution. See above ! >> >> > >> >>>> The BST solution is O(nlogn) but is practically more nice. :) >> >> > >> >>>> -------------------------------------------------- >> > >> >>>> Rohit Saraf >> > >> >>>> Second Year Undergraduate, >> > >> >>>> Dept. of Computer Science and Engineering >> > >> >>>> IIT Bombay >> > >> >>>>http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >> >> > >> >>>> On Mon, Apr 12, 2010 at 1:16 PM, Nikhil Agarwal >> > >> >>>> <[email protected]> wrote: >> >> > >> >>>>> On Mon, Apr 12, 2010 at 12:58 PM, Rohit Saraf >> > >> >>>>> <[email protected]> wrote: >> >> > >> >>>>>> are yaar... i meant BST... i thought that was obvious ! >> > >> >>>>>> sry if i confused you.... >> >> > >> >>>>> @rohit It's ok.Actually in this group people come up with very >> > >> >>>>> different and non-common solutions so its risky to take things >> > >> >>>>> 'obviously'. >> > >> >>>>> Rotation algo has a complexity of O(nlogn)[for constructing a >> > >> >>>>> BST] >> > >> >>>>> +O(n) [for rotating n times]=O(nlogn) . >> >> > >> >>>>> Till now best algo we have is using heaps which give rise to >> > >> >>>>> complexity >> > >> >>>>> = O(n+klogn) >> >> > >> >>>>> Please pass on algos having better runtime complexity. >> >> > >> >>>>>> -------------------------------------------------- >> > >> >>>>>> Rohit Saraf >> > >> >>>>>> Second Year Undergraduate, >> > >> >>>>>> Dept. of Computer Science and Engineering >> > >> >>>>>> IIT Bombay >> > >> >>>>>>http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >> >> > >> >>>>>> On Mon, Apr 12, 2010 at 12:38 PM, Nikhil Agarwal >> > >> >>>>>> <[email protected]> wrote: >> >> > >> >>>>>>> Hey rohit.You were referring to Binary tree.Search keyword >> > >> >>>>>>> was >> > >> >>>>>>> missing.Because rotation makes no sense in binary tree.Please >> > note >> > >> >>>>>>> binary tree and BST are different. >> >> > >> >>>>>>> On Mon, Apr 12, 2010 at 12:33 PM, Rohit Saraf >> > >> >>>>>>> <[email protected]> wrote: >> >> > >> >>>>>>>> Read the slides i uploaded. They explain what rotation does >> > >> >>>>>>>> in >> > a >> > >> >>>>>>>> BST. >> >> > >> >>>>>>>> Also you might like to refer to Red Black Trees in CLRS.... >> > that >> > >> >>>>>>>> chapter explains rotations. >> >> > >> >>>>>>>> -------------------------------------------------- >> > >> >>>>>>>> Rohit Saraf >> > >> >>>>>>>> Second Year Undergraduate, >> > >> >>>>>>>> Dept. of Computer Science and Engineering >> > >> >>>>>>>> IIT Bombay >> > >> >>>>>>>>http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >> >> > >> >>>>>>>> On Mon, Apr 12, 2010 at 8:18 AM, Rohit Saraf >> > >> >>>>>>>> <[email protected]> wrote: >> >> > >> >>>>>>>>> but still the binary tree solution is of more practical >> > >> >>>>>>>>> use.i >> > >> >>>>>>>>> will >> > >> >>>>>>>>> explain the solution once i reach my comp >> >> > >> >>>>>>>>> On 4/11/10, Nikhil Agarwal <[email protected]> >> > >> >>>>>>>>> wrote: >> >> > >> >>>>>>>>> > On Sun, Apr 11, 2010 at 9:56 PM, Rohit Saraf >> > >> >>>>>>>>> > <[email protected]> >> > >> >>>>>>>>> > wrote: >> >> > >> >>>>>>>>> >> Time complexity is O(n log n). But the last solution I >> > >> >>>>>>>>> >> gave >> > >> >>>>>>>>> >> has >> > >> >>>>>>>>> >> O(n). >> >> > >> >>>>>>>>> >> What did u not understand abt thesolution >> >> > >> >>>>>>>>> > @Rohit Please explain how that Binary tree solution >> > >> >>>>>>>>> > works. >> >> > >> >>>>>>>>> >> -------------------------------------------------- >> > >> >>>>>>>>> >> Rohit Saraf >> > >> >>>>>>>>> >> Second Year Undergraduate, >> > >> >>>>>>>>> >> Dept. of Computer Science and Engineering >> > >> >>>>>>>>> >> IIT Bombay >> > >> >>>>>>>>> >>http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >> >> > >> >>>>>>>>> >> On Sun, Apr 11, 2010 at 11:00 AM, Priyanka Chatterjee >> > >> >>>>>>>>> >> <[email protected]> wrote: >> >> > >> >>>>>>>>> >>> On 11 April 2010 10:46, Rohit Saraf >> > >> >>>>>>>>> >>> <[email protected]> wrote: >> >> > >> >>>>>>>>> >>>> Construct a binary tree from the data (maintain the >> > >> >>>>>>>>> >>>> size >> > of >> > >> >>>>>>>>> >>>> subtree >> > >> >>>>>>>>> >>>> under each node). >> > >> >>>>>>>>> >>>> Do rotations till the left subtree does not have size >> > >> >>>>>>>>> >>>> k. >> > >> >>>>>>>>> >>>> Rotation is a >> > >> >>>>>>>>> >>>> constant time operation. >> > >> >>>>>>>>> >>>> Please prove the correctness of your algorithm with >> > >> >>>>>>>>> >>>> the >> > >> >>>>>>>>> >>>> time >> > >> >>>>>>>>> >>>> complexity >> >> > >> >>>>>>>>> >>>> -------------------------------------------------- >> > >> >>>>>>>>> >>>> Rohit Saraf >> > >> >>>>>>>>> >>>> Second Year Undergraduate, >> > >> >>>>>>>>> >>>> Dept. of Computer Science and Engineering >> > >> >>>>>>>>> >>>> IIT Bombay >> > >> >>>>>>>>> >>>>http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >> >> > >> >>>>>>>>> >>>> On Mon, Mar 29, 2010 at 11:15 AM, blackDiamond >> > >> >>>>>>>>> >>>> <[email protected]> >> > >> >>>>>>>>> >>>> wrote: >> >> > >> >>>>>>>>> >>>>> nice solution appreciate it. but your algorithm is >> > wasting >> > >> >>>>>>>>> >>>>> time in >> > >> >>>>>>>>> >>>>> finding all the element... >> > >> >>>>>>>>> >>>>> instead of that just find boundary line kth element >> > which >> > >> >>>>>>>>> >>>>> can >> > >> >>>>>>>>> >>>>> help as >> > >> >>>>>>>>> >>>>> in finding element greater that kth and element small >> > than >> > >> >>>>>>>>> >>>>> kth and that >> > >> >>>>>>>>> >>>>> soluton can be done in O(N) >> >> > >> >>>>>>>>> >>>>> On Sun, Mar 28, 2010 at 10:02 PM, CHERUVU JAANU REDDY >> > >> >>>>>>>>> >>>>> <[email protected]> wrote: >> >> > >> >>>>>>>>> >>>>>> 1) Construct max heap by taking first k elements in >> > >> >>>>>>>>> >>>>>> an >> > >> >>>>>>>>> >>>>>> array >> > >> >>>>>>>>> >>>>>> 2) if k+1 element less than root of max heap >> > >> >>>>>>>>> >>>>>> a) Delete root of max heap >> > >> >>>>>>>>> >>>>>> b) Insert k+1 element in max heap and apply >> > >> >>>>>>>>> >>>>>> heapify >> > >> >>>>>>>>> >>>>>> method >> > >> >>>>>>>>> >>>>>> 3) else skip the element >> > >> >>>>>>>>> >>>>>> 4) apply above procedure for all n elements in an >> > >> >>>>>>>>> >>>>>> array >> >> > >> >>>>>>>>> >>>>>> At last you will get k smallest elements and root is >> > kth >> > >> >>>>>>>>> >>>>>> smallest >> > >> >>>>>>>>> >>>>>> element in the array >> >> > >> >>>>>>>>> >>>>>> this is O(nlogk) >> >> > >> >>>>>>>>> >>>>>> ---------------------------------------- >> > >> >>>>>>>>> >>>>>> CHERUVU JAANU REDDY >> > >> >>>>>>>>> >>>>>> M.Tech in CSIS >> >> > >> >>>>>>>>> >>>>>> On Sun, Mar 28, 2010 at 8:41 PM, abhijith reddy >> > >> >>>>>>>>> >>>>>> <[email protected]> wrote: >> >> > >> >>>>>>>>> >>>>>>> Can any one tell how to do this when there are 'm' >> > >> >>>>>>>>> >>>>>>> queries >> > >> >>>>>>>>> >>>>>>> like >> > >> >>>>>>>>> >>>>>>> "query i j k" find the kth largest element in >> > >> >>>>>>>>> >>>>>>> between >> > >> >>>>>>>>> >>>>>>> indices i->j in >> > >> >>>>>>>>> >>>>>>> an array. >> > >> >>>>>>>>> >>>>>>> When m is large even an O(n) algorithm would be >> > >> >>>>>>>>> >>>>>>> slow. >> > >> >>>>>>>>> >>>>>>> I thinking that each query could be answered in >> > >> >>>>>>>>> >>>>>>> O(sqrt(n)) >> > >> >>>>>>>>> >>>>>>> time >> > >> >>>>>>>>> >>>>>>> So any suggestions ? >> >> > >> >>>>>>>>> >>>>>>> Thanks >> >> > >> >>>>>>>>> >>>>>>> On Sun, Mar 28, 2010 at 7:57 PM, blackDiamond >> > >> >>>>>>>>> >>>>>>> <[email protected]> >> > >> >>>>>>>>> >>>>>>> wrote: >> >> > >> >>>>>>>>> >>>>>>>> there are better solution of O(n) are posted in >> > >> >>>>>>>>> >>>>>>>> the >> > >> >>>>>>>>> >>>>>>>> thread.......[?]. >> > >> >>>>>>>>> >>>>>>>> using order statices .... >> >> > >> >>>>>>>>> >>>>>>>> On Sun, Mar 28, 2010 at 6:49 PM, Mukesh Kumar >> > >> >>>>>>>>> >>>>>>>> thakur >> > >> >>>>>>>>> >>>>>>>> <[email protected]> wrote: >> >> ... >> >> read more » >> >> 338.gif >> < 1KViewDownload >> >> 361.gif >> < 1KViewDownload- Hide quoted text - >> >> - Show quoted text - > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- -------------------------------------------------- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
