1


MCD4710 – Introduction to Algorithms and Programming
Assignment 1
Assignment 1 (8%) - Trimester 2 2021
Due: Thursday, July 29, 2021 at 11:55pm (week 6)
Objectives

The objectives of this assignment are:
? To demonstrate the ability to implement algorithms using basic data structures and operations on them.
? To gain experience in designing an algorithm for a given problem description and implementing that
algorithm in Python.
? To explain the computational problems and the challenges they pose as well as your chosen strategies
and programming techniques to address them.

Marking Criteria

This assignment contributes to 8% of your final mark.

? Task 1: Single Output Vertex (1 mark)
? Task 2: Output Layer (1 mark)
? Task 3: Inner Layers (1 mark)
? Task 4: Full Inference (2 marks)
? Task 5: Reading Weights and Biases (2 marks)
? Task 6: Reading the Image File (1 mark)
? Task 7: Output Selection (1 mark)
? Task 8: Number Prediction (1 mark)
? Decomposition: 1 mark
? Variable names and Code documentation: 2 marks

Total: 13 Marks
































2

Overview

Inspired from the human brain, artificial neural networks (ANNs) are a type of computer vision model to classify images
into certain categories. In particular, in this assignment we will consider ANNs for the task of recognising handwritten
digits (0 to 9) from black-and-white images with a resolution of 28x28 pixels. In this assignment, you will create
functions that compute an ANN output for a given input.


Figure 1: Visualization of the Artificial Neural Network (ANN) that will be used in this assignment. The ANN
visualized has four layers in total with 784 vertices in its first layer (i.e., one for each pixel, coloured in with pink), 10
vertices in its last layer (i.e., one for each digit, coloured in with blue), and 16 vertices in its remaining layers (i.e.,
coloured in with yellow). The red arrow visualize the layer-by-layer information flow through the ANN.

Figure 1 illustrates the general build-up of an ANN for this assignment. The network receives the 784 pixels of the
input image in the form of a list of pixel values where the two possible values are 0 for white and 1 for black. Then
it performs a computation by passing the data through several layers of neurons and finally producing a list of
outputs with 10 elements. These 10 elements contain a numerical score for each possible digit (0 to 9) that
correspond to how likely the network thinks that the input image shows the specific digit.
For instance, the image in Figure 2 would be fed to the network as the list:

[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,?
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,?
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,?
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,?
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,?
0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,1,1,0,0,?
0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,?
0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,?
0,0,0,0,1,1,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,1,1,1,0,?
0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,?
0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,?
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,?
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,?
0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,?
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,?
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,?
3

0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,?
0,0,0]?


Figure 2: Visualization of the image with a resolution of 28x28 pixels that is classified to be number 4 by the
ANN.


The output list could then be

[‐2.166686,?‐5.867823,?‐1.673018,?‐4.412667,?5.710625,?‐6.022383,?‐2.174282,?0.378930,?
‐2.267785,?3.912823]?

This list shows the score of each digit, and you can see that the network thinks that this image represent 4 as 4 has the highest
score (5.710625). Also, this result shows that 7 and 9 has some positive score, thus there is a chance that they might be the
number. However, they are less likely.

It must be noted that the vertices in the input and the output layers work a bit differently than the inner layers. Thus, let
us focus on those first. The vertices in the input layer are extremely simple: they just forward the value of a single
input pixel to all vertices of the subsequent layer.

Task 1: Single Output Vertex (1 mark)

The output vertices are a little more complicated: given an input vector x = (x0 , . . . , xd?1 ) of some dimension d, they
compute a linear function:
?? ? ?? ? ? ? ?????? ? ? ? ? (1) defined by a d-dimensional weight vector of w and a single number b called the bias. Note that we use the usual
notation w ? x to denote the dot product of w and x, i.e., the sum( w0 x0 + ? ? ? + wd?1 xd?1) . Write the function linear(x,?w,?b)?that can be used to compute the output of an individual vertex in the
output layer by adhering to the following specification:

Input: An input list (x), a weights list (w) and a bias float (b).

Output: A single number corresponding to the value of f(x) in Equation 1.

