Running time

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. As 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

A very detailed question ... maybe to detailed since nobody replied.
What does the O(1) mean?
Also, query(s); should this return the seperate marks of a student or just the total?

Well, in my opinion it would never be good to leave an Array uninitialized. So, I would start with figuring out what the max students for student[n] and then make 'int n' equal it as a 'const int'. Then for flags do the same, I don't really think its possible to come up with a zero, well at least it will be almost impossible especially if that's the number you wanted.
But anyways just my two cents worth because I don't work with databases or queries, So sorry I couldn't of more assistance.