Computer Science APEA 15-100, Summer 2009
Homework 12
Due:  Sun 26-Jul-2009 at 11pm (email copy only)
(no late submissions accepted).

Read these instructions first!

• Now you are not given a file to start from!  Based on previous hw's, create your own Hw12.java file.  Be sure to name it exactly correctly, to include a main method that calls checkAssertsAreEnabled and testAll, and to have testAll call suitable test methods for all the methods you create.  Also, be sure that every method you write has exactly the right name and the right signature.
   
• Be sure to include your name, your Andrew ID, and your section clearly on the top of each file in your assignment.
   
• For non-programming problems:
  • Place all your solutions to the non-programming problems in a single file named Hw12 (with whatever extension is appropriate for the format you choose, such as Hw12.txt or Hw12.html, etc).  You must use 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:
  • Try to use well-named variables, proper indenting, reasonable commenting, etc.
  • Note:  You may use any/all Java concepts now!
     
• What to submit
  • Create a submission directory like this:  "koz-hw12"  (replace "koz" with your andrew id)
  • Place all the files you are submitting in that directory, zip that directory, and submit the zipped directory
     
• How to submit
  • Send an email with the zipped submission directory as an attachment to your CA by the submission deadline.  Do not miss the deadline, even by one minute!  Email problems are not a valid excuse for late submissions.
  • It is recommended that you "cc" yourself in that email, too, just to confirm that you properly sent the email.
     
• Note:
  • Improper submissions will be penalized up to 10 points and may be rejected.
  • Late submissions will be rejected.

1. Reading
2. Extended Lab
   1. Book Problems
   2. RatioDemo Reflections
   3. Coke Machine
3. RatioDemo Improvements
4. Bonus/Optional:  subsetSum

1. Reading
   Read Chapter 4 carefully (though you may just skim the portion on graphics and GUI's). Note that the next quiz will cover Chapter 4 (and then some!).  Be sure you have completed this reading assignment by then!
    
2. Extended Lab
   Do the following questions under lab conditions (that is, you may collaborate in small groups).  You must work alone on the other questions in this assignment!
    
   1. Book Problems
      Do the following Exercises from Chapter 4 (pp 200 - 201):  Exercises 4.1 and  4.3.
       
   2. RatioDemo Reflections
      Answer (in plain English, not in Java code!) the following questions regarding the RatioDemo and Ratio classes we wrote in class (see RatioDemo.java).  Your answers should be very brief and to-the-point.
      1. The testRatioClass method is defined outside the Ratio class.  Give an example of something this prevents the method from doing which it could do if it was defined inside the Ratio class.
      2. What are the fields in the Ratio class?
      3. What are the instance variables in the Ratio class?
      4. What are the class variables (aka, static variables) for the Ratio class?
      5. What are the instance methods in the Ratio class?
      6. What are the class methods (aka, static methods) for the Ratio class?
      7. What is the API (Application Programming Interface, aka public instance methods) of the Ratio class?
      8. Why, in general, do we make fields (instance variables) private?
      9. Mutators (methods that change fields) can do more than just change values -- they can ensure their consistency and integrity.  What precisely do the Ratio class's mutators do besides simply set the given field to the given value?
      10. Why did we make the gcd method private?
      11. Why did we make the gcd method static?
      12. Why did we make the reduce method private?
      13. Why did we not make the reduce method static?
      14. What is "this"?
      15. What is the main purpose of a constructor?
      16. Why might we want more than one constructor?  (Hint:  see the RatioDemo Improvement questions below...)
      17. Why did we write a toString method for Ratio?  What would happen if we did not do that?
      18. What would happen if we changed the toString method's name to, say, makeString?
      19. Why does toString return a String and not just print out the String?
      20. Why did we write an equals method for Ratio?  What would happen if we did not do that?
      21. Why does our equals method take an Object and not just a Ratio?
      22. What does instanceof do?  Why did we use it?
      23. Why did we have to cast the Object to a Ratio in our equals method?
      24. Can the null reference be cast to any reference type?  To find out, see what happens when you run this code (does it crash? If so, with what exception?):
             Object obj = null;
             String s = (String)obj;
             System.out.println(s);
      25. What exact exception occurs when you try to cast objects into types other than their own?  To find out, see what happens when you run this code:
             Object object = 42; // autoboxes to an Integer object
             String s = (String)object;
             System.out.println(s);
      26. Our "times" and "add" methods return new Ratio instances rather than directly modifying (mutating) the original object ("this").  Why?  What really undesirable behavior does this avoid?
      27. The "times" method (among others) can access the "num" and "den" properties not only of "this", but also of "that" -- even though "num" and "den" are private.  Explain.
           
   3. Coke Machine
      Start with this file:   CokeMachineDemo.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.
       
3. RatioDemo Improvements
   Copy the file RatioDemo.java to the file Hw12RatioDemo.java, then in that file add the following extensions or improvements to the code:
   1. Add methods for divide, subtract, and invert.
   2. Add a constructor that takes just an integer.
   3. Add a constructor that takes a String such as "2/7" or "-3/8".  Do not deal with any unusual cases (missing "/", overflow, negative denominator, zero denominator, etc, etc, etc).
      Hints:
      1. You can use the "indexOf" method to find the "/", then the substring methods to extract the first and second integers, then the Integer.parseInt method to convert these into int values.
      2. While you should understand the previous approach (and be able to reproduce it on a quiz or test), there is an easier approach which is perhaps less robust but which is fine here (and which you must also understand for a quiz or test), given that you do not have to deal with any unusual cases:  instead of the indexOf/substring approach, you can use the "split" method, as in s.split("/"), which will return an array of the substrings delimited by the "/" -- here, you can simply assume that the array is of size 2, and that element 0 is the numerator and element 1 is the denominator.  Then, just use the Integer.parseInt method to convert these values.
   4. Deal with negatives in a better way.  Right now, this prints false:
         Ratio r1 = new Ratio(-1,3);
         Ratio r2 = new Ratio(1, -3);
         System.out.println(r1.equals(r2));
   5. Add test code (with asserts, etc) for the API (all of the public instance methods, including the ones you just added)
   6. Write a static method that reads in 4 ratios (as Strings which then get converted to Ratio objects using the appropriate constructor you just wrote) representing the values m₁, b₁, m₂, and b₂ in the two equations y=m₁x+b₁ and y=m₂x+b₂, and prints out the ratio values (x,y) for the point of intersection of the two lines, or prints out "same" if the lines are identical, or "parallel" if they are not identical but do not intersect.
   7. List all the public and private methods, including constructors, in the Ratio class that were used in some way by your solution to the previous problem.
       
4. Bonus/Optional:  subsetSum
   Read the Wikipedia page on subsetSum.  Then, in the file Hw12BonusSubsetSum.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!