KXT201 Algorithms
First (Individual) Assignment 2009
Standard Level
Due: 3pm 30th
April
A Student Enrolment Database
Introduction
For this assignment you will need to create and modify a collection of data from input and
produce appropriate output based on information obtained from the collection. This
collection will be referred to as the "database". The assignment, which is worth 12% of the
unit mark, and marked out of 24, can be attempted at two different levels – "standard" level,
worth up to 21 marks, and "challenge" level, which includes the standard level and is worth
up to 3 more marks. The standard level assignment is described here and the additional
work for the challenge level is described in a supplement.
The challenge level assignment is aimed at providing some challenge for students for
whom a final unit mark of HD 80 would be a disappointment, and who find the weekly
work, tutorial exercises and standard level assignment quite straightforward. Students who
are not in that category are strongly advised not to attempt the challenge level assignment,
as it is likely that their final unit marks would benefit more from other activities such as
thorough testing of their standard level assignments to ensure that they work, and putting
more time into the weekly work. The extra marks in the challenge level assignment are
worth much less than the 6% associated with the weekly work (and tutorial participation),
and understanding the weekly work will be more relevant to the exam, which is worth
70%.
The Database
The database will contain information about students and units. Each student will have a
unique positive int ID number and a unique one "word" name, and each unit will have a
unique one "word" name. The information about the students and units must be stored in
the data structure specified later. The input must be read in a format specified later, and the
output must comply with the format requirements given later.
Testing
Programs will be tested automatically on alacritas / lawson, and marks for each test will
be awarded on a pass/fail basis. A test is passed only if your program completes without
crashing within the time allowed for the test and the output from your program is exactly
the same as the correct output, character for character — any failure to adhere to the format
requirements may lose many marks. After you have read this specification, you should
read the file /units/kxt201/assignment1/README to understand the testing procedure, and
look at the sample test data in the assignment1 directory.
System Availability
Experience shows that, unfortunately, the computer systems are often unavailable (e.g. due
to a power cut), or practically unusable, for much of the 72 hours before the deadline. This
is not an unforeseeable misfortune of the type that might justify a request for an
assignment extension.Data Structure Requirements
In this assignment all enrolment information must be stored (only) from the perspective of
the students.
The students must be stored, in ascending numerical order of ID number, in an array of
1000 structs of the following type:
struct student
{
int ID;
char *name;
node_ptr units;
};
where:
ID is the student's ID number;
name is the student's name, being a character pointer to dynamically allocated memory of
the appropriate size for the number of characters in that particular student's name (plus the
terminating '\0');
units is a binary search tree (BST) containing the units in which the student is currently
enrolled.
In addition to the array:
struct student students[1000];
there must be an int variable storing the number of students currently in the database,
(which will be at most 1000):
int n_students;
such that the array stores the data about the students in students[0] to
students[n_students – 1], with the students stored in ascending numerical order
of ID number. (You may define n_students and students to be static variables if
you wish.)
Each student's units must be stored in a (strcmp ordered) BST, for which the
implementation must be based upon that of the weekly work, modified as little as required.
The BST is to have a node type (and associated pointer type) defined as follows:
typedef struct node *node_ptr;
struct node
{
char *data_item;
node_ptr left;
node_ptr right;
};
where:
data_item is a unit's name, being a character pointer to dynamically allocated memory
of the appropriate size for the number of characters in that particular unit's name (plus the
terminating '\0');
left and right are the pointers to the left and right subtrees (respectively).
(In your code the node pointer definition will have to precede the definition of the student
struct type, as the definition of the student struct type uses the node pointer type.)
Note that you must store the information as required and may not store the information in
other ways, e.g. you may not store it by unit to make operation 6 (defined later) easier.
Also note that the requirement regarding the size of dynamically allocated memory needed
for a name (of either type, student or unit,) relates to the actual number of characters in the
individual name concerned, not to the maximum number of characters that might be in a
name.Database Operations
There are seven operations to be performed in the standard level assignment. The
operations are numbered so that the input can specify which operation is to be performed
by using that number. Each operation must meet a O() running time requirement. These
are specified for each operation, in terms of:
H, the maximum of the current BSTs' heights if correctly implemented;
S, the number of students currently in the database;
U, the maximum number of units that any individual student is currently enrolled in.
The first operation is the simplest
0 Finish execution, returning 0, O(SU).
The next two operations involve updating the database:
1 Add a specified student, (enrolled in no units), O(S).
2 Remove a specified student, (implicitly unenrolling them from all their units, if any),
O(S + U).
The next operation requires the obtaining and printing of information from the database:
3 Print, in ascending numerical order of ID number, the ID numbers and names of the
students in the database, O(S).
The next operations involve updating the database:
4 Enrol a specified student in a specified unit, O(H + log S).
5 Unenrol a specified student from a specified unit, O(H + log S).
The final operation requires the obtaining and printing of information from the database:
6 Print, in ascending numerical order of ID number, the ID numbers and names of the
students enrolled in a specified unit, O(SH).
Notes on the O() running time requirements:
a) You can assume that each call to any of scanf, printf, malloc, free, strlen, strcpy and
strcmp, takes time that is O(1).
b) Although S is actually limited to 1000, by the size of the array of students, the existence
of this limit must be ignored for the purposes of the O() running time requirements. (Code
must be based around n_students, not the size of the array. Any use of the limit of
1000 in the code will be regarded as breaking the O() requirements. For example,
initialising each student ID number or name to 0 or NULL will be regarded as breaking
the O() requirements, as doing so depends on the limit of 1000, however it is done.)
c) You do not need to make any special effort to have good constants in the running time
of your code, but equally, you must not make any effort to make it excessively inefficient
in constant terms – the marker will limit the length of time for which they wait for a test to
complete.Input and Output
Input must be read with scanf and output written with printf. The input and output format
requirements are given here, and you should look at the sample test data provided on
alacritas / lawson. You may make the following assumptions about the input:
a) The input will comply with the format requirements. (There will not be any extra marks
for handling incorrect input.)
b) The input will not request an illegitimate operation, e.g. there will not be a request to add
a student currently in the database or remove a student not currently in the database.
However, it is possible for a student that has been removed from the database to be added
again after their removal, and it is possible for a student to be re-enrolled in a unit from
which they have previously been unenrolled. It is also possible for there to be such
requests as one to print the students in the database when there are no students in the
database (in which case, as defined below, the output for the operation will consist of a
single blank line).
The format rules include the following general ones:
a) A blank line will be completely empty, no spaces, tabs etc.
b) The first item on a non-blank line will not be preceded by anything, e.g. spaces.
c) The last item on a non-blank line will be immediately succeeded by the end of line.
d) Successive items on a non-blank line will be separated by a single space.
e) Student and unit names will consist only of lower case letters and '_' characters, and
will each contain no more than 100 characters. (The 100 does not include a terminating
'\0'.)
f) Student ID numbers will be positive ints (and are never used with leading zeroes).
g) Where a student ID number and name are both given on a line, the number will be
before the name.
h) Where student and unit information are both given on a line, the student information
will be before the unit information.
Further rules relating to the input are:
a) An operation number will be the only item on its line.
b) For operation 0, the line with the operation number will be the last line in the input.
c) Apart from operation 0, the input associated with one operation will be followed
immediately by a line containing the operation number for the next operation.
d) For operation number 1, the line with the operation number will be followed by a line
containing the ID number and name of the student to be added.
e) For operation number 2, the line with the operation number will be followed by a line
containing the ID number of the student to be removed.
f) For operation number 4, the line with the operation number will be followed by a line
containing the student ID number and unit name to enrol.
g) For operation number 5, the line with the operation number will be followed by a line
containing the student ID number and unit name to unenrol.
h) For operation number 6, the line with the operation number will be followed by a line
containing the name of the unit for which the enrolments are to be printed.
Further rules relating to the output are:
a) No output will be produced except that for operations 3 and 6.
b) For operation 3 and operation 6, the output will consist (only) of a single blank line
followed by the relevant student ID numbers and names (if any), in ascending numerical
order of ID number, with one student's ID number and name per line.Submission of the Assignment
Your assignment, including the cover sheet, must be submitted electronically as below. You
must submit the source (.c and, if applicable, corresponding .h) files for your assignment,
a file named README, (not e.g. readme, or README.txt), described below, and a
completed electronic individual assignment cover sheet. (The cover sheet is available via
http://www.cis.utas.edu.au/cisview/assign_cover.jsp). You should not submit any other
files, (e.g. a.out). All source files must be able to be easily read and understood by the
marker. You should assume that the readability is judged in terms of what the code looks
like, when read with the "more" command, with standard tab settings of width 8.
The README must be plain text (not e.g. Word or PDF or rich text format), be easily
readable (with the "more" command) and start with your name and your student ID
number. The file must briefly describe the structure of the program and location of
functions in files, and be explicit about the origin of any code that you have taken (with or
without adaptation) from elsewhere. For example, the following description would suffice
for my own solution to the standard version of the assignment:
"The main(), in main.c reads the operation number and calls the relevant function, e.g.
op1(), for operation 1. The operations are implemented in students.c, and make use of the
BST code in bst.c. The BST code in bst.c is based on that of the weekly work and the
binary search in students.c is based on Weiss's code."
Note that your documentation here, and in the form of comments in code, should assume
that the marker knows the assignment specification, and is familiar with the weekly work,
tutorial exercises and the prescribed text, as well as knowing C in general.
You must submit from your own account, and you must not let others submit from your
account. (The submission program stores the submission under the name of the account
from which the submission occurred.)
To submit, create a directory called Standard1 in your home directory on
alacritas/lawson. Copy the files to be submitted (not e.g. a tar file containing them) into
that directory (not e.g. into a sub-directory of it). Then execute the following command at
the prompt, and act appropriately when requested, until you get the message that the
submission is complete:
kxt201-submit1
The message that submission is complete will be:
Submission complete.
If you re-submit, just use the same procedure and the system will keep track of the latest
version. Note that the system records the time of submission so that late submissions can
be penalised according to the School of Computing and Information Systems policy. If
you are considering resubmitting after the deadline, remember that this will attract a late
penalty. (You may find that the submission system leaves a copy of each of your
submissions in your alacritas/lawson home directory. There is no need to keep these
copies.)Assessment
The marker will assess your assignment as follows:
1. The marker will extract the files from your submission. If the files are present where
required, including a correctly named README file of the right form, with the right
information, this will be worth 2 marks.
2. The marker will attempt to compile (and link) your submission (unaltered) using
(exactly) the following command:
gcc –Wall –ansi –pedantic –O *.c
If this produces the assignment executable, a.out, without any warnings (or errors), this
will be worth 4 marks. If you do not get the 4 marks, but the marker is able to compile
(and link) your submission (unaltered), as C, using gcc, to produce an a.out, this will be
worth 1 mark.
3. The marker will read your code. If it is easily readable and understandable, as is
required, and your code appears to make a serious attempt to implement at least operations
0 to 3 using the required data structures, they will assess the code style in general, such as
readability or comprehensibility beyond minimum, out of 4 marks. For example, your use
of indentation and blank lines will affect readability. (As mentioned earlier, you should
assume that the readability is judged in terms of what the code looks like, when read with
the "more" command, with standard tab settings of width 8.) Similarly your use of
comments, choice of variable and function names, division of code into functions, and
division of functions between files will affect comprehensibility.
4. If you have used the required data structures, and the marker has been able to compile
(and link) your code (unaltered) as C, using gcc, they will then assess code functionality
by running your code on those tests for which you appear to have made a serious attempt
to implement the operations. As shown in the table below, the marks obtained for passing
a test depend upon whether you have met the O() running time requirements. (As tests are
time limited, failing to meet running time requirements could cause a test to be failed.)
Test 1 (uses only
operations 0 to 3)
Test 2 (uses only
operations 0 to 3)
Test 3 Test 4
Passing with
both required
Data Structures
and O()
4 marks 2 marks 2 marks 2 marks
Passing with
required Data
Structures, but
not O()
2 marks 1 mark 1 mark 1 mark
5. If it appears to the marker that your code might obtain more marks for functionality if a
trivial mistake were corrected (e.g. the code fails all tests because there is an additional
space being printed in one of your printfs), then they will correct the mistake and retest,
awarding you half of any additional marks obtained as a result of their work. (You should
not count on the marker getting right in a couple of minutes something that you have got
wrong over a much longer period of time!)
6. If your code as submitted uses the required data structures, meets all the O()
requirements, and passes all tests, the marker will check whether all dynamically allocated
memory is being correctly explicitly freed as soon as no longer required and all
dynamically allocated memory is correctly explicitly freed before the program terminates,
if so, this will be worth 1 mark.Assignment Individuality
You are encouraged to use relevant code from the weekly work, tutorials, or the prescribed
text, but must clearly acknowledge the origin of such code. However, this is an individual
assignment, which should otherwise be your own individual work. You are not permitted
to use code from elsewhere, especially code from other students, friends, relatives, etc, and
you must ensure that others do not have access to your code, or any description of it, in
any form, in whole or in part. In this unit, any undue similarity of your assignment to
others may be detected automatically and / or manually.
Assignment Specification Clarifications
It is intended that the assignment specification is complete and correct as first issued.
However, unlike programs meeting the assignment specification, the specification itself
is written without the possibility of compiling and executing to find mistakes. If you had
to submit assignment programs without having been able to compile and execute them, we
would expect there to be many mistakes in them that compiling and executing could have
helped find.
In the event that there is in the assignment specification a mistake that needs correcting, I
(Mike Cameron-Jones) would like to know about it, and will issue a clarification on the
unit web site, which you should repeatedly check in case such a clarification appears.
However, I do not want an e-mail deluge of false claims of mistakes to cause me to
overlook a notification of a genuine mistake. Thus, if you believe that you have found such
a mistake, please do the following:
1. Check that it is a mistake, and has not yet been corrected, by rereading the assignment
specification and the information on alacritas / lawson looking for things relating to the
apparent mistake, and looking at the unit web site to see if it has already been addressed.
2. Leave the matter overnight and then redo the full check.
3. Find another student in the unit who is unlikely to get such a matter wrong, and redo the
full check with them.
4. If, after all this checking, you're still sure that there is a mistake that needs correcting, e-
mail me a precise statement of what you believe the mistake to be and I will look at it, and
if necessary post a clarification.
Advice On Doing A Programming Assignment
It is up to you to do the assignment for yourself in the manner that works best for you, but
there will be some advice in a lecture near to the point at which the assignment is available.
The main general point to remember is to be realistic about what you personally can
achieve, and work within that, breaking the task down into pieces of a size that you can
handle. It is much easier to find a mistake in a small piece of code than in a large piece, so
you should work incrementally, testing as you go, so that you only have to look for
mistakes in the small part that you have just added / changed, not in your whole program.
(There is a debugger, ddd, on alacritas / lawson, but although I might use a debugger on
others' code, I recommend using extra printfs and thinking more, when debugging your
own code.) If you get stuck when looking for a mistake, it is often more productive to
leave it aside overnight and then look at it again the next day, than just keep going –
obviously this requires that you start early enough to do this, another point worth
considering. Starting early also gives the possibility of consulting when stuck. If you think
about the order in which you develop incrementally, you should be in a position to pass
the tests that only use operations 0 to 3 before you've even started work on the other
operations. Remember early to test your code, as it will be tested, where it will be tested –
having code working at home is worth nothing and systems are different. Check your final
submission carefully – compile and test it before copying the files into the Standard1
directory, and compile and test again in that directory after submission, as a final check.