Big Java / Java Concepts Lab 21

1.

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.

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.

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.

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?

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?

12.

                5
            /      \
         3            8
       /   \        /   \
      1     4      6      10
       \            \    /
        2            7  9

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;
   }
}

14.

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

13.

14.

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?

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.

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.

What changes did you need to make?