Faculty of Technology –Coursework Specification 2020/2021
Module name: Data Structures and Algorithms
Module code: CTEC2909
Title of the Assignment: Assignment
This coursework item is: (delete as appropriate) Summative
This summative coursework will be marked anonymously Yes
The learning outcomes that are assessed by this coursework are:
1 Explain and implement a variety of classical data structures.
3 Analyse specific programming language and library support for the development of sequential programs.
This coursework is: (delete as appropriate) Individual
This coursework constitutes 60% to the overall module mark.
Date Set: 28th October 2020.
Date & Time Due: Friday 20th November, 2020. 12p.m. (midday)
Your marked coursework and feedback will be available to you on:
If for any reason this is not forthcoming by the due date your module leader will let you
know why and when it can be expected. The Head of Studies (headofstudies-
[email protected] ) should be informed of any issues relating to the return of marked
coursework and feedback.
Note that you should normally receive feedback on your coursework by no later than
four working weeks after the formal hand-in date, provided that you met the
submission deadline.
18th
December,
2020.
When completed you are required to submit your coursework to:
• Blackboard VLE through Turnitin link
Late submission of coursework policy: Late submissions will be processed in accordance with
current University regulations which state:
“the time period during which a student may submit a piece of work late without authorisation and
have the work capped at 40% [50% at PG level] if passed is 14 calendar days. Work submitted
unauthorised more than 14 calendar days after the original submission date will receive a mark of
0%. These regulations apply to a student’s first attempt at coursework. Work submitted late without
authorisation which constitutes reassessment of a previously failed piece of coursework will always
receive a mark of 0%.”
Academic Offences and Bad Academic Practices:
These include plagiarism, cheating, collusion, copying work and reuse of your own work, poor
referencing or the passing off of somebody else's ideas as your own. If you are in any doubt about
what constitutes an academic offence or bad academic practice you must check with your tutor.
Further information and details of how DSU can support you, if needed, is available at:
http://www.dmu.ac.uk/dmu-students/the-student-gateway/academic-support-office/academic-
offences.aspx and http://www.dmu.ac.uk/dmu-students/the-student-gateway/academic-support-
office/bad-academic-practice.aspx
Tasks to be undertaken: See (following) attached document.
Deliverables to be submitted for assessment: See (following) attached document.
How the work will be marked: See (following) attached document.
Module leader/tutor name: Dr. George Okeyo
Contact details: [email protected]
Assignment

About this assessment
This assignment has THREE (3) parts with a total of 100 marks, which will constitute 60%
of your final mark for the module. Answer all parts.
The deadline for submitting your work via Turnitin on Blackboard is Friday 20th November,
2020 12p.m. (midday)

Objectives
The objective of this assessment is for you to demonstrate your understanding of sequential
data structures and the ability to apply that knowledge to design suitable data structures in
problem solving.

Submission
Submit your work for all sections apart from Part 1(c) as a single Word document or pdf
document through Turnitin via the portal available on Blackboard. Write your answers to the
questions, apart from Part 1(c), in the Word or pdf document. Submit Part 1(c) as a single zip
file.

Marking
For each question submitted in Word or PDF, you will receive full marks if the answer
provided is fully correct and includes all necessary parts, and partial marks if the answer has
some incorrect parts and/or is missing some essential concepts. For Part 1(c), you will receive
full marks for a data structure with at least five functional operations and fully commented
code. You will receive partial marks otherwise.

Anonymity
The assignment will be marked anonymously. You will compromise this anonymity if you
put your name on the work. Please include only your p-number on your assignment.

Assignment Specification -Total marks: 100
Choice of Programming Language
We expect you to develop your solution in Java. However, you may use an alternative
language such us C++ or Scala.

Specification
In a university faculty, each student is assigned a mentor at Level 4. Level 5 students are
assigned to mentor Level 4 students. Similarly, Level 6 students can mentor Level 5students.
Each student is mentored by only one student. However, each student mentor can mentor
several students. The faculty executive needs a solution that allows the details of mentors and
mentees to be stored and manipulated. For instance, it should be possible to: a) find a student,
and details of mentor and mentees as appropriate, b) modify mentors and mentees when
needed, c) print out details of each mentor and mentees, etc. For a Level 6 student, it should
be possible to navigate to their mentee chain, i.e. the Level 5 students that they mentor and
the Level 4 students that are mentored in turn by the Level 5 students. Table 1 gives an
example of data about mentors and mentees that should be stored and manipulated by the
solution.

