DSA with Dart 101: Dominating Sets and Dynamic Relations

Before diving into Sets and Dynamic Relations let’s discuss is it important to learn DSA with Dart programming language?

So Yes, learning Dart is essential for Flutter development, as it’s the primary programming language used. While it’s not absolutely necessary to master Data Structures and Algorithms (DSA) with Dart specifically for most app development tasks, having a strong understanding of DSA in general is important for improving your problem-solving skills and writing efficient code.

Mastering DSA helps you optimize the performance of your apps, especially when dealing with large datasets, complex UI interactions, or features like search, sorting, and filtering. Many of the principles of DSA can be applied across different programming languages, so you can first learn them in Dart or any other language and then translate that knowledge to your Flutter projects.

So, while DSA might not be immediately needed for simple Flutter apps, it becomes more relevant as you start developing complex apps with high performance requirements.

Sets and Relations

A set is a collection of distinguishable members or elements. The members are typically drawn from some larger population known as the base type. Each member of a set is either a primitive element of the base type or is a set itself.
There is no concept of duplication in a set. Each value from the base type is either in the set or not in the set. For example, a set named P might consist of the three integers 7, 11, and 42. In this case, P’s members are 7, 11, and 42, and the base type is integer.

In Figure shows the symbols commonly used to express sets and their relationships. Here are some examples of this notation in use. First define two sets, P and Q.

P = {2,3,5},  Q = {5,10}

• |P| = 3 (because P has three members) and |Q| = 2 (because Q has two members).
• The union of P and Q, written P ∪ Q, is the set of elements in either P or Q, which is {2, 3, 5, 10}.
• The intersection of P and Q, written P ∩ Q, is the set of elements that appear in both P and Q, which is {5}.
• The set difference of P and Q, written P − Q, is the set of elements that occur in P but not in Q, which is {2, 3}.

Note that P ∪ Q = Q ∪ P and that P ∩ Q = Q ∩ P, but in general P − Q ̸= Q − P.

• In this example, Q − P = {10}.

Note that the set {4, 3, 5} is indistinguishable from set P, because sets have no concept of order. Likewise, set {4, 3, 4, 5} is also indistinguishable from P, because sets have no concept of duplicate elements.

The powerset of a set S is the set of all possible subsets for S. Consider the set S = {a, b, c}. The powerset of S is

{∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}

A collection of elements with no order (like a set), but with duplicate-valued elements is called a bag or you can say that a bag is like a set, but with two important differences:

• Order doesn’t matter, like in a set.
• Duplicates are allowed, unlike in a set.

To indicate that something is a bag and not a set, square brackets [] are used instead of curly brackets {}.

For example:

• A bag [3, 4, 5, 4] is different from the bag [3, 4, 5] because the first bag has two 4s, while the second bag has only one.
• In a set, {3, 4, 5, 4} would be considered the same as {3, 4, 5} because sets don’t allow duplicates, so the second 4 would be ignored.
• However, bags like [3, 4, 5, 4] and [3, 4, 4, 5] are considered the same, even though the order of elements is different. This is because order doesn’t matter in bags.

Sequence

Let’s discuss what a sequence is and how it differs from other collections like sets and bags.

A sequence is a list of elements where the order matters. This is different from sets or bags, where the order of elements does not matter. I indicate a sequence by using angle brackets ⟨⟩ to enclose its elements.
For example, in a sequence ⟨3, 4, 5, 4⟩, the position of each element is important. If you change the order, it becomes a completely different sequence.

Just like in bags, a sequence can contain duplicate values. For instance, in ⟨3, 4, 5, 4⟩, the number 4 appears twice, and that’s perfectly fine.
Sequences have specific positions or indexes for their elements. These positions start from 0. So, in the sequence ⟨3, 4, 5, 4⟩, the number 3 is at index 0, the number 4 is at index 1, and so on.
If the order or the values change, the sequence is considered different. For example:

• ⟨3, 4, 5⟩ is different from ⟨5, 4, 3⟩ because the order of elements has changed.
• Similarly, ⟨3, 5, 4, 4⟩ is different from ⟨3, 4, 5, 4⟩ because the positions of the elements are not the same, even though they contain the same numbers.
• Example 1: ⟨apple, banana, cherry⟩ is a sequence where “apple” comes first, “banana” second, and “cherry” third. If you switch the order to ⟨cherry, banana, apple⟩, it becomes a completely different sequence.

Relation

A relation over a set S is a set of ordered pairs from S. An ordered pair (a, b) means that a is related to b in some way.
For example, if S = {a, b, c}, a relation might include pairs like (a, b), (b, c), etc.

If a relation is written as R = {(a, c), (b, c), (c, b)}, it means:

• a is related to c,
• b is related to c,
• c is related to b.

In the context of the explanation, SSS is a set of elements. In the simplest terms, you can think of it as a collection of distinct items. For example, the set S could be {a, b, c} meaning it contains the elements a, b, and c.

Infix Notation:

Instead of writing ordered pairs like (x, y), relations are often written using a mathematical operator. For example, the “less than” relation between numbers is written as 1 < 3, not (1,3).

Reflexive

Imagine you have a group of people, and each person is “friends” with themselves. This means every person in the group must have a connection to themselves. This is a reflexive relation.
Example: If S = { John, Mary, Paul }, then the relation would include (John, John), (Mary, Mary), and (Paul, Paul).

A relation R is reflexive if every element in S is related to itself.
For example, if S = {a, b, c}, the relation R must include (a, a), (b, b), and (c, c) for it to be reflexive.

Symmetric

If John is friends with Mary, then Mary must also be friends with John. This is a symmetric relation because the friendship goes both ways.
Example: If (John, Mary) is in the relation, then (Mary, John) must also be in the relation.

A relation R is symmetric if, whenever a is related to b, then b is also related to a.
For example, if (a, b) is in R, then (b, a) must also be in R for the relation to be symmetric.

Antisymmetric

Suppose we have a relation like “is taller than.” If John is taller than Paul, then Paul cannot be taller than John. This is an antisymmetric relation because if two people have a relationship in both directions, they must be the same person (which is not possible in the case of height).
Example: if (John, Paul) is in the relation, (Paul, John) cannot be unless John and Paul are the same person.

A relation R is antisymmetric if, whenever a is related to b and b is related to a, then a and b must be the same element.
For example, if both (a, b) and (b, a) are in R, then a = b. This property restricts how elements can related to each other.

Transitive

If John is friends with Mary, and Mary is friends with Paul, then John must also be friends with Paul for the relation to be transitive.
Example: If (John, Mary) and (Mary, Paul) are in the relation, then (John, Paul) must also be in the relation for it to be transitive.

A relation R is transitive if, whenever a is related to b, and b is related to c, then a must also be related to c.

Equivalence Relation

A relation is an equivalence relation if it is reflexive, symmetric, and transitive. It groups elements into equivalence classes, where each group contains elements that are all related to each other.

Example: If the relation is “is in the same class as,” then all students in the same class form an equivalence class, because this relation is reflexive (everyone is in the same class as themselves), symmetric (if you’re in the same class as someone, they are in the same class as you), and transitive (if you’re in the same class as one person, and they are in the same class as another, then you’re all in the same class).

Thank you for taking the time to read! Feel free to explore more of our content or leave a comment below.

Explore more content related Flutter and Dart