\documentclass[11pt]{article}
% Problem set: do not define TEMPLATE or SOL
% LaTeX template: define TEMPLATE but not SOL
% Solution: define both TEMPLATE and SOL
%\def\sol{1}
\def\template{1}
\usepackage{fullpage,graphicx}
\usepackage{amsmath,amsfonts,amsthm,amssymb,multirow}
\usepackage{algorithmic,comment,url,enumerate}
\usepackage{tikz}
\usepackage{framed}
\usetikzlibrary{decorations.pathreplacing, shapes}
\usepackage[ruled,vlined,commentsnumbered,titlenotnumbered]{algorithm2e}
\newcommand{\expecting}[1]{\noindent{[\textbf{We are expecting:} \em #1\em]}}
\newcommand{\hint}[1]{\noindent{[\textbf{HINT:} \em #1 \em]}}
\newcommand{\pts}[1]{\textbf{(#1 pt.)}}
\newcommand{\sgn}{\mathrm{sgn}}
\definecolor{shadecolor}{gray}{0.95}
\begin{document}
\noindent
\textbf{Problem Set 1 \ifdefined\sol Solution \fi} \hfill CS265, Fall 2020
\ifdefined\sol\else
\newline
Due: September 25 (Friday) at 23:59 (Pacific Time)
\ifdefined\template
\newline
Group members: INSERT NAMES HERE
\fi
%\today
\vspace{.4cm}\noindent
Please follow the homework policies on the course website.
\fi
\noindent
\rule{\linewidth}{0.4pt}
%TODO: could have some problem about black-box PIT, eg, showing that randomness is needed? or \url{https://drops.dagstuhl.de/opus/volltexte/2020/12611/pdf/LIPIcs-APPROX8.pdf} and citations therein.
%or \url{https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12610}
\begin{enumerate}
% ---------- Perfect Matchings ----------
\item \pts{5} \textbf{[Perfect Matchings.]}
Let $G = (V,E)$ be a \em bipartite graph \em with $n$ vertices on each side. A \em perfect matching \em in $G$ is a list of edges $M \subset E$ so that every vertex in $V$ is incident to exactly one edge.
For example, here is a bipartite graph $G$ (on the left), and a perfect matching in $G$ (shown in \textbf{bold} on the right):
\begin{center}
\begin{tikzpicture}[xscale=2,yscale=.6]
\begin{scope}
\foreach \i in {1,2,3,4,5}
{
\node[draw,circle](a\i) at (0,\i) {};
\node[draw,circle](b\i) at (1,\i) {};
}
\draw (a1)--(b1)--(a3)--(b4)--(a5)--(b5)--(a4)--(b3)--(a2)--(b2)--(a1);
\end{scope}
\begin{scope}[xshift=3cm]
\foreach \i in {1,2,3,4,5}
{
\node[draw,circle](a\i) at (0,\i) {};
\node[draw,circle](b\i) at (1,\i) {};
}
\draw[gray] (a1)--(b1)--(a3)--(b4)--(a5)--(b5)--(a4)--(b3)--(a2)--(b2)--(a1);
\draw[ultra thick] (a1)--(b1);
\draw[ultra thick] (a2)--(b2);
\draw[ultra thick] (a3)--(b4);
\draw[ultra thick] (a4)--(b3);
\draw[ultra thick] (a5)--(b5);
\end{scope}
\end{tikzpicture}
\end{center}
Your goal is to determine if the graph $G$ has a perfect matching.
There are efficient deterministic algorithms for this problem, but in this problem you'll work out a simple randomized one.\footnote{This randomized algorithm has the advantage that (a) it generalizes to all graphs (not necessarily bipartite), and (b) it can be parallelized easily. Moreover, it's possible to generalize it to actually recover the perfect matching (and not just decide if there is one or not).}
\begin{enumerate}
\item \pts{2} Recall that the \em determinant \em of an $n \times n$ matrix $A$ is given by
\[ \det(A) = \sum_{\sigma \in S_n} \sgn(\sigma) \prod_{i=1}^n A_{i, \sigma(i)}, \]
where the sum is over all permutations $\sigma: \{1, \ldots, n\} \to \{1, \ldots, n\}$, and where $\sgn(\sigma)$ denotes the signature\footnote{The \em signature \em of a permutation is defined as $-1$ if the permutation can be written as an odd number of transpositions, and $+1$ otherwise. \textbf{The exact definition isn't important} to this problem, all you need to know is that it's either $\pm 1$ in a way that depends on $\sigma$.}
of the permutation $\sigma$.
(For example, if $n=3$, then the function $\sigma: \{1,2,3\} \to \{1,2,3\}$ that maps $1 \mapsto 2$, $2\mapsto 1$, $3\mapsto 3$ is a permutation in $S_3$. The signature of $\sigma$ happens to be $-1$, although as noted in the footnote, if you haven't seen this definition before, don't worry about it).
Let $A$ be the $n \times n$ matrix so that
\[ A_{ij} = \begin{cases} x_{ij} & (i,j) \in E \\ 0 & \text{otherwise} \end{cases} \]
where the $x_{ij}$ are variables,
and $(i,j)\in E$ if and only if the $i$-th vertex on the left
and the $j$-th vertex on the right are connected by an edge in $G$.
%
Notice that $\det(A)$ is a multivariate polynomial in the variables $x_{ij}$.
Explain why $\det(A)$ is not identically zero if and only if $G$ has a perfect matching.
\item \pts{3} Use the part above to develop a randomized algorithm for deciding whether or not there is a perfect matching. Your algorithm should run in $O(n^3)$ operations. If $G$ has no perfect matching, your algorithm should return ``There is no perfect matching'' with probability $1$. If $G$ has a perfect matching, your algorithm should return ``There is a perfect matching'' with probability at least $0.9$.
You should clearly state your algorithm and explain why it has the desired properties.
\hint{You may use the fact that one can compute the determinant of a matrix $A \in \mathbb{R}^{n \times n}$ in $O(n^3)$ operations.}
\item \pts{0} \textbf{[Optional: this won't be graded.]} Extend your algorithm to actually \em return \em a perfect matching. And/or, extend your algorithm to non-bipartite graphs. As a hint, consider the matrix
\[ A = \begin{cases} x_{ij} & \{i,j\} \in E \text{ and } i < j \\ -x_{ji} & \{i,j\} \in E \text{ and } i \geq j \\ 0 & \text{ else } \end{cases}\]
\end{enumerate}
\ifdefined\template
\begin{shaded}
\textbf{SOLUTION:}
\ifdefined\sol
\input{solution/matching.tex}
\fi
\end{shaded}
\fi
\item \pts{8} Suppose you are rolling a fair, 6-sided die repeatedly.
\begin{enumerate}
\item \pts{4} What is the expected number of rolls until you get two 3's in a row (counting both 3's)? Justify your answer.
\hint{The answer is not $36$...}
\hint{If you find yourself doing a tedious computation, try to think of a simpler way. Perhaps look to the mini-lecture on linearity of expectation for some inspiration...}
\item \pts{4} What is the expected number of rolls until you get a 3 followed by \em either \em a 3 or a 4 (counting both rolls)?
Justify your answer.
\item \pts{0} \textbf{[Optional: this won't be graded]} What is the expected number of rolls until you get a 3 followed by a 4 (counting both rolls)?
\end{enumerate}
\ifdefined\template
\begin{shaded}
\textbf{SOLUTION:}
\ifdefined\sol
\input{solution/dice.tex}
\fi
\end{shaded}
\fi
\item \pts{12}
A long time ago (before COVID-19...) a queen wanted to hold a grand party. The queen had $n$ bottles of wine set aside for the party. Unfortunately, a wicked fairy had cursed $k$ of the $n$ bottles of wine, so that they would give severe indigestion to anyone who drinks from them. The queen did not want to give her guests indigestion. The court alchemist had devised a test to identify cursed wine: it only took a drop of wine, but the test was expensive. The queen suggested:
\begin{quote} Strategy 1: test all $n$ of the bottles! It will be expensive, but worth it for the comfort of my guests! \end{quote}
The alchemist, who was very clever, suggested another approach. The test could work on \em mixtures \em of wine: given a drop of wine from several bottles, the test will come up positive if any of the wine was cursed. The alchemest suggested:
\begin{quote} Strategy 2: divide the $n$ bottles into $n/m$ disjoint groups of size $m$, at random. (Suppose for convenience that $m$ divides $n$). Then test each of the groups, using one test per group. If any group tests positive, re-test each bottle in the group to identify the poison bottles.
\end{quote}
\begin{enumerate}
\item \pts{4} In terms of $n,m,k$, what is the expected number of groups that will test positive in Strategy 2? It's okay to leave your answer in terms of some binomial coefficients or something like that.
\item \pts{2} In terms of $n,m,k$, what is the expected total number of tests that we will need in Strategy 2? Again, it's okay to leave your answer in terms of some binomial coefficients or something like that.
\item \pts{6} Consider the following parameter regimes, where we think of $n \to \infty$. In which of these parameter regimes is Strategy 2 better than Strategy 1, in terms of expected number of tests as $n \to \infty$?
Below, the ``little-oh'' notation $f(n) = o(g(n))$ means that $f(n)/g(n) \to 0$ as $n \to \infty$; the ``little-omega'' notation $f(n) = \omega(g(n))$ means that $f(n)/g(n) \to \infty$ as $n \to \infty$; and all asymptotic notation is with respect to the limit $n \to \infty$.
\begin{enumerate}
\item $k = \Theta(1)$, $\omega(1) = m = o(\sqrt{n})$.
\item $k = \Theta(n^{5/6})$, $m = \Theta(n^{1/3})$
\item $2 \leq m = \Theta(1)$, $k = \Theta(\sqrt{n})$.
%\item $k = n/100$, $m$ is the best that you can choose it to be.
\end{enumerate}
\hint{At this point, you'll probably want to simplify any binomial coefficients you have lying around. There are a number of ways to do this.\footnote{
Here is a delightful---and very useful---note by Shagnik Das for more about various approximations of binomial coefficients:
\url{http://page.mi.fu-berlin.de/shagnik/notes/binomials.pdf}}
You may want to use the fact (which follows from Stirling's approximation) that for $\omega(1) = k = o(\sqrt{n})$,
\[{n \choose k} = (1 + o(1))\frac{1}{\sqrt{2\pi k}} \left( \frac{ne}{k} \right)^k. \]
It might also help to remember that $e^{-x} = 1 - x + O(x^2)$ as $x \to 0$.
Part of this problem is to get really comfortable with these sorts of approximations!
}
\item \pts{0}\textbf{[Optional: this won't be graded.]} The court jester, who was cleverer still, suggested the following plan, which had the advantage that only one round of testing was needed:
\begin{quote}
Strategy 3: Create $t$ groups. Put a drop of wine from bottle $i$ into group $j$ with probability $p$, independently for each $(i,j)$. (Note that one bottle may appear in several groups). For each bottle, if it is tested negative in at least one group, the bottle is safe and can be served to the guests. Otherwise, declare the bottle cursed.
\end{quote}
\begin{enumerate}
\item
In terms of $p,k,n$, what is the expected number of false positives (that is, bottles that are safe but are labeled cursed) in Strategy 3? What is the expected number of false negatives (cursed bottles labeled safe)?
\item Suppose that $p = 1/k$ and $k \geq 2$. Say that the queen wants to serve at least $n - 2k$ bottles at the party in expectation, and under no circumstances wants to serve a cursed bottle. How many tests does Strategy 3 use? How does this compare to Strategy 1?
\end{enumerate}
\end{enumerate}
\ifdefined\template
\begin{shaded}
\textbf{SOLUTION:}
\ifdefined\sol
\input{solution/cursed_bottles.tex}
\fi
\end{shaded}
\fi
\end{enumerate}
\end{document}