In-Lab 1--Create a simple hash table

Due: at the end of lab, Thursday September 9, 2004

Objective:
To understand the components of a hash table, including:
1. The array to hold the data
2. The hash function to map the key to the array index
3. Collision resolution

Create a simple hash table


• You can use either an array or an ArrayList for the hash table
• You should create a class to hold the data, which will be a key, value pair
• You can use anything you want for your key and value
  • For this in-lab assignment, best to keep it simple
• Use a simple hash function
  • If your key is an integer, just mod by the table size
  • If your key is a String, use the simple hash function given in lecture, or in your book.
• For collision resolution, use open addressing with Linear Probing
• This is covered on pages 411-421 in your text

Your program should include:


• A class to hold the key-value pairs
• A class to hold the array of key-value pairs
• A method to add data to the table
  • Since the hash function and collision resolution method are so simple, you could include them in this method, or you could write separate methods for them.
  • You can hard code input, read it from a file, or input it from the keyboard, however you prefer.
• A way to print out the contents of the hash table for testing.
• You may test your program with a separate class for the driver, or just put a main method in the same class as the array of key-value pairs.
• If you have time, you should implement a search method: Given a key, return the value associated with that key.





In-Lab 2--Experiment with a HashMap

Due: at the end of lab, Thursday September 16, 2004

Objective:
To practice using the HashMap class from the Java Collection Framework

The HashMap class
Go to the Java API and look at the methods in the HashMap class.  Be sure to read about the constructors, as well as the other methods.

What to do


• You are to try out the methods in the HashMap class so you are sure you know how to call them, and what they do when called.
• To do this, you can start with a little code declaring an object of type HashMap
  • It will put some data in the hash table.
  • It will then call some of the methods in the HashMap class.
• Download the code, compile it, and run it, so you can see what it does.
• Modify the code so you become familiar with how the Collection Framework works, how the methods in the HashMap class work, and what they do.
  • To do this, write some code that calls most of the other methods, and and write enough code so you output the results of the calls.

Ideas of other things to try


• Change the method of inputting data. When you use this class, you will almost certainly be inputting from a class with key-value pairs. In this case, you would call put with the arguments getKey and getValue which would be methods in the key-value class.
• You might try making it input the thesaurus that you are using in your Out Lab.
• Change the constructor so you control the initial size of the hash table and/or the maximum load factor. Then get it to rehash the table. See if you notice a time delay while rehashing is going on.

Due: at the end of lab, October 7, 2004

Objective:
Practice doing rotations with balanced BSTs

AVL rotations


• References: if you need help in the way AVL rotations work, any of the following references should help you. A couple of them are applets that will build the AVL tree for you.
  • Anne's lecture on AVL trees and rotations
  • An applet that builds trees, when you give the input
  • Another applet
  • Defintions and explanations
• Build these AVL trees using single rotations. You should add the values to a BST in the order given, then when the tree becomes out of balance, balance it. Be sure that the tree is balanced each time before you do an insertion.
  1. 1, 2, 3, 4, 5, 6, 7
  2. 8, 5, 12, 3, 2, 1

     Build these trees using double rotations

  3. 30, 20, 40, 35, 37
  4. 82, 75, 98, 60, 79, 80

     Build these trees using whatever rotations are necessary

  5. 4, 2, 6, 1, 3, 5, 7, 16, 15, 14, 13, 12, 8, 10
  6. 48, 76, 27, 52, 87, 50, 51, 92, 49, 52

Hand in:


