1.1 Programming Model

1.1.1

Give the value of each of the following expressions:

a. ( 0 + 15 ) / 2
b. 2.0e-6 * 100000000.1
c. true && false || true && true

a.

jshell> (0 + 15) / 2
$1 ==> 7

b.

jshell> 2.0e-6 * 100000000.1
$2 ==> 200.0000002

c.

jshell> true && false || true && true
$3 ==> true

1.1.2

Give the type and value of each of the following expressions:

a. (1 + 2.236)/2
b. 1 + 2 + 3 + 4.0
c. 4.1 >= 4
d. 1 + 2 + "3"

a.

jshell> (1 + 2.236)/2
$1 ==> 1.618
jshell> ((Object)1.618).getClass().getName()
$2 ==> "java.lang.Double"

b.

jshell> 1 + 2 + 3 + 4.0
$3 ==> 10.0 // Double

c.

jshell> 4.1 >= 4
$4 ==> true // Boolean

d.

jshell> 1 + 2 + "3"
$5 ==> "33"

1.1.3

Write a program that takes three integer command-line arguments and prints equal if all three are equal, and not equal otherwise.

public static void main(String[] args) {
    int first = Integer.parseInt(args[0]);
    int second = Integer.parseInt(args[1]);
    int third = Integer.parseInt(args[2]);

    if (first == second && second == third) {
        System.out.println("equal");
    } else {
        System.out.println("not equal");
    }
}

1.1.4

What (if anything) is wrong with each of the following statements?

a. if (a > b) then c = 0; b. if a > b { c = 0; } c. if (a > b) c = 0; d. if (a > b) c = 0 else b = 0;

a. The programs does not compile.

|  Error:
|  variable declaration not allowed here
|  if (a > b) then c = 0;
|             ^---------^

b. The program fails to compile.

|  Error:
|  '(' expected
|  if a > b { c = 0; }
|    ^
|  Error:
|  ')' expected
|  if a > b { c = 0; }
|          ^

c. The problem compiles.

d. The problem does not compile. It's missing a semicolon;

jshell> if (a > b) c = 0 else b = 0;
|  Error:
|  ';' expected
|  if (a > b) c = 0 else b = 0;
|                

1.1.5

Write a code fragment that prints true if the double variables x and y are both strictly between 0 and 1 and false otherwise.

static boolean areBetween0and1(double x, double y) {
    return isBetween0and1(x) && isBetween0and1(y);
}

static boolean isBetween0and1(double x) {
    if (x > 0 && x < 1) {
        return true;
    }
    return false;
}

1.1.6

What does the following program print?

int f = 0;
int g = 1;
for (int i = 0; i <= 15; i++) {
    StdOut.println(f);
    f = f + g;
    g = f - g;
}

It prints:

0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610

1.1.7

Give the value printed by each of the following code fragments:

a. double t = 9.0;
 while (Math.abs(t - 9.0/t) > .001)
 t = (9.0/t + t) / 2.0;
 StdOut.printf("%.5f\n", t);
b. int sum = 0;
 for (int i = 1; i < 1000; i++)
 for (int j = 0; j < i; j++)
 sum++;
 StdOut.println(sum);
c. int sum = 0;
 for (int i = 1; i < 1000; i *= 2)
 for (int j = 0; j < i; j++)
 sum++;
 StdOut.println(sum);

a) 3.00009

b) 499500

c) 1023

1.1.8

What do each of the following print?

a. System.out.println('b');
b. System.out.println('b' + 'c');
c. System.out.println((char) ('a' + 4));

Explain each outcome.

a) It prints 'b' and a new line

b) It prints 197. First 'b' is converted to int (98) and then 'c' to int (99) so the total is 98 + 99 = 197

c) It prints 'e'. First ('a' + 4) is converted to int. 'a' is 97 so result is 97 + 4 = 101. Then this int is converted to char which is 'e';

1.1.11

Write a code fragment that prints the contents of a two-dimensional boolean array, using * to represent true and a space to represent false. Include row and column numbers.

