# 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

### How to prove that $x(t) = cos{(frac{pi}{8}cdot t^2)}$ aperiodic?

2  Asked on February 16, 2021 by yk1

### Most General Unifier computation

1  Asked on February 16, 2021 by milano

### How to check if a number can be represented as the sum of two consecutive perfect cubes.

2  Asked on February 16, 2021 by sqrt

### How to compute $mathbb{P}(B(tau)leq a)$, $B(t)$ is standard Brownian motion.

1  Asked on February 15, 2021 by wheea

### Convergence radius for the Taylor series of a function of two variables.

0  Asked on February 15, 2021 by elster

### Probability distribution of time at which 2 random walks meet

0  Asked on February 15, 2021 by deltachief

### Looking for closed-forms of $int_0^{pi/4}ln^2(sin x),dx$ and $int_0^{pi/4}ln^2(cos x),dx$

7  Asked on February 15, 2021 by anastasiya-romanova

### Proving $sum_{cyc}frac{(a-1)(c+1)}{1+bc+c}geq 0$ for positive $a$, $b$, $c$ with $abc=1$.

2  Asked on February 14, 2021 by darius-chitu

### Proof that $frac{2^{-x}-1}{x} = sum_{n=0}^{infty} frac{ (-1)^{n+1}x^n(ln2)^{n+1}}{(n+1)!}$

3  Asked on February 14, 2021 by sugaku

### $24ml+1=k^2$ has no solution for all $l=1 dots m$

1  Asked on February 14, 2021 by gevorg-hmayakyan

### I can’t find the analytical expression of the sum from this probability problem

1  Asked on February 14, 2021

### Slightly confused about the commutator subgroup

1  Asked on February 14, 2021

### Isomorphism from ring to ring. Exercise from General Topology (J. Kelley)

1  Asked on February 14, 2021 by flowian

### Polynomial with root $α = sqrt{2}+sqrt{5}$ and using it to simplify $α^6$

4  Asked on February 14, 2021

### $sigma(n)$ is injective?

1  Asked on February 14, 2021 by ferphi

### Polynomial multiplication is associative

0  Asked on February 14, 2021

### Find area of equilateral $Delta ABC$

2  Asked on February 14, 2021 by ellen-ellen

### Convergence in distribution of $N(0, 1/n)$

1  Asked on February 13, 2021

### Diagonal of parallelogram and parallelepiped

0  Asked on February 13, 2021 by return