Question

(a) Write an algorithm (use pseudo-code) to determine whether a function
f ∶ Z100 → Z100 is surjective. That is, supply a “Method” to go with
Input: A function (array) f with f(i) ∈ Z100 for i = 0, 1, . . . , 99.
Output: Boolean B. B=‘true’ if f is surjective, ‘false’ otherwise.
Try to make your algorithm as efficient as possible.
Do NOT include an implementation of your algorithm in a programming language.
(b) How many comparisons does your algorithm perform for a worst case when f is
surjective? Count all tests for =, ≠, < and >. Include all comparisons used, not just
comparisons of function values. For example, remember that each pass of a loop
will require at least one comparison to test whether the exit condition(s) has/have
been met.

Answer 1

a) We create a set i=0,1,2...99 and another set of possible outputs j=0,1,2...99

We go through each element of the input set and check if its output f(i) lies in the output set. The element is marked as belonging to the output set. And we do this for each f(i). We also count the number elements in the output set that have been marked. IF/When this count reaches 100, we can claim to have a surjective function

b) For each f(i) we have to check if 0<=f(i)<=99 which is 2 comparisons.This is always the case (we always go through all elements of i=0,1,2...99)

So there are a total of 200 comparisons always (2 for each of the 100 elements)

Please do rate this answer positively if you found it helpful. Thanks and have a good day!