"Self test" for RC (are you prepared?)
Basic probability Questions
- Suppose that we have a fair dice and we carry out two
independent rolls of the dice, and sum the two values we
see. What is the probability this sum is 5?
Express the answer as a simple fraction.
- Consider a Bernoulli process where a coin is repeatedly flipped
until a 'head' is shown. Suppose the bias is 0.25 probability of
heads, and 0.75 of tails.
What is the expected number of flips before seeing
a 'head'? You may use the equality that the sum
of all i*ci terms from 1 to infinity is
c/(1-c)2.
- In the Monty Hall problem, we imagine the scenario where a
contestant is shown three curtains, exactly one having a
car behind it, and the other two each having a goat behind. The
curtains are large enough to hid car-or-goat, and well-soundproofed,
so you won't be able to guess what is behind. So this 1st choice
should be assumed to be a random choice.
The contestant chooses a curtain for their 1st choice, and in
response the TV host will open one of the other curtains.
The contestant then has the choice of sticking with her 1st choice,
or changing to the unopened curtain (we assume the host has not shown
the contestant the car, that would make things too easy!)
Should the contestant switch to the unopened curtain, or
stick with the 1st choice? Will it make a difference to the chance
of winning the car? Explain why.
- Consider a simple random variable X which takes on
positive integers. Let μ be the expected value E[X].
Prove/argue that for any positive value c, that
Pr[X ≥ c] ≤ μ/c.
Simple algorithmic thinking
- Imagine we are given a positive integer written in
decimal, and asked whether it can be divided by 4? For this
task we will not assume that the arithmetic operations are
atomic; instead we will count 1-step whenever we check
(or change) a single digit of a number.
Is there an O(1) algorithm to check whether the input is evenly
divisible by 4, or does
this problem require time increasing with the length of the
number?
- Which of the following sorting algorithms has the lowest
asymptotic worst-case running time (on arrays of length n):
QuickSort or MergeSort? What is that asymptotic
worst-case running-time?
- What is the best-case running time of MergeSort?
- Imagine we have an algorithm with running time T(n) on
inputs of length n, and that for all except a few small values
of n, the following recurrence holds:
T(n) = 3.T(n/3) + 2n
What is the asymptotic running-time of the algorithm? (and why!)
Logarithms and their application
What are the O(.) and Ω(.) relationships between
the following two pairs of expressions:
- 2n and 2n/2?
- lg(n!) and lg(nn)?
- Suppose we are given a positive integer in decimal
format (digits 0, ..., 9) of representation length L
(so L digits) and we want to recompute it in binary representation.
Specify the (approximate) increase in length, giving a reason?
Graphs and structures
In what follows below, we assume that we are working with
an undirected graph G=(V, E) where V is the set of n vertices,
and E is a set of undirected edges of the graph.
- What does it mean to say that an (undirected) graph is connected?
Give the definition.
- What is the definition of a clique of a graph?
- An Euler tour of G is defined to be an ordering
of all the edges in E such that for every pair of edges e=(u,v) and
f=(u', v') with f immediately following e in the ordering,
the second endpoint of e must be the same vertex as the
first endpoint of f (ie, v = u').
Explain/prove that if an undirected graph G has an Euler tour
(it may have many in fact), then every vertex of G has even degree.
Proving things
Our main "tool" in RC will be direct proof, and we will need
you to be comfortable with proof by induction (including "general
induction" and not simply n -> n+1), proof by contradiction, etc.
- There are infinitely many prime numbers.
Give a proof of this statement, using proof by contradiction.
Mary Cryan, mcryan AT inf DOT ed DOT ac DOT uk,
Informatics Forum 5.18, ext. 505153
