--- a/cws/pre_cw03.tex Thu Nov 04 12:20:12 2021 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,181 +0,0 @@
-% !TEX program = xelatex
-\documentclass{article}
-\usepackage{../style}
-\usepackage{../langs}
-\usepackage{disclaimer}
-\usepackage{tikz}
-\usepackage{pgf}
-\usepackage{pgfplots}
-\usepackage{stackengine}
-%% \usepackage{accents}
-\newcommand\barbelow[1]{\stackunder[1.2pt]{#1}{\raisebox{-4mm}{\boldmath$\uparrow$}}}
-\usepackage{ulem}
-
-\begin{document}
-
-% BF IDE
-% https://www.microsoft.com/en-us/p/brainf-ck/9nblgggzhvq5
-
-\section*{Preliminary Part 3 (Scala, 3 Marks)}
-
-\mbox{}\hfill\textit{``[Google’s MapReduce] abstraction is inspired by the}\\
-\mbox{}\hfill\textit{map and reduce primitives present in Lisp and many}\\
-\mbox{}\hfill\textit{other functional languages.''}\smallskip\\
-\mbox{}\hfill\textit{ --- Dean and Ghemawat, who designed this concept at Google}
-\bigskip
-
-\IMPORTANT{This part is about the shunting yard algorithm by Dijkstra.
- The preliminary part is due on \sout{\cwEIGHT{}} \textcolor{red}{11 December}
- at 5pm and worth 3\%.
- Any 1\% you achieve in the preliminary part counts as your
- ``weekly engagement''.}
-
-\noindent
-Also note that the running time of each part will be restricted to a
-maximum of 30 seconds on my laptop.
-
-\DISCLAIMER{}
-
-\subsection*{Reference Implementation}
-
-This Scala assignment comes with two reference implementations in
-form of \texttt{jar}-files. This allows
-you to run any test cases on your own computer. For example you can
-call Scala on the command line with the option \texttt{-cp
- postfix.jar} and then query any function from the
-\texttt{postfix.scala} file (similarly for file \texttt{postfix2.scala}). As
-usual you have to prefix the calls with \texttt{CW8a} and
-\texttt{CW8b}, respectively.
-
-
-\begin{lstlisting}[xleftmargin=1mm,numbers=none,basicstyle=\ttfamily\small]
-$ scala -cp postfix.jar
-
-scala> CW8a.syard(CW8a.split("( 5 + 7 ) * 2"))
-val res0: CW8a.Toks = List(5, 7, +, 2, *)
-\end{lstlisting}%$
-
-
-\subsection*{Hints}
-
-\noindent
-\textbf{For the Preliminary Part:} useful operations for determining
-whether a string is a number are \texttt{.forall} and \texttt{.isDigit}.
-One way to calculate the the power operation is to use \texttt{.pow}
-on \texttt{BigInt}s, like \texttt{BigInt(n).pow(m).toInt}.
-\bigskip
-
-
-\subsection*{Preliminary Part (3 Marks, files postfix.scala, postfix2.scala)}
-
-The \emph{Shunting Yard Algorithm} has been developed by Edsger Dijkstra,
-an influential computer scientist who developed many well-known
-algorithms. This algorithm transforms the usual infix notation of
-arithmetic expressions into the postfix notation, sometimes also
-called reverse Polish notation.
-
-Why on Earth do people use the postfix notation? It is much more
-convenient to work with the usual infix notation for arithmetic
-expressions. Most modern pocket calculators (as opposed to the ones used 20
-years ago) understand infix notation. So why on Earth? \ldots{}Well,
-many computers under the hood, even nowadays, use postfix notation
-extensively. For example if you give to the Java compiler the
-expression $1 + ((2 * 3) + (4 - 3))$, it will generate the Java Byte
-code
-
-\begin{lstlisting}[language=JVMIS,numbers=none]
-ldc 1
-ldc 2
-ldc 3
-imul
-ldc 4
-ldc 3
-isub
-iadd
-iadd
-\end{lstlisting}
-
-\noindent
-where the command \texttt{ldc} loads a constant onto the stack, and \texttt{imul},
-\texttt{isub} and \texttt{iadd} are commands acting on the stack. Clearly this
-is the arithmetic expression in postfix notation.\bigskip
-
-\noindent
-The shunting yard algorithm processes an input token list using an
-operator stack and an output list. The input consists of numbers,
-operators ($+$, $-$, $*$, $/$) and parentheses, and for the purpose of
-the assignment we assume the input is always a well-formed expression
-in infix notation. The calculation in the shunting yard algorithm uses
-information about the
-precedences of the operators (given in the template file). The
-algorithm processes the input token list as follows:
-
-\begin{itemize}
-\item If there is a number as input token, then this token is
- transferred directly to the output list. Then the rest of the input is
- processed.
-\item If there is an operator as input token, then you need to check
- what is on top of the operator stack. If there are operators with
- a higher or equal precedence, these operators are first popped off
- from the stack and moved to the output list. Then the operator from the input
- is pushed onto the stack and the rest of the input is processed.
-\item If the input is a left-parenthesis, you push it on to the stack
- and continue processing the input.
-\item If the input is a right-parenthesis, then you pop off all operators
- from the stack to the output list until you reach the left-parenthesis.
- Then you discharge the $($ and $)$ from the input and stack, and continue
- processing the input list.
-\item If the input is empty, then you move all remaining operators
- from the stack to the output list.
-\end{itemize}
-
-\subsubsection*{Tasks (file postfix.scala)}
-
-\begin{itemize}
-\item[(1)] Implement the shunting yard algorithm described above. The
- function, called \texttt{syard}, takes a list of tokens as first
- argument. The second and third arguments are the stack and output
- list represented as Scala lists. The most convenient way to
- implement this algorithm is to analyse what the input list, stack
- and output list look like in each step using pattern-matching. The
- algorithm transforms for example the input
-
- \[
- \texttt{List(3, +, 4, *, (, 2, -, 1, ))}
- \]
-
- into the postfix output
-
- \[
- \texttt{List(3, 4, 2, 1, -, *, +)}
- \]
-
- You can assume the input list is always a list representing
- a well-formed infix arithmetic expression.\hfill[1 Mark]
-
-\item[(2)] Implement a compute function that takes a postfix expression
- as argument and evaluates it generating an integer as result. It uses a
- stack to evaluate the postfix expression. The operators $+$, $-$, $*$
- are as usual; $/$ is division on integers, for example $7 / 3 = 2$.
- \hfill[1 Mark]
-\end{itemize}
-
-\subsubsection*{Task (file postfix2.scala)}
-
-\begin{itemize}
-\item[(3/4)] Extend the code in (1) and (2) to include the power
- operator. This requires proper account of associativity of
- the operators. The power operator is right-associative, whereas the
- other operators are left-associative. Left-associative operators
- are popped off if the precedence is bigger or equal, while
- right-associative operators are only popped off if the precedence is
- bigger.\hfill[1 Marks]
-\end{itemize}
-
-\end{document}
-
-
-%%% Local Variables:
-%%% mode: latex
-%%% TeX-master: t
-%%% End: