\ifx\AllTogetherMode\undefined%
\IfFileExists{../prefix.tex}%
{\input{../prefix}}%
{\input{prefix}}%
\fi
% =========================================================
\HomeworkStart%
{1} % Homework number
{2} % Week of semester submitted
{1.0} % Version
\begin{compactitem}
\item \textbf{Groups of up to three people can submit joint
solutions.} Each problem should be submitted by exactly one
person, and the beginning of the homework should clearly state the
Gradescope names and email addresses of each group member. In
addition, whoever submits the homework must tell Gradescope who
their other group members are.
\smallskip%
\item \textbf{Submit your solutions electronically on the course
Gradescope site as PDF files.} Submit a separate PDF file for
each numbered problem. If you plan to typeset your solutions,
please use the \LaTeX\ solution template on the course web site.
If you must submit scanned handwritten solutions, please use a
black pen on blank white paper and a high-quality scanner app (or
an actual scanner, not just a phone camera).
\smallskip%
\item Please sign up on Gradescope with your real name and your
\texttt{\si{illinois.edu}} email address. Failing to use your real
name and your UIUC email would lead to problems with handling your
grades. You can sign{}up to Piazza using a pseudo-name if you want
to.
\end{compactitem}
\vfill \Hr
\begin{center}
\Large \textbf{\color{red}~ Some important course policies
~}\\
\end{center}
\begin{compactitem}
\item \textbf{You may use any source at your disposal} -- paper,
electronic, or human-but you \emph{must} cite \emph{every} source
that you use, and you \emph{must} write everything yourself in
your own words. See the academic integrity policies on the course
web site for more details.
\smallskip
\item For any question, you can write \textbf{IDK} (``I Don't
Know'') and get 25\% of the points for the question. You would get
the points if and only if IDK is the only content of your
answer. Any answer containing ``IDK'' anywhere and \textbf{any}
additional text would immediately get a zero.
\smallskip
\item \textbf{Avoid the Three Deadly Sins!} Any homework or exam
solution that breaks any of the following rules will be given an
\textcolor{red}{\emph{automatic zero}}, unless the solution is
otherwise perfect. Yes, we really mean it. We are not trying to
be scary or petty (Honest!), but we do want to break a few common
bad habits that seriously impede mastery of the course material.
\begin{compactitem}\itemsep0pt
\item Always give complete solutions, not just examples.
\item Always declare all your variables, in English. In
particular, always describe the specific problem your
algorithm is supposed to solve.
\item Short \textbf{complete} answers are better than longer
answers. Unnecessarily long answers (which by definition are
not perfect) would get zero (i.e., 0) points. Avoid empty
expressions like ``in fact'', ``as anybody, or their uncle,
can see if they think about it...'', etc.
\item Always give credit to outside sources! (Yes, we are no
good with counting.)
\end{compactitem}
\end{compactitem}
\bigskip \hrule
\vfill
\begin{center}
\large \textbf{See the course web site for more
information.}\\[1ex]\normalsize
If you have any questions about these policies,\\
please do not hesitate to ask in class, in office hours, or on
Piazza.
\end{center}
\vfill
\hrule \vfil \vfil \vfil
% ----------------------------------------------------------------------
% \headers{CS/ECE 374}{Homework 0 (due January 24)}{Spring 2017}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{questions}%[\color{red} \huge \bf 1.]%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item \HWProblem{100}%
{Greedy coloring}%
{%
Given an undirected graph $\Graph$ with $n$ vertices, the
greedy coloring algorithm order the vertices of $\Graph$ in an
arbitrary order $v_1,\ldots, v_n$. Initially all the vertices
are not colored. In the $i$\th iteration, the algorithm assigns
$v_i$ the smallest color (i.e., positive integer) $k$ such that
none of its neighbors that are already colored have color
$k$. Let $f(v_i)$ denote the assigned color to $v_i$.
\begin{questions}
\item \points{30} Prove that the above algorithm computes a
valid coloring of the graph (i.e., there are is no edge
$uv$ in $\Graph$ such that $f(u)=f(v)$).
\item \points{30} Prove that if a vertex $v$ is colored by
color $k$, then there is a simple path in the graph
$u_1, u_2, \ldots, u_k=v$, such that for $i=1,\ldots, k$,
we have $f(u_i)=i$ (and $u_iu_{i+1} \in \EdgesX{\Graph}$
for all $i$).
\item \points{40} Prove that $\Graph$ either have a simple
path of length $\floor{\sqrt{n}}$, or alternatively,
$\Graph$ contains an independent set of size
$\floor{\sqrt{n}}$. A set of vertices
$X \subseteq \VX{\Graph}$ is \emphi{independent} if no two
vertices $x,y \in X$ form an edge in $\Graph$.
\end{questions}
}{}{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item \HWProblem{100}{Prefix it.}%
{%
Let $L \subseteq \{\T0,\T1\}^*$ be a language defined as
follows:
\begin{compactenumi}
\item $\eps \in L$.
\item For all $w \in L$ we have $\T0 w \T1 \in L$.
\item For all $x,y \in L$ we have $x y \in L$.
\end{compactenumi}
And these are all the strings that are in $L$. Prove, by
induction, that for any $w \in L$, and any prefix $u$ of $w$,
we have that $\#_{\T0}(u) \geq \#_{\T1}(u)$. Here $\#_0(u)$ is
the number of $\T0$ appearing in $u$ ($\#_{\T1}(u)$ is defined
similarly). You can use without proof that
$\#_{\T0}(xy) = \#_{\T0}(x) + \#_{\T0}(y)$, for any strings
$x,y$.
}{}{}%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item \HWProblem{100}{A recurrence.}%
{%
Consider the recurrence
\begin{equation*}
T(n) =
\begin{cases}
T(\floor{n/3})
+
T(\floor{n/4})
+
T(\floor{n/5})
+
T(\floor{n/6})
+ n & n \geq 6\\
1 & n < 6.
\end{cases}
\end{equation*}
Prove by induction that $T(n) =O(n)$.
(An easier proof follows from using the techniques described in
section 3 of these notes on
\href{http://jeffe.cs.illinois.edu/teaching/algorithms/notes/99-recurrences.pdf}{recurrences}.)
}{}{}{}
\end{questions}
\HomeworkEnd{}%