CS230 Data Structures, Wellesley College, Fall 1999

Problem Set 1

Due: Friday, September 17

[CS230 Home Page] [Assignments] [Documentation] [Software Installation] [FAQ] [CS Dept.] [CWIS]


Submission details:

On this problem set, you may work in teams of up to three people. Your team should submit a single softcopy (electronic) and hardcopy (paper) solution packet to these problems. For the softcopy solution, submit the solution folder for each of the problems to the drop folder of one of your team members. For the hardcopy solution, submit a printout of the relevant code for each problem. Your hardcopy solution should begin with a cover sheet that can be found here. The cover sheet asks you to list the names of your team members, the location of the dropped softcopy solution, and the time you took on each problem.


Problem 1: Mortgage Payments

You're thinking of buying a house! You've decided to use Java to see what sort of monthly mortgage payments you can afford.

There are three relevant parameters in determining a mortgage:

  1. The principal, which is the cost of the house after downpayment.
  2. The annual interest rate, measured in percent. These are hovering around 8% these days.
  3. The number of years in the mortgage, typically 30.

Let p be the principal, i be the annual interest rate, and y be the number of years in the mortgage. Then the monthly mortgage rate can be calculated according to the following formula:

p * (i/1200)
1 - (1/(1 + (i/1200)))(12*y)

(Note that the interest parameter i should be a number in the range 0 to 100 rather than 0 to 1. That is, 7.25% is expressed as 7.25, not 0.0725.) For example, the monthly mortgage payment on a $250,000 house (after downpayment) with 8% interest and a 30-year mortgage is $1834.41. After 30 years, the total mortgage payments amount to $660,388 = 2.64 times the listed cost of the house. This is how banks make money!

In this problem you should do the following:

For this problem, your hardcopy submission should contain a code listing for the Mortgage class and a printout of the output of executing the main() method of this class. Your softcopy submission for this problem (and Problem 2) should be your Mortgage folder.

Notes:


Problem 2: It's the Principal of the Thing

The mortgage method in Problem 1 tells you the monthly mortgage given the principal, interest rate, and the number of years. But suppose instead that you have determined the monthly mortgage M that best fits your budget and want to determine the principal P for the most expensive house you can afford for that mortgage (for a given interest rate and number of years).

One approach is to algebraically manipulate the formula from Problem 1 to express P as a function of M, interest, and the number of years. But you are rusty on your algebra, so you decide not to take that tack.

An alternative approach is to use the mortgage method from Problem 1 as a way of evaluating a sequence of guesses at the desired principal P. The principal P you seek is the one for which mortgage returns M. You can use the binary search idea from the HiLo game as a way of effectively guessing P. In particular, suppose you know that P is in the closed interval [lo, hi]. Then because mortgage is a monotonically increasing function, you can use the result of applying mortgage to the midpoint of lo and hi to narrow P to be in one half of this interval. By successively halving the interval, you can quickly converge to a result P' whose mortgage M' is within one dollar of M. At that point, you can declare P' as the desired principal.

Implement this idea by fleshing out the missing parts of the following FindPrincipal class, which you should implement in a file FindPrincipal.java within Mortgage.proj.

public class FindPrincipal {
	
  public static double find (double mortgage, double interest, double years) {
    return findBetween(mortgage, interest, years, 0, upperBound(mortgage, interest, years));
  }
	
  public static double findBetween (double mortgage, double interest, double years, double lo, double hi) {
    // Flesh this out.
  }
	
  public static double upperBound (double mortgage, double interest, double years) {
    // Flesh this out
  }
 
  public static void testFind (double m, double i, double y) {
    System.out.println("find(" + m + ", " + i + ", " + y + ") = " + find(m,i,y));
  }
	
  public static void main () {
    // Flesh this out
  }	
	
}

The find method defers to findBetween to find a principal in the interval [0, u], where u is an upper bound on the desired principal P -- i.e., u is guaranteed to be greater than or equal to P. The find method should use binary search to converge to a principal P whose mortage is within one dollar of the mortgage parameter to findBetween. (Use Math.abs to calculate absolute values.) The upperBound method determines an upper bound u for P. It should implement the following strategy: starting with the principal 1, successively double it until reaching a principal Q whose mortgage is greater than the given mortgage limit. Q is clearly an upper bound for P. The main method should test your code by determining the maximum house price that can be purchased for a $1200.00 per month mortgage in a 30-year mortgage at all interest rates between 5.0% and 10.0%, at 0.25% increments. The main method should print out lines of the form

find(1200, 7.75, 30) = 167424

with one line for each interest rate between 5.0% and 10.0%, at 0.25% increments.

