# Question
Title: Data structure and optimal algorithm for modeling reachable outputs given a set of inputs
Given the following:

* A set of input types $I$ = {a, b, d, ...}
* A set of functions $F$ (With associated costs, and possibly identical signatures) = {($c\_1$, a -\> d), ($c\_2$, (a,b) -\> e), ($c\_3$, e -\> (d,f)), ...}
* A set of desired output types $O$ = {f, g, h, ...}

I would like to build a system that can return the lowest cost set of functions in $F$ which need to be called to generate $O$ from $I$, if such a set exists (Let's call this subset $R$ ).

By "generate" I mean that for each $o \in O$ there is a function in the returned subset $R$ that includes $o$ among its outputs; and for each function in $R$, all of its inputs are either in $I$ or are outputs of other earlier functions.

If $F$ consisted of only single-variable functions this would be easy, as I could just use a graph with types as vertices and functions as edges, then find the shortest path from available input type vertices to desired output type vertices. With multi-input/multi-output functions I can still do this, but I have to make multiple re-traversals through the graph if I find that I do not yet have a function in the selected collection that can generate one or more of the inputs required for a particular function.

The best idea I've come up with to deal with the multi-input/multi-output function scenario is to still use a graph (a DAG specifically), but have each vertex represent a full collection of currently available types, with each edge representing a function, and many duplicate edges representing the same function being called using the required inputs from many different overlapping collections in the graph.

I'm looking for confirmation on whether or not this is a good approach, and any recommendations on alternative data structures or algorithms to solve this problem effectively.

# Answer
The problem is NP-hard, by reduction from set cover.

In particular, suppose we have a instance of the set cover problem, i.e., sets $S\_1,\dots,S\_m$, and the goal is to identify the smallest collection of sets whose union is $U$. We can create an instance of your problem, with $I=\emptyset$ and $O=U$, with one function $f\_i$ for each set $S\_i$, such that the output set of $f\_i$ is $S\_i$ and its input set is $\emptyset$, and every function has the same cost. Then the lowest-cost collection of functions that cover $O$ yields the smallest collection of sets whose union is $U$.

Therefore, you should not expect any efficient algorithm for your problem that always works.

Instead, you might consider using an off-the-shelf ILP solver. For instance, introduce a zero-or-one variable $x\_f$ for each function $f \in F$; the intended meaning of $x\_f=1$ is that $f$ should be included in the set of functions. Then, add linear inequalities to capture that this set is valid:

* For each function $g \in G$ and each type $t \notin I$ that is an input to $g$, add a linear inequality

$$\sum x\_f \ge x\_g,$$

where the sum ranges over all functions $f$ that contain $t$ as one of their output types.
* For each $o \in O$, add a linear inequality

$$\sum x\_f \ge 1,$$

where the sum ranges over all functions $f$ that contain $o$ as one of their output types.

Finally, the objective function is

$$\Phi = \sum\_{f \in F} c\_f x\_f,$$

where $c\_f$ is the cost of function $f$. This is an instance of integer linear programming (ILP), so you can use an off-the-shelf ILP solver to try to find the best solution to it.
> 2 votes

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


title: Inversion array of a given array

text:
# Question
Title: Inversion array of a given array
Let A\[1...n\] be an array of n distinct numbers. The ordering of the numbers is any permutation of \[1,2,...,n\]. An array Inv\_A is defined as follows: Inv\_A\[i\] = number of elements A\[j\] such that j\<i and A\[j\] \> A\[i\]. Give an optimal algorithm that computes the above array Inv\_A. For example if A = \[3,1,4,5,2\] then Inv\_A = \[0,1,0,0,3\]. Expected time complexity is O(nlogn).

# Answer
Apply heap-sort for in-place sorting in $O(log(n))$ time. For a real application, it's better to use the simple randomized-quick-sort. You can get enough build-in routines in almost every popular language.
> 0 votes

---
Tags: algorithms, time-complexity, data-structures, algorithm-analysis, arrays
---


# Question
Title: Does a random phenomenon have a pre defined probability distribution? what does it mean for something to be random?
While studying Shannon's notion of perfect secrecy I came upon the idea that a bit is perfectly random if it happens to be 0 or 1 with an equal probability. What does this mean? Also, what can we say about the determinism here?

# Answer
Determinism is not broken, it is just that you are unaware of the value of the bit and can make no bet on it (because the two outcomes are as likely).

If you have some extra information such as "there are twice as many ones as zeroes in total" (but you still don't know where), you'd better bet one than zero to maximize your chances.
> 1 votes

---
Tags: nondeterminism, randomness, cryptography
---


# Question
Title: Quickly obtaining sums of sets of numbers
We are given a set of $n$ bits, call them $a\_1$, $a\_2$,...,$a\_n$. We are also given a set of $m$ sums, where the sums $s\_1$, $s\_2$,...,$s\_k$,...,$s\_m$ are given as sums of some of the bits. For example:

$$s\_k = a\_3 + a\_5 + a\_{17} + a\_{22} + a\_{35}$$

There is more structure to the sums, however. The sums are split into $m / \alpha$ groups, where each sum is in only one group. For example, and to make things easier, sums $s\_1$, $s\_2$,...,$s\_{\alpha}$ are in group 1, sums $s\_{ \alpha + 1}$,...,$s\_{2\alpha}$ are in group 2, and so on. Then we know that each bit will occur exactly once in each group.

So for example, the bit $a\_1$ will appear in each group, the bit $a\_2$ will appear once in each group, and so on...

**QUESTION**

How fast can we calculate all of the sums?

**MY IDEAS**

If we assume that there are $\alpha$ sums in each group, then there are at most $2^\alpha$ combinations of bits. For example, if there are two sums, we know that there are four combinations of bits:

(0) Bits that are not in either sum

(1) Bits that are in sum 1 ($s\_1$), but not in sum 2 ($s\_2$)

(2) Bits that are not in sum 1 ($s\_1$), but are in sum 2 ($s\_2$)

(3) Bits that are in both sums.

Thus we need at most $n$ additions to calculate the sums of each of the $m / \alpha$ groups. So our total time is at most $n(m/\alpha)$ additions, since there are $m/\alpha$ groups.

---

However, I believe that we can do better! I'm guessing that we can also use subtraction and sums from different groups to arrive at a much better algorithm.

# Answer
> 0 votes
I believe that we can do even better than this answer, but perhaps this will help.

We split our list of bits $a\_1$, $a\_2$, $\dots$, $a\_n$ into approximately $n / \beta$ collections (these could also be called groups, but I make the distinction so that we know that these are different from the groups above). Here we set $\beta = \log{(m/(\log{(mn)})}$ In other words, the first collection consists of the first $\beta$ bits $a\_1$, $a\_2$, $\dots$, $a\_{\beta}$. The second collection consists of the second $\beta$ bits $a\_{\beta+1}$, $a\_{\beta+2}$, $\dots$, $a\_{2\beta}$, and so on.

We find all possible sums for each collection, of which there are approximately $2^{\log{(m/(\log{(mn)}))}} = m/(\log{(mn)})$. We then calculate each of these sums exactly. If we're careful, we can calculate each sum in constant time by adding or subtracting one bit from a sum with all other bits the same.

Thus we use roughly $m/(\log{(mn)})$ space to store each solution, times $\log{\log{(mn)}}$ maximum bits per solution, times $n / \log{(mn)}$ different collections.

The running time should be approximately $O \left( \frac{mn \log{ \log{ (mn)}}}{\log{(mn)})^2} \right)$ if I did my calculations right.

This is somewhat faster than the naive approach. Again, I believe that we can do better.

# Answer
> 0 votes
If I understand correctly, only the bits $a\_k=1$ are to be counted. Then, a given bit influences exactly one sum per group, and no sum in the same group have common terms. So a straightforward solution is to associate to every bit the list of sums it takes part to (one per group), and to accumulate that bit to these sums. This takes an effort $n+n'g$ where $n'$ denotes the number of ones and $g$ the number of groups.

Now if I am right, the only way to make it faster is by detecting common subexpressions between the groups (there are no common subexpressions within a group), and compute them once only. The extreme case would be that of all sums being identical across all groups, reducing the workload to $n+m$.

This said, finding the common subexpressions and minimizing their number seems a daunting task.

---
Tags: algorithms, asymptotics, upper-bound, finite-sets
---


# Question
Title: Given two strings ABC and CBA, find A, B and C
Given two strings ABC and CBA, find A, B and C.

Input: abcacab, cabcaab

Output: ab, ca, cab

The time complexity of brute force is O(n^3). Are there any better algorithms to solve this problem? Thanks!

# Answer
> 0 votes
I'd start by trying to find possible values of A.

A could be an empty string obviously.

Otherwise, you know the last character of A. Let's say that character is the first, fourth and nineteenth character of ABC. Then A could be one character. Or it could be the first four characters of ABC (if it matches the last four characters of CBA. Or it could be that last nineteen characters of ABC (if it matches the last 19 characters of CBA), and so on.

In your example, the last character of CBA was b, which is the second character of ABC, so (apart from A = empty), the only possibility for A was A = ab, leaving BC = cacab, CB = cabca. A = nine characters is not possible because the first and last nine characters of ABC and CBA are different.

For each possible value of A you now have BC and CB. You do the same examination. Except if the last character of B is in position k within BC, then the character k+1 of BC is the first character of CB, so this must also match.

You will be better off if you count which characters occur most often, and check the rarest characters. For example, if you have a million characters, and the character X occurs only once, at position 10 of ABC and 19 characters from the end in CBA then you conclude that A could be 28 characters, or is at most nine characters.

---
Tags: algorithms, time-complexity
---


# Question
Title: Hilbert's Hotel for guests with infinite string name
I was watching this video How An Infinite Hotel Ran Out Of Room, by Veritasium.

The video says that it is not possible to fit names made of infinite strings of $\\{A,B\\}$.

We know we can fit infinite people in the hotel, we also know that there solution that works and solution that don't work. For example if you have infinite buses with infinite people if we gave a room one bus at a time we would be full after the first bus, on the other hand if we make a matrix and translate the diagonal to a single line (as shown on the video) we can fit everyone.

Following this if we ignore the name and treat the set as a stack then you would fit all of them because it's then a infinite stack and we can use their hotel room number to identify them, would this not be a possible solution?

# Answer
An infinite string is uniquely identified by a function $s:\mathbb{N}\rightarrow \\{A,B\\}$, such that $s(n)$ is the $n$'th character in the string.

The number of such functions is known to be: $|\\{A,B\\}|^{|\mathbb{N}|}=2^{\aleph\_0}$.

Now, its also known that $2^{\aleph\_0}\>\aleph\_0$, and hence there is no way to assign strings to hotel rooms, and more formally:

there is no one-to-one function between the set of all strings, (denoted $\\{A,B\\}^\omega$) and $\mathbb{N}$.
> 3 votes

# Answer
There is, in fact, a solution. Convert the name to a binary number such that A=1 and B=0.

Then, either subtract each person’s name from infinite 1111111 or just remove all 0s before the first 1. Either way, the set becomes all binary numbers from 0 -\> infinity.

At that point, just add 1 and convert to decimal. Then you have all decimal numbers 1 -\> infinity.

You can use the trick in Veritasium’s video to move all current occupants to double their number, then take all ABBA’s friends and take their name-based number • 2 - 1 to make a set of odd numbers 1 -\> infinity and now they all have rooms based on their original names.

For my video about this: https://youtu.be/o1JXUKhUzh4
> -1 votes

---
Tags: uncountability, diagonalization
---


# Question
Title: shortest path increases monotonically => a bound on the length of one iteration of Edmons-Karp is then O(E) ... Convince me this is true
I was reading the proof of time-complexity for the Edmonds-Karp algorithm here (https://brilliant.org/wiki/edmonds-karp-algorithm/).

Everything in the first part of the proof (The section Monotonically increasing path length) makes sense. However, the last part of it is not very convincing (the part I have highlighted with red).

Can someone convince me that it is true that the fact that "the shortest path increases monotonically in the residual graph" implies a "bound on of one iteration of Edmonds-Karp algorithm to $O(E)$".

---

# Answer
> 1 votes
It is no wonder why that you doubt that "the shortest path increases monotonically in the residual graph" implies a "bound on of one iteration of Edmonds-Karp algorithm to $O(|E|)$".

The time bound of $O(|E|)$ has nothing to do with the fact that "the shortest path increases monotonically in the residual graph".

It takes $O(E)$ time to perform one iteration of Edmonds-Karp algorithm, since what it does is mostly a breadth-first search.

(It takes $O(|V| + |E|)$ time for a breadth-first search on a general graph. However, in the case of finding the maximum flow in a flow network, we assume the given network is connected or there is at least one edge incident to every vertex usually. That is, $|E|\ge |V|-1$ or $2|E|\ge|V|$. Then $O(|V|+|E|)=O(|E|)$)

---
Tags: algorithms, time-complexity, correctness-proof, network-flow
---


# Question
Title: Efficient sampling from all positive integers to find the largest integer below a transition for f(n)
Let's say we want to find the smallest positive integer *x* for which some property *A* holds. We know that such an integer exists. However, we have no knowledge about the scale of *x* (i.e. *x* could be 7 or 5'142 or 17 Quadrillion or whatever).

We have a function *f* that returns true when evaluated at values larger or equal to *x*, *f* returns false when evaluated at values strictly smaller than *x*. Let's assume evaluating *f* at *n* has a runtime complexity of $O(n^2)$.

What is a reasonable (or even optimal) way of selecting integers to evaluate *f* at in order to find x while reducing runtime? How would the answer change when the runtime complexity of *f* is different?

My thoughts:

Usually I would calculate the expected number of calculations needed and try to minimize that value. However, without any knowledge about the size of *x* I could not wrap my head around how I would do that since a uniform distribution over all positive does not make a lot of sense. Is there another type of distribution that can be used in such cases? Further it does not make sense to me to evaluate every integer in increasing order until *x* is found. Intuitively, I would probably evaluate powers of 10 (i.e. f(10), f(100), f(1000)), but this is surely not optimal.

Any thoughts are appreciated, even just the keyword that would lead to successful google results.

# Answer
The normal approach is to evaluate $f(1)$, $f(2)$, $f(4)$, $f(8)$, $f(16)$, $f(32)$, $f(64)$, etc., until you find the first power of two for which $f(2^k)=\text{true}$ (and thus $f(2^{k-1})=\text{false}$). Then, you use binary search in the range $\[2^{k-1},2^k\]$ to find the smallest value for which f returns true.

If the correct answer is $n$, the first stage will take $O(n^2)$ time, and the second stage will take $O(n^2 \log n)$ time, for a total running time of $O(n^2 \log n)$.

As gnasher729 indicates, if you care about the constant factors, you can optimize this by replacing 2 with an appropriate constant.

This process is sometimes called doubling search. See https://en.wikipedia.org/wiki/Exponential\_search and https://en.wikipedia.org/wiki/Binary\_search\_algorithm.
> 9 votes

# Answer
Linear search is $0,1,2,3,4,\cdots k,\cdots$. ($O(n)$ steps to pass $n$.)

Exponential search is $1,2,4,8,16,\cdots2^k,\cdots$. ($O(\lg(n))$ steps to pass $n$.)

Doubly exponential search is $2,4,16,256,65536,\cdots2^{2^k},\cdots$. ($O(\lg(\lg(n)))$ steps to pass $n$.)

And so on.

After you have found a $\text{true}$, you can continue with dichotomic searches at the previous growth levels.

If you expect truly huge numbers, you can use even faster growing sequences, such as $2\uparrow^k2$. ($O(\lg^\*(n))$ steps to pass $n$.)

There is no theoretical optimum.
> 12 votes

# Answer
If you want the exact value of x, you’d find an interval of width 2^k containing x, then k steps of binary search at a cost of roughly x^2 find x. Total cost about x^2 log x.

If you want a rough estimate for x, you’d evaluate at x = c^n for a suitable c \> 1. The cost is multiplied by c^2 for each n, so the total cost is c^2n * (c^2 / (c^2 - 1)).

C^2n = d\*x for some d, 1 \<= d \< c^2. You can calculate the expected value of d^2, multiplied by c^2 / (c^2-1) and pick c to minimise this factor.
> 7 votes

---
Tags: complexity-theory, sampling
---


# Question
Title: Optimizing method for counting length of elements between blocks
I'm currently trying to do a count of the number of elements between obstacles, for example:

000100001000 Would yield 3,4,3 and 01001110 would yield 1,2,1. More precisely i'm trying to find the sum of the above lengths passed to this function:

$f(x) = \frac {x(x+1)} {2}$

So the first example would yield a result of 22 (6+10+6) and the second would yield a result of 5 (1+3+1).

This is done repeatedly with the first element 'chopped off'. So for 000100001000, this would be calculated for 000100001000, 00100001000,0100001000 ,100001000 ,00001000 and so on (note that the answer for 10010 and 0010 would be the same since we're counting the distance between ones)

Currently i've just been using an $O(N^2)$ brute force approach, but i feel that i can easily improve this to O(N) since most of the information is already calculated after the very first element is processed. I'm wondering if there's a constant time method to process the subsequent elements after the first one is processed, but if not, what is the best approach?

Edit: I found a way to optimize the algorithm that requires this algorithm, but that implies that some of the zeroes could be transformed into ones when a digit is 'chopped off'. It's safe to assume that the element(s) that get transformed would be random. Eg: 0010 when chopped may transform into 011 or 110 or 111 instead

# Answer
One gap can be calculated as tetrahedral number $P(x) = \sum \limits \_{i = 1} ^{i=x} f(i) = \frac{x * (x + 1) * (x + 2)}{6}$ where $f(i) = \frac{i * (i + 1)}{2}$
After calculating all gaps to calculate chopped off sum you need to subtract $P(x) - P(x-1)$ from the sum.
> 0 votes

# Answer
If is unclear what your 0/1 represent (characters in a string or bits in integers). Anyway, extracting the symbols in sequence takes $O(n)$ operations for $n$ symbols.

There is no particular difficulty in counting the lengths of the continuous runs of zeroes (this is an $O(n)$ task) and accumulating the corresponding $f$ values (also $O(n)$ at worse).
> 0 votes

---
Tags: algorithms
---


title: Turing machine read time

text:
# Question
Title: Turing machine read time
Suppose I have a Turing machine that takes as input any string of length $n$, where $n$ is odd, and the Turing machine returns the middle character of the string.

What time complexity class is this in? Is it in $O(n)$ because the tape head must scan $n/2$ places to the right, counting as it goes, or is there a quicker, say $O(\log n)$ machine that could accomplish this task?

# Answer
For Turing machines with at least two tapes the problem can be solved in $\Theta(n)$ time, meaning that there exists a Turing machine that solves it using $O(n)$ steps and that all Turing machines must use $\Omega(n)$ steps (see also Yves Daoust's comment).

For Turing machines with one tape, the time needed to solve the problem is between $\Omega(n)$ and $O(n \log n)$.

The running time of your particular Turing machine depends on the details of the machine itself.

A possible two-tape Turing machine that requires time $O(n)$ works in multiple "rounds". Each round starts with the head placed on the first non-blank symbol of the tape and works as follows:

* Check whether the tape contains a single (non-blank) symbol (i.e., the next symbol is blank). If so, halt (that symbol is exactly the sought one). Otherwise reset the head to the first symbol.
* Determine whether the number $m$ of (non-blank) symbols currently on the tape is of the form $4k+1$ or $4k+3$, for some $k \in \mathbb{Z}$.

+ If $m=4k+1$, delete every other symbol in the tape (i.e., replace them with the blank symbol) starting with the second symbol. After this step the number of non blank symbols is $1 + \frac{m-1}{2} = 1 + \frac{4k}{2} = 2k+1$ and the middle non-blank symbol (i.e., the $k+1$-th symbol) is unaffected.
    + If $m=4k+3$, delete every other symbol in the tape starting with the first symbol. After this step the number of non blank symbols is $\frac{m-1}{2} = \frac{4k+2}{2} = 2k+1$ and the middle non-blank symbol is unaffected.
* Now the tape consists of alternating blank and non-blank symbols. Compact all the non-blank symbols so that they are contiguous (using the second tape). Place the head on the first non-blank symbol and move to the next round.

To see that the running time is indeed $O(n)$, notice that the last round starts with only one symbol and requires constant time, while every other round has $1+\ell \ge 3$ symbols (i.e., the middle symbol plus $\ell$ "additional" symbols) and requires at most $c \ell$ steps (for some constant $c$ independent of $\ell$). Moreover each such round at least halves the number of additional symbols.

Initially $\ell=n-1$ and hence the overall number of steps is at most: $$ O(1) + \sum\_{i=0}^{\infty} \frac{c(n-1)}{2^i} = O(1) + 2 c(n-1) = O(n). $$

A possible single-tape Turing machine that requires time $O(n \log n)$ also works in multiple "rounds". The idea of each round is as follows:

* If the length of the input is smaller than a (sufficiently large constant) explicitly move to the middle character and halt.
* Mark all the input cells with a "left" mark
* While there are at least 6 marks, scan the tape from left to right and delete every other "left" mark starting from the leftmost one
* Mark all the input cells with a "right" mark
* While there are at least 6 marks, scan the tape from right to left and delete every other "right" mark starting from the rightmost one
* Delete all symbols to the left of the leftmost "left" mark
* Delete all symbols to the right of the rightmost "right" mark
* Remove all marks, reset the head positions, and move to the next round (notice that the middle symbol has not changed).

Notice that each round (but the last) reduces the number of symbols by at least a constant fraction, and that a round with $m$ symbols requires $O(m \log m)$ time.
> 1 votes

---
Tags: time-complexity, turing-machines, runtime-analysis
---


# Question
Title: What happens to the running time if we reduce the size of input?
Let there is an algorithm whose running time is $O(n^2)$. Suppose we apply a preprocessing step on the algorithm in $O(n)$ so that it reduces the input size to $O(\sqrt{n})$ but doesn't effect the true answer of the algorithm. It is just for optimization. Now is it true to say that the running time of the algorithm is $O(n)$ when preprocessing is applied? Because $O(n^2)$ becomes $O(\sqrt{n}^2)$ which is $O(n)$.

# Answer
TL,DR: it's not the same $n$. That's where the confusion comes from.

When we say that an algorithm's complexity is $O(f(n))$ (i.e. $O(n)$ or $O(n^2)$ or whatever), it's implicit that $n$ is the size of the input. There is an implicit assumption here that there is a single numerical parameter that is “the size of the input” and that everyone agrees on what it is. (At least we have to agree up to what can be distinguished with asymptotic approximations — for example a length in bits vs a length in bytes doesn't matter since $O(f(8n))$ is the same thing as $O(f(n))$ for the kind of functions $f$ we tend to encounter in practice, such as polynomials.)

To be rigorous, we shouldn't say, for example, that a quadratic algorithm has running time $O(n^2)$, but that it has running time $O(n \mapsto n^2)$. What matters is the function, not the letter used in the description of the function. $O(n \mapsto n^2)$ is the same thing as $O(p \mapsto p^2)$ is the same thing as $O(z \mapsto z^2)$. (“$n$”, “$p$” and “$z$” respectively are bound variables in this notation.)

When you're dealing with multiple algorithms, the complexity of each algorithm may be expressed in terms of different parameters: it's not the same $n$ anymore. For example, if you chain algorithm A1 with algorithm A2 (i.e. the output of A1 is the input of A2), it's natural to express the complexity of A1 in terms of its input, and the complexity of A2 in terms of its input. So let $n$ be the size of the input to A1: the complexity of A1 is $O(f\_1(n))$. And let $p$ be the size of the input to A2: the complexity of A2 is $O(f\_2(p))$. That's not $O(f\_2(n))$, since now we're calling $n$ the size of the input to A1, not the size of the input to A2. With a more formal notation, the complexity of A1 is $O(f\_1)$ and the complexity of A2 is $O(f\_2)$ — we get rid of that troublesome undefined “$n$”.

In your example, we apply a first algorithm A1 which, when given an input of size $n$, produces an output of size at most $\sqrt{n}$. You don't say what the complexity of this algorithm is. I'm going to assume that it runs in linear time, i.e. $O(n)$. Then we apply a second algorithm A2 whose running time is quadratic, i.e. $O(p \mapsto p^2)$. If we want to express the running time of A2 as a step in the composition {A1;A2} for an input of size $n$, we note that the running time of this step is $O(p^2)$ where $p$ is the size of the input to A2, and we know that this size is at most $\sqrt{n}$. Therefore the running time of the second step, expressed in terms of the original input size, is $O((\sqrt{n})^2) = O(n)$. Again assuming that the running time of A1 is $O(n)$, the total running time of {A1;A2} is $O((\sqrt{n})^2 + n) = O(n + n)$ which by the properties of $O$ is $O(n)$.
> 2 votes

# Answer
Yes. That is correct.

Also, I think that "yes/no" questions are discouraged.
> 0 votes

# Answer
Undisputably, the global time is

$$O(n)+O((c\sqrt n)^2)=O(n).$$
> 0 votes

# Answer
The question is: How long does it actually take to solve the problem given the compressed data as the input?

Let’s say your original problem takes a square matrix with n elements as it’s input (that is sqrt(n) rows and columns) and your algorithm calculates a function of the diagonal in O(n^2). If you compress your matrix to sqrt(n) by throwing all the non-diagonal elements away, the algorithm still takes O(n^2). Except because of the reduced problem size, for data with size s the time is now O(s^4).

Here’s your problem. You have an algorithm that works in O(n^2) for highly redundant data of size n. After you dramatically reduce the problem size, you have no redundancy left. It is highly unlikely that your algorithm runs in O(s^2) for the instance of size s without redundancy.

Maybe you should give an actual example. I gave one where the time goes up from $O(n^2)$ to $O(n^4)$.

Here's a different situation: Your input is n items, of which k are \> 0. The output is a function of the k positive items and is found in $O (k^2)$, once the positive items are known. This is also $O (n^2)$. If you remove all items \<= 0 in O (n) then the time will be $O(n + k^2)$ in total. This will be O(n) in cases where the number of positive items is $O(n^{1/2})$ but not otherwise, say if half the items are positive.
> -1 votes

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


# Question
Title: Algorithms for finding closest graph node within set of nodes
Given a set of nodes $N$ on an undirected, weighted graph $G$ and a query node $n$, what is the fastest algorithm for finding the node in $N$ that is closest to $n$?

Furthermore, say we are doing many of these queries, so have many $n$'s, is there some data structure that could speed up this computation?

Thank you for any feedback or guidance.

Addendum: One other detail I did not mention, every time a query is made, $n$ is added to $N$, so for the next query, $N$ is larger by one node. Is there some version of Dijkstra's or bellman ford that can handle this dynamic situation?

# Answer
Without the addendum, you could do $O(|V|+|E|)$-time preprocessing (a single BFS, starting from the set $N$) that would let you solve each query in $O(1)$ time.

With the addendum, this seems much harder. I would suggest exploring dynamic shortest-paths. See, e.g., Recalculating shortest path after changing the weights, State-of-the-Art techniques on dynamic shortest path computations.
> 0 votes

---
Tags: algorithms, graphs, data-structures, discrete-mathematics, weighted-graphs
---


title: 2D fourier transform

text:
# Question
Title: 2D fourier transform
I an new to image processing and I have some questions I want to understand:

What is the meaning of the imaginary and real part of the 2d fourier transform? What can it tell me about the image it transformed from? For example, what can I tell about an image that its fourier transform omaginary part is always 0? and its real part always 0? What can I tell about an image that it fourier transforn in (0,0) equals 0?

# Answer
> 1 votes
It has same meaning as the 1d Fourier transform: the magnitude and phase of waves that, when superimposed, reconstruct your original signal. In one dimension,

1. the signal is (usually) a function of time, $f(t)$,
2. the Fourier transform takes you into the frequency domain, a kind of "inverse time", and
3. each function value, $F(\omega)$, tells you how much of the wave with frequency $\omega$ you have. Additionally, since we admit positive and negative frequencies, we can think of those waves as propagating "forward" or "backwards" along the time axis depending on the sign.

Now, in two (or more) dimensions, all of that still holds:

1. The signal is a function of space, $f(\mathbf{r})$ (where $\mathbf{r}$ is vector-valued),
2. The Fourier transform takes you into a *spatial* frequency domain, a kind of "inverse space" (k-space),
3. Each function value, $F(\mathbf{k})$, tells you how much of the wave with that (spatial) frequency *and propagating in that direction (along $\mathbf{k}$)* you have.

> What can I tell about an image that it fourier transforn in (0,0) equals 0?

Following from the above, if $\mathbf{k} = \mathbf{0}$ and $F(\mathbf{k})$ = 0, then

* you have no stationary signal component.
* The "amount of unpropagating wave" in your original signal is zero.
* The average value of your signal is zero.

All of these are equivalent statements.

---
Tags: image-processing, fourier-transform, digital-image-processing
---


# Question
Title: Is the executable always loaded to the same place in the text segment?
I am reading a book about data architecture, and I am wondering about the text segment and the memory adresses.

In one example(assembly using ARM) where the code was compiled there were adresses to global variables. Does this mean that the executable is always loaded in the same place in the text segment?, so that the adresses of the variables are always the same?

# Answer
> 1 votes
One protection against hacker attacks is “address space randomisation”. Basically code is always loaded to a different address, making it harder to attack. So on a modern device it’s very unlikely to be loaded to a fixed place.

There are two methods to support this: “relocatable code” can be modified at load time to work correctly in the place where it is loaded. “Position independent code” is designed to work correctly no matter where it is loaded.

---
Tags: computer-architecture, assembly
---


title: Formal grammar of MIU system

text:
# Question
Title: Formal grammar of MIU system
The MIU system, famous from Douglas Hofstadter, is a semi-thue system with the following rules:

Xi → Xiu
mX → mXX
XiiiY → XuY
XuuY → XY

and a start axiom "mi"

I have tried to find a formal *grammar* that generates all words that can be derived from the semi-thue system, but did not succeed. Is there a canonical way to construct/derive a formal grammar from a semi-thue system? Of course it is possible to convert it somehow, because semi-thue systems and unrestricted (type 0) grammars are congruent.

Any idea how the grammar for that particular example would look like?

# Answer
As Hendrik Jan remarked, the MIU-rules as a string rewriting system is not a semi-Thue system. Each string rewriting rule in a semi-Thue system does not care about context. A step of rewriting in a semi-Thue system consists of looking for a substring $s$, removing (forgetting) $s$ and inserting $t$ for some $(s,t)$ in a binary relation. However,

* Rule $Xi \to Xiu$ can only be applied when $i$ is at the end.
* Rule $mX → mXX$ can only be applied when $X$ is at the end. When applied, the rule has to remember what has been found, $X$.

---

It turns out the the MIU system generates the following regular language as proved here. $$\\{w\in L(m\\{i, u\\}^\*)\mid \text{the number of i's in } w\text{ is is divisible by }3 \\}.$$

Here is a regular grammar for the language, where $S\_k$ corresponds to the state of having $k$ $i$'s in the string.

$S\to mS\_0$
$S\_0\to uS\_0\mid iS\_1$
$S\_1\to uS\_1\mid iS\_2\mid\epsilon$
$S\_2\to uS\_2\mid iS\_0\mid\epsilon$
> 4 votes

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


# Question
Title: Is this PDA correct or an erratum? (Sipser example 2.14)
I don’t understand this state diagram. What if $n=0$? Then our input string is the empty string. We begin at $q\_1$, push \\$ onto the string, move to $q\_2$ but then fail. So the language recognized by this PDA is $n \geq 1$. If, however, we change the label on the vertical arrow to $\varepsilon, \varepsilon \rightarrow \varepsilon$, then we *do* recognize $n \geq 0$ as required, I think?

I checked Sipser’s online errata but didn’t see anything.

# Answer
Your given is a non deterministic PDA. It can either stop at $q\_1$ or move to $q\_2$ at the start. So, for empty input, it will still accept since $q\_1$ is an accept state.
> 0 votes

---
Tags: automata
---


# Question
Title: Is there a hypothesized "complete" class of problems between P and NP-hard?
For now, assume that P != NP. Is there a "complete" class of problems between P and NP-hard, and if so, what is it called? The two key words here are

1. between
2. complete

By between, I mean that it runs in super-polynomial time (not in P), but sub-exponential time (NP-hard is believed to take exponential time or greater).

By complete, I mean that reductions exist. E.g. just like how NP-complete problems like TSP and 3-SAT can be reduced to each other, the "in-between" class of problems similarly should have reductions to each other.

As an example, integer-factorization is widely believed not to be NP-hard, but not to be in P either, so it is a perfect candidate for this class. But is there a wide range of problems that can be reduced to/from integer factorization to create a "complete" class? Or are the problems between P and NP-hard mostly disconnected?

# Answer
One could reasonably defend a Yes or No answer.

Yes: consider, e.g., the class of GI-complete problems. Similarly, for any NP-intermediate problem Q, you can define the class of problems that can be reduced to Q, and define a class of Q-complete problems, namely, those where's a reduction from them to Q and a reduction from Q to them. That class might be a bit limited, but it does exist.

No: most natural problems in NP are either in P or are NP-complete. There are a few natural problems that are of intermediate difficulty (e.g., graph isomorphism, factoring), but they don't tend to be equivalent to too many other natural problems in NP. So, while there are some problems that can be reduced to/from them, if you care about natural problems you're likely to run across in your life there isn't a "wide range" of such problems (unless we're willing to accept non-natural/artificial problems that are constructed solely for this purpose). See, e.g., https://en.wikipedia.org/wiki/NP-intermediate.
> 2 votes

---
Tags: complexity-theory, np-complete, np-hard, np, factoring
---


# Question
Title: Strategy for searching for elementary cellular automata (cyclic boundary conditions) that repeat
I am looking for elementary cellular automata rules and initial conditions that give rise to interesting cycles (Cyclic boundary conditions, such that the leftmost entry is the neighbour of the rightmost entry). After running a rule with some starting state, the state of the CA might (will?) start repeating in "cycles".

I would like to search for and record rules and initial conditions that lead to interesting cycles (Similar to what was done here. The interesting-ness of a rule+initial condition will later be determined by a few metrics specific to my application.

How should I perform the search given that the CA width/dimensionality will be high (around 100) and the cycle period should be long (500-1000)?

This is my current strategy in python-like pseudo code:

```
dimensionality = 100
trails_per_rule = 10
max_evolutions = 1000

results = [] # Container to store the interesting rules and initial conditions
For rule in all ECA rules:  # Loop though all ECA rules
    states_that_lead_to_cycles = []  # For a given rule, create an intermediate store of states that lead to cycles.
    for trail in range(trails_per_rule): # Look for cycles using several starting states
       state = random_bit_array(dimensionality) # initial state
       if state in states_that_lead_to_cycles:
          break # Don't run an evolution that you know will lead to a cycle.
       else:
          evolution_store = [state]; # Contrainer to store the evolution of states as the rule is applied
          for i in max_evolutions:
              state = evolve(rule,state) # Apply the ECA rule
              if state is in evolution store: # Check if a cycle is identified
                 results.append(initial state, rule and cycle information) # Store the interesting cycle
                 states_that_lead_to_cycles.append(evolution_store[indexes of the cycle]) # Save all states that occur in the cycle and avoid them in future runs
                  break
              else:
                  evolution_store.append(state)

```

The reasoning is that all states that are confirmed to occur in a cycle should not be investigated again, since it is known that they will lead to a cycle. Since there are too many initial conditions to perform an exhaustive search, random initial conditions are chosen.

1. Does this seem like a reasonable strategy?
2. Will all rules eventually lead to cycles since there is a finite number of states that can be taken in the evolution? Are there different cycles possible for a given rule based on what the initial condition is?
3. Should I search only through the inequivalent ECA's? How can this be done?

Any advice or critique on my understanding will be appreciated.

# Answer
Yes, all initial states under all CA rules on a finite grid will eventually lead to a cycle (or a fixed state, which can be viewed as a cycle of length 1). More generally, iterating any fixed deterministic map on a finite domain of $n$ elements from any initial value in the domain will inevitably lead to a cycle in at most $n$ steps.

However, note that the expected length of the cycle, and the number of steps needed to find it, is proportional to $n$ for a randomly chosen bijective map and to $\sqrt n$ for a random non-bijective map. While the maps generated by CA rules are *not* randomly sampled from the set of all possible maps between grid states, AFAIK the same average-case behavior still holds empirically: the average cycle length for a randomly chosen CA rule on a $k$-cell lattice with $s$ states per cell is proportional to $s^k$ if the rule is reversible (and thus generates a bijective map), and to $s^{k/2}$ if it is not.

Of course, specific rules can deviate from this average-case behavior, and it's possible that your "interesting" rules happen to have a cycle structure that differs significantly from the average. (Indeed, I already implicitly noted one example of such a class of non-average rules, namely the reversible ones.) However note that, if this is the case, it also implies that most rules are not "interesting" by your definition.

---

As for the reasonability of your search strategy, I see no reason why it shouldn't work, in the sense that it should do what you say: find rules and initial states that lead to a cycle in less than some fixed number of steps.

However, I suspect that your search method is needlessly complicated, in the sense that (at least with your sample parameter values):

* For most rules, you're unlikely to find any cycles at all (since your maximum number of search steps, 1000, is significantly lower than the average expected cycle length $\sqrt{2^{100}} = 2^{50} ≈ 10^{15}$).
* For rules where many random initial conditions do converge quickly to a short cycle, it's likely that either:

+ (almost) all patterns converge to the same final state or cycle (e.g. the all-zero state, or a cycle between the all-zero and all-one states), or
    + there are many more cycles than your trials per rule (consider e.g. Conway's Game of Life, where a typical final cycle consists of a bunch of isolated static patterns and/or low-period oscillators scattered randomly on the grid).

In either case, there's little point in trying to detect whether two random initial states converge to the same cycle: either they almost always do (and the cycle is likely short, and thus would be quickly detected anyway), or they almost never do. (That is, of course, unless determining which of these two possibilities occurs is part of what you want to investigate!)

In general, I'd only bother trying to detect collisions between cycles if your number of trials per rule, multiplied by the maximum number of steps per trial, was comparable to or higher than the square root of the number of possible lattice states (so that observing two trials converging to the same cycle was likely even for a random rule).

In particular, if you did *not* try to detect collisions between separate cycles, you could use less memory-hungry cycle detection algorithm such as Floyd's ("tortoise and hare") or Brent's algorithm. While these typically need more steps to find the cycle (by some small constant factor), they also don't require looking up and storing states in a hash table, which saves time and memory accesses. Due to their low memory usage, these algorithms are also very well suited for parallel implementation e.g. on a GPU, which could likely speed up your search by many orders of magnitude.

(Also, if you really wanted to count the number of times each distinct cycle was found, you could still do that even in a parallel implementation: just pick a distinct state — e.g. the lexicographically lowest one — from each cycle found and return it as a representative of the cycle. The just count the number of times each representative state was returned.)

---

Ps. Yes, you can save some time by searching only one representative of each class of equivalent rules, since the cycle structure of equivalent rules will be isomorphic (i.e. identical up to a relabeling of the states).

The accepted answer to the question you linked already gives Python code for finding a representative of each equivalence class of ECA rules, but the general approach is:

1. For each rule, generate all of its equivalent rules by applying all the known equivalence transformations (such as swapping the left and right neighbors, or swapping the two cell states in both the input and the output) iteratively, until no more new equivalent rules are found.
2. Pick some canonical representative out of this set of rules, e.g. the one with the lowest rule number.
3. Mark all the equivalent rules as already processed, so that you won't need to repeat the process above for each of them. (Or just don't, and remove the duplicates from the list of canonical representative rules at the end.)

Note that there's some room for ambiguity in the definition of rule equivalence. In particular, for the subset of rules that are invariant under cell state inversion, there are additional transformations (such as inverting only the output states of the rules) which generate a rule that is in some sense equivalent to the original (in that the time evolution of any pattern under the transformed rule encodes its evolution under the original rule, and vice versa) but whose cycle structure is subtly different (e.g. the all-dead and all-live states are fixed points under one of the two equivalent rules, but form a 2-cycle under the other).

Also note that, on a finite lattice, even the two basic rule equivalences (left/right reversal and cell state reversal) will only be true equivalences if the grid boundary conditions are compatible with them. A cyclic boundary (where the left side of the grid loops around and connects to the right side) is compatible with both, but e.g. an all-zero boundary is not compatible with cell state reversal, and a boundary that was all zeroes on the left and all ones the right would not be compatible with either (although it *would* be compatible with their combination).
> 3 votes

---
Tags: search-problem, cellular-automata
---


title: compute cache miss rate by given code

text:
# Question
Title: compute cache miss rate by given code
I have been trying to solve questions like this before but I have stumbled in difficulty to track the the space of the cache. so there is an example of a question like this:

Given the code:

```
int A[1024,1024],B[1024,1024],C[1024,1024]

  for(int i=0;i<1024;i++){
     for(int j=0;j<1024;j++){
       for(int k=0;k<1024;k++){
            A[i,j]+=B[i,k]+C[k,j];
     }
    }
   }

```

That runs on a proccessor with data cache that has LRU(least recently used feature of the cache) and is fully associative. the cache has total size of 32KB and each block has size of 64B. size of int is 4 bytes. arrays are placed continously on memory.

what is the percentge miss rate(approximately) of cache in this program?

what I know: when we retrieve an element from the array we also bring all the block, for example for first element in B we bring the rest 64(Bytes)/4(size of int) =16 elements to the cache and thus we will have one miss at first but for the rest(15 elements of B) we wont have a miss cause they are in the cache. for array C we go to the main memory each time because the block that was brought is not the same block to the row after it.

thank you very much in advance!

# Answer
Your cache has 512 cache lines (512 x 64Byte cache line size = 32Kilobyte cache size).

In the innermost loop, each value k accesses a different row of the array, with each row being 1024 x 4 = 4,096, so each k accesses a different cache line. You therefore access 1024 different cache lines, your processor only has 512 lines, so any cache line belonging to array C will have been evicted before it is reused. 1024 cache misses for the complete inner loop, 1024^3 all in all. Your cache is quite useless.

The accesses to B\[i, k\] read 4096 consecutive bytes for 4096/64 = 64 cache misses, so that adds 64 x 1024^2 misses, and A\[i, j\] will remain cached practically all the time.

You greatly improve this by looping

```
for (j1 = 0; j1 < 1024; j1 += 16) {
    for (k = 0; k < 1024; ++k) {
        for (j = j1; j < j1 + 16; ++j) {
            ....
        }
    }
}

```
> 1 votes

---
Tags: computer-architecture, cpu-cache, memory-access
---


# Question
Title: How to find a crticial edge in a flow network?
The complete question is as follows:

> An edge of a flow network is called critical if decreasing the capacity of this edge results in a decrease in the maximum flow. Give an efficient algorithm that finds a critical edge in a network.

I believe some variation of Ford-Fulkerson would have to be used over here, however I am not too sure. Also I am a little confused by the wording of the question. What does efficient mean? In linear time i.e. $O(|V| + |E|)$?

# Answer
By the max-flow min-cut theorem the (maximum) flow $f$ between two vertices $s$ and $t$ in the network is equal to the overall weight of the edges in a minimum $s$-$t$-cut $C$.

The means that it suffices to find a minimum $s$-$t$-cut $C$ and return any edge $e \in C$ (decreasing the capacity $e$ reduces the weight of the minimum cut and hence the flow from $s$ to $t$).

A way to find $C$ using again the relation with the maximum flow is as follows: find a maximum flow from $s$ to $t$ (using the algorithm of your choice) and let $S$ be the set of saturated edges, i.e., edges such that the flow across them matches their capacity. Choose $C$ as the set of all edges $(u,v)$ such that $u$ is reachable from $s$ and $v$ can reach $t$ in $G-S$.
> 1 votes

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


title: Pattern Matching Algorithm in Java

text:
# Question
Title: Pattern Matching Algorithm in Java
I have to write an algorithm that solves below problem statement -

1. There is a project requirement which has list of titles:- "JobTitles" : \[ "Developer", "Programmer", "Java Developer",
"Java Software Engineer", "Java Software Developer", "Application Architect", \]
2. There is a list of applicants who have titles like -

Need to find out which applicant is close to the project requirement based on scoring system.

Current logic that I have implemented is(pseudocode)-

If project\_title.eqauls(applicant.split(,).forEach(title)) applicant.score +=4

If project\_title.contains(applicant.split(,).forEach(title)) applicant.score +=2

Is there any other method to implement scoring system to find closest possible match based on the keywords of requirement and applicant job title?

Thank you!

# Answer
> 1 votes
I would go with the following program to achieve what you're looking for:

```
import java.util.*;

class Applicant {
    public String name = "";
    public List<String> titles = new ArrayList<>();
    public Applicant(String name, String... titles) {
        this.name = name;
        this.titles = Arrays.asList(titles);
    }
}

class Matcher {
    private Applicant ideal;

    public Matcher(Applicant ideal) {
        this.ideal = ideal;
    }

    private class ApplicantComparator implements Comparator<Applicant> {
        @Override
        public int compare(Applicant a, Applicant b) {
            int x = 0, y = 0;
            for(String t : a.titles) {
                if(ideal.titles.contains(t)) x += 1;
            }
            for(String t : b.titles) {
                if(ideal.titles.contains(t)) y += 1;
            }
            return x - y;
        }
    }

    public void best(Applicant... applicants) {
        if(this.ideal == null) return;
        Collections.sort(Arrays.asList(applicants), new ApplicantComparator());
        int i = 1;
        System.out.println("Ideal applicant titles: " + ideal.titles.toString().substring(1, ideal.titles.toString().length() - 1));
        System.out.println("\nMost suited in list\n|");
        for(Applicant a : applicants) {
            System.out.println("| " + (i++) + " - " + String.format("%-24s", a.name) + a.titles.toString().substring(1, a.titles.toString().length() - 1));
        }
        System.out.println("|\nLeast suited in list");
    }
}

public class Main {
    public static void main(String[] args) {
        Matcher m = new Matcher(new Applicant("<IDEAL>", "Developer", "Programmer", "Java Developer", "Java Software Engineer", "Java Software Developer", "Application Architect"));
        m.best(
            new Applicant("Shawn", "Java Developer", "Software Developer", "Java Programmer")
            , new Applicant("John", "Application Architect", "Java Programmer", ".NET Developer")
            , new Applicant("Richard", "Software Developer", "Java Programmer")
        );
    }
}

```

Output:

Ideal applicant titles: Developer, Programmer, Java Developer, Java Software Engineer, Java Software Developer, Application Architect

Most suited in list
|
| 1 - Richard         Software Developer, Java Programmer
| 2 - Shawn           Java Developer, Software Developer, Java Programmer
| 3 - John            Application Architect, Java Programmer, .NET Developer
|
Least suited in list
```

---
Tags: algorithms
---


title: Proving that $|AB| \leq |A| \cdot |B|$

text:
# Question
Title: Proving that $|AB| \leq |A| \cdot |B|$
How to prove the inequality of concatenating two languages? $|AB|\leq |A| \cdot |B|$

I know that:

Let $A,B \subseteq \Sigma^\*$ and the concatenating of $A,B$ will as following: $AB=\\{wx \mid w \in A, x \in B \\}$. Hence by definition $\forall x \in w$ will be concatenating with every word in $B$ and vice versa, and if no words are repeated we get the new language which has the length of: $|A|\cdot|B|$. And $AB$ could be less than $|A|\cdot|B|$ because some words which could be repeated are ignored like, $\\{aa,aaa\\}\in A$, and $\\{aa,a\\} \in B$ we get: $\\{aaaa,aaa,aaaaa,aaaa\\} = \\{aaa,aaaa,aaaaa\\}$.

But I'm not sure if there is more direct way to prove it just using the inequalities with some simplifications like a normal equation?

# Answer
There is a simple function $f:A\times B\rightarrow AB$ (where $A\times B$ is the cross product of two sets).

Its not hard to show that this function is also onto, and therefore $|A|\cdot |B|=|A\times B|\ge |AB|$ as required.
> 3 votes

# Answer
How about induction on languages?

**Proof**. Assume that for every subset of $A$ the statement holds. Then there are two cases to consider:

1. Suppose $A = \varnothing$. Then $|A \bullet B| = |\varnothing \bullet B| = |\varnothing| = 0 \leq |\varnothing| \cdot |B| = 0$.
2. Suppose $A = S \cup T$, for any two disjoint subsets $S$ and $T$. Then $$ |A \bullet B| = |(S \cup T) \bullet B| = |(S \bullet B) \cup (T \bullet B)| \leq |S \bullet B| + |T \bullet B| \leq \\ \leq |S| \cdot |B| + |T| \cdot |B| = (|S| + |T|) \cdot |B| = |A| \cdot |B|. $$
> 0 votes

---
Tags: formal-languages
---


# Question
Title: What role does an asterisk serve in Backus–Naur Normal Form?
Suppose that you were reading some production rules for a context-free grammar in Backus–Naur Normal Form

What does the asterisk (`*`) mean?

In the example below, what is the difference between `<fun-def*>` and `<fun-def>`?

```
<program> ::= <fun-def*> int main(void) { <block> }

<block> ::= { <var-def*> <statement*> }

<fun-def> ::= void <var-name> ( <parameters> ) { <block> }
            | <type> <var-name> ( <parameters> ) { <block> }

<var-def> ::= <type> <var-name> ;
           | <type> <var-name> { <expression> } ;
           | <type> <var-name> = <expression> ;

```

# Answer
> 2 votes
I have never seen this syntax before, but most likely, `<var-def*>` is a typo for (or unusual way of writing) `<var-def>*`. A common extension of BN is to use the `*` operator from regular expressions. In other words, `<var-def>*` represents 0 or more instances of `<var-def>`.

This does not increase the expressive power of BNF and is just syntactic sugar. Of course we could have created a rule `<var-defs> ::= | <var-def> <var-defs>` and then used `<var-defs>` in place of `<var-def*>`. But sometimes it is convenient to be able to use the more concise syntax, without having to create extra non-terminals and rules to represent repetition.

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


# Question
Title: How can we escape the pipe character in Backus–Naur Normal Form?
Suppose that you were writing down the syntax rules for something like **C++** as a context-free grammar in Backus–Naur Normal Form

How can you distinguish between the pipe character as symbol in **C++** or as a Backus–Naur symbol?

Equivalently, how would you tell whether the `|` character represented a meta-logical operator or whether it represented the or-operator in **C++**?

In **C++** vertical bars (pipe characters) are often used as the logical-or operator. An example of `|` is shown below

```
if (inside_trash.is_full() || today.is_trash_day() ) {
    outside_trash << inside_trash;
}

```

But `|` is also used as a character in Backus–Naur Normal Form

I need some code to be able to parse a file written in something close to Backus–Naur Normal Form. We cannot just stare at the production rules with a human pair of eyes and say "well, that vertical bar right there is a terminal symbol, not a meta-logical choice operator".

In the following production rules `|` is a problem for boolean operators:

```
<conditional> ::= if ( <exp> ) <optional-else-clause>

<optional-else-clause> ::=  else { <block> }

     | else if (<exp>) { <block> }
 <optional-else-clause>
     | <nothing>

<exp> ::= <func-call> | <variable> | <literal>

<func-call> ::= <infix-fuc-call> | <prefix-func-call>

<prefix-func-call> ::= foo(<exp>)

<infix-call> ::= <exp> <operator> <exp>

<operator> ::= < | > | == | != | <= | >= | <- | -> | . | &= | << | >>  | %= | *= | += | ^=  | <<= | -= | && | /= | | || |

<block> ::= <func-call>;

<literal> ::= "hello" | 42 | -23 |
            | 42.0 | 3.14159 | ...
            | 'a' | 'b' | ...
            | true | false
<nothing> ::=

```

In most computer programs, we traditionally put a backslash to the left of meta-characters, and if we want a literal back-slash we write `\\`. Is there something like a backslash escape for Backus–Naur Normal Form? Maybe `\|` is the pipe character and `\\` is backslash?

For example, in the string `"Noam Chomsky\n"` the `\n` is a line-feed character, not back-slash followed by the letter "n".

# Answer
I suggest you read up on BNF. For instance, you could start with the Wikipedia article: https://en.wikipedia.org/wiki/Backus%E2%80%93Naur\_form. Often, we put literal characters in quotes, so `"|"` represents a `|` pipe symbol in the C++ program (i.e., a terminal to be matched during grammar parsing), and `|` represents the symbol that separates alternatives on the right side of a BNF rule.

It's common for people to use BNF in an informal way that differs from person to person. Sometimes people will omit the quotes for literals (terminals), in cases where this won't cause confusion. As your question illustrates, that can cause confusion if we want to match on literal symbols like `|`.
> 1 votes

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


title: Correctness vs Proof of Correctness

text:
# Question
Title: Correctness vs Proof of Correctness
Assuming we are observing an algorithm.I am confused as to how one needs to proof correctness.

What exactly the correctness represent for a given algorithm?

And why do we have to proof correctness, in case, correctness itself describes or points out that the algorithm does exactly what we want it to do. Basically the way I understand it, and I am sure I am wrong, proof of correctness, is something like proof of proof???

# Answer
> 3 votes
I claim that this algorithm returns the integer square root of any integer in the range 1 to 1000:

```
Sqrt(int X)
  return 0

```

Is it correct ? How can you convince me that it is correct (or incorrect) ?

What about

```
Sqrt(int X)
  int Y= 1, Z= 0
  while Y != Z:
    Z= Y
    Y= (X / Y + Y) / 2

  return Y

```

---
Tags: algorithms, correctness-proof
---


# Question
Title: Given a sequence of sets, choose one element from each to get the lowest number of changes
Let $k,n \in \mathbb{N} $ and non empty sets $X\_1, X\_2, \dots, X\_n \subseteq \\{1,2,\dots,k\\}$.

Define the change counting cost function $f: X\_1 \times X\_2 \times \dots \times X\_n \to \mathbb{N}$ by $f(x\_1, x\_2, \dots, x\_n) = \sum\_{i=2}^n\delta(i)$

where $\delta(i) = 1$ if $x\_i \neq x\_{i-1}$ and otherwise $0$

How can we find $(x\_1, x\_2, \dots, x\_n) \in X\_1 \times X\_2 \times \dots \times X\_n$ which minimizes the cost function?

For example consider the sets sequence: $\\{1,2\\}, \\{2,3\\}, \\{1,3\\}, \\{2,3\\}$ a solution can be one of $(1, 3, 3, 3)$ $(2,3,3,3), (2,2,3,3)$ which have one change. this is minimal because the sets' intersection is empty and hence we can't find a zero change vector.

Is there any efficient way to solve this?

We have $k^n$ options to check in the worst case, so by brute force, we have exponential time.

I read about the Assigment problem but couldn't model it to fit it, though I'm not sure this can't be done.

# Answer
> 0 votes
For every I = 1 to n, and for every x in xi, calculate the cheapest sequence for the first I sets ending in x.

For I = 1 it is trivial, every sequence has cost 0.

To find the cheapest sequence for I+1 sets ending in x, the cost is either the cheapest sequence for I sets ending in x or the cost of any sequence for I sets ending in anything other than I, plus 1.

Total cost is the sum of (element count of set I-1, timed element count of set I).

Albert Hendrik's method is easier and faster in this case, but this method can be applied to any situation where the cost is a function of your choice in set I and your choice in set I+1. For example if the cost is the absolute difference between two numbers or something more complicated.

# Answer
> 2 votes
You can just greedily take the element of the first set that appears in the most consecutive sets (decide equals arbitrarily). That's the first element of your solution. Then do the same for the next set after those consecutive sets.

---
Tags: assignment-problem
---


# Question
Title: Time complexity for concatenating strings
I was going through this piece of code from an algorithms books and something doesn't look clear

Please ignore the spelling errors,

How does 0(x + 2x + nx) reduce to o(xn^2) ?

My analogy, assuming x is a constant 1 and n is 2 (x + 2x) == 3 assuming x is a constant 1

From the book (x2^2) == 4 assuming x is a constant 1

Am i right ?

# Answer
> How does O(x + 2x + nx) reduce to O(xn^2) ?

`O(x + 2x + nx)` will be reduced to `o(xn)`. But as your text says `O(x + 2x + ... + nx)` will be reduced to `o(xn^2)`. (So if you have `n = 5` for example you have the time complexity `O(1x + 2x + 3x + 4x + 5x)` which is equal to `O(15x)`.) The time complexity of `1 + 2 + ... + n` is `O(n^2)` (since `1 + 2 + ... + n = (n^2+n)/2`, see my comment below). But in your case every addend in the sum must be multiplied with `x`, so you have `O(x*n^2)` as final result.
> 1 votes

# Answer
The author did not say

$$x+2x+\cdots+nx=n^2x.$$

He said

$$x+2x+\cdots+nx=\frac{n(n+1)}2x$$ so that

$$x+2x+\cdots+nx=O(n^2x).$$

If you don't know the meaning of the asymptotic notation $O$, read https://en.wikipedia.org/wiki/Big\_O\_notation.

Notice that $1+2=\dfrac{2\cdot(2+1)}2$ is quite right.
> 1 votes

# Answer
Here, Big $ O $ notation refers to the asymptotic upper bound to the running time as a function of input length. A formal definition and reference can be found here. As $ n^2 $ is a satisfactory upper bound to the function $ \frac{n(n+1)}{2} $ , the running time which comes out as $ \frac{n(n+1)}{2} $ can be expressed as $ O(n^2) $
> 0 votes

# Answer
We can't say what the time complexity is, because it depends on the implementation. There is no good reason why making a copy of a string with n characters should take O(n), and not O(1). Actually, implementors of standard libraries and languages will work hard to make sure the time is O(1).

I would be reasonably sure that equivalent code in Swift would run in O (xn). At least if we replace "sentence = sentence + w" with "sentence.append(w)", and a clever compiler can do that.
> -1 votes

---
Tags: algorithms, algorithm-analysis, big-o-notation
---


title: Is Turing completeness necessary?

text:
# Question
Title: Is Turing completeness necessary?
Most programming languages are Turing complete (finite memory blah blah blah), and when we design languages this is a goal.

But is it really necessary? What algorithms do we typically use that *require* Turing completeness? And do most industry software actually require it?

Like what can't pushdown automata do?

# Answer
> 1 votes
Say that a programming language is **general-purpose** if all computable tasks can be programmed in it. It is worthwhile having such langauges, for the same reason that it is worthwhile having a universal computing machine.

Every general-purpose programming language is Turing complete, because by design it can express the Universal Turing machine.

There are **special-purpose** programming languages that are not Turing-complete. Some examples include database query languages, programming languages in proof assistants, languages that allow only limited resources to be used, etc.

# Answer
> 0 votes
You could refer to the following video, as it discusses the questions that David Hilbert asked and resolved by Gödel and Turing. https://www.youtube.com/watch?v=HeQX2HjkcNo

# Answer
> -3 votes
Turing complete means no size limits.

For the C language, it’s easy to define an implementation with language-based limits that are way beyond physical limits. So you will never have an actual machine running into the limits. But the limits are there, so C is not Turing complete.

But if the limits are so high that building a machine that runs into the limits is physically impossible, at that point Turing complete or not makes no difference.

---
Tags: computability, pushdown-automata, turing-completeness
---


# Question
Title: Pumping lemma for context-free languages: Importance of length restriction
(from 'An Introduction to Formal Languages and Automata' by Peter Linz)

What I do not understand, is why we have done our best to make sure that the condition (8.2) holds. Why is this restriction important/useful?

# Answer
The restriction is definitely useful. It provides you with an additional guarantee on the structure of the decomposition of $w$, which you can exploit in your proofs.

For example the language $L = \\{a^n b^k c^n d^k \mid n, k \ge 0\\}$ is not context-free and a possible proof using the pumping lemma is as follows: suppose that $L$ is context free, and let $m$ be its pumping length. Consider the word $w=a^m b^m a^m b^m$. The pumping lemma ensures that there is a decomposition of $w = uvxyz$ with $|vxy| \le m$, and this implies that $vxy$ cannot contain both a $a$ and a $c$, nor both a $b$ and a $d$. As a consequence $uv^2xy^2z \not\in L$, which provides the sought contradiction.

Notice that the above proof would not work without using $|vxy| \le m$, since we could pick $u=a^{m-1}$, $v=a$, $x=b^m$, $y=c$, and $z=c^{m-1}d^k$, which satisfies $uv^i x y^i z \in L$ for all $i \in \mathbb{N}$.
> 1 votes

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


# Question
Title: Recurrence relation of multiply two $n$ bit numbers
Suppose given two $n$ bits numbers $A$ and $B$. Also suppose there is a machine that compute multiply two $\sqrt{n}$ bits numbers in $O(1)$. What is time complexity of multiplying two $n$ bits number in a such case?

I think we can use divide and conquer Karatsuba algorithm such that our recursion tree will has height $\log n-\log \sqrt{n}$ but at this step I got stuck because the answer is $O(n)$.

# Answer
If you are asked to find a O(n) algorithm, that is trivial. Split each number in $n^{1/2}$ groups of $n^{1/2}$ bits, calculate n multiplications in O(n) time, and then add the n partial sums.

Actually, the whole question is a massive abuse of Big-O notation: $n^{1/2}$ multiplication is O(1) means there is a constant c depending on the implementation, such that for every large n an $n^{1/2}$ multiplication can be performed in time ≤ c. Since n is arbitrary, we can take $n = n'^2$ which means two n' bit numbers can be multiplied in O(1). Which means the original problem can be solved in O(1).
> 1 votes

---
Tags: algorithms
---


title: Is this an inversion problem?

text:
# Question
Title: Is this an inversion problem?
I understand that total inversion in a sequence is the number of swaps that need to be done, to sort the sequence. And the best approach to solve this problem is to count swaps in a merge sort of the sequence.

Now I can think of another problem whose application I need. Imagine I have two unsorted sequences with permutation P1 and P2, how do I calculate the number of swaps to make P1 have same permutation as P2. i.e Instead of using a sorted sequence as the goal of my inversion calculation how do I use an unsorted sequence with permutation P2. Thanks

# Answer
> 1 votes
You can let the sequence given by $P\_2$ be the sorted order of the elements. For simplicity let your elements be the integers $0,1..., n-1$. In this example, let $n=3$. If $P\_2 =\[1, 0,3,2\]$. Then this permutation will be interpreted as $1 \< 0\<3\<2$.

To be able to use the above idea in your problem, you can let array $Rank$ be an inverted index of size $n$. That is the indices of $Rank$ represents each element and the value of each index is the index of the elements in $P\_2$. Using the example above $Rank\[0\] =1$ while $Rank\[1\]= 0$. Now, when comparing two elements, use their value in $Rank$. With this, 1 is less than 0, because $Rank \[1\]\<Rank\[0\]$.

You can uae a hash table to represent $Rank$ in case your elements are not $0,1..., n-1$.

---
Tags: algorithms, sorting, arrays, permutations
---


# Question
Title: Complexity of the feasibility and optimization problems
Given an optimization problem $P$, if we know that this optimization problem is NP-hard, is it necessary to check the complexity of the corresponding feasibility problem, i.e. the complexity of checking if the problem admits a feasible solution? Because in the case of $P$ the problem is not always feasible.

# Answer
> 1 votes
The problem of checking whether $P$ admits a feasible solution might or might not be NP-hard (both cases are possible).

For example, if $P$ it the problem of finding a vertex cover and the goal is to minimize the number of selected vertices then $P$ is NP-hard but a feasible solutions is trivial (just select all vertices).

On the other hand, if $P$ is the problem of finding a satisfying truth assignment for a $3$-SAT formula and the goal is that of minimizing the number of asserted variables, then both $P$ and the problem of checking whether a feasible solution exists are NP-hard.

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


title: Getting started with Program Analysis

text:
# Question
Title: Getting started with Program Analysis
I'm looking for resources on getting started with program analysis.

The only book I've found on the topic is the Nielson & Nielson book.

Other than that, it seems like there are only "compiler" books where "program analysis" would be a chapter, or something along those lines.

Do people know of any other resources?

# Answer
> 8 votes
Unfortunately there aren't many textbooks on the topic. I think the best way to learn program analysis today is to survey different courses that are available, play with a few implementations and then look at a few research papers for your specific needs. What follows is a very small sampling of what's out there. Since you specifically mentioned compiler-oriented analyses were easy to find, I will not cover such material below.

**Web-based resources** These are articles that emphasise the use of static analysis outside a compilation context.

1. A Reverse Engineering Reddit discussion on program analysis has many useful links.
2. Mozilla Wiki on abstract interpretation.
3. Deploying Static Analysis, a Dr. Dobbs article by Flash Sheridan
4. A Few Billion Lines of Code Later: Using Static Analysis to Find Bugs in the Real World, Al Bessey, Ken Block, Ben Chelf, Andy Chou, Bryan Fulton, Seth Hallem, Charles Henri-Gros, Asya Kamsky, Scott McPeak, Dawson Engler in Communications of the ACM.

**University courses on program analysis**

1. Anders Møller at Arhus University teaches a course that covers object-oriented and web technology.
2. Bor-Yuh Evan Chang at University of Colorado Boulder has a foundational course that involves an OCaml implementation and a graduate course.
3. Ben Hardekopf at the University of California Santa Barbara used to have a great set of assignments, but they are no longer available online. Some students who took his course seem to have made a Python implementation available.
4. Markus Müller-Olm has a graduate course on analysis of Android.
5. Reinhard Wilhelm at the University of Sarbruecken teaches a graduate course that covers static analysis applications such as timing analysis, cache behaviour prediction, and some shape analysis.
6. Sumit Gulwani from MSR taught a nice course on statically estimating resource consumption of programs (time/memory) at the Oregon Summer School on Programming Languages.
7. Koushik Sen at the University of California at Berkeley teaches a course that focuses on bug finding and whose topics cover concolic execution and software model checking.
8. Jeffrey Foster at the University of Maryland teaches a course that covers type systems, model checking, alias analysis and a lot of the other usual material.
9. Patrick Cousot spent a year at MIT and taught a comprehensive, foundational course on abstract interpretation. The assignments include an OCaml implementation which go from concrete collecting semantics to some algorithmically non-trivial ideas.
10. A graduate course on abstract interpretation taught by some leaders in the field is a good place to catch up on even more theory.
11. Patrick Cousot taught a short course on abstract interpretation at the Oregon Summer School on Programming Languages in 2009.

**Tools to play with**

I am not listing a lot of research tools here. There are many of those but I have tried to list a few that you can download and play with to understand the area better.

1. Interproc is a very educational tool to play with to learn about numerical static analysis.
2. The Apron Numeric Abstraction library if you are really into numeric analysis.
3. Slayer is a shape analysis tool from Microsoft Research.
4. jStar is an analyzer for Java that is based on separation logic.
5. Microsoft Research has numerous groups developing numerous tools, many of which are available for download or have web-demos. I cannot list everything here and suggest you play with them.

There is a lot more, but that's probably enough to keep you busy for a while.

# Answer
> 2 votes
This field is extremely broad... look for proofs of program correctness (there are a few tools around, like Klee). Then there are all sorts of "program checkers" of varying sophistication (see for example splint or flawfinder for a sampling of the range), programs that check for "programming guidelines compliance". Even Linux' smatch falls into this category.

For dynamic tools, there are all sorts of performance/test coverage tools around, and stuff for memory checking like valgrind.

Narrow the range of interest, then drill down.

# Answer
> 1 votes
There are **two research focuses** in program analysis: `dynamic` and `static` program analysis.

To have a first taste of program analysis, I recommend to read Chapter 4, 6, 9 in the Dragon book *if you have background in compilers*.

Or if at least you know basic graphs, it would be better to follow a graduate-level course, such as MIT 6.820 and CMU 17-355/17-665/17-819.

The above are about static program analysis. **If you care more about dynamic program analysis**, program profiling is a good point to start.

# Answer
> 0 votes
Nielson and Nielson have come out with another book called Program Analysis - An Appetizer which is supposed to be much more elementary compared to Principles of Program Analysis. It might be a good starting point. You can find it here

---
Tags: reference-request, compilers, semantics
---


# Question
Title: Hopcroft's minimization algorithm produces an incorrect result for a particular regular expression
I'm writing a DFA minimizer using Hopcroft's algorithm. While testing some regular expressions, I came out with an issue in the algorithm's output relative to two particular regular expressions:

* *a(b|c)\**
* *a(b|c\*)*

P.S.: the assumption is that both regular expressions are valid, but if that's not the case please let me know, I wouldn't be able to see what's wrong.

---

The difference between the two is that the first one allows for the letters *b* and *c* to be consumed an indefinite number of times, while the second one only allows for the letter *c* to be repeated indefinitely. This makes the scanner reach an accepting state if, after reading the letter *a*, it reads *b*. That is, it should stop when reading *ab* and consider an input like *abbbb* wrong, but *acccc* correct.

Let's generate the DFA for the first regex. Accepting states are in green. The picture below shows the DFA and its minimization.

All is good, let's generate the DFA for the second regex now.

After applying Hopcroft's algorithm, it occurs to me that the result is the same. However, the minimization of the second DFA is incorrect because it also allows to repeat the letter *b* indefinitely. Did I apply the algorithm in an incorrect way, is this a side effect of that particular regular expression? I can't seem to figure out.

I followed the pseudocode found on Engineering a Compiler, 2nd edition as explained in pages 54 to 57. The graphs are generated first using Thompson's construction, then the subset construction to get a DFA and minimized using Hopcroft's algorithm.

# Answer
I suspect what happened is that you took Split to subdivide a cluster of states based on whether the successor state is accepting or rejecting, which, since the pseudocode only contemplates a binary division (wrong), is understandable.

Below is some Python code that I believe correctly implements minimization while being only somewhat more low-level than that pseudocode.

```
import collections

DFA = collections.namedtuple("DFA", ("Q", "Sigma", "delta", "q_0", "F"))

# Minimizes the given DFA. To avoid making this function more complicated, I've
# assumed that the input contains no dead states.
def minimize(dfa):
    # Input state labeling. Two states are distinguishable iff they have
    # different labels.
    labels = {q: (1 if q in dfa.F else 0) for q in dfa.Q}

    # Refine the labels until we reach a fixed point.
    while True:
        label_count = len(set(labels.values()))
        for sigma in dfa.Sigma:
            # Extend each label by the label of the successor state after sigma.
            labels = {
                q: (label, labels.get(dfa.delta.get((q, sigma))))
                for (q, label) in labels.items()
            }
            # Renumber for a compact representation. In another language, we'd
            # do these steps at the same time.
            labels = renumber_labels(labels)
        if len(set(labels.values())) <= label_count:
            # Arrived at a fixed point.
            break

    # Compute the new transition function.
    delta = {}
    for q in dfa.Q:
        for sigma in dfa.Sigma:
            q_prime = dfa.delta.get((q, sigma))
            if q_prime is not None:
                delta[(labels[q], sigma)] = labels[q_prime]

    return DFA(
        Q=set(labels.values()),
        Sigma=dfa.Sigma,
        delta=delta,
        q_0=labels[dfa.q_0],
        F={labels[q] for q in dfa.F},
    )

def renumber_labels(labels):
    label_numbers = {}
    for label in labels.values():
        label_numbers.setdefault(label, len(label_numbers))
    return {q: label_numbers[label] for (q, label) in labels.items()}

a = "a"
b = "b"
c = "c"
print(
    minimize(
        DFA(
            Q={0, 1, 2, 3},
            Sigma={a, b, c},
            delta={
                (0, a): 1,
                (1, b): 2,
                (1, c): 3,
                (2, b): 2,
                (2, c): 3,
                (3, b): 2,
                (3, c): 3,
            },
            q_0=0,
            F={1, 2, 3},
        )
    )
)
print(
    minimize(
        DFA(
            Q={0, 1, 2, 3},
            Sigma={a, b, c},
            delta={(0, a): 1, (1, b): 2, (1, c): 3, (3, c): 3},
            q_0=0,
            F={1, 2, 3},
        )
    )
)

```

Output:

```
DFA(Q={0, 1}, Sigma={'a', 'c', 'b'}, delta={(0, 'a'): 1, (1, 'c'): 1, (1, 'b'): 1}, q_0=0, F={1})
DFA(Q={0, 1, 2, 3}, Sigma={'a', 'c', 'b'}, delta={(0, 'a'): 1, (1, 'c'): 3, (1, 'b'): 2, (3, 'c'): 3}, q_0=0, F={1, 2, 3})

```
> 1 votes

---
Tags: finite-automata
---


# Question
Title: Looking for name of a priority queue data structure based on bit-boundary buckets
*(Note: cross-listed on stack overflow: https://stackoverflow.com/questions/73362856/looking-for-name-of-a-priority-queue-data-structure-based-on-bit-boundary-bucket)*

I'm looking for the name of a data structure. I came up with this idea but suspect it should already be known, and don't know what to search to find it.

This priority queue is based on putting items into buckets based on the position of the largest bit that differs between the largest dequeued priority so far, and the item's priority. Its advantage, over for example a heap, is that it tends to move events in big contiguous groups instead of one by one which gives more memory locality. Note that this priority queue requires that dequeued priorities must increase monotonically. So for example it could be used for an advancing timeline of potential events, but it couldn't be used in all situations.

---

Suppose priorities are 32 bit integers. Then the priority queue has 33 buckets, each of which is just a vector of prioritized items where the priorities in bucket k differ from the largest dequeued priority at bit position k-1 (with "-1" meaning no difference).

To enqueue an item, append it into bucket `std::bit_width(largest_dequeued_priority ^ priority_of_item)`. If the item's priority is less than largest\_dequeued\_priority, throw a "not monotonic" exception instead of enqueueing.

To dequeue an item, find the first non-empty bucket. If there is none, fail. If the first empty bucket isn't bucket 0, then advance `largest_dequeued_priority` to the minimum item priority in that bucket and re-enqueue every item in the bucket to redistribute the items to lower buckets. Now pop an item out of bucket 0 and return it as the result.

# Answer
This data structure is called a **radix heap**.
> 0 votes

---
Tags: data-structures, reference-request, priority-queues
---


# Question
Title: Is there a working O(1)-space flood fill algorithm?
This is a purely theoretical question: among the known flood fill algorithms, there is one which does not require any dynamically-sized data structures, explicit or implicit: the so-called Walk-based filling, expressed there in *structured English*, e.g.

```
...
while front-pixel is empty do
    move forward
end while

jump to START

MAIN LOOP:
    move forward
    if right-pixel is inside then
        if backtrack is true and findloop is false and either front-pixel or left-pixel is inside then
            set findloop to true
        end if
        turn right
PAINT:
        move forward
    end if
START:
    set count to number of non-diagonally adjacent pixels filled (front/back/left/right ONLY)
...

```

An attempt to implement that algorithm has revealed that while it is quite clever, it is not robust. For example, given a herringbone pattern,

```
 *********
 **   *  *
 *  *   **
 * *...* *
 *  .*.. *
 ** ..*. *
 *  *...**
 * *   * *
 *********

```

if the starting point is one of the locations marked with a period, the algorithm goes into an infinite loop.

Is there a known robust O(1)-space deterministic (apparently, it has to be mentioned) flood fill algorithm? What would be its time complexity?

# Answer
Well, *purely theoretically*... It can be done in $O(1)$ space1 using some well-known techniques, though that may be like firing a cannon at sparrows. I will describe a slightly cumbersome and overengineered, but comprehensible solution in $O(\log n)$ space1, where $n$ is the board area, and then give a link that promises a constant space solution.

1 Space complexity can be measured in *bits* or in *words*. They typically differ by the factor of $\log n$. Space complexity classes usually are defined in terms of bits, and the algorithm cited by the author is constant-space in terms of words. I will use words complexity unless stated otherwise.

---

The core idea of a log-space algorithm is to iterate through cells of a given connected component in order of decreasing shortest path distance to the starting cell. Painting cells in this order guarantees that our connected component will never split into two parts and we will eventually paint it all.

First, we show that the predicate $DistanceAtMost(s, t, k)$, defining pairs of vertices ($s, t$) in an undirected graph such that distance between $s$ and $t$ is at most $k$, is computable in $O(\log n)$ space.

$DistanceAtMost(s, t, 1)$ is trivial. For $k \> 1$, $$DistanceAtMost(s, t, k) = \bigvee\limits\_w DistanceAtMost(s, w, \lfloor k \rfloor) \wedge DistanceAtMost(w, t, \lceil k \rceil).$$

To compute the predicate for given $s$, $t$, $k$, we enumerate all intermediate vertices $w$ independently check for paths from $s$ to $w$ and from $w$ to $t$ recursively. Recursion has $O(\log n)$ depth and $O(1)$ memory is required at each level (we need to keep a counter for $w$ and remember if current recursive call is computing the left or the right part of the conjunct). Thus the predicate is computable in $O(\log n)$.

Second, we define $$DistanceIsExactly(s, t, k) = DistanceIsAtMost(s, t, k) \wedge \neg DistanceIsAtMost(s, t, k - 1).$$

Now we are ready to solve the original problem. Let $(x\_0, y\_0)$ be the initial cell. We iterate $k$ from $n$ to $1$ and, for each cell $(x, y)$, check that distance between $(x, y)$ and $(x\_0, y\_0)$ is exactly $k$ (assuming that moves are only allowed by cells of a certain color). If so, we paint $(x, y)$ with the corresponding color.

Note that painting the furthest cell will not change shortest distances to other cells, so the order of iterating through $(x, y)$ pairs does not matter.

The time complexity is $O(n^{\lceil\log n\rceil})$ for one recursion call times $O(n^2)$ for iterating through distances and cells at the outer loop, giving $O(n^{\lceil \log n \rceil + 2})$.

---

To get a constant memory algorithm (or $(O\log n)$-bit memory) we need to dive into the deep CS. There is a rather recent (2004) breakthrough result showing that ST-connectivity in undirected graphs is solvable in log-space (bits). It proves the equivalence between $L$ and $SL$ complexity classes, where $L$ is a class of problems solvable in log-space and $SL$ is a class of problems log-space reducible to $USTCON$, the problem of determining if two vertices of an undirected graph belong to the same connected component. See Wikipedia page on SL for details.

It is not obvious to me if $DistanceIsExactly$ belongs to $SL$, but we can try different approach: iterate through cells in any order and paint the cell $(x, y)$ if it is not cutpoint, that is, removing it does not introduce new connected components. Checking it is quite simple: $(x, y)$ is not a cutpoint if removing it does not change connectivity between $(x\_0, y\_0)$ and $(x', y')$ for any $(x', y')$.

Also, the authors of the mentioned paper present, as stated in the abstract,

> a way to construct in log-space a fixed sequence of directions that guides a deterministic walk through all of the vertices of any connected graph.

However, I don't know if their algorithm still works if the graph is modified during traversal.

Regarding time complexity, Wikipedia page on SL claims $64^{32} \log N$ memory and $O(n^{64^{32}})$ time for the algorithm, which is completely impractical.
> 2 votes

# Answer
This is an algorithm I came up with, so I'm not sure that is was known before. It is essentially a modification of the walk-based filling method that you mentioned. I'll give a high-level description, with possibly more details to come later.

**EDIT...Please see the edit below**

---

The idea is that we will possibly divide the original region to fill into at most 2 regions. We initially start to go clockwise around the initial fill point, although we could have just as easily gone counter clockwise. (If the original fill location is surrounded by filled pixels, we are done.) It also doesn't matter if we go to the right, left, up, or down. The main idea is that we start circling around going clockwise. So again, we are proceeding around the original fill pixel:

```
**********
*        *
*  432   *
*  501   *
*  6     *
*        *
**********

```

Here I numbered the starting position with a 0 and numbered the next selections in increasing order.

The trick is that the algorithm will most likely have to cut itself off:

```
**********
*    3   *
*  **21  *
*  ***0  *

```

When it gets to position 3, notice that we've split the original region into 2 regions that both need to be filled. So we will mark the split with an "o", and continue, knowing that we now need to fill 2 regions:

```
**********
*  543o  *
*  **21  *
*  ***0  *

```

Eventually, we will either come to another split, or we will completely fill one of the regions (in this case, the region on the left).

If we completely fill one of the regions, we can then continue to fill, starting at the point we marked "o". Otherwise, we come to another split. The idea is to record the last few positions we were at as we go along. Now that we've come to another split, we backtrack to where there was no second split, and mark this location as the next location to work on. Then, we go back to the first marked location, and continue on.

The essential idea is that we go back and forth between the 2 regions, making sure that we never create a third region to fill.

---

**EDIT**

The idea is instead to continually circle around clockwise, trying to fill locations whenever they do not divide the current region into 2 regions.

So, for example, consider the following image, where we start at "0" and fill in the numbers in order:

```
**********
*        *
*  456   *
*  .01   *
***.32   *
*        *
**********

```

Here we skip the locations marked with a period, because they have the potential of splitting the region into two regions. We take care to proceed along the inside wall. So to continue with this example, we would fill:

```
**********
*        *
* a4567  *
* ..018  *
***.329  *
*  ....  *
**********

```

Note that once we get to 9, we stay to the inside, proceeding clockwise, over the periods, and skip some more periods. *We do not fill the periods*. We eventually arrive at "a" where we again fill.

There's another thing that we have to do. Proceeding again as in our example, we fill:

```
**********
* ...... *
* a4567b *
* ..018c *
***.329d *
*  ....  *
**********

```

Here we've skipped and then filled "b", "c", and "d". Next we come to a location that we will not fill. The logic here is that any time we come to a location that we do not fill, we record that position. Then, if we continue cycling through the unfilled positions and we come to this recorded or marked position, we know that the area surrounding area is only one pixel wide.

We now continue clockwise around the filled region, not filling anything, but seeing if there are any forks or branches where there is more than one direction to fill. If there is, we:

1. Go through the branch, away from the current region we were cycling through, still without filling anything.
2. We mark or record where we start in this new region.
3. Cycle clockwise in this new region, seeing if there is anything to fill.
4. If there is, and it doesn't split the region, we fill it.
5. Finally, we cycle through until we again arrive at the marked region.
6. We mark the other branch, so that we will come back to it.
7. We then proceed to fill the original fork we took, so that it does not split the region into two regions.
8. We go back to the second region we marked, which is the other fork.
9. Repeat until there are no more forks, then fill the rest.

If there were no forks around our recently filled region, we fill the remaining pixels and we are done.

This procedure should ensure that there are never more than 2 regions to fill.

---

This should work. Of course, there's a lot of details to keep track of.
> 0 votes

---
Tags: algorithms, graphics
---


# Question
Title: proof of non Turing-computable function g
In one of my lessons about turing machines I have been taught that the function g is not computable: \begin{cases}g(n)=f\_{n}(n)+1 & \text { if } f\_{n}(n) \text { is defined } \\ g(n)=1 & \text { if } f\_{n}(n) \text { is undefined }\end{cases}

Proof:
If $g$ is computable, then it can be computed by some Turing machine. Assume it's encoding is $k$. $$ \begin{cases}g(k)=f\_{k}(k)+1 & \text { if } f\_{k}(k) \text { is defined } \\ g(k)=1 & \text { if } f\_{k}(k) \text { is undefined }\end{cases} $$ but both are not equal to $f\_{k}(k)$ so the function g can not be computable. My teacher also made some sort of table and talked about diagonalization, but I couldn't follow the proof at all. Could someone explain this proof to me in detail?

# Answer
> 2 votes
#### Assign an integer to each Turing machine.

First, we fix an encoding scheme (or method) for all Turing machines (of some fixed kind, such as the one defined here) that encodes each Turing machine into a string of 0s and 1s. This string is interpreted as a positive integer in binary form.

Hence each Turing machine corresponds to an integer. Conversely, a positive integer may correspond to a Turing machine. For a positive integer $n$, if $n$ corresponds to a Turing machine, use $f\_n$ to denote that Turing machine. Otherwise, $f\_n$ is undefined.

#### Diagonalization

$$\text{For all }n\in\mathbb N,\ g(n)=\begin{cases}f\_{n}(n)+1 & \text { if both } f\_{n}\text{ and }f\_n(n) \text { are defined,} \\ 1 & \text { otherwise.}\end{cases}$$

The statement above defines a function $g$ from $\mathbb N$ to $\mathbb N$.

#### Why is $g$ not computable?

For the sake of contradiction, suppose $g$ is computable.

Then $g$ can be computed by some Turing machine. Assume that Turing machine is encoded as positive integer $k$. That is, that Turing machine is $f\_k$.

What is the value of $g$ at $k$? Since $g$ is computed by $f\_k$, $g(k)=f\_k(k)$.

On the other hand, replacing $n$ by $k$ in the definition of $g$, we have

$$g(k)=\begin{cases}f\_{k}(k)+1 & \text { if both } f\_{k}\text{ and }f\_k(k) \text { are defined,} \\ 1 & \text { otherwise}\end{cases}$$ There are two possible cases.

* Both $f\_{k}$ and $f\_k(k)$ are defined.
Then $g(k)=f\_k(k)+1$, which is not equal to $f\_k(k)$.
* Otherwise, $f\_k(k)$ is undefined (that is, the Turing machine that computes $g$ does not halt when the input is $k$).
Then $g(k)=1$, which is not equal to $f\_k(k)$ since $f\_k(k)$ is undefined.

So in all cases, $g(k)\not=f\_k(k)$, which contradicts the fact that $g(k)=f\_k(k)$. This contradiction shows our assumption, $g$ is computable must be wrong.

#### Where does the trick come from?

We want to construct/describe/define a function $g$ that is not computed by any Turing machine.

More explicitly, for each Turing machine, we want to do two things:

* find a number
* describe the value of $g$ at that number so that the value is different from the output of that Turing machine given that number as input.

A simple approach is to use the same number always, say $2022$ or $152866$. However, whatever value we let $g(2022)$ or $g(152866)$ be, there is a Turing machine that outputs $g(2022)$ given $2022$ as input (and outputs $g(152866)$ given $152866$ as input).

The idea is to find a different number for each different Turing machine.

For a Turing machine and the corresponding number, we will let $g$ at that number be any value that is different from the output of that Turing machine. For example, $g(k)=f(k) + 153595$. For example, $g(k)=f(k)^2 + 42$. If $f$ does not halt on $k$, $g(k)=91753$. The viable options are endless.

(Of course, we can also choose $g(k)=f(k)+1$ if $f$ halts on $k$ and $g(k)=1$ if $f$ does not halt on $k$.)

How can we find a different number for each different Turing machine? The encoding number of a Turing machine!

#### Exercises

Exercises 1. Function $h$ defined below is not computable. $$\text{For all }n\in\mathbb N,\ h(n)=\begin{cases}2^{f\_n(n)} & \text { if both } f\_{n}\text{ and }f\_n(n) \text { are defined,} \\ 3 & \text { otherwise.}\end{cases}$$

Exercises 2. Any function $s$ that satisfies the condition below is not computable. Note that there is no requirement of $s(n)$ when $n$ is not a square number. $$\text{For all }n\in\mathbb N,\ s(n^2)=\begin{cases}2f\_n(n^2) & \text { if both } f\_{n}\text{ and }f\_n(n^2) \text { are defined,} \\3n + 14043571 & \text { otherwise.}\end{cases}$$

---
Tags: turing-machines, computability, undecidability
---