2.3.1 Algorithms

Question 1

What should you do before developing an algorithm?

Answer 1

• Algorithm must be well defined
  
  • what inputs the algorithm will accept
  • what outputs will it produce
  • the scope of the algorithm

Question 2

What is execution time?

Answer 2

• How long an algorithm takes to run

Question 3

What ways can complexity be measured?

Answer 3

• Execution time - how many steps an algorithm will take with a given input
• Space - how much memory it takes up during execution

Question 4

What are the different Big O notation?

Answer 4

• O(1) - constant time
• O (Log²n) - logarithmic time
• O(n) - linear time
• O(n²) - squared time
• O(n³) cubed time
• O(n^c) - polynomial time
• O(nⁿ) - exponential time

Question 5

What is Bubble sort?

Answer 5

• They compare values and swaps if not in the correct order and does this with all pairs - process is repeated until all in correct order

Question 6

What are the features of pseudocode for bubble sort?

Answer 6

• Set swapped to false
• Add a for loop that loops to the end of the list
• IF list[n-1] > list[n] THEN
• Store the n-1 (greater one) in a temp variable and set n-1 to n
• Change n to temp and set swapped to true and repeat to next one

Question 7

What is the efficiency and space complexity of Bubble sort?

Answer 7

• Will perform n-1 comparisons every time
• Inefficient
• Simple algorithm and makes little additional use of memory other than a few variables - constant space complexity

Question 8

What is Insertion Sort?

Answer 8

• Assume the first item in the list is sorted
• This will start with the second item in the list and place it into a temporary variable. This is compared to the first item. If below all items are shifted by 1 (in sorted list)

Question 9

What is the space complexity of insertion sort?

Answer 9

• Makes very little additional use of memory other than few variables