Assignment •  FAQ •  Development Guide •  Code •  Checklist •

HW6 Development Guide

 

You should use this guide to help you to complete your assignment. You should follow it step by step, resolving errors before going on to the next step. Once you can follow this guide without errors, you should come up with more test cases and compare the output of your program with that of the solution.

Before we get started, make sure you are comfortable with using the jdb commands from previous homeworks as we will use them in this development guide as well.

1. Begin by writing the class implementation for UCSDStudent in Driver.java. Your class implementation should include all UCSDStudent methods that will be called by the HashTable code.
   Reference the Variable class implementation in Calculator.java for an example of the correct syntax. You can find this under the Code page of the assignment writeup.
2. Write the debugOn and debugOff methods in HashTable.java.
3. At this point, your program should report three "missing return statement" errors when compiled with make.

$ make Driver
javac -g Driver.java
./HashTable.java:83: error: missing return statement
}
^
./HashTable.java:99: error: missing return statement
}
^
./HashTable.java:104: error: missing return statement
}
^
./HashTable.java:109: error: missing return statement
}
^
4 errors
make: *** [Driver.class] Error 1


Get rid of these errors by adding return statements to the incomplete non-void methods in HashTable.java. Make sure that your program compiles without any errors.

4. Write the HashTable constructor. initialize each data field of the hashtable, and increment the static counter to keep track of how many hash table you have.
5. Try running Driver. It should prompt you to insert, lookup, or write. The write (i.e. toString) method is already given to you, so your job is to write the insert and lookup functionalities.

   $ ./Driver
   Initial Symbol Table:
   Hash Table 1:
   size is 5 elements, occupancy is 0 elements.
   
   Please enter a command:
   (c)heck memory, (i)nsert, (l)ookup, (o)ccupancy, (w)rite:
   

6. Write the locate method. Refer to leture handouts as to how to proceed to implement the bully algorithm.

   Note: All the hashing, (assigning to initial location, increment, and the loop of going to the next location) goes here. The method stops when it finds an empty index, finds the same item at an index, finds an occupied index that is less than the current element, or if you exhaust the table.
   Note: This method should leave index, which is a instance field of Hash Table that all methods have access to, where it left off so that Insert and Lookup know that location.

   Also remember to utilize debug messages as a development tool.


