Algorithms 4th Edition

Solution by Fatih KABAKCI

1 - Fundamentals

1.1 - Basic Programming Model

Exercises

1.1.1

a. 7

b. 200.0000002

c. true

1.1.2

a. 1.618

b. 10.0

c. true

d. 33

1.1.3

public class J113 {
    public static void main(String[] args) {

        int c1 = Integer.valueOf(args[0]);
        int c2 = Integer.valueOf(args[1]);
        int c3 = Integer.valueOf(args[2]);

        if (c1 == c2 && c1 == c3)
            System.out.println("all three equal");
        else
            System.out.println("all three not equal");
    }
}

1.1.4

a., there is no keyword then in Java. The code logically is correct though.

b. the condition operators should contain paranthesis (). Also, a couple curly brackets can not be used in that syntax.

c. c is correct.

d. the statement c=0 should be terminated with semicolon operator ;

1.1.5

public class J115 {
    public static void main(String[] args) {

        double x = 0.55;
        double y = 0.66;

        if (x > 0 && x < 1 && y > 0 && y < 1)
            System.out.println("true");
        else
            System.out.println("false");
    }
}

1.1.6

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

1.1.7

a. 3,00009

b. 499500

c. 1023

1.1.8

a. it prints b. Java basically considers it as character b.

b. it prints 197 which is an ASCII code. Java adds them up by looking up their ASCII codes. So, 98 + 99 returns as a result of 197.

c. it prints e. Java adds up 97 which is an ASCII code of a with 4, then it returns e which is a character of 101 ASCII code.

1.1.9

public class J119 {
    public static void main(String[] args) {
        
        int N = 10;
        
        // calculates that how many digits we need to represent it as binary
        int n = 1;
        while(Math.pow(2, n) <= N)
            n++;

        int []binary = new int[n];
        // calculates each bit and puts into array respectively
        for(int i = n - 1; i >= 0; i--) {
            binary[i] = N % 2;
            N /= 2;
        }

        for(int i = 0; i < n; i++)
            System.out.print(binary[i]);
    }
}

1.1.10

1.1.11

public class J1111 {
    public static void main(String[] args) {

        boolean array2D[][] = {
                { true, true }, 
                { false, false },
                { true, false }, 
                { false, true }};

        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 2; j++) {
                boolean content = array2D[i][j];
                if (content)
                    System.out.format("[%d, %d]:* ", i, j);
                else
                    System.out.format("[%d, %d]:  ", i, j);
            }
            System.out.println();
        }
    }
}

1.1.12

0
1
2
3
4
4
3
2
1
0

1.1.13

public class J1113 {
    
    final static int M = 3,N = 3;
    static int [][]arr = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    
    public static void print() {
        for(int i = 0; i < M; i++) {
            for(int j = 0; j < N; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
    
    public static void transposition() {
        for(int i = 0; i < M; i++) {
            for(int j = i; j < N; j++) {
                int temp = arr[i][j];
                arr[i][j] = arr[j][i];
                arr[j][i] = temp;
            }
        }
    }
    
    public static void main(String[] args) {
        print();
        transposition();
        print();
    }
}

1.1.14

public class J1114 {

    public static int myPow(int base, int exponent) {
        int c = 1;
        for (int i = 1; i <= exponent; i++) {
            c = c * base;
        }
        return c;
    }

    public static int lg(int N) {
        int i = 0;
        while (myPow(2, i + 1) <= N) {
            i++;
        }
        return i;
    }

    public static void main(String[] args) {
        System.out.println(lg(33));
    }
}

1.1.15

public class J1115 {

    private static boolean lookUp(int search, int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == search) {
                return true;
            }
        }
        return false;
    }

    private static int histogram(int[] a, int startIndex, int search) {
        int counter = 1;
        for (int i = startIndex; i < a.length; i++) {
            if (search == a[i])
                counter++;
        }
        return counter;
    }

    public static int[] histogram(int[] a, int M) {
        // a array elements that checked distinctly
        int[] av = new int[M];
        // array for histogram that calculates number of times i data appears
        int[] b = new int[M];
        // index for both av and b arrays
        int index = 0;

        int length = a.length;
        for (int i = 0; i < length; i++) {
            int search = a[i];
            // whether data has already counted or not ?
            if (!lookUp(search, av)) {
                av[index] = search;
                int numberOfdata = histogram(a, i + 1, search);
                b[index] = numberOfdata;
                index++;
            }
        }
        return b;
    }

    public static void main(String[] args) {

        int[] a = { 1, 2, 3, 3, 3, 2, 2, 1, 4, 5, 4, 8};
        int[] b = histogram(a, 6);

        for (int i = 0; i < b.length; i++)
            System.out.print(b[i] + ", ");
    }
}

1.1.16

Output:

131246

1.1.17

The answer has already provided in the book.

1.1.18

Output:
50
33

mystery(a, b) -> a * b

Output:
33554432
177147

mystery(a, b) -> a exp b

1.1.19

public class J1119 {