static void printContents(boolean[][] arr) {
    for (int i = 0; i < arr.length; i += 1) {
        for (int j = 0; j < arr[i].length; j += 1) {
            if (arr[i][j]) {
                System.out.printf("row: %d, column: %d = *\n", i, j);
            } else {
                System.out.printf("row: %d, column: %d = \n", i, j);
            }
        }
    }
}

1.1.12

What does the following code fragment print?

int[] a = new int[10];
for (int i = 0; i < 10; i++)
 a[i] = 9 - i;
for (int i = 0; i < 10; i++)
 a[i] = a[a[i]];
for (int i = 0; i < 10; i++)
 System.out.println(i); 

It prints:

0
1
2
3
4
5
6
7
8
9

1.1.13

Write a code fragment to print the transposition (rows and columns changed) of a two-dimensional array with M rows and N columns.

static void printTranspose(int[][] arr) {
    int[][] result = new int[arr[0].length][arr.length];
    for (int i = 0; i < arr.length; i += 1) {
        for (int j = 0; j < arr[i].length; j += 1) {
            result[j][i] = arr[i][j];
        }
    }
    for (int i = 0; i < result.length; i += 1) {
        for (int j = 0; j < result[i].length; j += 1) {
            System.out.printf("row: %d, column: %d = %d\n", i, j, result[i][j]);
        }
    }
}

1.1.14

Write a static method lg() that takes an int value N as argument and returns the largest int not larger than the base-2 logarithm of N. Do not use Math.

static int lg(int n) {
    if (n == 1) {
        return 0;
    }
    if (n == 2) {
        return 1;
    }
    int acc = 2;
    int result = 1;
    while (acc * 2 <= n) {
        acc *= 2;
        result += 1;
    }
    return result;
}

1.1.15

Write a static method histogram() that takes an array a[] of int values and an integer M as arguments and returns an array of length M whose ith entry is the number of times the integer i appeared in the argument array. If the values in a[] are all between 0 and M–1, the sum of the values in the returned array should be equal to a.length.

static int[] histogram(int[] arr, int M) {
    int[] result = new int[M];
    for (int i: arr) {
        if (i < M) {
            result[i] += 1;
        }
    }
    return result;
}

1.1.16

Give the value of exR1(6):

public static String exR1(int n)
{
 if (n <= 0) return "";
 return exR1(n-3) + n + exR1(n-2) + n;
}

Result is 311361142246

1.1.18

Consider the following recursive function:

public static int mystery(int a, int b)
{
 if (b == 0) return 0;
 if (b % 2 == 0) return mystery(a+a, b/2);
 return mystery(a+a, b/2) + a;
}

What are the values of mystery(2, 25) and mystery(3, 11)? Given positive integers a and b, describe what value mystery(a, b) computes. Answer the same question, but replace + with * and replace return 0 with return 1.

• mystery(2, 25) prints 2 * 25 = 50
• mystery(3, 11) prints 3 * 11 = 33

mystery indeed computes $a * b$;

If we replace + with * and 0 with 1 the fuction becomes:

public static int mystery(int a, int b) {
    if (b == 0) return 1;
    if (b % 2 == 0) return mystery(a * a, b / 2);
    return mystery(a * a, b / 2) * a;
}

This computes the value $a^b$.

1.1.19

Run the following program on your computer:

public class Fibonacci
{
 public static long F(int N)
 {
 if (N == 0) return 0;
 if (N == 1) return 1;
 return F(N-1) + F(N-2);
 }
 public static void main(String[] args)
 {
 for (int N = 0; N < 100; N++)
 StdOut.println(N + " " + F(N));
 }
}

What is the largest value of N for which this program takes less 1 hour to compute the value of F(N)? Develop a better implementation of F(N) that saves computed values in an array.

On my machine any values more than 50 resulted in really slow computation. Here is a better version (using longs):

public static long F(long N) {
    if (N <= 1) {
        return N;
    }
    long[] memo = new long[(int)(N + 1)];
    memo[0] = 0;
    memo[1] = 1;
    for (int i = 2; i <= N; i += 1) {
        memo[i] = memo[i - 1] + memo[i - 2];
    }
    return memo[(int) N];
}

