# Question
Title: Returning $k^{th}$ smallest number in $m$ sorted arrays
*Given $m$ sorted arrays $A\_1,A\_2,\dots,A\_m$, also $\mid A\_i\mid=n$ for each $i=1,2,\dots,m$. How we can compute $k^{th}$ smallest number in union of $A\_i$s (i.e. $\cup\_{i=1}^nA\_i$) in at most $O(m\log mn)$?*

$I.$ If I use Minheap to find $k^{th}$ element, th running time will be $O(m+k\log mn)$, so that $k$ can be $O(nm)$ so this idea is not the case.

$II.$ I try to use divide and conquer approach as follow:

a. Divide $m$ sorted arrays into two equal halves.

b. find $k^{th}$ in first half and second half.

at this stage I get stuck and have no idea, however, I prefer to find out some hints not complete solution.

# Answer
### Can we just use the median of medians of these arrays?

One strategy is to find the median of medians of these arrays, name it $x$. At least $T/4$ elements are less than $x$, and at least $T/4$ elements are greater than $x$, where $T$ is the number of all elements. If $k\<T/2$, we can delete those $T/4$ elements that are greater than $x$; if $k\ge T/2$, we can delete those $T/4$ elements that are less than $x$. Then recur.

However, this strategy does not work by itself. It turns out that not a single element can be removed without further information.

Here is an example. Consider the sorted row arrays below, where we have $49$ numbers. Suppose we are asked to find $23$-th smallest element. $$\begin{matrix} &a\_1:= &(1,&1,&1,&2, &13,&13,&13)\\ &a\_2:= &(1,&1,&1,&3, &13,&11,&13)\\ &a\_3:= &(1,&1,&1,&4, &13,&11,&13)\\ &a\_4:= &(1,&1,&1,&5, &13, &13,&13)\\ &a\_5:= &(1,&1,&1,&6, &7, &8, &9)\\ &a\_6:= &(10,&10,&10,&11, &13,&13,&13)\\ &a\_7:= &(10,&10,&10,&12,&13,&13,&13) \end{matrix}$$

Since $23\<49/2$, we will remove each element that is greater than the median in its respective array if that median is greater than the median of median of all arrays.

The median of the medians $2,3,4,5,6,11,12$ is $5$. Since array $a\_5$ is an array with median $6$ that is greater than $5$, we will remove $7, 8, 9$ in it. However, $9$ is the $23$-th smallest elements of all elements, the wanted element.

---

However, all are not lost. Dmitry provides the following remedy. "Given the median of the medians, you can determine whether its rank is greater or less than $k$ (by determining its rank in every sorted array using binary search). If it's greater than $k$, you delete all the elements which are greater than it (similarly if it's less than $k$)." With some further tweaking , we could arrive at an algorithm that runs in $O(m\log n\log (mn))$ time.

### The ideas

For simplicity, I will be ignoring off-by-one errors and treating some fractions as if they were integers from time to time. A rigorous and working implementation will be provided later.

Imagine the algorithm will run some logic repeatedly, removing elements that are not possible to be the $k$-th smallest number in each round. After each round, $k$ will be updated accordingly.

##### One round of removal

We want to remove as many element as possible in each round. However, it is either impossible or too slow to remove at least one element from each array or remove a constant number of elements from each array. Instead, we should accomplish in each round,

* select a significant portion of arrays
* remove a significant portion of elements at front or at back from each selected array (what remain of each array is a subarray of the original array).

Assume $k\>T/2$, where $T$ is the number of remaining elements. The plan for the other case, when $k\le T/2$ is symmetric.

Each array $\overline A\_i$ can be viewed as $\frac23|\overline {A\_i}|$ elements above $pivot\_i$ and $\frac13|\overline {A\_i}|$ elements below $pivot\_i$, where $\overline {A\_i}$ is the subarray of $A\_i$ that consists of the remaining elements in $A\_i$ while $pivot\_i$ is the $\frac13|\overline {A\_i}|$-th smallest element in $\overline {A\_i}$. Elements that are equal to $\overline {A\_i}$ are not mentioned since they will be treated as if they were above or below $pivot\_i$ appropriately.

We then collect the pair $(pivot\_i, |\overline {A\_i}|$) for all arrays.

We can adapt a linear selection algorithm to select the "$T/5$-th" smallest pivot, named it $J$, treating each pair $(pivot\_i, |\overline {A\_i}|$) as representing $|\overline {A\_i}|$ elements of value $pivot\_i$, where $T=\sum\_i|\overline {A\_i}|$, the total number of remaining elements. Since there are at most $m$ pairs of $(pivot\_i, |{\overline {A\_i}}|)$, we can select $J$ in $O(m)$ time.

For each $pivot\_i\le J$, remove all elements in $\overline{A\_i}$ that are below $pivot\_i$. Since $\frac45T\cdot\frac23=\frac8{15}T\>\frac T2$ elements that are above $J$ remain and all removed elements are smaller than $J$, the $k$-th element must have not been removed! Note the removal of elements in one array takes $O(1)$ time; all we do is to increase the index in $A\_i$ of the first element of $\overline {A\_i}$ by $\frac{|\overline {A\_i}|}3$.

One round of removal can be done in $O(m) + O(m) + m O(1)=O(m)$ time. It removes $\frac T5\cdot\frac13=\frac T{15}$ elements.

##### $O(\log mn)$ rounds of removal

The number of all elements is $mn$ initially.

Since $\frac1{15}$ of all remaining elements are removed in each round, after $O(\log mn)$ rounds, the number of remaining element would be reduced to $O(1)$, ideally. However near the end of this process when there are less than $15$ remaining elements in an array, the off-by-one errors and mistreated fractions might not be ignored. In the end, we end up with less than $15m=O(m)$ elements. ($15$ might be reduced; however, we need just a constant.)

Then we will use a linear selection algorithm to find the $k$-th element.

##### The total running time is $O(m)O(\log mn) + O(m)=O(m\log mn)$.
> 3 votes

---
Tags: algorithms
---


# Question
Title: If $L^*$ or $L^+$ is empty, can L be an infinite language?
I have to prove or disprove the implications in these two situations

1. $L^\* = \emptyset$ $\rightarrow$ $L$ is infinite
2. $L^+ = \emptyset$ $\rightarrow$ $L$ is infinite

Here are my thoughts.

1. I would say Kleene star operation (\*) is union of

$\qquad L^0 \cup L^1 \cup L^2 \cup \dots$

and since $\\\_^0 = \\{\epsilon\\}$ (even $\emptyset^ 0 = \\{\epsilon\\}$), there is no language $L$ such that $L^\* = \emptyset$.

How to prove finiteness/infiniteness?
2. Only language $L$ where $L^+ = \emptyset$ is $\emptyset$ which is a finite language. But how to prove there is no other language that is inifinite and the argument is valid for it?

---

EDIT: will it help if I rewrite the implications $A \rightarrow B$ to $\neg B \rightarrow \neg A$ ?

1. $L$ is finite $\rightarrow$ $L^\* \neq \emptyset$
2. $L$ is finite $\rightarrow$ $L^+ \neq \emptyset$

2) can be now interpreted as $\emptyset^+ = \\{\epsilon\\}$ and $\emptyset$ is a finite language. So the implication doesn't work.

# Answer
1) You need to take a look at this page. Remember that there is an *implication* to be proved true or false.

2) Consider the fact $L \subseteq L^{+}$ and apply it to the case $L^{+} = \emptyset$.
> 3 votes

# Answer
You have to *prove or disprove*.

L\* *always* contains the empty string and is therefore not empty. "L\* is empty" is a false statement. Anything follows from a false statement. So yes, if L\* is empty (which it cannot be) then L is infinite. L is also finite. And empty. And anything else, and all at the same time.

Let L be a language containing at least one string s. Then L+ contains s and is not empty. But if L is empty then L+ is empty. Therefore is L+ is empty, L is empty. And "L+ is empty" is possible, therefore "L+ is empty" implies L is empty, and it implies that L is not non-empty and definitely not infinite.
> 0 votes

---
Tags: formal-languages, finite-sets
---


title: prove $a^nb^nc^m; n,m \geq 0$

text:
# Question
Title: prove $a^nb^nc^m; n,m \geq 0$
I proved this language $L = a^nb^nc^m; n,m \geq 0$ is not regular the following way:

Let $L \cap a^\*b^\* = a^nb^n$

We know that $a^nb^n$ is not regular, and $a^\*b^\*$ is regular. Thus, if $L$ is regular, then $a^nb^n$ is too, but since the latter is not, $L$ is not. Is that safe to have as a proof?

# Answer
> 0 votes
What you wrote is a proof. If this is course work someone might claim it didn't use the pumping lemma - zero points for a perfectly fine proof.

There is a general version of the pumping lemma. Instead of having a string w and splitting it into w = xyz you can have a string uwv and split it into uxyzv with the same conditions for w and xyz; the usual pumping lemma is just the special case u = v = empty. You can use that by setting u = empty, v = c^m. So any set of substrings of a regular language must also fulfil the pumping lemma (such a set is not necessarily a regular language, but it must fulfil the pumping lemma).

This allows you to drop the $c^n$ components. An extreme example, if for every n ≥ 0 L contains a string with a substring $a^n b^n$ then L is not regular. Or if for infinitely many n ≥ 0 L contains a string with a substring $a^x b^y$ with x, y ≥ n, then L is not regular.

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


# Question
Title: Prove $a^nb^{n^2+n}$ is not regular by the pumping lemma
I want to prove this language $L=\\{a^nb^{n^2+n}:n\in\Bbb N\\}$ to be nonregular by the pumping lemma. This is my attempt, is this a correct way of doing it?

Let's suppose $L$ is regular. Let $s = a^kb^{k^2+k}$ such that $k \geq 0$ as a pumping length. So we have $s \in L$ and $|s| \geq k$.

Then, by the pumping lemma, $\exists s = xyz$ such that

1. $|xy| \leq k$,
2. $|y| \> 0$,
3. $\forall i \in \mathbb{N}, xy^iz \in L$.

Since $|xy| \leq k$ and $|y| \> 0$, then $x = a^\alpha$, $y = a^\beta (\beta \> 0)$, $z = a^{k - \alpha - \beta}b^{k^2+k}$, so $xy^iz = a^{k + i \beta - \beta}b^{k^2+k}$

Now, $$xy^iz \in L \iff (k+i\beta-\beta)^2 + k = k^2+k \tag{E}$$

To complete the proof I need to find a way to remove $k$ from the equation, and find $i$ such that $xy^iz \notin L$, but the simplification of equation $(E)$ is not easy, so I did the following simple way:

Let $k = 1$, so $s = abb$, we have $|s| \geq 1$, now, as $|xy| \leq k=1$ and $|y| \geq 1$, that means $y =a$, so $xy^iz = a^ibb$, and so for $i=2$ $xy^iz \notin L$, thus, $L$ is not regular.

However, I am not sure of the last step. Is it OK to let $k=1$?

