Description
1. Prove that for all n ≥ 1 and 1 ≤ k < n:
n
k
+
n
k + 1
=
n + 1
k + 1
.
2. (a) How many well-formed formulas can be constructed from one ∨; one
∧; two parenthesis pairs (,); and the three literals p, ¬p, and q?
(b) Under the equivalence relation defined by logical equivalence, how
many equivalence classes do the formulas in part (a) form?
3. Suppose you are trying to negotiate a maze and you are stuck with a
number of choices:
• Option A takes you to the exit in 5 minutes,
• Option B returns you to your current position after 3 minutes,
• Option C takes you to the exit in 8 minutes, and
• Option D returns you to your current position after 2 minutes.
(a) Suppose you make your choice uniformly at random, and if you return
to your current position you are unable to recall any of your previous
choices, so you always choose from all four options. What is your
expected time for exiting the maze?
(b) Suppose now you can remember any choice which returned you to
your current position, and you choose uniformly at random from
your unexplored options. What is your expected time for exiting the
maze?
4. Consider the following graph:
v1 v2 v3 v4
Consider the following process:
• Initially, start at v1.
• At each time step, choose one of the vertices adjacent to your current
location uniformly at random, and move there.
Let p1(n), p2(n), p3(n), p4(n) be the probability your location after n time
steps is v1, v2, v3, or v4 respectively. So p1(0) = 1 and p2(0) = p3(0) =
p4(0) = 0.
1
(a) Express p1(n + 1), p2(n + 1), p3(n + 1), and p4(n + 1) in terms of
p1(n), p2(n), p3(n), and p4(n).
(b) As n gets larger, each pi(n) converges to a single value (called the
steady state) which can be determined by setting pi(n + 1) = pi(n)
in the above equations. Determine the steady state probabilities for
all vertices.
(c) What is your expected distance from v1 in the steady state?
Comment: This is an example of a Markov chain – a very useful model for stochastic processes. This particular Markov chain
is modelling a (bounded) 1-dimensional random walk, also a very
common model with applications in many scientific fields.
5. Consider the following graph:
(a) Suppose you colour each vertex one of three colours chosen uniformly
at random. What is the probability you get a valid 3-colouring of the
graph?
(b) Suppose you orient each edge (e.g. top to bottom, left to right)
and choose, for each oriented edge, one of six “colour pairs” (i.e.
(red, blue), (red, green), (green, blue), (blue,red), (green,red), or (blue, green))
uniformly at random.
Each colour pair indicates how you colour the
two vertices of the oriented edge – e.g. if (u, v) is given (green, blue)
then u is coloured green and v is coloured blue. Note that a vertex
may be given more than one colour, in which case the colouring is
not valid. What is the probability you get a valid 3-colouring using
this process?
2
Advice on how to do the assignment
All submitted work must be done individually without consulting someone else’s
solutions in accordance with the University’s “Academic Dishonesty and Plagiarism” policies.
• Assignments are to be submitted via WebCMS (or give) as a pdf
• Be careful with giving multiple or alternative answers. If you give multiple
answers, then we will give you marks only for ”your worst answer”, as this
indicates how well you understood the question.
• Some of the questions are very easy (with the help of the lecture notes or
book). You can use the material presented in the lecture or book (without
proving it). You do not need to write more than necessary (see comment
above).
• When giving answers to questions, we always would like you to prove/explain/motivate your answers.
• If you use further resources (books, scientific papers, the internet,…) to
formulate your answers, then add references to your sources.
3