1.1.20

Write a recursive static method that computes the value of ln (N !)

Since $n! = 1 × 2 × 3 × ... × n$,

then $ log(n!) = log(1) + log(2) + log(3) + … + log(n)$.

Computing this for large values of n is costly. Since we are not asked for an approximation we can just calculate it directly. (using the lg function we implemented earlier)

static int lnProduct(int n) {
    if (n == 1) {
        return 0;
    }
    return lg(n) + lnProduct(n - 1);
}

1.1.21

Write a program that reads in lines from standard input with each line containing a name and two integers and then uses printf() to print a table with a column of the names, the integers, and the result of dividing the first by the second, accurate to three decimal places. You could use a program like this to tabulate batting averages for baseball players or grades for students.

public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    while (input.hasNextLine()) {
        String line = input.nextLine();
        String[] words = line.split(" ");
        String name = words[0];
        double first = Double.parseDouble(words[1]);
        double second = Double.parseDouble(words[2]);
        System.out.printf("Name: %s, Div: %.3f\n", name, first / second);
    }
}

1.1.22

Write a version of BinarySearch that uses the recursive rank() given on page 25 and traces the method calls. Each time the recursive method is called, print the argument values lo and hi, indented by the depth of the recursion. Hint: Add an argument to the recursive method that keeps track of the depth.

public static int rank(int key, int[] a) {
    return rank(key, a, 0, a.length - 1, 0);
}

public static String padLeft(String inputString, int length) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < length; i++) {
        sb.append(' ');
    }

    return sb.toString() + inputString;
}

public static int rank(int key, int[] a, int lo, int hi, int depth) {
    String out = padLeft(String.format("lo: %d, hi: %d\n", lo, hi), depth);
    System.out.print(out);
    if (lo > hi) return -1;
    int mid = lo + (hi - lo) / 2;
    if (key < a[mid]) return rank(key, a, lo, mid - 1, depth + 1);
    else if (key > a[mid]) return rank(key, a, mid + 1, hi, depth + 1);
    else return mid;
}

1.1.23 Add to the BinarySearch test client the ability to respond to a second argument: + to print numbers from standard input that are not in the whitelist, - to print numbers that are in the whitelist.

public static void main(String[] args) {
    int[] whitelist = readInts(args[0]);
    boolean printNotFromWhitelist = true;
    if (args[1].equals("+")) {
        printNotFromWhitelist = true;
    }
    if (args[1].equals("-")) {
        printNotFromWhitelist = false;
    }
    Scanner scanner = new Scanner(System.in);
    Arrays.sort(whitelist);
    while (scanner.hasNext()) { // Read key, print if not in whitelist.
        int key = scanner.nextInt();
        boolean notFound = rank(key, whitelist) < 0;
        // Print numbers from standard input that are not in the whitelist
        if (notFound && printNotFromWhitelist) {
            System.out.println(key);
        }

        // Print numbers from standard input that are in the whitelist
        if (!notFound && !printNotFromWhitelist) {
            System.out.println(key);
        }
    }
}

1.1.24

Give the sequence of values of p and q that are computed when Euclid’s algorithm is used to compute the greatest common divisor of 105 and 24. Extend the code given on page 4 to develop a program Euclid that takes two integers from the command line and computes their greatest common divisor, printing out the two arguments for each call on the recursive method. Use your program to compute the greatest common divisor or 1111111 and 1234567.

Solution trivial...

1.1.25

Use mathematical induction to prove that Euclid’s algorithm computes the greatest common divisor of any pair of nonnegative integers p and q.

In GCD the process terminates when a remainder of 0 is reached, and the last nonzero remainder in the process is gcd(p, q) with $p ≥ q$

The process in the Euclidean algorithm produces a strictly decreasing sequence of remainders $r0 > r1 > r2 > · · · >rn+1 = 0$

Hence the algorithm stops after no more than q divisions.

