Example of a deterministic algorithm?

algorithm deterministic
Steven Corea picture Steven Corea · Apr 17, 2012 · Viewed 22.3k times · Source

Good evening I was wondering if someone could please provide me with a simple pseudocode example of a deterministic algorithm... I will greatly appreciate it and surely give you points!!. thanks

Answer

Li-aung Yip picture Li-aung Yip · Apr 17, 2012

To me, "deterministic" could mean many things:

  • Given the same input, produces the same output every time.
  • Given the same input, takes the same amount of time/memory/resources every time it is run.
  • Problems of complexity class P that can be solved in polynomial time by a deterministic computer, as opposed to problems of complexity class NP which can be only solved in polynomial time using a non-deterministic computer.

Which of these do you mean?

The most simple deterministic algorithm is this random number generator.

def random():
    return 4 #chosen by fair dice roll, guaranteed to be random

It gives the same output every time, exhibits known O(1) time and resource usage, and executes in PTIME on any computer.

Related questions

Mapping two integers to one, in a unique and deterministic way

Imagine two positive integers A and B. I want to combine these two into a single integer C. There can be no other integers D and E which combine to C. So combining them with the addition operator doesn't work. …

Read More
What is a Deterministic Quicksort?

I have been reading about Quicksort and found that sometimes it' s referred to as "Deterministic Quicksort". Is this an alternate version of the normal Quicksort ? What is the difference between a normal Quicksort and a Deterministic Quicksort ?

Read More
How to merge two finite state automata?

Say I have two deterministic finite state automata represented by the following transition diagrams: FSA for keyword IF: IF ___ ___ _ / \ I / \ F // \\ >| 0 |----->| 1 |----->||2|| \___/ \___/ \\_// FSA for an ID: [A-Z][A-Z0-9]* ------------ ___ | _ LET | / \ LET // \\<------ >| 0 |-----&…

Read More