CS230 Data Structures, Wellesley College, Fall 1999

Problem Set 2

Due 11:59pm on Friday, September 24

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


Working in Groups on this Assignment

As on Problem Set 1, you are encouraged to work in groups of up to three people on this assignment. The times reported on PS1 indicate that this is a good idea. The average time to complete PS1 was about 7 hours for group members but over 9 hours for individuals working alone. Moreover, all but one group finished the assignment in 8 hours or less, while over half of those working alone took 9 or more hours. If you are in this latter category, you should definitely consider joining a group for PS2, since it is likely to save you lots of time. This is especially important considering that PS2 is a bit more challenging than PS1.

On this assignment, I recommend that you work with different team members than you did on Problem Set 1, just to get to know more of your fellow students. But I realize it is difficult to find partners with similar schedules, so if you've already formed a compatible group, you may stick together for this assignment. If you're in a group of two, I hope you will consider "adopting" a third member who is not yet associated with a group. The CS111-Fall99 Q&A folder is an excellent place to seek group members.

Due Date:

Because I am posting this problem set late (the afternoon of Saturday, Sep. 18), I have extended the due date of the assignment from Thursday, Sep. 23 to Friday, Sep. 24.

Grading:

Because I will be away at a conference between Sep 25 -- Oct 2, I will not be able to return your graded PS2s until I return.

Submission details:

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: Object Diagrams

In this problem, you will draw some object diagrams to illustrate your understanding of the Java Object Model and the important notion of sharing. Study the following code for the Pair class:


public class Pair { // Instance variables: public int left; public int right; public Pair (int l, int r) { left = l; right = r; } public boolean equals (Pair p) { return (left == p.left) && (right == p.right); } public static boolean [ ] comparisons (Pair [ ] [ ] pairArrays) { boolean [ ] bools = new boolean [8]; for (int i = 0; i < 4; i++) { bools[i] = (pairArrays[i][0] == pairArrays[i][1]); } for (int j = 0; j < 4; j++) { bools[j+4] = (pairArrays[j][0].equals(pairArrays[j][1])); } return bools; } public static void test() { // Note: new Pair [4] [ ] creates a 4-slot array // whose slots hold objects of type Pair [ ]. Pair [ ] [ ] pairss = new Pair [4] [ ]; Pair [ ] a = new Pair [3]; a[0] = new Pair (1,2); a[1] = a[0]; a[2] = new Pair (3,4); pairss[0] = a; pairss[1] = a; pairss[2] = new Pair[3]; pairss[2][0] = new Pair(1,2); pairss[2][1] = pairss[0][1]; pairss[2][2] = pairss[1][2]; pairss[3] = pairss[2]; boolean [ ] bools1 = comparisons(pairss); // *** Object Diagram #1 should depict this point *** pairss[1][1] = a[2]; pairss[3][0] = pairss[3][1]; boolean [ ] bools2 = comparisons(pairss); // *** Object Diagram #2 should depict this point *** } public static void main (String [ ] args) { test(); } }

For this problem, you are asked to draw object diagrams that are "snapshots" of the state of the Pair application at two "snapshots" during its execution:

  1. Draw an object diagram that depicts the state of the program immediately after the statement

boolean [ ] bools1 = comparisons(pairss);

is executed.

