CS 12 - Homework Assignment 1

CS 12 Homework Assignment 1

This assignment is due on Wednesday, July 30, 2003, at the start of the lecture. You may hand your solutions on paper, but please write legibly.

1. Suppose I gave you a sequence of integer numbers (not necessarily positive or even distinct), one at a time. In English, without using any C++ code at all, explain how you could determine the smallest number of the entire sequence. Be as explicit and precise in your argument as possible.

2. Now write a function int min(int a[], unsigned int length), taking as arguments an array of integers and its corresponding length, that determines and returns the smallest integer present in the array.

3. Here's a cool, but mysterious, way to numerically compute the square root of 2: start with any non-zero number, call it x0, then compute the number x1 = x0 / 2 + 1 / x0. Now that you have x1, compute x2 by applying the same formula to x1, x2 = x1 / 2 + 1 / x1. Then compute x3 = x2 / 2 + 1 / x2, and so on. You will notice that the sequence of numbers { x0, x1, x2, x3, ... } converges fairly quickly to the numerical value of the square root of 2, namely, 1.41421356...

Let's try that. Write a function float f(float x), taking for argument a number x (not necessarily an integer), which applies the formula above to x, returning the result. In other words, you must implement the function f(x) = x / 2 + 1 / x.

Next, write your main function in such a way that it asks the user for a non-zero starting number x0 and for a maximum number of iterations, maxIters, then repeatedly applies f() to the result obtained from the previous application of f(), printing the result every time, and doing it maxIters times. In other words, your main function will be printing f(x0), f(f(x0)), f(f(f(x0))), f(f(f(f(x0)))), etc, maxIters times.

4. Explain why you must not use integers for the argument and the return type of the function f() of the previous problem.

5. Now repeat problem 3., but with two modifications: (a) your main function must ask for yet another number from the user, N, whose square root you will compute, (b) your function f() now has two arguments and must compute the result of the formula f(x, N) = (x + N / x) / 2.