New answers tagged randomized-algorithms
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
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