    /**
     * Fibonacci memorizing using Array
     */

    private static long[] fibKey = new long[100];
    private static long[] fibValue = new long[100];
    private static int index = 0;

    private static long get(long N) {
        for (int i = 0; i < index; i++) {
            if (fibKey[i] == N)
                return fibValue[i];
        }
        return -1;
    }

    private static void put(long key, long value) {
        fibKey[index] = key;
        fibValue[index] = value;
        ++index;
    }

    public static long F(int N) {

        if (N == 0 || N == 1) {
            return N;
        } else {
            long data = get(N);
            if (data != -1) {
                // do not calculate anymore, just return it
                return data;
            }
            // has to be calculated once, then save it
            // calculation part
            long value = F(N - 1) + F(N - 2);
            // saving part
            put(N, value);
            return value;
        }
    }

    public static void main(String[] args) {
        for (int i = 0; i < 100; i++)
            System.out.println(i + " " + F(i));
    }
}

1.1.20

public class J1120 {

    public static long fact(long n) {
        if(n == 0 || n == 1)
            return 1;
        return n * fact(n - 1);
    }

    public static void main(String[] args) {
        for (int i = 0; i < 20; i++)
            System.out.println(i + " " + fact(i));
    }
}

1.1.21

import java.util.Scanner;

public class J1121 {

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        
        System.out.println("Please enter name, and two integers to fill following table");
        System.out.println("name" + "\t" + "int1" + "\t" + "int2" + "\t" + "result");
        
        do {
            String line = scan.nextLine();
            String[] lines = line.split(" ");

            String name = new String();
            int int1, int2, result;

            try {
                name = lines[0];
                int1 = Integer.parseInt(lines[1]);
                int2 = Integer.parseInt(lines[2]);
                result = int1 / int2;

                System.out.println(name + "\t" + int1 + "\t" + int2 + "\t" + result);
                
            } catch (NumberFormatException nfe) {
                System.out.println("The input wrong ! Please enter again");
            } catch (IndexOutOfBoundsException ibe) {
                System.out.println("Wrong input series ! Please enter again");
            } catch (Exception e) {
                System.out.println("Something wrong ! Please enter again");
            }
            System.out.println("Continue y/n ?");
        } while (scan.nextLine().equals("y"));
    }
}

1.1.22

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;

public class J1122 {

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

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

    public static int[] getFile() throws IOException {
        // example largeW.txt file that has the numbers 1 through 20
        BufferedReader br = new BufferedReader(new FileReader("src/largeW"));
        int[] numbers = new int[20];
        int index = 0;
        String line;
        try {
            while ((line = br.readLine()) != null) {
                numbers[index++] = Integer.parseInt(line);
            }
        } finally {
            br.close();
        }
        return numbers;
    }

    public static void main(String[] args) throws IOException {
        int[] numbers = getFile();
        Arrays.sort(numbers);
        rank(16, numbers);
    }
}

1.1.23

public static void main(String[] args) throws IOException {
        int[] numbers = getFile();
        Arrays.sort(numbers);

        if (rank(16, numbers) != -1)
            System.out.println("+");
        else
            System.out.println("-");
    }

1.1.24

import java.util.Scanner;

public class J1124 {
    public static int gcd(int p, int q) {
        if (q == 0)
            return p;
        int r = p % q;
        System.out.format("p:%d  q:%d\n", q, r);
        return gcd(q, r);
        
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("Enter two integers:");
        int p = scan.nextInt();
        int q = scan.nextInt();
        int r = gcd(p, q);
        System.out.format("gcd(%d, %d):%d\n", p, q, r);
    }
}

