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

learn more… | top users | synonyms

2
votes
1answer
41 views

The meaning of “set” in NP-complete problem

Garey and Johnson describe in their book many NP-complete problems which are based on sets, for example Hitting Set, Minimum Test Set, Set Packing, Set Splitting, and many more. The traditional ...
0
votes
0answers
22 views

Split k sets to 2 groups of sets ,is this np hard? [duplicate]

Given k sets ,each contain several elements . I want to split them to two groups , the first group contains m sets ,the second group contain n sets , m + n = k . Let w1 be the sum of the weights of ...
7
votes
2answers
590 views

Finding a fixed-size set whose members are contained by the largest number of other sets

I've been thinking about a problem, inspired by meeting a beginner-level foreign language professor at the Goethe-Institut who learned the five most common languages spoken by students in order to ...
2
votes
1answer
67 views

What kinds of problems are modeled by a recursive definition of a set of strings?

Given this definition: The set $\Sigma^*$ of strings over the alphabet $\Sigma$ is defined recursively by: BASIS STEP: $\lambda \in \Sigma^*$ (where $\lambda$ is the empty string) RECURSIVE ...
-1
votes
1answer
36 views

A max-even subset problem

I want to know if there is any polynomial algorithm for the problem, or any NP-completeness result. Given a set $S$ and $m$ subsets $C_1, \dots, C_m$ of $S$, we want to find a non-empty set $X\...
4
votes
3answers
146 views

My algorithm is different from CLRS' — is it wrong?

Exercise 2.3-7 from "Introduction to Algorithms" by Cormen et al. Third Edition, states: Describe a O(n lg n)-time algorithm that, given a set S of n integers and another integer x, determines ...
1
vote
0answers
41 views

Create the shortest list that contains a set of subsets in block

I have a problem where I have a set of subsets and I want to create the shortest list where I can find all subsets in it. Each subset must be a block of that list. The input is a set of set of ...
0
votes
1answer
33 views

Finding top k which are the most different from each other

Assume I have a set of items $A$ and each item $a \in A$ has a score $s(a)$. Also, each two items $a_1,a_2 \in A$ have variety score $var(a_1,a_2)$ which tells how different they are. I want to ...
1
vote
1answer
45 views

Letter Combinations of a Phone Number

I came across this problem in the “Elements of Programming Interviews” interview preparation book, and also on the site, leetcode.com (link to problem). Problem statement – Letter Combinations of a ...
25
votes
5answers
5k views

Boolean search explained

My mother is taking some online course in order to be a librarian of sorts, in this course they cover boolean searches, so they can search databases efficiently, however, she got a question sounding ...
2
votes
2answers
33 views

How to prove that $n$ sets have maximum of $2^n-1$ disjoint subsets when you have operations $\cup , \cap , \setminus$?

I just found out that you can have $2^{2^n-1}$ different subsets, made from $n$ sets, using operations $\cup , \cap , \setminus$. That is because when $n=2$, for example, you have 3 disjoint subsets: ...
0
votes
1answer
32 views

Express semantic duplicates of records formally

I'm working on a paper about record linkage and duplicate detection and want to visualize my definitions of "hard" and "semantic" duplicates. Hard ones are a 100% match; where's only true or false- ...
3
votes
0answers
32 views

Ordered set transformation data structure

Assume an ordered set $M = \{\tau_1, \tau_2, ..., \tau_n\}$ and a subset $S = \{\tau_k,\tau_l,...,\tau_m\}\subset M$ where $1\leq k,l,m \leq n$. All the items of $S$ are randomly ordered. The task is ...
0
votes
2answers
47 views

Generating general term of union of two countably infinite sets

I have two sets whose general terms are given as: $$ \begin{align*} A &= \{2⋅n \mid n ∊ ℤ\} \\ B &= \{2⋅n + 1 \mid n ∊ ℤ\} \end{align*} $$ I want to find the union of these two sets and return ...
2
votes
0answers
189 views

Efficient algorithm to approximate membership in a set of strings

I devised an algorithm / data structure and I would like to ask whether it already exists. The problem statement is: after having added some number of strings to the set, determine whether a given ...
0
votes
1answer
34 views

Total number of calls during insertion into binary tree

The problem: Find a formula for the total number of calls occurring during the insertion of n elements into an initially empty set. Assume that the insertion process fills up the binary search tree ...
1
vote
2answers
48 views

