# Question
Title: Dependency on adjacent blocks decreases as block count increases
The following is an excerpt from *Information Theory: A Tutorial Introduction*, page 65.

> Now, supposing the identity of each letter in English does not depend on any letter that is more than 10 letters away. In practice, the dependency between letters diminishes rapidly as inter-letter distance increase, as shown in Fig. 3.6. Once the block length has grown to $N = 10$, the identity of every letter in a given block $B\_k$ depends on other letters in that block and exactly two other blocks: the previous block $B\_{k-1}$ and the next block $B\_{k+1}$. All other blocks contain letters which are more than 10 letters away from, and therefore independent of, every letter in block $B\_k$.
>
> **If the original text is sufficiently long, and if there are a large number of blocks, then the dependency between adjacent blocks just described accounts for a tiny proportion of the overall dependency between blocks. Thus, the more blocks there are, and the longer each block is, the smaller the dependency between blocks.** By analogy, it is as if each block is one of a large number of independent super-symbols, and if the blocks are independent then finding their entropy is relatively simple. The only question is, how long do those blocks have to be to ensure that they are independent?
>
> The block length beyond which inter-letter dependence falls to zero is called correlation length $N\_C$. Once the block length exceeds the correlation length, it is as if all blocks are effectively independent, so increasing the block length $N$ beyond $N\_C$ has a negligible effect on the estimated entropy $G\_N$. At this point, $G\_N$ equals the entropy of English; that is $G\_N = H$. This matters because Shannon's theorems are expressed in terms of infinite block lengths, but in practice these theorems apply to any block length which exceeds the correlation length of the sequence under consideration.

Given some block, I can't see how block count decreases dependency on two blocks adjacent to it. Could someone, please, explain?

# Answer
> The more blocks there are, and the longer each block is, the smaller the dependency between blocks.

There are two tendencies. Let us explain one by one.

(**Tendency of more blocks**) Assume the block size does not change. The more blocks there are in a string, the smaller the dependency between blocks.

Suppose the block size is greater than 10. Suppose there are $N$ blocks. Since each block depends only two other blocks, the previous block and the next block, the total number of (unordered) dependent pairs of blocks is $N-1$ as each block is dependent on its next block except that there is no next block to the last block. There are $N(N-1)/2$ (unordered) pairs of blocks in total. The ratio of dependent pairs to all pairs, $\dfrac{N-1}{N(N-1)/2}=\dfrac 2N$ becomes smaller and smaller and can be arbitrarily close to 0 when $N$ goes bigger and bigger. That is one way in which we can understand the meaning of tendency of more blocks.

If the block size is not greater than 10, we can argue similarly since each block will depends on at most previous $\lceil\dfrac {10}{\text{block size}}\rceil$ blocks and next $\lceil\dfrac {10}{\text{block size}}\rceil$ blocks.

(**Tendency of longer blocks**) The larger each block size is, the smaller the dependency between adjacent blocks.

Consider two adjacent blocks $B$ and $C$ with $C$ following $B$. Let us consider the ordered pairs of letters where the first letter is in $B$ and the second letter is in $C$. Since every letter does not depend on any letter that is more than 10 letters away, there are at most $1+2+\cdots+10=55$ such pairs in which the two letters are dependent. As the block size $S$ goes bigger and bigger, the number of all possible pairs $S\times S$ becomes bigger and bigger quadratically. However, the number of dependent pairs stays at 55 once the block size is no less than 10. Hence the ratio of dependent pairs to all pairs becomes smaller and smaller. This is one way how we can understand the meaning of tendency of longer blocks.

If we agree that the nearer the letters, the stronger the dependency between them, then we can see that the dependency between adjacent blocks becomes smaller and smaller when the block size grows bigger and bigger even if we do not require the block sizes are no less than 10.

---

The above explanation follows roughly the same style as the original text. To be more precise, we should define the correlation of two blocks in mathematical terms and we should show how the ordered dependent pairs of letters from two blocks contribute/determine to the correlation of two blocks. That will not be an easy undertaking to be done rigorously. However, it is, I believe, intuitively clear that ratio of dependent pairs from two blocks to the total pairs is in proportional (not necessarily linearly) to the dependency of the two blocks, as long as the latter is defined reasonably. So the above explanation should convince you the correctness of the quoted conclusion. After all, that quoted conclusion is supposed to be easy and intuitive to understand.

---

> Given some block, I can't see how block count decreases dependency on two blocks adjacent to it.

If "block count" means the number of letters in a block, then "larger block count decreases dependency between the given block and either of the two blocks adjacent to it" is the tendency of more blocks as I have explained in the above.

If we consider "block count" as the number of blocks, then "larger block count" does not decreases dependency between the given block and either of the two blocks adjacent to it, as you believed.
> 2 votes

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


title: Prooving by Pigeonhole principle

text:
# Question
Title: Prooving by Pigeonhole principle
I've been given a question to solve:

`Given a set of non-negative distinct integers, and a value m, determine if there is a subset of the given set with sum divisible by m.`

For this, I used the dynamic programming approach which is not optimized and takes **O(m * m * n)** where `n` is the no. of distinct elements.

But, It's optimized time-complexity is **O(m^2)**. Here, is the solution.

But, while going through the explanation, I encountered this written:

`If n > m there will always be a subset with sum divisible by m (which is easy to prove with pigeonhole principle). So we need to handle only cases of n <= m.`

I did not understand this part and want to know, how will it be proved rather than trying it by taking examples.

Also, why is the equality present with `n < m` and not with `n > m` ?

# Answer
This problem is a variant of subset sum problem and in subset sum problem we have a target sum to achieve, according to which we can size our DP table but in our case we do not have any specific target sum but we want a sum which is divisible by some $m$. In the process we can have arbitrary intermediate sums and we do not have a clear bound to how to size the DP table.

One naive approach would be to have the maximum sum possible in the set divided by $m$, and then we can subtract the mod of that division from this maximum sum. This can be an upper bound to our possible sums in the set, but this can be very large for bigger values.

The solution is divided in two parts ($n$ is the no of elements in set):

1. $n \> m$, for $n \> m$ we will always have a subset with sum divisible by $m$.
2. $n \<= m$

For the first case where $n \> m$, let us define the set as $X = {X\_1, X\_2, ..., X\_n}$. Now if any value $X\_i$ is divisible by $m$, the claim trivially holds. Now, let us consider partial sets as $P\_i = \\{first\ i\ values\ of\ set\\}$ and modular sum

as $S\_i = sum(P\_i)%m$. So,

$S\_1 = (X\_1)%m$

$S\_2 = (X\_1 + X\_2)%m$

$S\_n = (X\_1 + X\_2 + ... + X\_n)%m$

If any of these values is 0 then the claim trivially holds as we have achieved a sum which is divisible by $m$. Also, if any of these value repeats i.e. some $S\_i = S\_j$ where $j \> i$, then also this claim holds. (why? we have added a multiple of m to Si to achieve $S\_j$ (e.g. 5%3 = 2 and 8%3 = 2, but 8-5 = 3)).

So this says that from $S\_1$ to $S\_N$ we must have distinct values. The range of mod function is 1 to $m-1$. Since $n \> m$, so for $S\_1$ to $S\_n$ some value should repeat from 1 to $m-1$. This is the pigeonhole principle in application.

For the second case we have the above solution. The mentality of this solution is that we will record all the mod values which can be obtained when partial sums are divided by $m$. If at any stage we capture the mod value to be zero then we are done. Also the bottom up procedure adds one element at each time.
> 1 votes

# Answer
Let the $n$ distinct positive integers are represented by $c\_1,\ldots,c\_n$. Now form a series of sums as;

\begin{align} S\_1 =&\\; c\_1 \\ S\_2 =&\\; c\_1 + c\_2\\ \vdots & \\ S\_n =&\\; c\_1 + \ldots c\_n \end{align}

Now, use the pigeonhole principle on the $S\_i$'s with $m$ holes and place them into the holes according to their result modulo $m$. We know that at least two $S\_i$'s are sharing the same hole since $n\>m$. Let call them $S\_i$ and $S\_j$.

$S\_i \equiv S\_j \bmod m \implies S\_j -S\_i \equiv 0 \bmod m \implies m| S\_j-S\_i$

By using the definition of $S\_i$ and $S\_j$ we can say that if $i\<j$ then $m \\;|\\; a\_{i+1} + \ldots + a\_{j}$

if $n \<= m$ we cannot prove it and even we can find counterexamples.
> 1 votes

# Answer
Let us prove the following **stronger proposition**. Notice that we do not require the given integers to be non-negative nor distinct. Also note that we do not require $n$ to be strictly greater than $m$.

> Given an array of $n$ integers and a positive integer $m\le n$, there will always be a nonempty subset with sum divisible by m.

Here is a simple proof.

Let $a\_i$ be the $i$-th element of the array, $0\le i\le m-1$.

Let $s\_i=a\_0+a\_1+\cdots+a\_i$ and (pigeon) $r\_i=s\_i\\%m$, the remainder of $s\_i$ divided by $m$. That is, $s\_i-r\_i$ is a multiple of $m$ and $0\le r\_i\lt m$. Note that the number of all possible values of remainders (holes) is $m$. Thera are two cases.

* All $r\_i$ are distinct. Since the number of $r\_i$ (pigeons) is $m$, all holes must be occupied by a pigeon. That means $0=r\_s$ for some $s$. That is, $a\_0+\cdots+a\_s$ is divisible by $m$.
* All $r\_i$ are not distinct. Suppose $r\_{i\_1}=r\_{i\_2}$ for some $i\_1\<i\_2$. Then $$(a\_{i\_1}+a\_{i\_1+1}+\cdots+a\_{i\_2-1})\\%m=(s\_{i\_2}-s\_{i\_1})\\%m=s\_{i\_2}\\%m-s\_{i\_1}\\%m=r\_{i\_2}-r\_{i\_1}=0$$

Proof is done.

Note that $m$ is best lower bound of $n$ to ensure a nonempty subset with sum divisible by $m$. If we allow $n\lt m$, it is possible that there is no subset with sum divisible by $m$. For example, we can have $m-1$ 1's. For any subset of $k\>0$ numbers, its sum is $k$, which is not divisible by $m$. If we require them to be distinct, we can take $1, m+1, 2m+1, \cdots, (m-2)m+1$.

---

Thanks to the above stronger proposition, we need to handle only cases of $n \lt m$ instead cases of $n\le m$ in the original article.
> 1 votes

# Answer
“It’s easy to prove”, so the proof should be short.

Calculate the sum of the first k numbers modulo m, for 0 \<= k \<= m. There are m+1 sums, and only m possible values, so two sums are equal modulo m. Their difference is divisible by m.
> 1 votes

---
Tags: algorithms, dynamic-programming, proof-techniques
---


# Question
Title: Will MST find the shortest path for each pair $(r,v)$?
Will local best choice will lead to global best choice? In other words, I'm thinking about whether it's possible that the MST has to put its branch location in the middle of two far nodes `A`,`B` and thus would make the path from root to `A` and `B` respectively not the global minimum?

---

This is Prim's algorithm, at page 634 (655 is pdf reader page):

While this is Dijkstra, at page 658 (679 is pdf reader page):

Book: Introduction to Algorithm 3ed.

# Answer
No, the MST may not find the shortest path for each pair of nodes $(r,v)$.

For example, consider a graph of three vertices $A,B,C$ with edge weight $AB\mapsto 2, AC\mapsto 2, BC\mapsto 3$. Its MST is edges AB and AC. However, the shortest path between $B$ and $C$ is the edge BC.
> 1 votes

---
Tags: algorithms, graphs, shortest-path, minimum-spanning-tree
---


title: Is this system Turing complete?

text:
# Question
Title: Is this system Turing complete?
I want to develop a genetic program that can solve generic problems like surviving in a computer game. Since this is for fun/education I do not want to use existing libraries.

I came up with the following idea:

The input is an array of $N$ integers. The genetic program consists of up to $N$ ASTs, each of which takes input from some of the array elements and writes its output to a single specific array element.

