Mathematics Asked on January 1, 2022
A recursive algorithm that I’m working on is based on traversing an $n$-dimensional hypercube. The quantity associated to each vertex can be computed by combining the values of all the adjacent vertices of lower weight (weight = number of 1s in the coordinate vector). The goal is to reach the vertex of highest weight (11…1) starting from the vertex of lowest weight (00…0).
In order to optimize the algorithm, I want to minimize space and time requirements. Time is the number of steps to reach the final vertex, and space is the largest number of values that need to be kept in memory at any moment.
Version 1: Compute all the $binom{n}{k}$ vertices of weight $k$, drop the vertices of weight $k-1$ and proceed with the vertices of weight $k+1$. This requires at most about $binom{n}{n/2}approx 2^n/sqrt{n}$ space and $sum_k kbinom{n}{k} = n2^{n-1}$ time.
Version 2: Compute all the vertices that are needed to "count" up from 00…0 to 11…1 while restarting for each value (i.e. dropping all intermediate values). This needs $O(n^2)$ space and $O(n!)$ time.
Is there a way of traversing the graph that combines the best of both the ideas above? i.e. $O(n^2)$ space and $O(n2^n)$ time?
2 Asked on February 16, 2021 by yk1
2 Asked on February 16, 2021 by sqrt
1 Asked on February 15, 2021 by wheea
1 Asked on February 15, 2021 by adilah
0 Asked on February 15, 2021 by elster
convergence divergence multivariable calculus taylor expansion
0 Asked on February 15, 2021 by deltachief
7 Asked on February 15, 2021 by anastasiya-romanova
calculus harmonic numbers improper integrals integration real analysis
2 Asked on February 14, 2021 by darius-chitu
3 Asked on February 14, 2021 by sugaku
1 Asked on February 14, 2021 by gevorg-hmayakyan
diophantine equations elementary number theory quadratic residues
1 Asked on February 14, 2021
1 Asked on February 14, 2021
1 Asked on February 14, 2021 by flowian
4 Asked on February 14, 2021
1 Asked on February 14, 2021 by ferphi
0 Asked on February 14, 2021
2 Asked on February 14, 2021 by ellen-ellen
1 Asked on February 13, 2021
convergence divergence normal distribution probability probability theory
Get help from others!
Recent Answers
Recent Questions
© 2023 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP