The tag has no wiki summary.

learn more… | top users | synonyms

3
votes
1answer
98 views

Data structure for a static set of sets

I have collection $U$ of sets, where each set is of size at most 95 (corresponding to each printable ASCII character). For example, $\{h,r,l,a\}$ is one set, and $U = \{\{h,r,l,a\}, \{l,e,d\}, ...
0
votes
1answer
44 views

If $A \cap B$ or $A \cup B$ or $A \times B$ is recursively enumerable is it true to say that both $A$ and $B$ are recursively enumerable?

Sets $A$ and $B$ are given but we don't know what kind of sets they are. If we know that $A \cap B$ is recursively enumerable is it true to say that both $A$ and $B$ are recursively enumerable? what ...
0
votes
1answer
47 views

Set Intersection with asymmetric set sizes

I'm looking for an algorithm to perform set intersection where set $N_1$ is very small and set $N_2$ is very large. Due to the constraints of the problem I am solving, I cannot rely on an algorithm ...
0
votes
1answer
33 views

Language intersections (set theory) - Understanding better

I've joined computer science classes at high school because I have a wide knowledge and a few years of experience in programming in multiple of languages, however I didn't fit in the requirements of ...
3
votes
1answer
25 views

Finding set of disjoint sets with additional value optimization

I've got a set $Q$ of pairs $[S, v]$ where $S$ is a nonempty set and $v$ is a value ($v \in \mathbb{N}_{+}$). I need to find a subset $R$ of $Q$ with following properties: Sum of all $v$'s is ...
1
vote
0answers
40 views

Show that every infinite recursive set has both a nonrecursive r.e. subset and a non-r.e. subset

My attempt to solve this: If $\mathcal{A}$ is an arbitrary infinite recursive set then the members of $\mathcal{A}$ can be ordered in ascending order. We can do bijection between $\mathcal{N}$ and ...
1
vote
0answers
17 views

How to find the accuracy of a set partitioning?

Suppose that there are $k$ sets $S_1, S_2, S_3, \dots, S_k$. The numbers $N = \{1, 2, \dots,n\}$ are distributed into these sets equally. Say that we partition $N$ into $m$ sets $P_1, P_2, \dots, ...
2
votes
1answer
39 views

Count-Min sketch: dyadic ranges

Can anyone give me a proof as to why Any range over a unviverse {1...n} can be reduced to at most $2log_2n$ disjoint dyadic ranges? Where a dyadic range is a range of the form ...
1
vote
0answers
41 views

Tradoff between space and false positive rate when using bloom filters

Bloom Filters have false positive rate of $\epsilon = 2^{-k}$ with a data structure of size $m = n\log (\frac{1}{\epsilon})\ln 2$. Suppose you fix the number of hash functions at $k \le 3$. What is ...
0
votes
2answers
50 views

find the optimal combination [closed]

Suppose I have these values with weights -- $$ x_1 = 2\\ x_2 = 4\\ x_3 = 5\\ $$ There is no negative or $0$ value. I need to find $2$ element subset with maximum value computed from a function ...
2
votes
1answer
21 views

How to apply “verification” and “decision” for the SUBSET SUM problem?

The SUBSET SUM problem states that: Given finite set S of integers, is there a subset whose sum is exactly t? Can someone show me why verification is simpler ...
1
vote
1answer
101 views

Minimize sum of squared error

I have an array of real numbers, I want to partition them into k sets. In each set, I calculate the sum of squared error. Then, I add up all the sum of squared error for all the set. I want to ...
3
votes
1answer
73 views

Count all possible unions in a collection of sets

Say we have a collections of sets $\mathcal X = \{X_1, \dots, X_n\}$ (not necessarily disjoint), and we want to count the number of possible unions of sets in $\mathcal X$, i.e. the size of ...
3
votes
1answer
84 views

Does any one know what this problem is called?

We are given finite sets $A$ and $B$ and a set $S\subseteq \mathcal{P}(A)$. The members of $\mathcal{S}$ may have arbitrary intersections with one another and their union is not necessarily $A$. ...
2
votes
0answers
120 views

Message protocol to probabilistically infer missing object from Union of two subsets of a larger set

This was a challenge problem I read some time ago and just remembered it: Say you have two people, $A$ and $B$, collect objects distinctly labeled $1,...,n$. They will each separately collect ...
0
votes
0answers
22 views

Partial recursive characteristic function for finite sets

In class we were told that, for every finite subset $X$ of the natural numbers, it is possible to find a partial recursive function $g(x)$ that outputs $1$ if $x\in X$ and $0$ if ...
1
vote
1answer
28 views

Find a collection of sets where each number from a given list is contained in a different set

I have a set of numbers S of cardinality N, and a collection of sets each containing some subset of S. The cardinality of each of these sets can be anywhere from 1 to N. The number of sets is ...
2
votes
1answer
178 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 ...
3
votes
1answer
44 views

How can finite sets be represented as a type?

Manually self-migrated from stack overflow. A set of objects of a type T is often represented using its indicator function (set T = ...
1
vote
1answer
26 views

Online and parallizeable set intersection algorithm

I have problem that is reducible to the following: From a collection of stacks, find all items whose "keys" are on all stacks. My current solution to this problem is to just pop things off as ...
1
vote
0answers
20 views

Given a set of sets and a storage area, find an order that minimizes the sum of the differences between each set and the storage area

This problem is based on an order picking problem with a forward area. The problem description is as follows. We have a warehouse with a set of items $I$ and a forward area $F$ of size $k$. Each ...
0
votes
1answer
38 views

Find strings in L^4

Let L = {ab,aa,baa}. I need to find L^4. From my understanding, I union the set. So: ...
2
votes
1answer
32 views

Typical set in Shannon's source coding theorem

I was following the textbook by David Mackay: Information theory inference and learning algorithms. I have question on asymptotic equiparition' principle: For an ensemble of $N$ $i.i.d$ random ...
4
votes
1answer
41 views

Communication complexity of comparing sets, for Bitcoin

In Bitcoin, when one node wants to tell another node about a block, it sends the block header, then all the transactions it contains. This is inefficient, because the receiving node might already have ...
1
vote
2answers
117 views

What is the term for this set

I have a set of related data/objects for which, when undergoing some algorithm, there should be only one valid match. Is there a unique term for this type of set? A common practical use case would be ...
3
votes
2answers
403 views

Returning a random subset with length k of N strings while only storing at most k of them

Here's the problem. I've written a program that reads strings from stdin, and returns a random subset of those strings. The only other argument provided to the program is the length of the subset, ...
1
vote
1answer
27 views

Is a set system an independence system, if and only if it is an accessible system, and has the Interval Property without Lower Bounds

From Wikipedia, a finite matroid $M$ is defined to be $(E,F)$, where $E$ is a finite set and $F$ is a family of subsets of $E$, so that it satisfies either nonempty, the hereditary property, and ...
4
votes
2answers
83 views

Existence of Efficient Set Difference Algorithm

As a foreword, I'm not asking what the algorithm is, just whether one can possibly exist (though, if it does already exist and someone knows what it is, that'd be great). Basically, given two sets ...
3
votes
1answer
76 views

Lower-bounding the Membership Problem in the Bitprobe Model

I am working through the following paper "Data Structures for Storing Small Sets in the Bitprobe Model" by Radhakrishnan et al. and am confused regarding one of their arguments about a lower bound. ...
2
votes
1answer
42 views

Find $k$ subsets containing a particular element quickly

Suppose there are $n$ subsets of $U$. I want to quickly (in terms of average-case) find k $ (< n)$ subsets that contain $e \in U$ (call this Extraction(e)). Elements are integers. To that effect, ...
1
vote
1answer
26 views

Set that keeps unique categories of objects

I would like to know if this type of special set operator exists, and if yes what is it called and if it has any other special properties. Lets say I have this set $S$ of items. Like all sets, if ...
2
votes
1answer
57 views

Maximizing the Sum of a Subset with Excluding pairs

I have a set of nodes S where all the nodes of an arbitrary integer value. I Also have a set of pairs of nodes from S, indicating that those node cannot be in the same subset. Given a subset of S, ...
4
votes
1answer
87 views

What does $\{$ a set $\}^{+}$ mean in the context of languages?

I came across this notation and I don't know the meaning of it, or if it's a typo: $\{$ some set $\}^{+}$ What does the + mean, i.e., the plus operator applied to a set?
2
votes
3answers
225 views

What is the point of (Compactness theorem in the) Overspill principle?

The principle (called a Löwenheim–Skolem theorem by Huth and Ryan) states Let $\phi$ be a sentence of predicate logic such that for any natural number $n \geq 1$, there is a model of $\phi$ with ...
0
votes
3answers
58 views

How do I mathematically express a set generated using two loop variables within a single for loop?

I don't know the proper mathematical expression for for-loops, especially those that carry two distinctly behaving variables with each iteration. For example, assuming ...
4
votes
3answers
90 views

How to enumerate a product set?

I am coding a procedure that takes an integer $d$, and generates $d$ finite lists $X_1 \ldots, X_d$ of elements. I would then like for it to output a list of the elements in the product set $X_1 ...
2
votes
2answers
75 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 ...
1
vote
1answer
22 views

What is the name two mutually idempotent functions?

To clarify, in haskell, there is an ord function that gives the byte integer of a character (i.e. ord 'a' yields ...
3
votes
1answer
166 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$ ...
2
votes
1answer
31 views

Total ordering of sets of fixed size

I'm curious if there is a name for this way of ordering finite sets of natural numbers (shown here for the case 3 elements, but can be extended to any number of them): ...
6
votes
2answers
212 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 ...
3
votes
1answer
133 views

Most common subset of size $k$

I'm trying to write an algorithm that detects the most common subset of at least size $k$, from a collection of sets. If there are ties for the most common subset, I want the one of them whose size ...
1
vote
1answer
95 views

Number of K-sets [closed]

I am having a plane in N dimension. Th distance between 2 points (a1,a2,...,aN) and (b1,b2,...,bN) is max{|a1-b1|, |a2-b2|, ..., |aN-bN|}. I need to to know how many K-sets exist(here K-set refers to ...
2
votes
1answer
59 views

Set packing variant

There are n collections of M sets. Pick a single set from each collection, such that all n picked sets are pairwise disjoint. This problem can be converted to the ...
4
votes
2answers
430 views

Equivalence of independent set and set packing

According to Wikipedia, the Independent Set problem is a special case of the Set Packing problem. But, it seems to me that these problems are equivalent. The Independent Set search problem is: given ...
-1
votes
1answer
153 views

Finding number of maximum independent sets in tree, using dynamic programming

I'm quite stuck trying to answer this. The problem of finding the size of the maximum independent set in a tree using dynamic programming is well documented and many solutions are around. I've been ...
3
votes
1answer
242 views

Is the set-partition problem polynomial time reducible to the subset-sum problem?

There are many solutions on the web showing that the subset-sum problem is polynomial time reducible to the set-partition problem. However, during my search, I came across the following powerpoint ...
3
votes
1answer
99 views

Is the image of a function the codomain of a function?

Here is a definition from the functions section in my discrete math textbook (Discrete Mathematics and its Applications 7e, Rosen 2012): Let $f$ be a function from $A$ to $B$, and let $S$ be a ...
7
votes
4answers
599 views

Computing set difference between two large sets

I have two large sets of integers $A$ and $B$. Each set has about a million entries, and each entry is a positive integer that is at most 10 digits long. What is the best algorithm to compute ...
-1
votes
1answer
865 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. ...