Preview

04 - Efficiency of Algorithms

 1. The importance of efficiency with respect to time was emphasised by _____________ in 1843 as applying to Charles Babbage's mechanical analytical engine

  Bill Gates

  John Von Neumann

  Ada Lovelace

  Alan Turing

 2. Complexity theory is interested in how algorithms scale with an increase in the input size.

  FALSE

  TRUE

 3. The order of an algorithm is a measure of the efficiency (______________________) of the algorithm as a function of the size of the problem.

  number of operations

  number of outputs

  number of inputs

  number of loops or iterative structures used

 4. An algorithm is considered efficient if its resource consumption, also known as computational cost, is at or below some acceptable level.

  FALSE

  TRUE

 5. Roughly speaking, 'acceptable' means: it will _______________________________ on an available computer, typically as a function of the size of the input

   run in a reasonable amount of time or space

  fail to cause any errors

  produce an exponential output

  run until it halts

 6. Thanks to the approximate doubling of computer power every 2 years, tasks that are acceptably efficient on modern smartphones and embedded systems may have been unacceptably inefficient for industrial servers 10 years ago

  TRUE

  FALSE

 7. The most commonly used notation to describe resource consumption or "complexity" is Donald Knuth's __________________________

  A* Algorithm

  Chaos theorem

  Algorithmic Analysis

  Big O notation

 8. For example, bubble sort may be faster than merge sort when only a few items are to be sorted; however either implementation is likely to meet performance requirements for a __________

  non linear stack

  small list

  non existent list

  large list

 9. Algorithms which include ______________________ may be more difficult to analyze in terms of Big O

  small data sets

  parallel processing

  infinite queues

  more than one input

 10. What is being defined here: "An upper bound on the running time for any input of given size"
There are three factors we need to consider 
for time complexity
-------------------------------------------

1. Worst case
2. Average case
3. Best case

  Best case

  Average case

  None of the listed options

  Worst case

 11. What is being defined here: "The lower bound on the running time"

  Best case

  Worst case

  Average case

  None of the listed options

 12. What is being defined here: "Assume all inputs of a given size are equally likely"

  None of the listed options

  Average case

  Best case

  Worst case

 13. In the example of a sequential search of a list of size 'n', in the worst case there are __ comparisons and the best case the number of comparisons is: ___

  n / 1

  n / n - 2

  1 / n

  n / n -1

 14. In the case of a sequential search of a list of size 'n', the average case would be:

  n/2 comparisons

  n - 1 comparisons

  n comparisons

  n * 2 comparisons

 15. An algorithm filling a matrix of size n*m with natural numbers 1,2,……will run in ___________

  O(n)

  O(n*m)

  O(n*m/2)

  O(n/m)

 16. Non polynomial algorithms will only work for very large input data sets

  FALSE

  TRUE

 17. Select the statement that best describes the following complexity example.
algorithmefficiency1.png

  Runs in O(n^2) where n is the size of the array

  Runs in quadratic time O(n*m)

  Runs in cubic time O(n^3)

  Runs in O(n) where n is the size of the array

 18. Select the statement that best describes the following complexity example.
algorithmefficiency2.png

  Runs in O(n^2) where n is the size of the array

  Runs in O(n) where n is the size of the array

  Runs in quadratic time O(n*m)

  Runs in cubic time O(n^3)

 19. Select the statement that best describes the following complexity example.
algorithmefficiency3.png

  Runs in quadratic time O(n*m)

  Runs in O(n^2) where n is the size of the array

  Runs in cubic time O(n^3)

  Runs in O(n) where n is the size of the array

 20. Select the statement that best describes the following complexity example.
algorithmefficiency4.png

  Runs in quadratic time O(n*m)

  Runs in O(n) where n is the size of the array

  Runs in cubic time O(n^3)

  Runs in O(n^2) where n is the size of the array

 21. The following runs in exponential time >> O(2^n)
algorithmefficiency5.png

  TRUE

  FALSE

 22. The following runs in linear time O(n)
algorithmefficiency6.png

  FALSE

  TRUE

 23. For the following data structures and actions, can you fill in the blanks for A, B and C
datastructures_efficiency.png

  A, B, C = O(1)

  A,B,C = O(n)

  A = O(1); B = O(n); C=O(1)

  A = O(1); B,C = O(n)

 24. The Big O notation for a hash table (adding a value) e.g. Dictionary would be O(n)

  FALSE

  TRUE

 25. Out of all the data structures the 'hash table' is generally considered the slowest for all the typical 'add', 'delete' and 'find' operations. O(n^3)

  FALSE

  TRUE