# Answer
> 0 votes
Your proof is not correct when you "let $k=1$". You cannot choose the pumping length $k$ when you are using the pumping lemma to prove a language is not regular. For example, your proof does not exclude the possibility that $L$ could be regular with pumping length $2$.

Using the pumping lemma method to prove a language $L$ is nonregular is a turn-based game against an adversary:

1. The adversary chooses an integer $p$.
2. You come up with a word $w \in L$ of length at least $p$.
3. The adversary splits the word into $w = xyz$, where $|xy| \leq p$ and $|y| \geq 1$.
4. If you come up with an integer $i$ such that $xy^iz \notin L$, you win.

If it can be demonstrated that you can win this game **no matter what the adversary does**, then $L$ is not regular.

Let me show how you can always win the game.

1. The adversary chooses $p$.
2. You come up with $w=a^pb^{p^2+p}\in L$.
3. The adversary split the word into $xyz$, where $|xy|\le p$ and $|y|\ge1$.
4. You come up with $xy^2z$.
$|xy^2z|=|w| + |y|= p^2+2p+|y|$, where $1\le|y|\le|xy|\le p$.
Since the length of $xy^2z$ is strictly between the lengths of two adjacent words, $a^pb^{p^2+p}$ and $a^{p+1}b^{(p+1)^2+(p+1)}$ in $L$, $ xy^2z\notin L$.

You have won the game.

---

Here is another way that uses string homomorphism and Myhill–Nerode theorem instead.

Assume $L$ is regular. Let $\sigma$ be the string homomorphism such that $\sigma(a)=\epsilon$ and $\sigma(b)=b$. Then $\sigma(L)=\\{b^{n^2+n}:n\in\Bbb N\\}$ is regular, too.

However, for any $0\le i\<j$,

* $b^{i^2+i}b^{2(i+1)}=b^{(i+1)^2+(i+1)}\in L,$
* $b^{j^2+j}b^{2(i+1)}=b^{(j+1)^2+(j+1)- 2(j-i)}\notin L.$

That is, each one of all infinitely many words of form $b^{i^2+i}$ belongs to a different Myhill–Nerode class w.r.t. to $\sigma(L)$. Myhill–Nerode theorem tells us that $\sigma(L)$ is not regular. This is a contradiction.

# Answer
> 0 votes
The general pumping lemma tells us that any language L' which is a set of substrings of strings in L must fulfil the pumping lemma for L to be regular (L' need not be regular but must fulfil the pumping lemma). Every string $a^n b^n$ is a substring of a string in L, the language L' = $a^n b^n$ has often been proved irregular because it doesn't fulfil the pumping lemma, therefore L is not regular.

(Careful: We don't prove that L' is irregular. We prove that it doesn't fulfil the pumping lemma. So L' being irregular proves nothing, it is the fact that the pumping lemma doesn't apply to L' which proves that L is not regular).

(Note: The proof for the general pumping level is basically the same as for the normal pumping lemma).

General rule: If for every n ≥ 0 $a^n b^n$ is a substring of some string in L, then L is not regular.

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


# Question
Title: regular languages under intersection and union, a bit of confusion to clarify
Let's assume that $L\_1 = a^nb^{2n}$ and $L\_2 = a^na^{2n}$, knowing that $L\_1$ is not regular, and $L\_2$ is. We also know that regular languages are closed under intersection and union, and complement. What can we say about $L\_3 = L\_1^\complement$ and $L\_4 = L\_2^ \complement$?

It seems correct to say $L\_4$ is regular, because $L\_2$ is, but since $L\_1$ is not regular, can we say about $L\_3$ the same?

Also, let's assume we have two irregular languages $L\_5$ and $L\_6$, can we say about their intersection and union as being irregular as well?

# Answer
Since $L\_3$ is the complement of $L\_1$, $L\_1$ is likewise the complement of $L\_3$. If $L\_3$ was regular, what would that imply regarding the regularity of $L\_1$?

For $L\_5$ and $L\_6$, consider for example the case where the two languages are each others' complements. Can you determine what languages result from the union and intersection of a language and its complement? Are these languages regular?
> 0 votes

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


# Question
Title: Determining all pixels of a specific color directly bordering on another color
I need a data structure/algorithm to efficiently retrieve borders and update changes.

There may be many (unconnected) regions of the same color. The shape of regions changes frequently over time and pixels may be randomly inserted - although most changes happen along the borders.

In this case, a pixel borders another if it is directly above, below, or to the left or right of it (Von Neumann neighborhood).

The lookup is as follows: retrieve all pixel coordinates with value Y that are neighbors of pixels with value X

Example: requesting all blue pixels bordering red pixels should return a list of pixels coordinates, here indicated in white:

So far I have tried the naive approach of checking every pixel, and then checking its neighbors if it is the required color, but this is too slow. I then changed to using a quadtree with a hierarchy of counters to avoid checking quads that do not contain either of the colors, but I feel this is still not the best solution. I have also tried using a bidirectional dictionary that maps values \<-\> coordinates, but this has been slower than the quadtree.

Edit: Using a better bidirectional directionary implementation, I can achieve about the same speed as the quadtree variant.

# Answer
> 0 votes
I solved this by saving, in addition to the map\[y\]\[x\] -\> color multidimensional array, a defaultdict(lambda : defaultdict(dict)) map, which maps from color -\> \[True, False\] -\> (Coordinates -\> True).

dict\[color\]\[True\] contains all coordinates which lie on a border (to either unclaimed or other color values), and so have to be checked when trying to find out borders, and dict\[color\]\[False\] maps to all coordinates that are surrounded only by their own color (or, in my special case, "unreachable" regions). These can be skipped when trying to search for neighboring pixels of a different color.

The last value is irrelevant, I only use a dictionary there to check if a coordinate is in there in O(1).

When setting a pixel, in addition to updating the map, all its four surrounding neighbors are checked if they have the same value, and if they do, the coordinate is saved in the dictionary\[color\]\[False\] map, otherwise in dictionary\[color\]\[True\]. Also, importantly, the same is done for all four neighbors themselves, because from their perspective, a value (may) be changing.

---
Tags: algorithms, graph-traversal, image-processing
---


# Question
Title: Two statements about optimal binary search trees
This is a paragraph from the book *CLRS*:

> What we need is known as an optimal binary search tree. Formally, we are given a sequence $K = (k\_1, k\_2, ..., k\_n)$ of $n$ distinct keys in sorted order (so that $k\_1 \< k\_2 \< ... \< k\_n$), and we wish to build a binary search tree from these keys. For each key $k\_i$, we have a probability $p\_i$ that a search will be for $k\_i$. Some searches may be for values not in $K$, and so we also have $n + 1$ “dummy keys” $d\_0, d\_1, d\_2, d\_n$ representing values not in $K$. In particular, $d\_0$ represents all values less than $k\_1$, $d\_n$ represents all values greater than $k\_n$, and for $i = 1, 2, ..., n - 1$, the dummy key $d\_i$ represents all values between $k\_i$ and $k\_{i + 1}$. For each dummy key $d\_i$, we have a probability $q\_i$ that a search will correspond to $d\_i$. Figure $15.9$ shows two binary search trees for a set of $n = 5$ keys. Each key $k\_i$ is an internal node, and each dummy key $d\_i$ is a leaf.

Now, looks like, without loss of generality, *CLRS* has restricted itself to (optimal) binary search trees whose leaves are dummy variables (and whose dummy variables are leaves). This suggests that one of these two statements must be true:

1. In any optimal binary search tree the leaves are the dummy variables and the dummy variables are leaves.
2. There exists some optimal binary search tree whose leaves are dummy variables and whose dummy variables are leaves. (and *CLRS* is going to find one of such trees in the following paragraphs. This tree might even be unique.)

The following paragraph also suggests that one of the previous statements must be true:

> As with matrix-chain multiplication, exhaustive checking of all possibilities fails to yield an efficient algorithm. We can label the nodes of any $n$-node binary tree with the keys $k\_1, k\_2, ..., k\_n$ to construct a binary search tree, and then add in the dummy keys as leaves. In Problem $12-4$, we saw that the number of binary trees with $n$ nodes is $\Omega(\frac{4^n}{n^{}\frac{3}{2}})$, and so we would have to examine an exponential number of binary search trees in an exhaustive search. Not surprisingly, we shall solve this problem with dynamic programming.

Which one is true? I strongly believe the second one is true.

# Answer
> 1 votes
I am afraid you put the cart before the horse sort of. It is not a question about which statement is true. Both statement do not make much sense since those dummy variables/leaves for them are not part of the binary search tree.

The dummy variables are used to represent the situations when "some searches may be for values not in $K$". At the time when we design/create/modify a binary search tree, no such "dummy variables" are included. Once we have a binary search tree, for the sake of explaining how a search might end up with, those dummy variables are "added". They can only appear as leaves by the definition of a binary search tree.

In other words, there are two trees. One is the binary search tree. The other tree is the tree of all possible search results on that binary search tree. The latter tree is completely determined by the former tree.

For the sake of brevity, the authors **choose to use one tree to represent those two trees**.

---
Tags: optimization, binary-search-trees
---


# Question
Title: How to solve linear equation with binary tree
I'm working on a school project that takes in a simple linear equation and has to return the value of $x$. The code I have transforms $x + 3 = 3x - 2$ into a binary tree format like so:

```
        =
      /   \
     /     \
    +       -
   / \     / \
  x   3   *   2
         / \
        3   x

```

With the expression in this format could someone please explain how can I obtain the value of $x$.
Any help is appreciated - if you have an alternative method that may make it easier I'd love to hear it.

# Answer
> -3 votes
For solving this question you should assume a tree with '=' root And in the left side of root push factors of x and in the right side push your constant values, now variable x is equal to sum of right side division by left side.

# Answer
> 2 votes
The solution of

$$ax+b=cx+d$$ is $$x=\frac{d-b}{a-c}.$$

