编程辅导 C C++ Java Python MIPS Processing 网络家教 在线辅导

编程家教 远程写代码 Debug 讲解答疑 课后答疑 不是中介,本人直接答疑

微信: ittutor QQ: 14061936 Email: ittutor@qq.com

导航

 

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.

相关推荐