Discrete Mathematics for Computer Science

Chapter Review 329

(b) Trace through the execution of the code on the set C = {Pl V P2, P1 V

"-P2, -IP V P2, -P11 V -P2} (so, for n = 2). Show what each Ci is after lines 8,

18, and 28. If the algorithm stops with a "stop" command, say what step caused

it to stop.

(c) Suppose C contains all possible clauses on the n proposition letters pl,

P2 ..... Pn. Prove that the test in step 30 will be executed exponentially (in n)

many times.

(d) Challenge: Prove that GreedySAT correctly determines whether C is satisfiable.

11. Consider the following two algorithms to check whether a number n is prime. Let
    computation of mod be the key operation.
    The first algorithm directly reflects the definition of "prime." Primality testing
    has been used in cryptography (secret coding), particularly in building "public key
    cryptograms."

INPUT: An integer n > I

OUTPUT: "prime" or "composite"

for d = 2 to n - 1

if mod(n, d) = 0

output "composite" and stop

output prime

Algortm Shree rialt es

INPUT: An integer n > t

OUTPUT: "prime" or "composite"

d=2

while (d^2 < n)

if mod(n, d) = 0

output "composite" and stop

d=d+1

output prime

(a) Show that if n is a k digit prime number, SimplestPrimalityTest executes the key oper-
ation approximately 1 0k times.