updated
authorChristian Urban <christian dot urban at kcl dot ac dot uk>
Thu, 27 Nov 2014 17:52:17 +0000
changeset 336 3cb200fa6d6a
parent 335 06d5fc15594d
child 337 92a718b88e14
updated
handouts/ho01.pdf
handouts/ho01.tex
handouts/ho08.pdf
handouts/ho08.tex
langs.sty
slides/slides09.pdf
slides/slides09.tex
Binary file handouts/ho01.pdf has changed
--- a/handouts/ho01.tex	Wed Nov 26 10:15:43 2014 +0000
+++ b/handouts/ho01.tex	Thu Nov 27 17:52:17 2014 +0000
@@ -286,14 +286,25 @@
 problem). So encryption seems to not solve the problem we face
 with the integrity of our counter.
 
-Fortunately, \emph{hash functions} seem to be more suitable
-for our purpose. Like encryption, hash functions scramble data
-in such a way that it is easy to calculate the output of a
-hash function from the input. But it is hard (i.e.~practically
-impossible) to calculate the input from knowing the output.
-Therefore hash functions are often called \emph{one-way
-functions}\ldots you cannot go back from the output to the
-input (without some tricks, see below). There are several such
+Fortunately, \emph{cryptographic hash functions} seem to be
+more suitable for our purpose. Like encryption, hash functions
+scramble data in such a way that it is easy to calculate the
+output of a hash function from the input. But it is hard
+(i.e.~practically impossible) to calculate the input from
+knowing the output. This is often called \emph{preimage
+resistance}. Cryptographic hash functions also ensure that
+given a message and a hash, it is computationally infeasible to
+find another message with the same hash. This is called
+\emph{collusion resistance}. Because of these properties hash
+functions are often called \emph{one-way functions}\ldots you
+cannot go back from the output to the input (without some
+tricks, see below). 
+
+
+
+
+
+There are several such
 hashing function. For example SHA-1 would hash the string
 \pcode{"hello world"} to produce the hash-value
 
Binary file handouts/ho08.pdf has changed
--- a/handouts/ho08.tex	Wed Nov 26 10:15:43 2014 +0000
+++ b/handouts/ho08.tex	Thu Nov 27 17:52:17 2014 +0000
@@ -5,7 +5,7 @@
 
 \begin{document}
 
