Preview

12 - Efficiency of Algorithms Basics

 1. All algorithms are exactly the same in terms of their efficiency in solving the same problem (e.g. binary and linear search)

  FALSE

  TRUE

 2. Measures are normally expressed as a function of the size of the input n. Common measures include:

  Time: how long does the algorithm take to complete?

  Space: How much memory is needed by the code and the amount of memory needed for the data on which the code operates

  Space: How much working memory (RAM) is needed by the algorithm?

  All of the above

 3. On a very small list of say two items, it would be more efficient to use the following searching algorithm:

  binary search

  bubble search

  linear search

  merge sort

 4. If an application is time critical then it may be better to prioritise speed over space

  TRUE

  FALSE

 5. A certain program requires the value of every pixel in a stored image to be changed. There are two algorithms available. What statement is true of algorithm #1 
Algorithm #1
=============
1. Entire image (all pixels) is read into memory
2. A parallel calculation is applied on every pixel
3. The image is then stored /saved again.



Algorithm #2
=============
1. A single pixel is read into memory
2. A calculation isperformed on the single pixel
3. The pixel (which has been changed) is stored.
4. REPEAT all the above steps until all the pixels are dealt with.

  Algorithm #1 is very fast and also space efficient as next to no memory is necessary

  Algorithm #1 is very fast but needs enough memory in order to hold the entire image and perform the calculation.

  None of the above

  Algorithm #1 is very slow but needs only minimal memory to store the image

 6. For maximum algorithm efficiency we wish to minimize resource usage (the resources being …..)

  time and space

  CPU usage and list memory

  lists and loops

  stacks and queues

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

  Bill Gates

  Ada Lovelace

  Alan Turing

  Grace Hopper

 8. Often a task could be handled either by using a fast algorithm which used a lot of memory, or by using a slower algorithm which used very little working memory

  None of the above

  This is called a space-time trade off

  This is called the 'impossible problem of Computing'

  This is called the space-divide

 9. An algorithm is considered efficient if its resource consumption (or computational cost) is at or below some acceptable level. Roughly speaking, 'acceptable' means:

  it will run an infinite loop ensuring that the solution will be eventually found

  it will take a very long time to process such that the length is equal to the time

  it will run in a reasonable amount of time on an available computer

  it will take a very short amount of time and the absolute minimum resources

 10. Big O notation is used to represent the complexity of an algorithm as a function of the size of the input n

  FALSE

  TRUE

 11. One factor in efficiency is called 'scalability' or complexity. In this context, complexity means 'if input n increases, how much longer does it take to complete' which is…

  space complexity

  bubble complexity

  time complexity

  coarse complexity

 12. The question:" If input 'n' increases how many more resources does it need" is essentially referring to 'space complexity'.

  FALSE

  TRUE

 13. For the following algorithm, which sums up all the numbers up to 'n', the time taken to complete this algorithm …… 
For x = 1 to n
    x = x + 1
    Next x

#Note this is more like VB.Net code than Python

  is directly related to the size of n

  if n was 2000, it would take 2000 loops to complete

  In this case time is said to increase 'linearly' with n

  All of the above are correct

 14. It is preferrable to have an algorithm which is constant and does not depend on the size of n. 
And the following algorithm is an improvement on using a for loop to sum up all the numbers up to 'n'. Sum of numbers = n(n+1) / 2

  FALSE

  TRUE

 15. Suppose you were required to sort 200 words into alphabetical order. You could do this using brute force going through every combination to find the right order.

  Even with a powerful computer, it would still take an incredibly long (impossibly long) time to work out.

  In mathematical terminology the number of combinations in this case would be factorial 200 or 200!

  The time efficiency of this algorithm is factorial n (n!)

  All of the above statements are true.

 16. The more practical way to attempt a sort would be to use a

  None of the above

  lineary or binary search

  bubble or quick sort

  faster CPU to compute the factorial

 17. Is it better to run a really fast algorithm that takes up a lot of memory or is it better to run a slower algorithm that uses less memory?

  None of the above

  It depends on whether the desired output is time critical or if there is a hardware limit

  It is always better to have a slower algorithm which takes less space

  It is always better to have a fast algorithm

 18. If there is a hardware limit to the memory capacity then a slower algorithm may be best for the situation

  TRUE

  FALSE

 19. Look at the two algorithms that require the value of every pixel in a stored image to be changed. What is true of algorithm #2? 
Algorithm #1
=============
1. Entire image (all pixels) is read into memory
2. A parallel calculation is applied on every pixel
3. The image is then stored /saved again.



Algorithm #2
=============
1. A single pixel is read into memory
2. A calculation isperformed on the single pixel
3. The pixel (which has been changed) is stored.
4. REPEAT all the above steps until all the pixels are dealt with.

  Algorithm #2 is slower than Algorithm #1 but the memory requirement is minimal as compared to Algorithm #1

  Algorithm #2 is clearly the superior algorithm in terms of both speed and space efficiency

  Algorithm #2 is much slower than #1 and also has a huge memory and space requirement

  Algorithm #2 is much faster than the first algorithm and the memory requirement is also minimal

 20. The Big O notation (learn more in advanced levels) basically quantifies how the input 'n' affects the outcome O

  TRUE

  FALSE


Report an error