Problem 1: Diagramming Destruction

Suppose that the following statements are executed in sequence within a subclass of MutableObjectList. For each statement, draw the box-and-pointer diagram that describes the state of the variables after that command.

MutableObjectList p = prepend("a", prepend("b", empty())); MutableObjectList q = prepend("c", prepend("d", prepend("e", empty()))); MutableObjectList r = p; setHead(tail(r), "f"); r = tail(q); setTail(q, prepend("g", tail(p))); setTail(tail(r), tail(p)); setTail(tail(p), r) setHead(tail(tail(tail(r))), "h");

Problem 2: Diagramming BSTs

Draw the sequence of binary search trees that would be obtained by starting with the empty binary search tree and inserting the following eight letters in order:

You only need to show the result of each insertion, and do
**not** need to show any sharing with the previous trees. Your
final tree should have eight nodes.

Let T be the name of the final tree from Part a. Draw the sequence of binary search trees that would be obtained by starting with T and deleting the following eight letters in order:

In the case where the node to be deleted has two non-empty
subtrees, assume that the node is replaced by its *predecessor*,
that is, the maximum value of its left subtree. (The successor would
also work, but we want the deletion process to be unambiguous.)

You only need to show the result of each deletion, and do
**not** need to show any sharing with the previous trees.

Repeat Parts a and b, except perform the insertions and deletions using red-black trees. Notes:

- You should assume that the insertion process always colors the root of top-level tree black after each insertion.
- As in Part b, assume that deleting a node N with two non-empty subtrees replaces it by its predecessor. This case should proceed in two steps: (1) replace the value of N by the value of its predecessor P, leaving the color of N unchanged; (2) delete the node originally holding the predecessor, removing doubly-black nodes as discussed in lecture.
- Although not necessary, you may wish to show intermediate trees used in the process of removing red-red violations (for insertion) or removing doubly-black nodes (for deletion).

Problem 3: Circular Queues

In class, we saw that a queue could be efficiently represented as a mutable list as long as we maintained pointers to both the front node of the list (where elements are dequeued) and to the last node of the list (where elements are enqueued). In this problem, we shall see that it is possible to get by with just a single pointer if we represent the queue as a circular list -- i.e., a list that wraps back on itself.

For instance, in this representation, enqueuing "A", "B", and "C" in order onto an initially empty queue would lead to a sequence structures depicted by the following box-and-pointer diagrams:

In the diagrams, the nodes have been annotated with labels that indicate the identity of the nodes. These labels underscore the fact that, in this representation, the head of a node never changes. However, the tails of nodes are rewired to give the depicted structure.

In all but the empty queue case, the queue variable holds a pointer to the back node of the queue (the one most recently enqueued). This facilitates enqueueing a new back node as well as dequeuing the front node (least recently enqueued) node, which is always the tail of the back node.

In this problem, you will implement queues in terms of the circular list representation sketched above. Using the static methods of MutableObjectLists (empty(), isEmpty(), prepend(), head(), tail(), setHead(), and setTail()), implement the following queue operations in the destructive interface to queues:

*Constructor Method:*

publicQueueCircular ();

*Instance Methods:*

publicbooleanisEmpty();publicvoidenq (Object x);publicObject deq ();publicObject first();publicintsize();publicvoidclear();publicObject clone();publicObjectList toList();

The file QueueCircular.java in the Object Collections folder of the ps8-programs folder contains code skeletons for these methods that you should flesh out. You can test your implementation by double-clicking on QueueCircular when running the CollectionsTest.html applet.

**Notes: **

- You need to prefix any method of the MutableObjectList class with "MOL." E.g., MOL.empty(), etc.
- The toList() method requires
returning an (immutable) ObjectList, which is a completely
separate class from MutableObjectList. You need to prefix any
method of the ObjectList class with
"OL." E.g., OL.empty(), etc. To
simplify converting between immutable and mutable object lists,
the following operations have been provided in the class MutableObjectListOps:
**public****static**ObjectList mutableToImmutable (MutableObjectList L)

Returns an immutable list with the same elements as L. (They are shared with L.)

**public****static**MutableObjectList immutableToMutable (ObjectList L)

Returns a mutable list with the same elements as L. (They are shared with L.) - Introduce any auxiliary methods that you find helpful.
- In many of the methods, you need to treat the case where elts is the empty list specially.
- Because elts is a circular list, it is tricky to define size(), clone(), and toList(). When traversing elts in these methods, you must be sure to include an appropriate stopping condition. If you neglect to do this, you will get an infinite recursion, and Symantec Cafe will crash. The best way to debug an infinite recursion is to insert lots of System.out.printlns in your code, and use these to pinpoint which part of your code is causing the infinite recursion.

**Submission Details:** For your softcopy submission, turn in
QueueCircular.java.For your hardcopy
submission, turn in QueueCircular.java
*and a copy of the transcript of the test cases*.