Mike's Outlab 2 Submission Instructions
E-mail your completed assignment to mthiesen@gmail.com. Attach all of your source code (.java files), a sample run (should be a .txt file), and your report to your e-mail. Do not send any .class files. Do not zip up or archive the files. Please use Microsoft Word for your reports. If you can't use MS Word, print out your report and bring it with you to your lab. I have no way to view Word Perfect files or MS Works files, so you must print them out and give them to me in person if you want them graded!
IMPORTANT: Your subject line should follow the following format:

 CS223-xx outlab2 Name 

Out-Lab 1:  Implement a Thesaurus using Hashing

Due: in one week (September 16, 2004) at the beginning of lab.

Description

A thesaurus is a dictionary of synonyms.  For example, here is a small thesaurus, with each word followed by its synonym(s):
    close   near  confined
    confined  cramped
    correct  true
    cramped  confined
    near  close
    one  singular  unique
    singular  one  unique
    true  correct
    unique  singular  one

Inplement a Thesaurus using a Hash table. This will involve:
1. Creating an Pair class much like the Entry class from SortedArrayDictionary. The word to be looked up will be the key, the first item of the Pair. The synonyms will be the second item of the Pair.
2. Use the hash function h(x) = x mod tableSize and the algorithm that involves Horner's rule to convert the key into an integer.
3. For this week, use linear probing for collision resolution. Your assignment for next week will be to use double hashing and chaining, and make a comparison of the efficiency of each.
4. Use a table size with a load factor about 0.5. Put a counter in your code to count the number of collisions. You will use this next week when you handle the collisions differently.
5. Put data in the thesaurus from a file
   • This data file has the key word first, then the synonyms on the same line.
   • It is up to you to decide on the size of your hash table. This is usually decided by knowing something about your data, so be sure to take a look at the data file
   • After the file is input into your hash table, you should output the number of collisions that had to be handled.
6. Write a driver class test the functionality of your thesaurus. It should:
   • Ask the user what word they would like the synonyms for.
   • Return the synonyms for a given word.
   • Respond appropriately if the word is not in the hash table.
7. You may NOT use the HashMap class from your book, or any other prewritten hash class. I want you to implement the hash table and handle the collisions yourself. You can use anything else from the STL

Out-Lab 2:  Handle Collisions Differently and Vary the Hash Function

Due: in one weeks (September 23) at the beginning of lab.

Using the lab you wrote last week, change the way you are handling collisions and the hash function.

1. As you change your code, you should probably keep backup copies of the original, unchanged code. Do this each time after you get something working, then change it for a new hash function, or collision resolution strategy.
2. First, use Chaining to handle collisions. You should adjust the table size so the load factor is about one. Remember, you must keep the table size prime.
3. Next, use double hashing. You can decide on the second hash function. The table size should be the same as you used for linear probing.
4. Choose one of the above collision resolution method (the one you feel was the most efficient for this problem) and change the hash function used to see if that makes a difference in the number of collisions. Possibilities:
   • Try a simpler hash function than the polynomical hash function required above. Perhaps just use the mod function with the key, or part of the key. Be sure to comment what you are doing. Don't try to keep the code efficient here, just experiment to see how different things work. Something simple may be as good as something more complex.
   • You can probably find other hash functions in other books, or online. You may try something you make up yourself.You should keep track of where different functions come from.
   • You should try at least two different hash function for this part, so you can make some comparisons of efficiency.

1. Make a table (or two) to show the number of collisions as you varied the collision resolution methods and the hash function. Explain what you tried, and try to analyze the variables used in terms of efficiency and programmer time to implement. (This will be about one-third your grade, so spend some time on this report)
2. Hand in your source code along with the above. Trial runs are not necessary if you got a chance to demo your program.

Out-Lab 3--Build a Binary Search Tree

Grading Criteria

Purpose
The purpose of this assignment is to have some practice programming a tree from scratch.

What to do

1. Design and implement a class for the node in your tree.
   You MAY NOT put a parent pointer in the node class (since then you could just use the code I gave you in class to do this assignment).
