Overall summary: 

  The first problem is an exercise in modeling in stages. 
  The second one is an exercise in unit testing. 
  The third one is about time complexity and order of growth.
  The fourth is about the Java Collections Framework. 
  Fifth exercise is about Basic Data Structures.
  Sixth exercise is about Tree Structures. 
  The last exercise is about ArrayLists and loops. 

Supporting materials:

  You were supposed to have with you and use Lab 12.

Lab 12 summary:

 1. loops and arrays 
 2. recursion (structural) and arrays 
 3. loops and lists, arrays 
 4. simple modeling (classes, instance members)
 5. basic unit testing 
 6. debugging/tracing (methods)
 7. basic data structures (pointers, debugging)
 8. orders of growth 
 9. orders of growth 
10. induction proofs (241, 211, 212) 
11. basic algebra (241) 

--

And now the answers to the final:

1. Employee, Manager, Executive

-bash-4.2$ pwd
/l/www/classes/c212/fall2018/final/one
-bash-4.2$ ls -ld *.java
-rw-r--r-- 1 dgerman www 409 Dec 17 22:43 Employee.java
-rw-r--r-- 1 dgerman www 524 Dec 17 22:43 Executive.java
-rw-r--r-- 1 dgerman www 526 Dec 17 22:32 Manager.java
-bash-4.2$ cat Employee.java
public class Employee {
  String name; // private, public or protected?
  double salary;
  public Employee(String name, double salary) {
    this.name = name;
    this.salary = salary;
  }
  public String toString() {
    return "Employee: " + this.name + " " + this.salary;
  }
  public static void main(String[] args) {
    Employee a = new Employee("Laura", 12.45);
    System.out.println( a );
  }
}

-bash-4.2$ cat Manager.java
public class Manager extends Employee {
  private String department;
  public Manager(String name, double salary, String department) {
    super(name, salary);
    this.department = department;
  }
  public String toString() {
    return super.toString() + " (is a Manager in " + this.department + ")";
  }
  public static void main(String[] args) {
    Employee a = new Employee("Michael", 10.36);
    Manager  b = new Manager ("Leslie", 15.23, "Sales");
    System.out.println( a );
    System.out.println( b );

  }
}

-bash-4.2$ cat Executive.java
public class Executive extends Manager {
  public Executive(String name, double salary) {
    super(name, salary, null);
  }
  public String toString() {
    return "Executive: " + this.name + ", " + this.salary;
  }
  public static void main(String[] args) {
    Employee  a = new Employee ("Owen", 2.71828);
    Manager   b = new Manager  ("Sara", 3.141592, "Marketing");
    Executive c = new Executive("Alex", 6.023);
    System.out.println( a );
    System.out.println( b );
    System.out.println( c );
  }
}

-bash-4.2$ javac *.java
-bash-4.2$ java Employee
Employee: Laura 12.45
-bash-4.2$ java Manager
Employee: Michael 10.36
Employee: Leslie 15.23 (is a Manager in Sales)
-bash-4.2$ java Executive
Employee: Owen 2.71828
Employee: Sara 3.141592 (is a Manager in Marketing)
Executive: Alex, 6.023
-bash-4.2$

2. StudentTest looks like this (see Chapter 08 in the text):

import org.junit.*;

public class StudentTest {
  @Test public void test001() {
    Student a = new Student("Laura");
    Assert.assertEquals("Laura", a.getName()); 
  }
  @Test public void test002() {
    Student a = new Student("Laura");
    a.addQuiz(100); 
    a.addQuiz( 85); 
    a.addQuiz( 92); 
    Assert.assertEquals(277, a.getTotalScore()); 
  }
  @Test public void test003() {
    Student a = new Student("Laura");
    a.addQuiz(100); 
    a.addQuiz( 85); 
    a.addQuiz( 92); 
    Assert.assertEquals(92.33, a.getAverageScore(), 0.01); 
  }
}