7. Next, write the insert method.

   Note: This method has no loops. Bumping is handled via recursion. Duplicate insertion of an item at its last probe location in a full list is a valid test case (but don't test that case now).

   When you are done, you should expect insert to be printed correctly.


8. Now let's check the functionality of the locate and insert methods using jdb. Run jdb Driver and follow the instructions. In your second window you should type:

$ \jdb -attach 80[xx]
Replace xx by the value that you copied from your first screen.
... First, we will set a breakpoint in the locate method.
main[1] stop in HashTable.locate
Deferring breakpoint HashTable.locate. It will be set after the class is loaded.
main[1] run

Now, in your first screen you should insert Aa with student number 1 to the Hash Table. Switch back to your second screen and continue running jdb.

main[1] next
Execute next as many times as needed until you execute the line that saves the hash code of the parameter element

main[1] print hashValue <replace hashValue by the variable you used to save the hash code of element>
     hashValue = 162
162 is the ASCII sum for Aa. If this is not correct, make sure you implemented your UCSDStudent hashCode method correctly!

main[1] next
Execute next as many times as needed until you set index using the formula discussed in class.
main[1] print index
     index = 2
If index is not equal to 2, you made a mistake in your algorithm. In that case, go back and debug your locate before you continue.

main[1] next
Execute next as many times as needed until you return from locate. At this point you enter the insert method. Continue entering next until you finally insert element to the table.
main[1] print table[index]
     table[index] = "name: Aa Studentnum: 1 "
If you get different results, go back and debug your insert before moving on. Once done, continue using jdb to insert the following: name: Bb Studentnum: 2 and name: Cc Studentnum: 3. Once you finish, your output should match the following when you write the Hash Table:

The Symbol Table contains:
Hash Table 1:
size is 5 elements, occupancy is 3 elements.
at index 1: name: Cc with studentNum: 3
at index 2: name: Aa with studentNum: 1
at index 4: name: Bb with studentNum: 2



Remember, you can run your program normally with the following command.

$ ./Driver
Initial Symbol Table:
Hash Table 1:
size is 5 elements, occupancy is 0 elements.
Please enter a command:
(c)heck memory, (i)nsert, (l)ookup, (o)ccupancy, (w)rite: i
Please enter UCSD Student name to insert: Aa
Please enter UCSD Student number: 1
Please enter a command:
(c)heck memory, (i)nsert, (l)ookup, (o)ccupancy, (w)rite: i
Please enter UCSD Student name to insert: Bb
Please enter UCSD Student number: 2
Please enter a command:
(c)heck memory, (i)nsert, (l)ookup, (o)ccupancy, (w)rite: i
Please enter UCSD Student name to insert: Cc
Please enter UCSD Student number: 3
Please enter a command:
(c)heck memory, (i)nsert, (l)ookup, (o)ccupancy, (w)rite: w
The Symbol Table contains:
Hash Table 1:
size is 5 elements, occupancy is 3 elements.
at index 1: name: Cc with studentNum: 3
at index 2: name: Aa with studentNum: 1
at index 4: name: Bb with studentNum: 2


9. Finally, write the lookup method. Like insert, lookup delegates to locate. In fact, the return value of lookup relies entirely on the return value of locate. Please note the return type of lookup and how you would be able to utilize locate to return the element you are looking for in your hashtable. It is important to understand this as it will greatly help you write a very simple lookup by relying on locate, so if you come across issues in look up it could be with a high probability that your locate is not implemented correctly. Remember to set index before calling locate.

After implementing lookup, use the following jdb commands to check your method:

$ jdb Driver
Now in a second terminal, run the following
$ \jdb -attach 80[xx]
Replace xx by the value that you copied from your first screen.
Set a break point in the lookup method by typing the following

main[1] stop in HashTable.lookup
Deferring breakpoint HashTable.lookup.
It will be set after the class is loaded.
Execute the program by
main[1] run
Now in the first window enter the choice like below
Listening for transport dt_socket at address: 80xx
Initial Symbol Table:
Hash Table 1:
size is 5 elements, occupancy is 0 elements.

Please enter a command:
(c)heck memory, (i)nsert, (l)ookup, (o)ccupancy, (w)rite:i
Please enter UCSD Student name to insert: Sravya
Please enter UCSD Student number: 125
Please enter a command:
(c)heck memory, (i)nsert, (l)ookup, (o)ccupancy, (w)rite:i
Please enter UCSD Student name to insert: Tiffany
Please enter UCSD Student number: 224
Please enter a command:
(c)heck memory, (i)nsert, (l)ookup, (o)ccupancy, (w)rite:i
Please enter UCSD Student name to insert: Yixuan
Please enter UCSD Student number: 323
Please enter a command:
(c)heck memory, (i)nsert, (l)ookup, (o)ccupancy, (w)rite:l
Please enter UCSD Student name to insert: Sravya
In the second terminal you should see something similar as below
Breakpoint hit: "thread=main", HashTable.lookup(), line=228 bci=0
228         if (debug)

Keep entering next in the terminal until you get to call locate check and see whether it works as intended or not. Once you get to the locate call you can enter step which will allow you to enter locate and see the details of the method through your terminal. Make sure to check each index your program check and do hand calculation to see if the program is looking at the correct index given the probe sequence and size of the table or not. This way you could point out the issue. Also check whether your program is going beyond the elements that it should check and not returning the correct index. You could also use list command that will show you which line of code will be executing next.

233         Your code to call locate and find the index for the student
main[1] step
>
Step completed: "thread=main", HashTable.locate(), line=157 bci=0
157         if (debug)
Keep going next untill you initialize the HashValue of the student.
Once you are in locate you could enter locals at any point which will list the local variables and arguments of your method
main[1] locals
Method arguments:
element = instance of UCSDStudent(id=569)
Local variables:
hashValue = 630
This way you could keep track of the hash value or any other local variable you have. You could also use print or dump commands to check the values of instances or behavior of classes. Let's check...

main[1] print element
element = name: Sravya Studentnum: 0
Notice how the student number is 0 that's because you have created a new base instance when user asked the program to look up student Tiffany

main[1] dump element
element = {
name: Sravya
Studentnum: 0
}

Enter next and execute the program until you have assigned index as well, now check the locals again, are they correct, do you see any discrepancy from what you expected those values to be?

main[1] locals
Method arguments:
element = instance of UCSDStudent(id=569)
Local variables:
hashValue = 630
original = 0
increment = 3
now dump the table[index] to see what is the element in that position
main[1] dump table[index]
table[index] = {
name: Sravya
Studentnum: 125
}

Awesome the table contains the student and your program should correctly return the proper result. Keep executing until locate and lookup both return and check whether your program prints the correct output or not in your first terminal

Student found!!!
name: Sravya Studentnum: 125
Please enter a command:
(c)heck memory, (i)nsert, (l)ookup, (o)ccupancy, (w)rite:

Now test it with a student name that doesn't exist and see the behavior. You should check the table and each index that go through by printing them or dumping the table and checking locals. If you see the program is stuck and not asking for you prompt ensure to enter cont in the second terminal until you see the prompt in the first terminal.

Please enter a command: ((i)nsert, (l)ookup, (w)rite): l
Please enter UCSD Student name to lookup: Nick
Keep execuating until you are in your locate and all the local variables are initialized, you should see something similar to below

main[1] locals
Method arguments:
element = instance of UCSDStudent(id=581)
Local variables:
hashValue = 389
original = 4
increment = 2

After you initialized your index, main[1] print index
index = 4
main[1] print table[index]
table[index] = null
So you can see that table value at index is null which means the student doesn't exist and locate should return false and lookup should handle the returning result to tell the Driver that student doesn't exist

Student Nick not there!
Please enter a command:
(c)heck memory, (i)nsert, (l)ookup, (o)ccupancy, (w)rite:



10. Now, write your jettison method to get rid of all the memory leaks that you are seeing after terminate your program via control-D.
11. Now test a variety of functionality demonstrating the bully algorithm.

$ ./Driver -x
[Hash Table 1 - Allocated]

------------ TRACKED MEMORY ------------
80 bytes of heap memory, created in Driver calling HashTable Ctor for the HashTable object.

Initial Symbol Table:
Hash Table 1:
size is 5 elements, occupancy is 0 elements.

Please enter a command:
(c)heck memory, (i)nsert, (l)ookup, (o)ccupancy, (w)rite: i
Please enter UCSD Student name to insert: name
Please enter UCSD Student number: 123
[Hash Table 1 - Inserting name]
[Hash Table 1 - Locate]
[Processing name]
[Hash Value Is 417]
[Trying Index 2]
[Hash Table 1 - Found Empty Spot]
Please enter a command:
(c)heck memory, (i)nsert, (l)ookup, (o)ccupancy, (w)rite: o
The occupancy of the hash table is 1
Please enter a command:
(c)heck memory, (i)nsert, (l)ookup, (o)ccupancy, (w)rite: i
Please enter UCSD Student name to insert: amen
Please enter UCSD Student number: 234
[Hash Table 1 - Inserting amen]
[Hash Table 1 - Locate]
[Processing amen]
[Hash Value Is 417]
[Trying Index 2]
[Hash Table 1 - Comparing amen and name]
[Trying Index 4]
[Hash Table 1 - Found Empty Spot]
Please enter a command:
(c)heck memory, (i)nsert, (l)ookup, (o)ccupancy, (w)rite: i
Please enter UCSD Student name to insert: mean
Please enter UCSD Student number: 345
[Hash Table 1 - Inserting mean]
[Hash Table 1 - Locate]
[Processing mean]
[Hash Value Is 417]
[Trying Index 2]
[Hash Table 1 - Comparing mean and name]
[Trying Index 4]
[Hash Table 1 - Comparing mean and amen]
[Bumping To Next Location...]
[Hash Table 1 - Inserting amen]
[Hash Table 1 - Locate]
[Processing amen]
[Hash Value Is 417]
[Trying Index 1]
[Hash Table 1 - Found Empty Spot]
Please enter a command:
(c)heck memory, (i)nsert, (l)ookup, (o)ccupancy, (w)rite: o
The occupancy of the hash table is 3
Please enter a command:
(c)heck memory, (i)nsert, (l)ookup, (o)ccupancy, (w)rite: w

------------ TRACKED MEMORY ------------
80 bytes of heap memory, created in Driver calling HashTable Ctor for the HashTable object.
24 bytes of heap memory, created in Driver calling UCSDStudent Ctor for the UCSDStudent object.
24 bytes of heap memory, created in Driver calling UCSDStudent Ctor for the UCSDStudent object.
24 bytes of heap memory, created in Driver calling UCSDStudent Ctor for the UCSDStudent object.

The Symbol Table contains:
Hash Table 1:
size is 5 elements, occupancy is 3 elements.
at index 1: name: amen with studentNum: 234
at index 2: name: name with studentNum: 123
at index 4: name: mean with studentNum: 345

Please enter a command:
(c)heck memory, (i)nsert, (l)ookup, (o)ccupancy, (w)rite: l
Please enter UCSD Student name to lookup: Tracker
[Hash Table 1 - Lookup]
[Hash Table 1 - Locate]
[Processing Tracker]
[Hash Value Is 716]
[Trying Index 1]
[Hash Table 1 - Comparing Tracker and amen]
[Trying Index 2]
[Hash Table 1 - Comparing Tracker and name]
[Trying Index 3]
Student Tracker not there!
Please enter a command:
(c)heck memory, (i)nsert, (l)ookup, (o)ccupancy, (w)rite: i
Please enter UCSD Student name to insert: Tracker
Please enter UCSD Student number: 1
[Hash Table 1 - Inserting Tracker]
[Hash Table 1 - Locate]
[Processing Tracker]
[Hash Value Is 716]
[Trying Index 1]
[Hash Table 1 - Comparing Tracker and amen]
[Trying Index 2]
[Hash Table 1 - Comparing Tracker and name]
[Trying Index 3]
[Hash Table 1 - Found Empty Spot]
Please enter a command:
(c)heck memory, (i)nsert, (l)ookup, (o)ccupancy, (w)rite:
------------ TRACKED MEMORY ------------
80 bytes of heap memory, created in Driver calling HashTable Ctor for the HashTable object.
24 bytes of heap memory, created in Driver calling UCSDStudent Ctor for the UCSDStudent object.
24 bytes of heap memory, created in Driver calling UCSDStudent Ctor for the UCSDStudent object.
24 bytes of heap memory, created in Driver calling UCSDStudent Ctor for the UCSDStudent object.
24 bytes of heap memory, created in Driver calling UCSDStudent Ctor for the UCSDStudent object.
24 bytes of heap memory, created in Driver calling UCSDStudent Ctor for the UCSDStudent object.


Final Symbol Table:
Hash Table 1:
size is 5 elements, occupancy is 4 elements.
at index 1: name: amen with studentNum: 234
at index 2: name: name with studentNum: 123
at index 3: name: Tracker with studentNum: 1
at index 4: name: mean with studentNum: 345


No memory leaks! All memory has been correctly jettisoned.




12. At this point, you should test your assignment extensively by coming up with your own test cases. You can access the public executable via:
    

    % ~/../public/hw6/java/Driver [-x]

13. Also, make sure to test the both the Calculator as well. You should run make new before testing your Calculator.
You can access the public executable via:


% ~/../public/hw6/java/Calc [-x]

14. Make sure that you have fully commented your program and added method and file headers for any files and methods you edited. Make sure your style follows the Style Outline for CSE 12. Then turn in your program by following The Turnin Procedure.

    Note: In order for your homework to be collected correctly, you must name your files Driver.java and HashTable.java, and the files must be located in hw6/java in your home directory.

 

Assignment •  FAQ •  Development Guide •  Code •  Checklist