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 December 15, 2021 by jos-luis-camarillo-nava

abstract algebra algebraic topology fundamental groups group theory klein bottle

3 Asked on December 15, 2021 by charith

2 Asked on December 15, 2021 by cannon444

0 Asked on December 15, 2021

abstract algebra diagonalization linear algebra linear transformations spectral theory

1 Asked on December 15, 2021

linear algebra numerical calculus numerical linear algebra numerical methods systems of equations

1 Asked on December 15, 2021 by golabi

expected value probability probability theory rademacher distribution

2 Asked on December 15, 2021

1 Asked on December 15, 2021

matrix exponential ordinary differential equations systems of equations

0 Asked on December 15, 2021

3 Asked on December 15, 2021 by orlin-aurum

algebra precalculus exponential function exponentiation real analysis real numbers

0 Asked on December 15, 2021 by neuroguy

chaos theory graph theory multigraphs network nonlinear dynamics

5 Asked on December 15, 2021

2 Asked on December 13, 2021

0 Asked on December 13, 2021 by charlessilva

1 Asked on December 13, 2021

elementary number theory fractions prime factorization sequences and series summation

2 Asked on December 13, 2021 by het

0 Asked on December 13, 2021

1 Asked on December 13, 2021 by user807688

Get help from others!

Recent Questions

- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?
- Does Google Analytics track 404 page responses as valid page views?

Recent Answers

- Joshua Engel on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?

© 2023 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP, SolveDir