Pledge of Honor |
1 a (10 pts) | 1 b (10 pts) | 1 c (10 pts) | 2 a (10 pts) | 2 b (10 pts) | 2 c (10 pts) | 3 a (25 pts) | 3 b (15 pts) | Total (100) |
A) For the following binary search tree, splay for 80 and draw the resulting tree.
55
/ \
/
\
31
89
/ \
/
\
81
91
/
/
/
/
61
90
/ \
/ \
57 67
/ \
/ \
62 79
/
/
78
B) The code for the splay operation given in lecture #32 (http://www.owlnet.rice.edu/~comp212/03-spring/lectures/32/code/BSTSplay.html) uses many anonymous visitors to avoid checking for emptiness of the subtrees. Write a visitor called IsEmpty that checks the emptiness of the host tree and rewrite BSTSplay using IsEmpty instead.
C) Consider the dictionary based on the binary search tree given in lecture #25 (http://www.owlnet.rice.edu/~comp212/03-spring/lectures/25/code/DictBT.html). Rewrite the insert method to use the splay operation BSTSplay.
A Treap is a binary tree that is a hybrid of a Binary Search Tree (BST) and a Heap. In a Treap, each node has both a key and a priority that are distinct fields. The defining property of a Treap is that the BST property is maintained over the keys and the Heap property is maintained over the priorities. For example, the following satisfies the Treap property if the maximum priority p is stored in the root.
k: 53 p: 87 / \ / \ / \ / \ k: 27 k: 79 p: 67 p: 44 / \ / \ k: 11 k: 29 k: 67 k: 89 p: 55 p: 57 p: 34 p: 41
Note: Like a BST, a Treap may be unbalanced. The following is also a Treap.
k: 66 p: 31 \ \ k: 78 p: 25 \ \ k: 99 p: 11
A) Write a BiTree visitor that implements insertion of a (key,priority,value) triple into a Treap. Let the (key,priority,value) triple be represented by the class TreapTriple.
class TreapTriple { Comparable key; Comparable priority; Object value; ... }
Hint: pay attention to the key as you descend the tree and the priority as you ascend.
B) Draw the Treap that would result from the insertion of the following
TreapTriples in the given order:
(k: 1, p: 78, v: ?), (k: 2, p: 0, v: ?), (k: 3, p: 55, v: ?),
(k: 4, p: 34, v: ?), (k: 5, p: 40, v: ?), (k: 6, p: 60, v: ?),
(k: 7, p: 10, v: ?), (k: 8, p: 15, v: ?) and (k: 9, p: 25, v:
?).
(Note: We don't care what the value of the TreapTriple
is. Thus, we just say "?" for each value.)
C) Write a BiTree visitor that implements removal of a (key,priority,value)
triple from a Treap. The caller provides only the key. The visitor
returns the triple or null if the key is not found.
Your goal is to design an appropriate object model for cards in order to use them in a variety of card games such as Blackjack, Solitaire, etc.
A) The design must closely model the following description of cards.B) Suppose in a game akin to Solitaire you have a list of cards and want to insert another card at the front of this list . The rules of the game in this situation are as follows.A card has a rank (i.e. Queen, Five, Ace, etc.) and is a member of a particular suit (e.g.. Heart, Spade, etc.). Hearts and Diamonds are red cards, while Spades and Clubs are black cards. In card games, the cards are either face up or face down. A card's behavior may differ depending on whether or not it faces up or down. A card that is face down can be flipped to be face up and vice-versa.
In a particular card game, one situation only considers rank and suit while another situation only considers rank and color. For example, in the game of Solitaire, the goal is to move appropriate cards around to make four stacks of cards, where each card must be of the same suit and ordered according to rank. In doing so, the cards may be placed into temporary card piles where only rank and color matter. In contrast to Solitaire, there are games akin to Blackjack that only consider the rank. Thus, the card design must be flexible enough to accommodate all possible considerations of face, rank, suit and color in order to be used in a large variety of games. The games that we want to play may be extant well-known card games or may be some new games that we just invent!
Write the Java code and javadoc for the classes and interfaces in your design. You need not define factories. Suppose your design has an abstract class AX and concrete subclasses X1, X2, X3 etc. To save some typing, you only need to write the code and javadoc for AX and X1 and then, instead of writing the code for X2, X3, etc., you only need to describe what it is that distinguishes X2, X3, etc. from X1. No UML is required. The documentation need not be extensive but should be concise and clear enough to describe your classes, interfaces and methods. Be sure to state what design patterns you are using. For example, if IVis is the visitor interface for the host class Host, then all you need to document is the IVis is the visitor for Host without having to describe each visiting method and their parameters, and for the visitor hook method in Host, simply state that this is the visitor hook method.
From your design in part a/, write the Java code to implement the above insertion rules. Your code should have as few "if" and other control flow constructs as possible. Use LRStruct to represent the list of cards. Your documentation need not be extensive but should be clear and concise.
In 300 words or less, compare and contrast the presentation of design patterns and object-oriented programming in the Post-OOP paper (PDF version) to the presentation in Comp 212.