pep-material: comparison cws/main

equal deleted inserted replaced

-:e9d14d58be3c
+:daf561a83ba6
 4000000: 0.99149 secs.
 4500000: 1.15395 secs.
 5000000: 1.29659 secs.
 \end{lstlisting}%$
 \subsection*{Preliminaries}
 The task is to implement a regular expression matcher that is based on
 derivatives of regular expressions. Most of the functions are defined by
 recursion over regular expressions and can be elegantly implemented
 \noindent
 The alternative regular expressions comes in two versions: one is
 binary (+ / \texttt{ALT}) and the other is n-ary ($\sum$ /
 \texttt{ALTs}). The latter takes a list of regular expressions as
-arguments.  In what follows we shall use $rs$ to stand for lists of
+argument.  In what follows we shall use $rs$ to stand for lists of
-regular expressions.  The binary alternative can be seen as an abbreviation,
+regular expressions. When the list is empty, we shall write $\sum\,[]$;
+if it is non-empty, we sometimes write $\sum\,[r_1,..., r_n]$.
+The binary alternative can be seen as an abbreviation,
 that is $r_1 + r_2 \dn \sum\,[r_1, r_2]$. As a result we can ignore the
 binary version and only implement the n-ary alternative.
 \begin{itemize}
 \item[(1)] Implement a function, called \textit{nullable}, by
 \end{tabular}
 \end{center}~\hfill[0.5 Marks]
 \item[(2)] Implement a function, called \textit{der}, by recursion over
 regular expressions. It takes a character and a regular expression
-as arguments and calculates the derivative of a regular expression according
+as arguments and calculates the \emph{derivative} of a regular expression according
 to the rules:
 \begin{center}
 \begin{tabular}{lcl}
 $\textit{der}\;c\;(\ZERO)$ & $\dn$ & $\ZERO$\\
 3) &$rs = (\sum rs_1) :: rest$ & $\dn$ & $rs_1 ::: \textrm{flatten}\;rest$\\
 4) &$rs = r :: rest$         & $\dn$ & $r :: \textrm{flatten}\;rest$ & (otherwise)\\
 \end{tabular}
 \end{center}
-The first clause just states that empty lists cannot be further
+The first clause states that empty lists cannot be further
-flattened. The second removes all $\ZERO$s from the list.
+flattened. The second removes the first $\ZERO$ from the list and recurses.
 The third is when the first regular expression is an \texttt{ALTs}, then
 the content of this alternative should be spilled out and appended
 with the flattened rest of the list. The last case is for all other
 cases where the head of the list is not $\ZERO$ and not an \texttt{ALTs},
 then we just keep the head of the list and flatten the rest.
 The last case is as follows: first apply $simp$ to all regular
 expressions $r_1,.. ,r_n$; then flatten the resulting list using
 \texttt{flts}; finally remove all duplicates in this list (this can be
 done in Scala using the function
-\texttt{\_.distinct}). \textcolor{red}{When you perform these
+\texttt{\_.distinct}). When you perform these
 operations, you end up with three cases, namely where the list is
 empty, contains a single element and ``otherwise''. These cases
-should be processed as follows}
+should be processed as follows
 \begin{center}
-\textcolor{red}{\begin{tabular}{l@{\hspace{4mm}}c@{\hspace{4mm}}ll}
+\begin{tabular}{l@{\hspace{4mm}}c@{\hspace{4mm}}ll}
 $\sum\;[]$ & $\mapsto$ & $\ZERO$\\
 $\sum\;[r]$ & $\mapsto$ & $r$\\
 $\sum\;rs$ & $\mapsto$ & $\sum\;rs$ & ``otherwise''\\
-\end{tabular}}
+\end{tabular}
 \end{center}
 For example the regular expression
 than your off-the-shelf matcher in your bog-standard language.
 \begin{center}
 \begin{tabular}{@{}cc@{}}
 \multicolumn{2}{c}{Graph: $(a^*)^*\cdot b$ and strings
-$\underbrace{a\ldots a}_{n}$}\bigskip\\
+$\underbrace{a\ldots a}_{n}$}\medskip\\
 \begin{tikzpicture}
 \begin{axis}[
 xlabel={$n$},
 x label style={at={(1.05,0.0)}},
 ymax=45,
 ytick={0,5,...,40},
 scaled ticks=false,
 axis lines=left,
 width=6cm,
-height=5.0cm,
+height=5.5cm,
 legend entries={Python, Java 8, JavaScript, Swift, Dart},
 legend pos=north west,
 legend cell align=left]
 \addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
 \addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
 ymax=45,
 ytick={0,5,...,40},
 scaled ticks=false,
 axis lines=left,
 width=6cm,
-height=5.0cm,
+height=5.5cm,
 legend entries={Java 9},
 legend pos=north west]
 \addplot[cyan,mark=*, mark options={fill=white}] table {re-java9.data};
 \end{axis}
 \end{tikzpicture}

changeset 424	daf561a83ba6
parent 418	fa7f7144f2bb
child 425	957808dcb367