Tasks
| Faculty of Computing, Engineering and Science |
Assessment Cover Sheet and Feedback Form 2019-20
| Module Code: CS2S560 |
Module Title: Data Structures and Algorithms with Object Oriented Programming |
Module Team: Emlyn Everitt, Janusz Kulon |
| Assessment Title and Tasks: ZZ-Practical Assessment 1 |
Assessment No. 1 |
|
| Date Set: 20-Sep-19 |
Submission Date: 17-Jan-20 |
Return Date: 14-Feb-20 |
IT IS YOUR RESPONSIBILITY TO KEEP RECORDS OF ALL WORK SUBMITTED
| Marking and Assessment |
| This assignment will be marked out of 100% This assignment contributes to 50% of the total module marks. |
| Learning Outcomes to be assessed (as specified in the validated module descriptor https://icis.southwales.ac.uk/ ): 1) Demonstrate knowledge, comprehension and discernment in the efficient application of common data structures and algorithms, and collections. 2) Demonstrate knowledge, comprehension and discernment in the efficient application of object-oriented programming. |
| Provisional mark only: subject to change and / or confirmation by the Assessment Board |
Tasks
| Grading Criteria: |
Tasks
Tasks
Scenario
You work for Operating Systems Ltd, a company specialising in the retailing of operating
systems and a keen competitor of Microsoft. One day your boss comes to you to say that he
wants you to develop:
• An integer stack
• An integer queue
• A scheduling algorithm (subclass of queue) – using an integer for priority and storing
integer values to represent process IDs
for their main flagship OS, Windowless 9.
Towards this end, the company has provided you with a public API specification (see
Appendix A) that you need to adhere to in the delivery of this functionality. You are also
required to code everything yourself, restricting your use of libraries to <iostream> only.
Make sure that you handle exceptions (e.g. when removing an item from an empty stack or
queue).
The scheduling algorithm needs to provide the following functionality, as discussed in
lectures:
• Be a subclass of the Queue class
• Use an int value as a process ID
• Use an int value as a priority (i.e. 1 = low, 10 = high)
• Handle exceptions in case the priority value exceeds the above range
• Be able to schedule as many processes as there is memory available; this memory
will need to be allocated on demand from the heap
Additional marks will then be awarded for:
• Incorporating a system of prioritisation that allows each process to have a priority
value assigned to it and to then be processed in order of that priority outside of the
default FIFO ordering
• Developing a system that prevents blocking – e.g. when the continual addition of
high priority events prevent lower priority events from being processed
Extra marks will be awarded to those who:
• Utilise efficient ways to deliver some of the above functionality (e.g. O(log N))
The highest marks will be awarded to those students who address some or all of the more
complex issues stated above. Please examine the grading criteria for further details of the
assessment.
Tasks
Code Comments
It is of particular importance that your code is well commented. The comments you make
will form your documentation for this assignment and the quality of those comments will
contribute significantly to your overall mark. Comments should attempt to describe the
functionality of each section of code and how it fits into the overall behaviour of the
program rather than just superficially describing what each line of code does in isolation.
e.g.
It should also be noted that the marks awarded for comments will be weighted in favour of
the feature complexity they are attempting to describe; with comments successfully
describing the more advanced features resulting in the most marks being earned.
Submission
When submitting your work, please submit your code in a single .cpp file to Unilearn. Also,
make sure that you do not include the ‘main’ function in your submission.
Correct
| x++; | // x is the iterator used to keep track of the position in the data structure //which is incremented each time the code loops |
Superficial
x++ //x is incremented
Appendix A
class Node
{
public:
Node(int value, Node* nextptr = NULL, Node* prevptr = NULL, int currentpriority = 0);
int getVal(void);
Node* getNext(void);
Node* getPrev(void);
void setVal(int value);
void setPrev(Node* prevptr);
void setNext(Node* nextptr);
int getPriority(void);
void setPriority(int priority);
private:
Node* next;
Node* prev;
int priority;
int value;
};
class Stack
{
public:
Stack(void);
~Stack(void);
void Push(int value);
Node* NodePop(void);
int Pop(void);
private:
Node* top;
};
class Queue
{
public:
Queue(void);
~Queue(void);
void Enqueue(int i, int priority = 0);
int Dequeue(void);
protected:
Node* back;
Node* front;
private:
virtual Node* NodeDequeue(void);
};
class Scheduler : public Queue
{
private:
Node* NodeDequeue(void);
};