MACM 203 Assignment 5
Spring 2022
This assignment is due Tuesday March 1st at 10pm. Upload your solutions to Crowdmark.
Write your solutions as a single Matlab Live Script and export the script to PDF. Write
the course number and assignment number as the title of the Matlab Live Script, followed
by the table of contents, and then create a section for each part of the question.
Keep in mind that your assignment, including the source code, is a document that will
be read in order to be marked. It has to be very clear and properly formatted.
Your Matlab code must be general enough to solve any other instance of the same problem
without modification. That is, if you are asked to run your code on some data that are
specified in the assignment, then your code must run on any similar data set (or solve
any similar problem) without modification.
Assignments should be written individually. You can discuss in groups, but you have to
write your assignment yourself. In case of plagiarism SFU policies will be applied.
Preamble
This week’s assignment focuses on dynamical systems.
Question 1 (20 marks)
Part (a)
A mouse lives in a house consisting of r rooms that are numbered 1, 2, . . . , r. Some pairs
of rooms are connected by doors. There may be more than one door connecting any pair
of rooms. Given is an r× r matrix D such that D(i, j) is the number of doors connecting
rooms i and j. Each door can be passed in both directions, hence D is a symmetric matrix
with zeros on the main diagonal. (Connections between rooms can have other forms, such
as air pipes etc., for simplicity we call all connections just “doors.”)
Every morning, the mouse chooses uniformly at random one of the doors leading out
of the room in which it currently is, then it passes through that door to an adjacent room,
and it stays there for the rest of the day. You can assume that each room has at least one
door.
Write a MATLAB function Mar that accepts on input the matrix D and it returns the
column stochastic matrix that describes the dynamical system outlined above (that is, the
matrix of the corresponding Markov chain). Your code should be as simple as possible.
1
Part (b)
Write a MATLAB function ThreeDays that accepts on input the matrix D and the number
of the room in which the mouse is today, and it returns the probabilities with which the
mouse will be in any of the r rooms in three days from now (that is, after three transitions).
Part (c)
Write a MATLAB function LongTime that accepts on input the matrix D and it returns
the probabilities with which the mouse will be in any of the r rooms after a long time.
(You can also think of these as fractions of time spent in each room.) You can assume
that it is possible to move from each room to each other room eventually. A calculation
similar to part (b) is not acceptable.
Functions ThreeDays and LongTime will call the function Mar, and these functions
should return a column vector of numbers.
Part (d)
Download the data file a5.mat from Canvas. Suppose that the matrix D in this file has
the meaning as given above, and suppose that the mouse is in room 4 today. Use your
function ThreeDays to compute the probabilities with which the mouse will be in any
of the rooms in three days from now. Then use your function LongTime to compute the
fractions of time that the mouse spends in each room in the long term.
Part (e)
Consider the Google PageRank algorithm as described on pages 10 and 11 in the class
notes. The web consists of pages numbered 1, 2, . . . , N and it is described by N × N
matrix G such that G(j, i) = 1 if there exists a link from page i to page j, and G(j, i) = 0
otherwise.
Assuming that following each link from a given page is equally likely, consider the
corresponding matrix A of transition probabilities as decsribed in the notes, and consider
the model with damping factor p (page 11 of the notes).
In the downloaded file a5.mat you will find a matrix G. Assuming that p = 0.2,
determine the fraction of time that the web browser will spend on each page in the long
term. Determine which page is visited most frequently, and which page is visited least
frequently, and the fractions of time spent on these two pages. Use the appropriate way
of calling the functions max and min.
2