% !TEX program = xelatex

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

\usepackage{../styles/slides}

\usepackage{../styles/mygraphs}

\usepackage{../styles/langs}

\usepackage{chessboard} 

%%\usepackage{../data}

%%\usepackage[export]{adjustbox}

\usetikzlibrary{shapes,arrows,shadows}

% 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}

\hfuzz=220pt 

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

%\newfontfamily{\consolas}{Consolas}

\lstset{language=Scala,

        style=mystyle,

        numbersep=0pt,

        numbers=none,

        xleftmargin=0mm}

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

% beamer stuff 

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

\begin{document}

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

\begin{frame}[t]

\frametitle{%

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

  \\[5mm]

  \huge PEP Scala (5) 

  \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\\

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

  \end{tabular}

  \end{center}

\end{frame}

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

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

\begin{frame}[t]

\frametitle{Housekeeping}

\mbox{}\medskip  

\begin{minipage}{1.2\textwidth}

\begin{itemize}

\item SGTs still ongoing next week

%\item LGT next week online: Ask-Me-Anything (will be recorded, TEAMS link will be emailed and published on KEATS)

%\item tests might break over Christmas  

\end{itemize}\bigskip

%\begin{center}

%\raisebox{-9mm}{\includegraphics[scale=0.15]{../pics/thanks.jpeg}} Junhuai Hou \quad Chin Wan

%\end{center}  

\end{minipage}

\end{frame}

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

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

%\begin{frame}[c]

%\frametitle{Main 4: \knight-Tour}

%

%\begin{center}

%\Large\bf hint

%\end{center}  

%

%\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};

\end{axis}

\end{tikzpicture}}}

  &

\onslide<1-2>{\begin{tikzpicture}

  \begin{axis}[

    xlabel={$n$},

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

    ylabel={time in secs},

    enlargelimits=false,

    ymax=35,

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

    axis lines=left,

    legend entries={You in M3}, 

    %%scaled ticks=false,

    width=5.5cm, 

    height=5cm]

%%\addplot[green,mark=square*,mark options={fill=white}] table {re2a.data};    

\addplot[magenta,mark=square*,mark options={fill=white}] table {re3a.data};

\end{axis}

\end{tikzpicture}}

\end{tabular}

\end{center}

\hfill\small\url{https://vimeo.com/112065252}

\end{frame}

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

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

%\begin{frame}[c]

%\frametitle{Marks for Preliminary 8}

%

%Raw marks (265 submissions):\bigskip

%

%\begin{itemize}

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

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

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

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

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

%\end{itemize}\bigskip\bigskip  

%

%\footnotesize

%(plagiarism/collusion interviews ongoing again!)

%

%\end{frame}

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

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

%\begin{frame}[c]

%\frametitle{Plan for Today}

%

%\begin{itemize}

%\item Polymorphic Types  

%\item Implicits

%\item Immutable OOP

%%\item Making Fun about Scala

%\end{itemize}

%\end{frame}

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

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

%\begin{frame}[c,fragile]

%\frametitle{How To calcululate 100 Mio Collatz Series?} 

%

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

%(1L to 100_000_000).map(collatz).max

%\end{lstlisting}

%

%\end{frame}

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

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

% \begin{frame}[c,fragile]

% \frametitle{Polyorphic Types} 

% %To be avoided:\bigskip\bigskip

% \small

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

% def length_string_list(lst: List[String]): Int = 

%  lst match {

%    case Nil => 0

%    case x::xs => 1 + length_string_list(xs)

%  }

% def length_int_list(lst: List[Int]): Int = 

%  lst match {

%    case Nil => 0

%    case x::xs => 1 + length_int_list(xs)

%  }

% \end{lstlisting}

% \end{frame}

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

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

% \begin{frame}[c,fragile]

% \frametitle{Polyorphic Types} 

% \small

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

% def length[A](lst: List[A]): Int = lst match {

%   case Nil => 0

%   case x::xs => 1 + length(xs)

% }

% length(List("1", "2", "3", "4"))

% length(List(1, 2, 3, 4))

% def map[A, B](lst: List[A], f: A => B): List[B] = 

%  lst match {

%    case Nil => Nil

%    case x::xs => f(x)::map(xs, f) 

%  }

% \end{lstlisting}

% \end{frame}

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

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

\begin{frame}[c]

\frametitle{DFAs}  

\begin{center}

\begin{tikzpicture}[>=stealth',very thick,auto,

  every state/.style={minimum size=0pt,inner sep=2pt,

    draw=blue!50,very thick,fill=blue!20},]

\only<1,3->{\node[state,initial] (Q_0)  {$\mbox{Q}_0$};}

\only<2>{\node[state,initial,fill=red] (Q_0)  {$\mbox{Q}_0$};}  

\only<1,2,4->{\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};}