See also http://silo.cs.indiana.edu:8346/c212/fall2018/1114a.phps

The class Student was not needed but here it is anyway: 

public class Student {
  private String name;
  public String getName() {
    return this.name; 
  }
  private int sum, count;
  public Student(String name) {
    this.name = name; 
  }
  public void addQuiz(int value) {
    this.sum += value;  
    this.count += 1; 
  }
  public int getTotalScore() { 
    return this.sum; 
  }
  public double getAverageScore() { 
    return this.sum / (double) this.count; 
  }
  public static void main(String[] args) {
    Student a = new Student("Jordan"); 
    a.addQuiz(100);
    a.addQuiz( 95);
    a.addQuiz( 87);
    System.out.println( "Grade report for: " + a.getName() ); 
    System.out.println( "Total score: " + a.getTotalScore() ); 
    System.out.println( "Average score: " + a.getAverageScore() ); 

  }
}

32. (a) O(n^2)
    (b) O(n^10)
    (c) O(n^4)
    (d) O(n^4)
    (e) O(n^3)
    (f) O(n^3)
    (g) O(n)
    (h) O(n^2) // thanks to Abbie for catching this!
    (i) O(2^n)
    (j) O(n)

Note: n^2 means n squared, 2^n means 2 to the n-th power, etc. 

Another note: on page 644 we read that T(n) is O(f(n)) if and only if 
there is n_0 and C constant such that T(n)/f(n) < C for all n > n_0. So
as an example if we take (g) T(n) = n + log(n) to prove T(n) is O(n) as
I indicated above I'd have to consider 

  T(n)     n + log(n)
 ------ = ------------
  f(n)         n 

When n goes to infinity this ratio goes to 1 so I can easily find a C > 1
and an n_0 such that for all n > n_0 I will have T(n)/f(n) < C (simple, very
basic calculus I). 

4. Collections 

   15.1 List since I can buy three pizzas, two apples and five hair brushes. 

   15.2 Priority queue (see pp. 699-700)

   15.3 Map<Date, Set<Event>> see Exercise 20 on p. 694

5. Consider the following list: A B C D E F

   Consider iterators | and / and notation from Lab 10.

   Here's the list with the first iterator in: A B C | D E F 

   Here | refers to C (the element on the left). 

   Let's add the second iterator: A B C | / D E F 

   Both iterators refer to C. Now we have two cases: 

(a) add an element with the first iterator and remove it with the second

   Let's add an element with the first iterator: A B C M | / D E F 
   
   Let's delete with the second iterator: A B C | / D E F 

   So we're back where we started and that's good (in this case). 

(b) add an element with the second iterator and remove it with the first

   Let's add an element with the second iterator: A B C | M / D E F 
   
   Let's delete with the first iterator: A B | M / D E F 

   QED: we lost C and we now have M (that was not there to start with). 

--

Code to drive home this argument (the code below not necessary, just the diagrams/discussion): 

-bash-4.2$ cat One.java
import java.util.*;

public class One {
  public static void main(String[] args) {
    List<String> a = new LinkedList<String>();
    a.add("A");
    a.add("B");
    a.add("C");
    a.add("D");
    a.add("E");
    a.add("F");
    System.out.println( a );

    Iterator<String>     one = a.listIterator();

    one.next();
    one.next();
    one.next();

    ((ListIterator<String>)one).add("M");

    one = a.iterator();

    one.next();
    one.next();
    one.next();

    one.remove();

    System.out.println( a );

  }
}

-bash-4.2$ javac One.java
Picked up _JAVA_OPTIONS: -Xms512m -Xmx512m
-bash-4.2$ java One
Picked up _JAVA_OPTIONS: -Xms512m -Xmx512m
[A, B, C, D, E, F]
[A, B, M, D, E, F]
-bash-4.2$

In fact Java will complain early about illegal state or concurrent modification exception etc. 

6. The following was needed: 

