Web Page
Suggested Review
Prime
A natural number N is prime if it has no
divisors other than 1 and itself
Write a function isAPrime that returns true if N is prime and false otherwise
public boolean isAPrime (int N) {
\\ brute force approach check each number
\\ and see if it divides N
for (int i=2;i < N;i++)
if (N % i == 0) // N is divisible by i
return false;
return true;
}
How many times is N % i == 0 executed
# of divides Time taken N is prime N - 1 = O(N) N is composite sqrt(N) = O(sqrt(N))
Improvements
We can improve this by noticing that any composite number must have at least two factors and the smallest factor cannot be larger than sqrt(N) in size. So we can limit the number of iterations to sqrt(N) - 1.
We can also halve this by dividing N by 2 and thereafter divide only by odd numbers so that we do only sqrt(N)/2 - 1 iterations
public boolean isAPrime (int N) {
if (N == 2) return true;
else if (N % 2 == 0) return false;
else {
for (int i=2;i <= sqrt(N);i++)
if (N % i == 0) // N is divisible by i
return false;
return true;
}
}
Fibonacci's rabbits
A certain man put a pair of rabbits in a place surrounded on all sides by a wall. How many pairs of rabbits can be produced from that pair in a year if it is supposed that every month each pair begins a new pair which from the second month on becomes productive?
number pairs generations month of rabbits 1st 2nd 0 1 o 1 1 o 2 2 o-------->o 3 3 o----->o o 4 5 o-->o o o-->o
The number of rabbits at any month n
>
1, f(n) is equal to:
the number of mature rabbits, f(n-2) plus
their current month's offspring, f(n-2) plus
the number of immature rabbits, f(n-1) - f(n-2).
which is equivalent to:
f(n) = f(n-1) + f(n-2)
Fibonacci numbers
recursive definition
f(0) = 1
f(1) = 1
f(n) = f(n-1) + f(n-2)
Recursive solution
public int f (int n) {
if (n < 2) return 1;
else
return f(n-1) + f(n-2);
}
The solution uses double recursion and is inefficient because it duplicates work. The number of recursive calls and additions equals f(n) So it runs in O(f(n)) time which grows exponentially f(n) . The iterative solution runs in O(n) time.
Program Correctness
Consider this program segment.
How do you convince youself
of its correctness?
% sum the first N positive integers
% PRECONDITION: N >= 0
final int N = 10; // or read in n
int sum = 0; // total so far
var count = 0; // integers included in "sum"
while (true) {
if (count == N) break; // I is true here ***
count = count + 1; // I is false
sum = sum + count; // I is true
}
System.out.println(sum);
// POSTCONDITION: sum = 0 + 1 + 2 + ... + N
Prove that the program produces the desired result
sum == 0 + 1 + 2 + 3 + ... + N
this is called the postcondition.
Formally the statement 'this program is correct' means that if the precondition, N >= 0 is true the postcondition follows after a finite number of steps. Informally, precondition and executing the program imply postcondition.
How do we do this? First we must understand what a loop invariant and what termination are.
There can be many loop invariants. We need to choose the one that is useful in proving program correctness.
An invariant is a function I : N -> {true,false}
In this case the most useful Loop Invariant I(n) is
n == the_number_of_times_passed *** and
count == n and
sum == 0 + 1 + 2 + 3 + ... + count
Proving Termination in this case means to prove that eventually
N == count so that the while loop exits.
To show the program is correct we only have to prove a loop invariant and that the program eventually terminates since the precondition and the loop invariant and termination of the loop (and the program) imply the postcondition.
pre and for all n, I(n) and termination => post.
Proof:
By induction on the_number_of_times_passed ***Base case 0 times past *** Prove I(0)
I(0) is sum = 0 and count = 0 which is correct If N == count then the loop exits at *** and we are done. otherwise N > 0 Assume we are given a fixed but arbitrary N > 0
Inductive step
Now assume that I(n) is true after n times past ***
If n == N then count == N and we would exit at *** and would be done
so 1 <= count < N then after one more iteration
countn+1 = countn + 1
= n + 1 by the induction hypothesis
sumn+1 = sumn + countn+1
= (1 + 2 + ... + n) + n + 1 by the induction hypothesis
which is correct. So we have proven the induction.
We only have to prove that the loop eventually exits
-1 < 0 and 0 < N - countn
=> 0 < N - countn - 1 < N - countn
=> 0 <= N - (countn + 1) < N - countn
=> 0 <= N - countn+1 < N - countn
so we are making progress and eventually
0 = N - count or equivalently
N == count
Since N was chosen arbitrarily it is true for any N.