Assignment 8

Goals: Learn to work with parametrized types. Learn to manipulate and mutate ArrayList – a direct access data structure.

Instructions

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:

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

There will be a separate submission for each problem - it makes it easier to grade each problem, and to provide you with the feedback for each problem wou work on.

The two submissions will be organized as follows:

• Submission HW8P1: The log file and the solution to the paramterized deque problem in one .zip file

• Submission HW8P2: The files Algorithms.java and ExamplesAlgorithms.java in one .zip file

Due Date: Thursday, March 13th, 11:59 pm.

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.

• Review the work you have done in Lab 8 and finish all problems.

Pair Programming Problems

Problem 1: Parametrized Dequeue

The data structure Deque you have built in the previous assignment 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 HW08Problem1.

Import into it your solution to Problem 2 from the previous assignment.

• Now change the classes Node, Sentinel, and Deque so that they are parametrized over the type of data each Node contains.

  Comment out all tests for the methods in your ExamplesDeque class and modify the examples of data so they would work with the new class definitions.

• Define a new class of data of your choice (books, pets, persons, ...) and make examples of lists of the items of this type.

• Uncomment all but the last two methods for the class Deque (and all helper methods they refer to in the class Node or the class Sentinel) and adjust them so that they work with the parametrized class definitions. Adjust all tests as needed.

• Add tests for all methods but use now the lists of the items of the new type of data you have defined.

• When testing the method find make sure that the object you are looking for is identical to the one that has been inserted into the Deque, as it relies on the Java pre-defined equals method.

• Next, design two classes that implement the Comparator interface in Java Collections Framework — one that compares Strings by lexicographical ordering, one that compares the objects you have designed in some meaningful order.

• Design the method insertSorted that consumes a Comparator parametrized over the type of data stored in the Deque and an element of the type T and inserts a new node that contains the given item into this ordered Deque, preserving the ordering.

  Design test for both types of data: Strings and the one’s you have defined.

• Design the method removeSorted that consumes a Comparator parametrized over the type of data stored in the Deque and an element of the type T and removes the node that contains the given item from this ordered Deque. If the element is not found, throw a RuntimeException with the message "Item " + t.toString() + " is not in this queue".

  Design test for both types of data: Strings and the one’s you have defined.

Problem 2: Binary Search

Start with a new project HW08Problem2 and create two files: Algorithms.java and ExamplesAlgorithms.java.

• In the class ExamplesAlgorithms make examples of sorted ArrayLists of Strings and Integers. Of course, there is no constructor that creates an ArrayList filled with values. You need to define a method initData that adds the values to the initially empty ArrayLists one at a time.

• Next, design two classes that implement the Comparator interface in Java Collections Framework — one that compares Strings by lexicographical ordering, one that compares Integers by their magnitude.

• Now, design the method binarySearchHelper in the class Algorithms that consumes five arguments:

  • an ArrayList of data of the type T (and sorted by the given Comparator)

  • the Comparator of the type T that determines the sorting order

  • the object of the type T that we are looking for

  • the lower index (inclusive)

  • the upper index (inclusive)

  The method produces the index at which the given object is located in the given ArrayList, within the given range of indices. If the object is does not appear in the given ArrayList the method returns -1.

• Design the method binarySearch in the class Algorithms that consumes three arguments:

  • an ArrayList of data of the type T (and sorted by the given Comparator

  • the Comparator of the type T that determines the sorting order

  • the object of the type T that we are looking for

  The method produces the index at which the given object is located in the given ArrayList. If the object is does not appear in the given ArrayList the method returns -1.

Make sure you test all possible situations: searching an ArrayList of size 1, finding the item at either end of the range, as well as item not found at either end or in the middle.