CS101 Quiz 5: Solutions

Keep in mind that there are many possible correct solutions to each problem. Ask if you are surprised by any of these answers, or if you are unsure of your answer.
1.  int expt(int n, int k) {  // assumes k >= 0
        int n_pow_i = 1;
        int i = 0;
        // loop invariant: n_pow_i = n^i
        while (i < k) {
            n_pow_i *= n;
            i++;
        }
        // on termination, i=k, so n_pow_i = n^k
        return n_pow_i;
    }

2.  double harmonicSum(int n) { // assumes n>0
        double sum = 1;
        double denom = 1;
        // loop invariant: sum = 1 + 1/2 + 1/3 + ... + 1/denom
        while (denom < n) {
            denom += 1;
            sum += 1/denom;
        }
        // on termination, denom=n so sum = 1 + 1/2 + 1/3 + ... + 1/n
        return sum;
    }

3.  double geometricSum(int n) { // assumes n >=0
        double sum = 1;
        int k = 0;
        double denom = 1;
        // loop invariants:  sum = 1 + 1/2 + 1/4 + ... + 1/2^k
        //                   denom = 2^k
        while (k < n) {
            k++;
            denom *= 2;
            sum += 1/denom;
        }
        // on termination, k=n so sum = 1 + 1/2 + ... + 1/2^n
        return sum;
    }

4.  int mult(int j, int k) {
        if (j < 0)
            return -mult(-j,k);
        else {
            int product = 0;
            int count = 0;
            // loop invariant: product = k*count
            while (count < j) {
                product += k;
                count++;
            }
            // on termination, count=j so product=k*j
            return product;
        }
    }

5.  int sumDownBy2(int n) { //assumes n>=0
        int k = n;
        int sum = n;
        // loop invariant: sum = n + (n-2) + (n-4) + ... k
        while (k > 1) {
            k -= 2;
            sum = sum + k;
        }
        // on termination, k = 1 or 0, so
        //    sum = the sum of the positive integers n, n-2, n-4,...
        return sum;
    }

6.  int sumOdd1toN(int n) { // assumes n>0
        int sum = 1;
        int i = 1;
        // loop invariants: sum = 1 + 3 + 5 + ... + i
        //                  i is odd
        while (i+2 <= n) {
            i += 2;
            sum += i;
        }
        // on termination, i=n (if n is odd) or i=n-1 (if n is even), so
        //    sum = the sum of the odd numbers from 1 up to n
        return sum;
    }


7.  int lcm(int j, int k) { // assumes k != 0
        int guess = j;
        // loop invariant: guess is a multiple of j.
        while ((guess % k) != 0)
           guess += j;
        // on termination, guess is a multiple of k.
        // since the loop tries each multiple of j, the smallest
        // such multiple that is also a multiple of k is returned.
        return guess;
    }