Algorithms编程代做、代写Data Structures程序、代写Python编程设计

日期：2021-01-12 11:17

Algorithms & Data Structures 2020/21

Coursework

Konrad Dabrowski & Matthew Johnson

Hand in by 15 January 2021 at 2pm on DUO.

Attempt all questions. Partial credit for incomplete solutions may be given. In written answers,

try to be as precise and concise as possible. Do however not just give us the what but also the

how or why.

The following instructions on submission are important. You need to submit a number of files

and we automate their downloading and some of the marking. If you do not make the submission

correctly some of your work might not be looked at and you could miss out on marks.

You should create a folder called ADS that contains the following files (it is important to get each

name correct):

? q1.ipynb containing the function hash

? q2.pdf containing the written answer to Question 2 and q2.ipynb containing the functions

floodfill stack and floodfill queue

? q3.ipynb containing the functions make palindrome, balanced code and targetsum

? q456.pdf containing your written answers to Questions 4, 5 and 6.

? q6.ipynb containing the functions InsertionSort, Merge3Way and HybridSort

You should not add other files or organise in subfolders. You should create ADS.zip and submit

this single file. Your written answers can be typed or handwritten, but in the latter case it is your

responsibility to make sure your handwriting is clear and easily readable. We will use Python 3

to test your submissions. Please remember that you should not share your work or make it

available where others can find it as this can facilitate plagiarism and you can be penalised. This

requirement applies until the assessment process is completed which does not happen until the

exam board meets in June 2021.

1

1. This question requires you to create a python function to add keys to a hash table. See

the detailed instructions in ADSAssignmentQ1.ipynb. Your submission for this question

should be a single file q1.ipynb containing a function hash. It should not depend on anything

other than the provided class Hash Table() which you do not need to include in

your submission. [15 marks]

2. This question requires you to create two python functions that implement a floodfill algorithm

using stack and queues. See the detailed instructions in ADSAssignmentQ2.ipynb.

Your submission for this question should be a file q2.ipynb containing functions

floodfill stack and floodfill queue, and a document q2.pdf. The function should

not depend on anything other than the provided code which you do not need to include in

your submission. [15 marks]

3. This question requires you to create three python functions that implement recursive algorithms

to solve the three problems described briefly below. See the detailed instructions in

ADSAssignmentQ3.ipynb. Your submission for this question should be a file q3.ipynb

containing functions make palindrome, balanced code and targetsum.

(a) Recall that a palindrome is a string such as abba or radar that reads the same forwards

as backwards. The problem MAKEPALINDROME has as input a string and a nonnegative

integer k and returns true or false according to whether or not the string can

be turned into a palindrome by deleting at most k characters. For example, for inputs

(banana, 1), (apple, 3), (pear, 3), (broccoli, 4) and (asparagus, 4) it returns true because

the palindromes anana, pp, p, occo and saras can be obtained by deleting, respectively,

1, 3, 3, 4 and 4 characters, but for (kiwi, 0) and (spinach, 5) it returns false. [5 marks]

(b) The balanced code of size k is the collection of all binary strings of length 2k such that

for each string the number of zeros in the first k bits is the same as the number of zeros

in the second k bits.

For example the balanced code of size 1 is

00, 11,

the balanced code of size 2 is

0000, 0101, 0110, 1001, 1010, 1111,

and the balanced code of size 3 is

000000, 001001, 001010, 001100, 010001, 010010, 010100, 011011, 011101, 011110

100001, 100010, 100100, 101011, 101101, 101110, 110011, 110101, 110110, 111111.

[5 marks]

(c) The problem TARGETSUM has as input a collection of positive integers S and a further

integer t and requires that numbers from S are selected whose sum t. For example, if

S = 1, 2, 3 and t = 5

then the solution is 2, 3.

And if

S = 1, 4, 5, 8, 12, 16, 17, 20 and t = 23

then the solution is 1,5,17.

Note that the order of the numbers in the solution is not important and that if there is

more than one possible solution, only one needs to be found. [10 marks]

2

Provide your written answers for questions 4, 5 and 6 in a single file q456.pdf. (Note that

python files are also needed for Question 6.)

4. Prove or disprove each of the following statements. We will assume that x > 0, and all

functions are asymptotically positive. That is, for some constant k, f(x) > 0 for all x ≥ k.

You will get 1 mark for correctly identifying whether the statement is True or False, and 1

mark for a correct argument.

(a) 4x

4

is O(2x

3 + 7x + 3). [2 marks]

(b) If f(x) is O(r(x)) and g(x) is O(s(x)) then f(x)/g(x) is O(r(x)/s(x)). [2 marks]

(c) 5x

3 + 2x + 1 is ω(x

2

log x). [2 marks]

(d) 3

2x = Θ(3

x

). [2 marks]

(e) 4x

3 + 6x

2 + 1 is o(x

3

log x). [2 marks]

5. For each of the following recurrences, give an expression for the runtime T(n) if the recurrence

can be solved with the Master Theorem. Otherwise state why the Master Theorem

cannot be applied. You should justify your answers.

(a) T(n) = 25T(n/5) + n

√

n. [3 marks]

(b) T(n) = 16T(n/2) + n

5

. [3 marks]

(c) T(n) = nT(n/3) + n

3

log n. [3 marks]

(d) T(n) = 32T(n/2) ? n log n. [3 marks]

(e) T(n) = 3T(n/3) + n log n. [3 marks]

6. This question requires you to create three python functions that together implement a recursive

sorting algorithm. See the detailed instructions in ADSAssignmentQ6.ipynb.

Your submission for this question should be a file q6.ipynb containing functions

InsertionSort, Merge3Way and HybridSort.

(a) Consider the MergeSort algorithm we have seen in lectures, but suppose we want to

change it in three ways, by changing the order of sorting (from largest to smallest

rather than smallest to largest), changing the base case (use InsertionSort for inputs of

length less than 4) and the number of sub-lists it recurses on (changing from 2 to 3).

Throughout this question, you may assume that no two elements in your list are equal.

? First, implement InsertionSort to sort elements of a list from largest to smallest.

This should work with any number of elements.

? Write a function Merge3Way that takes three lists as input, each sorted from largest

to smallest value and merges them into one list sorted from largest to smallest

value and returns it.

? Write a function HybridSort, which uses your Merge3Way and InsertionSort functions

to implement MergeSort recursing into three sub-lists rather than two. When

you recurse, the length of the three sub-lists must differ by at most 1. Instead of

recursively calling HybridSort until the list to be sorted has length 1, implement a

base case so that if HybridSort is called with fewer than four elements, then your

InsertionSort function is used instead. Your HybridSort function should work on

any length of list.

? You must at no time use any function for sorting that is not your own InsertionSort,

Merge3Way or HybridSort. [20 marks]

(b) What is the worst-case running time of this modified algorithm; find the best O(f(n))

that you can. What is the best-case running time of the algorithm; find the best

?(f(n)) that you can. Justify your answers. [5 marks]

3