\documentclass[12pt]{article}
\usepackage[margin=1in]{geometry} 
\usepackage{amsmath,amsthm,amssymb,amsfonts}
\usepackage{graphicx,epstopdf,fancyhdr,xspace,algorithm,algorithmic}
\usepackage[space]{grffile}
\pagestyle{fancy}
\usepackage{epsfig}
\usepackage[space]{grffile}
\usepackage{titlesec}
\usepackage[table,dvipsnames]{xcolor}
\usepackage{enumitem} 
\usepackage{tikz}
\usetikzlibrary{arrows,automata}
\cfoot{\thepage}
\usepackage{multicol}
\usepackage{hyperref}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    filecolor=magenta,      
    urlcolor=cyan,
}
 

\usepackage{thmtools}
\theoremstyle{definition}
\newtheorem{problem}{Problem}
\newtheorem{claim}{Claim}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{observation}{Observation}
\newtheorem{question}{Problem}
\newenvironment{solution}{\bigskip\noindent{\it Solution.}  \ignorespaces}{\hfill\qed}

\declaretheoremstyle[
    headfont=\bfseries\sffamily\color{ForestGreen!70!black}, bodyfont=\normalfont,
    mdframed={
        linewidth=2pt,
        rightline=false, topline=false, bottomline=false,
        linecolor=ForestGreen, backgroundcolor=ForestGreen!5,
    }
]{thmgreenbox}
\declaretheorem[style=thmgreenbox, name=Hint,numbered=no]{hint}
\declaretheorem[style=thmgreenbox, name=Technical Clarification,numbered=no]{technical}

\declaretheoremstyle[
    headfont=\bfseries\sffamily\color{darkgray!70!black}, bodyfont=\normalfont,
    mdframed={
        linewidth=2pt,
        rightline=false, topline=false, bottomline=false,
        linecolor=darkgray, backgroundcolor=darkgray!5,
    }
]{thmgraybox}
\declaretheorem[style=thmgraybox, name=Statement]{statement}

\declaretheoremstyle[
    headfont=\bfseries\sffamily\color{Goldenrod!70!black}, bodyfont=\normalfont,
    mdframed={
        linewidth=2pt,
        rightline=false, topline=false, bottomline=false,
        linecolor=Goldenrod, backgroundcolor=Goldenrod!5,
    }
]{thmyellowbox}
\declaretheorem[style=thmyellowbox, name=Fun Fact,numbered=no]{funfact}

\renewcommand{\epsilon}{\varepsilon}
\newcommand{\N}{\mathbb N} 

\titleformat*{\section}{\large\bfseries}