  1. Draw an object diagram that depicts the state of the program immediately after the statement

boolean [ ] bools2 = comparisons(pairss);

is executed.

Recall that an object diagram shows the state of the objects in ObjectLand. There are two kinds of objects: (1) class instances, which are drawn as boxes labelled by their class name that contain instance variables labelled by their names and (2) array objects, which are drawn as boxes labelled by their array type that contain variables labelled by their index. Variables themselves are drawn as boxes that contain either primitive data (e.g., numbers, booleans, characters) or references (pointers) to other objects. Sharing is indicated by having two pointers that point to the same object. For sample object diagrams, see the object diagrams in Problem 4 of this assignment.

Your object diagrams should not show execution frames, but they should include the following local variables of the test method: pairss, a, bools1, and bools2. These variables may be shown "floating" in the object diagrams. The diagrams should also show all objects that are reachable from these four variables. All such objects (both instances and arrays) should be labelled with their type, and should be drawn as boxes that contain labelled variables.

Notes:

Submission

For this problem, you should submit only a harcopy version of your two object diagrams. You can use pencil and paper for your diagrams -- you need not format them on a computer! (Unless you are very adept with drawing software, formatting the diagrams on the computer will take you much longer than drawing them by hand.)


Problem 2: Blackjack Backtrack

In Problem 3 of Problem Set 1, you implemented a simplified version of a Blackjack game in which aces always counted as 11 points. But, as explained in that problem, aces can count as either 1 or 11 in a real game of Blackjack. In this problem, you will modify the Blackjack game from Problem 3 of Problem Set 1 to count aces as either 1 or 11.

To see how this can be done, let's consider a concrete example: the hand [AC 5S AD 3H]. The handPoints() method of the BlackjackGame class you implemented in PS1 would count 30 points for this hand, which is a clear bust. But other possibilities point values for this hand are 10 (if both aces count as 1) and 20 (if one ace counts as 1 and the other as 11). We would like handPoints() to return the largest of these values that is less than or equal to 21 (20, in this case). If none of the values meets this criterion, we would like the handPoints() to return the smallest of the values, which will necessarily be greater than 21.

Solving this problem amounts to exploring a decision tree in which there is a two-way branch for every ace: one branch indicates that the ace counts as 11, while the other branch indicates that the ace counts as 1. Here is such a tree for our sample hand:

The top node of the tree is called the root, while the bottommost nodes (the black dots) are called leaves. The lines connecting two nodes are called edges. The tree assumes that we explore the cards from the highest index of the hand down, so 3H is at the root. Each edge of the tree is labelled with a weight that is the number of points charged for traversing an edge. Any path from the root down to a leaf corresponds to one way of counting the points in the hand. The point value associated with each root-to-leaf path is shown below each leaf. We will call a path from a node to leaf successful if the point value at the leaf is <= 21.

Conceptually, we would like to explore this tree as follows, using a strategy we'll call maxPointsLEQ. Assume that as it descends the tree, maxPointsLEQ keeps track of the maximum point value maxval that can be allocated to the as-yet-unexplored cards. When maxPointsLEQ starts at the root of the tree, maxval is initially 21. At every node it encounters, maxPointsLEQ will return the maximum number of points less than or equal to maxval for the unexplored cards (i.e., the cards at or below the node being encountered); if there is no such point value, it returns the smallest number of points greater than maxval. Since maxval is 21 at the root of the tree, invoking maxPointsLEQ at the root will yield a solution to our Blackjack problem.

Any time maxPointsLEQ encounters a non-ace card c with Blackjack value v, we know that v must be subtracted from maxval to yield the maximum value for the remainder of the unexplored cards. We also know that the value returned by maxPointsLEQ at c will be v more than the value returned for the remainder of the unexplored cards.

But when maxPointsLEQ encounters an ace, there is a decision to be made: is it counted as an 11 or as a 1? Since we're looking for the largest value <= maxval, we will first assume that it counts as 11 (i.e., take the left branch) and see how this decision pans out. If the value result returned by maxPointsLEQ for the remainder of the hand is <= (maxval - 11), then we succeed; there is a successful path from the ace to a leaf that has value result + 11. However, if the value result returned by maxPointsLEQ for the remainder of the hand is > (maxval - 11), then we fail; there is no successful path to a leaf based on the assumption that the ace counts as 11 points. So instead we backtrack (i.e., change our decision at a choice point) and instead assume that the ace counts as 1. Again we can either succeed (the value result returned for the rest of the hand is <= (maxval - 1)) or fail (the value result returned for the rest of the hand is > (maxval - 1). But this time, if we fail, there are no more choices to be tried, so maxPointsLEQ must return result + 1 in either case. (In the success case, this is the largest number <= maxval, and in the failure case, it is the smallest value > maxval.)

To give you a better sense how maxPointsLEQ processes a hand, here is the decision tree from above where every node is annotated with the value of the parameter maxval at that node and the returned value result for that node:

Note in this case that the maxPointsLEQ strategy only explores two root-to-leaf paths in the tree before it succeeds.

As another example, here is the annotated decision tree for the hand [AC 7S AD 3H]:

Here, the maxPointsLEQ strategy must explore all four root-to-leaf paths in the tree before it succeeds. It is also possible for maxPointsLEQ to fail on a hand. Indeed, in the above example, it fails for the subhands [7S AC] and [AC] in the left half of the tree, as well as for the empty subhand [ ] at the leaf labelled 22 on the right hand side of the tree. In all these cases, result is greater than maxval.

The strategy described above can be encoded as a recursive function (static method) maxPointsLEQ that takes two parameters (the hand of unexplored cards and maxval) and returns the largest point value for the cards <= maxval (if it exists) or the smallest point value for the cards > maxval (otherwise). For simplicity, we will assume that maxPointsLEQ behaves non-destructively; that is, the state of the hand parameter when a particular invocation of maxPointsLEQ is made should be the same as the state of the hand parameter when this invocation returns. Thus, any caller of maxPointsLEQ may assume that maxPointsLEQ does not change the state of its hand parameter.

The initial call to maxPointsLEQ is made from handPoints(), where 21 is supplied as the initial maxval:

