Description
Introduction
You work for an education company that develops and runs Massive Open Online Courses
(MOOCs). You have been asked to develop some software to manage student enrolments.
You decide to develop a prototype solution to test the performance of different data
structures and algorithms.
The company will initially only offer a few courses, but that may expand significantly in the
future. More importantly, each course may have many thousands of students – perhaps even
hundreds of thousands. Your software needs to provide the following functions:
1. Add a student
2. Remove a student
3. Enrol student in a course
4. Un-enrol student from a course
5. Print a summary of courses and the number of students enrolled in each course
6. Print an ordered list of students enrolled in a course
7. Print a list of courses that a given student is enrolled in
The number of courses that any student will enrol in is small. Furthermore, there is no
inherent order to the courses, so an ordered data structure is not required. Therefore you
decide to use a simple linked list to store the courses for each student.
The number of students will potentially be very large and, for quick access, sorted data is
required. Initially, you decide to test performance of a binary search tree to store the
students, but you would like to test an AVL tree as well. Note that, for this preliminary testing,
only the student ids will be stored (as long ints).
Assignment Specification – Part A (80%)
For this part of the assignment you will implement a prototype that uses BST to store
students, with each student record containing a list of courses the student is enrolled in. You
must use the BST and linked list code developed in the tutorials, however the data structures
will be modified for the new data (and functions will also require minor modifications to
accommodate these changes). The following definitions MUST be used:
typedef struct listNode{
char *data;
struct listNode *next;
} *ListNodePtr;
typedef struct list {
ListNodePtr head;
} List;
typedef struct bstNode {
long data;
List courses;
struct bstNode *left;
struct bstNode *right;
} *BSTNodePtr;
typedef struct bst {
BSTNodePtr root;
} BST;
The ListNodePtr and List definitions and (modified) linked list functions must be placed in
files stringlist.h and stringlist.c. The BSTNodePtr and BST definitions and
(modified) BST functions must be placed in files bst.h and bst.c.
All remaining code should be placed in a file called main.c that contains the main function
and program logic. This file will contain separate functions for each of the seven operations
listed in the introduction, as well as an eighth function to handle termination. Other functions
may be added if required.
Program I/O
All interactions with the program will be via the console. Operations 1-7 will be selected by
typing 1-7 at the command prompt. Quitting the application will be selected by typing 0. For
example, the following input sequence would add a student with id 123456, enrol that student
in course “abc123”, and then quit the application:
1
123456
3
123456
abc123
0
Note that this sequence shows the input only, not the program response (if any). You are free
to add prompts to make the application more user friendly, but this will not be assessed
(although it may be useful).
Program output in response to operations 5-7, should be as minimal as possible. You may
print a header if you wish, but this should be followed by one record per line with spaces
separating data. For example, in response to operation 5, the output might be:
Current enrolments:
abc123 32
def456 0
123def 10236
I/O Restrictions
You may assume that all input will always be in the correct format and contain no logical
errors.
Commands will always be in the range 0-7
Course names will always be strings less than 100 characters long and may contain any
alpha-numeric characters excluding spaces
Student ids will always be positive integers in the range 0-999999
The user will never attempt to add a student to a non-existent course
The user will never attempt to print data for a non-existent course
The user will never attempt to print data for a non-existent student
Note: Students that are enrolled in courses may be removed, in which case the course data for
that student should also be removed
Memory Management
Course names should be stored in appropriately size dynamically allocated memory. Names
will always be less than 100 characters long. For example, the course name “abc123” would
be stored in a char string of length 7.
Removing (un-enrolling) a student or removing a course should free all associated dynamically
allocated memory. Removing a course should free all memory for the enrolled students as
well as the course. The quit function should also free all dynamically allocated memory.
Assignment Specification – Part B (20%)
This part of the assignment should only be attempted once you have a fully implemented and
thoroughly tested solution to part A. It would be better to submit a complete part A and no
part B than to submit a partially complete part A and part B.
The requirements for this part of the assignment are exactly the same as for part A except that
an AVL tree must be used to store students, rather than storing them in a BST. The AVL files
should be named avl.h and avl.c. The AVL node definition should be a modified version of
the BST node.
Minimal assistance will be provided for this part of the assignment, especially if you cannot
demonstrate a fully implemented and thoroughly tested solution to part A.
Testing
It can be very time consuming to thoroughly test a program like this when all input is done
manually (imagine testing that your solution can manage 10000 students). A common method
of testing code like this is to use input redirection (and possibly output redirection). When
using input redirection your code runs without modification, but all input comes from a file
instead of from the keyboard.
This facility is provided in Visual Studio through the project properties dialog. For example, to
redirect input from a file called “test.txt”, you would add:
<“$(ProjectDir)test.txt”
to Configuration Properties|Debugging|Command Arguments. This will be demonstrated in
tutorials.
At least one small input test file with sample output will be provided. It is recommended that
you construct larger files to fully test your program.
Assignment Submission
Assignments will be submitted via MyLO (an Assignment 1 dropbox will be created). You
should use the following procedure to prepare your submission:
Make sure that your project has been thoroughly tested using the School’s lab
computers
Choose “Clean Solution” from the “Build” menu in Visual Studio. This step is very
important as it ensures that the version that the marker runs will be the same as the
version that you believe the marker is running.
Quit Visual Studio and zip your entire project folder along with a completed
assignment cover sheet
Upload a copy of the zip file to the MyLO dropbox
History tells us that mistakes frequently happen when following this process, so you should
then:
Unzip the folder to a new location
Open the project and confirm that it still compiles and runs as expected
o If not, repeat the process from the start
KIT205 Data Structures and Algorithms: Assignment 1 – Data Structures
Synopsis of the task and its context
This is an individual assignment making up 10% of the overall unit assessment. The assessment criteria for this task are:
1. Implement basic functionality for a console-base application
2. Implement and test a linked list to store courses
3. Implement and test a BST to store students
4. Implement and test an AVL tree to store students
A significant and extremely important part of software development is thorough testing. Small programming errors may attract a large penalty if the error is something
that should have been picked up in testing! Please try to complete your program early to leave enough time for testing.
Match between learning outcomes and criteria for the task:
Unit learning outcomes
On successful completion of this unit you will be able to … Task criteria:
1. Transform a real world problem into a simple abstract form that is suitable for computation
2. Implement common data structures and algorithms using a common programming language
3. Analyse the theoretical and practical run time and space complexity of computer code in order to select algorithms for
specific tasks
4. Use common algorithm design strategies to develop new algorithms when there are no pre-existing solutions
5. Create diagrams to reason and communicate about data structures and algorithms
1-4
1-4
–
–
–
Criteria HD (High Distinction) DN (Distinction) CR (Credit) PP (Pass) NN (Fail)
You have: You have: You have: You have: You have:
1. Implement
basic program
functionality
Weighting 10%
Correctly implemented console application
Stored strings in appropriately sized dynamically
allocated memory
Implemented a loop that repeatedly waits for input
and exits when the input is 0
Organised data structures and other codes as required
(even if implementations are not correct)
Completed all HD
requirements with some
minor errors or
inconsistencies
Correctly implemented a basic console application
The application repeatedly waits for input and exits
when the input is 0
All data structures are correctly defined and organised
into files as specified (even if implementations are not
correct)
Correctly implemented a
basic console application
The application
repeatedly waits for
integer input and exits
when the input is 0
2. Implement a
linked list to
store courses
Weighting 30%
Correctly implemented linked list functions covered in
tutorials
Correctly read and inserted courses into linked list
Used correct data structures
Freed all list memory (including strings for storing
course names)
Written linked list code that is clear and easy to follow
Correctly implemented
linked list functions
covered in tutorials
Correctly read and
inserted courses into
linked list
Used correct data
structures
Completed all DN
requirements with
some minor errors
Used correct data
structures
Implemented linked list
functions covered in tutorials
Read and inserted courses into
linked list
-orCompleted all DN
requirements, but the correct
data structures have not been
used
Made a genuine attempt
to get list operations
working correctly
-orSome list operations
working, but correct
data structures have not
been used
3. Implement a
BST to store
students
Weighting 40%
Correctly implemented BST functions covered in
tutorials
Correctly read and inserted student numbers into BST
Used correct data structures
Freed all BST memory
Written BST code that is clear and easy to follow
Correctly implemented
BST functions covered in
tutorials
Correctly read and
inserted student numbers
into BST
Used correct data
structures
Completed all DN
requirements with
some minor errors
Used correct data
structures
Implemented BST functions
covered in tutorials
Read and inserted student
numbers into BST
-orCompleted all DN
requirements, but the correct
data structures have not been
used
Made a genuine attempt
to get BST operations
working
-orSome BST operations
working correctly, but
the correct data
structures have not been
used
4. Implement an
AVL tree to
store students
Weighting 20%
Completed task 3 to HD level, but using AVL tree Completed task 3 to DN
level, but using AVL tree
Completed task 3
to CR level, but
using AVL tree
Completed task 3 to PP level,
but using AVL tree
Completed task 3 to NN
level, but using AVL tree