For this problem, your hardcopy submission should contain a code listing for the FindPrincipal class and a printout of the output of executing the main() method of this class. Your softcopy submission for this problem (and Problem 2) should be your Mortgage folder.


Problem 3: Blackjack

Blackjack (also known as twenty-one) is a popular casino card game. There are many versions of the game; here we consider one of the simplest variations.

The goal of the game is to acquire a hand of cards whose point value is as large as possible without exceeding 21 points. The point value of a hand is the sum of the point values of the individual cards, where:

For example,

Since the goal of the game is to get as close to 21 points without going over, the canonical value of a hand with multiple point values is the largest value less than or equal to 21, if such a value exists, or the smallest value greater than 21, if none of the possible values is less than 21. Some examples of canonical values:

Note that adding a card to a hand with aces may decrease its canonical value by changing the point value of an ace from 11 to 1.

For the remainder of this problem, we will simplify matters by assuming that aces always have 11 as their point value. For example, we will treat [AC AD AH] as having a point value of 33. However, next week, we will modify the calculation of point values so that aces can count as either 1 or 11.

In our simple version of the game, there are two participants: the player and the house (representing the casino). Each is dealt two cards from a fresh deck. Both of the player's cards are dealt face up, but one of the house's cards is dealt face down and so is a secret unknown to the player. Play proceeds in two stages:

  1. The player can elect to hit (be dealt another card which is added to her hand) as many times as she wants until she decides to hold (keep her hand) or she busts (gets a hand with point value greater than 21). If the player busts, the game is over, and the house wins. If the player holds, then play continues with the next stage.
  2. The house turns over the face down card and proceeds to hit until the value of the house's hand is 17 or greater. If the house busts, the player wins the game. If the final value of the house's hand is between 17 and 21, inclusive, then the participant with the higher point value wins the game. If the point values of the house and player are equal, the house wins the game.

In this problem, you are provided with a simple graphical user interface (GUI) to a Blackjack game and are asked to implement the rules of the game. For starters, you should first download the folder BlackjackTest from the CS230 download folder (this is on Nike, not on FirstClass). This folder contains compiled code (but not source code) for a working version of the Blackjack game that you will be implementing. Use the AppletViewer to run the Blackjack.html applet in the BlackjackTest folder, and play several games.

The interface is rather crude. For example, cards are represented as text rather than as icons, and the layout of the game leaves much to be desired. But the interface does the job, and is not the focus of this assignment. We will study how to implement user interfaces in Java in a few weeks. For now you should treat the interface as a black box.

Note that in addition to showing the cards in a hand, the interface also shows the number of points. This feature will help you debug your implementation of the point calculation for hands.

The game in the BlackjackTest applet differs in only one way from the game you will be implementing -- it counts aces as either 1 or 11 points, where in this problem you will only count them as 11 points.

After playing with the game in the BlackjackTest folder, you are ready for the assignment. Download the Blackjack folder from the CS230 download folder. This folder contains a number of compiled classes (.class files) implementing the Card Contracts handed out in class. It also contains the source code (.java files) for the user interface (BlackjackGUI.java) and the game rules (BlackjackGame.java). The main file you will be working with is BlackjackGame.java. You may also want to skim BlackjackGUI.java to see how it calls the methods in BlackjackGame.java. But note that it is not necessary to understand the details of how the user interface is built.

BlackjackGame.java contains a skeleton for the implementation of the BlackjackGame class. Instances of this class represent the state of a simple game of Blackjack, as described above. Abstractly, the game has the following state variables:

In this problem, your goal is to implement the following contract for the BlackjackGame class. You will do this by declaring appropriate instance variables and by fleshing out the code for the skeleton methods provided in BlackjackGame.java


Contract for the BlackjackGame class:

Public Constructor Method:

public BlackjackGame ()
Creates a new game in which both the player and the house have been dealt two cards from a fresh deck. The same deck should be used throughout the remainder of the game.

Public Instance Methods:

public Hand getPlayer()
Returns a copy of the current hand of the player in the game. Side effects to the returned hand should not affect the players hand in the game.

public Hand getHouse()
Returns a copy of the current hand of the house in the game. Side effects to the returned hand should not affect the players hand in the game.

public void playerHits()
Adds a new card to the player's hand.

public void housePlays()
Deals cards to the house until the house hand is worth 17 or more points.

Public Class Methods:

public static boolean isBusted (Hand h)
Returns true if the hand h is worth more than 21 points, and false otherwise.

public static int handPoints (Hand h)
Returns the number of points in the hand h. For simplicity, count all aces as 11. (On the next assignment, we will see how to count aces as both 1 and 11.)


For this problem, your hardcopy submission should be your final version of BlackjackGame.java and your softcopy submission should be your final version of the Blackjack folder.

Notes: