% !TEX program = xelatex

\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}

\usepackage{../styles/slides}

\usepackage{../styles/mygraphs}

\usepackage{../styles/langs}

%%\usepackage{../data}

\usepackage[export]{adjustbox}

\usetikzlibrary{shapes}

\hfuzz=220pt 

%\setmonofont[Scale=.88]{Consolas}

%\newfontfamily{\consolas}{Consolas}

\lstset{language=Scala,

        style=mystyle,

        numbersep=0pt,

        numbers=none,

        xleftmargin=0mm}

\newcommand{\LEFTarrow}[3]{%

\begin{textblock}{0}(#2,#3)%

\onslide<#1>{%

\begin{tikzpicture}%

\node at (0,0) [single arrow, shape border rotate=180, fill=red,text=red]{a};%

\end{tikzpicture}}%

\end{textblock}}

\newcommand{\DOWNarrow}[3]{%

\begin{textblock}{0}(#2,#3)%

\onslide<#1>{%

\begin{tikzpicture}%

\node at (0,0) [single arrow, shape border rotate=270, fill=red,text=red]{a};%

\end{tikzpicture}}%

\end{textblock}}

\newcommand{\bl}[1]{\textcolor{blue}{#1}}     

% beamer stuff 

\renewcommand{\slidecaption}{PEP (Scala) 04, King's College London}

% Swift, example (a*)*b  

\begin{filecontents}{re-swift.data}

5   0.001

10  0.001

15  0.009

20  0.178

23  1.399

24  2.893

25  5.671

26  11.357

27  22.430

\end{filecontents}

% Dart, example (a*)*b  

\begin{filecontents}{re-dart.data}

20 0.042

21 0.084

22 0.190

23 0.340

24 0.678

25 1.369

26 2.700

27 5.462

28 10.908

29 21.725

30 43.492

\end{filecontents}

\begin{filecontents}{re3a.data}

1 0.00003

500001 0.22527

1000001 0.62752

1500001 0.88485

2000001 1.39815

2500001 1.68619

3000001 1.94957

3500001 2.15878

4000001 2.59918

4500001 5.90679

5000001 13.11295

5500001 19.15376

6000001 40.16373

\end{filecontents}

\begin{filecontents}{re-python2.data}

1 0.033

5 0.036

10 0.034

15 0.036

18 0.059

19 0.084

20 0.141

21 0.248

22 0.485

23 0.878

24 1.71

25 3.40

26 7.08

27 14.12

28 26.69

\end{filecontents}

\begin{filecontents}{re-js.data}

5   0.061

10  0.061

15  0.061

20  0.070

23  0.131

25  0.308

26  0.564

28  1.994

30  7.648

31  15.881 

32  32.190

\end{filecontents}

\begin{filecontents}{re-java.data}

5  0.00298

10  0.00418

15  0.00996

16  0.01710

17  0.03492

18  0.03303

19  0.05084

20  0.10177

21  0.19960

22  0.41159

23  0.82234

24  1.70251

25  3.36112

26  6.63998

27  13.35120

28  29.81185

\end{filecontents}

\begin{filecontents}{re-java9.data}

1000  0.01410

2000  0.04882

3000  0.10609

4000  0.17456

5000  0.27530

6000  0.41116

7000  0.53741

8000  0.70261

9000  0.93981

10000 0.97419

11000 1.28697

12000 1.51387

14000 2.07079

16000 2.69846

20000 4.41823

24000 6.46077

26000 7.64373

30000 9.99446

34000 12.966885

38000 16.281621

42000 19.180228

46000 21.984721

50000 26.950203

60000 43.0327746

\end{filecontents}

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\frametitle{%

  \begin{tabular}{@ {}c@ {}}

  \\[5mm]

  \huge PEP Scala (4) 

  \end{tabular}}

  \normalsize

  \begin{center}

  \begin{tabular}{ll}

    Email:  & christian.urban at kcl.ac.uk\\

    %Office: & N\liningnums{7.07} (North Wing, Bush House)\bigskip\\

    Slides \& Code: & KEATS\bigskip\\

    Office Hour: &  Fridays 11:00 -- 12:00\\

    Location: & N7.07 (North Wing, Bush House)\bigskip\\

    Pollev: & \texttt{\alert{https://pollev.com/cfltutoratki576}}\\  \\

  \end{tabular}

  \end{center}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\begin{frame}[c]

%\frametitle{Hints in CW}

%

%\begin{center}  

%\includegraphics[scale=0.4]{../pics/hints.png}

%\end{center}

%

%\small

%\begin{itemize}

%  \item Scala Library, e.g.~\texttt{span} in \\

%  \url{https://www.scala-lang.org/api/current/scala/collection/immutable/List.html}

%\end{itemize}

%\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\begin{frame}[c]

%\frametitle{Discussion Forum}

%\begin{center}  

%\includegraphics[scale=0.38]{/Users/cu/discussion.png}

%\end{center}

%\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     

% \begin{frame}[c]

% \frametitle{Preliminary 7}

% Raw marks (261 submissions):\bigskip

% \begin{itemize}

% \item 4\%: \hspace{4mm}236

% \item 3\%: \hspace{4mm}10

% \item 2\%: \hspace{4mm}1

% \item 1\%: \hspace{4mm}0

% \item 0\%: \hspace{4mm}15 

% \end{itemize}\bigskip\bigskip  

% \footnotesize

% (plagiarism/collusion interviews ongoing!)

% \end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% \begin{frame}[c,fragile]

% \small

% \begin{lstlisting}[language=Scala, numbers=none, xleftmargin=1mm]

% def is_legal(dim: Int, p: Path, x: Pos) = {

%   if (...some_really_long_condition...) false

%   else true

% }

% \end{lstlisting}

% \pause

% \bigskip

% \rule{11cm}{0.3mm}

% \bigskip

% \begin{lstlisting}[language=Scala, numbers=none, xleftmargin=1mm]

% def is_legal(dim: Int, p: Path, x: Pos) = 

%   !(...some_really_long_condition...)

% \end{lstlisting}

% \end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% \begin{frame}[c,fragile]

% \small

% \begin{lstlisting}[language=Scala, numbers=none, xleftmargin=1mm]

% def foobar(...) = {

%   val cs = for (c <- str) yield c.toLowerCase

%   ...

% }

% \end{lstlisting}

% \pause

% \bigskip

% \rule{11cm}{0.3mm}

% \bigskip

% \begin{lstlisting}[language=Scala, numbers=none, xleftmargin=1mm]

% def foobar(...) = {

%   val cs = str.map(_.toLowerCase)

%   ...

% }

% \end{lstlisting}

% \end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% \begin{frame}[c,fragile]

% \small

% \begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-7mm]

% def RomanNumeral2Int(rs: RomanNumeral): Int = 

%  rs match { 

%    case Nil => 0

%    case M::r    => 1000 + RomanNumeral2Int(r)  

%    case C::M::r => 900 + RomanNumeral2Int(r)

%    case D::r    => 500 + RomanNumeral2Int(r)

%    case C::D::r => 400 + RomanNumeral2Int(r)

%    case C::r    => 100 + RomanNumeral2Int(r)

%    case X::C::r => 90 + RomanNumeral2Int(r)

%    case L::r    => 50 + RomanNumeral2Int(r)

%    case X::L::r => 40 + RomanNumeral2Int(r)

%    case X::r    => 10 + RomanNumeral2Int(r)

%    case I::X::r => 9 + RomanNumeral2Int(r)

%    case V::r    => 5 + RomanNumeral2Int(r)

%    case I::V::r => 4 + RomanNumeral2Int(r)

%    case I::r    => 1 + RomanNumeral2Int(r)

%  }

% \end{lstlisting}

% \end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c,fragile]

\frametitle{Last Week: Pattern Matching} 

\small

\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=3mm]

def fizz_buzz(n: Int) : String = 

  (n % 3, n % 5) match {

    case (0, 0) => "fizz buzz"

    case (0, _) => "fizz"

    case (_, 0) => "buzz"

    case _ => n.toString  

  }

\end{lstlisting}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c,fragile]

\frametitle{Last Week: Pattern Matching} 

\small

\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=3mm]

def mkeps(r: Rexp) : Val = r match {

  case ONE => Empty

  case ALT(r1, r2) => ...

  case SEQ(r1, r2) => ...

  case STAR(r) => ...

  case RECD(x, r1) => Rec(x, mkeps(r))

  ...

}

\end{lstlisting}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     

\begin{frame}[c,fragile]

\frametitle{Reverse Polish Notation}

{\Large\bl{$(3 + 1) * (2 + 9)$}}\bigskip

{\Large$\Rightarrow$}\bigskip

{\;\;\Large\bl{$3\;\;1\;+\;2\;\;9\;+\;*$}}

\begin{textblock}{3}(11,4)

\begin{onlyenv}<2>

\begin{lstlisting}[language=JVMIS]

ldc 3

ldc 1

iadd

ldc 2

ldc 9

iadd

imul

\end{lstlisting}

\end{onlyenv} 

\end{textblock}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     

% \begin{frame}[c,fragile]

% \frametitle{Sudoku}

% A very simple-minded version on 110 problems:\bigskip

% \begin{itemize}

% \item 1 core: 800 secs

% \item 2 cores: 400 secs

% \item 8 cores: 290 secs

% \item 18 cores: 142 secs

% \end{itemize}

% \end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% \begin{frame}[t]

%   \begin{center}  

%   \includegraphics[scale=0.3]{../pics/blow.png}

%   \end{center}

%   \begin{textblock}{14}(2,11.4)

%   \large\bf{}Mind-Blowing Regular Expressions:\\ 

%   \centering in Python, JavaScript, Java

%   \end{textblock}

% \end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c,fragile]

\frametitle{Regular Expressions} 

Suppose you have the regular expression 

\only<1-3>{\alert{\texttt{(a*)b}}}%

\only<4->{\alert{\texttt{(a*)*b}}} :\bigskip

\begin{center}

\only<1>{\code{"aaaaaaaaaaaaaaab"}}

\only<2>{\code{"aaaaa...........aaaaaaaaaaaaaaaaaaaab"}}

\only<3>{\code{"aaaaa...........aaaaaaaaaaaaaaaaaaaa"}}

\only<4>{\code{"aaaaa...........aaaaaaaaaaaaaaaaaaaab"}}

\only<5->{\code{"aaaaa...........aaaaaaaaaaaaaaaaaaaa"}}

\end{center}

\only<6>{

\begin{textblock}{13}(5,12)

How long does Python need to find out?

\end{textblock}}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}<1>[c]

  \frametitle{Main 3: Regexes}

\begin{center}

  \mbox{Graphs: regex \alert{\texttt{(a*)*b}} and strings $\underbrace{\;\texttt{a}\ldots \texttt{a}\;}_{n}$}\bigskip

  \small  

\begin{tabular}[t]{@{\hspace{-8mm}}c@{\hspace{-0mm}}c@{}}

\only<1>{\raisebox{6mm}{\begin{tikzpicture}

\begin{axis}[

    xlabel={$n$},

    x label style={at={(1.05,0.0)}},

    ylabel={time in secs},

    enlargelimits=false,

    xtick={0,5,...,30},

    xmax=33,

    ymax=35,

    ytick={0,5,...,30},

    scaled ticks=false,

    axis lines=left,

    width=5.5cm,

    height=5cm,

    legend entries={Java 8,Python,JavaScript,Swift,Dart},

    %legend entries={\small{}Python,  \small{}Java 8,  \small{}JavaScript},  

    legend pos=north west,

    legend cell align=left]

\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};  

\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};

\addplot[red,mark=*, mark options={fill=white}] table {re-js.data};

\addplot[magenta,mark=*, mark options={fill=white}] table {re-swift.data};

\addplot[brown,mark=*, mark options={fill=white}] table {re-dart.data};

\end{axis}

\end{tikzpicture}}}%

\only<2>{\raisebox{0mm}{\begin{tikzpicture}

\begin{axis}[

    xlabel={$n$},

    x label style={at={(1.05,0.0)}},

    ylabel={time in secs},

    %y label style={at={(0.06,0.5)}},

    enlargelimits=false,

    %xtick={0,30000,...,60000},

    xmax=65000,

    ymax=35,

    ytick={0,5,...,30},

    scaled ticks=true,

    axis lines=left,

    width=5.5cm,

    height=5cm, 

    legend entries={\small{}Java 9},  

    legend pos=north west]

\addplot[cyan,mark=*, mark options={fill=white}] table {re-java9.data};