Assignment 4
CMPU 145, Spring, 2019
Date assigned: 3/26/19. Date due: 4/2/19
Note - helper functions used in the many-to-one assignment, or
even the look-for-bros function from the midterm, can
be used to model the helper functions below.
Problem 1
---------
Check if a relation is a function:
A. Define a function, called MATCHES-SOME-FIRST?, that takes two inputs:
ITEM and RELN, where ITEM is anything (e.g., a number or a symbol)
and RELN is a list of pairs representing a relation. The function
should return #t if at least one of the pairs in RELN has ITEM as
its first entry, as illustrated below:
> (matches-some-first? 3 '((1 a) (2 b) (3 c) (4 d)))
#t
> (matches-some-first? 3 '((1 a) (2 b) (8 c) (4 d)))
#f
B. Define a function, called FUNCTION?, that takes a list of pairs as its
only input, representing some relation. It should return #t if that list
of pairs represents a *function* over its domain (i.e., if each item in
its domain maps to exactly one item in its range), as illustrated below:
> (function? '((1 a) (2 b) (3 c) (4 a) (5 b) (6 c)))
#t
> (function? '((1 a) (2 b) (3 c) (1 d) (2 e)))
#f
Hint: Use MATCHES-SOME-FIRST?
Problem 2
---------
Check if a function is injective:
A. Define a function, called MATCHES-SOME-SECOND?, that is the same as
MATCHES-SOME-FIRST? except that it returns #t if at least one of the pairs
in RELN has ITEM as its *second* entry:
> (matches-some-second? 'c '((1 a) (2 b) (3 c) (4 d)))
#t
> (matches-some-second? 'c '((1 a) (2 b) (8 e) (4 d)))
#f
B. Define a function, called INJECTIVE, that takes a list of pairs as
its only input, representing some relation. It should return #t if that
list of pairs represents an injective (i.e., one-to-one) function over its
domain, as illustrated below:
> (injective? '((1 a) (2 b) (3 c) (4 a) (5 b) (6 c)))
#f ;; not one-to-one
> (injective? '((1 a) (2 b) (3 c) (1 d) (2 e)))
#f ;; not a function
> (injective? '((1 a) (2 b) (3 c)))
#t ;; correct
This is super easy if you use Use MATCHES-SOME-FIRST? and MATCHES-SOME-SECOND?
Problem 3
---------
Compute the image of a function:
A. Define a function, called GET-FUNC-VALUE, that takes two inputs:
DOMAIN-VALUE and FUNC-PAIRS, in that order. However, it's easier to
explain what they are in the opposite order! FUNC-PAIRS is a list of
pairs representing a function; DOMAIN-VALUE is an element from the domain of
that function. The GET-FUNC-VALUE function should return as its output,
the function value associated with the given domain value.
> (get-func-value 2 '((1 2) (3 2) (2 4) (5 6)))
4
Note: You can assume that DOMAIN-VALUE is indeed an element of the domain
of the given function. Don't worry about runtime errors if GET-FUNC-VALUE
is called with bad data.
B. Define a function called, IMAGE, that takes two inputs:
SUBSET-OF-DOMAIN and FUNC-PAIRS, in that order!
- FUNC-PAIRS is a list of pairs representing a function.
- SUBSET-OF-DOMAIN is a subset of the domain of that function.
IMAGE should return a list representing the *image* of that function for
the given subset, as illustrated below.
> (image '(1 2 3) '((5 4) (3 4) (1 4) (2 6) (8 9)))
(6 4)
If done correctly, the output list will not contain any duplicates.
Submission Instructions
-----------------------
- Let's try submitting this assignment with the submit145 script and using hw4.
Please also include the assignment helper program along with your submission.
- A kind of rubric: this is a 20 point assignment with the following breakdown:
11 points - all functions work correctly
3 points - a sufficient number/kind of tester test cases
3 points - proper/sufficient comments
3 points - a test run is included with the submission