
diff -r dbf9d710ce65 -r d499da29894c handouts/ho02.tex
--- a/handouts/ho02.tex	Tue Aug 31 11:49:09 2021 +0100
+++ b/handouts/ho02.tex	Fri Sep 03 23:53:31 2021 +0100
@@ -8,7 +8,7 @@
 
 \begin{document}
 \fnote{\copyright{} Christian Urban, King's College London, 
-  2014, 2015, 2016, 2017, 2018, 2019, 2020}
+  2014, 2015, 2016, 2017, 2018, 2019, 2020, 2021}
 
 
 \section*{Handout 2 (Regular Expression Matching)}
@@ -27,10 +27,13 @@
 This lecture is about implementing a more efficient regular expression
 matcher (the plots on the right below)---more efficient than the
 matchers from regular expression libraries in Ruby, Python, JavaScript
-and Java (the plots on the left). For this consider some experimental
-data: The first pair of plots shows the running time for the
-regular expression $(a^*)^*\cdot b$ and strings composed of $n$
-\pcode{a}s, like
+and Java (the plots on the left).\footnote{Have a look at KEATS: students
+last year contributed also date for the Swift and Dart languages.}\medskip
+
+\noindent
+To start with let us look more closely at the experimental data: The
+first pair of plots shows the running time for the regular expression
+$(a^*)^*\cdot b$ and strings composed of $n$ \pcode{a}s, like
 \[
 \underbrace{\pcode{a}\ldots\pcode{a}}_{n} 
 \]
@@ -147,7 +150,7 @@
 In what follows we will use these regular expressions and strings as
 running examples. There will be several versions (V1, V2, V3,\ldots)
 of our matcher.\footnote{The corresponding files are
-  \texttt{re1.scala}, \texttt{re2.scala} and so on. As usual, you can
+  \texttt{re1.sc}, \texttt{re2.sc} and so on. As usual, you can
   find the code on KEATS.}
 
 Having specified in the previous lecture what
@@ -302,7 +305,9 @@
 yourself that they actually hold. As an aside, there has been a lot of
 research about questions like: Can one always decide when two regular
 expressions are equivalent or not? What does an algorithm look like to
-decide this efficiently? So in general it is not a trivial problem.
+decide this efficiently? Surprisingly, many of such questions
+turn out to be non-trivial problems.
+
 
 \subsection*{The Matching Algorithm}
 
@@ -492,15 +497,14 @@
 
 \noindent holds, which means our algorithm satisfies the
 specification. Of course we can claim many things\ldots
-whether the claim holds any water is a different question,
-which for example is the point of the Strand-2 Coursework.
+whether the claim holds any water is a different question.
 
 This algorithm was introduced by Janusz Brzozowski in 1964, but 
 is more widely known only in the last 10 or so years. Its
 main attractions are simplicity and being fast, as well as
 being easily extendible for other regular expressions such as
 $r^{\{n\}}$, $r^?$, $\sim{}r$ and so on (this is subject of
-Strand-1 Coursework 1). 
+Coursework 1). 
 
 \subsection*{The Matching Algorithm in Scala}
 




