Questions tagged [sets]

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

Filter by
Sorted by
Tagged with
1
vote
2answers
247 views

Set notation of the set of all strings

How do I present the complement using set notation? I guess it has to be shows with universal set - {aa,bb} but I do not know how to represent the universal set in ...
1
vote
1answer
84 views

What is an efficient way to calculate the biggest system of disjunct sets?

Let $I$ be a finite set of items and $\mathcal{M} = \{M | M \subseteq I\}$ be a set of subsets of $I$. The task is to find the biggest subset $\tilde{\mathcal{M}} \subseteq \mathcal{M}$ so that all ...
1
vote
1answer
80 views

Many-one reducibility: why $A = \{1\}$ is not a counterexample to $\forall A : A \leq_m A \cup \{0\}$?

I'm looking at a textbook exercise that asks to prove or give a counterexample that $\forall A : A \leq_m A \cup \{0\}$. $A \leq_m B$ is defined as: $\exists f$ total, computable s.t. $\forall x \in ...
2
votes
0answers
35 views

physical significance of membership function greater than one

In fuzzy logic, when we associate an element with a set, we usually do it in terms of membership grade which suggests the "belonging" of this element to the set. Membership grade value 0 means that ...
2
votes
1answer
193 views

Minimum number of sets of unreachable vertices for directed acyclic graph (DAG)

I have a DAG with vertices $V$ and edges $E$. If $v,w \in V$ are vertices such that $v$ is not reachable from $w$ and $w$ is not reachable from $v$, I will say that $\langle v,w \rangle$ is an ...
2
votes
2answers
173 views

Efficient immutable data structure for small multi-sets of integer ranges?

Background I'm currently writing some Elixir algorithms that are quite computationally expensive. The most-used datastructure is a multi-set of (finite) integer ranges. Modifying this data structure ...
2
votes
1answer
73 views

Compact, reversible mapping from set partitions of length k to integers

Given a set $S$ of length $n$, I'm looking to map all the $k$-length partitions of $S$ onto the set of integers such that these integers are as close to 0 as possible. Ideally the range would be $\...
2
votes
1answer
67 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 ...
7
votes
2answers
626 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
88 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
63 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
367 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
58 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
53 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
478 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 ...
29
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
60 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
43 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- ...
2
votes
0answers
57 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
64 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
629 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
168 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
100 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
422 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
752 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 ...
1
vote
1answer
92 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-...
1
vote
1answer
338 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
109 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
635 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
768 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
1k 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?
5
votes
1answer
189 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
132 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: ...
3
votes
1answer
102 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
138 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
96 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 ...
11
votes
0answers
944 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
4k 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
793 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 ...
5
votes
2answers
510 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
106 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
303 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
102 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
111 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
71 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
151 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 ...
1
vote
1answer
535 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
374 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
104 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
158 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 ...