Midterm Solutions

Problem 1

class Employee implements Comparable {
    private String name;
    private String ssn;
    private Date hired;
    public Employee(String name, String ssn) {
       this.name = name;
       this.ssn = ssn;
       hired = new Date();
    }
    public String toString() {
       return name + "(hired: " + hired + ")";
    }
    public String getSSN() { return ssn; }
    public boolean equals(Object other) {
       if (other == null) return false;
       Class cThis = getClass();
       Class cOther = other.getClass();
       if (!cThis.equals(cOther)) return false;
       Employee e = (Employee)other;
       return e.ssn.equals(ssn);
    }
    public int hashCode() {
       return toString().hashCode();
    }
    public int compareTo(Object other) {
       if (other == null) throw new ClassCastException();
       Class cThis = getClass();
       Class cOther = other.getClass();
       if (!cThis.equals(cOther)) throw new ClassCastException();
       Employee e = (Employee)other;
       return hired.compareTo(e.hired);
    }
}

interface ICompany {
    void hire(String name, String ssn);
    void fire(String name, String ssn);
    void printStaff();
}

public class Company implements ICompany {
    private SortedSet staff = new TreeSet();
    public void hire(String name, String ssn) {
       staff.add(new Employee(name, ssn));
    }
    public void fire(String name, String ssn) {
       //staff.remove(new Employee(name, ssn));
       Iterator p = staff.iterator();
       while(p.hasNext()) {
           if (ssn.equals(((Employee)p.next()).getSSN())) {
               p.remove();
               break;
           }
       }
    }
    public void printStaff() {
       Iterator p = staff.iterator();
       while(p.hasNext()) {
           System.out.println("" + (Employee)p.next());
       }
       System.out.println("+++++");
       //System.out.println(staff.toString());
    }

    public static void main(String[] args) {
       try {
           Company acme = new Company();
           Employee bud = new Employee("Bud Dub", "987-65-4321");
               acme.hire("Joe Smith", "555-55-5555");
        Thread.sleep(1000);
               acme.hire("Bill Jones", "123-45-6789");
               Thread.sleep(1000);
               acme.hire("Tina Init", "111-22-3333");
               acme.printStaff();
               acme.fire("Bill Jones", "123-45-6789");
               acme.printStaff();
       } catch(Exception e) {}
    }
}

Program Output

Joe Smith(hired: Sat Jul 17 18:12:56 PDT 2004)
Bill Jones(hired: Sat Jul 17 18:12:57 PDT 2004)
Tina Init(hired: Sat Jul 17 18:12:58 PDT 2004)
+++++
Joe Smith(hired: Sat Jul 17 18:12:56 PDT 2004)
Tina Init(hired: Sat Jul 17 18:12:58 PDT 2004)
+++++

Problem 2

    public static int maxSum(int[] a) {
      int index1 = 0, index2 = 0;
      for(int i = 0; i < a.length; i++) {
         if (a[index1] < a[i]) index1 = i;
      }
      for(int i = 0; i < a.length; i++) {
         if (index1 != i && a[index2] < a[i]) index2 = i;
      }
      return a[index1] + a[index2];
   }

Analysis

T_A(N) = 2N = O(N)

Alternatives:

The simplest algorithm computes a[i] + a[j] for i != j and returns the max. This algorithm runs in O(N²) time.

Using divide and conquer, we could compute the index, i, of the largest value in a[] in O(log N) time. We could repeat the process computing the index j of the largest value in a[] such that i != j. We then return a[i] + a[j]. This takes O(log N) time.

Problem 3

50N = W(1), O(N²), o(N²)

50N²+ 200N = W(1), O(N²), W(N²), Q(N²)

N % 7 = O(1), o(1), O(N²), o(N²)