Exam #3 - Comp 212

Rice University - Spring 2003

Instructions

  1. The examination is open book/notes.  You are allowed to consult any written materials available under the sun, except solutions from your current Comp212 classmates.  If your code is based on materials that we did not provide you, just give us the appropriate references.
  2. You are not allowed to discuss the exam in any way with anybody beside the instructors (Cox and Nguyen, but not the labbies) of this course.
  3. Do not post your questions on the newsgroup.  E-mail to both of us, alc@rice.edu and dxnguyen@rice.edu, your questions instead. We will reply to you directly, and if deemed necessary, we will forward our reply to the newsgroup as well.  We will check our e-mail as often as we can to catch and respond to your questions
  4. Write your code in the most object-oriented way possible, that is with the fewest number of control statements and no checking of the states and class types of the objects involved in any way.
  5. We expect correct Java syntax.
  6. There are 8 questions for a total of  100 points.  You have 5 hours to do the exam.
  7. There is one extra-credit question.  The time limit does not apply to this question.
  8. Submit a hard copy with all answers in type-written form, except perhaps diagrams (if any) which can be hand-drawn.  Be sure to print your name and sign the honor pledge.  Bring your exam to Zung Nguyen's office (DH 3098) and e-mail him (dxnguyen@rice.edu)  to  him of notify your submission. He will reply to confirm your submission. 
  9. The deadlines for submission are:
    • for graduating seniors:  12 PM (noon), May 01, 2003,
    • for the rest: 5 PM, May 07, 2003.
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)

 

1. About Splay Trees

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.

2. About Treaps

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.
 

3. Card Games

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.

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.

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.

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.

 

4.  Extra-Credit (Short) Essay (Time limit does not apply.  10 points)

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.