CSCE221- Assignment 5: Regex and csv files Solved

In this assignment we create a HashTable to store the entry UINS from students taken from a excel .csv file. Then we use the HashTable to search for specific UINs and enter their corresponding grade values

Problem 1

Describe the Data Stucture and algorithms used by your program?
In this program we use the HashTable data structure which relied on a hash function that is:

                                                                                        h(x) = k∗mod(m)                                                                                  (1)

Where k is the UIN value entered and m is the hash table size which in our case is m = 100. The HashTable is stored in a vector of Doubly Liked Lists which then will store the key values and quiz grades for the students. In our case, our vector is of size 100 and contains between 0 and 1 linked lists with nodes. Each node contains a key and a quiz value variable.

We also implement the Doubly Linked List Abstract Data Structure and a HashNode Data Structure.

These two data structures were modified for this assignment from the templated version that was used in Programming Assignment 3.

Describe the input and output data and any restrictions
A very important restriction on the input data is that the third column and fourth of the spreadsheet only contains digits because the regex code is respectively. Here we are assuming that the UIN is a 9 digit number and the quiz grade is a number that is smaller than 100. Another restriction we have imposed is that the size of the HashTable must be 100 entries. I have tested my program for correctness by creating a new input csv which contains repetitions of UINS and quiz grades. This was to test the functionality and the correct values for the maximum numbers of nodes in the link list. Both were a success and I have included the input2.csv file in the .tar to prove it.

Have you tested your program for corrections?
Figure 1: Testing the code for correctness

Yes, to test for correctness I created another input file which contained the same UIN for two quiz grades. Theoretically this should not be allowed, but I was curious as to see how the Linked List would compute.

Problem 1 continued on next page...             Page 2 of 3 Robert Quan CSCE 221 (Dr. Leyk 4:20pm): Programming Assignment 5 Regex andPcrsovbfilelmes 1 (continued)

As a result, the list computed correctly and the maximum number of nodes was updated accordingly. The figure 1 demonstrated the statistics when I use input2.csv

Which C++ fueatures or STL classes did you implement
I used the class cstdlib, iostream, stdexcept, vector, string, fstream and regex. All of these classes aid in the implementation and the output of the csv files. As for the c++ features, I implemented the string to integer function stoid on the matches from my regex pattern.

e) Provide statistics about the hast table
Figure 2: HashTable statistics

When using the original input given to us, I obtain the statistics displayed in figure 2. This is correct because the maximum number of nodes that contain a quiz grade will be 1 for every individual UIN that has a corresponding grade. The minimum is 0 for those lists that do not contain values for quizes. The average was the total number of quiz UIN grades per Total UINS. This gave me an average of 0.17 quizes per UIN. f) Conclusion

It is nice to see that the code for HashTables works, but the I do not see the benefit from indexing a vector. From my understanding, If we do include extra nodes then those nodes would theoretically aid in the run time for searching a HashTable. As the code stands, I do not see how indexing a 100 entry vector with link lists and then using only one node per link list to store values aids us in searching or minimizes space.