EX2

  1. What is the appropriate loop invariant for the following program fragment, which sets sum equal to the sum of the integers from 1 to n?
  2. 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.

  3. The following program fragment computes the sum of the integers in array A[0…n-1]:
  4. 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?

  5. Draw the profiles of the following strings of parentheses:
    1. (()(())
    2. ()())(()
    3. ((()())()())
    4. (()(()(())))
  6. Tell whether each of the following JAVA operators is prefix, postfix, or infix, and wheter they are unary, binary, or k-ary for some k>2.
    1. <
    2. &
    3. %
  7. A certain set of S integers is defined recursively by the following rules
  8. Basis: 0 is in S

    Induction: If i is in S, then i + 5 and i +7 are in S.

    1. What is the largest integer not is S?
    2. Let j be your answer to part (a). Prove that all integers j+1 and greater are in S.
  9. Suppose that we are given array A[0..4], with elements 10, 13, 4, 7, 11, in that order. What are the contents of the array A just before each recursive call to recSS, according to the recursive function below?
  10.  

    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);

    }

    }

  11. Write a recursive method add that takes an argument of type Node, as defined below, and returns the sum of the elements in the list.
  12. public Class Node {

    public int element;

    public Node next;

    }

  13. The greatest common divisor (GCD) of two integers I and j is the largest integer that divides both i and j evenly. For example, gcd(24,30) == 6, and gcd(24,35) == 1. Write a recursive function that takes two integers i and j, with i > j, and returns gcd(i,j). Hint: You may use the following recursive definition of gcd. It assumes that i > j.
  14. 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).

  15. Assume two list of Nodes (from question 7) the first list contains (1,2,3,4,5), the second (2,4,6,8,10). Show the result of applying the function merge, below, to the two lists.
  16. 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;

    }

  17. Prove that the function PrintList, below, prints the elements on the list that is passed as an argument. What statement S(i) do you prove inductively? What is the basis value for i?

void PrintList(Node list) {

while (list != NULL) {

System.out.println((list.element).toString());

list = list.next;

}

}