# Question
Title: How are two registers are enough to simulate a Turing machine?
The paper *A universal cellular automaton in the hyperbolic plane* says:

> Our simulation consists in simulating the execution of a register machine. It is known that **two registers are enough to simulate a Turing machine**, see \[10\], and so, by such a simulation, we shall obtain a universal computation.

It links to \[10\] which is *Computation: Finite and Infinite Machines*, a $200 book from Minsky with no reasonable/free version seemingly available on the web, so no easy access.

How are two registers enough to simulate a Turing machine? How do we know that? What is the sketch laid out in the Minsky book that explains how this works?

# Answer
> 4 votes
The reduction is sketched on Wikipedia.

---
Tags: turing-machines, computation-models
---


# Question
Title: Should the certificate for NPSPACE be polynomial in size?
There is a problem that I am working on. I have shown that the problem is NP Hard, but I haven't been able to show that it is in NP. But the problem is also known to be in EXP. My gut feeling is that the problem is PSPACE-complete. I am leaving aside PSPACE-hardness for now. Even if I have to prove that the problem is in PSPACE, it doesn't look so easy. My options are:

1. Write down a polynomial space algorithm
2. Reduce my problem to a QBF formula
3. Using Savitch theorem, PSPACE=NPSPACE. Therefore try to come up with a certificate for the problem that can be verified using polynomial space.

If I try to use the 3rd approach, do I have to ensure that the certificate is polynomially sized. **So basically what I am asking is if the certificate of the NDTM is stored in the working memory tape or the input memory tape**? If it is stored in the working memory, then I could use up exponential memory for the certificate, thus making it not a problem in PSPACE.

# Answer
It's OK for the certificate to be exponentially long only if (1) the space consumption of the verifier is polynomial in the size of the problem instance (it is *not* allowed to use space polynomial in the size of the certificate) and (2) the verifier only accesses the certificate in a read-once fashion: once it reads a particular part of the certificate, it is erased, and the verifier cannot ever read it again.

Conceptually, you can view the certificate as the record of nondeterministic choices made by the nondeterministic algorithm that proves the problem is in NPSPACE. That algorithm can only use polynomial space but can use exponential time, so it might make exponentially many nondeterministic choices, hence why the certificate can potentially be be exponentially long (and hence why the verifier must use space that is polynomial in the size of the problem instance, not the size of the certificate).

My thanks to Emil Jeřábek for pointing out that my original answer was wrong. As he writes:

> While an NPSPACE machine can use exponential time, and the natural way to certify its nondeterministic choices is using an exponential-size certificate that can be verified in polynomial space, this is *not* by itself enough to guarantee that the language is in (N)PSPACE, as exactly the same is true of NEXP. That is, any NEXP language has exponential-size certificates that can be verified by a PSPACE (or even coNP) machine that can only access a constant-size part of the witness at any given time: just take the transcript (sequence of configurations) of an accepting run of the NEXP machine as the certificate. The correctness of the transcript can be verified by checking local conditions that only involve a constant number of cells of at most two configurations at the same time, hence it can be easily done in polynomial space. What distinguishes NPSPACE from NEXP is that an NPSPACE machine cannot write down the certificate, and if it generates its parts nondeterministically on the fly, it has no way of ensuring that it generates the *same* bits if it "reads" the same chunk of the certificate *twice*. That is, it can only access the certificate in a read-once fashion: once it reads a particular part of the certificate, it is erased, and the verifier cannot ever read it again.
> 5 votes

# Answer
Lets say you have some certificate of length $s\>\>poly(n)$, and you are only allowed to store at most $poly(n)$ memory. Assuming you are capable of verifying "chunks" from the certificate of size $poly(n)$ at a time, it really wont matter what $s$ is.

Try to think of the following:

1. We iterate through all possible strings of size $poly(n)$ for the first "chunk", and verify if at least one of them makes you accept.
2. We delete that "chunk", and do the same for the "second chunk".
3. Do step 2 again until you have checked $\frac{s}{poly(n)}$ "chunks"

This will guarantee you will never use more than $poly(n)$ space, but will allow you to simulate any certificate size that you can verify in small parts. Hence, your language is in $PSPACE$.

I hope this helped!
> 4 votes

---
Tags: complexity-theory, space-complexity
---


title: Generalization of Cellular Automata

text:
# Question
Title: Generalization of Cellular Automata
So in the little I know about formalization of cellular automata, it appears there are 4 major categories of cellular automata:

1. 1-dimensional (cellular automata on the line)
2. 2-dimensional (cellular automata on the plane)
3. 3-dimensional (cellular automata in the cube)
4. hyperbolic cellular automata

In the plane example, there are 3 main tilings: the square tiling, triangular tiling, and hexagonal tiling, which seem to have been well studied. I am not sure about the 3D case yet. I have the book on Cellular Automata in Hyperbolic Spaces but haven't worked fully through it.

But it seems that the general model is a bunch of nodes/cells with links between them. I can imagine not just these *regular* grids/tilings, but cases where you have say 5-link cells connected to a bunch of 7-link cells, connected to a bunch of 4-link cells. The 7-link cells play a 7/8 musical rhythm, the 5-link cells a 5/8 musical rhythm, and the 4 a 4/4 musical rhythm. Then you see what patterns evolve out of that, or how they interact. Or those serve as input signals to another simplified cellular automaton which evolves.

Basically I'm wondering what work has been done on the generalization of cellular automata to beyond these 4 categories, and where I can learn more.

# Answer
Cellular automata can be defined on Cayley graphs of arbitrary groups. Intuitively, the states go on the nodes of the graph, and the neighborhood of a node is defined using the edges. The $d$-dimensional case corresponds to the group $\mathbb{Z}^d$ with edges $(\vec v, \vec v \pm \vec e\_i)$ for all nodes $\vec v \in \mathbb{Z}^d$ and the standard basis vectors $e\_1, \ldots, e\_d$.

Some very interesting results have been proved in this setting, with connections to geometric group theory, abstract algebra, and ergodic theory. Many results from classical CA theory generalize to CA on groups, but others only hold on some specific subclasses of groups. The book Cellular Automata and Groups by Ceccherini-Silberstein and Coornaert is a good resource on the topic.
> 3 votes

---
Tags: reference-request, cellular-automata
---


# Question
Title: How do you express a floor / ceiling in the approximation factor of an approximation algorithm?
Intuitively I feel like this is a bit of a dumb question, and is probably related to my vague understanding of approximation algorithms and whatnot.

Suppose I have some minimisation problem $X$ where, for some $n$, the optimal solution is $x$. If I make an algorithm such that it finds a solution of at worst, $\lceil1.5x\rceil$, how do I express this in the phrase that one seems to write, "This is a 1.5-approximation algorithm for the problem $X$" ?

I see usage of $\epsilon$ to denote some constants, but it always seems to go "in the same direction" as the minimisation / maximisation of the problem: that is, for a minimisation problem, someone would give $(5-\epsilon)$-approximation algorithm. Can I use it to go in the other direction? Should I be writing $(1.5 + \epsilon)$-approximation algorithm?

# Answer
The usual definition of an $\alpha$-approximation algorithm for a maximization problem is: an algorithm which returns a solution of value at most $\alpha \cdot \mathit{OPT}$, where OPT is the optimal value.

In practice, sometimes a more relaxed definition is used: the bound is only required to be $\alpha \cdot \mathit{OPT} + \beta$. This fits your case: if your algorithm is guaranteed to output a solution of value at most $\lceil \alpha \cdot \mathit{OPT} \rceil$, then it outputs a solution whose value is at most $\alpha \cdot \mathit{OPT} + \beta$.

Authors are often sloppy, and will just describe such an algorithm as an $\alpha$-approximation algorithm, though this term is somewhat ambiguous; sometimes the only way to know which definition is used is to read the paper.
> 2 votes

# Answer
Since ceil(1.5x) = 2 when x = 1, it is a 2-approximation. With the particular value 1.5, we know that ceil (1.5x) is either 1.5x or 1.5x + 0.5, so you could say it is an (1.5x + 0.5) approximation algorithm.

There are many problems where the answer x is always small. For example "what is the minimum number of colours to colour this planar graph". So I would very much hesitate to call it an 1.5+eps approximation algorithm, which would require that x \>= 0.5 / eps.
> 2 votes

---
Tags: complexity-theory, computability, approximation
---


title: Is it true that PRIMES are in SPARSE?

text:
# Question
Title: Is it true that PRIMES are in SPARSE?
I'm wondering if **PRIMES**, the language of all prime numbers represented in binary, which is $\\{10, 11, 101, 111, 1011, 1101, ...\\}$, belongs to the **SPARSE** class, a set of all sparse languages, that is, languages satisfying the property that the amount of words of length $n$ is bounded by some polynomial $p(n)$.

I believe the answer should be yes, because as the size of the tested number $p$ grows, the size of its binary representation grows logarithmically while the density of primes logarithmically shrinks, which leads me to an assumption that $p(n)$ could even be a constant, but I found no resources online to support or contradict this opinion.

# Answer
> 3 votes
If I remember correctly, there are $\Theta(\frac{n}{\log(n)})$ primes between $n$ and $2n$. Sum them up to get the number of primes up to $2n$, and then we know that $2n$ has $\log(n)+1$ bits. I think if you do the maths it will not end up in $SPARSE$, but I might be wrong here.

---
Tags: complexity-theory, formal-languages, primes
---


# Question
Title: Is pipeline bubbling only used with RAW data hazards?
I am studying computer science at university and we have an exam, which consists of several problems, one of which has to deal with pipelines.

My understanding is that one effective way to solve data hazards is to use pipeline bubbling - adding NOPs in order to stall the pipeline long enough to finish the operation, from which we will fetch the result.

Where my problem lies is conflicting information, regarding when we use bubbling. My professor's lectures state that bubbling is used to solve data hazards, no exceptions, while Wikipedia states that bubbling is used only with the RAW data hazard.

We have had some examples, which have left me very confused.

For example, we have the following operations:

S1: ADD R2,2,R1 ; R1 = R2 + 2

S2: SUB R1,R3,R4 ; R4 = R1 - R3

S3: MULT R5,3,R3 ; R3 = R5 * 3

S4: MULT R3,2,R3 ; R3 = R3 * 2

I have identified the following data hazards:

1. RAW - S1 and S2, S3 and S4
2. WAR - S2 and S3
3. WAW - S3 and S4

I have been told that I need a minimum of two operations between data hazards, which means that I need to add two NOPs between them.

My question is this - do I add NOPs between the RAW data hazards only (between S1 and S2 and S3 and S4) or do I add two between the WAR hazard as well(S2 and S3)?