2. Design a class for the tree itself. One data member (or attribute) in this class should be a reference variable to point to the root.
3. Decide on the functionality you will need. You must implement insertion, deletion, search, and outputting the tree's contents in order.
4. Write a driver to call your methods.
5. You can decide on what you want your tree to hold (the Comparable object) when you implement the driver, and input the data however you want. One idea might be to just make a tree to hold integers until everything is working, then modify it to handle the objects.
6. Remember that your key must be Comparable. Any methods in your tree class that say what the data type of the key is should be Comparable, not Object. This lets you use the compareTo method in the tree class.
7. Hand in your source code and the run.

Out-Lab 4--Solve a Programming Contest Problem

Purpose
The purpose of this lab is to give you experience analyzing a problem, and deciding the best way to solve it.

What to do
Below are three Programming contest problems. You should take a look at them, and decide which one you want to solve.

1. Is It a Tree
   • This problem has a solution posted with it, so you may not use it. I just thought you might be interested in a solution.
2. Word Search Wonder
3. Money for Nothing
4. If you solve both, you will get extra credit.

Out-Lab 5--Code a Red-Black tree

Due date:  You will have two weeks to complete this entire lab, but part of it will be due in one week.

Grading Criteria

Purpose
The purpose of this lab is to

1. Understand how a red-black tree keeps a BST balanced, and
2. Gain experience coding a complex algorithm

What to do


• This assignment is to write in Java a red-black tree that can handle any Comparable object
• You may work with a partner for this assignment.
• By the end of the first week (October 21) you must have the insert and print methods working and ready to demo in lab
• By the end of the second week (October 28) you should have the delete and search methods working and ready to demo.
• You may design the Entry (or node) class any way you want ( i.e. no restrictions on using a parent pointer)

Out-Lab 6--Moving on a checkerboard

Due date:  November 18, 2004

Purpose
The purpose of this lab is to give you a chance to try out your problem solving skills.

The problem


• You are given an n X n checkerboard and a checker. You must move the checker from the bottom edge of the board to the top edge of the board according to the following rule. At each step you may move the checker to one of three squares:
  1. the square immediately above
  2. the square that is one up and one to the left (but only if the ckecker is not in the leftmost column),
  3. the square that is one up and one to the right (but only if the ckecker is not in the righttmost column),
• Every time you move from square x to square y, you receive p(x,y) dollars. You are given p(x,y) for all pairs (x,y) for which a move from x to y is legal. Do not assume that p(x,y) is positive.
• You program should first solve this problem for the 5 X 5 and 8 X 8 checkboard with the given p(x,y) values.
  • Here is a big checkerboard for you to try out 100 X 100 It does not have the bottom row zero, but you should ignore the numbers in the bottom row.
  • Write in pseudocode an algorithm that figures out the set of moves that will move the checker from somewhere along the bottom edge to somewhere along the top edge while gathering as many dollars as possible. Your algorithm is free to pick any square along the bottom edge as a starting point and any square along the top edge as a destination in order to maximize the number of dollars gathered along the way.
  • Implement your algorithm in Java. You should be striving for the optimal amount of money with the given input.
  • What is the running time of your algorithm?

  In lab on November 18, you will exchange and run each others programs and a prize (points?) will be given for the program that earns the most money with a new n X n input. (Hint: the n will be large) In case of tie, the most efficient algorithm will win.

Out-Lab 7--Store a graph, then find a shortest path

Due date:  December 2, 2004

Purpose: The purpose of this lab is to give you experience working with graphs.
This is a two part assignment: the first to develop a class to store a graph, the second to find the shortest path through a graph.

1. Store the graph: you may use either an adjacency list or an adjacency matrix. They both present their own problems.
   • Extra credit for using an adjacency list.
2. You can use any of the code from the library or past assignments
3. You should enter the data from the file airport.txt. The format we decided on has the number of nodes on the first line, the names of all the nodes on the next n lines, and on each remaining line it has a node, then a distance to an adjacent node, the adjacent node name, for however many nodes are adjacent. Take a look at the file to see exactly what is used for separators.
4. An example of the type of graph you should be able to store is in the diagram at right.

Part 2--A Shortest Path Problem

1. You are to write a program that allows the user to enter the graph at right (or another similar to it), from a file cities.txt, then finds the shortest path from a city the user chooses to all other cities in the graph.
2. You can use any of the Java library or any code you have previously written.
3. The I/O is up to you, but should be user friendly, allowing the user to give a file name where the data is located, and should output the shortest path to all the cities from the given city.