# Questions tagged [sets]

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

272 questions
Filter by
Sorted by
Tagged with
0answers
18 views

### Unable to debug my code [on hold]

Problem is MARCHA1 of Codecehf . HERE is link :https://www.codechef.com/problems/MARCHA1 IN SHORT I'LL SUMMARISE THE QUESTION : we are given n number of notes of any denominaton and m is required ...
1answer
116 views

### Prove/disprove that the class of decidable (resp. partially decidable) languages is closed under symmetric difference

Prove/disprove that the class of decidable (resp. partially decidable) languages is closed under symmetric difference. A symmetric difference of sets A and B is the set (A \ B) ∪ (B \ A). I know that ...
0answers
20 views

### Disjoint Set Connected Components With Weighted Graph

I have been trying to solve this HackerRank problem (link). The basic premise of this problem is that there is a tree with undirected, but weighted, edges. The cost of a path in this tree is taken ...
2answers
444 views

### Reconstruct directed graph from list of ancestors for each node

I have a problem that I encountered that boils down to the following: Considered this directed graph I found on Google: I have the following information available to me ...
1answer
310 views

### How to read off the set represented by a van-Emde-Boas tree?

I'm reviewing my background in Algorithms and DS design. Specifically I never went through the van Emde Boas Tree. Though I can undestand the proto-vEB with related picture. I'm struggling to ...
1answer
70 views

### Lambda Calculus as a branch of set theory