If $rn$ is the last non-zero remainder in the process, then we have

$rn = gcd(rn, 0) = gcd(rn−1, rn) = ... = gcd(r0, r1) = gcd(p, q).$

For the base step $i = 0$, we have $gcd(p, q) = gcd(r0, r1)$ by definition of $r0 = a$ and $r1 = b$.

For each i in 0 ≤ i < n we have

$gcd(ri, ri+1) = gcd(ri+1, ri+2)$

This shows that if

$gcd(a, b) = gcd(ri, ri+1)$, then $gcd(a, b) = gcd(ri+1, ri+2),$

which is the induction step.

1.1.26

Sorting three numbers. Suppose that the variables a, b, c, and t are all of the same numeric primitive type. Show that the following code puts a, b, and c in ascending order:

if (a > b) { t = a; a = b; b = t; }
if (a > c) { t = a; a = c; c = t; }
if (b > c) { t = b; b = c; c = t; }

• The first if checks if $a > b$ and swaps $a$ with $b$. At the end we have $a < b$;
• The second if checks if $a > c$ and swaps $a$ with $c$. At the end we have $a < c$;
• The last if checks if $b > c$ and swaps $b$ with $c$. At the end we have $b < c$;

From all three we have $a < b < c$. For example if $a=3, b=2, c=1$ we have:

$3 > 2$ then $a = 2, b = 3$

$2 > 1$ then $a = 1, c = 2$

$3 > 2$ then $c = 3, b = 2$

1.1.27

Binomial distribution. Estimate the number of recursive calls that would be used by the code:

public static double binomial(int N, int k, double p)
{
 if ((N == 0) || (k < 0)) return 1.0;
 return (1.0 - p)*binomial(N-1, k) + p*binomial(N-1, k-1);
}

to compute binomial(100, 50). Develop a better implementation that is based on saving computed values in an array.

• Code seems to be wrong! We don't have a definition of binomial with two parameters!

The code should have been:

static int nChoseR(int n, int r) {
    // Since nCr is same as nC(n-r)
    // To decrease number of iterations
    if (r > n / 2)
        r = n - r;

    int answer = 1;
    for (int i = 1; i <= r; i++) {
        answer *= (n - r + i);
        answer /= i;
    }

    return answer;
}

static float binomialProbability(int n, int k, float p) {
    return nChoseR(n, k) * (float) Math.pow(p, k) *
        (float) Math.pow(1 - p, n - k);
}

1.1.28

Remove duplicates. Modify the test client in BinarySearch to remove any duplicate keys in the whitelist after the sort.

When you find one of the indexes you're looking for, and from there, then check all the left and right indexes for the same value and remove them from the array

public static void main(String[] args) {
    int[] whitelist = In.readInts(args[0]);
    Arrays.sort(whitelist);
    while (!StdIn.isEmpty()) { // Read key, print if not in whitelist.
        int key = StdIn.readInt();
        int index = rank(key, whitelist); // finds index of duplicate
        if (index >= 0) {
            int start = index - 1, end = index + 1;
            // Check left of index
            while (start != 0 && whitelist[start] == key) {
                if (whitelist[start] == key) {
                    start -= 1;
                } else {
                    break;
                }
            }
            // Check right of index
            while (end != whitelist.length - 1) {
                if (whitelist[end] == key) {
                    end += 1;
                } else {
                    break;
                }
            }
            int numOfDuplicates = end - start;
            if (numOfDuplicates > 0) {
                // Copy first part
                int[] first = Arrays.copyOfRange(whitelist, 0, start);
                // Copy second part
                int[] second = Arrays.copyOfRange(whitelist, end + 1, whitelist.length - 1);
                // Create result array with no duplicate keys
                int[] result = new int[first.length + second.length + 1];
                System.arraycopy(first, 0, result, 0, first.length);
                // Assign key in position
                result[first.length] = key;
                // Combine the results
                System.arraycopy(second, 0, result, first.length + 1, second.length);
                whitelist = result;
            }
        }
    }
}

