Re: [algogeeks] How strong is your quick sort fundamental?
You can compute recursively as below: We use f(n) to represent the number of comparisons which the Quick-Sort algo needs to take running on an array of n elements. Answer to question 1: f(n) = 2 * f(n/2) + n We can observe the following sequence of equations: f(n) = 4 * f(n/4) + 2 * n/2 + n = 4f(n/4)+2n f(n) = 8 * f(n/8) + 4 * n/4 + 2 * n/2 + n = 8f(n/8)+3n f(n) = 16 * f(n/16) + 4n ... So, we induce the final conclusion: f(n) = 2^k * f(n/2^k) + kn, where n/2^k 1 Thus f(n) = O(n*logn) This is really a tight boundary! Answer to question 2: f(n) = f(n/3) + f(2n/3) +n Same as above, we can conclude that: f(n) = O(n*logn) On Wed, Aug 25, 2010 at 11:16 AM, sourav souravs...@gmail.com wrote: The median of a set of n values is the \lceil n/2 \rceilth smallest value. 1. Suppose quicksort always pivoted on the median of the current sub-array. How many comparisons would Quicksort make then in the worst case? 2. Suppose quicksort were always to pivot on the n/3 th smallest value of the current sub-array. How many comparisons would be made then in the worst case? Support your answer giving mathematical proof / approach to your answer. [Note: In case quick sort always partitions the sub-array into 0 and n-1 elements (pivot comes to be first element or last element), then total of n^2 comparisions are done] -- 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] Re: Longest Palindromic Substring
The question would be complete if we know what order of notation is needed for solution. On 23.08.2010 15:32, Chi Hoang wrote: I don't think so, I've have wriiten a kart-trie: http://sourceforge.net/projects/kart-trie which is basically a patricia-tree or radix-tree. Such a tree has maximum 2 leafs at each branch whilst a suffix-tree can has more then 2 leafs at each branch (BTW. can you explain to me what does edge means when talking about trees?). This is my understanding of a suffix-tree so far. I'm awaiting your anwser! 2010/8/21 Chonku cho...@gmail.com mailto:cho...@gmail.com You use a trie when you want to model a number of strings. Suffix Tree is used only when you have one string in your model. Suffix Tree is a type of trie, but the difference lies in the intent. On Sat, Aug 21, 2010 at 7:22 PM, Chi c...@linuxdna.com mailto:c...@linuxdna.com wrote: Isn't that by definition a compressed trie, i.e patricia-tree, crit- bit tree (suffix-tree)? Or what is the difference? On Aug 20, 5:17 pm, Nikhil Jindal fundoon...@yahoo.co.in mailto:fundoon...@yahoo.co.in wrote: @chonku As i understand, a trie is used when we have a lot of strings (such as a dictionary). Here we just have a single string. The resultant trie will be: a \ b \ c \ l \ e \ v \ e \ l \ a \ b \ c We get a similar trie for the reverse string. So why are you using a trie here? I cant see any advantage of it here. On Fri, Aug 20, 2010 at 8:36 AM, Chonku cho...@gmail.com mailto:cho...@gmail.com wrote: Can we use a trie here. Make first pass from left to right and construct the trie. Make second pass from right to left and look for the trie branch with maximum nodes that match the characters. On Thu, Aug 19, 2010 at 7:46 PM, Nikhil Jindal fundoon...@yahoo.co.in mailto:fundoon...@yahoo.co.inwrote: Hi All, Givan a string, you have to find the longest palindromic substring. For ex: Longest Palindromic substring for abclevelabc is level. What is the most optimised solution possible? Please access the attached hyperlink for an important electronic communications disclaimer:http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email toalgoge...@googlegroups.com mailto:toalgoge...@googlegroups.com. To unsubscribe from this group, send email toalgogeeks+unsubscr...@googlegroups.com mailto:toalgogeeks%2bunsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com mailto:algogeeks%252bunsubscr...@googlegroups.com. For more options, visit this group athttp://groups.google.com/group/algogeeks?hl=en 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 toalgoge...@googlegroups.com mailto:toalgoge...@googlegroups.com. To unsubscribe from this group, send email toalgogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Please access the attached hyperlink for an important electronic communications disclaimer:http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are
[algogeeks] Re: kth smallest element in a heap x
Just do a little changes on your given function, that may help you
understand it:
We denote the transformed function as heap_compare_new:
int heap_compare_new(priority_queue *q, int i, int count, int x)
{
if ((count = k) || (i q-n) return(k-count);
/* change */
if (q-q[i] x) {
count++;
/* add one line */
count = heap_compare_new(q, pq_young_child(i), count, x);
/* change */
count = heap_compare_new(q, pq_young_child(i)+1, count, x);
}
return(count);
}
Is that clear now? The new function is used to count the number of
nodes, whose keys are smaller than x, in a subtree rooted on node i,
with a count base, represented by the parameter count, which means
that I have already known that there exist count nodes outside this
subtree having keys smaller than x. And once count becomes equal to k,
the procedure will end and return.
Actually heap_compare_new does the same thing as heap_compare. Here I
just made a minor adjustment that I turned variable 'count' in
original function to the 'k - count' version. The count parameters in
these two functions serve as the same role which I call the count
base.
On Aug 21, 6:11 pm, Ashim Kapoor ashimkap...@gmail.com wrote:
sure, but the implementation is confusing. My question is does not the 2nd
count overwrite the 1st value of count in side the function?
Thank you.
On Sun, Aug 22, 2010 at 1:04 AM, Harshal ..Bet oN iT!!
hc4...@gmail.comwrote:
if it is a min heap,, then traversing down from the root node, it takes
O(k) time to reach the kth smallest element. so, i think its just that
straight!!! plz correct me if m wrong???
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.- 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 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: National Instruments: points separated by a distance d
Let us assume that the point are given in the form of (x1,x2,xn). where n 1 and n is a natural number. Let the given point P is (xp1, xp2,, xpn). Then we have the following algorithm. For each of the point K = (a1,a2,...an) do the following 1. Set d := sqrt [(a1-xp1)^2 + (a2-xp2)^2 + ... + (an-xpn)^2]. 2. If d = D then output K. Running time order of number of number of points. -- 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] National Instruments: linked list subtraction
On 2010-8-25 20:25, Terence wrote: 1. Calculate the length of both list (A, B). 2. Find the position in the longer list corresponding to the head of shorter list, and copy the previous digits to output list C. (Or for simplicity, appending 0 to the shorter list so as to get the same length as the longer one) 3. Add the two lists into list C without performing carry. 4. Perform carries. For each digit x in sum C, and the previous digit px. a) if x 9, no change to x and px; b) if x 9, x = x - 10, px = px + 1; c) if x ==9, continue to next digit until you come to a digit x' not equal to 9 (or the end of list) if x' 9, x' = x' - 10, px = px + 1, and change all the 9's in between to 0. else, keep all those digits untouched. step 3 and 4 can be merged into one pass. Some clarifications to step 4: 1) Pointer update: Initially x point to the head of list C, and px point to a virtual node with value 0. (If carry to this node is performed, a node of value 1 is added to the head of C) After step 4.a, 4.b, both px and x pointed to the next node. After step 4.c, px advanced to x' and x pointed to the next of x'. 2) Correctness. The operation of step 4 (with above update procedure) ensures px 9 before possible carry. 0. Initially, px = 0 1. After 4.a, px = x 9 2. After 4.b, px = x - 10, while x is sum of 2 digits, so x = 18 = px = 8 3. After 4.c, if x' is not the tail of list, then x' != 9. px = x'(x'9) or px = x'-10(x'9) after update. Similar to above 2 cases, px 9. So after the pass of step 4, we've got the final result. The key point behind the steps is taking groups of (99..9x) as a whole. -- 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] National Instruments: linked list subtraction
Sorry for the mistake of addition vs subtraction. See my previous post for some clarifications on the addition procedure. The procedure of subtraction is similar. To calculate C=A-B: 1. Compare A and B, (first compare length. If length is equal, compare the digits from first to last). If A = B, then output C = 0. (A list of single node 0, or an empty list, depending on the format needed). If A B, then record the sign of C as minus, and swap A and B. 2. Find the position in A corresponding to the head of B, and copy the previous digits of A to output list C. (Or for simplicity, appending 0 to B so as to get the same length as A) 3. Subtract B from A without carry, get intermediate list C. 4. Perform carries on C. For each digit x in sum C, and the previous digit px.(For the first digit x, px = 0) a) if x 0, no change to x and px, both px and x advanced to next node. b) if x 0, x = x + 10, px = px - 1, both px and x advanced to next node. c) if x = 0, continue to next digit until you come to a digit x' not equal to 0 (or the end of list) if x' 0, x' = x' + 10, px = px - 1, and change all the 0's in between to 9. else, keep all those digits untouched. Advance px to x' and x to the next of x'. 5. Remove the initial 0s until C begins with non-zero digits. On 2010-8-25 23:45, Raj N wrote: @Terence: It is subtraction of 2 lists and not addition. N for your logic of addition for x9 you add px+1 and after that if it becomes 9 how do you know the previous of it as you've moved the previous pointer? Can someone comment on my logic ? On Wed, Aug 25, 2010 at 9:10 PM, Raj N rajn...@gmail.com mailto:rajn...@gmail.com wrote: They've mentioned that they're large lists. What if it is a 15 digit number? Its not efficient then. On Wed, Aug 25, 2010 at 8:29 PM, Sathaiah Dontula don.sat...@gmail.com mailto:don.sat...@gmail.com wrote: @Raj, How about doing like below ? Convert A to base 10 number, numA Convert B to base 10 number, numB, Then take the difference numC = abs(numA - numB), Then convert numC to linked list with the digits any comments ?, overflow condition is the problem here. Thanks regards, Sathaiah Dontula On Wed, Aug 25, 2010 at 3:24 PM, Raj N rajn...@gmail.com mailto:rajn...@gmail.com wrote: Input : Two large singly linked lists representing numbers with most significant digit as head and least significant as last node. Output: Difference between the numbers as a third linked list with Most significant digit as the head. Eg: --- Input: A = 5-4-2-0-0-9-0-0 B = 1-9-9 Output: C = 5-4-2-0-0-7-0-1 Required complexity : O(n) Constraint: Reversing linked list is NOT allowed -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@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 algogeeks@googlegroups.com mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@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. -- 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: Subsequence
Guys the problem is similar to lcs with just a little difference that here we don't have to maximize the lenght of subsequence but we have to maximize the sum for a given number of elements(k) which should be in non-decreasing order. ex : input : 6 4 2 7 5 8 7 8 k=4 output : 6+7+8+8=29 -- 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] stack
@anurag I meant the sorting without using any auxiliary data structure .Also we have to put the element in the tree and carry out a traversal for every element we insert in the tree .This takes O(n*logn) time , If one can sort the elements using a stack in O(n) time , we better sort with this method , say Stack sort Moral:-No (comparison based )sorting method exists for which time complexity is less than O(n*log n) also , without using any auxialliary data structure , we cannot create all the permutations of the stack Refer Donald knuth's TAOCP for more details On Mon, Jun 14, 2010 at 9:18 AM, Anurag Sharma anuragvic...@gmail.comwrote: Why not just pop all elements from stack ( O(n) ) and insert it in a self balancing Binary Search Tree (like RB Tree) (O(log(n) ) and then do and inorder traversal ( O(n) )and push elements in stack again. Time = O(nlog(n) + n) Space=O(n) (for storing the tree) Anurag Sharma On Sun, Jun 13, 2010 at 9:25 PM, Jitendra Kushwaha jitendra.th...@gmail.com wrote: Stack can be sorted in O(n^2). @sankalp: Stack can always be sorted. Why do you think it cant be in some cases ? One can think like insertion sort algo : 1. for i in (1,n) 2. Pop up the top n-1 element and keep nth element in global variable say hold 3. while pushing get the position for hold and push it there for loop will take O(n) and step 2 will take take O(n) time. So overall O(n^2) complexity Program can be done with recursion using a variable (hence O(1) space). But it will use system stack :) Any comments OR better solution is welcomed?? -- Regards Jitendra Kushwaha MNNIT, Allahabad -- 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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] Re: Subsequence
For the sequence ABCADGH ACDH is a subsequence.. On Wed, Aug 25, 2010 at 10:02 PM, Vikas Kumar dev.vika...@gmail.com wrote: can you define what here subsequence means? On Wed, Aug 25, 2010 at 9:32 PM, Rahul rv.wi...@gmail.com wrote: @Jaswanth It will be really kind if you will state the algorithm rather than providing codes, as it is tedious. -- 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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] Re: Array Problem
can you please explain more in detail the logic for XORing the index.
On 22.08.2010 07:53, UMarius wrote:
@Nikhil : I considered the array to be a linked list. xoring the
indexes helps when you don't know how many elements you have.
Marius.
On Aug 22, 5:04 am, Nikhil Agarwalnikhil.bhoja...@gmail.com wrote:
@marius Why are you xorring the indexes along with nos.?any special reason?
On Sun, Aug 22, 2010 at 7:19 AM, UMariusmar...@aseara.ro wrote:
@Dave: I read the question correctly and for A = { 1 , 2} B = { 2 , 1}
the output is correct.
Maybe I didn't explain the steps correctly. This is the code:
for(int i = 0 ; i arr1.Length ; i++)
{
arr1XOR ^= arr1[i];
arr1XOR ^= i;
arr1SUM += arr1[i];
arr1MUL *= arr1[i];
}
for (int i = 0; i arr2.Length; i++)
{
arr2XOR ^= arr2[i];
arr2XOR ^= i;
arr2SUM += arr2[i];
arr2MUL *= arr2[i];
}
if(arr1XOR == arr2XOR arr1SUM == arr2SUM arr1MUL ==
arr2MUL)
{
//SAME VALUES - IDENTICAL ARRAYS
}
else
{
//NOT IDENTICAL
}
Please correct me if I'm wrong.
Marius.
On Aug 22, 3:45 am, Davedave_and_da...@juno.com wrote:
@UMarius: A = {1,2}, B = {2,1} fails your test. If you reread the
original problem, you see that the question is not whether the arrays
are identical (which is easily determined by simply comparing them
element-by-element in O(n)), but whether they contain the same values,
possibly in a different order.
Dave
On Aug 21, 11:01 am, UMariusmar...@aseara.ro wrote:
What about this?
1. xor all elements of each array and their corresponding indexes
sum all the elements of each array mul all elements of each array
2. if all results are the same then the arrays are identical
Nice to meet you all, I just joined and this is my first post :) ...
Given two arrays of numbers, find if each of the two arrays have the
same set of integers ? Suggest an algo which can run faster than
NlogN
without extra space?- 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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups
.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks Regards
Nikhil Agarwal
Senior Undergraduate
Computer Science Engineering,
National Institute Of Technology,
Durgapur,Indiahttp://tech-nikk.blogspot.comhttp://beta.freshersworld.com/communities/nitd
--
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: Subsequence
@ jashwant raj,rahul i think we have to sort array in non-decreasing order e.g. increasing order 1 way . 2,4,1,4,8,6,7,9 1,2,4,4,6,7,8,9 it will take max(nlogn) time with best sorting algo... also if use counting sort it will take (n+k) time 2.way else in unsorted array it will take also o(logn) time to find if we use binary search in both cases then if we have to know k that is the length of sub- sequence so things is simple if length of subarray of length is 3 in above case is three then we have to find 3 element forming non-decreasing sub-array in array then sum them furture if its the case for sorted array it will take less time to find out max. in above case 3 max. is needed..so less time..O(1) constant time. in unsorted it will take atleast O(logn) time chk out solution. -- 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: Amazon: sort array
@Anand, @Abhishek
Thanks for the code and discussion.
However I am not clear as to how the approach suggested is running in
O(n) time. We are dividing and calling bitonicmerge() on two parts
recursively. So this should run in O(n log n) time complexity as
shown below
T(n) = n/2 + 2T(n/2) = n/2 + 2[n/4 + 2T(n/4)] = n/2 + n/2 + 4[n/8 +
2T(n/8)]
= n/2 + n/2 + n/2 + log n terms (because we are doubling base
each time so it should be log n terms]
= n [ 1/2 + 1/2 + 1/2 + ...log n terms]
= n [ (log n)/2] = 1/2*(n log n ) = O(n log n)
Also all the following links mention this approach to be O(n log^2(n))
in best case and O(n log n) in worst case
http://www.extreme.indiana.edu/sage/pcxx_ug/subsection3_6_2.html
http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm
http://en.wikipedia.org/wiki/Bitonic_sorter
Some explanation on how this is O(n) will be of great help.
Thanks in Advance.
Sourav
On Jul 3, 1:35 am, Abhishek Sharma jkabhishe...@gmail.com wrote:
@Anand: good one
On Sat, Jul 3, 2010 at 2:02 AM, Anand anandut2...@gmail.com wrote:
This is an example of bitonic sequence if we reverse the bottom half of the
array.
Sequence is called Bitonics if the sequence of number first
increases(ascending order) and then decrease(descending order).
1. We need to reverse the bottom half the array to make it bitonic.
2. Appy Bitonic Merge to get the final sorted array.: Complexity.O(n)
In the below code, I have implemented sorting n/w to sort any kind of array
but for bitonic sequence we only bitonic merge function call which take
O(n).
Refer section Sorting network from Corman for more details
http://codepad.org/ZhYEBqMw
On Fri, Jul 2, 2010 at 11:30 AM, ANKUR BHARDWAJ ankibha...@gmail.comwrote:
Given an array of n elements and an integer k where kn. Elemnts
{a[0].a[k] and a[k+1].a[n] are already sorted. Give an
algorithm to sort in O(n) time and O(1) space.
--
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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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] Sorting when n-√n numbers are already sorted
Let A[1..n] be an array such that the first (n − √n) elements are already sorted (though we know nothing about the remaining elements). Give an algorithm that sorts A in substantially better than (n log n) steps. This question is from chapter 4 : Algorithm Design Manual by S Skiena -- 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] Binary tree to LL
Give all possible methods to flatten a binary tree to a linked list. for eg. 50 / \ 25 60 / \ / \ 530 55 75 should be flattened to 5-25-30-50-55-60-75 PS: note that the tree should be converted to the LL and no separate LL should be formed. -- 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] Sorting when n-√n numbers are alre ady sorted
Can't we use bubble sort on remaining elements? On Thu, Aug 26, 2010 at 5:25 PM, sourav souravs...@gmail.com wrote: Let A[1..n] be an array such that the first (n − √n) elements are already sorted (though we know nothing about the remaining elements). Give an algorithm that sorts A in substantially better than (n log n) steps. This question is from chapter 4 : Algorithm Design Manual by S Skiena -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Cheers Naveen Kumar -- 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] Sorting when n-√n numbers are alre ady sorted
merge sort or quick sort or insert last root(n) element . This will take max n time . now merge the last root(n) element with the starting element .this will take n time . so final time complexity is nnlog(n) Rahul -- 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] Sorting when n-√n numbers are alre ady sorted
ooops wrong approach... :( On Thu, Aug 26, 2010 at 10:44 PM, Naveen Kumar naveenkumarve...@gmail.comwrote: Can't we use bubble sort on remaining elements? On Thu, Aug 26, 2010 at 5:25 PM, sourav souravs...@gmail.com wrote: Let A[1..n] be an array such that the first (n − √n) elements are already sorted (though we know nothing about the remaining elements). Give an algorithm that sorts A in substantially better than (n log n) steps. This question is from chapter 4 : Algorithm Design Manual by S Skiena -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Cheers Naveen Kumar -- Cheers Naveen Kumar -- 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] Binary tree to LL
I can only figure out the inorder traversal... On Thu, Aug 26, 2010 at 9:59 AM, krazee koder aravindhr...@gmail.com wrote: Give all possible methods to flatten a binary tree to a linked list. for eg. 50 / \ 25 60 / \ / \ 5 30 55 75 should be flattened to 5-25-30-50-55-60-75 PS: note that the tree should be converted to the LL and no separate LL should be formed. -- 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] Binary tree to LL
Am 26.08.2010 18:59, schrieb krazee koder: Give all possible methods to flatten a binary tree to a linked list. for eg. 50 / \ 25 60 / \ / \ 530 55 75 should be flattened to 5-25-30-50-55-60-75 PS: note that the tree should be converted to the LL and no separate LL should be formed. If the above example is preorder it must be: 5-25-30-55-60-75-50 because preorder is looking to me like nested sets or celco trees. Postorder would be: 50-25-5-30-60-55-75 Inorder: 5-25-50-30-60-55-75 or 5-25-50-40-55-60-75 I'm not to sure. Pls correct me if I'm wrong! -- 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] Binary tree to LL
No, you are wrong here. The inorder sequence should be 5 - 25 - 30 - 50 - 55 - 60 -75. The preorder sequence should be 50 - 25 - 5 - 30 - 60 - 55 - 75 The postorder sequence should be 5 - 30 - 25 - 55 - 75 - 60 - 50 Below is the analysis (from wikipedia): To traverse a non-empty binary tree in preorder, perform the following operations recursively at each node, starting with the root node: 1. Visit the root. 2. Traverse the left subtree. 3. Traverse the right subtree. To traverse a non-empty binary tree in inorder (symmetric), perform the following operations recursively at each node: 1. Traverse the left subtree. 2. Visit the root. 3. Traverse the right subtree. To traverse a non-empty binary tree in postorder, perform the following operations recursively at each node: 1. Traverse the left subtree. 2. Traverse the right subtree. 3. Visit the root. Go to http://en.wikipedia.org/wiki/Traversal and see details. On Thu, Aug 26, 2010 at 11:59 AM, Chi Hoang i...@chihoang.de wrote: Am 26.08.2010 18:59, schrieb krazee koder: Give all possible methods to flatten a binary tree to a linked list. for eg. 50 / \ 25 60 / \ / \ 5 30 55 75 should be flattened to 5-25-30-50-55-60-75 PS: note that the tree should be converted to the LL and no separate LL should be formed. If the above example is preorder it must be: 5-25-30-55-60-75-50 because preorder is looking to me like nested sets or celco trees. Postorder would be: 50-25-5-30-60-55-75 Inorder: 5-25-50-30-60-55-75 or 5-25-50-40-55-60-75 I'm not to sure. Pls correct me if I'm wrong! -- 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] Re: Subsequence
@ bittu input : 6 1 4 8 3 7k=2 output : 6 + 8 =14 it's not 7+8=15 which wud be the case if ul apply sorting and take k largest elements. if i got ur point correct. Rahul Verma NIT Allahabad -- 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] Binary tree to LL
At first, store the pointer to the first node in inorder traversal (in this
case 5) because its going to be the head of the list.
Then use the following logic.
flattenTree(TreeNode node) {
if (node is leaf node)
return node;
if (node.left exists) then
flattenTree(node.left)-next = node;
if (node.right exists) then
node-next = flattenTree(node.right);
return node;
}
On Thu, Aug 26, 2010 at 11:07 PM, Yan Wang wangyanadam1...@gmail.comwrote:
I can only figure out the inorder traversal...
On Thu, Aug 26, 2010 at 9:59 AM, krazee koder aravindhr...@gmail.com
wrote:
Give all possible methods to flatten a binary tree to a linked list.
for eg.
50
/ \
25 60
/ \ / \
530 55 75
should be flattened to 5-25-30-50-55-60-75
PS: note that the tree should be converted to the LL and no separate
LL should be formed.
--
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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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] Re: Sorting when n-√n numbers are alre ady sorted
@Rahul Agree with your approach. When you say merge the last root(n) elements with the starting elements, it means you are doing something like merge sort using an additional O(n) space. Correct me if I am wrong. This should give O(n) overall time complexity. How about an in - place approach? Some thoughts on this? On Aug 26, 10:22 pm, Rahul Singal rahulsinga...@gmail.com wrote: merge sort or quick sort or insert last root(n) element . This will take max n time . now merge the last root(n) element with the starting element .this will take n time . so final time complexity is n nlog(n) Rahul -- 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: Binary tree to LL
how to rearrange the pointers ?? -- 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] Sorting when n-√n numbers are alre ady sorted
Hi Sourav, I will first inplace sort the last √n elements in O(n) and then merge the two sorted arrays in O(n). The only problem: O(n) merging will not be inplace. On Thu, Aug 26, 2010 at 5:25 PM, sourav souravs...@gmail.com wrote: Let A[1..n] be an array such that the first (n − √n) elements are already sorted (though we know nothing about the remaining elements). Give an algorithm that sorts A in substantially better than (n log n) steps. This question is from chapter 4 : Algorithm Design Manual by S Skiena -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- 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: Sorting when n-√n numbers are already sorted
@saurav I dont think in place approach is possible . This will end up taking n^2 time . -- 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.
