Week 4

Question 1

what is a bucket sort?

Answer 1

• it uses keys as indices of a bucket B that has entries within an integer range [0,1,…N-1]
• so it has size |N|
• inially all items from the input sequence are moved to appropriate buckets, so an item with key K is moved to bucket B[k]
• Then move all items back into the sequence according to their order of appearance in consecutive buckets B[0], B[1],… B[N-1]

Question 2

What is the time complexity of a bucket sort?

Answer 2

• we have a for loop to run through every element which is O(n)
• and then for each of the buckets we remove every item so this is O(N+n)

Question 3

What is a radix sort?

Answer 3

• A radix sort uses bucket sorts with columns
• Can use it to order/compare words or fixed length numbers
• Can start from either the most or least significant bit, going column by column
• so on the first column, it compares the first bit of each item by doing a bucket sort, it then moves onto the next column if the items are equal

Question 4

What is the time complexity of a radix sort

Answer 4

d is the number of columns it has to perform a bucket sort on, so the time complexity = O(d*(N+n))

Question 5

How do we perform a radix sort on words of uneven length?

Answer 5

We make the words equal length by introducing a dummy character, that doesn’t belong to the alphabet, repeatedly for each extra character to make them equal length, then we can compare them.
- we class the dummy character as smaller than any letter in the alphabet (since it’s an empty space) so at_ _ will always be smaller than ata_

Question 6

When is a sorting algorithm described as stable?

Answer 6

If it is order preserving
- so if there’s a tie on the ith column, then the original order of the two elements remains unchanged
-

Question 7

Why does choosing to go from left to right (MSB) or right to left (LSB) make a difference in Radix sorting?

Answer 7

Depending on what you’re sorting, it could mean it sorts it into the wrong order
- for example since we read words from left to right, we have to compare them using the leftmost or most significant bit
- but since we ready binary numbers from the left, we need to compare them using the rightmost bit or least significant bit
- otherwise the comparison would be wrong!

Question 8

If we have integers of 6 digits and 4 digits long, and we perform a radix sort, what is the value of d?

Answer 8

• the value of d = 6, since we have to make the numbers the same length (by padding the 4 digit number with two dummy characters), so we have to compare 6 columns

Question 9

What type of algorithm is a merge sort?

Answer 9

A divide and conquer algorithm

Question 10

What type of algorithm is a quicksort?

Answer 10

• It’s similar to a divide and conquer accept that it doesn’t divide the problem into equal size subproblems
• with the randomised pivot, it aims to divide them into roughly equal sized problems

Question 11

What is the general outline for using the divide and conquer method?

Answer 11

• divide: if the input is small, directly solve (use a base case), otherwise divide input into smaller disjoint sets
• recur: recursively solve the associated subproblems (that use disjoint sets)
• conquer: take solutions of subproblems and merge them into a solution for the original problem

Question 12

How do we analyse the running time of a divide and conquer algorithm?

Answer 12

we use a recurrence relation T(n) which denotes running time based on input size n

Question 13

What is the recurrence relation we use to characterise running time of a merge sort?

Answer 13

T(n) = {c if n < 2, 2T(n/2)+cn if otherwise}
- since if the list is smaller than 2, we know if the item is found or not, else wise keep dividing the list cn and doing the comparison - n

Question 14

What is a recurrence relation?

Answer 14

An equation that defines a sequence based on a rule that gives the next term as a function of the previous terms

Question 15

What is the recurrence relation for a binary search?

Answer 15

• T(n) = {c if n < 2, T(n/2) + c}
  where c is the time to find the midpoint of the list and do the comparison
• each time we halve our data we add a constant c
• if we only have one element in the list it takes constant time to check if it’s the item we want

Question 16

What is the substitution method?

Answer 16

one method of solving a divide and conquer recurrence equation is to use the iterative substitution method, called plug and chug

Question 17

Why can we replace the 2*T(n/2^i) in a recurrence relation?

Answer 17

Since we know that T(n/2^i) = 1 so we can exchange it for c since T(n) = c when n < 2

Question 18

What is a general equation for a recurrence relation if we were to guess it

Answer 18

T(n) = {c if n <= d, a*T(n/b)+f(n) if n > d}

Question 19

What conclusions about the asymptotic form of T(n) can we draw from T(n) = {c if n <= d, a*T(n/b)+f(n) if n > d}?

Answer 19

• If f(n) is smaller than n^logb(a) then the first term is going to dominate the sum, so T(n) = Θ(n^logb(a)
• If n^logb(a) is smaller that f(n) is going to dominate the sum, so T(n) = f(n)

Question 20

what is case 1 of the master method?

Answer 20

where e > 0, if f(n) is O(n^logn(a-e)) then T(n) = Θ(n^logb(a))

Question 21

what is case 2 of the master method?

Answer 21

if f(n) is Θ(n^logb(a)log^k(n)) then T(n) = Θ(n^logb(a)log^k+1(n))

Question 22

what is case 3 of the master method?

Answer 22

e > 0 and k < 1, if f(n) is Ω(n^logb(a+e)) where af(n/b) <= kf(n/b) and n >= d then T(n) = Θ(f(n))

Question 23

How can we change the recurrence 2T(n^1/2) + logn into a form that allows us to use the master method?

Answer 23

• T(n) = 2T(n^1/2) + logn
• introduce k = logn
• T(n) - T(2^k) = 2T(2^k/2) + k
• substitute this into new function S(k) = T(2^k) =
• S(k) = 2S(k/2) + k

Question 24

What is it called when we have to introduce a new function S using substitution to get the recurrence relation into the correct form to use the master method?

Answer 24

A variable change

Question 25

What is the problem size of multiplying two numbers with n digits each? and what is the naive time complexity of calculating this?

Answer 25

It will be n because they each have that many digits
- time complexity is O(n^2)

Question 26

Why can we assume that the number of bits n used to represent two integers being multiplied together is a power of 2?

Answer 26

• If they’re not, we can just pad with 0’s to make them a power of 2 number of digits
• and padding with 0’s doesn’t change the problem size

Question 27

Why is multiplying an integer by a power of 2 easy to perform by a computer?

Answer 27

Because it’s simply just a shift operation (so shifting the bits left by 1 means multiply by 2)
- so multiplying by 2^k takes O(k) time which is better than O(n^2) time

Question 28

Strassen’s Algorithm

Answer 28

Strassen realised matrix multiplication can be done using divide and conquer using a smaller number of multiplications, it uses 7 matrix products instead of 8