Work with a partner. If you have a specific partner you want to work with,
let me know by Thursday at noon. Otherwise I will assign you a partner.
Goals
- Implement and understand a few simple search algorithms.
- Get better acquainted with generics
and interfaces in Java.
Relevant code
- SearchableCollection.java, the
interface that we'll use for all of our search implementations.
- LinearSearchableCollection.java, a
collection that uses linear search to search for specified search keys.
- Person.java, a stripped-down version of the Person we
used in the first programming assignment this term. This class is here to help you
keep track of the difference between search keys and the items in the collection.
This implementation of Person supports comparison of a Person to a String by
comparing the String to the Person's family name.
- TimingDemo.java, a simple demonstration of how
to count the number of milliseconds a chunk of code takes.
Background
In class on Feb 13, we discussed the search problem in general, and
looked at the two most common and simplest search algorithms:
linear search
and
binary search.
For this assignment, you'll implement some search algorithms based on a given interface,
and then you'll time your implementations to see whether they perform as you
expect them to.
Important note: The Java standard library contains many implementations
of search algorithms. For example, ArrayList includes an method called
indexOf,
which performs a linear search on the ArrayList contents. For this assignment,
you'll be writing your own implementations of various algorithms to help you understand how
they work. So for example, we'll use ArrayLists to store items sometimes, but we will
not search using indexOf. Once you understand the algorithms, we'll talk about how to use the
built-in versions in Java in your future software development.
What to do
- Study the classes and interfaces listed under "Relevant code" above, and write down and
ask questions you have about them. "Study" means reading, thinking, compiling, running, and
experimenting. Really: spend some time getting to know this code.
- Create a class called BinarySearchableCollection that implements the SearchableCollection interface.
Use LinearSearchableCollection as a model, but adjust your method implementations to ensure that
the BinarySearchableCollection is kept sorted, and uses binary search to search for search keys.
- How are you going to test BinarySearchableCollection? Think about this, and put your test code in
a main method in BinarySearchableCollection.
- Create a class called SearchTimer, whose job is to print out timing data for each of your
search algorithms. The structure and behavior of SearchTimer is up to you, but we'll discuss
some approaches in class.
- Write a short report (1-3 pages, depending on how many charts and graphs you include) comparing
your timing data with what the Big-O analysis of each algorithm would predict. Make sure
your report covers linear search and binary search.
Submit your report in PDF form as searchreport.pdf.
A little help
- Implement your BinarySearchableCollection code without worrying about
doing large-N tests at first. Get it working with small examples first.
- I recommend not using Person for your timing tests. Go with
BinarySearchableCollection<String, String>, etc. It's just easier to come up with
large-N lists of strings than it is to come up with large-N lists of people.
- As part of your planning, spend some time thinking about how you're going to generate
long lists of strings. Also, think about whether you should be timing failed searches
(i.e. looking for strings that aren't in the collection), successful searches
(i.e. looking for strings that are in the collection), or a mix of both.
- When you're collecting timing data, time only a loop containing a large number
of searches. Don't time how long it takes to load the data into your collection, and don't
time code that includes print statements. Those items would throw off your times.
- Since we're measuring times in milliseconds, we'll need pretty big N's to get useful
times. It's easy to quite a few searches and still end up with a milliseconds count of 0.
- You might find it helpful to have access to
a large list of English words.
And of course...
Start early(!), ask questions(!!), and have fun(!!!).