Description

CSCI 301 Lab 2 (Racket Programming: Recursion) Solved

1. Enter and load the following function.
(define (mystery L)
(if (null? L)
L

(append (mystery (cdr L))
(list (car L)))))
1) Run this function on the following lists
(mystery ‘(1 2 3))

(mystery ‘((1 2) (3 4) 5 6))
What does this function do? Explain the logic of the function.
Answer:

2) As you may have noticed, there is no return statement here. Explain how the return value is
determined in the above function.
Answer:

2. To watch your program in action with the debugger, click the “Debug” button instead of the “Run”
button. Then rerun your program by typing (in the definitions window)
(mystery ‘(1 2 3))

A series of debugging buttons will appear at the top of the definitions window. Click “Step”
repeatedly, and watch the pointer move through your code. Also watch the gray bar to the far left of
Page 2 of 3

the debugging buttons. DrRacket will show you the return values for functions when they are called.
You can also hover your mouse over variables (hover the mouse over the variable L, for example),
and DrRacket will show you those variable values to the right of the debugging buttons. You can also
see the stack of function calls and variable values to the right.

You will note a green arrow and circle in the body of mystery. These represent the expression that is
currently being evaluated. You should also note the red circle. That represents a breakpoint.
You can use the “Go” button to resume execution of your program. More instructions on debugging
can be found in the Racket documentation:

https://docs.racket-lang.org/drracket/debugger.html
3. Modify the program as follows:
(define (mystery L)
(if (null? L)
L

(begin
(displayln L)
(append (mystery (cdr L))
(list (car L))))))
What does begin do? What does displayln do?
Answer:

Page 3 of 3
4. Write a recursive function (gen-list start end). This function will generate a list of
consecutive integers, from start to end. (If start > end then an empty list is generated. See
how to compare two numbers: https://docs.racket-lang.org/heresy/math.html).
For example: (gen-list 1 5) —> (1 2 3 4 5)

5. Write a recursive function named sum that adds up all the elements in a list. For example:
(sum ‘(4 5 0 1)) —> 10
(sum (gen-list 1 5)) —> 15
Do something reasonable if the list is empty.

6. Write a recursive function, retrieve-first-n, that returns a list of the first n elements in a list.
Example:
> (retrieve-first-n 3 ‘(a b c d e f g h i))
(a b c)

Your code should do something appropriate if n is too big or too small (negative). It doesn’t
matter to me precisely what it does under these circumstances, so long as it does something
reasonable (doesn’t crash or return complete nonsense).

Your function should not use any other Racket functions than those which have been introduced
in this lab and lab 1. [An exception: if you wish, you may use the functions <, >, <=, or >=.]
7. Write a recursive function pair-sum? that takes an integer sequence as generated by the genlist function in exercise 4 above. This function tests whether any two adjacent values in the given
list sum to the given val.

For example,
(pair-sum? ‘(1 2 3) 3) —> #t since 1+2=3. Similarly,
(pair-sum? (gen-list 1 100) 1000) —> #f since no two adjacent integers
in the range 1 to 100 can sum to 1000.

You must use recursion, and not iteration. You may not use side-effects (e.g. set!).

To turn this assignment in:

1. Exercise 1 and 3: submit a copy of the document with your answers to exercise 1 and 3 on
Canvas.
2. Exercise 4 to 7: The solutions will be turned in by posting a single Racket program (lab02. rkt)
containing a definition of all the functions specified, (including gen-list, etc.).

 

CSCI 301 Lab 3 (Racket Programming: Recursion and Set Operations) Solved

In Racket sets can be represented as lists. However, unlike lists, the order of values in a set is not
significant. Thus both (1 2 3) and (3 2 1) represent the same set.

***For the following questions, you may assume that a sets contains only atomic values (numbers,
string, symbols, etc. but not sets or lists) and it does not contain duplicate members.

1. Write a Racket function(member? x L) that tests whether 𝑥 ∈ L where L is a set (represented as
a list). (Hint: 𝑥 ∈ L if and only if either x is equal to the head of L, or x is in the remainder of L.)
Test cases:
(member? 1 ‘(3 2 1)) —> #t
(member? 4 ‘(3 2 1)) —> #f
(member? 1 ‘())—> #f
(member? ‘susan ‘(susan john ryan)) —> #t

2. Write a Racket function(subset? L1 L2) that tests whether L1 ⊆ L2. L1 is a subset of L2 if
every element of L1 is also a member of L2.

Test cases:

(subset? ‘(1 2 3) ‘(3 2 1))—> #t
(subset? ‘(1 2 3) ‘(4 5 6)) —> #f
(subset? ‘(1 2 3) ‘(1 2 3 4 5 6)) —> #t
(subset? ‘(1 2) ‘())—> #f

***Use the function(member? x L)as a helper function in your implementation.
3. Write a Racket function (set-equal? L1 L2) that tests whether L1 and L2 are equal. Two sets
are equal if they contain exactly the same members, ignoring ordering (or in other words, two sets
are equal if they are a subset of each other). For example
(set-equal? ‘(1 2 3) ‘(3 2 1)) —> #t
(set-equal? ‘(1 2) ‘(3 2 1)) —> #f

(set-equal? ‘(ryan susan john) ‘(susan john ryan)) —> #t
Page 2 of 2

4. Two common operations on sets are union and intersection. The union of two sets is the set of all
elements that appear in either set (with no repetitions). The intersection of two sets is the set of
elements that appear in both sets.

Write Racket functions (union S1 S2)and(intersect S1 S2) that implement set union
and set intersection.

Test cases:

(union ‘(1 2 3) ‘(3 2 1)) —> (1 2 3)
(union ‘(1 2 3) ‘(3 4 5)) —> (1 2 3 4 5)
(union ‘(a b c) ‘(3 2 1)) —> (a b c 1 2 3)
(intersect ‘(1 2 3) ‘(3 2 1)) —> (1 2 3)
(intersect ‘(1 2 3) ‘(4 5 6)) —> ()
(intersect ‘(1 2 3) ‘(2 3 4 5 6)) —> (2 3)

The ordering of the elements in your answer may differ from the above.
You must use recursion, and not iteration. You may not use side-effects (e.g. set!).
The solutions will be turned in by posting a single Racket program (lab03. rkt) containing a definition of
all the functions specified.

 

CSCI301 Lab 4 (Racket Programming: Recursion and Set Operations) Solved

In Racket sets can be represented as lists. However, unlike lists, the order of values in a set is not
significant.

Thus both (1 (2 3))and((3 2) 1))represent the same set.
In lab 3, we have assumed that a set contains only atomic values (numbers, string, symbols, etc.) and it
does not contain duplicate members.

