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:
- 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.
-
[Mitzenmacher-Upfal] Problem 4.20 (analyzing quicksort, see Chapter 2.5 for
an introduction to quicksort)
-
(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.
-
Choose a project topic, some suggestions are here.