Design and Implementation of Bookcase ADT and MString

This assignment consists of two parts: implementing algorithms using ADTs (Abstract Data Types) to solve computational problems, and estimating the worst-case execution time and run-time complexity of a Bookcase method. Part (a) involves finding an empty space in a bookcase, part (b) adds an item to the bookcase, and part (c) counts the number of items of a given media type. The second part focuses on implementing a mutable string ADT with various inspectors and modifiers.

Assignment
This and the next question assess your understanding to solve computational problems by
designing, implementing and analysing algorithms and by using ADTs.
Question 1
Code files to download: TMA01_Q3_Bookcase.py and TMA01_Q3.py
Code file that you can only modify: TMA01_Q3.py
Consider a media management application that manages personal media on computing devices,
including books, films, music and video games. It allows adding, removing, searching items, etc.
You can think of a virtual bookcase containing shelves on which to keep items, as in the
application shown in Figure 1, with rows and columns.
Figure 1 User interface of Apple iBooks
Following good practice, we implement a Bookcase ADT in Python as a class, given in
file TMA01_Q3_Bookcase.py. This file must not be modified. This is an example of using
encapsulation to hide the internal representation of the bookcase from the user or client. You
should have read about the advantages of this approach in Unit 2.
In parts (a) to (c) you are asked to implement three functions that use the Bookcase ADT. Please
make sure you use the ADT, otherwise you will be penalised. Once you added the code for all
functions to file TMA01_Q3.py, you can check it by running the tests in that file.
a. Consider the computational problem of finding an empty space (any one will do) in a bookcase.
Problem: findSpace
Inputs: a Bookcase aBookcase
Preconditions: aBookcase has at least one free space
Outputs: a sequence of two integers (row, column)
Postconditions: aBookcase has no item at the returned row and column
 i.) Write the initial insight for an algorithm to solve the problem. Your algorithm must
use one or more operations of the Bookcase ADT.
 ii.) Implement the algorithm you described, using a tuple to represent the output
sequence. The function header
def findSpace(aBookcase):
is given in file TMA01_Q3.py. Include an assert statement for the precondition.

b. Consider the computational problem of adding an item to the bookcase.
Problem: addItem
Inputs: a Bookcase aBookcase; two strings name and mediaType
Preconditions: neither string is empty
Outputs: a boolean added
Postconditions: added is false if aBookcase had no free position, otherwise it is true
and aBookcase has one free position less, which now has an item with the
given name and mediaType
 i.) Write the initial insight for implementing an algorithm to solve the problem. Use
the findSpace function of part (a).
 ii.) Implement the algorithm you have just described. The function header
def addItem(aBookcase, name, mediaType):
is in the same file. Include any necessary assert statements.
c. Consider the computational problem of counting how many items are there of a given media
type (e.g. film, book, or music).
Problem: countItems
Inputs: a Bookcase aBookcase; a string mediaType
Preconditions: mediaType isn’t empty
Outputs: an integer counter
Postconditions: counter is the number of items in aBookcase that are of the
given mediaType
Write the code to solve that problem. The function header
def countItems(aBookcase, mediaType):
and assertion code are already provided.
d. Estimate the worst-case execution time T(r, c) and the run-time complexity of the Bookcase
method getEmptySpaces, where r is the number of rows/shelves of the bookcase and c is the
number of places per row/shelf. T(r, c) should express the number of assignments involved in
counting the empty spaces on the bookcase. Explain your answer.
(25 marks)

Question 2
Code files to use: TMA01_Q4_MString.py and TMA01_Q4.py
Code file that you can only modify: TMA01_Q4.py
In Python, strings are immutable: no character can be added to, deleted from, or replaced in a
string. To overcome that limitation, we define a mutable string ADT.
ADT: MString
Creator: newMString
Inputs: a Python string aPString
Preconditions: true
Outputs: an MString theMString
Postconditions: theMString has the same text as aPString
Inspector: length
Inputs: an MString theMString
Preconditions: true
Outputs: an integer theLength
Postconditions: theLength is the number of characters in theMString
Inspector: getChar
Inputs: an MString theMString; an integer n
Preconditions: 0 ≤ n < length(theMString)
Outputs: a character theChar
Postconditions: theChar is the (n+1)-th character in theMString
Modifier: setChar
Inputs: an MString theMString; an integer n; a Python string theChar
Preconditions: 0 ≤ n < length(theMString); theChar has length 1
Outputs: theMString
Postconditions: theChar is the (n+1)-th character in theMString
Modifier: addChar
Inputs: an MString theMString; a Python string theChar
Preconditions: theChar has length 1
Outputs: theMString
Postconditions:
 theChar is the last character in post-theMString
 length(post-theMString) = length(pre-theMString) + 1
Inspector: toString

Inputs: an MString theMString
Preconditions: true
Outputs: a Python string aPString
Postconditions: aPString has the same text as theMString
a. Give an invariant for the MString ADT.
(1 mark)
b. An implementation of the MString ADT is given in file TMA01_Q4_MString.py. It includes the
code for the truncate operation that, given n, removes the last n characters of a mutable string.
 i) Specify the truncate operation. Note that although there is no assert statement in
the code, the operation has preconditions.
 ii) Explain the complexity for truncate stated in the file.
(10 marks)