共计 5737 个字符，预计需要花费 15 分钟才能阅读完成。
Department of Electronic Engineering
ELE00028I Algorithms & Numerical Methods
Coursework Assessment 2020/21
SUMMARY DETAILS
This coursework (Programming Assignment) contributes 50% of the assessment for this
module.
Clearly indicate your Exam Number on every separate piece of work submitted.
Submission is via the VLE module submission point. The deadline is 12:00 on 20/4/2021,
Summer Term, Week 1, Tuesday. Please try and submit early as any late submissions will
be penalised. Assessment information including on late penalties is given in the Statement
of Assessment.
ACADEMIC INTEGRITY
It is your responsibility to ensure that you understand and comply with the University’s
policy on academic integrity. If this is your first year of study at the University then you also
need to complete the mandatory Academic Integrity Tutorial. Further information is
available at http://www.york.ac.uk/integri…
In particular please note:
● Unless the coursework specifies a group submission, you should assume that all
submissions are individual and should therefore be your own work.
● All assessment submissions are subject to the Department’s policy on plagiarism
and, wherever possible, will be checked by the Department using Turnitin software.
Department of Electronic Engineering, University of York
ELE00028I: Algorithms and Numerical Methods
Coursework Assessment 2020/2021
Assignment. Due Tuesday 20th April 2021, 12:00 noon
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”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
https://wiki.york.ac.uk/displ…
- 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:
Leicester Perth
Hull Bristol
Northampton Carlisle
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
compiler. 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: - A PDF report (no more than 6 A4 pages in length).
- 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. Also 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“myprogram 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.
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