Preview

02 - Limits of computation

 1. There are two main things that are said to impose limits on what can be computed: algorithmic complexity and ______________

  human error

  amount of loops used

  code length

  hardware

 2. Which of the following are areas that need to be considered when it comes to the limits of algorithms?

  Hardware limits

  Intractable problems

  All of the above are valid answers

  Problems that cannot be solved algorithmically

 3. Problems that have a polynomial (or less) time solution are called:

  complex

  tractable

  intractable

  algorithmic

 4. Problems that have no polynomial (or less) time solution are called:

  algorithmic

  complex

  tractable

  intractable

 5. Computing based solutions in the form of algorithms can be used to solve all possible problems

  FALSE

  TRUE

 6. If a specific problem required _________________ than is feasible, it could be rendered effectively 'unsolvable'

  no computer hardware

  more computer memory

  a minimal amount of computer memory

  no computer memory

 7. Certain problems have what is called exponential complexity. This means that the problems requires an _____________________________.

  quadratic x linear amount of work

  enormous amount of work

  linear amount of work x 2

  exponential amount of work

 8. If a problem has exponential complexity, using faster or more processors (e.g. improving hardware) would make a world of difference and improve efficiency.

  TRUE

  FALSE

 9. Intractable problems can be made more efficient and useful (in terms of time) by using _________________

  less time

  heuristic methods

  Big O algorithmic techniques

  binary search methods

 10. There are certain problems that computers may never be able to solve e.g. the halting problem, wang tile problem, kolmogorov complexity 
Note: You may, as an extension, want to look into quantum computing and watch this video. Could quantum computing help remove some of the limitations we currently have?

  FALSE

  TRUE


Report an error