# HG changeset patch
# User Christian Urban <urbanc@in.tum.de>
# Date 1479986738 0
# Node ID 6024381415cb166377531aecd6e6cbdf1205f5a9
# Parent  f1295a0ab4ed7d3bbf1faf0c42ea0175130f99f5
updated

diff -r f1295a0ab4ed -r 6024381415cb progs/catastrophic.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/catastrophic.java	Thu Nov 24 11:25:38 2016 +0000
@@ -0,0 +1,40 @@
+// a case of catastrophic backtracking in Java
+//
+// regexp: (a*)*b
+// strings: aa....
+
+import java.util.regex.*;
+
+public class catastrophic {
+    public static void main(String[] args) {
+
+        //we always run all the tests twice -> warmup of the JVM
+        for (int runs = 0; runs < 2; runs++) {
+            
+            Pattern pattern = Pattern.compile("(a*)*b");
+            
+            // Run from 5 to 28 characters
+            for (int length = 5; length < 28; length++) {
+                
+                // Build input of specified length
+                String input = "";
+                for (int i = 0; i < length; i++) { input += "a"; }
+                
+                // Measure the average duration of two calls...  
+                long start = System.nanoTime();
+                for (int i = 0; i < 2; i++) {
+                    pattern.matcher(input).find();
+                }
+                
+                System.out.println(length + " " + input + ": " 
+                       + ((System.nanoTime() - start) / 2000000000d) 
+                       + "s");
+            }
+        }
+    }
+} 
+
+
+
+// javac catastrophic.java 
+// java catastrophic
diff -r f1295a0ab4ed -r 6024381415cb slides/slides03.pdf
Binary file slides/slides03.pdf has changed
diff -r f1295a0ab4ed -r 6024381415cb slides/slides03.tex
--- a/slides/slides03.tex	Thu Nov 24 10:41:42 2016 +0000
+++ b/slides/slides03.tex	Thu Nov 24 11:25:38 2016 +0000
@@ -240,7 +240,7 @@
 \end{axis}
 \end{tikzpicture}}
   &
-\begin{tikzpicture}
+\onslide<2>{\begin{tikzpicture}
   \begin{axis}[
     xlabel={$n$},
     x label style={at={(1.05,0.0)}},
@@ -255,7 +255,7 @@
 %%\addplot[green,mark=square*,mark options={fill=white}] table {re2a.data};    
 \addplot[red,mark=square*,mark options={fill=white}] table {re3a.data};
 \end{axis}
-\end{tikzpicture}
+\end{tikzpicture}}
 \end{tabular}
 \end{center}
 
@@ -289,6 +289,29 @@
 
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
+
+\begin{frame}[c]
+\frametitle{Marks for CW6 (Part 1)}
+
+Absolute raw marks, alleged collusions still included:
+
+\begin{itemize}
+\item 0\%: 18 students
+\item 1\%: 2
+\item 2\%: 11
+\item 3\%: 29
+\item 4\%: 18
+\item 5\%: 33
+\item 6\%: 55
+\item 7\%: 62 
+\end{itemize}  
+\end{frame}
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
 \end{document}