Object-Oriented Programming
and Its Applications
School of Mathematics
The University of Edinburgh
ASSIGNMENT 3
Newton’s Method
Task 3.1. Recall that Newton’s method can be used to obtain a zero of a function F : Rn !
Rn. The Newton iterations are given by,
where x0 2 Rn is the initial estimate and J(x) 2 Rn⇥n denotes the Jacobian matrix.
On the other hand, if F : Rn ! Rm, where m 6= n, then the Jacobian matrix J(x) is an
m ⇥n matrix, which implies that it is not invertible (recall that only square matrices can be
invertible). Therefore, Newton’s method is not applicable for finding a zero of F if m 6= n.
However, we can overcome this obstacle by approaching the same problem from a di↵erent
perspective. Suppose that F : Rn ! Rm, where m 6= n. We can think of F as a vector of m
real-valued functions, i.e.,
where fi : Rn ! R for each i = 1,...,m.
Therefore, F(x) = 0, where 0 2 Rm, if and only if fi(x) = 0 for each i = 1,...,m. Using
this observation, we can define a new function f : Rn ! R as follows:
(1) f(x) = Xm
i=1
(fi(x))2 .
Note that f(x)
0 for each x 2 Rn and f(x) = 0 if and only if fi(x) = 0 for each
i = 1,...,m. Therefore, in order to compute a zero of F : Rn ! Rm, we can try to solve
the following unconstrained optimization problem:
(2) min x2Rn (1/2)f(x),
where f is given by (1). The factor (1/2) is used to simplify the expressions for the gradient
and the Hessian matrix.
The gradient of f is given by
rf(x) = J(x)
TF(x), 1
and the Hessian of f is given by
r2
f(x) = J(x)
T J(x) +Xm
i=1
fi(x)r2
fi(x).
(1) (C#) The table below presents the population of the UK (in millions) between 1955
and 2015:
Year Period (t) Population (yt)
Suppose that you would like to establish a relation between t (period number) and
yt (population in millions). Below are three proposed relations:
(i) yt = x1ex2t
(ii) yt = x1
1 + x2ex3t
(iii) yt = x1 + x2t + x3t
2 + x4t
3
Using the given data, you need to find the best possible parameters (x1, x2 for model
(i); x1, x2, x3 for model (ii); x1, x2, x3, x4 for model (iii)). For each of the three models,
define appropriate functions and implement the suggested approach in C#.
(2) (On paper) Give a brief discussion of your solution approach and your choices of
initial solutions you used in the Newton’s method. Among the three proposed models,
discuss which one would be a better choice in terms of explaining the relation between
t and yt. In your discussion, pay attention to the behaviour of the proposed model
for large values of t. Justify your answer.
Clustering
Task 3.2. Given a collection of objects, clustering is concerned with organising objects in
a group in such a way that objects in the same group are “similar” to one another. Suppose
that we have n objects labelled 1, 2,...,n and dij denotes the distance between object i and
object j, where i = 1,...,n; j = 1,...,n. Then D = (dij ) 2 Rn⇥n is the distance matrix
of interest. Clearly, dii = 0 for each i = 1,...,n and the similarity between objects i and j
decreases as dij increases.
(1) (C#) Consider data points in Rd. Write a C# code for computing the following
distance measures that will map every pair of locations i, j 2 V observations, where
2
V = {1,...,n}, to a single distance measure. The output should be the n⇥n distance
matrix:
• Euclidean distance:
• Manhattan distance:
• Mahalanobis distance:
where S 2 Rd⇥d is the sample covariance matrix of the full dataset given by.
(2) (C#) Implement the following clustering algorithms:
• Greedy approach: Place every data point in a separate cluster. Then place
the two clusters with minimum distance in a new cluster. Calculate the mean
location of the new cluster. Find the two clusters with the minimum distance
between them and merge them again. Repeat until all data points are in one
cluster. Based on this approach you can prune the obtained clustering scheme on
di↵erent levels. Figure 1 illustrates a representation of a clustering realisation for
a dataset with 5 data points. Based on it, we can infer that the best clustering
consisting of 3 clusters, for example, is (A),(B),(C, D, E).
• Fixed number of clusters approach: For a prespecified number of clusters k,
pick randomly k points of the dataset as cluster centres. Assign each of the
remaining n
k points to the nearest cluster centre. Repeat until convergence
the following two steps. Firstly, calculate the new cluster centres for each cluster
by computing their mean. Then, remove all labels and re-assign each point to
the nearest cluster centre. Test all of the introduced methods on the two datasets
provided.
(3) (C#) Apply the two clustering methods for all distance measures across the two
datasets. The data is in files cluster2.csv and cluster4.csv. The first column in each
dataset is the index of the entry. The first dataset is two-dimensional while the latter
one is four-dimensional.
3
Figure 1. Clustering realisation
(4) (On paper) Report your findings. Allocate the appropriate number of clusters for
each dataset. Discuss the results for the proposed distance measures. Visualise your
findings with appropriate plots.
Large-Scale TSP
Task 3.3. Recall the TSP problem: We are given a set of n cities V = {1,...,n} and
pairwise distances dij for each i 2 V and j 2 V . We would like to compute a tour that visits
each city exactly once and returns to the starting city.
TSP is a hard problem to be solved to optimality. Therefore, heuristic approaches are
used to obtain good solutions. However, if the number of cities n is large, then even the
heuristic approaches can be computationally very expensive. One way to tackle a large-scale
TSP problem is as follows: Cluster the set of cities to form groups with smaller number of
cities. Solve the TSP problem in each cluster separately using a heuristic approach. Finally,
merge the resulting TSP tours to obtain a good TSP tour for the original TSP problem.
(1) (On paper) Consider a TSP instance with n cities in which (x1, y1),(x2, y2),...,(xn, yn)
denote the coordinates of the n cities. Describe a heuristic approach based on clustering,
computing a TSP tour for each cluster, and merging the resulting TSP tours
to obtain a TSP tour for the original TSP problem. Describe your procedures clearly,
specify the inputs and outputs, and remember to justify your procedures.
(2) (C#) Implement the procedure in part (1) and test your code on the two TSP instances
provided (tsp1.csv and tsp2.csv). They both consist of 200 datapoints in two
dimensions.
4
(3) (On paper) Give a brief discussion of your results for di↵erent inputs (i.e., number
of clusters, choice of the TSP heuristic, etc.) and compare your solutions with the
solution from the nearest neighbour heuristic on the original instance.
5
INSTRUCTIONS
Written Report. Your report should be typeset (preferably in LATEX). It should consist
of the following parts:
(1) A cover page with the names of the group members.
(2) A main body that includes the solutions of the written parts of each task.
(3) An appendix that includes your C# codes, figures, tables, plots, references, etc.
For each task, your report should include:
(1) A short section explaining how your code is structured and why it is done so. You
should explain how you avoid code duplication, how you ensure flexibility, etc.
(2) The choices of the parameters used in your experiments along with their justifications.
You may consider including tables and figures in the appendix.
(3) A discussion and interpretation of your results.
(4) Any other information related to your solution.
Your report should fulfill the following requirements:
(1) The main body should consist of a maximum of 5 pages with at least 10pt font and
at least 2 cm margins on each of the four sides.
(2) The appendix does not count towards the page limit. However, the appendix should
only contain the C# codes and any other supplementary material supporting the
content of the main body (e.g., tables, figures, plots, references, etc.). We expect you
to provide a single program with multiple classes and methods. Everything should
run from a single sln file in less than 5 minutes.
Steps.
(1) Check the list of the groups on Learn. (2 students per group)
(2) Download the data files on Learn (for Tasks 3.2 and 3.3).
(3) For submission, go to the Learn page and submit the assignment. There are two
parts to be submitted:
• The report in PDF format.
• A zip file that contains all of your C# codes, including all files required for your
code execution (e.g. tsp1.csv, libraries, code bases).
Deadline. The deadline is Friday, 29th of November at noon. Late submissions will follow
standard university policy. The project is considered submitted only once all two parts have
been submitted.
Contact. If you have any questions about the tasks,
If you have any problems submitting the assignment on Learn, please contact Skarleth
Carrales at Skarleth.Carrales@ed.ac.uk