Consider the following problem: Let A be an array of records where each record contains three members A student id number; . A class section number The number of credit hours for the given class Array A represents all the students and the classes they are taking in a given semester at OSU (Oregon State University) The total number of credit hours taken by a student with id number X is the sum of the credit hours of the classes taken by student X Given array A and a positive integer h we wish to compute the tota number of credit hours taken by each student and then report the NUMBER of students who are taking a total of h or more credit hours 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 and Member Input to your algorithm is array A the size n of array A and a positive integer h. The algorithm returns the NUMBER of students who are taking h or more credit hours in the semester represented by A (b) Assume your hash table has size at least 2n. Analyze the EXPECTED asymptotic 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.) Consider the following problem: Let A be an array of records where each record contains three members A student id number; . A class section number The number of credit hours for the given class Array A represents all the students and the classes they are taking in a given semester at OSU (Oregon State University) The total number of credit hours taken by a student with id number X is the sum of the credit hours of the classes taken by student X Given array A and a positive integer h we wish to compute the tota number of credit hours taken by each student and then report the NUMBER of students who are taking a total of h or more credit hours 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 and Member Input to your algorithm is array A the size n of array A and a positive integer h. The algorithm returns the NUMBER of students who are taking h or more credit hours in the semester represented by A (b) Assume your hash table has size at least 2n. Analyze the EXPECTED asymptotic 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.)