1.1.29

Equal keys. Add to BinarySearch a static method rank() that takes a key and a sorted array of int values (some of which may be equal) as arguments and returns the number of elements that are smaller than the key and a similar method count() that returns the number of elements equal to the key. Note : If i and j are the values returned by rank(key, a) and count(key, a) respectively, then a[i..i+j-1] are the values in the array that are equal to key.

 /*
     Returns the
     number of elements that are smaller than the key
      */
 static int rank(int key, int[] a) {
     int index = Arrays.binarySearch(a, key);
     int lessThanCount = 0;
     if (index >= 0) {
         int curr = index - 1;
         while (curr >= 0) {
             if (a[curr] != key) {
                 lessThanCount += 1;
             }
             curr -= 1;
         }
     }
     return lessThanCount;
 }

 /*
     Returns the number of elements equal to the key
  */
 static int count(int key, int[] a) {
     int index = Arrays.binarySearch(a, key);
     int count = 0;
     if (index >= 0) {
         count += 1;
         int start = index - 1, end = index + 1;
         // Check left of index
         while (start >= 0) {
             if (a[start] == key) {
                 start -= 1;
                 count += 1;
             } else {
                 break;
             }
         }
         // Check right of index
         while (end < a.length - 1) {
             if (a[end] == key) {
                 end += 1;
                 count += 1;
             } else {
                 break;
             }
         }
     }
     return count;
 }

1.1.30

Array exercise. Write a code fragment that creates an N-by-N boolean array a[][] such that a[i][j] is true if i and j are relatively prime (have no common factors), and false otherwise.

If the greatest common divisor (gcd) of 2 numbers a and b is 1 (i.e. gcd(a, b) = 1) then a and b are relatively prime.

static boolean[][] relPrimeTable(int N) {
    boolean[][] result = new boolean[N][N];
    for (int i = 0; i < N; i += 1) {
        for (int j = 0; j < N; j += 1) {
            result[i][j] = gcd(i, j) == 1;
        }
    }
    return result;
}

1.1.31

Random connections. Write a program that takes as command-line arguments an integer N and a double value p (between 0 and 1), plots N equally spaced dots of size .05 on the circumference of a circle, and then, with probability p for each pair of points, draws a gray line connecting them.

public class Ex1131 extends Canvas {
    int N;
    double p;

    Ex1131(int N, double p) {
        this.N = N;
        this.p = p;
    }
    public static void main(String[] args) {
        int N = Integer.parseInt(args[0]);
        double p = Double.parseDouble(args[1]);

        JFrame frame = new JFrame("Random Connections");
        Canvas canvas = new Ex1131(N, p);
        canvas.setSize(400, 400);
        frame.add(canvas);
        frame.pack();
        frame.setVisible(true);
    }

    public void paint(Graphics g) {
        int radius = 100;
        double angle = Math.PI;
        Point2D[] points = new Point2D.Double[N];
        for (int i = 0; i < N; i += 1) {
            angle = angle + Math.PI / 4;
            System.out.println(angle);
            double x = radius * Math.cos(angle) + 200;
            double y = radius * Math.sin(angle) + 200;
            g.fillOval((int) x, (int) y, 5, 5);
            points[i] = new Point2D.Double(x, y);
        }
        g.setColor(Color.GRAY);
        for (int i = 0; i < N; i += 1) {
            for (int j = i + 1; j < N; j += 1) {
                if (Math.random() < p) {
                    g.drawLine((int) points[i].getX(), (int) points[i].getY(), (int) points[j].getX(), (int) points[j].getY());
                }
            }
        }
    }
}

1.1.32

Histogram. Suppose that the standard input stream is a sequence of double values. Write a program that takes an integer N and two double values l and r from the command line and uses StdDraw to plot a histogram of the count of the numbers in the standard input stream that fall in each of the N intervals defined by dividing (l , r) into N equal-sized intervals.

public class Ex1132 extends Canvas {
    ArrayList nums;
    int N;
    double r;
    double l;

