Codelet 1: Sets and Bit Strings

The due date for this codelet is January 30, 11:59PM.

Introduction

The goals of this codelet are to refresh your knowledge of Python with a concrete implementation of a set class. This draws on the Computer Project problem 1 from Chapter 2 of Rosen’s Discrete Mathematics and Its Applications.

Outline

• Grading
• Core Task

Your assignment

Your task is to:

1. Download codelet1.zip from the course website and open it. You will find these instructions and codelet1.py which has scaffolding for you.
2. Complete the core task which is implementing some class methods for basic set operations.

Grading

When assessing your code, satisfactory achievement is demonstrated, in part, by:

• Simple, clear, and clean code
• Uses only basic Python (no imports beyond what is already in the file)
• Code passes all relevant tests

Core Tasks

Given subsets A and B of a set with \(n\) elements, use bit strings to find \(\overline{A}\), \(A \cup B\), \(A \cap B\), \(A \setminus B\), and equality (e.g., \(A = B\)). In particular, you will implement a class Set which builds a bit string for some arbitrary set \(S\) given a universe \(U\) (which contains \(n\) elements). You may assume \(U\) is a reasonable size. Note, \(U\) can contain any Python object (with a defined equality operator; e.g., strings, floats, ints, lists, and instances of your Set class). Your class will implement each of the operators outlined above.

In addition to the class Set there are two helper functions create_bitstring and create_subset which you should implement before implementing Set, so that you can more easily check your code.

Submitting

Submit your file codelet1.py (with that EXACT name) to gradescope. There is an autograder which will tests your code. You may re-submit as many times as you would like prior to the deadline.