2022 Developer Survey is open! Take survey.

# Tag Info

Accepted

• 269k
1 vote
Accepted

### Does a graph diameter equal to DFS tree depth?

Regarding DFS the answer is no. Here there is a counter example. The red arcs represent the DFS tree starting from the topmost node. This tree depth is 5 while the diameter is 3. On the other hand, ...
• 1,168
1 vote

### Canonical representation of finite maps on non-overlapping finite rational intervals

Here is another solution. You can use the SeqHash data structure in the following paper: VerSum: Verifiable Computations Over Large Public Logs. Jelle van den Hooff, M. Frans Kaashoek, and Nickolai ...
• 140k
1 vote

### Canonical representation of finite maps on non-overlapping finite rational intervals

It's possible to build a data structure that in practice has $O(\lg n)$ lookup, $O(\lg n)$ insertion, and $O(1)$ equality-tests. I'll describe how below. (If you care about theoretical worst-case ...
• 140k
1 vote
Accepted

### Properties of Reverse Polish Notation expressions that are algebraically invariant

You ask for a computable property that can be used as a fingerprint for equivalence (algebraic equivalence in your case). There are two general approaches to this kind of question: Take a canonical ...
• 2,059
1 vote
Accepted

### match an array with a given set of arrays

Let $s$ be the size of an array (36 in your example), $v$ the number of possible values (here 13) of each element, $n$ the numbers of reference arrays (here 24), i.e., the size of the set \$S=\{A_i \...
• 19.1k
1 vote

### match an array with a given set of arrays

You could calculate something like crc32 of the arrays and compare them with the crc32 of the new array. If the crc32's of the arrays match then you can do further check if the elements actually match ...
• 141

Only top scored, non community-wiki answers of a minimum length are eligible