-\section*{Handout 7 (Bitcoins)}
+\section*{Handout 8 (Bitcoins)}
 
 In my opinion Bitcoins are an elaborate Ponzi
 scheme\footnote{\url{http://en.wikipedia.org/wiki/Ponzi_scheme}}---still
@@ -758,7 +758,7 @@
 \noindent Finally, a government would potentially not really
 need to follow up with such threads. Just the rumour that it
 would, could be enough to get the Bitcoin-house-of-cards to
-tumble. Some governments have already such a ``impressive''
+tumble. Some governments have already such an ``impressive''
 trackrecord in this area, such a thread would be entirely
 credible. Because of all this, I would not have too much hope
 that Bitcoins are free from government \& Co interference when
@@ -781,11 +781,10 @@
 the UN, say, would find the money and incentivise people to,
 for example, solve protein folding
 puzzles?\footnote{\url{http://en.wikipedia.org/wiki/Protein_folding}}
-There are projects like
-Folding@home\footnote{\url{http://folding.stanford.edu}} which have 
+For this there are projects like
+Folding@home\footnote{\url{http://folding.stanford.edu}}. 
 This might help with curing diseases such as Alzheimer or
-diabetes, which to a large portion baddies and goodies will
-suffer at some point. The same point is made in the article
+diabetes. The same point is made in the article
 
 \begin{center}\small
 \url{http://gizmodo.com/the-worlds-most-powerful-computer-network-is-being-was-504503726}
@@ -794,8 +793,6 @@
 \end{document}
 
 bit coin
-https://bitcoin.org/bitcoin.pdf
-https://bitcoin.org/bitcoin.pdf
 
 A fistful of bitcoins
 http://cseweb.ucsd.edu/~smeiklejohn/files/imc13.pdf
--- a/langs.sty	Wed Nov 26 10:15:43 2014 +0000
+++ b/langs.sty	Thu Nov 27 17:52:17 2014 +0000
@@ -8,28 +8,10 @@
 \definecolor{codepurple}{rgb}{0.5,0,0.35}      % keywords
 \definecolor{codedocblue}{rgb}{0.25,0.35,0.75} % doc
 \definecolor{codeblue}{rgb}{0.25,0.35,0.75}    % types
-\definecolor{darkgray}{rgb}{.4,.4,.4}
 
 \BeforeBeginEnvironment{lstlisting}{\par\noindent\begin{minipage}{\linewidth}}
 \AfterEndEnvironment{lstlisting}{\end{minipage}\par}
 
-\lstdefinelanguage{JavaScript}{
-  keywords={break,case,catch,continue,debugger,default,% 
-    delete,do,else,false,finally,for,function,if,in,instanceof,% 
-    new,null,return,switch,this,throw,true,try,typeof,var,void,while,with},
-  morecomment=[l]{//},
-  morecomment=[s]{/*}{*/},
-  morestring=[b]',
-  morestring=[b]",
-  ndkeywords={class,export,boolean,throw,implements,import,this},
-  keywordstyle=\color{codepurple}\bfseries,
-  ndkeywordstyle=\color{darkgray}\bfseries,
-  identifierstyle=\color{black},
-  commentstyle=\color{codegreen}\ttfamily,
-  stringstyle=\color{codegreen}\ttfamily,
-  sensitive=true
-}
-
 \lstdefinelanguage{Scala}{
   morekeywords={abstract,case,catch,class,def,%
     do,else,extends,false,final,finally,%
@@ -38,28 +20,28 @@
     private,protected,requires,return,sealed,%
     super,this,throw,trait,true,try,%
     type,val,var,while,with,yield},%
-  otherkeywords={=>,<-,<\%,<:,>:,\#,@},%
+  otherkeywords={=>,<-,<\%,<:,>:,\#},%
   sensitive=true,%
   %directives={Int,Char,Rexp,String,Boolean,BigInt,Unit,List,Set},%
   %moredelim=*[directive]:,%
   morecomment=[l]{//},%
   morecomment=[n]{/*}{*/},
+  morestring=[s]{"""}{"""},
   morestring=[b]",
   morestring=[b]',
-  morestring=[b]"""
 }[keywords,comments,strings]
 
 \lstdefinelanguage{While}{
-  morekeywords={if,then,else,while,do,true,false,write,upto,for,skip},
-  otherkeywords={=,!=,:=,<,>,;},
-  sensitive=true,
+  morekeywords={if,then,else,while,do,true,false,write,upto,read,for,skip},
+  morecomment=[l]{//},
   morecomment=[n]{/*}{*/},
-}
+  morestring=[b]",
+  otherkeywords={=,!=,:=,<,>,\%;*,/},
+}[keywords,comments,strings]
 
 \lstdefinestyle{mystyle}
        {basicstyle=\ttfamily,
 	keywordstyle=\color{codepurple}\bfseries,
-        %directivestyle=\color{codeblue}\bfseries,
 	stringstyle=\color{codegreen},
 	commentstyle=\color{codegreen},
 	morecomment=[s][\color{codedocblue}]{/**}{*/},
@@ -72,7 +54,8 @@
 	showstringspaces=false,
         xleftmargin=8mm,
         emphstyle=\color{codeblue}\bfseries,
-        keepspaces}
+        keepspaces
+}
 
 \lstset{language=Scala,
         style=mystyle}
@@ -80,4 +63,5 @@
 
 \newcommand{\code}[1]{{\lstinline{#1}}}
 \newcommand{\pcode}[1]{\mbox{\lstset{language={},keywordstyle=\color{black}}\lstinline!#1!}}
+\newcommand{\scode}[1]{\mbox{\lstset{language={},basicstyle=\ttfamily\color{codegreen}}\lstinline!#1!}}
 \makeatother
Binary file slides/slides09.pdf has changed
--- a/slides/slides09.tex	Wed Nov 26 10:15:43 2014 +0000
+++ b/slides/slides09.tex	Thu Nov 27 17:52:17 2014 +0000
@@ -3,29 +3,16 @@
 \usepackage{../langs}
 \usepackage{../graphics}
 \usepackage{../grammar}
+
 %\usepackage{soul}
 
-\makeatletter
-\newenvironment<>{btHighlight}[1][]
-{\begin{onlyenv}#2\begingroup\tikzset{bt@Highlight@par/.style={#1}}\begin{lrbox}{\@tempboxa}}
-{\end{lrbox}\bt@HL@box[bt@Highlight@par]{\@tempboxa}\endgroup\end{onlyenv}}
-
-\newcommand<>\btHL[1][]{%
-  \only#2{\begin{btHighlight}[#1]\bgroup\aftergroup\bt@HL@endenv}%
-}
-\def\bt@HL@endenv{%
-  \end{btHighlight}%   
-  \egroup
-}
-\newcommand{\bt@HL@box}[2][]{%
-  \tikz[#1]{%
-    \pgfpathrectangle{\pgfpoint{1pt}{0pt}}{\pgfpoint{\wd #2}{\ht #2}}%
-    \pgfusepath{use as bounding box}%
-    \node[anchor=base west, fill=orange!30,outer sep=0pt,inner xsep=1pt, inner ysep=0pt, rounded corners=3pt, minimum height=\ht\strutbox+1pt,#1]{\raisebox{1pt}{\strut}\strut\usebox{#2}};
-  }%
-}
-\makeatother
-
+%\newcommand\hl[1]{%
+%    \tikz[baseline,%
+%      outer sep=-15pt, inner sep = 0pt%
+%    ]%
+%   \node[decorate,rectangle,fill=yellow,anchor=text]{#1};%
+%}%
+\newcommand{\hl}[1]{#1}
 
 % beamer stuff 
 \renewcommand{\slidecaption}{APP 09, King's College London}
@@ -864,7 +851,7 @@
          | \meta{var}\\
 : \meta{Stmt} ::= \meta{label} :
          | \meta{var} := \meta{Exp}
-         | jump? \meta{Exp} \meta{label}
+         | jmp? \meta{Exp} \meta{label}
          | goto \meta{label}\\
 : \meta{Prog} ::= \meta{Stmt} \ldots\\
 \end{plstx}}
@@ -884,7 +871,7 @@
          | \meta{var}\\
 : \meta{Stmt} ::= \meta{label} :
          | \meta{var} := \meta{Exp}
-         | jump? \meta{Exp} \meta{label}
+         | jmp? \meta{Exp} \meta{label}
          | goto \meta{label}\\
 : \meta{Prog} ::= \meta{Stmt} \ldots\\
 \end{plstx}}
@@ -897,7 +884,7 @@
                    language={},xleftmargin=3mm]
       a := 1
       n := 5 
-top:  jump? n = 0 done 
+top:  jmp? n = 0 done 
       a := a * n 
       n := n + -1 
       goto top 
@@ -970,13 +957,13 @@
 \end{center}
 
 \footnotesize
-\begin{lstlisting}[language=Scala,numbers=none,xleftmargin=-5mm]
+\begin{lstlisting}[numbers=none,xleftmargin=-5mm]
 def eval_exp(e: Exp, env: Env) : Int = e match {
-  case Num(n) & n
-  case Var(x) & env(x)
-  case Plus(e1, e2) & eval_exp(e1, env) + eval_exp(e2, env)
-  case Times(e1, e2) & eval_exp(e1, env) * eval_exp(e2, env)
-  case Equ(e1, e2) & 
+  case Num(n) => n
+  case Var(x) => env(x)
+  case Plus(e1, e2) => eval_exp(e1, env) + eval_exp(e2, env)
+  case Times(e1, e2) => eval_exp(e1, env) * eval_exp(e2, env)
+  case Equ(e1, e2) => 
     if (eval_exp(e1, env) == eval_exp(e2, env)) 1 else 0
 }
 \end{lstlisting}
@@ -1088,14 +1075,14 @@
 \begin{lstlisting}[language=Scala,numbers=none,xleftmargin=-5mm]
 def eval(sn: Snips) : Env = {
   def eval_stmts(sts: Stmts, env: Env) : Env = sts match {
-    case Nil & env
-    case Label(l)::rest & eval_stmts(rest, env)
-    case Assign(x, e)::rest & 
+    case Nil => env
+    case Label(l)::rest => eval_stmts(rest, env)
+    case Assign(x, e)::rest => 
       eval_stmts(rest, env + (x -> eval_exp(e, env)))
-    case Jump(b, l)::rest & 
+    case Jmp(b, l)::rest => 
       if (eval_exp(b, env) == 1) eval_stmts(sn(l), env) 
       else eval_stmts(rest, env)
-    case Goto(l)::rest & eval_stmts(sn(l), env)
+    case Goto(l)::rest => eval_stmts(sn(l), env)
   }
 
   eval_stmts(sn(""), Map())
@@ -1138,12 +1125,12 @@
                    language={},
                    basicstyle=\ttfamily,
                    xleftmargin=1mm,
-                   escapeinside={(*@}{@*)}]
-      a := (*@\hl{'+'}@*)
-      n := (*@\hl{'+'}@*) 
-top:  jmp? n = (*@\hl{'0'}@*) done 
+                   escapeinside={(*}{*)}]
+      a := (*\hl{'+'}*)
+      n := (*\hl{'+'}*) 
+top:  jmp? n = (*\hl{'0'}*) done 
       a := a * n 
-      n := n + (*@\hl{'-'}@*) 
+      n := n + (*\hl{'-'}*) 
       goto top 
 done:
 \end{lstlisting}