## CSE 131 Module 3: Iteration

### Practice Problems

Directions: In Lab 2, you wrote recursive procedures to implement several arithmetic functions. In these practice problems, you will implement similar functions using iteration (loops). Provide an iterative implementation for each of the following specifications.

If you are planning to complete the optional extension on loop invariants for this module, you should prepare by additionally:

• stating the loop invariant(s) for the computation, and
• showing (informally) that the termination condition and the loop invariant imply that the correct result will be produced.

1. Write an iterative procedure `expt` with the following specification. Use repeated multiplication. Do not use the built-in exponentiation method.
```PARAMETERS:   integers n and k, with k >= 0
RETURN VALUE: the value of n to the power k
EXAMPLES:     expt(3,2) is 9
expt(5,0) is 1
expt(2,5) is 32
```

2. Write an iterative procedure `harmonicSum` with the following specification.
```PARAMETERS:   a positive integer, n
RETURN VALUE: the sum 1 + 1/2 + 1/3 + ... + 1/(n-1) + 1/n
```

3. Write an iterative procedure called `geometricSum` with the following specification.
```PARAMETERS:   a non-negative integer, k
RETURN VALUE: the sum 1 + 1/2 + 1/4 + 1/8 + ... + 1/(2^k)
```

4. Write an iterative procedure `mult` with the following specification. Use repeated addition. Do not use the multiplication operator.
```PARAMETERS:   integers j and k
RETURN VALUE: the product j*k
```

5. Write an iterative procedure `sumDownBy2` with the following specification.
```PARAMETERS:   a positive integer n
RETURN VALUE: the sum of the positive integers n + (n-2) + (n-4) + ...
EXAMPLES:     sumDownBy2(7) is 7+5+3+1 = 16
sumDownBy2(8) is 8+6+4+2 = 20
```

6. Write an iterative procedure `sumOdd1toN` with the following specification.
```PARAMETERS:   a positive integer n
RETURN VALUE: the sum of all the odd integers between 1 and n, inclusive
EXAMPLES:     sumOdd1toN(7) is 1+3+5+7 = 16
sumOdd1toN(8) is 1+3+5+7 = 16
sumOdd1toN(1) is 1
```

7. The least common multiple (LCM) of two numbers is the smallest number that is a multiple of both. Write an iterative procedure `lcm` with the following specification.
```PARAMETERS:   positive integers j and k
RETURN VALUE: the least common multiple (LCM) of j and k
EXAMPLES:     lcm(3,5) is 15
lcm(6,8) is 24
```