1.2 Data Abstraction

1.2.1

Write a Point2D client that takes an integer value N from the command line, generates N random points in the unit square, and computes the distance separating the closest pair of points.

Brute force approach:

public class Ex121 {
    int N;

    public static void main(String[] args) {
        int N = Integer.parseInt(args[0]);
        Point2D.Double[] points = new Point2D.Double[N];
        for (int i = 0; i < N; i += 1) {
            double x = ThreadLocalRandom.current().nextDouble(0, 400);
            double y = ThreadLocalRandom.current().nextDouble(0, 400);
            points[i] = new Point2D.Double(x, y);
        }

        System.out.println(findClosestPairsBruteForce(points));
    }

    static double dist(Point2D p1, Point2D p2) {
        return Math.sqrt((p1.getX() - p2.getY()) * (p1.getX() - p2.getX()) +
                (p1.getY() - p2.getY()) * (p1.getY() - p2.getY())
        );
    }

    static double findClosestPairsBruteForce(Point2D[] points) {
        double min = Double.MAX_VALUE;
        for (int i = 0; i < points.length; i += 1)
            for (int j = i + 1; j < points.length; j += 1)
                if (dist(points[i], points[j]) < min)
                    min = dist(points[i], points[j]);
        return min;
    }
}

1.2.2

Write an Interval1D client that takes an int value N as command-line argument, reads N intervals (each defined by a pair of double values) from standard input, and prints all pairs that intersect.

TODO

1.2.3

Write an Interval2D client that takes command-line arguments N, min, and max and generates N random 2D intervals whose width and height are uniformly distributed between min and max in the unit square. Draw them on StdDraw and print the number of pairs of intervals that intersect and the number of intervals that are contained in one another.

TODO

1.2.6

A string s is a circular rotation of a string t if it matches when the characters are circularly shifted by any number of positions; e.g., ACTGACG is a circular shift of TGACGAC, and vice versa. Detecting this condition is important in the study of genomic sequences. Write a program that checks whether two given strings s and t are circular shifts of one another. Hint : The solution is a one-liner with indexOf(), length(), and string concatenation.

Solution is based from this article:

static boolean isCircular(String a, String b) {
    boolean result = false;
    if (a == null || b == null) {
        return false;
    }
    if (a.length() != b.length()) {
        return false;
    }
    String combined = a + a;
    if (combined.indexOf(b) >= 0) {
        result = true;
    }
    return result;
}

1.2.7

What does the following recursive function return?

public static String mystery(String s){
 int N = s.length();
 if (N <= 1) return s;
 String a = s.substring(0, N/2);
 String b = s.substring(N/2, N);
 return mystery(b) + mystery(a);
}

It reverses the provided string. For example ABCDEFG becomes GFEDCBA.

1.2.9

Instrument BinarySearch (page 47) to use a Counter to count the total number of keys examined during all searches and then print the total after all searches are complete. Hint : Create a Counter in main() and pass it as an argument to rank().

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

public static int rank(int key, int[] a, int lo, int hi, Counter c) {
    if (lo > hi) return -1;
    int mid = lo + (hi - lo) / 2;
    if (key < a[mid]) {
        c.increment();
        return rank(key, a, lo, mid - 1, c);
    } else if (key > a[mid]) {
        c.increment();
        return rank(key, a, mid + 1, hi, c);
    } else return mid;
}

1.2.10

Develop a class VisualCounter that allows both increment and decrement operations. Take two arguments N and max in the constructor, where N specifies the maximum number of operations and max specifies the maximum absolute value for the counter. As a side effect, create a plot showing the value of the counter each time its tally changes.

static class VisualCounter {
    private final String name; // counter name
    private int count = 0; // current value
    private int N = 0; // maximum number of operations
    private int max = 0; // maximum absolute value for the counter
    private int opCount = 0; // current operations count

    public VisualCounter(String id, int N, int max) {
        name = id;
        this.N = N;
        this.max = max;
    }

    public void increment() {
        if (opCount < N && count < max) {
            count++;
            opCount += 1;
        }
    }

    public void decrement() {
        opCount += 1;
        count--;
    }

    public int tally() {
        return count;
    }

    public String toString() {
        return count + " " + name;
    }
}

1.2.11

Develop an implementation SmartDate of our Date API that raises an exception if the date is not legal.

We just add a simple validation for invalid day/year/month combinations

