Complete the following assignments from the textbook. You may use any method/notation you like to show trees as long as you explain it and it's clear for grading purposes.
Page 535-536 Questions 8, 9, and 10
Page 598 Question 4
[To be clear each operation in part a) occurs one after another on the original heap shown]
Part 2 - iLab (35 points)
The purpose of this week's iLab is to implement and test a simple Hash table. You need to implement a hash table based on 13 elements. The table inserts a string and then test to see if the sting is in the table.
Use the following hash function code...
const int hashSize = 127 ;
int hashValue = 0 ;
for (int index = 0; index < teststring.length(); index++)
{
hashValue = (hashValue x 31) + teststring[index];
}
hashValue %= hashSize ;
For the purposes of this assignment only (don't do this in the real world!) you may simply overwrite the value already in the hash table if a collision occurs as long as you report this to the user. However, if you feel energetic, implement a link list or use linear probing to store the collisions instead.
You will need to create a driver routine to test the implementation. Commands to test the routine should include...
Insert (reports collision if it occurs)
Delete (returns success or failure)
Find (sees if string is in table, but does not delete it)
Remember to watch the border cases - removing items that do not exist for example. You do not need to worry about a full hash table.
General iLab Comments
All coding assignments for this class will be using Microsoft Visual Studio 2010. If you do not have 2010, you should be able to use it through iLab Citrix. Let me know if there are any problems.
[You may submit source files create in other IDEs, such as eclipse, with the provision that they are in a format that is easy to import into Visual Studio. Projects will be graded in visual studio so make sure they compile and execute correctly in Visual Studio.]
Please review the announcement Programming Assignment Standards and Guidelines for basic information on what is required for programming assignments.