Python Questions

By

TMA02 – Python

Question 1 (30 marks)

The TMA questions and guidance page has all the files mentioned in this question.

More to Read:
Short Questions Political Science

Imagine you are part of a team developing a crossword app that helps the user, e.g. by listing all 3-letter English words ending in ‘t’. For such a feature, it is better to store dictionary words sorted by length instead of alphabetically.

The team lead asks you to write a function that takes a non-empty list of non-empty strings (e.g. [‘hi’, ‘this’, ‘is’, ‘Jane’]) and returns a new list with the same strings in increasing length. Words of the same length must appear in the original order (that’s called a stable sorting). For this example, the result is [‘hi’, ‘is’, ‘this’, ‘Jane’]. You are asked to use this bucket sort algorithm:

Compute the maximum length Lof the words in the list. For the example, L is 4.
Create a list with Lbuckets, each bucket being initially the empty list. For the example, this step creates [[], [], [], []].
Put each word in the right bucket: words of length 1 (like ‘a’ and ‘I’) go in the first bucket, words of length 2 go in the second bucket, etc. For the example, the result of this step is [[], [‘hi’, ‘is’], [], [‘this’, ‘Jane’]]. The first and third buckets remain empty.
Compute the sorted list by first adding the words in bucket 1, then those in bucket 2, etc. For the example, the result of this step is [‘hi’, ‘is’, ‘this’, ‘Jane’].
This part is about Python’s list operations (Python activity 1.5).

Step 2 has been implemented for you in file TMA02_Q1.py. Implement the rest of the algorithm by replacing the pass statements by your code (about 12 lines). You can only use the Python list operations given in the Companion’s appendix. Copy the completed bucket_sorted function into your Solution Document.

We advise you add one step at a time and test it with file TMA02_Q1_tests.py. You should add your own tests. Your tutor will use a different test file, so make sure your code solves the general problem, not just the problem instances (tests) we provide. (12 marks)

Explain how your implementation guarantees the sort to be stable, i.e. keeps the original order of words of the same length. (2 marks)
This part is about algorithmic complexity (Unit 2 Section 4.1and theCompanion).

State and explain the worst-case Big-O complexity of your bucket sort implementation in terms of the number of words n, i.e. the length of the input list. The unit of computation is the assignment. Use the complexities in the Companion’s appendix.

Explain also why the problem size is just the number of words and not dependent on the number of buckets L too. (5 marks)

This part is about heap sort (Unit 3 Section 4.2) and the professional skill of comparing alternative approaches.

A team member suggests it would be easier to just take heap sort and in the percolation process replace every comparison of strings in the heap by the comparison of their lengths, i.e. x < y becomes len(x) How to create Testimonial Carousel using Bootstrap5

Clients' Reviews about Our Services