15.9: Exercises

Last updated
Save as PDF

Page ID: 18907

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

The code for this chapter is in the ch07 directory of ThinkJavaCode. See [Section 0.4] for instructions on how to download the repository. Before you start the exercises, we recommend that you compile and run the examples.

If you have not already read Appendix A.5, now might be a good time. It describes Checkstyle, a tool that analyzes many aspects of your source code.

Exercise \(\PageIndex{1}\)

Consider the following methods:

public static void main(String[] args) {
    loop(10);
}
public static void loop(int n) {
    int i = n;
    while (i > 1) {
        System.out.println(i);
        if (i % 2 == 0) {
            i = i / 2;
        } else {
            i = i + 1;
        }
    }
}

Draw a table that shows the value of the variables i and n during the execution of loop. The table should contain one column for each variable and one line for each iteration.
What is the output of this program?
Can you prove that this loop terminates for any positive value of n?

Exercise \(\PageIndex{2}\)

Let’s say you are given a number, a, and you want to find its square root. One way to do that is to start with a rough guess about the answer, x₀, and then improve the guess using this formula:

\[ x_{1} = (x_{0} + a/x_{0})/2 \nonumber \]

For example, if we want to find the square root of 9, and we start with \(x_{0} = 6\), then \(x_{1} = (6 + 9/6) / 2 = 3.75\), which is closer. We can repeat the procedure, using \(x_{1}\) to calculate \(x_{2}\), and so on. In this case, \(x_{2} = 3.075 \) and \(x_{3} = 3.00091\). So it converges quickly on the correct answer.

Write a method called squareRoot that takes a double and returns an approximation of the square root of the parameter, using this technique. You should not use Math.sqrt.

As your initial guess, you should use \(a/2\). Your method should iterate until it gets two consecutive estimates that differ by less than \(0.0001\). You can use Math.abs to calculate the absolute value of the difference.

Exercise \(\PageIndex{3}\)

In Exercise 6.11.9 we wrote a recursive version of power, which takes a double x and an integer n and returns \(x^{n}\). Now write an iterative method to perform the same calculation.

Exercise \(\PageIndex{4}\)

Section 6.7 presents a recursive method that computes the factorial function. Write an iterative version of factorial.

Exercise \(\PageIndex{5}\)

One way to calculate \(e^{x}\) is to use the infinite series expansion:

\[e^{x} = 1 + x + x^{2} / 2! + x^{3} / 3! + x^{4} / 4! + \dots \nonumber \]

The ith term in the series is \(x^{i} / i!\).

Write a method called myexp that takes x and n as parameters and estimates \(e^{x} \) by adding the first n terms of this series. You can use the factorial method from Section 6.7 or your iterative version from the previous exercise.
You can make this method more efficient if you realize that the numerator of each term is the same as its predecessor multiplied by x, and the denominator is the same as its predecessor multiplied by i. Use this observation to eliminate the use of Math.pow and factorial, and check that you get the same result.
Write a method called check that takes a parameter, x, and displays x, myexp(x), and Math.exp(x). The output should look something like:
```
1.0 2.708333333333333 2.718281828459045
```
You can use the escape sequence "\\t" to put a tab character between columns of a table.
Vary the number of terms in the series (the second argument that check sends to myexp) and see the effect on the accuracy of the result. Adjust this value until the estimated value agrees with the correct answer when x is 1.
Write a loop in main that invokes check with the values \(0.1, 1.0, 10.0,\) and \(100.0\). How does the accuracy of the result vary as x varies? Compare the number of digits of agreement rather than the difference between the actual and estimated values.
Add a loop in main that checks myexp with the values \(-0.1, -1.0, -10.0,\) and \(-100.0\). Comment on the accuracy.

Exercise \(\PageIndex{6}\)

One way to evaluate \( exp(-x^{2}) \) is to use the infinite series expansion:

\[ exp(-x^{2}) = 1 - x^{2} + x^{4}/2 - x^{6}/6 + \dots \nonumber \]

The ith term in this series is \((-1)^{i} x^{2i} / i!\). Write a method named gauss that takes x and n as arguments and returns the sum of the first n terms of the series. You should not use factorial or pow.