diff -r 9e7897f25e13 -r e52cc402caee slides/slides04.tex --- a/slides/slides04.tex Thu Nov 29 17:15:11 2018 +0000 +++ b/slides/slides04.tex Fri Nov 30 03:44:27 2018 +0000 @@ -4,6 +4,7 @@ \usepackage{../langs} %%\usepackage{../data} \usepackage[export]{adjustbox} +\usetikzlibrary{shapes} \hfuzz=220pt @@ -16,10 +17,26 @@ 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) 03, King's College London} +\renewcommand{\slidecaption}{PEP (Scala) 04, King's College London} \begin{filecontents}{re3a.data} 1 0.00003 @@ -54,6 +71,20 @@ 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 @@ -73,23 +104,50 @@ 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 (3) + \huge PEP Scala (4) \end{tabular}} \normalsize \begin{center} \begin{tabular}{ll} Email: & christian.urban at kcl.ac.uk\\ - Office: & N7.07 (North Wing, Bush House)\\ + Office: & N\liningnums{7.07} (North Wing, Bush House)\\ Slides \& Code: & KEATS\medskip\\ - Scala Office & \\ - Hours: & Thursdays 11 -- 13\\ + Office Hours: & Mondays 12:00 -- 14:00\\ \end{tabular} \end{center} @@ -97,85 +155,209 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\begin{frame}[c] +\frametitle{Somewhere Remote} + +\begin{center} +\includegraphics[scale=0.37]{../pics/sahara.jpg} +\end{center} + +\end{frame} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\begin{frame}[t] +\frametitle{This is a bit harsh\ldots} + +\mbox{}\\[-22mm]\mbox{} + +\begin{center} +\begin{bubble}[10.5cm] + ...trying a new method because the fucking github reports dont tell me + which test failed. It's not really helpful when the inline tests work + and it compiles but all i get is 'one test failed'... really helpful my dude. +\end{bubble} +\end{center} + +\begin{center} +\begin{bubble}[10.5cm] + ...Reverted back and finished part 5, this is ridiculous how one test works + and all I get is 'ONE TEST FAILED'. Fix your reports before giving us + assignments like this... +\end{bubble} +\end{center} + + +\end{frame} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\begin{frame}[t,fragile] +\frametitle{Needless to say I tried it out} + +\mbox{}\\[-7mm]\mbox{}\footnotesize + +\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-4mm] +> legal_moves(8, Nil, (2,2)) + = List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)) + +> legal_moves(8, Nil, (7,7)) + = List((6,5), (5,6)) + +> legal_moves(8, List((4,1), (1,0)), (2,2)) + = List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)) + +> legal_moves(1, Nil, (0,0)) + = List((-1,-2), (-2,-1)) + +> legal_moves(2, Nil, (0,0)) + = List((1,-2), (-1,-2), (-2,-1), (-2,1)) + +> legal_moves(3, Nil, (0,0)) + = List((1,2), (2,1), (2,-1), (1,-2), (-1,-2), (-2,-1), (-2,1), (-1,2)) +\end{lstlisting} + +\LEFTarrow{1}{9}{9} +\LEFTarrow{1}{12}{11} +\DOWNarrow{1}{10}{13} + +\end{frame} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c,fragile] - -\begin{textblock}{6}(0.5,0.5) -\begin{bubble}[11.5cm] -\footnotesize -\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm] -import java.util.concurrent._ -import java.util.concurrent.atomic._ +\small + +\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-7mm] +def is_legal(dim: Int, p: Path, x: Pos): Boolean = { + if (......some_really_long_condition.....) false + else true +} +\end{lstlisting} - def collatz(input:Int){ - CollatzConjecture(input); - println(count.get()); - } - def collatz_max(input:Int){ - val List = new Array[Int](input) - for (i <- 0 to input-1){ - CollaĵConjecture(i); - List(i)=count.get(); - count.set(0); - } - val max = new AtomicInteger(); - max.set(List(0)); - val index = new AtomicInteger(); - index.set(1); - -\end{lstlisting} -\end{bubble} -\end{textblock} +\pause +\bigskip +\rule{11cm}{0.3mm} +\bigskip + +\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-7mm] +def is_legal(dim: Int, p: Path, x: Pos): Boolean = + ......some_really_long_condition..... +\end{lstlisting}\pause + \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c,fragile] +\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}{6}(0.5,0.5) -\begin{bubble}[11.5cm] -\footnotesize -\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm] - for(i<-0 to input-1){ - val temp :Int=max.get(); - if (temp < List(i)){ - max.set(List(i)); - index.set(i); - } - } - println("("+max.get() +","+ index.get()+ ")"); - } +\begin{textblock}{9}(4,12) +\LARGE{} +\only<3->{\boldmath\alert{$a$}}% +\only<4->{\boldmath\alert{$b$}}% +\only<5->{\boldmath\alert{$a$}}% +\only<6->{\boldmath\alert{$a$}}% +\only<7->{\boldmath\alert{$a\quad\Rightarrow \textbf{yes}$}}% +\end{textblock} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t] +\frametitle{DFAs} - def CollatzConjecture(n: Long): Long = { - count.incrementAndGet(); - if (n <= 1) - 1 - else if (n\%2 ==0) - CollatzConjecture(n/2); - else - CollatzConjecture((3*n)+1); - } - } -\end{lstlisting} -\end{bubble} -\end{textblock} +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}[c] - \frametitle{CW3 (1 Part): Regexes} + \frametitle{CW\liningnums{9} (\liningnums{1} Part): Regexes} \begin{center} Graphs: $(a^*)^* b$ and strings $\underbrace{\;a\ldots a\;}_{n}$\bigskip \begin{tabular}[t]{@{\hspace{-8mm}}c@{\hspace{-4mm}}c@{}} -\raisebox{6mm}{\begin{tikzpicture} +\only<1>{\raisebox{6mm}{\begin{tikzpicture} \begin{axis}[ xlabel={$n$}, x label style={at={(1.05,0.0)}}, @@ -189,15 +371,36 @@ axis lines=left, width=5.5cm, height=5cm, - legend entries={Python, Java 8}, + 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}; \end{axis} -\end{tikzpicture}} +\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<2>{\begin{tikzpicture} +\onslide<1-2>{\begin{tikzpicture} \begin{axis}[ xlabel={$n$}, x label style={at={(1.05,0.0)}}, @@ -210,7 +413,7 @@ width=5.5cm, height=5cm] %%\addplot[green,mark=square*,mark options={fill=white}] table {re2a.data}; -\addplot[red,mark=square*,mark options={fill=white}] table {re3a.data}; +\addplot[magenta,mark=square*,mark options={fill=white}] table {re3a.data}; \end{axis} \end{tikzpicture}} \end{tabular} @@ -221,16 +424,12 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] -\frametitle{Where to go on from here?} +\frametitle{Hint} -\begin{itemize} -\item Martin Odersky (EPFL)\ldots he is currently throwing out everything - and starts again with the dotty compiler for Scala\medskip +\begin{center} +\LARGE\textbf{\alert{Pattern-Matching}} +\end{center} -\item Elm (\url{http://elm-lang.org})\ldots web applications with style\medskip - -\item Haskell, Ocaml, Standard ML, Scheme, \ldots -\end{itemize} \end{frame} @@ -240,81 +439,9 @@ \begin{frame}[c,fragile] \frametitle{\alert{Questions?}} -{\tiny -\begin{verbatim} - * - * * - * * - * * * * - * * - * * * * - * * * * - * * * * * * * * - * * - * * * * - * * * * - * * * * * * * * - * * * * - * * * * * * * * - * * * * * * * * - * * * * * * * * * * * * * * * * - * * - * * * * - * * * * - * * * * * * * * - * * * * - * * * * * * * * - * * * * * * * * - * * * * * * * * * * * * * * * * - * * * * - * * * * * * * * - * * * * * * * * - * * * * * * * * * * * * * * * * - * * * * * * * * - * * * * * * * * * * * * * * * * - * * * * * * * * * * * * * * * * -* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * -\end{verbatim}} - - -\begin{textblock}{6}(8.5,3.5) -\begin{bubble}[5cm] -\footnotesize -\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm] -++++++++[>+>++++<<-]>++>> -+<[-[>>+<<-]+>>]>+[-<<<[- ->[+[-]+>++>>>-<<]<[<]>>++ -++++[<<+++++>>-]+<<++.[-] -<<]>.>+[>>]>+] -\end{lstlisting} -\end{bubble} -\end{textblock} - \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -\begin{frame}[c] -\frametitle{Marks for CW6 (Part 1 + 2)} - -Raw marks: - -\begin{itemize} -\item 6\%: 154 students -\item 5\%: 66 -\item 4\%: 18 -\item 3\%: 13 -\item 2\%: 2 -\item 1\%: 1 -\item 0\%: 21 -\end{itemize} -\end{frame} - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -\end{document} \end{document}