Week 3

Question 1

What is the sorting problem?

Answer 1

• given a collection of n elements and a total ordering arrange the elements into a non-decreasing order

Question 2

What is a priority queue?

Answer 2

• a priority queue is a container of elements, each having an associated key
• Keys determine the priority used in picking elements to be removed

Question 3

What are the 4 fundamental methods performed on a priority queue

Answer 3

• insertItem(k, e) - element e with key k
• removeMin() - remove element with the minimum key
• minElement() - return element with the minimum key currently in the priority queue
• minKey() - return key of minimum element

Question 4

what order are elements stored in in priority queues?

Answer 4

• we work on maintaining the element with the minimum key currently in the priority queue

Question 5

How is a deletion completed in a priority queue and what is the time complexity of this?

Answer 5

• The elements with the current minimum key is deleted and the priority queues minimum is updated.
• this is completed in logarithmic time

Question 6

How can we use a priority queue to perform sorting on a set of elements in two phases?

Answer 6

• Phase 1: put elements of set one by one into an initially empty priority queue by a series of insertions, after each insertion the priority queue pulls up the minimum so it’s ordered and we have the minimum in linear time
• Phase 2: extract the elements from the priority queue with a series of remove operations. When all items have been extracted and added to a list, this list will be sorted in non-decreasing order

Question 7

Describe the primary queue sorting algorithm

Answer 7

• the priority queue is initially empty
• while the input set is not empty, remove the first element and insert it into the priority queue, do n times for every item in the list
• then when we have a full sorted priority queue, remove all n items, by searching through the priority queue and adding the minimum element to the new sorted list.

Question 8

What is the running time of the priority queue sorting algorithm?

Answer 8

O(nlog) because there’s technically 2nlogn since putting n elements in PQ then searching logn to find where to insert them takes nlogn time, and we do this again n times when we remove every item from the pq to add to a sorted list, hence nlogn, but 2nlogn = O(nlogn)

Question 9

What is a heap data structure?

Answer 9

• This is an implementation of a priority queue that is efficient for both insertions and deletions
• elements and keys are stored in a complete binary tree (so every level apart from perhaps the bottom level will have a the maximum number of children possible)

Question 10

What are the properties of a heap data strucutre?

Answer 10

• In a heap T, for every node v (excluding the root) it’s key is >= it’s parents key
• if we take any path from the root to an external leaf, it only had elements that are non-decreasing, so the root must be the global minimum

Question 11

How can we implement a heap data structure?

Answer 11

• As a nearly complete binary tree containing elements with keys satisfying the heap-order property stored in an array
• need to store a reference to the last used node T in the bottom level of the binary tree
• a comparator function that defines the total order relation on keys and which is used to maintain the minimum/maximum element at the root of T

Question 12

What is the last used node/element at the bottom level of the binary tree/heap?

Answer 12

The rightmost element/node on the lowest level of the tree

Question 13

How are items inserted into heaps?

Answer 13

• begin by adding the element to the bottom of tree in the position of the first unused/empty child
• then if need be, the new element bubbles it’s way up the heap until the heap order property is restored

Question 14

What is the time complexity of insertion into a heap?

Answer 14

At max we’ll need to do 2^n number of swaps where n is the height of the heap, the insertion is only O(1) so the time complexity is log2(n)

Question 15

How is deletion in a heap carried out?

Answer 15

• deletion consists of removing the minimum/maximum element which is at the root, so we remove this
• the element in the ‘last’ position is immediately moved to the root and then sinks/bubbles down to restore heap-order property

Question 16

When bubbling the item at the root node down, how do we decide which subtree’s element to swap with?

Answer 16

• We swap with the element that’s smallest.
• For example if the item at the root = 8 and the left subtree holds 6 and the right subtree holds 5, we would swap 8 with 5 at the right subtree
• this is because if we move the larger value up this will break the heap-order property
• if we moved 6 up, then 6 is bigger than 5 so the heap-order property would be broken.

Question 17

What are the time complexities of finding the size/is empty, minElement, minKey, insertItem and removeItem methods for a heap?

Answer 17

• size, is Empty - O(1)
• minElement, minKey - O(1)
• insertItem - O(logn)
• removeMin - O(logn)

Question 18

What is the divide and conquer method and how is it achieved?

Answer 18

• it’s a method for solving certain types of algorithmic problems
• divide the input data into two or more disjoint subsets
• recursively solve the subproblems associated with the subsets
• conquer: take the solutions to sub problems and merge them into a solution to solve the original problem

Question 19

How is a merge sort performed?

Answer 19

• a way to apply divide and conquer method to sorting
• setting an input size 0 or 1 as the base case
• dividing the input sequence in half, recursively divide each sequence in half until every input is in a list on their own, this will hit the base case and unwind
• as the algorithm unwinds, it will sort each list, merging them together into a final completely sorted list

Question 20

What are the 3 steps in the divide and conquer method

Answer 20

1. divide, recur, merge

Question 21

What does merging mean in a merge sort

Answer 21

Putting the inputs in global sorted order

Question 22

What is the time complexity of a merge sort

Answer 22

• sorts in time nlogn
• this is since during each recursive step we divide a sublist in two which takes O(n) time, and we will recursively call the algorithm at most O(logn) times since we’re dividing the list in two, this gives O(nlogn) run time for mergesort

