# Question
Title: Closed formula for two variable recurrence
I would like to know if there exists a closed form formula to the following recurrence:

* $f(s, 0) = 1$
* $f(s,b) = \displaystyle\sum\_{i=1}^{min(s, b)} \left\[ (s-i+1)\times f(i, b-i) \right\] $

This recurrence gives the solution to problem F of the ICPC Latin American regionals of 2019.

The problem itself can be solved in $O(n^2)$ by using dynamic programming and keeping a matrix of precomputed sums. I'm just curious about if there is some technique that allows obtaining a closed formula to recurrences like this, so I can solve it in better runtime complexity.

# Answer
I do not have a strong mathematical background, but I am afraid that recursive functions cannot always been written in closed form.

ex1.

f(n) = sum(\[1,2,..,n\]) can be written as
f(1) = 1
f(n) = n + f(n-1)

Of course f(n) = n\*(n+1)/2

ex2.

f(n) = prod(\[1,2,3,4,..n\]) = n!
f(1) = 1
f(n) = n * f(n-1)

No known closed formula :( (I don't even know how to prove something like this)

In your case, I find it extremely difficult because your recursion makes use of an if statement under the min() function.
> 1 votes

---
Tags: recurrence-relation
---


# Question
Title: Proving the language $L= \{0^n 1^m \space | \space m \equiv 0 \space mod \space n, \space n \geq 2 \}$ is not regular using the pumping lemma
I am trying to learn about applying the pumping lemma and I'm not really sure how to go about proving this language isn't regular with the pumping lemma:

$L= \\{0^n 1^m \space | \space m \equiv 0 \space mod \space n, \space n \geq 2 \\}$

Now I realize that the condition $m \equiv 0 \space mod \space n$, is essentially saying that $m$ is some multiple of $n$. Is it possible that could you go about proving that $L$ is not regular in the way that you can prove that $L = \\{0^n 1^n\\}$ is not regular since $m$ is a multiple of $n$, since $m = kn$ (where $k$ is some integer)?

***Updated:***

-- My attempt at the proof:

If the language $L$ is regular, then by the pumping lemma $\exists \space p \space | \space \forall s \in L \cap \Sigma ^{\geq p} $.

Next by the pumping lemma $\exists x, y, z : s = xyz$, where $s$ is a string such that:

(1) $|y|\geq1$

(2) $|xy|\leq p$

(3) $\forall i\geq0, xy^iz \in L$

Now suppose we let $m = kp$, where $k$ is some integer, let the string $s = 0^p 1^{kp}, s\in L$ and $|s|\geq p$. By the pumping lemma the decomposition of $s$ is defined by $s = xyz$. Now we show that $\forall x, y, z$ that (1)-(3) do not hold.

If (1) and (2) hold, then $s=0^p1^{kp} = xyz$, with $|xy|\leq p$ and $|y|\geq 1$.

So $x = 0^u, y=0^v, z=0^w1^{kp}$

$u+v \leq p$, $v \geq 1 $, $w \geq 0$

$u+v+w = kp$

But (3) fails for $i=2$ since $xy^2z = 0^u0^v0^v0^w1^{kp} = 0^{u+2v+w}1^{kp} \not\in L$ since $u+2v+w \neq kp $

Hence $L$ is *not* a regular language.

Is this the correct way to go about this proof?

# Answer
Here is a nicer proof, (implicitly) using the Myhill-Nerode criterion. Let $p\_1,p\_2,p\_3,\ldots$ be the list of all primes, and consider the words $x\_i = 0^{p\_i}$, $y\_i = 1^{p\_i}$. Then $x\_i y\_i \in L$ while $x\_i y\_j \notin L$ for $i \neq j$. So given a DFA for $L$, if $\sigma\_i$ is the state that the DFA is at after reading $x\_i$, we must have $\sigma\_i \neq \sigma\_j$ for $i \neq j$ (why?), so the DFA must have infinitely many states.
> 3 votes

# Answer
A bit simpler: Assume $L$ is regular, so it satisfies the pumping lemma. Call the constant of the lemma $p$, and take the string $w = 0^p 1^p$, we have that $w \in L$ and $\lvert w \rvert = 2 p \ge p$. By the lemma, we can write $w = x y z$ with $\lvert x y \rvert \le p$, $y \ne \epsilon$, so that for all $k \ge 0$ we have $x y^k z \in L$. Now $y$ is $0^r$, for $1 \le r \le N \le p$, if we consider $k = 2$ we have $x y^2 z = 0^{p + r} 1^p$, and certainly $p \not\equiv 0 \pmod{p + r}$, contradiction.
> 0 votes

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


# Question
Title: Why does this Pumping Lemma example show irregularity?
the first 4 steps of these are my own work - however the following steps are from my book, and I don't understand what it's saying, and I have not found any resources. Could someone clarify this?

Show C = {w|w has an equal number of 0s and 1s} is not regular. Show by contradiction.

1) Assume C is regular, and thus the Pumping Lemma conditions hold.

2) Assume a pumping length of `p`.

3) Let the string `s =` $0^p$$1^p$.

4) `s = xyz` and let `x` and `z` be the empty string. Therefor for i \> 0, x$y^i$z always has an equal number of 0s and 1s, so it seems like it can be pumped.

5) But since condition 3 of the pumping lemma says that `|xy| <= p`, then `y` must consist of only 0s.

How does step 5 justify `y` consisting of only zeros? If we said ealrier that `x` and `z` are the empty strings, then doesn't that imply that `s = y` = $0^p$ $1^p$?

How does this make y only zeros?

Thanks!

# Answer
> 4 votes
$s$ consists of $p$ zeroes followed by, well, it doesn't matter what. $xy$ is the start of $s$ and consists of at most the first $p$ characters of $s$. All of those $p$ characters are zeroes so, in particular, $y$ is all zeros.

Step 4 of your proof is invalid because you can't choose what $x$ and $z$ are. The pumping lemma tells you that, if $C$ is regular, there is *some* way of writing every appropriate $s\in C$ as $s=xyz$ such that blah, blah, blah. It doesn't tell you that writing $s=\varepsilon y\varepsilon$ will work.

# Answer
> 4 votes
You cannot proceed in this way. The Pumping Lemma for regular languages tells us that if a language $L$ is regular, then there exists a $p \geq 0$ such that every $s \in L$ such that $\lvert s \rvert \ge p$ can be partitioned as $s = xyz$ in such a way that

1. $|y| \> 0$
2. $|xy| \leq p$
3. $xy^iz \in L$ for all $i \geq 0$

To show that a language $L$ fails to be regular, we must show that for *any* choice of $p$ we can find an $s \in L$ such that *every possible partition* of $s$ will violate one or more of the above three conditions.

In your attempted solution, your candidate string has length $2p$. Condition 2 tells us that $y$ *must* occur within the first $p$ symbols and must therefore consist of $0$s only.

If condition 1 is to also hold, $y$ must be non-empty. But then $xy^2z \notin L$, as this string will have more occurrences of $0$s than of $1$s. So condition 3 cannot hold, if we require conditions 1 and 2 to hold.

Your misunderstanding is one that students often make; they assume that the partition must be one that somehow "magically pairs off" the symbols according to its shape: If the candidate string has a part consisting of $0$s followed by a part consisting of $1$s, then the initial substring $x$ must somehow consist of all the $0$s. *This is not the case.* That you then also assume that $x$ is empty, shows an internal contradiction: At the same time you claim that $x$ *must* consist of all $0$s and that $x$ can be chosen to be any string whatsoever, in this case the empty string.

# Answer
> 3 votes
We cannot assume $x$ and $z$ to be empty strings. It can be understood as follows: If we try and construct the automaton there has to be some part of the string which leads it to the final state from the state which contains loops.

for further reference refer to this post: In context of pumping lemma for regular languages .

By taking proper assumptions we can see that $|xy| \leq p$ which implies $xy$ can contain only zeroes, so pumping $y$ will create a string which has more zeroes than ones.

# Answer
> 1 votes
I's easy to understand the pumping lemma if you see where it comes from.

Assume L is regular, so there is a finite state machine. Say that state machine has p-1 states. That's where the p comes from.

Now parse any string of length p or more that is in the language. Since there are only p-1 states, somewhere within parsing the first p characters of the string you must enter some state S twice.

Let x be the string that gets you to state S for the first time (x could be an empty string if S is the initial state). Let y be the string that gets you from S back to S (y has a length \> 0, the length of x + y is less than p). z is the rest of the string starting with S. If you repeat y as often as you like, the FSM will take you back to S again and again every time you repeat S. So $x y^n z$ is an element of L for every n ≥ 0.

# Answer
> 0 votes
Suppose **C** is a regular language and let **P** be the **'pumping length'**.Consider the string **S = aPbP**. Note that **S *ε* C** and **|S| = 2P ≥ P**, so the pumping lemma will hold. Then as you stated we have to divide the string in to 3 parts ***xyz***. The idea behind this is to split the whole string into parts in such a form that '**part**' of it can be pumped or repeated more times and even then the language string will be regular(This is explained by the condition **xyiz ε C** for all **i ≥ 0**).

The automation requires an initial state and a final state to end(we consider acceptor and not transducer ). So we cannot simply assume **x** and **z** both as **0**.

So here we have to take **P** in such a way that it satisfies the condition for pumping lemma and we can conclude that it contains only **P** characters which in turn contains only **0**'s here. Eg: take **P = 3**, then `S = aaabbb`, split **S** into **xyz** in such a way that **|y| \> 0** and **|xy|≤ P**. Since the first 3 symbols of **S** are all **a**'s and **z** forms the rest of the string. say **|x| = 1** and **|y| = 2** then **|z|= 3**. After this if for **xyiz**, take `i = 2`, you will get the string `'aaaaabbb'` which is not in string **S** and hence by contradiction its not a regular language.

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


# Question
Title: Special Monotone SAT problem: NP complete?
Say we have the set $X=\\{ x\_1, x\_2, \dots \\}$ of variables. Then we consider the following problem: Is the formula $$\bigwedge\_{(a,b,c) \in A}(a \vee b \vee c) \wedge \bigwedge\_{(a,b,c) \in B}(\neg a \vee \neg b \vee \neg c)$$ for $A,B \subset X^3$ satisfiable.

This problem has been called *Montone-3-Sat* before and it is known to be NP-complete.

My question is: If we assume that $A=B$ has to hold, is the problem still NP-complete? I.e. we ask if we can color vertices in such a way that always specific three of them do not have the same color.

The results I have found on the internet confuse me a bit, because I believe the definitions of Monotone-Sat, Not-All-Equal-Sat are not always the same. The definitions of NAE3SAT I've seen allow arbitrary 3-CNF-formulae as input, so this doesn't seem the same as that.

# Answer
> 3 votes
The variant where $A=B$ is known as monotone not-all-equal 3-satisfiability, i.e., Monotone NAE3SAT. According to Wikipedia, it is NP-complete. It is not the same problem as Monotone-3-SAT.

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


# Question
Title: Equivalent regular grammar with minimum number of nonterminals
Given a set of terminal symbols $\Sigma=\\{a,b\\}$ and a set of nonterminal symbols $N=\\{S,A,B\\}$ with start symbol $S$, then the two following sets of production rules are equivalent:

* $S\to aA$
* $A\to aA$
* $A\to bB$
* $B\to aA$
* $B\to bB$
* $B\to \epsilon$

and

* $S\to aA$
* $A\to aA$
* $A\to bA$
* $A\to b$

They both match any string starting with $a$ and ending with $b$, but the second set of rules has only two nonterminals instead of three. Is there a standard way to convert an arbitrary (regular) grammar to the equivalent grammar with the smallest number of non terminals? I don't think this can be achieved by the rules for Chomsky normal form.

