Binary file cws/main_cw03.pdf has changed
--- a/cws/main_cw03.tex Tue Dec 07 01:35:00 2021 +0000
+++ b/cws/main_cw03.tex Tue Dec 07 23:17:51 2021 +0000
@@ -362,10 +362,23 @@
\end{tabular}
\end{center}
- The last case is as follows: first apply $simp$ to all regular expressions
- $r_1,.. ,r_n$; then flatten the resulting list using \texttt{flts};
- finally remove all duplicates in this list (this can be done in Scala
- using the function \texttt{\_.distinct}).
+The last case is as follows: first apply $simp$ to all regular
+expressions $r_1,.. ,r_n$; then flatten the resulting list using
+\texttt{flts}; finally remove all duplicates in this list (this can be
+done in Scala using the function
+\texttt{\_.distinct}). \textcolor{red}{When you perform these
+ operations, you end up with three cases, namely where the list is
+ empty, contains a single element and ``otherwise''. These cases
+ should be processed as follows}
+\begin{center}
+\textcolor{red}{\begin{tabular}{l@{\hspace{4mm}}c@{\hspace{4mm}}ll}
+$\sum\;[]$ & $\mapsto$ & $\ZERO$\\
+$\sum\;[r]$ & $\mapsto$ & $r$\\
+$\sum\;rs$ & $\mapsto$ & $\sum\;rs$ & ``otherwise''\\
+\end{tabular}}
+\end{center}
+
+
For example the regular expression
\[(r_1 + \ZERO) \cdot \ONE + ((\ONE + r_2) + r_3) \cdot (r_4 \cdot \ZERO)\]
--- a/cws/main_cw04.tex Tue Dec 07 01:35:00 2021 +0000
+++ b/cws/main_cw04.tex Tue Dec 07 23:17:51 2021 +0000
@@ -30,10 +30,6 @@
This part is about searching and backtracking. You are asked to
implement Scala programs that solve various versions of the
\textit{Knight's Tour Problem} on a chessboard.
-% The preliminary part (4\%) is due on \sout{\cwNINE{}}
-% \textcolor{red}{16 December} at 5pm; the core part (6\%)
-% is due on \cwNINEa{} at 5pm. Any 1\% you achieve in the
-% preliminary part counts as your ``weekly engagement''.
\medskip
% Note the core, more advanced, part might include material you have not
--- a/main_solution1/drumb.scala Tue Dec 07 01:35:00 2021 +0000
+++ b/main_solution1/drumb.scala Tue Dec 07 23:17:51 2021 +0000
@@ -123,14 +123,40 @@
def yearly_yield(data: List[List[Option[Double]]], balance: Long, index: Int): Long = {
val somes = data(index).flatten
+ println(s"somes: $somes")
val somes_length = somes.length
if (somes_length == 0) balance
else {
val portion: Double = balance.toDouble / somes_length.toDouble
- balance + (for (x <- somes) yield (x * portion)).sum.toLong
+ println(s"portion: $portion")
+ val b = balance + (for (x <- somes) yield (x * portion)).sum.toLong
+ println(s"balance $b")
+ println(s"profit ${(for (x <- somes) yield (x * portion)).sum}")
+ b
}
}
+val dd = List(List(Some(0.9)), List(Some(0.9)))
+yearly_yield(dd, 100, 0)
+
+def yearly_yield2(data: List[List[Option[Double]]], balance: Long, index: Int) : Long = {
+
+ val share = balance/data(index).flatten.size.toDouble
+ println(s"portion: $share")
+ def count(data: List[Option[Double]], prof: Double, share: Double) : Double = data match{
+ case Nil => prof
+ case x::rest => count(rest,prof + (x.getOrElse(0.0) * share), share)
+ }
+ val balance_double = count(data(index), 0.0, share)
+ println(balance_double)
+ println(s"balance ${balance_double + balance}")
+ println(s"profit $balance_double")
+ //if (balance_double >= balance_double.toLong.toDouble+0.5) (balance_double + 1).toLong else balance_double.toLong
+ (balance_double.toLong + balance)
+}
+
+yearly_yield2(dd, 100, 0)
+
// test case using the deltas calculated above
//println("Task 6 yield from Google and Apple in 2010 with balance 100")
@@ -140,6 +166,7 @@
//val goog_aapl_yield = yearly_yield(goog_aapl_deltas, 100, 0)
+//val goog_aapl_yield = yearly_yield2(goog_aapl_deltas, 100, 0)
//println("Rounded yield: " ++ goog_aapl_yield.toString ++ "\n")
@@ -161,10 +188,20 @@
}
}
+def compound_yield2(data: List[List[Option[Double]]], balance: Long, index: Int): Long = {
+ if (index >= data.length) balance else {
+ val new_balance = yearly_yield2(data, balance, index)
+ compound_yield2(data, new_balance, index + 1)
+ }
+}
+
def investment(portfolio: List[String], years: Range, start_balance: Long): Long = {
compound_yield(get_deltas(get_prices(portfolio, years)), start_balance, 0)
}
+def investment2(portfolio: List[String], years: Range, start_balance: Long): Long = {
+ compound_yield2(get_deltas(get_prices(portfolio, years)), start_balance, 0)
+}
//test cases for the two portfolios given above
@@ -176,6 +213,25 @@
}
+investment(List("GOOG", "AAPL", "BIDU"), 2000 to 2000, 100)
+investment2(List("GOOG", "AAPL", "BIDU"), 2000 to 2000, 100)
+
+investment(List("GOOG", "AAPL", "BIDU"), 2000 to 2001, 100)
+investment2(List("GOOG", "AAPL", "BIDU"), 2000 to 2001, 100)
+
+investment(List("GOOG", "AAPL", "BIDU"), 2000 to 2002, 100)
+investment2(List("GOOG", "AAPL", "BIDU"), 2000 to 2002, 100)
+
+investment(List("GOOG", "AAPL", "BIDU"), 2000 to 2003, 100)
+investment2(List("GOOG", "AAPL", "BIDU"), 2000 to 2003, 100)
+
+investment(List("GOOG", "AAPL", "BIDU"), 2000 to 2004, 100)
+investment2(List("GOOG", "AAPL", "BIDU"), 2000 to 2004, 100)
+
+investment(List("GOOG", "AAPL", "BIDU"), 2000 to 2005, 100)
+investment2(List("GOOG", "AAPL", "BIDU"), 2000 to 2005, 100)
+
+
@@ -192,5 +248,3 @@
-
-
--- a/main_solution3/re.scala Tue Dec 07 01:35:00 2021 +0000
+++ b/main_solution3/re.scala Tue Dec 07 23:17:51 2021 +0000
@@ -108,6 +108,7 @@
case r => r
}
+simp(ALT(ONE | CHAR('a'), CHAR('a') | ONE))
// (4) Complete the two functions below; the first
// calculates the derivative w.r.t. a string; the second
--- a/main_solution4/knight3.scala Tue Dec 07 01:35:00 2021 +0000
+++ b/main_solution4/knight3.scala Tue Dec 07 23:17:51 2021 +0000
@@ -64,4 +64,10 @@
// testcases
//print_board(70, tour_on_mega_board(70, List((0, 0))).get)
+
+
}
+
+
+val dim = 30 //75
+M4c.print_board(dim, M4c.tour_on_mega_board(dim, List((0, 0))).get)
--- a/main_templates3/re.scala Tue Dec 07 01:35:00 2021 +0000
+++ b/main_templates3/re.scala Tue Dec 07 23:17:51 2021 +0000
@@ -12,6 +12,21 @@
case class SEQ(r1: Rexp, r2: Rexp) extends Rexp // sequence
case class STAR(r: Rexp) extends Rexp // star
+import scala.language.implicitConversions
+import scala.language.reflectiveCalls
+
+def charlist2rexp(s: List[Char]): Rexp = s match {
+ case Nil => ONE
+ case c::Nil => CHAR(c)
+ case c::s => SEQ(CHAR(c), charlist2rexp(s))
+}
+implicit def string2rexp(s: String): Rexp = charlist2rexp(s.toList)
+
+
+// "a|b"
+ALT(CHAR('a'), CHAR('b'))
+
+val reg : Rexp = "a" | "b" // CHAR('a')
// some convenience for typing regular expressions
@@ -29,6 +44,9 @@
}
implicit def string2rexp(s: String): Rexp = charlist2rexp(s.toList)
+
+
+
implicit def RexpOps (r: Rexp) = new {
def | (s: Rexp) = ALT(r, s)
def % = STAR(r)
--- a/main_testing4/knight_test.sh Tue Dec 07 01:35:00 2021 +0000
+++ b/main_testing4/knight_test.sh Tue Dec 07 23:17:51 2021 +0000
@@ -5,7 +5,7 @@
echo -e "" > $out
-echo -e "Below is the feedback for your submission of CW 8" >> $out
+echo -e "Below is the feedback for your submission of knight{1,2,3}.scala" >> $out
echo -e "" >> $out
#echo -e "!! Important: !!" >> $out
#echo -e "Because of limitations with our testing infrastructure, we can only" >> $out
Binary file pics/commits.png has changed
--- a/progs/cube.sc Tue Dec 07 01:35:00 2021 +0000
+++ b/progs/cube.sc Tue Dec 07 23:17:51 2021 +0000
@@ -61,7 +61,7 @@
def pp_cube(c: Cube) : String =
s"${pp_face(c.f1)}\n${pp_face(c.f2)}\n${pp_face(c.f3)}\n${pp_face(c.f4)}\n${pp_face(c.f5)}\n${pp_face(c.f6)}"
-// specific cube
+
val init =
Cube(Face(White, Green, White, White),
Face(Blue, Yellow, Orange, Red),
@@ -137,7 +137,7 @@
def searchS(cs: Set[Cube], d: Int) : Boolean = {
println(s"Depth: $d Cands: ${cs.size}")
- //memory()
+ memory()
if (cs.exists(solved == _)) true
else searchS(cs.flatMap(actionsS), d + 1)
}
@@ -163,13 +163,13 @@
def search2(cs: List[(Cube, Actions)], d: Int) : (Cube, Actions) = {
println(s"Depth: $d Cands: ${cs.length}")
- val res = cs.find(solved == _._1)
+ val res = cs.find(init == _._1)
if (res.isDefined) res.get
else search2(cs.flatMap((actions2 _).tupled), d + 1)
}
//println("List Version with Actions")
-//println(search2(List((init, Nil)), 0)._2.mkString("\n"))
+//println(search2(List((solved, Nil)), 0)._2.mkString("\n"))
//println(s"${time_needed(1, search2(List((init, Nil)), 0))} secs")
// using Maps for recording the moves
@@ -181,13 +181,13 @@
def searchM(cs: Map[Cube, Actions], d: Int) : Actions = {
println(s"Depth: $d Cands: ${cs.keySet.size}")
- val res = cs.keySet.find(solved == _)
+ val res = cs.keySet.find(init == _)
if (res.isDefined) cs(res.get)
else searchM(cs.flatMap((actionsM _).tupled), d + 1)
}
println("Map Version with actions")
-println(searchM(Map(init -> Nil), 0).mkString("\n"))
+println(searchM(Map(solved -> Nil), 0).mkString("\n"))
println(s"${time_needed(1, searchM(Map(init -> Nil), 0))} secs")
@@ -205,3 +205,11 @@
println("Bidirectional Version with actions")
println(bsearch(Map(init -> Nil), Map(solved -> Nil), 0))
println(s"${time_needed(1, bsearch(Map(init -> Nil), Map(solved -> Nil), 0))}")
+
+
+
+
+
+
+// more memory
+// JAVA_OPTS="-Xmx2g"
\ No newline at end of file
--- a/progs/lecture3.scala Tue Dec 07 01:35:00 2021 +0000
+++ b/progs/lecture3.scala Tue Dec 07 23:17:51 2021 +0000
@@ -2,6 +2,7 @@
//=================
+
// naive quicksort with "On" function
def sortOn(f: Int => Int, xs: List[Int]) : List[Int] = {
--- a/progs/lecture4.scala Tue Dec 07 01:35:00 2021 +0000
+++ b/progs/lecture4.scala Tue Dec 07 23:17:51 2021 +0000
@@ -1,6 +1,36 @@
// Scala Lecture 4
//=================
+// tail-recursion
+// polymorphic types
+// implicits
+
+import scala.annotation.tailrec
+
+@tailrec
+def fact(n: BigInt): BigInt =
+ if (n == 0) 1 else n * fact(n - 1)
+
+@tailrec
+def factT(n: BigInt, acc: BigInt): BigInt =
+ if (n == 0) acc else factT(n - 1, n * acc)
+
+
+println(factT(1000000), 1))
+
+
+def foo[A](args: List[A]) = ???
+
+foo(List("1","2","3","4"))
+import scala.annotation.tailrec
+
+
+// from knight1.scala
+def first(xs: List[Pos], f: Pos => Option[Path]) : Option[Path] = ???
+
+// should be
+def first[A, B](xs: List[A], f: A => Option[B]) : Option[B] = ???
+
// expressions (essentially trees)
@@ -252,7 +282,6 @@
// Tail recursion
//================
-@tailrec
def fact(n: BigInt): BigInt =
if (n == 0) 1 else n * fact(n - 1)
@@ -519,7 +548,7 @@
def increment = s.map(c => (c + 1).toChar)
}
-"HAL".increment
+"HAL".increment.map(_.toInt)
// Abstract idea:
@@ -580,7 +609,7 @@
implicit def string2rexp(s: String): Rexp =
charlist2rexp(s.toList)
-val r1 = STAR("hello")
+val r1 = STAR("ab")
val r2 = STAR("hello") | STAR("world")
--- a/progs/lecture5.scala Tue Dec 07 01:35:00 2021 +0000
+++ b/progs/lecture5.scala Tue Dec 07 23:17:51 2021 +0000
@@ -1,9 +1,36 @@
// Scala Lecture 5
//=================
+// Questions at
+//
+// pollev.com/cfltutoratki576
+
+(n, m) match {
+ case Pat1 =>
+ case _ =>
+}
+
+val delta : (State, Char) => State =
+ { case (Q0, 'a') => Q1
+ case (Q0, 'b') => Q2
+ case (Q1, 'a') => Q4
+ case (Q1, 'b') => Q2
+ case (Q2, 'a') => Q3
+ case (Q2, 'b') => Q2
+ case (Q3, 'a') => Q4
+ case (Q3, 'b') => Q0
+ case (Q4, 'a') => Q4
+ case (Q4, 'b') => Q4
+ case _ => throw new Exception("Undefined") }
+class Foo(i: Int)
+val v = new Foo(10)
+
+case class Bar(i: Int)
+
+val v = Bar(10)
--- a/progs/mandelbrot.scala Tue Dec 07 01:35:00 2021 +0000
+++ b/progs/mandelbrot.scala Tue Dec 07 23:17:51 2021 +0000
@@ -104,8 +104,8 @@
val d_x = (end.re - start.re) / W
val d_y = (end.im - start.im) / H
- for (y <- (0 until H)) {
- for (x <- (0 until W)) {
+ for (y <- (0 until H).par) {
+ for (x <- (0 until W).par) {
val c = start +
(x * d_x + y * d_y * i)
Binary file slides/slides04.pdf has changed
--- a/slides/slides04.tex Tue Dec 07 01:35:00 2021 +0000
+++ b/slides/slides04.tex Tue Dec 07 23:17:51 2021 +0000
@@ -39,6 +39,35 @@
% 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
@@ -150,7 +179,8 @@
Slides \& Code: & KEATS\bigskip\\
%Office Hours: & Thursdays 12:00 -- 14:00\\
%Additionally: & (for Scala) Tuesdays 10:45 -- 11:45\\
- \multicolumn{2}{c}{\Large\textbf{https://pollev.com/cfltutoratki576}}\\
+ \multicolumn{2}{c}{\Large\textbf{https://pollev.com/cfltutoratki576}}\\[2cm]
+ \textcolor{red}{Scala Install Clinic:} & \textcolor{red}{This evening at 17:00 (online)}\\
\end{tabular}
\end{center}
@@ -185,104 +215,104 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Preliminary 7}
+% \begin{frame}[c]
+% \frametitle{Preliminary 7}
-Raw marks (261 submissions):\bigskip
+% 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
+% \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!)
+% \footnotesize
+% (plagiarism/collusion interviews ongoing!)
-\end{frame}
+% \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c,fragile]
-\small
+% \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}
+% \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
+% \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}
+% \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}
+% \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c,fragile]
-\small
+% \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}
+% \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
+% \pause
+% \bigskip
+% \rule{11cm}{0.3mm}
+% \bigskip
-\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=1mm]
-def foobar(...) = {
- val cs = str.map(_.toLowerCase)
- ...
-}
-\end{lstlisting}
+% \begin{lstlisting}[language=Scala, numbers=none, xleftmargin=1mm]
+% def foobar(...) = {
+% val cs = str.map(_.toLowerCase)
+% ...
+% }
+% \end{lstlisting}
-\end{frame}
+% \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c,fragile]
-\small
+% \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}
+% \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}
+% \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -331,34 +361,34 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c,fragile]
-\frametitle{Sudoku}
+% \begin{frame}[c,fragile]
+% \frametitle{Sudoku}
-A very simple-minded version on 110 problems:\bigskip
+% 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}
+% \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}
+% \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[t]
+% \begin{frame}[t]
- \begin{center}
- \includegraphics[scale=0.3]{../pics/blow.png}
- \end{center}
+% \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{textblock}{14}(2,11.4)
+% \large\bf{}Mind-Blowing Regular Expressions:\\
+% \centering in Python, JavaScript, Java
+% \end{textblock}
+% \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -387,12 +417,14 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}<1>[c]
- \frametitle{CW 9: Regexes}
+ \frametitle{Main 3: Regexes}
\begin{center}
- Graphs: \alert{\texttt{(a*)*b}} and strings $\underbrace{\;\texttt{a}\ldots \texttt{a}\;}_{n}$\bigskip
-
-\begin{tabular}[t]{@{\hspace{-8mm}}c@{\hspace{-4mm}}c@{}}
+ \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$},
@@ -406,13 +438,16 @@
scaled ticks=false,
axis lines=left,
width=5.5cm,
- height=5cm,
- legend entries={\small{}Python, \small{}Java 8, \small{}JavaScript},
+ 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}
@@ -445,6 +480,7 @@
ymax=35,
ytick={0,5,...,30},
axis lines=left,
+ legend entries={You in M3},
%%scaled ticks=false,
width=5.5cm,
height=5cm]
@@ -460,7 +496,35 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c,fragile]
+\small
+\textcolor{red}{MacOSX}\medskip
+\begin{minipage}{13cm}
+ \begin{itemize}
+ \item[0)] (if needed) \texttt{brew install java} \;\;or\;\; \texttt{brew reinstall java}
+ \item[1)] \texttt{curl -s "https://get.sdkman.io" | bash}
+ \item[2)] \texttt{sdk install scala 2.13.7}
+ \end{itemize}
+\end{minipage}\bigskip
+
+\textcolor{red}{Windows / Linux Ubuntu}\medskip
+
+\begin{minipage}{13cm}
+ \begin{itemize}
+ \item[0)] (if needed) \texttt{sudo apt-get remove scala-library scala}
+ \item[1)] {\fontsize{8.5}{8.5}\selectfont\texttt{sudo wget https://downloads.lightbend.com/scala/2.13.7/scala-2.13.7.deb}}
+ \item[2)] \texttt{sudo dpkg -i scala-2.13.7.deb}
+ \end{itemize}
+\end{minipage}\bigskip
+
+\begin{minipage}{13cm}
+other Linux distros: \texttt{sudo apt-get scala}
+\end{minipage}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}
Binary file slides/slides05.pdf has changed
--- a/slides/slides05.tex Tue Dec 07 01:35:00 2021 +0000
+++ b/slides/slides05.tex Tue Dec 07 23:17:51 2021 +0000
@@ -8,6 +8,129 @@
\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}
@@ -38,16 +161,100 @@
\begin{tabular}{ll}
Email: & christian.urban at kcl.ac.uk\\
%Office: & N\liningnums{7.07} (North Wing, Bush House)\bigskip\\
- Slides \& Code: & KEATS\\
+ Slides \& Code: & KEATS\bigskip\\
% & \onslide<2>{\alert{PDF: A Crash-Course in Scala}}\bigskip\\
%Office Hours: & Thursdays 12:00 -- 14:00\\
- %Additionally: & (for Scala) Tuesdays 10:45 -- 11:45\\
+ %Additionally: & (for Scala) Tuesdays 10:45 -- 11:45\\
+ \multicolumn{2}{c}{\Large\textbf{https://pollev.com/cfltutoratki576}}\\[2cm]
\end{tabular}
\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]
@@ -241,151 +448,6 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\tikzstyle{sensor}=[draw, fill=blue!20, text width=3.8em, line width=1mm,
- text centered, minimum height=2em,drop shadow]
-\tikzstyle{ann} = [above, text width=4em, text centered]
-\tikzstyle{sc} = [sensor, text width=7em, fill=red!20,
- minimum height=6em, rounded corners, drop shadow,line width=1mm]
-
-\begin{frame}[fragile,c]
-\frametitle{Compilers 6CCS3CFL}
-
-\begin{tikzpicture}
- % Validation Layer is the same except that there are a set of nodes and links which are added
-
- \path (0,0) node (IR) [sc] {\textbf{WHILE Language}\\ compiler};
- \path (IR.west)+(-2.2,1.7) node (sou1) [sensor] {Fact};
- \path (IR.west)+(-2.2,0.5) node (sou2)[sensor] {Fib};
- \path (IR.west)+(-2.2,-0.7) node (sou4)[sensor] {Primes};
- \only<2>{\path (IR.west)+(-2.2,-1.9) node (sou3)[sensor] {BrainF**k};}
-
- \path [draw,->,line width=1mm] (sou1.east) -- node [above] {} (IR.160);
- \path [draw,->,line width=1mm] (sou2.east) -- node [above] {} (IR.180);
- \only<2>{\path [draw,->,line width=1mm] (sou3.east) -- node [above] {} (IR.200);}
- \path [draw,->,line width=1mm] (sou4.east) -- node [above] {} (IR.190);
-
- \path (IR.east)+(2.2, 0.8) node (tar2)[sensor] {JVM};
- \path (IR.east)+(2.2,-0.8) node (tar3)[sensor] {LLVM{\small(x86)}};
-
- \path [draw,<-,line width=1mm] (tar2.west) -- node [above] {} (IR.5);
- \path [draw,<-,line width=1mm] (tar3.west) -- node [above] {} (IR.-5);
-
-
-\end{tikzpicture}
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
- \begin{frame}[c]
- \frametitle{Dijkstra on Testing}
-
- \begin{bubble}[10cm]
- ``Program testing can be a very effective way to show the
- presence of bugs, but it is hopelessly inadequate for showing
- their absence.''
- \end{bubble}\bigskip
-
-
- \end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{\Large Proving Programs to be Correct}
-
-\begin{bubble}[10cm]
-\small
-{\bf Theorem:} There are infinitely many prime
-numbers.\medskip\\
-
-{\bf Proof} \ldots\\
-\end{bubble}\bigskip
-
-
-similarly\bigskip
-
-\begin{bubble}[10cm]
-\small
-{\bf Theorem:} The program is doing what
-it is supposed to be doing.\medskip
-
-{\bf Long, long proof} \ldots\\
-\end{bubble}\bigskip\medskip
-
-\small This can be a gigantic proof. The only hope is to have
-help from the computer. `Program' is here to be understood to be
-quite general (compiler, OS, \ldots).
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-\begin{frame}[c]
-\frametitle{Can This Be Done?}
-
-\begin{itemize}
-\item in 2011, verification of a small C-compiler (CompCert)
-\begin{itemize}
-\item ``if my input program has a certain behaviour, then the compiled machine code has the same behaviour''
-\item is as good as \texttt{gcc -O1}, but much, much less buggy
-\end{itemize}
-\end{itemize}
-
-\begin{center}
- \includegraphics[scale=0.12]{../pics/compcert.png}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%% ~2,237,800 lines of proof in 474
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Fuzzy Testing C-Compilers}
-
-\begin{itemize}
-\item tested GCC, LLVM and others by randomly generating
-C-programs
-\item found more than 300 bugs in GCC and also
-many in LLVM (some of them highest-level critical)\bigskip
-\item about CompCert:
-
-\begin{bubble}[10cm]\small ``The striking thing about our CompCert
-results is that the middle-end bugs we found in all other
-compilers are absent. As of early 2011, the under-development
-version of CompCert is the only compiler we have tested for
-which Csmith cannot find wrong-code errors. This is not for
-lack of trying: we have devoted about six CPU-years to the
-task.''
-\end{bubble}
-\end{itemize}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{seL4 / Isabelle}
-
-\begin{itemize}
-\item verified a microkernel operating system ($\approx$8000 lines of C code)\bigskip
-\item US DoD has competitions to hack into drones; they found that the
- isolation guarantees of seL4 hold up\bigskip
-\item CompCert and seL4 sell their code
-\end{itemize}
-
-\only<2>{
-\begin{textblock}{5}(5.5,1.9)
- \includegraphics[scale=0.25]{../pics/drone.jpg}
-\end{textblock}}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -393,8 +455,7 @@
\frametitle{Where to go on from here?}
\begin{itemize}
-\item Martin Odersky (EPFL)\ldots he is currently throwing out everything
- and starts again with the dotty compiler for Scala 3.0\medskip
+\item Martin Odersky (EPFL) developed Scala 3.0\medskip
\item Elm (\url{http://elm-lang.org})\ldots web applications with style\medskip
@@ -463,26 +524,6 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-
-\begin{frame}[t]
-
- \begin{center}
- \includegraphics[scale=0.4]{../pics/mind2.jpg}
- \end{center}
-
- \begin{textblock}{14}(2,11.4)
- \large\bf{}Mind-Blowing Programming Languages:\\
- \centering Scala\;\;?
- \end{textblock}
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-
-\end{document}
-
\end{document}
