Practice with sets

Due
Wed Sep 18 11:59 pm
Starter files
lab2.zip
Submission
Please submit your work using Gradescope.

Overview

The learning goals of this lab are the following:

  • continue to practice working with an important data type for this course, sets
  • practice thinking about recursive functions

In this lab, you are asked to implement the one method in the SetsPractice class. The removeX method takes a set of sets and a string x and returns a new set of sets where every occurrence of x has been removed from the sets. This is a warm up method to the more complex methods you will implement next week.

In addition, there are some pencil and paper problems to get you thinking recursively in preparation for next week’s lab.

Requirements

Warm up with removeX This method is a warm up problem that will help you catch some common mental bugs around how java objects work. In Java, a Set of objects is really a set of references to objects. When you have finished this method, be sure to upload to gradescope and check the results of the tests provided there before going on.

Test your work In the main method, you should call your method on various examples to verify that it works correctly.

Pencil & paper exercises Answer the questions below (see “Thinking Recursively”).

Teaming up You may work with a partner. Larger groups are not permitted.

Thinking Recursively

Working with a partner, answer these questions. Check your answers with a TA or professor before the end of lab.

  1. Sets can be defined via enumeration or abstraction. Let’s define $S$ by enumeration: $S := \{ 1, 2, 3 \}$ and let’s define $T$ be abstraction: $T := \{ (x + 1) \bmod 4: x \in S \}$. What are the elements of $T$?
  2. Suppose $S := \emptyset$. What is $\mathcal{P}(S)$? (Be careful!)
  3. Consider $A := \{ a, b, c \}$. What is $\mathcal{P}(A - \{ a \})$? (See if you can observe a relationship between $\mathcal{P}(A)$ and $\mathcal{P}(A - \{ a \})$. The next question asks you to formalize this pattern.)
  4. Given a set $S$ of arbitrary size and let $x$ be some element in $S$. Define $T := S - \{ x \}$ and define $P_T := \mathcal{P}(T)$. Let $P_S := \mathcal{P}(S)$. Express $P_S$ in terms of $P_T$ and $x$ using set operations (union, intersection, difference) and set abstraction (see first question).

Your answer to the last question provides a hint on how you might implement power set generation using recursion (think of $P_T$ as the result of a recursive call on a smaller input).