Computer Science Department – Rutgers University Spring 2018
CS 205: Final Exam Question 1 – Functions 16:198:205
Let SN = {0, 1, 2, . . . , N − 1}, i.e., the integers greater than or equal to 0, and strictly less than N .
1) Define a function f : S13 7→ S13 by f(x) = 6x mod 13.
a) What is the domain of f? The range of f? The image of f?
b) Prove that f is injective, using the formal definition of injectivity.
c) Is f invertible? If so, give the values of its inverse function.
2) Define a function g : S15 7→ S15 by g(x) = 6x mod 15.
a) What is the domain of g? The range of g? The image of g?
b) Show that g is not injective. If x1 and x2 in S15 map to the same value under g, what must be true about
x1 and x2?
c) Show that g is not surjective. If y ∈ S15 is not mapped to by g, what must be true of y?
d) Give a set A ⊂ S15 and B ⊂ S15 such that g is an invertible map from A to B. Find the largest A,B you
can.
Given a function f : S 7→ S (unrelated to the above), a value x ∈ S is a fixed point or has order 1 if x = f(x).
Similarly, x has order 2 if x = f(f(x)), and order 3 if x = f(f(f(x))). A point x has order k if applying f k-times
to x yields x. If x never returns to x under repeated applications of f , then x has infinite order, or is transitory.
3) For any N > 1, give an example of an f : SN 7→ SN that has no fixed points.
4) For any N > 1, give an example of an f : SN 7→ SN that has only a single point of finite order.
5) Argue that for any N > 1, given f : SN 7→ SN , if x has finite order, then x has an inverse under f , i.e., if every
point x ∈ SN has a finite order, then f is invertible. Consider small examples first.
Suppose you had a program that, given an image file as input, returned a tag from a finite set of tags Tags =
{cat,dog, orange, . . . ,UFO,CannotBeDetermined}, describing the contents of that image (a standard computer vision
problem).
6) Describe this program as a function, mapping one set to another set. What is the domain, what is the range?
Be as precise as you can be. Is this function invertible?
7) Suppose that the program were restructured so that it returned a collection of tags describing the contents of
the image. For instance, a picture of a dog and a cat sitting together might return {dog, cat}. Describe this
program as a function, mapping one set to another set. What is the domain, what is the range? Be as precise
as you can be. Is this function invertible?
1
Computer Science Department – Rutgers University Spring 2018
Bonus
A computer can generally be thought of as a device for executing sequences of commands known as programs. A
program can be thought of as a description of a function mapping inputs to outputs. By running a computer over
a potentially infinite amount of time, producing an infinite sequence of characters as output, we may interpret their
computations as producing real numbers.
Thinking in terms of a program as a finite sequence of characters or commands and similarly assuming that the
program input must also be finite – argue that there are real numbers that cannot be computed by any program.
Why is this argument independent of such facts as computer speed or architecture/design?
2