\documentclass[12pt]{article}
\usepackage{6820}

\newcommand\seq[3]{#1_{#2},\ldots,#1_{#3}}
\newcommand\subs\subseteq
\newcommand\set[2]{\{#1\mid#2\}}
\newcommand\supp[1]{\mathsf{supp}(#1)}
\newcommand\reals{\mathbb{R}}

\pagestyle{empty}

\begin{document}

\header{Homework 4}{Due Wednesday, November 2, 2022}

\begin{enumerate}
\item
Consider the following fallacious argument. Let $S=\{1,2,\ldots,n\}$, $n$ odd. Assign the elements of $S$ random priorities chosen independently with uniform probability from the real interval $[0,1)$. Assemble the elements into a treap so that the elements are in inorder with respect to the data values $S$ and heap order with respect to the random priorities. Since we expect the tree to be balanced, the most likely place for the middle element $m = (n+1)/2$ to be found is at the root, therefore its expected depth in the tree is minimum among all elements of $S$.

State and prove a result that shows that this argument is as wrong as it can possibly be.

\item
A \emph{(discrete) probability distribution} on a set $X$ is a real-valued function $\mu:X\to\reals$ such that $\mu(x)\ge 0$ for all $x\in X$ and $\mu(X) = 1$, where $\mu(A)=\sum_{x\in A}\mu(x)$ for $A\subs X$. The \emph{support} of $\mu$ is the set $\supp\mu = \set{x\in X}{\mu(x)>0}$. A \emph{joint distribution} on $X$ and $Y$ is simply a probability distribution on the cartesian product $X\times Y$. For a joint distribution $\mu:X\times Y\to\reals$, the \emph{marginal distributions} of $\mu$ are
\begin{align*}
& \mu_X:X\to\reals && \mu_Y:Y\to\reals\\
& \mu_X(x) = \sum_{y\in Y}{\mu(x,y)} && \mu_Y(y) = \sum_{x\in X}{\mu(x,y)}.
\end{align*}
Given finite sets $X$ and $Y$, distributions $\alpha:X\to\reals$ and $\beta:Y\to\reals$, and a subset $R\subs X\times Y$, you would like to know whether there exists a joint distribution $\mu$ on $X\times Y$ with $\supp\mu\subs R$ and marginals $\alpha$ and $\beta$, and to find such a joint distribution if so.
\begin{enumerate}
\item
Prove that such a joint distribution exists if and only if
\begin{enumerate}[(i)]
\item
for all $A\subs X$, $\alpha(A)\le\beta(R(A))$, where $R(A) = \set{y}{\exists x\in A\ (x,y)\in R}$, and
\item
for all $B\subs Y$, $\beta(B)\le\alpha(R^{-1}(B))$, where $R^{-1}(B) = \set{x}{\exists y\in B\ (x,y)\in R}$.
\end{enumerate}
(\emph{Hint}.
 Hfr gur znk-sybj zva-phg gurberz. Nqq n fbhepr naq n fvax jvgu pncnpvgvrf rapbqvat gur qrfverq znetvanyf gb gur ovcnegvgr tencu (K,L,E).)
\item
Give an efficient algorithm for this problem.
\end{enumerate}

\item
Given a connected undirected graph $G$, we would like to find a spanning tree whose largest edge weight is minimum over all spanning trees of $G$.
\begin{enumerate}
\item
Show that any minimum-weight spanning tree has this property.
\item
Describe an $O(m)$ algorithm for this problem. (\emph{Hint}.
 Hfr gur yvarne-gvzr zrqvna-svaqvat nytbevguz sebz Yrpgher 1. Guvax qvivqr naq pbadhre.)
\end{enumerate}

\end{enumerate}

\end{document}
