ELE00028I Algorithms & Numerical Methods Coursework Assessment 2021/22
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
ELE00028I Algorithms & Numerical Methods Coursework
Assessment 2021/22
ELE00028I: Algorithms and Numerical Methods
Coursework Assessment 2021/2022
Task: Design, implement and test a program that constructs a graph of cities and energy expended in travelling between them, then outputs the paths with minimal energy consumption between pairs of specified locations.
The context of this assessment is the future when electric cars are the norm and so is battery charging onthego with the use of wireless chargers under the roads. The chargers can sense the presence of a car above them and charge as the car passes over, resulting in a net positive energy gain (or a net negative loss of energy) of the battery. The “energy” data file provided, lists the energy loss incurred when travelling from one city to the other. Some roads have wireless chargers embedded under them, thus resulting in a net negative amount of energy expended (or net energy gained).
The objective of this assessment is to choose the path of least energy expenditure or even maximum energy gain, given a source and a destination city. All the paths connecting source and destination cities are twoway roads i.e. the car can go both ways and will expend the same energy going from source to destination and vice versa. However, in the best path, the car should visit each city only once (to prevent a chance of looping around the same city constantly to gain energy).
You are to write and verify a program in C that implements a graph abstract data type (ADT) suitable for the processing of information about energy spent in travelling between cities, and that returns the path between two cities that leads to least energy loss. It should read and store information from a tabdelimited “energyv221” file in which each line consists of two cities and the net loss/gain in energy in travelling between them. A printout of the file is appended. An electronic version (which should be used in the assessment) can be found on the course website at
wiki.york.ac.uk/display/EE/Algorithms
– under the “Assessment” section.
The program should read in a second tabdelimited file, “citypairs” in which each line consists of two cities. For each pair of cities, it should find the best path between those cities and print out a list of the cities on the route and the overall energy spent. You should run your program and include the output in your report for a file containing the following cities:
Lincoln Doncaster Bristol
Perth
Whitby
Blackpool
You must decide the most appropriate data structure and algorithms. As discussed in class a very good implementation will:
• Use a welldesigned graph ADT that localizes information
• Use a shortest path algorithm, such as BellmanFord algorithm
• Take care of negative cycles in the graph
This assignment counts for 100 % of the total mark of Algorithms and therefore 50 % of the total mark of ELE00028I Algorithms and Numerical Methods.
Academic Conduct
This is an individual assignment – you must work on the program and report on your own. You may consult any sources of information you can find providing you give appropriate reference and attribution to the authors.
Borrowing small reusable pieces of useful code from other sources is acceptable. However, wholesale copying or reworking of a complete program written by someone else is against the rules. If you use fragments of code written by anyone else, you must make it clear in both your report and the code which part is yours and which has been written by the other person.
If the rules on what constitutes correct academic conduct are not clear, please consult the university regulations Academic Misconduct as indicated on the front sheet for this assignment.
Submission
You are to write your program in standard ANSI C using Code::Blocks and the minGW (gcc) C com piler. The program must compile and execute correctly on the university lab machines available via the virtual desktop service (so the “local install” version of this is also acceptable).
Submission will be electronic via the VLE in a zipped folder containing two parts:
1. A PDF report (no more than 6 A4 pages in length).
2. The Code::Blocks project folder containing at least (a) A .cbp Code::Blocks project file
(b) A src folder containing the C source code of your program
(c) Any data files you create / use as input to your program
The written report should explain your design, your choice of data structures and algorithms used in the program and should include consideration of memory requirements and computational efficiency. It should clearly explain how you tested the program. Include the output from your program for the cases described above.
You should implement the program in the form of one or more C modules, i.e. with a .h interface file, a .c implementation file and a main .c program.
Your program does not need an interactive user interface (and certainly not a graphical user interface). It is acceptable, for example, to invoke your program through a command line interface like “mypro gram energy citypairs output” where myprogram is the name of your program, energy is the name of the provided text file of energy loss between cities, citypairs is the name of the text file saying which
particular start and end cities are to be calculated, and output is the name of a text file in which to write the output. But, appropriate default values for the file names should be assumed by the program.
NOTE: Anonymised marking – use your exam number only
Marking will be done anonymously so DO NOT put your name on or in any of the submission parts. Instead, your report, code comments and filenames should identify you using your exam number only.
Marks Allocation
In report:
Design choices and justification. |
/ 20 |
Testing methodology, results and comment. |
/ 20 |
In code:
Correctness – syntax, logic, function. |
/ 20 |
Clarity and maintainability – structure, style, comments. |
/ 20 |
In both:
Program match to report, including verification of output for given city pairs file and efficiency as claimed. |
/ 10 |
Program match to spec – complete, correct, including correct output for an unseen citypairs file. |
/ 10 |
Data file
York
Leeds
Liverpool
Manchester
Reading
Hull 60
Doncaster
Nottingham
Sheffield
Oxford
-47
161
-61
-43
Oxford
Birmingham
Liverpool
Carlisle
Nottingham
Birmingham
Leicester
Blackpool
Newcastle
Birmingham
103
63
79
95
-77
Leeds
Glasgow
York 39
Edinburgh -74
Moffat
Doncaster
Northampton
Leicester
Sheffield
Whitby
Glasgow
Lincoln
Sheffield
Carlisle 65
Hull 76
Birmingham 90
Lincoln
Birmingham
Newcastle
Perth 93
Doncaster
Doncaster
Cardiff Bristol
Bristol Reading
Hull Nottingham
Blackpool Leeds
Birmingham Bristol
Manchester Leeds
Carlisle Blackpool
Birmingham Liverpool
Perth Edinburgh
Leicester Northampton
Newcastle York
Glasgow Moffat
Leicester Sheffield
Carlisle Liverpool
Birmingham Manchester
Birmingham Cardiff
Oxford Bristol
Leeds Hull 89
Edinburgh Carlisle
Nottingham Sheffield
Liverpool Manchester
York Whitby 78
Carlisle Glasgow
Sheffield Lincoln
York Doncaster
Newcastle Edinburgh
Leeds Sheffield
Northampton Oxford
Manchester Carlisle
-71
130
145
116
139
64
140
126
83
61
135
-28
100
-30
129
172
116
154
61
56
50
74
55
177
53
68
20
2022-03-19