Designing and Implementing Algorithms for Media Management and Mutable String ADT
Added on -2019-09-16
This assignment assesses the understanding of designing and implementing algorithms and using ADTs to solve computational problems. The first question involves implementing functions using the Bookcase ADT to solve problems related to media management. The second question involves understanding and using the MString ADT to perform operations on mutable strings. The output is in JSON format.
| 4 pages
| 1019 words
| 453 views
Trusted by 2+ million users, 1000+ happy students everyday
AssignmentThis and the next question assess your understanding to solve computational problems by designing, implementing and analysing algorithms and by using ADTs.Question 1Code files to download:TMA01_Q3_Bookcase.pyandTMA01_Q3.pyCode file that you can only modify:TMA01_Q3.pyConsider 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.Figure1User interface of Apple iBooksFollowing good practice, we implement a Bookcase ADT in Python as a class, given in fileTMA01_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. Pleasemake sure you use the ADT, otherwise you will be penalised. Once you added the code for all functions to fileTMA01_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: findSpaceInputs: a BookcaseaBookcasePreconditions:aBookcasehas at least one free spaceOutputs: a sequence of two integers(row, column)Postconditions:aBookcasehas no item at the returnedrowandcolumni.) Write the initial insight for an algorithm to solve the problem. Your algorithmmust 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 headerdef findSpace(aBookcase):is given in fileTMA01_Q3.py. Include anassertstatement for the precondition.
b. Consider the computational problem of adding an item to the bookcase.Problem: addItemInputs: a BookcaseaBookcase; two stringsnameandmediaTypePreconditions: neither string is emptyOutputs: a booleanaddedPostconditions:addedis false ifaBookcasehad no free position, otherwise it is true andaBookcasehas one free position less, which now has an item with the givennameandmediaTypei.) Write the initial insight for implementing an algorithm to solve the problem. Use thefindSpacefunction of part (a).ii.) Implement the algorithm you have just described. The function headerdef addItem(aBookcase, name, mediaType):is in the same file. Include any necessaryassertstatements.c. Consider the computational problem of counting how many items are there of a given media type (e.g. film, book, or music).Problem: countItemsInputs: a BookcaseaBookcase; a stringmediaTypePreconditions:mediaTypeisn’t emptyOutputs: an integercounterPostconditions:counteris the number of items inaBookcasethat are of the givenmediaTypeWrite the code to solve that problem. The function headerdef countItems(aBookcase, mediaType):and assertion code are already provided.d. Estimate theworst-caseexecution time T(r, c) and the run-time complexity of the Bookcase methodgetEmptySpaces, whereris the number of rows/shelves of the bookcase andcis the number of places per row/shelf. T(r, c) should express thenumber of assignmentsinvolved in counting the empty spaces on the bookcase. Explain your answer.(25marks)
Found this document preview useful?
You are reading a preview Upload your documents to download or Become a Desklib member to get accesss