The normal notion of an algorithm is the deterministic notion.
If a deterministic algorithm (or program) is run twice on the same input, it follows exactly the same sequence of steps both times.
In order to say that a deterministic algorithm solves a problem, it must eventually stop on every input, and it must always give the correct answer.
Partial computation is another notion of computation that is useful in computability theory. It is only used for decision problems.
A partial algorithm stops to indicate that the answer is yes and loops forever to indicate that the answer is no.
A problem is partially computable if there is a partial algorithm for it.
The halting problem is an example of a partially computable problem.
You should be prepared to show that a particular problem is partially computable.
A nondeterministic algorithm is also used for a decision problem. It is an evidence checker.
Such an algorithm does not need to solve a problem in the usual way at all. Instead, the program receives two pieces of information: The problem input and some evidence.
A nondeterministic algorithm for set S accepts pair (x, e) if it finds e convincing evidence that x ∈ S.
(Alternatively, it accepts pair (x, e) if it finds e convincing evidence that the correct answer to input x of problem S is 'yes'. You can see here how the set notation leads to simpler terms.)
Suppose that check(x, e) returns yes if e is convincing evidence that x ∈ S, and returns no otherwise. Nondeterministic algorithm 'check' is required to have two properties.
If x ∈ S then there must exist evidence e so that check(x, e) = yes.
If x ∉ S then there must not exist evidence e so that check(x, e) = yes.
Notice that, when the answer is yes, convincing evidence is required. When the answer is no, evidence is not required.
You should be prepared to write a nondeterministic polynomial-time algorithm for a given problem.
Randomized algorithms can rely on random events, such as coin tosses. Randomized algorithms are not always required to give the correct answer. But a randomized an algorithm usually has a confidence parameter, k, that controls the error probability.
Here are some kinds of randomized algorithms.
One kind of randomized algorithm always gives the correct answer. But its running time is a random variable. With probability 1 it will eventually stop and give an answer.
Another kind has one-sided errors. When the algorithm answers yes, the answer is definitely yes. But when it answers no, the probability that the correct answer is no is at least 1 − 2−k.
A third kind has two sided errors. Any time the algorithm gives an answer, the answer is correct with probability at least 1 − 2−k.