Sets and StickersSets in Computer Science for BeginnersZurich OkorenBlockedUnblockFollowFollowingMay 6Photo by Annie Spratt on UnsplashWhat are sets?According to Wikipedia:In computer science, a set is an abstract data type that can store unique values, without any particular order.
In other words we can think of sets as a collection of different objects.
In that collection, no two objects are the same meaning, there are no duplicates.
Additionally, within that collection it doesn’t matter where the object is in that collection, it just has to be there.
For example, let’s take a look at the stickers on this laptop.
Notice that no two stickers are the same.
For now let’s assume the space you see on the laptop is a collection.
Each sticker is an element of that collection.
We also don’t care where the stickers are on the laptop.
All we care about is that they are on the laptop.
Why does this matter?Well it matters because it allows us to implement operations such as finding the union, intersection and differences of two sets.
In other words, it allows us to compare two collections of things.
In the case of unions, we can compare two sets and ask: Which elements are in one collection OR the other.
This can be better visualized in the adjacent Venn diagram.
Basically, as long as the element is part of at least one of the the sets, then it’s part of the union.
This also includes elements that are in BOTH sets.
If we go back to are laptops and stickers analogy, that would mean if we have two laptops with stickers which stickers are in one laptop or the other?.Answer: all the stickers!Intersections are almost the opposite of unions where we are actually returning the elements that are in one collection AND also in the other collection.
These elements have to be part of both sets in order to meet the requirements for an intersection.
In other words which stickers can be found in both laptops?Lastly, the difference between sets are the elements that are in one set the are NOT in the other set as illustrated by Venn Diagram below.
Meaning I only care about the stickers that are in MY laptop only.
I don’t really care about the stickers that are also in the other laptop.
This may seem like fairly simple to us humans, but to a computer its relatively complex.
Thankfully, high level programming languages, which are languages that look closer to human language than machine language, such as Python allow us to write programs without needing to worry about all the syntax that machine languages need to work.
Here’s the CodeThe following set implementation uses a custom set class that is built on top of a custom hash table class.
For simplicity’s sake we’ll only look at the methods discussed in this article.
However, my full implementation can be found here.
UnionIntersectionDifferenceNext Steps…Thank you for taking the time to read the article.
If you take a look at the code, you might notice some strange things that look like O(n).
What I’m doing there is annotating the algorithmic analysis of the function, which you can learn more about here.
I also mentioned hash tables in this article, which I highly recommend Vaidehi Joshi’s article on hash tables here.
.. More details