# Answer
> 0 votes
*The question is not well detailed.* Because, without knowing depth of the pipe, ISA, in order vs out order is crucial for the answer. However, to answer the question: RAW hazards can be mostly solved with NOPs (the number of NOPs is dependent on your design of the pipeline, and it is compiler/hardware's responsibility to either to insert bubbles in software or hardware level). However, when you learn about forwarding units, you will understand that most RAW hazards can be easily solved by forwarding the up-coming written value of the register to the next instructions if needed.

Now WAR or WAV hazards can or can not be solved by bubbles. It seems confusing already but the idea of inserting bubbles does not guarantee that S2 will happen to read the "correct" value of R3. That is why general idea is to make sure in hardware level R3 is "saved/remembered" but not written into register file, until S2 is completed. Therefore, we create a new hardware module called hazard unit that deals with these types of problems.

---
Tags: cpu-pipelines
---


# Question
Title: Elegant algorithm to semi-decide if two lambda calculus terms are equivalent
Given two lambda terms $t\_1$ and $t\_2$, it is semi-decidable if they are equivalent (i.e. can be rewritten as each other using alpha, beta, and eta conversions). An algorithm to do this is to try every sequence of rewrites starting with $t\_1$, and if any of them end with $t\_2$, then output true.

What other algorithms can be used? Are there any more "elegant" algorithms?

EDIT: \[This\] claims that a generalization of the Knuth-Bendix completion algorithm can semidecide the word problem. It has not citations though.

# Answer
> 0 votes
Let me just note that the way you've written your solution it is not guaranteed to work. You need to consider all rewrites of $t\_1$ and $t\_2$. If you don't you get things like $t\_1 \equiv y$, $t\_2 \equiv (\lambda x.x) y$.

So, a not-particularly elegant solution is considering all the $αβη$-reductions paths from $t\_1, t\_2$ and see if there is a common term. If $t\_1 =\_{βη} t\_2$ then there will be common reduct by the Church-Rosser properties of $βη$-reductions.

# Answer
> -1 votes
Let’s first suppose we can reduce both $t\_1$ and $t\_2$ to their $\beta \eta$-normal forms; $$t\_1 \twoheadrightarrow\_{\beta \eta} M \qquad \text{and} \qquad t\_2 \twoheadrightarrow\_{\beta \eta} N$$ If $M$ and $N$ are identical, we are done. Otherwise, we check $\alpha$-equivalence by induction on term complexity:

1. if $M$ is a variable
    * if $N \equiv M$, output true
2. if $M$ is an abstraction $(\lambda x. M\_1)$
    * if $N$ is an abstraction $(\lambda y. N\_1)$
        + output whether $N\_1\[y:=x\]$ and $M\_1$ are $\alpha$-equivalent
3. if $M$ is an application $(M\_1\ M\_2)$
    * if $N$ is an application $(N\_1\ N\_2)$
        + output whether both $M\_1$ is $\alpha$-equivalent to $N\_1$ and $M\_2$ is $\alpha$-equivalent to $N\_2$

*(You could also use de Bruijn notation and avoid the need for $\alpha$-conversions.)*

For non-normalising terms, you can at best use the above procedure after each $\beta \eta$ reduction, but it shouldn't be possible (because of Halting problem) to have anything better than “iterative trying”.

---
Tags: algorithms, lambda-calculus, term-rewriting, equality
---


# Question
Title: Poping a symbol on a PDA when Input and Stack are Irrelevant
Say I had a PDA with alphabet language {0,1}, and a stack language {P,Q,\\$}. In the PDA I don't really care what the inputs are at the end and I just want to clear the stack back down to the special character. I could write out the transitions like:

1,P-\>e

1,Q-\>e

0,P-\>e

0,Q-\>e

e,P-\>e

e,Q-\>e

1,\\$-\>\\$

0,\\$-\>\\$

but that's a bit much. Is it in convention to instead just write:

{0,1},{P,Q}-\>e

e,{P,Q}-\>e

{0,1},\\$-\>\\$

Note that I'm not trying to pop more than a symbol at a time, just to I don't care about the inputs or stack at this point. With this small alphabet and stack it's not horrible... but if the languages were larger that would be a lot of diction for every individual case. I just want loop on this state to get to a point where the inputs are e and the stack is \\$ so that I can transition to the final accept state with e,\\$-\>e

I only ask because I have not seen any textbook or material write transitions as such. So this is either a yes or no answer, or if there's some other convention for how to handle larger alphabets, please let me know what it is.

# Answer
This is technically allowed (its just a shorthand, I believe its understandable, but if you aren't sure, just explain what it represents)

However, one important thing to note is that $\\{0,1\\}\times \\{P,Q\\}\rightarrow \epsilon$ is a ***totally different*** transision than $\\{\epsilon\\}\times\\{P,Q\\}\rightarrow \epsilon$.

The first one would "eat up" a part of the input, for every symbol you delete from the stack (which *also* means you will delete a bounded number of elements from the stack)

While the second one will just totally empty the stack and will not change the input altogether (and the number of elements deleted here is not bounded).

---

Usually, the second approach is the better one for clearing the stack, since it:

1. Clears the entire stack and not only a portion of it
2. Does not "eat up" the input symbols
> 1 votes

---
Tags: formal-languages, pushdown-automata
---


# Question
Title: Counting strongly connected components in a directed graph in $NL$
Define $K\\\_SCC = \\{ \langle G, k \rangle \\,:\\, G \text{ has at least $k$ strongly connected components} \\}$

I want to show that $K\\\_SCC \in NSPACE(\log n)$, using that $st-CONN$ and $\overline{st-CONN}$ are both in NL, where $st-CONN = \\{\langle G,s,t \rangle \\,:\\, \text{there is a path from $s$ to $t$ in $G$} \\}$.

Would appreciate any help

# Answer
Ask the prover to give you any node from $k$ distinct connected components.

You have only to verify that the nodes are not in the same connected components (hence, they are in $k$ different components, meaning that $\langle G, k\rangle \in K\_{SCC}$)

Also, ask for the proof of $st-CON$ between any two of them.

Notice that even though the proof is gigantic, at every point in time the verifier will need to only verify a small portion of the proof: only one $st-CON$ is being processed at a time, hence the verifier can be constructed in such a way that will require only $O(\log(n))$ space.

The pseudocode for the verifier should look similar to this:

* For every $i\neq j$ with $1\le i,j\le k$, do:
    + Take a look at the next $O(\log(n))$ bits of proof, and verify $st-CON$ for the $i$'th and the $j$'th nodes
> -2 votes

---
Tags: complexity-theory, graphs, space-complexity, computation-models, nondeterminism
---


# Question
Title: Same notation/terminology for union of sets and concatenation (Kleene star)?
> For the union of sets we use the union operator $\cup$ (or $\bigcup$). And for a concatenation (Kleene star) we also use the union operator. The operations are different, but why the same terminology and operator?

The following is my understanding of the union of sets versus the concatenation of sets (Kleene star). Please correct me if I'm wrong.

**Union of sets**

For the two sets $\\{a,b\\}$ and $\\{a,b\\}$ we have the union \begin{align} \\{a,b\\}\cup\\{a,b\\}=\\{a,b\\} \tag 1 \end{align} ***Update:*** For reference I used Union (set theory) from Wikipedia.

**Concatenation of sets (Kleene star)**

The concatenation of $\\{a,b\\}$ and $\\{a,b\\}$ is also a union *(same notation?!)* of two sets \begin{align} \\{a,b\\}^\*&=\bigcup \_{i=0}^{2} \\{a,b\\} ^2 \tag 2\\ &=\\{a,b\\} \cup \\{a,b\\} \tag 3\\ &=\\{\epsilon,a,b,aa,ab,ba,bb,aaa,aab,aba,abb,baa,\dots\\} \tag 4 \end{align}

***Update:*** For reference I used Kleene star from Wikipedia. And here's where my confusion lies because at Wikipedia they also use the notation with the union operator: $$ V^\* = \bigcup\_{i\geq 0} V^i = V^0\cup V^1 \cup V^2 \cup V^3 \cup V^4 \cup \cdots \tag 4 $$ Which is the same (?!) notation as in my $(2) - (3)$ but with the upper bound $2$. And the notation does not coincide with $(1)$.

# Answer
Wikipedia is using $\cup$ in its usual meaning, set union. When Wikipedia defines $$ V^\* = \bigcup\_{n \geq 0} V^n = V^0 \cup V^1 \cup V^2 \cup \cdots, $$ it literally means that $V^\*$ is the union of the sets $V^0,V^1,V^2,\ldots$

The concatenation happens in the definition of $V^n$, which can be defined as follows: $V^0 = \\{\epsilon\\}$, and $V^{n+1} = \\{ xy : x \in V^n, y \in V \\}$. In words, $V^n$ is the concatenation of $n$ words from $V$.
> 2 votes

# Answer
The concatenation of two sets of strings is the set of all pairwise concatenations of their elements: $AB = \\{ xy \mid x \in A, y \in B \\}$. For instance, the concatenation of $\\{a,b\\}$ and $\\{a,b\\}$ is $\\{aa, ab, ba, bb\\}$.

Now we can write

* $A^2 = AA$ = all strings that are 2 strings from $A$ concatenated
* $A^3 = AAA$ = all strings that are 3 strings from $A$ concatenated
* $A^4 = AAAA$ = all strings that are 4 strings from $A$ concatenated
* and so forth, and, for consistency,
* $A^1 = A$ = all strings that are 1 string from $A$ concatenated
* $A^0 = \\{ \epsilon \\}$ = all strings that are 0 strings from $A$ concatenated

Now the Kleene star of a set $A$ is the set $A^\*$ formed by all strings consisting of *arbitrarily many* concatenations of strings from $A$. That is to say: such a string is

* *either* 0 strings from $A$ concatenated (it is in $A^0$)
* *or* 1 string from $A$ concatenated (it is in $A^1$)
* *or* 2 strings from $A$ concatenated (it is in $A^2$)
* *or*, ...

In other words: $\displaystyle A^\* = \bigcup\_{n}{A^n}$. The *either ... or* is where the union comes from.

You also wrote: correct me if I'm wrong. Well, you wrote this:

> \begin{align} \\{a,b\\}^\*&=\bigcup \_{i=0}^{2} \\{a,b\\} ^2 \tag 2\\ &=\\{a,b\\} \cup \\{a,b\\} \tag 3\\ &=\\{\epsilon,a,b,aa,ab,ba,bb,aaa,aab,aba,abb,baa,\dots\\} \tag 4 \end{align}

Line (2) is just a weird way of writing $\\{ a, b \\} \cup \\{ a, b \\} \cup \\{ a, b \\}$. This is indeed equal to $\\{ a, b \\} \cup \\{ a, b \\}$ (3), which in turn is equal to $\\{ a, b \\}$. No string concatenation is going on at all here, so you're not getting any other elements than just $a$ and $b$. In (4), suddenly, you have a lot of concatenations. Clearly, that can't be right. You must have miscopied this from a source in which (2) and (3) were different.
> 1 votes

---
Tags: formal-languages, automata, discrete-mathematics, notation
---


# Question
Title: How would you specify a grammar that can parse letters separated by single underscores?
In JavaScript, let's say, it is easy to build a string intermixed with single underscores by just *joining* the string parts.

```
let string = ['foo', 'bar', 'baz'].join('_')

```

In addition, it is straightforward to write a grammar that can have letters separated by **at least one** underscore.

```
grammar = letter letterOrUnderscore*
letter = a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z
underscore = _
letterOrUnderscore = underscore|letter

```

That will match the input string:

```
foo_bar_baz

```

However, it will also match these unwanted strings:

```
a____
ab__c
abc__d___

```

Basically, it will match *sequences of underscores*, when what we want is *only one underscore between each sequence of letters*, and we shouldn't have trailing underscores. So only these are acceptable, for example:

```
a
ab_c
abc_d

```

The question is, how do you define a grammar to only allow **1 underscore between each sequence of letters**? I can't figure out how to write any sort of custom "grammar DSL" that can, in a straightforward way, handle this situation... I'm stumped currently how to do this.

```
grammar = letter then
  if previous == letter
    next = letter | underscore
  else
    next = letter

```

So it seems to need to access to the previous state, is there no other way to define this? Besides not being very "DSL-like", it's also significantly harder to handle this sort of situation.

# Answer
What you are describing is a regular language, so describing it with a regular expression would be a good approach.

Another way to view the language is one word, followed by zero or more (underscore word) sequences.

In PCRE syntax, `[a-z]+(_[a-z]+)*`.

The same idea can be used to remove left recursion from some grammars; instead of a production rule like $E \to E + E$ (expressions can be combined with plus), you use $E \to T S$ with $S \to \varepsilon; S \to + T S$ (terms can be followed by zero or more "operations", which is an operator followed by a term)
> 2 votes

---
Tags: formal-grammars, parsers
---


# Question
Title: Effectively decidable vs. noneffectively (or ineffectively) decidable
The introduction of https://www.sciencedirect.com/science/article/pii/0001870882900482 starts with the following sentence:

> The word problem for commutative semigroups is effectively decidable.

I know what a “decidable” problem or, more precisely, a “decidable” language over an alphabet means: there is an algorithm that terminates on every input and returns “yes” or “no”, depending on whether the input belongs to the language or not.

So, if the sentence were “The word problem for commutative semigroups is decidable”, I'd think this: for each (most likely, finite) alphabet $$ and each commutative semigroup $\langle G,\mathord\circ\rangle$, where $G\subseteq ^\*$, there is an algorithm that, started with a string $s\in ^\*$ as input, terminates and says whether $s\in G$ or not. Please correct me if I'm wrong.

Now, what the hell does *effectively* mean? Is there anything *non-effectively decidable* or *ineffectively decidable*? How would *effectively decidable* be different from *ineffectively decidable* or *non-effectively decidable*?

# Answer
> 4 votes
"Decidable" and "effectively decidable" mean the same thing. I realize that's a bit confusing; but it reflects a difference in terminology between two communities.

(Strictly speaking, I suspect there might be a difference between those two concepts if Church's thesis is false; but if Church's thesis is true, then they are equivalent.)

---
Tags: terminology, decidability
---


# Question
Title: How does software prefetching work with in order processors?
From prof. Onut Mutlu's slides on prefetching, this example has been shown as software prefetching:

```
for (i = 0; i < N, i++) {
   __prefetch(a[i + 8]);
   __prefetch(b[i + 8]);
   sum += a[i] * b[i];
}

```

On Wikipedia, it says that to determine the number of element of an array to prefetch ahead is calculated by $miss\\\_penalty/cycles\\\_per\\\_iteration$. My question is if the processor is in-order, what is the point of software prefetching, because even if I prefetch with the formula above, I have to stall my CPU, and `sum += a[i] * b[i];` can not go through memory access stage. And overall number of memory accesses and `sum += a[i] * b[i];` will be the same with or without prefetching.

I understand that if my CPU is out order, then in 8th iteration `sum += a[8] * b[8];` can just go through memory access stage, as a\[8\] and b\[8\] will be cache hit, so it will just take 8 cycles and because k = 8, then next 7 sum instructions will also just go through without a problem.

# Answer
> 6 votes
"In-order" processors only *issue* instructions in order. Completion is out-of-order even on most processors that are called "in-order". "in-order" just means: if the processor needs to stall the issuing of the next instruction because of a RAW, WAW, or WAR dependence, it can't issue any other instruction during the stall.

In the example you are showing the `sum += a[i]*b[i]` doesn't have any dependence on the immediately preceding `__prefetch()` instructions, so can issue immediately.

---
Tags: computer-architecture, compilers, cpu-cache, memory-hardware, cache
---


# Question
Title: Finding the distance from a point to a $R^m$ restricted area in $R^n$
The problem is described below:

When m=2 and n=3, it is basically finding the distance between a point and a line segment in $R^3$.

But when both m and n are larger, do I have to use a generic optimizer to solve this, or this problem can be precisely solved with mathematics, like the case when m=2 and n=3?

What I have done for now:

Approach A:

I tried to solve it with Gram–Schmidt process and projection but got stuck.

For example, the following R code:

```
P <- c(1,1,1,1)

m <- rbind(c(1,-1,1,2)*1/3,c(1,2,1,1)*1/5)

m2 <- qr.Q(qr(t(m)))

P2 <- P%*%m2[,1]*m2[,1]+P%*%m2[,2]*m2[,2]

```

It does not take into account the restriction $w\_1+w\_2=1$

Approach B:

Tried to solve it with lagrangian optimization, but also got stuck there.

# Answer
> 1 votes
Given a matrix $M$ and vector $y$, you are trying to find a vector $x$ that minimizes $\\|Mx-y\\|\_2$, subject to $x \ge 0$ and $\\|x\\|\_1=1$.

Without the additional constraints on $x$, this would be a least squares problem, which could be solved through linear algebra (see https://en.wikipedia.org/wiki/Linear\_least\_squares), or with gradient descent.

With those additional constraints, you might try projected gradient descent.

---
Tags: algorithms, optimization, computational-geometry
---


# Question
Title: Why is the vulnerable time in pure aloha twice the frame time?
The time required to send a frame is called frame time. Vulnerable time is the time during which no transmission should be done to avoid any collision.

My question is what kind of problem will be created if vulnerable time was equal to frame time?

# Answer
This is because in pure ALOHA, even if a bit of a frame collides with a bit of another frame, both the frames get discarded. Also, in pure ALOHA, a station doesn't listen to the medium before transmitting. So, it has no way of knowing that another frame was already underway. If another frame was indeed underway already, then the newly transmitted frame becomes vulnerable. That is why it is called "vulnerable time". It equals twice of the frame time because it counts the *time in which the transmission of another frame should start so as to make the current frame vulnerable*. This time interval includes:

* **the frame time** because if transmission of another frame were started in the frame time of the current frame, collision would occur.
* **a time interval (equal to the frame time) before the frame time** because if transmission of another frame were started in this time interval, collision would still occur.

> My question is what kind of problem will be created if vulnerable time was equal to frame time?

If the vulnerable time were equal to frame time, any frame (say A) transmitted prior to the considered frame (say B) could be transmitted within the frame time of the considered frame (B), resulting in a collision.

Suppose a sender X starts transmitting at time instant '0' and finishes at instant 't'. Then any other sender Y should start at or after instant 't' and continue till instant '2t' (because if Y start its transmission even a tiny amount of time before 't', there will be collision). Here, the vulnarable time for the frame transmitted by Y is the sum of its own frame time (i.e. 't' to '2t') and another time duration (i.e. '0' to 't'), effectively being '0' to '2t'. This is the time interval during which no sender should send on the channel to ensure that the frame sent by Y doesn't collide.
> 4 votes

# Answer
If vulnerable time was equal to frame time, there is a chance to collide with a frame as there is no gap. Let me give an example :

If there is a car in road and it maintains a gap of 2 meter from front and back there is less chance to hit with another car on the road, or if each and every car in a road maintains 2 meter gap there will be less hit if some one push brake.

But if vulnerable time was equal to frame time that is, if each car on the road maintains zero distance there is maximum possibility to get hit. I think it's clear now.
> 2 votes

# Answer
The stations participating in aloha don't need to transmit frame starting at the initial time t=0.

But the vulnerable time(T) is added to initial time to create some kind of check points (t, t+T, t+2T,...).

So if a station decides to send a frame somewhere between (t, t+T), the transmission time will cross the t+T point and use some of the time between t+2T.

In order to avoid collision we have to include the next duration (t+T, t+2T) also into vulnerable time because another station might decide to transfer between time period (t+T, t+2T) causing collision
> 0 votes

# Answer
Suppose at time t=0 station A starts sending the frames, then station A takes T(i.e Transmission Delay) unit time to transmit the frame during this interval if any other station sends the frame then the collision will occur. Then the idea comes if after the time T if any station wants to send the frame then there should not be any collision but wait what if any other sender sends the frame at time T-t'(where t'-\>0 i.e very small) then it will collide with the frame which is sent by station A and after the collision that useless data transmitted till T-t'+T i.e 2T-t' and up to this time if any station sends frame then that will also collide. So the vulnerable time for the transmission of the frame is taken 2\*T because t' is very small it tends to zero so we can neglect that.
> 0 votes

# Answer
In aloha vulnerable time is twice frame time. To see why this is, suppose you transmit the msg bit in 10sec(FT) to the receiver. So when you start transmission of msg bit and before completing 10 sec if anyone is transmit another msg bit than there will be collision occur same as 10sec before you transmit the msg bit than less collision occur. So we can say total vulnerable time is twice of frame time.
> -1 votes

---
Tags: computer-networks
---


# Question
Title: Reason that integers are used for priorities instead of float
Why are priorities always from a fixed set of integers? In operating systems priorities are integers typically between 1..MAX. But what is the reason that this is the case, when it would obviously be easier to place a new task between priority 2 and 3 with priority 2.5 instead? The way it is now, my scheduling can run out of priorities if my operating system has priorities between 1 and 10 and I need to schedule more than 10 different priorities or must re-arrange for a new task that should be between two subsequently scheduled tasks.

# Answer
Historically, floating point has been slower than integer arithmetic, though this has not been the case for about 20 years on most non-embedded architectures.

The more compelling reason is to optimise FPU context switching.

When an operating system switches between two threads (not to mention the fact that the operating system itself is software that uses CPU registers), the contents of the CPU registers needs to be saved and restored. A typical modern CPU might have 16 or so general-purpose 64-bit registers, so that's 128 bytes.

Modern FPUs, however, have wide SIMD registers, and thus carry much more state; on modern Intel-esque CPUs, for example, you need 512 bytes.

You could save and restore these on every context switch, but that would incur a nontrivial cost. Instead, most system services, device drivers, and system programs (not to mention the OS itself) are written so they don't use the FPU. Not only does merely invoking a system call not require saving and restoring the FPU, neither does context switching to a system service and back again.

To support this, you need a few things:

* The compiler needs a mode where it will never generate any instructions which involve the FPU. This ensures that the kernel and other system software never changes the FPU state implicitly.
* The CPU needs a mode or flag where it traps to the operating system when a FPU instruction is executed. This flag is set whenever the CPU context switches to a thread for which the FPU state is "stale", and the FPU state is switched if the trap happens.

Note that while this optimisation "works", it has been the source of a Spectre-like security vulnerability on recent Intel CPUs, where it can leak information when the FPU operation is executed speculatively. But even without the full lazy FPU switch optimisation, this still allows saving and restoring FPU context *only* when a context switch actually occurs, rather than on every system call.
> 5 votes

---
Tags: process-scheduling, multi-tasking
---


# Question
Title: If regex describes FSAs, what string formats describe Turing machines?
(Topic summary under the line.)

Regex, at least the formal definition featuring only | and \*, is used to describe words accepted by a given FSA, but it can be transformed into the corresponding state diagram (by constructing a NFSA with epsilon transitions from "modules" that correspond to the *concatenations*, *alternations* and *Kleene stars* in the regex, and then deriving the DFSA from that). Thus, it is as if regex captures the "essence" of state diagrams, which are just oriented graphs; a way to encode the entire graph in a single string.

A DFSA needs to have as many outgoing transitions per each state as there are symbols in the chosen alphabet. Let's assume two for our alphabet L: 0 and 1. These symbols can be understood as if-else statements, the machine takes one path if it sees a 0, and a different path for 1. We can provide substitutions of the form 0-\>0A, where A is some set of tape instructions. Choosing the right syntax semantics for the context-free aspects of these strings then allows us to omit the 0's and 1's entirely. For example, replace ()\* with \[\], so that \[A\]B reads "while 1, A, else end while, B". Similarly, since |L|=2, we can ultimately reduce every *alternation* to the form (A|B) (so for example no expressions of the "(A|B|C)" kind), and thus we can rephrase this as "if 1, A, else B, end if". Finally, for pesky cases where the while condition is inverted, we can define "!\[\]" for now, which reads "while 0...".

Example Busy Beaver-esque automaton (state 1 = initial, state 0 = halting):

State 1: if ( read 1 ) { A; state = 2; } else { B; state = 0; }
State 2: if ( read 1 ) { C; state = 2; } else { D; state = 1; }

Where A, B, C, and D are instructions for the tape-manipulating machinery.
Compact code for this state-transition table: 2021
String representation of the instructions themselves: \[A\[C\]D\]B

Informal proof of the correctness of the above string: If the first read symbol is 0, the first \[\] won't execute and B will execute instead; the halting state will follow. Otherwise if 1, do A and transition to state 2 (not deducible from the string). Then, if read 1, do C and don't change states, aka "\[C\]". Finally, otherwise if 0, do D and go to state 1, which was the same as the initial one, ergo return to the beginning of the string (the first "\[").

The very much esoteric language Brainfuck is notorious for its simplicity, and the only control flow it provides is a "while (true)"-style loop "\[\]". However, it is my suspicion that not every state diagram can be constructed in Brainfuck, or this experimental language of mine. For a machine with the code "2001", I couldn't find a string that wouldn't utilize gotos/breaks. (My attempt: \[A(C\*,D)\]B, where * means to break from \[\]; "(,)" as usual means if-else). It seems that while every state diagram can be converted into regex, once we give each edge a unique label and aim to preserve them and their paths, the task becomes impossible in some instances, namely when there is a loop with two or more exits.

---

My question: if FSAs have regex, what do Turing machines have? Is there some succinct way to represent their state diagrams using a single string? Brainfuck seems like a good candidate at first, but it probably cannot describe every possible state diagram; at least that is my guess. No one programs by drawing state diagrams, programs are written (stored) as inline strings of symbols, hence my interest.

Additional question: how come Brainfuck is Turing-complete without selections (if-else statements), how come iterations (while loops) can substitute for selections, and is there a human-friendly algorithm for this? (I am aware of the structured program theorem, but that one includes selections. I am seeking proof of the substitution claim.) Moreover, it seems like some state diagrams cannot be described solely using context-free structures and require gotos/breaks. Is there proof for this, and what does this tell us about Turing completeness or programming language design? (For one, I know it breaks the context-free syntax, but I wish to learn more.)

# Answer
Any language that is accepted by a FSA can be accepted by a regular expression, and vice versa.

Any language that is accepted by a Turing machine can be accepted by an unrestricted grammar, and vice versa.

See the Chomsky hierarchy.

If you literally mean that you just want a string that describes a Turing machine, it is easy to obtain one: convert the specification of the Turing machine to text. This is basically the same idea as representing a program by its source code; the source code can be viewed as a single long string.

Since you asked about Brainfuck: Brainfuck is Turing complete. This means that any language that is accepted by a Turing machine can be accepted by a Brainfuck program, and vice versa. Pretty much nothing about Brainfuck is human-friendly, so while this statement can be proven, I don't expect a short human-friendly proof of it.

You might also be interested in https://en.wikipedia.org/wiki/Turing\_completeness, What does being Turing complete mean?, Are there minimum criteria for a programming language being Turing complete?, Does a do-while loop suffice for Turing-completeness?.
> 2 votes

# Answer
There is indeed an extension of regular expressions that accepts the language of two-stack push-down automata, which has the same expressive power as Turing machines.

First off, to make the algebra more obvious, I'm going to define the operators using Kleene algebra notation.

$0$ is the empty set and $1$ is the zero-length string. Juxtaposition, or $\cdot$, means string concatenation, and $+$ means set union. The algebra satisfies the usual non-commutative semiring axioms:

$$A + B = B + A$$ $$A + (B + C) = (A + B) + C$$ $$A + 0 = 0 + A = A$$ $$A \cdot (B \cdot C) = (A \cdot B) \cdot C$$ $$A \cdot 1 = 1 \cdot A = A$$ $$A\cdot(B + C) = A \cdot B + A \cdot C$$ $$(A + B) \cdot C = A \cdot C + B \cdot C$$ $$0 \cdot A = A \cdot 0 = 0$$

Plus the axiom that addition (i.e. set union) is idempotent:

$$A + A = A$$

Plus, of course, the Kleene closure operator $A^\*$, which I won't axiomatise here, but you know what it means.

Now let's think about single-stack PDAs. Probably the most straightforward way to express this is using Dirac notation. Intuitively, the "bra" $\left\< \psi \right|$ pushes the stack symbol $\psi$ onto the stack, and the "ket" $\left| \psi \right\>$ pops the stack symbol $\psi$.

It satisfies a few axioms. First off, brackets commute with terminal symbols:

$$a \left\< \psi \right| = \left\< \psi \right| a$$

$$a \left| \psi \right\> = \left| \psi \right\> a$$

When a bra meets a ket, they form a kind of orthonormal inner product:

$$\left\< \psi \right| \left| \psi \right\> = 1$$ $$\left\< \psi \right| \left| \phi \right\> = 0$$

Intuitively, pushing a stack symbol followed by popping the *same* symbol is equivalent to doing nothing, whereas pushing a stack symbol followed by popping a *different* symbol is not allowed, and so the language accepted by that sequence of operations is the null set.

Once you have those operators, you can do things like give a "PDA expression" which accepts the language $a^n b^n$:

$$ \left\< 0 \right| \left( a \left\< 1 \right| \right)^\* \left( b \left| 1 \right\>\right)^\* \left| 0 \right\>$$

To implement two-stack PDAs, and hence Turing machines, you simply need two kinds of push and pop, say $\left\< \phi \right|\_1$ and $\left\< \phi \right|\_2$. Coming up with interesting "Turing expressions" is left as an exercise.

And just to go down the rabbit hole, the Dirac notation is suggestive of how you could generalise this even further. "Classical" stacks give you an orthonormal inner product whose only values are $0$ and $1$. If you allowed other values of the inner product, this would give you a regular expression-like notation which can represent quantum Turing machines.
> 3 votes

---
Tags: formal-languages, turing-machines, finite-automata
---


# Question
Title: Why does it take O(n!) time to specify a canonical ordering for learning flatten adjacency matrices/graphs?
I was reading a paper for learning graphs (paper is GraphRNN) and it says in section 2.2 (emphasis by me):

> Vector-representation based models. One naive approach would be to represent G by flattening $A^π$ into a vector in $R^{n^2}$, which is then used as input to any off-the-shelf generative model, such as a VAE or GAN. However, this approach suffers from serious drawbacks: it cannot naturally generalize to graphs of varying size, and requires training on all possible node permutations or **specifying a canonical permutation,both of which require O(n!) time in general**

I understand how flattening the adjacency matrix would require the algorithm to receive all possible orderings and thus it takes $O(n!)$ to learn it - but I don't understand why specifying a canonical ordering has that issue to. With some abuse of notation just do $\pi(G,A) = G^\pi,A^\pi$ for all graphs before giving them to the training algorithm. Something like (say we have $N$ graphs with $n$ verticies and we loop T times):

```
for t in T
  for G,A in Graphs.Dataset
      Gpi, Api = pi(G,A)  # takes worst case O(n^2) to at least do print the adj matrix
      y = mdl(Gpi, Api)
      loss(y,Gpi,Api).backward().sgd() # assume we are doing SGD or something

```

The run time seems $O(N)\*O(n^2)$ not $O(N)\*O(n!)$. So I am not sure why the canonical representation takes $O(n!)$ (note I am aware that just multiplying big-Os like that can lead to problems but specifying the summation explicitly in this case I think leads to no issues).

Thanks for the help!

---

cross:

# Answer
If we had a way to canonicalize graphs efficiently, then we could canonicalize the graph before feeding it to the ML.

Unfortunately, no polynomial-time algorithm for graph canonization is known. One naive algorithm for graph canonization runs in $O(n!)$ time. I don't believe the claim is literally correct that graph canonization requires $O(n!)$ time, but a plausible conjecture is that there is no polynomial-time algorithm for graph canonization. I suspect that's what that quote is trying to express.
> 1 votes

---
Tags: graphs, algorithm-analysis, machine-learning, runtime-analysis, graph-traversal
---


title: Why does Slotted Aloha work?

text:
# Question
Title: Why does Slotted Aloha work?
So the way I understand it, if station A and station B, for example, try to transmit a frame at the same slot, a collision occurs, leading to an attempt at the next slot. But wouldn't the algorithm just repeat itself? The same two stations would try again on the second slot and it would still cause a collision. Also, it means that the first slot would remain unused.

Am I understanding it wrong?

# Answer
> 1 votes
This is a good question. As you study more, will find that all the Aloha protocol variants are highly inefficient and ambiguous. And yes, slotted Aloha’s central concept seems to suggest that a collision sparks an infinite loop of data collision. Let’s look at the (only) two tenets of the Pure Aloha protocol from UOH, 1971:

* If any device has data to send, send it
* If a collision occurs, scrap and try again later

Slotted Aloha is just an extension of Pure Aloha that adds one more tenet:
* Data must be sent at regular intervals (slots)

The use of regular intervals increases efficiency significantly.

Now, about collisions, observe the following diagram:

Source: Wikimedia

Notice how devices C, F, and H encounter a collision when they all try to send data in the same interval? Device C tries to resend the data right away, device F waits for a few frames and device H has yet to try sending the data again.

When it comes to the Aloha protocols, what does one mean by sending the data “later”? One second from now is later. Three slots is later. Two years is later. That is up to each device to decide.

If later means the same frame for every device, than yes, infinite collision will occur. This is why a quality method must be developed to prevent this behavior. In programming this is called a back-off scheme.

A predictable and efficient back-off scheme will attempt to implement a probable generation of frames (both new frames and repeats from data that collided) that reduces the probability of collision, such as a Poisson Distribution.

Recommend Reading: Poisson Distribution

# Answer
> 0 votes
This is the very obvious question in the case of slotted aloha but the only reason to use slotted is the efficiency which in case pure aloha is very low. Vulnerable time in the case of pure aloha is 2\*T (where T is transmission delay) where in the case of slotted aloha it is reduced to T so we can see only this advantage in the case of slotted aloha.

---
Tags: computer-networks
---


# Question
Title: Understanding a summation notation. Sum(j=2 to n) j - 1
I have been reading analysis of insertion sort in the "Introduction to algorithms" and faced a problem with understanding a specific summation notation when the worst case occurs.

I know how one can get formula for arithmetic series when we deal with **while loop header**, I mean 2+3+...+n equals to (n\*(n+1) / 2) - 1. But what I do not understand is how one can get formula for **while loop body**:

It is obvious, that we execute while loop body one time less, than while loop header, because of the final conditional test. Hence, we should subtract one. But how do we get n * (n - 1) / 2?

# Answer
> 2 votes
$$\sum\_{j=2}^n \left(j - 1\right) = \sum\_{i=1}^{n-1} i$$

---
Tags: algorithm-analysis, summation
---


# Question
Title: Is $L = \{xw^3x^{rev}\mid x, w\in\{0, 1\}^*\}$ context-free?
The title pretty much explains the question, but still: Is the language $$L = \\{xw^3x^{rev}\mid x, w\in\\{0, 1\\}^\*\\}$$ context-free?

I think it isn't and would motivate that suspicion by the following reasoning: if we consider the two languages: $$L' = \\{xwx^{rev} \mid\ x,w\in\\{0, 1\\}^\*\\} \text{ which is context-free}$$ $$L'' = \\{w^3\mid w\in\\{0, 1\\}^\*\\} \text{ which can be shown to be non-context-free by the pumping lemma}$$ Now if $L''$ were context-free, then we could obtain the initial language $L$ by "enclosing" $L''$ with $L'$, i.e. $L'$ is sort of a sub-language of $L''$. We can do that by extending the eventual CFG of $L'$ (let's assume its starting non-terminal is $S'$) with the following productions: $$S'' \to 0S''0 \\,\mid\\, 1S''1 \\,\mid\\, S'$$ and thus obtaining a grammar for $L$ whose starting symbol is $S''$.

The only problem is that I'm not sure how to formalize that idea and if it's even right and enough to prove that $L$ isn't context-free. Any ideas are welcome! Many thanks in advance!

# Answer
> 1 votes
Use closure properties to formalize your intuitions.

Context-free languages are closed under intersection with regular languages. In this case you can go from $L$ to (a language close to) $L''$ by observing that the string $xx^{rev}$ has the same first and last letter.

---
Tags: formal-languages, context-free, formal-grammars
---


# Question
Title: Given an array A and a minimum heap H which of the following are true?
I got this series of questions, each needs to either be proved or disproved (w/ example).

1. If $A$ is sorted in non-descending order, it is a valid minimum heap.
2. If $H$ is represented by $A$, therefore $A$ is a sorted array in non-descending order.
3. If $H$ is represented by $A$ (such that $A\[1\]$ is the first element), then for any $2i \< j$, the expression $A\[i\] \< A\[j\]$ is true
4. If $H$ is represented by $A$ (such that $A\[1\]$ is the first element), then the following is a sorted array:
5. If we sort each level in H separately, it will still be a valid minimum heap.

This was my proof:

1. `true`. Tested for with arrays $\[1\]$, $\[1,2\]$, $\[1,2,2\]$ that it works. Assume it works for any size array $k \< n$. Then set the array size to $k=n-1$. Added an element to the list. Since the list is already sorted, the new element can either be equal to the last or larger than the largest element in the list. So it will always be a leaf. Maintaining minimum heap.
2. `false`. $\[10,50,40\]$ is a valid minimum heap.
3. `?`. Apparently the answer is `false` but any heap I tested worked.. So I don't understand how this could be false.
4. `?`. I didn't really understand the order of operations here and could not find the series. Is it $2\*log(n)-1$ or $2\*log(n-1)$ or $2\*(log(n)-1)$ or ...? In any case, I couldn't make sense of it.
5. `true`. Same as (1) essentially. Assume for one level, two levels. Check for n levels.

How did I do? Also, help with 3-4 would be much appreciated!

# Answer
I think you are right in 1,2,5. I didnt really understand your proof for 5, since it should be different from 1.

Also, the proof for 1 can be greatly simplified: $A\[i\]\le A\[2i\],A\[2i+1\]$ is the definition of the minimality property in the heap, and you can directly show that using the fact your list is ordered.

About 3, try to create a big heap such that the left subheap has large values but the right subheap has small values

About 4, it doesn't really matter if its $2\log(n) -1$ or $2(\log(n)-1)$. Think of the series as a path from the root to some leaf. It should help you figure that out :)

I hope i managed to help you!
> 1 votes

---
Tags: data-structures, heaps
---


# Question
Title: Detecting and correcting collisions in (Zorbist) hashing to avoid errors in transposition table
**Context**

Say I have a transposition table that uses keys produced by (e.g. Zorbist) hashing game positions.

The table has a finite recycled memory (`key % p` is the `index` of the key, `p` is table size and prime).

That is, at `table[index(key)]` (there) we store `key` and (game position) `evaluation`.

So, when fetching cached evaluation of a game position `P` that was hashed into `key`:

* If `key` matches with key stored at `index(key)`, we return `evaluation` stored there.
* Else, we return default value (indicating "empty"), then rewrite `key` and `evaluation` there.

*(I've basically summarized how a simple transposition table can be implemented.)*

**Collision problem**

The problem is when two different game positions `P1` and `P2` are hashed into the same `key` (collision).

Say that we encounter position `P1` first. First time reading this `key`, "empty" value will be returned and `evaluation1` for `P1` will be stored in `table[index(key)]`. Second time reading this `key` (matching key at index), `evaluation1` for `P1` will be returned. This will either:

* Be fine, in the case that we encountered `P1` again.
* Be an error in the game evaluation, in the case that we encountered `P2`.

> How can this error be detected and corrected, efficently?

Apparently stockfish uses something like this Zorbist hashing and has verification *"Every entry is carefully validated before use,..."*, meaning that *"...this (game engine) would work even if every hash table access would return random numbers."*; But, how is this verification implemented?

# Answer
I don't have any particular experience with transposition tables in particular, but in general, the standard way to use a hash table stores the key (e.g., the value P1 or P2) in the entry, not the hash of the key. This way you can detect collisions.

Terminology: in standard hash table usage, the key is the value (i.e., the position, such as P1 or P2), not its hash.

There are many standard ways to resolve collisions in hash tables, e.g., using open chaining or closed chaining. See https://en.wikipedia.org/wiki/Hash\_table. However, I suspect those are not needed for transposition tables, as I suspect it is fine to return "unknown" in the event of a collision. If so, you might not need any of those methods.
> 0 votes

---
Tags: hash, hash-tables, hashing, board-games
---


# Question
Title: More efficient algorithm for Withdraw/Deposit position in bank statement
I am parsing bank statements where the transaction amount is ambiguous as to the withdraw/deposit nature and the balance is only given periodically.

My goal is to more efficiently, than brute force, find where the possible withdraw/deposit position should be.

For Example:

| Transaction ID | Withdraw/Deposit? | Balance |
| --- | --- | --- |
| 1 | \\$10 | \\$400 |
| 2 | \\$10 |  |
| 3 | \\$10 |  |
| 4 | \\$10 |  |
| 5 | \\$10 | \\$440 |

In the above example, to go from balance \\$400 to \\$440, transactions 2 to 5 need to be deposits.

My current algorithm brute forces it by simply testing all possible positional permutations, 16 in the worst case.

Of course this grows exponentially if there are fewer transactions with balances. 18 rows would be 262,144 potential attempts.

Collisions/Multiple answers to ambiguous sets are fine.

# Answer
This is an instance of the subset-sum problem. As such, you can use standard algorithms for the subset-sum problem to find candidate solutions -- e.g., the pseudopolynomial-time algorithm using dynamic programming is probably a reasonable choice.

Suppose the transaction amounts are $a\_1,\dots,a\_n$. Let $D$ be the difference in balances. Then our goal is to find a set $W$ of indices that represent the withdrawals (then $\[n\]\setminus W$ represents the deposits); this set should satisfy the condition $$\sum\_{i \in W} a\_i - \sum\_{i \notin W} a\_i = D.$$ This is equivalent to the condition $$\sum\_{i \in W} 2 a\_i = D + \sum\_{i=1}^n a\_i.$$ Let $T = D + \sum\_{i=1}^n a\_i$. Then $T$ is a known constant, and the goal is to find a subset of $2a\_1,\dots,2a\_n$ that sum to $T$. This is exactly the subset-sum problem.
> 2 votes

# Answer
Lets say you have $n$ unknown rows, and you started with $L$ money. After the $n$ transactions, you ended up with $L'$ money.

Basically, you want to know which of the $n$ unknown transactions were deposited and which were withdrawn. So, lets denote by $a\_i$ the money in transaction $i$.

Our task is to find $s\_i\in\\{-1,+1\\}$ such that: $L + \sum\_{i=1}^n s\_i\cdot a\_i = L'$, or equivalently, $\sum\_{i=1}^n s\_i\cdot a\_i=L'-L$.

If I remember correctly, you can order the $a\_i$'s in decreasing order and then apply some greedy algorithm. Im not 100% sure this is correct, but I hope I helped you formalize this question in such a way that can help you think and solve this problem :)
> 0 votes

---
Tags: algorithms
---


# Question
Title: Whats the difference between baremetal and full-featured in Embedded Systems?
Our professor talked about the "two" types of embedded systems in today's lecture, listing these.

1.) Baremetal

2.) Full-featured

Now I found out what he means by baremetal, but I can't find anything about "full-featured" in the whole WWW.

What do both terms mean exactly, and how do I distinguish between them? In which points do they differ?

# Answer
> 2 votes
I feel this terminology is not well defined and it is difficult to tell what it means out of context. What I believe your professor had in mind, relates to how many options are already "built in" in the system and are available for the user-programmer. I will explain.

Let's say you are engineering your own embedded card. You pick a CPU. You pick controllers. You decide the interfaces to the outer world. Etc. Then, once the card is manufactured, you will have to write the *drivers* by yourself - the pieces of software that allow the CPU to operate the system and mainly operate the external interfaces of your card. This would be a "bare metal" system, as it provides you (the programmer) no pre-defined drivers or operations.

On the other hand, you could base your system on a pre-designed micro-controller. Such a chip already includes a cpu along with many peripherals that interface the chip to the outer world (cf. a system on a chip). Operating this microcontroller chip is quite easy as the "hard work" was already done by the designers of the chip. Complex operations, e.g., converting digital information to analog information to be output by the analog output, are as easy as writing a byte to some pre-defined address. The microcontroller will know to take the information from that address and do all the rest. That is, the designers of that chip provide you with a "fully featured", easy to operate chip.

---
Tags: operating-systems
---


# Question
Title: What is the sense of distance in the definition of SSSP Problem?
I was studying about algorithms and came across the SSSP problem which stated:

Given connected weighted directed graph G(V,E) and a node S, find the shortest path from S to all nodes of the graph.

The distance of a path between 2 nodes is clear. It is the sum of the weights of the edges that make up the path.

But I don't understand **how to** define the distance between a node and **all** the other nodes.

Then I would like to clarify how the distance from a node to all other nodes is defined.

Thanks in advance.

# Answer
> 2 votes
It is defined by the function $d\_s(x)=distance(s,x)$. Basically, its just the distance function where we fix the source node to be $s$.

---
Tags: algorithms
---


# Question
Title: How should I evaluate time complexity for matrix if I have a fixed (constant) amount of rows and columns?
Suppose, that I have a four-by-four matrix and I want to print each element of it.

```
matrix = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]
for row in matrix
    for elem in row
         print(elem)

```

So, I have a questions:

a) Should I consider, that such iterating requires O(k + n) in terms of big O notation, where k is a number of rows and n is a number of columns? I mean, $\sum\_{i=1}^k1$ \+ $\sum\_{j=1}^n1$ = O(k + n), we sum number of iterations that are required for rows and number of ones for columns. If I should not, then what is wrong with my estimates or how should I calculate big O for a matrix?

