New answers tagged

1 vote
Accepted

Construction of a collection of subsets of $\{1,2,\ldots,n\}$ with certain properties

Here's an elaboration on my comment, assuming I didn't get lost in all the notation above: For $\mathfrak{S}=\mathcal{P}([n])$, the power set of $[n]$, it holds that \begin{equation*} f_{\mathfrak{S}}(...
3 votes

Is there a purely functional vector with O(1) access to the front and back but O(log n) concatenation?

You can achieve the exact characteristics you're looking for with Finger Trees. The most basic finger tree is defined in terms of 2-3 tree nodes: ...
1 vote

Worst-case complexity of computing a certain non-standard dot product + algorithms realizing this complexity

Disclaimer. This is just to provide some details for Yuri's nice response to Q3, and generalize it to arbitrary group sizes. Let $n=p_1 + \ldots + p_k$ be a partition of $n$ in to $k \ge 1$ positive ...
  • 291
4 votes
Accepted

Worst-case complexity of computing a certain non-standard dot product + algorithms realizing this complexity

Let $z$ be the coordinate-wise product of $x$ and $y$; that is, $z_i = x_i y_i$ for all $i$. Then we need to compute $\sum_{S\in {\cal S}} z_S$. Q1: We can solve the problem using dynamic programming. ...
  • 3,899

Top 50 recent answers are included