COMP1828
Module Leader: Dr IK SOO LIM
Advanced Algorithms and Data Structures
Designing, developing & testing a journey planner
Faculty Header ID:
Contribution: 50% of course
Deadline Date: Monday 28/11/2022
This coursework should take an average student who is up-to-date with tutorial work approximately 30 hours
Feedback and grades are normally made available within 3 calendar weeks of the coursework deadline
Learning Outcomes:
1 Select and employ data structures appropriate to a variety of problems.
2 Formulate and solve mathematical models using appropriate algorithms and data structures.
3 Obtain programmatic solutions using appropriate software, including a high level programming language.
4 Describe and discuss the efficiency, complexity, accuracy and limitations of algorithms.
Plagiarism is presenting somebody else's work as your own. It includes: copying information directly from the Web or books without referencing the material; submitting joint coursework as an individual effort; copying another student's coursework; stealing coursework from another student and submitting it as your own work. Suspected plagiarism will be investigated and if found to have occurred will be dealt with according to the procedures set down by the University. Please see your student handbook for further details of what is / isn't plagiarism.
All material copied or amended from any source (e.g. internet, books) must be referenced correctly according to the reference style you are using.
Your work will be submitted for plagiarism checking. Any attempt to bypass our plagiarism detection systems will be treated as a severe Assessment Offence.
Coursework Submission Requirements
• An electronic copy of your work for this coursework must be fully uploaded on the Deadline Date using the link on the coursework Moodle page for COMP1828.
• For this coursework you must submit a single PDF document. In general, any text in the document must not be an image (i.e. must not be scanned) and would normally be generated from other documents (e.g. MS Office using "Save As .. PDF"). For mathematical notation, you can use MS Word equation tools
https://support.microsoft.com/en-us/office/write- an-equation-or-formula-
4f799df7-4ca4-4670-afd3-6135768b01d0 .
• For this coursework you must also upload the source code and any additional
supporting work as a single ZIP file.
• There are limits on the file size (see the relevant course Moodle page).
• Make sure that any files you upload are virus-free and not protected by a password
or corrupted otherwise they will be treated as null submissions.
• All coursework must be submitted as above. Under no circumstances can they be
accepted by academic staff
The University website has details of the current Coursework Regulations, including details of penalties for late submission, procedures for Extenuating Circumstances, and penalties for Assessment Offences. See http://www2.gre.ac.uk/current-students/regs
• Detailed Specification
This coursework is to be done in groups. Each member of the group will need to describe their contribution to the work and only one copy of the final report and the zip file will have to be uploaded per group (by a member, e.g. a group leader). See below for details of the assessment.
• Assessment Criteria
The assessment comprises one question and is worth 100 marks. See below for a detailed breakdown of marks for the question.
• Grading Criteria
Each member must make a significant individual contribution to the technical development work as well as contributing to the overall team effort. The allocation of marks will reflect the quality of the work produced and will be based on the breakdown provided by the team. For example, in a team of three members A, B, and C if the breakdown provided by the team is A=100%, B=100%, and C=50%. Then for an overall project mark of 60% this will mean that A is awarded 60%, B is awarded 60%, and C is awarded 30%. If the team do not provide any breakdown or if any nonsensible breakdown is provided by the team, then the marker will allocate the same mark to each team member.
Criteria for Assessment
80-100
70-79
60-69
50-59
40-49
30-39
0-29
Content, knowledge and understanding
Demonstrates exceptional systematic understanding of problem solving, computer programming and algorithmic performance. There is exceptional evidence of engagement with all key elements.
Demonstrates an excellent systematic understanding of problem solving, computer programming and algorithmic performance. There is also excellent evidence of engagement with all key elements.
There is a very good systematic understanding of problem solving, computer programming and algorithmic performance. There is also some very good evidence of engagement with all key elements.
Has demonstrated a good understanding problem solving, computer programming and algorithmic performance. There is also some good evidence of engagement with most key elements with some omission of detail.
Has demonstrated a satisfactory level of understanding of problem solving, computer programming and algorithmic performance. There are a few notable omissions and there is limited evidence of engagement with all key elements. Overall a satisfactory attempt at this criteria.
A poor understanding of one or more of the following - problem solving, computer programming and algorithmic performance.
There is insufficient evidence of engagement with the key elements. Overall an unsatisfactory attempt.
Little or no understanding of one or more of the following - problem solving, computer programming and algorithmic performance.
There is very little evidence of engagement with the key elements. Overall a very unsatisfactory attempt.
Cognitive/Intellectual Skills
Demonstrates exceptional use of a critical analysis of information leading to the proposal of a robust and detailed solution. There is exceptional evidence of reflection that identifies the strengths and weakness of the approaches undertaken.
Demonstrates an excellent use of a critical analysis of information leading to the proposal of a robust and detailed solution. There is also excellent evidence of reflection and judgement based on the interpretation of the results obtained.
Demonstrates a very good use of a critical analysis of information leading to the proposal of a detailed solution. There is also some very good evidence of reflection and judgement based on the interpretation of the results obtained.
Demonstrates some good critical analysis of information leading to the proposal of a detailed solution. There are some exposed weaknesses of cognitive skills. There is also some good evidence of reflection and judgement based on the interpretation of the results obtained.
Has shown some satisfactory level of critical analysis of information. There is evidence of reflection and judgement based on the interpretation of the results obtained at a threshold pass level.
Has shown little use of techniques to undertake a critical analysis of information. The reflection and judgement based on the interpretation of results is weak and lacks detail.
Has shown little or no use of techniques to undertake a critical analysis of information. The reflection and judgement based on the interpretation of results is very weak and lacks detail.
Communication, Organisation and Presentation
Graduate Employability and Application of Skills
Demonstrates exceptional use of argument and language which effectively communicates information to the target audience. The structure and flow of the report is clear and of an exceptional quality. There is exceptional evidence of the qualities of transferrable skills necessary for employment that required personal judgement and successful experimentation.
Demonstrates excellent use of argument and language which effectively communicates information to the target audience. The structure and flow of the report is clear and of an excellent quality. There is excellent evidence of the qualities of transferrable skills necessary for employment that required personal judgement and successful experimentation.
Demonstrates a very good use of argument and language which effectively communicates information to the target audience. The structure and flow of the report is clear and overall is very good. There is also very good evidence of the qualities of transferrable skills necessary for employment that required personal judgement and mostly successful experimentation.
There is good use of argument and language which communicates information to the target audience. The structure and flow of the report is mostly coherent and overall is good. There is also some good evidence of the qualities of transferrable skills necessary for employment.
The use of argument and language which communicates information to the target audience is mostly acceptable with some shortcomings in the grammar. The structure and flow of the report is barely acceptable with some presentation issues. There is also some evidence of the qualities of transferrable skills necessary for employment.
The use of argument and language which communicates information to the target audience is mostly at a substandard level. The structure and flow of the report is unacceptable with some presentation issues. There may also be little evidence of the qualities of transferrable skills necessary for employment.
The use of argument and language which communicates information to the target audience is at a substandard level. The structure and flow of the report is unacceptable with significant presentation issues. There may also be little/no evidence of the qualities of transferrable skills necessary for employment.
Referencing, sourcing, acknowledging and coverage
The exceptional use of appropriate references reflects clear and detailed understanding of the referenced works and its contents from a variety of sources.
The excellent use of appropriate references reflects clear and detailed understanding of the referenced works and its contents referenced works.
The use of references reflects a very good understanding of the cited work and its contents. Some references may not be the most recent.
The use of references reflects a good understanding of the cited work and its contents. Some references may not be the most recent or are taken from a narrow range of sources.
The use of references reflects a satisfactory understanding of the cited work and its contents. Some references may not be appropriate or the most recent or are taken from a narrow range of sources.
The use of references reflects a poor understanding of the cited work and its contents. The references may not be sufficient or appropriate or the most recent or are taken from a narrow range of sources.
Little or no cited work. The references may not be appropriate or the most recent.
Designing, developing and testing solutions for the London Underground system
Group setup:
You have a limited opportunity to form a team comprising four people to solve the problems outlined in this document. Please note that some of your team members will most likely not be in your allocated tutorial group, so you are advised to consider this as part of defining your group. You must nominate a team leader and (s)he must register your team with the course leader by the deadline date stated by the course leader and before you start to work on this assignment. You must do this by emailing the course leader Dr IK SOO LIM (
[email protected]) the names and 9-digit ids of all the team members and CC’ing all team members. You will get a confirmation email in two working days; if you do not get one, your email message may not have got through. If necessary, the course leader will (re)assign team members.
Data:
The London Underground tube system is a complex interconnection of stations across the London area. You are provided with a standard map in pdf format that depicts the network. This map was downloaded from the Transport For London (TFL) site at https://tfl.gov.uk/maps/track/tube . The travel times taken between any two successive stations are determined already based on previously collected data and are provided in the accompanying excel spreadsheet called “London Underground Data.xlsx”. This data :
1. has not been quality checked and may contain errors or omissions. You are to decide how you will report and act on these as part of your study.
2. does not include the waiting time at a station or the (dis)embarking of passengers.
Task 1: [30 %]
(1a)
Your team have been asked to provide a model software solution for a route planner of the London Underground tube system for use by the general public. You should provide a model that will determine the solution for the quickest journey time and you should carefully consider the design, implementation and testing of the software.
For a user of the underground system, your solution needs to provide
1. the functionality to quickly and efficiently elicit the information from the customer for
a planned route
2. provide a list of stations showing how the customer will travel from one starting
station (x) to the destination station (y) on the underground system 3. how long the journey will take in total
(1b)
Your team also has to provide the histogram of (quickest) journey times between each pair of stations.
Task 2: [30 %]
(2a)
Due to a certain reason, the government has to consider closing tube lines between immediate neighbouring stations as many as possible, while meeting the following condition: 1. A journey between any pair of stations should be still possible. For instance, even if the line between immediate neighbouring stations, Piccadilly Circus and Green Park, is closed, the journey between those two stations should be still possible on
a different route.
Your team has been asked to provide a model software solution to assist the government with the decision:
1. If the closure meeting the condition is not feasible, justify the conclusion.
2. If the closure is feasible, provide a set of the closed lines by specifying a pair of immediate neighbouring stations per line; e.g. Piccadilly Circus -- Green Park, if the
line connecting these immediate neighbouring stations is closed.
(2b)
Your team also has to report on the impacts of the closure on (quickest) journey times between each pair of stations.
Task 3: [30 %]
Your team is also asked to come up with your own idea to augment Task 1 or 2. An alternative is to come up with a new task related to the London Underground Data, which would require an algorithm that is different from those used for Tasks 1 and 2; you may use an algorithm that is not covered during the lectures but use an existing (library) code for it.
For instance, to augment Task 1, you may include an additional feature of a table or graphic showing the list of stations from start to destination with corresponding times of how long it will take: a table or graphic showing the list of stations from start to destination with corresponding times of how long it will take: travel time to next station, etc. To get a higher mark, you may NOT use the example of the table/graphic idea but use something else of your own. You should carefully consider the design, implementation and testing of the software based on your own idea.
The remaining 10 % or 10 marks are for the weekly log, the description of individual members’ contributions; see Deliverable 1.
Deliverables:
Deliverable 1 – the report in PDF format
Use the template (GroupX.doc) provided to write a report; replace ‘X’ with your number (e.g. for group 9, the final name should be Group9.doc and then exported as Group9.pdf). It should be saved or exported as a pdf format and uploaded as the main document.
This report must include:
1. Justification of the choice of the data structures and algorithms [10 marks] 2. Critical evaluation of the performance of the data structures and algorithms used
[10 marks]
3. Discussion for the choice of test data you provide and a table detailing the
tests performed
4. Screen-captured demonstration of your working source code
5. Outcomes of Task 1, 2, and 3
6. Conclusion and critical discussion on the limitation of the work done
7. Weekly log of progress, group formation, individual contribution toward the final
outcome by each team member [10 marks]
In one of the sections of the report, you should include the names of the group members and for each student named, no more than two paragraphs written by each student detailing their role, the tasks that they completed and a percentage of the total work completed (see Grading Criteria below).
Deliverable 2 – well-commented python source code
The correctly working source code should be uploaded as a zip file. This should be self- contained such that no additional download should be required to run it.
Failure of submitting the source code may lower your total mark by up to 50 marks.
Deliverable 2 should be placed in a zip file which must be uploaded separately from the report.
You must implement your solution using the python programming language. You may use any sample code provided in the module lectures, laboratories or other sources as an aid, but make sure you correctly reference any source code that you use that was NOT authored by your team. Unreferenced code taken from elsewhere may involve an investigation into an academic misconduct offence.
Finally, you are strongly advised to commence work on this coursework as soon as it has become available. If you are unsure about any of these instructions, then please contact the Module Leader with your query either by using email or make an appointment to see them online as early as possible.
[10 marks] [20 marks] [20 marks] [20 marks]