# Question
Title: Replacing 0x1021 polynomial with 0x8005 in this CRC-16 code
I found a highly optimized CRC-16 implementation originally intended for microcontrollers. It is noticeably faster than the traditional method, but is hard-coded to model the specific unreflected polynomial `0x1021`, or x^12 + x^5 + x^0.

I was then able to determine, when slightly modified, the reflected variant of this polynomial can be modelled as well, which is `0x8408`, or x^15 + x^10 + x^3. This is achieved by changing bit shift direction as well as the polynomial shifts. Though I'm unsure of the specifics of how it works. I've also found examples of CRC-32 that use this approach, but require many more operations.

Now, I am wondering if it is possible to use this same approach to use other polynomials, specifically `0x8005`, or x^15 + x^2 +x^0. To do so I need to understand what this code is doing, but it's highly cryptic. This is a essentially an edge case of CRC, amounting to clever usage of bitwise optimizations.

Here is the code for the unreflected CRC-16 using polynomial `0x1021`:

```
// in JavaScript, but easily translates to C etc.
function crc16(data, crc = 0, xorout = 0) {
    for(let i = 0, t; i < data.length; i++, crc &= 0xFFFF) {
        t = (crc >> 8) ^ data[i]; // shift high crc byte over
        t = (t ^ t >> 4);
        crc <<= 8; // shift left 1 byte
        crc ^= (t << 12) ^ (t << 5) ^ (t);
    }
    return crc ^ xorout;
}

```

This can model CRC-16 variants such as XMODEM or "CCITT-FALSE" depending on the initial value of `crc` and `xorout`.

The `crc` variable stores the current CRC value, while the `t` variable is temporary storage for intermediate calculations. The expression `(t << 12) ^ (t << 5) ^ (t)` appears to model the actual polynomial, which gets XOR'd into the CRC for every byte of input.

For `0x8005`, also an unreflected polynomial, one might assume a drop in replacement such as `(t << 15) ^ (t << 2) ^ (t)` would do the trick, but it does not work. In fact, in that code, the `(t << 12)` cannot be changed, though other terms can, if they're less than `(t << 8)`. So this only covers polynomials 4096 through 4607.

As I said before, I was able to correctly model the reflected version of `0x1021` as well using a similar construction. Here is the code for that:

```
function crc16b(data, crc = 0, xorout = 0) {
    for(let i = 0, t; i < data.length; i++, crc &= 0xFFFF) {
        t = (crc) ^ data[i];
        t = (t ^ t << 4) & 255; // &255 is to remove overflow
        crc >>= 8; // shift right 1 byte
        crc ^= (t << 8) ^ (t >> 4) ^ (t << 3);
    }
    return crc ^ xorout;
}

```

This code correctly models the reflected variants such as CCITT-TRUE, ISO/IEC 14443 among others.

The code is slightly different to account for it being reflected, but the structure is essentially the same. However the expression that represents the polynomial is a bit strange: `(t << 8) ^ (t >> 4) ^ (t << 3)`. It doesn't seem to line up with the expected polynomial representation x^15 + x^10 + x^3.

The polynomial I want to translate to this structure is `0x8005` (or its reflected version, `0xA001`). It has both reflected and unreflected variants. I am referencing the different CRC-16 variants and vectors from here: http://reveng.sourceforge.net/crc-catalogue/16.htm

This page uses a test string "123456789", to check implementation correctness, so I typically check it as an array:

```
crc16([49, 50, 51, 52, 53, 54, 55, 56, 57])

```

And these are the expected values for two CRC-16 variants I am targeting (which use `0x8005` polynomial or `0xA001` reversed):

```
For init=0x0000 and xorout=0x0000
----------------------------------
CRC-16/UMTS (unreflected) = 0xfee8
CRC-16/ARC  (reflected)   = 0xbb3d

```

What I want to do is modify the above code to implement the polynomials `0x8005` and `0xA001`, but I'm having trouble figuring out how it even works in the first place. I figured `0x8005` would be a good fit because of the few number of bits which are used.

Any ideas on how this is actually implementing CRC-16, or what might be required to translate other polynomials?

A classic resource on CRC is A Painless Guide to CRC Error Detection Algorithms

---

Also if it helps, here are traditional implementations of CRC-16 (but are less efficient):

These implementations allow any polynomial to be supplied as input. Here is the unreflected version:

```
// Targets XMODEM
var crc16 = function(data) {
    var POLY = 0x1021, INIT = 0, XOROUT = 0;
    for(var crc = INIT, i = 0; i < data.length; i++) {
        crc = crc ^ (data[i] << 8);
        for(var j = 0; j < 8; j++) {
            crc = crc & 0x8000 ? crc << 1 ^ POLY : crc << 1;
        }
    }
    return (crc ^ XOROUT) & 0xFFFF;
};

```

And the reflected equivalent (notice the change of shift direction...):

```
// Targets KERMIT
var crc16b = function(data) {
    var POLY = 0x8408, INIT = 0, XOROUT = 0;
    for(var crc = INIT, i = 0; i < data.length; i++) {
        crc = crc ^ data[i];
        for(var j = 0; j < 8; j++) {
            crc = crc & 1 ? crc >> 1 ^ POLY : crc >> 1;
        }
    }
    return (crc ^ XOROUT) & 0xFFFF;
};

```

# Answer
Yes, it's possible, but there is no magic formula. Each polynomial requires a unique set of operations, and the number of operations required can vary highly. A solid grasp of CRC math is also necessary to craft these solutions. Unfortunately I only have a cursory understanding, so my explanation may be limited.

The best way to illustrate this is to compare them. Here's the code for `0x1021`:

```
 t = (c >> 8) ^ d;
 t ^= t >> 4;
 c = (c << 8) ^ (t << 12) ^ (t << 5) ^ t;

```

And here is the equivalent for `0x8005`:

```
 t = (c >> 8) ^ d;
 z = t;
 t ^= t >> 4;
 t ^= t >> 2;
 t ^= t >> 1;
 t &= 1;
 t |= z << 1;
 c = (c << 8) ^ (t << 15) ^ (t << 1) ^ t;

```

As you can see, the code required to implement different polynomials, can be highly variable. The second implementation requires more operations and intermediates.

The `0x1021` polynomial appears to require very few operations, and so it's a good choice for microcontrollers which are slower and have little RAM. It may be unique in this regard.
> 0 votes

---
Tags: algorithms, arithmetic, error-correcting-codes, mathematical-analysis, crc
---


# Question
Title: The opcode "load the next word into Register A" mentioned by Gandalf61
Gandalf61 mentions here that there are opcodes that "load the next word into Register A", treat the bits at the next address defined by program counter as data and loads this data. I am interested in examples of computers and CPUs that have such as opcode.

*Context: Learning basic computer architecture, and interested in how to load constants into registers. In nandgame.com and "nand to Tetris" course (that uses "hack computer" and "hack assembly"), there is "a-instruction", specified by 15th bit set to 0, that treats the instruction as 15 bits of data. With "load immediate" instruction (or similar name) in a few real-world CPUs I read about, a few bits will be treated as data and loaded into register. I am interested overall in how a constant defined in assembly or in a program gets into the CPU. Have not seen any that worked like Gandalf61 mentioned, therefore asking.*

# Answer
Many/most architectures include this kind of instruction. It might be known as "load immediate" or "move" with an immediate/literal/constant value. See, e.g., https://en.wikipedia.org/wiki/Addressing\_mode#Immediate/literal, https://en.wikipedia.org/wiki/Instruction\_set\_architecture#Data\_handling\_and\_memory\_operations, or look into the instruction sets of any of your favorite computer architectures.
> 2 votes

# Answer
Expanding on the comments about x86:

One of x86's "load immediate" instructions is `MOV eax, 0x11223344` encoded as `B8 44 33 22 11` (x86 is little-endian).

There are two ways you could view this instruction.

Officially, it's a 5-byte-long instruction `MOV eax, 0x11223344` which stores the value 0x11223344 into eax.

But you could also view this as a 1-byte instruction `MOV eax, next 4 bytes from EIP` (encoded as `B8`) followed by the 4-byte value 0x11223344.

These are two different ways to think about the exact same machine code bytes which make the processor do the exact same thing.
> 2 votes

---
Tags: cpu
---


# Question
Title: Interpreting results of Sobel Edge Detection
I am implementing A No-Reference Perceptual Blur Metric paper.

Somewhere in the prep steps they mention the use of vertical Sobel filter for finding vertical edges.

> The algorithm is summarized in Fig. 1. First we apply an edge detector (e.g. vertical Sobel filter) in order to find vertical edges in the image. We then scan each row of the image1.

I am using `scipy.ndimage.sobel(y, axis=1)` on Y component of the image as suggested in the paper. But to be honest I don't know how should I interpret this output to decide if there is an edge in this area or not.

Basic idea of the solution from the paper is summarised in this graph:

So I think I understand how to calculate the edge width using the algorithm but to be able to do that I need to know the location for the green dashed line. I think this is what Sobel filter gave them or interpreting the results of `scipy.ndimage.sobel(y, axis=1)` will give me.

How will I be able to identify the locations of green dased lines from the output of `scipy.ndimage.sobel(y, axis=1)`.

# Answer
I might be wrong, but I think the red line is actually discrete line segments, and it looks like the green dashed lines are placed two red segments away from a local max or local min. Otherwise, I think the idea is that you take two equidistant lines, some distance away from the local min or max.
> 0 votes

# Answer
The paper does not describe how the edge location is chosen ("vertical Sobel filter" is not sufficient), but it seems that only the edge width is used (distance between extrema). So it could be that the green annotation was made by hand. You should not worry.
> 0 votes

---
Tags: algorithms, computer-vision, image-processing
---


title: Reductions but no algorithms

text:
# Question
Title: Reductions but no algorithms
in "Introduction to Automata Theory, Languages and Computations" by Motwani, Ullman and Hopcroft, when they need to prove, for instance, Rice's theorem, they reduce the universal language, $L\_u$, to the language $L\_p$, where the latter is defined as the language containing the codes (binary) of all the TM $M$ such that $L(M) \in P$, where $P$ is a non-trivial property of $RE$ languages.

In the proof, they don't give the algorithm that converts an instance of $L\_u$, $(M,w)$, to an instance of $L\_p$, $\<M'\>$, but they give a description of $M'$, saying that this should be sufficient to convince the reader that a TM able to perform a conversion from $(M,w)$ to $\<M'\>$ exists.

I don't understand how this should be sufficient to convice myself that an instance-conversion algorithm exists. I mean: we are only describing $M'$, how can we be sure a TM is able to take $(M,w)$ as input and give us the binary code of $M'$?

# Answer
> 1 votes
This is very common. Specifying a Turing machine formally is super tedious and often not very insightful. It amounts to implementing a program, in a horribly inconvenient programming language. Writers typically assume that you already know how to write programs and that you can figure out how to implement something as a Turing machine, and leave it up to you to fill in those tedious details.

For instance, if I give you pseudocode of an algorithm, I am presuming that you will know how to turn that into an implementation. Same deal in these theorems: the author is trusting that you will know how to turn that description into an algorithm and then into code.

---
Tags: turing-machines, reductions, rice-theorem
---


# Question
Title: Prove that the "6-rule" CFG for arithmetic expressions below is unambiguous
**Question**: Prove that the 6-rule CFG for arithmetic expressions below is unambiguous.

The CFG is as follows. $G = (V:=\\{E,T,F\\}, \Sigma:=\\{+, \times,(,),x\\},R,E\\})$

where $R$ consists of 6 rules:

$E\rightarrow E+T ~|~ T~~~~~~ T\rightarrow T\times F|F~~~~~~ F\rightarrow (E) | x$

**My thoughts**: I think we should start by showing each string $s$ in language has a unique derivation by strong induction on the length of $s$, but not sure how to proceed. Could you please help?

Many thanks!

# Answer
> 0 votes
Sometimes explicit induction can be avoided by using contradiction. Assume there is a smallest pair of different derivation(trees) that derive the same string. Since the pair is different, we can also assume that the roots of the trees are the same, but the applied productions differ.

