diff -r 371acb50643d -r cc6d036401f4 cws/cw03.tex --- a/cws/cw03.tex Fri Nov 24 03:10:23 2017 +0000 +++ b/cws/cw03.tex Fri Nov 24 08:58:11 2017 +0000 @@ -57,8 +57,8 @@ December at 11pm. In the first part, you are asked to implement a regular expression matcher based on derivatives of regular expressions. The reason is that regular expression matching in Java -can sometimes be extremely slow. The advanced part is about an -interpreter for a very simple programming language.\bigskip +and Python can sometimes be extremely slow. The advanced part is about +an interpreter for a very simple programming language.\bigskip \noindent \textbf{Important:} @@ -328,11 +328,13 @@ If you want to see how badly the regular expression matchers do in -Java and Python with the `evil' regular expression, then have a look -at the graphs below (you can try it out for yourself: have a look at -the file \texttt{catastrophic.java} on KEATS). Compare this with the -matcher you have implemented. How long can the string of $a$'s be -in your matcher and still stay within the 30 seconds time limit? +Java\footnote{Version 8 and below} and in Python with the `evil' regular +expression $(a^*)^*\cdot b$, then have a look at the graphs below (you +can try it out for yourself: have a look at the file +\texttt{catastrophic.java} and \texttt{catastrophic.py} on +KEATS). Compare this with the matcher you have implemented. How long +can the string of $a$'s be in your matcher and still stay within the +30 seconds time limit? \begin{center} \begin{tikzpicture} @@ -351,7 +353,7 @@ axis lines=left, width=6cm, height=5.0cm, - legend entries={Python, Java}, + legend entries={Python, Java 8}, legend pos=outer north east] \addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data}; \addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data}; @@ -366,8 +368,8 @@ programming language. But remember, some serious companies have built their business on Scala.\footnote{\url{https://en.wikipedia.org/wiki/Scala_(programming_language)\#Companies}} -And there are far more esoteric languages out there. One is called -\emph{brainf***}. You are asked in this part to implement an +And there are far, far more esoteric languages out there. One is +called \emph{brainf***}. You are asked in this part to implement an interpreter for this language. Urban M\"uller developed brainf*** in 1993. A close relative of this @@ -377,9 +379,9 @@ instructions in total and all of which are single characters. Despite the minimalism, this language has been shown to be Turing complete\ldots{}if this doesn't ring any bell with you: it roughly -means every algorithm we know can, in principle, be implemented in +that means every algorithm we know can, in principle, be implemented in brainf***. It just takes a lot of determination and quite a lot of -memory resources. Some relatively sophisticated example programs in +memory resources. Some relatively sophisticated sample programs in brainf*** are given in the file \texttt{bf.scala}.\bigskip \noindent