\urlstyle{same}
\PassOptionsToPackage{hyphens}{url}
\newcommand{\homework}[6]{
   \pagestyle{myheadings}
   \thispagestyle{plain}
   \newpage
   \setcounter{page}{1}
   \noindent
   \begin{center}
   \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.28in { {\bf CS256:~Algorithm Design and Analysis \hfill} }
       \vspace{6mm}
       \hbox to 6.28in { {\Large \hfill #1 \normalsize{(#2)}  \hfill} }
       \vspace{6mm}
     \hbox to 6.28in { {\it Instructor: #3 \hfill } }
       %\hbox to 6.28in { {\it TA: #4  \hfill #6}}
   %   \vspace{2mm}
   }
   }
   \end{center}
   \markboth{#1}{#1}
   \vspace*{4mm}
}
\definecolor{grayX}{gray}{0.95}

\begin{document}
\homework{Assignment 1}{due 2/14/24}{Sam McCauley}{}{}{}
 

\bigskip

\noindent
\LaTeX{} typesetting is worth 5 points on this assignment.



\subsection*{Time Complexity}

\begin{question}[10 points]
Take the following list of functions and arrange them in ascending order of growth rate.  That is, if function $f(n)$ and $g(n)$ are such that $f(n)$ is $O(g(n))$, then $g(n)$ must immediately follow $f(n)$ in your list seperated by a comma.  If two functions have asymptotically the same order, that is,
$f(n) = \Theta(g(n))$, then indicate that explicitly and place them at the same index in your list.  For full credit, you must give a brief justification for the ordering of {\em each adjacent pair}. 

To be clear: your solution should be an ordering of (a), \ldots (k).  You should also label every adjacent pair in the ordering; first briefly explaining why your solution is accurate, and also stating if the adjacent pair has asymptotically the same order.  Thus, overall, your solution should consist of 1 ordering, as well as 9 explanations.

\paragraph{Note.} 
All $\log$s are base $2$. You may find that sometimes instead of comparing $f(n)$ and $g(n)$ directly, it is easier to compare $\log (f(n))$ and $\log (g(n))$). As $\log(x)$ is a strictly increasing function for $x>0$, $\log (f(n)) < \log(g(n))$ implies $f(n) < g(n)$. 

\begin{multicols}{2}
\begin{enumerate}[label = (\alph*)]
\item $\log n$
\item $\log{\sqrt{n}}$
\item $\sqrt{\log n}$ 
\item $\log{(\sqrt{3^n})}$
\item $\sqrt{\log{(3^n)}}$
\end{enumerate}
\columnbreak
\begin{itemize}
\item[(g)] $4^{{\log n}}$
\item[(h)] $5^n$
\item[(i)] $n(\log n)^{3}$
\item[(j)] $n^{\frac{2}{\log n }}$
\item[(k)] $2^{n^{2}}$
\end{itemize}
\end{multicols}
\end{question}

\begin{solution}
  
\end{solution}

\newpage
\begin{question}[10 points]
  \label{gale_shapley_lower_bound}

  For any $n$, consider the following input:
  For all $1\leq i\leq n$, the preferences for $h_i$ are $s_1, s_2, \ldots, s_n$. For all $1\leq i\leq n$, the preferences for $s_i$ are $h_1, h_2, \ldots, h_n$.


  Show that for any $n$, under the above input, the \texttt{while} loop of Gale-Shapeley iterates $\Omega(n^2)$ times (in other words, the hospitals make $\Omega(n^2)$ offers).   You are not required to give a formal inductive proof---a clear English explanation suffices.  
  \bigskip

  \begin{technical}
  For this question, we will assume that the list of free hospitals is implemented using a queue, exactly as we saw in class, and assume that the queue begins with all hospitals in order $h_1,\ldots, h_n$ (so $h_1$ will be the first hospital removed from the queue).
\end{technical}
\end{question}

\begin{solution}
  
\end{solution}

\newpage

\begin{question}[10 points]
 \label{gale_shapley_best}
 Decide whether you think the following statement (Statement~\ref{best_preference_matched}) is \textsc{True} or \textsc{False}.  If the statement is true give a proof; if false give a counterexample.

\begin{statement}%
\label{best_preference_matched}
	Consider an instance of the Stable Matching problem in which there is a hospital $h$ and a student $s$ such that $h$ is ranked first on the preference list of $s$, and $s$ is ranked first on the preference list of $h$.  Then $h$ and $s$ must be matched to each other in every stable matching for the instance.
\end{statement}
\end{question}

\begin{solution}
  
\end{solution}

\newpage

\begin{question}[10 points]
(KT 3.9) There is a natural intuition that two nodes that are far apart in a communication network, i.e. separated by many hops, have a more tenuous connection than two nodes that are close together. Here is one way of making this intuition precise.

Suppose that an $n$-node undirected graph $G = (V, E)$ contains two nodes $s$ and $t$ such that the distance between $s$ and $t$ is strictly greater than $n/2$.
\begin{enumerate}[label = (\alph*)]
    \item Prove that there must exist some node $v$, not equal to either $s$ or $t$, such that deleting $v$ from $G$ destroys all $s$-$t$ paths. (In other words, show that the graph obtained from $G$ by deleting $v$ contains no path from $s$ to $t$.)
    \item Give an algorithm with running time $O(m + n)$ to find such a node $v$. 
\end{enumerate}
\end{question}

\begin{solution}
  
\end{solution}


\newpage
\begin{question}[10 points]
The diameter of a graph $G$ is the ``longest shortest path'', that is, $diam(G) = \max\{dist(u,v) : u,v \in V\}$, where $d(u,v)$ is the length of the shortest path from $u$ to $v$ in $G$.

One way to calculate the diameter is by calculating $d(u,v)$ for all pairs of vertices and finding the largest.  However, this is prohibitively expensive for large graphs, 
so some people have explored algorithms that can more quickly \emph{estimate} the diameter of the graph.  

Give a linear-time algorithm\footnote{Remember: Linear time for a graph $G = (V,E)$ means time
$O(n + m)$, where $n = |V|$ and $m =|E|$.}
that, given an undirected graph $G$, returns a diameter estimate that is always within a factor of 1/2 of the true diameter.  That is, if the true diameter is $d$, show that your algorithm returns a value $k$ where $d/2 \leq k \leq d$.  You may assume that $G$ is connected.

\begin{hint}
Let's say I know the distance from $x$ to $y$ and the distance from $y$ to $z$.  What can I say about the distance from $x$ to $z$?  
\end{hint}


\begin{funfact}
This approximation factor is not far from optimal for a linear-time algorithm: there is a conditional lower bound showing that approximating the diameter to a factor better than $3/2$ requires $\Omega(n^2)$ time. See: Liam Roditty and Virginia Vassilevska Williams.  ``Fast approximation algorithms for the  diameter  and  radius  of  sparse  graphs.'' STOC 2013.
\end{funfact}
\end{question}

\begin{solution}
  
\end{solution}


\newpage
\subsection*{Bonus Feedback Question}
Question is optional with bonus points for answering.  Feel free to add a descriptive answer.  

\begin{question}[2 point]
This problem set was:
\begin{multicols}{2}
\begin{enumerate}[noitemsep, label = (\alph*)]
    \item Just right amount of challenging, hits a good balance!
    \item Too challenging, and not in a good way.
\end{enumerate}
\columnbreak
\begin{itemize}[noitemsep]
    \item[(c)] On the easy side for now
    \item[(d)] Other (please specify)
\end{itemize}
\end{multicols}
\end{question}

\begin{solution}

\end{solution}


\end{document}
