Questions tagged [sets]

Questions about finite and infinite sets and multisets, related data structures and concepts.

276 questions
Filter by
Sorted by
Tagged with
112 views

2k views

Multisets of a given set

A multiset is an unordered collection of elements where elements may repeat any number of times. The size of a multiset is the number of elements in it counting repetitions. (a) What is the number of ...
233 views

Finding “fingerprint” sets

Let's say we have 10 people, each with a list of favorite books. For a given person X, I would like to find a special subset of X's books liked only by X, i.e. there is no other person that likes all ...
13k views

What is complement of Context-free languages?

I need to know what class of CFL is closed under i.e. what set is complement of CFL. I know CFL is not closed under complement, and I know that P is closed under complement. Since CFL $\subsetneq$ P I ...
1k views

Cantor's diagonal method in simple terms?

Could anyone please explain Cantor's diagonalization principle in simple terms?
145 views

Functions between sets?

I recently took a practice exam for the Computer Science GRE and this was one of the questions: Assume that set $A$ has 5 elements and set $B$ has 4 elements, how many functions exist from set $A$ ...
225 views

Computing the rank of a multiset after inserting another element

What is the procedure for computing the rank of a multiset after inserting an element? For instance, lets say we have a set $S = (0,1)$ containing $n = 2$ distinct elements. The multiset $M = (1,1)$ ...
376 views

Problems for which algorithms based on partition refinement run faster than in loglinear time

Partition refinement is a technique in which you start with a finite set of objects and progressively split the set. Some problems, like DFA minimization, can be solved using partition refinement ...
Given a set $\mathbf{S}$ of sets, I’d like to find a set $M$ such that every set $S$ in $\mathbf{S}$ contains at least one element of $M$. I’d also like $M$ to contain as few elements as possible ...