People who code: we want your input. Take the Survey

# Tag Info

2

Let $P$ denote the number of pairs of indices $i<j$ such that $f(i)=1$ and $f(j)=0$, and let $C$ be the minimal number of flips required to make $f$ monotone. First, we show by induction on $n$ that for every function $f$ defined on $[n]$ it holds that $C^2\le 3P$. Suppose that the claim holds for $n$ and let $f$ be a function defined on $[n+1]$. We ...

1

A comparator circuit is a circuit computing a function on $x_1,\ldots,x_n \in \{0,1\}^n$. The inputs to the circuit are labeled with either constants ($0$ or $1$), inputs ($x_1,\ldots,x_n$) or negated inputs ($\lnot x_1,\ldots,\lnot x_n$). The only allowed gate is a comparator gate, which has two inputs $a,b$ and two outputs $a\land b,a\lor b$. The circuit ...

1

I am not sure counting sort would work, since it does not depend on the base, but on the range of the sorted values. In this case, you would need to create an array of size $(n-1)\sqrt{n}$ to count, so you would be in $\Omega(n^{3/2})$. As suggested in the comment, radix sort may do the trick here. It is not possible to sort in $O(n)$ for one of the other ...

1

Since this problem is basically about merging the element not in $B$ with element in $B$ to minimize order inversions, this answer will be focused on the following problem. The algorithm and analysis hereof can be extended to the problem in the question easily. $A$ is a sorted array of $n$ integers. $B$ is an array of $m$ integers. $n\gt0, m\gt0$. How can ...

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