Is there a deterministic algorithm to construct $(n,k)$-universal set of minimum size?

Let $S\subseteq \{0,1\}^n$, $S$ is a $(n,k)$-universal set if for every subset of indices $I$ of size $k$, projecting $S$ to $I$ yield the $2^k$ binary strings (all the possible strings of $I$). $S$ ...
0
votes
2answers
122 views

Countability of a binary tree

Problem: We'll define a binary tree as a tree where the degree of every internal node is exactly 3. Show that the set of all binary trees is countable. My attempt: A set is countable if it is ...
0
votes
3answers
39 views

Computing the intersection of N sets over an M-element universe

Suppose I have $N$ sets $S_1,\dots,S_N$ each with elements from set $\{1,\dots,M\}$. 1.) What is a good algorithm to find $S_1\cap\dots\cap S_N$? 2.) I am also looking for a good parallel and a good ...
0
votes
1answer
27 views

Datalog - Single Step Operator

I am currently taking a class called Logic for Computer Scientist. During the first four weeks or so now we have been studying a concept Datalog with subsections Syntax and Formal Semantics and Fixed-...
0
votes
1answer
47 views

Partitioning a set to the maximum number of subsets summing to zero

Given a multiset of numbers $X = \{x_1, \dots, x_n\}$, such that $\sum X = 0$, how can $X$ be partitioned to the maximum number of subsets so that each subset sums to zero? I have searched around a ...
1
vote
1answer
75 views

Logic formula for exactly n unique objects (no more, no less)

I have a question in Logic: If I am asked to construct a formula, using the '=' predicate, that shows that there are exactly n objects, I need to show that there are no n+1 objects, right? For ...
3
votes
1answer
36 views

Why use minhash instead of directly computing Jaccard coefficient?

Minhash is said to estimate the Jaccard coefficient - supposedly because it's faster to compute. Given two sets $A$ and $B$, minhash (with k hash functions) takes $O(k*(|A|+|B|))$ time to compute. ...
4
votes
3answers
140 views

Data structure to store sphere points (latitude,longitude) and retrieve all points within a distance

I have a set of thousands~millions of points on a sphere's surface, each with latitude, longitude. I want to quickly get all points within a distance d of a ...
1
vote
2answers
237 views

Number of finite strings over a countably infinite alphabet

If the alphabet is countably infinite, then is the number of finite-length strings over this alphabet countably or uncountably infinite?
6
votes
1answer
99 views

How to find a minimum set of axioms within a set of propositions?

I have a set of propositions, for example $\{a_1,a_2,\dots,a_n\}$. Some propositions depend on others (for example, $a_1,a_2\Rightarrow a_3$, means if $a_1,a_2$ are true, then $a_3$ is true). I want ...
3
votes
2answers
26 views

How do set partitions get mapped by restricted growth functions

I am reading Skiena but do not have a formal background in Computer Science. On page 457 he discusses generating set partitions via restricted growth functions. Here's specifically what he says: ...
2
votes
1answer
69 views

Find a regular language that is “infinitely between” two other regular languages

Suppose I have two regular languages $L_{1}$ and $L_{2}$ such that $L_{1} \subseteq L_{2}$ and $L_{2} - L_{1}$ is infinite. I want to find another regular language $L_{3}$ such that $L_{1} \subseteq ...
0
votes
0answers
38 views

Vertex-independent paths [duplicate]

