CS 12 - Homework Assignment 1

CS 12 Homework Assignment 1

This assignment is due on Tuesday, October 7, 2003, at the start of the lecture. You must hand your solutions on paper, and printed (ie, not hand-written). Please staple your solutions.

1. [3 points] Suppose I gave you a sequence of integer numbers (not necessarily positive or even distinct). 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, but don't write an essay. Instead, give short instructions of the form "pick the fifth number" or "square the number you selected", etc.

2. [3 points] 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, namely, x2 = x1 / 2 + 1 / x1. Then compute x3 by applying the same formula again, this time to x2, 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, that is, 1.41421356...

a. [2 points] Let's try that. Choose a number for x0 and then write the result of computing the first 10 numbers of the sequence, that is, print the values of { x0, x1, x2, ..., x9, x10 } for your choice of x0. You might want to use a calculator.

b. [2 points] Now 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.

c. [3 points] Next, write a small C++ program with a 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 computing and printing x1 = f(x0), x2 = f(x1), x3 = f(x2), etc, maxIters times.

In your solution, show your complete program and also a printout of a few trial runs.

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

5. [3 points] 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.