Basic Data Structure Knowledge

A set is an unordered collection of objects.

S = { 2, 4, 7 }

This means S denotes a set containing the numbers 2, 4 and 7.

The concatenation of two strings x ∈ Σ^n, y ∈ Σ^m is the (n+m)-length string xy obtained by writing y after x. That is, if x ∈ {0,1}^n and y ∈ {0,1}^m, then xy is equal to the string z ∈ {0,1}^n+m such that for i ∈ [n], z_i = x_i and for i ∈ {n,..., n+m-1}, z_i = y_i-n

For any natural number n ∈ N, we define the set [n] as {0, …, n-1} = { k ∈ N: k < n }

The Kleene Star, or Kleene Operator/Kleene Closure, is a unary operation (meaning there’s only one input), either on sets of strings or on sets of symbols or characters. It is usually written like Σ* or V*, and can be described as the set containing the empty string and all finite length strings that are generated via concatenating arbitrary elements of V, including the use of the same element multiple times.

{0,1}^n = {(x0,...x_n-1) : x0,..., xn-1 ∈ {0,1} } This may also be expressed as {0,1}* = ∪_(n ∈ N) {0,1}^n

This is the set of all n-length binary strings for some natural number n. This should read as: The set of all n-tuples of zeroes and ones ({0,1}^n) is equal to the set of x to x(n-1) such that every x is an element of the set {0, 1}. So, for example, {0,1}^3 = {000, 001, 010, 011, 100, 101, 110, 111}

Ranks = { A, K, Q, J, 10, … }, Suits = { Spades, Hearts, Clubs, Diamonds } When we do Ranks x Suits, this would be the Cartesian Product of the 13-element set of Ranks and the 4-element set of Suits, resulting in 52 ordered pairs that would represent all of the possible cards. Because Cartesian Products factor in order, however, technically, while Suits x Ranks would also produce 52 ordered pairs, this would be a different answer.

A set can either be defined by listing the elements or writing down the rule that they satisfy.

This is a definition of a set, that says that EVEN is equal to the set containing x, such that x is the product of 2 * y, and is y is some non-negative integer.

This is a definition for the set EVEN, which contains an infinite set of elements following the pattern of { 0, 2, 4, … } (Implying that this is a set of all even numbers)

No, a set can be any collection of things. For example, the elements can refer to cities, vowels, other sets, etc.

UNION (∪): This is the set that contains all the elements that are either in S and in T if we are looking for the union of sets S and T.

INTERSECTION (∩): The intersection of S and T is the set of elements that are both in S and in T.

DIFFERENCE ( – ): The set difference of S and T is the set of elements that are in S but not in T.

A tuple is an ordered collection of items. So if a set is a tuple, then the tuple { 1, 5, 2, 1 } is not the same as the tuple { 1, 1, 5, 2 } or even { 1, 5, 2 }

A string is a tuple where every element comes from some finite set Σ.

A sequence is a tuple that is infinite.

If S and T are sets, then their Cartesian Product is denoted as S x T, and it is the set of all ordered pairs (s, t) where s ∈ S and t ∈ T

n ∈ S

This means n is part of the set S.

For example: S = { 2, 4, 7 }, therefore 2 ∈ S

Sets are identical when they contain the same elements regardless of their order. For example,

S = { 2, 4, 7 } and V = { 7, 4, 2 }

S is identical to V

Technically, a set cannot have an element repeat itself. For example, if a set is defined as S = { 2, 2, 4, 7 }, it is essentially the same as S = { 2, 4, 7 }.

The cardinality of a set is denoted as | S |, and means the number of elements a set contains. If we have something that says | S | = 3, then that means that the cardinality, or length, of the set S is 3. Likewise, if S = { 1, 2, 3 }, then, based on the number of elements seen in the set S, the cardinality of S is 3. Cardinality can be defined for both finite and infinite sets.

This means that the cardinality, or length, of the set S is 4

Finite sets have a finite number of elements and are countable. Infinite sets have an finite number of elements and can be countable or uncountable.

The set of natural numbers is a countable infinite set because we can technically list them and thus count them.

A subset is when all the elements of one set exist in another set. This is denoted as S ⊆ T

This means S is a subset of the set T.

A superset is what T is to S if their relationship is denoted as S ⊆ T. This means that every element of S exists in T, and there T is a superset of S.

A strict subset, also known as a proper subset, is denoted as A ⊊ B. This means that A is a subset of B, but A != B.

This means A is a strict subset of B.