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
| Co-NP & 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.
Bad Example of a Random Algorithm -- the dart board \pi calculator
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 ]
Programming Pearl from Brian Strader
[ 358027.381121 ]
Jon Bentley and quicksort -- Mike Schick
[ bentley.html ]
QuickSort Article by Bentley and McIlroy
From: Minhchau Dang, Stephen Collins, Jason Hunt, Scott McAllister, and Raini Armstrong, Jedidah Mwangi
[ bentley93engineering.pdf ]
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.
11.4.2 A Turing-Machine 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 ?
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).
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
11.4.4 The Class RP 493 -- Monte Carlo Algorithms
| M \ w | in L | not in L
|
|---|
| Accepts | >0.5 | 0
|
| not Accepts | <0.5 | 1
|
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
| M \ w | in 0*+1* | not in 0*+1*
|
|---|
| Accepts | >0.5 | 2^(-n)
|
| not Accepts | <0.5 | 1-2^(-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::="Zero-error 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.
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
[ 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.
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.