Task 2 Written Part
Definitions and Assumptions
• Boggle Board:
– A Boggle board is a grid of size n × n, where n is a positive integer.
Each cell of the grid contains a single letter from a specified alphabet.
• Word Definition:
– A word in Boggle is any sequence of letters formed by moving from
one cell to an adjacent cell, including horizontal, vertical, and diag-
onal neighbors. The word can be of any length from 1 to n2 letters.
A word can be any combination of letters.
• Alphabet Size:
– The alphabet size x denotes the number of distinct letters that can
be used on the Boggle board.
Current Complexity
In the current setup of Boggle where letters can be reused:
• Branching Factor: After the initial move, each subsequent move is lim-
ited to a branching factor of 7, as the previous square cannot be revisited.
This reduces the number of paths the algorithm must explore from any
starting point to a maximum of 7 after the initial step.
• Recurrence Relation:
– Base Case: For a single letter, the complexity is T (1) = n2, as every
cell in the grid can be a starting point.
– First Move: For the first move, the complexity is T (2) = T (1) × 8,
since there are eight possible directions to move from any starting
point.
– Subsequent Moves: For k ≥ 3 until n2 − 1, the recurrence relation
becomes T (k) = T (k − 1) × 7, as each subsequent move is constrained
to the remaining 7 directions. The last square can’t have any valid
moves as all other squares in the board have been visited.
6
• Big O Complexity: The overall complexity is:
T (k) = O

n2 × 7(n2−2)
Impact of Disallowing Repeated Letters on Com-
plexity And Using A Memoization Table
Memoization and Complexity
To analyze the theoretical Big O runtime of the algorithm using a DFS approach
with a memoization table, we consider the following factors:
• Position (x, y) on the board: There are n2 possible positions on an n × n
board.
• State of the Visited Cells Array: Each of the n2 cells can either be
visited or not, resulting in 2n2
possible states.
• State of the Used Letters Array: Each letter in the alphabet (size X)
can either be used or not, resulting in 2X possible states.
Combining the Components
To determine the total number of unique memoization states, we multiply the
number of possibilities for each component:
• Positions: n2
• States of the visited array: 2n2
• States of the used letters array: 2X
Thus, the total number of unique memoization states is:
n2 × 2n2
× 2X
Theoretical Big O Runtime
Considering memoization, the complexity can be expressed as:
O

n2 · 2n2+X 
7
Explanation
• The term n2 represents the number of starting points (each cell in the
grid).
• The 2n2
term accounts for the exponential number of possible states for
the visited cells array.
• The 2X term accounts for the exponential number of possible states for
the used letters array.
Handling Word Length Implicitly
In Boggle, the word lengths vary from 1 to n2. This variation in word lengths
is implicitly managed by the states of the visited array:
• As the DFS progresses, the visited array keeps track of the cells that have
been included in the current path.
• Each unique state of the visited array corresponds to a specific sequence
of cells visited, which directly correlates to the length of the word formed
so far.
• For example, if the visited array has 5 cells marked as visited, it implies
that the current word being formed is of length 5.
• Thus, different lengths of words are naturally represented by the different
states of the visited array as the DFS explores various paths on the board.
Conclusion
Under the new rule that each letter can only be used once per word, the theo-
retical Big O runtime of the algorithm using a DFS approach with memoization
is:
O

n2 · 2n2+X 
Practical Implications
By limiting each letter to a single use per word:
• The algorithm reduces the number of recursive calls and the depth of the
search tree it needs to construct and traverse.
• This leads to quicker decision paths and potentially faster identification
of valid words.
Overall, this rule modification simplifies the computational task, ensuring
more efficient processing and addressing the issue of performance degradation
in scenarios where letters are frequently repeated on the 
Task 2: Boggle Buddy

The game of Boggle is normally played on a 4x4 grid. 16 dice, each die printed with six characters from the letters A to Z, are placed in a closed container and the container is shaken. The dice land in the 4x4 grid and the letter on the top face is the letter for that grid square. A three-minute timer is typically started and players try and make as many words from the letters on the grid as they can before time runs out. These words have to follow certain rules - for this task we will assume the rules followed are:

    Each letter (except for the first letter) must be adjacent (horizontally, vertically or diagonally) to its preceding letter.

    A grid square's letter can only be used once (if there are two copies of the same letter appearing in different grid squares - both can be used).

    The word must be one of the allowed words.

Though there are additional rules when played as a group of players, but points are assigned for the total number of letters in all valid words made.
Part C (Written)

The parents notice the program often takes time to think of solutions, but only on boggle games where the same letter appears lots of times. Given the sand timer for thinking of words gives such a short time, they ask if there's a way to speed it up, for example, if each letter can only be used once in each word (even if it appears more than once on the board). How might their rule modification change the worst case complexity of finding all words?
Task 2: Prefix Tries and Boggle Graphs
Background - Prefix Tries

For Task 2, you will need to build a prefix trie. This is a data structure where, rather than containing a full key in each node, each edge in the trie represents a particular letter. Since each edge is associated with a character, both checking whether a given string is in the tree and finding all strings that match a given prefix are efficient operations.

For example, to store the strings "ham", "hat", "hi" and "who", our prefix tree might look like:

For simplicity, the tree will:

    Contain a pointer for each possible following character - even if that character is unlikely to appear.

    Also store the \0 character used as the delimiter when storing the string in the tree. 

This means every node will contain 256 pointers - the majority of most of which are typically set to NULL. This also means each leaf of the tree will correspond to the completion of an inserted string - with completion of strings occurring nowhere else in the tree.
Background - Boggle Graphs

For a given set of dice, a graph can be constructed showing the connections.

This graph can then be used to work out what are valid words to play. For example, the word "open" could be played, starting from O:
Part C (Written)

In Part C, you must create a pdf format document called written-tasks.pdf, which explains the impact of only allowing each letter to appear once in each word (regardless of how many times the letter appears on the board). Your answer must state an upper-bound on the time complexity reflecting the impact of this change, with each term used explained clearly.

In order to avoid trivial answers, you must assume the board could be extended arbitrarily to higher dimensions (e.g. 5x5 and beyond) and that the alphabet used could increase in size (e.g. the maximum length of a word is not 26 letters).
2C[-0.5]: You had some very good arguments when discussing the complexity of part 2A. But the discussion on the main topic is not good enough, and the complexity seems inaccurate for part C
Analyse the above answer and see what is the error in my complexity and fix it based on the above information
State all theory used in your answer and link it to the problem at hand
you must WITHOUT FALI WRITE THE ANSWER IN OVERLEAF LATEX NOTAITON FOR THE OVERLEAF ONLINE TYPESETTER