For instance, for layer 3, with an input vector x = (1.0, 3.5), weight vector w = (3.8, 1.5) and bias b = ?1.7, the
output of a single vertex (i.e., the output of vertex 4 in Figure 3) is computed as:

>>>?x?=?[1.0,?3.5]?
>>>?w?=?[3.8,?1.5]?
4

>>>?b?=?‐1.7?
>>>?linear(x,?w,?b)?
7.35?


Figure 3: Visualization of the example ANN that has three layers in total with 2 vertices in its first layer (i.e.,
coloured in with pink), 2 vertices in its last layer (i.e., coloured in with blue), and 2 vertices in inner layer (i.e.,
coloured in with yellow). The red arrow visualizes the layer-by-layer information flow through the ANN.

Task 2: Output Layer (1 mark)

Now to compute the combined output of the whole output layer that consists of vertices, we just have to compute
the joint output of many linear functions. That is, given the weight vectors ?, … , ??? , biases ?, … , ??? of the individual vertices and the input data x flowing in from the preceeding layer, the output of the output layer is described
by the function:
?? ? ?
? ? ? ??
??? ? ? ???
?
(2)

Write function linear_layer(x,?w,?b)?that can be used to compute the output of the whole output layer by
adhering to the following specification:

Input: An input l is t (x), a table of weights (w) and a list of biases (b).

Output: A list of numbers corresponding to the values of f(x) in Equation 2.

For instance, the following input vector x, weight table w, and biases b,
? ?1.0, 3.5?, ? ? 3.8, 1.5?1.2, 1.1? , ? ??1.7, 2.5?
the output of the whole output layer (i.e., the output of vertices 4 and 5 in the example ANN that is
visualized in Figure 3) is computed as:

>>>?x?=?[1.0,?3.5]?
>>>?w?=?[[3.8,?1.5],?[‐1.2,?1.1]]?
>>>?b?=?[‐1.7,?2.5]?
>>>?linear_layer(x,?w,?b)??
[7.35,?5.15]?

Task 3: Inner Layers (1 mark)

Next we need to compute the output of the vertices in the inner layers. Individually, the output of a single vertex
that is located in an inner layer is computed by the following piecewise linear function:
?? ? max ? ? ? , 0? (3)

5

for a given input vector x, weight vector w and bias b. Therefore, given the weight vectors ?, … , ??? , biases ?, … , ??? of the individual vertices and the input data x flowing in from the preceeding layer, the output of an inner layer is described by the function:

?? ? ?
max ?? ? ? ?, 0??
max ???? ? ? ???, 0?
?
(4)


Write function inner_layer(x,?w,?b)?that can be used to compute the output of an inner layer by adhering to
the following specification:

Input: An input list (x), a table of weights (w) and a list of biases (b).

Output: A list of numbers corresponding to the values of f (x) in Equation 4. For instance, the following input vector x, weight table w, and biases b,
? ?1, 0?, ? ?2.1, ?3.1?0.7, 4.1? , ? ??1.1, 4.2? the combined output of the whole inner layer (i.e., the output of vertices 2 and 3 in the example ANN that is visualized in Figure 3) is computed as:

>>>?x?=?[1,?0]?
>>>?w?=?[[2.1,?‐3.1],?[‐0.7,?4.1]]?
>>>?b?=?[‐1.1,?4.2]?
>>>?inner_layer(x,?w,?b)??
[1.0,?3.5]?

Task 4: Full Inference (2 marks)

Finally, we can put everything together to compute the output of the whole ANN (e.g., scores) given some input vector
(e.g., pixels). Specifically, the output of the ANN is computed layer-by-layer starting from the input layer, continuing
with the inner layer(s) and ending with the output layer. It is worth noting that the outputs of one layer is acting as inputs for
the next layer. Think about a way to ensure the correct transfer of data from one layer to the next.

Write function inference(x,?w,?b)?that can be used to compute the output of an ANN by adhering to the
following specification
Input: An inputs list (x), a list of tables of weights (w) and a table of biases (b).

Output: A list of numbers corresponding to output of the ANN.