b) Can not we say, that such algorithm requires constant amount of time, because we have a well-defined input - four-by-for matrix, can we? I would like to specify what I mean: if we have constant input, does it mean, that our algo requires constant amount of time to compute in terms of big O?

# Answer
> 1 votes
## For the first question

No, its actually $O(n\cdot k)$. To see why, we have two explanations.

1. The number of elements in the matrix is $n\cdot k$ and we run through all of them
2. The inner loop takes $O(n)$ time, but notice that we run it $k$ times. Hence, the actual summation that represents the running time is:

$$\sum\_{i=1}^k\sum\_{j=1}^n 1 = \sum\_{i=1}^k n = O(n \cdot k)$$

---

## For the second question

Yes, for as long as your input is well defined and with a constant size, as in this example. So actually, in this particular instance it takes $O(1)$ time. However this is usually not very interesting, since you are usually interested in more than just once matrix, or in the actual algorithm that performs the computation.

---
Tags: time-complexity, matrices, big-o-notation
---


# Question
Title: Select the optimal edge to add to a subgraph for minimal the shortest path
The question is as follows: Let G be connected, directed weighted Graph with non-negative edge weights and let s and t be vertices in G. Furthermore, let K be a subgraph of G with the same number of vertices but fewer edges.

The task is to add an edge that is in G but not in K such that the length of the shortest path between s and t is as small as possible with a constraint of O(|E|\*log|V|).

