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

You are confusing countable and finite. A finite set is always countable, however a countable set can be infinite. You only need to find an injection from your set and $\mathbb{N}$, it means that you can identify each element of your set using a natural number (a code if you prefer). For instance you can code the set of functions from $\{a,b\}$ to $\mathbb{...


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 ...


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. ...


3

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 ...


2

It is NP-hard. Here is a reduction from a variant of vertex cover: Given a graph $G$ with $n$ vertices and a positive integer $k$ where $n+k$ is even, determine whether there is a vertex cover with size $k$. This variant is also NP-complete. Given an instance graph $G$ with $n$ vertices $v_1,\ldots,v_n$ and $m$ edges $e_1,\ldots,e_m$, as well as an integer ...


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

Saad Balbiyad's answer is correct. This answer spells out some of the ideas in more detail. A set is countably infinite if its elements can be paired up with natural numbers so that (a) no elements are paired up with the same number, (b) no element is paired with two numbers, (c) there are no numbers or elements left unpaired. In other words, a set is ...


2

I believe a hashing approach should give you $O(N)$ time, where $N$ is the length of the longer array (we can relax the constraint that they are the same size). Simply put all the elements in the first array into a hashset, and then check whether each element in the second array exists in the hashset. You could even account for duplicates by instead using ...


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

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 ...


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

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 ...


1

You can solve this problem with the inclusion exclusion principle. Assume you have two subsets $S_1, S_2$, then the number of ways to choose two elements is the number of ways to choose a number from $S_1$ multiplied by the number of ways of choosing an element from $S_2$ minus the number of ways of choosing the same number from $S_1$ and $S_2$. Now given ...


1

This problem is NP-hard. It is called "the minimum-k-union problem". Given a universe $U$ and a family of sets $\mathcal{F}$ over this universe. Are there $k$ distinct sets in $F$ such that the union of all these sets has size at most $d$. Your presentation is the matrix formulation of this problem where each column corresponds to an element in the universe ...


1

Your problem is known as Maximum coverage. The greedy algorithm (repeatedly take a set which covers the maximum number of uncovered elements) is a $1-1/e$ approximation, and runs quite efficiently.


1

If the language is infinite, the word $\# w_1 \# w_2 \ldots$ would be infinite, and so doesn't map to an integer in any meaningful way. Applying the diagonal argument on the set of all finite languages might (indeed, will) result in an infinite language.


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