tag:blogger.com,1999:blog-3722233.post110992733203443427..comments2020-09-27T10:10:33.180-05:00Comments on Computational Complexity: Finding DuplicatesLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-3722233.post-1110203509652112282005-03-07T07:51:00.000-06:002005-03-07T07:51:00.000-06:00Anonymous,
I think the binary search method you p...Anonymous,<br /><br />I think the binary search method you posted will fail on the input:<br /><br />1, 2, 3, 4, 4<br /><br />After the first pass,<br />mid = 3<br />n1 = 2<br />n2 = 1<br />n3 = 2<br /><br />Since n1 >= n3 is true in this case, the algorithm will close in on the first part of the list, which does not contain the duplicate.<br /><br />See an earlier post for a binary search which I think does work.Jonathanhttps://www.blogger.com/profile/04884672993717687570noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1110203409846954592005-03-07T07:50:00.000-06:002005-03-07T07:50:00.000-06:00The following is a partial answer to the problem a...The following is a partial answer to the problem above.<br />[ I was attending the New Horizons workshop in Kyoto, Japan last week; after Muthu's talk I was<br />discussing the following with Muthu. Jun Tarui (tarui+at-mark+ice.uec.ac.jp)]<br /><br />Finding duplicates in the stream setting above requires Omega(log n/ loglogn) passes.<br /><br />Proof Sketch:<br /><br />Assume n is odd.<br />Consider a restricted class of inputs such that A(1), A(2), ..., A((n+1)/2) are distinct and<br />A((n+1)/2 + 1), ..., A(n+1) are distinct.<br />A solution for this class of inputs with s bits of memory and r stream-passes<br />implies a two-party protocol for the following communication game<br />with r rounds and s communication bits in each round.<br /><br />Alice and Bob get size-(n+1)/2 subsets A and B of {1,...,n} respectively <br />and the task is to find and agree<br />on some w that is in the intersection of A and B.<br /><br />This task is equivalent to the monotone Karchmer-Wigderson game for the Majority<br />funtion of n variables (Alice and Bob get a max term and a min term).<br />A protocol with r rounds and s bits per round for this game correnponds to<br />a monotone (i.e. AND/OR) circuit computing the Majority function <br />with depth at most r and fan-in at most 2^s.<br />Hastad's size lower bound for such circuits imply the claimed bound on the number of passes<br />above for s=O(log n).<br /><br />When n is even, consider the complexity of any function that outputs 1 if the number of 1's<br />is more than n/2 and outputs 0 if it is less than n/2. (end-of-proof-sketch)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1110181474168461362005-03-07T01:44:00.000-06:002005-03-07T01:44:00.000-06:00I think the binary search would work as follows:
...I think the binary search would work as follows:<br /><br />binsearch(a , b)<br />begin<br />-> choose mid = (a + b)/2<br />-> count no. of elements <, = and > mid, say n1, n2 and n3<br />-> if n2 >= 2 end<br />-> else if n1 >= n3 binsearch(a , mid -1)<br />-> else binsearch(mid + 1, b)<br />end<br /><br />Now, just call binsearch(1 , n).<br /><br />We need to maintain the values of n1, n2 and n3 in each pass and the values of a and b all the time. All of these require O(log n) space.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1110087030429826332005-03-05T23:30:00.000-06:002005-03-05T23:30:00.000-06:00Regarding the binary search algorithm, I think the...Regarding the binary search algorithm, I think the statement "Uses constant amount of space" is wrong...<br /><br />The variable "upper" needs to be able to represent N, which requires log N bits. So even the binary search method requires log N space.Jonathanhttps://www.blogger.com/profile/04884672993717687570noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1110065769423641202005-03-05T17:36:00.000-06:002005-03-05T17:36:00.000-06:00> "binary search takes more than O(n) queries."
Y...> "binary search takes more than O(n) queries."<br /><br />Yes, but Lance also asked: "Now suppose A is streamed, that is we get in order A(1),A(2),�,A(n+1) and then get another pass etc. How many passes do you need to find a w?"<br /><br />The binary search method solved this variant of the problem, unless I'm mistaken.Jonathanhttps://www.blogger.com/profile/04884672993717687570noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1110064512818149862005-03-05T17:15:00.000-06:002005-03-05T17:15:00.000-06:00you can sum all numbers
since
sum 1..n = n(n-1)/2...you can sum all numbers<br />since <br />sum 1..n = n(n-1)/2 you need around <br />2 log n = O(log n) bits<br />there the correct answer is<br />sum - n(n-1)/2<br />Definitly O (log n) bits is enough<br /><br />in case of stream one pass is enough<br />just sum numbers again :)<br /><br />just a joke<br /><br />it would be interestig to solve a problem in general case<br />assume k numbers out of n are duplicated<br />So by suming you get sum <br />a_1 + \cdot a_k = sum - n(n-1)/2<br /><br />it may happen that you need small amount of memory/computations to find out which exactly numbers are duplivated if you know sum<br /><br /><br />just for funnyALhttps://www.blogger.com/profile/01796354487712418267noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1110060014211648942005-03-05T16:00:00.000-06:002005-03-05T16:00:00.000-06:00As an aside, note that if exactly one element is d...As an aside, note that if exactly one element is duplicated it can be done in one pass using O(log n) space: simply add all the numbers, substract n(n+1)/2 and that is the duplicated number.<br /><br />AlexAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1110050733977478322005-03-05T13:25:00.000-06:002005-03-05T13:25:00.000-06:00binary search takes more than O(n) queries.binary search takes more than O(n) queries.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1110043101244078782005-03-05T11:18:00.000-06:002005-03-05T11:18:00.000-06:00Just for fun, here's a C++ function that seems to ...Just for fun, here's a C++ function that seems to work, using a binary search. Uses constant amount of space. Sorry for the formatting...<br /><br />unsigned findDup(const std::vector<unsigned> &vec, bool diagnostics)<br />{<br />unsigned lower = 1, upper = vec.size()-1;<br /><br /> while(true)<br /> {<br /> unsigned count = 0, middle = (upper+lower)/2;<br /><br /> for(unsigned i=0; i<vec.size(); i++)<br /> if(lower <= vec[i] && vec[i] <= middle) count++; <br /><br /> if(count > middle-lower+1) upper = middle;<br /> else lower = middle+1;<br /><br /> if(lower >= upper)<br /> return upper;<br /> }<br />}Jonathanhttps://www.blogger.com/profile/04884672993717687570noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1109993784107945082005-03-04T21:36:00.000-06:002005-03-04T21:36:00.000-06:00http://domino.research.ibm.com/Comm/wwwr_ponder.ns...http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/January2004.htmlAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1109985391289602052005-03-04T19:16:00.000-06:002005-03-04T19:16:00.000-06:00"Create a linked list kind of structuure where the..."Create a linked list kind of structuure where there are n+1 nodes" sounds like O(n) space, not O(log n).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1109962767262490682005-03-04T12:59:00.000-06:002005-03-04T12:59:00.000-06:00"First a warm-up puzzle: Find w using only O(n) qu..."First a warm-up puzzle: Find w using only O(n) queries to entries of A (remember you only get O(log n) space). Hint: Use pointer chasing."<br />Ans: create a linked list kind of strucutre where there are n+1 nodes, <br />a) value at node i, v[i]=A[i]<br />b) pointer from node i to node <br />v[i].<br />check for loops in the linked list by using pointer chasing, starting from node n+1.Anonymousnoreply@blogger.com