[algogeeks] Re: puzzle
Sorry abt the previous post ( and this one ) if it ended up as a spam. I just saw the question and left the place. When I finished posting, ppl hav already given replies... On Jul 7, 12:12 am, 991 wrote: > Approach 1: > > Start from storey 1 and go up. keep dropping one of the eggs. As soon > at it breaks, return the storey you are in now. No. of drops in the > worst case: 99 > > Approach 2: > > Split the building into 10 '10 storeyed' parts. > > Start Dropping eggs at 10,20,30,...th storey. > If it breaks at say 40th, use the other egg from 31st storey till 39th > and return the ans. > > No. of drops in worst case: approx. 20 > > Approach 3: > > Why should v divide the building into equal storeyed segments? Have > more storeys in lower part of the building and let it come down as we > go up. How does it help? Well by the nature of our method, if it > breaks at some 80+ storey (say), we want use the second egg lesser > number of times that it was when it is in 20th storey or something. > > The first egg can be used in this order: 14,27,39,50,60... ( I am > about to sleep now and I have no energy to find out the exact starting > number. But I hope that u get the idea.) > > Now the same approach can be used once the first egg breaks. > > No. of drops in worst case: Approx. 14 > > More on this problem: Find an algo for any general number of eggs and > any general number storeys... > > Dont look at the hint below before giving it a try. > > Hint: DP > > On Jul 6, 10:05 pm, shiv narayan wrote: > > > > > > > > > * You are given 2 eggs. > > * You have access to a 100-storey building. > > * Eggs can be very hard or very fragile means it may break if dropped > > from the first > > floor or may not even break if dropped from 100 th floor.Both eggs are > > identical. > > > * You need to figure out the highest floor of a 100-storey building an > > egg can be > > dropped without breaking. > > * Now the question is how many drops you need to make. You are allowed > > to break 2 > > eggs in the process -- 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. 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: puzzle
Approach 1: Start from storey 1 and go up. keep dropping one of the eggs. As soon at it breaks, return the storey you are in now. No. of drops in the worst case: 99 Approach 2: Split the building into 10 '10 storeyed' parts. Start Dropping eggs at 10,20,30,...th storey. If it breaks at say 40th, use the other egg from 31st storey till 39th and return the ans. No. of drops in worst case: approx. 20 Approach 3: Why should v divide the building into equal storeyed segments? Have more storeys in lower part of the building and let it come down as we go up. How does it help? Well by the nature of our method, if it breaks at some 80+ storey (say), we want use the second egg lesser number of times that it was when it is in 20th storey or something. The first egg can be used in this order: 14,27,39,50,60... ( I am about to sleep now and I have no energy to find out the exact starting number. But I hope that u get the idea.) Now the same approach can be used once the first egg breaks. No. of drops in worst case: Approx. 14 More on this problem: Find an algo for any general number of eggs and any general number storeys... Dont look at the hint below before giving it a try. Hint: DP On Jul 6, 10:05 pm, shiv narayan wrote: > * You are given 2 eggs. > * You have access to a 100-storey building. > * Eggs can be very hard or very fragile means it may break if dropped > from the first > floor or may not even break if dropped from 100 th floor.Both eggs are > identical. > > * You need to figure out the highest floor of a 100-storey building an > egg can be > dropped without breaking. > * Now the question is how many drops you need to make. You are allowed > to break 2 > eggs in the process -- 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. 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: Bipartite Matching?
The question can be restated as follows: Given a graph, is it bipartite?. If yes, find the partition. A graph is bipartite if and only if there is no odd cycle. The following algo wl find the partition and if there is an odd cycle, it wl report that it is not possible. Level Decompose the graph with respect to some vertex. ( BFS can be used here) ( O(V+E) ) If there is an edge between two vertices which are both in odd or in even depth, return false. ( Running through all the edges ) ( O( E) ) Else return partition 1 = all vertices at odd depth. partition 2 = all vertices at even depth. Overall complexity: O(V+E) I think this answers your question. On Jul 6, 12:37 am, Nitish Garg wrote: > Can you point me through any tutorial for Graph Coloring? I think CLRS does > not explain graph coloring. -- 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. 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: segment tree
Try this: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor On Jul 4, 5:15 pm, geek forgeek wrote: > any1 -- 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. 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 Array
Radix sort can solve the problem in O(N) time. Max. value of input is N^2 so in binary representation, we need d = 2(logN)+1 digits to represent each number. ( It is O(logN) - thats the key) Now group logN bits ( say r = logN ) The maximum value in each group is O( 2^r) This is the base in which we will do radix sort. No of digits in this new base = d/r Max value of each digit in this new base = 2^r Time taken for radix sort: O( No. of digits * ( Time for sorting each digit ) ) Time for sorting N numbers on one digit = O(n+2^r) So total time = O( d/r * (n+2^r) ) By the choice of d and r, we get Time = O(N). Infact this will work any range polynomial in N. Note that this is just a theoretical analysis and in general Quick sort beats Radix sort in practice because of the hidden constant factors On Jun 28, 9:55 pm, L wrote: > There is one way in which we can do O(n). > Convert the numbers in base 'n'. [ O(n) ]. > Now, there are 2-digit numbers, each digit ranging from 0 to n-1. > You can call count-sort 2 times (for each digit), so, complexity is O(n > +n) =O(n). > > On Jun 27, 12:22 am, Dan wrote: > > > Your question is good for a classroom style discussion/debate. > > However, in the real world, there is no simple answer. > > > There are lots of sorting algorithms. Each one has it's pros & cons > > and no single sorting algorithm is "best", especially when not much is > > known about the data to be sorted. In your case about all that > > we really know is that there are no negative numbers involved. I > > don't think that helps very much (any?). Then... you need to > > consider the programming language and computer system used for the > > implementation. Yes. They do matter. Sometimes, they matter a > > LOT. Don't assume that an O(x) algorithm is better than an O(y) > > algorithm just because x is less than y. > > > Dan :-) > > > On Jun 26, 12:14 am, ross wrote: > > > > Given a sequence of numbers in the range of 1-N^2, what is the most > > > efficient way to sort the numbers (better than NlgN).. > > > Can counting sort be used here? Is an O(N) solution possible.. -- 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. 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: Queue using a stack
Tell me the approach you have thought of. On Jun 28, 8:39 am, Ashish Goel wrote: > Hi, > > The implementation is simple using 2 stacks, however we also need to make > sure that if queue length is say x, we are able to enqueue x elements. As > per my understanding, i could think of the solution using 4 stacks instead > of 2(1 for enqueue, 1 for dequeue, 1 aux for enqueue, 1 aux for dequeue) . > Is there any better approach. > > Best Regards > Ashish Goel > "Think positive and find fuel in failure" > +919985813081 > +919966006652 -- 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. 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: Longest simple path problem
I will explain with an example: 3 a --- b | | | | | 5 | 4 | | c-d 1 lets say we want to find the shortest path from c to b, denote sp(x,y) as the length of the shortest path from x to y SP(c,b) = min( SP(c,a) + SP(a,b) , SP(c,d) + SP(d,b) ) // this step should be done for all vertices other that the source and the sink. which in this case is a and d. this is fine but we must make sure that the resulting path is simple. If the shortest path is P1(source,x) + P2(x,sink), assuming that the recursive calls produce simple paths, the shortest path from source to sink is also simple. this is true since if the two paths returned share an vertex (other than the end point) (say v), then P1(source,v)+P2(v,sink) is a shorter path, violating the assumption of shortest path. ( this argument is valid iff the cycle corresponding to P1(v,x) +P2(x,v) has non negative weight - else there is no notion of "shortest path"). on the other hand, for longest path problem, such greedy choices wont work. For example consider the same recurrence this time but instead of minimum find the maximum. For the graph above, LP(c,d) = 12 and the corresponding path is c-a-b-d LP(d,b) = 9 and the corresponding path is d-c-a-b both paths are simple but their concatenation results in a non simple path. (This is due to the nature of "longest". Think about it - its definitely a bad guy...deserves its position in NP class...) Hope you understood... On Jun 28, 11:45 am, ankit sambyal wrote: > Shortest simple path problem is in P, but Longest simple path problem > is in NP. Explain why the greedy choice(on edge weights) is not > suitable in the second case . > > Ankit Sambyal > BITS Pilani -- 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. 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.
