©2010 Felleisen, Proulx, et. al.

8  Abstracting Over the Data Type

Practice Problems

Practice problems help you get started, if some of the lab and lecture material is not clear. You are not required to do these problems, but make sure you understand how you would solve them. Solving them on paper is a great preparation for the exams.

Finish Lab 8 and include all the work in your portfolio.

Pair Programming Assignment

8.1  Problem

Binary Search

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

1. In the 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.

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

3. Now, design the method binarySearch in the class Algorithms that consumes the lower index (inclusive), the upper index (exclusive), an ArrayList of data of the type T, a Comparator of the type T, and an object of the type T and produces the index for this object in the given ArrayList or throws a RuntimeException if the object is not found.