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 on­the­go 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 two­way 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 tab­delimited “energy­v22­1” 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 tab­delimited 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 well­designed graph ADT that localizes information

•  Use a shortest path algorithm, such as Bellman­Ford 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