(a) Write an algorithm (use pseudo-code) to determine whether a function f: Z100 Z100 is surjective....

Transcribed Image Text:

(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. (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.