$($a$)$ The game of Boggle involves trying to make words from a $44$

grid of randomly selected letters. Players are allowed to start a

word in any position, and move up$,$ down, left, right or diagonally

to spell out a word, without retracing any steps. Explain how the

problem of finding words in the grid could be coded up as either

a depth$-$first search or a breadth$-$first search. Give a general

outline of how you would structure this program.

$($b$)$ Define the concepts of $P$ problems, NP problems and NP$-$

complete problems. Explain what the $P=?$ NP problem is$,$ and

outline its significance for computer science.

$($c$)$ Show how Dijkstra's algorithm would find the shortest path

between the start and finish for the weighted undirected graph

$[5$ marks$]$

$[7$ marks$]$

represented by the adjacency matrix below. What is the shortest

path and what is its length?

$($d$)$ Provide an overview of the Rabin$-$Karp string searching

algorithm. Why is this algorithm useful for detecting plagiarism?