Unless you want to handle other types of equations (but you don't explain), this is the general case.

# Answer
> -1 votes
https://www.cs.utexas.edu/users/novak/algebra.pdf

Here is a link to a university article on a similar equation

# Answer
> -2 votes
This is nothing but a $parse$ $tree$ of your expression. Now coming to your question, you cannot actually obtain something from any parse tree. Parse trees are used in an abstract concept in compilers (to be exact they are the output of syntax analysis phase of a compiler). What you can do, or your software can do is that, u can first simplify the equation like--\>

$x+3=3x-2$

$=\>2x=5$

$=\>x=5/2$

Now u can design a parse tree for the same, like

---
Tags: data-structures, binary-trees
---


# Question
Title: prove $a^nb^m; n<3m + 2$ is not regular by the pumping lemma
I want to prove this language $a^nb^m; 0 \leq n\< 3m+2$ to be not regular by the pumping lemma. This is my attempt, is this a correct way of doing it?

Let's suppose $L$ is regular. Let $s = a^{3k+1}b^{k}$ such that $k \geq 0$ as a pumping length. So we have $s \in L$ and $|s| \geq k$.

Then, by the pumping lemma, $\exists s = xyz$ such that

1. $|xy| \leq k$,
2. $|y| \> 0$,
3. $\forall i \in \mathbb{N}, xy^iz \in L$

Since $|xy| \leq k$ and $|y| \> 0$, then $x = a^\alpha$, $y = a^\beta (\beta \in \mathbb{N}^\*)$, $z = a^{3k+1 - \alpha - \beta}b^{k}$, so $xy^iz = a^{3k +1 + i \beta - \beta}b^{k}$

Now, $xy^iz \in L \iff 3k +1 + i \beta - \beta \< 3 k + 2\iff \beta(i-1) \< 1$, and so $xy^iz \notin L \iff \beta(i-1) \geq 1$, which is true for $i = 2$. Thus, as this is in contradiction with the third assumption of the pumping lemma, $L$ is not regular.

# Answer
> 0 votes
There are two quite general classes of languages that don’t fulfil the pumping lemma: (1) a^n where n is an element of an infinite set with arbitrary large gaps between set elements. (2) a^n b^n for n \>= 0.

And the generalised pumping lemma says: If L is regular then any set of substrings of elements of L fulfils the pumping lemma.

This solves practically all problems posted here very quickly. Every string a^n b^n is a substring of some string of your language, so by the generalised pumping lemma and (2) the language is not regular.

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


# Question
Title: Finding the best algorithm for nearest neighbor search in a 2D plane with moving points
I am looking for an efficient way to perform nearest neighbor searches within a specified radius in a two-dimensional plane. According to Wikipedia, space-partitioning data structures, such as :

* k-d trees,
* r-trees,
* octrees,
* quadtrees,
* cover trees,
* metric trees,
* locality-sensitive hashing,
* and bins,

are often used for organizing points in a multi-dimensional space and can provide O(log n) performance for search and insert operations. However, in my case, the points in the two-dimensional plane are moving at each iteration, so I need to update the tree accordingly. Rebuilding the tree from scratch at each iteration seems easier, but I would like to avoid it if possible because the points only move slightly between iterations.

I have read that k-d trees are not naturally balanced, which could be an issue in my case. R-trees, on the other hand, are better suited for storing rectangles. Bin algorithms, on the other hand, are easy to implement and provide near-linear search performance within local bins.

I am working on an autonomous agent simulation where 1,000,000 agents are rendered in the GPU, and the CPU is responsible for computing the next movement of each agent. Each agent is influenced by other agents within its line of sight, or in other words, other agents within a circular sector of angle θ and radius r.

Given these considerations, what would be the best algorithms for my use case?

# Answer
I expect that nearly every data structure offers a way to update a particular value stored in the data structure.

For instance, with an quadtree, if the position of a point changes slightly, you can look its prior position in the data structure, check whether the new position lies within the same cell, and if not, traverse up the tree (to the parent, grandparent, etc.) to find the first region that contains the new position, and then traverse downward from there. If the point has moved only a little bit, that may be faster than deleting the old location and inserting the new location, or building a new quadtree from scratch.

I expect that a similar method can be applied to any space-partitioning tree.

I would suggest that you try implementing each of the standard data structures, with this refinement for updating positions that are already in the data structure, and evaluate how well each works on your dataset/workload. That should tell you which works best. If any more specific question arises out of that, you will be in a good position to ask a more focused question here.
> 1 votes

---
Tags: algorithms, optimization, nearest-neighbour
---


# Question
Title: Kolmogorov complexity and data compression revisited
The question of the relationship between Kolmogorov complexity and data compression is rather difficult. However, at the heuristic level, the complexity of an object and the rate of its compression by known algorithms *are related*.
I used the built-in function Compress\[\] of Mathematica to estimate the compression ratio of various data reducing to a character string.
*Not for the entire string*, but rather gradually, observing how the compression ratio changes with the growth of data volume.

Here's what happened with: Pi digits, some text, Thue-Morse sequence, differences between primes and built-in RNG:

I believe that a significant estimate of data complexity isn't just degree of compression of a whole data, but the parameters of changing it with increasing data length.

But to get these parameters (by fitting eg), we need to know *what is the hypothetical shape of the curve?*
Power, exponential, linear-fractional or it's combination?

We see that the law is there, but what is the form?

# Answer
There is no one answer for the shape of the curve. It depends on the data you are trying to compress.

* For the string 00000..., with a sufficiently good compression algorithm, we can expect the compression function to behave asymptotically like $f(x) \approx c/n$ for large enough $n$, when compressing the $n$-length prefix of this string, where $c$ is some constant.
* For pi, with a sufficiently good compression algorithm, we can expect the compression function to behave like asymptotically like $f(x) \approx c$ for large enough $n$, when compressing the $n$-length prefix of this string, where $c$ is some constant.
* For other strings, there might be some other function for the compression ratio, depending on the specific string you are compressing.

The relationship between Kolmogorov complexity and data compression is quite simple. The Kolmogorov complexity of a string $x$ is at most $\text{len}(C(x)) + \text{len}(D)$, i.e., at most the length of the compressed version of $x$ plus the length of the decompression algorithm. This upper bound is true for every lossless compression algorithm.
> 1 votes

---
Tags: complexity-theory, data-compression, heuristics
---


# Question
Title: Does it make sense to call GAP a "procedural" language?
GAP is a computer algebra system (CAS) that Wikipedia tells me is written in C, a procedural programming language. Does this mean we can say GAP's language is procedural? Or is this characterization a misunderstanding of what a CAS is, and what programming paradigms are?

# Answer
Yes, GAP as a programming language is a procedural language.

"The simplest test to apply is that a language is procedural if it has assignable (mutable) variables", Michael Kay pointed out. The quote below from section 4.8, "variables" of the reference manual of GAP shows GAP can be a procedural language. (I cannot find evidences that show GAP can be classified as a functional language or multi-paradigm language.)

> After a variable has been bound to a value an assignment can also be used to bind the variable to another value.

Note that, for most programming languages including many functional languages (or what I know), the runtime/compiler is mostly/partially written in C, mostly because of the requirement of high performance and the need to interact with hardware. Whether the runtime/compiler is written in C has nothing to do with whether the languages themselves are procedural languages or functional languages.

For example, the runtime for GHC, a popular environment for the flagship functional language Haskell is implemented by a mixture of C, assembly and C--.

It looks most of computer algebra systems provide/use procedural programming languages. Many of them such as Maple provide/use multi-paradigm programming languages.
> 9 votes

# Answer
I'd like to focus on this part of the question because it is not answered, yet:

> GAP is ... is written in C ...
> Does this mean we can say GAP's language is procedural?

**No**

The sentence "\[some language\] is written in C" means that the interpreter or compiler is written in C. The sentence does not say anything about the programming language itself.

You may invent any programming language and write a compiler for that language.

If the compiler for your language is written in C programming language, your language is "written in C".

If your language does not know the concept of procedures and/or functions, your language is not "procedural".

> Does it make sense to call GAP a "procedural" language?

I can't answer this question because I don't know GAP.

However, if it is a "procedural" language, the reason for being a "procedural" language is because GAP knows the concept of functions and procedures.

The fact that GAP is written in C is not a criterion for saying that GAP is "procedural".
> 8 votes

---
Tags: functional-programming, programming-paradigms
---


# Question
Title: What machines are required to solve the emptiness of regular and context-free langauges?
Consider the language definition:

$L = \\{\<M\>| M$ is a DFA and $M$ accepts some string of the form $ww^{r}$ for some $w\in \Sigma^{\*}\\}$

The language $L$ is :

A) Regular

B) Context-free but not regular

C) Recursive but not context-free

D) Recursive enumerable but not recursive

**Solution provided:** Is to create a product machine(intersection) of $M\times P$ where $P$ is the pushdown automata which accepts all the even length palindromes, this product machine will also be a PDA as $REG \cap CFL=CFL$, now it comes down to checking emptiness of $CFL$ is decidable hence recursive, as we need to do this for any $M$ we need to able to simulate a PDA which requires at least an $LBA$

**My approach:** First, we create a machine $M^{r}$ which accepts the language $L^{r}$ now we do product construction(intersection) of $M \times M^{r} \times E$ where $E$ is DFA which accepts all even length strings over sigma, this product machine will be an FSM as $REG \cap REG \cap REG = REG$ so in my approach it comes down to checking emptiness of Regular language.

**My doubt:** How did they decide to check the emptiness of **CFL** we require at least an **LBA** and what type of machine is required in my approach as we need to check the emptiness of regular language?

# Answer
Note that a string in $K\cap K^r$ is not necessarily a palindrome. Hence your argument can not work as a shortcut.

However, the complexity is *not* because of the $ww^r$ in the definition. Given $M$ one mey construct a finite state automaton $M'$ such that $M'$ accepts $w$ iff $M$ accepts $ww^R$, see How to show that a language {w|ww^R in A} is regular, A being regular? This is a simple construction, involving the simulation of $M$ on $w$ synchronously forward and backward. Checking whether $M'$ accepts any string at all is simple.

The problem is that it is even hard to think of a decent way of encoding a finite state automaton suitable for reading by a PDA while being able to compute paths in the DFA from the input.
> 2 votes

# Answer
It is rather straight-forward to show that the language here is decidable.

The "solution provided"-attempt is not sound: Just because we can reduce the problem at hand to deciding non-emptyness of a PDA doesn't mean that we have to able to able to handle arbitrary PDAs here - after all, we are looking just at very specific instances here.

Whether A) or B) might be the correct answer is not even necessarily well-defined. The language at hand refers to an encoding of DFAs as finite words. If we care about decidability, using any reasonable encoding leads to the same answer anyway, and that's it. But if we are using more limited automata models, it will become important to be much clearer on how we encode stuff.

A DFA will not be able to do much meaningful stuff with encoded DFAs, even for smart encodings. On inputs having far more states than the processing DFA has, we just can't answer any "global" questions about its structure. However, we can easily cheat by including the answer in the encoding.

Making a PDA operate on a DFA is going to become more interesting. My hunch would be that the most obvious encodings of DFAs won't make this work. Cheating is still an option, but by going for a sufficiently redundant encoding of states/transitions we can probably built an encoding of DFAs which is not obviously cheating, and which enables a PDA to decide our language.
> 0 votes

---
Tags: formal-languages, undecidability
---


# Question
Title: Given two sets of coordinates, find out neighboring ones
I have two sets of 2-dimensional coordinates on an integer grid, $A$ and $B$

$A = \\{(x\_{A1},y\_{A1}), (x\_{A2}, y\_{A2}), (x\_{A3}, y\_{A3}), \dots\\}$

$B = \\{(x\_{B1},y\_{B1}), (x\_{B2}, y\_{B2}), (x\_{B3}, y\_{B3}), \dots\\}$

I need to find all coordinates in $B$ that are directly above, below, or to the left or right of any coordinate in $A$.

So they differ by one of $\\{(1,0), (-1,0), (0,1), (0,-1)\\}$ from the matching coordinate(s) in $A$.

As an example,

$A = \\{(0,0), (1,2), (2,2)\\}$

$B = \\{(0,1), (1,2), (0,3)\\}$

