KIT205 Data Structures and Algorithms Assignment 1: Data Structures
th
Due: 26 April, 11:55pm
Introduction
You work for an online marketing company that manages a number of store loyalty programs. You have been asked to develop some software to manage the customer database. You decide to develop a prototype solution to test the performance of different data structures and algorithms.
The company manages the program for several stores, but this number is not expected to grow beyond a few dozen. More importantly, each program may have many thousands (perhaps even millions) of customers; and, as a result of aggressive cross-marketing, many of these customers are subscribed to multiple loyalty programs. Your software needs to provide the following functions:
1. Subscribe: This function will prompt the user for a customer id and loyalty program name. If this data does not already exist in the database, it will be added. A subscription will then be added for this customer and program.
2. Unsubscribe: This function will prompt the user for a customer id and loyalty program name. The function will then remove this subscription but will not remove customers or loyalty programs from the database, even if they have no subscriptions.
3. Print Summary: This function will print a line for each loyalty program, with each line containing the name of the program followed by the number of subscribed customers.
4. Print Subscribers: This function will prompt the user for the name of a loyalty program, then print an ordered list of customer ids for all subscribers to this program, each one on a separate line.
5. Print Subscriptions: This function will prompt the user for a customer id, then print all of the loyalty that this customer is subscribed to.
It is very important that access to data is very fast since many operations may occur each second. This will be especially important when dealing with customers since the number of customers may be very large and insert, delete, and find operations will be very common.
Initially, you decide to test performance using a combination of binary search trees, linked lists and arrays, but you would like to test an AVL tree as well. For preliminary testing, you decide that only the customer ids and loyalty program names will be stored.
Assignment Specification – Part A
For this part of the assignment you will select appropriate linked list, BST, and array data structure to implement the four operations. Part of the assignment task is to use these data structures in an efficient way. Your implementations of list and BST data structures MUST be based on the definitions used in lectures and tutorials as given below.
typedef struct listNode{
int data;
struct listNode *next;
} *ListNodePtr;
typedef struct list {
ListNodePtr head;
} List;
typedef struct bstNode {
int data;
struct bstNode *left;
struct bstNode *right;
} *BSTNodePtr;
typedef struct bst {
BSTNodePtr root;
} BST;
These data structures will need to be modified to support the customer and loyalty program information, which will be stored as long ints and strings. You will also need to add cross- references between the data structures to represent subscriptions. These may be one-way references – i.e. a customer might have references to the programs they are subscribed to, but the programs might not have references to the subscribed customers, or vice versa.
The ListNodePtr and List definitions and (modified) linked list functions must be placed in fileslist.handlist.c. TheBSTNodePtrandBSTdefinitionsand(modified)BSTfunctions 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 four operations listed in the introduction, as well as a fifth 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-4 will be selected by typing 1-4 at the command prompt. Quitting the application will be selected by typing 0. For example, the following input sequence would subscribe the customer ‘123’ to the loyalty program ‘abc’, and then quit:
1 123 abc 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 3 and 4, 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 3, the output might be:
Current subscriptions:
abc 32
def 0
ggg 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-4
• Loyalty program names will always be strings less than 100 characters long and may
contain any alpha-numeric characters excluding spaces
• Customer ids will always be positive integers in the range 0-999999999
• The user will never attempt to print data for a non-existent loyalty program
• The user will never attempt to print data for a non-existent customer
Memory Management
Loyalty program names should be stored in appropriately size dynamically allocated memory. Names will always be less than 100 characters long. For example, the program name “abcdef” would be stored in a char string of length 7.
Unsubscribing from a program may require you to free memory for that subscription (but not for the customer or program itself). The quit function should free all dynamically allocated memory.
Solution Requirements
You must develop a reasonably time efficient solution, but you also want to keep the code clean and simple to make your code easier to modify and maintain (a computer scientist called Donald Knuth, famously said that “premature optimisation is the root of all evil”).
Remember that, while the number of customers may be large, the number of loyalty programs is expected to be relatively small.
So, to score full marks your solution must:
• utilise at least one linked list and at least one bst
• strings must be stored in appropriately sized dynamically allocated memory
• the memory for all data structures should be freed when the data is no longer
required
• If the number of customers is C and the number of loyalty programs is L then:
o Op1shouldbeO(L+logC) o Op2shouldbeO(L+logC) o Op3shouldbeO(L*C)
o Op4shouldbeO(L+C)
o Op5shouldbeO(L*logC)
Note: A clever implementation might be able to achieve a better Big O for some of these operations, but that is not required to achieve full marks on this assignment. You will not receive extra marks for an implementation that achieves better performance.
Also note that the following work would get close to a pass mark:
• BST and linked list code implemented correctly as per tutorial work
• Evidence that you have made a sensible choice about how to use the data structures (this could be determined from code comments or variable names, that make it clear
what choices you have made)
• BST and linked list code adapted to store customers and loyalty programs (node
definitions only – functions don’t need to be correctly adapted)
• A working main loop (calls functions when options are selected, functions collect
required input, but may not do anything with that input, exits without errors)
• A solid attempt to get BST and linked list functions working in this context (with the
main loop and adapted data structures)
It is best to submit a program that compiles and runs without errors, even if the program doesn’t do anything. If you have added new code that breaks you program, comment this code out before submitting (and add an explanation) so that the marker can easily see what you have completed. After running your program, the marker will then check the code to determine what else you have attempted. Code that doesn’t compile or crashes is extremely difficult to mark, and the marker may be forced to give you less marks if they are unable to confirm what is working (they have very limited time to fix bugs).
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. (If you look at the marking sheet below, you will see that this part is worth at most 15%)
The requirements for this part of the assignment are exactly the same as for part A except that an AVL tree must be used, rather than a BST. The AVL code should be placed in bst.h and bst.c, with AVL functions added to these two files (you may also need to modify the node definition, but this should have no effect on the BST functions).
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 customers). 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
• Upload a copy of the zip file to the MyLO dropbox
NOTE: By submitting your assignment you are implicitly stating that the submitted work is your own, except where you have explicitly and clearly acknowledged the work of others. For example, if your solution has been developed after consulting a particular website, you should add a comment to the top of your file that describes how you used that resource and where to find it. Failure to acknowledge any help that you received or resources that you have utilised and instead presenting the work as your own is plagiarism and will be dealt with through academic misconduct procedures.
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 Ifnot,repeattheprocessfromthestart
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. Select appropriate data structures to store problem-specific data
2. Adapt generic data structures for use in a specific problem
3. Implement generic list data structures and algorithms
4. Implement generic tree data structures and algorithms
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 efficient 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, 2 3, 4 -
-
-
Criteria
HD (High Distinction)
DN (Distinction)
CR (Credit)
PP (Pass)
NN (Fail)
You have:
You have:
You have:
You have:
You have:
1. Select appropriate data structures to store problem-specific data
Weighting 10%
Data structures have been mapped to problem data in a way that promotes efficient time and memory utilisation
Data structures have been mapped to problem data
Working linked list and BST code from tutorials, but little attempt to match data structures to problem data
2. Adapt generic data structures for use in a specific problem
Weighting 15%
Correct adaption of linked list data structure for storing customers, programs or subscriptions
- and -
Correct adaption of tree data structure for storing customers, programs or subscriptions
Correct adaption of linked list data structure for storing customers, programs or subscriptions
- or -
Correct adaption of tree data structure for storing customers, programs or subscriptions
Partially correct adaption of linked list data structure for storing customers, programs or subscriptions
- or -
Partially correct adaption of tree data structure for storing customers, programs or subscriptions
Correct code for input loop, but little attempt to adapt data structures for this problem
3. Implement generic list data structures and algorithms
Weighting 25%
Linked list functions implemented correctly, including freeing all memory correctly (including on quit)
Linked list functions implemented correctly, without freeing all memory
Implemented some linked list functions correctly for this problem
Little attempt to get linked list operations working
4. Implement generic tree data structures and algorithms
Weighting 50%
AVL functions implemented correctly, including freeing all memory correctly (including on quit)
Implemented some AVL functions correctly for this problem.
BST functions implemented correctly, including freeing all memory correctly (including on quit)
Implemented some BST functions correctly for this problem.
Little attempt to get BST operations working