Lab 5

1 Lab Objectives

• To give you practice with Java hashtables.

• To introduce you to Java’s built-in lists.

• To introduce you to Javadoc, Java’s built-in documentation system.

If you already know Java’s LinkedLists, Hashtables, and Javadoc, feel free to skip to the challenge problem at the end.

2 Problem Setup

Many websites recommend books and movies based on combinations of items that other people have liked. For example, if Sue likes "Avatar" and "Driving Miss Daisy" and Joe likes "Avatar", the system might recommend that Joe watch "Driving Miss Daisy". This week, we use this problem as a foundation for practicing with hashtables, lists, and Javadoc (Java’s documentation system).

Our goal is to create a recommendation system that contains a mapping from users to lists of items that they like. You might want to think about how you would design this before seeing the detailed problems below.

3 A Crash Course in Java’s built-in Lists

We’ve made several references in class to Java’s built-in list implementation (called LinkedList). For today, we just want you to get familiar with how to create and add elements to lists. If you want to use the LinkedList classes, you first need the following statement at the top of your file:

import java.util.LinkedList;

The LinkedList package has several minor and one major difference from the lists we’ve created manually. The minor differences arise in the names of operators. The major difference is that Java’s operators do not return a new list. Instead, they modify an existing list. We’ll get into the serious implications of this difference next week. For now, it largely means that you have to write your code somewhat differently than before. This is best seen by example. Imagine that we wanted to write code to create a list with one element. Rather than write something like

4 Problems (be sure to finish)

These problems work through information that we will assume you know in the rest of the course. Even if you have to work briefly at home to finish these up, please do so as they will affect future lectures or assignment requirements.

• Create a Recommender class with a hashtable called Likes that maps names of people to lists of names of items (books, movies, songs, etc). Use Java’s LinkedList class as described above for the list. Use an appropriate access modifier to prevent another class from accessing or editing the hashtable directly.

  You may find Java’s hashtable documentation useful for reference.

• Add a method addLikes that consumes the name of a person and the name of an item and adds that item to the person’s likes entry.

• Add a method bothLiked that consumes the name of a person and the names of two items and returns a boolean indicating whether the person likes both items.

• Create an IRecommender interface for the class that requires the addLikes and bothLiked methods.

• JavaDoc: Now, we want to add documentation to this system. Java has a built-in documentation system called Javadoc that produces documentation in html. Both DrJava and Eclipse have options for generating Javadoc output automatically (in DrJava, go to the Tools menu, then Javadoc; in Eclipse, go to "Generate Javadoc" under the Project menu). Run Javadoc documentation generation on your Recommender class. Explore the output: what has Javadoc detected automatically about your class hierarchy?

• The Javadoc documentation is still missing some important details, like descriptions (purpose statements) of the methods. Javadoc has an annotation language, with which you add such details to fields and methods through stylized comments. See this tutorial on Javadoc. Use it to add your name and purpose statements to each method.

• If you want to see what Javadoc does on a more extensive class hierarchy, download the Infinite Trees code from Monday’s class and generate its baseline Javadoc.

5 Challenge Problem: Longest Common Subsequence

We want to write a function lcs that consumes two strings and produces an string. The output string is the longest common subsequence of characters in the two input strings. Characters in subsequences need not be consecutive in the original word, but they must occur in order. For example, the longest common subsequence of "baseball" and "fable" is "abl". If a world has two subsequences of the same maximal length, return either one.

A good solution to this will take a lazy approach and compute the value for an expression only once. Your submitted solution should not simply generate all possible subsequences from all pairs of positions into the strings then look for the longest (though if thinking about the program this way first helps you get a feel for the problem, feel free).

As a hint, given input strings s1 and s2, you can compute the lcs of the first i chars of s1 and the first j chars of s2 by looking at:

• the lcs of i-1 chars from s1 and j chars from s2,

• the lcs of i chars from s1 and j-1 chars from s2,

• the lcs of i-1 chars from s1 and j-1 chars from s2,

• and knowing whether the i-1st character of s1 and the j-1st character of s2 are the same.

6 What to Turn in

Submit all .java files that you produced for this assignment to the Lab5 area via Turnin.