H22 Lab 2 - Savings Calculator

Due Date: Wednesday, January 25, 23:59PM

I. Overview

This lab is written to accomplish several objectives: The first objective is for you to write an implementation of a binary search algorithm, which is a very common and useful algorithm in computer science. Writing a binary search algorithm is all the more useful because binary search is a non-trivial example of a recursive algorithm, which is a fundamental algorithmtic concept. Secondly, this programming exercise asks you to write a robust code, which reacts well to incorrect inputs given by the user, inputs out of range for the algorithm to meaningfully handle, display, etc.

Optionally (a bonus part), you can experiment with a graphical interface.  This is a good exercise for you (once you are done with the basic part), because the way the graphical intefaces are implemented utilizes several java API classes, and hence this exercise will give you some practice with the way java implements class hierarchy. In particular, you will see how to deal with exceptions thrown by some of the methods you will use. 

Hint:  Before you start, read the whole lab, and take note of the paragraph on grading at the end...

II. The Binary Search Algorithm

Suppose that you are planning an expensive purchase some time in the future. For example, you may be planning for the down-payment of a house or saving for college tuition. You would like to set aside a fixed amount of cash each month and put it in an interest-bearing account so that you have the desired amount of money at the desired time. You will write a program this week that calculates the amount of money required each month.

There are three input numbers that are required from the user. The first is the target savings amount which will be expressed as an integer representing the target number of dollars to be saved. We will call this targetSavings. The second piece of input is a positive integer with the number of months until the savings must be achieved. We will call this numberOfMonths.  The final piece of input is a double with the annual interest rate (i.e. the number 5.3 would be an annual interest rate of 5.3%). We will call this interestRate.  You will then use these three numbers to calculate the amount that must be saved each month. You will need at least two Java methods to calculate this amount. You may choose to have more in order to break up your code into manageable sized tasks.

Notice that the input is a triple of types (int,int,double).  These are the types of the input values, but we recommend that internally your algorithms should use a different representation of all amounts of money.  Namely, we recommend that you denote monetary values as integers denoting the number of cents.  This is because a cent is the smallest money unit, and because an alternative representation as a pair of two integers, one representing dollars and the other representing cents, is less convenient to work with. 