# Answer
Create two copies of $K$, and denote them by $K\_1, K\_2$. for a vertex $v$,we will denote by $v\_1$ its copy in $K\_1$ and by $v\_2$ its copy in $K\_2$.

Now, for each edge $e=(v,u)$ in $G$, add a (directed) edge between $v\_1\in K\_1$ and $u\_2\in K\_2$.

Now search for the smallest path between $s\_1$ and $t\_2$.

---

As a side note, the "trick" of cloning graphs and connecting them in a particular way is very useful in algorithms.
> 1 votes

---
Tags: shortest-path
---


# Question
Title: Find two nodes in a BST such that the root's key is the average of their keys without extra space in $\theta(n)$ worst case time
We can do this in $\theta(n^2)$ time if we calculate the average of all couples of nodes in the tree and compare it to the root, but this is too much time.

We can do this in linear time but with extra space by saving the in-order traversal of the left sub tree to array A, and the right sub tree to array B.

Now for the first node in A, scan B, until we find the matching node in B, or until we reach a too large element in B save that index as $k$.

If it is the second case, iterate over the rest of A and for each node:

Traverse B backwards from index $k-1$ until we find the matching node, or, if we reached a node that is too small, save the index as $k-2$ and repeat.

This takes $\theta(n)$ time but is using extra space. How can we do this in $\theta(n)$ and without extra space?

