Week 4 Flashcards
what is a bucket sort?
- 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]
What is the time complexity of a bucket sort?
- 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)
What is a radix sort?
- 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
What is the time complexity of a radix sort
d is the number of columns it has to perform a bucket sort on, so the time complexity = O(d*(N+n))
How do we perform a radix sort on words of uneven length?
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_
When is a sorting algorithm described as stable?
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
-
Why does choosing to go from left to right (MSB) or right to left (LSB) make a difference in Radix sorting?
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!
If we have integers of 6 digits and 4 digits long, and we perform a radix sort, what is the value of d?
- 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
What type of algorithm is a merge sort?
A divide and conquer algorithm
What type of algorithm is a quicksort?
- 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
What is the general outline for using the divide and conquer method?
- 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
How do we analyse the running time of a divide and conquer algorithm?
we use a recurrence relation T(n) which denotes running time based on input size n
What is the recurrence relation we use to characterise running time of a merge sort?
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
What is a recurrence relation?
An equation that defines a sequence based on a rule that gives the next term as a function of the previous terms
What is the recurrence relation for a binary search?
- 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
What is the substitution method?
one method of solving a divide and conquer recurrence equation is to use the iterative substitution method, called plug and chug
Why can we replace the 2*T(n/2^i) in a recurrence relation?
Since we know that T(n/2^i) = 1 so we can exchange it for c since T(n) = c when n < 2
What is a general equation for a recurrence relation if we were to guess it
T(n) = {c if n <= d, a*T(n/b)+f(n) if n > d}
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}?
- 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)
what is case 1 of the master method?
where e > 0, if f(n) is O(n^logn(a-e)) then T(n) = Θ(n^logb(a))
what is case 2 of the master method?
if f(n) is Θ(n^logb(a)log^k(n)) then T(n) = Θ(n^logb(a)log^k+1(n))
what is case 3 of the master method?
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))
How can we change the recurrence 2T(n^1/2) + logn into a form that allows us to use the master method?
- 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
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?
A variable change
What is the problem size of multiplying two numbers with n digits each? and what is the naive time complexity of calculating this?
It will be n because they each have that many digits
- time complexity is O(n^2)
Why can we assume that the number of bits n used to represent two integers being multiplied together is a power of 2?
- 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
Why is multiplying an integer by a power of 2 easy to perform by a computer?
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
Strassen’s Algorithm
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
