# Tag Info

Accepted

### What exactly is the semantic difference between set and type?

To understand the difference between sets and types, ones has to go back to pre-mathematical ideas of "collection" and "construction", and see how sets and types mathematize these. ...
• 31k

### in O(n) time: Find greatest element in set where comparison is not transitive

The standard algorithm for finding a maximum still works. Start with $a_1$ and go over the elements, if you see a larger value, update the maximum to be that value. The reason this works is that every ...
• 13.4k
Accepted

• 16.7k

### How to find the maximal set of elements $S$ of an array such that every element in $S$ is greater than or equal to the cardinality of $S$?

There is nothing wrong with your algorithm, and of course most of recursive algorithms can be converted into loops, here a loop version of your recursive code: ...
Accepted

### The meaning of "set" in NP-complete problem

It doesn't matter. If a certain problem has one version in which the encoding of sets allows for repeated elements (which are ignored semantically), and another in which repeated elements are ...
• 278k
Accepted

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

I believe your problem is a direct instance of the NP-hard Maximum Coverage Problem, which is related to Set Cover. From wikipedia, Maximum Coverage Problem: As input you are given several sets ...
• 76
Accepted

### Find an algorithm that finds a minimal hitting set for sets limited in size

Here are two algorithms for the case $k=2$, also known as Vertex Cover; we think of the sets $S_i$ as edges and of the elements $\{1,\ldots,n\}$ as vertices. We can assume that each edge connects two ...
• 278k
Accepted

### Subset of numbers whose XOR has least Hamming weight

Your problem is known as calculating the minimal distance of a (binary) linear code, and is NP-hard, as shown by Vardi. It is even NP-hard to approximate within any constant factor, as shown by Dumer, ...
• 278k
Accepted

### Is the intersection of infinitely many recursive sets recursive?

Since you already know about unions, you could figure this out by remembering the de Morgan laws: the complement of a union is the complement of the intersection of complements. With this in mind: let ...
• 31k
Accepted

### PL: What solves the type isomorphism $X \cong (X \rightarrow \mathbf{2})$?

To say that we cannot solve $X \cong (X \to 2)$ in sets means that we have to do it in another category. And because we're talking programming languages, we should be looking for one in domain theory. ...
• 31k

### Smallest set of balls under hamming distance that covers all $n$-bit strings

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-...
• 278k

### Recover a set with the information of the sums of all its subsets

If you know the sums of all the two element subsets you can recover the elements unless $n$ is a power of $2$. See Jan Boman, Ethan D. Bolker, Patrick O'Neil, The Combinatorial Radon Transform modulo ...
• 167
Accepted

### What is the difference between the set containing the empty string and the set containing nothing at all?

Yes, that's it. One important difference could be seen using concatenation: let $L$ be any nonempty language. Then $\{\varepsilon\}L = L$, but $\emptyset L = \emptyset$. Clearly those are different.
• 15.9k

### Set notation of the set of all strings

The universe here is the set of all strings over the alphabet $\{a,b\}$ and is usually denoted by $\{a,b\}^*$. You have way too many brackets.
• 30.8k

### Equivalent expression in English: Set Notation $\{0,1\}^K$

In set theory $B^A$ denotes the set of functions from $A$ to $B$. Thus, an element $f\in B^A$ is a function $f:A\rightarrow B$. In your specific case $\{0,1\}^k$ is the set of functions from the ...
As an addition to Ariel's answer about the concerns raised by Emil Jeřábek: If we allow $A<B$ and $B<A$ then there is no O(n) algorithm: Assume you have elements $A_1 ... A_n$. Your algorithm ...
Category theory is in some sense a generalization of set theory: the category $C$ could be the category of sets, or it could be something else. So, you learn less if you learn that $x$ is an object ...