# Answer
> 0 votes
Your idea using the in-order traversal is good. Instead of constructing the in-order traversal, you can just traverse and get the element you currently need. That means you wont construct the full output of the in-order traversal, but instead you will get only one item at a time from that traversal, when you need it.

---
Tags: algorithms, binary-trees, binary-search-trees
---


title: When can a (max) heap be a BST?

text:
# Question
Title: When can a (max) heap be a BST?
Cheers, let's suppose we have a MAX heap which does not allow duplicate elements. Is it possible for this heap to be a BST ? Choose the right answer(s) below:

1. A heap can never be a BST
2. A heap is always a BST
3. A heap can be a BST if there is only one node inside it (root)
4. A heap can be BST if and only if it has up to 2 nodes

Which one would be an appropriate answer ? I would choose (3) and (4), and my explanations for all I give as an answer. Thanks!

# Answer
> 2 votes
To start off:

A **(max) heap** is a *complete binary tree*, in which every node's value is larger or equal to its children's values.

A **BST** is a *binary tree*, where every node has up to 2 children and every node's value is larger than all the values of its left subtree, and smaller than all the values of its right subtree.

1. The heap I thought of was just have one value, e.g. 8. Since it has no children, this tree alone is only made up of its root. This tree is complete and the root's values are larger that those of its children so it's a heap. This tree is also a BST with no children. So there is a heap which is also a BST.
2. This is of course false. Let max heap be:

