Hi all,
My question is as follows:
Implement a database to maintain the total of all continual assessment marks awarded to students for the next semester. Students start with 0 marks at the beginning of the semester. Ass students complete assignments, the marks they get are added to this total. Let n be the number of students currently enrolled. You should develop a data structure that supports the following 2 operations.
add(s,m) where 0 <= s < n, m is a Natural number, adds m marks to the total for student s and returns the total.
query(s), where 0 <= s < n, returns the marks for student s.
In addition, before the transactions start, the procedure init will be called to perform any initializations that you may require.
Show how you would implement this database so that add, query, and init all take time O(1) through the use if 3 arrays of size n and a counter. The initial contents of all three arrays are undefined and you may not assume that they have been initialized to any particular value.
I was thinking the procedure init just initializes the starting marks of the students to be 0. One array, student[n], would be used to store the marks of the n number of students. Another array, flag[n], could be used to reflect the status of each corresponding student[n] cell in the procedure init, i.e. since all arrays are uninitialized, they would contain garbage values. So, say we're dealing with student a, then if flag[a] != 0, set student[a] = flag[a] = 0, before executing the procedures add or query. One problem is that there is still the very slim chance that the garbage value turns out to be 0. Is this possible?
I think in this way, add, query and init should use only O(1) time, since each time the procedure is called, it only deals with one array element directly. I guess I could use the counter to see if all n number of students have been initialized, and if so, then init need not be executed. However, if I do it this way, what is the extra array for?
What is a more efficient way to implement the database?
Thank you.
Regards,
Rayne
