268
|
1 |
% !TEX program = xelatex
|
6
|
2 |
\documentclass{article}
|
426
|
3 |
\usepackage{../styles/style}
|
166
|
4 |
\usepackage{disclaimer}
|
426
|
5 |
\usepackage{../styles/langs}
|
6
|
6 |
|
|
7 |
\begin{document}
|
|
8 |
|
|
9 |
|
329
|
10 |
%% should ask to lower case the words.
|
|
11 |
|
396
|
12 |
\section*{Core Part 2 (Scala, 3 Marks)}
|
6
|
13 |
|
264
|
14 |
\mbox{}\hfill\textit{``What one programmer can do in one month,}\\
|
|
15 |
\mbox{}\hfill\textit{two programmers can do in two months.''}\smallskip\\
|
276
|
16 |
\mbox{}\hfill\textit{ --- Frederick P.~Brooks (author of The Mythical Man-Month)}\bigskip\medskip
|
264
|
17 |
|
411
|
18 |
\IMPORTANTNONE{}
|
202
|
19 |
|
|
20 |
\noindent
|
144
|
21 |
Also note that the running time of each part will be restricted to a
|
202
|
22 |
maximum of 30 seconds on my laptop.
|
39
|
23 |
|
166
|
24 |
\DISCLAIMER{}
|
39
|
25 |
|
|
26 |
|
202
|
27 |
\subsection*{Reference Implementation}
|
45
|
28 |
|
306
|
29 |
Like the C++ part, the Scala part works like this: you
|
202
|
30 |
push your files to GitHub and receive (after sometimes a long delay) some
|
306
|
31 |
automated feedback. In the end we will take a snapshot of the submitted files and
|
268
|
32 |
apply an automated marking script to them.\medskip
|
45
|
33 |
|
268
|
34 |
\noindent
|
306
|
35 |
In addition, the Scala part comes with reference
|
|
36 |
implementations in form of \texttt{jar}-files. This allows you to run
|
474
|
37 |
any test cases on your own computer. For example you can call \texttt{scala-cli} on
|
471
|
38 |
the command line with the option \texttt{--extra-jars docdiff.jar} and then
|
202
|
39 |
query any function from the template file. Say you want to find out
|
203
|
40 |
what the function \texttt{occurrences} produces: for this you just need
|
396
|
41 |
to prefix it with the object name \texttt{C2}. If you want to find out what
|
202
|
42 |
these functions produce for the list \texttt{List("a", "b", "b")},
|
|
43 |
you would type something like:
|
6
|
44 |
|
202
|
45 |
\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
|
471
|
46 |
$ scala-cli --extra-jars docdiff.jar
|
202
|
47 |
|
396
|
48 |
scala> C2.occurrences(List("a", "b", "b"))
|
202
|
49 |
...
|
|
50 |
\end{lstlisting}%$
|
|
51 |
|
|
52 |
\subsection*{Hints}
|
6
|
53 |
|
203
|
54 |
\noindent
|
396
|
55 |
\textbf{For the Core Part 2:} useful operations involving regular
|
203
|
56 |
expressions:
|
|
57 |
\[\texttt{reg.findAllIn(s).toList}\]
|
|
58 |
\noindent finds all
|
|
59 |
substrings in \texttt{s} according to a regular regular expression
|
|
60 |
\texttt{reg}; useful list operations: \texttt{.distinct}
|
|
61 |
removing duplicates from a list, \texttt{.count} counts the number of
|
|
62 |
elements in a list that satisfy some condition, \texttt{.toMap}
|
|
63 |
transfers a list of pairs into a Map, \texttt{.sum} adds up a list of
|
|
64 |
integers, \texttt{.max} calculates the maximum of a list.\bigskip
|
45
|
65 |
|
39
|
66 |
|
|
67 |
|
202
|
68 |
\newpage
|
396
|
69 |
\subsection*{Core Part 2 (3 Marks, file docdiff.scala)}
|
6
|
70 |
|
396
|
71 |
It seems plagiarism---stealing and submitting someone
|
203
|
72 |
else's code---is a serious problem at other
|
|
73 |
universities.\footnote{Surely, King's students, after all their
|
|
74 |
instructions and warnings, would never commit such an offence. Yes?}
|
|
75 |
Detecting such plagiarism is time-consuming and disheartening for
|
|
76 |
lecturers at those universities. To aid these poor souls, let's
|
|
77 |
implement in this part a program that determines the similarity
|
|
78 |
between two documents (be they source code or texts in English). A
|
|
79 |
document will be represented as a list of strings.
|
6
|
80 |
|
|
81 |
|
202
|
82 |
\subsection*{Tasks}
|
45
|
83 |
|
|
84 |
\begin{itemize}
|
203
|
85 |
\item[(1)] Implement a function that `cleans' a string by finding all
|
396
|
86 |
(proper) words in the string. For this use the regular expression
|
276
|
87 |
\texttt{\textbackslash{}w+} for recognising words and the library function
|
|
88 |
\texttt{findAllIn}. The function should return a document (a list of
|
396
|
89 |
strings).
|
|
90 |
\mbox{}\hfill\mbox{[0.5 Marks]}
|
45
|
91 |
|
203
|
92 |
\item[(2)] In order to compute the overlap between two documents, we
|
202
|
93 |
associate each document with a \texttt{Map}. This Map represents the
|
203
|
94 |
strings in a document and how many times these strings occur in the
|
202
|
95 |
document. A simple (though slightly inefficient) method for counting
|
203
|
96 |
the number of string-occurrences in a document is as follows: remove
|
202
|
97 |
all duplicates from the document; for each of these (unique)
|
|
98 |
strings, count how many times they occur in the original document.
|
203
|
99 |
Return a Map associating strings with occurrences. For example
|
6
|
100 |
|
45
|
101 |
\begin{center}
|
203
|
102 |
\pcode{occurrences(List("a", "b", "b", "c", "d"))}
|
45
|
103 |
\end{center}
|
|
104 |
|
202
|
105 |
produces \pcode{Map(a -> 1, b -> 2, c -> 1, d -> 1)} and
|
45
|
106 |
|
|
107 |
\begin{center}
|
203
|
108 |
\pcode{occurrences(List("d", "b", "d", "b", "d"))}
|
48
|
109 |
\end{center}
|
45
|
110 |
|
202
|
111 |
produces \pcode{Map(d -> 3, b -> 2)}.\hfill[1 Mark]
|
6
|
112 |
|
203
|
113 |
\item[(3)] You can think of the Maps calculated under (2) as memory-efficient
|
202
|
114 |
representations of sparse ``vectors''. In this subtask you need to
|
203
|
115 |
implement the \emph{product} of two such vectors, sometimes also called
|
|
116 |
\emph{dot product} of two vectors.\footnote{\url{https://en.wikipedia.org/wiki/Dot_product}}
|
148
|
117 |
|
203
|
118 |
For this dot product, implement a function that takes two documents
|
202
|
119 |
(\texttt{List[String]}) as arguments. The function first calculates
|
|
120 |
the (unique) strings in both. For each string, it multiplies the
|
203
|
121 |
corresponding occurrences in each document. If a string does not
|
|
122 |
occur in one of the documents, then the product for this string is zero. At the end
|
|
123 |
you need to add up all products. For the two documents in (2) the dot
|
|
124 |
product is 7, because
|
45
|
125 |
|
|
126 |
\[
|
202
|
127 |
\underbrace{1 * 0}_{"a"} \;\;+\;\;
|
|
128 |
\underbrace{2 * 2}_{"b"} \;\;+\;\;
|
|
129 |
\underbrace{1 * 0}_{"c"} \;\;+\;\;
|
203
|
130 |
\underbrace{1 * 3}_{"d"} \qquad = 7
|
202
|
131 |
\]
|
|
132 |
|
|
133 |
\hfill\mbox{[1 Mark]}
|
|
134 |
|
|
135 |
\item[(4)] Implement first a function that calculates the overlap
|
|
136 |
between two documents, say $d_1$ and $d_2$, according to the formula
|
|
137 |
|
|
138 |
\[
|
|
139 |
\texttt{overlap}(d_1, d_2) = \frac{d_1 \cdot d_2}{max(d_1^2, d_2^2)}
|
45
|
140 |
\]
|
|
141 |
|
316
|
142 |
where $d_1^2$ means $d_1 \cdot d_1$ and so on.
|
203
|
143 |
You can expect this function to return a \texttt{Double} between 0 and 1. The
|
474
|
144 |
overlap between the lists in Task (2) is $0.5384615384615384$.
|
202
|
145 |
|
203
|
146 |
Second, implement a function that calculates the similarity of
|
|
147 |
two strings, by first extracting the substrings using the clean
|
|
148 |
function from (1)
|
|
149 |
and then calculating the overlap of the resulting documents.\\
|
346
|
150 |
\mbox{}\hfill\mbox{[0.5 Marks]}
|
|
151 |
\end{itemize}
|
203
|
152 |
|
6
|
153 |
|
268
|
154 |
\end{document}
|
6
|
155 |
|
|
156 |
%%% Local Variables:
|
|
157 |
%%% mode: latex
|
|
158 |
%%% TeX-master: t
|
|
159 |
%%% End:
|