\documentclass[11pt]{article}
\usepackage{fullpage,amsmath,hyperref}
\begin{document}
\begin{center}\Large\bf
CS/ECE 374 A (Spring 2020)\\
{\Large Homework 1} (due Jan 30 Thursday at 10am)
\end{center}
\medskip\noindent\hrulefill\bigskip
\noindent
{\bf Instructions:} Carefully read\
\url{http://engr.course.illinois.edu/cs374/sp2020/A/hw_policies.html}
and \url{http://engr.course.illinois.edu/cs374/sp2020/A/integrity.html}.
\begin{itemize}
\item \textbf{Groups of up to three people may 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 If you are not using your real name and your
\texttt{illinois.edu} email address on Gradescope, you will need
to fill in the form linked in the course web page.
\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.
\item For any homework problem or subproblem (except for bonus questions), you can write \textbf{IDK} (``I Don't
Know'') and get 25\% of the points for that problem or subproblem. 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 may be given an
\emph{automatic zero}.
\begin{itemize}
\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 Always avoid unnecessarily long answers.
\end{itemize}
\end{itemize}
\hrulefill
\newcommand{\eps}{\varepsilon}
\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}
\newpage
\begin{description}
\item[Problem 1.1:]
Let $L\subseteq\{0,1\}^*$ be the language defined recursively
as follows:
\begin{itemize}
\item The empty string $\eps$ is in $L$.
\item For any string $x$ in $L$,
the string $1x$ is also in $L$.
\item For any strings $x,y,z$ in $L$,
the string $0x0y0z$ is also in $L$.
\item The only strings in $L$ are those that can be
obtained by the above rules.
\end{itemize}
\begin{enumerate}
\item[(a)] Prove that $L \:\subseteq\: \{ x\in\{0,1\}^*:
\mbox{$\#_0(x)$ is divisible by 3}\}$, by using induction (for example, on the length of the string). Here, $\#_0(x)$ denotes the number
of 0's in the string $x$. (As always, use \emph{strong} induction.)
\item[(b)] Prove that $\{ x\in\{0,1\}^*:
\mbox{$\#_0(x)$ is divisible by 3}\} \:\subseteq\: L$, by using induction.
\end{enumerate}
\bigskip
\item[Problem 1.2:]
A string $z\in\{0,1\}^*$ is said to be \emph{balanced} if it has exactly the same number of
0's and 1's. Let $L$ be the language consisting of all strings $x\in\{0,1\}^*$ that
contain at least one balanced substring with length at least 6. [Note: the definition would
be far less interesting if 6 is changed to 2 :-).]
For example, $11011011101\not\in L$ but $11{\bf 101100}110\in L$ (because of the bold substring).
Given a long string $x$ of length $n$, deciding whether $x\in L$ may at first seem to require a lot of effort, as there are $\Theta(n^2)$ substrings to check. But it turns out we only need to check $\Theta(n)$
substrings\ldots
More precisely, for $x\in\{0,1\}^*$, prove the following fact: $x\in L$ if and only if $x$ contains a balanced
substring of length between 6 and 11.
[Hint: in the more difficult direction, assuming that $x$ does not contain a balanced
substring of length between 6 and 11, prove that every substring $z$ with length at least 6
is unbalanced, by induction on $|z|$.]
[More Hint: it may be helpful to first prove the following observation: if $x$ is a balanced string that starts with a 0 and ends with a 0, then we can decompose $x$ as $uv$
for shorter strings $u$ and $v$ where both $u$ and $v$ are balanced. To prove this observation, let $\#_0(i)$ and $\#_1(i)$ denote the number of 0's and 1's in the first $i$ symbols of $x$, and apply the ``intermediate value theorem'' to the function $\#_0(i)-\#_1(i)$ (over $i=1,\ldots,|x|-1$)\ldots]
\bigskip
\item[Problem 1.3:]
Consider the following recurrence:
\[ T(n) \:=\: \left\{ \begin{array}{ll}
8\,T(\floor{n/3}) + 9\,T(\floor{n/9})+ 2020 & \mbox{if $n\ge 9$}\\
374 & \mbox{if $1\le n\le 8$}
\end{array} \right.
\]
Prove that $T(n)=O(n^2)$ by induction.
[Hint: you may need to use an induction hypothesis of the form
$T(n)\le cn^2 - c'$ for some constants $c$ and $c'$ to be determined.]
\end{description}
\end{document}