    Ex1132(int N, double r, double l, ArrayList nums) {
        this.N = N;
        this.r = r;
        this.l = l;
        this.nums = nums;
    }

    public static void main(String[] args) {
        int N = Integer.parseInt(args[0]);
        double l = Double.parseDouble(args[1]);
        double r = Double.parseDouble(args[2]);
        ArrayList nums = new ArrayList<Integer>();
        for (int i = 3; i < args.length; i += 1) {
            nums.add(Integer.parseInt(args[i]));
        }

        JFrame frame = new JFrame("Histogram");
        Canvas canvas = new Ex1132(N, l, r, nums);
        canvas.setSize(400, 400);
        frame.add(canvas);
        frame.pack();
        frame.setVisible(true);
    }

    public void paint(Graphics g) {
        int x = 30;
        int height = 400;
        int width = 300;
        // Draw a horizontal base line
        g.drawLine(10, height - 45, width - 10, height - 45);
        int[] count = new int[N];
        for (Iterator i = this.nums.iterator(); i.hasNext(); ) {
            int number = (int) i.next();
            int intervalIndex = number / N;
            count[intervalIndex] += 1;
        }

        // Find the maximum count. The maximum count has the highest bar
        int maxCount = 0;
        for (int i = 0; i < count.length; i++) {
            if (maxCount < count[i])
                maxCount = count[i];
        }
        for (int i = 0; i < count.length; i += 1) {
            // Find the bar height
            int barHeight = (int) (((double) count[i] / (double) maxCount) * (height - 55));
            // Display a bar (i.e. rectangle)
            g.drawRect(x, height - 45 - barHeight, 10, barHeight);
            // Move x for displaying the next character
            x += N;
        }
    }
}

1.1.33

Matrix library. Write a library Matrix that implements the following API:

public class Matrix
static double dot(double[] x, double[] y) vector dot product
static double[][] mult(double[][] a, double[][] b) matrix-matrix product
static double[][] transpose(double[][] a) transpose
static double[] mult(double[][] a, double[] x) matrix-vector product
static double[] mult(double[] y, double[][] a) vector-matrix product

Develop a test client that reads values from standard input and tests all the methods.

public static int[][] mult(int[][] firstMatrix, int[][] secondMatrix) {
    int r1 = firstMatrix.length; // row1
    int r2 = firstMatrix[0].length; // col1
    int q1 = secondMatrix.length; // row2
    int q2 = secondMatrix[0].length; // col2
    int[][] product = new int[r1][q2];
    if (r1 != q2) {
        return product;
    }
    for (int i = 0; i < r1; i++) {
        for (int j = 0; j < q2; j++) {
            for (int k = 0; k < c1; k++) {
                product[i][j] += firstMatrix[i][k] * secondMatrix[k][j];
            }
        }
    }
    return product;
}

static double dot(double[] x, double[] y) {
    double result = 0;
    for (int k = 0; k < x.length; k++) {
        result += x[k] * y[k];
    }
    return result;
}

static int[][] transpose(int[][] arr) {
    int[][] result = new int[arr[0].length][arr.length];
    for (int i = 0; i < arr.length; i += 1) {
        for (int j = 0; j < arr[i].length; j += 1) {
            result[j][i] = arr[i][j];
        }
    }
    return result;
}

1.1.34

Filtering. Which of the following require saving all the values from standard input (in an array, say), and which could be implemented as a filter using only a fixed number of variables and arrays of fixed size (not dependent on N)? For each, the input comes from standard input and consists of N real numbers between 0 and 1.

• Print the maximum and minimum numbers.
• Print the median of the numbers.
• Print the k th smallest value, for k less than 100.
• Print the sum of the squares of the numbers.
• Print the average of the N numbers.
• Print the percentage of numbers greater than the average.
• Print the N numbers in increasing order.
• Print the N numbers in random order.

Require saving all the values from standard input:

1. Print the maximum and minimum numbers.
2. Print the median of the numbers.
3. Print the k th smallest value, for k less than 100
4. Print the sum of the squares of the numbers
5. Print the percentage of numbers greater than the average

