\documentclass[twoside]{article}
\usepackage[usenames,dvipsnames,svgnames,table]{xcolor}
\definecolor{darkgreen}{rgb}{0.0,0,0.9}
\usepackage[colorlinks=true,pdfpagemode=UseNone,citecolor=OliveGreen,linkcolor=BrickRed,urlcolor=BrickRed,
%pagebackref,
pdfstartview=FitW]{hyperref}
%\usepackage[backref=true, backend=biber, isbn=false, url=true, firstinits=true, maxnames=20, style=alphabetic,]{biblatex}
%\addbibresource{references.bib}
\usepackage{graphics,amsmath,amsthm,thmtools,amssymb,tikz,mathtools, algorithm, algpseudocode,enumerate}
\setlength{\oddsidemargin}{0 in}
\setlength{\evensidemargin}{0 in}
\setlength{\topmargin}{-0.6 in}
\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\headsep}{0.75 in}
\setlength{\parindent}{0 in}
\setlength{\parskip}{0.1 in}
\def\X{b}
\def\tX{\tilde{b}}
\def\mX{B}
\def\tmX{\tilde{B}}
\def\bone{{\bf 1}}
\def\eps{\epsilon}
\def\R{\mathbb{R}}
\def\mP{\mathbb{P}}
\def\mE{\mathbb{E}}
\def\cT{{\cal T}}
\def\reff{\textup{Reff}}
%
% The following commands set up the lecnum (lecture number)
% counter and make various numbering schemes work relative
% to the lecture number.
%
\newcounter{lecnum}
\renewcommand{\thepage}{\thelecnum-\arabic{page}}
\renewcommand{\thesection}{\thelecnum.\arabic{section}}
\renewcommand{\theequation}{\thelecnum.\arabic{equation}}
\renewcommand{\thefigure}{\thelecnum.\arabic{figure}}
\renewcommand{\thetable}{\thelecnum.\arabic{table}}
\newcommand{\PP}[2]{\mP_{#1}\left[#2\right]}
\newcommand{\weight}[1]{w(#1)}
\renewcommand{\P}[1]{\mP\left[#1\right]}
\newcommand{\E}[1]{\mE\left[#1\right]}
\newcommand{\EE}[2]{\mE_{#1}\left[#2\right]}
\newcommand{\norm}[1]{\|#1\|}
\DeclareMathOperator{\trace}{trace}
\DeclareMathOperator{\vol}{vol}
\DeclareMathOperator{\Var}{Var}
%
% The following macro is used to generate the header.
%
\newcommand{\lecture}[4]{
\pagestyle{myheadings}
\thispagestyle{plain}
\newpage
\setcounter{lecnum}{#1}
\setcounter{page}{1}
\noindent
\begin{center}
\framebox{
\vbox{\vspace{2mm}
\hbox to 6.28in { {\bf CSE 521: Design and Analysis of Algorithms
\hfill Winter 2017} }
\vspace{4mm}
\hbox to 6.28in { {\Large \hfill Problem Set #1 \hfill} }
\vspace{2mm}
\hbox to 6.28in { \hfill {\it Deadline: #2} \hfill}
\vspace{2mm}}
}
\end{center}
\markboth{Problem Set #1: #2}{Problem Set #1: #2}
% {\bf Disclaimer}: {\it These notes have not been subjected to the
% usual scrutiny reserved for formal publications. They may be distributed
% outside this class only with the permission of the Instructor.}
% \vspace*{4mm}
}
%
% Convention for citations is authors' initials followed by the year.
% For example, to cite a paper by Leighton and Maggs you would type
% \cite{LM89}, and to cite a paper by Strassen you would type \cite{S69}.
% (To avoid bibliography problems, for now we redefine the \cite command.)
% Also commands that create a suitable format for the reference list.
\renewcommand{\cite}[1]{[#1]}
\def\beginrefs{\begin{list}%
{[\arabic{equation}]}{\usecounter{equation}
\setlength{\leftmargin}{2.0truecm}\setlength{\labelsep}{0.4truecm}%
\setlength{\labelwidth}{1.6truecm}}}
\def\endrefs{\end{list}}
\def\bibentry#1{\item[\hbox{[#1]}]}
%Use this command for a figure; it puts a figure in wherever you want it.
%usage: \fig{NUMBER}{SPACE-IN-INCHES}{CAPTION}
\newcommand{\fig}[3]{
\vspace{#2}
\begin{center}
Figure \thelecnum.#1:~#3
\end{center}
}
% Use these for theorems, lemmas, proofs, etc.
\newtheorem{theorem}{Theorem}[lecnum]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newenvironment{proofof}[1]{{\em Proof of #1.}}{\hfill%\rule{2mm}{2mm}
\qed}
% **** IF YOU WANT TO DEFINE ADDITIONAL MACROS FOR YOURSELF, PUT THEM HERE:
\begin{document}
%FILL IN THE RIGHT INFO.
%\lecture{**LECTURE-NUMBER**}{**DATE**}{**LECTURER**}{**SCRIBE**}
\lecture{1}{Jan 18 (at 12:00 PM) in \href{http://canvas.uw.edu}{Canvas}}
%\footnotetext{These notes are partially based on those of Nigel Mansell.}
% **** YOUR NOTES GO HERE:
% Some general latex examples and examples making use of the
% macros follow.
%**** IN GENERAL, BE BRIEF. LONG SCRIBE NOTES, NO MATTER HOW WELL WRITTEN,
%**** ARE NEVER READ BY ANYBODY.
\vspace{-.6cm}
\begin{center} Instructions\end{center}
\vspace{-.6cm}
\begin{itemize}
\item You should think about each problem by yourself for at least an hour before choosing to collaborate with others.
\item You are allowed to collaborate with fellow students taking the class in solving the problems (in groups of at most 3 people for each problem). In fact this is encouraged so that you interact with and learn from each other. However, you must write up your solutions on your own. If you collaborate in solving problems, you should clearly acknowledge your collaborators for each problem.
\item You are not allowed to search for answers or hints on the web. You are encouraged to contact the instructors or the TA for a possible hint if you feel stuck on a problem and require some assistance.
\item Solutions typeset in LATEX are preferred.
\item Feel free to use the Discussion Board or email the instructor or the TA if you have any questions or would like any clarifications
about the problems.
\item This problem set is slightly longer because January 16 is a holiday
\item Please upload your solutions to Canvas. The solution to each problem must be uploaded separately.
%\item There are seven problems. Only students signed up for the graduate version need to turn in the last problem (others may do so as extra credit if they have time).
\end{itemize}
\hrule
\begin{enumerate}[1)]
%\item Show that all eigenvalues of any symmetric matrix are real.
\item Given a graph $G=(V,E)$, a cut is an $\alpha$-approximate min cut, if the number of its edges is at most $\alpha$ times the minimum cut of $G$. Use an extension of the contraction algorithm to show that any graph $G$ has at most $n^{2\alpha}$ $\alpha$-approximate min cuts. You would also receive full credit if you show that the number of $\alpha$-approximate min cuts is at most $n^{O(\alpha)}$.
\item In this problem you are supposed to implement Karger's min-cut algorithm. I have uploaded three input files to the course website. Each file contains the list of edge of a graph; note that the graphs may also have parallel edges.
For each input file you should output the size and the number of min cuts. Please upload your code to Canvas. You should also write the output of your program for each input in the designated ``text box'' of Problem 2 in Canvas.
\noindent{\bf Extra Credit: } Find the size and the number of min-cuts of the graph in file \\
\href{http://courses.cs.washington.edu/courses/cse521/17wi/a3.in}{http://courses.cs.washington.edu/courses/cse521/17wi/a3.in}. Write your solution in the ``text box'' of Problem 2 in Canvas.
%Here, R_e is the effective resistance of the edge e in the electrical network where the resistance of each edge is 1.
\item Given a graph $G=(V,E)$ with $n=|V|$ vertices. Let $k$ be the size of the minimum cut of $G$. In this problem we show that if $k$ is large enough we can down sample $G$ and preserve the size of its min-cut.
Let $H$ be a subgraph of $G$ defined as follows: For every edge $e$ of $G$ include $e$ in $H$ with probability $p=\frac{12\ln n}{k\eps^2}$. If we include $e$ in $H$ we weight it by $1/p$.
We show that %if $k>2\log n$, then
the (weighted) min-cut of $H$ is at least $k(1-\eps)$ with probability at least $1-1/n$. Note that $H$ has only $p|E|$ many edges (in expectation). So, $H$ has significantly less edges than $G$ if $k\gg \ln(n)/\eps^2$.
\begin{enumerate} [a)]
\item For a cut $(S,\overline{S})$, let
$$w_H(S,\overline{S})=\frac{|H(S,\overline{S})|}{p}$$
be the sum of the weights of all edges of $H$ across this cut. Show that for any set $S\subset V$,
$$ \E{w_H(S,\overline{S})} = |E(S,\overline{S})| $$
\item Use Chernoff bound to show that for any set $S\subset V$,
$$ \P{w_H(S,\overline{S}) < (1-\eps) |E(S,\overline{S})| } \leq e^{-6\ln n|E(S,\overline{S})|/k} = n^{-6|E(S,\overline{S})|/k}$$
\item Use union bound and the statement of Problem 1 to show that for any integer $\alpha\geq 1$, with probability at least $1-1/n^2$, for all sets $S$ where
$\alpha k \leq |E(S,\overline{S})| \leq 2\alpha k$,
$$ w_H(S,\overline{S}) \geq (1-\eps) |E(S,\overline{S})|. $$
\item Use another application of union bound to show that with probability at least $1-1/n$, for all sets $S\subset V$
$$ w_H(S,\overline{S}) \geq (1-\eps) |E(S,\overline{S})|.$$
\end{enumerate}
%$$ $$
\item
Consider the following process for executing $n$ jobs on $n$ processors. In each round, every (remaining) job picks a processor uniformly and independently at random. The jobs that have no contention on the processors they picked get executed, and all other jobs {\em back off} and then try again. Jobs only take one round of time to execute, so in every round all the processors are available.
For example, suppose we want to run 3 jobs on 3 processors. Suppose in round 1, jobs 1 and 2 choose the first processor and job 3 chooses the second processor. Then job 3 will be executed and jobs 1 and 2 back off. Suppose in round 2, job 1 chooses the third processor and job 2 chooses the first processor. Then both of them are executed and the process ends in 2 rounds.
In this problem we almost show that the number of rounds until all jobs are finished is $O(\log \log n)$ with high probability.
\begin{enumerate}[a)]
\item Suppose less than $\sqrt{n}$ jobs are left at the beginning of some round. Show that for some constant $c>0$, with probability at least $c$ no job remains after this round.
\item In the first round we have $n$ jobs. Show that the expected number of processors that are picked by no jobs is $n(1-1/n)^n$.
\item Suppose there are $r$ jobs left at the beginning of some round. What is the expected number of processors that are matched to exactly one job?
What is the expected number of jobs remaining to be completed after that round?
\item Suppose in each round the number of jobs completed is exactly equal to its expectation. Show that (under this false assumption) the number of rounds until all jobs are finished is $O(\log \log n)$.
\item In this part we almost justify the false assumption.
Suppose there are $r$ jobs left at the beginning of some round. Let $E$ be the expected number of processors that are matched to exactly one job.
Show that for any $k>1$, the number of processors with exactly one matched job is in the interval
$[E-k\sqrt{r}, E+k\sqrt{r}]$
with probability at least $\exp(-\Omega(k^2))$.
You can use the McDiarmid's inequality to prove the claim.
\begin{theorem}[McDiarmid's inequality]
Let $X_1,\dots,X_n\in {\cal X}$ be independent random variables. Let $f:{\cal X}^n\to\R$. If for all $1\leq i\leq n$ and
for all $x_1,\dots,x_n$ and $\tilde{x}_i$,
$$ |f(x_1,\dots,x_n)-f(x_1,\dots,x_{i-1},\tilde{x}_i,x_{i+1},\dots,x_n)| \leq c_i,$$
then
$$ \P{|f(X_1,\dots,X_n)-\E f| \geq \eps} \leq 2\exp\left(\frac{-2\eps^2}{\sum_{i=1}^n c_i^2}\right)$$
\end{theorem}
\end{enumerate}
\end{enumerate}
%\printbibliography
\end{document}