So can we have two derivation trees that start with the productions $F\to (E)$ and $F\to x$ and derive the same string. Obviously not. The same should be checked for the pair $E\to E+T$, $E\to T$ and the pair $T\to T\times F$, $T\to F$.

---
Tags: automata, context-free, pushdown-automata, computation-models
---


# Question
Title: How this state set of DFA was retrieved from the given NFA
I have this NFA:

```
1,{2, 3}
2,empty
3,{4}
4,empty

```

All the arrows in this NFA are epsilon-arrows.

I understand that all possible states that can be reached from each of the states, using only epsilon paths are these:

```
E(1) = {1,2,3,4}
E(2) = {2}
E(3) = {3,4}
E(4) = {4}

```

However I don't understand how this state set was achieved:

```
DFA = {empty, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {1, 2,
3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}}

```

My understanding is that the transition table that looks like this:

```
   epsilon
1  2, 3
2  -
3  4
4  -

```

is to be used to determine the DFA, along with the E function.

I tried to do it like this:

```
Start state = 1 => the Result = {E(1)} = {{1, 2, 3, 4}}

T({1, 2, 3, 4}) = E(transitionTable({1, 2, 3, 4})) = E({2, 3, 4}) = {2, 3, 4}

Result = {{1, 2, 3, 4}, {2, 3, 4}}

T({2, 3, 4}) = E({4}) = {4}

Result = {{1, 2, 3, 4}, {2, 3, 4}, {4}}

T({4}) = E({}) = {}

Result = {{1, 2, 3, 4}, {2, 3, 4}, {4}, {}}

```

What am I doing wrong here? Any help is appreciated.

EDIT:

Transition table:

```
   epsilon
1  2, 3
2  -
3  4
4  -

```

EDIT:

Using this converter: https://joeylemon.github.io/nfa-to-dfa/

With this file:

```
{"nodes":[

{"label":"1","loc":{"x":200,"y":100},"transitionText":{"2":["ε"],"3":["ε"]}},

{"label":"2","loc":{"x":600,"y":100},"transitionText":{}},

{"label":"3","loc":{"x":400,"y":400},"transitionText":{"4":["ε"]}},

{"label":"4","loc":{"x":600,"y":400},"transitionText":{},"acceptState":true}],

"fsa":{"states":["1","2","3", "4"],"alphabet":["ε"],"transitions":{"1":{"ε":["2"],"ε":["3"]},"2":{},"3":{"ε":["4"]}},"startState":"1","acceptStates":["4"]}}

```

gives this:

https://i.stack.imgur.com/Cl9aP.png

So it says the states in DFA are `Q' = {{Ø}, {1,3}, {4}, {3,4}}`, not

`{{}, {4}, {2, 3, 4}, {1, 2, 3, 4}}`

# Answer
Observe that the states of the DFA in question is the **powerset** of the states of the NFA, while the process of converting the NFA to a DFA you have presented is called subset construction. Since the resulting states of the DFA using subset construction is guaranteed to be a subset of the powerset of the states of the NFA, you can actually define the state of the DFA to be the entire powerset, hence your DFA in question. However, its possible that there will be certain states in the powerset that will be unreachable from the start state and therefore useless (*although in the worst-case the resulting DFA might actually have all that exponentially many reachable states*).

What you did on the other hand, is you try to compute only reachable states from the start state. Your computation of $\varepsilon$-closure (paths using $\varepsilon$ transition only) is correct. However, your process of computing DFA state from each NFA transition will still generate unreachable states. I suggest that you read the link on subset construction I have given above for the step-by-step process. If your familiar with breadth-first search (BFS), the general idea of subset construction is similar. You just have to understand how to determine the reachable (neighbors) states from a given state.

As a hint, the DFA that you should generate must have a single state only $\\{1,2,3,4\\}$ which is both a start and final state.
> 0 votes

---
Tags: automata, finite-automata
---


# Question
Title: If $f \in \mathcal{o}(g)$, does $f \circ g \in \mathcal{o}(g \circ f)$?
It's a widely known fact that $\lambda n. \left\lfloor \lg n! \right\rfloor \in \mathcal{O}(\lambda n. \left\lfloor \lg n \right\rfloor!)$. Is it also true (I tried and haven't found a counterexample so far) for all functions $f$ and $g$ satisfying $f \in \mathcal{o}(g)$, not just $f(n) = \left\lfloor \lg n \right\rfloor$ and $g(n) = n!$? If so, does the result still hold with $\mathcal{o}$ replaced by $\mathcal{O}\setminus\Theta$? And under what condition can the conclusion be strengthened with $\mathcal{o}$ or $\mathcal{O}\setminus\Theta$ in place of $\mathcal{O}$?

# Answer
There is no relation between $f \circ g$ and $g \circ f$ in general.

* If $f(n) = n^2$ and $g(n) = n^3$, then $f \circ g = g \circ f$
* If $f(n) = \log n$ and $g(n) = n^2$, then $f \circ g \in o(g \circ f)$.
* If $f(n) = \log n$ and $g(n) = \sqrt n$, then $f \circ g \in \omega(g \circ f)$.
> 3 votes

# Answer
No. Try $f(x)=\sqrt x$ and $g(x)=x^2$.
> 0 votes

---
Tags: asymptotics
---


# Question
Title: Substitutions unions vs composition are not the same?
I'm studying substitutions. A substitution is a set of mappings from variables to terms $\\{a \rightarrow b; c \rightarrow d;...\\}$.

Given these substitutions:

* $\sigma\_1 := \\{x \rightarrow y\\}$
* $\sigma\_2 := \\{y \rightarrow x\\}$
* $\sigma\_3 := \sigma\_1 \cup \sigma\_2 $

And this term : $t := f(x, y)$ are following substitutions correct?

* $t\sigma\_1 \Rightarrow f(y, y)$
* $t\sigma\_2 \Rightarrow f(x, x)$
* $t\sigma\_1\sigma\_2 \Rightarrow f(x, x)$
* $t\sigma\_3 \Rightarrow f(y, x)$

For some reason, I expected that $t\sigma\_1\sigma\_2 = t\sigma\_3$ which seems not to be the case, I came across this during the implementation of substitutions here https://gist.github.com/dhilst/81592505f2bdc886e9085bd24d352e60 where I implemented the substitution by implementing a function that does one substitution and then composing multiple substitutions from a list, and then implementing the notation $t\\{a \rightarrow b; c \rightarrow d; ...\\}$ as $t\\{a \rightarrow b\\}\\{c \rightarrow d\\}\\{...\\}$ which looks wrong now

# Answer
By definition, a substitution in first-order logic consists in simultanously replacing variables for their mapped terms, whereas the composition is the result of applying the substitutions in the order they are given (https://en.wikipedia.org/wiki/Substitution\_(logic)#First-order\_logic).

Hence, when applying a composition of substitutions, one substitution may affect the other one according to the order they have (like in your examples, first applying $\\{x\rightarrow y\\}$ and then applying $\\{y\rightarrow x\\}$ is the same as applying $\\{x\rightarrow x; y \rightarrow x\\}$; but first applying $\\{y\rightarrow x\\}$ and then $\\{x \rightarrow y\\}$ would result into $\\{y \rightarrow y; x\rightarrow y\\}$). This is not the case with a union of substitutions (where $\\{x \rightarrow y\\} \cup \\{y \rightarrow x\\}$ is the same as $\\{y \rightarrow x\\} \cup \\{x \rightarrow y\\}$).
> 3 votes

---
Tags: first-order-logic
---


# Question
Title: Program counter in ISA with multi-word size for instructions
Some ISA's have instructions that are multiple words, such as the MOV instruction in x86. How does the program counter behave in that case, if the instruction loaded is more than one word? For example, the 5 byte MOV eax, 0x11223344 in x86, encoded as B8 44 33 22 11. In the case of that example, I would assume PC (EPI register in x86 if I understand right) is incremented by two (4 byte + 4 byte, two words, assuming word size is 4 byte. ) I tried to test it myself in this emulator , but it only increments by one. I assume emulator wrong. I ask broadly here because people here would likely know: How does the program counter behave (generally, across specific ISA's) if the instruction loaded is more than one word?

# Answer
You have an instruction that is five bytes in size. After executing that instruction, what do you think where the next instruction is stored? Since the word size on a modern processor is 8 bytes, assume we have an instruction that is 11 bytes in size. Where do you think the next instruction is stored?
> 1 votes

---
Tags: cpu
---


# Question
Title: Efficient Method for Distance Comparison in Euclidean Space
I have a vector of 2D Euclidean coordinates, and I need to find out if two or more points are within a distance threshold.

The naive approach is to compare each point with every other point, but I am not interested in **O(n2)** solutions. There are no other information or data that can be used to restrict the search space.

What is a good algorithm that has a runtime complexity of **O(nlog(n))** or faster? I am working with C++, and I am looking into Boost's r-tree (not sure it is appropriate).

# Answer
I've had to do something along these lines. My solution: Pick one of the dimensions and divide it into 'buckets' of width equal to the threshold (only finitely many buckets are required for finitely many points). Then place each point into its bucket; when doing so, check for proximity to another point against all points already in the same bucket plus the (at most) two immediately adjacent buckets. Because of the chosen bucket width, no point in any other bucket can be too close. If the points are reasonably scattered in two dimensions, there should need to be approximately O(N) comparisons, I estimate. Of course, it is possible for some point sets to be badly distributed (e.g all in one bucket), so you may need to do some preliminary calculation on the point set to pick which dimension is better to divide.
> 0 votes

---
Tags: algorithms, euclidean-distance
---


# Question
Title: How substituituion composition is associative?
I'm not convinced that substitutions are associative, I read the https://en.wikipedia.org/wiki/Substitution\_(logic)#First-order\_logic and the https://www.youtube.com/watch?v=\_cVNeccMF-E

My problem is in this case, I use $\Rightarrow$ to mean *reduces to*

$( f(X,Y)\\{X \rightarrow Y\\} )\\{Y\rightarrow X\\} \\ \Rightarrow f(Y, Y)\\{Y\rightarrow X\\}\\ \Rightarrow f(X, X)$

While

$f(X,Y)(\\{X \rightarrow Y\\}\\{Y\rightarrow X\\}) \\ \Rightarrow f(X,Y)\\{X \rightarrow Y;Y\rightarrow X\\} \\ \Rightarrow f(Y,X)$

I think my reduction understanding should be wrong but I don't know where.

# Answer
As you have proven the composition $\\{X\to Y\\}\\{Y \to X\\}$ is not $\\{X\to Y; Y\to X\\}$. Rather the composition is (assuming that it acts on terms to the left of it) $\\{Y \to X\\}$.

Also, that has nothing to do with associativity. See https://en.wikipedia.org/wiki/Associative\_property.
> 1 votes

---
Tags: first-order-logic
---


# Question
Title: Choice of data structure to contain last 5 minutes of long continuous data stream
Let's assume that I am continuously receiving big amount of data. For example, this millisecond I get 100 numbers, next millisecond I get another 500 numbers, after that I might get nothing for a several milliseconds and then again get some numbers in the next millisecond. Also assume that this process lasts for weeks. However, I don't really need to save old data in memory. What I really need is to remember data received in the last 5 minutes. That is, all I want is to be able to present data for last 5 minutes whenever I am asked to.

Do you have any ideas on how to realize this? What kind of data structure would help in such a situation and how should I use it? All I could imagine was saving with every piece of data the moment of time when it was received, storing everything in a queue and constantly deleting element from queue's head if its time shows that it was received more than 5 minutes ago. I hope there is a more elegant/efficient solution.

Thank you.

# Answer
The data structure you are looking for is double-ended queue (deque). It is basically what you have imagined, with the extra ease of operations on the front.

Deque has been implemented in many languages in their standard libraries or packages, with some extra operations available for practical convenience usually. For example, you can access any element by an index in a deque in C++ or Python implementation (that index is the number of elements before the element accessed).
> 2 votes

---
Tags: algorithms, data-structures, queues
---


# Question
Title: How to approximate percentile value from value-count map?
Background: How Percentile Approximation Works (and Why It’s More Useful Than Averages)

In traditional scenario, we store each value in an array/slice, in that case, we can just sort the array, and get the approximate percentile. For example,