The first Java method is a method called amountSaved that takes in a candidate monthly payment in cents candidatePayment and then calculates the amount that would be saved if the person sets aside candidatePayment cents each month for numberOfMonths months. The interest will be compounded monthly. That is, starting with the initial value of zero, you will iterate for numberOfMonths months, and each month you will add in candidatePayment and multiply the amount saved by (1 + (interestRate/(12*100))).  At each point, the amount saved should be rounded down to an integer since we will assume that the bank does not keep track of fractions of cents. For consistency, it is best for every one to round downwards instead of using the round method in class Math. (I bet that this is what real banks do too.)  [[As a bonus you can experiment with your code to find out the effects of such rounding "error" for some realistic interest rates:  What's the accumulative effect of the way the bank rounds the cent fractions?]]

Once you have your method amountSaved working you need to write a method that calculates the correct amount monthlyPayment to set aside. This method should be called calculateMonthlyPayment, (for purpose of simplifying our testing of your code, all these methods should be methods of a SavingsCalculator class, and it should take a triple (int,int,double) as an input, as discussed above. The output of this method should be the smallest value of X such that amountSaved( X ) is at least targetSavings.  This is the minimal monthly payment (in cents) required to achieve the input target savings given the input number of months and the interest rate.  To find this value, your method should do a binary search for the desired monthlyPayment.  (You can read more about a binary search algorithm is in chapter 9.3.3.)  In order to do a proper binary search, you will need an upper bound and a lower bound for the correct monthlyPayment. You should take 0 as a lower bound, while a reasonable upper bound could be targetSavings/numberOfMonths. Note that this is the amount you would have to set aside if the interest rate were 0. The binary search algorithm preceeds as follows:  Given the current (min,max) values and the target value t, at each iteration the binary search tests if the value for the monthly payment given by median med=(min+max)/2, is greater or less than the desired value t . This test will require the amountSaved method which you have written.  If the amountSaved(med) is greater than t, you should recurse the binary search algorithm on interval (min,med), and if it is smaller than t, then you should recurse the binary search algorithm on interval (med,max).  This way, the algorithm can zoom down on the smallest value m s.t. amountSaved(m) is greater or equal to t.

Hint: A good way to keep a sanity check and see if your algorithm does what you expect it to do, is to embed in your code commands that print out all sort of intermediary values your algorithm deals with.  Once you are satisfied that the code does what it's supposed to, you can remove these printing commands.

III. Interface, Robust Code, Exception Handling

In your program you should only assume that the user inputs some strings as the values of the three input fields. The inputs should be taken from a console. (See examples how to do this in the book and in the lecture notes.) The correct inputs should be two non-negative integer values for the target savings and the number of months, and a non-negative real value between 0 and 100, for the interest rate. Therefore, you must check for the unreasonable input values (like non-numerical values, negative values, out of range, etc.) You also need to check for more subtle problems, like if the number of months is so large that even setting aside a single penny a month will result in too much savings. In each case, you need to print out a reasonable and polite error message to the user. If there are no errors, you should output the monthly value to be saved in dollars and cents, e.g. $45.27.

The best way to handle certain type of incorrect inputs is by using exceptions. In general, from any input (console, file, graphics), you should assume that the inputs given by the user can be extracted only as strings. To extract integer (or double, float, etc) values from such input string s, you can use a method like Integer.valueOf(s).intValue() , (see examples in ch.1 in the textbook), or, a simpler method Integer.parseInt(s). Then, to handle the case when s cannot be parsed as an integer (or double, float, etc) value, you should catch and appropriately handle the exception(s) thrown by these methods. One way to find what exceptions these methods throw is to program it first without handling the exception, and see what the java interpreter reports when the input string is wrong. Another (and better) way is to check a java reference for all exceptions thrown by the input-parsing method you use. For example, for the exceptions thrown by the above method, see http://java.sun.com/j2se/1.4.2/docs/api/java/lang/Integer.html. You can find appropriate classes, methods, and their exceptions to handle string-to-integer (string-to-float, string-to-double, etc) conversion starting from the link above which describes the Integer class, and exploring the related classes (Float, Double, etc).

To facilitate easy testing of your code (both for us and for you), we have implemented a class SavingsCalculatorTester.java , which enables you to write a series of test cases, in a file like input.in.  The SavingsCalculatorTester.test method creates on object of class Input, and here is the definition of the java class Input.java. The SavingsCalculatorTester reads each line of the input.in file, interprets each of these lines as triples of inputs, and calls the SavingsCalculator.calculateMonthlyPayment method on each of these inputs. You should modify the code of the SavingsCalculatorTester (where specified) so that it handles all the input errors as explained above, because as it is right now this code assumes the input.in file contains correctly formed inputs.

Turning in Your Code

See the introduction to the lab to find out how to turn in your files.


You will be graded on correctness of your binary search algorithm (70%), and on how robust your code is to input errorrs (30%).

Bonus (Optional Part):  Graphical user interface (and learning about class hierarchy)

Here is a sample code which you can use to experiment with a graphical user interface for a program you have written:


In this code, the action starts when the user presses the Calculate button. Your code will start out in the paint method, but you will need to call other methods from there to do your calculations. You may also decide to have some data that is global to the entire class, although you should only need to keep the three input variables global. You will notice that this GUI implementation uses the JFrame JAVA API class, which is a part of the java.awt package. As you understand how this GUI works, you will see the paint method taking the Graphics object as an argument. This Graphics class admits methods like drawString which the code above uses to display outputs of the calculations. (For now this code only basically copies the inputs provided by the user, but you will re-write to make these outputs meaningful.) As you try to use this code you will notice that the drawString method writes out the output without clearing first the previous output written on the same spot. Examine the methods provided by this API class and find one that allows you to print the output cleanly, with the outputs of the previous computations erased first. You can examine the documentation of these classes on-line. For example, the JFrame class is described here: http://java.sun.com/j2se/1.4.2/docs/api/javax/swing/JFrame.html, and the Graphics class is described here: http://java.sun.com/j2se/1.4.2/docs/api/java/awt/Graphics.html.