1.1.25

/* gcd {a and b} = gcd {b and b mod a} should be same by induction of it. */
    
    public static void main(String[] args) {
        for (int i = 100; i >= 50; i--) {
            for (int j = 1; j <= 50; j++) {
                int a = gcd(i, j);
                int b = gcd(j, i % j);
                System.out.format("gcd(%d, %d) = gcd(%d, %d mod %d) = %d %b\n", i, j, j, i, j, a, a == b);
            }
        }
    }

Creative Problems

1.1.26

public class J1126 {
    public static void main(String[] args) {
        // 3 2 1
        // 3 1 2
        // 2 1 3
        // 2 3 1
        // 1 3 2
        // 1 2 3
        int a = 3;
        int b = 2;
        int c = 1;

        if (a > b) {
            int temp = a;
            a = b;
            b = temp;
        }

        if (b > c) {
            int temp = b;
            b = c;
            c = temp;
        }

        if (a > b) {
            int temp = a;
            a = b;
            b = temp;
        }
        System.out.println("The sorted numbers are " + a + " " + b + " " + c);
    }
}

1.1.27

The code is provided http://algs4.cs.princeton.edu/11model/Binomial.java.html on this link.

public static double binomial2(int N, int k, double p) {
        double[][] b = new double[N+1][k+1];

        // base cases
        for (int i = 0; i <= N; i++)
            b[i][0] = Math.pow(1.0 - p, i);
        b[0][0] = 1.0;

        // recursive formula
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= k; j++) {
                b[i][j] = p * b[i-1][j-1] + (1.0 - p) *b[i-1][j];
            }
        }
        return b[N][k];
    }

1.1.28

import java.util.Arrays;

public class J1128 {

    public static void show(int[] numbers) {
        for (int i : numbers)
            System.out.print(i + " ");
        System.out.println();
    }

    private static int[] slide(int point, int[] numbers) {
        for (int k = point; k < numbers.length - 1; k++) {
            numbers[k] = numbers[k + 1];
        }
        return numbers;
    }

    public static int[] removeDuplicates(int[] a) {
        int length = a.length;

        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                while (a[i] == a[j]) {
                    a = slide(j, a);
                    --length;
                }
            }
        }

        int[] removedNumbers = new int[length];
        for (int i = 0; i < length; i++) {
            removedNumbers[i] = a[i];
        }
        return removedNumbers;
    }

    public static void main(String[] args) {

        int[] whitelist = { 1, 2, 1, 3, 4, 5, 6, 3, 4, 3 };

        Arrays.sort(whitelist);
        show(whitelist);
        whitelist = removeDuplicates(whitelist);
        show(whitelist);
    }
}

1.1.29

import java.util.Arrays;

public class J1129 {

    public static int rank(int key, int[] a) {
        Arrays.sort(a);

        int counter = 0;
        for (int i : a) {
            if (i < key)
                counter++;
        }
        return counter;
    }

    public static int count(int key, int[] a) {
        Arrays.sort(a);

        int counter = 0;
        for (int i : a) {
            if (i == key)
                counter++;
        }
        return counter;
    }

    public static void main(String[] args) {

        int[] a = { 1, 2, 3, 4, 6, 6, 7, 8, 9, 10 };
        int key = 6;
        int i = rank(key, a);
        int j = count(key, a);
        System.out.println("i:" + i);
        System.out.println("j:" + j);
        if (a[i + j - 1] == key)
            System.out.println("valid");
        else
            System.out.println("invalid");
    }
}

1.1.30

public class J1130 {

    public static int gcd(int p, int q) {
        if (q == 0)
            return p;
        return gcd(q, p % q);

    }