The ASTs can be arbitrary complex and consist only of four arithmetic operators ($+$, $-$, $\times$, $/$) and can operate on constants and fixed elements of the given array (no random access).

So for $N=3$, we have three ASTs, for example:

\begin{align\*} a\[0\] &= a\[0\] + 1\\ a\[1\] &= a\[0\] + a\[1\]\\ a\[2\] &= a\[0\] \times 123 + a\[1\]\\,. \end{align\*}

The $N$ ASTs are executed one after another and this is repeated infinitely.

Now my question, is this Turing complete or will it fail to solve some kinds of problems common for an game AI?

# Answer
You can probably use this to simulate register machines and, if you can do that, the system is Turing complete.

The setup is as follows.

* The machine has a sequence of names registers, each of which holds a non-negative integer.
* Program instructions are labelled with non-negative integers and execution starts with, say, instruction $0$;
* The three possible instructions are:
    + halt;
    + increment register $R$ and goto instruction $I$ (where $R$ and $I$ are integer constants);
    + if register $R$ is zero, goto instruction $I$; else, decrement $R$ and goto instruction $J$ ($R$, $I$ and $J$ are constants).

For example, the following program adds the contents of registers $0$ and $1$ and halts with the sum in register $0$:

```
0. if R1=0, goto 2 else decrement R1 and goto 1
1. increment R0 and goto 0
2. HALT

```

My recollection from computation theory classes 20+ years ago is that you can simulate a Turing machine using a register machine with two registers (and certainly with some fixed number of registers). Proving this is long and tedious because you have to code up the tape and all manipulations of it as arithmetic operations and, heck, you even have to code up arithmetic operations such as addition, multiplication and exponentiation. Oh, and you'll probably have to be more careful than I was with my addition routine, because you'll probably want to do arithmetic on two values without destroying them both, which requires copying them to extra registers and then copying back.

You can simulate a two-register machine (i.e., a register machine with two registers) with $n$ instructions with your system as follows. Use two array cells to store the register values, and then probably one array value for each instruction, such that $A\[i\]=1$ if instruction $i-2$ is the next to be executed and $A\[i\]=0$, otherwise. Then executing the system with $A=\[x,y,1,0,\dots,0\]$ should simulate the register machine running with input $x$ in the first register and $y$ in the second. If there are $n$ instructions in the program, ASTs will look like this:

$$A\[i\]=(A\[2\]\*v\_0) + (A\[3\]\*v\_1) + ... + (A\[n+2\]\*v\_n)\\,,$$

where $v\_j$ is the value that should be stored in $A\[i\]$ if instruction $j$ is executed.

Note that all of this assumes that the array elements can hold unboundedly large numbers. If not, your system only has a finite number of states so cannot be Turing-complete. The simulation I have in mind only uses non-negative integer values in the arrays.
> 2 votes

# Answer
If your $/$ operation is integer division (i.e. rounds towards 0, or towards the nearest integer, or in some other ways is confined to integers), and your array elements can grow arbitrarily large, your system is Turing-complete even without any form of branching (and without the ability to use a non-constant an array index, which could be used as a form of branching).

There's been investigation into this sort of system (arithmetic, but no branching) in various places (including on Stack Exchange); my own name for it is "Blindfolded Arithmetic" (i.e. you're doing sums, but you never get to look at the values you're working on because you don't have a conditional). A summary of many of the results is available here.

