## CS 101 (Spring 1999) Quiz 5: Iteration

Quiz Posted
(Wednesdays)
Given in class
(Wednesdays)
10 Feb 17 Feb

### Information about quizzes:

• On the date a quiz is given, a die will be thrown by a student in the class.
• Books and notes are put away.
• A question very similar to the chosen published question will be written on the board.
• You have 5 minutes to answer the question.
The questions are intended to be straightforward. If you keep up with the material in the class, almost no preparation may be necessary. The Collaboration Policy allows you to study in groups for the quizzes, but you are on your own when you take the quiz.

You will fare better on the quiz if you try working the problems before looking at the solutions. If you don't understand the question or its answer, please get help.

Directions: In Lab 4, you wrote recursive procedures to implement several arithmetic functions. In these problems, you will implement similar functions using iteration (loops). For each of the following specifications,

• provide an iterative implementation,
• state the loop invariant(s) for the computation, and
• show (informally) that the termination condition and the loop invariant imply that the correct result will be produced.
Doing these on paper is fine, but actually implementing and testing these procedures will give you greater assurance that they work.

1. Write an iterative procedure `expt` with the following specification. Use repeated multiplication. Do not use the built-in exponentiation method. (Yes, this was done in class. Try to do it without looking at your notes.)
```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
```

[ solution ]

Last modified 06:54:35 CST 05 February 1999 by Ron K. Cytron