Let $s$ and $t$ be 2 vertices (not adjacent) in graph $G$. Let $p_l(s,t;G)$ be the $maximum$ number of vertex-independent paths from $s$ to $t$ in graph $G$, of length $\le$ $l$ ($l \in \{1,...,|G|\}$...
-2
votes
1answer
36 views

Regular language subsets [duplicate]

If $L_{1} \subseteq L_{2}$ and $ L_{2}$ is regular, does it follow that $L_{1}$ is necessarily regular? I don't understand this question, is there any proof to show this or is there an assumption we ...
6
votes
0answers
317 views

Alternative to Bloom filter for extreme parameters

A Bloom filter is a space-efficient probabilistic data structure to perform membership-tests on a set (see Wikipedia's page for a definition; I use the same notations below). I am interested in a ...
2
votes
5answers
98 views

How to prove a set has infinite cardinality?

Set S is a set consisting of all string of one or more a or b such as "a, b, ab, ba, abb, bba..." and how to prove set S is a infinity set. I have tried proving set S as one to one corresponding to ...
1
vote
1answer
115 views

Algorithm for generating coprime number sequences?

Does anyone know of an algorithm to generate a set of numbers of size $N$ which are all co-prime to eachother? Ideally I'm looking for something that has random access abilities so i could ask for ...
4
votes
2answers
225 views

Efficiently finding $k$ smallest elements of Cartesian product

Given lists $A_1, A_2, \dots, A_n$ of non-negative numbers, I want to find the $k$ smallest elements of the Cartesian product $A_1 \times A_2 \times \dots \times A_n$ ordered by the value $x_1 + x_2 + ...
3
votes
3answers
95 views

Algorithm that finds concise representations of sets of pairs using Cartesian products

I feel like there should be a known algorithm to the following problem, but I am short of ideas how to construct or search for it. Suppose as an input you have a list of two-dimensional data points (...
3
votes
1answer
66 views

Data structure for optimal deduplication of common subsets

Consider a database with the following properties: It stores symbols (represented as 64-bit integers) and sets of symbols Sets may contain thousands of symbols, and there may be thousands of sets ...
2
votes
1answer
87 views

How can a set offer better search performance than an array

While reading the following tutorial on iOS development Working with Foundation (section on Sets near the bottom), I came across the following statement: "Because sets don’t maintain order, they offer ...
3
votes
1answer
84 views

Data structure for ordered counted set

Is there a name for a counted set (multiset) that is ordered? For example lets say this data structure represents a shopping cart (or basket if you're British). The shopping cart shows the order the ...
0
votes
1answer
55 views

Understanding the definition of endless sets

In a course on theoretical computer science we have to prove if sets are endless. I have two problems with the exercise: I don't understand exactly, what an endless set is (I find it very hard to ...
-1
votes
1answer
41 views

$k$-Multiset intersection efficient algorithm

Given a collection of sets $C= \{S_1,S_2,\cdots,S_n\}$ such that each set $S_i \in C$ is sorted and has at least $k$ elements. What is the most efficient algorithm for finding the intersection of ...
0
votes
0answers
161 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 ...
0
votes
2answers
81 views

set complement and superset

If 'S is a set complement of S, then a set complement of a superset of S' is a subset of S. Just want to verify that above is true just based on the definition of ...
1
vote
1answer
51 views

Is the union of finite and infinite sequences over alphabet of length 1 countable?

Is the union of finite and countably infinite sequence over alphabet $\Sigma=\{1\}$, countably infinite as well? I understand this is similar a question to the one of finite and countably infinite ...
4
votes
2answers
139 views

Given an amount of sets with numbers, find a set of numbers not including any of the given

Given an amount of sets with numbers (0-20 e.g) , we are asked to find the maximum set of numbers from 0-20 that doesn't include any of the given sets(it can include numbers from a set,but not the ...
0
votes
1answer
50 views

How can I formalize key value stores with set theory?

I'm currently developing a simple key-value NoSQL store and want to build its formal model. I found article about key value formalisation with category theory, but I'm interested are there some works ...
2
votes
2answers
155 views

Does “contains only” imply “contains”?

Written in English, does "the set S contains only members of set T" imply that S does contain some member of set T? How would this relationship be written formally?
1
vote
1answer
69 views

Minimal Number of Fixed Size Sets to contain all Sets

My problem is very similar to the one posted here. Instead of finding one set covering the maximum of subsets, I need to find the minimal number of sets to cover all subsets. I have $U = \{1, 2, ..., ...
5
votes
2answers
297 views

Application of set theory subjects as ordinals, forcing, generic filters in software engineering

I am going to teach a course in set theory for software engineering students. I am going to talk in this course about: ordinal numbers, partial orders, well ordering, generic filters and maybe some ...
3
votes
1answer
263 views

What is the name of the property where $f(A) \supseteq f(B)$ when $A\supseteq B$?

Suppose I have a function $f$ on sets. What is the property of $f$ called when, for all sets $x$, $y$: $f(x)$ is a superset of $f(y)$ when $x$ is a superset of $y$ i.e. $$\forall x,y : x\...
1
vote
1answer
63 views

What is the complement of ACFG

What is the complement of $\mathrm{ACFG} = \{ G \mid G \text{ is a CFG and }L(G) = \Sigma^* \}$? I think it is $\mathrm{ECFG} = \{ G \mid G\text{ is a CFG and }L(G) = \emptyset \}$. It makes sense ...