cws/cw03.tex
changeset 156 cc6d036401f4
parent 155 371acb50643d
child 157 15f1fca879c5
--- 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