```
[67, 68, 70, 71, 76, 78, 78, 79, 80, 98]

```

We could get the p90(90th percentiles) is `80`, by

1. Get the `length` of the array, which is `10`
2. Calculate the `index` by `int(length * 0.9)`, which is `9`
3. Return the index data `return arr[index-1]`, which is `80`

In my specific case, I have a `sync.Map`, and the data looks like:

```
{67:5 , 68:8, 70:20:, 71:10, 76:80, 78:120, 79:90, 80:73, 98:2}

```

We can interpret that by saying: there are 5 people got a score of 67 and so on.

Just wondering if there's any exists algorithm to calculate the approximate percentile value in this case?

# Answer
> 1 votes
Compute the prefix sum of the counts,

```
67:5, 68:13, 70: 33, 71: 43, 76: 123, 78: 243, 79: 333, 80: 406, 98: 408

```

and find the value corresponding to `90%` of `408` = `367.2`. (Between `79` and `80`.)

---
Tags: algorithms
---


# Question
Title: How to resolve the clash between definition of Big O notation and Inductive Hypothesis when proving running time by substitution method?
Suppose you have to prove the solution to the following recurrence by Induction,

$$ T(n)= \begin{cases} \Theta(1), & n=1 \\ 2 T(\lfloor n/2 \rfloor)+\Theta(n), & n\>1 \end{cases} $$ Here, $\Theta(1)$ and $\Theta(n)$ are notational abuse and they represent arbitrary positive constant and arbitrary linear function respectively.

First, we guess the solution, $$ T(n)=O(n\log n) $$ which expanded, $$ T(n)\le cn\log n \quad \forall n\ge n\_0,\text{where }c\>0, n\_0\in \mathbb N $$

Now, we want to prove $\forall nP(n)$, where $$ P(n):T(n)\le cn\log n \quad \forall n\ge n\_0,\text{where }c\>0, n\_0\in \mathbb N $$

We will assume $P(k)$ for some $k$ and show $P(k+1)$. But what does it mean to assume $P(k)$ for some $k$ here? The expression $\forall k\ge n\_0$ hurts by brain since we have taken $k$ to be some natural number and prefixing it with universal quantifier doesn't make sense to me.

How do we go about this?

**Update**

Actually the problem is with $P(n)$. It cannot contain quantifiers. It is atomic in First-order Logic.

# Answer
What you asking about is mathematical induction theorem, more known as mathematical induction principle. It states, that $$\begin{cases}{} P(n\_0) \text{ true} & \\ (\forall n \geqslant n\_0)\big(P(n)\Rightarrow P(n+1)\big) & \end{cases} \Rightarrow (\forall n\geqslant n\_0)P(n) $$

verbally it means, that for proving $(\forall n \geqslant n\_0)P(n) $ is enough to prove two sentences: $P(n\_0)$ and implication $(\forall n \geqslant n\_0)\big(P(n)\Rightarrow P(n+1)\big) $. In last one $n$ is, so called, bound variable, dummy variable, and can be replaced with any other letter except $P$ and $n\_0$. For example it same with $(\forall k \geqslant n\_0)\big(P(k)\Rightarrow P(k+1)\big) $.

**About update**

Sentence under consideration is $T(n)=O(n\log n), n\to \infty\quad (2)$ and it's definition, of course **contain** quantifiers. As $n$ is bound variable in $(2)$, then it is not fully correct to denote it by $P(n)$, because, really, it does not contain $n$. Exact is to write $T\in O(f)$, where $f(x)=x \log x$.

**Example of using**:

Let me show how is it possible to use math. induction with sentences type $f\in O(g)\quad(3)$. Assume $f(n)=g(n)=n$. Formally $(3)$ is following: $$\exists c\>0, \exists n\_0 \in \mathbb{N}, \forall k \> n\_0, k\leqslant c\cdot k\quad (4)$$ All variables used are bound except $\mathbb{N}$. Let's choose $c=1=n\_0$, denote by $P(k)$ sentence $ k\leqslant k$ and start proof of sentence $\forall k \> 1,P(k)$, using math. induction with respect to $P$. Because holds $P(1)$ and $(\forall k \geqslant 1)\big(P(k)\Rightarrow P(k+1)\big)$, then proof is finished trivially.
> 0 votes

---
Tags: time-complexity, recurrence-relation, big-o-notation, induction
---


# Question
Title: Proving grammar equivalence in simple grammar (generate any sequence of three characters)
Goal is proving grammar equivalence

---

Upper-case symbols are non-terminal.

Lower-case symbols are terminal.

The start symbol is `S`.

A grammar production rule is **non-terminals-only** if it only contains non-terminals. For example: `AB -> CDE`

A grammar rule is **non-terminal-to-terminal** if the left side has one non-terminal and the right side has one terminal. For example: `A -> a` `B -> b`

A grammar is **aterminal** if:

* The number of terminals equals the number of non-terminals
* All rules are non-terminals-only or non-terminal-to-terminal
* Each non-terminal has a corresponding terminal via a non-terminal-to-terminal rule (and each terminal appears exactly once in a non-terminal-to-terminal rule)

For example:

Grammar 1

```
S -> SS
S -> A

S -> s
A -> a

```

It's called aterminal, because, in some sense, there's no distinction between terminals and non-terminals.

All grammars in this question are unrestricted, but aterminal.

---

If you start with a sequence of symbols, and use multiple production rules to generate a new sequence of symbols, you can consider that an additional (but redundant) rule.

For example:

Grammar 2:

```
A -> BB
B -> CC
C -> AA

A -> a
B -> b
C -> c

```

If we start with a non-terminal `B`:

```
B (we happen to start with B)
CC (B -> CC)
AAC (C -> AA)
AAAA (C -> AA)

```

Therefore we can add `B -> AAAA` to the grammar without changing the language it recognizes.

---

Grammar 3

```
S -> SS
S -> A
S -> B

S -> s
A -> a
B -> b

```

Grammar 3 generates any (non-empty) sequence of `s`,`a` and `b`. For example, to generate `sab`:

```
S (start rule)
SS (S -> SS)
SSS (S -> SS)
SAS (S -> A)
SAB (S -> B)
sAB (S -> s)
saB (A -> a)
sab (B -> b)

```

---

Grammar 4

```
S -> SS
S -> A
AA -> B

S -> s
A -> a
B -> b

```

Using the idea from Grammar 2, we can start with `S` and derive:

```
S (happen to start with S)
SS (S -> SS)
AS (S -> A)
AA (S -> A)
B (AA -> B)

```

Therefore we can derive `S -> B` as an additional rule.

**I believe now, having add `S -> B`, we can remove `AA -> B` and thus Grammars 3 and 4 are equivalent, but I don't know how to prove this. Is this right??? If so, what's the proof???**

Here's my progress:

Additionally, we can derive `S -> AA`.

Now we have three rules of this form:

```
X -> Y
Y -> Z
X -> Z

```

Namely:

```
S -> AA
AA -> B
S -> B

```

Maybe when you have 3 rules of this form, AND the only way to get `Y` is by "first going through `X`", then you can remove the `Y -> Z` rule. I don't know if this is right or how to formalize this.

# Answer
> 2 votes
You can prove grammar equivalence by showing that they represent the same language,use fixed pont iteration method to find language of context free grammar.

---
Tags: formal-grammars
---


# Question
Title: Identify the missing number in a set given its superset
Given a set B and B’s superset A, if B is missing 1 number (let’s y) but don’t know which number it is, how to find that number? That is,

> B’ = B \ {y}, for some unknown element y
> B = A \ {x}, for some unknown elements x
> I’d like to know y.

The original context is from Problem6,

> Miners A and B each have a set of transac- tions in their mempool. Suppose that miner A’s set is a superset of miner B’s. Miner A wants to send to B the transactions that B is missing. The problem is that A does not know which transactions B is missing.
>
> > a. Suppose B is only missing one transaction. Show that A can send a single 32-byte message to B that quickly lets B identify the missing transaction hash. B will send the missing transaction hash to A, and A will send back the transaction data.
> > Hint: Think of computing the xor of all the transaction hashes in A’s mempool.

So far, my thought is:

> xor all numbers in A = C
> C xor B = missing number and difference between 2 sets

And I’m stuck at here.

# Answer
I don't undestand what is the difficulty you are having.

If $B = A \setminus \\{x\\}$ for some element $x$, then: $$ \begin{align\*} \left( \bigoplus\_{b \in B} b \right) \oplus \left( \bigoplus\_{a \in A} a \right ) &= \left( \bigoplus\_{b \in B} b \right ) \oplus \left( \bigoplus\_{a \in A \setminus {x}} a \right) \oplus x \\ & = \left( \bigoplus\_{b \in B} b \right ) \oplus \left( \bigoplus\_{a \in B} a \right) \oplus x \\ &= 0 \oplus x = x. \end{align\*} $$
> 0 votes

---
Tags: algorithms, bit-manipulation, communication-complexity
---


title: Weigher problem

text:
# Question
Title: Weigher problem
I got interested in one problem. I have $N$ rocks, where rock with minimum weight have number equal to $1$, the next heaviest stone has a number equal to 2, etc..

So a rock with maximum weight have a number equal to $N$. And I have $N$ requests, each of N request contains two integers: $R$ $(1≤R≤N)$ and $S$ $(1≤S≤2)$. $R$ is the number of the stone that will be placed on the bowl $S$. All $R$ are different.

For each request I return $\>$ if the left bowl is larger than the right, $\<$ if the right bowl is larger than the left, $?$ if isn't possible determine that is bowl larger.

Constraint on $N$ is $(N \< 10^5)$

For example, for input:

```
5
1 2
3 1
2 1
4 2
5 1

```

output is:

```
<
>
>
?
>

```

I have no idea whatsoever how to solve this problem. But I wonder, that segment tree can be helpful, but I could not develop my idea.

# Answer
> 0 votes
Here some progress. I'm assuming that no two rocks have the same weight.

We model a generic bowl as as set $X\subseteq \\{1,\dots, N\\}$ whose elements are the indices of the stones contained in the bowl. Let $n(i,X)$ denote the $i$-th largest index in $X$. If $X$ contains less than $i$ stones, let $n(i,X) = 0$. Let $w(i)$ denote the weight of the stone with index $i$, and define $W(X) = \sum\_{i \in X} w(i)$.

**Claim:** Bowl $A$ is certainly heavier than bowl $B$ if and only if $n(i,A) \> n(i,B)$ for all $i=1,\dots, |B|$.

Proof of the "if" direction. Notice that $n(|B|,A) \> n(|B|, B) \ge 1$ and hence $|A| \ge |B|$. Then: $$ W(A) = \sum\_{i=1}^{|A|} w(n(i,A)) \ge \sum\_{i=1}^{|B|} w(n(i,A)) \> \sum\_{i=1}^{|B|} w(n(i,B)) = W(B). $$

Proof of the "only if direction". Let $i^\*$ be an index such that $1 \le i^\* \le |B|$ and $n(i^\*,A) \< n(i^\*,B)$ and consider the following weight assignment:

* For $j \< n(i^\*,B)$, $w(j) = N - j$.
* For $j \ge n(i^\*,B)$, $w(j) = N^2 - j$.

We have: $$ \begin{align\*} W(A) - W(B) &\le \sum\_{i=1}^{i^\*-1} \bigg( w(n(i, A)) - w(n(i, B)) \bigg) + \sum\_{i=i^\*}^{|A|} w(n(i, A)) - w(n(i^\*,B))\\ & \le (i^\* -1) N + (|A|-i^\* + 1) N - (N^2 - N) \\ & \le |A| \cdot N + N - N^2 \\ & \le (N-1)N - N^2 \< 0. \end{align\*} $$

Therefore the problem boils down to pairing stones from the two bowl in decreasing order of weight, and checking whether each stone from one bowl is larger than the matching stone in the other bowl.

---
Tags: algorithms, data-structures
---


title: Is Huffman coding dynamic programming

text:
# Question
Title: Is Huffman coding dynamic programming
Huffman coding follows a bottom-up approach where as Shannon-Fano coding is top-down. Is that contrast similar to dynamic programming versus greedy algorithm (dynamic programming always give optimal solution whereas greedy algorithm is sub-optimal)? If yes why is Huffman called greedy? Why greedy algorithm can also be bottom-up? Isn't that a feature for DP?

