- 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*c^{i}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.

- 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!)

What are the O(.) and Ω(.) relationships between the following two pairs of expressions:

- 2
^{n}and 2^{n/2}? - lg(n!) and lg(n
^{n})? - 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?

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.

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

Informatics Forum, 10 Crichton Street, Edinburgh, EH8 9AB, Scotland, UK
Tel: +44 131 651 5661, Fax: +44 131 651 1426, E-mail: school-office@inf.ed.ac.uk Please contact our webadmin with any comments or corrections. Logging and Cookies Unless explicitly stated otherwise, all material is copyright © The University of Edinburgh |