New answers tagged

1

The flaw in your approach is that you assume that the second level contains only $2$ and $3$. The following examples is min heap with $3$ not in the second level. 1 / \ 2 5 / \ / \ 3 4 6 7 The solution is available here. Solution: The root of the tree has to be the minimum element, therefore $1$ is at the root. Now we need to find ...


3

You are describing the Resolution refutation system, which is complete in the sense that if a CNF is unsatisfiable, then it can be proven using Resolution. Resolution is also implicitly used in most SAT solvers. The width of a Resolution refutation is the maximal number of literals in a clause encountered during the refutation. There are 3CNFs on $n$ ...


2

To generalize your approach to $k$-subsets of an $n$-set, you would need to build a hypergraph. Ordinary graph edges are relations between pairs of vertices. Hypergraphs allow relations between arbitrary sets of vertices. They are extremely general objects, essentially representing families of sets. This question provides two good answers for how to (...


1

You seem interested in just pairs of indices. Then, if you have $n$ elements you can just generate all pairs of indices $(i,j)$ with $0 \le i < j < n$. For i=0,1,...,n-2: For j=i+1, i+2, ..., n-1: Output (i,j)


0

To formally prove my algorithm works, I think it is sufficient to show these three things. I haven't managed to prove all of them, but still leaving this as an incomplete answer and hope to fill in the gaps over time. Would appreciate if people can help fill the blanks of course. In any path created from a valid BST using the algorithm in my question, there ...


3

My answer is not a formal proof, but I hope it contains enough information to make you feel confident about your own solution. My strings start at $1$. Sorry, old habit. Consider a binary tree $T$ with $n$ nodes. Assume $T$ has $n$ nodes, subtrees $T_\ell$ and $T_r$. If the root of $T$ has label $k$ this means that $T_\ell$ has $k-1$ nodes. A tree with $n$ ...


2

The operation of translating between combinatorial objects and their indices in some enumeration is known as ranking/unranking (ranking is to convert an object to a number, unranking is the opposite). In your case, you are interesting in ranking/unranking subsets. Suppose that you are given a subset $S$ of $\{1,\ldots,n\}$ of size $k$, and want to convert it ...


Top 50 recent answers are included