Practice Problems
Pair Programming Problems
Problem 1:   Circular data
Problem 2:   Binary Search
Problem 3:   Dequeue for Strings
Problem 4:   Parametrized Dequeue

Assignment 5

Goals: Learn to program with mutation and resolve circularity in data.


The names of the classes must be exactly the same as specified. The same is the case for the names and types of the fields within the class, as well as the order in which they are defined and listed as the constructor arguments. This allows us to design our own Examples class that tests your program.

Make sure you follow the style guidelines that WebCAT enforces. For now the most important ones are: using spaces instead of tabs, indenting by 4 characters, following the naming conventions (data type names start with a capital letter, names of fields and methods start with a lower case letter), and having spaces before curly braces.

You will submit this assignment by the deadline using the Web-CAT submission system. You may submit as many times as you wish. Be aware of the fact that close to the deadline the WebCAT system may slow down to handle many submissions - so try to finish early.

With each homework you will also submit your log file named pair-user1-user2.txt where you replace user1 and user2 with the usernames of the two partners.

On top of both files you will have five lines of comments as follows:

// assignment 5

// partner1-last-name partner1-first-name

// partner1-username

// partner2-last-name partner2-first-name

// partner2-username

(In the text file you do not need the two slashes)

Your submission sould consist of the following files:

all combined into one file.

You will not submit the solution for Problem 3: the Deque designed to work only with the String data.

Due Date: Tuesday, October 29th, 12:00 midnight.

Practice Problems

Work out these problems on your own. Save them in an electronic portfolio, so you can show them to your instructor, review them before the exam, use them as a reference when working on the homework assignments.

Pair Programming Problems

Problem 1: Circular data

Finish all work in the Lab 6 and hand it in.


Submission for Problem 1:

What will be tested on submission:

Problem 2: Binary Search

Start with a new project HW05Problem2 and create two files: and

Problem 3: Dequeue for Strings

Create a project with the name HW05Problem3.

We would like to build a list in such a way that we can start either at the front, or at the back, and move through the list in either direction. In order to do so, we have decided on the structure to represent the following scenarios:


            | Deque |


            | node  |--+

            +-------+  |





          | Sentinel |


          | ""       |

      +---| next     |

      |   | prev     |-----------------------------+

      |   +----------+                             |

      |                                            |

      v                                            v

+----------+   +----------+   +----------+   +----------+

| Node     |   | Node     |   | Node     |   | Node     |

+----------+   +----------+   +----------+   +----------+

| "abc"    |   | "bcd"    |   | "cde"    |   | "def"    |

| bcdnode  |-->| cdenode  |-->| defnode  |-->| sentinel |

| sentinel |<--| abcnode  |<--| bcdnode  |<--| cdenode  |

+----------+   +----------+   +----------+   +----------+

Every list has a header that consists of the Sentinel node. This node does not change, only its fields that provide the links to the first and the last item in the list can change.

Each node has two links, one to the next item in the list and one to the previous node in the list.

The Sentinel node is always present. It does not contain any useful data, i.e. the data field may be either null, or for the list of Strings the empty String. Its role is to provide the link to the head of the list and to the tail of the list.

The empty list has just one node, the Sentinel that contains no useful data, and its links to the first and to the last item just reference the Sentinel node itself.

The Deque is a wrapper class that contains one field, the Sentinel node for this list. So an empty list would have the following class diagram:


     | Deque |


     | node  |--+

     +-------+  |

+----+   +------+

|    |   |  +----+

|    |   |  |    |

|    v   v  v    |

|  +----------+  |

|  | Sentinel |  |

|  +----------+  |

|  | ""       |  |

+--| next     |  |

   | prev     |--+


Problem 4: Parametrized Dequeue

The data structure you have built in the previous problem is very useful, except for the fact that the data in the list can only be of the type String.

Create a project with the name HW05Problem4.

Import into it your solution to Problem 3.