Numerical and statistical methods – Route finding

Order Details;

© Alex Hagen-Zanker, University of Surrey
ENG2106 ENG2106 ENG2106 ENG2106 ENG2106 ENG2106 ENG2106 ENG2106 – CourseworkCourseworkCourseworkCourseworkCourseworkCourseworkCourseworkCourseworkCourseworkCoursework briefbriefbriefbriefbrief
Numerical and statistical methods
This coursework for ENG2106 consists of three exercises where you need to apply numerical methods in MATLAB. The purpose of this coursework is to develop and demonstrate your independence in the use of numerical methods. You will need to do your own research into the methods to use and write your own implementation in MATLAB.
The methods that you will apply for this coursework have not been covered in the lectures or lecture notes. You will not be tested on these new methods in the final exam paper.
This coursework is done in groups of four students. Please form groups and submit the list of four group members as well as a name for your group by email by Friday 13 March, 1pm. Anybody not in a group by that time will be allocated to a group automatically and the formed groups will be announced on 16 March.
The report should include all MATLAB code used. The coursework should be submitted as a single pdf-file through the Assignment folder on SurreyLearn. The deadline for the submission is Tuesday 5 May 2014, 4pm. Beware, even though these questions are short, they do entail a substantial amount of work each and require planning.
The coursework will be marked on the demonstrated understanding of methods and correctness of results (60%), as well as the quality of the MATLAB code (25%) and the presentation of the report (15%).
Conciseness in explanation and presentation is important, and the whole report may not take more than 12 pages.
Understanding of methods is demonstrated by:
– Crisp and correct language when discussing mathematical concepts.
– Correct and consistent use of equations and terms.
– Consistency between described methods, associated equations and implementation in MATLAB.
– Correct solution to problems and verification of results.
Quality of MATLAB code is demonstrated by:
– Correctness, readability and conciseness of the code.
– The appropriate use of comments
– The use of MATLAB techniques introduced in the lecture notes and tutorials. In particular these are the use of scripts and functions, function functions and anonymous functions.
– Where appropriate it is preferred to develop generic and reusable solutions on the basis of user-defined functions. See also Section 8 of the Introduction to MATLAB lecture notes
ENG2106 – Coursework brief
2
The presentation of the report will be expected to be professional, which entails the following:
– Title page including names and URN’s of the group members
– Consistent numbering of sections, pages, equations, tables and figures.
– Consistent use of styles (fonts and sizes) for headers and body text.
– Well-formatted and appropriately sized figure and tables
– All figure axes labelled. A descriptive caption for each table and figure.
– Well-formatted and numbered equations
– Correct and to the point language
– Inclusion of a reference section and correct use of references and citations
The style and formatting must be consistent over the whole report and not vary per question.
Plagiarism and attribution
All work must be done within your group. The usual rules for plagiarism, citation and attribution apply and also extend to the use of MATLAB code. If you are at some point inspired by code from an external source, this must be clearly indicated and justified in the written report. Any failure to do so will be referred to the Department’s Academic Integrity Committee. Avoiding plagiarism should be common sense, if in doubt consult the learning materials in the Student Common Room section on SurreyLearn.
Any externally inspired code must be fully adapted to the standards and techniques used and recommended in the module. In other words, you have to make it your own. Any failure to do so will result in the lowest possible marks for Understanding of Methods and Quality of MATLAB Code.
This means, for instance, that the MATLAB input and feval functions should not be used. Functions should not be passed as string literals; e.g., ezplot(‘sin(x)’) is not an acceptable alternative for ezplot(@sin).
Good luck & enjoy!
ENG2106 – Coursework brief
3
1 Ordinary Differential Equations (25 points)
This exercise will ask you to use a variation of the Runge-Kutta method called the Midpoint Method.
Consider the following differential equation:
2
2 4 13 0
d y dy
y
dx dx
  
with y 0  2and y0 1.
1a) Verify that   2 2cos3 sin3 x y  e x  x is the analytical solution to this problem.
1b) Rewrite the given second-order ODE as a system of coupled first-order ODE.
1c) Present the MATLAB code for a generic function function for the Midpoint Method. You may use
the given solution for the tutorial of week 4 as a starting point. Further, present the MATLAB code
of a script that applies your Midpoint Method to solve for the domain [0, π] in respectively 4, 8, 16
and 64 steps.
1d) Plot the results, along with the analytical solution and explain the differences between the
solutions briefly.
2 Root finding (35 points)
This exercise will ask you to use the modified secant method to find the all roots of the following
functions:
2 0.3 0.2
1
( ) sin(3 ) 2 2
1
( ) 10 x
f x x x
x
g x x e 
   

 
Note that the method will only give a single root for given initial conditions. You will therefore need
to apply it several times with different parameters to find all solutions.
2a) Plot the functions and identify the approximate value of x for each root. Discuss what difficulties
you would expect to encounter when searching for roots using the above method, as well as your
strategy for dealing with these difficulties.
2b) Explain the procedure that you will follow to find the roots to an absolute precision of 10-4.
Explain any estimates and assumptions you are making.
2c) Present the MATLAB code to solve the problem for the root values. The code must at least
consist of two M-files: one containing the user defined function of the modified secant method and
one consisting of the script applying the function to find the roots.
2d) Give the roots and discuss whether you are confident that all roots have been found. How many
iterations were necessary to find each of the roots?
ENG2106 – Coursework brief
4
3 Route finding (40 points)
This exercise will ask you to use the Bellman-Ford algorithm to find the shortest path over a road network.
The input to the problem consists of two csv files that are on the ENG2106 page of SurreyLearn.
The first file called nodes.csv contains node coordinates in the following described in table 1. Nodes are the begin- and end-points of road segments.
Table 1. Structure of nodes table in nodes.csv file.
Node
X
Y
1
x1
y1
2
x2
y2
3
x3
y3



m
xm
ym
The second file called edges.csv contains link specifications in the following format. Each edge is a road segment that can be travelled over in both directions. A and B are the nodes at either end of the segment.
Table 2. Structure of edges table in edges.csv file.
Edge
A
B
1
a1
b1
2
a2
b2
3
a3
b3



n
an
bn
3a) Present the code that used MATLAB’s function csvread to read both files. Create separate vectors for x, y, A and B. Calculate the length of each edge and store it in a vector w.
3b) Present MATLAB code to plot the whole network. It will look best if you plot the edges as thick white lines on a black background.
3c) Introduce the Bellman-Ford algorithm briefly and explain it in terms of the vectors created in 3a). Do you need to introduce any further vectors and matrices? How do you name them, and what information do they contain?
3d) Use the Bellman-Ford algorithm to calculate the distance from node 1 to all other nodes. Plot the road segments on the route from node 1 to node 263 with a separate color and line thickness.
3e) Use the Bellman-Ford algorithm to find out which two nodes in the network are the furthest removed from each other. Plot the network once more and mark the shortest route between these nodes.