Algorithms

Question 1

What does it mean for an algorithm to be “stable”, as opposed to “non-stable”?

Answer 1

A stable algorithm is one that preserves the relative order of the items with equal sort keys.

For example, let’s say we wanted to sort a list of strings, and we have two strings that start with s.

A stable algorithm is one that, no matter how many times the algorithm is repeated, those two strings will always be in the same order.

Stable algorithms tend to be more efficient, and make it easier to implement multikey sorts.

Question 2

What is the general process for a selection sort algorithm?

Answer 2

We first go to the end of the list, then find the largest element.

That largest element is then put at the end of the list. After this, we call selection sort again on the rest of the list, until we reach the base case.

Question 3

What is the order of a selection sort algorithm?

Answer 3

O(n²).

Question 4

What are the benefits and downsides of selection sort?

Answer 4

It is simple and can easily be implemented in linked lists.

However, it is inefficient for large input sets, as it runs at an order of O(n²).

Question 5

What is the general process for a insertion sort algorithm?

Answer 5

A pointer x, at the end of the list, and y, directly before it, create a “partition” at the end. With each loop, our y pointer decreases by one, letting a new element into the partition.

We then check if this new element is sorted. If it is not, we move it slowly along the partition until it is.

Repeat this until the list is sorted.

Question 6

What does it mean for an algorithm to be “in-place”?

Answer 6

An in-place algorithm is one that does not create a new object to store the sorted data.

Question 7

What is the order of an insertion sort algorithm?

Answer 7

O(n²).

Question 8

What is the primary use of an insertion sort algorithm?

Answer 8

Insertion sort is typically used when we want a solution that is not in-place - that is, a solution that creates a new list at the end.

Note that insertion sort can be done in-place, but is most commonly used for the above.

Question 9

What is the general process for a bubble sort algorithm?

Answer 9

We go through the list backwards.

For each element in the list, if that element is greater than the element before it, swap them.

Keep looping until everything is sorted.

Question 10

What is the order of a bubble sort algorithm?

Answer 10

O(n²).

Question 11

What is meant by a “divide-and-conquer” algorithm?

Answer 11

A divide and conquer algorithm splits a problem into many smaller subtasks, and then combines their solution into a solution for the larger instance.

Question 12

What is the general method of a Quicksort algorithm?

Answer 12

We pick one item from the list (e.g. list[i]), at any point, and call it the pivot. Commonly, we pick the middle element.

We then reorganise the list so that all smaller elements are placed before the pivot, and all larger elements are placed after the pivot.

We then call Quicksort again to solve the partitions. We can also use another sorting algorithm on these partitions if we want it to be simpler.

Question 13

What is the master theorem for divide and conquer algorithms?

Answer 13

The master theorem is a theorem that is always correct for determining the order of a D&C algorithm.

It states that:
T(n) = O(nᵈ) if a < bᵈ
T(n) = O(nᵈ log n) if a = bᵈ
T(n) = O(nˡᵒᵍᵇ ᵃ) if a > bᵈ

Where a is the number of subproblems created at each stage…
b is the divisor of the size of the array…
and d is the number of subproblems created at each recursive stage.

Question 14

What is the order of a Quicksort algorithm?

Answer 14

O(n log n).

Question 15

What is the general method of a Mergesort algorithm?

Answer 15

We recursively break the given input array by half each time until the array cannot be split anymore.

When this is done, and we have many arrays consisting of one element, we recursively merge each “pair” of arrays by choosing the smallest element and putting it into the front of a new array.

When we have done this to every pair of arrays, we have a sorted list.

Question 16

What is the order of a Mergesort algorithm?

Answer 16

O(n log n).

Question 17

What are the benefits and downsides of using Mergesort?

Answer 17

It is stable, robust and performs in O(n log n), which is the best you can get in terms of speed in comparison-type sorting methods.

However, it may require an array of up to the size of the original list to use as an auxillary array. This is not necessary, however the algorithm becomes significantly more complex if we don’t use one.

Question 18

What is the difference between Least Significant and Most Significant Digit RadixSort?

Answer 18

LSD (Least) starts from the first, or least significant, digit in the sequence.

Question 19

What is the general method of a RadixSort algorithm?

Answer 19

We start by converting the keys we have been given into their bases. For example, we may want to strip an integer down to its digits.

When we sort using the LSD, we start at the rightmost digit and sort based on that digit. We then iteratively sort each digit sequence backwards until we have reached the final digit in the sequence.

