.Open 18 . Schedule .Table Date .Item Meet'g .Item $Study(2 pts) .Item Bring(5 pts) .Item $Topic(5 pts) .Item Notes .Row Wed May 31 .Item 17 .Item Chapter 11 sections 11.1, 11.2, 11.3 .Item Ex .Item Co-NP & PSPACE .Row Mon Jun 5 .Item 18 .Item Chapter 11 sections 11.4 .Item $Ex .Item Randomization RP ZPP .Row Wed Jun 7 .Item 19 .Item Chapter 11 sections 11.5, 11.6 .Item Ex .Item Primality .Close.Table . Random Introduction One obvious trick for translating a nondeterministic solution to a problem into a deterministic algorithm is to replace the "luck guess" by a random choice. We might expect that random algorithms will have more power than deterministic ones but less power than NP... if so we are closer to separating P from NP. Complexity classes are largely based on the worst case behavior of algorithms and machines. In many cases the client is interested in the average time. One way to improve the average time while reducing the chance of a worst case is to use randomization. The "take home message" from this section is the practical technique of introducing a little randomness into programs to keep the customer satisfied. As a result the assigned work was about a practical experience. . Bad Example of a Random Algorithm -- the dart board \pi calculator To evaluate \pi .List Repeatedly pick random pairs of real numbers (`x`,`y`) in the range -0.5 .. +0.5 and count the number of times `x^2+y^2 < 0.25`, Output (the number of hits)/(number attempts). .Close.List .Open Review Assigned Work . Hints from Jacob Pitassi It was very hard to find information on Bentley\'s quicksort problem. Here is a link that hints that Bentley had qsort run to long on him and that he wants psort which has a worst case of O(nlogn). .See http://portal.acm.org/citation.cfm?id=1045972&dl=GUIDE&coll=GUIDE . Programming Pearl from Brian Strader .See http://doi.acm.org/10.1145/358027.381121 . Jon Bentley and quicksort -- Mike Schick .See http://www.cs.cmu.edu/afs/cs/user/copetas/www/public/calendar/bentley.html . QuickSort Article by Bentley and McIlroy From: Minhchau Dang, Stephen Collins, Jason Hunt, Scott McAllister, and Raini Armstrong, Jedidah Mwangi .See http:://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/421/09/bentley93engineering.pdf .Close .Open 11.4 Language Classes Based on Randomization 487 . Ch 11.4 pp 487-488 -- Randomization Is there any way to produce a truly random number using a computer/Turing machine? . Ch 11.4 pp -- ZPP Why is it that a modern computer can not make a true random number? History of Random numbers.... . 11.4.1 Quicksort: an Example of a Randomized Algorithm 488 Jon Bentley has written an article explaining what happens to a program who does not randomize quick sort! See $Ex below. .Open 11.4.2 A Turing-Machine Model Using Randomization 489 . Example 11.12 Quicksort on a randomized TM .Open ERRATA in example 11.12 Replace since `m` not be a power of 2 By since `m` may not be a power of 2. .Close . Ch 11.4.2 pp 489 -- A Turing Machine Using Randomization Figure 11.6: A Turing machine with the capability of using randomly "generated" numbers: can you explain the functionality of Random bits Tape? How is the random number "pivot" picked so that it is not larger then the number of elements ? . Ch QuickSort How efficient would it be to do a quicksort on a Turing machine? When computers had small amounts of of RAM, no disks, and a few tape drives.... they worked just like a Turing Machines and the most common library program was a multi-tape sort. We did not use quicksort. A polyphase n-way balanced merge sort was usually used. Knuth shows that it is close to optimal in Vol 3 of the Art of Computer Programming. This quick sort always does the right thing but its runtim is random. Worst case is O(n^2). Average case is O(n log n) -- on a multitape TM. On a one+random tape we can expect an average time of O( n^2 (log n)^2). .Close . 11.4.3 The Language of a Randomized Turing Machine 490 The following table of possibilities may help explain the options .Table M \ w in L not in L .Row Accepts OK false +ve .Row not Accepts false -ve OK .Close.Table . Example 11.13 -- Homogeneous strings 0*+1* . Could you Please explain the table on figure 11.7 . 11.4.4 The Class RP 493 -- Monte Carlo Algorithms .Table M \ w in L not in L .Row Accepts >0.5 0 .Row not Accepts <0.5 1 .Close.Table PLUS M must accept in polynomial time. . Ch 11.4 pp 494 -- RP-P Can you give an example of a problem in RP but not P? Errrrr.... No! . Example 11.14 = Example 11.13 .Table M \ w in 0*+1* not in 0*+1* .Row Accepts >0.5 2^(-n) .Row not Accepts <0.5 1-2^(-n) .Close.Table The example above is not RP. . Example 11.15 -- Graphs with triangles .Table M \ w some triangle No triangle .Row Accepts >0.5 0 .Row not Accepts <0.5 1 .Close.Table .Open 11.4.5 Recognizing Languages in RP 495 . Ch 11.4.5 pp 495 -- RP Could you show how to recognize languages in RP using Theorem 11.16? . Ch 11.4.5 pp 495 -- Recognizing Languages in RP Can you show an example where we use Theorem 11.16 to determine membership in RP? Anecdote: Playing poker dice... Discussion: Is my coin double headed? It keeps coming up heads! This is an ambiguous section heading. It could mean Use this section to find out if your language is RP or it could mean How to construct a more reliable automata/recognizer for an RP language. .Close . Theorem 11.16 -- If L in RP then we can reduce error by any amount in polynomial time Proof: repeat the same algorithm... . 11.4.6 The Class ZPP 495 ZPP::="Zero-error Probabilistic Polynomial time". Does the right thing .Table M \ w in L not in L .Row Accepts 1 0 .Row not Accepts 0 1 .Close.Table But the time is random and its AVERAGE is O(n^k) for some k. Compare with Quicksort. . 11.4.7 Relationship Between RP and ZPP 496 Co-RP::= {Languages L: complement(L) is_a RP }. . Note RP and Co-RP The text remarks that we don't know if the complements of RP languages are also RP or not. . Theorem 11.17 ZPP= RP & co-RP Also see .See http://en.wikipedia.org/wiki/ZPP . Ch 11.4.7 pp 496 -- Relationship between RP/ZPP Can you go over Theorem 11.17 and how RP and ZPP are related? Structure of proof .Let L is RP and complement(L) is RP ... (hyp)|- L is ZPP .Close.Let .Let L is ZPP ... (hyp)|- L is RP and L is co-RP .Close.Let . 11.4.8 Relationships to the Classes P and NP 497 . Theorem 11.18 P ==> ZPP Simple proof. . Theorem 11.19 RP==>NP Simple proof. . Figure 11.8 -- map of P....ZPP Memorize. .Close . Ex The book doesn't have an exercise for this section. Instead find out about Jon Bentley's experience with quick sort at AT&T Labs. This is in a book: "Programming Pearls" (Addison Wesley Reading MA 1986) and was originally published as an article in the ACM's "Communications of the ACM" magazine. This article should be in the ACM digital library and so easily accessible on-line from on-campus. Jon also published another version of the story with Doug McIlroy....can you find it? Bring what you find to class -- hard copy and/or a URL. By the way -- a copy of Bentley's "Programming Pearl's" belongs on every computer programmer's book shelf. .Close 18 . Next -- Prime Numbers .See ./19.html . Notes (Study): Read & think about the assigned items. Submit one question by selecting the submit button at the top of the web page. To earn complete credit you need to do this at least 90 minutes before the start of class. Hints. Read each section twice -- once the easy bits and then the tough bits. Use a scratch pad and pencil as you read. (Topic): To earn all the possible points you must: turn up on time, not leave early, present work when called upon, and take part in discussions.