would result in

$R = \\{(0,1), (1,2)\\}$

How can I efficiently do this?

# Answer
> 2 votes
If the coordinates keep reasonable values and if you can afford marking the points in an image, start with an empty image, mark all $B$ pixels (takes $\\#B$ pixel sets) and test all neighborhoods of the $A$ pixels (takes $4\times\\#A$ pixel tests).

If you need to do this repeatedly, rather than clearing the image every time, better erase the $B$ pixels (another $\\#A$ pixel sets).

Hard to make it faster.

---

Another solution is to sort both point sets in lexicographical order $y$ then $x$ using a linear-time sort (histogram sort). Then a simple merge pass will detect the common points.

But instead of using $A$ directly, replace every point in $A$ by its four Von Neumann neighbors.

# Answer
> 1 votes
Store $B$ in a hashtable.

For each element of $A$, check whether it is in the hashtable. Also, for each element of $A$, for each of its four neighbors, check whether that neighbor is in the hashtable.

The expected running time will be approximately $O(|A|+|B|)$.

---

If you want a further constant-factor speed-up, it is possible to speed this up even further, if $A,B$ are sparse.

Given a location $(x,y)$ in $A$, compute $x'= \lfloor x/2 \rfloor$, $y'=\lfloor y/2 \rfloor$, and then store $(x,y)$ in a hashtable keyed on $(x',y')$. This basically breaks the grid up into $2 \times 2$ blocks, with all locations in the same $2 \times 2$ block treated identically and hashed identically. Now given a location $(u,t)$ in $B$, you can find three $2 \times 2$ blocks that cover $(u,v)$ and its neighborhood. So, look up those three blocks in the hashtable, check whether any of them contain any points in $A$, and if so, check whether they are in the neighborhood of $(u,v)$. In the average case, you'll need to do about 3 hashtable lookups per point of $A$, rather than 5.

The expected running time is still $O(|A|+|B|)$, but the constant factor is reduced by about a ratio of $5/3$.

# Answer
> 0 votes
Is this a one-time comparison, or might there be a single *A* and multiple *B*s?

If the test is to be run on multiple *B*s, one could put more effort into analyzing *A* and greatly reduce the multiple look-up times.

For instance:

* First build a boolean table (array or hash) that is True for each member of *A*, and for each neighbor of *A*.
* For each *B*, simply check whether each element is in the table.

That's still $O(|A|+|B|)$, but processing each *B* will require only 1 lookup, not 5.

---
Tags: algorithms, graphs, search-algorithms, sets, image-processing
---


# Question
Title: when is 2's complement used, or called into use in hardware
so when doing digital design, lets say building a calculator we only take the 2s complement of a negative number.

> 13+(-12)=1
> 001101 + 110100 = (1)000001
> the 1 in parenthesis is overflow that "falls off"

what is the design so that negative numbers are converted into a 2s complement?

# Answer
First thing, `the 1 in the parenthesis is overflow that "falls off"` is wrong. Overflow *may* occur when you add same sign numbers or subtract opposite sign numbers.

As far as the design is concerned, the cpu handles it automatically when the operands are signed integers(when you write something like `a = -1`). For floating point numbers, we have the IEEE-754 notation. Since **2's complement is just 1's complement + 1** (not the exact mathematical definition but works in this case), the cpu can use some instructions like complementing all the bits(bitwise negation) and handling the addition or like scanning the bits from LSB to MSB till the first occurence of **1** and then inverting the remaining bits.
> 1 votes

# Answer
There are two common types of numbers which are directly handled by CPUs: integers and floating-point numbers.

Integers are stored using two's complement. This means that an $n$-bit integer is stored using $n$ bits. The *interpretation* of these $n$ bits depends on whether you think of them as representing signed integers (in which case the MSB is the sign bit) or unsigned integers. When performing operations on integers, you typically tell the CPU whether to treat them as signed or unsigned; this makes a difference in some, but not all, cases.

In contrast, floating-point integers have an explicit sign bit. Two's complement might be used internally when implementing arithmetic on them, but that's an implementation detail.
> 0 votes

# Answer
All common CPU's do use the 2's complement representation. Because they need to handle negative values and because the sign/mantissa representation is less convenient.
> 0 votes

---
Tags: arithmetic, binary
---


# Question
Title: Producing "moves" to permute one array to another
I have 2 arrays, **A** and **B**, which each contain the same **N** elements, but in a different order. (A different permutation) There are also no duplicates in **A** and **B**.

I'm trying to devise an algorithm which generates a series of moves, which changes **A** into **B**.

A move means to move one element in an array to another position (not a swap though). An example of a move would be:

```
1
2
3

Move index 2 to index 0 would be:

3
1
2

```

Now it should always be possible to change **A** to **B** in less than **N** moves. However, the hard part for me is that one requirement is that the series of moves which are generated should be able to be applied sequentially, so something like this should work:

```
let A = .....
let B = .....

let moves = generate_moves(A, B)

foreach move in moves:
    A.move(move.from, move.to) // Moves the element at move.from to move.to

Assert(A == B)

```

The key is that the resulting moves should be able to be applied sequentially, and each time a move occurs, **the indices in the entire array shift**, so therefore the next moves need to take into account the shifting indices.

### Example:

Suppose array **A** is as follows:

```
5
1
3
2
4

```

And **B** is as follows:

```
1
4
3
5
2

```

Then one set of moves that could be produced to get from **A** to **B** is:

```
Move index 1 to 0
Move index 4 to 1
Move index 3 to 2

```

### What I tried:

I made an algorithm like this:

1. Go through each element in **B**
2. If the element at the same position in **A** is wrong, then output a move that moves the correct element into position
3. Repeat until **B** is exhausted

This works, except you need to keep bookmarking information for **A**, because every move changes the indices of the elements above the move source.

So I used a tree structure to store the bookmarking information.

Therefore, the above mentioned algorithm takes O(n log n) time, because I need to shift my source indices for the move by an offset which is stored in the tree.

**My question is: Is it possible to make an algorithm to do this task in O(N) time, but without ever generating more than N moves?**

It seems this problem has some similarities to this problem, because it also involves recovering the indices of elements after they have been offset at any point in time.

# Answer
> 1 votes
As I have mentioned in my comment, your problem is indeed related to the counting the number of inversions, which can be shown to have a lower-bound of $\Omega(n \log n)$ if you are to only allowed to compare elements.

To see this, let $x$ and $y$ be some elements, such that $x$ comes before $y$ in $B$. In your solution, you traverse $B$ in order and create a move to transfer an item in $A$ to its correct position in $B$. Therefore, $x$ will be moved first before $y$. Now, the position of $y$ in $A$ will only be affected if $y$ comes before $x$ in $A$, or if $x$ and $y$ is an inversion in $B$. So if you are to find the final position of $y$ in $A$ when you are to create the move to transfer $y$ in its correct position, you have to determine how many inversions are there in $B$ with respect to $y$ to determine the amount of offset to add to $y$'s original position in $A$. This you have to do with all $n$ items.

So your current solution that requires additional $O(n \log n)$ time to track the position of elements is necessary. But I think you can make it simpler if you would compute the number of inversions upfront, before creating the moves, using an $O(n \log n)$ solution rather than maintaining a tree structure that you need to update each time a move is created.

# Answer
> 1 votes
* Build a map between each value and its index for list B.
* Repeat until finished.
    + Find index of value of first element of list A.
    + Swap position 1 and the indexed position within list A.
    + If A\[1\] = B\[1\], work with 2 instead of 1 (etc. for 3, 4, …).

---
Tags: algorithms, time-complexity, arrays, permutations
---


# Question
Title: How do I keep track of different ways I can structure a 2D array
As of recently I've been trying to get better at algorithms and I've stumbled onto one that I can't seem to solve.

The idea behind the algorithm is to try to find as many different ways as possible to store each object of size K in an array of N\*N given certain restraints.

So take this grid right here

```
.X.X
.XX.
...X
....

```

There are 6 possible ways to store 4 different objects of sizes 1 - 4

```
4X.X
4XX1
422X
4333

4X1X
4XX.
422X
4333

3X.X
3XX1
322X
4444

3X1X
3XX.
322X
4444

2X1X
2XX.
333X
4444

2X.X
2XX1
333X
4444

```

The problem I'm facing is trying to come up with an algorithm that could solve this problem. The first thing that comes to mind is to utilize recursion to find each possible solution for each size, but then I draw a blank. I've also read about backtracking but I can't seem to make it fit this problem even though I feel as if it should be possible by creating some sort of state space tree.

What's a good way to approach this problem? Is there a typical algorithm one would use? I'm not looking to have the problem solved for me but rather having broken down into logical steps if possible.

The original description for the problem can be found here https://vjudge.net/problem/Kattis-minibattleship

# Answer
> 1 votes
This is an example of an exact cover problem. It is NP-complete in general.

There are many algorithms that can solve exact cover problems reasonably efficiently on moderate-sized examples, but Knuth's Algorithm X is probably your best bet.

# Answer
> 0 votes
The most natural solution is probably exactly to use recursive backtracking. Since you haven't told us what difficulty you had in applying that, it's not clear how to help you.

The statespace is the set of all partially-filled out grids. Given a state (a partially filled-out grid), a transition is obtained by picking the lowest-numbered shape that is not already in the grid, picking any valid location and orientation for it, and placing it in the grid there. This yields a state space tree, which can be explored through recursive backtracking (which you can think of as depth-first search in that tree).

---
Tags: algorithms, graphs, backtracking
---


# Question
Title: Describing the set of Running Time of all Turing Machines
Consider the set of all valid Turing Machines descriptions $T\_{All}$, and the set of functions that denote the real (not asymptotic) running time of Turing Machines in $T\_{All}$, lets call it $R\_{All}$.

Since there are infinite functions, not all of which might represent the running time of a valid Turing Machine, how do we describe this subset of $R\_{All}$ mathematically (say to a non CS individual) who doesn't know anything about TM etc.

Is there an accurate, self contained, complete mathematical definition that describe this subset of mathematical functions without referring to anything else like TM?

# Answer
It is not possible to describe the subset of functions that represent the running time of valid Turing machines in terms of pure mathematics, without reference to the concept of a Turing machine. This is because the concept of a Turing machine is fundamental to the definition of this subset of functions.

A Turing machine is a mathematical model of a hypothetical computer that can perform any computation that is theoretically possible, given enough time and memory. The running time of a Turing machine is the number of steps it takes to complete a computation, as a function of the size of the input.

To define the subset of functions that represent the running time of valid Turing machines, we must first define the concept of a Turing machine and specify the conditions under which a function can be considered to represent the running time of a Turing machine.

For example, we could say that a function f(n) belongs to the subset of functions that represent the running time of valid Turing machines if and only if there exists a Turing machine M and an input x such that the number of steps M takes to compute f(|x|) on input x is equal to f(|x|). Here, |x| represents the size of the input x.

This definition captures the idea that the running time of a Turing machine is a function of the size of the input, and it links the concept of a Turing machine to the mathematical concept of a function. However, it does not provide a self-contained, complete mathematical definition of the subset of functions that represent the running time of valid Turing machines, as it relies on the concept of a Turing machine, which is not a purely mathematical concept.
> 2 votes

# Answer
Short answer: No.

These are called the time constructible functions. The definition is basically what you would expect it to be: a function $f(n)$ is fully time constructive if there is a Turing machine that, on input $1^n$, stops after exactly $f(n)$ steps. I'm not aware of any simple and complete characterization of the set of such functions that does not refer to Turing machines.
> 1 votes

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


# Question
Title: Is Enumerator a variant of Turing machine that starts with empty string and builds according to the description of language
My understanding is an "Enumerator" is a Turing Machine that: instead of taking an input string, then going through a series of transitions and "halting" or "not halting" on it, it does not accept any input string and it starts with a blank string and builds the final string according to the rules of the language

For example: if our language was L = { w | w is made up of 0^n1^n, where n \>= 0 }

A normal Turing Machine would have a input tape and it would receive an input on that tape and this normal Turing Machine would go through a series of transitions to deduce whether this string belongs to the language or not

An enumerator, a variant of normal Turing Machine, would have 3 different tapes, an input tape + work tape + output tape. Since, we don't have any input we don't interact with input tape at all ( which means we can remove that tape if we want to ), the work tape is used as a temporary workspace for constructing strings - at the end when we finish constructing a string we may choose to copy the symbols from the work tape to output tape and adding a "#" symbol on the output tape at the end of the output tape which will act as a separator from the next string and we will then blank out the work tape, the output tape acts like a printer for string with '#' separating different strings

In an enumerator, to produce strings for the given language, we will start on a start state and then take the transition to write 'n' number of '0' on the work tape, then writing 'n' number of '1' on worktape ( using appropriate logic of crossing out / blank symbol for 'counting' ). Then once we are done with that we will go to a special state called the "enumeratored state" which will copy the symbols from the work tape to output tape ( again through a series of transitions ) and then blank out the work tape + add the separator symbol on the output tape

This will continue on forever for strings of all lengths unless we have designed to produce specific strings of this language

In a nutshell, enumerator just helps building strings according to a pattern whilst turing machines help to check if a certain strings adheres to a certain pattern

Which also gives rise to the theorem that: "A language is accepted by a Turing machine if and only if some enumerator enumerates it"

Is my understanding correct?

# Answer
> 1 votes
Your idea of "an enumerator" is pretty good.

In fact, you have recovered the origin of the term "recursively enumerable" as explained in the textbook *Introduction to the Theory of Computation* by Michael Sipser.

> **ENUMERATORS**
>
> As we mentioned earlier, some people use the term recursively enumerable language for Turing-recognizable language. That term originates from a type of Turing machine variant called an enumerator. Loosely defined, an enumerator is a Turing machine with an attached printer. The Turing machine can use that printer as an output device to print strings. Every time the Turing machine wants to add a string to the list, it sends the string to the printer. Exercise 3.4 asks you to give a formal definition of an enumerator. The following figure depicts aschematic of this model.

Your theorem also appears in that book.

> THEOREM **3.21**
>
> A language is Turing-recognizable if and only if some enumerator enumerates it.

---
Tags: turing-machines, recursively-enumerable
---


title: Optimising updates to a way point graph

text:
# Question
Title: Optimising updates to a way point graph
I have a graph of vertices and connected edges as shown in the image below.

I have a function that iterates from every single vertex and finds closed loops in order to find all polygons in the graph.

Here is an example of my graph which has found all the polygons in the graph:

Now if i add a new segment (seen in red)

What i currently do is basically wipe my array of all polygons found, and find all polygons again.

But this is clearly not needed because not all polygons are going to need to be updated here.

How can I optimise my function so I can avoid checking the entire graph again?

Its obvious P2 doesn't exist anymore, its been cut into two new polygons. And P3 and P4 only needs an edge inserted into its array of edges. And P1 is unchanged.

I only want to check the minimum amount of vertices that will find all the new polygons and changes to pre-existing ones. But I am not sure which vertices have to be rechecked besides the two new ones added on each end of the red edge added to the graph.

# Answer
> 1 votes
> I have a graph ...

I read that as "a *planar* graph".

You didn't describe your analysis data structures, so I will make some assumptions. Let U be the initial undirected graph, and G the corresponding digraph where each edge becomes a pair of edges, forward + backward. Now we have suitable input for a python method to use Johnson\[1975\], simple\_cycles() in networkx. The cost of (n + e) × (c + 1) is on the expensive side for a graph with many polygons, but we incur the cost just once, and I don't see how to get away with doing less work.

Maintain a set of cycles. Given a cycle, lexically order its nodes, so the 1st node could name the cycle, could name the polygon. Or if you prefer, tack on a mapping and generate P1 .. Pn names as each polygon (cycle) is added and deleted.

Maintain a `cycle_member` attribute on each node. Notice that it is a `set`. One of your example nodes is member of {P1, P2, P4}.

---

> add a new segment

1. Find the set of affected nodes (four, in your red segment example).
2. From those affected nodes, find the dominant `cycle_member` cycle, which *all* those nodes are in.
3. Remove that cycle from all nodes in the cycle (P2, in your example).
4. Construct a small new digraph from that cycle plus new edge.
5. Compute both `simple_cycles`.
6. Visit the nodes of both cycles, updating each `cycle_member` attribute.

This scales to large graphs, where most cycles and most nodes are distant from the inserted edge. In a graph with a million polygons, the update avoids touching nearly all the cycles and nearly all the nodes.

---
Tags: algorithms, graphs, graph-traversal
---


# Question
Title: Confusion regarding "epsilon" transition in NFAs, whether taking epsilon before or after reading the input affects the final states
Let's say we have a NFA as follows:

It has 3 states, q1 - q2 - q3 and can make transition from q1 to q2 on 0 or epsilon and from q2 to q3 on 1 or epsilon

My question is do we take epsilon transition before reading input or after reading input and after reading the input, if we reach a state where we have epsilon transition do we take that transition? if the latter part is correct then we can conclude that: we can take epsilon transition without consuming input at any point in time i.e before or after reading the input

Let's try processing some input string, so you can better understand my problem, input is "0"

Case 1: We split ( not literally ) the NFA ***before*** reading anything. So, since there's an epsilon transition from the start state q1, we start in q1 and q2 but there's also an epsilon transition from q2 to q3. Meaning that we are going to start in q1, q2, q3 ( consider 3 branches )

Then we read in our input which is 0:

* from q1 the machine would visit q2, now ***before*** reading the next input we can take the epsilon arrow and split q2 into q2 and q3. Meaning the next symbol would be processed in these two states

***Note***: Above once we split before reading 0, then changed state and then again took the epsilon from the new state, is it legal to take epsilon from q2 since it would technically be "***after***" reading 0 but "***before***" reading the next input

* from q2 the machine would go to a trap state and hence reject
* from q3 the machine would go to a trap state and hence reject

Case 2: We split ( not literally ) the NFA ***after*** reading anything. In this case we start in just q1, read in the input 0 and move to state q2. And ***after*** reading the 0, we realise that we are on a state that has an epsilon transition to q3, so we split q2 to q2 and q3

There can be a 2b case: where instead of taking the epsilon from the new state, we first read in the input - take the epsilon transitions and then move on to the new resultant state, in this case after processing the current input, we would have q1, q2 and q3 as the final states

We can clearly see that in case 1 ( splitting before reading ) and case 2 ( spliting after reading ) we landed in the same set of final states, does this mean it does not matter if we split before or after?

This is important concept, because it's used in NFA to DFA, PDA and turing machine. Please help me!

# Answer
> 2 votes
It happens both before *and* after.

Remember this is a *non-deterministic* automaton. Any time there is an epsilon transition, the automaton can either take that transition, or not take it -- it's a free choice. The automaton has the choice to do so before reading anything, and after, and in between reading every symbol. In fact, it can take as many epsilon transitions as it wants, at any time.

This is non-deterministic, so even though you have only a single input, there are many possible paths that might be taken through the automaton. The input is accepted if at least one of those paths is an accepting path.

See also How does an NFA use epsilon transitions?.

Also, your textbook undoubtedly has a formal mathematical definition. Try working through that definition, for the specific example you gave. You will discover what happens.

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


# Question
Title: Is there an alternative for the formal language theory that could be used for flowchart diagrams?
I am creating a tool for validating, parsing, and interpreting flowchart diagrams on diagrams.net, and it is necessary to give users an opportunity to define a set of rules for the diagram. So, in the end, I want to achieve something like ANTLR for diagrams with the following features:

* Some kind of DSL for defining parser and lexer rules
* Building a parse tree for a given diagram with a given set of rules
* Traversing the parse tree and generating code from it

I failed to find some existing tools or theoretic models for such a task, so currently, I am trying to apply context-free grammars for this task, but the problem is that CFGs and all the theory and tooling utilizing them interprets the input as a sequence of tokens, and flowchart diagrams have two major differences from that:

1. In texts, each token, except EOF, is followed by exactly one token. In flowcharts, after one token may come multiple tokens, for example after the Decision Element.
2. There can be loops in flowcharts.

#### Branches support

I managed to resolve the first problem – created a top-down parser that can validate and parse a diagram with branching using an extended form of CFG, where production rules can be defined as $\alpha \to \beta$, where $\alpha \in V$, $\beta \in (V\cup V'\cup \Sigma)^\*$.

$^\*$ \- Kleene star operation, $\Sigma$ \- set of terminals, $V$ \- set of non-terminals, $V' = \\{f(v) : v \in V\\}$, where $f(v)$ is special non-terminal that represents one or more branches of non-terminal $v$

For example: (capitals are non-terminal characters, lowercase are terminals)

```
CONDITION -> decision ACTION'
ACTION -> process
ACTION -> end

```

There, the first rule describes that the `decision` token (rhombus) must be followed by 1 or more branches of `ACTION`. This grammar could process diagrams like this one:

#### Specific questions

1. Maybe I am reinventing the wheel and there is already some parsers or theory that could be applied to this task.
2. If there are no current solutions, how could I implement loops support? I am currently looking into the idea of keeping a map `token -> AST node candidates`, and reevaluating the candidates each time the lexer visits the same token, but the concept of tying node candidates to tokens seems very unnatural for CFG parsers.

# Answer
Not sure why you would go straight to CFGs to resolve this when most flowcharts can be represented as rational functions, AKA finite-state transducers. These can be expressed as regular patterns: considering your diagram, it would be expressed as

```
((1, print['1']) | (2, print['2']) | (3, end))

```

Looping constructs can obviously be modelled as well

```
((1, print['1']) | (2, print['2']))* (3, end)

```

CFG constructs would come into the picture if one or more nodes on the flowchart represented an embedded flowchart. This is exactly analogous to a method in an algorithmic programming language like C or Java, where the flow of control (instruction pointer trace) runs a regular pattern as long as the stack pointer is fixed, and embedded flows (called methods) are represented similarly.

If you are interested, see ginr for a robust regular pattern compiler with support for multidimensional patterns (rational functions and relations).
> 1 votes

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


# Question
Title: Conversion of epsilon NFA to DFA, handling epsilon transitions
I am reading Michael Sipser's "Introduction to theory of computation" 3rd edition, page 55 - 56, the topic "equivalence of DFAs and NFAs"

1. ***Case 0:*** Michael Sipser asks us to handle the transition function of "non epsilon NFAs" as follows: δ'( R, a ) = $\bigcup\_{\_{r \epsilon R}}^{}δ(r, a)$
2. ***Case 1:*** Michael Sipser, then, introduces us to the transition function of "epsilon NFAs" as follows: $δ'( R, a ) = \\{ q \\,\\,\epsilon \\,\\, Q | q \\,\\,\epsilon \\,\\,E(δ( r, a )) \\,\\,for \\,\\, some \\,\\, r \\,\\,\epsilon \\,\\, R\\}$
3. ***Case 2:*** This is how I like to think intuitevly, that is taking epsilon arrows as soon as we see one, $δ'( R, a ) = \\{ q \\,\\,\epsilon \\,\\, Q | q \\,\\,\epsilon \\,\\,δ( E(r), a )) \\,\\,for \\,\\, some \\,\\, r \\,\\,\epsilon \\,\\, R\\}$

Look at the position of Transition function and epsilon function! in case 2 and 3

Where function ***E()*** implies "Epsilon Closure" of a state. But, here if you realize Michael Sipser asks us to take epsilon closure ***after*** reading the input + transitioning to a new state. Basically it's like saying, if we are on a state then we don't have to take the epsilon transition immediately and we need to first process the input - move to a new state - and then take the epsilon transition from the new state ( if it exists ). He also modifies the start state of the resultant DFA to be E(start state)

Later he implies that taking epsilon before or after ( after as i mentioned above ) reading is the same! Basically case 2 and 3, mentioned above should produce same states but that isn't the case

Let's look at an example of NFA:

***NOTE:*** Also, imagine we had a loop from state 3 to state 3 on input "b"

Now, DFA would have $2^{number of states}n$, one of the states of DFA would be "1". If we consider the transition function for state 1 in DFA on input "b", we would end up with following two cases:

1. Using case 1 transition function, from above, we would end up with { 2 }
2. Using case 2 transition function, from above, we would end up with { 2, 3 }

Where as, he implies case 1 and case 2 should produce same results

So, where am i wrong? I fail to understand how case 1 would be same as case 2

EDIT: Removed an accidental apostrophe EDIT 2: Tweaked example a little, by adding a loop ( did not re-draw the diagram )

# Answer
I think your confusion is with Sipser's comment that you can convert an NFA with $\varepsilon$ to a DFA by either reading an input first then you compute the epsilon closure or by computing the epsilon closure first before reading an input. To clarify that, yes you can do both. However, Sipser might have not mentioned that if you compute the epsilon closure **before** reading an input, **there is no need to modify the start state**. However, **you must compute the epsilon closure after reading the entire input**. You can verify these using the NFA you gave as an example.

Personally, I cannot remember seeing that comment of him in his text prior to your question. Possibly I missed or simply ignored that.

**Note:** Your case 2 is not enough so to capture Sipser's comment that $\varepsilon$ can be processed before reading an input since as I have mentioned, there must be an epsilon closure after reading the *entire input*. This I think will be a little cumbersome to express since Sipser's transition function is defined only for reading a single input and not an entire word/string.
> 0 votes

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


# Question
Title: Searching for the largest bipartite subgraph
OpenAI's Chat-GPT told me:

There is no known exact algorithm for finding the largest bipartite subgraph in a graph in polynomial time. This problem is generally believed to be NP-hard, which means that there is no known polynomial-time algorithm for solving it.

Is this correct?

# Answer
> 2 votes
The problem of finding a largest bipartite subgraph of a graph is equivalent to the maximum cut problem. Karp proved NP-completeness of this problem.

That is, this problem is proven NP-hard, not "believed to be NP-hard." I suggest you use ChatGPT as hints for more research, and not take responses as is. They are often confident-sounding but very wrong.

# Answer
> 1 votes
Garey and Johnson (Computers and intractability) states that the subgraph isomorphism problem is $\mathsf{NP}$-complete, and contains several special cases, like Clique, Complete bipartite, Hamiltonian cycle or Hamiltonian path.

If you could find the largest bipartite subgraph, you could find the largest complete bipartite subgraph, so yes, that's true.

To find the largest complete bipartite subgraph in a bipartite graph $G = (X\sqcup Y, E)$:

* construct $G' =(X\sqcup Y, E')$ where $E' = \\{\\{x, y\\}\mid x\in X, y\in Y \text{ and }\\{x, y\\}\notin E\\}$;
* find a maximum matching in $G'$;
* find a minimum vertex cover in $G'$ using König's theorem;
* the complement of that vertex cover is a maximum complete bipartite subgraph in $G$.

---
Tags: graphs, np-hard, bipartite-graph
---


# Question
Title: Is S->E+S|E, E->number|(S) same as S->number|(S+S)?
I'm reading https://ilyasergey.net/CS4212/\_static/lectures/PLDI-Week-07-more-parsing.pdf

On page 11, there's the definition of Sum Grammar:

```
S -> E + S | E
E -> number | (S)

```

Just wondering if this grammar same as follows:

```
S -> number | (S+S)

```

# Answer
In modified grammar:

1. We cannot generate $number + number + number....+ number$, as every operation will have a parenthesis associated with it.
2. Redundant parenthesis: $number + number$, we will have to describe it as $(number + number)$ here the parenthesis are redundant.

If you modify the grammar to:

$S\rightarrow S+S$ $|(S)|$ $number$

It will solve both the issues mentioned and generate the same language as Sum Grammar but it's an ambiguous grammar and doesn't have the properties of Sum grammar(right-to-left associativity)
> 1 votes

---
Tags: compilers
---


# Question
Title: A graph is strongly connected iff every non-trivial cut contains an edge
As the title states, I am asked to prove that a directed graph $G=(V,E)$ is strongly connected iff for all non-empty subsets $\emptyset \neq S \subset V$, the cut $\delta(S) \neq\emptyset$, where $$\delta(S)= \left\\{ (u,v)\in E \mid u \in S,\\; v\in V \setminus S \right\\}.$$

I've shown that if $G$ is strongly connected, there has to be atleast 1 (possibly 2) edges in $\delta(S)$ for any $\emptyset \neq S\subset V$ which is one side of the proof.

However, when approaching the other side, I cant seem to find any intuition on how to start the proof, I just cant seem to understand what information I can deduce from the fact that there are edges which cross every non-trivial cut (basically the same as saying that $\delta (S)\neq\emptyset $ for all $\emptyset\neq S\subset V$)

(I've proven the first direction by showing that since $S$ is not empty and $G$ is strongly connected, there has to be an edge from a vertex which is not in $S$ to a vertex in $S$, thus showing that $\delta(S)$ is not empty)

# Answer
> 2 votes
You can prove the existence of a path between any $u$ and $v$ vertices using the following process:

* set $S = \\{u\\}$;
* while $S \neq V$ do
    + for each $(x, y)\in \delta(S)$, add $y$ to $S$

The property "all vertices in $S$ are reachable from $u$" is a loop invariant for the while loop.

If you suppose that $\delta(S)\neq \emptyset$ for all non-trivial $S$, that means that the size of $S$ increases each loop, and the loop halts if and only if $S = V$.

# Answer
> 0 votes
For the sake of a contradiction, assume the graph is not strongly connected. If a graph is not strongly connected, then there is a pair $u$ and $v$ such that there is no path from $u$ to $v$.

Let $R(u)$ be the *reachability set* of $u$, i.e. the vertices reachable from $u$.

Now, since $v \notin R(u)$, it means that $S = R(u) \subset V$ with $\delta(S) = \emptyset$ contradicting the assumption that every non-trivial cut is nonempty.

Our only assumption was that the graph was not strongly connected which then must be false. The graph is strongly connected.

---
Tags: minimum-cuts, connected-components
---


title: Proving L1 ∪ L2 ⊆ L1* L2*

text:
# Question
Title: Proving L1 ∪ L2 ⊆ L1* L2*
I'm stuck here, how can i prove this: $$L\_1 \cup L\_2 \subseteq L\_1^\*L\_2^\*$$

$$\begin{array}{rcl} x\in L\_1\cup L\_2 & \Rightarrow & x\in L\_1^\* \lor x\in L\_2^\*\\ &\Rightarrow &x\in L\_1^\*\cup L\_2^\* \end{array}$$

What's next?

# Answer
> 1 votes
Star closure of $L\_1$ is $$L\_1^\*=L\_1^0 \cup L\_1^1\cup L\_1^3\cup\dots\\;\\;.$$ Also star closure of $L\_2$ is as follow $$L\_2^\*=L\_2^0\cup L\_2^1\cup L\_2^2\cup L\_2^3\dots\\;\\;.$$ Obviously, concatenation of $$ L\_1^\*L\_2^\*=\\{L\_1^0 \cup L\_1^1\cup L\_1^3\cup\dots\\}\\{L\_2^0\cup L\_2^1\cup L\_2^2\cup L\_2^3\dots \\} $$ has languages like $$L\_1\cup L\_2$$ as its subset.

# Answer
> 0 votes
You can show first that $L\_1 \cup L\_2 \subset L\_1^\*L\_2^\*$:

* Note that $L\_1^\*L\_2^\* = L\_1^0L\_2^\* \cup L\_1^1L\_2^\* \cup L\_1^2L\_2^\* \cup ... $. Since $\varepsilon \in L^\*$ and $L=L^1$, it follows that $L\_1 \subset L\_1^1L\_2^\*$ which then implies that $L\_1 \subset L\_1^\*L\_2^\*$.
* To show that $L\_2 \subset L\_1^\*L\_2^\*$ use the same idea as above but using the fact that $L\_1^\*L\_2^\* = L\_1^\*L\_2^0 \cup L\_1^\*L\_2^1 \cup L\_1^\*L\_2^2 \cup...$.

Now, if $L\_1$ and $L\_2$ are both $\\{\varepsilon\\} $ then $L\_1 \cup L\_2 = L\_1^\*L\_2^\*$, since $\varepsilon^\*=\varepsilon$ and $\varepsilon\varepsilon =\varepsilon$.

Using all those facts above, $L\_1 \cup L\_2 \subseteq L\_1^\*L\_2^\*$.

# Answer
> 0 votes
L1\* L2\* contains among many others any string in L1 concatenated with 0 strings from L2, and 0 strings from L1 concatenated with any string of L2. That’s it.

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


# Question
Title: Sort doubly linked list with just manipulating pointers
Given doubly linked list $L$ that contains $n$ elements of numbers. Between QuickSort, and MergeSort and InsertionSort, which algorithm preferred to sorting $L$ by just swapping links of $L$?

I think the InsertionSort is better option but I have no any idea to show that that minimize number of changing pointers. Any help will appreciated?

Suppose in below black edge is previous link and green edge is next link, after swapping liknks:

# Answer
Minimizing the number of changing pointers is equivalent to minimizing number of swaps, which is obtained by Selection Sort.
> 0 votes

# Answer
Only MergeSort has a guaranteed $O(n\log n)$ behavior. You may well consider Natural MergeSort, that has the extra property of adaptiveness.

---

If you only care about swapping links (?), I guess that both StraightSelection and StraightInsertion achieve an optimal (certainly in the worst case, $O(n)$).
> 0 votes

# Answer
Selection sort will sort in O(n^2) with O(n) pointer changes. So if for some reason you need to minimise the number of pointer changes, that’s it.

On the other hand, you can just put all the pointers into an array, sort the array, and reconstruct the double linked list.

(I actually had this in a job interview. I recommended either this, or bubble sort if it is absolutely not time critical because bubble sort of a double linked list is fun).
> 0 votes

---
Tags: algorithms, sorting
---


title: Correct way to encode strings

text:
# Question
Title: Correct way to encode strings
I'm interested in analyzing the randomness of strings using relative count for 1-, 2-, etc tuples.
E.g. for a long string `"abbccba.."` with an alphabet `["a", "b", "c"]` , the quantities `["a", "b", "c"], ["aa", "ab", "ba", "bb", "ac", "ca", "cc", "bc", "cb"]` etc should be approximately equal for every kind of tuples.
Of course it is convenient to encode the string in *binary form* with the alphabet `["0", "1"]` (the number of tuples will be minimal), but how to do it correctly?
The primitive coding scheme `{"a"→"00", "b"→"01", "c"→"10"]}` (or similar) gives even a different number of "0" and "1"!

# Answer
> 0 votes
Take a look at Huffman coding \- efficient algorithm for finding optimal (as short as possible) binary coding for given string. This algorithm takes alphabet and weights (usually probabilities of each letter in your text) of each symbol in alphabet, as input. Then computes for each symbol in alphabet optimal coding.

I don't really understand your problem, but this might be helpful.

---
Tags: strings, randomness, encoding-scheme
---


# Question
Title: Determine minimum and maximum number of leaves on a complete tree
I want to determine the minimum and maximum number of leaves of a complete tree(not necessarily a binary tree) of height $h$.
I already know how to find minimum($h+1$) and maximum($2^{h+1}-1$) number of **nodes** from the height, but what about *leaves*? Is there a way to determine them knowing nothing but height of the tree?

# Answer
> 1 votes
Hint:

> Try the case $h=1$. What's the minimum? What's the maximum?

# Answer
> 1 votes
For a given **height (h)** in m-ary tree, you can calculate first the max/main number of nodes and then calculate the leaves according to each situation:

1. To calculate the **max/min** number of nodes in m-ary tree use the following equations:

**Maximum number of nodes: $\frac{m^{h+1}-1} {m-1}$**

**Minimum number of nodes: $(mh)+1$**

2. Now you would use the following equation to calculate and find the **internal nodes (I)** from **vertices (n)**

**$I = \frac{n-1} m$**

3. You would have **Internal nodes (I)**, and **vertices (n)**. So finally you would use the following equation to find the **leaves (L)**

**$L = n - I$**

---
Tags: trees, binary-trees
---


# Question
Title: When converting a epsilon NFA to NFA to DFA, how to handle the start state?
Let's say, initially we have an epsilon NFA in which the start state, say state 1, has epsilon transition to state 3

We know when converting from epsilon NFA to NFA, we apply the following formula for each state: E(T(E(state), input)), where E = epsilon closure and T = transition function. In this stage the start state for the NFA remains the same as it was for epsilon NFA, right?

Now, when we convert the NFA to DFA, are we still supposed to use the same start state that was in the NFA and epsilon NFA because if you think about this then when directly converting from epsilon NFA to NFA we use epsilon-closure of the start state. So, remembering the first line of the post

1. In the above case: If we use the same start state we would end up with a single set element representing the start state ( same as that of NFA and eNFA ) in this case it would stay "1"
2. If we directly convert eNFA to NFA then the start state would be "1,3"

This might seem minute, but it changes the entire language in the final DFA

# Answer
> 5 votes
There is no need to apply the $\varepsilon$-closure twice when computing transitions. There are two main ways to convert an $\varepsilon$-NFA into a NFA: the forward closure and the backward closure. Consider $(Q, \Delta, I, F)$ an $\varepsilon$-NFA.

* In the forward closure, you are trying to apply $\varepsilon$-transitions **after** each normal transition, to see where you can reach. Since that is the case, you must just be sure that there is no problem for the very first transition, and modify the starting states. A NFA recognizing the same language would be $(Q, \Delta', I', F)$, where $I'=\mathcal{E}(I)$ and $\Delta'(q, a) = \mathcal{E}(\Delta(q, a))$.
* In the backward closure, you are trying to apply $\varepsilon$-transitions **before** each normal transition, to see from where you can start. Since that is the case, you must consider the very last transition, and modify a bit final states. A NFA recognizing the same language would be $(Q, \Delta'', I, F'')$, where $F'' = \\{q\in Q\mid \mathcal{E}(q) \cap F \neq \emptyset\\}$ and $\Delta''(q, a) = \bigcup\limits\_{p\in \mathcal{E}(q)}\Delta(p, a)$.

Of course, if your convention of NFA allows only one starting state, only the second transformation can be applied, unless $I = \\{q\_0\\}$ and $\mathcal{E}(q\_0) = \\{q\_0\\}$.

Here are some example of conversions. Despite being different, all those NFA's recognize the language $a^\*b^\*c^\*$.

The idea for converting $\varepsilon$-NFA directly to DFA is exactly the same: you either apply $\varepsilon$-closure after transitions, but start from a bigger set of states, or apply before transitions and modify final states.

In the previous example, the backward closure is already a DFA (but it is not always the case).

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


# Question
Title: A Markov algorithm that does unary multiplication
I am learning Markov algorithms and came across the paper *Markov Algorithm* by CHEN Yuanmi. I am trying to understand the following example (well, any of the examples in the paper).

> Example 3: Multiplication. MA3 = $\\{\Sigma, P, P\_0\\}$
>
> * $\Sigma = \\{a, A, B, C, \\#\\}$
> * Productions in $P$:
> $p\_1: Ba \to aB$
> $p\_2: Aa \to aBA$
> $p\_3: a \to \epsilon $
> $p\_4: a\\#\to \\#A $
> $p\_5: \\#a \to \\#$
> $p\_6: \\# \to \epsilon$
> $p\_7: B \to a$
> $p\_8: \epsilon \to \cdot \epsilon$
> * $ P\_0 = \\{p\_8\\}$
>
> Remark: Given the input in form of "$\underbrace{aa...a}\_x\\#\underbrace{aa...a}\_{y}$", the algorithm will halt with the output in the form of "$\underbrace{aa...a}\_{x \times y}$".

My question is about the above example. I understand the rules should be applied in linear order. So given an input of "$aaa\\#aaa$", the first rule to match would be $p\_3$, which says to replace `a` with the empty character. So the string will be consumed down to a single `#`, which is then also replaced with an empty character ($p\_6$), then the machine halts with no output($p\_8$). How does this achieve multiplication? What am I not understanding?

# Answer
You have demonstrated that example on multiplication cannot be correct.

Well, there is typo in that example. The substitution rule $p\_3$ should have been $$A\to\epsilon$$
> 2 votes

---
Tags: turing-machines, strings, multiplication, term-rewriting
---


# Question
Title: Boolean Integer Linear Optimization/Programming
Trying to solve an ILP optimization problem with a number of potential boolean variables and then express constraints on these variables based on those boolean results.

Let's say I am doing 5 coin flips and allowing people to choose heads or tails for each coin flip. They are able to choose one or more specific flips and whether or not they think it would be heads, and then if they are correct they get tickets back depending on how many flips they chose. Eg: You pick heads for flip 3 and tails for flip 5 and if both are correct you get 3 tickets. Another person picks heads for flip 1, heads for flip 2 and tails for flip 3 and if they are correct they get 10 tickets.

I want to be able to express something like:

```
y=3 if x_3=1 (heads) & x_5=0 (tails)
y=10 if x_1=1 (heads) & x_2=1 (heads) and x_3=1 (heads)

```

So on and so forth

And with a large number of trials - how would I be able to determine what the best/worst case scenario is in terms of having to pay out the most/least tickets to optimize what the ideal results would be?

Thanks for any help

# Answer
> 0 votes
Yes, it is certainly do-able. Use a different $y$ for each rule, e.g., $y\_1=1$ if the first rule triggers or $y\_1=0$ otherwise, $y\_2=1$ if the second rule triggers or $y\_2=10$ otherwise, etc. Then your goal is to minimize or maximize $3y\_1+10y\_2+\dots+y\_n$.

It is easy to express each rule (e.g., $y\_1=1$ if $x\_3=1$ and $x\_5=0$, or $y\_1=0$ otherwise) using the methods in Express boolean logic operations in zero-one integer linear programming (ILP). In particular, $y\_i$ is a logical-AND of some of the $x\_j$'s, so you can use the rule for logical-AND from there.

---
Tags: optimization, linear-programming, boolean-algebra, integer-programming
---


# Question
Title: Math symbol to represent an operator to convert from double-precision to 32-bit integer value?
I'm looking for a good mathematical symbol to represent the conversion from a double-precision floating value to an unsigned 32-bit integer value. Does anyone have suggestions for a good Greek letter or a math symbol to express this?

The best candidate I can think of is to use a symbol for a floor function with a subscript like below:

Is there a more official way to represent this?

# Answer
As far as I know, there is no common/standard symbology to represent finite types. Neither floating-point nor unsigned integer. And even less for conversions, taking into account that they are not always possible. You can represent the naturals as the set $\mathbb N$, but there is nothing for the floating-point numbers, a special subset of the rationals.

If you want to stress the data type conversion aspect, better use a typecast-like notation. If you just want to express the numerical value, $\text{floor}$ ($\lfloor x\rfloor$) is good enough.
> 0 votes

---
Tags: integers
---


# Question
Title: Dynamic Programming- Calculating visit in a weighted matrix
I found this question on a forum chat on and while looking at it I thought I can solve it using recursion,

> A group of friends is split into cells in a room in a random arrangement of m X n cell locations in a rectangular or square form, such that each person in a cell can see all the people in their cell as well as the people in all the cells at the higher or equal position in row or column number. You are required to find out how many persons can be seen by each cell player from their respective cells i.e. you have to print the view matrix. persons in cell \[i,j\] can see all the players in cell \[a,b\], where a = i to m and b = j to n.

Let there is a matrix= \begin{bmatrix}1&1&1\\1&1&1\\1&1&1\end{bmatrix} The output must be =\begin{bmatrix}9&6&3\\6&4&2\\3&2&1\end{bmatrix}

After hours of thinking about it, I realized that this question can be done using dynamic programming, I don't know enough about dynamic programming, after few tutorials from the internet, I am confused, Can anyone refer me a very exact question like this on the Internet,I am unable to find a question like this, I wish to learn about this topic by doing this question. Otherwise,you can also tell me how questions like this are done. I will keep editing as I understand how to do this question. Thanks.

Few resources that helped me that it is dynamic programming question:

What is dynamic programming about? When can I use dynamic programming to reduce the time complexity of my recursive algorithm?

# Answer
> 1 votes
A problem is called solvable by Dynamic Programming if its solution can be calculated by solving its sub-problems.

Let's see how the current state of the given problem depends on its previous states (aka sub-problems).

Let the answer to the block in colour C be denoted by Ans(C).

We can clearly see that,

**Ans(PINK) = 1 + Ans(BLUE) + Ans(ORANGE) - Ans(GREEN)**

*Note: we are subtracting the GREEN block because it was added twice (once in ORANGE and once in BLUE).*

Mathematically speaking, if **Ans(i,j) = answer to the block starting from (i,j) and ending at (n,m).**

**Ans(i,j) = 1 + Ans(i+1,j) + Ans(i,j+1) - Ans(i+1,j+1)** This is known as the Dynamic Programming transition.

The base cases are self-explanatory :)

2D Prefix Sums (generalised solution): https://usaco.guide/silver/more-prefix-sums?lang=cpp

# Answer
> 0 votes
Let $A\[i,j\]$ be the total number of people a person in that cell can see.

The following recurrence can help you:

$$A\[i,j\]= \begin{cases} m\times n, & \text{if $i=0$ and $j=0$}\\ A\[i,j-1\]-m, & \text{if $i=0$ and $j≠0$}\\ A\[i-1,j\]-n, & \text{if $i≠0$ and $j=0$}\\ A\[i-1,j-1\] -m-n+1, & \text{otherwise} \end{cases}$$

Try and work through the math for yourself. If you still have trouble understanding the logic, then feel free to ask.

More generally, to solve problems using dynamic programming, take care of the base case first. In this case, it's the first cell which is the only one that is sort of "hardcoded". Notice how the rest of the cells are all defined based on a previous cell in the table. If you're familiar with induction (which I really hope you are), then this is equivalent to relying on the induction hypothesis.

Hope that helped :)

---
Tags: algorithms, dynamic-programming
---


# Question
Title: Deciding if a graph is "Single Connected"
The definition of "Single Connected" is that for every $u,v \in V$ there is at most a single simple path from $u$ to $v$, and at most a single simple path from $v$ to $u$.

The objective is to find an efficient algorithm to decide whether the graph is "single connected".

I've managed to come up with the following algorithm:

```
for all v in V:
      Perform DFS(v)
      for all e in E, check if:
          there is a forward edge
          there is a cross edge

```

if there is a forward edge/cross edge, we have found another simple path between $u$ and $v$, therefor the graph is not single connected.

This algorithm runs in $O(|V| \cdot (|V|+|E|))$ which is okay, but according to a colleague, this is solveable in linear time.

The most I've been able to think of is using tarjan's algorithm to reduce the graph to a DAG , however I am unsure on how to proceed from there.

I've also managed to find this question:

is it possible to determine using a single depth-first search, in O(V+E) time, whether a directed graph is singly connected?

yet it remains unanswered.

# Answer
Is your graph directed or undirected?

If your graph is undirected then the condition you mention is equivalent to your graph being a forest (every connected component is a tree).
> 2 votes

---
Tags: graphs, connected-components
---


# Question
Title: Are there any mathematical properties of consecutive integer power modulo operations that could be exploited for algorithmic speed gain?
I'm attempting to search through all the integers between 10^15 and 10^16 to check if they are in the oeis sequence A277274, and the entirety of the program can be summarized as mostly equivalent to :

```
for n in range(int(10**15),int(10**16)):
    if pow(3, n, n) == 11:
        print("Found one: {}".format(n))

```

Since the modulo argument is changing each time through the loop, I can't take advantage of modular arithmetic's property of taking a "running modulo" as n increases, and a speedup of powmod due to the modulo argument being prime also seems like it wouldn't help too much due to having to prime test the integers, and primes being less dense in my search area (although a Miller-Rabin prime test might help).

Python's builtin powmod implementation seems rather quick to begin with, but simply incrementing through the integers on my modern machine with one thread would take ~250 years to get through them all, whereas someone exhaustively found all the members of A277274 \< 10^15 in much less than 25 years. So I assume I'm missing something. (And yes, I do realize the problem is "embarrassingly parallel", but even a 20-fold increase in speed will not help my current algorithm)

I'm positive something is just under my nose. And I'm writing this question half as a brainstorming exercise. But I'm guessing 3 or 11 being prime might help, or the prime factorization of 3^n being trivial might lead somewhere, but no algorithmic speedups spring to mind when reading through the properties of modular arithmetic.

# Answer
Do a sieve.

First you can strike out all multiples of 3, 4, and 11. You've already gotten rid of over half.

But now the property that you use is that if `p` is a prime then `3^(kp) mod p = 3^k mod p` which has a pattern that repeats with a period of `p-1`.

So, for example, for `5` the pattern goes `3, 2, 1, 4`. And `11 mod 5` is `1`. And therefore we strike out 3 out of 4 multiples of `5`.

For `7` the pattern goes `3, 2, 6, 4, 5, 1`. And `11 mod 7` is `6`. So we get to strike out 5 out of 6 of the multiples of `7`.

But for `13` the pattern goes, `3, 9, 1, 3, 9, 1, 3, 9, 1, 3, 9, 1`. So we get to strike out all of the multiples of `13`. The same is true for `23`.

For `17`, `19` and `29` we get to strike out all but 1. But for `37` we only get to strike out all but 2.

I think that on average for a prime `p` you will get to strike out `(p-2)/(p-1)` of its multiples. So continue until you have have struck out most values fairly cheaply. And then do the remaining ones with your existing test.

There are a number of ways to parallelize. The basic idea being to hand out a bunch of primes to a worker, have it sieve them and divide the sieve into chunks of fixed size. For each chunk, collect the chunks from all the workers, and use `or` to merge the sieves. Then walk the sieve and come up with a list of candidates and test them.

This is not embarrassingly parallel. But it is going to be good enough that I can see how the program could run fast enough to be acceptable.
> 1 votes

---
Tags: performance, modular-arithmetic
---


# Question
Title: A chatbot's take on dynamic scoping: it is easier to debug - correct?
I asked the chatbot at you.com, "what is an advantage of dynamic scoping?" and it said the following on the pane titled YouChat. (If you click the link, you will probably see a different reply by YouChat since, apparently, there is some random/live factor in its algorithm).

> One of the main advantages of dynamic scoping is that it is more flexible and convenient than static scoping. Dynamic scoping makes it easier to pass parameters from one subprogram to another and allows for more efficient use of memory, as the same variables can be used across different subprograms. Additionally, dynamic scoping makes it easier to debug code as the scope of a variable is more visible.

The last statement threw me since I would have thought that dynamic scoping makes it harder to debug as compared with lexical scoping rather than easier, is that correct?

# Answer
No, it's not correct.

Dynamic scoping is hard to reason about, and therefore hard to debug; because it is hard to reason about, it causes problems for code analysis tools, including optimisers and garbage collectors. If you're thinking about writing a language, implement block-level lexical scoping from the start. Then you won't have to figure out how to shoehorn it into the language later. \[Note 1\].

Really, this answer shouldn't be necessary. Or, it should only be necessary as a response to a claim from a credible source, perhaps a source so old that the error is understandable. But I fear that if left unanswered, this question will continue to contribute to the soup of misconceptions out of which AI brews its answers.

---

### Notes

1. See Perl `my` vs. `local`, or JavaScript `var` vs. `let`/`const`. Changing midstream from one scoping model to another one is difficult and leaves you with a huge legacy corpus using the old model which you have to maintain forever -- or until you get tired of supporting ancient versions -- so it is not a decision to be taken lightly. Think about why both of those languages chose to change their scoping model despite the cost. Read up on the concept of "technical debt"
> 2 votes

---
Tags: programming-languages, compilers, language-design
---


# Question
Title: Ordered sequence with logarithmic insert and remove
**Problem:** we have a sequence of numeric values, e.g. `[102, 25, 77, 17, 2, 13]`. We need to implement 3 operations, each can be at most logarithmic time complexity.

1. `insert(i, v)` \- inserts value `v` at index `i`.
2. `remove(i)` \- removes value at index `i`.
3. `peek(i)` \- returns value at index `i`.

**What I've tried:** AVL tree, where node keys are elements' indices. It theoretically guarantees log time for all three operations. The problem is when we use e.g. `insert(0, v)`, we need to update all of the other indices (we want to keep the proper order), resulting in `O(n)` complexity. Sample sequence would look like this in my way of thinking:

# Answer
I think you have already a good idea with AVL trees.

To improve the data structure, you should keep track of the size of each subtree (and discard indices, they are not really useful here).

In details, a node $x$ of the tree should have the following information:

* value;
* size;
* height;
* pointer to the left child;
* pointer to the right child.

There is no key in there, since those trees are not binary search trees, but the values are ordered by increasing indices when considering the in-order (like the keys in a BST). However, since the indices may change during the process, as you have stated, there is no use in storing those.

Peeking is the easiest algorithm:

```
define a.peek(i):
   s ← a.left.size
   if s = i then return a.value
   if s > i then return a.left.peek(i)
   return a.right.peek(i - s - 1)

```

To insert an element at position $i$, we search the position the same way as the peeking is done and continue in the left or right child (eventually with the node it replaces). All size and heigths or ancestors must be modified and some rotations may be necessary to keep the balance of each node.

```
define a.insert(i, v):
   if a is empty then
      a.value ← v
      a.size ← 1
      a.height ← 0
      a.left ← empty
      a.right ← empty
      return
   s ← a.left.size
   if s = i then
      if a.left.height < a.right.height then
         a.left.insert(i, v)
      else
         a.right.insert(0, a.value)
         a.value ← v
      a.size ← a.size + 1
      a.height ← 1 + max(a.left.height, a.right.height)
   else if s > i then
      a.left.insert(i, v)
      a.size ← a.size + 1
      a.height ← 1 + max(a.left.height, a.right.height)
      if a.left.height > a.right.height + 1 then
         do a right rotation
   else
      //similar insertion in the right child

```

When deleting a node, it need to be replaced. The easiest way to do it is to use a node in the child of greatest height, either the rightmost node in the left child or the leftmost node in the right child. Implementation left to you.

All those operations have time complexity linear in the height of the tree, which is logarithmic in the size, given that the balance is keeped.
> 5 votes

# Answer
You need to augment the AVL tree with weight information on every node (i.e. the number of nodes in the subtree rooted there).

Insertion and deletion will require to increment/decrement the weights of all nodes from the root to the insertion/deletion point.

Lookup will use the weight information to choose the descent directions.

Note that the index information remains implicit.

Searching for index $3$:

After deletion:
> 2 votes

---
Tags: algorithms, time-complexity, data-structures, search-algorithms, avl-trees
---