	public static int handPoints (Hand h) {
		return maxPointsLEQ(h, 21);
	}
	
	public static int maxPointsLEQ (Hand h, int maxval) {
		Flesh out the details of this method.
	}

To begin this problem, download the Cards folder from the CS230 download folder. This folder contains all the code you will need to do Problems 2, 3, and 4 of this assignment. The BlackjackGame.java file contains a complete implementation of the BlackjackGame class except for the missing body of the maxPointsLEQ method, which you must flesh out.

Notes:

Submission

For this problem, your hardcopy submission should be your final version of BlackjackGame.java. Your softcopy submission for this problem (as well as for Problems 3 and 4) should be the Cards folder as modified in Problems 2, 3 and 4.


Problem 3: Data Abstraction -- Cards

The Contendo game company is attempting to implement a number of card games in Java on a hand-held computer with a small amount of memory. Because memory is such a limited resource, they are looking for any way they can to reduce the amount of memory their program uses. They hire Abby Stracksen, one of the world's top data abstraction experts, to improve the memory usage of their implementation.

One of the files they show to Abby is their implementation of the Card abstraction, which is shown in Appendix A. You should study this appendix now.

Abby notes that every Card instance requires space for two variables: one to hold a pointer to the card's value, and another to hold a pointer to the card's suit. Abby observes that the amount of space per Card instance can be reduced from two variables to one by using a single integer variable whose contents ranges between 0 and 51 to encode which of the 52 cards in a deck is denoted by the card. In particular, she settles on the following correspondence between integers and cards:

