Write an algorithm that determines if a function f from the

Write an algorithm that determines if a function f from the finite set A to the finite set B is an onto function.

Solution

A function f from A to B is “onto” iff for every element b there is an element a with f(a) = b

Solution: Algorithm

• Assume A has n elements, B has m elements.

• Keep a count for each element in B, setting counts to 0.

• For each compute = and add one to b’s count.

• If any b has a count of 0, then “not onto”, otherwise “onto”

Algorithm

OntoCkeck();

IsOnto true;

RecordKeeping = [0];

for j=1 to m

append 0 to recoedkeeping

for i=0 to n

for j=0 to m

if f(xi)=yj

RecordKeeping [j] =1;

for j=0 to m

RecordKeeping [j]=0

IsOnto False

Reuturn IsOnto