# 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

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

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