pep-material: comparison cws/cw03.tex

equal deleted inserted replaced

-:85f2f75abeeb
+:2d57b0d43a0f
 \begin{document}
 \section*{Coursework 8 (Scala, Regular Expressions}
-This coursework is worth 10\%. It is about regular expressions and
+This coursework is worth 10\%. It is about regular expressions,
-pattern matching. The first part is due on 30 November at 11pm; the
+pattern matching and polymorphism. The first part is due on 30
-second, more advanced part, is due on 7 December at 11pm. You are
+November at 11pm; the second, more advanced part, is due on 7 December
-asked to implement a regular expression matcher. Make sure the files
+at 11pm. You are asked to implement a regular expression matcher. Make
-you submit can be processed by just calling \texttt{scala
+sure the files you submit can be processed by just calling
-<<filename.scala>>}.\bigskip
+\texttt{scala <<filename.scala>>}.\bigskip
 \noindent
 \textbf{Important:} Do not use any mutable data structures in your
 submission! They are not needed. This excludes the use of
 \texttt{ListBuffer}s, for example. Do not use \texttt{return} in your
 \item[$\bullet$] \url{http://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016}
 \item[$\bullet$] \url{https://vimeo.com/112065252}
 \item[$\bullet$] \url{http://davidvgalbraith.com/how-i-fixed-atom/}
 \end{itemize}}
-\subsection*{Tasks (file re.scala)}
+\subsubsection*{Tasks (file re.scala)}
 \begin{itemize}
 \item[(1a)] Implement a function, called \textit{nullable}, by recursion over
 regular expressions. This function tests whether a regular expression can match
 the empty string.
 \end{center}
 For example the regular expression
 \[(r_1 + \ZERO) \cdot \ONE + ((\ONE + r_2) + r_3) \cdot (r_4 \cdot \ZERO)\]
-simplifies to just $r_1$.
+simplifies to just $r_1$. \textbf{Hints:} Regular expressions can be
-\hfill[1 Mark]
+seen as trees and there are several methods for traversing
+trees. One of them corresponds to the inside-out traversal. Also
+remember numerical expressions from school: there you had exprssions
+like $u + \ldots + (1 \cdot x) * \ldots (z + (y \cdot 0)) \ldots$
+and simplification rules that looked very similar to rules
+above. You would simplify such numerical expressions by replacing
+for example the $y \cdot 0$ by $0$, or $1\cdot x$ by $x$, and then
+look if more rules are applicable. If you organise this
+simplification in an inside-out fashion, it is always clear which
+rule should applied next.\\\mbox{}\hfill[1 Mark]
 \item[(1d)] Implement two functions: The first, called \textit{ders},
 takes a list of characters and a regular expression as arguments, and
 builds the derivative w.r.t.~the list as follows:
 You need to copy all the code from \texttt{re.scala} into
 \texttt{re2.scala} in order to complete Part 2.  Parts (2a) and (2b)
 give you another method and datapoints for testing the \textit{der}
 and \textit{simp} functions from Part~1.
-\subsection*{Tasks (file re2.scala)}
+\subsubsection*{Tasks (file re2.scala)}
 \begin{itemize}
 \item[(2a)] Write a \textbf{polymorphic} function, called
 \textit{iterT}, that is \textbf{tail-recursive}(!) and takes an
 integer $n$, a function $f$ and an $x$ as arguments. This function
 \end{tabular}
 \end{center}
 Make sure you write a \textbf{tail-recursive} version of
 \textit{iterT}.  If you add the annotation \texttt{@tailrec} (see
-below) you should not get an error message.
+below) your code should not produce an error message.
 \begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm]
 import scala.annotation.tailrec
 @tailrec
 You can assume that \textit{iterT} will only be called for positive
 integers $0 \le n$. Given the type variable \texttt{A}, the type of
 $f$ is \texttt{A => A} and the type of $x$ is \texttt{A}. This means
 \textit{iterT} can be used, for example, for functions from integers
-to integers, or strings to strings.  \\ \mbox{}\hfill[2 Marks]
+to integers, or strings to strings, or regular expressions to
+regular expressions.  \\ \mbox{}\hfill[2 Marks]
 \item[(2b)] Implement a function, called \textit{size}, by recursion
 over regular expressions. If a regular expression is seen as a tree,
 then \textit{size} should return the number of nodes in such a
 tree. Therefore this function is defined as follows:
 \end{tabular}
 \end{center}
 You can use \textit{size} and \textit{iterT} in order to test how much
 the 'evil' regular expression $(a^*)^* \cdot b$ grows when taking
-successive derivatives according the letter $a$ and compare it to
+successive derivatives according the letter $a$ and then compare it to
 taking the derivative, but simlifying the derivative after each step.
 For example, the calls
 \begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm]
 size(iterT(20, (r: Rexp) => der('a', r), EVIL))
 size(iterT(20, (r: Rexp) => simp(der('a', r)), EVIL))
 \end{lstlisting}
 produce without simplification a regular expression of size of
-7340068 for the derivative after 20 iterations, while the latter is
+7340068 after 20 iterations, while the one with
+simplification gives
 just 8.\\ \mbox{}\hfill[1 Mark]
 \item[(2c)] Write a \textbf{polymorphic} function, called
 \textit{fixpT}, that takes

changeset 79	2d57b0d43a0f
parent 78	85f2f75abeeb
child 86	f8a781322499