\documentclass[12pt]{article}
\usepackage[letterpaper,margin=1in]{geometry}
\usepackage{amsmath,amsthm,amssymb,latexsym}
\usepackage{array,multirow,alltt,enumerate,bbm,eucal,graphicx}
\usepackage[colorlinks]{hyperref}
\usepackage{xcolor,stmaryrd,bussproofs,mathpartir}
\usepackage{tikz,pgfmath}
\usepgflibrary{shapes}
\usetikzlibrary{arrows,automata,backgrounds}

\oddsidemargin=0in
\topmargin=-1cm
\textheight=22cm
\textwidth=6.5in
\parskip=6pt
\leftmargini=3ex
\newlength\courseheader
\newcommand\header[2]{
\fboxrule=.5mm\fboxsep=1.2mm
\courseheader=\textwidth
\addtolength{\courseheader}{-4mm}
\begin{center}\framebox{\parbox\courseheader{\textbf{Analysis of Algorithms\hfill #1\\CS6820 Fall 2022\hfill #2}}}\end{center}
\vspace{5mm}
}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newcommand\reals{\mathbb R}
\newcommand\naturals{\mathbb N}
\newcommand\len[1]{|\kern1pt#1\kern1pt|}

\begin{document}

\header{Homework 1}{Due Wednesday September 7, 2022}

\begin{enumerate}
\item
Let $S\subseteq\reals^2$, $\len S=n$. Show how to find a pair of points in $S$ of minimum Euclidean distance in time $O(n\log n)$. You may assume constant-time arithmetic and comparison of real numbers.

\item
Let $d\in\naturals$ be a fixed constant. Let $G=(V,E)$ be a connected undirected graph with edge weights $w:E\to\naturals$ such that all simple\footnote{no repeated vertices} cycles of $G$ are of length at most $d$.  Show how to find a minimum-weight spanning tree in linear time.  You may use the following facts from class without proof.

\vspace{-1em}
\paragraph{Lemma 1}
If $e$ is a minimum-weight edge crossing some cut, then there exists a minimum-weight spanning tree containing $e$.

\vspace{-1em}
\paragraph{Lemma 2}
If $e$ is a maximum-weight edge in some cycle, then there exists a minimum-weight spanning tree that does not contain $e$.

(\emph{Hint}.  $O(dm)$ is possible.  Do a modified depth-first search.  Do something interesting when either (i) you see a previously visited node, or (ii) you cannot proceed downward.)

\item
We would like a data structure \texttt{UninitializedArray} that supports the following operations:
\begin{flushleft}
\begin{tabular}{ll}
$\mathtt{new}(n)$ & creates a new \texttt{UninitializedArray} of length $n$\\
$\mathtt{isInitialized}(k)$ & returns \texttt{true} iff the element $k$ has been initialized\\
$\mathtt{insert}(k,d)$ & inserts datum $d$ into position $k$ of the array
\end{tabular}
\end{flushleft}
Show how to implement this data structure so that each of these operations can be performed in constant time independent of $n$ and $k$.  You may assume constant-time allocation of array storage.  Constant-time integer operations on memory addresses are permitted, and you may use additional memory freely.

\item
\href{https://www.cs.cornell.edu/courses/cs6820/2022fa/Handouts/CLRSbiconnected.pdf}{Here} you will find a series of exercises from CLRS\footnote{Corman, Leiserson, Rivest, and Stein, \emph{Introduction to Algorithms}} regarding the biconnected components of an undirected graph $G = (V,E)$. Read it over to get familiar with the problem. Here we take a somewhat different approach.
\begin{enumerate}
\item
Define a relation $\sim$ on edges: $e_1\sim e_2$ if either $e_1=e_2$ or $e_1$ and $e_2$ lie on a common simple\footnotemark[1] cycle. Prove that $\sim$ is an equivalence relation.
\item
We define a \emph{biconnected component} to be an equivalence class of $\sim$, a \emph{bridge} to be a singleton equivalence class, and an \emph{articulation point} to be a vertex adjacent to edges in two or more equivalence classes. Argue that these definitions are equivalent to CLRS's. (The treatment of CLRS assumes the given graph is connected, but we can ease this assumption by replacing all occurrences of ``\ldots whose removal disconnects $G$'' with ``\ldots whose removal increases the number of connected components of $G$.'')
\item
Let $(u,v)$, $(v,w)$ be adjacent (directed) tree edges in a DFS tree of $G$. Argue that $(u,v)\sim(v,w)$ iff there is a back edge from a descendant\footnote{The descendants and ancestors of a node are usually assumed to include the node itself. Use the adjective \emph{proper} if you don't want that.} of $w$ to an ancestor\footnotemark[3] of $u$.
\item
Show that every $\sim$-class has a unique edge of minimum depth (distance from the root) in the DFS tree. This edge can serve as a canonical representative of its $\sim$-class.
\item
Give a linear-time algorithm for finding all such edges. This is essentially the same as CLRS 23.2(h).
\end{enumerate}

\end{enumerate}
\end{document}
