Faculty of Technology – Coursework Specification 2019/20
|Module name:||Data Structures and Algorithms|
|Title of the Assignment:||Assignment|
|This coursework item is: (delete as appropriate)||Summative||
|This summative coursework will be marked anonymously||
|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:||Tuesday 22nd October, 2019.|
|Date & Time Due:||Friday 15th November, 2019. 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 ([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.||Friday, 13th December, 2019.|
|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. David Smallwood|
|Contact details:||[email protected]|
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 15th November, 2019 12p.m. (midday)
The objective of this assessment is for you to demonstrate your understanding of issues related to the design and use of sequential data structures and algorithms.
Submit your work as a single Word document or pdf document through Turnitin via the portal available on Blackboard. Write your answers to the questions in the Word or pdf document.
DO NOT submit any code, either as separate files or within your document. Any code submitted will not be marked.
For each question, you will receive full marks if the answer provided is fully correct and includes all necessary aspects, and partial marks if the answer has some incorrect parts and/or is missing some essential concepts.
The assignment will be marked anonymously. You will compromise this anonymity if you put your name on the work. Please include your p-number on your assignment.
Assignment Problem Total marks: 100
Your task is to design data structure/s suitable for the following scenario. You may decide that the scenario requires a single data structure, or a combination of data structures – this is up to you to decide and explain. There is no perfect solution – there will be arguments about space and time that pertain to any solution you choose. Please read the whole assignment through carefully before considering your solution.
A computer program is to be written that will:
- Read in a complete text document one line at a time
- Allow the user to request specific information about the document and respond accordingly. For example, the user may ask the program to list all the line numbers on which a given word appears.
Your task is not to write the program itself, but to design the data structure/s that will most effectively support its operation. This can include (and/or may be any combination of) any of the data structures studied in the module so far, e.g. graphs, hash maps, linked lists, trees.
The data structure you choose to store the words in the document will be empty initially, and then will be updated dynamically as the text file is read in. You can assume that the text file will be read in one line at a time; that the line number is represented as a counter which is incremented after each line is read in; and that once a line of text has been read in, the line is broken up into a list of the individual words on that line.
When deciding upon your solution you should consider the efficiency and performance of the data structure during the ‘build phase’ (as the data structure is populated) and how it will subsequently support the following operations which will be available to the user once the file has been read in completely.
- Print all the line numbers on which a given word occurs
- Print true/false depending upon whether or not a given word was in the file
- Print the total number of times a given word occurs on a specific line (may be zero)
- Print all the words that occurred on a given line
In the operations above, a line can be identified by its line number. (There is no given maximum number of lines in the file, nor any given number of words on any line. However, for the sake of a theoretical upper limit, these numbers will not exceed the maximum value that can be stored in a 4-byte integer).
Part 1 – Your solution (40 marks – 20 marks for (a) and (b) together and 20 marks for (c))
(a) Outline any further 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 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. Be as specific as possible, e.g. if you chose to use a graph, explain details such as what type of graph you are using, whether it will be implemented as an adjacency matrix or adjacency lists, what the vertices represent, what the edges represent, what any weightings on the edges represent, etc. If you used a hash map, state what type the keys and values are, what the keys and values represent, etc. Note that these are just examples of the kind of information required. What you will need to describe will depend on your chosen solution. The idea is to make it clear what the solution is and how the information is going to be represented. You may include some generic diagrams to support your discussion.
(c) Show, using diagrams, how your chosen data structure will look when a relatively small (e.g. around five lines with an average of eight words on each line) number of lines has been input. Write down the actual lines of text used in your example clearly so that they can be checked fully against the pictorial representation you provide. The idea here is to include sufficient information so that the overall structure is fully illustrated. Make sure that your diagram is annotated so that each aspect is clear to someone else reading it. Write down any assumptions that you make. Diagrams that just contain only a few pieces of information will lose marks.
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. If relevant, compare it with alternative choices to explain the advantages of your solution. Your justification should discuss the performance of your data structure/s while the program is in its ‘build phase’ (i.e. reading in the text file line by line and adding words to the data structure).
Part 3 – Operations (40 marks – 10 marks for each of the four operations)
For each of the four operations listed above (in the assignment problem section), explain how the operation would work using the data structure/s you chose and what time complexity the operation would have. Make sure that each of the four answers clearly states which operation it relates to, so that the marker cannot misunderstand your explanations. We suggest that you write four subsections (numbered 1, 2, 3, 4) and that you write out the relevant operation at the start of each section: this should provide the necessary clarity to your solutions.
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.
END OF ASSIGNMENT
(See the following pages for the Marking Grid).