Of course this is a max heap, but not a BST since 6 is placed to the right of 8.

3. Ιncorrect, but we need to see (4) to prove it
4. Up to two nodes means that we can either have 0, 1 or 2 nodes.

If we have 0 nodes, it holds.

If we have 1 node, it also holds, we proved that.

If we have 2 nodes, it also holds. Let a max-heap with 2 nodes. For it to be max-heap it must be a complete tree, so by definition the second node should be placed to the left of the first node (root). By definition of the max-heap, the second node also contains values smaller than that of the first node (root). This is also tree for a BST with 2 nodes. So it's correct. Since (3) says **only** , (3) is incorrect.

(If anything is incorrect please point it out. Thanks!)

---
Tags: binary-trees, heaps, binary-search-trees
---


# Question
Title: Z-function and the minimum string period
Let $s$ be a string of length $n$. One of the classical solutions to the problem of finding the smallest period $p$ of $s$ (that is, smallest $p$ such that $s$ can be obtained as a concatenation of the several copies of $p$) uses so-called $Z$-function. In words, $Z=Z\[0..n\]$ with $Z\[0\] = 0$ and $Z\[i\]$ is the length of the longest substring starting at position $i$ which coincides with some prefix of $s$. Given that, it is easy to solve the problem of the smallest period: we iterate through $i$, and if at some point we find $i$ such that $i + z\[i\] = n$ and $n$ modulo $i$ is $0$, then $s\[0..i-1\]$ is our answer.

Now back to the question. Suppose $s$, as before, is a prefix (of length no more than, say, $10^6$) of an infinite string $ppppppppp...$ obtained by concatenation of infinitely many copies of $p$. The goal is to recover the smallest possible $p$. Can we adopt the algorithm above to solve the problem?

Example: $s = abcabca$, the answer is $p=abc$.

# Answer
If at some point we find $i$ such that $i + z\[i\] \ge n$, then the smallest possible $p$ is $s\[0..i-1\]$.
> 2 votes

---
Tags: algorithms, strings, substrings
---


# Question
Title: Difference between convex hull algorithms
I was wondering what are the main differences in terms of efficiency of convex hull algorithms? Brute force algorithm is inefficient due to iterating over every three vertices in our set and its time complexity is $O(n^3)$ and probably is never good to use. But what about **Gift wrapping**, **Graham's scan** and **Chan's algorithm**? My understanding is that Graham scan and Chan's are efficient, Graham scan on smallers sets and Chan's algorithm on bigger sets but what are main pros and cons of those three algorithms? When to use which ?

# Answer
> 6 votes
If $n$ is the number of 2D points, let $h \le n$ be the number of points on the convex hull. Then:

* Gift wrapping takes time $\Theta(n h)$, which can be $\Theta(n^2)$ in the worst case. It is relatively simple to implement. Gift-wrapping generalizes to 3 dimensions and beyond.
* Graham scan takes time $O(n \log n)$. It is very easy to implement especially if you use the so-called monotone chain (also known as Andrew scan) variant. It does not generalize easily to 3 dimensions and beyond.
* Chan's algorithm takes time $O(n \log h)$, which is asymptotically optimal. It is somewhat more sophisticated to implement than the Graham scan. It generalizes to 3 dimensions.

Therefore, my suggestion would be:

* If your points are 2D, go for the Andrew scan. The difference between $\log h$ and $\log n$ may not be worth the extra complications of Chan's algorithm unless your dataset is truly huge.
* If your points are 3D, Chan's algorithm makes sense and is faster than gift-wrapping in the worst-case.
* If your points are in higher dimension than 3D, use gift-wrapping, since the other algorithms either don't work or require very complex adaptations anyway.

---
Tags: computational-geometry, convex-hull
---


# Question
Title: Can you help with a contex-free grammar for the language 0^n 1^m 2^k where n+ 2k >= m?
Can you help with a contex-free grammar for the language 0^n 1^m 2^k where n + 2k \>= m?

# Answer
Hint: The language is the same as $0^i 0^n 1^n (11)^k 2^k 2^j$. If I made no mistakes. Which is up to you to check. And yes, there’s a tiny mistake.
> 0 votes

---
Tags: formal-grammars
---


# Question
Title: Can we supervise on the hidden states of RNN?
I'm trying to generate some history-dependent model with machine learning, whose underline physical model has a clear definition of its "internal state variable" (a state derived from historical inputs) and how this variable interacts with the inputs to get the outputs. Mathematically this reads: $y\_t=f(x\_t,h\_t)$, $h\_t=g(x\_1, ..., x\_{t-1})$ .

Intuitively, this can be realized by RNN(or LSTM/GRU). Now I wonder if we can add the supervision on state variables to the loss function to improve prediction. For instance, we extract the hidden states $H$ output from our RNN and pass them through another branch of feed-forward network to predict the internal state variables $h$. The loss function then has two parts, one is for model outputs $\sum (y-\hat{y})^2$, and the other is for model internal states $\sum(h-\hat{h})^2$.

Any insight toward the following questions are welcomed:

* Will this approach work? (Does it make sense?)
* Potential issues?

I'll also be really grateful if anybody can indicate closely related works in the answers! Thanks in advance!

# Answer
> 1 votes
There are several examples of performing supervision on hidden states for history dependent models.

**Latent variables**

Loss functions are commonly applied to internal states such as latent variables in *variational autoencoders* (VAEs).

**Hidden states**

Supervision **directly on hidden states**, as opposed to latent states in RNNs, has been performed for imposing sparsity, as in \[\]:

> In order to impose sparsity, we introduce an L1-norm loss term over the output gate at layer $l$ as
>
> $$\mathcal{L}^S(o^l(x,\theta)) = \sum\_{1 \leq b \leq B} \sum\_{1 \leq \> t\leq T} | o\_t^l(x^{(b)})|.$$

**Autoregressive Neural Networks**

Additional, *auxilliary latent variables* have been used to increase the flexibility of variational inference. An example of this is given in \[\] where hidden state $\mathbf{h}$ and latent state $\mathbf{z}\_{t-1}$ are fed into an autoregressive neural network, with final output $\mathbf{z}\_t$.

# Reference

Learning Sparse Hidden States in Long Short-Term Memory, (paper)

Improved Variational Inference with Inverse Autoregressive Flow, (arxiv)

# Answer
> 1 votes
Your physical model looks dubious. It is a bit unusual and might not be a perfect match for a RNN/LSTM. I am hoping that your physical model is actually $y\_t=f(x\_t,h\_t)$, $h\_t=g(x\_{t-1},h\_{t-1})$. If so, then this is a good fit for the kind of supervision on internal states that you plan to do -- and the answer to your question is yes, you can do this, and it is a sensible thing to do.

