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

\newcommand\seq[3]{#1_{#2},\ldots,#1_{#3}}

\begin{document}

\header{Homework 3}{Due Wednesday, October 5, 2022}

\begin{enumerate}
\item
Show how to decide in time $O(n\,\alpha(n))$ whether two given deterministic finite automata are equivalent (accept the same set of input strings). If you have forgotten the definition of a deterministic finite automaton from your undergrad course on automata theory, there is a link on the \href{https://www.cs.cornell.edu/courses/cs6820/2022fa/handouts.htm}{handouts page}. Assume that the alphabet size is constant. (\emph{Hint}.
 Hfr n jbexyvfg nytbevguz va pbawhapgvba jvgu havba-svaq. Gur jbexyvfg fubhyq pbagnva cnvef bs fgngrf gung ner sbeprq gb or rdhvinyrag vs gur gjb fgneg fgngrf ner.)

\item
An \emph{isolated vertex} of an undirected graph $G$ is a vertex with no incident edges. Let $B$ be any deterministic algorithm that determines from the adjacency matrix of $G$ whether $G$ has an isolated vertex. Prove that for every $n$, $B$ must make $\binom n 2$ probes of the adjacency matrix in the worst case; that is, for some graph on $n$ vertices, it must look at every potential edge. (\emph{Hint}.
 Hfr na \emph{nqirefnel nethzrag}: gung vf, cynpr n ubfgvyr nqirefnel va punetr bs pbafgehpgvat gur tencu $T$ ba gur syl va erfcbafr gb $O$'f dhrevrf va n jnl gung sbeprf $O$ gb ybbx ng rirel rqtr.)

\item
In this version of the union-find problem, we assume that path compression is used, but linking by size is not. Thus when two trees are linked, the first is always linked into the second, regardless of size.

\begin{enumerate}
\item
Starting from $n$ singleton sets, prove that if all union operations precede all find operations, then the cost of a sequence of $m$ operations is $O(m)$.

\item \emph{Self-reproducing binomial trees}. 
Suppose a binomial tree $B_k$ is created from singletons $\seq x1{2^k}$ by a sequence of $2^k-1$
union operations, then the following code is executed:
\begin{flushleft}
\ \phantom{dd}\texttt{for}\ $(i = 2^k,\ldots,n)$\ \{\\
\ \phantom{dddd}\texttt{union}($x_i$, $x_{i+1}$);\\
\ \phantom{dddd}\texttt{find}($y_i$);\\
\ \phantom{dd}\}
\end{flushleft}
where at each iteration, $y_i$ is the leaf at maximum distance
from the root in the tree rooted at $x_i$. Prove that at each iteration,
the cost of the find operation is $\Omega(k)$.

\item
Using the previous result, prove a lower bound of $\Omega(m\log m)$ on the worst-case cost of a sequence of $m$ operations. (\emph{Hint}.
 Hfr na nzbegvmrq nanylfvf.)
\end{enumerate}

\end{enumerate}

\end{document}