# Answer
> dynamic programming always give optimal solution whereas greedy algorithm is sub-optimal

Not True. There are problems where even a greedy approach would result in an optimal solution(Fractional knapsack, Minimum cost spanning tree, etc). **An algorithm is said to be greedy if at every step it chooses a candidate and adds it to the solution set, without worrying about optimality**, which is very clear in how the Huffman algorithm works(follows the optimal merge pattern, which again is a greedy procedure).

Top down and Bottom up approaches are terms related to dynamic programming implementations, and huffman coding uses neither. One might feel that since we build the huffman tree from the leaves to root it is a bottom up approach, however it is not the same as bottom up dynamic programming.
> 1 votes

---
Tags: dynamic-programming, greedy-algorithms, huffman-coding
---


# Question
Title: Average and max. hitting time to a specific vertex
Consider simple random walks that stop when reaching a given node $x$ in an undirected, unweighted and connected graph on $n$ nodes. Let

* $H(i,x)$ denote the (expected) hitting time from $i$ to $x$, with $H(x,x)=0$.
* $H\_{\max} = \max\_{i \in V} H(i,x)$ and $H\_{\text{avg}} = \frac{1}{n}\sum\_{i \in V} H(i,x)$.

I am interested in the (asymptotic) largest possible ratio of $\frac{H\_{\max}}{H\_{\text{avg}}}$ in function of $n$. Similar to this question, but now considering the single-source variant w.r.t a specified node.

The worst example I was able to construct has ratio $\Omega(n^{3/4})$: Consider an $n$-star graph with center node $x$, attach to $x$ a lollipop graph of $2n^{1/4}$ vertices (i.e., a path of length $n^{1/4}$, attached with a clique of size $n^{1/4}$). So $H\_{\max} \approx n^{3/4}$, and $$H\_{\text{avg}} \approx \frac{n\cdot 1 +n^{1/4}\cdot n^{3/4}}{n} \in O(1),$$

since the average hitting time (over all the lollipop vertices) to $x$ is cubic in the size of the lollipop graph.

Are there any worse examples where $\frac{H\_{\max}}{H\_{\text{avg}}}$ is larger, perhaps even $\Omega(n)$?

# Answer
> 0 votes
The same question was asked at https://mathoverflow.net/questions/426969/average-and-max-hitting-time-to-a-specific-vertex

and for convenience, I reproduce the answer I just wrote there. Perhaps one of these copies will be removed eventually.

**Notation:** Let $G=(V,E)$ be an undirected simple graph of $n$ nodes. If $\tau\_x$ is the (random) time it takes the walk to reach the node $x$, then write $H(v,x)=E\_v(\tau\_x)$. Denote $H\_{\max}(x):=\max\_{u \in V} H(u,x)$ and $ H\_{\rm avg}(x) =\frac1n\sum\_{v \in V} H(v,x)$.

**Claim:** $ H\_{\max}(x) \le 2n^{3/4} H\_{\rm avg}(x)$ for all $x$.

Proof: Given $M\>0$, define $$S=\\{v \in V: H(v,x) \le M H\_{\rm avg}(x) \\,,$$ where Clearly $$n H\_{\rm avg}(x) \ge \sum\_{v \in S^c} H(v,x) \ge |S^c|\cdot M H\_{\rm avg}(x) \\,,$$ so $|S^c| \le n/M.$

Given a starting node $u \in V$, denote by $\tau\_{S}$ the first time the random walk from $u$ visits $S$, and let $H(u,S):=E\_u\[\tau\_{S}\]$ be its expectation (which is $0$ if $u \in S$, the interesting case will be $u \in S^c$.)

Consider the graph $G^\*$ on |S^c|+1 nodes, obtained from $G$ by contracting all nodes in $S$ to a single supernode s. Then $H(u,S)$ in $G$ is the expected hitting time $H^\*(u,s)$ in $G^\*$ from $u$ to $s$, which is well known to be at most $ |S^c|^3$. See, e.g., \[1\] for the slightly weaker bound $(|S^c|+1)^3$. In fact, one can multiply this upper bound by $4/27+o(1)$, see \[2\], but we will not worry about optimizing the constants. A related stronger result on exploration time is in \[3\].

Then the strong Markov property at time $\tau\_S$ implies that $$H(u,x) \le H(u,S)+\max\_{v \in S} H(v,x) \le (n/M)^3+M \cdot H\_{\rm avg}(x) $$ $$\le \Bigl((n/M)^3+M\Bigr) \cdot H\_{\rm avg}(x) \\,. \tag{1}$$ (We may assume that $ H\_{\rm avg}(x) \ge 1$, otherwise $G$ is a star.)

To minimize the right hand side of $(1)$, without optimizing the constants, choose $M=n^{3/4}$. We conclude that $ \max\_{u \in V} H(u,x) \le 2n^{3/4} \cdot H\_{\rm avg}(x) \\,. $$ $$ \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \Box$

\[1\] https://www.yuval-peres-books.com/markov-chains-and-mixing-times/
https://pages.uoregon.edu/dlevin/MARKOV/mcmt2e.pdf Proposition 10.16 page 134.

\[2\] Brightwell, Graham, and Peter Winkler. "Maximum hitting time for random walks on graphs." Random Structures & Algorithms 1, no. 3 (1990): 263-276.

\[3\] Barnes, Greg, and Uriel Feige. "Short random walks on graphs." In Proceedings of the Twenty-Fifth annual ACM symposium on Theory of computing, pp. 728-737. 1993. See Theorem 1.

---
Tags: probability-theory, randomness, markov-chains, random-walks
---


# Question
Title: An intuitive explanation of "provably complex combinatorial games"
It is very surprising to me that some combinatorial games such as generalized chess are EXPTIME complete. I have no idea why having a solver for a combinatorial game allows you to solve arbitrary exponential problems. The reason is that while I understand that such games can be solved in exponential time, they seem to me to be a quite *specific* exptime problem, and I cannot see how exptime problems that are unrelated to games would be reducible to them (whereas the fact that CSAT, SAT, 3SAT etc are NP-complete is much more clear to me).

In particular I would like to see a "direct" proof, where arbitrary exptime problems are encoded as instances of some combinatorial game. Hence I tried to read the original paper "Provably Difficult Combinatorial Games" by Stockmeyer and Chandra. However it is quite dense. It would be helpful if there is an intuitive simple (possibly a bit handwavy) description of a reduction of arbitrary EXPTIME problems to a combinatorial games.

**EDIT**: It would suffice to give a simple description of the reduction of "does DTM M halt in k steps?" to such a combinatorial game, as pointed out in the comments. That this is possible is equally surprising to me as the original problem

**EDIT 2**: Just to give a sense of what I find surprising about this: I would have guessed that such games are at best PH-Complete, since a game essentially checks a question of the form $\forall x\_1,\exists y\_1, \forall x\_2 ....Win(x\_1,y\_1,...y\_k)$. This is the whole point of game semantics.

# Answer
As you already see, the essence of the two-player games is *alternation*. The class of languages recognized by an alternating Turing machine in polynomial time $\mathrm{APTIME}$ is equivalent to the $\mathrm{PSPACE}$, the class of languages recognized by a polynomial-space Turing machine.

The $\mathrm{APTIME}$ class corresponds to games that can only last for a polynomial number of turns. This restriction is valid for permanent token-placing games such as Hex or M,n,k-game (a generalization of tic-tac-toe).

However, other games such as Checkers or generalized chess can last for an exponential number of non-repeating turns. Therefore, it is more appropriate to use $\mathrm{APSPACE}$, the class of languages recognized by an alternating Turing machine using polynomial space.

Now, the question is how to prove $\mathrm{APSPACE}$ is equivalent to $\mathrm{EXPTIME}$, the class of languages recognized by a deterministic Turing machine in exponential time. The direction $\mathrm{APSPACE} \subseteq \mathrm{EXPTIME}$ can be shown by a brute-force search algorithm. For the other direction, given a deterministic Turing machine $M$ and an input $I$, define propositions:

* $P^1\_t(i,q)$: "at step $t$, the head of the Turing machine is position $i$ and the internal state is $q$".
* $P^2\_t(i,a)$: "at step $t$, the content of the tape cell $i$ is alphabet $a$".

Then, it is $\mathrm{EXPTIME}$-hard to determine $P^1\_t(0,q\_f)$ given the terminating state $q\_f$ and time $t$ encoded in binary.

Now, we can show that the propositions $P^1\_t$s and $P^2\_t$s can be represented by a Boolean formula, where leaves of the formula are $P^1\_{t-1}$s and $P^2\_{t-1}$s. Namely, for $t \> 0$, $$ \begin{align} P^2\_t(i,a) \iff & P^2\_{t-1}(i,a) \land \not \exists q, P^1\_{t-1}(i,q) \\ \lor & \exists b, P^2\_{t-1}(i,b) \land \exists q, P^1\_{t-1}(i,q) \land \delta(q,b) = a \end{align} $$

where $\delta(q, a)$ is the symbol written to the cell after the transition of the Turing machine with the internal state $q$ and the cell alphabet $a$. The formula for $P^1\_t$ is left to readers.

Furthermore, this Boolean formula can be constructed in $O(\mathrm{poly}(|M| + |I| + \log i))$ time. Therefore, the proposition $P^1\_t(0,q\_f)$ can be determined by an alternative Turing machine using $O(\mathrm{poly}(|M| + |I| + \log t))$ space by using the formulae recursively, concluding $\mathrm{APSPACE} = \mathrm{EXPTIME} \\; \Box$.
> 4 votes

# Answer
Let me put a few ideas about the chess, to start from:

* The main course of any game is to win. So assuming that both players will do best to prevent win or loose is against the logic of game and asks different question. **What will be the complexity of not getting winner?** instead of **Complexity of winning?**
* Since chess players have a goal to win, the next thinking step is define what does this means. Specifically in chess this means winning material (take figures). And material is a target for your algorithm.
* So eventually chess algorithm will be focused on winning material (not the game itself, taking figures one by one based on priority) - winning the game is consequence of winning material
* As a result of that **the move of a figure** is decision tree, where you can through many leaf's without analysing since they have same outcomes (useless moves no hits, or same positions after a course of 5-6 moves) do the best choice. You still get a lot, and as more steps you analyse as more combinations you have, **and each next will include previous**. Let's have a look practically: 1 move will be for ex 20 combinations, respond similarity 20, and the next one ~30. We should be able to see that number of moves have **direct dependency on number of empty spaces on the board and figure capabilities** (task have limits and those are clear).

So the task is polynomial-time many-one reduction, because estimation of complexity of each next move will include estimation of complexity of previous move. Since instead of re-evaluation, you can reuse (i.e transform).

Now let's analyse reverse question, making sure that nobody wins - in the same way we can consider that both players will make sure that targets/materials are not hit, with all consequences.

Hope that helps :)

PS: I skipped chess tactic for simplicity.
> 0 votes

---
Tags: complexity-theory, np-complete, reductions
---


title: Average vs Worst-Case Hitting Time

text:
# Question
Title: Average vs Worst-Case Hitting Time
Consider a simple random walk on an undirected graph and let $H\_{ij}$ be the hitting time from $i$ to $j$. How much bigger can $$ H\_{\rm max} = \max\_{i,j} H\_{ij}, $$ be compared to $$ H\_{\rm ave} = \frac{1}{n^2} \sum\_{i=1}^n \sum\_{j=1}^n H\_{ij}.$$ For all the examples I can think of, these two quantities are of roughly the same order of magnitude.

To make this into a formal question, define $$\phi(n) = \max\_{\mbox{undirected graphs with } n \mbox{ nodes }} \frac{H\_{\rm max}}{H\_{\rm ave}}.$$ How fast does $\phi(n)$ grow with $n$?

# Answer
> 2 votes
The quantity $\phi(n)$ grows like $\Theta(n)$.

