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

  hardware

  amount of loops used

  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

  Intractable problems

  Hardware limits

  Problems that cannot be solved algorithmically

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

  algorithmic

  intractable

  complex

  tractable

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

  algorithmic

  tractable

  intractable

  complex

 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 memory

  a minimal amount of computer memory

  no computer hardware

  more computer memory

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

  enormous amount of work

  linear amount of work x 2

  exponential amount of work

  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 _________________

  Big O algorithmic techniques

  binary search methods

  heuristic methods

  less time

 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