EX2
int sumer (int n) {
int sum = 0;
for (int i = 1 ; i<= n; i++)
sum = sum + i ;
return sum;
}
Prove your loop invariant by induction on i, and use it to prove that the program works as intended.
int sumer2 (int A[]) {
int sum = 0;
for (int i = 0 ; i< A.length; i++)
sum = sum + A[i] ;
return sum;
}
What is an appropriate loop invariant? Use it to show that the fragment works as intended.
3) Find the largest value of n for which the program below works on your computer.
int factorial (int n) {
int i = 2;
int fact = 1;
while (i <= n){
fact = fact * i ;
i++;
}
return fact;
}
What are the implications of fixed-length integers for proving programs correct?
Basis: 0 is in S
Induction: If i is in S, then i + 5 and i +7 are in S.
int recSS (int A[], int i) {
int small, temp ;
if (i < A.length) {
small = i ;
for (int j = 0 ; j < A.length; j++)
if (A[j] < A[small])
small = j ;
temp = A[small];
A[small] = A[i];
A[i] = temp;
RecSS(A,i+1);
}
}
public Class Node {
public int element;
public Node next;
}
Basis: If j divides i evenly, then j is the GCD of i and j.
Induction: If j does not divide i evenly, let k be the remainder when i is divided by j. Then gcd(i,j) is the same as gcd(i,k).
Node merge(Node list1, Node list2) {
if (list1 == NULL) return list2 ;
else if (list2 == NULL) return list1;
else if (list1.element <= list2.element) {
List1.next = merge(list1.next, list2);
Return list1;
}
else {
list2.next = merge(list1,list2.next);
return list2;
}
return null;
}
void PrintList(Node list) {
while (list != NULL) {
System.out.println((list.element).toString());
list = list.next;
}
}