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:

  All of the above

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

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

  Time: how long does the algorithm take to complete?

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

  linear search

  binary search

  merge sort

  bubble search

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

  FALSE

  TRUE

 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.

  None of the above

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

  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.

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

  time and space

  lists and loops

  CPU usage and list memory

  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

  Alan Turing

  Ada Lovelace

  Bill Gates

  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

  This is called a space-time trade off

  This is called the 'impossible problem of Computing'

  None of the above

  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 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

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

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

  TRUE

  FALSE

 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…

  coarse complexity

  bubble complexity

  space complexity

  time 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

  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

  is directly related to the size of n

 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

  TRUE

  FALSE

 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.

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

  All of the above statements are true.

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

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

 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?

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

  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 fast algorithm

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

  FALSE

  TRUE

 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 much slower than #1 and also has a huge memory and space requirement

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

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

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

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

  FALSE

  TRUE


Report an error