\documentclass[11pt]{article}
\usepackage{fullpage,amsmath,hyperref}
\begin{document}
\begin{center}\Large\bf
CS/ECE 374 A (Spring 2024)\\
{\Large Homework 1} (due Jan 25 Thursday at 10am)
\end{center}
\medskip\noindent\hrulefill\bigskip
\noindent
{\bf Instructions:} Carefully read\
\url{https://courses.grainger.illinois.edu/cs374al1/sp2024/hw_policies.html}
and \url{https://courses.grainger.illinois.edu/cs374al1/sp2024/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 Any homework or exam
solution that breaks any of the following rules could be given a
\emph{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}
\newcommand{\ceil}[1]{\left\lceil#1\right\rceil}
\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 strings $1x01$ and $11x0$ are also in $L$.
\item For any strings $x,y$ such that $xy$ is in $L$,
the string $x011y$ is also in $L$.
(In other words, inserting $011$ anywhere to a string in $L$
yields another string in $L$.)
\item The only strings in $L$ are those that can be
obtained by the above rules.
\end{itemize}
\newcommand{\Ldouble}{L_{\mbox{\scriptsize\rm double}}}
Define $\Ldouble=\{ x\in\{0,1\}^*: \#_1(x) = 2\#_0(x)\}$, where $\#_a(x)$ denotes the number of
occurrences of the symbol $a$ in the string $x$.
\begin{enumerate}
\item[(a)] Prove that $L \subseteq \Ldouble$, by using induction. (You should use \emph{strong} induction.)
\item[(b)] Conversely, prove that $\Ldouble\subseteq L$, by using induction.
[Hint: What does a string that does not contain $011$ as a substring look like?
It may be helpful to decompose the string into blocks of 0's and 1's (i.e., write it as $0^{i_1}1^{j_1}0^{i_2}1^{j_2}\cdots 0^{i_k}1^{j_k}$ with $i_1,j_1,\ldots,i_k,j_k\ge 1$, if it starts with a 0 and ends with a 1; and similarly for the other cases).]
\end{enumerate}
\bigskip
\item[Problem 1.2:]
Consider the following recurrence:
\[ T(n) \:=\: \left\{ \begin{array}{ll}
2\,T(\floor{2n/3}) + 11\,T(\floor{n/3})+ 2024n+374 & \mbox{if $n\ge 3$}\\
5 & \mbox{if $n=1$ or $n=2$}
\end{array} \right.
\]
Prove that $T(n)=O(n^3)$ by induction.
[Hint: try an induction hypothesis of the form
$T(n)\le cn^3 - c'n-c''$ for some constants $c,c',c''$ to be determined.]
\end{description}
\end{document}