Reference no: EM131008159

I have my DATA STRUCTURE AND ALGORITHMS programming assignment

WHICH SHOULD BE DONE ON VISUAL STUDIO IN C PROGRAMMING

Let me know how and what sort of help you can provide

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 course
2. Remove course
3. Enrol student
4. Un-enrol student
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 is small, but may grow significantly, so a scalable solution is required. 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.

The number of students per course 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 student enrolments, 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

For this part of the assignment you will implement a prototype that uses a linked list to store courses, with each course having a name and a BST of students. 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 bstNode {

long student_id;

struct bstNode *left;

struct bstNode *right;
} *BST;

typedef struct course{

char *name; BST students;

} Course;

typedef struct courseNode {

Course data;

struct courseNode *next;

} *CourseList;

The Course and CourseList definitions and (modified) linked list functions must be placed in files courselist.h and courselist.c. The BST 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 create a course called "abc123" and enrol a student with id "123456" in that course then quit the application:

1
abc123

3
abc123

123456
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 or 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: Courses that contain enrolled students may be removed, in which case student data for that course 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

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. No assistance at all will be given unless you can demonstrate a fully implemented and thoroughly tested solution to part A.

Synopsis of the task and its context

This is an individual assignment making up 12% of the overall unit assessment. The assessment criteria for this task are:

1. Implement and test a linked list to store courses

2. Implement and test a BST to store students

3. Implement and test an AVL tree to store students

A significant part of the assessment procedure will involve automated tests. Therefore, it is very important that your own testing is very thorough.

Attachment:- Assignment.rar