public class Tree {
  int value;
  Tree left, right;
  public Tree(int value, Tree left, Tree right) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
  public int countLeaves() {
    if (this.left == null && this.right == null) return 1;
    else if (this.left == null) return this.right.countLeaves();
    else if (this.right == null) return this.left.countLeaves();
    else return this.left.countLeaves() + this.right.countLeaves();
  }
}

Here's the code in action (added some code just to illustrate): 

-bash-4.2$ cat Tree.java
public class Tree {
  int value;
  Tree left, right;
  public Tree(int value, Tree left, Tree right) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
  public int countLeaves() {
    if (this.left == null && this.right == null) return 1;
    else if (this.left == null) return this.right.countLeaves();
    else if (this.right == null) return this.left.countLeaves();
    else return this.left.countLeaves() + this.right.countLeaves();
  }
  public String toString() {
    if (this.left == null && this.right == null)
      return "( " + this.value + " . . )";
    else if (this.left == null)
      return "( " + this.value + " . " + this.right + " )";
    else if (this.right == null)
      return "( " + this.value + " " + this.left + " . )";
    else return "( " + this.value + " " + this.left + " " + this.right + " )";
  }
  public static void main(String[] args) {
    Tree a = new Tree(3, null, null); // one leaf
    System.out.println( a + " has " + a.countLeaves() + " leaves." ); // 1
    a = new Tree(3, new Tree(2, null, null), null); // still one leaf
    System.out.println( a + " has " + a.countLeaves() + " leaves." ); // 1
    a = new Tree(3, new Tree(2, null, new Tree(5, null, null)), null); // still one
    System.out.println( a + " has " + a.countLeaves() + " leaves." ); // 1
    a = new Tree(3, new Tree(2, null, new Tree(5, null, null)), new Tree(3, null, null)); // two leaves now
    System.out.println( a + " has " + a.countLeaves() + " leaves." ); // 2
    a = new Tree(3, new Tree(2, new Tree(1, null, null),
                                new Tree(5, null, null)),
                    new Tree(3, null, null)); // three leaves
    System.out.println( a + " has " + a.countLeaves() + " leaves." ); // 3
    a = new Tree(3, new Tree(2, new Tree(1, null,
                                            new Tree(3, null, null)),
                                new Tree(5, new Tree(2, null, null),
                                            new Tree(-1, null, null))),
                    new Tree(3, null, null)); // now four leaves
    System.out.println( a + " has " + a.countLeaves() + " leaves." ); // 4
  }
}
-bash-4.2$ javac Tree.java
-bash-4.2$ java Tree
( 3 . . ) has 1 leaves.
( 3 ( 2 . . ) . ) has 1 leaves.
( 3 ( 2 . ( 5 . . ) ) . ) has 1 leaves.
( 3 ( 2 . ( 5 . . ) ) ( 3 . . ) ) has 2 leaves.
( 3 ( 2 ( 1 . . ) ( 5 . . ) ) ( 3 . . ) ) has 3 leaves.
( 3 ( 2 ( 1 . ( 3 . . ) ) ( 5 ( 2 . . ) ( -1 . . ) ) ) ( 3 . . ) ) has 4 leaves.
-bash-4.2$

7. The first part ends in a concurrent modification exception (as you probably expected): 

-bash-4.2$ cat One.java
import java.util.*;

public class One {
  public static void main(String[] args) {
    ArrayList<String> a = new ArrayList<String>();
    a.add("Trump");
    a.add("Bernie");
    a.add("Bernie");
    a.add("Hillary");
    a.add("Trump");
    a.add("Trump");
    a.add("Bernie");
    a.add("Trump");
    a.add("Hillary");
    a.add("Trump");
    System.out.println( a );
    for (String name : a)
      if (name.equals("Trump"))
        a.remove(name);
  }
}

-bash-4.2$ javac One.java
-bash-4.2$ java One
[Trump, Bernie, Bernie, Hillary, Trump, Trump, Bernie, Trump, Hillary, Trump]
Exception in thread "main" java.util.ConcurrentModificationException
        at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
        at java.util.ArrayList$Itr.next(ArrayList.java:859)
        at One.main(One.java:17)
