SEMT20001: Principles of Computational Modelling
COURSEWORK ASSESSMENT: QUESTION 1
Question 1: Computability & Complexity
(a) By adapting your solution to Worksheet 2 Q7 implement a Turing Machine in Python which when given a string of n 1s as input, outputs a string of 2n + 2 1s. (6 marks)
(b) A recursive version of bubble sort is as follows: For k buckets and the unsorted list list,
● Let l be the total number of distinct elements in list. If l = 0 or l = 1 then list is sorted. Else,
● Let mx = max(list) and m = min(list) and determine ∆ = k/mx-m . Then define k buckets as the intervals Bi = [m+(i-1)∆, m+i∆) for i = 1,..., k - 1 and Bk = [m+(k -1)∆, mx].
● Allocate the elements of list to the buckets.
● Then recursively bucket sort each of the buckets.
Write your own well documented Python code for recursive bucket sort bucketsort which takes as inputs an unsorted list list and the number of buckets k, and returns the relevant sorted list. Explain your design and implementation decisions, and any tests used to verify and validate the code. (5 marks)
(c) Write Python code to evaluate the average run time of your version of bucketsort as a function of list length. Specifically, for a given list length n and number of buckets k your code should evaluate the run time for sorting 100 random permutations of the list range(1,n+1) using bucketsort with k buckets, and returns the average of these times. Explain your design and implementation decisions, and any tests used to verify and validate the code. (4 marks)
(d) Use this code to compare the time complexity for bucketsort when k = 2 and k = n. Plot average run time for k = 2 and k = n for n from 2 to 500. For k = 2 use polyfit to fit a function an log(n)+b relating n and average run time, and plot this function together with average run time against n. For k = n use polyfit to fit a function an2 + bn + c relating n and average run time, and plot this function together with average run time against n. Taking account of these results express the average time complexity for bucketsort with k = 2 and k = n using big O notation. (4 marks)
(e) Since for each list size n we are sorting permutations of range(1,n+1) then on average we can expect there to be close to a uniform number of elements in each bucket, i.e. k/n . Hence, the expected run time of bubblesort with k buckets on a list of size n satisfies;
where the term kn is the time required for allocating each of the n elements to one of the k buckets.
Use this expression to determine O(ˆT) when k = 2 and k = n. (6 marks)