Project#2

Frequently Asked Questions

1. Important: Are reports necessary?
   You dont't have to prepare a Report on the performance of hashing functions and collision resolution techniques. But if you do, you will get bonus points depending on how good you prepare the report. However you should submit a report of your program (class, method, function definitions). You will not submit the printed source code (just on diskette with executable). But submit your report printed.
2. How can I easily prepare my Report for the runs?
   I have asked to drop the reposrt part of the Project#2 by most students. I want you to see that the report part is even more simple than the project part. Now assume that you have written the project part, you are sure that your class (or eq equivalently functions in C) is perfctly running, and you meet the requirements. Then analyse that the report part consists of two runs: one is with given datasets, the other is with the datasets randomly generated by your program. Than all you need to do is to perform the following steps (just for second part of your report, the other part is very similar):
   • Put your class code in a library file and include it in your report generator file. (or equivalently you can copy and paste your class or functions into that file)
   • Your main body should look like the following code (pseudo code included)

   for (hashingfunction=1;hashingfunction<=4;hashingfunction++) {
     for (openaddresing=1;openaddresing<=3;openaddresing++) {
       for (loadfactor=0.1;loadfactor<=0.7;loadfactor+=0.05) {
         for (I=1;I<=10;I++) {
           hash.create(181,hashingfunction,openaddresing);
           hash.rand(loadfactor);
           probes[hashingfunction][openaddresing][loadfactor] += hash.printstat();
         }
         probes[hashingfunction][openaddresing][loadfactor] /= (10*round(181*loadfactor));
       }
     }
   }
   

   Here probes array (three dimensional) gives you the data needed to plot loading factor vs average probes (by average robes I mean the total probes divided by the number of data in the hash table, thus average probes for a data).
   You can easily save the values in probes in a text file (format is up to you), and easily import the data in that text file into a ploting program (Excel for example). It is not a hard job if you know how to do, trust me!
3. What create 187 3 2 means?
   This command creates a new hash table (by deleting the existing one if previously created) with a table size 187. This hashing table uses third hashing function defined in project description, and quadratic probing as collision resoluiton technique.
4. Should I test user errors such as unknown commands, performing an operation before the hash table is created?
   No! But you must do promt some obvious messages like "The string you are searching for can not be found in hash table.". The messages that will be written by your program is up to you, but you must satisfy the design criteria in the project description first.
5. What should program do when inserting a string that is already in hash table?
   Actually do not insert the string again but give a warning message.
6. What should I do if rand generates same string that it previously generated or already in hash table?
   First generate the string, than test if that string already in hash table. If the string is not in the hash table insert it otherwise generate a new string and test again. So if your table size is 851 and command is rand 0.3 generate 851*0.3=255 random strings that are not in hash table and insert them. Do not create all random strings and insert them at once, but rather create one string and insert it into hashing table.
7. What must be the format of the file created by savedump command?
   The first three line of the file must contain table size, hashing function used, and collision resolution method. The actual table must start after 4th line. There should be a line for each string in the table even if that slot is empty. If the slot is empty insert a new line character.
8. Suppose I have insert 'cati' and 'arap' strings into hashing table and they are collide. I put 'arap' just after 'cati'. What should I do in searching 'arap' after 'cati' is deleted?
   Do not test such situations, just assume that the strings that do not cause collisions will be deleted.
9. Does ord('a') means ASCII value of character 'a' or 0?
   Value of ord('a') used in project description is taken as 0. So it is different than the actual ord defined in C++. To convert it just code ord(c)-ord('a')
10. Can I write my program in C?
    Projects written in C or C++ will be accepted but other languages are not. Be sure to test your program on computers in PC Lab in our department. If some other installations (like dll's if you are working on windows environment) is needed to run your program bring the installation CDs or diskettes with you to demo. It is your responsibility to run your programs on PCs in our department not ours.
11. How can I read or write to or from a file?
    You can use fopen to open a file for reading or writing. The syntax is

    FILE *f;
    f = fopen("test.txt","r"); // to open a file for reading
    f = fopen("test.txt","w"); // to open a file for writing, 
    

    You can use fscanf, fgets, fgetc to read from file. But I suggest you to use fgets.

    char msg[10];
    fgets(msg, 9, f);
    // reads 9 char or up to end of line
    // (which comes first) from file pointed
    // by f and assigns msg
    char msg2[] = "Output";
    fputs(msg2, f);
    // writes the content of msg2
    // to the file pointed by f
    

12. When we construct hash table, which structure we use, i mean do we use link list structure? or array structure?
    The data structure to store hash table is up to you. But obviously you cannot use a static array because you can not change its size on runtime. Do not assume that table size can not be greater than a specific value. Be more generic and alloca space for hash table in run time. Suppose that you create an hash table class (so create will be a method in that class). You can use the class vairable string4 *table where string4 is also a pointer to characters. Then you can use new function to allocate space for hash table: table = new string4[tablesize].
13. What will be the second hashing function in double hashing?
    The second hashing function in double hashing will be h(c1 c2 c3 c4) = R - ((26^3 ord(c1)+26^2 ord(c2)+26 ord(c3)+ ord(c4)) mod R) where R is the closest prime number to table size and smaller than it. (R<tablesize, R is prime).