Re: [algogeeks] Cartesian Product in set theory
The unordered pair will be a subset of cartesian product. What is the significance of it? On 8 February 2010 21:18, pinco1984 paris...@gmail.com wrote: Hi all, I have came across a problem and I am not aware if there is such a thing in set theory and if so what is it called. Mainly I have several sets that I am interested in their cartesian product. But this cartesian product should not be a set of ordered pairs but a set of sets. Basically unordered pairs. I wonder if this concept is well defined and what is it called. Thanks. P. -- 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] Cartesian Product in set theory
Not indeed. Cartesian product produces tuples as the result, but I am interested in the set form of these tuples. if there are two sets like X={A,B,C} Y={A,B} then The Cartesian product will be: X.Y={(A,A),(A,B),(B,A),(B,B),(C,A),(C,B)} Whereas if insted of tuples sets were produced it would be like the followings: X.Y={{A}, {A,B}, {B}, {A,C}, {B,C}} P. On Feb 9, 2010, at 5:21 AM, vignesh radhakrishnan wrote: The unordered pair will be a subset of cartesian product. What is the significance of it? On 8 February 2010 21:18, pinco1984 paris...@gmail.com wrote: Hi all, I have came across a problem and I am not aware if there is such a thing in set theory and if so what is it called. Mainly I have several sets that I am interested in their cartesian product. But this cartesian product should not be a set of ordered pairs but a set of sets. Basically unordered pairs. I wonder if this concept is well defined and what is it called. Thanks. P. -- 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 . Parisa -- 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] Monte Carlo Algorithm to find a repeated element
An array arr has n/4 copies of a particular unknown element x. Every other element in arr has at most n/8 copies. Give an O(logn) time Monte Carlo alorithm to identify x. The answer should be correct with high probability. -- 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] Cartesian Product in set theory
you can always eliminate them On Tue, Feb 9, 2010 at 5:07 PM, Parisa paris...@gmail.com wrote: Not indeed. Cartesian product produces tuples as the result, but I am interested in the set form of these tuples. if there are two sets like X={A,B,C} Y={A,B} then The Cartesian product will be: X.Y={(A,A),(A,B),(B,A),(B,B),(C,A),(C,B)} Whereas if insted of tuples sets were produced it would be like the followings: X.Y={{A}, {A,B}, {B}, {A,C}, {B,C}} P. On Feb 9, 2010, at 5:21 AM, vignesh radhakrishnan wrote: The unordered pair will be a subset of cartesian product. What is the significance of it? On 8 February 2010 21:18, pinco1984 paris...@gmail.com wrote: Hi all, I have came across a problem and I am not aware if there is such a thing in set theory and if so what is it called. Mainly I have several sets that I am interested in their cartesian product. But this cartesian product should not be a set of ordered pairs but a set of sets. Basically unordered pairs. I wonder if this concept is well defined and what is it called. Thanks. P. -- 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. Parisa -- 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. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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] Cartesian Product in set theory
Yes, it is, and that is my question. What if instead of ordered pairs it is sets. Is this concept well defined? I mean no one can use cartesian product anymore to represent this staff. What is the operation for this. On Feb 9, 2010, at 2:01 PM, saurabh gupta wrote: http://en.wikipedia.org/wiki/Cartesian_product it is defined as a set of ordered pairs. On Tue, Feb 9, 2010 at 9:51 AM, vignesh radhakrishnan rvignesh1...@gmail.com wrote: The unordered pair will be a subset of cartesian product. What is the significance of it? On 8 February 2010 21:18, pinco1984 paris...@gmail.com wrote: Hi all, I have came across a problem and I am not aware if there is such a thing in set theory and if so what is it called. Mainly I have several sets that I am interested in their cartesian product. But this cartesian product should not be a set of ordered pairs but a set of sets. Basically unordered pairs. I wonder if this concept is well defined and what is it called. Thanks. P. -- 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 . -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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 . Parisa -- 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]
hey, i have a solution to ur prob : a) for k=2 case, check at intervals of sqrt(n) you will find the jar between say sqrt(i) and sqrt(i+1) do a linear search between sqrt(i) and sqrt(i+1) ( clearly the order is sqrt(n) ) b) for k=k! , consider at kth root of n instead of sqrt everywhere above. I guess you will be able to do the reasoning part now Rohit Saraf Sophomore IIT Bombay --- http://www.cse.iitb.ac.in/~rohitfeb14 On Tue, Feb 9, 2010 at 8:03 PM, suganya c sugu18901...@gmail.com wrote: can u help with the solution for this problem.?? You’re doing some stress-testing on various models of glass jars to determine the height from which they can be dropped and still not break. The setup for this experiment, on a particular type of jar, is as follows. You have a ladder with n rungs, and you want to find the highest rung from which you can drop a copy of the jar and not have it break..We ca~, this the highest safe rung. It might be natural to try binary search: drop a jar from the middle rung, see if it breaks, and then recursively try from rung n/4 or 3n/4 depending on the outcome. But this has the drawback that y9u could break a lot of jars in finding the answer. If your primary goal were to conserve jars, on the other hand, you could try the following strategy. Start by dropping a jar from the first rung, then the second rung, and so forth, climbing one higher each time until the jar breaks. In this way, you only need a single j ar--at the moment it breaks, you have the correct answer--but you may have to drop it rt times (rather than log rt as in the binary search solution). So here is the trade-off: it seems you can perform fewer drops if you’re willing to break more jars. To understand better how this tradeoff works at a quantitative level, let’s consider how to run this experiment given a fixed budget of k _ 1 jars. In other words, you have to determine the correct answer--the highest safe rung--and can use at most k jars In doing so. (a) Suppose you are given a budget of k = 2 jars. Describe a strategy for finding the highest safe rung that requires you to drop a jar at most f(n) times, for some function f(n) that grows slower than linearly. (In other words, it should be the case that limn-.~ f(n)/n = 0.) (b) Now suppose you have a budget of k 2 jars, for some given k. Describe a strategy for fInding the highest safe rung using at most k jars. If fk(n) denotes the number of times you need to drop a jar according to your strategy,then the functions f1,f2,f3...should have. the property that each grows asymptotically slower than the previous one: lirnn_~ fk(n)/fk_l(n) = 0 for each k. thank u, -- 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.