---
Tags: machine-learning, neural-networks
---


# Question
Title: Is there an FPTAS for 3-way number partitioning?
The maximization problem of the 3-way number partitioning reads as follows: given $n$ positive integers, partition them into 3 subsets such that the smallest sum is as large as possible. It is known to be NP-hard, but does it have an FPTAS?

I found answers for some related problems:

Is there any FPTAS for 3-way number partitioning?

# Answer
> 2 votes
I found an FPTAS for a very similar problem: finding a partition such that the *largest* sum is as *small* as possible. This problem is equivalent to the problem of identical-machines scheduling: there are $m$ identical machines (in our case $m=3$), and $n$ jobs with different processing times, and we need to assign jobs to machines such that the latest completion time is as early as possible. In this paper:

> Sartaj K. Sahni (1976). Algorithms for Scheduling Independent Tasks. Journal of the ACM. 23 (1): 116–127.

there is an algorithm that attains at most $1+\epsilon$ of the minimum in time $O(n\cdot (n^2 / \epsilon)^{m-1})$, which is an FPTAS for any fixed $m$.

However, this does not answer the original problem, which is to make the *smallest* sum as *large* as possible.

---
Tags: algorithms, approximation, polynomial-time, partitions, subset-sum
---


# Question
Title: How to prove that $L = \{w\in\{a,b\}^*\mid w = uav \text{ and } |u| = |v|\}$ is not a regular language
$L = \\{w\in\\{a,b\\}^\*\mid w = uav \text{ and } |u| = |v|\\}$

I know to use the pump lemma, but I don’t know how to use it correctly.

# Answer
> 1 votes
Suppose towards a contradiction that $L$ is regular and let $p$ be its pumping length. Consider $w = b^pab^p \in L$. By the pumping lemma there is some integer $1\le i \le p$ such that $b^{p+ki} a b^p \in L$ for all choices of an integer $k \ge -1$. However, choosing $k=-1$ yields $b^{p-i} a b^p \not\in L$, which provides the sought contradiction.

---
Tags: regular-languages, pumping-lemma
---


# Question
Title: Is it possible to reverse engineer cellular automata?
Given a sequence of states of a given cellular automata, is it possible to construct the rules of the automata & hence predict the next state? To be clear, initially the rules are NOT known but the output sequence is.

# Answer
> 1 votes
This problem is somewhat similar to programming by example https://en.wikipedia.org/wiki/Programming\_by\_example

In this paradigm, a system is given a sequence of states (examples) and asked to synthesize a program that could generate that sequence. The system could be given many different examples and asked to synthesize a program that works with all provided examples.

To answer your question, yes it is possible. The simplest way to do this is to write a program that simply "remembers" all of the examples and outputs successive states when appropriate. If the synthesized program is asked to complete a step it has not seen in an example, then it simply outputs something arbitrary but deterministic.

This program may not give you what you want and would surely but large in size (larger than all of the provided examples combined); It can serve as an upper bound in program size. It is more interesting to minimize the size of this program and hope that the smaller program makes generalizations about the inputted examples and is thus more useful. If this minimal program makes a mistake somewhere (assuming you have distinct sets of examples for 'learning' and 'testing') then you can provide it with more examples that correct its mistakes.

# Answer
> 1 votes
As long appropriate initial constraints on the CA rule (and, in particular, on the neighborhood size) are provided, yes, this is possible.

In fact, the basic algorithm is quite simple. It relies on the fact that the transition rule for a CA with a finite number of states and a finite neighborhood size has a finite number of possible inputs, and can thus be generically represented as a *rule table* mapping each possible input neighborhood to an output cell state:

1. Start with an initial rule table mapping each neighborhood to an extra "unknown" state.
2. For each cell in the input sequence (except for the final step), look up the output cell state for its neighborhood in the rule table. If it's currently unknown, set it to the actual observed state of the cell in the next generation. Otherwise, if it doesn't match the observed next-generation state, abort with an error.
3. Once all cells have been successfully processed, output the resulting rule table.

Note that the resulting rule table may still have some unknown output cell states if the corresponding neighborhoods never occur in the input sequence. Replacing such unknown cell states with any valid cell state will produce a CA rule compatible with the input sequence.

It is not, of course, guaranteed that each of these possible rules will produce the same next state. However, if the input is sufficiently representative of typical neighborhoods that occur during the evolution of the CA then this is quite likely to be the case.

---

Also note that if the given input sequence consists only of slices of a larger lattice, rather than the entire state of a finite lattice with known boundary conditions, then the neighborhoods of cells near the spatial edges of the input sequence may not be fully defined.

Such cells cannot be processed as described in step 2 above. We can, of course, simply skip such cells in step 2 and just hope that the remaining cell transitions in the input are sufficient to define the CA rule, and then later verify that the resulting rule is also compatible with the skipped edge cells.

More generally, to ensure that the rule(s) we find are exactly those compatible with the given input even at the edges, we'd need to find some self-consistent assignment of cell states not only to the neighborhoods in the rule table but also to cells outside the edges of the input slices. In general, this can be formulated as a boolean satisfiability (SAT) problem and passed to a general-purpose SAT solver. In fact, there already exist programs that can do exactly that, at least for certain classes of CA rules, such as Logic Life Search (LLS), which can perform exactly this kind of search for a class of CA rules that includes e.g. Conway's Game of Life.

(In fact, LLS can do a lot more than that — it can also e.g. fill in gaps in the input sequence or even search *ex nihilo* for rules and/or sequences that satisfy certain boundary conditions, such as ones with the initial input state reappearing after $n$ generations, but shifted a certain number of cells — i.e. for spaceships.)

---
Tags: cellular-automata
---


# Question
Title: What is the optimal solution for the following "Largest lexicographical string with <= K consecutive elements" problem? Why is my answer wrong?
This is a simple question I ran into in a remote interview:

Given a collection of letters, permute them (or one of its subset) into a string such that:

* each letter can only be repeated for \<= 11 times sequentially in the permutation
* the string is lexicographically the largest

For one case, the collection of letters is:

zzzzzzzzzzzzzzzzzzzzzzzzzzzzyzzzzzzzyzzzyzzzzzzyzyzxyzzzzzzyzzxzyzyzyzzzyzyzzzzzzzyzzzzzzzzzzzzzzzzyzzzzzzzzzzzzzzzyyzzzzzzzzzzzzzzzzzzzzzzzyzzzyzzzzzzzyzzzzzzzzzzzyyzzzzzzzzzzyzzzzyzzzyzzzzzzzzzzzzyzzzzzzzzzzzzzyzzzzzzzzyzzzzzzzzzyzzzzzzyyzzyzzzzzzzzzzzzzzyzzzzzzzzzzzzzzzzzzzzzzzzzzyzzyyyyyzzzzzzzzzyzyzzzzzzzzzzzzzzxzzzzzzzyzzzzzzzzzyyzzzzyzzzzzzzzzzzzzzyzzzzzyzzzzzzzyzzzzzzzzzzzzzzyyzyzzzzyzzzyzzzzzzyzzzzzzzzyzzzzzzzyzzzzzzzzzzzzxxzzzzzzzzzzzzzzzzzzzzzxyzyzzzzzzzzzzzzzzzzzzyzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzyzzzzzzzzyzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzxxzyzyzzyzzzzzzyzzzzxzzzzzzzzzzyzzzzyzzzzzzyzyzzzzzyzzyzyzzzzzzzzzzzzzzzzzzzzzzzzzzzzyzzzzzzzzyzzyyzyyzzzzzzyzyzzzzzzzzzyzzxzzzzyzzzyzzzyyzzzzzxzzzyyzzyzzzxyzzzzzzzzzzzzzyzyzzzzzzzzzzzzzzzyzzzyzzzzzzzzzyzzzzzzzzzzzxzzzzzzzzzzyzzyzzzzzzzzzzzzzzyyzyzzzyzzzzzzyzzzzzxzzzzzzzzzzzzzzzzzzzzzzzzzzzyyzyzzzzzzzzzzzzzzzzzyzzzzzzzzzzzzzzzzzzzzzyzzzzzzzzzyzzzzzzzzyzzzzzzzzzzzzzzzyzzzzzzxzyzxyzzzzzzzzzzzzzzzzzyzzzxzzzzzzzzzzzyzzzzzz

once converted to a multi-set, it contains:

* 17 'x'
* 114 'y'
* 869 'z'

My answer for this case is:

zzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyyyyyyyyyyyxyyyyyyyyyyyxyyyyyyyyyyyxyyxxxyxxxxxxxxxxx

Then the interviewer AI kept telling me that my answer is sub-optimal.

I've tried to find a better answer but it appears that none is available. Can you give a better answer for this case?

(Sorry due to the NDA I'm not allowed to write my code here, but it is a simple algorithm of greedy finite-state automaton with no backtracking + preemptive pruning)

# Answer
"permute them (or **one of its subset**) into a string"

This subset is better:

zzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyyyyyyyyyyyxyyyyyyyyyyyxyyyyyyyyyyyx**yyy**
> 3 votes

---
Tags: sorting, strings
---


# Question
Title: How are extremely large integers stored and implemented in programming languages?
We have data types like `int` and `long` etc. which can store just a few bytes of integers. But when we are implementing cryptographic algorithms like RSA or Elliptic Curves, we know that the key values are usually 1024 bits long.

How is this implemented in C and C++?

I had gone through `/crypto/rsa.c` in the Linux kernel which stored these values in some sort of data type called MPI which was included by a module named `<linux/mpi.h>`. It would be nice if someone could explain what this MPI thing was.

# Answer
> 13 votes
MPI stands for Multiple Precision Integer. Multiple precision arithmetic is what you need when you work with integer types that go beyond the machine width $w$.

The basic idea is simple, you represent a large integer with multiple fixed-width words where the i-th word is the i-th "digit" in base B where $B = 2^w$. For example, most current machines are 64-bit so the width $w$ is 64, so with a single word you can represent unsigned integers up $2^{64}-1$. To represent integers larger than $2^{64}-1$, say a 1024-bit integer as in your RSA example, you use $\lceil{1024 / 64}\rceil = 16$ words $a\_0, a\_1, a\_2, \ldots, a\_{15}$. Then your integer $x$ of choice is encoded as $$ x = a\_0 + 2^{64} a\_1 + 2^{2\*64} a\_2 + \ldots + 2^{15\*64} a\_{15}. $$ Note that this is essentially a $1024$-bit representation, the only difference is that the bits are grouped into blocks of size 64.

Operations like additions, multiplication etcetera are implemented by building on machine addition, multiplication and so on, but of course additional work is needed to take care of carries and the like. I am not sure what the Linux kernel is using, but in the GNU/Linux world a widely used multiple precision arithmetic library is the GMP.

---
Tags: cryptography, c++, c
---


# Question
Title: Why is $EQ_{cfg}$ not recognizable but is co-turing-recognizable
I've seen the proof that $EQ\_{CFG}$ is not recognizable but its complement is, my problem is that in the proof that it's complement is recognizable, it says that we test every string in $\sum^\*$ and checks if it's generated by one of the $CFG$s but not the other. My question is that why don't we use this method to solve $EQ\_{CFG}$ problem, where we iterate on all possible strings in $\sum^\*$ and confirm that it either gets generated or not by both $CFGs$

# Answer
> 1 votes
The difference here comes from the requirement to *halt*.

An algorithm that returns "true", must always do so in finite time, hence, it will never be able to go through all strings in $\Sigma^\*$ and confirm that it is either generated not by both CFGs.

However, for the complement problem, the requirement changes drastically: It is enough to show **one** string $w$ such that $w\in L(G\_1)$ and $w\notin L(G\_2)$ (or vice versa) to know that $L(G\_1)\neq L(G\_2)$. This allows us to find this string $w$ and halt when we see it, without the need to continue and check more strings.

I hope this gave you some intuition :) (P.S, this is **not** a formal proof)

