New answers tagged ds.data-structures
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}}(...
- 800
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:
...
- 31
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