Big Java / Java Concepts Lab 21

Sets and Maps

1.

Consider the following line of code:

Set names = new HashSet();

Why is the variable names of type Set rather than type HashSet?


2.

Unlike the ListIterator interface, the Iterator interface for a set cannot add an item to a specified position. Is there a reason for this? If so, what is it?


3.

The Iterator interface contains a next method. Why does the interface not contain a previous method?


4.

For each of the following problems, indicate whether it would be more appropriate to use a HashSet or a HashMap, and explain your reasoning:

1. A program that keeps track of bank account information (name, account number, account type, balance)

2. A phonebook program that stores your friends' names and phone numbers

3. A program to inventory the contents of your refrigerator

4. A program that stores a list of your favorite fruits

5. A program that stores a list of the favorite fruits of all the students in your class.


5.

Suppose you write a program to keep track of the hometowns of all the students in your class using a HashMap. What values would you use for the key set? What values would you use for the value set?



6.

The static method TimeZone.getAvailableIDs returns an array of time zone ID strings, such as America/Los_Angeles or Asia/Bankgok. Once you have an ID, you can get the time zone by calling the static method TimeZone.getTimezone. Finally, to find the time at a given time zone, call
DateFormat timeFormatter = DateFormat.getTimeInstance(); 
timeFormatter.setTimeZone(zone);
Date now = new Date();
System.out.println(timeFormatter.format(now));

Unfortunately, there is no fast method for finding the time zone for "Los_Angeles". We want to speed up this search by using a Map<String, TimeZone>.

Write a program that calls getAvailableIDs, strips out the city names (by discarding the Continent/ prefix and turning underscores into spaces), gets the TimeZone objects, and puts the (city name, time zone) pairs into a map.

To verify that your map is set up correctly, print out the first ten entries.

What is the code for your program?



7.

What does your program print?



8.

Now enhance your program so that users can enter city names. Look up the time zone for the city and print out the local time, or tell the user if you can't find a matching city.

City: Los Angeles
Local time: 06:26:09
City: Berlin
Local time: 15:27:12
City: Fargo
Local time: not available
City: Quit
Bye

What is the code for your program?

Hashing


9.

Create an Employee class. The class contains the id (of type long), name, phone number and job title of the employee. Implement the methods:

public boolean equals(Object other)

public int hashCode()


10.

Write a test program that stores a set of employees in a HashSet<Employee> and prints out the elements in the set. Try adding the same employee twice. What is the code of your test program? 



11.

How can you simplify the equals and hashCode methods if you know that employees are uniquely determined by their ID?

Binary Search Trees


12.

Write a program that builds up the following binary search tree and prints its contents.

                5
/ \
3 8
/ \ / \
1 4 6 10
\ \ /
2 7 9
What is the code for your program?



13.

In this exercise, we will add an iterator to the binary search tree class in the text book. We want to be able to execute code such as

BinarySearchTree tree = new BinarySearchTree();
// add elements
Iterator iter = tree.iterator();
while (iter.hasNext())
do something with iter.next();

The iterator should visit the tree elements in sorted order.

Here is a naive attempt at the iterator:

public class BinarySearchTree
{
. . .
public Iterator iterator() { return new BSTIterator(); }

private class BSTIterator implements Iterator
{
public BSTIterator() { current = root; }
public boolean hasNext() { return current != null; }
public Object next()
{
Object r = current.data;
if (current.left != null) current = current.left;
else current = current.right;
return r;
}
public void remove() { throw new UnsupportedOperationException(); }

private Node current;
}
}

Unfortunately, this simplistic approach won't work. Which elements will the iterator visit when it traverses the tree of problem 12?





14.

The simplistic implementation can't back up when it reaches a leaf. Unfortunately, our Node objects don't have a pointer to the parent. Therefore, we need to store a stack of partially explored nodes. When reaching a leaf, pop off the top of the stack and continue the search at that node.

   private class BSTIterator implements Iterator
{
. . .
private Node current;
private Stack<Node> partiallyExplored;
}

Draw pictures of the state of this iterator for each traversal step in the tree of problem 11.



13.

Now implement the iterator class. What is the code for your implementation?

14.

Add an iterator to the program that you wrote in problem 12. What is the code for your test program?

Tree Sets

15.

Write a program that uses a tree set to store employees. Ask the user to enter employee information, add each employee to the three set. When the user is done, print the elements of the tree set. You can modify the program you created in problem 10.


16.

Run both implementations of the program (the one that uses a hash set and the one that uses a tree set) and insert information about the employees Brown, Smith and Johnson (in that order). What is the output of both programs?

Heaps

17.

A min-heap is an almost complete tree in which the values of all nodes are at most as large as those of their descendants. A max-heap is the opposite of a min-heap. The largest element is stored in the root of a max-heap.

Turn the MinHeap class in the book into a MaxHeap class. What is the code?


18.

Write a tester class that tests your MaxHeap.

What is the code?


19.

For convenience, the MinHeap and MaxHeap class leave the 0 element of the array empty. Then the child nodes of the node with index i have index 2 · i and 2 · i + 1 , and the parent node of the node with index i has index i / 2.


Change your implementation so that the 0 entry is not wasted. (Hint: Look at the HeapSorter class of your text book.)  Run your test program again to verify that your changed implementation works correctly.

What changes did you need to make?