# Questions tagged [sets]

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

19 questions
Filter by
Sorted by
Tagged with
1k views

### Looking for a set implementation with small memory footprint

I am looking for implementation of the set data type. That is, we have to maintain a dynamic subset $S$ (of size $n$) from the universe $U = \{0, 1, 2, 3, \dots , u – 1\}$ of size $u$ with operations ...
6k views

### Is every subset of a decidable set, also decidable?

Is it true that if A is a subset of B, and B is decidable, than A is guaranteed to be decidable? I believe it would be true because all the subsets of B should also be decidable making A decidable. I'...
1k views

### Concatenation of the intersection of two languages

I'm enrolled to a Formal Language And Automata course, and we have to prove this equation on sets of strings: $$(L_1\cap L_2)\cdot L_3 ≠ (L_1\cdot L_3) \cap (L_2\cdot L_3)$$ I've tried a lot of sets ...
97 views

### Redistributing a set of uniformly distributed numbers to an arbitrarily defined shape

Lets say I have a random number generator that spits out uniform numbers from 0 to 1 Next, I have a shape defined by a series of vertices, like { [0, 0.4], [0.5, 0.2], [1, 0.4] } In those vertices, ...
79 views

### Parser theory: How to systematically compute FOLLOW sets?

Forgive me for my ignorance as I am self-teaching myself some of this theory... I am having some trouble understanding how to systematically/algorithmically compute FOLLOW sets, given that I have ...
62 views

992 views

### How to find the maximal set of elements $S$ of an array such that every element in $S$ is greater than or equal to the cardinality of $S$?

I have an algorithmic problem. Given an array (or a set) $T$ of $n$ nonnegative integers. Find the maximal set $S$ of $T$ such that for all $a\in S$, $a\geqslant |S|$. For example: If $T$=[1, 3, 4, ...
320 views

### Asymptotic lower bound on the number of comparisons needed to find the intersection of unsorted arrays

A homework problem in my current CS class asks us to produce a comparison-based procedure for taking (essentially—there are some poorly-specified rules about duplicates) the set intersection of $k$ ...