Week 4 Complexity

Question 1

Algorithm

Answer 1

An algorithm is a set of rules by which the answer to a problem
can be found. It should have the following properties:
*finiteness;
*definiteness;
*well-defined inputs and outputs;
*effectiveness.

Question 2

Complexity

Answer 2

The complexity of an algorithm is the time taken for the algo-
rithm to terminate as a function of the inputs — in our case,
the time taken will typically be a function of the number of
vertices |V|and/or the number of edges |E|.

Question 3

Polynomial-time problem

Answer 3

We say that a problem is a polynomial-time problem if it can
be solved by a polynomial-time algorithm on a ‘deterministic
Turing machine’. The class of all polynomial-time problems
is called P.

Question 4

Non-deterministic polynomial-time problem

Answer 4

We say that a problem is a non-deterministic polynomial-time
problem if it can be solved by a polynomial-time algorithm on
a ‘non-deterministic Turing machine’. The class of all non-
deterministic polynomial-time problems is called NP.