# Tag Info

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

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