Table 1: Mentorship Record
Mentor Mentees
P2531111 P2531120, P2532211
P2531120 P2530201
P2532211 P2530150, P2530190, P2530210
P2534141 P2530229, P2530250
P2530001 P2530230, P2534141

From Table 1, P2531111 and P2530001 are Level 6 mentors. P2531120, P2532211 and
P2534141 are Level 5 mentors but are also mentees to Level 6 students. P2530201,
P2530150, P2530190, P2530210, P2530229, and P2530250 are Level 4 mentees. P2530230
is a Level 5 student who is yet to be allocated a mentee.

You should design a data structure that models the scenario described above and stores the
kind of data depicted in Table 1. In actual sense, you should design an Abstract Data Type
(ADT). For simplicity, the data structure will only need to store p numbers (which are
strings). You should also write a program that simulates the working of the designed data
structure, showing some of its operations.

Task Description
Please read the task description carefully before you embark on developing your solution.
A data structure will be needed that will support at least five (5) of the following operations:
• Assign student mentors to mentees.
• Let the user search for a mentee determine if the mentor has been assigned
• Find a mentor for a given mentee
• Let the user search for a mentor
• Find all the mentees for the given mentor
• Reassign mentors
• Reassign mentees
• Remove mentors
• Remove mentees at any level of study
• Etc.

Think of your data structure as a library that will be available for programmers to use in
implementing the appropriate program to maintain the records of mentors and mentees. You
should decide on which data structures -arrays, linked lists, trees, graphs, hash maps- would
best form the building blocks for the data structure that you design. You should also write a
simple program that invokes at least five (5) of the above operations.

The key thing to consider is the efficiency of the operations for the proposed data structure. It
is desirable that the proposed data structure defines efficient operations as measured by time
complexity.


Part 1 – Your solution (50 marks – a) 5 marks, (b) 10 marks, c) 25 marks, and
d) 10 marks)

a) Outline any assumptions you make about how the program will operate that affect your
decisions on the data structure. Please note that any such assumptions should be realistic
and justifiable in light of the scenario.

b) Explain which data structure/s you chose and how it would store the information. The
task is to explain how it will be used for this particular problem, not just generic
information about the data structure. Provide as much detail as possible. For instance, if
you choose to use a tree, explain what each node represents, what type of tree you are
using, how the tree is implemented. If each node is a hash map, explain what the keys and
values represent, and so on.

c) Provide code for the designed data structure and the simple program that invokes its
operations. Include comments in the code to make the data structure and the program that
invokes its operations easy to understand.

d) Table 1 is an example of data that forms a mentor-mentee chain. Show, using
diagrammatic illustrations, how your chosen data structure will look when a mentee-
mentor chain of a few students from Level 4 to Level 6 is created. Clearly label or
annotate the diagrams so that it is easy for the reader to understand the representation.

Part 2 – Justification of the choice (20 marks)

Explain the reasons behind your choice of data structure/s. This might include issues like the
time complexity of operations that will be used on your structure/s, the space complexity, the
ability of your chosen structure to handle a particular kind of information, or any other
reasons you had. It may be helpful to compare your solution with alternative choices to
explain its advantages.

Part 3 – Operations (30 marks – 10 marks for each of the three operations)

