Data Structures And Algorithms Assignment - Efficient Sorting
Learning Outcomes
- Synthesise and implement stacks, linked lists, sorting and queues.
- Compile and use abstract data types within programs.
- Evaluate algorithms in terms of efficiency and justify the selection of the most appropriate data structure or algorithm for a given problem.
Task 1 -
This task requires you to produce fully working program/programs, which will compare operation times of various sorting algorithms for given sets of data.
You should carefully consider the criteria below and then develop a fully documented program that will calculate the time taken to sort lists of 10, 100, 1000, and 10,000 integer numbers which will be supplied by the tutor in class.
There should be a minimum of 3 sorting algorithms used in the program, including an insertion sort, a bubble sort and another sorting algorithm of your choice.
The program is to be written in a programming language of your choice.
You must write a report that includes the following: -
- A description of each algorithm used, including pseudo code and/or flowcharts.
- A full code listing with comments
- A table of results showing the time required for each algorithm to execute once. Use the speed of the insertion sort as a guide to compensate for different processor speeds.
- An explanation of how the timing of each algorithm is achieved.
- Justification of the best sorting algorithm to be used for the various data sets supplied.
- Any additional paperwork you consider necessary including additional research and discussions on sorting algorithms.
Additional marks will be awarded for complexity and explanations of algorithms used including discussions on how the test results were obtained.
Task 2 -
A bank has a call centre set up for customers and requires a piece of software to count and track waiting calls.
The telephone system can only keep 20 calls on hold at any time.
Once a call is made to the bank the following information is logged on a computer and put into a queue.
- Call number
- Time called
- Queue ID number
The program will initially have no calls in memory. A basic menu screen will allow the user to perform the following operations: -
1. Add data to the queue.
2. Put call through to operator.
3. Remove call from the queue (customer disconnect).
4. Update queue.
- When a call comes in the data is added to the queue.
- If a call is at the top of the queue then it will be the next one to get a free operator.
- Some calls will be disconnected by the customer before they reach the top of the queue, your program should allow for this.
On the menu screen you should also display the calls waiting and the time each call has been waiting.
This information is then to be used to calculate an average number of calls waiting and also the average wait time for a call to be sent to an operator. This should also be shown on the screen.
You may add additional functionality to the program if you consider it necessary.
Task 2.1 - Discuss the use and implementation of various methods to store data and also discuss the method you will use to create a working program which is best suited for this problem.
Task 2.2 - You must produce a specification for the data structure used. Fully explain how you will implement the data structure.
Task 2.3 - Produce a working program which creates and uses your chosen algorithm for this scenario.
Document and test the program and provide screenshots and a full code listing of your program.
Include any additional information necessary.
Task 2.4 - Evaluate your program and suggest areas for improvement.