Laboratory Exercise

Search Times for Lists

Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004

Purpose

Prerequisites

Understanding of the following sections of Algorithms and Data Structures: The Science of Computing:

Background

This exercise empirically verifies the theoretical time to search lists. Doing this requires establishing some theoretical background not presented in Algorithms and Data Structures: The Science of Computing, and writing a subclass of the book’s List class with which to do the main experiment.

The List Class and Its Subclasses

Chapter 11 of Algorithms and Data Structures: The Science of Computing thoroughly describes the List class. A complete implementation of this class is available, in a file named List.java. The “Final Details” section of this document explains where to find this file.

Any Java source file that uses the List class should “import” it via a statement of the form

This exercise requires defining a subclass of List, a definition that is subtle in several ways. Section 11.5.1 of Algorithms and Data Structures: The Science of Computing discusses the subtleties. For this exercise, pay particular attention to how to write makeNewList methods.

Wrapper Classes

The list subclass in this exercise will represent lists of integers. Unfortunately, integers, i.e., values of Java type int, are not objects in Java, and so cannot be stored directly in lists. (As explained in appendix section A.2.1 of Algorithms and Data Structures: The Science of Computing, Java has two kinds of data: objects and non-objects; List objects (and most other collections) can hold any kind of object, but not non-object values.) Fortunately, the designers of Java anticipated such problems, and provided “wrapper” classes for all the non-object data types. A wrapper is a very simple object that basically does nothing except contain one value of a non-object type. For example, instances of the wrapper class Integer each hold one int, instances of Character hold a char, etc. To store a non-object value in a collection, create a wrapper object to hold the non-object value, then store the wrapper in the collection. For example

To retrieve the non-object value from the collection, retrieve the wrapper and then extract the non-object from the wrapper. For example

(The notation (Integer) before someList.getFirst() in this example is a cast that tells the Java compiler that this particular use of getFirst will return an Integer object. Casts are often used when retrieving data from collections, because the retrieval message is usually declared to return some very generic class— e.g., Object — but client programmers often know much more precisely what classes their application stores in the collection. See appendix section A.5.2 of Algorithms and Data Structures: The Science of Computing for more information on casts.)

Here are some common wrapper classes from the Java class library. Every wrapper class provides a constructor that takes a single value of the corresponding non-object type as its only parameter. Every wrapper class also handles a parameterless message for extracting the non-object value from a wrapper, as indicated in the following table (the examples above of wrapping and unwrapping an int illustrate how one might use these constructors and extractors).

Non-Object Type	Wrapper Class	Extraction Message
int	Integer	intValue
long	Long	longValue
double	Double	doubleValue
float	Float	floatValue
char	Character	charValue
boolean	Boolean	booleanValue

Exercise

The heart of this exercise is an experiment that tests a hypothesis about the worst-case execution time of searches in lists. In order to do this experiment, you need to form the hypothesis, and write a subclass of List that supports the experiment. The lab exercise thus breaks down into three parts:

Search Time in Lists

The first task is to derive an asymptotic expression for the worst-case time to search a list. In terms of the List class, this is the worst-case execution time of the find method. Express time as a function of list length. Note that the worst case happens when the item being sought is not in the list at all.

A List Subclass

The experiment’s goal is to verify that the asymptotic expression for list search time corresponds to the actual behavior of lists. Doing this requires a way to create lists of a variety of lengths, with which to time find messages. Thus the second task in this lab is to define a subclass of List that provides a new constructor. This constructor should take two integers, n and m, as its parameters, and should initialize a list to contain the integers from n to m, in ascending order.

The new constructor is the only unique feature that the List subclass needs (but don’t forget that every List subclass needs a makeNewList method). Everything else the experiment needs can be inherited from List.

The Experiment

Finally, the third task in this lab is to do an experiment that tests the hypothesis that the worst-case time to search a list is asymptotically equal to the expression derived in the first task.

Data collection for this experiment will mainly involve timing worst-case searches in lists of various sizes. The subclass defined in the second task will be helpful here, because it makes it easy to initialize lists of known sizes, and with precisely known contents (so that it is easy to calculate a value that won’t be in the list, and therefore will cause a worst-case search).

Final Details

Finding the List Class

The List.java file can be downloaded from the World Wide Web, or copied from the Course Materials file server.

Documentation for the class is also available on the Web. The main documentation page is an index to documentation for all the Java classes written for use with Algorithms and Data Structures: The Science of Computing. To see the documentation for a specific class, click on that class’s name in the left-hand panel of the page.

Submitting Your Work

Turn in your derivation for the worst-case time to search a list, and a report on your experiment. Be sure the report clearly says what the experiment’s hypothesis is, describes how you did the experiment (including printouts of relevant code), shows the data you collected, shows your analysis of the data, and states your conclusion about the validity of the original hypothesis. The derivation for the worst-case execution time can be included in the “hypothesis”section of the report.