Late last night, I was working feverishly to complete my computer science assignment (due today). Today I woke up with only a very fuzzy recollection of what I had done on the assignment. But it was sitting there on my desk in a brown paper envelope, ready to be handed in. After handing it in, I began to remember what I wrote. And these memories scared me. Apparently I had gotten so sick of working on it that I just started writing down whatever came to mind.
Later on, I found on my computer the "overview document" which I wrote to explain certain aspects of the program I wrote. Just to illustrate some of the stuff that your brain produces at 3:00 in the morning, here it is in its entirety:
Part 3: Overview Document
Class Design – Part 1:
In part 1, Three classes were used: Student, Graduate, and Undergraduate. Student was the parent class for Graduate and Undergraduate. Inheritance was used because both Undergraduate and Graduate students share characteristics like student number, first name, and last name, and also because the assignment said we were “encouraged to use inheritance”. In each class, all member variables are kept private, and Get() and Set() functions are used to read and write to these variables. The Student class runs no constructors or destructors, because it should never be called except by Graduate or Undergraduate, which have their own. Destructors are in fact never used, because the “new” command was not used, and as such the memory does not need to be freed. Which is a good thing, because I am pretty sketchy on how memory works. But that doesn’t matter, right? As long as I can comment my code properly, and separate function definitions and implementations, it’s all good. Heck, on assignment 2 I got 30/50 and my program didn’t even work.
The class Graduate has three constructors: one for no initial parameters (which sets the student number to -1), one for only one parameter, and one that sets all the variables according to the passed parameters. The constructors have a simple tester to make sure the student number is 8 digits long. Similarly, the Undergraduate class also has three constructors; the only difference being the set variables and the tester checking for a 9-digit student number.
Each class, per the assignment requirements, is contained within its own .cpp file, and has its own .h file. This makes for lots of “#include” statements, but I suppose it makes things somewhat neater.
Class Design – Part 2:
For part 2, a new class called StudentRecords was created. It uses no constructors or destructors. Again, all the member variables are kept private, because there are some variables (such as arraylength) that could cause serious problems if modified from outside. Get(), Insert(), and Delete() functions handle everything that is allowed to be modified externally.
For a data structure, an array was used. This seemed at the time (sometime late Tuesday night) to be the best choice, because I was sick of linked lists. In retrospect, a linked list is probably a much better choice, but as it is now Wednesday morning, there isn’t much time to entirely rewrite the code. However, there are some advantages to using arrays:
1. Eliminates pointers! (I hate pointers)
2. They take up less space in computer memory (kind of; this will be addressed later).
3. They are phenomenally easy to write algorithms for (being able to address an array member with a variable comes in handy sometimes).
The only problem with using an array is that you can’t dynamically change their size. To get around this problem, I wrote the code blindly assuming that you could. After all, if you can do it in Java, it should be fair game for a C++ assignment that isn’t even being marked electronically. Writing the code with this assumption is actually pretty neat, because it allows you to write algorithms for deleting and inserting without having to call functions that create new arrays and passing around pointers and all that garbage. I figure that it’s the concept that’s important, not the implementation. Perhaps this should wait until next semester’s course though (Algorithms and Data Structures). Anyways, since the students are stored as an array of pointers, it made the GetAsArray() function (which is supposed to return an array of pointers) quite easy to write too.
Space/Time Complexity Analysis:
Wow, when you say “space/time” it sounds like you are talking about relativity or string theory or something. But I digress. I don’t even know why a space complexity is needed; my computer has 1.5 gigs of RAM, and I know some people that have even more, so I’m not entirely sure why space is so critical. After all, even in the worst case there are still the page and swap files (which one is it that acts as extra RAM? I can never remember. It’s like the difference between the stack and the heap.). Although I must admit that when I tried to declare an array that would be big enough to store all possible student numbers (all 900,000,000 of them), it gave me an error. I guess Windows XP doesn’t like competition for taking up the most system memory. Granted, nine hundred million student numbers would never be used, but until you get up to that number you can never really be sure that the array is big enough. “Segmentation fault”, here I come! So. Time complexity. For the Insert() function, the complexity is O(n) for a list of length n, because it runs through the loop once to move all the items, then adds the new item. Get() is O(1), because it just goes right to whichever entry is i+1th. GetStudentNumber() is again O(n) because it has to go through each item in the list and check for the correct student number. Delete is O(n), and so is DeleteStudentNumber(). GetAsArray is O(1) because the array already exists and it just gets passed back.