-bash-4.2$

Now if we switch the loop: 

-bash-4.2$ cat Two.java
import java.util.*;

public class Two {
  public static void main(String[] args) {
    ArrayList<String> a = new ArrayList<String>();
    a.add("Trump");
    a.add("Bernie");
    a.add("Bernie");
    a.add("Hillary");
    a.add("Trump");
    a.add("Trump");
    a.add("Bernie");
    a.add("Trump");
    a.add("Hillary");
    a.add("Trump");
    System.out.println( a );

    for (int i = 0; i < a.size(); i++) {
      if (a.get(i).equals("Trump")) {
        a.remove(i);
      }
    }
    System.out.println( a );

  }
}

-bash-4.2$ javac Two.java
-bash-4.2$ java Two
[Trump, Bernie, Bernie, Hillary, Trump, Trump, Bernie, Trump, Hillary, Trump]
[Bernie, Bernie, Hillary, Trump, Bernie, Hillary]
-bash-4.2$

Let's go back through these with a different list and then summarize. 

Different list, enhanced loop and attempt to remove while iterating: 

-bash-4.2$ cat Three.java
import java.util.*;

public class Three {
  public static void main(String[] args) {
    ArrayList<String> a = new ArrayList<String>();
    a.add("Trump");
    a.add("Trump");
    a.add("Trump");
    a.add("Bernie");
    a.add("Trump");
    a.add("Hillary");
    a.add("Hillary");
    a.add("Trump");
    System.out.println( a );
    for (String name : a)
      if (name.equals("Trump"))
        a.remove(name);
  }
}

// [Trump, Trump, Trump, Bernie, Trump, Hillary, Hillary, Trump]
-bash-4.2$ javac Three.java
Picked up _JAVA_OPTIONS: -Xms512m -Xmx512m
-bash-4.2$ java Three
Picked up _JAVA_OPTIONS: -Xms512m -Xmx512m
[Trump, Trump, Trump, Bernie, Trump, Hillary, Hillary, Trump]
Exception in thread "main" java.util.ConcurrentModificationException
        at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
        at java.util.ArrayList$Itr.next(ArrayList.java:859)
        at Three.main(Three.java:15)
-bash-4.2$

As for the last case: 

-bash-4.2$ cat Four.java
import java.util.*;

public class Four {
  public static void main(String[] args) {
    ArrayList<String> a = new ArrayList<String>();

    a.add("Trump");
    a.add("Trump");
    a.add("Trump");
    a.add("Bernie");
    a.add("Trump");
    a.add("Hillary");
    a.add("Hillary");
    a.add("Trump");

    System.out.println( a );

    for (int i = 0; i < a.size(); i++) {
      if (a.get(i).equals("Trump")) {
        a.remove(i);
      }
    }
    System.out.println( a );

  }
}

// [Trump, Trump, Trump, Bernie, Trump, Hillary, Hillary, Trump]

-bash-4.2$ javac Four.java
Picked up _JAVA_OPTIONS: -Xms512m -Xmx512m
-bash-4.2$ java Four
Picked up _JAVA_OPTIONS: -Xms512m -Xmx512m
[Trump, Trump, Trump, Bernie, Trump, Hillary, Hillary, Trump]
[Trump, Bernie, Hillary, Hillary]
-bash-4.2$
   
So here's the summary: 

(a) concurrent modification exception 

(b) concurrent modification exception 

(c) [Trump, Bernie, Bernie, Hillary, Trump, Trump, Bernie, Trump, Hillary, Trump]
becomes 
    [       Bernie, Bernie, Hillary,        Trump, Bernie,        Hillary       ]

(d) [Trump, Trump, Trump, Bernie, Trump, Hillary, Hillary, Trump]
becomes 
    [       Trump,        Bernie,        Hillary, Hillary       ]

--