Algorithms

Algorithms don't have to terminate. Consider a program which prints out the digits of Pi one after another. It does not terminate, but it's implementing an algorithm to calculate those digits.

Algorithms don't have to be deterministic. Consider optimisation algorithms which use randomness like genetic algorithms and simulated annealing. They can use pseudo-randomness, but that's not part of the algorithm (usually), it's part of the implementation, and true external randomness is allowed too. Some algorithms only work if they have a source of randomness, and thus are non-deterministic. If the randomness is not truly random, they fail to terminate for some inputs.

Consider also parallel algorithms; a lot of them have non-deterministic behaviour because the global executation order is inherently not determined.

Perhaps there is some definition of "algorithm" which requires termination and determinism, and perhaps it was always like that in the distant origins of the word (before computers...), but it's not a definition I'm familiar with.