When we sort using the MSD, we start at the leftmost digit and sort forwards. LSD is typically preferred as we have to sort less digits for our algorithm to be completed.

Question 20

What is the order of a RadixSort algorithm?

Answer 20

Assuming the use of a form of Quicksort to sort each digit, O(n).

Question 21

What is the benefit to using RadixSort?

Answer 21

RadixSort is not only the best method for multi-key sorting, as it can be performed on any set of data that can be represented bitwise, but it is also completely stable, making it perfect for large databases.

It’s also blazing fast - in best-case it can reach O(n) complexity, breaking the limit on comparison-based algorithms while also being totally stable.

Question 22

What is the general method of a Counting Sort algorithm?

Answer 22

We first count the number of times a certain digit appears in the list, and store it in a seperate array, called a count array, that is as large as the range of numbers to be sorted.

Then, we compute a cumulative sum of the count array, to aid with placing elements back in the array.

Finally, we count backwards from the end of the original array, and when we find a number, we check its cumulative sum in the count array, and place it there. We also decrement the cumulative sum, so that duplicates are placed before it.

Question 23

What do we need to know before starting a Counting Sort algorithm?

Answer 23

We need to know the range of numbers in the array, so that we can accurately create a count array.

Question 24

What is the order of a Counting Sort algorithm?

Answer 24

O(k + n), where k is the range of values in the input array.

Question 25

What are the benefits and downsides to Counting Sort?

Answer 25

It has a linear complexity at O(k + n), and is totally stable. It is also easy to comprehend and understand.

However, it requires extra space to be allocated for the count array, and its speed relies heavily on the range of values to be sorted. Furthermore, it only works for sorting integers or elements that can be represented as integers like ASCII characters.

Question 26

What is a hash table?

Answer 26

A hash table is a data structure that maps a key k to position hash(k), such that hash(k) is a hash function that maps the universe of keys into the slots of the hash table.

For example, if we had a hash table of length n, our hash(k) would turn the key k into an integer along the range 0 -> n.

e.g. hash(123) could give us 10, so the value 123 would be placed in the hash table at slot 10. Then, if we ever want to find 123 again, we hash it and get 10 again.

Question 27

What are the benefits of using a hash table over using a list or array?

Answer 27

A hash table retains the O(1) time to access an element, while also providing certain benefits of sequential access structures such as lists like easy insertion and removal, as elements are not linked, only referenced to.

Question 28

What is a hash function?

Answer 28

A hash function is a function that maps the universe of possible keys to a slot in our hash table.

A good hash function is described as one that satisfies the assumption of uniform hashing.

Question 29

What is uniform hashing, and why is it important to a hash function?

Answer 29

Uniform hashing is the assumption that each possible key is equally likely to hash to any of the m slots in the hash table.

It can also be described as assuming that our universe of keys has a one-to-one correlation with the slots of the hash table.

It is important to a hash function because if uniform hashing is a correct assumption, we do not need to worry about issues such as collision.

Question 30

What is meant by collision in a hash table? Describe two methods of solving collision.

Answer 30

Collision is an error where the hash function outputs the same value for two different inputs. Of course, this would mean, without solving this problem, we would need to store two pieces of data in the same slot, which is undesirable.

One method of solving collision is chaining, where each slot in the hash table is a list of elements.

Another method is open addressing, where if we get a collision, we simply move it n places down the table until we find an open slot.

Question 31

What are the different valid probing methods in open addressing?

Answer 31

One method is linear probing, where we simply move n places down the table. However, this can lead to an issue called primary clustering, where we end up creating large groups - or “clusters” - of occupied slots, increasing the probability that we will collide again.

A way to solve this is with quadratic probing, where we instead move it n^2 places down the table. This results in secondary clustering, which is similar but not as intense as primary clustering.

Finally, another method is rehashing, where if we reach a collision, we simply use another hash function in a sequence of hash functions.

Question 32

How do we search in a chained hash table?

Answer 32

We first hash the target, then take the value of that hash and go to that slot. If the target exists, it must be in that slot.

We then search the list in that slot using a linear search (assuming linked lists). If we find the target, great! If we don’t, it doesn’t exist in the table.

Question 33

What is the worst-case of a chained hash table?

Answer 33

T(n) = time_hash + time_linear_search
T(n) = O(1) + O(n)
T(n) = O(n)