However, a general set can contain other sets (here you may again
assume that a set does not contain duplicate members). See the examples in the exercises below.
Extend your solutions to lab 3 to allow sets to contain other sets. Make sure to test additional cases of
sets containing sets containing sets, etc.

Hint: You may write helper functions and call them in the primary functions. A useful helper function
could be to test whether a given sublist/set exists in the given primary list/set.

1. Write a Racket function (set-equal? L1 L2) that tests whether L1 and L2 are equal. Two sets
are equal if they contain exactly the same members, ignoring ordering (or in other words, two sets
are equal if they are a subset of each other).

For example
(set-equal? ‘(1 (2 3)) ‘((3 2) 1)) —> #t
(set-equal? ‘(1 2 3) ‘((3 2)1)) —> #f
(set-equal? ‘(1 2 3) ‘((1 2 3))) —> #f

2. Two common operations on sets are union and intersection. The union of two sets is the set of all
elements that appear in either set (with no repetitions). The intersection of two sets is the set of
elements that appear in both sets.

Write Racket functions (union S1 S2)and(intersect S1 S2) that implement set union
and set intersection. For example
(union ‘(1 (2) 3) ‘(3 2 1)) —> (1 2 3 (2))
(union ‘((1 2 3)) ‘((3 4 5))) —> ((1 2 3) (3 4 5))
(union ‘((1 2 3)) ‘((3 2 1))) —> ((1 2 3))

(intersect ‘((1 2 3)) ‘((3 2 1))) —> ((1 2 3))
(intersect ‘((1 2 3)) ‘((4 5 6))) —> ()
(intersect ‘((1) (2) (3)) ‘((2) (3) (4))) —> ((2) (3))

The ordering of the elements in your answer may differ from the above.
You must use recursion, and not iteration. You may not use side-effects (e.g. set!).

The solutions will be turned in by posting a single Racket program (lab04. rkt) containing a definition of
all the functions specified.

 

CSCI301 Lab 5 (Properties of Relations) Solved

Implement the following Racket functions:

1. Reflexive?
Input: a list of pairs, L and a list S. Interpreting L as a binary relation over the set S,
Reflexive? returns #t if L is a reflexive relation over the set S and #f otherwise.

Examples:

(display “Reflexive?\n”)
(Reflexive? ‘((a a) (b b) (c c)) ‘(a b c)) —> #t
(Reflexive? ‘((a a) (b b)) ‘(a b c)) —> #f
(Reflexive? ‘((a a) (a s) (b b) (c c)) ‘(a b c)) —> #f
(Reflexive? ‘() ‘()) —> #t

2. Symmetric?

Input: a list of pairs, L. Interpreting L as a binary relation, Symmetric? returns #t if L is a
symmetric relation and #f otherwise.

Examples:

(display “Symmetric?\n”)
(Symmetric? ‘((a a) (a b) (b a) (b c) (c b))) —> #t
(Symmetric? ‘((a a) (a b) (a c) (c a))) —> #f
(Symmetric? ‘((a a) (b b))) —> #t
(Symmetric? ‘()) —> #t

3. Transitive?

Input: a list of pairs, L. Interpreting L as a binary relation, Transitive? returns #t if L is a
transitive relation and #f otherwise.

Examples:

(display “Transitive? \n”)
(Transitive? ‘((a b) (b c) (a c))) —> #t
(Transitive? ‘((a a) (b b) (c c))) —> #t
(Transitive? ‘((a b) (b a))) —> #f

