Laboratory Exercise

Lab 10 — 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.

Theoretical Execution Time

Chapter 11 of Algorithms and Data Structures: The Science of Computing presents an algorithm for searching lists. The book does not, however, derive any theoretical times to search a list.

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 times of searches in lists. However, before doing this experiment, a hypothesis about the worst-case execution time of searches in lists is needed, as is 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, in 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. Nominally, n is the inclusive lower bound on the range of integers to put in the list, and m the inclusive upper bound. However, n may be greater than m, in which case the list should be made empty.

The new constructor is the only unique feature that the List subclass needs. Don’t forget, however, that every List subclass needs a makeNewList method. Everything else the experiment needs can be inherited from List.

The Experiment

The final task in this lab is to do an experiment that tests the hypothesis that the worst-case time to search a list is the asymptotic 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).

Final Details

Finding the List Class

Documentation for List 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

This lab is due on Monday, November 22. Turn in a document that includes your derivation for the worst-case time to search a list, and a report on your experiment. As usual, the report should include a statement of the hypothesis you tested (this can largely be part of the derivation of worst-case search time), a description of your experimental procedure (probably supported by a printout of your List subclass and other code you wrote for the experiment), all the data you collected, a description of your data analysis and its results, and a statement of the conclusions you reached concerning the validity of the hypothesis. Finally, include a sentence or two in the report saying whether you consider lists to be “good” data structures for searching (this part of the report should start by defining what you think makes a data structure good for searching, then say why you think lists are or aren’t good under that definition).

Revisiting this Experiment

In a couple of weeks, we will do an experiment similar to this one, except that it deals with the worst-case times to search trees. I will ask you in that exercise to compare your tree results to your list results, so it will be a good idea to be sure you save this week’s results — either by keeping a copy when you turn in the report for this experiment, or by holding on to your report when I return it (which should be well before you do the tree experiment).