JAVA Homework Interval Halving Objective The goal of this ho

JAVA

Homework: Interval Halving

Objective

The goal of this homework is to \"discover\" an algorithm for finding integer roots, such as 823823 and 74498157449815.

Note: In mathematics, the notation denotes the \"rounding down\" (or \"floor\") function that \"throws away\" the fractional part of a real number. For example, 18.432=1818.432=18, 18.69=1818.69=18, and 0.9934=00.9934=0. Similarly, denotes the \"rounding up\" (or \"ceiling\") function, and 18.432=1918.432=19, 18.69=1918.69=19, and 0.9934=10.9934=1.

A Fast Algorithm for Searching

Consider the following guessing game: one player picks an integer value, call it secret_number, such that 0 secret_number < 1001; the other player tries to guess the secret_number and after each guess the first player only tells the second player whether secret_number < guess_number. This is the only question the first player is allowed to answer and therefore the only piece of information the second player receives after each guess. What strategy would you follow to try and guess the secret_number in as few guesses as possible?

There are many different strategies that could be chosen, some better than others; with many strategies you will be lucky sometimes and find the secret_number in very few guesses, but you will find that more often than not you will need quite a few guesses. There is, however, one particular strategy that is guaranteed to always lead to the correct answer in no more than 10 guesses. Can you guess how it works?

Basically the idea is to start with a low bound, lowEnough, and a high bound, tooHigh, on the possible secret_number. In this case, clearly lowEnough = 0 and tooHigh = 1001. The first guess is the number in the middle of the [lowEnough, tooHigh) interval, i.e., (lowEnough + tooHigh) / 2 or 500 in the example. There are two possibilities: (1) secret_number < 500 (the guess_number), then the secret_number must be in the interval [0, 500), in other words, we update the high bound so that tooHigh = 500; (2) it is not the case that secret_number < 500 and secret_number must be in the interval [500, 1001), and we update the low bound so that lowEnough = 500. Note that in one guess we have already reduced the space of possible answers to half of the original range. Let\'s say that indeed our first guess was too low, so we know the secret_number must be in the interval [500, 1001). Let\'s do it all over again. The next guess is the number in the middle of the new [lowEnough, tooHigh) interval, [500, 1001), i.e., 750. Depending on whether secret_number < 750 or not, we update tooHigh or lowEnough, respectively, and continue in the same fashion. Before long we\'ll find the secret_number, guaranteed.

This algorithm is an example of an interval halving or binary search strategy. Its efficiency comes from the property that at each step we eliminate half of the interval of possible solutions. In the following homework questions you will discover how interval halving can be used to efficiently find integer roots.

The Questions

Carefully consider and answer the following questions.

Suppose someone claims that 823=4823=4. How would you verify whether 823=4823=4 using powers of 4 and powers of 5? Is 823=4823=4?

Suppose that n, r, and root denote integer values where r > 0 and n 0. Further, suppose that rootrn<(root+1)rrootrn<(root+1)r. Can we conclude that root=nrroot=nr? Carefully justify your answer.

Suppose that n and r denote integer values where r > 0 and n 0. Further, suppose you would like to know nrnr. When finding nrnr by a guess and verify method, is there any reason to try a guess, say g, where g < 0? Explain your answer. Similarly, is there any reason to try a guess g where g > n? Explain.

Again, suppose that n and r denote integer values where r > 0 and n 0. What are two \"simple\" values, say lowEnough and tooHigh, such that lowEnough nrnr < tooHigh. Explain based on your answer to the previous question.

Suppose you would like to know 472265472265. Explain how you could find 472265472265 using a guess and verify method. Note: Explain your answer by relating this problem to the number guessing game described earlier. Think about what would be an appropriate question to use in place of \"Is secret_number < guess_number?\" and think about good choices for the starting values of lowEnough and tooHigh.

Assume you are given the power method specified as follows:

/**

* Returns {@code n} to the power {@code p}.

*

* @param n

*            the number to which we want to apply the power

* @param p

*            the power

* @return the number to the power

* @requires Integer.MIN_VALUE <= n ^ (p) <= Integer.MAX_VALUE and p >= 0

* @ensures power = n ^ (p)

*/

private static int power(int n, int p) {...}

Use your answers to the previous questions to implement the root method specified below. Be sure to use the idea of interval halving.

/**

* Returns the {@code r}-th root of {@code n}.

*

* @param n

*            the number to which we want to apply the root

* @param r

*            the root

* @return the root of the number

* @requires n >= 0 and r > 0

* @ensures root ^ (r) <= n < (root + 1) ^ (r)

*/

private static int root(int n, int r) {...}

Additional Questions

In the number guessing game, how many guesses at most will be needed to guess a secret number in the interval [0, n) where n > 0 when using the interval halving strategy discussed above?

Explain how you answered the previous question.

/** * Returns {@code n} to the power {@code p}. * * @param n *            the number to which we want to apply the power * @param p *            the power * @return the number to the power * @requires Integer.MIN_VALUE <= n ^ (p) <= Integer.MAX_VALUE and p >= 0 * @ensures power = n ^ (p) */ private static int power(int n, int p) {...}

Solution

import components.simplewriter.SimpleWriter;
import components.simplewriter.SimpleWriter1L;

public final class IntegerRoot {

    /**
     * Private constructor so this utility class cannot be instantiated.
     */
    private IntegerRoot() {
    }

    /**
     * Returns {@code n} to the power {@code p}.
     *
     * @param n
     *            the number to which we want to apply the power
     * @param p
     *            the power
     * @return the number to the power
     * @requires Integer.MIN_VALUE <= n ^ (p) <= Integer.MAX_VALUE and p >= 0
     * @ensures power = n ^ (p)
     */
    private static int power(int n, int p) {
        int result = 1, count = 0;
        while (count < p) {
            result *= n;
            count++;
        }
        return result;
    }

    /**
     * Returns the {@code r}-th root of {@code n}.
     *
     * @param n
     *            the number to which we want to apply the root
     * @param r
     *            the root
     * @return the root of the number
     * @requires n >= 0 and r > 0
     * @ensures root ^ (r) <= n < (root + 1) ^ (r)
     */
    private static int root(int n, int r) {
        int low = 0;
        int high = n + 1;
        int i = (high - low) / 2;

        while (high - low > 1) {
            if (n >= power(i, r)) {
                low = i;
            } else {
                high = i;
            }
            i = (high + low) / 2;
        }

        return low;
    }

    private static boolean isPalindrome(String s) {
        int length = s.length();
        if (length <= 1) {
            return true;
        } else if (s.charAt(length - 1) == s.charAt(0)) {
            return isPalindrome(s.substring(1, length - 1));
        } else {
            return false;
        }
    }

    /**
     * Main method.
     *
     * @param args
     *            the command line arguments
     */
    public static void main(String[] args) {
        SimpleWriter out = new SimpleWriter1L();

        final int[] numbers = { 0, 0, 0, 1, 1, 1, 82, 82, 82, 82, 82, 3, 9, 27,
                81, 243 };
        final int[] roots = { 1, 2, 5, 1, 2, 17, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5 };
        final int[] results = { 0, 0, 0, 1, 1, 1, 82, 9, 4, 3, 2, 3, 3, 3, 3,
                3 };

        for (int i = 0; i < numbers.length; i++) {
            int x = root(numbers[i], roots[i]);
            if (x == results[i]) {
                out.println();
            } else {
                out.println();
            }
        }
        String a = \"abcba\";

        out.print(isPalindrome(a));

        out.close();
    }

}