From mliskov@lark.lcs.mit.edu Tue Oct 10 20:19:32 2000 Date: Tue, 10 Oct 2000 20:19:06 -0400 (EDT) From: Moses Liskov To: Nancy Lynch Subject: Re: exam > Moses, > > I looked over the exam in the directory. It looks nice. > At the moment, I think we're light on the state machine stuff. Only > one problem, and it's the most recent thing they'll be doing (3 > lectures). I had thought of a question for that. A simple state machine question using invariants: The following describes an algorithm that, given a number, produces the prime factorization of that number. The prime factorization of a number can be represented as a list of all the prime numbers that divide that number, where each prime is listed multiple times if it divides the number more than once. Assume that the Append function takes a list and an element, and adds that element to the end of that list. FactorPrime (n): 1. i := 2. 2. List := Empty List. 3. m := n. 4. If m := 1 then return (List). 5. If i|m then { 5a. Append (List, i) 5b. m := m/i 6. Else i := i+1 7. Go to step 4. (a) (5 points) Represent this algorithm as a state machine. In what states will there be no transitions? Answer: The states of the machine are triples (i, m, List). The start state is (2, n, ()). The transitions are nothing if m = 1, and otherwise, (i, m, List) -> (i+1, m, List) when i doesn't divide m, and (i, m/i, Append(List, i)) when i does divide m. The algorithm finishes when m = 1, so those states are the only ones with no transitions out. (b) (10 points) Using an invariant, prove that the algorithm always outputs the prime factorization of its input $n$ if it terminates. Answer: The following is the invariant we will use. P(q) = "m times the product of all numbers in List equals n, and List contains no non-prime numbers, and no prime numbers (other than 1) less than i divide m." In the start state (2, n, ()), this is true. The list is empty, so the product of all numbers in it is considered to be 1. 1*n = n. Furthermore, the list contains no numbers at all so it cannot contain any non-prime numbers. Finally, there are no prime numbers less than 2 other than 1. Now suppose we know that P(q) is true. We will prove that P(\delta(q)) is true. There are two cases: (i) i|m. Then, \delta(q) is the state (i, m/i, Append(List,i)) First note that if the product of all numbers in list was $k$, the product of all numbers in Append(List, i) would be $ki$. Therefore, since $km = n$ then $(ki)(m/i) = km = n$ also. Secondly, if no prime numbers less than $i$ divide $m$, then no prime numbers less than $i$ divide $m/i$ since $m/i$ divides $m$. Next, we must prove that Append(List, i) contains no prime numbers. The only element in Append(List, i) that is not in List (which we know contains no prime numbers) is i. Thus, we are asked to prove that i is prime. Suppose $i$ is not prime. Then $i$ has a prime factor smaller than $i$ other than 1: call it $h$. Since $h|i$ and $i|m$ we know that $h|m$. But, since P(q) is assumed, there can be no prime numbers smaller than $h$ other than 1 which divide $m$. Thus, by contradiction, we see that $i$ is prime. Therefore, P(\delta(q)). case ii: i does not divide m. Then, \delta(q) is the state (i+1, m, List). First notice that since List did not change and neither did m, then $m$ times the product of all numbers in List must still be equal to $n$. Secondly, since List did not change, it cannot contain any non-prime numbers, since P(q) is true. Finally, we must verify that no primes less than $i+1$ other than 1 divide $m$. The only number less than $i+1$ which is not less than $i$ is $i$ itself. Since we know that $i$ does not divide $m$, we see that $i$ cannot be a prime less than $i+1$ which divides $m$. Therefore, P(\delta q). By the invariant theorem, the function stops in a state in which $m$ times the product of all numbers in List is equal to $n$. Since it only stops when $m$ = 1, this means the product of all the numbers in List (which is what is output) is equal to $n$. Futhermore, we know there are no nonprime numbers in List, so List must be the prime factorization of $n$. (c) (5 points) Prove that this algorithm always terminates. (You may take it for granted that $m >= i$ at any stage of the algorithm except when $m = 1$. Answer: The following is a termination function: f(q) = n+m-i. Note that if we increase i, this decreases f(\delta q) by 1. If we do not increase i, we divide m by i. This decreases f(\delta q) by a factor of m(i-1)/i. This is always positive, since if $i|m$ then $i|n$ so by the time we reach $i = n$ we must stop. Then, the lowest value of the function is when $m = 1$ and $i = n$, where f evaluates to 1. By the termination function, the algorithm terminates.