Preview

05 - Suitability of different Algorithms

 1. In order to decide which algorithm to chose over another, they are compared in terms of their efficiency: the _____ it takes to find the solution and the resources which are consumed in the process
Useful explanation of Big O with examples: https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation

  factors

  time

  bound

  determination

 2. Space-wise efficiency is referring to the amount of (memory) space the algorithm will take up before it terminates with the correct solution
Useful link for a complete overview, check out: http://bigocheatsheet.com/

  TRUE

  FALSE

 3. When considering space-wise efficiency, the aim is to utilise data structures which take up ______________________

  the most memory

  the least inputs

  the least outputs

  the least amount in memory

 4. Example: populating a list with variables of type "real" will be ___________ inefficient, when it is clear that only whole numbers (integers) will ever be needed to solve the problem

  time-wise

  Big O

  O(n)

  space-wise

 5. This is the amount of time it takes for the algorithm to terminate with the correct solution

  Space-wise efficiency

  Time-wise efficiency

  Big O efficiency

  Memory efficiency

 6. Insertion Sort uses the insertion method and while it can perform at O(n) in the best case, it performs at O(n2) in the average and worst case.

  FALSE

  TRUE

 7. Consider the following algorithm: Count the number of computational steps in the algorithm
number1 <- INPUT

number2 <- INPUT

sum1 <- number1 + number2

number3 <- INPUT

sum2 <- sum1 + number3

  8

  5

  6

  7

 8. An ___________ algorithm is considered highly efficient, as the ratio of the number of operations to the size of the input decreases and tends to zero when n increases

  O(n^2)

  O(log n)

  None of these options are valid

  O(n*m)

 9. For a larger data set a linear search would be preferrable (more efficient or suitable) than a binary search.

  TRUE

  FALSE

 10. The Best Case represents the ________ speed the the algorithm can operate in in the most optimal conditions

  slowest

  fastest

  None of these options are valid

  normal

 11. The Worst Case represents the _______ speed that the algorithm will operate in in the worst conditions

  slowest

  None of these options are valid

  fastest

  normal

 12. The Average Case represents the average (or expected) speed the the algorithm will operate in in ______ conditions.

  None of these options are valid

  slowest

  fastest

  normal

 13. Fill in the blanks for the following excerpt
Some problems cannot be solved in polynomial time. 
Certain things are used in the world because of this. 
___________________________________ is a prime example. 

It is computationally hard to find two prime factors of a 
very large number. If it wasn't, we couldn't use the 
public key systems we use.

  Public Key Cryptography

  Wireless Technology

  Simple addition and the finding of prime factors

  Quantum computing

 14. The worst case scenario for a Bubble Sort is O(n)

  FALSE

  TRUE

 15. These are algorithms which provide close approximations for problems for which no known polynomial solution algorithm exists

  Approximation algorithms

  Tractable algorithms

  Quantum algorithms

  Intractable algorithms