public class SmartDate {
    private final int month;
    private final int day;
    private final int year;

    public SmartDate(int m, int d, int y) throws IllegalArgumentException {
        validateDate(m, d, y);
        month = m;
        day = d;
        year = y;
    }

    public int month() {
        return month;
    }

    public int day() {
        return day;
    }

    public int year() {
        return year;
    }

    public String toString() {
        return month() + "/" + day() + "/" + year();
    }

    boolean isLeapYear(int year) {
        return year % 4 == 0 && (year % 100 != 0 || year % 400 == 0);
    }

    public boolean equals(Object x) {
        if (this == x) return true;
        if (x == null) return false;
        if (this.getClass() != x.getClass()) return false;
        Date that = (Date) x;
        if (this.day != that.day) return false;
        if (this.month != that.month) return false;
        if (this.year != that.year) return false;
        return true;
    }

    private void validateDate(int m, int d, int y) throws IllegalArgumentException {
        if (m > 12 || m < 1) {
            throw new IllegalArgumentException("Invalid Month");
        }
        if (d > 31 || d < 1) {
            throw new IllegalArgumentException("Invalid Day");
        }
        if (isLeapYear(y) && m == 2 && d > 29) {
            throw new IllegalArgumentException("Invalid Day");
        }
    }
}

1.2.12

Add a method dayOfTheWeek() to SmartDate that returns a String value Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, or Sunday, giving the appropriate day of the week for the date. You may assume that the date is in the 21st century

A nice hack:

public static String getDay(int day, int month, int year) {
    String dayOfWeek = null;
    String[] days = {
        "Sunday",
        "Monday",
        "Tuesday",
        "Wednesday",
        "Thursday",
        "Friday",
        "Saturday"
    };

    String date = String.valueOf(day) + "/" + String.valueOf(month) + "/" + String.valueOf(year);
    try {
        SimpleDateFormat format1 = new SimpleDateFormat("d/M/yyyy");
        Date dt1 = format1.parse(date);
        dayOfWeek = days[dt1.getDay() - 1];
    } catch (Exception e) {
        System.out.println(e);
    }

    return dayOfWeek;
}

1.2.13

Using our implementation of Date as a model (page 91), develop an implementation of Transaction.

class Transaction implements Comparable < Transaction > {
    String who;
    Date when;
    double amount;

    Transaction(String who, Date when, double amount) {
        this.who = who;
        this.when = when;
        this.amount = amount;
    }

    String who() {
        return who;
    }

    Date when() {
        return when;
    }

    double getAmount() {
        return amount;
    }

    @Override
    public String toString() {
        StringBuilder s = new StringBuilder();
        s.append("<Transaction ");
        s.append("who=" + who);
        s.append(" when=" + when);
        s.append(" amount=" + amount);
        s.append(">");
        return s.toString();
    }

    @Override
    public boolean equals(Object that) {
        // If the object is compared with itself then return true
        if (that == this) {
            return true;
        }

        if (!(that instanceof Transaction)) {
            return false;
        }

        Transaction t = (Transaction) that;

        // Compare the data members and return accordingly
        return Double.compare(amount, t.getAmount()) == 0 &&
            t.who == who && when == t.when;
    }

    @Override
    public int hashCode() {
        int result = 17;
        result = 31 * result + (int) amount;
        result = 31 * result + when.hashCode();
        result = 31 * result + who.hashCode();
        return result;
    }

    @Override
    public int compareTo(Transaction that) {
        if (when.compareTo(that.when) < 0)
            return -1;
        if (when.compareTo(that.when) > 0) {
            return 1;
        }
        // Transaction is identical: compare amount and who
        if (this.amount < that.amount) {
            return -1;
        } else if (this.amount > that.amount) {
            return 1;
        } else {
            return who.compareTo(that.who);
        }
    }
}

1.2.14

Using our implementation of equals() in Date as a model (page 103), develop implementations of equals() for Transaction.

Done in 1.2.23

1.2.16

Rational numbers. Implement an immutable data type Rational for rational numbers that supports addition, subtraction, multiplication, and division. public class Rational

Rational(int numerator. int denominator)
Rational plus(Rational b) sum of this number and b
Rational minus(Rational b) difference of this number and b
Rational times(Rational b) product of this number and b
Rational divides(Rational b) quotient of this number and b
boolean equals(Rational that) is this number equal to that ?
String toString() string representation

