\documentclass[11pt]{article}
%\usepackage{pstricks,pst-node}
\usepackage{alltt,fullpage,graphics,color,epsfig,amsmath, amssymb}
\usepackage{hyperref}
\usepackage{boxedminipage}
%\newcommand{\edgee}[1]{\begin{math}\stackrel{#1}{\longrightarrow}\end{math}}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\begin{document}
\setlength{\parskip}{.1 in}
\begin{center}
\LARGE
\textbf{CS 473: Algorithms, Fall 2016}
\\[0.5ex]
\textbf{HW 0 (due Tuesday, August 30th at 8pm)}
\end{center}
\noindent
This homework contains three problems. {\bf Read the instructions for
submitting homework on the course webpage}.
\noindent {\bf Collaboration Policy:} For this home work, each student
should work {\em independently} and write up their own solutions and
submit them.
\begin{enumerate}
%----------------------------------------------------------------------
\iffalse
\item[0.] Write the sentence {\bf \em ``I understand the course policies. I worked
on this homework on my own.''} Solutions that omit this sentence will not be
graded.
\fi
\item Solve the following recurrences in the sense of
giving an asymptotically tight bound of the form $\Theta(f(n))$ where
$f(n)$ is a standard and well-known function. No proof necessary for
the first four parts; simply state the bound.
\begin{enumerate}
\item $A(n) = n^{1/3} A(n^{2/3}) + n$, $A(n) = 1$ for
$1 \le n \le 8$.
\item $B(n) = B(n/2) + \sqrt{n}$, $B(1) = 1$.
\item $C(n) = 3C(n-1) + 1$, $C(1) = 0$.
\item $D(n) = 3D(n/3) + 4D(n/4) + n^3$, $D(n) = 1$ for $n \le 4$.
\item \emph{Prove} by induction that the $T(n)$ defined by the recurrence
$$T(n) = n + \frac{1}{n}\sum_{i=1}^{n-1} \left(T(i) + T(n-i-1)\right)$$ with
$T(n) = 1$ for $n \le 2$ satisfies the bound $T(n) = O(n \log n)$.
\end{enumerate}
\item Let $G=(V,E)$ be directed graph with non-negative edge lengths
where $\ell(e)$ denotes the length of edge $e \in E$ that represents
travel distances in a network. The nodes of the graph are
partitioned into red, blue, white and black sets denoted by $R, B,
W, K$ respectively. Describe an algorithm that given two distinct
nodes $s,t \in V$ finds a shortest walk that contains at least one
red, one blue and one white node. You should give a {\em reduction}
from this problem to solving a shortest path problem in a directed
graph; that is, assume that you have access to an algorithm that given
a directed edge-weighted graph $H$ and two nodes $u,v$ computes a
$u$-$v$ shortest path (for instance Dijkstra's algorithm accomplishes this).
Do \emph{not} describe a customized algorithm. You need to prove the
correctness of your reduction.
\item Consider the standard balls and bins process. A
collection of $m$ identical balls are thrown into $n$ bins: each
ball is thrown independently into a bin chosen uniformly at random.
\begin{enumerate}
\item What is the (precise) probability that a particular bin $i$
contains exactly $k$ balls at the end of the experiment? Let $X$
be the (random) number of bins that contain exactly $k$ balls.
What is the expected value of $X$?
\item What is the variance of $X$?
\item Consider the same experiment but with $m=n$. Now balls and
bins are numbered from $1$ to $n$. We say that there is a match in
bin $i$ if at the end of the experiment it contains the ball
numbered $i$ (it could contain other balls as well). What is the
probability that there are exactly $k$ matches?
\end{enumerate}
Explain your calculations when you derive the bounds.
\end{enumerate}
\newpage
{\bf The remaining problems are for self study. Do \emph{NOT} submit for grading.}
\begin{itemize}
\item Sort the following functions from asymptotically smallest
to asymptotically largest. Your answer should be a sorted list. Note that
there may be ties.
\[
\begin{array}{cccc}
\ln \ln n & (\sqrt{3})^{\lg n} & n^{1+1/\lg n} & e^{\ln \ln n} \\
&&&\\
\sqrt{n} & H_n & 4^{H_n} & n^{1.2} \\
&&&\\
\lg^{\lg n} n & n^n & n! & (1+1/n)^{3n \ln n}
\end{array}
\]
To jog your memory: $\lg n = \log_2 n$ and $\ln n = \log_e n$ and
$H_n = \sum_{i=1}^n 1/i \simeq \ln n + 0.577215\ldots$
is the $n$'th harmonic number.
\item Let $G=(V,E)$ be an undirected and connected graph.
Fix a vertex $u \in V$. Let ${\cal T}_1$ be the set of all spanning
trees that can be obtained by doing a depth first search (DFS) in
$G$ starting with $u$. Note that there are multiple DFS trees
possible because of the choice available in exploring the neighbors
of a node. And let ${\cal T}_2$ be the set of all spanning trees
that can be obtained by doing a breadth first search (BFS) starting
with $u$. Prove that there are trees $T_1 \in {\cal T}_1$ and $T_2
\in {\cal T}_2$ such that $T_1=T_2$ (in the sense that they have the
same set of edges) if and only if $G$ is a tree. {\em Hint: Understand how
DFS and BFS explore the graph if it is a simple cycle.}
\item A standard priority queue data structure stores keys
that have associated priorities and supports two basic operations:
insertion of a key with a given priority, and extracting a key with
the highest priority. Priority queues can be implemented at the
cost of $O(\log n)$ per operation where $n$ is the number of
keys stored in the data structure. In some applications
the number of distinct priorities, $k$, is often very small compared
to the number of keys and the parameter $k$ is often known
in advance. Design a modified priority queue data structure that
supports insertions and extract in $O(\log k)$ time per
operation. Your data structure knows $k$ in advance and should
report an error if more than $k$ distinct priorities are inserted
into it at any point. You should assume that when exctracting a key
with highest priority it does not matter which of the keys with that
priority is returned. {\em Hint: combine a standard priority queue
with an auxiliary standard data structure.}
\item See Homework 0 from Spring 2016 taught by Jeff Erickson.
\url{https://courses.engr.illinois.edu/cs473/sp2016/hw/hw0.pdf}.
\end{itemize}
\end{document}