Question 23

What are counting inversions?

Answer 23

Having two sets of rankings of numbers, e.g. 1 3, 4, 5, 2 and 1, 2, 4, 3, 5 and counting the number of inversions between the two rankings to give a meaningful metric of the difference in the two rankings

Question 24

how do we count inversions

Answer 24

• Suppose that a1, a2, a3… an denotes a permutation of the integers 1, 2, … n, the pair of integers i,j are said to form an inversion if i <j> aj</j>
• for example if a1 = 1, a2 = 2, a3 = 3, a4 = 4, a5 = 5 and we have the ranking 1,3,2,4,5
• here i = 3 and j = 2 but 2 < 3 so this is an inversion

Question 25

What happens if we invert a permutation from it’s correct order?

Answer 25

It’ll contain the largest umber of inversions

Question 26

What is the naive approach of counting inversions?

Answer 26

-running through all pairs to see if they form an inversion in the permutation which gives us a run time of O(n^2) which is not efficient

Question 27

What is the more efficient method for counting inversions and what time complexity is this completed in?

Answer 27

• using a divide and conquer algorithm
• we divide the permutation list in half. we recursively divide the permutation list until each item is in a list on it’s own (this is the base case), we then merge the lists by sorting each sublist, as we merge the lists we count the number of inversions from pairs. We merge the lists until only one sorted list is returned
• then we have counted all the inversions

Question 28

How do we know that the divide and conquer counting inversion algorithm counts all of the inversions?

Answer 28

• Because when we put an item into a merged list, we’ll have already counted it’s inversions in it’s own list and it’s inversions with the other list will be counted while we move it into the merged list,
• we count all the items with another list by following that if we’re moving an item I from B into the merged list, since each list is sorted and I is being moved before any other items in A, we know that I must be smaller than the ones in A, even though all of these come before I in the input list, hence we can count an inversion between I and every item left in A

Question 29

What is the quicksort algorithm

Answer 29

• a divide and conquer algorithm that performs sorting
• it chooses a pivot x in the input set and creates three subsets, less than, equal to or greater than x
• it then recursively sorts the elements into each group
• one every element is in a group on it’s own (base case), it unwinds, merging every list into a sorted list until there is one final sorted list

Question 30

What is the runtime of a quicksort?

Answer 30

• a pivot must be chosen each time, if a bad choice is made, meaning that it leads to the height of the quicksort tree being n, then worst case time complexity = O(n^2) as we’re performing n operations to sort the n elements, for n levels

Question 31

what is a randomised quicksort?

Answer 31

• where we randomly select the pivot element, instead of having a specific formula for choosing it in the normal quicksort

Question 32

what is basic probability?

Answer 32

• it can be used to analyse the average-case performance of algorithms
• some inputs are more/less probable to appear, so we can use probability distribution to pick the more efficient inputs

Question 33

What is a sample space? explain what the same space of a fair 6 sided dice is?

Answer 33

A sample space is the set of all possible outcomes from an experiment
- sample space of a fair dice is {1,2,3,4,5,6} as these are all the results you can get from rolling the dice

Question 34

What is a probability space and an event?

Answer 34

a probability space is a sample space s and a probability function pr, which maps subsets of S to [0,1]
- an event is a subset of the sample space

Question 35

What is a probability function?

Answer 35

A probability function Pr possesses the following properties:
- Pr(empty set) = 0
- Pr(whole set S) = 1
- Pr(a subset of S) = probability between 0 and 1
- if A and B are subsets of S and have no intersection of elements, the probability of A and B happening is the same as the probability of A happening + the probability of B happening

Question 36

give an example of how independent events effect the probability of landing head on a coin toss?

Answer 36

Independent events means that two events do not have any effect on the probability of the other happening. So if I land heads first, it does not increase or decrease the probability that the coin will next land on heads again or on tails

Question 37

How do we mathematically represent that two events are mutally independent?

Answer 37

Pr(A n B) = Pr(A) * Pr(B)

Question 38

What is conditional probability?

Answer 38

The probability of an event occurring given that some other event has already occurred.

Question 39

How do we calculate conditional probability?

Answer 39

Pr(A n B) / Pr(B)
probability of the intersection of A and B divided by the probability of A happening

Question 40

What is a random variable?

Answer 40

A function that maps outcomes from some sample space to real numbers.

Question 41

Where do we use random variables in algorithms?

Answer 41

We use them with a discrete set of outcomes to characterise running time of a randomised algorithm

Question 42

What does the expectation of a random variable tell us?

Answer 42

It tells us what value I should expect from the experiment, repeating it many time and taking the mean

Question 43

What is the expected running time of a randomised quicksort?

Answer 43

O(nlogn) (which is much better than the normal quicksort with complexity n^2)

Question 44

What criteria does a good pivot in a quicksort meet?

Answer 44

a good pivot is if the size of neither L or G is a larger than 3/4*size of the set

Question 45

Why can we class the time complexity of the randomised quicksort algorithm as nlog2n

Answer 45

Because anything that is logi(n) can also be logj(n) is j > i
- so since the randomised quicksort has a time complexity of log4/3(n) it also belongs to the class of log2(n) since 2 > 4/3