Algorithms and programming

Question 1

What is a recursive algorithm?

Answer 1

A recursive algorithm is one that repeatably calls itself until a base case is met.

Question 2

What are the advantages of recursion?

Answer 2

More natural to read.
Suited to certain problems, for example those using trees.
Quicker to write as some functions are naturally recursive.
Can reduce the size of the problem with each call

Question 3

What are the disadvantages of recursion?

Answer 3

Can run out of stack space / memory (due to too many calls) causing it to crash. This can be avoided with tail recursion.
More difficult to trace / follow as each frame on the stack has its own set of variables
Requires more memory than the equivalent iterative algorithm.
Usually slower than iterative methods due to maintenance of the stack

Question 4

What is iteration?

Answer 4

Iteration is when the same procedure is repeated using a count controlled ‘for’ loop or a condition controlled ‘while’ loop.

Question 5

Identify where the recursion is taking place.

01 def factorial(n)
02      if n == 0:
03          return 1
04     else:
05         return n * factorial(n-1)

Answer 5

Line 05

Question 6

Identify the base case/terminating condition.

01 def factorial(n)
02      if n == 0:
03          return 1
04     else:
05         return n * factorial(n-1)

Answer 6

Line 02

Question 7

What is the worst case number of searches for binary search?

Answer 7

O(log2(n)) when the search reaches the deepest level of the tree.

Question 8

What is the best case number of searches for binary search?

Answer 8

O(1) when the target value is the middle element.

Question 9

What is the average case number of searches for binary search?

Answer 9

O(log2(n) -1)

Question 10

What is the worst case number of searches for linear search?

Answer 10

O(n) when the value at the end of the list or not in the list so that n comparisons are needed.

Question 11

What is the best case number of searches for linear search?

Answer 11

O(1) when the value is equal to the first element of the list so only one comparison is needed

Question 12

What is the average case number of searches for linear search?

Answer 12

O(n/2)

Question 13

What is logarithmic complexity O(log n)?

Answer 13

The inverse of exponential growth. (Halving a dataset)

Question 14

What is linear complexity O(n)?

Answer 14

An algorithm who’s complexity will grow in direct proportion to the size of the input data. (For/While loop)

Question 15

What is constant complexity O(1)?

Answer 15

Algorithm that will always execute in the same time regardless of the size of the input data set. (No loops)

Question 16

What is polynomial complexity O(n^2)?

Answer 16

An algorithm whose performance is directly proportional to the squared size of the input data set. (Nested loops)

Question 17

What is exponential complexity O(2^n)?

Answer 17

An algorithm whose growth doubles with each addition to the input data set (Recursion)

Question 18

Write a binary search algorithm in pseudocode.

Answer 18

def binary

Question 19

In what situation would you use a linear search?

Answer 19

Unsorted array as it does not need to be sorted, useful if often inserting/removing
Array is very small
Item being searched for is very close to start of the array

Question 20

In what situation would you use a binary search?

Answer 20

Sorted array

Large amount of data

Question 21

What are the key steps of quicksort

Answer 21

Quicksort is a divide and conquer algorithm

1) Pick an element in the array as the “pivot”
2) In the partition phase it “partitions” the array into two divisions: Items to the left of the pivot are less than the “pivot”, and items to the right of the pivot are greater than the “pivot”
3) It does this recursively on smaller and smaller subarrays until the entire array is sorted.

Question 22

What is the worst case complexity of quicksort?

Answer 22

O(n^2)

Question 23

What is the best and average case complexity of quicksort?

Answer 23

O(n log n)

Question 24

What are the advantages of quicksort?

Answer 24

On average it runs very fast.

It requires no additional memory.

Question 25

What are the disadvantages of quicksort?

Answer 25

Quicksort’s running time degrades if given an array that is almost sorted (or almost reverse sorted).

Question 26

Write pseudocode for a bubble sort

Answer 26

SET counter = 0
SET swapped = True
SET swaps = 0
SET length TO LENGTH(list)
WHILE swapped == True DO
      WHILE counter < length – 1 DO
           IF list[counter] > list[counter + 1] THEN
                 SET temp TO list[counter]
                 SET list[counter] TO list[counter + 1]
                 SET list[counter + 1] TO temp
                 SET swaps TO swaps + 1
           END IF
           SET counter TO counter + 1
           SET length TO length - 1
       END WHILE
       IF swaps = 0 THEN
            SET swapped TO False
       ELSE
             SET swaps TO 0
             SET counter TO 0
       END IF
END WHILE

Question 27

What are the advantages of bubble sort

Answer 27

Simple to write and understand