\documentclass[12pt,a4paper]{article}
\usepackage{ctex}
\usepackage{amsmath,amscd,amsbsy,amssymb,latexsym,url,bm,amsthm,mathrsfs}
\usepackage{epsfig,graphicx,subfigure}
\usepackage{enumitem,balance,mathtools}
\usepackage{wrapfig}
\usepackage{mathrsfs, euscript}
\usepackage[usenames]{xcolor}
\usepackage{hyperref}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{exercise}{Exercise}[section]
\newtheorem*{solution}{Solution}

\numberwithin{equation}{section}

\renewcommand{\thefootnote}{\fnsymbol{footnote}}

\newcommand{\postscript}[2]
 {\setlength{\epsfxsize}{#2\hsize}
  \centerline{\epsfbox{#1}}}

\renewcommand{\baselinestretch}{1.0}

\setlength{\oddsidemargin}{-0.365in}
\setlength{\evensidemargin}{-0.365in}
\setlength{\topmargin}{-0.3in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\textheight}{10.1in}
\setlength{\textwidth}{7in}
\makeatletter \renewenvironment{proof}[1][Proof] {\par\pushQED{\qed}\normalfont\topsep6\p@\@plus6\p@\relax\trivlist\item[\hskip\labelsep\bfseries#1\@addpunct{.}]\ignorespaces}{\popQED\endtrivlist\@endpefalse} \makeatother
\makeatletter
\renewenvironment{solution}[1][Solution] {\par\pushQED{\qed}\normalfont\topsep6\p@\@plus6\p@\relax\trivlist\item[\hskip\labelsep\bfseries#1\@addpunct{.}]\ignorespaces}{\popQED\endtrivlist\@endpefalse} \makeatother
\begin{document}
\noindent

%========================================================================
\noindent\framebox[\linewidth]{\shortstack[c]{
\Large{\textbf{Lab13-Algorithm}}\vspace{1mm}\\
CS101-�������ѧ���ۿκ���ҵ����ʦ��John Hopcroft��2016 �＾ѧ��}}
%\vspace{1mm}
\begin{center}
\footnotesize{\color{red}$*$ �ɴ�ӡ��ҳֱ����ҳ������/��ֽװ������ע����\quad ������\_\_\_\_\_\_\_\_\_\_\_\_ \quad ѧ�ţ�\_\_\_\_\_\_\_\_\_\_\_ \quad �༶��\_\_\_\_\_\_}

\footnotesize{\color{blue}$*$ ���Ӱ���ҵ��ֱ���ϴ����γ���վ}
\end{center}

Solve $3$ of the following exercises.

\begin{enumerate}
\item Lexer and Parser are important components of a Compiler. A lexer converts the source code (a sequence of characters) into a sequence of tokens (a token could be generated by a {\it Regular Expression}), and a parser converts a sequence of tokens into a parse tree (which could be generated by a {\it Context Free Grammar}).

Given the RE description of the tokens and the CFG of the programming language:
\begin{itemize}
	\item Tokens:
\begin{eqnarray*}
	\textit{assign} &: & \leftarrow \\
	\textit{left\_bracket} & : & ( \\
	\textit{right\_bracket} & : & ) \\
	\textit{operator} & : & + | - \\
	\textit{number} & : & [0-9]^{+} \\
	\textit{identifier} & : & [a-zA-Z0-9]^{+} \\
\end{eqnarray*}
 	\item CFG:
\begin{eqnarray*}
	\textbf{PROGRAM} &: & \textbf{STATEMENT}^{+} \\
	\textbf{STATEMENT} &: & \textit{identifier } \textit{assign } \textbf{EXPRESSION}\\
	\textbf{EXPRESSION} &: & \textit{identifier} \\ & | & \textit{number} \\ & | & \textit{left\_bracket } \textbf{EXPRESSION } \textit{right\_bracket} \\ & | & \textbf{EXPRESSION } \textit{operator } \textbf{EXPRESSION}
\end{eqnarray*}
\end{itemize}


And you need to use Dynamic Programming to parse the following program:
\begin{eqnarray*}
	a&\leftarrow&1 \\
	b&\leftarrow&a - (a + a)
\end{eqnarray*}

You only need to write down the table used in DP.

{\bf HINT:} Firstly, you need to convert the CFG to a {\it Chomsky Normal Form} one.

\item Construct a {\it divide and conquer} algorithm to rearrange the sequence $1, 2, 3\cdots, n$ that satisfies there is no arithmetic subsequence with length $\geq 3$.

\item Prove the {\it Master theorem}.

\textbf{Master Theorem}: Let a be an integer greater than or equal to $1$ and b be a real number greater than $1$. Let $c$ be a positive real number and $d$ a nonnegative real number. Given a recurrence of the form
	\[T(n) = \begin{cases}
		aT(n/b) + n^c & \text{if}~ n>1\\
		d & \text{if}~n = 1
	\end{cases}
	\]
	then for $n$ a power of $b$,
	\begin{enumerate}
		\item if $\log_ba < c, T(n) = \Theta(n^c)$,
		\item if $\log_ba = c, T(n) = \Theta(n^c\log n)$,
		\item if $\log_ba > c, T(n) = \Theta(n^{\log_ba})$.
	\end{enumerate}

\item It is possible to perform multiplication of large numbers in (many) fewer operations than the usual brute-force technique of ``long multiplication". As discovered by Karatsuba in 1962, multiplication of two $n$-digit numbers $num_1$ and $num_2$ can be done with a complexity less then $O(n^2)$ using identities of the form
\[A = (a+b\cdot 10^{\lceil n / 2 \rceil}) \text{~and~} B = (c+d\cdot 10^{\lceil n / 2 \rceil}).\]
Then
\[A\cdot B= ac + [(a+b)(c+d)-ac-bd]]\cdot 10^{\lceil n / 2 \rceil} + bd\cdot 10^{n}.\]
Use the {\em Master Theorem} to give a bound of {\em Karatsuba Algorithm}.

\item Prove the {\it Cut lemma}:

\textbf{Cut Lemma}:
Let $X \subseteq T$ where $T$ is an MST (Minimum Spanning Tree) in $G(V, E)$. Let $S \subseteq V$ such that no edge in $X$ crosses
between $S$ and $V-S$; i.e., no edge in $X$ has one endpoint in $S$ and one endpoint in $V-S$.
Among edges crossing between $S$ and $V-S$, let $e$ be an edge of minimum weight. Then
$X\cup \{e\}\subseteq T'$ where $T'$ is an MST in $G(V, E)$.
\end{enumerate}



%========================================================================
\end{document}
