2 | Proof by I, proof by C, algorithm

Question 1

Three types of Proof?

Answer 1

1. Direct proof
2. Indirect proof
   proof by contradiction
3. Proof by induction

Question 2

Steps for Proof by Induction

Answer 2

Theorem, eg P(n)

Base case, eg for a (often 0 or 1) prove P(a)

Induction hypothesis (IH) eg that for some value k, P(k) holds

Induction step (IS) Show that if P(k) holds, P(k+1) also holds.

–> combination of these steps shows that P(n) is true for all values of n.

Question 3

Definition of an algorithm

Answer 3

Algorithm is a set of rules for carrying out calculation.

Execution of an algorithm must not include
- subjective decisions
- call for some intuition

Question 4

Deterministic algorithm?

Answer 4

• given a particular input, will always produce the same output
• underlying machine always passing through the same sequence of states.

Question 5

P Class?

Answer 5

• decisions problems
• easily solvable in Polynomial time w/ deterministic machine

Question 6

NP Class?

Answer 6

• decisions problems
• Nondeterministic Polynomial time: solvable in polynomial time by a nondeterministic Turing machine.
• verifiable in polynomial time by a deterministic Turing machine.

Question 7

NP-hard class

Answer 7

• (believed) can not be solved in polynomial time
• at least as hard as the hardest problem in NP
• Not all NP-hard problems are in NP.
• It takes a long time to check them.

Question 8

NP Complete class

Answer 8

• both NP and NP-hard: hard problems in NP.

Question 9

What is a tractable problem

Answer 9

Tractable means that a problem can be solved in practice as well as in theory

Question 10

What is an intractable problem

Answer 10

problems that can be solved in theory but not in practice .

Question 11

What is a heuristic?

Answer 11

• cannot control the error and it may be difficult to estimate it
• designed for problem solving more quickly when classic methods are too slow for finding an exact or approximate solution,
• or when classic methods fail to find any exact solution in a search space.
• This is achieved by trading optimality, completeness, accuracy, or precision for speed.
• In a way, it can be considered a shortcut.

Question 12

Symbol for:

for all

Answer 12

∀

Question 13

Symbol for:

such that

Answer 13

:

Question 14

Symbol for:

there exists

Answer 14

∃