Hand in your diagrams of trees, showing the rotations, reasonably neat. It is expected that every diagram will be correct, since you can check it with the applets. Just be aware you will not have the applets available on an exam :-)(You have two hours to do this, so don't get too impatient)

Next week
Be prepared to demo your programs with data set provided by Mike.

Due: at the end of lab, October 14, 2004

Objective:  Practice building Red-Black trees

Applet to use to check your work.

Build these Red-Black trees


1. 8, 5, 12, 3, 2, 1
2. 1, 2, 3, 4, 5, 6, 7, 8
3. 30, 20, 40, 35, 37
4. 82, 75, 98, 60, 79, 80, 65, 62
5. 48, 76, 27, 52, 87, 50, 51, 92, 49, 90
6. 4, 2, 6, 5, 7, 16, 15, 14, 13, 12, 8, 10

Hand in:

Hand in your diagrams of trees, showing the rotations, reasonably neat. It is expected that every diagram will be correct, since you can check it with the applets.

• This in-lab will be devoted to working on the code for your red-black tree
• Mike will show you how deletions are done in a red-black tree and give you some pseudocode.

Due: at the end of lab, October 28, 2004

Objective:  Become familiar with dynamic programming

What to do:
For this lab, you should do #3 and #4 of the exercises on page 133 of the Neapolitan/Naimipour text. Because you may not all have your text in lab, I will spell out the assignment below.

1. Implement the two algorithms for finding the binomial coefficient given in your text(algorithms 3.1 and 3.2), or in class. One uses recursion to find the binomial coefficient, the other uses dynamic programming.
   • Study the preformance of the two algorithms using different problem instances (i.e. different n and k values)
   • You should devise ways to "study" the preformance. One way might be to count comparisons, but you may be able to come up with better ways. Large values of n and k will show greater differences than small values.
   • Write a report stating how you "studied" the performance and what your study showed. This is to turn in.
2. Modify the algorithm that uses dynamic programming so that it is more efficient.
   • You will turn in this source code, and a run. Be sure you include comments with the source code stating how you modified the algorithm. This will be considered the second part of your report.

Due: at the end of lab, November 4, 2004

Objective:  
Understand the chained matrix multiplication algorithm, and code it in Java

What to do:
Implement the chained matrix multiplication pseudocode from lecture or your text.

• The goal of the chained matrix multiplication algorithm is to find the optimal order in which to multiply a chain of matrices. To do this, two functions are used
  1. the first to find the minimum number of multiplications necessary to built chains of length 2, 3, 4, ...n, and
  2. the second to record the value of k that was used to find the chains of each length.
• You will find the pseudocode for these functions on page 113 and 115 of your text, or, if you did not bring your text, Mike will have a handout that you can use. The first function pseudocode was given in lecture.
• Test your code with the example given in class (so that you know what the answers are, and you can check the logic of your code) The example:
  

     A1 30 X 35
     A2 35 X 15
     A3 15 X 5
     A4 5 X 10
     A5 10 X 20
     A6 20 X 25 

• After you are sure you code is working correctly, run it on this set of data:
  

     A1 29 X 46
     A2 46 X 15
     A3 15 X 5
     A4  5 X 22
     A5 22 X 27
     A6 27 X 25 
     A7 25 X 7
     A8  7 X 32
     

• Hand in: You should email to Mike your source code and a run on both sets of data. The run should include output from the table built of the minimum number of multiplications for all chain lengths, as well as the actual way to parenthesize the multiplications.

Due: at the end of lab, November 18, 2004

In lab today, you will test your n X n checkerboard that you created for the Out-Lab due this week.

When you hand in your source code at the end of lab you should also hand in:

1. A description of the algorithm you used to solve the problem. You may want to include a diagram in your explanation.
2. A chart showing how well your program did on each of the test data that Mike has for you to run.
3. The time complexity of your program.

1. Demo your program that inputs a graph, then finds the shortest path between a given node, and all the other nodes in the graph.
2. Fill out evaluations for this course.

Your have two choices for this:
1. Go to lab at your usual time, and fill out the course evaluation there
   • Mike will keep track of who comes to lab to do the evaluation
2. Fill it out on your own time, and email me that you have done so
   • On the subject line of the email, just put "Survey done"
   • Be sure I can tell who the email is from
   
   To fill out the evaluation go to: http://www.cs.montana.edu/survey/