\section*{Coursework 7 (Scala)}

This coursework is worth 10\%. The first and second part are due

measuring similarity in texts, and for recommending movies

what the function \texttt{occurrences} produces: for this you just need

scala> CW7a.occurrences(List("a", "b", "b"))

\noindent

\textbf{For Part 1:} useful operations involving regular

expressions:

\[\texttt{reg.findAllIn(s).toList}\]

\noindent finds all

substrings in \texttt{s} according to a regular regular expression

\texttt{reg}; useful list operations: \texttt{.distinct}

removing duplicates from a list, \texttt{.count} counts the number of

elements in a list that satisfy some condition, \texttt{.toMap}

transfers a list of pairs into a Map, \texttt{.sum} adds up a list of

integers, \texttt{.max} calculates the maximum of a list.\bigskip

\noindent

\textbf{For Part 2 + 3:} use \texttt{.split(",").toList} for splitting

strings according to commas (similarly $\backslash$\texttt{n}),

\texttt{.getOrElse(..,..)} allows to querry a Map, but also gives a

default value if the Map is not defined, a Map can be `updated' by

using \texttt{+}, \texttt{.contains} and \texttt{.filter} can test whether

an element is included in a list, and respectively filter out elements in a list,

\texttt{.sortBy(\_.\_2)} sorts a list of pairs according to the second

elements in the pairs---the sorting is done from smallest to highest,

\texttt{.take(n)} for taking some elements in a list (takes fewer if the list

contains less than \texttt{n} elements).

It seems source code plagiarism---stealing and submitting someone

else's code---is a serious problem at other

universities.\footnote{Surely, King's students, after all their

  instructions and warnings, would never commit such an offence. Yes?}

Detecting such plagiarism is time-consuming and disheartening for

lecturers at those universities. To aid these poor souls, let's

implement in this part a program that determines the similarity

between two documents (be they source code or texts in English). A

document will be represented as a list of strings.

\item[(1)] Implement a function that `cleans' a string by finding all

  (proper) words in this string. For this use the regular expression

  \texttt{$\backslash$w+} for recognising word characters and the

  library function \texttt{findAllIn}. The function should return a

  document (a list of

  strings).\\

\item[(2)] In order to compute the overlap between two documents, we

  strings in a document and how many times these strings occur in the

  the number of string-occurrences in a document is as follows: remove

  Return a Map associating strings with occurrences. For example

  \pcode{occurrences(List("a", "b", "b", "c", "d"))}

  \pcode{occurrences(List("d", "b", "d", "b", "d"))}

