\documentclass[12pt]{article}

\usepackage{graphicx}
\usepackage{amsmath,amssymb,url}
\usepackage{bbm}

\newfont{\bssdoz}{cmssbx10 scaled 1200}
\newfont{\bssten}{cmssbx10}


\oddsidemargin  0in \evensidemargin 0in \topmargin -0.5in
\headheight 0.25in \headsep 0.25in
\textwidth   6.5in \textheight 9in
\parskip 1.5ex  \parindent 0ex \footskip 20pt

\begin{document}
\parindent 0ex
\thispagestyle{empty} \vspace*{-0.75in}
{\bssdoz CME 305: Discrete Mathematics and Algorithms}
{\\ \bssten Instructor: Reza Zadeh (rezab@stanford.edu) }
{\\ \bssten HW\#2 --  Due at the beginning of class Thursday 02/09/17}
\vspace{5pt}

\begin{enumerate}


\item {\bf(Kleinberg Tardos 7.27)}
Some of your friends with jobs out West decide they really need some extra time 
each day to sit in front of their laptops, and the morning commute from Woodside 
to Palo Alto seems like the only option.  So they decide to carpool to work.
Unfortunately, they all hate to drive, so they want to make sure that any carpool 
arrangement they agree upon is fair and doesn't overload any individual with too 
much driving.  Some sort of simple round-robin scheme is out, because none of them 
goes to work every day, and so the subset of them in the car varies from day to day.

Here's one way to define \emph{fairness}.  Let the people be labeled 
$S=\{p_1,\ldots,p_k\}$.  
We say that the \emph{total driving obligation} of $p_j$ over a set of days is 
the expected number of times that $p_j$ would have driven, had a driver been 
chosen uniformly at random from among the people going to work each day.  
More concretely, suppose the carpool plan lasts for $d$ days, and on the $i^{th}$ 
day a subset $S_i\subseteq S$ of the people go to work. Then the above definition 
of the total driving obligation $\Delta_j$ for $p_j$ can be written as 
$\Delta_j = \sum_{i: p_j \in S_i} \frac 1 {|S_i|}$.  
Ideally, we'd like to require that $p_j$ drives at most $\Delta_j$ times; 
unfortunately, $\Delta_j$ may not be an integer.

So let's say that a \emph{driving schedule} is a choice of a driver for each day ---
that is, a sequence $p_{i_1},p_{i_2},\ldots,p_{i_d}$ with $p_{i_t} \in S_t$ ---
and that a \emph{fair driving schedule} is one in which each $p_j$ is chosen as 
the driver on at most $\lceil \Delta_j \rceil$ days.

\begin{enumerate}
 \item Prove that for any sequence of sets $S_1,\ldots,S_d$, there exists a fair 
 driving schedule.
 \item Give an algorithm to compute a fair driving schedule with running time 
 polynomial in $k$ and $d$.
\end{enumerate}

\item Recall Karger's algorithm for the global min-cut problem. In this problem
we modify the algorithm to improve its running time.
\begin{enumerate}
\item Prove that if we stop the original Karger's algorithm when the remaining 
number of vertices is
\[ \max \left\{ \lceil 1+ n/\sqrt{2} \rceil , 2 \right\} \, , \] 
the probability that we have contracted an edge in the 
min-cut is less than $1/2$. Lets call this procedure \emph{Partial Karger}.
\item Now suppose we apply \emph{Partial Karger} to two copies of $G$ to produce 
graphs $G_1$ and $G_2$. We then recursively apply these steps to $G_1$ and $G_2$
and so on until each recursive call returns a graph on two vertices.
If $r(n)$ is the running time of this process as a function of the number of 
vertices $n$ of $G$, derive a recursive equation for $r(n)$ and solve it to obtain
an explicit expression for the running time 
(you may use $O(\cdot)$ notation to simplify your recursive equation).
\item Show that the algorithm in part $(b)$ produces $O(n^2)$ contracted graphs 
on two vertices each. Prove that the probability that at least one of them contains
a global min-cut is at least $1/\log(n)$ up to a multiplicative constant.

{\bf Hint:} Think of the recursion as a binary tree with paths leading to the 
$O(n^2)$ leaves representing the two-vertex contracted graphs.
\item Compare the running time of the above algorithm to Karger's original given
the same probability of failure.
\end{enumerate}


\item An independent set in a graph is a set of vertices with no edges
connecting them. Let $G$ be a graph with $nd/2$ edges $(d > 1)$, and consider the following
probabilistic experiment for finding an independent set in $G$: delete each vertex of $G$
(and all its incident edges) independently with probability $1 - 1/d$.
\begin{enumerate}
\item Compute the expected number of vertices and edges that remain after the deletion
process. Now imagine deleting one endpoints of each remaining edge.
\item From this, infer that there is an independent set with at least $n/2d$ vertices in any
graph with on $n$ vertices with $nd/2$ edges.
\end{enumerate}


\item Prove that a graph can only have at most $n \choose 2$ different cuts that realize the global minimum cut value.

\item Exhibit a graph $G=(V,E)$ where there are an exponential (in $|V|=n$, the number of nodes) number of minimum cuts between a
particular pair of vertices. Do this by constructing a family of graphs parameterized on $n$ and give a pair of vertices $s,t$ such
that there are exponentially many minimum cuts between $s$ and $t$.

\item Exhibit a directed graph that has cover time exponentially large in the number of nodes. Contrast this with 
the cover time of undirected graphs discussed in class.

\item Given a directed graph $G$, we want to find a Cycle Cover (or return None
if one does not exist). Recall that a cycle cover is a set of cycles covering all nodes.
Provide a polynomial time algorithm for this problem, and justify correctness.

\item Compute the cover time of a cycle with $n$ vertices.\\

\item Suppose we have a $2n\times 2n$ ($n \ge 2$) table where each cell is filled with an integer in $\{1,2,3,...,2n^2\}$. Moreover, each integer shows up exactly twice. Show that one can pick $2n$ cells that satisfy all the following conditions: (1). all the numbers written in these cells are distinct; (2). in each row exactly one cell is picked out; (3) in each column exactly one cell is picked out. \\

\item Say we have an $n \times n$ checkerboard.\footnote{With credit to Jeff Erickson: \url{http://jeffe.cs.illinois.edu/teaching/algorithms/}.} The tiles are two-colored, i.e.
  white and black. We delete an equal number of white and black squares from the board.
  Describe and analyze an algorithm 
  to determine whether an efficient tiling of Dominoes  
  (which are $2 \times 1$ pieces) exists,
  subject to the constraint that each square is covered and no domino is hanging   off the board.

\begin{center}
  \includegraphics[scale=0.2]{tiling.pdf}
\end{center}

Your input is a two-dimensional indicator array, of size $n \times n$, whose
$i,j$ value is one if and only if the square in row $i$ and column $j$
has been deleted. Your output is a single bit; you do \emph{not} have to compute
the actual placement of the dominoes. In the example shown above, your algorithm
should return \texttt{True}.

\end{enumerate}

\end{document}