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