Takehome Midterm Exam



Out: Thursday, March 18.
The exam is due at class on Thursday, April 1.
No late submissions will be accepted.

You can not discuss the exam with anyone else, and
you can not consult any other sources (including books, people, and webpages) except for
your class notes and the textbooks [Motwani-Raghavan] and [Mitzenmacher-Upfal].

Email Linji (ljyang at gatech dot edu) and myself for clarifications/questions about any of the problems.
    Exam problems:

  1. Min 3-way cuts:
    For an undirected graph G=(V, E), a 3-way cut is a subset S of edges
    whose removal from G breaks the graph into at least 3 components. The size
    of the 3-way cut is the number of edges in S.
    Use a randomized algorithm to prove that there are O(n4) 3-way cuts of minimum size.

  2. [Mitzenmacher-Upfal] Problem 4.20 (analyzing quicksort, see Chapter 2.5 for an introduction to quicksort)

  3. (Note, the following is a purely geometric problem, it has nothing to do with graphs.
    And you don't need to know any geometry beyond that a sphere means a 3-dimensional ball.)
    Monochromatic coloring of a cube in a two-colored ball:
    Ten percent of the surface of a sphere is colored blue while the rest is colored red.
    Show that irrespective of the manner in which the colors are distributed, it is
    possible to inscribe, in that sphere, a cube with all its vertices red.
    Hint: Use the first moment method.

  4. Choose a project topic, some suggestions are here.