Please solve the quiz below submit it in class on Jan 7, otherwise you
cannot register for the course.  You are expected to work alone.  You
may consult books for general help; if you find the solution directly,
please write that on your submission.

The marks you obtain on the quiz will not count towards the final
grade.  The quiz is meant to help you decide whether you should be
taking the course, whether you are likely to find it attractive, and
also how hard you will need to work in order to do well in the course.
But whether to take the course is your decision entirely.

Note that this course is not compulsory, and it is likely to be
difficult (see the homeworks/tests/notes of last year's offering to
get some idea).  You will be expected to work regularly on homeworks.
Attendance, while not compulsory, is strongly recommended, because
there is no clear textbook.  Notes will be put up, but this cannot be
guaranteed, and it is your responsibility to keep up with what is
covered in class by attending and/or asking fellow students.  You are
also strongly encouraged to talk to me during office hours for solving
doubts.

-------------

1.  Consider the statements (1) "If f(i) >= f(j) then q(i) >= q(j)",
    and (2) "If q(i) < q(j) then f(i) <= f(j)".  Relate these
    statements, i.e. state if they are equivalent, or if one implies
    the other etc, or if they are unrelated.  Be sure that you would
    be able to solve this problem if one of the >= was changed to >.

2.  [Kleinberg-Tardos, Exercise 3.9] Suppose an n node m edge
    undirected unweighted graph G=(V,E) contains two nodes s,t such
    that the distance between s and t is strictly greater than n/2.
    Show that there must exist some node v, distinct from s and t,
    such that deleting v from G destroys all s-t paths.  (In other
    words, the graph obtained from G by deleting v contains no path
    from s to t.)  Give an algorithm with running time O(m+n) to find
    such a node v.

3.  Fill in the blanks in the following.

    Theorem: A bipartite graph (U,V,E) with |U|=|V|=n has a perfect
    matching if it satisfies property H.  Property H: any subset X of
    U has at least |X| neighbours.

    Proof: 
    Notation: Given subsets U' and V' of U and V, we will use
    (U',V') to denote the subgraph induced by U' and V'.

    The proof is by induction, the induction hypothesis being ... 

    Consider vertex u1 from U.  We know it must have at least one
    neighbour, say v1.  Consider the graph G'=(U-u1,V-v1).  If G'
    satisfies property H, we are done, because ...

    Suppose G' does not satisfy property H.  Then there must exist U'
    in U-u1 having neighbour set V' (in G') such that |V'|<|U'|.  Now
    (U',V'+v1) must satisfy property H because ...  Also
    (U-U',V-V'-v1) satisfies H because ...  Hence ...

4.  Let G be a connected undirected graph with n vertices.  Consider
    its adjacency matrix, i.e. the nxn matrix A, where a_ij = 1 if
    there is an edge from vertex i to vertex j, and 0 otherwise.
    a_ii=0 for all i.  Suppose G is d-regular, i.e. every vertex has
    degree 3.  Show that the all 1s vector, i.e. [1 1 1 ... 1]^T is an
    eigenvector of A.  What is its eigenvalue?  Suppose G has k
    connected components, each d-regular.  Give k linearly independent
    eigenvectors of G.

5.  Suppose there are n people in a room.  What is the expected number
    of pairs that share a birthday?  Assume that birthdays are
    independent and uniformly distributed over the year.  Can you use
    this information to estimate the probability that all the people
    in the room have distinct birthdays?

6.  Consider the following algorithm for finding the gcd of m,n, where
    m,n>0 are integers.

    ----

    while(m != n){
      if (m>n) m = m - n;
      else n = n - m;
    }
    cout << m;

    -----

    Prove that this is correct.

7.  I have a board with 2^n rows and 2^n columns.  I wish to tile it
    tiles made by attaching 3 squares in an L shape.  My requirement
    is that one of the 4 central squares must remain untiled.  Prove
    that this can always be done.


-----