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

  polynomial fashion using linear progression

  single step

  non-halting type method

  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

  FALSE

  TRUE

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

  TRUE

  FALSE

 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.

  computable

  finite

  potentially solvable, but only by a super computer

 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?

  induction

  reduction

  ressurection

  supposition

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

  reducible

  ressurectable

  suppositional

  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

  TRUE

  FALSE

 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.

  a longer time

  an infinite time

  a shorter time

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

  linear time

  quadratic 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

  quadratic time

  constant time

  linear time

  polynomial 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 __________________.

  eventually halt

  loop at least once

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

  halt or loop forever

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

  decision problem

  halting problem

  non computable problem

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

  polynomial problem

  tractable problem

  decision problem

  intractable problem

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

  FALSE

  TRUE


Report an error