Implemented as a filter: 1. Print the average of the N numbers 2. Print the N numbers in random order 3. Print the N numbers in increasing order

1.1.35

Dice simulation. The following code computes the exact probability distribution for the sum of two dice:

int SIDES = 6;
double[] dist = new double[2*SIDES+1];
for (int i = 1; i <= SIDES; i++)
 for (int j = 1; j <= SIDES; j++)
 dist[i+j] += 1.0;
for (int k = 2; k <= 2*SIDES; k++)
 dist[k] /= 36.0;

The value dist[i] is the probability that the dice sum to k. Run experiments to validate this calculation simulating N dice throws, keeping track of the frequencies of occurrence of each value when you compute the sum of two random integers between 1 and 6. How large does N have to be before your empirical results match the exact results to three decimal places?

Using the code below:

public static boolean areAllTrue(boolean[] array) {
    for (boolean b: array)
        if (!b) return false;
    return true;
}

public static boolean allSimilar(double[] distr, double[] freq) {
    boolean[] equal = new boolean[distr.length];
    for (int i = 0; i < distr.length; i += 1) {
        BigDecimal aa = new BigDecimal(distr[i]);
        BigDecimal bb = new BigDecimal(freq[i]);
        aa = aa.setScale(3, RoundingMode.HALF_EVEN);
        bb = bb.setScale(3, RoundingMode.HALF_EVEN);
        equal[i] = aa.equals(bb);
    }
    return areAllTrue(equal);
}


public static void main(String[] args) {
    double[] distr = diceDistr();
    double[] freq = new double[13];
    int trials = 1000;
    while (!allSimilar(distr, freq) && trials < 10e6) {
        trials += 1000;
        for (int i = 0; i < trials; i += 1) {
            int randomNum1 = ThreadLocalRandom.current().nextInt(1, 7);
            int randomNum2 = ThreadLocalRandom.current().nextInt(1, 7);
            freq[randomNum1 + randomNum2] += 1;
        }
        for (int i = 0; i < freq.length; i += 1) {
            freq[i] /= trials;
        }
    }
    System.out.println(trials);
}

I managed to complete it after 297000 trials. It also depends on the rounding mode.

1.1.36

Empirical shuffle check. Run computational experiments to check that our shuffling code on page 32 works as advertised. Write a program ShuffleTest that takes command-line arguments M and N, does N shuffles of an array of size M that is initialized with a[i] = i before each shuffle, and prints an M-by-M table such that row i gives the number of times i wound up in position j for all j. All entries in the array should be close to N/M.

1.1.37

Bad shuffling. Suppose that you choose a random integer between 0 and N-1 in our shuffling code instead of one between i and N-1. Show that the resulting order is not equally likely to be one of the N! possibilities. Run the test of the previous exercise for this version.

1.1.38

Binary search versus brute-force search. Write a program BruteForceSearch that uses the brute-force search method given on page 48 and compare its running time on your computer with that of BinarySearch for largeW.txt and largeT.txt.

static int bruteForceSearch(int[] arr, int k) {
    int n = arr.length;
    for (int i = 0; i < n; i++) {
        if (arr[i] == k)
            return i;
    }
    return -1;
}

public static void main(String[] args) {
    int[] whitelist = readInts(args[0]);
    Arrays.sort(whitelist);

    Scanner s = new Scanner(System.in);
    long startTime = System.nanoTime();
    while (s.hasNext()) {
        int key = s.nextInt();
        if (Arrays.binarySearch(whitelist, key) < 0) {
            System.out.println(key);
        }
    }
    long endTime = System.nanoTime();
    long totalTime = endTime - startTime;
    System.out.println(totalTime);
}

1.1.39

Random matches. Write a BinarySearch client that takes an int value T as command-line argument and runs T trials of the following experiment for N = 103, 104, 105, and 106: generate two arrays of N randomly generated positive six-digit int values, and find the number of values that appear in both arrays. Print a table giving the average value of this quantity over the T trials for each value of N.