\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-02-02 10:00}}%
	{Problem Set \#0}

Some reminders about logistics.  See the course webpage for full details.

\begin{itemize}

	\item \textbf{Submission Policy:} Submit psets via gradescope.  Student psets must obey the following constraints:
		\begin{itemize}
			\item Each problem starts on its own page.
			\item The first page has the following metadata:
				\begin{itemize}
					\item author(s) of the problem set
						\begin{itemize}
							\item name(s)
							\item netid(s)
						\end{itemize}
					\item pset number
					\item list of collaborators
				\end{itemize}
		\end{itemize}

	\item \textbf{Collaboration Policy:} For \emph{this} problem set, each student must work independently and submit their \emph{own} solutions.  For the \emph{remaining} problem sets, students are allowed to work in groups of up to three.

	\item \textbf{Late Policy:} Late psets are not accepted.  Instead, several lowest-scoring pset problems will be dropped from a students score.

\end{itemize}

All problems are of equal value.

\begin{enumerate}

	\item Solve the following recurrences, by giving an asymptotically tight bound of the form $\Theta(f(n))$ where $f(n)$ is a standard and well-known function.  Assume as a base case that $T(n)=2$ for $n\le 16$.  No proofs are necessary.
		\begin{enumerate}
			\item $T(n)=3T(\nicefrac{n}{3})+n$.
			\item $T(n)=5T(n-3)+7$.
			\item $T(n)=n^{\nicefrac{1}{2}}T(n^{\nicefrac{1}{2}})+n$.
			\item $T(n)=T(\nicefrac{n}{3})+n$.
			\item $T(n)=4T(n^{\nicefrac{1}{3}})+\log n$.
		\end{enumerate}

		\emph{Hint:}  For a review on how to solve recurrences, see Kleinberg-Tardos \S 5.1--5.2.

	\item French Flag Walk.  Erickson Chapter 5, Problem \#16 (\url{http://jeffe.cs.illinois.edu/teaching/algorithms/book/05-graphs.pdf}).

		\emph{Hint:}  For a review of basic graph algorithms, see Kleinberg-Tardos \S 3.

	\item A college university has $n^2$ buildings on a grid $\{1,\ldots,n\}\times\{1,\ldots,n\}$.  The grid has roads connecting adjacent grid points, that is $(i,j)$ is connected to the (at most 4) neighbors $\{(i+1,j),(i-1,j),(i,j+1,i,j-1)\}$ (some of these points may not exist, due to edge conditions).

		After a snowstorm, the university must plow the roads of snow.  A building is considered \emph{accessible} if all roads segments leading to it are cleared.  For example a building at $(1,1)$ is accessible if the road segments $(1,1)-(1,2)$ and $(1,1)-(2,1)$ are cleared.

		Suppose the university hires a new snow plow company that clears each road in the university with probability $0\le p\le 1$.

		\begin{enumerate}
			\item Calculate the expected number of roads that will be cleared.

			\item Calculate the expected number of buildings that will be accessible.

			\item Calculate the expected number of buildings that will be accessible, \emph{conditioned} on the event that exactly $n$ roads are cleared.
		\end{enumerate}

		\emph{Hint:}  For a review of probability see Kleinberg-Tardos \S13.12, and Shoup \S8.1-8.4 (\url{https://shoup.net/ntb/ntb-v2.pdf}).

\end{enumerate}

\end{document}