\only<3>{\node[state,fill=red] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};}

\only<-3,5->{\node[state] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};}

\only<4>{\node[state,fill=red] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};}

\only<-4,6->{\node[state] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};}

\only<5>{\node[state,fill=red] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};}

\only<-5>{\node[state, accepting] (Q_4) [right=of Q_1] {$\mbox{Q}_4$};}

\only<6->{\node[state, accepting,fill=red] (Q_4) [right=of Q_1] {$\mbox{Q}_4$};}

\path[->] (Q_0) edge node [above]  {\alert{$a$}} (Q_1);

\path[->] (Q_1) edge node [above]  {\alert{$a$}} (Q_4);

\path[->] (Q_4) edge [loop right] node  {\alert{$a, b$}} ();

\path[->] (Q_3) edge node [right]  {\alert{$a$}} (Q_4);

\path[->] (Q_2) edge node [above]  {\alert{$a$}} (Q_3);

\path[->] (Q_1) edge node [right]  {\alert{$b$}} (Q_2);

\path[->] (Q_0) edge node [above]  {\alert{$b$}} (Q_2);

\path[->] (Q_2) edge [loop left] node  {\alert{$b$}} ();

\path[->] (Q_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (Q_0);

\end{tikzpicture}

\end{center}

\begin{textblock}{10}(4,12)

\LARGE{}\phantom{b}

\only<-2>{\boldmath\textcolor{gray}{$a$}}\only<3->{\boldmath\alert{$a$}}%

\only<-3>{\boldmath\textcolor{gray}{$b$}}\only<4->{\boldmath\alert{$b$}}%

\only<-4>{\boldmath\textcolor{gray}{$a$}}\only<5->{\boldmath\alert{$a$}}%

\only<-5>{\boldmath\textcolor{gray}{$a$}}\only<6->{\boldmath\alert{$a$}}%

\only<-6>{\boldmath\textcolor{gray}{$a$}}\only<7->{\boldmath\alert{$a\quad\Rightarrow \textbf{yes}$}}% 

\end{textblock}

\end{frame}

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

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

\begin{frame}[t]

\frametitle{DFAs}

A \alert{\bf deterministic finite automaton} (DFA) consists of

5 things:

\begin{itemize}

\item an alphabet \bl{$\varSigma$}  

\item a set of states \bl{$\mbox{Qs}$}

\item one of these states is the start state \bl{$\mbox{Q}_0$}

\item some states are accepting states \bl{$F$}, and

\item there is transition function \bl{$\delta$}\bigskip 

\small

which takes a state  and a character as arguments and produces a 

new state; this function might not be everywhere defined 

\end{itemize}

\begin{center}

\bl{$A(\varSigma, \mbox{Qs}, \mbox{Q}_0, F, \delta)$}

\end{center}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{NFAs}  

\begin{center}

\begin{tikzpicture}[>=stealth',very thick, auto,

    every state/.style={minimum size=0pt,inner sep=3pt,

      draw=blue!50,very thick,fill=blue!20},scale=2]

\node[state,initial]  (Q_0)  {$\mbox{Q}_0$};

\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};

\node[state, accepting] (Q_2) [right=of Q_1] {$\mbox{Q}_2$};

\path[->] (Q_0) edge [loop above] node  {\alert{$b$}} ();

\path[<-] (Q_0) edge node [below]  {\alert{$b$}} (Q_1);

\path[->] (Q_0) edge [bend left] node [above]  {\alert{$a$}} (Q_1);

\path[->] (Q_0) edge [bend right=45,looseness=1.3] node [below]  {\alert{$a$}} (Q_2);

\path[->] (Q_1) edge [loop above] node  {\alert{$a,b$}} ();

\path[->] (Q_1) edge node  [above] {\alert{$a$}} (Q_2);

\end{tikzpicture}

\end{center}

\end{frame}

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

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

\begin{frame}[t]

\frametitle{Where to go on from here?}

\begin{itemize}

\item Martin Odersky (EPFL) developed Scala\medskip