 0 : 2C
 1 : 2D
 2 : 2H
 3 : 2S
 4 : 3C
 5 : 3D
 6 : 3H
 7 : 3S
  ...
44 : KC
45 : KD
46 : KH
47 : KS
48 : AC
49 : AD
50 : AH
51 : AS

In this problem, you will use Abby's idea as the basis for a new implementation of the Card class that will replace the one shown above.

To begin this problem, download the Cards folder from the CS230 download folder. This folder contains implementations of all of the card abstractions discussed in class, plus the Blackjack program from Problem Set 1 and the video poker program mentioned in class. Before you make any modifications, do the following:

You should begin by removing the instance variables value and suit from the Card class and replacing them by a single integer instance variable named num:

private int num; // New instance var for Card. Should be in range 0--51.

Next, modify the definitions of the constructor method and all the instance methods (but not the class methods) of the Card class so that they work correctly with the new num instance variable in place of the old ones. You should not change the interfaces to any of these methods; you should just change their implementations! What you are doing is changing the internals of the Card black-box abstraction in such a way that it still appears to work as it did before from the outside world. This is the essence of data abstraction.

For instance, the Card constructor should still take two arguments: a Value v and a Suit s. Your job is to figure out how to generate a number between 0 and 51 that corresponds to the card that has Value v and Suit s. Similarly the value() and suit() methods should return the value and suit of the card, just as before.

When you have changed the implementations of the constructor and instance methods in Card to be consistent with your new representation, test your changes by executing the main() method you studied above. (Be sure to quit out of the Applet Viewer and launch a new Applet Viewer before performing this test.) You have succeeded when the test behaves exactly as it did for the original implementation. If the test does not behave correctly, you need to fix your new implementation of the Card class.

Once you are satisfied that your new Card class works, rename it to be Card-num.java, and rename Card-orig.java back to Card.java. (You could use your new class throughout the rest of the assignment, but it might contain subtle bugs that could complicate the other problems, so its best to use the original implementation just in case.)

Notes/Hints:

Submission

For this problem, your hardcopy submission should be Card-num.java. Your softcopy submission for this problem (as well as for Problems 2 and 4) should be the Cards folder as modified in Problems 2, 3 and 4.


Problem 4: Data Abstraction -- Hands

An obvious implementation of the Hand class uses an array of n cards to represent a hand with n cards. For example, the object diagram corresponding to the hand [6S, AC, JD] would be:

Appendix B contains implementation based on this representation. This implementation appears in the Hand.java file within the Cards folder. We will study it in class on Tuesday, September 21, but it is worth looking at before then.

One drawback of this representation is that a new array must be created and filled every time a new card is added or removed. This means that it can be expensive to add a large number of cards in sequence to a hand. For instance, if k cards are added in sequence to an initially empty hand, then:

In total, k arrays are created, and the number of array slots filled is 1 + 2 + 3 + ... + k = k(k+1)/2. This implies that the time to create a hand with k cards is quadratic in k. As noted in the first lecture, quadratic is usually considered "bad", and we would like to do better.

There is a cleverer representation for a sequence of elements that requires less copying than the naive representation considered above. The idea is this: we will represent a sequence of length elements using two instance variables: an instance variable size which holds the number of cards n, and an instance variable elts with capacity slots, where n <= capacity. Slots 0 through size - 1 of elts will be filled with the n elements of the sequence; slots size through capacity - 1 can be filled arbitrarily (we will never look at them). For example, here is an object diagram depicting the representation of the sample hand [6S, AC, JD] assuming a capacity of 4 (which is encoded as the length of the array):

The "?" in slot 3 indicates "don't care". The advantage of such a representation is that it is easy to add cards. Adding a new card c requires filling the slot at index size with c and incrementing size. For example, adding 2H to the hand represented above should yield:

But what happens when an add is performed when the array is already filled to capacity? In this case it is necessary to increase the length of the array. It turns out that a good strategy is to create a new array that is double the length of the existing array, and copy the elements from the existing array into the new one. For instance, adding 9C to the hand in our running example should yield:

The main advantage of this new representation is that it is much cheaper to add k elements in sequence to an empty array. Suppose the initial capacity of the empty array is 1 element. Then when adding k elements, it is only necessary to create new arrays when adding elements whose (0-based) index is of the form 2i : e.g., elements 1, 2, 4, 8, 16, 32, etc. Thus only log2(k) arrays are created. Furthemore, it turns out that the total number of array slots filled when adding k elements is less than 2k, so that the time for adding k elements to an empty hand is linear, which is considered "good" in this context.

What about removing a card? Removing a card at index i requires shifting all elements at indices i + 1 through size - 1 to the left by one unit, and decrementing size. While elements must be shifted, a new array never needs to be created (we never shrink the size of an array). For instance, removing JD from index 2 in our running example yields:

In this problem, you will modify Hand.java to implement the more efficient representation described above. You will use the same Cards folder that you downloaded for Problems 2 and 3. Before you make any modifications, do the following:

In Hand.java, first remove the instance variable cards and replace it by the following two instance variables:

	private Card [ ] elts; 
	private int size;

You should also add the following new class variable:

	private static int initialCapacity = 1; 

Then you should change the constructor methods and all the instance methods of the Hand class to be consistent with this new representation. You should assume that the capacity of an empty hand is the value of initialCapacity. Referring to this class variable rather than a "magical" constant makes it more apparent how to change the initial capacity for an empty array.

You can test your changes by executing the main() method in the Deck class that you studied above. (Be sure to quit out of the Applet Viewer and launch a new Applet Viewer before performing this test.) You have succeeded when the test behaves exactly as it did for the original implementation. If the test does not behave correctly, you need to fix your new implementation of the Hand class.

Notes:

Submission

For this problem, your hardcopy submission should be your final version of Hand.java. Your softcopy submission for this problem (as well as for Problems 2 and 3) should be the Cards folder as modified in Problems 2, 3 and 4.


Appendix A: A Simple Implementation of the Card Abstraction

// The following code can be found in the file Card.java within the Card folder.
public class Card {
	
	// Instance Variables:
	
	private Value value; // The value of this card.
	private Suit suit; // The suit of this card.
	
	// Constructor Method:
 
	public Card (Value v, Suit s) {
	// Returns a new card with the given value and suit.
		value = v;
		suit = s;
	}
 
	// Instance Methods:
 
	public Value value() {
	// Returns the value of this card.
		return value;
	}
 
