Learning objectives
By the end of this week you can:
- 1 Describe sets by roster and by set-builder notation.
- 2 Decide subset relations and compute power sets and Cartesian products.
- 3 Apply union, intersection, difference and complement, and prove set identities.
- 4 Connect set identities to the logical equivalences from week 3.
- 5 Use Python sets, and measure similarity with the Jaccard index.
★ the wow moment
Netflix, Spotify and plagiarism checkers all compute |A ∩ B| / |A ∪ B|.
The Jaccard similarity of two sets is a single line of set algebra. It recommends songs, finds near-duplicate web pages and flags copied homework. You will build a mini recommender with it.
Topics
- Sets, elements, the empty set
- Subsets and power sets
- Cartesian products
- Union, intersection, difference, complement
- Set identities and membership tables
- Computer representation with bit strings
Before class
- Skim Rosen 2.1–2.2 (20 minutes is enough; we go through it together).
- Bring paper and a pen: part of every lecture is solving by hand.
In industry
-
Databases
UNION, INTERSECT and EXCEPT in SQL are set operations; a JOIN starts as a Cartesian product.
-
Bloom filters
Browsers and databases test set membership approximately with tiny memory.
-
Access rights
Permissions are sets; “can this user do X” is a membership test.
Lab 7: Sets and a Mini Recommender
Implement power sets and Cartesian products, verify set identities, and recommend courses with Jaccard similarity.
due Fri, Nov 20 · 23:59 · 100 points · opens in week 9
Go deeper
- Discrete Mathematics: An Open Introduction (Oscar Levin) · Section 0.3, sets
- Book of Proof (Richard Hammack) · Chapter 1, sets
- Mathematics for Computer Science (Lehman, Leighton, Meyer) · Chapter 4.1
Tags:setspower setCartesian productunionintersectionJaccard