>> [CNS] >> [Comp Sci Dept] >> [R J Botting] >> [CS546/646] >> 18 [Text Version]
Session: [01] [02] [03] [04] [05] [06] [07] [08] [09] [10] [11] [12] [13] [14] [15] [16] [17] (18) [19] [20]
Thu Jun 8 13:03:04 PDT 2006

# 18

## 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
1. 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,
2. 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

#### ERRATA in example 11.12

Replace
1. since m not be a power of 2

By

2. 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 \ win Lnot in L
AcceptsOKfalse +ve
not Acceptsfalse -veOK

### 11.4.4 The Class RP 493 -- Monte Carlo Algorithms

M \ win Lnot in L
Accepts>0.50
not Accepts<0.51
PLUS
1. 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 \ win 0*+1*not in 0*+1*
Accepts>0.52^(-n)
not Accepts<0.51-2^(-n)
The example above is not RP.

### Example 11.15 -- Graphs with triangles

M \ wsome triangleNo triangle
Accepts>0.50
not Accepts<0.51

### 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...

This is an ambiguous section heading. It could mean

1. Use this section to find out if your language is RP or it could mean
2. 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

2. ZPP::="Zero-error Probabilistic Polynomial time".

Does the right thing
M \ win Lnot in L
Accepts10
not Accepts01
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

3. 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

1. L is RP and complement(L) is RP
2. ...
3. (hyp)|-L is ZPP

(Close Let )

Let
1. L is ZPP
2. ...
3. (hyp)|-L is RP and L is co-RP

(Close Let )

### 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.

. . . . . . . . . ( end of section 18) <<Contents | End>>

[ 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.

# Standard Definitions

1. FSA::="Finite State Acceptor/Automata", a theoretical machine with a finite set of states.
2. ND::="Non-deterministic", a machine that can try out many possibilities and always guesses the right choice. Note: For a given problem a ND solution is simpler and easier to understand than a deterministic one. We study ND machines to discover how to use them as high-level designs for more complicated deterministic machines. Plus it's fun.
3. PDA::="Push down Automata", a machine with a finite control and a single stack for remembering intermediate data. Kind of like half a TM.
4. RJB::=The author of this document, [ ../index.html ]
5. |-RJB="Richard J Botting, Comp Sci Dept, CSUSB".
6. Schedule::= See http://www.csci.csusb.edu/dick/cs546/schedule.html.
7. Search::= See http://www.csci.csusb.edu/dick/cs546/lookup.php.
8. Syllabus::= See http://www.csci.csusb.edu/dick/cs546/syllabus.html, and also see [ syllabus.html ] (my generic syllabus).
9. TBA::="To Be Announced".
10. TM::="Turing Machine".
11. NTM::="Nondeterministic Turing Machine".
12. nondeterministic::="A machine that can make choices as it runs and accepts an input iff any sequence of choices leads to acceptance."
13. DTM::="Deterministic Turing Machine".
14. runtime::=run_time,
15. run_time::="The number of steps a TM takes before it halts when start on a given input".
16. complexity::="The largest run_time for any word with a given length" , usually expressed as an assymptotic (Big-O) formula.
17. P::@problem=class of problems that a DTM can compute in polynomial_time.
18. NP::@problem=class of problems that a NTM can compute in polynomial_time.
19. polynomial_time::=An algorithm/TM is said to halt in polynomial time if the number of steps given n items of data is less than O(n^c) for some constant c.

# From Logic

20. LOGIC::= See http://www.csci.csusb.edu/dick/maths/logic_25_Proofs.html

21. (LOGIC)|- (ei): Existential instantiation -- if P is true of something then we can substitute a new variable for it.
22. (LOGIC)|- (eg): existential generalization -- if P is true of this thing then it is true of something!
23. (LOGIC)|- (given): a proposition that is assumed as part of a Let...End Let argument. Typically if A and B and C then D starts with assuming A,B, and C are given. They are called the hypotheses.
24. (LOGIC)|- (goal): a proposition that we wish to prove. Typically the part after the then in an if...then... result. This is called the conclusion.
25. (LOGIC)|- (def): By definition of a term defined above.
26. (LOGIC)|- (algebra): Either by using well known algebraic results, or by use a series of algebraic steps.
27. (LOGIC)|- (RAA): Reduce to absurdity. The end of a Let/Po/Case/Net that establishes the negation of the last set of assumptions/hypotheses.