Grading Guide for Assignment 6.

On all questions, the grade depends on whether the loop is consistent
with the invariant. It doesn't matter at all whether the loop does the
job or not; it MUST be consistent with the invariant. For example, if
the invariant says 

    P:  x is not in b[0..k-1]
   
but the initialization is k= 1;, then the students gets
0 out of 3 points for the initialization, because it does not make
P true. (In this case, the correct initialization is: k= 0;.)

The only parts that requires running the progam is Question 1 part a.


Question 1. Part a (28 points).
5 points: The program compiles
5 points: Execution of the program does what it's supposed to do
(look at spec of method buttonPressed in sample solution given below)

2 points for good method spec and invariant
4 points for initialization truthifying the invariant
4 points for the right loop condition
4 points for the loop body making progress toward termination
4 points for the loop body keeping the invariant true

Question 1. Part b (8 points).
Give 1 point for each of the 8 questions.

Question 2 (18 points).
2 points for good method spec and invariant
4 points for initialization truthifying the invariant
4 points for the right loop condition
4 points for the loop body making progress toward termination
4 points for the loop body keeping the invariant true

Question 3 (18 points).
2 points for good method spec and invariant
4 points for initialization truthifying the invariant
4 points for the right loop condition
4 points for the loop body making progress toward termination
4 points for the loop body keeping the invariant true

Question 4 (18 points).
2 points for good method spec and invariant
4 points for initialization truthifying the invariant
4 points for the right loop condition
4 points for the loop body making progress toward termination
4 points for the loop body keeping the invariant true

Question 5 (18 points).
2 points for good method spec and invariant
4 points for initialization truthifying the invariant
4 points for the right loop condition
4 points for the loop body making progress toward termination
4 points for the loop body keeping the invariant true


Question 1. Part (a)
// = binary representation of nonnegative integer n
public static String binaryRep(int n) {
    int m=  n;
    String s=  "";
	// inv: n  =  m*2**k + (int represented by s)
	//      (for some k)
	while (m != 0) {
		// Prepend next digit to s
		    int d= m%2; // Note: 0 <= d <= 9
			s=  (char)(d + Œ0¹) + s;
	    m= m/2;
   }
   
// Display in String field 0 the binary
// representation of the integer in int field 0
// and return null.
public Object buttonPressed() {
    int n= getIntField(0);
    setStringField(0,binaryRep(n));
    return null;

}

Part (b) (1)
The binary representation of 2**2 is 100
The binary representation of 2**3 is 1000
The binary representation of 2**4 is 10000
The binary representation of 2**n is 1 followed by n zeros.

Part (b) (2)
The binary representation of 2**4-1 is 1111
The binary representation of 2**5-1 is 11111
The binary representation of 2**6-1 is 111111
The binary representation of 2**n-1 is a sequence of n 1's.

Question 2.
    // = index of first odd value in b[h..k] (k+1 if none)
    public static int firstOdd(int[] b, int h, int k) {
        int p= h;
        // inv: b[h..p-1] contains only even values
        while (p != k+1 && b[p] % 2 == 0) {
            p= p+1;
        }
        return p;
    }

Question 3: 
    // Sort b[h..k]
    public static void selectionsort(int b[], int h, int k) {
        int p= k+1;
        // inv: b[p..k] is sorted and b[h..p-1] <= b[p..k]
        // bound function t: p-h
        while (p != h) {  // (could also use p != h-1)
            int max;
            // Store in max the index of largest elem. of b[h..p-1]
                max= h;
                // inv: b[max] is the largest of b[h..m-1]
                // bound function: p-m
                for (int m= h+1; m != p; m= m+1) {
                    if (b[m] > b[max])
                        max= m;
                }
            p= p-1;
            // Swap b[max] and b[p]
                int t= b[max]; b[max]= b[p]; b[p]= t;
        } 
    }
   
Question 4:
    // = the integer whose binary rep is b[0..k-1]
    public static int intBinary(int[] b, int k) {
        int p= 0;
        int n= 0;
        int exp= 1;
        // inv: exp = 2**p  and
        //      n is the integer represented by b[h..k-1]
        while (p != k) {
            if (b[p] == 1)
                { n= n+exp; }
            exp= 2*exp;
            p= p+1;
        }
        return n;
    }
        
Question 5.
    // = gcd(a,b), for a>0, b>0
    public static int gcdloop(int a, int b) {
        int p= a;
        int q= b;
        // invariant: gcd(a,b) = gcd(p,q)
        while (p != q) {
            if (p>q) p= p-q;
            else q= q-p;  
        }
        return p;
   
    }