The function inference?behaves as follows for the example ANN (i.e., visualized in Figure 4), with the weight
matrices, and biases table b,
? ??2.1, ?3.1?0.7, 4.1? , ?
3.8, 1.5
?1.2, 1.1?? , ?, ?
?1.1, 4.2
?1.7, 2.5? and input vector ? ?1, 0?

>>>?x?=?[1,?0]?
>>>?w?=?[[[2.1,?‐3.1],?[‐0.7,?4.1]],?[[3.8,?1.5],?[‐1.2,?1.1]]]?
>>>?b?=?[[‐1.1,?4.2],?[‐1.7,?2.5]]?
>>>?inference(x,w,b)?
[7.35,?5.15]?

Next, we will focus on implementing functions that read in and store data from text files.




6
Task 5: Reading Weights and Biases (2 marks)

The weights and biases of the ANN will be stored in a text file and must be read in and stored. For example, the
weights and biases of the example ANN that are visualized in Figure 3 will have the following format:

#w?
2.1,‐3.1?
‐0.7,4.1?
#b?
‐1.1,4.2?
#w?
3.8,1.5?
‐1.2,1.1?
#b?
‐1.7,2.5?

where the character #w?and?#b?are?used to separate the weights from the biases.
Write function read_weights_biases(filename)?that can be used to read in the weights and the biases of the
ANN by adhering to the following specification:

Input: A string (filename), that corresponds to the name of the file that contains the weights and biases of the ANN.

Output: A tuple w, b corresponding to the weights and biases of the ANN. For example,
>>>?w_example,?b_example?=?read_weights_biases(‘example_weights_biases.txt’)?
>>>?w_example?
[[[2.1,?‐3.1],?[‐0.7,?4.1]],?[[3.8,?1.5],?[‐1.2,?1.1]]]?
>>>?b_example?
[[‐1.1,?4.2],?[‐1.7,?2.5]]?
?
Task 6: Reading the Image File (1 mark)

The image in Figure 2 visualizes a black-and-white image of a handwritten digit using zeros for white pixels and
ones for black pixels over 28x28 pixels (i.e., 784 in total). Write function read_image(filename)?that can be used
to read in the image visualized by Figure 2 by adhering to the following specification:

Input: A string (filename),?that corresponds to the name of the file that contains the image.

Output: A list of numbers corresponding to input of the ANN. You need to read the 1’s and 0’s into a 1D list, ignoring
how they are stored in separate rows in the file.
The function read_image?behaves as follows:
>>>?x?=?read_image(‘image.txt’)?
>>>?len(x)?
784?
>>>?x?
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,?
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,?
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,?
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,?
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,?
0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,1,1,0,0,?
0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,?
0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,?
0,0,0,0,1,1,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,1,1,1,0,?
0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,?
0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,?
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,?
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,?
0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,?
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,?
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,?
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,?
0,0,0]?
?
7

Finally, we will solve the handwritten digit classification task.

Task 7: Output Selection (1 mark)

The computed scores by the ANN will be used to predict what number is represented in the image. Specifically,
given a vector of computed scores x = (x0 , . . . , xd?1 ) of some dimension d, the predicted number i will be the
index of score xi with the highest score. Write function argmax(x)?that can be used to return the index of an
element with the maximum value.

Input: A list of numbers (i.e., x) that can represent the scores computed by the ANN.

Output: A number representing the index of an element with the maximum value in the list x. If there are multiple
elements with the same maximum value, the function should return the minimum index (e.g., see the example below).

For example, argmax?behaves as follows for input list x:

>>>?x?=?[1.3,?‐1.52,?3.9,?0.1,?3.9]?
>>>?argmax(x)?
2?



Task 8: Number Prediction (1 mark)
Finally, write function predict_number(image_file_name,? weights_biases_file_name) that solves the
handwritten digit classification task.

Input: A string (i.e., image_file_name) that corresponds to the image file name, and a string (i.e.,
weights_biases_file_name) that corresponds to the weights and biases file name.

Output: The number predicted in the image by the ANN.

For example, predict number behaves as follows for file names ‘image.txt’, and ‘weights_biases.txt’:

>>>?i?=?predict_number(‘image.txt’,‘weights_biases.txt’)?
>>>?print(‘The?image?is?number?’?+?str(i))??
The?image?is?number?4?