Select three operations (as per the task description or any additional operations you define),
and for each operation implemented in the data structure, explain how the operation would
work using the data structure/s you chose and the time complexity that the operation would
have. Make sure that each of the three answers clearly states which operation it relates to, so
that the marker cannot misunderstand your explanations. We suggest that you write three
subsections (numbered 3(a), 3(b), and 3(c) and that you write out the relevant operation at the
start of each section: this should provide the necessary clarity to your solutions.

Word Limits
For all sections, except Part 1(c), it is expected that in total you will only have one or two
pages of text and diagrams. The emphasis in marking will be on whether you explained the
relevant points correctly, and not on how long your answers are. Brief paragraphs of about
80-100 words to answer each section would be sufficient as long as the necessary points are
mentioned. Part 1(c) will be submitted separately as a zip file.


END OF ASSIGNMENT

See the following pages for the Marking Grid
Mark
Range
Part 1a and 1b Part 1c Part 1d Part 2 Part 3
90-
100%
An appropriate solution with
no or very minor
typographical errors only,
with a clear explanation of
the structure’s behaviour,
including relevant details as
described in the question
specification, demonstrating
an excellent understanding
of the principles.
A suitable data structure
that implements at least five
operations and a program
that invokes at least five
operations has been
implemented. In addition,
the solution is fully
annotated with clear,
detailed, and meaningful
comments.
Clear and appropriate
diagrams/tables showing the
example data or another similar
example, with the data correctly
represented according to the
chosen structure and no errors
except minor typographical
errors, demonstrating an
excellent knowledge of the
chosen data structure/s.

An excellent
justification of the
choice with correct
reasoning containing no
errors except minor
typographical errors.
An excellent
knowledge of the
relevant concepts has
been demonstrated.

A clear, correct explanation of
how each operation works and the
correct time complexity given,
with no errors except minor
typographical errors. An excellent
knowledge of the relevant
concepts has been demonstrated.

80-
89%
An appropriate solution with
minor errors only, with a
clear explanation of the
structure’s behaviour and the
chosen solution, including
relevant details as described
in the question specification,
demonstrating a very good
understanding of the
principles.
A suitable data structure
that implements at least five
operations and a program
that invokes at least five
operations has been
implemented. However, the
comments have minor
errors or deficiencies.
Clear and appropriate
diagrams/tables showing the
example data or another similar
example, with the data correctly
represented according to the
chosen structure and only some
minor errors that do not indicate
a lack of knowledge. The answer
demonstrates a very good
knowledge of the chosen data
structure/s.

A very good
justification of the
choice with correct
reasoning containing
only some minor errors.
A very good knowledge
of the relevant concepts
has been demonstrated.

A clear, correct explanation of
how each operation works with
only minor errors, and the correct
time complexity given, or with
minor errors which still
demonstrate a very good
understanding of complexity
analysis. A very good knowledge
of the relevant concepts has been
demonstrated.

70-
79%
An appropriate solution with
minor errors or some minor
deficiencies, with a generally
clear explanation of the
structure’s behaviour and the
chosen solution, including
most relevant details as
described in the question
specification, demonstrating
A suitable data structure
that implements at least five
operations and a program
that invokes at least five
operations has been
implemented. However, the
solution has minor errors in
operations, comments, or
component data structures.
Clear and appropriate
diagrams/tables showing the
example data or another similar
example, with some minor errors
in the representation of the data
that indicate some incorrect
understanding of the chosen data
structure/s, but still demonstrates
a good level of knowledge.
A good justification of
the choice with mostly
correct reasoning
containing some errors
but still demonstrating
a good knowledge of
the relevant concepts.

A clear, mostly correct explanation
of how each operation works with
some errors. An incorrect time
complexity may have been given,
but the answer still demonstrates a
good knowledge of complexity
analysis, or the other aspects of the
answer demonstrate a very good
understanding of how the
a good understanding of the
principles.
operation works. A good
knowledge of the relevant
concepts has been demonstrated.
60-
69%
A solution that is generally
appropriate but has some
flaws or errors, and/or where
the explanation is lacking
certain details that make the
full intention clear. The
solution demonstrates a
generally good
understanding of the
principles.
A data structure solution
that is generally adequate
but has some flaws or errors
in comments, operations, or
component data structures.
In addition, a program that
invokes some of the
operations has been
implemented.
Clear and appropriate
diagrams/tables showing the
example data or another similar
example, with some errors in the
representation of the data that
indicate some incorrect
understanding of the chosen data
structure/s, but still demonstrates
a generally good level of
knowledge.

A generally good
justification of the
choice with mostly
correct reasoning
containing some errors
but still demonstrating
a generally good
knowledge of the
relevant concepts.

A generally correct explanation of
how each operation works with
some errors. An incorrect time
complexity may have been given,
but the answer still demonstrates a
generally good knowledge of
complexity analysis, or the other
aspects of the answer demonstrate
a good understanding of how the
operation works. A generally good
knowledge of the relevant
concepts has been demonstrated.

50-
59%
A solution that is mostly
appropriate but has some
significant flaws or errors,
and/or where the explanation
is lacking significant details,
but where the overall intent
is still clear. The solution
demonstrates an adequate
understanding of the
principles.
A data structure solution
that is generally adequate
but fails to provide
important operations. In
addition, the choice of
component data structures
does not fully represent the
problem specification. In
addition, a program that
invokes some of the
operations has been
implemented.
Generally clear and appropriate
diagrams/tables showing the
example data or another similar
example, with major errors in the
representation of the data
indicating some incorrect
understanding of the chosen data
structure/s, but where the general
idea appears to be correct. An
adequate level of knowledge has
been demonstrated.

A sufficient
justification of the
choice with some
errors, demonstrating
an adequate knowledge
of the relevant
concepts.
A sufficient explanation of how
each operation works with errors,
but which still demonstrates an
adequate level of knowledge. An
incorrect time complexity may
have been given. An adequate
level of knowledge of the relevant
concepts has been demonstrated.

40-
49%
A solution that will not work
correctly as described but is
generally adequate if
significant flaws or errors
are ignored, and/or where the
explanation is unclear but
appears to have the general
idea correct. An
A data structure solution
that fails to work and
support the operations
described in the problem
specification. However, the
solution demonstrates some
grasp of data structure
concepts and operations.
Generally appropriate
diagrams/tables showing the
example data or another similar
example, with major errors in the
representation of the data
showing incorrect understanding
of the chosen data structure/s. A
Significant errors in
reasoning in the
justification of the
choice, demonstrating a
basic level of
knowledge.
An incorrect explanation of how
each operation works, but which
still demonstrates a basic level of
knowledge. An incorrect time
complexity may have been given.
A basic level of knowledge of the
relevant concepts has been
demonstrated.
understanding of the basic
principles has been
demonstrated.
basic level of knowledge has
been demonstrated.


30-
39%
A solution that does not
handle the problem as
described due to significant
problems, and/or where the
explanation is so unclear that
it is not possible to
determine the intent. A weak
understanding of the basic
principles has been
demonstrated.
A data structure solution
that cannot solve the
problem described in the
problem specification. The
solution presents some
comments.
Diagrams/tables that are not
appropriate for the chosen
structure and/or do not show a
suitable amount of data to enable
the solution to be assessed,
and/or have significant errors in
the representation of the data. A
weak understanding of the basic
principles has been
demonstrated.

Incorrect reasoning for
the justification of the
choice containing
significant errors. A
weak understanding of
the basic principles has
been demonstrated.

A weak and incorrect explanation
of how each operation works. An
incorrect time complexity may
have been given. A weak level of
knowledge of the relevant
concepts has been demonstrated.

20-
29%
A weak solution that does
not handle the problem as
described due to significant
problems, and/or where the
explanation is so unclear that
it is not possible to
determine the intent. Very
low understanding of the
principles has been
demonstrated.
A data structure solution
that is weak and provides
no more than two
operations.
Incorrectly constructed
diagrams/tables that are not
appropriate for the chosen
structure and/or do not show a
suitable amount of data to enable
the solution to be assessed,
and/or have very significant
errors in the representation of the
data. A very low understanding
of the basic principles has been
demonstrated.

Incorrect reasoning for
the justification of the
choice containing
significant errors. A
very weak
understanding of the
basic principles has
been demonstrated.

A very weak and incorrect
explanation of how each operation
works. An incorrect time
complexity may have been given.
A very weak level of knowledge of
the relevant concepts has been
demonstrated.

10-
19%
A very weak solution that
does not handle the problem
as described due to
significant problems, and/or
where the explanation is so
unclear that it is not possible
to determine the intent. An
extremely low understanding
of the principles has been
demonstrated.
A data structure solution
that is very weak and
provides only one
operation.
Incorrectly constructed
diagrams/tables that are not
appropriate for the chosen
structure and/or do not show a
suitable amount of data to enable
the solution to be assessed,
and/or have very significant
errors in the representation of the
data. An extremely low
understanding of the basic
Incorrect reasoning for
the justification of the
choice containing
significant errors. An
extremely low
understanding of the
basic principles has
been demonstrated.

The explanation is incorrect and
demonstrates an extremely low
understanding of the basic
concepts.
principles has been
demonstrated.

0-9% An incorrect solution to the
problem demonstrating no
understanding of the
principles.
A data structure solution
that is completely unrelated
to the problem
specification.
Incorrect diagrams/tables and/or
does not show a suitable amount
of data to enable the solution to
be assessed. No understanding of
the basic principles has been
demonstrated.

Incorrect or no
reasoning for the
justification of the
choice demonstrating
no understanding of the
basic principles.

Incorrect or no explanation,
demonstrating no understanding of
the basic concepts.


欢迎咨询51作业君