8. Consider the following problem: Let A be an array of records where each record contains two members: . A student id number . A class section number; Array A represents all the students and the classes they are taking in a given semester at OSU (Oregon State University). Given array A and a positive integer I we wish to compute the total number of students in each class section and then report the NUMBER of classes with more than I students in the semester represented by A. (a) Write an algorithm (in pseudocode) which solves this problem USING A HASH TABLE. (Do NOT use sorting.) Your algorithm should use the hash table operations, Initialize, Insert, Retrieve, Member and Add. Input to your algorithm is array A, the size n of array A, and a positive integer I. The algorithm returns the NUMBER of classes with more than I students in the semester represented by A. (b) Assume your hash table has size at least 2n. Analyze the asymptotic EXPECTED running time of your algorithm on an array Justify your running time analysis. (You can assume either chained hashing or open address hashing.) (c) Assume your hash table has size at least 2n. Analyze the WORST CASE running time of your algorithm on an array Justify your running time analysis. (Note that the worst case time for insertion/find in a hash table is different than the expected case time. The difference between the worst case and expected times of insertion/find in the hash table will affect the worst case and expected times of your algorithm. You can assume either chained hashing or open address hashing.) 8. Consider the following problem: Let A be an array of records where each record contains two members: . A student id number . A class section number; Array A represents all the students and the classes they are taking in a given semester at OSU (Oregon State University). Given array A and a positive integer I we wish to compute the total number of students in each class section and then report the NUMBER of classes with more than I students in the semester represented by A. (a) Write an algorithm (in pseudocode) which solves this problem USING A HASH TABLE. (Do NOT use sorting.) Your algorithm should use the hash table operations, Initialize, Insert, Retrieve, Member and Add. Input to your algorithm is array A, the size n of array A, and a positive integer I. The algorithm returns the NUMBER of classes with more than I students in the semester represented by A. (b) Assume your hash table has size at least 2n. Analyze the asymptotic EXPECTED running time of your algorithm on an array Justify your running time analysis. (You can assume either chained hashing or open address hashing.) (c) Assume your hash table has size at least 2n. Analyze the WORST CASE running time of your algorithm on an array Justify your running time analysis. (Note that the worst case time for insertion/find in a hash table is different than the expected case time. The difference between the worst case and expected times of insertion/find in the hash table will affect the worst case and expected times of your algorithm. You can assume either chained hashing or open address hashing.)
