Schedule
Date
 Meet'g
 Study(2 pts)
 Bring(5 pts)
 Topic(5 pts)
 Notes


Wed May 31
 17
 Chapter 11 sections 11.1, 11.2, 11.3
 Ex
 CoNP & PSPACE

Mon Jun 5
 18
 Chapter 11 sections 11.4
 Ex
 Randomization RP ZPP

Wed Jun 7
 19
 Chapter 11 sections 11.5, 11.6
 Ex
 Primality

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.
To evaluate \pi
 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).
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).
[ citation.cfm?id=1045972&dl=GUIDE&coll=GUIDE ]
[ 358027.381121 ]
[ bentley.html ]
From: Minhchau Dang, Stephen Collins, Jason Hunt, Scott McAllister, and Raini Armstrong, Jedidah Mwangi
[ bentley93engineering.pdf ]
Ch 11.4 pp 487488  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....
Jon Bentley has written an article explaining what happens
to a program who does not randomize quick sort! See Ex below.
11.4.2 A TuringMachine Model Using Randomization 489
Example 11.12 Quicksort on a randomized TM
ERRATA in example 11.12
Replace
 since m not be a power of 2
By
 since m may not be a power of 2.
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 ?
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 multitape sort. We did not use quicksort.
A polyphase nway 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).
11.4.3 The Language of a Randomized Turing Machine 490
The following table of possibilities may help explain the options
M \ w  in L  not in L


Accepts  OK  false +ve

not Accepts  false ve  OK

Example 11.13  Homogeneous strings 0*+1*
Could you Please explain the table on figure 11.7
M \ w  in L  not in L


Accepts  >0.5  0

not Accepts  <0.5  1

PLUS
 M must accept in polynomial time.
Can you give an example of a problem in RP but not P?
Errrrr.... No!
M \ w  in 0*+1*  not in 0*+1*


Accepts  >0.5  2^(n)

not Accepts  <0.5  12^(n)

The example above is not RP.
Example 11.15  Graphs with triangles
M \ w  some triangle  No triangle


Accepts  >0.5  0

not Accepts  <0.5  1

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.
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::="Zeroerror Probabilistic Polynomial time".
Does the right thing
M \ w  in L  not in L


Accepts  1  0

not Accepts  0  1

But the time is random and its AVERAGE is O(n^k) for some k.
Compare with Quicksort.
 CoRP::= {Languages L: complement(L) is_a RP }.
Note RP and CoRP
The text remarks that we don't know if the complements of
RP languages are also RP or not.
Theorem 11.17 ZPP= RP & coRP
Also see
[ 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 coRP
(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.
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 online from oncampus. 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.