Computer Science 15-100 (Sections S-V), Fall 2008
Homework 8
Due: Fri 31-Oct-2008 at 4:59pm (email copy and identical physical copy)
(no late submissions accepted).

Note: This is due at 4:59pm. Submit your hardcopy in Mark's office or Angie's office (next door) by then.

Read these instructions first!

Be sure to include your name, your Andrew ID, and your section clearly on the top of each file in your assignment.
Also on the top of each file, include a timesheet logging all the time you spent on that part of the assignment.
You will not be graded on your number of hours, but this information will be helpful to the course staff.
For non-programming problems
- Place all your solutions to the non-programming problems in a single file named Hw8 (with whatever extension is appropriate for the format you choose, such as Hw8.txt or Hw8.html, etc). You must use a one of these file formats: plain text (txt), or RTF, or HTML, or Word (doc, not docx), or PDF. No other file formats will be accepted.
- Show your work. Correct answers without supporting calculations will not receive full credit.
For programming problems:
- Place each solution in its own file named exactly as given below, and with a class name that exactly matches the file name. So if the file name is Hw8Foo.java, the main class in that file must be Hw8Foo.
- Use well-named variables, proper indenting, reasonable commenting, etc.
What to submit
- Either one zip file, Hw8.zip, containing all your files (this is preferred), or all the files as attachments to a single email (do not send one email per file!). It is recommended that you "cc" yourself in that email, too, just to confirm that you properly sent the email.

ch1Exercises
SCALES Practice
1. AndrewFinger
2. Mystery Methods
The Television Class
The Coke Machine Class
Bonus/Optional: subsetSum

ch1Exercises
Read and study Chapter 1. Then, do the following Exercises from Chapter 1 (pp 53-55):
Exercises 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.12, 1.13
SCALES Practice
1. AndrewFinger
  Start with this file: Hw8AndrewFinger.java
  As written, this program allows the user to enter a search key for Andrew id's, and then it prints out all the information the Andrew "finger" daemon returns for that key. You can enter actual andrew id's or other user information (try "stehlik" for example). Try it out! Your task is to write the method getAndrewIds that takes a search key and -- using the andrewFinger method already written for you, and searching the result for lines labeled as "login name" -- returns a sorted non-null (though perhaps empty) array of Strings containing all the andrew id's that the finger program returns for the given key. For example, given the search key "stehlik", your method would return the array { "kstehlik", "mjs" }. Note that the file already has a getAndrewIds method defined for you (so you just have to fill in the body), as well as a testGetAndrewIds method (though you may wish to add more test cases).
2. Mystery Methods
  In the written portion of your submission, answer the following questions in general, and in just a few words of plain English.
  Hint #1: while you should definitely trace the code in these problems to make some sense out of it, you may also wish to actually test the code with samples of your choosing, at least to verify that it works as you think it does!
  
  Hint #2: if you follow the previous hint, you may also want to use one of the printArray methods (or a simple adaptation of them) in the notes for 2d arrays.
  1. In general, when will the following method return true?
```
  public static boolean f(char[][] a, String s) {
    if ((a == null) || (s == null)) return false;
    int rows = a.length;
    int cols = a[0].length;
    if (s.length() != rows*cols) return false;
    int si = 0;
    for (int col=0; col<cols; col++) // col first!
      for (int row=0; row<rows; row++) {
        if (s.charAt(si) != a[row][col])
          return false;
        si++;
      }
    return true;
  }
```
    Hint: Here is the "even better" 2d printArray method adapted to work over arrays of chars rather than ints (the changes from the int version are highlighted):
```
  // even better version!
  public static void printArray(char[][] a) {
    int rows = a.length;
    int cols = a[0].length;
    System.out.print("[ ");
    for (int row=0; row<rows; row++) {
      if (row > 0) System.out.print("  ");
      System.out.print("[");
      for (int col=0; col<cols; col++) {
        if (col > 0) System.out.print(", ");
        System.out.format("%3c",a[row][col]); // field-width = 3
      }
      System.out.println("]");
    }
    System.out.println("]");
  }
```
  2. In general, what does the following method do?
```
  public static int[][] g(int[][] a, int r, int c) {
    if (a == null) return null;
    int rows = a.length, cols = a[0].length;
    if ((rows == 0) || (cols == 0)) return null;
    int[][] result = new int[rows-1][cols-1];
    for (int row=0; row<rows; row++)
      for (int col=0; col<cols; col++)
        if ((row != r) && (col != c)) {
          int targetRow = ((row < r) ? row : row-1);
          int targetCol = ((col < c) ? col : col-1);
          result[targetRow][targetCol] = a[row][col];
        }
    return result;
  }
```
The Television Class
Start with this file: Hw8Television.java
Do not modify the Hw8Television main class. Make this code work by adding the appropriate classes with the appropriate methods as described by the test methods called by this main method. Note that you do not have to add any code to the test cases, though you do have to solve them with general-purpose solutions (and not just hard-code the example test cases!).

Hint #1: look carefully at the test code to infer the behavior of the Television class. It is straightforward (no tricks, really!), but you will not be provided with any description beyond this test code. "Use the force, read the source!"

Hint #2: to solve this incrementally, you may wish to comment out parts of the test code so the parts you have implemented will compile and can be tested as you go.
The Coke Machine Class
Start with this file: Hw8CokeMachine.java
As with the preceding problem, do not modify this problem's main class, and make this code work by adding the appropriate classes with the appropriate methods as described by the test methods called by this main method. Same hints apply, too.
Bonus/Optional: subsetSum
Read the Wikipedia page on subsetSum. Then, in the file Hw8BonusSubsetSum.java, write the following method (along with a suitable test method):
public static boolean subsetSum(int[] a)
This method takes an arbitrary-sized array of ints and returns true if some non-empty subset of elements in the array sums to zero. For example, given the array {−7, −3, −2, 8, 5}, the result is "true" because the subset {−3, −2, 5} sums to zero. As the Wikipedia page notes, this problem is NP-complete, which basically means that your solution will be very slow for even moderately-sized arrays (and that's ok). Later in the course, we may learn about techniques that make problems such as this easier to program. The point of this bonus problem is for you to discover one of those techniques on your own, so be sure not to consult any online sources (besides that one Wikipedia page) or read about this problem in textbooks or elsewhere. Also, note that the Wikipedia page discusses an approximate polynomial time (that is, fast) solution. That does not apply here. We want an exact solution, which will be slow, but again, that's ok.

Hint: if you are given an array with N elements, think about counting from 0 up to (2^N-1) using an N-digit binary number, and how that might relate to this problem... Following on this hint, you will get most of the points for solving this problem for arrays of size 32 or smaller (why does that make the problem easier?), but full credit requires that you solve it for even larger arrays (though, being NP-complete, these larger arrays may require vast amounts of time).

Carpe diem!