    public static void show(boolean a[][]) {
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a.length; j++) {
                System.out.print(a[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {

        int N = 5;
        boolean a[][] = new boolean[N][N];

        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                if (gcd(i, j) == 1) {
                    a[i][j] = true;
                } else {
                    a[i][j] = false;
                }

        show(a);
    }
}

1.1.31

import java.awt.Color;
import java.awt.Graphics;
import javax.swing.JFrame;
import javax.swing.JPanel;

public class J1131 extends JPanel {

    private static final long serialVersionUID = 1L;
    static int N;
    static double p;

    public J1131(int n, double pr) {
        N = n;
        p = pr;
    }

    public void paint(Graphics g) {

        /* https://github.com/ekis/algos/blob/master
         * /algorithms/exercises/src/main/java/github/com
         * /ekis/algorithms/chapter1/fundamentals/creativeprobs/Exercise1131.java
         */
        int width = getWidth() / 4;
        int height = getHeight() / 4;
        int min = Math.min(width, height);
        int r = 4 * min / 5;
        int r2 = Math.abs(min - r) / 2;
        g.setColor(Color.GRAY);
        for (int i = 0; i < N; i++) {
            if (p >= Math.random()) {
                double t = 2 * Math.PI * i / N;
                int x = (int) Math.round(width + r * Math.cos(t));
                int y = (int) Math.round(height + r * Math.sin(t));
                g.fillOval(x - r2, y - r2, 2 * r2, 2 * r2);
            }
        }
        g.drawOval(width - r, height - r, 2 * r, 2 * r);
    }

    public static void main(String[] args) {
        try {
            int n = Integer.valueOf(args[0]);
            double p = Double.valueOf(args[1]);

            JFrame frame = new JFrame("J1131");
            frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
            frame.setSize(600, 400);
            frame.setLocation(400, 100);
            frame.getContentPane().add(new J1131(n, p));
            frame.setVisible(true);

        } catch (NumberFormatException nfe) {
            System.out.println("User input error");
        }
    }
}

1.1.32

public class J1132 {
    public static void draw_histogram(int[] intervals, double[] samples) {
        // https://github.com/morrxy/algs4/blob/master/exercise/1.1.32/ex_1_1_32.java
        StdDraw.setPenRadius(.006);
        StdDraw.line(0, 0, 1, 0);
        StdDraw.line(0, 0, 0, 1);

        int total = samples.length;
        double interval_width = 1.0 / intervals.length;
        double halfWidth = interval_width / 2;
        StdDraw.setPenColor(StdDraw.GRAY);
        StdDraw.setPenRadius();

        for (int i = 0; i < intervals.length; i++) {
            double x = i * interval_width + halfWidth;
            double y = (double) intervals[i] / total / 2;
            StdDraw.rectangle(x, y, halfWidth, y);
        }
    }

    private static boolean isElementOf(double value, double[] values) {
        for (double val : values) {
            if (value == val)
                return true;
        }
        return false;
    }

    private static boolean isFallInterval(double val, double l, double r) {
        if (val >= l && val <= r) {
            return true;
        }
        return false;
    }

    public static int[] frequency(double[] values, int n, double l, double r) {
        double[] distinct = new double[n];
        int[] frequency = new int[n];

        for (int i = 0; i < n; i++) {
            double value = values[i];
            if (isFallInterval(value, l, r) && !isElementOf(value, distinct)) {
                distinct[i] = values[i];
                for (int j = i; j < n; j++) {
                    if (value == values[j]) {
                        frequency[i]++;
                    }
                }
            } else {
                distinct[i] = 0;
                frequency[i] = 0;
            }
        }

        int[] filteredFrequency = new int[n];
        int index = 0;
        for (int i = 0; i < frequency.length; i++) {
            if (distinct[i] != 0)
                filteredFrequency[index++] = frequency[i];
        }
        return filteredFrequency;
    }

    public static void main(String[] args) {
        try {
            int n = Integer.valueOf(args[0]);
            double l = Double.valueOf(args[1]);
            double r = Double.valueOf(args[1]);

            double[] input = { 1, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 7, 8, 8, 8, 9, 10, 10 };
            int[] frequencyVals = frequency(input, n, l, r);

            draw_histogram(frequencyVals, input);

        } catch (NumberFormatException nfe) {
            System.out.println("User input error");
        }
    }
}

1.1.33

class Matrix {
    /**
     * 
     * @param x
     * @param y
     * @return
     */
    public static double dot(double[] x, double[] y) {
        if (x.length == y.length) {
            double result = 0;
            for (int i = 0; i < x.length; i++) {
                result += x[i] * y[i];
            }
            return result;
        }
        return -1;
    }

    /**
     * 
     * @param x
     * @param y
     * @return
     * 
     *  Input: matrices A and B
        Let C be a new matrix of the appropriate size
        For i from 1 to n:
        For j from 1 to p:
        Let sum = 0
        For k from 1 to m:
        Set sum ‹ sum + Aik * Bkj
        Set Cij ‹ sum
        Return C
     */
    public static double[][] mult(double[][] a, double[][] b) {
        int n = a.length;
        int m = a[0].length;
        int p = b[0].length;

        double[][] c = new double[n][p];
        double result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < p; j++) {
                for (int k = 0; k < m; k++) {
                    result += a[i][k] * b[k][j];
                }
                c[i][j] = result;
            }
        }
        return c;
    }

    /**
     * 
     * @param a
     * @return
     */
    public static double[][] transpose(double[][] a) {
        for (int i = 0; i < a.length; i++) {
            for (int j = i; j < a.length; j++) {
                double temp = a[i][j];
                a[i][j] = a[j][i];
                a[j][i] = temp;
            }
        }
        return a;
    }
    
    /**
     * 
     * @param a
     * @param x
     * @return
     */
    public static double[] mult(double[][] a, double[] x) { 
        int n = a.length;
        int m = a[0].length;
        double[] y = new double[x.length];
        double result = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                result += a[i][j] * x[j];
            }
            y[i] = result;
        }
        return y;
    }
    
    /**
     * 
     * @param x
     * @param a
     * @return
     */
    public static double[] mult(double[] x, double[][] a) {
        return mult(a, x);
    }
}

