Q4 String Register (25 marks)¶
We want to design a data structure which we will call a register and which has the following properties:
• It stores strings of characters belonging to an alphabet $A$. We denote $c$ the total number of characters in the alphabet $A$. $A$ can be set to be any set of characters, e.g. $\{a, b, c\}$, or $\{0, \dots,9\}$, or $\{a, \dots, z, A, \dots, Z\}$.
• The operation to determine whether a string of size $k$ belongs to the register takes $O(\log c \times \log k)$ runtime in the worst case.
• Adding a string to the register takes $O(c \log k)$ runtime in the worst case.
• Removing a string from the register takes $O(\log c \times \log k)$ runtime in the worst case.
Note that the runtime complexities are independent of the number of elements stored in the register. Finally, remark that a string and (some of) its substring can all belong to the register.
Q4.1 (22 marks)¶
Without using other data structures than Python lists, describe a data structure which meets the requirements described above. We recommend using a tree.
If you cannot find a way to meet the runtime requirements, provide an algorithm and implementation anyway. You may get up to half of the marks for doing so.
(write your answer here)
Implement this algorithm:
In [0]:
#TODO implement the algorithm
Using the module unittest, write unit tests for your class. To obtain full marks, you need to write unit tests which extensively cover all cases. We recommend using the module random. Note that this question will only be marked if you provide both a functional program and unit tests. You will only receive marks for features which are implemented and tested convincingly.
In [0]:
import unittest
#TODO implement unit tests.
Q4.2 (3 marks)¶
Determine and prove the worst-case runtime complexity of each of the core operations of the register.
(write your answer here)