# Answer
> 3 votes
A regular grammar corresponds directly to a finite automaton, mapping each non-terminal to a state. So this question is equivalent to asking how to minimize the number states in a finite automaton. Unfortunately, minimizing NFAs is hard. See, for example, Gregor Gamlich, 2007.

---
Tags: formal-languages, regular-languages
---


title: polynomial reduction & co np complete

text:
# Question
Title: polynomial reduction & co np complete
I would like to know how we can demonstrate these two problems :

* $A \leqslant\_p B$ implies $\overline A \leqslant\_p \overline B$
* The complement of 3-SAT is co-NP-complete

# Answer
> 1 votes
For the first one, since $A \leq\_p B$, there must exist a function $f \in \operatorname{FP}$, such that $x \in A$ if and only if $f(x) in B$ for an arbitrary word $x$. We can prove that $f$ is also a reduction from $\overline A$ to $\overline B$ as follows: Let x be an arbitrary word. \begin{align} x \in \overline A &\iff\\ x \notin A &\iff\\ f(x) \notin B &\iff\\ f(x) \in \overline B&\\ &\qquad\square \end{align}

Now for the second part, we know that 3-SAT is NP-complete. For a given language $A \in \operatorname{co-NP}$, let $B = \overline A$. Clearly $B \in \operatorname{NP}$ and hence, there is a reduction from $B$ to 3-SAT. As proven above, the same reduction is a reduction from $A$ to the complement of 3-SAT.

---
Tags: np-complete, polynomial-time-reductions
---


# Question
Title: How do I replace a D Flip Flop with a JK Flip Flop
Hello I have this circuit with this I want to learn about Mealey and Moore.

Is this a Mealy Automata? I would say yes because of the upper LED depends on the variables I got.

Otherwise isn't the line of J the next State? So it is a Moore because it only depends on its states?

Now I want to replace the D Flip Flop with a JK how could I do this?

I would just implement a JK to change it but I guess there are things that have to be done so the automata has the same outputs. Any suggestions on how to do this?

Thanks

# Answer
> 0 votes
Just as a hint, the general way to solve a problem like this is to write a truth table. The "inputs" to the truth table are the inputs to the machine plus the states of the flip-flops (one bit per FF), and the "outputs" are the outputs of the machine and the outputs of the flip-flops.

From that truth table, you can see if it's a Mealy machine. And given the desired "state on this time" and "state next time", and you can work out what the inputs to a J-K flip-flop should be:

```
 Q Q' | J K
------+-----
 0 0  | 0 X
 0 1  | 1 X
 1 0  | X 1
 1 1  | X 0

```

Where X is "don't care".

I only mentioned the truth table because you wanted to show that it was a Mealy machine, and finding the mapping of inputs and outputs is a definite way to get there.

As for the main question you're asking, you can't replace a D flip flop with a JK flip flop in the general case due to timing. D flip flops "read" their input on (say) the leading edge of the clock, and "output" their result effectively straight away, after a short propagation delay. JK flip flops, on the other hand, "read" on the leading clock edge and "output" on the trailing edge.

This property of JK flip flops can be useful; they are extremely resistant to combinational hazards, for example. But it does mean that they respond half a clock cycle later than a D flip flop.

Assuming that this isn't an issue (and I doubt it is in your circuit), you can just feed D into J and not-D into K.

---
Tags: automata
---


# Question
Title: Does input space size contribute at all to the runtime of an algorithm?
I just started learning about NP-Complete problems and one of the first examples they give is Set Cover:

> Given a set $U$ of $n$ elements, a collection $S\_1, \ldots, S\_m$ of subsets of $U$, and a number $k$, does there exist a collection of at least $k$ of these sets with the property that not two of them intersect?

This is I'm sure a very basic question, but I was wondering whether the amount of space in $n$ the *input* takes up matters at all in the formulation of runtime. This is the first example of an algorithm I've seen where the input itself takes up space exponential in $n$ since of course there are $2^n$ possible subsets of $U$. Thus, it seems that possibly the time needed to allocate the space necessary to even "handle" the input prevents there from being a polynomial time algorithm.

Or rather, do we just assume that the input magically appears in our hands already allocated before we start keeping track of algorithm runtime? And as a side question, can we choose what data structure it is given to us in? This seems more natural to me, but I wanted to make sure. I know, for example, that the time needed to allocate an *output* (or allocate anything in between) does matter.

# Answer
We measure the running time as a function of the length of the input, not as a function of $n$. So, it doesn't matter whether the length of the input is $2^n$ or not.

When we talk about an exponential-time function, we normally mean exponential in the length of the input, not exponential in some other parameter (like $n$).

For your problem, the length of the input could be $2^n$, but it will typically be a lot less than $2^n$, because typically we'll have many fewer sets than that. Either way, it doesn't matter, because we're measuring the running time as a function of the input length.

Typically, the format/representation of the input doesn't affect the running time much; the running time will be identical for any reasonable way to represent or encode the input. So, typically that doesn't matter. In the cases where it *does* matter, be careful to specify the input representation, or ask if it isn't specified.
> 2 votes

---
Tags: algorithms, complexity-theory
---


# Question
Title: Slowest growing upper bound for the minimum length of a complementary prefix regular expression
A postfix regular expression acting on a binary alphabet (specification from this post) can be described using the following grammar,

`R → 0 or 1 or _ or ! or RR; or RR| or R+`

where,

`0` and `1` match their selves,

`!` matches nothing,

`_` matches the empty string,

`;` is concatenation,

`|` is alternation,

`R+` matches 1 or more occurrences of `R`.

(The linked post above gives some example regular expressions and the strings it matches.)

What is the slowest growing upper bound on the length of the regular expression complementary to another regular expression as a function of the length of the latter?

So far, I have a double exponential. I show that an "input" regular expression $r\_1$ will give an NFA that has 1 more state than the length of $r\_1$. By the powerset construction, the resulting DFA will a maximum of have $2^{1+\text{length(}r\_1\text{)}}$ states. Clearly, the complementary DFA will have the same number of states, i.e. the same size.

I then use an algorithm to construct a regular expression given a DFA to get the upper bound of the length of this regular expression as a function of the size of the DFA. This gave another exponential, $\frac{16}{3}(4^n-1)$ where $n$ is the size of the DFA.

Combining the two gives $\frac{16}{3}(4^{2^{n+1}}-1)$, where $n$ is the length of $r\_1$, as the length of the complementary regular expression. I am not concerned about the constants, as stated in the question, only how fast it grows. So, if I got my big-O notation correct, this gives $O\left(4^{2^n}\right)$.

---

This seems unnecessarily large, can it be lower? Can it be lowered to a mere exponential?

# Answer
Wikipedia says that taking the complement "can cause a double exponentially blow-up of its length" and cites the following paper:

Succinctness of the Complement and Intersection of Regular Expressions. Wouter Gelade and Frank Neven. STAC 2008.

In particular, they give a concrete language that triggers the doubly exponential blowup. See Theorem 4.1 in the paper.

That paper considers the normal representation for regexps rather than postfix, but I don't see any reason to expect that to change the bottom line. You could work through their example and their proof if you want to be sure.
> 3 votes

---
Tags: regular-languages, finite-automata, regular-expressions
---


# Question
Title: Use the pumping lemma to show it's not regular
I just learned pumping lemma this week and got confused on this question.

B={$a^{fn}$ | $f\_n$ is a Fibonacci number} for $a \in Σ$.

Hint: the sequence of Fibonacci numbers get increasingly further apart.

I am trying to prove this is not regular using pumping lemma, but 'Fibonacci numbers get increasingly further apart' seems really tricky when I try to pump up to prove it's not $\notin$ B.

# Answer
> 1 votes
Suppose that $B$ were regular. According to the pumping lemma, there exists an integer $p \geq 1$ such that every word $w \in B$ of length at least $p$ has a decomposition $w = xyz$, with $|xy| \leq p$ and $y \neq \epsilon$, such that $xy^tz \in B$ for all $t \geq 0$.

Pick some Fibonacci number $F\_n$ such that (1) $F\_n \geq p$ and (2) $F\_{n+1} - F\_n \> p$. Then $1^{F\_n} \in B$ has length at least $p$, and so it can be decomposed as $1^{F\_n} = xyz$, where $|xy| \leq p$ and $y \neq \epsilon$, and $xy^2z \in B$. But $xy^2z = 1^m$, where $F\_n \< m \leq F\_n + p \< F\_{n+1}$.

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


# Question
Title: If I have an MST, and I add any edge to create a cycle, will removing the heaviest edge from that cycle result in an MST?
> Let's say that I have an MST, $T$. I pick an edge not in $T$ and change its weight, and add it to $T$ to create a cycle. Will removing the heaviest edge from that cycle result in an MST?

MST means minimum spanning tree of a graph. I came across these two posts:

and I follow both until the case where $w\_{old}\>w$ and $e\notin T$. They both say that deleting the heaviest edge will guarantee an MST, but I don't see how to prove that. The cycle property just says that IF you have an MST, it can't have an edge which is the heaviest edge in a cycle of the original graph $G$; it is NOT saying that IF you have a tree that doesn't contain an edge that happens to be the heaviest edge of some cycle in the original graph $G$, you are an MST.

To make the question more explicit in terms of the problem it was trying to solve, I will copy a part of the first link:

> If its weight was reduced, add it to the original MST. This will create a cycle. Scan the cycle, looking for the heaviest edge (this could select the original edge again). Delete this edge.

I don't understand why this guarantees that we find an MST. Sure, we get a spanning tree but why does deleting this heaviest edge yield a MINIMUM spanning tree?

# Answer
The important part is that you start with an MST for the original graph. With this extra piece of information, you can build a proof by contradiction, as follows:

Construct the new tree as described (add the edge, check the cycle, remove the edge with the largest weight), now assume for contradiction that this tree is not an MST. This may be for several reasons:

1. The real MST of the new graph differs in an edge that's not in the cycle. Then the original MST wasn't an MST to begin with, and we have a contradiction.
2. The real MST differs in an edge that's in the cycle, but then, as the rest of the tree is the same, we can't have removed the heaviest edge from the cycle, and we have a contradiction again.

Therefore the new tree is an MST of the new graph.
> 0 votes

---
Tags: algorithms, graphs, weighted-graphs, minimum-spanning-tree
---


# Question
Title: Prove that the language is not regular without using Pumping Lemma
I am practising problems on Regular Languages and I came across this question:

> Prove that the language $$\\{a^m b^n : m ≥ 0, n ≥ 0, m \ne n\\}$$ is not regular. (Using the pumping lemma for this one is a bit tricky. You can avoid using the pumping lemma by combining results about the closure under regular operations.)

I have tried to prove it using pumping lemma in the following way:
Let p be a sufficiently large integer, then we construct the string: $$s = a^pb^{p + p!}$$ Now by pumping lemma conditions, the string $s$ can be written as $xyz$ where $|xy| \le p$. Hence $xy$ contains only $a$'s.
If we choose any substring $y$ of length $k \le p$ from $xy$, we can always find a $C$ such that $$p+C\*k = p + p!$$

We can also prove it if we choose $s$ to be just the single character string $a$ and then we pump down.

Q1. Please let me know if there is a flaw in the above proofs.
Q2. How can closure properties be applied to prove the above? Till now I have applied closure properties to prove regularity, but never the converse.

# Answer
> 4 votes
1) your proof is correct (and nice).

2)They could mean prove that the complement is not regular (this is a classic result, and the proof is simpler). More generally, if you saw in course some languages that are not regular, you can probably reduce one of them to this one by closure operations.

