Develop A Prototype System To Test Different Data Structure Options For The Student Database. Due to COVID, the University has had recent experience in run

Develop A Prototype System To Test Different Data Structure Options For The Student Database. Due to COVID, the University has had recent experience in running courses online.  This presents an opportunity to expand online courses to become MOOC (Massive Open Online Course) with many thousands of students enrolled in each unit.  This has the potential to create performance issues for the student record system.

Your task is to develop a prototype system to test different data structure options for the student database. Assessment/Assignment-2-Student-DB/Assignment 2 – Student DB – Copy – Copy.html

KIT205 Data Structures and Algorithms
Assignment 2

Due 10th September, 11:55pm

Due to COVID, the University has had recent experience in running courses online.  This presents an opportunity to expand online courses to become MOOC (Massive Open Online Course) with many thousands of students enrolled in each unit.  This has the potential to create performance issues for the student record system.

Your task is to develop a prototype system to test different data structure options for the student database.

The student database must support the following operations:

Add student

Remove student

Enrol student in a unit

Un-enrol student from a unit

Print an ordered summary of units and the number of students enrolled in each unit

Print an ordered list of students enrolled in a specific unit

Print an ordered list of units that a specific student is enrolled in

Assignment Specification – Part A (~80% of marks)

For this part of the assignment you will implement a prototype that uses a binary search tree of students (for the prototype you will store only student id), with each BST node also storing a linked list of units that the student is enrolled in (for the prototype, you will store only the unit code, as a string). You must use the BST and linked list code as 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 char* String;

typedef struct listNode{
String unit_code;
struct listNode *next;
} *ListNodePtr;

typedef struct list {
ListNodePtr head;
} UnitList;

typedef struct bstNode {
long student_id;
UnitList units;
struct bstNode *left;
struct bstNode *right;
} *BSTNodePtr;

typedef struct bst {
BSTNodePtr root;
} StudentBST;

The ListNodePtr and UnitList definitions and (modified) linked list functions must be placed in files list.h and list.c. The BSTNodePtr and StudentBST 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 all other program logic (there should not be any program logic or I/0 code in your linked list or bst files). This file will contain separate functions for each of the seven operations listed above, 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”, and then enroll student “123456” in the unit  “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:

Unit enrollments:
abc123 32
def123 0
def456 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

Unit names will always be strings less than 100 characters long and may contain any alpha-numeric characters (no spaces)

Student ids will always be positive integers in the range 0-999999

The user will never attempt to enrol a non-existent student in a unit

The user will never attempt to print data for a non-existent student

The user will never attempt to remove non-existent students

The user will never attempt to unenrol a student from a unit that they are not enrolled in

Memory Management

Unit 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 should free all associated dynamically allocated memory, including memory for the units that they are currently enrolled in. The quit function should also free all dynamically allocated memory.

Assignment Specification – Part B (~20% of marks)

This part of the assignment should only be attempted once you have fully implemented and thoroughly tested your 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.  Part B is worth only 20% of the marks, but may require more than 20% of the effort (mostly reading and testing).

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 standard BST.  To implement the AVL tree, reuse the BST struct definitions, but add a height variable to the node struct.  Leave all BST functions in place, but add AVL functions to your bst.h and bst.c files.  Add a switch in your main.c file so that it is easy for the marker to switch between BST and AVL functions (e.g. to switch between bst_insert and avl_insert).

Minimal assistance will be provided for this part of the assignment.  No assistance at all will be given unless you can 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 1000’s of students and courses).  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. Some small test files have been provided with input files (input1, input2) you can use for redirection and output files (output1, output2) that you can use to check for correct output.  However, it is recommended that you construct your own larger files to fully test your program!  As well as larger test files, it would also be wise to construct files that test edge cases. Testing is very important!  Few marks will be deducted for minor programming errors, but many marks may be deducted if these errors could be easily fixed if identified by thorough testing. Assignment Submission Assignments will be submitted via MyLO (using the Assignment 2 dropbox). Submissions should consist of a single zipped Visual Studio project. You should use the following procedure to prepare your submission: Make sure that your project has been thoroughly tested 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 (to save space you may remove the hidden ".vs" folder before zipping - but this is not required) 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 If not, repeat the process from the start (a common error occurs when copying projects, where the code files you are editing end up existing outside of the project folder structure – and therefore don’t get submitted when you zip the folder) Learning Outcomes and Assessment This assignment is worth 10% of your overall mark for KIT205.  Your submission will be assessed by examining your code and by running additional tests in Visual Studio.  If your submission does not run in Visual Studio 2019 on Windows, it cannot be assessed.  Grades will be assigned in accordance with the Assignment 2 rubric. The assignment contributes to the assessment of learning outcomes: LO1 Transform a real-world problem into a simple abstract form that is suitable for efficient computation LO2 Implement common data structures and algorithms using a common programming language LO3 Analyse the theoretical and practical run time and space complexity of computer code in order to select algorithms for specific tasks images/banners/0f5150f3-753c-4105-b996-ea9b35d9baba-2c540bbd852.au0f5150f3-753c-4105-b996-ea9b35d9baba Assessment/Assignment-2-Student-DB/input1.txt 1 123456 1 000001 1 999999 3 123456 tom470 3 123456 def102 3 000001 def102 3 999999 abc101 1 543210 3 999999 kkk305 3 999999 def102 1 111111 3 123456 kkk305 3 123456 abc101 7 123456 7 111111 7 999999 0 Assessment/Assignment-2-Student-DB/input2.txt 1 123456 1 000001 1 999999 3 123456 tom470 3 123456 def102 3 000001 def102 3 999999 abc101 1 543210 3 999999 kkk305 3 543210 def102 3 999999 def102 1 111111 3 123456 kkk305 3 123456 abc101 2 123456 3 000001 tom470 3 000001 def102 4 999999 kkk305 5 6 kkk305 6 def102 7 999999 0 Assessment/Assignment-2-Student-DB/output1.txt Enrolments for 123456: abc101 def102 kkk305 tom470 Enrolments for 111111: Enrolments for 999999: abc101 def102 kkk305 Assessment/Assignment-2-Student-DB/output2.txt Enrolment summary: abc101 1 def102 3 tom470 1 Students enrolled in kkk305: Students enrolled in def102: 1 543210 999999 Enrolments for 999999: abc101 def102 Table of Contents.html   KIT205 Data Structures and Algorithms - Assignment 2 - Student DB 1. Assignment 2 - Student DB 2. input1 3. input2 4. output1 5. output2

Submit a Comment

Open chat