\documentclass[12pt]{article}%
\usepackage{374} %
\usepackage{374_extra} %
% =========================================================
\begin{document}
% \bigskip%
\noindent{\LARGE H{}W 0}%
\hfill{ Due: \textbf{Wednesday, September 6, \Year{} at 10am}}%\\
\\[-0.2cm]
{\noindent \rule{\linewidth}{0.2mm}}%
% \smallskip%
\noindent{\textbf{\Course: \CourseName, \Semester}}
\hfill\Version{3.0}%
\\[-0.2cm]
{\noindent \rule{\linewidth}{0.4mm}}%
\bigskip%
\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.
\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).
\item You are \emph{not} required to sign up on Gradescope (or
Piazza) with your real name and your illinois.edu email address;
you may use any email address and alias of your choice. However,
to give you credit for the homework, we need to know who
Gradescope thinks you are. \textbf{Please fill out the web form
linked from the course web page.}
\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.
\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.
\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 Never use weak induction.
\item Always give credit to outside sources! (Yes, we are not
good in counting.)
\end{compactitem}
\end{compactitem}
\bigskip \hrule
\vfill
\begin{center}
\large \textbf{See the course web site for mo
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}{Repeat that.}{
\begin{questions}%[(A)]
\item Let $x_1, \ldots, x_n$ be a sequence of integer
numbers, such that $\alpha \leq x_i \leq \beta$, for all
$i$, where $\alpha,\beta$ are some integer numbers. Prove
that there are at least $\ceil{n/(\beta-\alpha+1)}$ numbers
in this sequence that are all equal.
\item Let $\Graph=(\Vertices,\Edges)$ be an undirected
graph. Unless we say otherwise, a graph has no loops or
parallel edges. Prove, using (A), that if
$|\Vertices| \ge 2$ there are two distinct nodes $u$ and
$v$ such that degree of $u$ is equal to degree of $v$.
Recall that the degree of a node $x$ is the number of edges
incident to $x$.
\item Prove that if all vertices in $\Graph$ are of degree
at least one, then there is a (simple) path between two
distinct nodes $u$ and $v$ such that degree of $u$ is equal
to degree of $v$.
\end{questions}
}{}{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\medskip
\item \HWProblem{100}{Mix this.}{%
The \emph{sort}, $w^s$, of a string $w \in \brc{\Sym0,\Sym1}^*$
is obtained from $w$ by sorting its characters. For example,
$\Sym{010101}^s = \Sym{000111}$. The sort function is formally
defined as follows:
\[
w^s := \begin{cases}
\epsilon & \text{if $w=\epsilon$}\\
\Sym0 x^s & \text{if $w = \Sym0 x$}\\
x^s \Sym1 & \text{if $w = \Sym1 x$} \\
\end{cases}
\]
The \emphi{merge} function, evaluated in order from top to
bottom, is
\[
m(x,y) := \begin{cases}
y & \text{if $x=\eps$}\\
x & \text{if $y=\eps$}\\
\Sym0 m(x',y) & \text{if $x = \Sym0 x'$}\\
\Sym0 m(x,y') & \text{if $y = \Sym0 y'$}\\
\Sym1 m(x',y) & \text{if $x = \Sym1 x'$} \\
\end{cases}
\]
For example, we have $m(\Sym{10}, \Sym{10}) = \Sym{1010}$,
$m(\Sym{10}, \Sym{010}) = \Sym{01010}$, and
$m(\Sym{010}, \Sym{0001100}) = \Sym{0000101100}$.
For a string $x \in \{\Sym{0}, \Sym{1}\}^*$, let
$\#_{\Sym{0}}(x)$ and $\#_{\Sym{1}}(y)$ be the number of
$\Sym{0}$s and $\Sym{1}$s in $x$, respectively. For example,
$\#_{\Sym{0}}(\Sym{0101010}) = 4$ and
$\#_{\Sym{1}}(\Sym{0101010}) = 3$.
\begin{questions}%[(A)]
\item (\textbf{Not for submission.}) Prove by induction
that for any string $w \in \{\Sym{0},\Sym{1}\}^*$ we have
that $w^s \in \Sym{0}^* \Sym{1}^*$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\medskip%
\item Prove by induction that for any string
$w \in \{\Sym0,\Sym1\}^*$ we have that
$\#_\Sym{0}(w) = \#_\Sym{0}(w^s)$. Conclude that
$\#_\Sym{1}(w) = \#_\Sym{1}(w^s)$ and $|w| = \abs{w^s}$,
for any string $w$.
\medskip%
\item Prove by induction that for any two strings
$x,y \in \{\Sym0,\Sym1\}^*$ we have that
\begin{align*}
\#_{\Sym{0}}\pth{ m(x,y)} = \#_{\Sym{0}}(x) +
\#_{\Sym{0}}(y).
\end{align*}
\Hint{Do induction on $|x| + |y|$.}
Conclude that
$\#_{\Sym{1}}\pth{ m(x,y)} = \#_{\Sym{1}}(x) +
\#_{\Sym{1}}(y)$. and $\abs{m(x,y)} = \abs{x} + \abs{y}$.
[This part is somewhat tedious if you write carefully all
the details out explicitly. Avoid repetition by stating
that you are (essentially) repeating an argument that was
already seen in the proof.]
\medskip%
\item Prove by induction that for any two strings $x,y$ of
the form $\Sym{0}^* \Sym{1}^*$, we have that $m(x,y)$ is of
the form $\Sym{0}^* \Sym{1}^*$.
\medskip%
\item Prove (using the above) that
$(x \Cdot y)^s = m(x^s, y^s)$ for all strings
$x, y \in \brc{\Sym{0},\Sym{1}}^*$.
\end{questions}
}{}{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\medskip%
\newcommand{\bu}{\bf u}%
\newcommand{\bv}{\bf v}%
\item \HWProblem{100}{Walk on the grid.}{%
Let $p_0=(x_0,y_0)$ be a point on the positive integer grid
(i.e., $x_0, y_0$ are positive integer numbers). A point
$(x,y)$ is \emphi{good} if $x=y$ or $x=0$ or $y=0$. For a point
$p=(x,y)$ its \emphi{successor} is defined to be
\begin{align*}
\alpha(p)
=
\begin{cases}
(x,y-x -1) & y > x \qquad \text{(vertical move)}\\
(x-y - 1,y) & x> y \qquad \text{(horizontal move).}
\end{cases}
\end{align*}
Consider the following sequence $W(p_0) = p_0, p_1, \ldots$
computed for $p_0$. In the $i$\th stage of computing the
sequence, if $p_{i-1}$ is good then the sequence is done as we
arrived to a good location. Otherwise, we set
$p_i = \alpha(p_{i-1})$.
\begin{questions}%[(A)]
\item Prove, by induction, that starting with any point $p$
on the positive integer grid, the sequence $W(p)$ is finite
(i.e., the algorithm performs a finite number of steps
before stopping).
\item (Harder.) Given such a sequence, every step between
two consecutive points is either a vertical or a horizontal
move. A \emphi{run} is a maximal sequence of steps in the
walk that are the same (all vertical or all
horizontal). Prove that starting with a point $p =(x,y)$
there are at most $O( \log x + \log y)$ runs in the
sequence $W(p)$.
\end{questions}
}{}{}{}
\end{questions}
\end{document}