For the lower bound, consider the following graph: a clique on $m$ vertices connected to a path of length $k = C\log m$ for an appropriate $C$ (so $n = m + k \approx m$), in which each vertex of the path is also connected to the first vertex of the path (the one incident to the clique). The maximal hitting time is some large number $M = \exp(k)$. The hitting time of two vertices in the clique is around $m \ll M$. The hitting time of a vertex on the path and any other vertex is at most $M$. So the average hitting time is at most roughly $m + \frac{2kn}{n^2} M = O(kM/n)$. In fact, the hitting time of a vertex at distance $t$ from the clique is roughly $\exp(t)$ (for $t \gg \log m$), and if we take this into account then we get an average hitting time of roughly $m + \sum\_{t=1}^k \frac{2n}{n^2} \exp(t) = O(M/n)$. This shows that $\phi(n) = \Omega(n)$.

For the upper bound, let $H\_{ij}$ be the maximum hitting time. The triangle inequality shows that for each $k$, either $H\_{ik} \geq H\_{ij}/2$ or $H\_{kj} \geq H\_{ij}/2$. So at least $n/2$ of the hitting times are at least $H\_{ij}$, showing that the average hitting time is at least $H\_{ij}/n$. This shows that $\phi(n) = O(n)$.

# Answer
> 3 votes
This is an addendum to the answer by Yuval Filmus. Indeed $\phi(n)=\Theta(n)$, and the upper bound is explained in that answer. I don't understand the argument for the lower bound given there, but a simpler graph will yield the required bound. Let $G$ consist of a clique of $n-1$ vertices, where one of them, say $x$, is connected to one additional vertex called $y$. Let $f(v):= E\_v \tau\_y=H(v,y)$ denote the expected hitting time from $v$ to $y$. Then, by conditioning on the first step and using symmetry, $$ \forall v\notin\\{x,y\\}, \quad f(v)=1+\frac1{n-2} f(x) +\frac{n-3}{n-2} f(v)$$ and $$f(x)=1+\frac{n-2}{n-1} f(v) \\,.$$ Solving these linear equations gives $f(v)=(n-1)^2$ and $f(x)=n^2-3n+3$. On the other hand, only $n-1$ of the $n(n-1)$ mean hitting times are of order $n^2$, (namely when the target is $y$). The mean hitting time of every target vertex in the clique is less than $2n$, so $H\_{\rm ave}=O(n)$.

---
Tags: probability-theory, markov-chains, random-walks
---


# Question
Title: How long a graph random walk takes to hit every vertex?
I have a simply connected graph $G$. I start at a uniformly randomly chosen vertex, and from there, randomly walk through the graph by choosing a random edge to follow at each step.

On average, how many steps $T$ until the random walk hits every vertex? Can this be efficiently computed?

Here are some cases for which I'd like the question answered (from most general to least general). The more general the case you can solve, the better.

1. $G$ is a directed weighted graph, and an edge is chosen w.p. proportional to its weight.
2. $G$ is an undirected weighted graph, and an edge " " "
3. $G$ is a directed graph.
4. $G$ is an undirected graph.
5. $G$ is a tree.

For bonus points, it'd be cool if you could say something about the distribution of $T$. E.g. is there a chernoff-style bound like $\Pr\[T\geq t\]\leq e^{-t/\tau}$? What is the variance of $T$? Etc.

All I can easily think of is the following: compute the transition matrix $P$ for the random walk by normalizing rows of the adjacency matrix $A$. Its highest eigenvalue will be 1, and second-highest eigenvalue will be $\lambda\_2$. The random walk will converge to its stationary distribution roughly exponentially at a rate (time-scale) of $\frac{1}{\lambda\_2}$. At the stationary distribution, each node will have positive probability (because $G$ is connected). So I imagine that $T$ will, at worst, be on the order of $\frac{1}{\lambda\_2}$.

# Answer
The cover time is at most the maximal hitting time multiplied by the harmonic number $1+\ldots+1/n$. This is the Mathews bound, see, e.g., Section 11.2 in \[1\].

In fact, the cover time can be estimated up to a constant factor deterministically in polynomial time. See \[2\], where the history of the problem is also discussed.

\[1\] https://www.yuval-peres-books.com/markov-chains-and-mixing-times/ https://pages.uoregon.edu/dlevin/MARKOV/mcmt2e.pdf

\[2\] Ding, Jian, James R. Lee, and Yuval Peres. "Cover times, blanket times, and majorizing measures." In Proceedings of the forty-third annual ACM symposium on Theory of computing, pp. 61-70. 2011.
> 2 votes

---
Tags: graphs, probability-theory, graph-traversal, markov-chains, random-walks
---


# Question
Title: Why scopes in general do not have prologue and epilogue instructions?
Data only accessible in a scope, seems to still be maintained by the stack. What is the reason that entering and exiting scopes (in general) does not do the same "prologue and epilogue" instructions that are done when entering and exiting functions?

What test1 and test2 show, in test2 8 byte is allocated in the stack, but it has already left the scope for `int a` when declaring `int b`. The ISA is x86 (compiled on godbolt.org with x86-64) but I assume this behavior might exist in many different standards, and ask from a more general computer science point of view.

```
void test1(){
    int a;
    { a = 141; }
    a = 257;
}

test1():
    push    rbp
    mov     rbp, rsp
    mov     DWORD PTR [rbp-4], 141
    mov     DWORD PTR [rbp-4], 257
    nop
    pop     rbp
    ret

void test2(){
    { int a = 141; }
    int b = 257;
}

test2():
    push    rbp
    mov     rbp, rsp
    mov     DWORD PTR [rbp-4], 141
    mov     DWORD PTR [rbp-8], 257
    nop
    pop     rbp
    ret

```

# Answer
You have made an assumption about scopes in the C language which is not correct.

Unlike general Algol family languages, C does not have infinitely nested scopes for every statement block. Although your have used the brackets `{}` inside a function, you have not created a new scope. the only scope present is that of the function, and the prologue and epilogue only exist to create new scopes for the function itself.

In languages that have more generalised scoping rules that permit classes inside classes and functions nested inside functions and blocks are the equivalent of anonymised functions, then yes your would have a new scope. However not in the language you chose to do your test. In, say Algol 68, you would have made a new scope like you were trying to test!
> 1 votes

# Answer
At every point in time, the space on the stack must be large enough to handle all variables that are in scope. And you generally don't want to use more stack space than needed to avoid wasting space.

Now lets say you required 104 bytes of stack space before entering a scope, and 108 bytes are required within the scope. If you make the stack space always 108 bytes you waste 4 bytes of stack space while not in scope. However, if you need to change it from 104 to 108 bytes, you need instructions to increase, and then to decrease the stack size, and these instructions take space as well. These instructions even take space if you never enter the scope, or the whole function.

So its a balancing act: Do you want to save stack space, or do you want to save instructions? Having "int a;" vs. "int a\[10000\];" in the scope would make a huge difference.
> 1 votes

---
Tags: cpu, assembly, instruction-set
---


title: Question about Markov Chains

text:
# Question
Title: Question about Markov Chains
The following question is taken from the book titled **"Probability models for Computer Science"** written by Sheldon M. Ross.

Question:

A particle moves along **n + 1** vertices that are situated on a circle in the following manner. At each stage the particle moves one step that is either in the clockwise direction with probability **p** or in the counter-clockwise direction with probabiity **1-p**.

Starting at a specified state let **T** denote the time of the first return to that state. Now how to find the probability that the particle has visited all the vertices by time **T**

# Answer
First suppose that $p \ne 1/2$, and let $q=1-p$. If the first step is clockwise, then the problem is a gambler's ruin problem, and the chance of success (visiting all nodes) is $$\frac{1-q/p}{1-(q/p)^{n+1}} \\,,$$ See \[1\] or \[2\], section 17.3 or \[3\]. If the first step is counterclockwise, then the chance of success is $$\frac{1-p/q}{1-(p/q)^{n+1}} \\,.$$ Thus overall, the probability that the particle has visited all the vertices by time $T$ is $$p\frac{1-q/p}{1-(q/p)^{n+1}}+q \frac{1-p/q}{1-(p/q)^{n+1}} \\,. \tag{\*}$$

If $p=1/2$ then again there is a reduction to a gambler's ruin problem, so by \[1\] or \[2\] Section 2.1, or \[3\], the answer is 1/(n+1). This answer can also be obtained by taking the limit as $p \to 1/2$ in $(\*)$.

\[1\] Feller, W. 1968. An introduction to probability theory and its applications, third edition, Vol. 1, Wiley, New York. Chapter XIV

\[2\] https://www.yuval-peres-books.com/markov-chains-and-mixing-times/

\[3\] Grinstead, C. and L. Snell. 1997. Introduction to Probability, 2nd revised edition, American Mathematical Society, Providence. Chapter 12.
> 2 votes

# Answer
Here is the idea. Let the vertices be $v\_0,\ldots,v\_n$, where $v\_0$ is the origin and the vertices are arranged in clockwise order. The first step is either clockwise or counterclockwise — let's say clockwise. Then the probability you're after is the probability that you reach $v\_n$ before you reach $v\_0$, starting at $v\_1$. This is random walk on a line, so you should be able to analyze it.
> 1 votes

---
Tags: probability-theory, markov-chains
---


# Question
Title: Is there a PRNG that visits every number exactly once, in a non-trivial bitspace, without repetition, without large memory usage, before it cycles?
PRNGs (pseudorandom number generators) generally have a bit length for the binary numbers they generate (e.g. 32 bits, 64 bits). This is the universe of their possible numbers.

It seems that they typically cycle when they reach their 2^bitlen number.

Is there one that, before it cycles, will generate each possible number in its universe, exactly once, without repetition, for larger bitspaces (e.g. 64, 128, 256), without large memory requirements (such as storing numbers generated so far, or a shuffled list of future numbers).

Another way to put this: Is there an algorithm than exhaustively “traverses” or “visits” each binary number in a bitspace, exactly once, in a pseudorandom order? (with large bitspace and low memory usage, as above)

EDITS:

I now have the impression that, while PRNGs do typically eventually cycle (repeat their sequence), the point at which one cycles is specific to the algorithm, and is usually NOT after 2^bitlen numbers (where bitlen is the size in bits of their binary output). Please correct this if wrong.

I expect that a PRNG is still a PRNG if it generates a duplicate number (within its period, before it cycles), or if it never generates (within its period) some numbers that are possible in the bitspace of its output. I'm not looking for these kinds.

I'm looking for an algorithm that works as if it's just reading off N-bit binary numbers from a massive randomly-shuffled list of all N-bit binary numbers, but without the massive memory requirement of such a list.

I'm interested in algorithms meeting this criteria that are pseudorandom in a cryptographically-secure way, and also those not cryptographically-secure that are quicker or simpler.

# Answer
Sure. Pick a block cipher (i.e., pseudorandom permutation), $E\_K$, and a random key for it, $K$. Let $x\_i=E\_K(i)$. Then this has the properties you are looking for.

## Short explanation:

As the block cipher $E\_K$ maps each *n*-bit value uniquely to another *n*-bit value, all the resulting values must be different for different input values. Effectively that means $E\_K$ creates a permutation of *n*-bit values that can be varied by changing $K$.
> 39 votes

# Answer
A linear-feedback shift register (LFSR) is a terrible PRNG(\*), but (with correct selection of feedback taps) it seems to meet all your qualifications.

A LFSR can run extremely fast -- faster than standard natural binary counters.

> Is there one that, before it cycles, will generate each possible number in its universe, exactly once, without repetition, for larger bitspaces (e.g. 64, 128, 256), without large memory requirements (such as storing numbers generated so far, or a shuffled list of future numbers).

