"Self test" for RC (are you prepared?)

Basic probability Questions

  1. 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.

  2. 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.

  3. 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.

  4. 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

  1. 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?

  2. 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?

  3. What is the best-case running time of MergeSort?

  4. 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:

  1. 2n and 2n/2?
  2. lg(n!) and lg(nn)?

  3. 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.

  1. What does it mean to say that an (undirected) graph is connected? Give the definition.

  2. What is the definition of a clique of a graph?

  3. 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.

  1. 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