Algorithms

Question 1

Explain the steps of binary search

Answer 1

• Binary search is more efficient than linear search
• In binary search, the list must be ordered
• First, the middle term of the list is compared with the target term. If the term matches the target then the index is returned
• If not, the top half of the list is ignored if the target term is less than the middle term
• If the target term is greater than the middle term, the bottom half of the list is ignored
• This is repeated until the target term is found

Question 2

Explain the steps of linear search

Answer 2

• Each item in the list is compared with the search item. If it does not match, the next term is compared

Question 3

Explain the stages of bubble sort

Answer 3

• Starting at the beginning, two adjacent terms are compared with eachother and then sorted in order
• The last term of the first comparison is then compared with the next adjacent term, ordering them aswell
• Once the end of the list has been reached, the last term will be in the correct place. The algorithm then resets for another pass

Question 4

Explain the steps of insertion sort

Answer 4

• Starts with one of the items from the list
• The next item is compared with the first item. If it is greater than the first item is shifted to the left and the next item takes its place. if the next item is less than the first item than the first item is shifted to the right and the next item takes its place
• This is repeated until the list is ordered

Question 5

Explain the steps of merge sort

Answer 5

• The list is broken up into individual terms
• Adjacent terms (in twos) are put back together in order, creating many mini lists
• Adjacent mini lists are then compared and put back together in order
• This is repeated until the whole list is back together in order

Question 6

What is Dijkstra’s shortest path algorithm?

Answer 6

• An example of an optimisation algorithm that calculates the shortest path from a starting location to all other locations

Question 7

What is Big O notation?

Answer 7

• Big O notation is used to express the complexity of an algorithm
• Describes the scalability of an algorithm as it’s order (O)

Question 8

What are the main rules of Big O notation?

Answer 8

• Remove all terms except the one with the largest factor or exponent
• Remove any constants

Question 9

What is O(1)?

Answer 9

• Constant
• An algorithm that takes a constant amount of time
• Requires the same number of instructions, regardless of the size of the input data

Question 10

What is O(n)?

Answer 10

• Linear
• As the input size grows, the number of instructions required increases proportionally
• E.G: a linear search of 100 items will take 10 times longer than that with 10 items
• Shown with loops (not embedded)

Question 11

How is O(n) written in code?

Answer 11

• Linear Big O is shown using loops
• Each loop adds an extra n onto the Big O
• The loops must NOT be embedded
• E.G: 3 for loops in the algorithm = O(3n)

Question 12

What is O(n²)?

Answer 12

• Polynomial
• The time taken to complete the algorithm is proportional to the square of the size of the input data

Question 13

What is an example of an algorithm which is O(n)?

Answer 13

• Linear search

Question 14

How is O(n²) written in code?

Answer 14

• Requires the use of nested loops (embedded)
• Regardless of the number of loops nested, they are all referred to as polynomial (hence still O(n²))

Question 15

What is an example of an algorithm which is O(n²)?

Answer 15

• Bubble sort
• n passes are made, and for each pass, n comparisons are made
• Nests loops

Question 16

What is O(2ⁿ)?

Answer 16

• Exponential
• An algorithm which takes double the time to execute for each additional data value

Question 17

What is the issue with O(2ⁿ)?

Answer 17

• The number of instructions executed becomes very large, very quickly
• Hence, few everyday algorithms use exponential time due to its sheer inefficiency

Question 18

What is O(logn)?

Answer 18

• Logarithmic
• An algorithm that takes very little time as the size of the input grows larger

Question 19

What is an example of an algorithm which is O(logn)?

Answer 19

• Binary search
• Doubling the size of the input data has very little effect on the overall number of instructions executed by the algorithm

Question 20

What are the different cases of complexity?

Answer 20

• All algorithms have a best case, average case and worst case scenario
• Best case: where the algorithm is most efficient (e.g: a linear search finding the item on the first element)
• Average case: where an algorithm performs at neither its best nor its worst (e.g: a linear search finding the item at the middle of the list)
• Worst case: where an algorithm is least efficient (e.g: a linear search finding the item on the last element)

Question 21

In what case is complexity measured?

Answer 21

• Big-O notation is always measured by the worst case performance of an algorithm
• This allows programmers to select algorithms based on minimum performance levels

Question 22

Rank the different Big O algorithms

Answer 22

• O(1)
• O(logn)
• O(n)
• O(nlogn)
• O(x^2)
• O(x^3)
• O(2^x)
• O(x!)

Question 23

What is an example of O(nlogn)?

Answer 23

• Merge sort

Question 24

What is the time complexity of binary search?

Answer 24

• O(logn)

Question 25

What is the space complexity of binary search?

Answer 25

- Iterative binary search (fixed number of variables): O(1) - Recursive binary search: O(logn)

Question 26

What is the time complexity of linear search?

Answer 26

- O(n)

Question 27

What is the space complexity of linear search?

Answer 27

- O(1) - Does not require any additional memory that grows with the size of the input

Question 28

What is the time complexity of bubble sort?

Answer 28

- O(n²) - Nested loops

Question 29

What is the space complexity of bubble sort?

Answer 29

- O(1) - Operates in space with a fixed amount of memory

Question 30

What is the time complexity of insertion sort?

Answer 30

- O(n²)

Question 31

What is the space complexity of insertion sort?

Answer 31

- O(1) - Requires no additional space

Question 32

What is merge sort?

Answer 32

- A sorting algorithm that uses divide and conquer - Reduces the size of the problem into smaller problems that are more easily solvable

Question 33

Explain the steps of merge sort

Answer 33

- The merge sort list is divided in half to create two sub-lists - Each sub-list is then divided again until each sub-list contains only one item - Groups of two adjacent sub-lists are then sorted and merged together to form a new, larger, sorted sub-list - Repeat merging until all sub-lists are merged into one, sorted list

Question 34

What is the time complexity of merge sort?

Answer 34

- O(nlogn)

Question 35

What is the space complexity of merge sort?

Answer 35

- O(n) - Required to store the sub-lists

Question 36

What is an A* search algorithm?

Answer 36

- Builds on Dijkstra's by using a heuristic - A heuristic is a rule of thumb, best guess or estimate that helps the algorithm accurately approximate the shortest path to each node

Question 37

Why is Dijkstra's algorithm inefficient?

Answer 37

- Dijkstra's algorithm uses a single cost function: the real distance from the initial node to every other node - The cost function is unreliable, as A to B may be larger than A to C but Dijkstra's will follow C anyway as it is faster, even if it doesn't lead to the goal node

Question 38

How does the A* search algorithm work?

Answer 38

- It uses two functions - g(x): the real distance cost function - cost from start to current node - h(x): heuristic function - estimated cost from current node to goal - Therefore, f(x) = g(x) + h(x) - If h(x) increases, it means the algorithm is travelling further away from the goal node

Question 39

What is the heuristic function in the A* search algorithm?

Answer 39

- Approximate the straight line distance from the current node to the goal node - By following nodes based on shorter heuristic distances, the algorithm can be sure it is getting closer to the goal node

Question 40

What is the difference between the A* search algorithm and Dijkstra's algorithm?

Answer 40

- A* search focuses on reaching the goal node - Dijkstra's algorithm calculates the distance from the initial node to every other node