	public Suit suit() {
	// Returns the suit of this card.
		return suit;
	}
 
	public boolean equals (Card c) {
	// Returns true if c has the same value and suit as this card; false otherwise.
		return ((value.equals(c.value)) && (suit.equals(c.suit)));
	}
 
	public int compare (Card c) {
	// Returns -1 if this card precedes c in the card ordering; 
	// 0 if this card is equal to c in the card ordering;  
	// and 1 if this card follows c in the card ordering. 
		if (value.equals(c.value)) {
			return suit.compare(c.suit);
		} else {
			return value.compare(c.value);
		}
	}
 
	public String toString() {
	// Returns a string representation of this card. 
		return value.toString() + suit.toString();
	}
 
 
	// Various testing methods not shown
	
}


Appendix B: A Simple Implementation of the Hand Abstraction

// The following code can be found in the file Hand.java within the Card folder.
public class Hand {
	
	// Instance Variables:
	
	private Card [ ] cards; 
	
	// Constructor Methods:
 
	public Hand () {
	// Returns an empty hand (i.e., a hand without cards).
		cards = new Card[0];
	}
	
	private Hand (Card [ ] cs) {
	// Used by the copy() method
		cards = cs;
	}
 
	// Instance Methods:
 
	public int size () {
	// Returns the number of cards in the hand.
		return cards.length;
	}
 
	public void add (Card c) {
	// Adds the card c to the hand so that it is at the last index.
		// Create a new array one slot longer than old:
		Card [ ] newcards = new Card[cards.length + 1];
		// Copy cards from old array to new:
		for (int i = 0; i < cards.length; i++) {
			newcards[i] = cards[i];
		}
		// Put c in last slot of new array:
		newcards[cards.length] = c;
		// Update instance variable:
		cards = newcards;
	}
 
	public Card remove (int i) {
	// Removes the card at index i from the hand and returns it. 
	// The indices of all cards whose index was initially greater than i are decremented by 1. 
	// The behavior is unspecified for indices out of range. 
		Card c = null; // This is how you write the null pointer in Java. 
		if ((i >= 0) && (i < cards.length)) {
			c = cards[i];
			// Create a new array one slot shorter than old:
			Card [ ] newcards = new Card[cards.length - 1];
	  	// Copy cards from old array to new, skipping index i:
		  for (int less = 0; less < i ; less++) {
		  	newcards[less] = cards[less];
		  }
		  for (int greater = i+1; greater < cards.length ; greater++) {
		  	newcards[greater-1] = cards[greater];
		  }
			// Update instance variable:
			cards = newcards;
		}
		return c;
	}
 
	public Card get (int i) {
	// Returns the card at index i in the hand. 
	// The behavior is unspecified for indices out of range. 
		return cards[i];
	}
 
	public void set (int i, Card c) {
	// Replaces the card at index i with c.  
	// The behavior is unspecified for indices out of range. 
		cards[i] = c;
	}
 
	public void sort () {
	// Rearrange the cards in the hand to be in card sorted order by index, 
	// from low value to high value. 
	// For simplicity, use insertion sort. Quadratic behavior won't be too bad
	// since hands will never be very large.
		for (int i = 1; i < cards.length; i++) {
			insert(i);
		}
	}  
	
	private void insert (int i) {
	// Assume that cards[0..i-1] is sorted. Insert card at i into sorted order
	// from low oto hi. 
		Card c = cards[i];
		int j = i; // j is the insertion point.
		while ((j > 0) && (cards[j-1].compare(c) == 1)) {
			cards[j] = cards[j-1];
			j = j - 1;
		}
		cards[j] = c;
	}
 
	public Hand copy () {
	// Return a new hand that has the same cards as this hand.
		Card [ ] newcards = new Card [cards.length];
		for (int i = 0; i < cards.length; i++) {
			newcards[i] = cards[i];
		}
		return new Hand(newcards);
	}
 
	public String toString() {
	// Returns a string representation of this hand. 
		StringBuffer sb = new StringBuffer();
		sb.append(this.type() + "[");
		if (cards.length > 0) {
			sb.append(cards[0].toString());
			for (int i = 1; i < cards.length; i++) {
				sb.append(",");
				sb.append(cards[i].toString());
			}
		}
		sb.append("]");
		return sb.toString();
	}
	
	protected String type() {
		return "Hand"; // Can be overridden by subclasses, Deck in particular.
	}
}