Hot answers tagged

8

The existential form of the axioms of set theory is convenient for the meta-theoretic explorations of set theory, such as forcing etc., where it is important to have a minimal language to worry about (only $\in$ relation). But even just stating the axioms of set theory without any constants and operation symbols is pretty haunting, see this gist of mine. If ...


6

The object you are looking for is known as a covering code. Finding the smallest covering code for a given radius is generally a difficult problem, just like its more well-known dual problem, error-correcting codes.


4

No. In computer science, a language is normally defined to be a subset of $\{0,1\}^*$. If $L$ is a language, then the powerset $2^L$ is not a subset of $\{0,1\}^*$, so it is not a language. (See e.g., https://en.wikipedia.org/wiki/Formal_language#Definition.) If $L$ is finite, then the powerset $2^L$ is finite, so as Emil Jeřábek points out, there is a ...


4

Observe that: $T(N) = 2T(N-1) + 2^{N-1}$ $T(1) = 2$ Note that the entire runtime, our algorithm only spends time generating more data. Therefore, our function T represents both the amount of time that the function spends running on an input of size N, and also the amount of data it generates from an input of size N. We have $2T(N-1)$ because we first make ...


3

Interesting question. The right intuition should probably be along the guideline that two random subsets of cardinality $n$ drawn from some $cn$ elements for some constant $c$ differ from each other significantly with a probability very close to 1 and, hence, the weight of the minimum spanning tree of the graph $G$ should be $\mathcal\Theta(n^2)$ on average. ...


2

I'll list two possible approaches that might be reasonably effective in practice, though their worst-case running time is no better than what you listed. Indices You can build up an index for each word. Build a hash table. For each word that appears in any clean name, the hashtable maps that word to a list of all dirty names that contain that word. This ...


2

Set are at a higher level of abstraction than algorithms. You can certainly analyze algorithms at that level of abstraction but that's not the usual level of abstraction for discussing algorithms, instead you'd refer to data structures such as stacks, vectors, lists, linked lists etc. Sets are instead used in formal modeling contexts (Z,Coq,Agda,F-Star) to ...


2

Since you talk about sets I assume that there are no duplicates. You can assume $n \le m$ otherwise you can answer "no" in time $O(1)$. You can further assume $\max_{a \in A} a \le \max_{b \in B} b$, otherwise the answer is again "no", and can be found in time $O(\min\{m, U\})$, where $U = \max_{a \in A} a$. Your problem can be solved in $O(\min\{m \log ...


2

Your problem is NP-hard. To see this, you can reduce it from the minimum test cover (or test collection) problem: given a set $X$ of $\ell$ elements and a collection $C = \{C_1, \dots, C_k \}$ of $k$ subsets of $X$, find a minimum test cover for $X$ and $C$, i.e., a subset $C'$ of $C$ that has minimum size and satisfies the following property: for every pair ...


2

You can compute the sumset (well, difference set) $X-Y$ using standard techniques (Computing Cardinality of Sumsets using Convolutions and FFT). As an optimization, I suggest first replacing $X,Y$ with $X'=X \bmod p$, $Y'=Y \bmod p$ where $p$ is at least $n+m$ or so. Then, enumerating through the elements of the multiset $X'-Y'$ by decreasing cardinality ...


2

The complexity of the distance function depends on the type of the iterators supplied: in general it only required to take linear time in the distance but, in the special case in which the input iterators are random access iterators, the worst-case running time is linear. (I believe this is accounting for the time spent in the function in itself, and assumes ...


2

I understood the problem as that we can select any $S_i$ satisfying these conditions. Then the answer is $\{0, 1, 2, 3, 4, 5\}$. The construction is unique in a certain sense. Wlog we can assume that $S=A$ (otherwise, just remove redundant elements from $S$). I'll use $A, B, C, D, E$ instead of $S_i$. One way to arrive at a solution is to draw a Venn diagram ...


2

There are many ways to perform this enumeration. Note first that you can count the number of cases in half by postulating that $Q = \{q_0,q_1\}$, that is, fixing which among the two states is initial; the choice doesn't matter due to symmetry. Now you are left with 16 possibilities. At this point there are many ways to cut the search space even further. Here ...


2

You can't. Consider the following sets for some $k$, with $m=k^2$ (they both are powers of $2$): $\{1..k\}$, $\{k+1..2k\}$, $\ldots$, $\{m-k+1..m\}$ $\{1, 3, 5, \ldots, 2k-1\}$, $\{2, 4, 6, \ldots, 2k\}$, $\{2k+1, 2k+3, \ldots, 4k - 1\}$, $\{2k+2, 2k+4, \ldots, 4k\}$, $\ldots$ $\{1, 5, 9, \ldots, 4k - 3\}$, $\{2, 6, 10, \ldots, 4k-2\}$ $\ldots$. Each ...


2

In 2D, a linear transformation has the form $v \mapsto Mv$ where $M$ is a $2\times 2$ matrix, so the transformation has four parameters. Thus, the transformation is uniquely determined if you have two points $p_1,p_2$ from the first set and two points $q_1,q_2$ and if you know that $p_1$ transforms to $q_1$ and $p_2$ to $q_2$. You can find this linear ...


1

I'm not sure how well it'll work, but the idea is simple: Consider a continuous relaxation of the function Run projected gradient descent 1.) First, consider a discrete case: let $x_i$ be $1$ if we pick an $i$-th element, and $0$ otherwise. The constraint is $\sum_i x_i \le k$. For each set $S_j$, we want to write a function which is $1$ when all $i \in ...


1

I can describe a solution that runs in linear time and is likely to give a solution that is close to optimal, if all of the sets $S_i$ are chosen uniformly at random, and only for the specific parameters you mentioned. The method is easy to describe; explaining why it is likely to be close to optimal is much hairier. Algorithm Pick two sets $S_{i_1},S_{i_2}...


1

This problem (at least assuming you wish to find some sort of maximal subset) is simply the multidimensional knapsack problem, see e.g. "The Multidimensional Knapsack Problem: Structure and Algorithms" by Jakob Puchinger, Günther Raidl, Ulrich Pferschy. To read that paper in your terminology, a quick translation. Your 'components' are known as ...


1

You haven't shown the full proof, but it most likely has the form "Assume that the set is countable. Consider any enumeration. Then (blah-blah-blah) shows that there is a number not in the enumeration. That's a contradiction, so our assumption must have been wrong." If that's the structure of the proof, then pointing out that the proof appears ...


1

An idea is to use a tree of set instead of a tree of indexes. One can develop it arbitrarily to a valid tree of indexes at end. An advantage is that you obtain all the valid trees with this process. Let's consider the set of sets $A$ as a list $A[i]$. The initial tree $G(V, E)$ of set contains only one vertex which is the first set $root = s_0$. And you keep ...


1

Set $A = B$ and $|U| = \Theta(\log |A|)$, and you run up against the Orthogonal Vectors Conjecture trying to do better than $|A|^{2-o(1)}$.


1

Your second idea seems to be close. Here is the actual algorithm (no random pivot is required): Find the $i{n\over k}$'th order statistic for every $1\le i\le k$. This will take $O(n)$ each time for $k$ values: $O(nk)$. For every such $i$, put all elements with values between the $i{n\over k}$'th and the $(i+1){n\over k}$'th order statistics in the $i$'th ...


1

Suppose the input is $a,b$, two $n$-digit long numbers. We allow leading zeroes (we will see in a moment why). Let $c$ be the longest common prefix of $a,b$, and let $a=cA$, $b=cB$. If $A = 0^{n-|c|}$ and $B = 9^{n-|c|}$ then we simply output $c$ (this includes the case $|c|=n$). Otherwise, let $d_A$ be the first digit of $A$, and let $d_B$ be the first ...


1

Preprocessing: For each $(k_i, v_i)$ pair, and for each $x \in k_i$, add $(x, (k_i, v_i))$ to a map data structure (e.g., a hashtable) with $x$ as the key. To process a query $q$, for each $y \in q$ look up all values in the map, append all of them to a list, and finally remove duplicates (or instead add them directly to a data structure that can collapse ...


1

Note the following line of code: powerSet.add(new ArrayList<>(SelectedSoFar); Whenever we create a subset, we add the subset (list) to a list of list : power set. The size of subset will be $n$ (actually it will vary from $1$ to $n$, but we can take it to be $n$). Even though adding a list requires one line of code, but it will involve copying all ...


1

Let $k = 11$ in your problem, so we want to generate all sets with values in the range $0$ to $k$ and with between $1$ and $12$ elements. Then you can do the following: First generate all sets for $k-1$ (recursively) Then, for each set, make two copies, one with a $k$ on the end and one without a $k$ on the end. If you prefer doing it iteratively, here is ...


1

If all of $D$ divide $P$, then $P$ is also multiple of $\gcd(D)$. Any sum like $S$ is a multiple of $\gcd(D)$ too, so you can divide everything by $\gcd(D)$ and consider just the case where the $D_i$ are relatively prime. For definiteness, take $D$ sorted in increasing order. In that case you have just: $\begin{equation*} P = c \cdot \prod_{1 \le k \...


1

The proof is by induction. The base case $t = k$ is clear. Suppose that the claim is true at some time $t$. We will prove it for time $t+1$. Let the first $t+1$ elements be $x_1,\ldots,x_{t+1}$. By the induction hypothesis, at time $t$ each of the $\binom{t}{k}$ possible $k$-subsets of $x_1,\ldots,x_t$ is found in the array with equal probability. The ...


Only top voted, non community-wiki answers of a minimum length are eligible