Another technique without pumping lemma is to show that the number of Myhill-Nerode equivalence classes is infinite.

# Answer
> 2 votes
Assume a *finite* state machine. Since the state machine is finite there are n != m where $a^n$ and $a^m$ end up in the same state. So $a^nb^n$ and $a^m b^n$ both end up in the same state, so are either both in L or both not in L, which contradicts the definition of L.

# Answer
> 1 votes
To use closure properties, suppose $L$ is regular. Then it's complement, $\overline{L}$ is also regular, and so is $\overline{L} \cap \mathcal{L}(a^\* b^\*) = \\{ a^n b^n \colon n \ge 0\\}$, but that one is known non-regular. Contradiction.

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


title: Explanation for indirect addressing

text:
# Question
Title: Explanation for indirect addressing
While reading about minimal instruction set computer I found out that one needs at least (for example) the ability to increment or decrement the value stored in register, a test for zero and a jump.

A machine with such instruction set would be Turing-complete, correct? Is this called "Counter machine"?

But then I found out about the so-called "Random-access machine" which adds "indirect addressing", meaning I can access a register not just by explicitly specifying memory address or label but I can also fetch an address out of an address, like `[Rn]`. This should be useful for enabling mechanisms akin to "pointers" in C-like languages, for example.

My question is, why there is the need for "indirect addressing"? Since I presume both machines (without and with indirect addressing) are Turing complete, is it "merely" for convenience? Or are some programs which cannot be expressed without indirection?

PS: I'm a complete noob in this area so please bear with me: if I was to implement `memcpy`, i.e. to transfer the values of bunch of registers to other bunch of registers, how would I do it without indirection? I mean, I can write `copy 1 word from x to y`, `copy 2 words from x to y`, ... but in general, how do I say `copy n words from x to y` without it?

## Edit:

For example, imagine I receive zero-terminated string via network, say `1 2 3 0` which I would like to store to some of my infinitely-many registers. Receiving `0` halts the program. I have an instruction `take r` which copies one word from the input to register `r`. No indirection means (?) that `r` has to be a direct constant number. How do I then move to "n-th" register? In other words, I don't understand how do I move back and forth among the registers, when the only mechanism I have is to read/set register 1, 2, 3, ...?

# Answer
Here is how you can implement indirect addressing without an atomic operation that does so.

We assume that we can label memory cells (either tape cells or registers, or whatever) in some way. This can be implemented by marked copies of the tape alphabet, or a special encoding of the content.

*Idea:* Addresses are offsets. If you want the $n$th cell, move a marker $n$ steps from the beginning. For that, you maintain a counter at a fixed location (determined by the programmer/compiler). After that, perform your operation on the first marked cell. Remove the marking when you are done.
> 3 votes

# Answer
Yes, both counter machines and random access machines are Turing complete. The inclusion of indirect addressing does not expand the range of functions that can be computed - it simply makes programming simpler and improves notional efficiency (although the efficiency of an abstract machine is a rather vague concept).
> 1 votes

---
Tags: computer-architecture, computation-models, turing-completeness
---


# Question
Title: Is this a CFL: $L_1 = \{wxyx | w, x, y \in (0 + 1)^+\}$?
I recently found a question asking whether the language given below is context-free or not:

$L\_1 = \\{wxyx | w, x, y \in (0 + 1)^+\\}$

My intuition is that I can design a non-deterministic push-down automaton for the language. I would appreciate if you could correct me if I am wrong, or brief me on how I could prove that it is indeed context-free.

# Answer
> 1 votes
It’s a trick question. There must be four letters or more. Let the last letter be a, where a is 0 or 1. If any other letter other than the first or second to last is a, then the string is in L. (Pick x = a, w = everything before the first a, y = everything between first and last a). If you can’t find a in these places, the string cannot be in the language because you can’t match the last x with another one.

So you don’t have to check for two equal strings of identical length at all, the language is much simpler. And it is regular.

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


# Question
Title: Why there is no polynomially large sequence of polynomial large weights that derandomize the isolation lemma?
I was studying the paper Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size by Arvind and Mukhopadhyay and came across the following claim (Observation 1.2 on page 3):

"More precisely, for any polynomially bounded collection of weight assignments $\\{w\_i\\}$ $i \in \[n^c\]$ with weight range $\[n^{c'}\]$, there exists a family $F$ of subsets of $\[n\]$ such that for all $j \in \[n^c\]$, there exists two minimal weight subsets with respect to $w\_j$.

They claim that this follows from a counting argument that uses the existence of $2^{(2^n)}$ set systems. The article they cite does not contain a proof of this assertion.

*Question:* What proof are they thinking of? Why is their claim true?

# Answer
I learned the following argument from Dieter van Melkebeek (but any mistakes are my own). I'm not sure that this is what Arvind and Mukhopadhyay had in mind, because the assumptions are not the same, as I point out after the argument. I am still interested in learning alternative proofs.

The idea will be to start with the collection of all subsets, and iteratively fix it by removing subsets until the conditions are satisfied. This is similar to the deletion method from the probabilistic method.

We will iterate the following algorithm:

```
F := Powerset([n])
While there is some i in [n^c] such that w_i makes F min unique:
    Update F by removing the element with min w_i weight.

```

It suffices to show that this algorithm terminates with a non-empty set $F$.

To wit, note that each time we find such an $i$, the minweight of $F$ under $w\_i$ increases by at least $1$. Since the max weight of any set under $w\_i$ is $n^{c' + 1}$, this means that for each weight $w\_i$, we can update $F$ at most $n^{c' + 1}$ times during the algorithm. Thus, in total $F$ is updated at most $n^{ c + c' + 1}$ times. Since each step removes one set from $F$, this means that $F$ is nonempty at the end of the procedure provided that $2^n \> n^{ c + c' + 1}$.

Additionally, at the end of the process $F$ can be culled to size at most $2n^{c}$, by picking two min-weight sets for each $w\_i$ $i \in \[n^c\]$.

