tag:blogger.com,1999:blog-4068183698747623113.post5031685703664530875..comments2023-10-29T10:40:34.638-04:00Comments on A CS Professor's blog: Testing SortednessClaire Mathieuhttp://www.blogger.com/profile/10957755706440077623noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-4068183698747623113.post-33545562522054211322012-01-25T13:54:29.182-05:002012-01-25T13:54:29.182-05:00Thank you very much. =)Thank you very much. =)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4068183698747623113.post-25544864282324668912012-01-24T21:26:39.111-05:002012-01-24T21:26:39.111-05:00The answer is in Wikipedia's article about Ver...The answer is in Wikipedia's article about Vertex Cover, in the paragraph "Approximate Evaluation".Claire Mathieuhttps://www.blogger.com/profile/10957755706440077623noreply@blogger.comtag:blogger.com,1999:blog-4068183698747623113.post-78380528863998708872012-01-24T20:50:42.009-05:002012-01-24T20:50:42.009-05:00Sorry, but how would you prove that:
"It is ...Sorry, but how would you prove that:<br /><br />"It is known (basic approximation algorithms fact) that the maximum matching M has size at least 1/2 times the minimum vertex cover, |M| >= |S|/2"<br /><br />It looks deceptively simple and I'm sure I'm missing something trivial but I just can't seem to be able to do it. Thanks.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4068183698747623113.post-36599917311071608922011-10-20T17:13:51.591-04:002011-10-20T17:13:51.591-04:00Thanks Anonymous. I inserted a sentence to remove ...Thanks Anonymous. I inserted a sentence to remove the confusion: "By check, I mean, with reasonable confidence (say, you're correct with probability 99%)."<br /><br />Thanks to your help, by the time the semester comes I'll have lecture notes for this class ready already!Claire Mathieuhttps://www.blogger.com/profile/10957755706440077623noreply@blogger.comtag:blogger.com,1999:blog-4068183698747623113.post-74040214569396634232011-10-20T16:25:26.192-04:002011-10-20T16:25:26.192-04:00"Then one of those edges would (probably) be ..."Then one of those edges would (probably) be found after a logarithmic number of tries."<br /><br />The "probably" here is the first time that you mention the test is probabilistic. Before you write:<br /><br />"By "nearly sorted", I mean that only a few of the numbers are out of place: if we ignore 4% of the numbers (outliers), the rest is sorted."<br /><br />And "Output "The array is nearly sorted" if and only if all the checks are successful."<br /><br />While reading I was constantly wondering how you can assert this by looking only at a fraction of the input.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4068183698747623113.post-79468076224684308982011-10-20T09:35:38.740-04:002011-10-20T09:35:38.740-04:00Very nice Anonymous. Thanks!Very nice Anonymous. Thanks!Claire Mathieuhttps://www.blogger.com/profile/10957755706440077623noreply@blogger.comtag:blogger.com,1999:blog-4068183698747623113.post-32597151100495873192011-10-20T03:14:16.545-04:002011-10-20T03:14:16.545-04:00See Problem 2-1 at:
http://ocw.mit.edu/courses/el...See Problem 2-1 at:<br /><br />http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/assignments/ps2.pdf<br /><br />for a variant.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4068183698747623113.post-74030739504541882672011-10-19T15:56:53.936-04:002011-10-19T15:56:53.936-04:00Oops. Notation error, sorry! I meant, the outliers...Oops. Notation error, sorry! I meant, the outliers.Claire Mathieuhttps://www.blogger.com/profile/10957755706440077623noreply@blogger.comtag:blogger.com,1999:blog-4068183698747623113.post-86557551706429454832011-10-19T15:02:58.367-04:002011-10-19T15:02:58.367-04:00I had almost exactly the same confusion myself !I had almost exactly the same confusion myself !Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-4068183698747623113.post-69232796259545476492011-10-19T13:49:23.053-04:002011-10-19T13:49:23.053-04:00Sorry, maybe I misunderstand what you wrote. I don...Sorry, maybe I misunderstand what you wrote. I dont see why S is a minimum vertex cover of the graph you constructed. First S is a set of edges. If you interpret the end points of edges in S as a vertex cover, the size of this vertex set can be smaller than |S|. Also it should not be minimum in general. If A is sorted then the graph has no edges. But S has a fixed size of nlogn.Anonymousnoreply@blogger.com