You do not have to worry about testing for overflow (see Exercise 1.2.17), but use as instance variables two long values that represent the numerator and denominator to limit the possibility of overflow. Use Euclid’s algorithm (see page 4) to ensure that the numerator and denominator never have any common factors. Include a test client that exercises all of your methods.

static class Rational {
 int numerator;
 int denominator;

 Rational(int numerator, int denominator) {
  this.numerator = numerator;
  this.denominator = denominator;
 }

 Rational plus(Rational b) {
  if (denominator == b.denominator) {
   return new Rational(numerator + b.numerator, denominator);
  }
  int lcmNumber = lcm(denominator, b.denominator);
  int timesFirst = lcmNumber / denominator;
  int timesSecond = lcmNumber / b.denominator;
  return new Rational((timesFirst * numerator) + (timesSecond * b.numerator), lcmNumber);
 }

 Rational minus(Rational b) {
  if (denominator == b.denominator) {
   return new Rational(numerator - b.numerator, denominator);
  }
  int lcmNumber = lcm(denominator, b.denominator);
  int timesFirst = lcmNumber / denominator;
  int timesSecond = lcmNumber / b.denominator;
  return new Rational((timesFirst * numerator) - (timesSecond * b.numerator), lcmNumber);
 }

 public boolean equals(Rational that) {
  return denominator == that.denominator && numerator == that.numerator;
 }

 Rational times(Rational b) {
  int newNuminator = numerator * b.numerator;
  int newDenuminator = denominator * b.denominator;

  return new Rational(newNuminator, newDenuminator);
 }

 Rational divides(Rational b) {
  Rational reciprocal = new Rational(b.denominator, b.numerator);

  // Ignore simplification step...
  return times(reciprocal);
 }

 @Override
 public String toString() {
  return "Rational{" +
   "numerator=" + numerator +
   ", denominator=" + denominator +
   '}';
 }

1.2.17

Robust implementation of rational numbers. Use assertions to develop an implementation of Rational (see Exercise 1.2.16) that is immune to overflow.

TODO

1.2.18

Variance for accumulator. Validate that the following code, which adds the methods var() and stddev() to Accumulator, computes both the mean and variance of the numbers presented as arguments to addDataValue():

public class Accumulator
{
 private double m;
 private double s;
 private int N;
 public void addDataValue(double x)
 {
 N++;
 s = s + 1.0 * (N-1) / N * (x - m) * (x - m);
 m = m + (x - m) / N;
 }
 public double mean()
 { return m; }
 public double var()
 { return s/(N - 1); }
 public double stddev()
 { return Math.sqrt(this.var()); }
}

This implementation is less susceptible to roundoff error than the straightforward implementation based on saving the sum of the squares of the numbers.

Add a main and verify that after each step the results are correct:

public static void main(String[] args) {
 Accumulator acc = new Accumulator();
 System.out.println(acc.mean()); // 0.0
 System.out.println(acc.var()); // 0.0
 System.out.println(acc.stddev()); // 0.0

 acc.addDataValue(10);

 System.out.println(acc.mean()); // 10.0
 System.out.println(acc.var()); // NaN
 System.out.println(acc.stddev()); // NaN

 acc.addDataValue(15);

 System.out.println(acc.mean()); // 12.5
 System.out.println(acc.var()); // 12.5
 System.out.println(acc.stddev()); // 3.5355339059327378

 acc.addDataValue(20);

 System.out.println(acc.mean()); // 15
 System.out.println(acc.var()); // 15
 System.out.println(acc.stddev()); // 5
}

1.2.19

Parsing. Develop the parse constructors for your Date and Transaction implementations of Exercise 1.2.13 that take a single String argument to specify the initialization values, using the formats given in the table below. Partial solution:

public Date(String date)
{
 String[] fields = date.split("/");
 month = Integer.parseInt(fields[0]);
 day = Integer.parseInt(fields[1]);
 year = Integer.parseInt(fields[2]);
}

For simplicity:

public class Transaction {
    String who;
    Date when;
    double amount;

    public Transaction(String transaction) throws ParseException {
        String[] fields = transaction.split("/");
        who = fields[0];
        SimpleDateFormat format = new SimpleDateFormat("dd-MM-yyyy");
        when = format.parse(fields[1]);
        amount = Double.parseDouble(fields[2]);
    }
}