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 ______________

  code length

  amount of loops used

  hardware

  human error

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

  All of the above are valid answers

  Problems that cannot be solved algorithmically

  Hardware limits

  Intractable problems

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

  complex

  algorithmic

  tractable

  intractable

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

  tractable

  complex

  intractable

  algorithmic

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

  TRUE

  FALSE

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

  no computer memory

  more computer memory

  no computer hardware

  a minimal amount of computer memory

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

  enormous amount of work

  exponential amount of work

  linear amount of work x 2

  quadratic x linear 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.

  FALSE

  TRUE

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

  less time

  heuristic methods

  binary search methods

  Big O algorithmic techniques

 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?

  TRUE

  FALSE