Preview

01 - Types of problems

 1. Fill in the blanks for the following excerpt.
You are familiar with many problems (or functions) that are computable 
(or decidable), meaning there exists some algorithm that computes an answer
(or output) to any instance of the problem (or for any input to the function)
in a ____________________________.

  single step

  non-halting type method

  polynomial fashion using linear progression

  finite number of simple steps.

 2. For the following operation, given any integer 'x', it would not be possible to compute x + 1 in a finite number of steps.
f(x) = x + 1 

  TRUE

  FALSE

 3. A non-computable is a problem for which there is no algorithm that can be used to solve it.

  FALSE

  TRUE

 4. One of the most famous examples of non-computability (or undecidability) is the__________________.

  x = x - 1 problem

  halting problem

  babbage conundrum

  turing machine

 5. To show that a problem is not computable, we need to show that no algorithm exists that solves the problem.

  TRUE

  FALSE

 6. We know the Halting Problem is noncom- putable. If a solution to some new problem P could be used to solve the Halting Problem, then we know that P is __________.

  also noncomputable.

  finite

  potentially solvable, but only by a super computer

  computable

 7. The proof technique where we show that a solution for some problem P can be used to solve a different problem Q is known as a _________.
Note:
P = NP Challenge
Can every problem whose solution can be quickly
verified by a computer also be quickly 
solved by a computer?

  supposition

  ressurection

  induction

  reduction

 8. A problem Q is __________ to a problem P if a solution to P could be used to solve Q

  suppositional

  ressurectable

  reducible

  inducable

 9. The following problem is computable: Computing the greatest common divisor of a pair of integers.

  TRUE

  FALSE

 10. The folllowing problem is non-computable: Finding the shortest path between a pair of nodes in a finite graph

  FALSE

  TRUE

 11. Fill in the blanks for the following excerpt.
Computer scientists classify algorithms according to how 
they scale as the problem gets bigger. If N measures the 
size of the problem, the number of data points, dimensions,
 records and so on, ideally we would like an algorithm 
that takes ______________ as N gets bigger.

  the same time

  an infinite time

  a longer time

  a shorter time

 12. Usually the time taken to complete a task depends on N or N squared or some power of N. Such algorithms are said to take “_____________” and these are regarded as good algorithms

  constant time

  quadratic time

  linear time

  polynomial time

 13. The best algorithms that we can hope for is an algorithm that runs in ________ i.e. it doesn't matter how big the problem is the task takes the same time

  linear time

  constant time

  polynomial time

  quadratic time

 14. Non-polynomial time algorithms are the ones that grow to the point where what you thought was just slow for 10 items suddenly takes more time than the universe has to run for 11 items!

  FALSE

  TRUE

 15. Decide whether the excerpt below referring to NP problem is true or false.
There are also the NP – Nondeterministic Polynomial – problems. 
These are such that if you guess a solution then you can verify 
that it is a solution in polynomial time but if you don’t guess a 
solution then you can’t find one in polynomial time.

  TRUE

  FALSE

 16. The question “is this number a nonprime” is NP because it only takes a single divisor to prove that it isn’t. Is the excerpt true or false?
NP problems are hard to solve but easy to check. 

You can think of the divisor provided as a “certificate”
 that the number in question isn’t a prime. On the other 
hand the related, or “dual” question, “is this number a
 prime” cannot be solved by providing a certificate.

  TRUE

  FALSE

 17. The halting problem is easy to explain – simply write a program that examines other programs to determine if they __________________.

  loop for a finite number of times, but always less than 1 million

  eventually halt

  loop at least once

  halt or loop forever

 18. A type of algorithmic problems that returns a yes/no answer and is decidable is called a:

  halting problem

  decision problem

  halted problem

  non computable problem

 19. An algorithmic problem that will not be solved in a polynomial time frame. It can take too long to solve. It might be plausible with a limited input.

  tractable problem

  intractable problem

  decision problem

  polynomial problem

 20. A tractable problem is an algorithmic problem that can be solved in a polynomial time frame. (reasonable time frame)

  FALSE

  TRUE