(a) Let Z 0,1,.,n-1). Write an algorithm (use pseudo-code) to determine whether
ID: 3702674 • Letter: #
Question
(a) Let Z 0,1,.,n-1). Write an algorithm (use pseudo-code) to determine whether a function f:Z Z is injective. That is, supply a "Method" to go with Input: A number n ? Z and a function (array) f with f(i) ? Zn for i-0, 1, . . . , n-1} Output: Boolean B. B f f is injective, 'false' otherwise. Try to make your algorithm as efficient as possible. You can include an implemen- tation of your algorithm in a programming language if you wish, plus sample input and output. However your program will be treated as back-up only, and ignored if it does not agree with your algorithm, or is not written to be comprehensible to a reader not familiar with your choice of programming language (b) For n 10 how many comparisons does your algorithm use for a worst case when f is injective? Count all tests for-, #, . Include all comparisons used, not just comparisons of function valuesExplanation / Answer
public static boolean bijective(int []zc) //zc is the domain
{
copy zc into zr //zr is the range and according to the question domain equal to co-domain
/**
* points to be noted for a bijective function
* for each x in domain there should be a f(x) exist in co-domain
* one element of co-domain should map to only one element of domain so we remove the f(x) after each itteration
* if one of them is not satisified then return false and get out of the loop
* if it is true for all elements then return true and exit
**/
for(int i=0;i<z.length();i++)
{
k=f(zc[i]);
search k in zr
if(not found)
return false;
if(found)
remove k from the co-domain
}
return true;
}
public static int f(int x) //it will return f(x)
{
return f(x); //write your function here
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.