public class J1133 {
    public static void main(String[] args) {
    }
}

1.1.34

import java.util.Random;

class Filter {
    public double max(double[] n) {
        return sort(n)[n.length - 1];
    }

    public double min(double[] n) {
        return sort(n)[0];
    }

    public double median(double[] n) {
        int l = n.length;
        double[] sorted = sort(n);
        if (l % 2 == 0) {
            return (sorted[(l / 2) - 1] + sorted[(l / 2)]) / 2;
        }
        return sorted[l / 2];
    }

    public double kth(double[] n, int k) {
        return sort(n)[k];
    }

    public double sumOfSquares(double[] n) {
        double acc = 0.0;
        for (double d : n) {
            acc += d * d;
        }
        return acc;
    }

    public double avg(double[] n) {
        double acc = 0.0;
        for (double d : n) {
            acc += d;
        }
        return acc / n.length;
    }

    public double percentageOfGreaterThanAvg(double[] n) {
        double avg = avg(n);
        int counter = 0;
        for (double d : n) {
            if (d > avg) {
                counter++;
            }
        }
        return (100 * counter) / n.length;
    }

    public void printAsc(double[] n) {
        System.out.println("Asc order");
        double[] d = sort(n);
        show(d);
    }

    public void printRandomly(double[] n) {
        System.out.println("Random order:");
        double[] d = shuffle(n);
        show(d);
    }

    public double[] sort(double[] n) {
        for (int i = 0; i < n.length; i++) {
            for (int j = 0; j < n.length - 1; j++) {
                if (n[j] > n[j + 1]) {
                    double temp = n[j];
                    n[j] = n[j + 1];
                    n[j + 1] = temp;
                }
            }
        }
        return n;
    }

    public double[] shuffle(double[] n) {
        Random r = new Random();
        for (int i = 0; i < n.length; i++) {
            int i1 = r.nextInt(n.length - 1);
            int i2 = r.nextInt(n.length - 1);
            double temp = n[i1];
            n[i1] = n[i2];
            n[i2] = temp;
        }
        return n;
    }

    public void show(double[] n) {
        System.out.println("Printing the values:");
        for (double d : n) {
            System.out.print(d + " ");
        }
        System.out.println();
    }
}

public class J1134 {
    public static double[] getValues(String file) {
        // assume that the values are coming from a file..
        double[] values = { 3, 1, 2, 5, 4, 0 };
        return values;
    }

    public static void main(String[] args) {
        double[] values = getValues("");

        Filter f = new Filter();

        System.out.println("Max and min:" + f.max(values) + " and " + f.min(values));
        System.out.println("Median:" + f.median(values));
        System.out.println("kth smallest:" + f.kth(values, 3));
        System.out.println("Sum of squares:" + f.sumOfSquares(values));
        System.out.println("Average:" + f.avg(values));
        System.out.println("% Greater than average:" + f.percentageOfGreaterThanAvg(values));
        f.printAsc(values);
        f.printRandomly(values);
    }
}

1.2 - Data Abstraction

It continues