(Transitive? ‘((a b) (b a) (a a))) —> #f
(Transitive? ‘((a b) (b a) (a a) (b b))) —> #t
(Transitive? ‘())—> #t

You must use recursion, and not iteration. You may not use side-effects (e.g. set!).
The solutions will be turned in by posting a single Racket program (lab05.rkt) containing a definition of
all the functions specified.

 

CSCI 301 Lab 6 (Properties of Relations) Solved

Implement the following Racket functions:

1. Reflexive-Closure

Input: a list of pairs, L and a list S. Interpreting L as a binary relation over the set S,
Reflexive-Closure should return the reflexive closure of L.

Examples:

(Reflexive-Closure ‘((a a) (b b) (c c)) ‘(a b c))
—> ‘((a a) (b b) (c c))
(Reflexive-Closure ‘((a a) (b b)) ‘(a b c))
—> ‘((a a) (b b) (c c))
(Reflexive-Closure ‘((a a) (a b) (b b) (b c)) ‘(a b c))
—> ((a a) (a b) (b b) (b c) (c c))
(Reflexive? ‘() ‘(a b c))
—> ‘((a a) (b b) (c c))

2. Symmetric-Closure

Input: a list of pairs, L. Interpreting L as a binary relation, Symmetric-Closure should
return the symmetric closure of L.

Examples:

(Symmetric-Closure ‘((a a) (a b) (b a) (b c) (c b)))
—> ‘((a a) (a b) (b a) (b c) (c b))
(Symmetric-Closure ‘((a a) (a b) (a c)))
—> ‘((a a) (a b) (a c) (b a) (c a))
(Symmetric-Closure ‘((a a) (b b)))
—> ‘((a a) (b b))
(Symmetric-Closure ‘())
—> ‘()

3. Transitive-Closure

Input: a list of pairs, L. Interpreting L as a binary relation, Transitive-Closure should
return the transitive closure of L.

Examples:

(Transitive-Closure ‘((a b) (b c) (a c)))
Page 2 of 2
—> ‘((a b) (b c) (a c))
(Transitive-Closure ‘((a a) (b b) (c c)))
—> ‘((a a) (b b) (c c))

(Transitive-Closure ‘((a b) (b a)))
—> ‘((a b) (b a) (a a) (b b)))
(Transitive-Closure ‘((a b) (b a) (a a)))
—> ‘((a b) (b a) (a a) (b b))

(Transitive-Closure ‘((a b) (b a) (a a) (b b)))
—> ‘((a b) (b a) (a a) (b b))
(Transitive-Closure ‘())
—> ‘()

You must use recursion, and not iteration. You may not use side-effects (e.g. set!).
The solutions will be turned in by posting a single Racket program (lab06. rkt) containing a definition of
all the functions specified.

 

CSCI 301 Lab 7 (Operations on Bags) Solved

Bags are structures very like sets save that they permit multiple instances as members. Like sets,
order is irrelevant. For example, the following bag contents are permitted:
[�, �, �, �, �, �, �]
and
[�, �, �, �, �, �, �]

Because of this difference between bags and sets, the bag-theoretic operations are somewhat
different from those defined for sets. Here are three of them.

1. Bag-Difference.

The operation Bag-Difference when applied to two bags results in a bag
where each element appears as many times as it appears in the first bag, minus the
number of times it appears in the second bag (but never less than 0 times).

For example
(bag-difference ‘(a a b a) ‘(b a a)) —>'(a)
(bag-difference ‘(a b a a) ‘(a b c)) —>'(a a)
(bag-difference ‘(a b c) ‘(a b a a)) —>'(c)
(bag-difference ‘(a b c) ‘(a b c)) —>'()
(bag-difference ‘() ‘(a b a a)) —>'()
(bag-difference ‘(a b a a) ‘())—>'(b a a a)

2. Bag-Union.

The operation Bag-Union results in a bag that contains the maximum
number elements that are contained in the operands.

For example
(bag-union ‘(a a b a) ‘(b a a)) —>'(a b a a)
(bag-union ‘(a b a a) ‘(a b c)) —>'(a a a b c)
(bag-union ‘(a b c) ‘(a b a a)) —>'(c a b a a)
(bag-union ‘(a b c) ‘(a b c)) —>'(a b c)
(bag-union ‘() ‘(a b a a)) —>'(a b a a)
(bag-union ‘(a b a a) ‘())—>'(a b a a)
Page 2 of 2

3. Bag-Intersection.

The operation Bag-Intersection results in a bag that contains the
minimum number of elements that are contained in the bag operands.

For example
(bag-intersection ‘(a a b a) ‘(b a a)) —> ‘(b a a)
(bag-intersection ‘(a b a a) ‘(a b c)) —> ‘(b a)
(bag-intersection ‘(a b c) ‘(a b a a)) —>'(a b)
(bag-intersection ‘(a b c) ‘(a b c)) —>'(a b c)

(bag-intersection ‘() ‘(a b a a)) —>'()
(bag-intersection ‘(a b a a) ‘())—>'()
The solutions will be turned in by posting a single Racket program (lab07. rkt) containing a
definition of all the functions specified.