This answer to a question about whether C is the mother of all languages contained an interesting tidbit that I am curious about: The functional paradigm, for example, was developed mathematically (...
1answer
53 views

### Variant of the “Stable Roommates Problem” when room has not 2 but “n” mates

I'm looking at the name of a variant of the Stable Roommates Problem, when the rooms have more than 2 mates, ie for example 6 to 8. Does this problem has a specific name? A well-known algorithm? To ...
0answers
21 views

### For a collection $S$ of weighted sets $S_i$, find those $k$ elements that maximise the sum of weights of all sets $S_i$ covered by them

I have a collection $S$ of sets $S_i$. Each $S_i$ has a weight given by how many times this set was observed in some data. I now want to find the $k$ elements that maximize the cumulative weight of ...
0answers
118 views

### What is the deterministic time complexity of obtaining the set of distinct elements?

Consider a sequence $s$ of $n$ integers (let's ignore the specifics of their representation and just suppose we can read, write and compare them in O(1) time with arbitrary positions). What's known ...
1answer
439 views

### What happens if the associativity level is greater than the cache size?

I am working on a computer organization caching problem The Problem: What happens if the associativity level is greater than the cache size? I know that associativity level is how many blocks are ...
1answer
75 views

### Finding longest subset arithmetic progression with given difference

Given a list of distinct positive integers, I am trying to find the largest subset that forms an arithmetic sequence with a given difference D. For example, given D = 5, with the set of numbers 1, 5, ...
1answer
61 views

### Fast hash function for set equality

I'm searching an hash function for integer set equality that must be fast. It must support update (adding an element already in the set must not change the hash) and union. MinHash has these 2 ...
1answer
95 views

### Suggest a Data Structure To Manage 2 Sets

I was given the following problem which really baffled me, and I would like some guidance in solving it. I want to make a data-structure which represents two sets $A,B\subseteq \mathbb{R}$, so that I ...
1answer
94 views

1answer
21 views

### Name for multiset with fractional amounts?

What do you call a set which accepts multiples of the same element, even in fractional amount? Is there even an established for this? Example from a video game about production chains: For a ...
1answer
80 views

### Is it possible to add every word in a file to a set in $\mathrm{O}(n)$ time?

The Problem: I am currently analyzing a simple program that takes a file of length $n$, splits it into its individual words (seperated by white space) and adds those words to a set: ...
1answer
68 views

### Distinct elements count of huge multiset

I know that HyperLogLog can approximate the distinct elements count of a huge multiset but I was wondering if it was possible, using a method I saw mentioned on an IRC channel, to get an exact answer ...
1answer
44 views

### Finding combinations of variables that can take value of -1/0/1 that produce sum of 0 with added constraint

I have 64 variables that can either take a value of -1, 0, or 1 and I am interested in finding all possible combinations of variables such that I have n variables in each the positive and negative ...
0answers
45 views

### The maximum number of uniquely intersected elements from the all possible intersection scenarios among the sets in a two-column matrix

Let us define a $n \times 2$ matrix M consisting of integer sets, such that the first column consists of the so-called intersecting sets, and the second column ...
2answers
94 views

### What does the intersection symbol (∩) mean when applied to two non-set elements?

I came across a piece of literature in which I saw the intersection symbol (∩) being used on two non-set elements in the definition of an equivalence relation; I have posted it below for reference. ...
1answer
54 views

### Basic Set Theory problem

So i'm relatively new to computer science and have been learning set theory and am stumped on a question in it. The question specifies that we're only looking at subsets of universe U = {0,...,n-1}. ...
1answer
41 views

### Find K-subset that includes the most W-subsets

I have a set $S$ of $N$ elements, and a set $\Sigma$ of $N$ subsets of $S$: $\sigma_0, \ldots, \sigma_{N - 1} \subset S$, each with $W \ll N$ elements. Subsets can overlap partially or totally. For ...
3answers
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 ...
1answer
153 views

### Count the number of subsets with product less than or equal to k [closed]

You are given an array $A$ of $n$ positive integers, you have to find the number of subsets the product of whose elements is less than or equal to a given integer $k$. Is there an efficient algorithm ...
1answer
56 views

### Algorithm / data structure to filter documents by number of missing words

Is there a data structure or an algorithm or a combination of both to allow me to filter a set of documents based on the number of missing words (compared to another list)? Problem Definition We ...
1answer
28 views

### Identifying the Equivalence Classes of a Language with equal number of 10 and 01 strings

I'm doing a problem where I need to find the equivalence classes of the language below: Let A = {x ∈ {0, 1}* | #(01, x) = #(10, x)}, where, for a, b ∈ {0, 1}*, #(ab, x) is the number of places in x ...
1answer
80 views

### Union of infinitely many regular languages [duplicate]

I need to prove or disprove the following statement. If $A_n ⊆ \Sigma^*$ is regular for each $n \in \mathbb{N}$ then $\bigcup\limits_{n=0}^{\infty} A_n$ is regular. I know that if two languages ...
1answer
89 views

### Proving the singleton language {x} is regular for all x ∈ Σ*

So I'm aware that the singleton language is in fact regular for all x ∈ Σ*, but I do not understand why it is. A formal proof would help, but also getting some intuition as to why it is regular would ...
2answers
96 views

### Proving that Every Full Prefix-Free Language is Maximal

I'm practicing a problem where I need to prove that every full prefix-free language is maximal. I know a prefix-free language A is maximal if it is not a proper subset of any prefix-free language, ...
1answer
30 views

### Proving existence results

I'm doing a problem where I need to prove that there is a language A ⊆ {0, 1}* with both of the following properties: (i) For all x ∈ A, |x| ≤ 5. (ii) Every DFA that decides A has more than 8 states....
4answers
83 views

### Proving B* = B on a given set

I have the set: B = {x ∈ {0,1}* | there is an equal number of 0's and 1's in x} and therefore, B* = {e,01,10,0011,0101,0110,1100,1010,1001,....etc} I need to either prove or disprove that B*=B I ...
1answer
31 views

### $A^* = B^*$ with $\{0,1\}$ contained in $A$ but not in $B$

I'm trying to exhibit two formal languages $A,B ⊆ \{0,1\}^*$ such that $A^* = B^*$ and $\{0,1\}$ is contained in $A$ but not in $B$. Finding a language for $A$ is very easy, but I get stuck on $B$, ...
1answer
65 views

### Proof of an Infinite Binary Sequence

I have a problem where given an infinite binary sequence S ∈ {0, 1}∞ to be "prefix-repetitive" if there are infinitely many strings w ∈ {0, 1}* such that ww is a prefix of S. I need to prove that if ...
1answer
35 views

### Proving $A^\ast = A$ on a given set

I am working on some set theory and am trying to prove how a set can have the property $A^* = A$. For set $A=\{0^n1^n \mid n \ge0\}$, I still do not understand exactly what $A^*$ is. For example, I ...
1answer
69 views

### Minimal set of subintervals that 'covers' any subinterval in K subintervals

I have a big interval $I = [a, b]$ of size n. I want an asymptotically minimal set of subintervals of $I$ (let's call it $S$) one can use to construct any subinterval of $I$, by concatenating at most ...
3answers
217 views

How to efficiently ¹⁾ choose from a set of numbers $S$, a given number $n$ of disjoint subsets, each with a given sum $K$ of chosen elements? ¹⁾ Not as in $P$, I just want something smarter than $O(n^... 0answers 43 views ### Find a partition of multiset of binomial coefficients with constriants Given the multiset$S$where the elements are defined by the binomial coefficient${n \choose k}$where$n \in \mathbb{N}$and$ 0\leq k \leq n$find the partition$P$of$S$such that the sum of ... 1answer 41 views ### Can You List the Names of Some Algorithms For Determining the Intersection of Two Context Free Grammars? Suppose we have two sets of strings XS and YS such that set XS is described by grammar GX and YS is described by grammar GY. We want an algorithm which accepts GX and Gy as inputs. The algorithm will ... 1answer 41 views ### Find four sets where each element from those four appears in at least two of those four sets I have a list of sorted arrays ("sets") of integers$A_1..A_n$where each element is unique w.r.t. the other elements in the same array:$A_i = \{x_{i,1}..x_{i,c_i}\}x_{i,p} < x_{i,p+1}A_i$... 2answers 64 views ### Given a set$A$of sets find a minimal set$B$of pair-wise disjoint sets such that each set in$A$can be expressed as a union of sets in$B$I recently thought of the following problem: Given a set$A$of sets find a minimal set$B$of pair-wise disjoint sets such that each set in$A$can be expressed as a union of sets in$B$. For ... 2answers 203 views ### set cover where only certain special subsets are allowed I am trying to solve a problem which turns out to be a form of the set cover problem. I've implemented the greedy Set cover approximation algorithm for set cover, but it turns out to not be accurate ... 1answer 28 views ### Is a set$B = \{y, \exists x \in A, f(x)=y\}$recursive if A is a recursive set and f is a$N->N$total computable function? Obviously, B would be recursive if for every TCF f, there was an inverse fuction that would return all possible values, as we could just take these and then check if any of them is in A. However I ... 1answer 546 views ### compressing a set of binary strings with fixed length I'm looking for a data structure / algorithm to store an unordered set S of binary strings of a fixed length n (i.e. all ... 1answer 73 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 ... 4answers 6k views ### Given a set of sets, find the smallest set(s) containing at least one element from each set 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 ... 1answer 48 views ### PL: What solves the type isomorphism$X \cong (X \rightarrow \mathbf{2})\$?

In Practical Foundations for Programming Languages, on page 138 (page 156 of the pdf), it says: Requiring solutions to all type equations may seem suspicious, because we know by Cantor’s Theorem ...