diff -r 65731df141a5 -r 08b5ddbc7e55 cws/cw04.tex --- a/cws/cw04.tex Wed Oct 30 14:07:58 2019 +0000 +++ b/cws/cw04.tex Wed Oct 30 14:21:16 2019 +0000 @@ -106,7 +106,7 @@ This coursework is about the shunting yard algorithm by Dijkstra and a regular expression matcher by Brzozowski. The preliminary part is due on \cwNINE{} at 4pm; the core, more advanced part, is due on \cwNINEa{} -at 4pm. The preliminary part is about the shunting yard algorithm that +at 4pm. The preliminary part is about the Shunting Yard Algorithm that transforms the usual infix notation of arithmetic expressions into the postfix notation, which is for example used in compilers. In the core part, you are asked to implement a regular expression matcher based on @@ -142,7 +142,7 @@ \begin{lstlisting}[xleftmargin=1mm,numbers=none,basicstyle=\ttfamily\small] $ scala -cp re.jar -scala> import CW9a._ +scala> import CW9c._ scala> for (i <- 0 to 5000000 by 500000) { | println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL, "a" * i))) + "secs.") | } @@ -257,7 +257,7 @@ \subsubsection*{Task (file postfix2.scala)} \begin{itemize} -\item[(3)] Extend the code in (7) and (8) to include the power +\item[(3/4)] Extend the code in (7) and (8) to include the power operator. This requires proper account of associativity of the operators. The power operator is right-associative, whereas the other operators are left-associative. Left-associative operators @@ -300,9 +300,10 @@ {\small \begin{itemize} -\item[$\bullet$] \url{http://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016} +\item[$\bullet$] \url{https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019} +\item[$\bullet$] \url{https://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/} +\item[$\bullet$] \url{https://davidvgalbraith.com/how-i-fixed-atom} \end{itemize}} % Knowing how to match regular expressions and strings will let you @@ -350,7 +351,7 @@ \item[(6)] 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 xregular expression according + as arguments and calculates the derivative of a regular expression according to the rules: \begin{center} @@ -485,7 +486,7 @@ taking the derivative, but simplify the result. The sizes are given in \texttt{re.scala}. \hfill[1 Mark] -\item[(6)] You do not have to implement anything specific under this +\item[(10)] You do not have to implement anything specific under this task. The purpose here is that you will be marked for some ``power'' test cases. For example can your matcher decide within 30 seconds whether the regular expression $(a^*)^*\cdot b$ matches strings of the