The basic idea behind the known solutions is to use integer division as a relational operator (if you're rounding towards 0, $1 \over (x\times x)+1$ is 1 if and only if $x$ is 0; and for positive $a$ and $b$, $b+1 \over a+1$ is 0 if and only if $a$ is larger than $b$), and multiplication to form conditionals (e.g. $a+(c\times(b-a))$ is $a$ if $c$ is 0, or $b$ if $c$ is 1).

Once you have relational operators and conditionals, all you need is a way to simulate unbounded storage. The normal method of doing this is to simulate stacks (which contain a finite number of possible elements, but can grow unboundedly large) using the digits of an array element to some base. For example, using base 10, you have 10 possible digits; pushing to the stack is multiplying by 10 and adding the new digit; popping the stack is a division and modulus ($a$ mod $b$ can be written as $a-(b\times(a/b))$). Two stacks allow you to simulate a tape, and then you can build a Turing machine. (You can even simulate halting, via division by zero.)

Without unbounded array elements, this can't be Turing-complete because it only has finitely many states. If your division works on the rationals rather than integers, I don't know what the computational class of the resulting language would be (there's no obvious way to prevent rounding errors accumulating, but there might be a subtle way to do so).
> 0 votes

---
Tags: computability, computation-models, turing-completeness
---


# Question
Title: What's the usage of $S$ in Dijkstra shortest path algorithm in the book Introduction to Algorithms?
I don't understand how the $S$ is needed in dijkstra shortest path algorithm. For each node $v$ in $G.V$, the $v.\pi = previous\\\_node$ is used to denote it previous node in the shortest path to the current node, and $\rm{}INITIALIZE\rm{-}SINGLE\rm{-}SOURCE(G,s)$ also initialize all $v.\pi=NIL,$ so if it's impossible to reach some node, a simple check $$\textrm{if }v.\pi==NIL$$ is enough. So why the $S$ is needed? If all node can be reached then $S=G.V$ and it will be useless...

**Edit**: I add the book statement, but I wonder since that the priority queue has been used, the description becomes inconsistent with the pseudocode follows, no need to refer to $V-S$, which will slow down the algorithm?

**Edit2**: I suspect that priority queue is not a requirement of dijkstra SP algorithm, it's just a technique to speed up it, so the pseudocode in my another question on Dijkstra's SP algorithm is correct?

**Edit3**: Now I got stuck on my own comment, I suspect it's not correct:

* >

I tried to make use of $S$, so I tried $G.Adj\[u\]\color{blue}{-S}$ and thought it will speed up the updating, but what if the following happen that the edge $(\color{red}{v,u})$ will not be selected since $\color{blue}S$ is already subtracted?

+

---

Book: Introduction to Algorithm 3ed. page 658, (forget about the679 is just pdf reader page #.)

# Answer
> 3 votes
Yes, the set $S$ is not needed in the Dijkstra’s algorithm, which is at the beginning of section 24.3, *Dijkstra’s algorithm* of the book *introduction to algorithms* by CLRS, third edition. That is, line 2 and line 6 in procedure DIJKSTRA($G,w,s$) can be removed without affecting the algorithm.

One immediate purpose of $S$ is to facilitate the proof of theorem 24.6 (Correctness of Dijkstra’s algorithm) of the book. Also, other implementations of Dijktra's might use that set more visibly such as the set of visited nodes in Wikipedia's entry. It is indeed a cornerstone concept to understand Dijktra's algorithm.

By the way, your observation that the line 7 of line 7 could be improved to "for each vertex $v \in G.Adj\[u\]\setminus S$" is very nice. In fact, that is done in the Wikipedia' entry mentioned above. Should that be done, $S$ could not be removed any more as you have emphasized.

---
Tags: algorithms, graphs, shortest-path, minimum-spanning-tree
---


title: DFA accept 00 as a substring

text:
# Question
Title: DFA accept 00 as a substring
How can design this question if we have an equation like that ={wxw | w={0,1}\* , x=00} accept 00 it means not contain 000,001,100, but accept all these {00,1001,110011,001000001.....}. Thank you for helping me.

# Answer
> 0 votes
as said above the language is non-regular , since there is no way a Finite automata can compare the existence of two same string in a single compound string. which is the case here. its is advised that please show the efforts that you made apart from asking questions.

# Answer
> 0 votes
After processing k 1’s in a row, the shortest string that would be accepted is 00, followed by k 1’s. This shows that after processing k 1’s or k’ 1s for k != k’, we are in different states. Which means there is an infinite number of states, therefore no DFA.

In general for any prefix u there is a set of suffixes v such that uv is in the language. Each such set is a state; if there are infinitely many different sets of suffixes leading to an accepted string then there is no DFA.

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


# Question
Title: What should be the minimum value when the two threads are executed concurrently
```
int count=0;
void *thfunc()
{
    int ctr=0;
    for(ctr=0;ctr<100;ctr++)
    count++;
}

```

If \*thfunc() is executed by two threads concurrently in a uniprocessor system, what will be the minimum value of count when both threads complete their execution? Assume that count++ is performed by using three instructions:(1) Read value of count from memory to a CPU register R,(2) Increment R,(3) Store the value in memory.

(a) 200

(b) 2

(c) 100

(d) None of the above

According to me, the answer should be 100. I cant find any execution sequence in which the count value can go down below 100. But my manual says that the answer is 2.

Can anyone please tell me what I am doing wrong? Also, please explain how the answer 2 is obtained?

Thanks in advance!

# Answer
Here's a tricky interleaving. `R1,R2` denote the independent logical registers used by the threads, while `count` is the shared variable in memory.

* Thread 1 starts its first iteration, performing only a read. `count=0, R1=0, R2=?`
* Thread 2 performs 99 iterations. `count=99, R1=0, R2=99`
* Thread 1 completes its first iteration (increment and write). `count=1, R1=1, R2=99`
* Thread 2 starts iteration #100, performing only a read. `count=1, R1=1, R2=1`
* Thread 1 performs the other 99 iterations. `count=100, R1=100, R2=1`
* Thread 2 completes its iteration #100 (increment and write). `count=2, R1=100, R2=2`
* Both threads now exit, having completed their execution.

So, the sequence is something like

```
rX = read by thread X
iX = local increment by thread X
wX = write by thread X

r1,
r2,i2,w2,r2,i2,w2,...,r2,i2,w2,  (99 full iterations)
i1,w1,
r2,
r1,i1,w1,r1,i1,w1,...,r1,i1,w1,  (99 full iterations)
i2,w2

```
> 4 votes

---
Tags: operating-systems, parallel-computing, threads, mutual-exclusion
---


# Question
Title: What, if any, is the term for a node whose children are all leaf nodes?
More specifically, I'm interested to know if there is a term that describes a tree node that meets two conditions: \- It has \>= one child \- Any children that it has are all leaf nodes.

# Answer
They are classified as nodes of height 1 by convention in the case of a rooted tree.

The height of a node $N$ is the number of edges on the longest downward simple path from $N$ to a leaf, according to *Introduction to Algorithms* by CLRS as well as the Wikipedia entry.

You might want to use penultimate nodes as suggested by Orlp. Please note some papers define a penultimate node slight differently on general graphs as a nonleaf node that is adjacent to a leaf node. For example, Patrolling Games.
> 2 votes

---
Tags: data-structures, terminology, trees
---


title: probability of collision

text:
# Question
Title: probability of collision
my data's range is from 1 to 9 and I have two subsets of integers from this range. the hash function takes each of this subsets and calculate product of these three integers and maps this set to the result of this multiplication.I want to know the probability of collision by this hash function with this two subsets of integers that they are from 1 to 9 and the size of each subset equals 3.

# Answer
> 0 votes
Here is a Python program that uses brute-force to compute the probability of hash collision of two randomly-chosen different 3-element subsets of $\\{1,2,3,4,5,6,7,8,9\\}$.

Here is the output of the program.

```
6 [(1, 2, 3)]
8 [(1, 2, 4)]
10 [(1, 2, 5)]
12 [(1, 2, 6), (1, 3, 4)]
14 [(1, 2, 7)]
16 [(1, 2, 8)]
18 [(1, 2, 9), (1, 3, 6)]
15 [(1, 3, 5)]
21 [(1, 3, 7)]
24 [(1, 3, 8), (1, 4, 6), (2, 3, 4)]
27 [(1, 3, 9)]
20 [(1, 4, 5)]
28 [(1, 4, 7)]
32 [(1, 4, 8)]
36 [(1, 4, 9), (2, 3, 6)]
30 [(1, 5, 6), (2, 3, 5)]
35 [(1, 5, 7)]
40 [(1, 5, 8), (2, 4, 5)]
45 [(1, 5, 9)]
42 [(1, 6, 7), (2, 3, 7)]
48 [(1, 6, 8), (2, 3, 8), (2, 4, 6)]
54 [(1, 6, 9), (2, 3, 9)]
56 [(1, 7, 8), (2, 4, 7)]
63 [(1, 7, 9)]
72 [(1, 8, 9), (2, 4, 9), (3, 4, 6)]
64 [(2, 4, 8)]
60 [(2, 5, 6), (3, 4, 5)]
70 [(2, 5, 7)]
80 [(2, 5, 8)]
90 [(2, 5, 9), (3, 5, 6)]
84 [(2, 6, 7), (3, 4, 7)]
96 [(2, 6, 8), (3, 4, 8)]
108 [(2, 6, 9), (3, 4, 9)]
112 [(2, 7, 8)]
126 [(2, 7, 9), (3, 6, 7)]
144 [(2, 8, 9), (3, 6, 8)]
105 [(3, 5, 7)]
120 [(3, 5, 8), (4, 5, 6)]
135 [(3, 5, 9)]
162 [(3, 6, 9)]
168 [(3, 7, 8), (4, 6, 7)]
189 [(3, 7, 9)]
216 [(3, 8, 9), (4, 6, 9)]
140 [(4, 5, 7)]
160 [(4, 5, 8)]
180 [(4, 5, 9)]
192 [(4, 6, 8)]
224 [(4, 7, 8)]
252 [(4, 7, 9)]
288 [(4, 8, 9)]
210 [(5, 6, 7)]
240 [(5, 6, 8)]
270 [(5, 6, 9)]
280 [(5, 7, 8)]
315 [(5, 7, 9)]
360 [(5, 8, 9)]
336 [(6, 7, 8)]
378 [(6, 7, 9)]
432 [(6, 8, 9)]
504 [(7, 8, 9)]
3-element subsets: 84
total pairs: 3486
duplicity:  27
probability: 0.00774526678141136

```

The last line of the above output shows the wanted probability is $\dfrac{27}{3486}\approx 0.0077$.

I do not see any mathematical technique that can lead to an easy and fast calculation by hand. If we are asked to compute that kind of probability for many-element subsets such as 10-elements subsets of $\\{1,2,\cdots, 40\\}$, we might be motivated to find a more efficient solution such as using integer factorization or some algorithms from the problem of subset sums, which may or may not be useful. Otherwise, a program that takes several minutes to write and less than a second to run is the perfect usage of our programming ability and our computers.

# Answer
> 0 votes
I made a program to brute force this.

This means that a very close low bound of this would be $\frac{36}{441}$, so a not that big chance.

If you wanted to avoid overlaps, I suggest you either use a different algorithm or block out all the duplicates, because the chance of this overlapping is pretty high ($8\\%$).

---
Tags: probability-theory, hash, statistics
---


# Question
Title: Binary 2s Compliment Applied Twice Gives Original - How?
At the moment the maths behind binary 2s compliment seems like voodoo to me.

If I take 0011 (+3) and "flip and add 1", I get 1101 (-3)

If I apply the same process to 1101, ("flip and add 1"), I get back to the original positive value.

How is this so?

# Answer
> 3 votes
First, if we wouldn't get the same number after negating it twice, it wouldn't make much sense, right?

So we just need to prove that the "complement and add 1" has indeed the effect of negation, i.e., taking $x$ into $-x$ (and thus, $-x$ to $x$). (well, maybe except for an edge case I will mention below.)

A signed number of $n$ bits, $b\_{n-1}, \ldots, b\_1,b\_0$ where each $b\_i\in\\{0,1\\}$, is to be interpreted in the following way: the $i$-th bit amount $2^i$ **except** for the last bit (MSB). The MSB $b\_{n-1}$ is what makes the number negative, and can be seen as having the value $-2^{n-1}$.

> Sanity check.
> 4 bits. The number 5 is 0101 = 2^2+ 2^0 = 4+1. The number -5 is 1011 = -2^{3}+ 2^1+2^0 = -8+2+1 = -5.

With this in mind, given $x = -2^{n-1}b\_{n-1} + \sum\_{i=0}^{n-2}2^ib\_i$ if we complement each bit ($b\_i \to (1-b\_i)$) we will get $$\begin{align}NOT(x) &= -2^{n-1}(1-b\_{n-1}) + \sum\_{i=0}^{n-2}2^i(1-b\_i) \\ & = -2^{n-1} + \sum\_{i=0}^{n-2}2^i - \[-2^{n-1}b\_{n-1} + \sum\_{i=0}^{n-2}2^ib\_i\] \\ &= -1 -x \end{align}$$ therefore, $NOT(x)+1$ equals $-x$.

Note the edge case(s).If $x=0$ then negating it should give 0. Yet complementing each bit gives $111111 \ne 0$ and after +1 we will get back 0 (ignoring the carry). The other edge case is the maximal negative number $1000$ for 4-bit numbers. If we negate it we get $0111$ after complementing and $1000$ after adding 1 to the complemented number. In this case (and this case only) the 2-complement system "doesn't work" and gives that the negation of $x$ is $x$.

# Answer
> 3 votes
If we look at the numbers in an unsigned way, flipping a binary number $x$ on $n+1$ bits is computing $(2^{n+1} -1) - x = M - x$.

Proof for that: $x = \sum\_0^n b\_i2^i$. $x$ flipped : $\sum\_0^n (1-b\_i)2^i = \sum\_0^n 2^i -\sum\_0^n b\_i2^i = (2^{n+1} - 1) - x$

Therefore, flip and add one : $y = (M - x) + 1$

Again : $z = (M - y) +1 = (M - ((M - x) + 1)) + 1$
$z = (M - (M - x) - 1) + 1$
$z = M - M + x - 1 + 1$
$z = x$

# Answer
> 3 votes
The other answers have given rigorous mathematical answers, so I'll try to give a more intuitive way to understand 2's complement. I'll use 4-bit numbers like the original example.

First principle: for a 4-bit number n, 1111 - n is the same as flipping the bits of n. If you try a few examples, hopefully this is obvious.

Second principle: since we ignore carries out of our 4-bit number, 10000 and 0000 are the same.

Using the first principle, flipping bits and adding 1 is the same as (1111 - n) + 1. Rearranging, this is (1111 + 1) - n, or 10000 - n. By the second principle, this is just 0 - n which is the negation of n.

This demonstrates that "flip and add 1" negates a number. Negating a number twice yields the original number, so doing "flip and add 1" twice also yields the original number.

# Answer
> 2 votes
This might not be a formal answer but give you a idea what happens when you do 2's complement. Take any binary number and do the following:

* Traverse binary bits from right to left
* Find the first 1 bit
* Reverse every bit after first 1

Source for shortcut method

This is shortcut method to get 2's complement of a number Example:

Binary number= 01000100

2's complement= 10111100 (You can verify the answer and this shortcut always works)

You can see we started from right, copied bits until a 1 is reached, then flip the rest. So this means for our example, last 3 bits wont be flipped and rest will be flipped. If we again apply 2's complement on this number, last 3 bit wont be flipped and rest will be.

i.e: Original Number = 01000100

2's Complement = 10111100

2's complement of 10111100 = 01000100 (original number obtained)

So you can imagine 2's complement flips few bits and always leaves few bits at the Left End. This is why 2's complement work because we flip only specific bits every time. If you don't understand any part please comment

---
Tags: binary, numeral-representations
---


# Question
Title: Is there an algorithm to achieve optimal compression in a "streamed" manner, assuming equal probability of each possibility?
(Sorry for the question title; edits are welcome.)

Let's say that you have a set of data made of repeating units, consisting of a value with $2$ possibilities, a value with $3$ possibilities, $5$ possibilities, $4$ possibilities, repeat. The total number of possibilities per unit is $2\times3\times5\times4=120\text{ possibilities}$. Assuming that these are all equally probable, that's $\log\_2120\approx6.9\text{ bits}$. This means that the minimum space required to represent $1$ unit is $1\text{ Byte}$, but the minimum space required to represent $1000$ units is $864\text{B}$.

The naïve way of producing this compression would be to put them all into a base-120 number, then convert this to binary. However, this requires having access to *all of the data* at once in order to decompress it. There must\[citation needed\] be some algorithm that can take in a stream of compressed data, output a stream of decompressed data, and only use finite memory, but I can't find one.

Please describe and explain such an algorithm, if one exists.

# Answer
> However, this requires having access to all of the data at once in order to decompress it.

Not true. The trick is to compress *backwards*, from the last symbol, to the first. You do need all the data at once to *compress* though.

However, what you are looking for can be done with *arithmetic coding*, without even needing access to all of the data at once during compression.
> 2 votes

---
Tags: algorithms, data-compression, entropy
---


# Question
Title: Construct PDA for ${ \{0^m1^n0^{2n} | n>0\}}$
I have to construct PDA for ${ \\{0^m1^n0^{2n} | n\>0\\}}$

So my idea is to (informally) not pushing anything into the stack while having 0s at first, then when automata start accepting 1s it should push X onto the stack twice on every 1 and then when start accepting 0s it should pop X once every time until stack will be empty.

Is my understanding correct? If not, how should I proceed?

# Answer
Yes, your understanding is correct. You may need a bit more mechanism to ensure there is at least one 1 after the initial 0's.
> 1 votes

---
Tags: pushdown-automata
---


# Question
Title: The complexity of the reachability-coreachability analysis of a finite state machine
Let $A = \\{\Sigma,Q,\delta,q\_{0}, Q\_{m}\\}$ be a finite state machine (FSM). A state $q \in Q$ is reachable if there exists a string $s \in \Sigma^{\*}$ such that $\delta(q\_{0},s) = q$. The state $q$ is coreachable if there exists a string $s$ such that $\delta(q,s) \in Q\_{m}$.

I'm wondering what is the computational complexity of the reachability-coreachability analysis of a FSM, as a function of $|Q|=n$. In particular, the input is a FSM $A$, and I'd like the algorithm to output a list of all states that are reachable, and a list of all states that are coreachable. What is the worst-case asymptotic complexity of this function, as a function of $n$?

# Answer
> 1 votes
Since the nature of the OP's question relates to discrete-event systems (as he/she indicated in one of the comments), the argument to derive the complexity can be different compared to what Apass.Jack proposed, as follows.

Given $n = |Q|$, $m = |Q\_{m}|$, and $k = |\delta|$,

Reachability test shall be applied to every state in $Q\setminus\\{Q\_{m}\dot{\cup}\\{q\_{0}\\}\\}$ since the initial state does not need to be reachable, and the reachability of marked states are taken into account by coreachability. So, one has to check the reachability of $n-m-1$ states. Furthermore, coreachability test is only meaningful to $Q\_{m}$, and we have to examine it $m$ times. In the worst case, one has to traverse the whole DFA to check (co)reacahbility. Thus, according to the complexity of BFS/DFS, which is, $O(|Q|+|\delta|) = O(n+k)$, one reads

$O((n+k)(n-m-1)) + O((n+k)m) = O((n+k)(n-1)) = O(n^2 + kn -n -k)$.

$n$ and $k$ are negligible since they are much less than $n^2$ and $kn$ yielding

$O(n^2+kn)$

# Answer
> 2 votes
Let $m\ge1$ be the size of the alphabet $\Sigma$.

---

Let us restrict our attention to the two most common models of finite state machines (FSM), deterministic finite automatons (DFA) and non-deterministic finite automatons (NFA). We know that FSM corresponds naturally to the directed multi-graph as explained by Wikipedia entry on state diagram.

A $n$-state $DFA$ $D=(Q,\Sigma,\delta,q\_0,F)$ corresponds a directed multi-graph $G$, whose nodes are also $Q$ and all of whose nodes have outdegree $m$. Whenever we mention some $q\in Q$, it will be clear whether we mean the state $q$ in $D$ or the node $q$ in $G$. It takes $O(mn)$ time to convert $D$ to $G$.

* The problem of determining all reachable states from state $q\_0$ in $D$ corresponds to the problem of determining all reachable nodes from node $q\_0$ in $G$. If we use the classic breadth first traversal starting from node $q\_0$ to solve the later problem, the worst case happens when we have to go through all arcs in $G$, which is $\Theta(mn)$ time-complexity. In fact, for any algorithm to determine the set of all reachable nodes, all edges must be checked.
* The problem of determining all co-reachable states in $D$ corresponds to the problem of determining all reachable nodes from $q'$ in graph $G'$, where $G'$ is $G$ with all edges reversed and with one extra node $q'$ that is connected to all node $q\_i\in F$. The conversion from $G$ to $G'$ takes $O(mn+n) = O(mn)$ time. If we use the classic breadth first traversal starting from node $q'$ to solve the later problem of all reachable nodes, the worst case happens when we have to go through all arcs in $G'$, which is $\Theta(m(n+1)=\Theta(mn)$ time-complexity. In fact, it is easy to see that asymptotically, solving the problem of co-reachability has the same worst-case time-complexity as solving the problem of reachability.

To summarize, the worse case to determine the reachability or co-reachability of a $n$-state DFA takes $\Theta(mn)$ time.

---

In this section, we will explain the exact meaning of the statement "all edges must be checked" for the case of reachable states.

(**All edges by adversary**) Let $G$ be a multi-graph $G$ of $n$ nodes and a start node $q\_0$. Each node $q$ has exactly $m$ outgoing edges $\\{q\_\sigma\mid \sigma\in\Sigma \\}$. The only way for us to know the other endpoint of $q\_\sigma$ is to inquire from a truthful smart adversary $A$, who can config the other endpoint on the fly. Each inquiry must be "which node is the endpoint of $q\_\sigma$ other than $q$?" for some $v$ and $\sigma$. The minimal number of inquiries needed to determine the set of reachable nodes from $q\_0$ is $mn$.

Proof. Let $Q=\\{q\_0, q\_1, \cdots, q\_{n-1}\\}$.

Here is $A$'s strategy to reply to the inquiry. Initialize $n$ empty set $S\_q$, $q\in Q$. For an inquiry about $q\_\sigma$ with $q=q\_i$, there are five cases.

* if $i\lt n-2$ and $\\#S\_q\lt m-1$, reply that $q\_\sigma$ is the loop from $q$ to $q$. Add $\sigma$ to $S\_q$.
* if $i\lt n-2$ and $\\#S\_q= m-1$, reply that $q\_\sigma= (q,q\_{i+1})$. Add $\sigma$ to $S\_q$.
* if $i\ge n-2$ and $\\#S\_{q\_{n-2}} + \\#S\_{q\_{n-1}}\lt 2m-1$, reply that $q\_\sigma$ is the loop from $q$ to $q$. Add $\sigma$ to $S\_q$.
* if $i\ge n-2$ and $\\#S\_{q\_{n-2}} + \\#S\_{q\_{n-1}}= 2m-1$, reply $q\_\sigma=(q\_{n-2}, q\_{n-1})$ when $q=q\_{n-2}$ and reply $q\_\sigma=(q\_{n-1}, q\_0)$ when $q=q\_{n-1}$. Add $\sigma$ to $S\_q$.
* if $\\#S\_\sigma= m$, the inquiry must have been done before and, hence, reply the same as before.

I will leave the rest of the proof as an exercise.

---

**Exercise 1**. Finish the proof of "all edges by adversary". Show that $A$'s strategy is consistent in the sense that there is one such $G$ that all replies of $A$ are true. Furthermore, after $mn-1$ inquires, we cannot determine whether $q\_{n-1}$ is reachable from $q\_0$ or not.

Interested readers can do the following exercise that deals with NFA.

**Exercise 2.** the worse case to determine the reachability or co-reachability of a $n$-state NFA takes $\Theta(mn^2)$ time.

---
Tags: complexity-theory, finite-automata, graph-traversal
---


# Question
Title: How to prove that a problem is undecidable by using the Halting problem?
I cannot understand how to reduce the halting problem to a property to show that is undecidable.

For example, I have this property of a Turing Machine and I have to prove if it's recursive or not:

*"M eventually enters the fifth state in its rule list when executed on an empty tape"*

How can I do it? Do I have to reduce it to a halting problem or vice-versa?

Thanks in advance.

# Answer
> 1 votes
When you reduce problem A to problem B, you show that B is *at least as hard* as A. (It's sort of like a proof by contradiction: if B were any easier, then A would become just as easy.) And undecidability is about as hard as you can get, in computer science.

So what you want to do here is:

* Assume you have an oracle for the "fifth state problem"
* Show that you can solve the Halting Problem with this oracle
    + It doesn't matter how long it takes or how many times you call the oracle, for this problem (since all you care about is decidability)
* The Halting Problem is undecidable
* Therefore, the "fifth state problem" is also undecidable

Here are a few hints to get you started:

* You can reorder the states in a Turing machine without really changing anything important
* If a TM has less than five states, you can add new "dummy" states that are never used, without really changing anything important
* A TM never needs more than one halting state
* The question "does this TM halt on empty input?" is a variant of the Halting Problem that is also undecidable

---
Tags: turing-machines, computability, reductions, undecidability, halting-problem
---


# Question
Title: Can Non-Linear Grammars generate Regular Language?
I stumbled upon the following non-linear grammar

$$S \to AB$$ $$A\to aaA\mid \epsilon$$ $$B \to Bb\mid \epsilon$$

and the language generated by this non-linear grammar is {a^2nb^m : n ≥ 0, m ≥ 0} which looks to be regular. I was successful in drawing a DFA for this language.

Thus far, I have studied that Left Linear and Right Linear grammars classify as Regular Grammar and generate Regular Languages. I know there are certain Linear Grammars that can be converted to corresponding Left Linear or Right Linear equivalent forms. Similarly, I am guessing, we can write a Right or Left Linear grammar in a Non-Linear fashion and get the same regular language which is what is happening here.

Thus, what I understand is that Left Linear or Right Linear Grammars always generate Regular languages but a Non-Linear grammar may or may not generate a regular language. Is that the correct way to put it? Are there any gaps in my understanding?

Wkipedia states "an example of a linear, non-regular language is {a^nb^n}". Can I then say that above language is an example of non-linear, regular language? That sounds and probably is wrong.

# Answer
> 2 votes
You are confused a bit I believe by using the terms grammar and language somewhat interchangeably.

A grammar is a set of production rules. A language is a set of words. A language is described, or *generated* by a grammar.

They are not the same and you should be careful at all times to see which is which.

There are a lot of terms such as "context-free", "linear", "regular", etc, that are *direct properties of grammars*. That is their original definition.

These terms when applied to a *language*, has a different, indirect meaning. When I say that a language L is X for those above properties, I mean that there *exists a grammar* with property X that generates L.

Now this can get confusing. Let's take your original grammar. It itself is not linear or regular, but the language it generates is both. Why? Because I can construct another grammar for it which generates the same language, which has those properties:

$$S \to A$$ $$A \to aaA \mid B$$ $$B \to bB \mid \epsilon$$

If you want to be even stricter I could make it a strictly right-linear grammar without epsilon productions (other than the whole language being nullable):

$$S \to aA\_2 \mid bB \mid \epsilon$$ $$A\_1 \to a A\_2$$ $$A\_2 \to aA\_1 \mid aB \mid a$$ $$B \to bB \mid b$$

Finally, we have that for language classification we have (among others):

$$\text{Left-linear} = \text{Right-linear} =\text{Regular} \in \text{Linear} \in \text{Context-Free}$$

> Can I then say that above language is an example of non-linear, regular language?

That is indeed wrong, because the language above *is* linear. You are confused because you are looking at the grammar, which *isn't* linear. Just because a certain grammar for a language isn't property X doesn't mean that there doesn't exist another grammar that generates the same language that has property X.

That's why it's generally hard to prove that a *language* doesn't have some property X. You need to show that every possible grammar you can construct for that language doesn't have that property, because a single one is enough to give that property to the language.

---
Tags: regular-languages, context-free
---


# Question
Title: Can the Dijkstra algorithm work with a negative arc?
When there is no negative circle in the graph? And can Dijkstra not work even if there is a negative arc that does not create a negative cycle?

# Answer
The most common implementation of Dijkstra's algorithm (for example, the one you find on Wikipedia), will *not* work correctly in this case, because once a node is extracted from the priority queue, its label (distance from the source) will never be revised. Consider the following example: there are four nodes $a,b,c,d$ (node $a$ is the source), and four arcs: $a \rightarrow b$ with cost 10, $a \rightarrow c$ with cost 4, $b \rightarrow c$ with cost -8, and $c\rightarrow d$ with cost 1. With the classic implementation, Dijkstra's algorithm will extract node $c$ from the queue before node $b$, and hence will report 5 as the length of the shortest path from $a$ to $d$, while the correct answer is 3.

There is, however, a conceptually simple modification that guarantees correctness of the algorithm on any instance with negative weights but no negative cycles. You simply put back a node in the priority queue after you discovered a shorter path to it. In the above example, after the node $b$ is expanded we discover a shorter path to $c$, and put $c$ back in the queue. Expanding $c$ one more time allows to find the correct path to $d$.

Note however that, while correct, the running time of this "revised Dijsktra" is no longer the same as the original implementation, because now we may have to expand the same node multiple times. In fact, the running time can be exponential in the number of nodes.
> 3 votes

---
Tags: algorithms, graphs
---


# Question
Title: How do I count the exact number of executed commands for a MIPS program?
I want to know what the best way is to count the number of executed commands for a given MIPS program. Let's say we're given a simple for loop that counts from $0$ to $100$. For this I would write the following MIPS code:

```
li $s1, 0
li $t0, 100

for_loop:
    addi $s1, $s1, 1
    beq $s1, $t0, exit
    j for_loop

exit:

```

Since I have $2$ `li`'s before the loop, that would be $+2$ commands and then within the for\_loop, the 99 loops pass for `addi`, `beq` and `j` which makes it $99⋅3$ and then $2$ for `addi` and `beq`. That makes it a total of $301$ executed commands. Is my answer correct? If not then what is the correct procedure to count the number of executed commands and if in the future I come across a more complex example, then how should I deal with it?

# Answer
> 2 votes
There are two ways: You use a simulator and count the actual number of instructions (or do it manually), which of course only works for fixed input like your case here. Or you use mathematics to calculate the number of instructions, just as you did.

In general, mathematical analysis ranges from easy to hard to impossible for humans, so there is no general method.

Sometimes you’re lucky to get a result like “about 2.25 n^2”, or “$\Theta (n^2)$ or similar. How do you deal with it? You do your best.

---
Tags: algorithms, computer-architecture, programming-languages
---


# Question
Title: Sublinear Homomorphism Property Testing Counter Example
This is a homework question, so I'm not looking for answers, just general guidance.

I'm looking at a Sublinear Algorithms survey where (Group) Homomorphism property testing is discussed. The case of homomorphisms from $\left(\mathbb{Z}\_{n}, +\right)$ to $\left(\mathbb{Z}\_{n}, +\right)$ (where + is the modulo addition) in particular.

Since $$f:\mathbb{Z}\_{n}\to\mathbb{Z}\_{n}\ is\ a\ homomorphism\iff\forall x\in\mathbb{Z}\_{n}:\ f\left(x+1\right)\equiv\_{n}f\left(x\right)+f\left(1\right)$$ (I've managed to prove that), it is suggested to property test $f\left(x+1\right)\equiv\_{n}f\left(x\right)+f\left(1\right)$.

To counter that suggestion it is said that for a sufficiently large $n$, $$f:\begin{array}{lll} \mathbb{Z}\_{n} & \to & \mathbb{Z}\_{n}\\ x & \mapsto & x\ \left(mod\ \left\lceil \sqrt{n}\right\rceil \right) \end{array}$$ maintains $f\left(x+1\right)\equiv\_{n}f\left(x\right)+f\left(1\right)$ for $1-\frac{1}{\sqrt{n}}$ fraction of the $x\in\mathbb{Z}\_{n}$ (managed to prove that), but that $f$ is $1-\frac{1}{\sqrt{n}}$-far from any homomorphism (where $\epsilon$-far means that in order to get a homomorphism out of $f$ we have to change at least $\epsilon n$ outputs of $f$).

We're asked to show a counter example of a function that passes the test for $1-o\left(1\right)$ fraction of the inputs, but is $\frac{1}{100}$-far from homomorphisms, which is a bit easier.

So I wanted to show $f$ as my example. I managed to prove what I wrote so far, but I'm still trying to prove $f$ is $1-\frac{1}{\sqrt{n}}$-far.

What I've tried:

Assume by contradiction that $\delta\left(f\right)\<n-\sqrt{n}$ (where $\delta\left(f\right)$ is the distance from homomorphisms), that is there exists $h$, an homomorphism, with less than $n-\sqrt{n}$ different (compared to $f$) outputs.

I've divided into 2 cases.

First case is $h\left(1\right)=f\left(1\right)$ which means $h\left(1\right)=1$. It is easy to get a contradiction this way, since then there exists $x\>\sqrt{n}$ such that $h\left(x\right)=f\left(x\right)$ (otherwise, contradiction to $\delta\left(f\right)\<n-\sqrt{n}$). Since $h$ is a homomorphism, we get $$h\left(x\right)=\underset{i=1}{\overset{x}{\sum}}h\left(1\right)=\underset{i=1}{\overset{x}{\sum}}1=x\neq f\left(x\right)$$

Now the other case where $h\left(1\right)\neq f\left(1\right)$ is where I'm stuck. It's hard for me to get intuition since apparently this is only true for large $n$'s, which makes it hard to look at basic examples. I'm not even sure dividing to these cases is the best approach, and would love some help. Thanks!

Edit:

As requested, a link to the survey by Ronitt Rubinfeld. Only managed to find it in ps format.

# Answer
> 1 votes
Thanks to the help in the comments I was able to unfixate and find an answer to the question. I prove $\delta\left(f\right)\geq\frac{1}{2}-\frac{1}{2\sqrt{n}}$.

Let $h:\mathbb{Z}\_{n}\to\mathbb{Z}\_{n}$ be an homomorphism.

• If $h\left(1\right)=f\left(1\right)$ then $h\left(1\right)=1$ and h is the identity function, since $h\left(0\right)=0$ and $$h\left(x+1\right)=h\left(x\right)+h\left(1\right)=h\left(x\right)+1$$ due to homomorphisms definition and properties. We get $\delta\left(f,h\right)=1-\frac{1}{\sqrt{n}}\geq\frac{1}{2}-\frac{1}{2\sqrt{n}}$ (since they disagree on $n-\sqrt{n}$ values).

• Otherwise, $h\left(1\right)\neq f\left(1\right)$, that is $h\left(1\right)\neq1$. Assume by contradiction that exists $x\in\mathbb{Z}\_{n}$ such that $h\left(x+1\right)=h\left(x\right)+1$, but due to homomorphisms definition we get $$h\left(x+1\right)=h\left(x\right)+h\left(1\right)=h\left(x\right)+1$$ which is a contradiction to $h\left(1\right)\neq1$. Since our function $f$ maintains that $$h\left(x+1\right)=h\left(x\right)+1$$ for $x\in\mathbb{Z}\_{n}\backslash\left\\{ q\sqrt{n}|0\leq q\leq\sqrt{n}-1\right\\}$ , which means $n-\sqrt{n}$ “bad” pairs of $x$ and $x+1$. This means that in order to get any homomorphism, including $h$, we have to change at least one value for each pair, which means at least $\frac{\sqrt{n}-1}{2}$ values changed for each interval $\left\[q\sqrt{n},\left(q+1\right)\sqrt{n}\right)\cap\mathbb{Z}\_{n}$ (where $0\leq q\leq\sqrt{n}-1$), otherwise due to to the pigeonhole principle we have two consecutive values that are unchanged which is again a contradiction since then $h\left(x+1\right)=h\left(x\right)+1$. So in total we have at least $$\sqrt{n}\frac{\sqrt{n}-1}{2}=\frac{n-\sqrt{n}}{2}$$ values changed, which means $$\delta\left(f,h\right)\geq\frac{1}{2}-\frac{1}{2\sqrt{n}}$$

---
Tags: algorithms, randomized-algorithms, randomness, linear-algebra
---


# Question
Title: Can You List the Names of Some Algorithms For Determining the Intersection of Two Context Free Grammars?
Suppose we have two sets of strings XS and YS such that set XS is described by grammar GX and YS is described by grammar GY.

We want an algorithm which accepts GX and Gy as inputs. The algorithm will return `true` if the intersection of sets XS and YS is non-empty and will return `false` otherwise. We do not need to know exactly what the intersection is. It is possible that the intersection set is massive, so returning a container of all elements is unreasonable. Describing the intersection as a grammar is okay as long as it's apparent whether the grammar actually describes a non-empty set of string or not.

Just the name of the algorithm is fine if a Google search using that name will bring up the result. If the algorithm is obscure, additional information would be helpful.

# Answer
There is no such algorithm. Start by googling undecidability. The problem itself is called "language intersection/disjointness".
> 2 votes

---
Tags: algorithms, context-free, decision-problem, sets
---


title: How to "logically" solve boolean logic

text:
# Question
Title: How to "logically" solve boolean logic
I came across of one excellent book Elements of Computing Systems and in chapter 1 we need to implement the "primitive" logic gates (for example: Not, And, Or, Xor, Mux, etc) based on a Nand gate.

Up to now I'm just solving these boolean implementations by guessing all required gates which is so much time consuming. I'm not able to find any logic in the implementation.

I'm wondering if you have any method, tipp how to solve this.

Here is an example of the Mux requirements presented in the book

Mux requirement image example Mux requirement image example continue

# Answer
> 1 votes
The nand gate is defined as follows --when and, not gates are available--

```
a nand b  ≡  ¬(a ∧ b)

```

Hence, since conjunction is idempotent, $a ∧ a ≡ a$, we have the not gate:

```
a nand a  ≡  ¬ a

```

Since negation is its own inverse, $¬ ¬ x ≡ x$, we have the and gate:

```
  a ∧ b
≡ ¬ ¬ (a ∧ b)                   -- double negation
≡ (¬ (a ∧ b)) nand (¬ (a ∧ b))  -- not in terms of nand
≡ (a nand b) nand (a nand b)    -- using ‘definition’ of nand

```

Finally, the or gate:

```
   a ∨ b
≡  ¬¬ a ∨ ¬¬ b                 -- double negation
≡  ¬ (¬ a ∧ ¬ b)               -- De morgan's law
≡  (¬ a) nand (¬ b)            --  using ‘definition’ of nand
≡  (a nand a) nand (b nand b)  -- not in terms of nand

```

Neato!

---
Tags: logic, discrete-mathematics, boolean-algebra
---


# Question
Title: Can a list with $\mathcal{O}(1)$ access have an insertion complexity better than $\mathcal{O}(n)$?
It seems intuitive that there's no list data structure which has $\mathcal{O}(1)$ worst case time complexity for random access and a worst case complexity better than $\mathcal{O}(n)$ for insertion: if insertion is allowed to affect only a *small part* of the list, then there's no way for it to always keep the *entire list* in a structure that allows for constant time element access.

Is there any proof (or counterexample) of this?

# Answer
> 0 votes
Yes, you can have both as fast as possible random access and faster-than-full-rebuild insertion time.

I assume you know how dynamically growing arrays work. Also, I assume you know how to make them work in $O(1)$ worst-case. These techniques allow us to focus on the problem for lists of limited size only.

Let $n$ be the maximal size (capacity) of the list. Let’s divide the list into $O(\sqrt{n})$ blocks of equal size $B$ (which is $O(\sqrt{n})$ too). Let also $b\_j$ denote a cyclic shift of the $j$-th block.

When you need to **access** $i$-th element of the list, you calculate its position as follows in $O(1)$:

$$f(i) = (b\_j + i \mod B) + B \times j$$

where $j = \lfloor \frac{i}{B} \rfloor$.

When you need to **insert** something into $i$-th position, you first make a cyclic shift of everything from $j$-th block to the end:

1. Decrement all $b$ values starting from $j$.
2. Swap the elements on the boundaries of consequtive blocks, so that every element is in its right place.
3. Then you fix $j$-th block by rebuilding it from scratch.

This gives you $O(\sqrt{n})$ insertion complexity.

# Answer
> -1 votes
As accessing to an element is in $O(1)$, it would be something like an array. And, if this assumption is true, your discussion would be near the concept of "Dynamic Array". It's insertion to the array is $O(1)$ and amortized **cost of $n$ insertion** to the data structure is $O(n)$. It might be helpful for what you want to reach.

---
Tags: time-complexity, lists
---


# Question
Title: Real world applications of first order logic
I study an AI course and we done some lectures about first order logic and the first thing that I was thinking is, what are the real world applications of first order logic and generally logical languages , especially in AI ?

# Answer
If you want a specific example, IBM Watson should qualify. Check the links for details on how they use Prolog. I'd say that Prolog made a huge hype in its day, and most real today's system are based on different principles rather than "first-order logic programming" in narrow sense. However, there is definitely a niche for this approach. We live in the age of other hypes, that's it.
> 1 votes

---
Tags: artificial-intelligence, first-order-logic
---


# Question
Title: Increasing the weights of all edges in an undirected graph makes a minimum cut still minimum
We have an undirected graph, with a weight function and a minimum cut. If you raise the weights of all the edges by one, the minimum cut remains minimal even with the new weights.

I know this is refutation, but I could not find a good example of refutation. I would be happy if you would help me.

# Answer
> 2 votes
Consider the following graph. The min-cut is $\[s\]\[a,b,c,d,t\]$ with value 3. After the weights of all edges are increased by 1, the min-cut becomes $\[s,a,b,c,d\]\[t\]$ with value 5.

It does not matter whether you are considering cuts with terminals or without terminals (if with terminals, the terminals are $s$ and $t$).

---
Tags: graphs, minimum-cuts
---


# Question
Title: Can the complement of an unrecognizable language be a recognizable language?
I know that complement of a language that is recursively enumerable, but not recursive, is definitely not recursively enumerable (or unrecognizable). So my question is what can be said about the complement of an unrecognizable language?

# Answer
> 1 votes
Sure: the Halting language (sometimes called $K$) is recursively enumerable whereas its complement ($\overline{K}$) is famously *not*.

Generally speaking, the existence of such languages follows from the implication you state -- the complement of enumerable yet undecidable languages can not be enumerable -- by the existence of precisely enumerable yet undecidable languages.

That said, there are also non-enumerable languages whose complement isn't either.

---
Tags: computability, semi-decidability
---


# Question
Title: Delete a node with 2 children in a binary search tree
Recently in class we learned how to delete a node from a binary search tree. Since in a binary search tree, each node can have at most 2 nodes, there are 3 cases of deletion.

Case 1: The node is a leaf node. In that case you can simply delete the pointer to that node and free up the memory for that.

Case 2: The node has one child. In that case, you can connect the parent and child of that node and delete the pointer to and from the node you want to delete.

Case 3: The node has 2 children. Here is where I'm having a bit of a problem. Let's assume we have the following example.

I want to delete the node "4". To do this, I go to the largest integer node on its right side, i.e. "5" and swap their values. So 4 becomes 5 and 5 becomes 5. The I can simply delete the node "5" and I'll be done. Is this approach correct or am I missing anything?

# Answer
> 1 votes
Your approach works in your example, but not in general. For example, if the node with key 5 also has a left child with key 4.5, it will not be correct because the resulting tree is not a binary search tree anymore.

You have to replace the node to be deleted (4) not with its right child (5), but with its successor in the key ordering, which is the least-valued node in its right sub-tree (in your example, that is indeed 5, but in my example it would be 4.5, not 5).

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


# Question
Title: Why can't a left-recursive, non-deterministic, or ambiguous grammar be LL(1)?
I've learned from several sources that an LL(1) grammar is:

1. unambiguous,
2. not left-recursive,
3. and, deterministic (left-factorized).

What I can't fully understand is why the above is true for any LL(1) grammar. I know the LL(1) parsing table will have multiple entries at some cells, but what I really want to get is a formal and general (not with an example) proof to the following proposition(s):

A left-recursive (1), non-deterministic (2), or ambiguous (3) grammar is not LL(1).

# Answer
> 1 votes
I have done some more research, and I think I've found a solution for the 1st and 2nd questions, as for the 3rd one, I found an existing solution on StackOverflow for it, the proof attempts are written below:

We start by writing the three rules of the definition of an LL(1) grammar:

For every production `A -> α | β` with `α ≠ β`:

1. `FIRST(α) ∩ FIRST(β) = Ø`.
2. If `β =>* ε` then `FIRST(α) ∩ FOLLOW(A) = Ø` (also, if `α =>* ε` then `FIRST(β) ∩ FOLLOW(A) = Ø`).
3. Including `ε` in rule (1) implies that at most one of `α` and `β` can derive `ε`.

**Proposition 1:** *A non-factored grammar is not LL(1).*

**Proof:**

If a grammar G is non-factored then there exists a production in G of the form:

```
A -> ωα1 | ωα2 | ... | ωαn

```

(where `αi` is the `i-th α`, not the symbols `α` and `i`), with `α1 ≠ α2 ≠ ... ≠ αn`. We can then easily show that:

```
∩(i=1,..,n) FIRST(ωαi) ≠ Ø

```

which contradicts rule (1) of the definition, thus, a non-factored grammar is not LL(1). ∎

**Proposition 2:** *A left-recursive grammar is not LL(1).*

**Proof:**

If a grammar is left-recursive then there exists a production in G of the form:

```
S -> Sα | β

```

Three cases arise here:

1. If `FIRST(β) ≠ {ε}` then:

`FIRST(β) ⊆ FIRST(S)`

`=>  FIRST(β) ∩ FIRST(Sα) ≠ Ø`

which contradicts rule (1) of the definition.
2. If `FIRST(β) = {ε}` then:

2.1. If `ε ∈ FIRST(α)` then:

`ε ∈ FIRST(Sα)`

which contradicts rule (3) of the definition.

2.2. If `ε ∉ FIRST(α)` then:

`FIRST(α) ⊆ FIRST(S)` (because `β =>* ε`)

`=>  FIRST(α) ⊆ FIRST(Sα) ........ (I)`

we also know that:

`FIRST(α) ⊆ FOLLOW(S) ........ (II)`

by `(I)` and `(II)`, we have:

`FIRST(Sα) ∩ FOLLOW(S) ≠ Ø`

and since `β =>* ε`, this contradicts rule (2) of the definition.

In every case we arrive at a contradiction, hence, a left-recursive grammar is not LL(1). ∎

**Proposition 3:** *An ambiguous grammar is not LL(1).*

**Proof:**

While the above proofs are mine, this one is not, it's by Kevin A. Naudé which I got from his answer that is linked below:

https://stackoverflow.com/a/18969767/6275103

---
Tags: formal-languages, formal-grammars
---


# Question
Title: find all paths from source to destinations and then calculate the path with minimum cost
I am trying to solve one problem. Please refer complete problem statement before proceeding.

> You are given a road network, with N cities and M bi-directional roads. Each road has some positive amount of tax associated to it,meaning if there is a road connecting cities A and B with tax C, you will need to pay C rupees to the government every time when you use this road.
>
> but you have a wildcard which can be used at most K times and when you use wildcard while using a road, you do not need to pay tax associated with the road.
>
> You are planning to visit one city this weekend, due to limited budged you want to estimate minimum passible cost from you home-city to every other city, so that you can choose the destination according to the budget, your home-city is a city numbered with 1.

For solving above problem I am Following this approach. Step 1) Calculate all the path between vertices u,v. Step 2) For a Path p=\[i-j-k-l\] do following

```
   for(int i=0;i<k;i++){
           int weight=findEdgeWithMaxWeight(p);
     cost of path p=cost of path-weight;
    }

```

I am repeating this step2 for all the paths for u,v and at last I am choosing the path with minimum weight. As my answer.

Consider following diagram to visualize my approach.

But problem with above approach is that I am have to calulate all the path between u,v to get the answer. Is there any way to get the optimal path with out calculating all the paths?

Edit: Hope Problem is bit clearer now.

# Answer
> 1 votes
One way to solve this is a Dijkstra variant with the following DP-Relaxation:
The distance array will be 2-dimensional array for which $Dist\[i\]\[j\]$ is the shortest path from the source to the city $i$ using $j$ wildcards.
When processing a vertex $i$, for an incident edge $e\\{i, j\\}$ with cost $c$ we update as following:(for all values of k)
$Dist\[j\]\[k\] = min(Dist\[j\]\[k\], Dist\[i\]\[k\] + C)$
$Dist\[j\]\[k\] = min(Dist\[j\]\[k\], Dist\[i\]\[k-1\])$ The correctness follows from the fact that we are trying all placements of the wildcards and keeping the so-far-optimal.
The runtime is the usual Dijkstra runtime multiplied by the $K$ factor in the relaxation i.e. $O((e+n\log(n))k)$ using Fibonacci Heaps.

---
Tags: algorithms, graphs
---


# Question
Title: Invariant on "Find K Closest Elements" problem
I run across this problem:

Given a sorted array, two integers `k` and `x`, find the `k` closest elements to `x` in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

For example, given `[1,2,3,4,5]`, `k=4`, `x=3`, we should have `[1,2,3,4]`. There is one solution using binary search:

```
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
    int left = 0;
    int right = arr.size() - k;
    while (left < right)
    {
        int mid = left + (right - left) / 2;
        if (x - arr[mid] <= arr[mid+k] - x)
        {
            right = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
    return vector<int>(arr.begin() + left, arr.begin() + left + k);
}

```

I couldn't understand `if (x - arr[mid] <= arr[mid+k] - x)` part and I try to explain this using precondition, invariant, and postcondition like we do with the simple binary search problem. But, I have no clue what's the invariant in this case and how we prove the invariant holds through the loop execution. I also follow the article from topcoder but that doesn't help.

My attempt for the invariant: the index of the first number that is among the k closest values for the given target is in \[left, right\]. However, I cannot fully convince myself this is correct and actually holds during the loop.

If this question belongs to stackoverflow, let me know and I'll post it there instead.

Thanks in advance.

# Answer
If `x - arr[mid] <= arr[mid+k] - x`, then for any `l` that `l > mid`, we have

```
x - arr[l-1] <= x - a[mid] <= arr[mid+k] - x <= arr[l+k] - x,
arr[l-1] - x <= arr[l+k] - x,

```

which means `|arr[l-1] - x| <= |arr[l+k] - x|`. So for any range `[l, l+k]` where `l > mid`, we can move it to left until `l == mid` while the elements contained are no farther from `x`, therefore it is safe to set `right = mid`.

Otherwise, the proof is similar.
> 1 votes

# Answer
The main idea of the algorithm is that `mid` will indicate the starting point of the subarray of length `k` that we are interested in (this a bit more specific than your correct intuition about this being in the interval `[left,right]`).

Notice that `x - arr[mid] <= arr[mid+k] - x` is equivalent to `x <= (arr[mid] + arr[mid+k])/2`, which in particular implies that `x <= arr[mid+k]`. If `x-arr[mid]` were a negative number, it means that clearly we can move to the left, since `x` is definitely not in `[arr[mid],arr[mid + k]]`. So suppose that `x - arr[mid]` is positive, and suppose for a contradiction that shifting the interval by one to the right gives a better solution: by our conditions and the fact that the array is ordered, we have `arr[mid+k+1]-x >= arr[mid+k]-x >= x-arr[mid]`, which proves that `arr[mid+k+1]` is further from `x` than `arr[mid]` is, a contradiction (notice that we are required to give preference to the smaller elements, so even if the inequalities above were in fact equalities, moving to the right would be a mistake).

This proves that is is safe to set `right=mid`.
> 0 votes

---
Tags: algorithms, algorithm-analysis, binary-search, loop-invariants
---


# Question
Title: How many pairs of brackets are sufficient to make Brainfuck Turing complete?
Brainfuck is a Turing complete programming language that uses only 8 symbols (6 if you ignore I/O).

The two most notable ones that push it to Turing completeness are `[`and `]`, essentially Brainfuck's label and goto.

Normally, programs in Brainfuck use multiple sets of `[]`, but I was wondering exactly how many pairs of these brackets have to be used to make Brainfuck Turing complete?

More simply, what is the least amount of brackets that you'd need to simulate an n-state Turing Machine (Give the number of brackets for 1, 2, and three state Turing Machines)?

**Notes:**

We are assuming an infinite tape and no computational limits.

It is a 2-symbol Turing Machine

# Answer
> 10 votes
This is a further development of @ais523's answer, reducing it to only two sets of brackets, and also using a more compact cell placement based on Golomb ruler theory. ais523 has made a compiler for this construction, as well as this TIO session showing a sample resulting BF program running with debug tracing of the TWM counters.

Like the original, this starts with a program in The Waterfall Model, with some restrictions that don't lose generality:

1. All counters have the same self-reset value $R$; that is, the TWM trigger map $f$ has the property that $f(x,x)=R$ for all $x$.
2. There is a single halting counter $h$.
3. The number $c$ of counters is $(p-1)/2$ for some prime number $p$.

# Golomb ruler

We combine the Erdős–Turán construction with the permutation function of a Welch–Costas array in order to get a Golomb ruler with the necessary properties.

(I'm sure this combined construction cannot be a new idea but we just found and fit together these two pieces from Wikipedia.)

Let $r$ be a primitive root of $p=2c+1$. Define the function

$$g(k)=4ck - ((r^k-1)\bmod(2c+1)), k=0,\ldots,2c-1.$$

1. $g$ is a Golomb ruler of order $2c$. That is, the difference $g(i)-g(j)$ is unique for every pair of distinct numbers $i,j \in \\{0,\ldots,2c-1\\}$.
2. $g(k)\bmod(2c)$ takes on every value $0,\ldots,2c-1$ exactly once.

# Tape structure

For each TWM counter $x\in \\{0,\ldots,c-1\\}$, we assign two BF tape cell positions, a *fallback cell* $u(x)$ and a *value cell* $v(x)$:

$$u(x)=g(k\_1)\<v(x)=g(k\_2)\mbox{ with }u(x)\equiv v(x)\equiv x\pmod c$$

By the second property of $g$ there are exactly two distinct $k\_1,k\_2$ values to choose from.

A fallback cell's content will most of the time be kept at $0$, except when its counter has just been visited, when it will be at $2R$, twice the counter self-reset value. A value cell will be kept at twice the value of the corresponding TWM counter.

All other cells that can be reached by the BF program execution (a finite number) will be kept at odd values, so that they always test as nonzero. After initialization this is automatic because all cell adjustments are by even amounts.

If desired, all cell positions can be shifted rightwards by a constant in order to avoid moving to the left of the initial BF tape position.

# BF program structure

Let $H = v(h)-u(h)$ be the distance between the halting counter's value and fallback cells, and let $N$ be a number large enough that $cN+1 \geq v((x+1)\bmod c) - u(x)$ for all counters $x$. Then the basic BF program structure is

> *initialization* `[` `>`$\times (H+cN+1)$ `[` `<`$\times c$ `]` *adjustments* `<`$\times H$ `]`

## Initialization

The *initialization* phase sets all cells reachable by the program to their initial values, in a state as if the last counter had just been visited and the just active cell was its fallback cell $u(c-1)$:

1. Value cells are initialized to twice the initial content of the corresponding TWM counter, except that counter $0$ is pre-decremented.
2. Fallback cells are set to $0$, except cell $u(c-1)$, which is set to $2R$.
3. All other cells reachable by the program (a finite number) are set to $1$.

Then the tape pointer is moved to position $u(c-1)-H$ (an always non-zero cell) before we reach the program's first `[`.

## Beginning of outer loop

At the beginning of an iteration of the outer loop, the tape pointer will be at either $u(x)-H$ or $v(x)-H$ for a counter $x$.

Let $y=((x+1)\bmod c)$ be the next counter to visit.

The movement `>`$\times (H+cN+1)$ places the tape pointer on a position that is $\equiv y\pmod c$ and not to the left of $v(y)$.

The inner loop `[` `<`$\times c$ `]` now searches leftwards in steps of $c$ for a zero cell. If counter $y$ is zero, then it will stop at the (zero) value cell $v(y)$; otherwise it will find the fallback cell $u(y)$.

Whichever cell is found becomes the new *active* cell.

## Adjustments

The *adjustment* phase adjusts various cells on the tape based on their position relative to the active cell. This section contains only `+-><` commands and so these adjustments happen unconditionally. However, because all counter-related cells are in a Golomb ruler pattern, any adjustments that are not proper for the current active cell will miss all the important cells and adjust some irrelevant cell instead (while keeping it odd).

Separate code must thus be included in the program for each possible required pair of active and adjusted cell, *except* for an active cell's self-adjustment, which, because adjustment is based solely on relative position, must be shared between all of them.

The required adjustments are:

1. Adjust the previous counter's fallback cell $u(x)$ by $-2R$.
2. Adjust the current counter's fallback cell $u(y)$ by $2R$, *except* if the current active cell is $v(h)$ and so we should halt.
3. Adjust the next counter's value cell $v((y+1)\bmod c)$ by $-2$ (decrementing the counter).
4. When the active cell is a value cell $v(y)$ (so the counter $y$ has reached zero), adjust all value cells $v(z)$ by $2f(y,z)$ from the TWM trigger map. $v(y)$ itself becomes adjusted by $2R$.

The first and second adjustments above are made necessary by the fact that all active cells must adjust *themselves* by the same value, which is $2R$ for value cells, and thus also for fallback cells. This requires preparing and cleaning up the fallback cells to ensure they get back to $0$ in both the value and fallback branches.

## End of outer loop

The movement `<`$\times H$ represents that at the end of the adjustment phase, the tape pointer is moved $H$ places to the left of the active cell.

For all active cells *other* than the halting counter's value cell $v(h)$, this is an irrelevant cell, and so odd and non-zero, and the outer loop continues for another iteration.

For $v(h)$, the pointer is instead placed on its corresponding fallback cell $u(h)$, for which we have made an exception above to keep it zero, and so the program exits through the final `]` and halts.

# Answer
> 12 votes
I'm not 100% sure that it's impossible to do this with two sets of brackets. However, if the cells of the BF tape allow unbounded values, three sets of brackets are enough. (For simplicity, I'll also assume that we can move the tape head left past its starting point, although because this construction only uses a finite region of the tape, we could lift that restriction by adding sufficiently many `>` commands at the start of the program.) The construction below requires assuming Artin's conjecture to be able to compile arbitrarily large programs; however, even if Artin's conjecture is false, it will still be possible to show Turing-completeness indirectly via translating an interpreter for a Turing-complete language into BF using the construction below, and running arbitrary programs via giving them as input to that interpreter.

The Turing-complete language that we're compiling into unbounded BF is The Waterfall Model, which is one of the simplest known computational models. For people who don't know it already, it consists of a number of counters (and initial values for them), and a function $f$ from pairs of counters to integers; program execution consists of repeatedly subtracting 1 from every counter, then if any counter $x$ is 0, adding $f(x,y)$ to each counter $y$ (the program is written in such a way that this never happens to multiple counters simultaneously). There's a Turing-completeness proof for this language behind my link. Without loss of generality, we'll assume that all counters have the same self-reset value (i.e. $f(x,x)$ is the same for all $x$); this is a safe assumption because for any specific $x$, adding the same constant to each $f(x,y)$ will not change the behaviour of the program.

Let $p$ be the number of counters; without loss of generality (assuming Artin's conjecture), assume that $p$ has a primitive root 2. Let $q$ be $p(1+s+s^2)$, where $s$ is the lowest power of 2 greater than $p$. Without loss of generality, $2q$ will be less than $2^p$ ($2q$ is bounded polynomially, $2^p$ grows exponentially, so any sufficiently large $p$ will work).

The tape arrangement is as follows: we number each counter with an integer $0 \leq i \< p$ (and without loss of generality, we assume that there's a single halt counter and number it $2$). The value of most counters is stored on tape cell $2^i$, with the exception of counter 0, which is stored on tape cell $2q$. For each odd-numbered tape cell from cell -1 up to and including $2^{p+1}+2p+1$, that tape cell always holds 1, unless it's immediately to the left of a counter, in which case it always holds 0. Even-numbered tape cells that aren't being used as counters have irrelevant values (which might or might not be 0); and odd-numbered tape cells outside the stated range also have irrelevant values. Note that setting the tape into an appropriate initial state requires initialising only finitely many tape elements to constant values, meaning that we can do it with a sequence of `<>+-` instructions (in fact, only `>+` are needed), thus no brackets. At the end of this initialisation, we move the tape pointer to cell -1.

The general shape of our program will look like this:

> *initialisation* `[>>>[` `>`$\times(2^p-1)$ `[` `<`$\times(2p)$ `]>-]` *adjustment* `<<<]`

The initialisation puts the tape into the expected shape and the pointer on cell -1. This is not the cell to the left of a counter (0 is not a power of 2), so it has value 1, and we enter the loop. The loop invariant for this outermost loop is that the tape pointer is (at the start and end of each loop iteration) three cells to the left of a counter; it can be seen that the loop will thus only exit if we're three cells to the left of counter 2 (each other counter has a 1 three cells to its left, as to have a 0 there would imply that two counters' tape positions were 2 cells apart; the only two powers of 2 that differ by 2 are $2^1$ and $2^2$, and $q$'s binary representation changes from strings of $0$s to strings of $1$s or vice versa at least four times and thus cannot be 1 away from a power of 2).

The second loop repeatedly loops over the counters, decrementing them. The loop invariant is that the tape pointer is always pointing to a counter; thus the loop will exit when some counter becomes 0. The decrement is just `-`; the way we get from one counter to the next is more complex. The basic idea is that moving $2^p-1$ spaces to the right from $2^x$ will place us on an odd-numbered cell $2^p+2^x-1$, which is to the right of any counter ($2^p$ is the last counter, $2^x-1$ is positive because $x$ is positive); modulo $2p$, this value is congruent to (by Fermat's Little Theorem) $2^x+1$. The innermost loop repeatedly moves left by $2p$ spaces, also not changing the index of the tape cell modulo $2p$, and must eventually find the cell congruent to $2^x+1$ modulo $2p$ that has the value (which will be the cell to the left of some counter); because of our primitive root requirement there's exactly one such cell ($2q-1$ is congruent to $-1$ modulo $2p$, and $2^{\log\_{2,p}(r)+1}-1$ is congruent to $2r-1$ for any other $r$, where $\log\_{2,p}$ is the discrete logarithm to base 2 modulo $p$). Additionally, it can be seen that the position of the tape pointer modulo $2p$ increases by $2$ each time round the middle loop. Thus, the tape pointer must cycle between all $p$ counters (in order of their values modulo $2p$). Thus, every $p$ iterations, we decrease every counter (as required). If the loop breaks partway through an iteration, we'll resume the decrease when we re-enter the loop (because the rest of the outermost loop makes no net change to the tape pointer position).

When a counter does hit 0, the middle loop breaks, taking us to the "adjustment" code. This is basically just an encoding of $f$; for every pair $(x,y)$, it adds $f(x,y)$ to the tape element which is the same distance left/right of the current tape pointer as counter $y$'s tape location is left/right of counter $x$'s tape location (and then removes the tape pointer back to where it started). Whenever $x\neq y$, this distance turns out to be unique:

* The difference between two powers of 2 is a binary number consisting of a string of 1 or more $1$s followed by a string of 0 or more $0$s (with the place values of the start of the number, and the start of the $0$ string, depending on the larger and smaller respectively of $x$ and $y$); thus all those differences are distinct. * As for the difference of a power of 2 and $q$, it must contain at least two transitions between strings of $1$s and $0$s ($q$ contains at least four such transitions, the subtraction can only remove 2), thus is distinct from all differences of two powers of two, and these differences are obviously also distinct from each other.

For $x=y$, we obviously find that the distance moved is 0. But because all $f(x,y)$ are equal, we can just use this as the adjustment for the current cell. And it can be seen that the adjustment code thus implements the "when a counter hits 0" effect for every counter; all the cells that actually represent counters will be adjusted by the correct amount, and all the other adjustments will affect non-counter even-numbered cells (the difference between two even numbers is even), which have no effect on the program's behaviour.

Thus, we now have a working compilation of any program in The Waterfall Model to BF (including halt behaviour, but not including I/O, which isn't needed for Turing-completeness) using only three pairs of brackets, and thus three pairs of brackets are enough for Turing-completeness.

---
Tags: turing-completeness
---


title: Is the following Grammar LL(1)

text:
# Question
Title: Is the following Grammar LL(1)
I was given the following grammar

$S \rightarrow S ( S ) S\mid \epsilon$

First I was asked to eliminate left recursion, yielding me the following :

$S \rightarrow S' $

$S' \rightarrow (S)SS' \mid \epsilon$

I was then asked If the grammar is LL(1). So I computed the FIRST and FOLLOW sets shown below:

$\mathrm{FIRST}(S) = \mathrm{FIRST}(S') = \\{ ( , \epsilon \\}$,

$\mathrm{FOLLOW}(S) = \mathrm{FOLLOW}(S') = \\{ \\$, ( , ) \\}$.

I now tried building the LL(1) parsing table $M$ as follow:

Since we have production $S \rightarrow S' $ and $\mathrm{FIRST}(S') = \\{ ( , \epsilon \\}$, the table's entry $M \[ S , ( \] = S \rightarrow S'$.

But since $\epsilon$ belongs in $\mathrm{FIRST}(S')$ then for each element $b$ in $\mathrm{FOLLOW}(S)$,

$M \[ S , b \] = S \rightarrow S' $.

This would entail that $M \[ S , ( \] = S \rightarrow S' $.

Since the entry was already populated, is this a conflict? If yes, what kind?

Or since the 2 productions are the same we can just ignore it?

Also if the second case is the right one, is the grammar LL(1)?

# Answer
> 0 votes
> Since the entry was already populated, is this a conflict? If yes, what kind? Or since the 2 productions are the same we can just ignore it? Also if the second case is the right one, is the grammar LL(1)?

Although the entry was populated, this is not a conflict since the same rule is put into the table entry $M \[ S , ( \]$, which can be ignored.

However, the grammar is not LL(1). This can be seen from either of the following.

* The string ()() has following two different leftmost derivations. $$S\rightarrow S'\rightarrow (S)SS'\rightarrow (S')SS'\rightarrow ()SS'\rightarrow()S'S'\\ \rightarrow()(S)SS'S'\rightarrow()(S')SS'S'\rightarrow()()SS'S'\\ \rightarrow()()S'S'S'\rightarrow()()S'S'\rightarrow()()S'\rightarrow()()$$ $$S\rightarrow S'\rightarrow (S)SS'\rightarrow (S')SS'\rightarrow ()SS'\rightarrow()S'S'\\ \rightarrow()S'\rightarrow()(S)SS'\rightarrow()(S')SS'\rightarrow()()SS'\\ \rightarrow()()S'S'\rightarrow()()S'\rightarrow()()$$
* When we build the table entry $M\[S', (\]$, it will have two entries, $S' \rightarrow ( S ) S S'$ and $S' \rightarrow\epsilon$.

Although neither the new grammar nor the original grammar is LL(1), the language generated by either of them is LL(1) since it is generated by following LL(1) grammar.

$$S \rightarrow (S)S \mid \epsilon $$

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


# Question
Title: No. of disk blocks writes required for writing the file
Assume that a file is written using write(fd, buf, K) system calls, where fd is the file descriptor, and K, the number of files to be written to the current file offset which is a multiple of the disk block size D. The total number of disk block writes required to be executed before the system call returns is:

(a) is equal to K/D

(b) is less than K/D

(c) is greater than K/D

(d) None of the above.

In my opinion, the answer should be (c). But the solution manual says it's (d).

I believe the number of file writes required for writing a file is $ceil(K/D)$ So, the answer should be (c).

Am I correct? If not, what am I doing wrong?

Thanks in advance!

# Answer
> 2 votes
The correct answer is: greater or equal to K/D, depending on the fact that K can be a multiple of D or not. So, the answer is actually c), which differs from the other three answers.

Note that if there were an answer “ceil(K/D)”, that would have been the correct answer.

---
Tags: computer-architecture, database-theory, memory-hardware, filesystems
---


# Question
Title: A greedy algorithm for the bottle filling problem
(There’s no need to write the algorithm, I just need help with the greedy choice).

Problem: you are given bottles numbered 1 to n. Each bottle i has a capacity of Ci and currently contains Li. We want to poor water between the bottles so that as many bottles as possible will be filled (Li = Ci) but doing so while moving a minimal amount of water. Write a greedy algorithm that will print instructions on how to do so (poor x liters from bottle i into bottle j). Prove correctness of your algorithm, and give its time complexity.

I’m having trouble solving this problem. We need to write a greedy algorithm, and so the solution is of the type: “take bottle with certain property x and poor as much as you can (until it’s empty or until the other bottle is full) into bottle with certain property y”. But putting in all of the simple properties don’t seem to work and can be refuted with a counter example. Any ideas?

# Answer
> 1 votes
Here is the "greedy" idea.

Suppose you need to choose one bottle to fill completely with minimal amount of water. Which bottle will you choose?

Once you have chosen one bottle and fill it completely with water, the situation you are in now is just as before but one bottle less. You can apply the "greedy" choice again. And so on.

# Answer
> 1 votes
Assume you have 100 empty one litre bottles and 50 filled two litre bottles. So what is your optimal solution, having 50 filled bottles by doing nothing or having 100 filled bottles by pouring 100 litres into the empty bottles? I assume the latter.

You have a fixed amount of water. To have as many filled bottles as possible, you sort the bottles by capacity and find the largest n such that the n smallest bottles can be filled. There may be some water left, but not enough to fill bottle #n+1.

Now comes the hard part: You may have many choices to pick the filled bottles. Say you have bottles filled with 100.999 litres total, and the smallest 200 bottles have a capacity of 1 litre to 1.010 litres total, other bottles are 2 litres or more. You may have a huge number of choices which 100 bottles to fill. I think this is equivalent to the knapsack problem, therefore NP-complete.

# Answer
> 0 votes
The answer builds off of gnasher's answer. (The problem as a whole is not NP-complete, though.)

You have a starting configuration of water, and and at the end you're going to fill as many bottles as you can, and they will all be the smallest bottles. There might be some water left in other larger bottles, but that's okay as long as none of it's enough to fill a whole nother bottle.

So, there are sort of two goals: -Fill water into small bottles (most in need of filling) -Empty the large bottles first (least in need of filling).

So if you take your largest bottle with water, then it's definitely not going to be full in the final state, so you can use it to start filling other bottles. Pour from it into the smallest, second smallest, etc. until it's empty. Then go with the second largest bottle. And so on.

This is greedy in that you're not planning, just moving immediately the most useless part to the most useful.

It's correct because, for all the water that you pour, you would have needed to fill at least that much anyway: you need to have that small bottle full in the final solution anyway, so you're not wasting anything.

Of course you do have to stop early enough! If you don't have enough "spare" water to fill the next-smallest bottle, then stop!

This can also be finnicky if you have ties for largest bottle, then you have to choose which one to pour from first, in case one can get filled up and it has more already in there. You will still eventually end up with as many filled as possible, but if you aren't careful you could pour water inefficiently between equally large bottles.

# Answer
> 0 votes
The problem is NP-complete, shown by reducing the knapsack problem to it.

Take the knapsack problem: Given are n items with weight 0 \< w\_i \<= 1, and value v\_i \> 0. Pick items with total weight \<= 1, maximising the total value of items picked. Let the total value of all items be V, and the total weight W \<= n.

We now take n bottles of capacity 1 + w\_i filled with w\_i + v\_i / 2V and n empty bottles of capacity 1, plus another bottle of capacity 2n and filled with n - W + 1/2. Total amount of fluid is n+1. We can fill n bottles but not n + 1.

If we decide to fill bottle i then we need to pour 1 - v\_i/2V, filling an empty bottle requires pouring 1. When we optimise the bottle filling problem, we fill n bottles with the sum of w\_i \<= 1, and the sum of 1- v\_i/2V minimised, so the sum of v\_i is maximised, solving the knapsack problem.

---
Tags: algorithms, greedy-algorithms
---


# Question
Title: Find the minimum N such that the sum of beauty of all numbers from 1 to N is at least X
The beauty of a number is defined as follows :-

```
public int beauty(long number)
{
     int count = 0;

     while( number > 0 )
     {
         count += (number & 1);
         number = number / 2;
     }

     return count;
}

```

Given X, we need to find the minimum N such that the sum of beauty of all numbers from 1 to N (inclusive) is at least X. X may be as large as upto 10^18 and there are 2\*(10^4) test cases.

As far as I have understood, the beauty of the number is the count of set bits in the integer. So we need to find the sum of count of set-bits from 1 to N. But numbers such as X = 10^18 give the values 10^15 for N. It is not feasible to run loop from 1 to 10^15. Is there a better algorithm ?

# Answer
**Notations** :

* $b(x)$ is the beauty of $x$.
* $S\_c(n) = \sum\_{x = 0}^{2^n-1} (b(x)+c)$ where $c\in\mathbb N$
* $\tilde O(\log t)$ : polylogarithmic in $t$

**Argument** :

Let's first show that $S\_c(n)$ is easy to calculate for any $c,n\in\mathbb N$. Each number in $\[\\!\[0, 2^{n-1}\]\\!\]$ has at most $n$ bits, and for each $i\in\[\\!\[1, n\]\\!\]$, exactly half of the numbers below $2^n$ have the $i$-th bit set to 1. Therefore, we can rewrite $$\sum\_{x =0}^{2^n-1} b(x) = \sum\_{i = 1}^n 2^n/2 = n\cdot 2^{n-1}$$ (in 0, the result is 0). This leads to : $$ S\_c(n) = 2^{n-1}\cdot (c+2n)$$ Since $S\_c(n)$ grows exponentially and is computable in $O(n)$, it takes $\tilde O(\log X)$ time to find the (unique) $n$ such that \begin{equation}S\_c(n)\le X\< S\_c(n+1)\end{equation}

We'll note $n\_0$ this $n$ for $c = 0$. One should notice that this $n\_0$ is the index of the leftmost bit set to 1 in $N$ $$\sum\_{x = 0}^N b(x) = \sum\_{x = 0}^{2^{n\_0}-1} b(x) + \sum\_{x = 2^{n\_0}}^N b(x)$$ Moreover, $N\<2^{n+1}$, so each $x$ in the rightmost sum has $n$ bits and the leftmost bit set to 1, i.e. : $$\sum\_{x = 2^n}^N b(x) = \sum\_{x = 0}^{N-2^n} b(x) + 1$$

We therefore get a **recursive call** : we can find the index of the leftmost bit set to 1 in $N-2^n$ by finding $n\_1$ such that $S\_1(n\_1)\le (X- S\_0(n\_0)) \le S\_1(n\_1+1)$

This lends the following algorithm :

```
s(n,c) =
    if n = 0 then c
    else (2^(n-1)*(c+2*n))

smallest_n(x,c,n) = //We shall call this function with n = 0
    if s(n+1,c) > x then n
    else smallest_n(x,c,n+1)

sum_beauties_above(x,c) =
    if x = 0 then 0
    else
        let n = smallest_n(x,c,0) in
        let n' = sum_beauties_above(x - s(n,c),c+1) in
        2^n + n'
sum_beauties_above(x,0)

```

the first function takes $O(n)$ time, the second takes $\tilde O(\log X)$. The main function calls itself as many times as $N$ has bits set to $1$, which is bounded by $\log N\le \log X$, and each call has complexity $\tilde O(\log X)$, so we keep a polylogarithmic complexity in $X$.

However, this has been written in functionnal programming style, and is not tail-recursive, therefore, it is highly suboptimal, but this way of writing seems easier to understand, and one should take care of optimization.
> 1 votes

# Answer
Let us first solve the following problem:

> Given $n$, count the total number of 1-bits of all integers from $0$ to $n-1$.

Suppose that $n = 2^{m\_1} + 2^{m\_2} + \cdots + 2^{m\_k}$, where $m\_1 \> m\_2 \> \cdots \> m\_k$; every positive integer has such a representation. We can divide the range $\[0,n) := \\{0,\ldots,n-1\\}$ into the following ranges: $$ \[0,n) = \[0,2^{m\_1}) + \[2^{m\_1}, 2^{m\_1}+2^{m\_2}) + \cdots + \[2^{m\_1} + \cdots + 2^{m\_{k-1}}, 2^{m\_1} + \cdots + 2^{m\_k}). $$ Let's start with the first range, $\[0,2^{m\_1})$. This range consists of all $m\_1$-bit numbers. Each particular bit is 1 exactly half the time, and so the total number of 1-bits in $\[0,2^{m\_1})$ is $m\_12^{m\_1-1}$.

The second range consists of all numbers in $\[0,2^{m\_2})$ to which $2^{m\_1}$ was added. The additional power contributes an extra 1-bit to each number in the range, for a total of $m\_2 2^{m\_2-1} + 2^{m\_2}$, which can also be written as $2^{m\_2} (m\_2/2 + 1)$.

Continuing in this way, we see that the total number of 1-bits of all integers in $\[0,n)$ is $$ 2^{m\_1}(m\_1/2) + 2^{m\_2}(m\_2/2+1) + 2^{m\_3}(m\_3/2+2) + \cdots + 2^{m\_k}(m\_k/2+k-1). $$

This suggests the following algorithm:

1. Find the maximal $m\_1$ such that $\sigma\_1 := 2^{m\_1}(m\_1/2) \leq x$. In case of equality, return $2^{m\_1}-1$.
2. Find the maximal $m\_2 \< m\_1$ (if any) such that $\sigma\_2 := \sigma\_1 + 2^{m\_2}(m\_2/2+1) \leq x$. In case of equality, return $2^{m\_1} + 2^{m\_2}-1$.
3. Continue in this way. If you get stuck at $m\_1,\ldots,m\_k$, return $2^{m\_1} + \cdots + 2^{m\_k}$.

(Getting stuck means that there is no $m\_{k+1} \< m\_k$ such that $\sigma\_{k+1} \leq x$.)
> 0 votes

---
Tags: algorithms, arrays, bit-manipulation
---


# Question
Title: Who decides that process needs cpu time or not?
I wonder how does particular process gets CPU time or resources whenever it's required to execute some instructions? When a process is in the idle state or waiting for input, it's not occupying the CPU but, if it is suddenly found that there is an instruction that requires CPU time, who tells that to the CPU?

# Answer
> 1 votes
Typically it will be an operating system process to take responsibility for "waking up" other processes. Most commonly, the so-called process scheduler, which is a key component of every operating system.

For example, if a user process requires some data to be read from disk before continuing its computation, it may be put into a waiting state by the scheduler until the data are available. The scheduler gives the CPU to other processes that are runnable (not waiting), then when the data are available the user process becomes runnable again.

# Answer
> 0 votes
This is done by the operating system's scheduler. This software module is responsible for allocating CPU time to runnable processes and also updating which processes are runnable, e.g., when a process has to wait for I/O or when I/O completes, allowing a process to run again.

---
Tags: computer-architecture, operating-systems, cpu
---


# Question
Title: Algorithm for Items Best Fit/Arangement in a Box
I was looking for an algorithm that will give the best fit arrangement of package items in a box. For example given a large box and various items with multiple shapes(can be rectangle, square and so on and so forth), how will I arrange the items so that it will fit in the box? DO we have already an algorithm for that? If yes, what algorithm is it?

If no, I was thinking of making an algorithm for it.

# Answer
> 1 votes
Yes, there are plenty of algorithms.

Here are some existing literature about packing rectangles.

Here are some libraries that can be used readily.

---
Tags: algorithms
---