Programming
Continuous Assessment 2
This continuous assessment (CA) comprises 25% of the overall module assessment.
This is an individual exercise and your attention is drawn to the College and University guidelines
on collaboration and plagiarism, which are available from the College website.
Note that both paper (BART) and electronic submissions are required.
This CA tests your knowledge of the programming in Python that we have covered so far. You
may not be able to do all of the exercises initially, but we will cover the necessary material over
the next weeks.
Make sure that you lay your code out so that it is readable and you comment the code appropriately.
Exercises
1 Logistic maps
The logistic map (1) has been created to model growth and death rates of species. It is a fully
deterministic map that depends on a single scalar parameter. If you are interested in knowing
more about the logistic map and its use in various applied sciences, please take a look here:
https://en.wikipedia.org/wiki/Logistic map.
Further studies highlighted the surprising behaviour of the map for specific configurations of its
control parameter. In particular, the series of real values generated with such map can vary from
a perfectly period behaviour (i.e., a series of numbers with very regular behaviour) to a chaotic
series, that is, a series with very disordered, apparently random behaviour. In formulas, the logistic
map reads:
yt+1 = pyt(1 − yt); (1)
where yt 2 [0; 1]; t = 0; 1; : : : ; T, being T > 0 the number of steps, and p is a positive, real-valued
parameter, whose range is limited to the (0; 4] interval (please note that 0 is excluded).
Write a Python program that implements the logistic map (1). Your code should contain a function
called logistic map(initial condition, steps=100, p=3.0) that returns a series and then do
the following:
1. Iterate the map for a given number of times T > 0 by using each of the following parametrizations: p 2 f3:0; 3:4; 3:6785; 3:84; 4g. For each
parametrization, initialize the map with a
random, uniformly distributed number in the unit interval, i.e., y0 2 [0; 1].
2. Plot the obtained series in a nice graph to visualize the differences of the generated series
with respect to the parametrizations taken into account.
HINT: Very nice plotting functionalities are available by importing import matplotlib.pyplot
as plt. You might need to install matplotlib. Please consult the online documentation to findECM1400 Programming Continuous Assessment 2
out how to plot a series of numbers (https://matplotlib.org/users/pyplot tutorial.html) or
take a look at what has been done during the workshops.
Your program should be in a file called logisticmap.py. You should submit:
• A copy of your logisticmap.py program (electronic submission).
• Hardcopy of your logisticmap.py program (paper submission, via BART).
• Hardcopy of the output of your logisticmap.py program and screen shots of the five related
trajectories (paper via BART).
[20 marks]
2 Horizontal visibility graph
A graph is typically described as a pair of vertices (also called nodes) and edges (also called links)
{ see Figure 1 for an example.
Figure 1: A sample graph with five vertices numbered from 0 to 5 and five (undirected) edges
describing their connections.
A graph can be described by a binary, square matrix called adjacency matrix, which we will denote
as A. If the graph possesses n vertices, then A is an n × n binary matrix (note that binary means
that A contains only of 0s and 1s). The adjacency matrix associated to the graph shown in Figure
1 is:
A =
266664
0 0 1 0 1
0 0 1 0 1
1 1 0 0 0
0 0 0 0 1
1 1 0 1 0
377775
(2)
Rows and columns are one-to-one mapped with the vertex identifiers. In our example above, the
first row/column is associated vertex with id 0; the second row/column with the vertex with id 1
and so on. Considering the first row, we notice that there is a 1 at the third and fifth columns of A,
indicating that vertex with id 0 is connected to vertices with id 2 and 4 (as in fact is shown in Figure
1). Each matrix element can be identified by using two indices, say i and j, indexing the rows and
columns of A, respectively. For instance, A[i; j] with i = 0 and j = 4 refers to element located in the
first row and fifth column, that is, 1 in our example above; on the other hand, when i = 1 and j = 3
we are pointing to 0. It is should be easy for you to recognize that such a matrix is symmetric”,
that is, if vertex 0 is connected with 2, then vertex 2 is also connected to 0. If you want to know more
about graphs, please read: https://en.wikipedia.org/wiki/Graph (discrete mathematics)
2ECM1400 Programming Continuous Assessment 2
Figure 2: A sample horizontal visibility graph with 10 vertices corresponding to the 10 numbers
composing the series. Edges connecting the vertices are shown as horizontal black lines with arrows.
A horizontal visibility graph (HVG) is a special type of graph that is used to describe series of
numbers (also called time series in many scientific disciplines). An HVG is associated with a finite
univariate series x = (xt)T t=1 of length T > 0, and is constructed by assigning a vertex/node vt to
each datum xt; t = 1; 2; : : : ; T , in the series. Its adjacency matrix A is computed according to the
following simple rule: two vertices vi and vj, i 6= j are connected by an edge (A[i; j] = 1) if and
only if the corresponding data satisfy
xi; xj > xp; for all i < p < j: (3)
A visual illustration of the above rule in shown in Figure 2, where a series of ten real-valued numbers
in [0; 1] is mapped to its corresponding HVG. Please notice that two adjacent elements on the series
are always assumed to be connected (e.g., the first one is always connected to the second one, the
second one to the third one and so on; see the example in Figure 2). Here, in order to improve
visualization and understanding of the rule, data points (i.e., the vertices of the horizontal visibility
graph) are visualized as vertical bars in red and their edges are shown as horizontal black lines.
A weighted HVG (wHVG) is a regular HVG that instead of having binary edge values, it contains
real values defined as follows:
A[i; j] = 1=q(j − i)2 + (xi − xj)2 2 [0; 1]: (4)
Since self-loops (i.e., edges connecting a vertices with itself) are forbidden in HVGs, edge weights
are always well-defined in Eq. 4. The use of weights permits to capture additional information, as
it accounts for distance along the sequence (j − i) and amplitude differences (xi − xj) of two data
points connected by the visibility rule (3).
Write a Python program implementing what follows:
1. Generate three series of numbers: (1) a monotonically increasing series, (2) an alternating
series, and (3) a sinusoid. For this task, write a function get series(n, stype=0) that takes
two arguments, the first specifying the length of the series and the second one identified the
3ECM1400 Programming Continuous Assessment 2
type of function to generate. The function should return the generated series. A monotonically increasing series of length four is, for
instance, 0, 1, 2, 3. A valid alternating series of
length seven can be defined as follows 1, 0, 1, 0, 1, 0, 1. Finally, a sinusoidal series yt should
be generated according to the following equation:
yt = sin(2π · f · xt=fs);
where sin(·) is the built-in sine function, f specifies the frequency of the sinusoid (in Hertz,
may be float), fs specifies the sampling rate (must be integer), · indicates standard multiplication operation between numbers, and finally, xt
is an integer value going from x0 = 0 to
xT −1 = T − 1 with unitary increments (T as usual denotes the desired length of the series).
In your program, use f = 500 and fs = 10000.
2. Compute horizontal visibility graphs associated to such functions. To this end, write a function horizontal visibility graph(series,
weighted=False) that takes as input a series
of real-valued numbers and returns the adjacency matrix associated to the HVG computed
according to (3). DO NOT use any scientific library for manipulating vectors and matrices,
such as numpy; use only built-in functionalities for constructing adjacency matrices.
HINT: Take a look at the way a list of lists works: it can easily used to implement a (square)
matrix.
3. Print the horizontal visibility graphs associated with the three series on the console as square
matrices. To this end, write a function print hvg(hvg) that takes an adjacency matrix and
prints out each row of the matrix to the console, printing either a space if an element of row is
0, else printing its value. Please, compute and print the weighted edges (weighted adjacency
matrix) only in the alternating function case.
4. Instantiate the logistic map (1) with the previous parametrizations (i.e., f3:0; 3:4; 3:6785; 3:84; 4g)
and construct related horizontal visibility graphs. Create a dictionary associating logistic
map parametrizations and related horizontal visibility graphs. To this end, write a function process logisticmap(params, steps=100) that returns
a dictionary containing the
aforementioned key/value pairs.
5. In the main of your program, print the key/value pairs in the dictionary by showing the
horizontal visibility graph (without weights) associated to each parametrization of the logistic
map.
Your program should be in a file called hvg.py. You should submit:
• A copy of your hvg.py program (electronic submission).
• Hardcopy of your hvg.py program (paper submission, via BART).
• Hardcopy of the output of your hvg.py program (paper via BART).
[40 marks]
3 Random walks on graphs
Let G be a graph with n vertices. As before, let us denote with A its adjacency matrix, encoding
the links (i.e., the edges) between the vertices of G. A walk in G is a sequence of vertices. For
instance, considering the graph shown in Figure 1, a possible walk of length four is (0; 2; 1; 4; 0)
as the graph G contains those four edges: f0; 2g; f2; 1g; f1; 4g; f4; 0g, allowing to perform the four
steps of the walk. This can be easily verified by visually inspecting the figure or by looking at the
4ECM1400 Programming Continuous Assessment 2
configuration of the 1s in the corresponding adjacency matrix (2). Please notice that (i) as before
vertex identifiers start from 0 and (ii) a walk does not need to start and end at the same vertex as
in the previous example (that’s actually called a cycle).
A random walk in G is walk where the transitions between two vertices are non-deterministic, that
is, they are governed by a probabilistic rule that can be fully inferred from the adjacency matrix.
Such rules of transition between vertices are encoded in another matrix, called transition matrix
T. Following the same example in Figure 1, the transition matrix of the sample graph G is:
T =
266664
0 0 0:5 0 0:5
0 0 0:5 0 0:5
0:5 0:5 0 0 0
0 0 0 0 1:0
0:33 0:33 0 0:33 0
377775
(5)
The transition matrix shown in (5) is easy to interpret. For instance, assuming we start from vertex
0 (corresponding to the first row of T), we have equal chances to moving to either vertex 2 or 4.
Said in other terms, there is a probability equal to 0.5 to transition to vertex 2 and 0.5 toward
vertex 4. The same holds for vertex 1; in fact, first and second rows are equal. On the other hand,
assuming we are in vertex 3, we are forced to deterministically move (i.e., move with probability 1)
toward vertex 4. Please notice that, differently from A in Eq. 2, transition matrices are not always
symmetric!
Each component Tij of the transition matrix (5) can be easily computed as follows:
Tij =
Aij
di ; (6)
where Aij is the related component in the adjacency matrix and di = Pn j=0 −1 Aij is called degree of
the ith vertex. In other terms, the degree of vertex i is given by the number of edges connected to
vertex i.
Now we know how to move around the graph by using the transition matrix. A reasonable question
would be where should we start our random walk?” The answer to such a question is given by
the so-called initial vertex distribution. The initial vertex distribution of a graph with n vertices is
a vector p of n components that encodes the a-priori probability of being in each vertex. Said in
other terms, the first component of p, denoted as p0 or p[0] in Python, contains the probability of
starting our random walk from vertex 0; the second component contains the probability of starting
from vertex with id 1 and so on. Something you should keep in mind is that, being p a distribution
over the vertices, the sum of its components should be 1; take it for granted for now, you will go
back to these things later on, probably during your second/third academic year as undergrad. How
do we compute p? The initial vertex distribution can be easily computed as follows:
pi =
di
Pn j=0 −1 dj : (7)
Everything we said so far is useful to perform the so-called unbiased random walks on graphs, which
is the standard” way to perform random walks. However, it is possible to bias the transitions
toward vertices having a high/low number of incident edges, i.e., with high/low degree. This can
be achieved by means of the so-called biased random walks. The underlying idea remains exactly
5ECM1400 Programming Continuous Assessment 2
the same. We just need to change the way we compute the transition matrix (6) and the initial
vertex distribution (7). Notably, in the biased random walks case, (6) is updated as follows:
Tij =
Aijdα j
Pn k=0 −1 Aikdα k ; (8)
where α is a parameter: when α > 0 we prefer vertices having a large number of edges; whereas
α < 0 indicates preference toward vertices with a low number of edges. When α = 0, it is easy to
understand that (8) becomes equal to (6). Please notice that the notation dα l indicates: the value
dl raised to the power of α. Finally, in the biased random walks case, (7) is updated as follows:
pi =
cidα i
Pn k=0 −1 ckdα k ; (9)
ci =
n−1
X j
=0
Aijdα j : (10)
Write a Python program implementing the following functionalities:
1. Define a function called get graph from series(length=25) that generates a numeric series
of length 25 from the logistic map with 0.1 as initial condition and its controlling parameter
set to 4. Such a function should then compute the horizontal visibility graph associated to
such a series and return its adjacency matrix.
2. Define a function called random walk(adj matrix, steps=1000, biased=False, alpha=1.0)
that allows to perform both standard and biased random walks on graphs encoded in the adjacency matrix passed as argument. Your function should
return a list of visited vertices
(i.e., their numeric identifiers). Perform both unbiased and biased random walks of 200 steps;
α = 5 as bias parameter on the adjacency matrix obtained in Question 3.1.
HINT: Here, you should probably use the choose vertex(probability) downloaded from
the module website. However, please feel free to re-implement the function from scratch if
you prefer.
3. Define a function called print triplets(visited vertices, k=20) that takes a list of visited vertices and prints triplets of them, limiting
this to the first k if there are more than k
to print. For instance, if visited vertices are 0, 1, 2, 3, then your function should print [0,
1, 2], [1, 2, 3]. Print the first 20 triplets from the biased and unbiased random walks
carried out in Question 3.2.
4. Write a function called verify equality(adj matrix) that performs a routine check (i.e., a
sort of debugging). In particular, it should evaluate whether the code you wrote for computing
a biased transition matrix produces a standard, i.e., unbiased transition matrix when α = 0.
5. Write a function that prints histograms of vertex degrees of the generated graph. So, for
example if we assume the following sample adjacency matrix, we would obtain:
>>> a = [[0 , 1, 1], [1, 0, 0], [1, 0, 0]]
>>> print_degree_histogram (a)
Vertex ID 0: **
Vertex ID 1: *
Vertex ID 2: *
Apply this function to the adjacency matrix generated in Question 3.1.
6ECM1400 Programming Continuous Assessment 2
6. Write a function count vertex occurrence(visited vertices) that counts the occurrences
of vertices in a random walk. Such a function should use a dictionary to store only the
occurrences of vertices visited during the random walks. Print the resulting vertex occurrences
for both the biased and unbiased random walks carried out in Question 3.2 and observe the
differences! In the biased case, vertices having high degree should occur much more than in
the unbiased case.
The main of you program should test all such functionalities and produce outputs accordingly.
Your program should be in a file called rw.py. You should submit:
• A copy of your rw.py program (electronic submission).
• Hardcopy of your rw.py program (paper submission, via BART).
• Hardcopy of the output of your rw.py program, (paper via BART).
[40 marks]
[Total 100 marks]
Submitting your work
The CA requires both paper and electronic submissions.
Paper You should submit paper copies of the code and any output for all the other questions to the
Harrison Student Services Office by the deadline of 12:00 Wednesday 15th November,
2017. Markers will not be able to give feedback if you do not submit hardcopies of your code
and marks will be deducted if you fail to do so.
Paper submissions should have the BART cover sheet securely attached to the front and
should be anonymous (that is, the marker should not be able to tell you are from the submission). If this is the first time you have used BART,
please make sure that you understand the
procedure beforehand and leave plenty of time as there are often queues close to the deadline.
Where you are asked for paper copies of the output of your code, please copy and paste the
output from the terminal rather than taking a screenshot, because the screenshot is often
illegible after printing. To cut and paste from a Windows Command window, highlight the
text you want to paste, right click in the Command window, click on Select all”, press Enter,
and past into your document (control-V or from the menu).
Electronic You should submit the files containing the code for each question via the electronic
submission system at http://empslocal.ex.ac.uk/submit/. You should use the category
2017~11~15~ECM1400~LorenzoLivi~CA2. Make sure that your code is in files with the names
specified in the questions. Use zip or rar or tar to compress these into a single file, and
upload this file using the submit system. You must do this by the deadline.
You will be sent an email by the submit system asking you to confirm your submission by
following a link. Your submission is not confirmed until you do this. It is best to do it
straightaway, but there is a few hours leeway after the deadline has passed. It is possible to
unsubmit and resubmit electronic coursework | follow the instructions on the submission
website.
7ECM1400 Programming Continuous Assessment 2
Marking criteria
Work will be marked against the following criteria. Although it varies a bit from question to
question the criteria all have approximately equal weight.
• Does your algorithm correctly solve the problem?
In most of these exercises the algorithm has been described in the question, but not always
in complete detail and some decisions are left to you.
• Does the code correctly implement the algorithm?
Have you written correct code?
• Is the code syntactically correct?
Is your program a legal Python program regardless of whether it implements the algorithm?
• Is the code beautiful or ugly?
Is the implementation clear and efficient or is it unclear and inefficient? Is the code well
structured? Have you made good use of functions?
• Is the code well laid out and commented?
Is there a comment describing what the code does? Are the comments describing the major
portions of the code or particularly tricky bits? Do functions have a docstring? Although
Python insists that you use indentation to show the structure of your code, have you used
space to make the code clear to human readers?
There are 10% penalties for:
• Not submitting hardcopies of your programs.
• Not naming files as instructed in the questions.
8
