Computer Science Department – Rutgers University
Spring 2018
CS 205: Final Exam Question 1 – Functions
LetSN ={0,1,2,…,N−1},i.e.,theintegersgreaterthanorequalto0,andstrictlylessthanN. 1) Defineafunctionf:S13 →S13 byf(x)=6x mod13.
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) Defineafunctiong:S15 →S15 byg(x)=6x mod15.
16:198:205
- 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 → 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) ForanyN>1,giveanexampleofanf:SN →SN thathasnofixedpoints.
- 4) ForanyN>1,giveanexampleofanf:SN →SN thathasonlyasinglepointoffiniteorder.
- 5) Argue that for any N > 1, given f : SN → 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