\item[(3)] You can think of the Maps calculated under (2) as memory-efficient

  implement the \emph{product} of two such vectors, sometimes also called

  \emph{dot product} of two vectors.\footnote{\url{https://en.wikipedia.org/wiki/Dot_product}}

  For this dot product, implement a function that takes two documents

  corresponding occurrences in each document. If a string does not

  occur in one of the documents, then the product for this string is zero. At the end

  you need to add up all products. For the two documents in (2) the dot

  product is 7, because

    \underbrace{1 * 3}_{"d"} \qquad = 7

  You can expect this function to return a \texttt{Double} between 0 and 1. The

  Second, implement a function that calculates the similarity of

  two strings, by first extracting the substrings using the clean

  function from (1)

  and then calculating the overlap of the resulting documents.\\

  \mbox{}\hfill\mbox{[1 Mark]}

\end{itemize}\bigskip

\subsection*{Part 2 (2 Marks, file danube.scala)}

You are creating Danube.co.uk which you hope will be the next big thing

in online movie renting. You know that you can save money by

anticipating what movies people will rent; you will pass these savings

on to your users by offering a discount if they rent movies that

Danube.co.uk recommends.  

Your task is to generate \emph{two} movie recommendations for every

movie a user rents. To do this, you calculate what other

renters, who also watched this movie, suggest by giving positive ratings.

Of course, some suggestions are more popular than others. You need to find

the two most-frequently suggested movies. Return fewer recommendations,

if there are fewer movies suggested.

The calculations will be based on the small datasets which the research lab

GroupLens provides for education and development purposes.

\begin{center}

\url{https://grouplens.org/datasets/movielens/}

\end{center}

\noindent

The slightly adapted CSV-files should be downloaded in your Scala

file from the URLs:

\begin{center}

\begin{tabular}{ll}  

  \url{https://nms.kcl.ac.uk/christian.urban/ratings.csv} & (940 KByte)\\

  \url{https://nms.kcl.ac.uk/christian.urban/movies.csv}  & (280 KByte)\\

\end{tabular}

\end{center}

\noindent

The ratings.csv file is organised as userID, 

movieID, and rating (which is between 0 and 5, with \emph{positive} ratings

being 4 and 5). The file movie.csv is organised as

movieID and full movie name. Both files still contain the usual

CSV-file header (first line). In this part you are asked

to implement functions that process these files. If bandwidth

is an issue for you, download the files locally, but in the submitted

version use \texttt{Source.fromURL} instead of \texttt{Source.fromFile}.

\subsection*{Tasks}

\begin{itemize}

\item[(1)] Implement the function \pcode{get_csv_url} which takes an

  URL-string as argument and requests the corresponding file. The two

  URLs of interest are \pcode{ratings_url} and \pcode{movies_url},

  which correspond to CSV-files mentioned above.  The function should

  return the CSV-file appropriately broken up into lines, and the

  first line should be dropped (that is omit the header of the CSV-file).

  The result is a list of strings (the lines in the file). In case

  the url does not produce a file, return the empty list.\\

  \mbox{}\hfill [1 Mark]

\item[(2)] Implement two functions that process the (broken up)

  CSV-files from (1). The \pcode{process_ratings} function filters out all

  ratings below 4 and returns a list of (userID, movieID) pairs. The

  \pcode{process_movies} function returns a list of (movieID, title) pairs.\\

  \mbox{}\hfill [1 Mark]

\end{itemize}  

\subsection*{Part 3 (4 Marks, file danube.scala)}

\subsection*{Tasks}

\begin{itemize}

\item[(3)] Implement a kind of grouping function that calculates a Map

  containing the userIDs and all the corresponding recommendations for

  this user (list of movieIDs). This should be implemented in a tail

  recursive fashion using a Map as accumulator. This Map is set to

  \pcode{Map()} at the beginning of the calculation. For example

\begin{lstlisting}[numbers=none]

val lst = List(("1", "a"), ("1", "b"),

               ("2", "x"), ("3", "a"),

               ("2", "y"), ("3", "c"))

groupById(lst, Map())

\end{lstlisting}

returns the ratings map

\begin{center}

  \pcode{Map(1 -> List(b, a), 2 -> List(y, x), 3 -> List(c, a))}.

\end{center}

\noindent

In which order the elements of the list are given is unimportant.\\

\mbox{}\hfill [1 Mark]

\item[(4)] Implement a function that takes a ratings map and a movieID

  as argument.  The function calculates all suggestions containing the

  agiven movie in its recommendations. It returns a list of all these

  recommendations (each of them is a list and needs to have the given

  movie deleted, otherwise it might happen we recommend the same movie

  ``back''). For example for the Map from above and the movie

  \pcode{"y"} we obtain \pcode{List(List("x"))}, and for the movie

  \pcode{"a"} we get \pcode{List(List("b"), List("c"))}.\\

  \mbox{}\hfill [1 Mark]

\item[(5)] Implement a suggestions function which takes a ratings map

  and a movieID as arguments. It calculates all the recommended movies

  sorted according to the most frequently suggested movie(s) sorted

  first. This function returns \emph{all} suggested movieIDs as a list of

  strings.\\

  \mbox{}\hfill [1 Mark]

\item[(6)]  

  Implement then a recommendation function which generates a maximum

  of two most-suggested movies (as calculated above). But it returns

  the actual movie name, not the movieID. If fewer movies are recommended,

  then return fewer than two movie names.\\

  \mbox{}\hfill [1 Mark]

\end{itemize}