# Hypercube traversal algorithm

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?

## Related Questions

### Minimum of $n$ geometric random variables

3  Asked on December 15, 2021

### Fundamental group of Klein Bottle

2  Asked on December 15, 2021 by jos-luis-camarillo-nava

### Derivative of $h(x,t)=gleft(frac{x}{t^2}right)$

3  Asked on December 15, 2021 by charith

### Lottery – Probability Discrepancy

2  Asked on December 15, 2021 by cannon444

### prove the spectral theorem for commutative operators with guidance

0  Asked on December 15, 2021

### Show numeric unstability of Cramer’s rule

1  Asked on December 15, 2021

### Need an upper bound for a simple expectation involving Rademacher random variables.

1  Asked on December 15, 2021 by golabi

### Question concerning prime ideals of $mathbb{C}[x,y]$

2  Asked on December 15, 2021

### Why is the solution to a non-homogenous linear ODE written in terms of a general fundamental solution and not a matrix exponential?

1  Asked on December 15, 2021

### $F=p_1times p_2$ a hyperbolic space?

0  Asked on December 15, 2021

### How to prove that $(a^m)^n=a^{mn}$ where $a,m,n$ are real numbers and a>0?

3  Asked on December 15, 2021 by orlin-aurum

### Find locus of point

0  Asked on December 15, 2021

### Nonlinear dynamics and state space trajectories of networks with time-dependent architecture

0  Asked on December 15, 2021 by neuroguy

### I don’t understand Gödel’s incompleteness theorem anymore

5  Asked on December 15, 2021

### If $T(p(t)) = p(t+1)$ then find its minimal polynomial where $T$ is a linear operator from $Bbb{P_n} rightarrow Bbb{P_n}$

2  Asked on December 13, 2021

### about the Laguerre square expansion Sin(x)

0  Asked on December 13, 2021 by charlessilva

### If $p$ and $q$ are coprime positive integers s.t. $frac{p}{q}=sum_{k=0}^{100}frac1{3^{2^k}+1}$, what is the smallest prime factor of $p$?

1  Asked on December 13, 2021

### Prove that a Tower of Height $H$ can be built if $H*(H+1)/2 = R + G$

2  Asked on December 13, 2021 by het

### How can I find the solution around $r=1$ for this ODE?

0  Asked on December 13, 2021

### Can I square both sides of inequality for these functions?

1  Asked on December 13, 2021 by user807688