Since we delete up to $n^{c + c' + 1}$ sets from $F$, we only need to work with a universe of set systems of size ${2^n \choose n^{c + c' + 1} } = O( 2^{(n^{c + c' + 2})})$. This makes me think that this argument is not the one that uses the fact that there are $2^{2^n}$ set systems.
> 1 votes

---
Tags: complexity-theory, probability-theory, discrete-mathematics, lower-bounds
---


# Question
Title: Obtaining an acyclic graph by removing edges using an algorithm that decides ACYCLIC
i don't understand the following:

If there's an algorithm that can decide ACYCLIC in Polynomial time, then there's an algorithm who returns a set of k edges, so that the graph obtained by deleting the k edges is without cycles - in polynomial time.

The algorithm should get a directed graph and a natural k as an input, and output, if there are k edges as needed, a list of k edges, so that the graph obtained from erasing those k edges is cycles. if there are no such k edges, it simply outputs "no".

Question:my question in addition to the answer already given is this part: " then there's an algorithm who returns a set of k edges, so that the graph obtained by deleting the k edges is without cycles - in polynomial time." - what can be this algorithm? how to do it using a turing machine?

Problematic part: I can only use an algorithm that decides ACYCLIC, but it is forbidden to use any other NP-Complete algorithms, and it's running time must be polynomial in regards to its input size.

My attempt: well, to check/decide if a directed graph is ACYCLIC or not, we'll visit it topologically using DFS, then using a stack, we'll traverse edges to see if any edge in the digraph leads back to an edge already visited. if already visited - there's a cycle, if not - there's no cycle.

The algorithm: on an input of a directed graph, to check ACYCLIC:

1)finding an vertex that has only outgoing nodes - if such node doesn't exist - return "graph has cycles"

2)on that node, run DFS and traverse the digraph; add each edge found to a stack. if a vertex is shown twice - return "graph has cycles".

3)if no cycles found, accept.

But, I am not sure how to do it in regards to the algorithm required in the problem(first two paragraphs of the questions - basically, returning a set of k edges, so that by removing them, the graph will be cycles.

would really appreciate knowing how to do it.

thank you very much

# Answer
> 2 votes
**Disclaimer** This solution assumes that the language $\text{Acyclic}$ is the language that contains exactly all acyclic directed graphs.

It is impossible to achieve this in polynomial time unless $\operatorname{P}=\operatorname{NP}$. The reason is that the problem you have to solve is NP-hard. It is called the directed feedback arc set problem. It is one of Karp's 21 hard problems. On the other hand, finding whether a graph is acyclic can be done with any graph traversal method in polynomial (actually linear) time. Hence, $\operatorname{P}^{\text{Acyclic}} = \operatorname P$. Hence, if you solved the task you are given in polynomial time you would have proven $\operatorname{P} = \operatorname{NP}$.

---
Tags: algorithms, complexity-theory, graphs, np-complete, decision-problem
---


# Question
Title: minimizing the maximum between a degree of a tree and its height
I'm interested in asymptotically minimizing the maximum between the height of a tree of degree $k$ with $n$ leaves, and $k$, i.e. minimizing $\max(k, \log\_kn)$ asymptotically.

If I set $k = \frac {\log n}{\log \log n}$, then the height of the tree is $\log\_\frac{\log n}{\log \log n}(n) = \frac{\log n}{\log \frac {\log n}{\log \log n}}$.

What is the asymptotic height of that tree, is $$\frac{\log n}{\log \frac {\log n}{\log \log n}} = \Theta(\frac{\log n}{\log \log n})$$ and if so, is this optimal?

# Answer
Yes, it is true that $\dfrac{\log n}{\log \frac {\log n}{\log \log n}} = \Theta(\dfrac{\log n}{\log \log n}).$ In fact, we have the following more accurate approximation, $$\frac{\log n}{\log \frac {\log n}{\log \log n}} \sim \frac{\log n}{\log \log n}.\tag{app}$$

**Proof**. $$\begin{aligned} \lim\_{n\to\infty}\frac{\ \frac{\log n}{\log \frac {\log n}{\log \log n}}\ }{\ \frac{\log n}{\log \log n}\ }&=\lim\_{n\to\infty}\frac{\log\log n}{\log \frac {\log n}{\log \log n}} =\lim\_{n\to\infty}\frac{\log\log n}{\log\log n-\log\log \log n}\\ &=\frac{1}{1-\lim\_{n\to\infty}\frac{\log\log \log n}{\log\log n}} =\frac{1}{1-0}=1. \end{aligned}$$

So, if we set $k = \frac {\log n}{\log \log n}$, then the height of the tree, $\frac{\log n}{\log \frac {\log n}{\log \log n}}$ is $\frac{\log n}{\log \log n}$ asymptotically and, hence, so is the larger one between the height of the tree and $k$.

---

Now, the question is what is the asymptotic behavior of the minimum of the larger one between $\log\_kn $ and $k$, i.e. $h(n)=\min\_k\max(\log\_kn,k)$.

Since $k$ is increasing with respect to $k$ while $\log\_k n$ is decreasing with respect to $k$, the minimum of the larger one between $k$ and $\log\_k n$ for a given $n$ is obtained when $k=\log\_k n$, assuming $k,n\>1$.

What is the solution to $k=\log\_k n$ for a given $n$? $$k=\log\_kn\Leftrightarrow k= \frac{\log n}{\log k}\Leftrightarrow \log k\cdot k= \log n\Leftrightarrow \log k\cdot e^{\log k}= \log n$$ By the definition of the Lambert $W$ function, we should have $$\log k = W\_0(\log n),$$ where $W\_0(\cdot)$ is the principal branch of the Lambert $W$ function, as we are only interested in the real positive values. So, $$k = e^{W\_0(\log n)}.$$ Accordingly, $$h(n)=\left.\max(\log\_kn,k)\right|\_{k=e^{W\_0(\log n)}}=e^{W\_0(\log n)}.$$

The same article on Lambert $W$ function tells that $$ W\_0(x) = \log x - \log\log x + o(1).$$ Substituting $\log n$ for $x$, we have $$ W\_0(\log n) = \log\log n - \log\log\log n + o(1).$$ So, $$ h(n) =e^{W(\log n)}= e^{\log\log n} e^{-\log\log\log n} e^{ o(1)}=\frac{\log n}{\log\log n}\ e^{o(1)},$$ Since $e^{o(1)}$ goes to 1 when $n$ goes to infinity, $$h(n)\sim{\frac{\log n}{\log\log n}}.$$

---

Combining the above conclusions, we see that if we set $k = \frac {\log n}{\log \log n}$, then the larger one between the height of the tree and $k$ approaches its minimum $h(n)$ as well as ${\frac{\log n}{\log\log n}}$ asymptotically.

---

To be nit picky, it should be pointed out that we have been ignoring the expected requirement that $k$ should be an integer. It would require cumbersome analysis to adapt the above analysis and conclusion for integer $k$. In the end, we have still $$\min\_{1\lt k\le n,\ k\in\mathbb N}\max(k, \log\_kn)\sim\frac{\log n}{\log\log n}.$$
> 2 votes

---
Tags: asymptotics, trees
---


title: Can I assume that L1 is regular?

text:
# Question
Title: Can I assume that L1 is regular?
$L\_{4},L\_{2}$ are regular languages.

given an expression which we know is regular: $L\_{4}\cap \bar{L\_{2}}\cap \bar{L\_{1}}$

May I assume that the language $L\_1$ is regular? using closure properties

# Answer
> 1 votes
No, in general. If $\bar{L\_2}$ and $L\_4$ are both the empty language, or have an empty intersection, then $L\_4\cap\bar{L\_2}\cap\bar{L\_1}$ is regular, but that says nothing about whether $L\_1$ is regular.

---
Tags: automata, regular-languages
---


# Question
Title: Neural branch predictors linear, classical predictors exponential, in resources?
Wikipedia states:

> The main advantage of the neural predictor is its ability to exploit long histories while requiring only **linear resource growth**. Classical predictors require **exponential resource growth**.

What is the reason for this?

# Answer
In a classic perceptron-based branch predictor, each static branch has one weight value for each global history bit. Therefore the storage is equal to the number of static branches with entries times the size of weights times the number of history bits. If the number of static branches is constant and the weight size is constant, the storage size increases linearly with the number of history bits. The computation overhead for a straightforward tree design would be a little more complex: the final addition of each half would replace a carry-propagate adder at the end with a carry-save adder and the final addition would use a carry-propagate adder one bit larger. (For a branch direction decision, one technically does not need the full sum but only the most significant bit.)

If one wants to include correlations of history bits (e.g., branch A is usually taken when history bit 7 is set and history bit 9 is clear and when history bit 7 is clear and history bit 9 is set will not be predicted well with only separate weights for history bits 7 and 9), the growth would obviously be superlinear. The classic design does not account for correlations among history bits.
> 1 votes

---
Tags: cpu, cpu-pipelines
---


title: non deterministic space hierarchy

text:
# Question
Title: non deterministic space hierarchy
I want to prove the non deterministic space hierarchy theorem.

Let $f(n),g(n)\geq\log n$ be space constructible functions such that $f(n)=o(g(n))$, **Prove**:

$$NSPACE(f(n))\subsetneq NSPACE(g(n))$$

I feel that the standard way of constructing a TM that takes as an input a TM and simulates the machine on itself, then flipping the output won't work because the input is a nondetrministic TM maybe. Can someone suggest a hint?

# Answer
The Wikipedia proof for the non-deterministic *doesn't* flip the output. It considers the language $$ L = \\{ (\langle M \rangle, 1^t) : \text{$M$ accepts $(\langle M \rangle, 1^t)$ in space $g(|(\langle M \rangle, 1^t)|)$} \\}. $$ This language is in $\mathsf{NSPACE}(g)$. The Immerman–Szelepcsényi theorem shows that if $L \in \mathsf{NSPACE}(f)$ then also $\overline{L} \in \mathsf{NSPACE}(f)$, which leads to a contradiction.
> 2 votes

# Answer
This is just an elaboration of the proof noted above. Consider the following algorithm:

A(x) {

Step 1: If x is not of the form $(M,1^{t})$ for some nondeterministic Turing machine $M$ and integer $t$, reject.

Step 2: Compute $q = 2^{g(n)}$ where $n$ is the length of $x$.
/ * Needs $O(g(n))$ deterministic space, assuming $g$ is constructible \*/

Step 3: Using a universal Turing machine, simulate $M$ on $x$ for $q$ steps. If $M$ accepts $x$, accept $x$. Otherwise, reject $x$.
/ * This simulation requires only $O(g(n))$ space \*/
}

Claim: $L(A)$ is not equal to $L(M)$ for any $O(f(n))$ space non deterministic Turing machine if $f(n) = o(g(n))$ and $f(n)$ is constructible.

Proof: For the sake of contradiction, assume that a non deterministic Turing machine $M$ accepts $L(A)$ in $O(f(n))$ space. Then, by Immerman-Szelepscsenyi theorem, there exists a machine $N$ that accepts the complement of $L$ in $O(f(n))$ space.

Consider a string $x$ of the form $x = (N, 1^{t})$ of length $n$ such that $t$ is large enough to ensure that the simulation of $N$ on input $x$ in step 3 of the algorithm runs to completion on all computational paths of $N$.

Now suppose $(N, 1^{t})\in L(A)$. By Step 3 of the algorithm, this means that $N$ accepts $(N, 1^{t})$ on at least one computational path - that is, $(N, 1^{t})\in L(N)$. However, both $A$ and $N$ cannot accept the input $(N, 1^{t})$ because of our assumption that $L(N)$ is the complement of $L(A)$.

Hence, we conclude that $A$ does not accept $(N, 1^{t})$. But this too is contradictory. By Step 3 of the algorithm, $N$ must reject $(N, 1^{t})$ on all computational paths. In other words, $N$ must reject $(N, 1^{t})$. But both $A$ and $N$ cannot reject $(N, 1^{t})$ as $L(N)$ was assumed to the the complement of $L(A)$.

We conclude that our assumption that $M$ accepts $L(A)$ is contradictory and that $L(A)$ is different from the language accepted by any non deterministic Turing machine that uses $O(f(n))$ space for any $f(n)=o(g(n))$.
> 2 votes

---
Tags: complexity-theory, turing-machines, space-complexity
---


# Question
Title: Algorithm for coherent motion. Which bus is app user on?
I am currently working on an app with a map of the city, with markers for each bus. As a feature, the phone should show which bus the user is on.

To achieve this I am working on building a function that consumes a stream of a set of buses and their positions (`Stream<Set<Tuple2<BusId, Location>>>`), and a stream of phone location, to produce a Stream of bus predictions. The prediction should contain a confidence level.

The function should return the current prediction in real-time, and handle scenarios where the user changes the bus.

How could this be accomplished?

Both streams contain very precise locations at a rate of once every second.

# Answer
> 0 votes
You basically have a table as follows:

```
Time | Person | Bus1 | Bus2 | ... | BusN  |
=====+========+======+======+=====+=======+
  0  | (x,y)  | (x,y)| (x,y)| ... | (x,y) |
  1  | (x,y)  | (x,y)| (x,y)| ... | (x,y) |
...

```

`x,y` being the coordinates of that Person/Bus at a specific point in time.

You then calculate the distance for each pair of Person/Bus and timepoint and map each Bus-Person-distance column to its rolling average of approx. 20 to 60 seconds (depends on precision and stuff like this).

You can then map the distances for each time-segment to a probability to be in a specific bus (if the location data quality is high, this should be pretty easy).

If you then plot the probabilities over time, for most times a specific bus should be on top. If this probability gets lower and another one rises, the person is likely changing the bus (or the buses are near each other).

PS: If your location API has methods for distance calculations, use those. If you have to do it yourself, there are some formulas to get from latitude and longitude to something for which the Euclidean distance ($D = \sqrt{(x\_2-x\_1)^2 + (y\_2-y\_1)^2}$) works (using that with latitude/longitude is wrong in general: see here.

PPS: I am not entirely sure, whether this problem is actually related to Computer Science.

# Answer
> 0 votes
I ended up solving this using Tensorflow. For every app position recording, and every bus I created a timeline of displacement between bus and app position recording.

I got a CSV file looking like this:

```
displacement-30,displacement-20,displacement-10,displacement0,displacement10,displacement20,displacement30,timeDeviation-30,timeDeviation-20,timeDeviation-10,timeDeviation0,timeDeviation10,timeDeviation20,timeDeviation30,onBus
0.01,0.013,0.023,0.017,0.012,0.006,0.021,0.5,0.5,0.5,0.5,0.5,0.5,0.5,1
0.42,0.42,0.42,0.42,0.425,0.407,0.405,0.47,0.48,0.49,0.5,0.498,0.501,0.503,0
0.42,0.42,0.42,0.425,0.407,0.405,0.406,0.477,0.487,0.497,0.5,0.498,0.5,0.498,0
0.42,0.42,0.42,0.425,0.407,0.405,0.406,0.482,0.492,0.502,0.5,0.503,0.499,0.498,0
0.42,0.42,0.425,0.407,0.405,0.406,0.406,0.489,0.499,0.502,0.5,0.502,0.5,0.505,0
0.42,0.425,0.407,0.405,0.406,0.406,0.405,0.497,0.5,0.498,0.5,0.498,0.503,0.501,0
0.42,0.425,0.407,0.405,0.406,0.405,0.406,0.503,0.501,0.504,0.5,0.499,0.497,0.497,0
0.425,0.407,0.405,0.406,0.406,0.405,0.406,0.502,0.5,0.502,0.5,0.505,0.503,0.503,0
0.425,0.405,0.405,0.406,0.405,0.406,0.406,0.502,0.497,0.501,0.5,0.498,0.498,0.498,0
0.405,0.405,0.406,0.405,0.406,0.406,0.405,0.499,0.503,0.502,0.5,0.5,0.5,0.5,0
0.405,0.406,0.405,0.406,0.406,0.405,0.428,0.503,0.502,0.5,0.5,0.5,0.5,0.5,0
0.406,0.405,0.406,0.406,0.405,0.428,0.424,0.502,0.5,0.5,0.5,0.5,0.5,0.5,0
0.405,0.406,0.406,0.405,0.428,0.424,0.424,0.5,0.5,0.5,0.5,0.5,0.5,0.499,0

```

Each displacement is normalized as 0-1000 meters. The time deviation is used in case an incomplete timeline needs to be processed.

I will expand the features to include if bus was detected using Bluetooth beacons, the heading between bus and app position.

---
Tags: algorithms
---


# Question
Title: If $L$ is a regular language then so is $L/a =\{w | wa ∈ L\}$, where $L$ is a language over $\Sigma$ and $a \in \Sigma$
I'm trying to work out a proof by construction that $L/a$ would be regular.

$a$ is any final symbol at the end of an accepted string, so I figured the only part of the machine that would have to be changed is the set of accepted states ($F$)

I came up with the following definition of $F'$ for the new

$F' = \\{q ∈ Q | \delta(q, a) ∈ F\\}$

Where $Q$ is the set of states (the same for both machines), and $\delta$ is the transition function (also the same for both machines). I believe this would make any state that has a transition to an accepting state in the first machine an accepting state in the second machine (including prior accepting states, if they have a self-loop).

Am I missing anything here? It seems suspicious to me that I would only need to modify the set of accepting states and not any other component.

# Answer
This proof uses both construction and knowledge of closure properties of regular languages.

First, we know that regularity of languages is closed under the reversal operation, see proof of Thm. 4.2 here.

We can then define an operation named chop such that:

$$ \text{chop}(L)=\\{w|aw \in L\\}, \text{ where } a \in \Sigma, $$

We can construct an NFA for chop, which simply omits the first transition (hence removing the first character):

*This NFA is incomplete, but is just for the sake of illustration*

Therefore the regularity is closed under the chop operation.

Finally, observe that we can produce R/a operation using chop and reversal:

$$ L/a = (\text{chop}(L^{R}))^{R} $$

Hence L/a has been constructed using closure properties so must be regular.

Hope this helps!

*Source: Formal Languages module, second year, BSc Computer Science University of Warwick.*

Edit: capitalisation of first word.
> 1 votes

---
Tags: formal-languages, regular-languages, finite-automata, closure-properties
---


# Question
Title: Compression algorithms for small strings - building upon / extending Huffman
I'm exploring algorithms to compress small strings like the following - every line is to be compressed individually, i.e. even those small strings should get compressed:

```
ZYXH1|104932,104932,927.6000,200,1,927.4000,1600,1
ZYXH1|104932,104932,3390,1600,1,3389,2700,1
HXDFF|0001739.42;HXDFF:Y|0U010:49:32
ZYXH1|104932,104932,5360,5400,1,5350,16400,1
ZYXH1|104931,104931,1966,2800,1,1965,3800,1;HXYFBR|0003.12;HXCFBR|0001.14;HXCFER|0006.7;HXMKCF|0003268409320112.0
ZYXH1|104932,104932,526,192400,1,525,88400,1
ZYXH1|104932,104932,803,6300,1,802,63900,1
ZYXDFF|803;ZYXDFF:Y|104932;ZYXVW|100800.6381;ZYXVL|1121700,104932;TAXTIC|L719;TAXNO|L1121700
ZYXH1|104932,104932,1367,2100,1,1366.5000,2800,1
HXYFBR|0002.04;HXCFBR|0001.52;HXCFER|00015.0;HXMKCF|0001676300748887.4
ZYXH1|104932,104932,380,63500,1,379,21500,1
ZYXH1|104932,104932,5360,5400,1,5350,16400,1
ZYXH1|104932,104932,803,3900,1,802,63800,1;ZYXVA|898075800
ZYXH1|104932,104932,3045,4700,1,3040,5500,1;ZYXDFF|3040;ZYXDFF:Y|104932;ZYXVW|1003043.4356;ZYXVL|164600,104932;ZYXVA|498213500;TAXTIC|L199;TAXTICD|L42;TAXNO|L164600;TAXDFG|Y0058
ZYXDFF|3040;ZYXDFF:Y|104932;ZYXVW|1003043.3304;ZYXVL|169800,104932;TAXTIC|L202;TAXNO|L169800
ZYXDFF|3040;ZYXDFF:Y|104932;ZYXVW|1003043.2935;ZYXVL|171700,104932;TAXTIC|L206;TAXNO|L171700
ZYXDFF|3040;ZYXDFF:Y|104932;ZYXVW|1003043.2764;ZYXVL|172600,104932;HXCFF|0003040;HXCFF:T|0T010:49;TAXTIC|L212;TAXNO|L172600
ZYXDFF|3040;ZYXDFF:Y|104932;ZYXVW|1003043.2745;ZYXVL|172700,104932;TAXTIC|L213;TAXNO|L172700
ZYXH1|104932,104932,4168,1200,1,4167,100,1

```

I have a couple of megabytes worth of data like the above, which allows me to create a static statistical model, i.e. for Huffman. If I have such a static model, I can embed that with the decompressor, removing the need to transmit/store it, i.e. trading compression rate for adaptability (important with these small strings).

I have now tried various algorithms, and the results of compressing those megabytes worth of strings (using a simple program that transmits the compressed data via TCP) are as follows:

```
 Algorithm       Rate  Bytes/sec
--------------------------------
 deflate optim   46.7%    3724917
 deflate fast    44.2%    3831672
 huffman         41.9%   11169462
 lz4 1576 optim  25.6%    4334541
 lz4 18576 fast  23.5%   42504338
 lz4 1576 fast   23.4%   70996590
 uncompressed       0%  105210881

```

So deflate is at the top of the list when it comes to the compression rate, (even for these small strings, where deflate does not rely on a shared static model) but it's 2 to 3 times slower than (my home-grown) Huffman coder. Given all the repeating character patterns in the input data, it would seem one could do much better than the Huffman coder which only looks at single bytes. LZ4 can be really fast with small buffer sizes (I only listed sizes of 1576 and 18576, Bytes/sec for bigger sizes drops significantly), but compression rate is not that good.

Are there simple ways to change / extend a per-byte Huffman coder to make use of the fact that there are many repeating (multi-byte) character patterns?

But it shouldn't grow the statistical model to thousands of entries (currently the model has at most 256 symbols, and merely changing from 1-grams to 2-grams would increase it to up to 32768), because in fact I do want to change and hence store/transmit the statistical model, but not for every string, but only every, say, 1 megabyte or so. So it would be somewhere between a static statistical model and a fully dynamic statistical model.

# Answer
A simple variant of Huffman is due, I believe, to David Wheeler.

Suppose the alphabet is $\Sigma = \\{s\_1, \dots, s\_n\\}$ and let $\star$ be some new character that's not in $\Sigma$. For each character $s\in\Sigma$, let $p(s)$ be the most common character to occur immediately after $s$ in your dataset.

To compress the string $X=x\_1\dots x\_N$, you first scan through it and, each time $x\_{i+1}=p(x\_i)$, replace $x\_{i+1}$ with $\star$, giving a new string over alphabet $\Sigma\cup\\{{\star}\\}$. Then run ordinary Huffman on the resulting string. The idea is that the character $\star$ should be really common in the modified string, so it should get a really short codeword.

For example, if your alphabet is $\\{a,b,c,d\\}$ and $p(a)=a$, $p(b)=a$, $p(c)=d$ and $p(d)=c$, then the string $abacd$ would be transformed to $ab{\star}c{\star}$ and $cdcdcd$ would be transformed to $c{\star}{\star}{\star}{\star}{\star}$.

Since all your example strings begin with `Z`, it might also be worth storing the most common initial character to allow you to replace the first character of the string with $\star$, too.
> 4 votes

# Answer
Check out these libraries for compressing short strings:

https://github.com/siara-cc/unishox :

**Unishox** is a hybrid encoder (entropy, dictionary and delta coding). It works by assigning fixed prefix-free codes for each letter of the 95 letter printable Character Set (entropy coding). It encodes repeating letter sets separately (dictionary coding). For Unicode characters (UTF-8), delta coding is used. It also has special handling for repeating upper case and num pad characters.

Unishox was developed to save memory in embedded devices and compress strings stored in databases. It is used in many projects and has an extension for Sqlite database. Although it is slower than other available libraries, it works well for the given applications.

https://github.com/antirez/smaz :

**Smaz** was developed by Salvatore Sanfilipo and it compresses strings by replacing parts of it using a codebook. This was the first one available for compressing short strings as far as I know.

https://github.com/Ed-von-Schleck/shoco :

**shoco** was written by Christian Schramm. It is an entropy encoder, because the length of the representation of a character is determined by the probability of encountering it in a given input string.

It has a default model for English language and a provision to train new models based on given sample text.

PS: The first one was developed by me and its working principle is explained in this article:

Comparison: I compressed the first line of your data and posted the screenshot below:

I also compressed the whole text using Unishox and it gives a savings of 47.8%:
> 1 votes

---
Tags: data-compression, huffman-coding
---


# Question
Title: Distinction between 2 languages.One is regular the other is not
whenever it needs to be determined if langage is regular or not, I use the notion that it is impossible for a machine to "remember" an infinte states.

given 2 languages:$L\_1=\\{(01)^{n}(10)^{n}|n \in \mathbb{N}\\}$

$L\_2=\\{(01)^{n}0(10)^{n} |n \in \mathbb{N}\\}$

The only difference between $L\_1$ and $L\_2$ is the $0$ in the middle. $L\_1$ is non-regular but $L\_2$ is .

In the appendix page in the workbook it's written that:the intuition used in L1 is that I need to remeber an infinite states, and then using the "Pumping Lemma" they disproved that it is regular. It also says that L2 is regular and it is possible to build a DFA for the language.

**I am not looking for answers for how to solve this**, just why this notion of "machine have to remember an infinite states" is not applicable to $L\_2$ because it seems that in $L\_2$ the machine needs to remember how many times $01$ appeared then after $0$ machine needs to repeat the same number of time for $10$.

I also use this webpage:https://www.geeksforgeeks.org/how-to-identify-if-a-language-is-regular-or-not/

A bit over year ago I asked about the statemnets written there and they told it is not fully reliable(theorem no. 5 : "concatenation of pattern(regular) and a non-pattern(not regular) is also not a regular language.")

Why language is not regular

Before trying to draw a DFA or disaproving using pumping lemma I use these theorems, but as it seems it maybe unreliable.

**The questios are:** why L1 is regular and L2 is not(I understand that one can be described via dfa and the other is not, just why L2 is not supposed to remember an infinite states).

and if the link for "geeks for geeks" can be used, to help to decide if language is regular or not?(I know that the only way to determine is by building dfa or pumping lemma=\> these are the only 2 ways I've so far as a student studied,but before wasting time in the exam for building "DFA" for non regular language I need some sort of "hunch" as to choosing to disaprove by pumping lemma or building a DFA).

# Answer
> 2 votes
This is one of those trap questions where $L\_2$ can actually be written in a different way that makes it obvious that it is a regular language. See if you can figure out what $L\_2$ is "really doing", and the answer will become obvious.

Solution:

> $L\_2 = 0(1010)^\*$

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


# Question
Title: Integer Linear programming formulation if then condition
I want to create constraints such that I can implement the following condition:

Let A be an integer variable \>= 0 with an upper bound of 12

I want to introduce the following variable B also an integer:

`if A = 1 then B = 0 else B = A`

# Answer
> 0 votes
you can introduce a binary variable z verifying the following constraints :

* (A-1) \<= 12\*z
* z\<= 0.5\*A
* -(1-z)\*12 \<= B-A \<= (1-z)\*12
* -12\*z \<= B \<= 12\*z

---
Tags: optimization, linear-programming, integer-programming, constraint-programming
---


# Question
Title: Is the sieve an improvement for prime finding over an optimized algorithm?
I don't think it is, as you have to loop through each set multiple times at least.

implementation of sieve in JS \- in the answer at the bottom. The link shows a 10X improvement using sieve.

In this case it is faster b.c. the function changes the integers to bits and is working with bits instead of integers.

But if you look at the structure of the code it has 3 loops. An optimized non sieve version has only 2 loops.

For example here is an optimized algorithm:

```
function findPrimes(n){
  const primes = [2];
  label: for(let i = 3; i <= n; i += 2){
    for(let j = 0; j < primes.length; j++){
      if(i % primes[j] === 0) {
        continue label;
      }
    }
    primes.push(i);
  }
  return primes;
}

```

and here is the sieve method using bit-wise operations.

```
  "sieve": function sieveOfEratosthenes(n) {
    var sieve = new Int32Array(Math.ceil((n + 1) / 64)).fill(-1);
    var primeVals = [2];

    for (var i = 3; i * i <= n; i += 2) {
      if (sieve[i >> 6] & (1 << (i >> 1 & 31))) {
        primeVals.push(i);

        for (var j = i * i; j <= n; j += i + i) {
          sieve[j >> 6] &= ~(1 << (j >> 1 & 31));
        }
      }
    }

    while (i <= n) {
      if (sieve[i >> 6] & (1 << (i >> 1 & 31))) {
        primeVals.push(i);
      }
      i+=2;
    }
    return primeVals;
  }

```

# Answer
Sorry, but you can’t just count loops, the number of loops is totally irrelevant.

If you count *nested* loops, that is *slightly* significant but can be very misleading.

You need to count how many iterations a loop performs. In the first example, the number of iterations is up to primes.length, which is around n / log n. In the second example, the number of iterations in the inner loop is less than n / 2i, and i grows quickly.

Add a counter to each function and see how often the inner loop gets executed.

PS. Let n = 1 billion, and print say every 100th prime added to primeVals. Then check how long it takes. The sieve will take a good time. But I can promise you, the “optimised” algorithm will be a lot more than ten times slower.
> 2 votes

---
Tags: algorithms, algorithm-analysis, time-complexity
---


# Question
Title: Matching two sets when you cannot do within-set comparisons
Suppose you have two lists, `A` and `B`, each with length n. The elements of A cannot be compared with other elements of `A`--there is no order relation among them--and likewise for `B`. However, elements of `A` can be compared with elements of `B`. So for instance, suppose we have a function `compareTo(a,b)` where `a` is an element of `A` and `b` is an element of `B`. If `a` is less than `b` it returns -1, if they're equivalent it returns 0, and if `a` is greater it returns 1.

Further suppose that a perfect matching exists between the elements of `A` and `B`, in the sense that for every element of `A` there is precisely one element of `B` such that `compareTo(a,b)` evaluates to 0. And vice versa (for each `b` there is precisely one `a` such that they're equivalent).

How do we write an efficient algorithm to find the perfect matching?

---

My attempts: Well, there's the naive algorithm which takes an element of `A` and finds its corresponding element of `B`, repeating until all matchings have been found. This runs in O(n^2) so we want to beat this.

It sounds kind of like Gale-Shapley but an input to that algorithm is a preference list. In this setting we have ties, where preference lists don't. And even generating something like a preference list would take n^2 time. Since it is fundamental to Gale-Shapley that members of one set propose to their highest preferences of the other, this doesn't seem applicable to the given problem.

We could try to use an element of `A` to partition the set `B` and try to divide-and-conquer. But you would only have divided `B` and wouldn't know which elements of `A` to give to the recursive call. You could then try to use `B` to partition `A`. To describe this more, let's give a specific example. Suppose `A = [a1,a2,a3,a4]` and `B = [b4,b1,b3,b2]` and suppose that `ai < bj` if `i < j`, and likewise for `=` and `>`. We could arbitrarily select `a1` and then use it to partition `B` into the elements that come out greater in the comparison, `[b4,b3,b2]` and the elements that come out smaller `[]`. Since along the we way we found that `a1` matched `b1` we make that assignment and eliminate them from the rest of the algorithm. Now that we know `a1` was quivalent to `b1` we can use `b1` to partition `A` into `[]` and `[a2,a3,a4]`. We recursively call the algorithm on the smaller sets `[], []` which satisfies the conditions: they have the same length and have perfect matching. And recursively call the algorithm on the larger sets `[a2,a3,a4], [b4,b3,b2]` which also have the same length and have a perfect matching.

I think this algorithm is correct, but in the worst case it doesn't beat the worst-case runtime of the naive algorithm. So I don't think I'm on the right track here.

# Answer
This is the so-called "nuts and bolts" problem, and your pivoting approach can be shown (under uniform choices of pivots) to give a randomized algorithm with expected query complexity $O(n \log n)$, using the analysis of Quicksort as a template.

Fast deterministic algorithms are less obvious. The first true breakthrough paper I know of for this is that of Alon et. al., which shows one simple algorithm with query complexity $O(n^{1.5} \sqrt{\log n})$ (basically by combining the quicksort approach you describe with a moderately expensive pivot-finding procedure), and another much more involved one with complexity $O(n\\,\textrm{polylog}\\,n)$ (also based on quicksort, but the identification of the pivot goes through some more hardcore expander machinery).

Subsequently, Komlós et. al. found an asymptotically optimal algorithm with $O(n \log n)$ deterministic query complexity using a different approach based on sorting nets.
> 4 votes

---
Tags: algorithms
---


# Question
Title: What does it mean if a generic structure is type-erased?
This documentation states that the generic structure `AnyIterator` is a type-erased iterator of `Element`.

# Answer
> 1 votes
It means that at runtime you will not be able to see what object comes out of the collection, as that information is removed from the lower-level code that is generated by the compiler.

In your specific instance, it would mean that at runtime an object of type `AnyIterator<Element>` will not be able to tell you what is the exact type of `Element`, unless ofcourse, you (implicitly/explicitly) cast it.

---
Tags: programming-languages
---


# Question
Title: Approach for algorithm to find closest 3-D object in a list of many similar objects to a given test case
Lets say I have a list of many (10s of thousands - millions) objects, and each of these objects has a given number of 3-D vertices (my current implementation uses 8 vertices each, but this number can be reduced if it causes a very significant increase in performance). These vertices are currently stored as floats from 0-255, but this range can also be changed if need be, assuming it will not reduce accuracy too drastically. Also, I can store these objects in any data structure that would be beneficial for this algorithm.

I am given another such object, also with the same number (8) 3-D vertices, but of which in general it must be assumed that none of the vertices are common with any vertices included in the list of stored previous objects.

With all of this in mind, I need an algorithm that will return an object from that list that is optimally close to the test case object (close being defined in the normal, euclidean distance, sense). By optimally close, I mean that it does not have to be the global optimum if this will greatly increase performance, although if there is a quick algorithm that will always return the global optimum i would love to hear it.

# Answer
If your shapes are not too elongated, you could calculate their axis-aligned bounding boxes (BBs) and store these bounding boxes in an index, such as R-Tree, quadtree or one of their more modern variants. Then:

1. Define a distance function that gives the closest BB to the BB of your search-object.
2. Find the BB in the index that is closest to the BB of you search object.
3. Calculate the actual distance $d$ between the search-object and the object from the index.
4. Search the index again, this time with a window query that is by $d$ larger than the previous search BB. This should return all objects that are potentially closer than $d$.
5. Brute force all returned objects to calculate their actual distance to your search object.

Worst case complexity of the worst case is $O(N)$ for $N$ objects, but average case should be closer to $O(log N)$.
> 2 votes

# Answer
The best I can come up with is to compute the centroid of each object and store the centroids in a nearest-neighbor data structure; to find the matches for a test object $T$, look up its centroid in the data structure and iterate through the objects in order of the distance between their centroid and $T$'s centroid and compute the distance to each. The heuristic is to stop iteration after exploring some fraction of the objects.

Depending on how you compute the distance between two objects, this might perform arbitrarily badly in the worst case, but it's possible it might be acceptable for some workloads if you don't encounter the worst case.
> 1 votes

---
Tags: algorithms, data-structures, optimization, search-algorithms, euclidean-distance
---


# Question
Title: Unbounded, 2-dimensional knapsack problem
I have the following problem:

There is rectangle with fixed $W \> w\_i$ width and $H \> h\_i$ height. Given a set of item types, where each type has some $w\_i$ width, $h\_i$ height and $v\_i$ value. I would like to maximize the value of the items placed in the rectangle.

An item can be placed as many times as needed. Not every type has to be present in the optimal solution. Two items can not overlap.

Is there any literature available for this (or a similar) problem? Is there a name for this problem? I didn't have luck with finding info on optimizing inside a 2-D region.

# Answer
Just the special case of (in your terms) 1-dimensional knapsack is NP-complete, and that is a special case of your 2-dimensional one (just take a strip of width one to be filled with strips of width one). It is very unlikely that an efficient algorithm exists for your problem.

Similar problems are handled e.g. by newspapers (need to fill pages with rectangles for ads, for instance), when cutting up sheets into custom sizes and similar applications. Search for those, there must be publications on approximation algorithms.
> 1 votes

---
Tags: knapsack-problems
---


# Question
Title: Proving the regularity of the following language
I have a question about the following problem:

> Prove that the language $\\{a^nva^n | v \in \Sigma^\*, n \ge 1\\}$ is regular over $\Sigma = \\{a,b\\}.$

I know that in proving a language is regular I can either construct a DFA, give a regular expression or show the Nerode-Relation has finite index.

My main problem is, that I cannot understand why this should be a regular language, since $\\{a^nb^n | n \ge 1\\}$ is not regular and of similar form. Also, I do not understand how a DFA should recognize the same amount of a's at the front and at the end of a word.

# Answer
You can always take $n = 1$ for any string in your language...
> 2 votes

---
Tags: formal-languages, regular-languages
---


title: To reach k set consensus (k=2)

text:
# Question
Title: To reach k set consensus (k=2)
If I can use FIFO queue and read/write registers, can I reach wait free 2 set consensus if I have 3 processes? I thought is I can, but I saw a conclusion from text book says "we cannot achieve 2 set consensus on 3 processes in shared memory system", so I'm confused now.

# Answer
> 1 votes
Quoted from Chapter 16 of the book: Distributed Computing: Fundamentals, Simulations, and Advanced Topics (2004):

> (Page 345) We now show that there is no algorithm for solving $k$-set consensus in the presence of $f \ge k$ failures.

and

> (Page 351) **Theorem 16.7** There is no wait-free algorithm for solving $2$-set consensus problem in an asynchronous shared memory system with three processors.

The proof is quite complicated. See also the paper: The Asynchronous Computability Theorem for $t$-Resilient Tasks.

# Answer
> 0 votes
Yes you can. A FIFO queue has consensus number 2, thus you can implement 2-processors consensus using FIFO queues and registers. So, let processor 1 just decide its own input, and let processors 2 and 3 use 2-processors consensus to agree on one of their inputs and decide it. At most 2 values will be decided, thus solving 2-set-consensus among 3 processors.

Note that it is impossible to implement set-consensus using only shared memory (i.e. read-write registers). In distributed computing, a shared-memory system usually means a system in which only read-write registers are present, hence your textbook quote.

---
Tags: distributed-systems
---


title: Collision entropy definition

text:
# Question
Title: Collision entropy definition
The collision entropy is defined as the Renyi entropy for the case $\alpha = 2$. It is given by

$$\mathrm{H}\_{2}(X)=-\log \sum\_{i=1}^{n} p\_{i}^{2} \tag{1}$$

Take two random variables $X$ and $X'$ which follow the same probability distribution. The probability of a collision is then simply $P\_{\rm coll} = \sum\_{i=1}^{n} p\_{i}^{2}$. I would then expect that we say the collision entropy is just $H(P\_{\rm coll})$ i.e.

$$-\left(\sum\_{i=1}^{n} p\_{i}^{2}\right)\log\left(\sum\_{i=1}^{n} p\_{i}^{2}\right) - \left(1 -\sum\_{i=1}^{n} p\_{i}^{2}\right)\log\left(1-\sum\_{i=1}^{n} p\_{i}^{2}\right)$$

This is in analogy with the binary entropy but with the probability replaced with the probability of a collision.

What is the motivation behind choosing $(1)$ to be the definition of collision entropy?

# Answer
> 1 votes
When $X$ is distributed uniformly over a domain of size $n$, then Shannon entropy, collision entropy and min-entropy are all equal to $\log n$. In a sense, all of these parameters measure the amount of uncertainty in $X$.

In contrast, your proposed definition is always between $0$ and $1$, tending to zero as $X$ gets more unpredictable. This is quite different from other notions of entropy, in which zero stands for *predictable*.

---
Tags: information-theory, entropy
---


# Question
Title: Spotting the difference between two arrays using divide-and-conquer
Say we have two equal-sized arrays that contain a 1 or 0 at each of their indices. These two arrays are identical, except at one unique index. We want to find and output that particular index.

For simplicity, assume we can use two subroutines that can sum any subarray in our first and second arrays, respectively.

How would we use this to find a suitable algorithm using a divide-and-conquer approach? And if so, how many times would it have to call the subroutines? I assume we can start by dividing our arrays into two and solving our problem recursively from there.

# Answer
Compute sums for the first two halves of the arrays, if they agree, the difference (if any) is in the second halves. If they don't agree, check first quarters, and so on.
> 1 votes

# Answer
You could just compare the values in a loop, which is trivial and works just fine. And we are now arguing about constant factors.

Consider how many array elements you read if the first two items are different (answer: n items from each array). Quite inefficient.

As a micro-optimisation adding k elements and comparing the sum would often be faster than comparing k elements. You could in a loop compare sums of k elements for some small fixed k.

Of course this only works if your guarantee (“exactly one item different”) is true, and the items are small integers so there is no overflow or rounding error. So just go with a straightforward loop unless speed is essential.
> -1 votes

---
Tags: algorithms, asymptotics, divide-and-conquer
---


title: Kleene star operations

text:
# Question
Title: Kleene star operations
Let $$ be any alphabet and let $\_ \subseteq ^{∗}$ and $\_2 \subseteq ^{∗}$ be two non-empty languages.

a. If $\_ ^{∗} \neq ^{∗}$ than what can we say about $L\_1$.

b.Let $\Lambda \in L\_1$ and $\Lambda \in L\_2$. Show using axioms and theorems of languages that $\_ ^{∗}\_2 = ^{∗}$

For (a), $\Lambda$ should not belong to $L\_1$ but I do not know how to prove that.

For (b),we have to prove that $\_ ^{∗}\_2 \subseteq ^{∗}$ and $ ^{∗} \subseteq\_ ^{∗}\_2$ for equality to exist. We can also distinguish two cases, when $L = \Lambda $, then $\Lambda ^{∗} \Lambda = ^{∗}$, but how can we prove that when $L \neq \Lambda $

Any idea

# Answer
> 1 votes
**Hint:**

You are right on (a). The proof involves key results for Kleene star as follows. $$ \Sigma^{\*}=\bigcup\_{n\geqslant1}\Sigma^{n}\quad\text{and}\quad L\Sigma^{\*}=\bigcup\_{n\geqslant1}L\Sigma^{n}\quad\text{and}\quad \Sigma^{\*}L=\bigcup\_{n\geqslant1}\Sigma^{n}L $$ Where $\Sigma^{n}$ can be considered as the set of the concatenation of i strings in $\Sigma$, and $L\subset \Sigma^{\*}$.

For (a), $L\_1\Sigma^{\*}\subset\Sigma^{\*}$ since for all $n,L\_1\Sigma^{n}\subset\Sigma^{n}$. If $\Lambda\in L\_1$, then $n,L\_1\Sigma^{n}=\Sigma^{n}$ for all $n$. Thus $L\_1\Sigma^{\*}=\Sigma^{\*}$.

For (b), notice that if $\Lambda\in L\_1$ and $L\_2$, then $L\_1\Sigma^{\*}=\Sigma^{\*}$ and $\Sigma^{\*}L\_2=\Sigma^{\*}$. Thus $L\_1\Sigma^{\*}L\_2=\Sigma^{\*}L\_2=\Sigma^{\*}$.

# Answer
> 0 votes
You already have part of the answer for (a), but there's a bit more. For example, if $L\_1 = \\{a\\}$ (and $\Sigma$ isn't just $a$) we certainly don't have $L\_1\Sigma^\* = \Sigma^\*$. Can you come up with an extension? I knew you could.

---
Tags: regular-languages, finite-automata, kleene-star
---


# Question
Title: Is this a misleading or undesirable implementation of a hash map?
I read a C++ implementation of a hash map here. https://www.geeksforgeeks.org/implementing-hash-table-open-addressing-linear-probing-cpp/

Let's say key `k1` has a hash index of `h`. Suppose there's a collision with key `k2` such that `hash(k1) == hash(k2)`. Then won't the new hash index of `k2` become `h+1`?

```
Key: k1     Index: h
Key: k2     Index: h+1

```

Suppose we introduce a third key `k3` such that `hash(k3) == h+1`. Then when we insert `k3` into the hash map, its hash index will become `h+2`.

```
Key: k1    Hash value: h      Hash table index: h
Key: k2    Hash value: h      Hash table index: h+1
Key: k3    Hash value: h+1    Hash table index: h+2

```

This can cause the hash indexes for keys to be shifted over 1 in the case of collisions (as seen above), and if collisions happen frequently then they could be shifted over more than once.

Is this a bad implementation of a hash map? From an aesthetic point of view I prefer the linked approach, where each hash node has a pointer to a next node, such that if multiple nodes have the same hash index, they are all part of the same linked list starting at that hash index.

In the linked approach, at least we have the assurance that a key will logically correspond to its hash index in the hash table, even if it's part of a linked list (in which case it doesn't physically correspond, but logically still does, since the head of the linked list is stored there).

Is the implementation of the hash map in GeeksForGeeks bad? Is the linked approach more logical and intuitive? What are your thoughts?

**Note:** The linked approach I refer to is simply to store a linked list at each hash index in the hash table, such that if multiple keys are hashed to that index, they are stored in this linked list.

# Answer
As others have indicated, this code example doesn't do resizing, and this is an important part of a "real" dynamic hash table. Whether or not it's "bad" depends on what it's trying to achieve as an example, but it's certainly not code that you should deploy.

Linear probing isn't necessarily a bad idea. After all, it has excellent locality. But since you asked about a specific scenario, let's explore that. The scenario is where you have two keys, `k1` and `k2`, which have the same hash value `h`, and a third, `k3`, with the hash value `h+1`.

Most hash table designs rely on the premise that the hash function is "good". If you have a "good" hash function, this should be a difficult scenario to engineer on purpose, but it's still possible that it happens with high enough probability just by virtue of storing a lot of entries in the hash table.

Consider an open addressing hash table with $m$ slots and $n$ elements in it. Denote the load factor by $\lambda = \frac{n}{m}$. Then if the hash function is "good", and $m$ and $n$ are large enough, the probability that a given slot has $k$ elements that would "naturally" hash to that slot is given by the Poisson distribution:

$$P(k; \lambda) = \frac{e^{-\lambda} \lambda^k}{k!}$$

So the probability that a given slot has at least 2 elements is:

$$P\_1 = 1 - P(0; \lambda) - P(1; \lambda)$$

And the probability that the very next slot has at least 1 element is:

$$P\_2 = 1 - P(0; \lambda)$$

The probability of this scenario occurring to a given hash slot is:

$$P\_1 P\_2 = 1 - e^{-\lambda} (\lambda + 2) + e^{-2\lambda} (\lambda + 1)$$

...and so on. Multiply this by $m$ to give the expected number of times this scenario happens for any $m$ and $n$.

(Exercise: Suppose that you have $m$ pigeonholes and $n$ pigeons, and you assign pigeons to pigeonholes randomly and $m$ is large enough. Then the proportion of pigeonholes with $k$ pigeons assigned follows a Poisson distribution. Show that the expected number of "pigeon collisions" is $\frac{1}{2}$ when $n = \sqrt{m}$.)

Remember, though, that short probes aren't necessarily a problem. What you're trying to avoid is long probes. Specifically, you're trying to ensure that the *maximum probe length*, that is, the largest distance that an entry is from its "home", is small. This number gives the maximum "work" that you may have to do to look for an entry.

In open addressing, it is common practice to keep track of this maximum probe length, and update it when a new element is inserted. This number is used for (at least!) two purposes: to decide when to stop searching, and to decide when to resize the table.
> 2 votes

# Answer
It's quite normal.

If your hash table is getting too full, you will get a high number of collisions - time to resize the hash table.

If your hash table is not very full, a high number of collisions is possible, but not very likely.
> 1 votes

---
Tags: data-structures, hash-tables, c++
---


# Question
Title: There are functions with f (n) = f (2n) which can't be calculated
I have to proofe that there are functions defined by $f:\mathbb{N} \rightarrow \mathbb{N}, f(n)=f(2n), \forall n\in \mathbb{N}$, which are not-computable. However I'm not really sure about the correct method.

I thought about a proof by contradiction. Assume each of those functions are computable. Then, by the Church-turing-thesis, there has to exist a TM which can compute every of those functions. Therefore $L(M)=\\{code(M) | \text{M calculates this type of function}\\}$ would be decidable. However I profed earlier, that this language is undecidable. This would lead to a contradiction, but I'm not sure about the correctness of my profe...

Thank you for your help :)

# Answer
Cook up some encoding of Turing machines so that if $n$ codes a machine, $2 n$ codes "the same" (perhaps use binary numbers ending in 1 as starting points, and 0s at the end are disregarded, thus making that odd $n$ and $n \cdot 2^k$ represent the same machine). Then use that e.g. $\operatorname{HALT}(M)$ (does $M$ halt if started on an empty tape?) isn't computable.
> 3 votes

# Answer
Another way to do it: Take any non-computable function $g(n)$, then the function defined as:

$\begin{equation\*} f(2^k (2 n + 1)) = g(n) \end{equation\*}$

for all $k \ge 0$ satisfies your conditions.
> 1 votes

---
Tags: turing-machines, computability, church-turing-thesis
---


# Question
Title: Fetching multi word instruction from memory
A per, from my understanding, instruction decode is a subcycle of Instruction fetch. Now say I have a three-word instruction to be fetched from memory(1 word opcode and remaining words operand address).

**My doubt here is: will fetch cycle makes one memory reference and remaining instruction will be fetched in ID stage of Execute cycle or fetch itself fetches the complete 3 word instruction?**

---

With this knowledge I am trying to answer the following question:

Consider a three word machine instruction

```
ADD A[R0], @B

```

The first operand (destination) `A[R0]` uses indexed addressing mode with `R0` as the index register. The second operand (source) `@B` uses indirect addressing mode.

A and B are memory addresses residing at the second and third words, respectively. The first word of the instruction specifies the opcode, the index register designation and the source and destination addressing modes. During the execution of `ADD` instruction, the two operands are added and stored in the destination (first operand).

The number of memory cycles needed during the execution cycle of the instruction is:

```
3 Cycles
4 Cycles
5 Cycles
6 Cycles

```

The total cycle can be 4 or 6 depending on how many cycles fetch is taking. If fetch takes one then Execute will take 6; if fetches take 3 cycles(to fetch complete instruction) then execution will take 4 cycles.

# Answer
> 1 votes
The answer: It depends on the implementation in that particular processor architecture. If this is just a made up example of an architecture, it probably hasn't been thought through properly, so nobody knows the answer.

That said, if I had to implement instruction fetch, then it would fetch the whole instruction.

# Answer
> 0 votes
If an instruction is variable length then we fetch one word in fetch cycle then we decode that word and if it is more than one word then we fetch these remaining words in Execution cycle. Here fetch cycle takes one memory access always, irrespective of instruction length.

If an instruction is fixed length (say 2 words each instruction) then why to fetch only one word in fetch cycle, we fetch 2 words in fetch cycle, here fetch cycle takes 2 memory access as only one-word fetching at a time.

If nothing is given then we can't just assume variable length.

# Answer
> 0 votes
As @gnasher729 says, **it is really case-dependent.**

If your question is for the fundamental course purpose, it is better to figure out the specific implementation of processors (stimulators also) and instructions. There are some ways to analyze it generally, like the number of memory access, but not all instructions follow it either.

---
Tags: computer-architecture
---


title: Support Vector Machines as Neural Nets?

text:
# Question
Title: Support Vector Machines as Neural Nets?
This is more of a conceptual question.

I have learned about Neural Nets, and I have some clue as to how Support Vector Machines work. I read somewhere however that given the appropriate kernel (is that right?), the SVM is identical to the Neural Net. Could someone who understands this please enlighten me as to how that's possible?

# Answer
An SVM with a linear kernel has the same expressive power as a single perceptron in a neural net, since both are linear classifiers. If you think of the kernel function as mapping your input to a higher dimensional feature space then the SVM is still a linear decision boundary in that high dimensional kernel space. You could theoretically use the high dimensional kernel space features as input to a neural network as well as long as the kernel space is finite. Again the linear SVM behaves similarly to a single perceptron.

However, this only applies to linear SVMs. In practice SVMs are typically used with a non-linear kernel, and then no such equivalence applies. So this claimed equivalence might be a bit misleading, if you are comparing how SVMs tend to be used in practice to how neural nets tend to be used in practice.

Summary: Think of an linear SVM as being similar to a single perceptron instead of a neural network.
> 4 votes

# Answer
For simplicity lets consider a simple single hidden layer feed forward neural net for binary prediction. At test time the neural network predicts

$$ p(Y = 1 \mid X = x) = \sigma(w \cdot \varphi(Ax)), $$ where $w$ is the vector of hidden to output connections, $A$ is the matrix of input to hidden connections, $\sigma$ is the logistic sigmoid function, $\varphi$ is an element wise function (normally something like a sigmoid, tanh, rectified linear, etc), and I've ignored biases for simplicity.

Now skim through the section Nonlinear Classification in the SVM Wikipedia article. Notice how essentially we have the same thing above, but with everything happening in the neural network before the final dot product serving as the *transform* function $\varphi$, and that's it. The advantage of neural networks is they allow you to easily *learn* this transform, which can be very beneficial.
> 2 votes

# Answer
some says it is because of this architecture SVM is comparable to neural nets
> 2 votes

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


# Question
Title: Why do some search trees store all the elements in leaves, while others don't?
1. Why do some **search trees** store all elements in the leaves, while other search trees don't? One difference that makes is whether a successful search may end up in an internal node.

For m-ary search trees, the former case will need more leaves and more heights than the latter. Is this the benefit of not storing all the elements in the leaves?

Is storing all the elements in the leaves only for looking consistent? Does it have some benefits? Someone said that

> Contrary to what you said, in the three examples you gave, the internal nodes also contain values.
>
> In a B+ tree for example, all values are located in the leaves, the internal nodes only contains keys
>
> "This is interesting only when the data is separated in a key and some other value (as in a database). This **allows more keys to go in the internal nodes**, **limiting the tree depth**. When the nodes are on a slow medium, this limits the time needed to go to the data." But I don't quite understand that, because

* when we choose to store records in the internal nodes, we don't need to store the actual records in the internal nodes, but can always store with each key a pointer to the actual records, so that we can save space to store more keys. So I don't understand why he said that "**This allows more keys to go in the internal nodes**".
    * as mentioned above, I guess storing elements in the leaves rather than also in internal nodes will make the search trees higher, so I don't understand why he said that storing all the elements in the leaves can "**limit the tree depth**".
2. **For B-trees and 2-3 trees**, why do some references define them so that all the elements are stored in the leaves, while other references don't? Note that 2-3 trees are special B-trees, according to Aho's book.

I just found that

* the definitions of 2-3 trees and B trees in Aho's Data Structures and Algorithms store all the elements in the leaves, so that a successful search always end up in a leaf
    * But the examples of 2-3 trees and B trees in Wikipedia and also in wikipedia and in Sedgewick's Algorithms (also see the first picture below) and in CLRS (see the second picture below) store only some elements in the leaves, so that a successful search may end up in an internal node.
3. For **binary search trees**, why all the references define them so that not all elements are stored in the leaves?

I haven't seen any reference that define binary search trees with all elements defined in the leaves, or am I missing it?

Can Huffman trees be viewed as binary search trees where all the elements are defined in the leaves?
4. Is balancing the only or most important aspect where **2-3 trees** improves over **binary search trees**?

From the above questions, I mentioned that some references define 2-3 trees so that all the elements are stored in the leaves, while others don't, and within my readings, binary search trees are always defined so that not all the elements are stored in the leaves. Is whether search trees store all elements in the leaves an important aspect to distinguish between 2-3 trees and binary search trees, as important as the balancing aspect?

Thanks.

# Answer
The point is that often data is bulky and moreover of variable size (i.e., a full student record) while the keys needed to locate the data (name, enrollment number) is small and fixed size. Different requirements, keep them separate.
> 2 votes

# Answer
There are a lot of questions in here, and I'm going to pick out a few that may help answer your questions.

**Why do some search trees store all elements in the leaves, while other search trees don't?**

Others have mentioned the difference between B-trees and B+-trees. For databases specifically, B+-trees have a huge advantage over B-trees: they support range queries more efficiently.

Consider a SQL statement such as:

```
SELECT something FROM table
WHERE field >= 10 AND field < 20;

```

Suppose also that there is a B+-tree index on `field`, where the leaf nodes are connected (e.g. they form a doubly-linked list) in addition to the tree above them. Then one way to satisfy this query is to search for the value 10 in the index, and then traverse the leaf nodes.

With B-trees, you would have to traverse up and down the tree, which involves accessing (and, in a concurrent environment, *locking*) more nodes/disk pages.

**Can Huffman trees be viewed as binary search trees where all the elements are defined in the leaves?**

Huffman trees usually aren't binary search trees. In binary search trees, an inorder traversal results with the leaves ordered according to "less than" ordering. In Huffman trees, that is usually not the case.

Consider the following frequency distribution over the following alphabet:

```
A     1
B     8
C     1

```

Any valid Huffman tree must have a node with A and C as children. But A \< B \< C. So you cannot have a Huffman-shaped binary *search* tree for this frequency distribution.

(Having said that, some applications of Huffman trees remap the alphabet into increasing or decreasing *frequency* order. See, for example, canonical Huffman codes or Wavelet trees.)

**Is balancing the only or most important aspect where 2-3 trees improves over binary search trees?**

Probably not even that. Research is fairly consistent that any balancing scheme for binary search trees is as good as any other. The purpose of balancing BSTs is to avoid pathological behaviour (i.e. "sticks"), and so a choice of balancing scheme should be based on criteria other than how well it balances.
> 2 votes

# Answer
You mention that "2-3 trees are special B-trees". Note that B-trees are different from **B+-tree**. In a B-tree, internal nodes also store part of the keys, while in a B+-tree, keys are all stored in the leaves. Therefore, 2-3 trees, as B-trees of order 3 by definition, can have elements in their internal nodes.
> 1 votes

---
Tags: data-structures, search-trees, balanced-search-trees
---


# Question
Title: How many snakes there can be in the "snakes and ladders" game?
How to calculate the maximum allowed number of snakes in the game of "snakes and ladders" from mathematical/algorithmic point of view assuming that there is a nxn board?

UPD: My thoughts are simple, but they might be incorrect: I suppose once any two fields on the board cannot be involved twice forming a snake it means that in nxn board there can be nxn/2 snakes

# Answer
If we assume any given square can be the head or tail (but not both) of at most one snake then clearly an upper limit on the number of snakes on a $n \times n$ board is $\frac {n^2} 2$. For a $m \times n$ board we can generalise this to $\frac {mn} 2$. And we can reach this upper limit if either $m$ or $n$ is even. What happens if $m$ and $n$ are both odd ?
> 2 votes

---
Tags: algorithms, discrete-mathematics, board-games
---


title: Reservoir Sampling vs Round Robin

text:
# Question
Title: Reservoir Sampling vs Round Robin
You are given a List of numbers (length unknown).

Let's say the length is 10.

GetRandom(List) is called once. If implemented correctly, each number has 1/10 probability of being returned.

GetRandom(List) is called 100 times. If implemented correctly, each number will appear 10 times in the result.

*Fine?*

You now have to do the same for a Stream of numbers.

GetRandom(Stream, 5) is called. This adds 5 to the Stream. Stream is of length N=1, then 5 is returned (probability = 1/N = 1)

GetRandom(Stream, 3) is called. 3 is added to stream. N=2. Either 3 or 5 is returned (prob = 1/2).

How will this be tested for correctness?
If GetRandom(Stream) (without adding any more numbers) is called 10 times when length of list is 2, each number (3 & 5) should be returned ~5 times.

GetRandom(Stream, 7) is called. 7 is added to Stream. N = 3. One of the 3 numbers (5, 3, 7) is returned (probability = 1/3).

But how will this be tested for correctness?
If GetRandom(Stream) is called 10 times when N = 3, each number is returned ~3 times.

*So far, so good ?*

Alright, here is my algorithm:

```
N = 0
Pointer = 0

GetRandom(Stream, Number = NULL):
    Pointer += 1

    if Number is NOT NULL:
        N += 1
    else:
        if Pointer == N:
            Pointer = 1    # Reset

    return Stream[Pointer]    # Assume 1-based indexes

```

This simply cycles through all numbers in order / round-robin fashion.

If GetRandom(Stream) is called on a Stream with 100 numbers, 1000 times, each number will appear exactly 10 times.

If GetRandom(Stream, 77) is called on a Stream with 100 numbers (77 is the 101st number), while Pointer got reset to initial location 1. Then when GetRandom(Stream) is called 101 times, then on the 101st call, 77 will be output, which satisfies the required probability of 1/101. If it's called 202 times, then on the 202th call, 77 will be output, which satisfies 2/202.

Why bother with Reservoir Sampling k/k+1, Why bother with a random number generator?

# Answer
> 3 votes
it seems that you're asking why bother with reservoir sampling when you're capable of tricking the test that you wrote?

Round robin doesn't return random numbers. It returns numbers deterministically. Well much more deterministic seeming than reservoir/other methods.

Your tests should be better. If you need the result to seem random and not deterministic, make a test which captures that instead of one which is based on empirical probability.

EDIT to add a test example: another test for randomness (one that round robin would fail) is that you run the same process many times and don't get the same result every time. For uniform random sampling of a stream (the output of reservoir sampling) for a set/list/stream of a fixed size the probability to get one specific subset of size k should be 1/(n choose k) . You can run your method once then another 10000 (or any number of times) and see that you get the first result approximately only 1/(n choose k) times.

---
Tags: probability-theory, randomness
---


title: Designing a DFA and the reverse of it

text:
# Question
Title: Designing a DFA and the reverse of it
There is a theorem that says if a language is regular, its reverse is regular as well. How can I draw a DFA that shows if a language is regular, it's regular as well?

# Answer
> 19 votes
$L^R$ is the reverse of the language $L$ and for designing $L^R$ you must:

1. Reverse all edges in the transition diagram.
2. The accepting state for the LR automaton is the start state for the main automaton.
3. Create a new start state for the new automaton with epsilon transitions to reach of the accept states for the main automaton.
4. Convert this NFA back into a DFA.

# Answer
> -1 votes
To write the reverse of a DFA, Change all the initial states to final and the final ones to initials(for the later, if there are multiple final states, use a new state and use null transitions to each of them). At last... Reverse the edges.

---
Tags: regular-languages, automata
---