\documentclass[11pt]{article}
	\usepackage[margin=1in]{geometry}
	\usepackage{amsfonts, amsmath, amssymb, amsthm}
	\usepackage{microtype}
	\usepackage{nicefrac}
	\usepackage[small]{complexity}

	\usepackage[colorlinks=true]{hyperref}
	\hypersetup{
		linkcolor=[rgb]{0.5, 0.2, 0.2},
		citecolor=[rgb]{0.2, 0.5, 0.2},
		urlcolor =[rgb]{0.2, 0.2, 0.5}
	}

	% complexity, needs to be after hyperref to work
		\renewcommand{\S}{\defaultS}
		\renewcommand{\L}{\ComplexityFont{L}}
		\newcommand{\ETIME}{\ComplexityFont{E}}

	\newcommand{\thecourse}{\errmessage{Course is undefined}}
	\newcommand{\handout}[5]{
		%\renewcommand{\thepage}{#1-\arabic{page}}
		\noindent%
		\begin{center}%
			\framebox{%
				\vbox{%
					\vspace{1mm}%
					\hbox to 5.78in {
						{\bf \thecourse}%
						\hfill%
						\smash{\parbox[t]{3in}{\raggedleft #2}}%
					}%
					\vspace{\baselineskip}%
					\hbox to 5.78in { {\Large \hfill #5  \hfill} }%
					\vspace{\baselineskip}%
					\hbox to 5.78in {%
						\smash{\parbox[b]{2.5in}{\raggedright #3}}%
						\hfill
						\smash{\parbox[b]{3in}{\raggedleft #4}}%
						}%
				}%
			}%
		\end{center}%
		\vspace*{4mm}%
	}%

	% \setlength\parindent{0pt}

	% https://tex.stackexchange.com/questions/21004/add-asterisk-after-labels-in-enumerate
	\newenvironment{starnumerate}{\enumerate\setupstarnumerate}{\endenumerate}
	\newif\ifstaritem
	\newcommand{\setupstarnumerate}{%
		\global\staritemfalse
		\let\origmakelabel\makelabel
		\def\staritem##1{\global\staritemtrue\def\mesymbol{##1}\item}%
		\def\makelabel##1{%
		\origmakelabel{##1\ifstaritem\rlap{\mesymbol}\fi\enspace}%
		\global\staritemfalse}%
	}

	% math
	\newcommand{\N}{\mathbb{N}}
	\newcommand{\F}{\mathbb{F}}
	\newcommand{\bits}{\ensuremath{\{0,1\}}}
	\newcommand{\la}{\langle}
	\newcommand{\ra}{\rangle}
	\newcommand{\rX}{\mathsf{X}}
	\newcommand{\rY}{\mathsf{Y}}
	\newcommand{\rZ}{\mathsf{Z}}
	\newcommand{\e}{\mathrm{e}}
	\renewcommand{\vec}[1]{\overline{#1}}
	\newcommand{\floor}[1]{\lfloor #1 \rfloor}
	\newcommand{\ceil}[1]{\lceil #1 \rceil}
	\newcommand{\eps}{\epsilon}
	\DeclareMathOperator{\Var}{Var}

	\renewcommand{\E}{\mathbb{E}}

	%	open/closed intervals
	%       [
	\newcommand{\ocint}[2]{\ensuremath{(#1,#2]}}%)
	\newcommand{\icint}[1]{\ocint{\infty}{#1}}
	%       (
	\newcommand{\coint}[2]{\ensuremath{[#1,#2)}}%]
	\newcommand{\ciint}[1]{\coint{#1}{\infty}}
	\newcommand{\ccint}[2]{\ensuremath{[#1,#2]}}%)
	\newcommand{\ooint}[2]{\ensuremath{(#1,#2)}}%)

	% copied from 2018-01_cs473-algorithms.lectures.zip/prefix.tex
	\newcommand{\fcode}[1]
		{
			\smallskip
			\centerline{
				\fbox{
					\begin{minipage}{0.95\linewidth}
						\code{#1}
					\end{minipage}
				}
			}
			\smallskip
		}
	\newcommand{\innercode}[1]
		{
			\begin{tabbing}
				----\=----\=----\=----\=----\=----\=----\kill
				#1
			\end{tabbing}
		}
	\newcommand{\code}[1]
		{
			\footnotesize
			\tt
			\begin{center}
				\innercode{#1}
			\end{center}
		}


\begin{document}

\renewcommand{\thecourse}{cs473 Algorithms}
\handout{0}%
	{}%
	{Prof.\ Michael A. Forbes}%
	{Due: \textit{Mon., 2026-03-30 17:00}}%
	{Problem Set \#5}

Submissions must obey the following guidelines when using \emph{reductions} to solve problems, in particular when using algorithms for computing maximum flows as a black-box.

\begin{itemize}

	\item \emph{Construction:}  Submissions must completely describe the relevant capacitated graph by describing the vertices, the edges (with direction), and capacities.  The source $s$ and sink $t$ must also be identified.

	\item \emph{Forward reduction:}  Submissions must describe an algorithm to, given the original input, construct the above mentioned capacitated graph.  This includes a correctness and complexity analysis.

	\item \emph{Backwards reduction:}  Submissions must describe an algorithm to, given a maximum flow in the constructed capacitated graph, efficiently solve the original problem.  This includes a correctness and complexity analysis.  An argument for correctness will typically require two directions.  First, if the resulting maximum flow is \emph{large} in value, then the produced solution to the original problem is correct.  Second, if the resulting maximum flow is \emph{small} in value, then the produced solution to the original problem is correct.

	\item \emph{Complexity:}  The overall complexity of the entire algorithm must be specified as a function of the \emph{original} input (\textbf{not} as a function of the constructed capacitated graph).

	\item Submissions should assume that maximum flows can be computed in $O(nm)$ time on graphs with $n$ vertices and $m$ edges, and in particular should \textbf{not} reproduce a maximum flow algorithm unless required.
		
\end{itemize}

Analogous guidelines exist for reductions to other problems whose algorithms were presented in lecture or auxiliary reading, such as shortest paths with negative edge lengths, or maximum bipartite matching.

All problems are of equal value.

\begin{enumerate}

	\item Let $G=(V,E)$ be a (directed) capacitated graph with non-negative integral capacities $(c_e)_{e\in E}$.  Let $k$ be an integer.

		\begin{enumerate}

			\item Design an efficient algorithm to decide if $G$ has a flow $f$ of value $k$, where all edge flows $f_e$ are \emph{even}.

			\item Design an efficient algorithm to decide if $G$ has a flow $f$ of value $k$, where all edge flows $f_e$ are \emph{odd}.

		\end{enumerate}

	\item Overlay Networks.  Kleinberg-Tardos Chapter 13, Problem \#4.

	\item In this problem we improve the analyses from lecture.
		\begin{enumerate}
			\item Prove that in the contention resolution process on $n$ players, the time until all players successfully communicate is $O(n\lg n)$.

				\emph{Hint:} Use a formula we derived for the expectation of a random variable.
			
			\item Consider the following algorithm for picking a splitter, which we used to develop our randomized selection algorithm.  Let $0<\epsilon<1$ be a parameter.

				\fcode
				{
					{\bf pick-splitter$_\epsilon$}($a=(a_1,\ldots,a_n)$):\\
					\>	while\\
					\>	\>	randomly pick $i\in\{1,\ldots,n\}$\\
					\>	\>	partition $a$ into $b,a_i,c$ with $b_j<a_i<c_k$ for any $j,k$\\
					\>	\>	let $r=|b|+1$\\
					\>	\>	if $\epsilon n \le r\le (1-\epsilon)n$, return $a_i$
				}

				In lecture, we considered the above algorithm when $\epsilon=\nicefrac{1}{4}$.

				\begin{enumerate}
					\item For each value of $0<\epsilon<1$, give an analysis of the expected number of comparisons used for our \textbf{selection} algorithm, when using the above \textbf{pick-splitter}$_\epsilon$ algorithm.

					\item Choose a value of $\epsilon$ to minimize the number of comparisons from part (i).
				\end{enumerate}
		\end{enumerate}


\end{enumerate}

\end{document}