With a proper selection of feedback taps, a standard n-bit LFSR produces a "maximum length sequence", producing 2^n-1 output values (all possible output values, except for the all-zeros value, without repetition until it cycles back to the first value). There are a variety of techniques for tweaking the system to add that one final value all-zeros, so it produces all possible n-bit values. The only memory required is the n-bit current state of the LFSR. (A little more memory may be required if you want it to halt after it's cycled through all 2^n-1 values without repetition).

For example (based on http://users.ece.cmu.edu/~koopman/lfsr/ ):

```
#include <stdint.h>
#include <inttypes.h>
// David Cary
uint64_t next_LFSR64(){
  static uint64_t i = UINT64_C(1); // or any other non-zero value
  #define feed (UINT64_C(800000000000000D)
  // a few other special values of feed will also produce MLS, including:
  // #define feed (UINT64_C(800000000000000E)
  // #define feed (UINT64_C(800000000000007A)

  if (i & 1)  { i = (i >> 1) ^ feed; }
  else        { i = (i >> 1);       }
  return i;
};

```

will produce a maximum-length sequence of all possible 64-bit values (except the 0 value) without repetition until it cycles back to the initial value.

In principle (from a table from Roy Ward and Tim Molteno), a feedback term of

```
const uint256_t feed =
    (UINT256_C(1)<<255) +
    (UINT256_C(1)<<253) +
    (UINT256_C(1)<<250) +
    (UINT256_C(1)<<245); // warning: untested.
static uint256_t i = UINT256_C(1); // or any other non-zero value

```

would in theory produce all possible 256-bit values except all-zeros, but of course our Sun won't last that long.

(\*) From a cryptographic point of view, we want random-number generators and PRNGs to generate numbers that are very difficult for any attacker to guess ahead of time, even if that attacker has seen the previous thousand or so output values of that generator. The Berlekamp-Massey algorithm makes it easy to guess the next output of a LFSR given practically no information about the size of the LFSR and surprisingly few output values of the LFSR. Fortunately for cryptographers, cryptographically strong PRNGs exist which are immune to the Berlekamp-Massey algorithm. For example, all good stream ciphers use cryptographically strong PRNGs.
> 20 votes

# Answer
The *period* of a PRNG is how many random numbers you can generate before the sequence starts to repeat. If you don't mind using lower-quality PRNG algorithms, some classic ones (which fell out of favour for good reason) have short periods; for example **an LCG can be constructed with any period you want, even for non-power-of-2**.

---

Good quality PRNGs have a period much larger than the bit-space of their output. (Their internal state is wider than one output.) e.g. at least a couple words for a 1-word output, like for fast modern PRNGs such as the xorshift family.

The Mersenne Twister (the usual recommendation for C++: `std::mt19937`) has a famously large amount of state to initialize and manage, giving it a period of 219937 − 1. A large period is not the only figure of merit for a PRNG, but a short period is a serious flaw. (https://prng.di.unimi.it/ discusses various factors of PRNG quality, and has a comparison table of periods and which statistical tests are passed/failed by various PRNGs.)

For a PRNG with `n` bits of internal state, the maximum possible period is 2n, iterating through every internal state once before repeating. If the output is the entire state, achieving that maximum-period goal would mean generating each number exactly once, which is your requirement. (And some constructions do, although an LFSR can't generate 0).

But then they'd generate each number again *in the same order*. More interesting would be a PRNG that could sample every integer in its output range without replacement, and then do it again *in a different order*, and not just from a different starting point. That's non-trivial.

---

There are multiple crusty old PRNG algorithms which used to be used to implement functions like C `rand()` or `random()` which can return their whole state, and have maximal periods for that state.

The linear congruential generator is probably the most famous, where `seed = (seed * a + c) % m;` / `return seed;`

### Generating 0 .. m-1 in a pseudo-random order without replacement

Interestingly, **an LCG can be constructed with period `m` for any `m`**. In some cases the sequence isn't very random, e.g. having some obvious patterns in the way they traverse the numbers from 0..m-1, at least with the way I chose to select `c` and `a` that would ensure a period `m`

I used this once, when low-quality randomness was acceptable (because nearby integers often had different-enough effects). I just wanted some permutation of the numbers in a 0..n range for rearranging trees via subtree pruning-regrafting aka SPR, to search for a maximum-likelihood tree in phylogenetics. This was a half-finished library that I shared **on Github** (GPLv2) in case pieces of it were useful.

I don't know if there are better algorithms for doing this for a non-power-of-2 period; this is just what I came up with many years ago, in about 2006. Another option would be to do something with a period somewhat too long, and discard out-of-range samples. (That could allow avoiding very low-randomness LCGs; see the comments in the code about some bad cases, like when `m` has no repeated prime factors.)

**I constructed an LCG with `m` = the desired period (and output range), and chose `c` and `a` in a way that created a maximal-period LCG for that modulus**. Knuth's The Art of Computer Programming was a useful resource for this.

```
// GPLv2, copyright Peter Cordes, written in 2006-2007 at Dalhousie University
// while running the computers for the phylogenetics group (math/stats/biology)

struct lcg {
    unsigned int state;
    unsigned int a, c, m;
    unsigned int startstate;
};

int is_prime(int p);     // these do what the name implies
int next_prime (int i);  // see lcg.c on github for the implementation I copied

/******************** Linear Congruential Generator setup ************/
/* to generate all possible SPRs in a pseudo-random order, we generate
 * all the numbers between 0 and the number of possible SPRs once each
 * without repetition using an LCG of the form: x_n+1 = x_n*a + c mod m.
 */
/*
 * Knuth: TAOCP 3.2.1: ex 2: if a and m are relatively prime,
 * the number X_0 will always appear in the period.  (will return to start?)
 *
 *  3.2.1.2: Theorem A: An LCG will have period m iff:
 *   -  c is relatively prime to m
 *   -  b = a-1 is a multiple of p, for every prime p dividing m
 *   -  b is a multiple of 4, if m is a multiple of 4
 *
 *  3.2.1.3: ex 4:  m = 2**e >= 8  ->  maximum potency when a mod 8 = 5.
 *   small multipliers are to be avoided.
 *
 * Numerical recipies suggests c = a prime close to (1/2 - sqrt(3)/6)*m
 */

/* make up some parameters for an LCG that will have the maximum period
 * equal to the range, so every value is generated once.
 * When maxval doesn't have any repeated prime factors, a = m+1,
 * which is the same as a=1.  It's not exactly random, but it does still
 * mix up which SPRs are done.
 */

void findlcg(struct lcg *lcg_params, int maxval)
{
    unsigned int a, b, c, m = maxval;
    int i;

    primesetup (maxval+maxval/2);

    if (m<=6){ // will be either 6 or 2.  Just loop in order
        b=0;
        c=1;
    }else{
        int divlimit = m;
        b=1; // b must be a multiple of all of m's prime factors
        if (!(m%2)){
            b=2;
            while (divlimit%2 == 0) divlimit /= 2;
        }
        for (i=3 ; i <= divlimit ; i+=2){
            if (is_prime(i) && m%i == 0){
                b *= i;
                while (divlimit%i == 0) divlimit /= i;
            }
        }

        if (!(m%4)){    // if m is a mult of 4, b must be.
            while (b%4) b *= 2;
        }

        /* make sure a isn't too small */
        while (b<sqrtf(m)) b*=7;

        if (b == m) b=0;  // just give up and avoid overflow

// Numerical Recipies says there is "lore" behind this... :)
// TAOCP says it's useless unless the multiplier sucks (section 3.3.3, eq. 40)
// That would be us.
        c = next_prime(max(5, (0.5 - sqrtf(3)/6.0)*m - 2));
        while (m%c == 0) c = next_prime(c+1);
        // Luckily we don't have to test for c>m, because it doesn't
        // happen with any m<100, and there are enough primes later...
/* I've observed that when a == m, (e.g. a=13, c=13, m=72) you often get
 * two consecutive numbers...  Do something to avoid that if it's a problem */
    }

    a = b+1;

    unsigned long long l = (unsigned long long)a * m;
    if (l > ULONG_MAX){
        fprintf(stderr, "spr: chosen Linear Congruential Generator is bogus\n"
        "   x_n+1 = x_n*%u+%u mod %u\n"
        "   a*m > ULONG_MAX, so it would overflow :(\n", a, c, m);
    }

    lcg_params->a = a;
    lcg_params->c = c;
    lcg_params->m = m;
    lcg_params->startstate = UINT_MAX;
    lcg_params->state = rand() % m;    // Linux/glibc rand() is not terrible
}

```

The actual PRNG function.
I didn't bother with any tricks to speed up the `%m` part; this was good enough for a first version.

```
// startstate = UINT_MAX means we've just started
// UINT_MAX as a return value means we've looped.
unsigned int lcg(struct lcg *lcgp) {
    // use long just to avoid overflow on multiply
    unsigned long a = lcgp->a, c = lcgp->c, m = lcgp->m;
    unsigned long old = lcgp->state;

    if (lcgp->startstate == UINT_MAX)
        lcgp->startstate = old;
    else if (old == lcgp->startstate)
        return UINT_MAX;
    // will continue to return this until startstate is reset

    lcgp->state = (a*lcgp->state + c) % m;
    return old;
}

```

With `m` being a power of 2type\_width, the modulo is just binary truncation an happens for free. But that results in the low bits of the value having a very short period, e.g. alternating odd/even for the low bit.

Some LCG implementations use a wider state, like 48-bit, and return the high 32 bits of that. So the lowest bit returned doesn't have that short-period problem. (But then you wouldn't have the period = 2output\_width property you're looking for.)
> 11 votes

# Answer
What is your intended application?

Apart from PRNGs, there are also quasirandom sequence generators. They are (almost certainly) not cryptographically secure, but have other desirable properties. From mathworld:

> A sequence of n-tuples that fills n-space more uniformly than uncorrelated random points, sometimes also called a low-discrepancy sequence. \[...\] useful in computational problems where numbers are computed on a grid, but it is not known in advance how fine the grid must be to obtain accurate results. Using a quasirandom sequence allows stopping at any point where convergence is observed, \[...\]

They are useful in numerical integration, for example.
> 4 votes

---
Tags: pseudo-random-generators
---


title: How to prove that P = NP?

text:
# Question
Title: How to prove that P = NP?
So if someone proves with an algorithm that SAT can be solved in deterministic polynomial time, then P = NP and that's it?

# Answer
Yes, that would be it – just as if someone had found $a,b,c,n\>2$ satisfying $a^n+b^n=c^n$, that would have been it for Fermat's last theorem.

No one ever found such numbers, and the reason turned out to be that there aren't any: the conjecture was true. It seems likely that the reason no one has found a polynomial-time SAT solver after all these decades is also that there aren't any.

There are barriers to proving P=NP. In particular, the famous relativization barrier applies to proofs of P=NP as well as P≠NP. But I don't know whether that implies that a polynomial-time algorithm is hard to find, or just means that any algorithm that you did find would, in fact, not relativize as a proof.

It might also be possible to prove P=NP nonconstructively, i.e., without presenting any particular algorithm. But it's easy to prove that a SAT solver that simulates all Turing machines in parallel until one of them produces a correct answer completes in polynomial time if P=NP, so we would still know a polynomial-time SAT solving algorithm in that case, though it's utterly useless because of the astronomical constant factor.
> 3 votes

---
Tags: satisfiability
---


# Question
Title: "Hack computer" from Nand2Tetris registers, any real world examples of similar design?
The "Hack CPU" (Wikipedia/Hack\_computer) is a theoretical computer design created by Noam Nisan and Shimon Schocken and described in their book and also used in their Coursera course Nand2Tetris, and in the game https://nandgame.com. Their CPU only has two registers, A and D. Both registers are loaded via the output of the ALU. When loading data from memory to either the A or D register, it has to first pass through the ALU. The A register can also be loaded directly from an instruction, and it also holds the addresses used when accessing memory.

This design surprises me a bit since it seems very slow to have to pass through ALU to load the registers. I am interested in if there is any smart rationale behind the design, and if there are real-world examples of CPUs with similar design? Was the design for example common in the early days of computers? Both questions sort of tell me the same thing: is the design any good, or is it just something more like "educational fiction".

Some more context to their "Hack computer", it uses Harvard architecture.

# Answer
> 2 votes
Yes, most CPUs(\*) have an accumulator-based architecture. In fact, most CPUs have the very simplest kind of accumulator-based architecture, the kind used in the "Hack CPU", with an accumulator that can only be loaded from the ALU, and whose output can only go back into the ALU, and one input of the ALU connected only to the accumulator. (The D register is the accumulator of the Nand2Tetris "Hack CPU").

> it seems very slow to have to pass through ALU to load the registers.

Some accumulator-based processors do have additional connections that can read out the accumulator directly or write to the accumulator directly or both, bypassing the ALU. But routing through the ALU (for example, by zeroing one of the inputs and performing an OR operation) does not add significant delay to LOAD or STORE. Leaving out those additional connections generally reduces transistor count and area, simplifies wiring, and so reduces cost. (thanks, Paul A. Clayton).

An integer ALU is completely combinational logic, producing outputs very quickly after new inputs are applied -- less than a clock cycle. So loading a value from memory into the accumulator (which requires passing that data through the ALU), or writing the value in the accumulator out to memory (which also requires passing that data through the ALU) is not any slower than the register file (completely bypassing the ALU) used in more recent CPUs. Both architectures can be designed to take a single memory cycle for a LOAD or a STORE. (The register file does makes some *other* kinds of instructions run faster).

> real-world examples of CPUs with similar design?

* As you can see from any PIC microcontroller architecture block diagram, 8-bit PIC microcontrollers have an accumulator called the "W register" connected exactly the same way.
* The 8085 has an accumulator: "the only way to put a value into the accumulator is through the ALU." -- "Ken Shirriff: Reverse-engineering the 8085's ALU", but it has additional connections to to the ALU that bypass the accumulator. (thanks, user52174)
* The Intel MCS-51 architecture ("8051" and "8031") has historically been popular. Although Intel no longer sells chips with this architecture, lots of other chips with this architecture are still in production. The MCS-51 also has only a single accumulator, although the 8051 / 8031 architecture block diagram shows more complicated and flexible connections.
* The PDP-8 architecture has only a single accumulator. (FIXME: link to diagram).
* The MOS 6502 (still in production as the Western Design Center 6502) has only a single accumulator. (FIXME: link to diagram).
* The Hitachi 6301 had two accumulators.

(\*) In particular, since 2013 Microchip has been shipping a billion CPU chips every year. Most of them are 8-bit PIC microcontrollers with a traditional accumulator-based architecture.

Chips that include the Western Design Center 6502 ship "over a hundred million units per year".

You may be more familiar with computers that have a register file, with many registers that are all more-or-less equally connected to the ALU. In particular, you may be familiar with the x86 architecture (although many people call all of those ALU-connected registers "accumulators", and sometimes call one of those registers "the accumulator"). Since 2020, the number of x86 architecture CPU chips shipped (combined from all manufacturers) is about 350 million per year, so many people incorrectly think it's the top seller, but other CPU architectures sell even more chips per year.

> common in the early days of computers?

As far as I can tell, the accumulator-based architecture is *still* more common in terms of CPUs shipped per year than any other CPU architecture. (It was also common in the early days of computers).

> is the design any good

That's a matter of opinion. Some people can't stand it. Other people love it and say there are still categories where it is "the best". But I would hesitate to call an architecture "bad" when it currently outsells (in terms of CPUs sold per year) all x86 CPUs from all manufacturers combined.

---
Tags: cpu
---


# Question
Title: Communication protocol so that messages are read "synchronously"
Is there a communication protocol that ensures that both parties can read the other one's message at the same time (or at the very least, only after sending their own message, thus no party can read a message and then send their own).

# Answer
> 2 votes
I'm not sure exactly what you're trying to achieve (formulating the goal precisely seems tricky or unclear to me), but you might be interested in reading about "fair exchange" in the cryptographic literature. See, e.g., https://crypto.stackexchange.com/q/8333/351. The short version you're likely to find is that there are no protocols with strong guarantees (without making strong assumptions), but without knowing more context, it's hard to know whether there might be something that is good enough for your needs.

# Answer
> 0 votes
You might be interested in reading about various "commitment schemes" in cryptography.

Commitment schemes are easier to implement than "fair exchange", but make weaker guarantees -- typically they can be designed so two parties send some initial messages (where Alice has initial message A and Bob has initial message B) to guarantee that no party can *read* someone's plaintext and then pretend they composed a message *before* reading that plaintext, when that message was actually composed only *after* reading the other's plaintext.

---
Tags: communication-protocols
---


# Question
Title: Max flow bottleneck approach flow after k iterations
This is a question from a previous exam in Graph theory and algorithms, the correct answer is E but I don't understand why.

Given a network flow $(G,c)$ over graph $G(V,E) $.

Assume we run Edmonds-Karp algorithm to find the max flow with the Max Bottleneck approach.

After $\frac{|E|}{2}$ iterations we decide to stop the algorithm. What is true about the current flow?

1. The flow we found is a maximum flow.
2. The flow we found is at least $\frac{3}{4}$ of the max flow.
3. The flow we found is at least $\frac{1}{2}$ of the max flow.
4. The flow we found could be be as small as we like depending on $c $ and $G$.
5. all above answers are wrong.

In class we proved a lemma that says this ($f^\*$ is the max flow) $$ \left|f^{\*}\right|-\left|f^{k}\right|\le\left(1-\frac{1}{\left|E\right|}\right)^{k}\left|f\right|\implies $$ $$ \left|f^{\*}\right|-\left|f^{\frac{\left|E\right|}{2}}\right|\le\left(1-\frac{1}{\left|E\right|}\right)^{\frac{\left|E\right|}{2}}\left|f\right| $$ now we can use Taylor's approximation for the binomial function and get that: $$ \left|f^{\*}\right|-\left|f^{\frac{\left|E\right|}{2}}\right|\le\left(1-\frac{1}{\left|E\right|}\right)^{\frac{\left|E\right|}{2}}\left|f\right|\approx\left(1-\frac{1}{\left|E\right|}\cdot\frac{\left|E\right|}{2}\right)\left|f\right|=\frac{\left|f\right|}{2}\implies \\ \left|f^{\*}\right|-\left|f^{\frac{\left|E\right|}{2}}\right|\le\frac{\left|f\right|}{2} $$ This means that we can improve our flow by as much as $\frac{|f|}{2} $. Why wouldn't answer C be correct?

# Answer
Let $h(x)=(1-\frac1{x})^{\frac x2}$ for $x\ge2$.
**Claim**: $h(x)\gt\frac12$ if $x\gt2$.

Proof: Let $g(x)=\ln(1-x)+x$ for $0\le x\lt1$.
Since $g'(x)=-\frac1{1-x} + 1 \le 0$, we have $g(x)\ge g(0)=0$.

$h'(x)=\frac12(1-\frac1{x})^{\frac x2}\left(\ln(1-\frac1x)+\frac{1}{x-1}\right)=\frac12(1-\frac1{x})^{\frac x2}\left(g(\frac1x) + \frac1{x(x-1)}\right)\gt0$ for $x\ge2$.
So $h(x)\gt h(2)=\frac12$ for $x\gt2$. $\quad\checkmark$

---

> $$\left(1-\frac{1}{\left|E\right|}\right)^{\frac{\left|E\right|}{2}}\left|f\right|\approx\left(1-\frac{1}{\left|E\right|}\cdot\frac{\left|E\right|}{2}\right)\left|f\right|=\frac{\left|f\right|}{2}$$

The above approximation is misleading, as the claim above implies that $\left(1-\frac{1}{\left|E\right|}\right)^{\frac{\left|E\right|}{2}}\left|f\right|\gt\frac{\left|f\right|}2$ when $|E|\gt2$. Hence, it is impossible to obtain $\left|f^{\*}\right|-\left|f^{\frac{\left|E\right|}{2}}\right|\le\frac{\left|f\right|}{2}$ from the lemma you learned in the class. So, you should not be able to ascertain answer C is correct.
> 1 votes

---
Tags: graphs, network-flow, ford-fulkerson
---


# Question
Title: Semi-bounded probabilistic polynomial-time, is it equal to BPP?
The complexity class $\mathsf{BPP}$ is typically defined as the class of all problems for which:

1. Running an algorithm once takes polynomial time at most.
2. The answer is correct with the probability at least $2/3$.

The complexity class $\mathsf{PP}$, on the other hand, has $1/2$ instead of $2/3$ in the second constraint. Now, we can create a class that lies between them:

1. Running an algorithm once takes polynomial time at most.
2. The answer "YES" is correct with the probability at least $2/3$.
3. The answer "NO" is correct with the probability at least $1/2$.

Is this complexity class equivalent to $\mathsf{BPP}$? If this is not known, is it in $\mathsf P/poly$ at least?

# Answer
Your class is the same as BPP. If you run your algorithm $n$ times, then in the YES case, the expected number of YES answers is at least $(2/3)n$, while in the NO case, the expected number of YES answers is at most $(1/2)n$. Moreover, both of these values are concentrated by Chernoff bounds. Therefore if you answer YES if you see at least $0.6n$ many YES answers, then you get the correct answer with exponentially small error probability.
> 2 votes

---
Tags: complexity-theory, polynomial-time, probabilistic-algorithms
---


# Question
Title: Is the set of Turing machines that halt on infinitely many inputs not recursively enumerable?
Consider this "generalized halting problem": $$ GHP = \\{\<M\>| \mbox{ there are infinitely many inputs that $M$ halts on}\\}. $$

I'd like to prove that $GHP\notin RE$, but it doesn't seem straightforward easy.

Any ideas?

---

My first thought was to try the opposite: suppose that there were at most $k$ halting inputs. Then we can recognize these inputs (e.g., run all inputs of length $\le i$ for $i$ steps, for $i=0,1,\ldots$, until you find $k$ halting inputs.)

This almost shows that $GPH\in \overline{RE}$, only that we don't know $k$, so I'm not sure how to proceed.

# Answer
In fact, GHP is very far from r.e. - it is $\Pi^0\_2$-complete, meaning that in particular it is strictly more complicated (in the sense of Turing reducibility) than any r.e. set. This includes the halting problem itself; in fact, GHP is Turing-equivalent to "the halting problem's halting problem." Soare's book *Recursively enumerable sets and degrees* contains a proof of this and similar results; there, GHP is called "$\mathsf{Inf}$" instead.

If you just want to show that GHP is not r.e., a "baby" version of the full argument suffices: it's enough to show that the complement of the halting problem is many-one reducible to GHP; this is because no properly $\Pi^0\_1$ set (such as the complement of the halting problem) can ever be many-one reducible to a $\Sigma^0\_1$ (= r.e.) set. To do this we argue as follows: given a machine $M$, let $N\_M$ be the machine which on input $n$ first tests whether $M(0)$ halts within $n$ steps, and halts and outputs $7$ (say) if it doesn't and goes into an endless loop if it does. Crucially, "halts within $n$ steps" **is** something we can computably check, so the construction $M\leadsto N\_M$ actually makes sense. Clearly $N\_M$ halts on infinitely many inputs iff $M(0)$ never halts, so we've reduced the complement of (one version of) the halting problem to GHP.

A more detailed version of this idea gives the general reduction of any $\Pi^0\_2$ set to GHP.
> 2 votes

---
Tags: complexity-theory, computability, halting-problem, recursively-enumerable
---


# Question
Title: LZ-type compression vs. entropy-encoding of BWT data
Why does there seem to be a preference for using Huffman (or Arithmetic) coding instead of a Lempel-Ziv type compression algorithm for Burrows-Wheeler Transformed data?

I noticed that data compressors such as Bzip2 or ZZip use mainly a combination of BWT, RLE and Huffman/Arithmetic coding. I would like to know what are the reasons against using a LZ-type algorithm instead of entropy encoding.

# Answer
> 0 votes
LZ-type algorithms are useful for data for which context is predictive, like text consisting of lexemes and following some grammar. That is not so for the output of the BWT (nor of the MTF transform which is performed after BWT).

---
Tags: data-compression
---


title: Time reversible Markov chains question

text:
# Question
Title: Time reversible Markov chains question
Let **Q** be a symmetric transition probability matrix on states 1 , . . . , n; that is $q\_{i,j} = q\_{j,i}$ for all *i* , *j*.

Consider a markov chain defined as follows. Whenever the chain is in state *i*, the value of a random variable $X\_i$ with probability mass function $P(X\_i = j)= q\_{i,j}$ is generated; if $X\_i = j,$ then the chain either moves to state *j* with probability $b\_j/(b\_i + b\_j),$ or it remains in state *i* otherwise, where $b\_1,...,b\_n $ are specified positive numbers.

Now how to show that the Markov chain is time reversible with stationary probabilities $$\pi\_j = \frac{b\_j}{\sum\_{i=1}^n b\_i}, j = 1,...,n$$

Any computer science help will be accepted.

Note: This question is taken from **PROBABILITY MODELS for Computer Science** written by Sheldon M. Ross.

# Answer
> 2 votes
For this chain, the transition probabilities for $j \ne i$ are are $$p\_{ij}=q\_{ij}\\,\frac{b\_j}{b\_i+b\_j}\\,.$$ Thus $\pi\_i=b\_i/Z$ satisfy $$\pi\_i p\_{ij}=\frac{b\_ib\_j}{Z(b\_i+b\_j)}=\pi\_j p\_{ji}\\,,$$ which is the equation defining reversibility.

---
Tags: matrices, markov-chains
---


# Question
Title: Proving that the cover time for graph is exponential in the worst case
How can I prove that the cover time for a directed graph $G$ can be exponential in the size of $G$?

The cover time is the expected length of a random walk that visits all vertices.

# Answer
You do it in two steps:

1. First you think of a graph which you can expect to be difficult.
2. Then you prove your suspicion.

Let's start with the first step - do you have any graph in mind?
> 4 votes

# Answer
If the digraph is not strongly connected, then the cover time is infinite, so let's assume the digraph is strongly connected. Here is an example: Consider $n\>2$ vertices $v\_1,\ldots,v\_n$, with a directed edge from $v\_i$ to $v\_{i+1}$ for $i=1,\ldots,n-1$ and a directed edge from $v\_j$ to $v\_1$ for $j=2,\ldots,n$. Starting from $v\_1$, the number of visits to $v\_1$ before reaching $v\_n$ has a geometric distribution with parameter $2^{2-n}$, so the expected hitting time from $v\_1$ to $v\_n$ (which is a lower bound for the cover time) is at least $2^{n-2}.$
> 1 votes

---
Tags: algorithms, graphs, random-walks
---


# Question
Title: Given $n$ unique items and an $m^{th}$ normalised value, compute $m^{th}$ permutation without factorial expansion
We know that the number of permutations possible for $n$ unique items is $n!$. We can uniquely label each permutation with a number from $0$ to $(n!-1)$.

Suppose if $n=4$, the possible permutations with their labels are,

```
0:  1234
1:  1243
2:  1324
3:  1342
4:  1432
5:  1423
6:  2134
7:  2143
8:  2314
9:  2341
10: 2431
11: 2413
12: 3214
13: 3241
14: 3124
15: 3142
16: 3412
17: 3421
18: 4231
19: 4213
20: 4321
21: 4312
22: 4132
23: 4123

```

With any well defined labelling scheme, given a number $m, 0 \leq m \< n!$, we can get back the permutation sequence. Further, these labels can be normalised to be between $0$ and $1$. The above labels can be transformed into,

```
0:       1234
0.0434:  1243
0.0869:  1324
0.1304:  1342
0.1739:  1432
0.2173:  1423
0.2608:  2134
0.3043:  2143
0.3478:  2314
0.3913:  2341
0.4347:  2431
0.4782:  2413
0.5217:  3214
0.5652:  3241
0.6086:  3124
0.6521:  3142
0.6956:  3412
0.7391:  3421
0.7826:  4231
0.8260:  4213
0.8695:  4321
0.9130:  4312
0.9565:  4132
1:       4123

```

Now, given $n$ and $m^{th}$ normalised label, can we get the $m^{th}$ permutation while avoiding the expansion of $n!$ ? For example, in the above set of permutations, if we were given the $m^{th}$ normalised label to be $0.9$, is it possible to get the closest sequence `4312` as the answer without computing $4!$ ?

Cross-posted from Math.SE: https://math.stackexchange.com/q/3743499/14578

# Answer
Well, from the clarifications made in the comments, then this could be a solution.

I haven't checked for correctness. Specifically the requirement of choosing the closest label to the one input. I think I am taking the one immediately below the number input. Probably that can be fixed by using closest integer, instead of floor below.

Let $L=L\_1$ be the input label, which is a real number. Maybe we can just assume that it is in $\[0,1\]$.

We begin with the full collection of numbers say $C\_1=\\{1,2,3,...,n\\}$ from where one will be eliminated at each step.

In the first step we compute $a\_1=\lfloor L\_1\cdot n\rfloor$. We pick the $a\_1$-th element $p\_1$ of $C\_1$ to be the first element of the permutation and remove it form $C\_1$. So, define $C\_2=C\_1\setminus\\{p\_1\\}$. Define $L\_2=L\_1\cdot n-a\_1$.

Continue in this way, in the $k$-th step, for $k=2,3,...,n$, put $a\_k=\lfloor L\_k\cdot (n-k+1)\rfloor$, take $p\_k$ to be the $a\_k$-th element of $C\_k$ and define $C\_{k+1}=C\_k\setminus\\{p\_k\\}$ and $L\_{k+1}=L\_k\cdot(n-k+1)-a\_k$.

Finish when there are no more elements in $C\_k$, or maybe when there is just one which will be forced to be the last element in the permutation.

---

See also factorial number system. Since this is essentially what we are doing.
> 1 votes

# Answer
While I'm not sure about "closest" this sounds a lot like arithmetic encoding using a uniform distribution for the $n-i$ "characters" at position i (using 0-based indexing for the positions). To simplify the decoding one should encode the indexes and reorder the characters as one goes, e.g. by swapping the encoded character to the end. For example, we initially have the characters in order $\[1, 2, \dots, n\]$ (where each takes up range of size $\frac{1}{n}$). Let's say the first character in the permutation was 2, then we swap it to the end giving $\[1, n, 3, 4, \dots, n-1\]$ as the ordering of the characters for the next encoding. Thus, $n$ would get the second range in this new ordering.
> 1 votes

---
Tags: algorithms, time-complexity, computability, recurrence-relation, permutations
---


# Question
Title: Constructing a data structure for a computer algebra system
In thinking about how to approach this problem I think several things will be required, some tivial:

1. An expression tree where non-leaf node is an operation (not sure if that part is redundant), but not every node has just two children.
2. All nodes for operations have a defined number of children that they must have (some operators are unary (like $!$) while others are binary ($\*,+,-,$ etc) and still other are n-ary ($f(a,b,d)$ and versions with different amounts of variables).
3. All leaf nodes are some type of number

I am under the impression that the tree should not explicitly retain information regarding the order of operations, but rather that information should be used in the parsing stage to insert things into the tree correctly.

This leads to the question, how should inserting to a specific position in the tree be done? Simply passing a list of directions (from root, take node zero, then node 1, etc, then insert) will work, but it seems overly clunky.

Or should I avoid that situation entirely (not talking about editing an equation here, just building a representation of one) by using the fact that in some sense the tree must be complete (all binary operations MUST have two children, etc, and even operators that are seemingly ambiguous (the $\_{^-}$ sign for example) but these ambiguities are resolved before this point. That would all me to insert "in order"

Am I taking a reasonable approach? Does it make no sense whatsoever?

Additionally, are there papers or articles that I should read about CAS systems?

**Clarification:** The tree will need to support three different compound operations.

1. Creation: (from a string, but how to actually do that is beyond the scope of this question)
2. Reduction: (to some type of canonical form) so that if $a+b$ and $b+a$ are both entered and reduced, they will form identical trees.
3. Evaluation: Be able to traverse the tree

These are all the operations that need to be supported. There are probably many other more basic operations that may need to be supported, but in this case it only matters that the three operations above are supported. My understanding is that search for example is not a property that will be required, but deletion will be (of a whole subtree).

# Answer
From the comments OP wrote, I understand he wants to start small. However, we need to think more generally so that the to-be developped CAS can be of real use. Otherwise it is nothing but another calculator. Please see Definition of Computer Algebra System.

My suggestion:

Numbers, elements, sets, operations, etc. are fundermental in algebra. The data structures will have to be about them. In particular, you can start with elementary set theory. Determine what will be an element, a set, etc. The elements should be generic(they can be anything). Abstraction is the key. Then, what are the operations associated with them? Constructing a set, membership test, union, intersection, etc. Once we have them in place, plug in the number manipulation packages to the system is a matter of instantiation.
> 4 votes

# Answer
The most straightforward approach for representing an algebraic expression is a parse tree. However, its big drawback is that it is difficult to reason about. That $xyz = zyx$ and $(xy)^2 = x^2y^2$ is not easy to infer using a normal parse tree. Instead, I suggest using this data structure:

$$ node \leftarrow sum | name | const\\ sum \leftarrow term\_1, \ldots, term\_n\\ term \leftarrow pow\_1, \ldots, pow\_n\\ pow \leftarrow (fun, fun)\\ fun \leftarrow (name, node\_1, \ldots, node\_n) $$

It is a tree that constrains the types of the nodes on each level. The sum's children are terms and the terms' children are factors, and the factors have a pair of functions which serves as the base and the exponent as their children.

To represent an expression, say $x + 2x + \sqrt x$, create the tree:

```
sum(term(pow(fun(id, x), fun(id, 1))),
    term(pow(fun(id, 2), fun(id, 1)),
         pow(fun(id, x), fun(id, 1))),
    term(pow(fun(id, 2), fun(id, 1/2)),
         pow(fun(id, x), fun(id, 1))))

```

The tree is evaluated recursively. To evaluate the sum, create a mapping from the non-constant factors of every term to the sum of its constant factors. If the term has no constant factors, use `term(pow(fun(id, 1), fun(id, 1)))`:

```
{pow(fun(id, x), fun(id, 1)) : sum(
    term(pow(fun(id, 1), fun(id, 1))),
    term(pow(fun(id, 2), fun(id, 1))),
    term(pow(fun(id, 2), fun(id, 1/2))
)}

```

Evaluate all keys values. It is easy since there are no variables in the expression:

```
{pow(fun(id, x), fun(id, 1)) : sum(
    term(pow(fun(id, 3), fun(id, 1))),
    term(pow(fun(id, 2), fun(id, 1/2))
)}

```

Note that $1 + 2 + \sqrt 2 = 3 + \sqrt 2$ which is not a rational number. The next step is to produce a new sum by joining all keys with their values:

```
 sum(term(pow(fun(id, sum(term(pow(fun(id, 3), fun(id, 1)))
                          term(pow(fun(id, 2), fun(id, 1/2)))))),
          pow(fun(id, x), fun(id, 1))))

```

So the result is $(3 + \sqrt 2)x$. Optionally, you can distribute multiplication over addition to get $3x + \sqrt 2 x$.

Evaluation of terms work similarly; you create a mapping from factors to the sums of their powers. E.g $x^2x^3$ would produce the mapping:

```
{fun(id, x) : sum(term(pow(fun(id, 2), fun(id, 1))),
                  term(pow(fun(id, 3), fun(id, 1))))}

```

Then you'd just evaluate the sum and create the new term $x^5$.
> 4 votes

# Answer
This looks like a classical application for Object-Oriented Programming (OOP), or more explicitly, Polymorphism.

You could create a basic object, e.g. `treeObj` with a method `evaluate`, and then generate sub-types for every object in your language, e.g. a `plusOp` object for the $+$ expression, the constructor of which takes two other `treeObj` as its left and right operands.

Every subclass of `treeObj` implements its own `evaluate` method which is called recursively on its operands. This is essentially Depth-First tree traversal.

Construction of such a tree from a string is usually done by converting the string into tokens, and then assembling the tree *from the bottom up*. For this you may want to have a look at LALR parsers, or, for more simple languages, a Recursive Descent parser.

Reduction is a bit trickier, as each node defines equivalence differently. Personally, I would handle this by making each `treeObj` provide a function `isEqual`, which compares it to another `treeObj`. Each different sub-type of `treeObj` could then implement its own commutativity, depending on the underlying mathematical properties of the operator.

In summary, a lot of Polymorphism and Recursion.
> 2 votes

# Answer
Take a look at Chapter 8 of Paradigms of Artificial Intelligence Programming \- where the author Peter Norvig solves this problem in Common Lisp.
> 2 votes

---
Tags: data-structures, computer-algebra, mathematical-software
---