Question

Describe an algorithm that determines whether a function from a finite set of integers to another finite set of integers is onto.

Short answer

An algorithm that determines whether a function from a finite set of integers to another finite set of integers is onto, can be given as below:

\user1procedure onto $f\left(x\right)\left(X=\left\{x_1,x_2,...,x_n\right\},y=\left\{y_1,y_2,...,y_m\right\}:setofintegers\right)$

\user1$fori:=1$ to m

Algorithm will return false if given function is not onto function, otherwise, it will return true.

Step-by-step solution

Steps Algorithm follows

Steps that algorithm has to follow are:

1. We will use for loop to select element from Y having condition i = 1 to m . Then, use another for loop to select element from X , having condition j = 1 to n .
2. Then if statement will check that every element in has corresponding element in X . Condition for if loop will be$f\left(x_j\right)=y_i$ .
3. We use one variable c to count how many elements Y in have corresponding element in X . If there is no corresponding value in X for any element in Y i.e., then algorithm will return false, otherwise it will return true.

Step 2:

The algorithm based on above conditions given as below:

\user1 procedure onto_$f\left(x\right)\left(X=\left\{x_1,x_2,....,x_n\right\},y=\left\{y_1,y_2,...,y_m\right\}:setofintegers\right)$

\user1 $fori:=1$to m