W1 - Sets

Question 1

What is Cardinality of sets

Answer 1

• Number of elements in the set
• Denoted by |A| or #A

Question 2

What does N_0 mean

Answer 2

the set of nonnegative natural numbers (include zero and natural number)

Question 3

If A is an alphabet, what does:

A^k
A^*
A^0 

mean

Answer 3

• A^k, where k∈N_0, represents all the possible k possible strings
  ○ E.g., if A={0,1} then:
  A^1={0,1}
  A^2= {00,01,10,11}
  A^3= {000,001,010,011,100,101,110,111}
• A^∗ is the strings of all the possible finite lengths
  ○ It is an infinite set
  ○ Same example: A^∗ = {ε,0,1,00,01,10,11,000,001,…}
• A^0={ε} if A is an alphabet - characters belong to some finite set
  ○ This is the empty string

Question 4

What is a superset/subset

Answer 4

if A is a subset of B, A⊆B
if A is a superset of B, A⊇B

Question 5

What is maximum and maximal clique
And what is minimum and minimal clique

Answer 5

A maximum clique is a clique of maximum size; there is no larger clique.
* i.e., the biggest (or multiple biggest of the same size) maximal clique

A maximal clique is a clique that is not a proper subset of any other clique.

• i.e., cannot be extended by including another element such that all the elements are adjacent to each other

A minimum subset with some property has smallest size among all subsets with the property.
* i.e., smallest possible clique

A minimal subset with some property is a subset with the property that is not a proper superset of any other subset with the property. So, no proper subset has the property. In other words, if we remove anything from it, the property no longer holds.

• i.e., removing a element removes the clique

Clique = all nodes are connected to each other

Question 6

What is a powerset and what is size of powerset

ie How many subsets can the B have?

Answer 6

All the possible subsets, represetned by P(b).

size of powerset
|P(B)|=2^n

```E.g., B={1,2,3}
Then it can have the subsets:
{┤}
{1}, {2}, {3}
{1,2}{2,1}{2,3}

{1,2,3}
There is 8 subsets, i.e., 2^3=8

Using power set notation:
P(B)={┤},{1}, {2}, {3}, {1,2}, {2,1},{2,3}, {1,2,3}
|P(B)|=2^3=8```

Question 7

Eqs for Binomial coefficients

Normal and recurcive (not sure if recursive is needed)

Answer 7

(n choose k)= n! / (k!∗(n−k)!)

n choose k = [(n-1) choose (k-1)] + [(n-1) choose (k)]

Question 8

Set difference
What does B\A do

Answer 8

not(A) and B

think of it as B-A

Question 9

Symmetric difference

A△B

Answer 9

A△B = {x:x∈A or x∈B but not both}

exclusive or

A△B =(A∖B)∪(B∖A)
=(A∩¯B)∪(¯A∩B)
= (A∪B)∖(A∩B)

Question 10

Cardinality of Cartesian product

Answer 10

∣A×B∣=∣A∣∗∣B∣

Question 11

Rules for Partition
and what is coarsest and finest partition?

Answer 11

partition of a set A is a set of non-empty, disjoint subsets whose union is A
• Non-empty = contains >1 element, i.e., no empty elements
• Disjoint = no overlap,
Union is A = all the elements in the subset ‘add’ up is A
• Union is A = all the elements in the subset ‘add’ up is A

Properties
• coarsest partition of A is itself, i.e, {A}
• finest partition is where each element is its own set, i.e., for a set A, {{a}:a∈A}