---
Tags: turing-machines, undecidability, computation-models
---


# Question
Title: What is a generalized automaton that has ability to look up anything in memory from environment?
An automaton determines its next state from the current state and the next input symbol. A pushdown automaton adds a stack which you can push/pop/read from. But then there are probably a lot of intermediate things to a completely generic system where each transition is based on the current transition and *any information from the environment*. For example, a traditional function in an imperative language like JavaScript is essentially this sort of thing, where it goes to a function, then based on the lexical and global scopes, it figures out what input to pass to the next function (essentially). What is this sort of system? How to formalize this into an automaton sort of thing?

Is this just a register machine? If so, what is the best formalization of the mathematical model (in terms of research papers or books) which is freely available? Or better yet, what is the mathematical model listed explicitly here? If not, what is it?

Wondering if there is anything that models this sort of system using *states* and such. Wondering what the relation is to a FSM, and how to translate one to the other if possible, or at least relate them.

# Answer
The theory you seem to be looking for is called AFA or "abstract family of acceptors". You can read an early version of it on wikipedia, but its notions are hard to parse, without examples and such.

For AFA theory we first define an *abstract type of memory*. This is very similar to abstract data type now common in data structures. Such a memory type first defines the domain of the memory, its *storage configurations*. For pushdown automata that is a stack (formalized as a string), for a register machine that is a sequence of natural numbers, for a TM that is a (working) tape.

Then the memory type needs tests and operations. Tests are Boolean functions that are applied to the memory. For a pushdown we can check emptyness or verify the topmost symbol. Operations are applied to the memory. For the PDA the operations are of obviously pop and push. We have to be careful, the operations can be partial.

Now with memory type $X$ we can build an $X$-*automaton*. Such an automaton is basically a finite state automaton with its usual one-way input tape, equipped with an additional memory device of type $X$. Instructions of the automaton are roughly of the form $(p,a,T,F,q)$ That is short for:

> In state $p$, reading $a$ from the input, and configuration $C$, we can move, provided $C$ satisfies the combination of tests $T$, the new state will be $q$, and the new configuration will be $F(C)$ obtained by applying the sequence $F$ of instructions.

With the usual initial and final states one can define computations (that should start with specific initial memory configurations) and the family of languages accepted by such $X$-automata.
> 1 votes

---
Tags: automata, computation-models
---


# Question
Title: Where will the TLB entries be stored if the cache memory get full (or can this situation occur)?
As we know that the entries of the TLB get copied into the cache memory once another process is chosen to be run by the scheduler. But what if the cache memory is full and there is no space left for the entries to be copied?

# Answer
Your premise appears to be faulty. As far as I know, normally no such thing happens on a context switch. Either the TLB is left unchanged; or the TLB has entries "evicted" (removed from the TLB; but not copied somewhere else, they are just deleted from the TLB).
> 1 votes

---
Tags: operating-systems, memory-management
---


# Question
Title: What is the closure of context-free languages under finite intersections?
Famously the intersection of context-free languages need not be context-free. On the other hand the intersection of context-sensitive languages is context-sensitive.

So this leads to the question: what is the closure of context-free languages under finite intersections? Does this class of formal languages have a name? Do we get all context-sensitive languages this way?

# Answer
> 9 votes
The intersections of context-free languages will never reach the full family of context-sensitive languages.

> The class of languages expressible as the intersection of $k$ context-free languages is shown to be properly contained within the class of languages expressible as the intersection of $k + 1$ context-free languages. Hence an infinite hierarchy of classes of languages is exhibited between the class of context-sensitive languages and the class of context-free languages.

Quoted from: An infinite hierarchy of intersections of context-free languages. Leonard Y. Liu & Peter Weiner Mathematical Systems Theory 7 (1973) 185–192. https://doi.org/10.1007/BF01762237 (paywall)

An explicit example is also given, with a reference to the PhD thesis of the first author.

> not every context-sensitive language is expressible as an intersection of a finite number of context-free languages, e.g., $L = \\{ a^{2^n} \mid n \in \mathbb N \\}$.

Note however, that context-free languages over a one letter alphabet are in fact regular. That means that if a finite number of CF languages intersects to a language in $\\{a\\}^\*$, then we can as well assume each of these languages to be within $\\{a\\}^\*$. This implies we intersect a finite number of regular languages, which is regular again.

# Answer
> 5 votes
Intersections (and more generally, Boolean combinations) of context-free languages are included in the class LOGCFL, which is a quite weak subclass of P (on a low level of the NC hierarchy). Thus, it is very far from the class of all context-sensitive languages. In particular, $\mathrm{LOGCFL\subseteq DSPACE}((\log n)^2)$, while $\mathrm{CSL=NSPACE}(n)$; the space hierarchy theorem ensures that these classes are different, and that there are many intermediate levels of conplexity in between them.

---
Tags: complexity-theory, formal-languages, context-free, formal-grammars, context-sensitive
---


# Question
Title: Understanding the upper bound proof for quick sort
I'm trying to understand the average run time of quicksort which is $O(n \log n)$.

I understand the intuition behind it: if we partition array $A$ to e.g. $\alpha n $ and $(1-\alpha)n$ then we essentially partition $\log n$ times and each partition performs $n$ comparisons. And this happens with high probability; e.g. partition to $c$ and $n-c$ for a constant $c$ is less likely because $c/n$ is smaller than $\alpha n/n$ for large $n$.

Now I want to prove this bound. The first observation is that if we consider a sorted array $A'$, then elements $A'\[i\]$ and $A'\[j\]$ are compared at most once. This is because we only compare with pivot and then remove it during partitioning. Therefore the expected number of comparisons becomes

\begin{align} \mathbb{E}\left\[\sum\_{i=1}^n \sum\_{j=i+1}^n 1\\{A'\[i\] \text{ compared with } A'\[j\]\\} \right\] = \sum\_{i=1}^n \sum\_{j=i+1}^n P\\{A'\[i\] \text{ compared with } A'\[j\]\\} \end{align}

It remains to compute the probability of comparing $A'\[i\]$ and $A'\[j\]$. Now one argument is that if we pick a pivot before $A'\[i\]$ or after $A'\[j\]$, then $A'\[i\]$ and $A'\[j\]$ remain together in the next subarray. So this probability becomes the probability of choosing $A'\[i\]$ or $A'\[j\]$ as a pivot in subarray $A'\[i,...,j\]$ which is simply $2/(j-i+1)$. My question is: Why do we only need to compute the probability of choosing $A'\[i\]$ or $A'\[j\]$ as a pivot *only* in subarray $A'\[i,...,j\]$?

I'm confused because I think at the beginning we have an array of length $n$ so there is a $2/n$ chance for picking them as a pivot, some chance $x\_1$ to pick a pivot between them (so they'll never be compared), and some chance $1-x\_1-2/n$ to pick a pivot before or after them (so they remain in the same subarray and may be computed). In the last case, again the probability of picking one $A'\[i\]$ and $A'\[j\]$ depends on the array length. How can I show that this line of thinking also gives the same runtime?

At the same time, it makes intuitive sense that the probability of comparison depends only on the number of elements between $A'\[i\]$ and $A'\[j\]$.

# Answer
> 2 votes
You have misunderstood the analysis of randomized quicksort.

The idea is that we can view pivot selection in randomized quicksort in the following way. We first select a permutation $\pi$ on the elements on the array. When choosing a pivot among some subarray $B$, we choose the element of $B$ which appears first in $\pi$.

Suppose that $i \< j$. We are interested in knowing whether two elements $A'\[i\]$ and $A'\[j\]$ will ever be compared. In order for them to be compared, $A'\[i\]$ or $A'\[j\]$ needs to be chosen as pivot for some subarray which contains both of them. The elements $A'\[i\]$ and $A'\[j\]$ remain in the same subarray as long as none of $A'\[i+1\],\ldots,A'\[j-1\]$ is chosen as pivot. Hence $A'\[i\]$ and $A'\[j\]$ will be compared if in the permutation $\pi$, the first element among $A'\[i\],\ldots,A'\[j\]$ is either $A'\[i\]$ or $A'\[j\]$. This happens with probability $2/(j-i+1)$. We conclude that the expected number of comparisons is $$ \sum\_{1 \leq i \< j \leq n} \frac{2}{j-i+1} = \Theta(n\log n). $$ This expression represents the *expected* number of comparisons, not an *upper bound* on the number of comparisons. In the worst case, *all* elements will be compared to one another. The best upper bound on the number of comparisons is $\binom{n}{2}$.

---

Another way to estimate the expected number of comparisons is using your intuition. Denoting the expected number of comparisons by $T(n)$, we have $$ T(n) = n-1 + \frac{1}{n} \sum\_{m=0}^{n-1} (T(m) + T(n-1-m)) = n-1 + \frac{2}{n} \sum\_{m=0}^{n-1} T(m). $$ We also have $$ T(n+1) = n + \frac{2}{n+1} \sum\_{m=0}^n T(m). $$ Subtracting, we get $$ (n+1) T(n+1) - n T(n) = 2n + 2T(n), $$ and so $$ \frac{T(n+1)}{n+2} = \frac{T(n)}{n+1} + \frac{2n}{(n+1)(n+2)}. $$ It follows that $$ T(n) = (n+1) \sum\_{m=1}^{n-1} \frac{2m}{(m+1)(m+2)} = \Theta(n \log n). $$

---
Tags: algorithms, algorithm-analysis, runtime-analysis, sorting, quicksort
---


# Question
Title: sentiment analysis by sentence similarity
How can sentence similarity be used for sentiment analysis? I know we have sentence Bert which can use cosine sim to measure the distance between to vectors (the sentence embeddings), but has anyone used to for sentiment analysis specifically?

# Answer
Using a probabilistic language modelling approach to compute the probability of a sentence brings a performance concern.

If we had the following set of documents:

q1: I like this movie

d1: Such a great film

d2: I hated this movie

Using a probabilistic language model we would be able to infer that q1 is probabilistically closer to d2 than to d1, despite that being true we would be wrongly classifying the documents.

In order to compute sentiment analysis a text classifier is usually needed, using supervised machine learning classification methods such as Naïve Bayes, Logistic Regression, SVM, K-nearest Neighbours.
> 1 votes

# Answer
I expect that measuring the similarity of two sentences probably isn't a useful way to do sentiment analysis. There are better methods for sentiment analysis, so rather than adopting the artificial constraint that it must work by measuring the similarity of two sentences, it's better to use standard methods (I expect they will perform better).
> 0 votes

---
Tags: natural-language-processing
---