title: Grammar with fewest variables

text:
# Question
Title: Grammar with fewest variables
I am looking over a past exam for a theory of computation class I am taking, and unfortunately no solutions are provided. I am stuck on this question, and would greatly appreciate any help or hints.

1. The Myhill-Nerode Theorem provides the minimum number of states of a DFA to recognize a regular language. Argue that an analogue for context-free languages is unlikely to be discovered.
2. Prove that the grammar with fewest variables equivalent to a grammar G is uncomputable.

# Answer
> 2 votes
Let $L \neq \emptyset$ be a language over some alphabet $\Sigma$, let $|$ be a symbol not in $\Sigma$, and consider the language $|L = \\{ |w : w \in L \\}$. Suppose that $L$ could be generated using a context-free grammar with a single nonterminal $S$.

Since $L \neq \emptyset$, $S \Rightarrow^\* |w$ for some word $w$. Therefore:

* Every rule contains at most one $S$ on the right-hand side. Indeed, otherwise you could generate a word with more than one $|$.
* Every rule containing exactly one $S$ must be of the form $S \to Sw$, where $w \in \Sigma^\*$. Indeed, the rule cannot contain $|$, since otherwise $S$ would generate a word with more than one $|$; and the rule cannot contain anything to the left of $S$ since then $S$ would generate a word not beginning in $|$.
* Every rule not containing any $S$ must be of the form $S \to |w$, where $w \in \Sigma^\*$ (in fact, $w \in L$).

Let $A$ be the collection of words $w \in \Sigma^\*$ for which there is a rule $S \to |w$, and let $B$ be the collection of words $w \in \Sigma^\*$ for which there is a rule $S \to Sw$. Thus $$ L = |AB^\*. $$ Conversely, it is easy to check that every language of this form (with $A,B$ finite) has a context-free grammar with a single nonterminal. Considering also the empty language, we have shown:

> The language $|L$ can be generated using a context-free grammar with a single nonterminal iff $L = AB^\*$ for some finite (possibly empty) $A,B$.

The collection of languages of the form $AB^\*$ is closed under quotient from the left, which is the following operation: $\sigma^{-1}S = \\{ w : \sigma w \in S \\}$. Indeed, if $\epsilon \notin A$ then $\sigma^{-1}(AB^\*) = (\sigma^{-1}A)B^\*$, and if $\epsilon \in A$ then $\sigma^{-1}(AB^\*) = (\sigma^{-1}A)B^\* \cup (\sigma^{-1}B)B^\*$. Therefore, Greibach's theorem shows that determining whether a context-free grammar generates a language of the form $AB^\*$ is undecidable.

Given a context-free grammar $G$, we easily construct a context-free grammar for $|L(G)$. The language of this context-free grammar can be generated by a single nonterminal iff $L(G)$ is of the form $AB^\*$, and so the following problem is undecidable: Given a context-free grammar, determine whether its language can be generated by a context-free grammar with a single nonterminal.

# Answer
> 1 votes
Suppose we can find $G’$ \- a grammar with the fewest variables and equivalent to $G$ \- with the help of a Turing machine $T$. Thus there exists $T$ taking input $G$ and giving output $G’$. Suppose that $G’$ is unique up to relabeling of variables.

Then we can use this $T$ to decide ${EQ\_{CFG}}^1$ ; i.e. by applying $T$ on $G\_1$ and on $G\_2$ and deciding if the descriptions are equivalent (using exhaustive search is possible since we have a finite number of rules and variables). This is a contradiction because $EQ\_{CFG}$ is undecidable.

$ ^1 $\- whether two CFGs are equivalent or not

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


# Question
Title: Winning strategy for a given game on graphs
The game goes as follows. Two players are playing a game, player 1 and player 2, in which the first player starts by naming a hero $h\_1$, then player 2 responds with a villain $v\_1$ who has played in a movie with $h\_1$. Then player 1 responds with another hero $h\_2$ who has played in a movie together with $v\_1$, and so forth. Each hero and villain can be used at most once. The first player that can not name any character (available heroes/villains do not have a common film with the last choice of the other player), loses the game. Player 1 always starts the game.

The input is a set of heroes $H$, a set of villains $V$ ($|H| = |V| \geq 1$) and a family of movies $M$, where each movie is a set of heroes and villains who appeared in that movie.

The question is: Can you, based on $H$, $V$ and $M$, decide which player wins the game assuming both players are playing optimally?

---

Example:

Given the following data: the heroes are *Iron Man*, *Captain America*, *Thor* and *Spider-Man*. The villains are *Whiplash*, *Ultron*, *Thanos* and *Vulture*. The movies are *Avengers: Infinity War* (stars Iron Man, Captain America, Thor, Thanos and Spider-Man) and *Spider-Man: Homecoming* (stars Iron Man, Vulture and Spider-Man). Can you decide which player has the winning strategy?

---

My approach is to use maximum bipartite matching to find out which player has the winning strategy, because we can split the data in two sets, namely $H$ and $V$ and have relations between those two sets. The Hopcroft-Karp algorithm can take two of such sets and find out the maximum cardinality. Please correct me if I'm wrong: in the cases in which there is a perfect matching, player 2 wins and otherwise player 1 wins. Whenever there is a perfect matching, it means that player 2 has always had an answers to the hero that player 1 named.

How would you solve this? Is there a better, more efficient solution than some maximum bipartite matching.

# Answer
The short answer is, Player two wins if and only if the corresponding graph admits a matching that "covers" the set $H$.

---

Here is a bit of explanation.

Your idea is almost right. However, the proof is not intuitive and you might miss some details which you need if it is a theoretical question or if you need to design the exact winning strategy and not only output the winning player.

So let us start with the part missing from your answer. Assume a given instance corresponds to a graph that admits a perfect matching. According to your strategy, Player 2 wins in this case which is right. Now assume the same instance is given with one more villain, or ten more villains or one thousand of them. Clearly, player two still wins since adding villains, regardless to how we assign them, only helps the second player. So your claim does not always hold. However, your answer is very close to my claim and have the same intuition. It is only missing a bit of formality.

**Claim.** Assuming both players are playing optimally, Player 1 wins if and only if, given an instance $I$, the corresponding graph does not admit a matching saturating the set $H$.

So what does that mean? A matching saturates a set of vertices $S$, if each vertex in $S$ is incident to a vertex in the matching. Now we prove the claim. We show two winning strategies one for Player two when the graph admits a matching the saturates the set $H$ and one for Player two when the graph does not admit such a matching.

**Proof.** Now assume the graph admits such a matching. Let this matching be $M$. The strategy goes as follows. As long as Player one did not lose, for each choice $h \in H$ for Player one, choose $v \in V$ the vertex matched to $h$ in $M$.

The correctness follows directly from the fact that each vertex of Player two is unique and adjacent to the choice of Player one (due the properties of a matching). Intuitively, Player one will run out of moves at some point (possibly after choosing all heroes in the set $H$).

Now assuming the graph does not admit a matching saturating $H$, according to Hall's theorem, there is a subset $A \subseteq H$, such that $|N(A)| \< A$. Choose such a set that is minimal inclusion-wise. We claim that there is a matching $M'$ that saturates $N(A)$. Assuming otherwise, again due to Hall, there is a subset $S \subseteq N(A)$ such that $|N(S)| \< S$, but then removing $N(S) \cap A$ from $A$ and $S$ from $N(A)$ yields a subset of $A$ that also contradicts Hall's condition which forms a contradiction to the choice of $A$ to be minimal. Hence, there is a matching $M'$ that saturates $N(A)$.

Now the strategy goes as follow. Choose a vertex in $A$ that is not incident to any edge in $M$. Such a vertex exists since $|N(A)| \< |A|$. Choose this vertex at first and for each choice $v \in V$ of player two, choose the vertex $h \in H$ matched to $v$ in $M'$.

Again, it is easy to see that Player two will run out of moves at some point (possibly after choosing all vertices in $N(A)$) and hence, Player one wins.
> 4 votes

---
Tags: algorithms, graphs, bipartite-matching, game-theory
---


title: Ambiguous Grammar demostration exercise

text:
# Question
Title: Ambiguous Grammar demostration exercise
Hi im stuck on an exercise of ambiguous grammar. I need an example that shows that this grammar is ambiguous. The grammar is defined as follows:

$$S \rightarrow aT | bR$$ $$R \rightarrow a | aS | bRR$$ $$T \rightarrow b | bS | aTT$$

Thanks!

# Answer
An example is the word $aabbab$.

We can either create it like this $$S \rightarrow aT \rightarrow aaTT \rightarrow aabST \rightarrow aabbRT \rightarrow aabbaT \rightarrow aabbab.$$ Or like this $$S \rightarrow aT \rightarrow aaTT \rightarrow aabT \rightarrow aabbS \rightarrow aabbaT \rightarrow aabbab.$$
> 0 votes

---
Tags: formal-grammars, ambiguity, tree-grammars
---


# Question
Title: Deterministic pushdown automaton for a given language
I am trying to make a deterministic pushdown automaton from this language but without success. Here is the language definition:

$\ L=\\{0^n 1^m a^i b^j \ /\ m,n,i,j \> 0 \ and \ m+n=i+j \\} $

Thanks!

# Answer
Let us start with an automaton for ${2^rc^r}$ for the alphabet $\\{2, c\\}$. This is quite a standard example. As long as you are reading $2$ add a letter to the stack until you read the first $c$. Then for each $c$ pop a letter from the stack. The word and the stack should finish at the same time.

Now using this automaton we should be able to build one for you language, where the string of $c$s should turn to any concatenation of a staring of $a$s and a string of $b$s and the string of $2$s turns into a concatenation of a string of ones and a string of twos. This means for each zero you read push a letter to the stack until you read the first one. Then for each one push a letter to the stack until you read the first $a$ then for each $a$ pop a letter until you find the first $b$ and then pop for each $b$. The stack should turn empty upon reading the last letter in the world. Note that the DPA should rejects the string if at any point it reads an unexpected letter (a $0$ after an $a$ for example).

Note that one of the substrings might be empty, so you should consider the case of starting with $a$s directly after zeroes for example.
> 1 votes

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


# Question
Title: Path with least max-weight, in an undirected connected graph
The problem we were given, states that we have graph, where vertices are cities, and edges are roads. Each edge has a weight equal to the kilometers of the corresponding road. We want to get from city $A$ to city $B$, with a car that can last up to $M$ kilometers in one go, but we can refuel, every time we go to a city. It isn't mentioned, but i guess we can't suppose that the graph is acyclic, since it represents a country's map.

We need to find two algorithms that give as the least $M$ our car needs to have to get from a city $A$ to city $B$. One should have time complexity $m\log m$, and the other one linear (where $m$ is the number of edges).

I thought that we could use BFS/DFS for that, but they aren't what we are looking for, because of the complexity. The only other thing I came up with is using Kruskal algorithm somehow, because it has the complexity we want, and also the graph is connected, so maybe we have less things to worry about. As for the linear one, I can't find anything.

# Answer
> 2 votes
This problem is known as the minimax path problem. A linear time algorithm is given in this note. I quote it here. Note the note solves the bottleneck shortest path problem, and to solve your original minimax path problem, you should reverse the sense of all the weight comparisons performed by the algorithm, or equivalently replace every edge weight by its negation.

> The correctness of Algorithm 1 (for undirected graphs) is rather obvious: If in line 6 it turns out that the graph still is $s$$t$–connected, than hiding the edges of weights less than $M$ in line 5 did not affect the optimal solution. Otherwise, in each subgraph to be shrunken in line 9, every vertex can be connected to every other one by a path with capacity at least $M$; thus the bottleneck of $t$ (being smaller than $M$) will remain the same in the shrunken graph.
>
> Furthermore, the algorithm runs in time $O(m)$, where $m = |E|$ denotes the number of edges: The crucial observation is that in every iteration of the loop in lines 3–11 half of the edges are removed from the graph, either by shrinking all "thick" edges (in line 9) or by dropping all "thin" edges (in line 5). As all steps inside that loop can be done in linear time in the size of the current graph, the total running time is bounded by $$O(m)+O\left(\frac{m}{2}\right)+O\left(\frac{m}{4}\right)+\cdots=O(m).$$ This shows the following result.

# Answer
> 0 votes
Please check whether $m$ is the number of edges. If the graph is complete, we need at least $O(m^2)$ time just for reading weights of all edges.

Anyway, Kruskal looks like the right algorithm to think about.

We need to find the first $M$ such $A$ and $B$ will belong to the same component in the graph induced by the set of edges with weights $\le M$. It means that we can check this condition after each Kruskal' iteration, and when it holds at the first time, weight of the last edge will be an answer.

If we use, e.g., DSU for the implementation, we will have complexity $O(E \log E)$, where $E$ is the number of edges.

If the set of edges is already sorted, we get $O(E \cdot{} \alpha(m))$. If not, I don't think that a linear algorithm exists, because intuitively it should be not easier than sorting.

---
Tags: algorithms, graphs
---


# Question
Title: Using the pumping theorem to show that this language is not context-free
Let $\sigma = \\{a,b,c\\}$ and let $L = \\{s | s = a^jb^jc^k\\}$ where $k=i\cdot j$ and $i,j \geq 0\\}$. Using the pumping theorem, prove that $L$ is not context-free.

I really don't know where to start, here. Nobody in the class knows what to do and we're all failing pre-curve.

# Answer
> 0 votes
Suppose that $L$ is context-free. Then the pumping lemma for context-free languages tells us that $L$ has a pumping length $p \ge 1$. We want to show that this leads to a contradiction, by exhibiting a string that is in $L$ but cannot be pumped in the manner specified in the lemma.

Consider the string $s = a^pb^pc^{(p^2)}$. Clearly, $s \in L$.

Now, see if you can show that all the possible ways of breaking down this string into the chunks specified in the lemma lead to a pumped string that is *not* in $L$.

---
Tags: formal-languages, context-free, pumping-lemma
---


# Question
Title: Why does the category of language types have morphisms, not functors?
I am probably not phrasing this question well, so please bear with me as I try to explain what I mean.

I am working on learning category theory, as applied to programming. So far, I understand that:

* Objects in a category are "unbroken"; you're not supposed to peer inside them to see their internal structure.
* Any Set is a category
* Programming language types can be thought of as sets. (Bool is the set True, False; Int is the set of all integers; etc.)
* Thus, all of the types in a language form a category of sets.
* Morphisms are arrows between objects.
* If those objects are themselves categories, then the morphisms get called functors.

Taken together, that would imply that a function from Int to Bool is a functor, because it's a map from the the set category Int to the set category Bool.

However, I have also read elsewhere (in particular https://www.johndcook.com/blog/2014/05/10/haskell-category-theory/), that thinking of it that way is wrong and we really shouldn't be talking about language types being a base category with "just" morphisms. But I don't see how that fits with my previous logic.

I therefore must conclude that my previous logic is faulty, but I'm unclear how or why. What is the right way to conceptualize this? Are Sets just extra special exceptions? Or is it really just an arbitrary matter of preference for how to view the problem space? Or am I just flat out wrong somewhere?

# Answer
> 4 votes
There are several ideas floating around here. You can look at a programming language through a categorical lens, and then types are objects, and they are indeed opaque. So Bool is not a set of True and False in this picture. It's an object that has two morphisms (injections) going into it, one corresponding to True, and one to False. In Haskell these are the two constructors of Bool. They take no arguments, but that is interpreted as being morphisms from the terminal object (the unit type). It all works out nicely.

Then there is the more traditional picture where types are just sets of values and morphisms are functions between sets. Sets and functions form a category Set. That picture works nicely as long as you don't talk about partial function (ones that loop forever).

Then there is the third idea that every individual set is a category in itself. It's a discrete category, meaning there are no morphisms (other than identity) between elements. In that case, functions between sets would indeed correspond to functors between discrete categories. But a functor between discrete categories is nothing but a function on objects (elements) which is trivial on morphisms, so it's not a very interesting point of view.

---
Tags: programming-languages, category-theory
---


# Question
Title: Weighted Average of Neural Networks with Cross Entropy Cost Function
What is the best way to create an ensemble of neural networks utilising weighted averaging when these networks were trained to minimise cross entropy error function?

The literature I found (e.g. \[1\]) seems to be talking only about weighted averages of neural networks that employ mean square error (MSE) cost function. Anything other than that seems to require a modification of the training algorithm. Is there an analytic extension of \[1\]'s generalized ensemble method (GEM) algorithm to compute neural networks' weightings when cross entropy error function is used? Or some entirely different algorithm would be required? Or maybe it can only be done by numerically estimating those optimal weightings?

\[1\] M. P. Perrone and L. N. Cooper, "When networks disagree: Ensemble methods for hybrid neural networks," in Artificial Neural Networks for Speech and Vision. Chapman and Hall, 1993, pp. 126-142.

# Answer
> 1 votes
*Disclaimer:* In most situations, I would expect that a single neural network will be at least as good as an ensemble, so there's typically probably not much reason to bother with an ensemble. In particular, if we compare an ensemble of $n$ small neural networks to a single big neural network that is $n$ times as large, I would expect that typically the big neural network will perform at least well as the ensemble. So in most situations you're probably better off skipping the ensemble and training a big neural net. That said, here's how you can train an ensemble.

*Unweighted average:* The simplest way to train an ensemble is to use an unweighted average of the softmax outputs of the individual networks. Let $F\_1,\dots,F\_n$ denote the networks in the ensemble, $F\_i(x)$ denote the vector of softmax outputs of the $i$th network on input $i$, and $F\_i(x)\_c$ denote the softmax output for class $c$ from $F\_i(x)$. Define $F$ by

$$F(x) = (F\_1(x) + \dots + F\_n(x))/n,$$

i.e.,

$$F(x)\_c = (F\_1(x)\_c + \dots + F\_n(x)\_c)/n.$$

This is the unweighted average of the individual networks. You can train $F$ in two ways: either train each network individually, or train the whole ensemble end-to-end.

* To train the ensemble end-to-end, you treat $F$ as a big model whose parameters are all of the parameters of all of the networks, and you optimize cross-entropy loss applied to the output of $F$.
* Alternatively, you can train each network individually. Train $F\_1$ using cross-entropy loss on the output of $F\_1$; then train $F\_2$; and so on.

In principle, end-to-end training should yield performance at least as good as training each network individually. However, training each network individually is simpler and requires less memory on the GPU.

*Weighted average:* We can generalize these ideas to train an ensemble that is a weighted average of the outputs of the individual neural networks. Define $F$ by

$$F(x)\_c = {\alpha\_{1c} F\_1(x)\_c + \dots + \alpha\_{nc} F\_n(x)\_c \over \alpha\_{1c} + \dots + \alpha\_{nc}},$$

where the $\alpha\_{ic}$ are the weights. There are two ways to train such an ensemble:

* You can train it end-to-end. You have a big model for $F$, whose trainable parameters are the parameters of the individual networks as well as the weights $\alpha\_{ic}$. Then, apply an optimizer to minimize cross-entropy loss applied to the output of $F$.
* Alternatively, you can train each network individually, then fix the networks and train the weights $\alpha\_{ic}$ subsequently. Once you've trained the individual networks, compute new feature vectors $v\_{ij} = F\_i(x\_j)$, where $x\_j$ is the $j$th element of the training set. Now you can throw away the $x$'s and work only with the $v\_{ij}$'s, as we have $$F(x\_j)\_c = {\alpha\_{1c} v\_{1jc} + \dots + \alpha\_{nc} v\_{njc} \over \alpha\_{1c} + \dots + \alpha\_{nc}}.$$ Finally, user an optimizer to learn the parameters $\alpha$ that minimize the cross-entropy loss on $F(x\_j)$'s, using the above equation to relate this to the (trainable) $\alpha$'s and the (fixed) $v$'s. Any stochastic gradient descent based optimization method should work fine. You might want to initialize all the $\alpha$'s to $1/n$, and renormalize the $\alpha$'s after each iteration to prevent them from growing without bound.

The same tradeoffs between end-to-end training vs training each network individually apply.

I'm not expecting an ensemble based on a weighted average to do significantly better than an unweighted average, in most cases; and I'm not expecting an ensemble to do significantly better than a single large network, in most cases. But there could always be exceptions, and hopefully this gives you a reasonable way to train such ensembles.

---
Tags: neural-networks
---


# Question
Title: Given an unsorted list of $n$ items, how many random comparisons are needed on average to be able to sort the list?
There is an unsorted list of $n$ items $x\_1, \ldots, x\_n$. Until you can sort the list, you are given one of the ${n \choose 2}$ possible binary comparisons uniformly at random (with replacement).

On average, how many of these random comparisons will you need to be able to sort the list?

Some follow-up questions:

1. What does the distribution for the number of comparisons needed look like?
2. What is the answer if you use $k$-ary comparisons instead of binary ones.
3. What is the answer if the comparisons are made without replacement (i.e. you won't get the same comparison twice)?
4. Given a set of comparisons, how can one check if the list is sort-able? I'm almost certain the answer is to construct a DAG and topological sort, but I just want to confirm.

An exact-ish answer would be nice, but a big $O$ answer is fine too, I suppose.

# Answer
> 5 votes
Asympotically, you'll need $\Theta(n^2 \log n)$ comparisons.

Suppose $x\_{(1)},\dots,x\_{(n)}$ denotes the elements in sorted order. Then if you don't see a comparison between $x\_{(1)}$ and $x\_{(2)}$, you will have no way to tell which order they should appear in. The same is true of every pair of adjacent element. So, there are $n-1$ coupons (one per adjacent pair of elements), and you need to collect them all. Based on the coupon collector problem, we know you'll need $\Theta(n \log n)$ randomly chosen coupons before we've collected them all. Each observation has a $2/n$ chance of being a coupon, so in total we'll need $\Theta(n^2 \log n)$ observations before we've collected all the coupons. If we collect all the coupons, we can sort the $x$'s; if we're missing any coupon, we can't sort them.

The subsequent questions boil down to facts about the coupon collector problem, and you can use the tail bounds on Wikipedia to bound the information about the distribution.

If comparisons are chosen without replacement, then you need $\Theta(n^2)$ observations.

A reasonable way to check whether the list is sortable is to do a topological sort, then check that you've observed a comparison between every pair of adjacent items in the topologically sorted order.

---
Tags: sorting, probability-theory, randomized-algorithms, dag
---


# Question
Title: How to prove properties about a specific modular arithmetic equivalence
Ever since I was introduced to modular arithmetic, I've had some trouble with it. I think it uses a part of my brain that I haven't used often. Anyways, I've been thinking about this specific equivalence: $$a^3 \equiv 5 \\, (\text{mod } 7)$$ And I have a hunch that no $a$ exists s.t. this equivalence is true. Simulating it, it's clear that there is a pattern: 6, 1, 6, 6, 0, **1, 1, 6, 1, 6, 6, 0,** 1, 1, 6, 1, 6, 6, 0...

But I can't figure out how to formally prove 1. that this pattern is the actual pattern and as an extension, 2. that the equivalence above doesn't hold (it should be trivial if I can prove 1).

Can anyone help? Thanks so much.

# Answer
You can prove it by calculating the value of $a^3 \bmod 7$ for $a=0,1,2,3,4,5,6$; if none of those yield 5, then you have proven the claim.

Why is this sufficient? Well, if $a \equiv b \pmod 7$, then $a^3 \equiv b^3 \pmod 7$. So, if there was any solution to $a^3 \equiv 5 \pmod 7$, then you could take $b = a \bmod 7$, and that would be another solution. Now $b$ is one of $0,1,2,3,4,5,6$, so we've proven that if there is any solution, then one of $0,1,2,3,4,5,6$ must be a solution. Conversely, if none of $0,1,2,3,4,5,6$ is a solution, then there is no solution whatsoever.

For the special case of squaring (rather than cubing), you might be interested in quadratic reciprocity, which is a more advanced technique that allows to check for the existence of solutions to such an equation. There is also cubic reciprocity, though I'm not sure whether it leads to an efficient algorithm to check for solutions when you have a cube instead of a square.
> 3 votes

---
Tags: proof-techniques, modular-arithmetic
---


# Question
Title: Is it decidable whether a given Turing machine moves its head more than 481 cells away from the left-end marker, on input ε?
So, while reading some problems on decidability, I came across the following resource: https://www.isical.ac.in/~ansuman/flat2018/tm-more-undecidable.pdf

Here, on page no 12, it is written that the problem is decidable and with the following argument:

> "Yes, Simulate M on for upto m^481 · 482 · k steps. If M visits the 482nd cell, accept, else reject."

I am quite confused with the step count. Can anyone please explain what does this mean, or maybe point to some resources where I can find a proper explanation!!!! Image of the slide

# Answer
A run of a TM is a sequence of *configurations*, where each configuration states the contents of the tape (from the left marker, up until the point where it is blank all the way to the right), the location of the head, and the state.

An important feature of (deterministic) TMs is that you can uniquely continue a run from a given configuration. That is, a configuration has all the information you need to proceed.

In particular, if a configuration $c$ yields a runs that gets back to $c$, at some point, then the run is stuck in a loop (note that this is not a necessary condition, a run might not halt while never repeating a configuration!).

Now, consider all the possible configurations that use up to 481 cells. There is a finite amount of those, namely $m^{481} \cdot 482 \cdot k$ (where $m$ is the size of the alphabet, and $k$ is the number of states).

Thus, if you simulate the run for that many steps, then either at some point the machine goes beyond 481 cells, in which case you accept, or it doesn't, in which case you know for sure that a configuration must repeat (by the pigeonhole principle), so you can reject.
> 4 votes

---
Tags: turing-machines, automata, undecidability
---


# Question
Title: What is f(x,y) in Digital Image Processing?
I am a novice in Digital Image Processing, and while reading the book of DIP by Gonzalez and Woods, I find that they have represented digital image as $f(x,y)$ but nowhere it is mentioned what is $x$ and $y$ actually that we are passing to the function $f?$ Does $f(x,y)$ represent the intensity of the points located at point $(x,y)$, so does $f$ actually returns the intensity of the pixel at that point or is it something else that I am missing?

# Answer
Yes, it represent the intensity at that point.

```
f( x, y ) gives the intensity of a channel at position (x, y)

```

Source : https://courses.cs.washington.edu/courses/cse557/00wi/lectures/imageprocessing.pdf
> 1 votes

---
Tags: image-processing
---


# Question
Title: Normalization in IBM hexadecimal floating point
According to the Wikipedia link of IBM hexadecimal floating point:

> Consider encoding the value −118.625 as an IBM single-precision floating-point value.
>
> The value is negative, so the sign bit is 1.
>
> The value 118.62510 in binary is 1110110.1012. **This value is normalized by moving the radix point left four bits (one hexadecimal digit) at a time until the leftmost digit is zero, yielding 0.011101101012.** The remaining rightmost digits are padded with zeros, yielding a 24-bit fraction of .0111 0110 1010 0000 0000 00002.
>
> The normalized value moved the radix point two digits to the left, yielding a multiplier and exponent of 16+2. A bias of +64 is added to the exponent (+2), yielding +66, which is 100 00102.
>
> Combining the sign, exponent plus bias, and normalized fraction produces this encoding:
>
> S Exp Fraction
> 1 100 0010 0111 0110 1010 0000 0000 0000
> In other words, the number represented is −0.76A00016 × 1666 − 64 = −0.4633789… × 16+2 = −118.625

Now, the definition of normalization according to Wikipedia says that

> In base $b$ a normalized number will have the form $±d\_0.d\_1d\_2d\_3...×b\_n$ where $d\_0≠0$, and the digits $d\_0,d\_1,d\_2,d\_3,...$ are integers between $0$ and $b−1$

So, how is $0.011101101012 \times 16^2$ a normalized number?
In fact this number cannot be represented as a normalized one with base $16$ exponent because the closest we can get is $1.1101101012 \times 16^1 \times 2^2$. What am I missing here?

# Answer
I'm going to start with this famous quote from James Wilkinson's 1970 Turing Award Lecture, *Some Comments from a Numerical Analyst*.

> In the early days of the computer revolution computer designers and numerical analysts worked closely together and indeed were often the same people. Now there is a regrettable tendency for numerical analysts to opt out of any responsibility for the design of the arithmetic facilities and a failure to influence the more basic features of software. It is often said that the use of computers for scientific work represents a small part of the market and numerical analysts have resigned themselves to accepting facilities "designed" for other purposes and making the best of them. I am not convinced that this in inevitable, and if there were sufficient unity in expressing their demands there is no reason why they could not be met. After all, one of the main virtues of an electronic computer from the point of view of the numerical analyst is its ability to "do arithmetic fast." Need the arithmetic be so bad!

In 1970, Fortran had only been cross-platform for four years. A lot of numerical analysis was being done on IBM hardware, and System/360 in particular, but every CPU vendor had its own floating point format, and most of them (as Wilkinson indicated) were not designed by those who demanded high-quality floating point arithmetic.

Today, the industry has standardised on IEEE-754. It's imperfect, because everything is, but it's reliable and can be relied upon.

Wikipedia's definition of "normalised number" (or "normalized number"; I'm going to type it as my dialect spells it) is the current modern definition. It's the one you learned in high school when discussing scientific notation. It's the one used by IEEE-754. It's the one that's in all the modern textbooks.

But it's not the only normal form for floating point that has existed, and I think that's the source of the confusion here.

Interestingly, it's not the only normal form in use today! There is at least one place in modern programming where a different normal form is still in use, because it pre-dates IEEE-754.

The C standard library has a function to extract the parts of a floating-point number's normal form, called `frexp`. But the normal form that it uses is that the mantissa is in the range $\left\[ 0.5, 1 \right)$, not the modern $\left\[ 1, 2 \right)$. This is a notorious "gotcha" for numeric analysts working in C or C++ today.
> 1 votes

---
Tags: floating-point, numeral-representations
---


# Question
Title: How to prove Shortest Common Superstring is NP-Hard
After some research and many youtube videos I have learnt that to prove a problem is *NP-Hard*; you would need to reduce that problem to known NP-Hard problems such as Subset Sum Problem, Halting Problem, Satisfiability Problem or Traveling Salesman Problem. Now my problem is **Shortest Common Superstring**

* **Input:** A finite set R = {r1, r2, ..., rm} of binary strings (sequences of 0 and 1); positive integer k.
* **Question:** Is there a binary string w of length at most k such that every string in R is a substring of w, i.e. for each r in R, w can be decomposed as w = w0rw1 where w0, w1 are (possibly empty) binary strings?

In this link it states that the problem is NP-Hard(https://www.geeksforgeeks.org/shortest-superstring-problem/), besides I am using the greedy algorithm stated there to solve the problem.

So I need help with choosing which NP-Hard Algorithm to reduce to and a way to reduce it. I do not expect a full solution(even though it would be welcome), just guidance would be enough. I honestly do not have much clue on how to go about it.

# Answer
This article may help you.

Theorem 1 states that Hamilton path problem can be reduced to SCS even if all strings have fixed length $H \ge 3$.

For your case with strings of any length but fixed alphabet, this is also true, but the proof is more technical.
> 1 votes

---
Tags: algorithms, np-hard, np, nondeterminism
---


title: Multi-agent randomized behavior

text:
# Question
Title: Multi-agent randomized behavior
In **Artificial Intelligence: A Modern Approach** Edition 3, Page of 43, At Single Vs. Multi-agent section's last line, Writer says,

> In some competitive environments, randomized behavior is rational because it avoids the **pitfalls of predictability**.

Can someone help me understanding this line? Specially, what does he mean by **pitfalls of predictability** ?

# Answer
Think of playing the game rock-paper-scissors. If you were using a deterministic algorithm to choose which of rock, paper, or scissors to chose, you'd also choose the same one. Thus, if I played you, I could quickly figure out how to learn every time, because you are predictable. So, it is a better strategy for you to randomize your choice: choose uniformly at random among the three options every time. That makes you unpredictable, and increases your chances of winning the game.
> 2 votes

# Answer
Someone who owns (an abstract of) the book might be able to give you a better contextualized answer, but in general models and simulations are subject to certain 'laws' that the systems they represent usually are not. In the case of multi-agent systems, one of these is the fact that some agent gets to act first on a given time step, even though the designer often assumes and intends for them to act in parallel (this is the result of computers being incapable of truly parallel computation). If the same agent were to consistently act first, that could introduce significant bias into the system. This is probably what the author means with the pitfall of predictability and why randomization is important; so that we can prevent (to some extent) these sorts of issues.
> 2 votes

---
Tags: artificial-intelligence
---


# Question
Title: What is the time complexity of determining whether a solution $x$ exists to $x^k \equiv c \pmod{N}$ if we know the factorization of $N$?
Suppose we are given an integer $c$ and positive integers $k, N$, with no further assumptions on relationships between these numbers. We are also given the prime factorization of $N$. These inputs are written in binary. What is the best known time complexity for determining whether there exists an integer $x$ such that $x^k \equiv c \pmod{N}$?

We are given the prime factorization of $N$ because this problem is thought to be hard on classical computers even for *k* = 2 if we do not know the factorization of $N$.

This question was inspired by this answer, where D.W. stated that the nonexistence of a solution to $x^3 \equiv 5 \pmod{7}$ can be checked by computing the modular exponentiation for $x = 0,1,2,3,4,5,6$, but that if the exponent had been 2 instead of 3, we could have used quadratic reciprocity instead. This lead to my discovery that there are a large number of other reciprocity laws, such as *cubic reciprocity*, *quartic reciprocity*, *octic reciprocity*, etc. with their own Wikipedia pages.

# Answer
If $p$ is prime, then $x^k\equiv c \pmod p$ has a solution if and only if $c^{(p-1)/g} \equiv 1$ where $g=\gcd(k,p-1)$. The solution is given by $x \equiv \sqrt\[g\]{c^h} \pmod p$ where $h^{-1} \equiv k/g \pmod{p-1}$. You can take $g$th roots in polynomial time using an extension of the Tonelli-Shanks algorithm; see On taking roots in Finite Fields by Adleman, Manders, and Miller. (Strictly speaking, this algorithm requires either reasonable number theoretic assumptions or randomization.) Given one solution $x$, the other solutions will have the form $x \beta^i$ where $\beta$ is an element of order $g$ modulo $p$.

If $p^m$ is a prime power and $\gcd(p,k)=1$, then you can use Hensel lifting to test whether $x^k \equiv c \pmod{p^m}$ has a solution. In particular, let $x\_i=x \bmod p^i$ and $c\_i=c \bmod p^i$ and $y\_i = (x\_{i+1} - x\_i)/p$ and $d\_i = (c\_{i+1} - c\_i)/p$. Now find $x\_1$ such that $x\_1^k \equiv c\_1 \pmod p$. If this has no solution, then neither does $x^k \equiv c \pmod{p^m}$, so we can terminate immediately. Otherwise, we're next going to try to find $x\_2$ such that $x\_2^k \equiv c\_2 \pmod{p^2}$. Writing $x\_2 = x\_1 + p y\_1$ and $c\_2 = c\_1 + p d\_1$, we obtain the equation

$$(x\_1 + y\_1 p)^k \equiv (c\_1 + d\_1 p) \pmod{p^2},$$

or equivalently,

$$k x\_1 y\_1 \equiv (c\_1 - x\_1^k)/p + d\_1 \pmod p.$$

If $k x\_1 \not\equiv 0 \pmod p$, then we can let $y\_1 = ((c\_1 - x\_1^k)/p + d\_1) \cdot (k x\_1)^{-1} \bmod p$ and we have a solution for $x\_2$. Otherwise, test whether $x\_1^k \equiv c\_2 \pmod{p^2}$; if it is, then setting $x\_2=x\_1$ gives a solution, otherwise there is no solution and we can terminate. Repeat the same process to find $x\_3$, then $x\_4$, etc., until you have found $x\_m$. While there may be multiple possible solutions for $x\_1$, there is no need to branch and try all of them, because either all will be extendable to $x\_m$ or none will.

I am not sure what to do if $\gcd(p,k)=1$. Perhaps someone else can fill in this gap.

If $N$ is a product of prime powers $p\_1^{m\_1} \cdots p\_n^{m\_n}$, then you can use the Chinese remainder theorem to check for a root modulo each of the $p\_j^{m\_j}$. A root exists modulo $N$ if and only if it exists modulo each prime power; and once you've found a solution for each prime power, you can combine them with the CRT to obtain a solution modulo $N$.

---

Proof for first paragraph: If $p$ is prime, then there exists an element $\alpha$ of order $p-1$; assuming $x \equiv \alpha^X \pmod p$ and $c \equiv \alpha^C \pmod p$, we find that the equation has a solution if and only if $Xk \equiv C \pmod{p-1}$ has a solution, which is equivalent to the stated condition in the first paragraph.
> 2 votes

---
Tags: time-complexity, number-theory, modular-arithmetic
---


title: Converting IPV4 address into Binary

text:
# Question
Title: Converting IPV4 address into Binary
So given an IP address it is converted into binary via calculating the binary of all different segments and then joining them. For example, 12.32.18.01 converted into a binary it would amount to this number in decimal form 12\*2^24 + 32\*2^16 + 18\*8 + 01 My question is why to go through all this trouble and calculation. Why not just get rid of the dots in the original Ip and then convert that integer into binary. So, for this example, the binary of the above example would amount to this integer in decimal 112 032 018 001. I mean what's the problem with second approach?

# Answer
> 1 votes
I am going to answer this question in two parts:
First,
Without reaching into the depths of communication, I want to mention that the data that humans do understand(such as this answer which I am typing) is classified under Layer 7 of the TCP/IP stack. This data gets converted into analog signals that travel over the wire, and any hosts connected to these wires translate these analog signals to electric signals. Electric signals have two states, 0 and 1, which we humans call binary format. So any data on the wire would essentially be looked upon as a sequence of bits and bytes.

The IP address that you mention, is a component of the IP Protocol, and this protocol is used to carry packets end to end between two hosts on a network. So, the data would be added as a payload on top of an IP packet which contains a IP header. Any devices in between these two hosts which operate on Layer-3 of the TCP/IP stack(the network layer!) would use this header to process the packet. Similarly the end hosts would use this header to determine if the packet indeed was sent to them. The IP protocol specifies the syntax and semantics of the IP Packet header, and as you might notice the size of the fields are fixed. Now any machine which is looking at a sequence of bits coming in (with the knowledge that it is receiving the IP header) can just read as many bytes as it wants to extract every field of the header. For example, given that the system knows where the IP header starts, the system could read the first 4 bits and understand that it would just read the version of IP packet.

Second,
The conversion that you mentioned, between binary and dotted decimal, is purely for representing data in human readable format(as the other answer mentions). Tools like Wireshark do this to show details of a packet(the internals of this are fascinating). So, you can choose whichever method to convert one form to the other, but the machines don't really need to do this at the level of the TCP/IP stack where it really matters. The system doesn't really see it as a dotted decimal construct, but a data structure which consists of four 8 byte fields, (or two 16).

Hope this helps !

# Answer
> 0 votes
The dotted-decimal notation for IP Addresses is specifically a "human-readable" format. e.g. IP address 192.168.0.0 is from a private address range. The reason I mentioned "private" is to emphasize on the usefulness of dotted-decimal representation to analyze the classes/subnets that a given IP address represents.

Now, you're right that we could get rid of the dots and directly convert the IP address into an integer. But, it doesn't matter because computers understand numbers (including IP address) only in binary. So, although following notations represent one and the same thing, you might be interested in different notations based on the use-case: studying to grasp concepts, analyzing classes/subnets or debugging actual packet data from the network interface(which will be just a string of zeros/ones).

`192.168.0.0` = `3232235520` = `0xC0A80000` = `0b11000000101010000000000000000000`

---
Tags: algorithms, algorithm-analysis, binary
---


# Question
Title: Is it possible for a syscall to pack together different places in memory?
While programming with buffers like `uint8_t*` in C++ I often arrive at situations on where I'm forced to do copies. For example, if I receive packets in chuncks from the world and I want to parse something big that is formed of these packets, I'd have to create a bigger buffer and store them, in this buffer, sequentially as they arrive. Then I can parse this big buffer efficiently.

Since the kernel can have virtual memory through page tables, shouldn't it be possible for someone to create a syscall that gets a pointer to a list of all these small buffers (and their sizes), and create a big virtual buffer that acts as if I've copied all the mini buffers inside it?

# Answer
No, that isn't possible in general, because the page tables work at a page granularity. If the length of every buffer is an exact multiple of the page table size, and every buffer starts at a page table boundary, you could do what you're proposing, but otherwise you can't. Since buffers usually won't satisfy those conditions, it's not very useful to create such a syscall.

There *are* techniques for structuring software to avoid making copies. However, this often requires that you restructure the code to support this. See https://en.wikipedia.org/wiki/Zero-copy.
> 3 votes

---
Tags: memory-management, os-kernel
---


# Question
Title: one-to-many matching in bipartite graphs?
Consider having two sets $L$ (left) and $R$ (right). $R$ nodes have a capacity limit. Each edge $e$ has a cost $w(e)$.

I want to map each of the $L$ vertices to one node from $R$ (one-to-many matching), with minimum total edge-costs.

Each vertex in $L$ must be mapped to one vertex in $R$ (but each node in $R$ can be assigned to multiple $L$-nodes).

Examples: Consider the capacity of $R$ nodes is $2$.

1) This is NOT correct, since one node from $L$ has not assigned to a node in $R$.

2) This is NOT correct, since the capacity of a node in $R$ is violated.

3) This IS correct. All $L$ nodes are assigned to a node in $R$, and the capacity of $R$ nodes is not violated.

Any idea how can I solve this?

# Answer
> 4 votes
This problem is called the B-matching problem. Where you are given a function $b:V \rightarrow \mathbb{N}$ that assign a capacity to each vertex and a function $u:E \mapsto \mathbb{N}$ that assigns a weight to each edge.

The problem is solvable in polynomial time. An easy solution is to reduce the problem to minimum weight maximum matching. Create $b(v)$ copies of each vertex $v$ and connect each of them to all neighbors of the original vertex v. We get a polynomial time reduction, since for $b(v) \geq \mathrm{deg}(v)$ we can set $b(v) := \mathrm{deg}(v)$ since we can not match $v$ with more vertices than its neighborhood anyway and that each of its neighbors is matched with at most one vertex in your special case.

---
Tags: algorithms, graphs, matching, string-matching
---


# Question
Title: longest palindromic subsequence / substring and dynamic programming
The longest palindromic *subsequence* problem can be solved using dynamic programming because it is recursive and has overlapping subproblems, as described in https://www.geeksforgeeks.org/longest-palindromic-subsequence-dp-12/ .

On the other hand, AFAIK there is no dynamic programming solution to the longest palindromic *substring* problem. In the DP solution presented at https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/ , the overall solution is equal to the naive one: to compare the length of all palindromic substrings. The only difference is that DP is used to speed up the process of finding if each substring is palindromic, which reduces the time complexity from O(n^3) (naive solution) to O(n^2).

Why is there a DP solution for the LP subsequence problem, but not for the substring problem? Is it because the former can be expressed by a recursion and the latter not?

# Answer
Finding substring palindromes of maximum size can be solved in linear time in several ways. Right now come to my mind solutions using data structure such as: \- Manacher \- Palindromic Tree \- Binary search + (Hashing or suffix array) (not really linear but almost, $O(n \cdot \log n)$

If you let me use prewritten code to solve this problem I'd choose first option, is probably the faster and easy way, but personally I don't feel comfortable implementing Manacher from scratch.

I'll try to expand in the binary search + hashing solution.

First let's solve the subproblem: is it substring from a to b a palindrome? If you use rolling hash you will be able to determine hash of substring in O(1), so you can hash the string and it's reverse, and ask whether a substring and it's reversed counterpart match in hash. Notice that this solution is susceptible to fail due to hashing collisions, and one way to address this is using some more elaborated data structure such as suffix array.

After having such function, you can binary search over the length of the palindrome, this is: fix a length k, then go over every substring of length k and check whether it is or not a palindrome.

It has a problem, and it is that function is not monotone over k, but this happens because odd palindromes are not contained in even palindromes necessarily, and vice versa. To address this just run two binary search, first over even integers, and second one over odd integers.
> 1 votes

---
Tags: dynamic-programming
---


# Question
Title: Minimum unweighted anticlique (independent set) cover / partition
Suppose I have a set of integer intervals, and I want to generate a visualization like the one attached. One obvious way of accomplishing this is to put every interval in its own row; this obviously respects the constraint that no two overlapping intervals are put into the same row, but it is hard to read because the number of rows is $O(\mathrm{\\#\\,\\,of\\,\\,intervals})$.

In general, I think the minimum number of rows can be calculated by finding the size of the largest clique in the graph whose nodes are intervals that has an edge iff two intervals overlap. Is there an efficient (polynomial-time, approximate if necessary) algorithm, that, given a set of integer intervals, returns a minimum sized partition of the intervals into "y-axis values" such that no two elements of a subset overlap?

I suspect this problem is equivalent to the following (but disregard this if you disagree): is there an efficient way to compute an exact vertex cover $C$ of an interval graph $G = (V, E)$ such that $\forall I \in C. I^2 \cap E = \emptyset$ and $|C|$ is minimized? It seems like this is closely related to the maximum independent set problem.

# Answer
> 2 votes
This is precisely the graph coloring problem. Each subset of $C$ is a color, and we are trying to prevent adjacent vertices from having the same color, while minimizing the number of colors used. According to these lecture notes there is a polynomial-time greedy algorithm for coloring interval graphs based on the fact that every interval graph has a perfect elimination ordering.

---
Tags: graphs, intervals, clique, vertex-cover
---


# Question
Title: How to remove cycles from a directed graph by edge contraction?
We have cyclic directed graph (possibly disconnected). For cycles consisting of two vertices A-\>B and B-\>A, we replace them by a single vertex. In case of A-\>B, B-\>C, C-\>A we also replace them by one vertex. We replace N vertices when all reachable from each other. Edges leaving a vertex stay as edges leaving the group containing the vertex. For example,

```
digraph cyclic {
        rankdir=BT;
01
2->3
3->2
5->2
6->4
8->3
9->4
a->4
a->9
9->a
b->8
b->c
c->b
6->7
7->8
8->6
}

```

We must obtain

```
digraph acyclic {
        rankdir=BT;
01
5->23
678->23
678->4
a9->4
bc->678
}

```

How is algorithm? Practical application of problem: we have class where method depends from fields and other methods. How decomposite to max number smallest classes? we allow multiple inheritance, inheritance diamond, but not allow cycles.

# Answer
> 2 votes
Since the only way to get rid of a cycle by edge contractions is to contract all the edges of the cycle to result in a single vertex, the vertices of the new graph are the strongly connected components of the original graph. Two vertices have an edge between them if the original components corresponding to these two vertices had such an edge in the same direction.

Strongly connected components can ve found in linear time.

---
Tags: algorithms, graphs, dag
---


# Question
Title: How connected are information theory and algorithmic information theory?
In the book by Cover and Thomas on information theory, there is a chapter on algorithmic information theory (kolmogorov complexity and so forth).

As far as I understand, algorithmic information theory was developed separately from information theory, and Kolmogorov didnt formalize AIT in terms of shannon entropy and so forth (am I wrong?)

**How connected are the two fields?** Are they really about quite separate things? Are there only some marginal connections? Or are they deeply connected?

# Answer
I don't have the background to give a deep answer about how deeply connected the fields are, but Li and Vitanyi's *An Introduction to Kolmogorov Complexity and Its Applications*--probably the most widely known textbook on AIT--repeatedly incorporates mathematical and conceptual material from information theory (such as Shannon entropy) into its presentation of AIT. Here is a quotation from the third edition (p. 73) that illustrates a connection that might be considered deep:

> We are interested in a measure of information content of an individual finite object, and in the information conveyed about an individual finite object by another individual finite object. Here, we want the information content of an object x to be an attribute of x alone, and not to depend on, for instance, the means chosen to describe this information content. Making the natural restriction that the description method should be effective, the information content of an object should be recursively invariant (Section 1.7) among the different description systems. Pursuing this thought leads straightforwardly to Kolmogorov complexity.

(Apart from the fact that most of the paragraph clearly seems to be discussing Shannon information, it comes immediately after a paragraph that discusses a quotation by Shannon.)
> 1 votes

---
Tags: information-theory, kolmogorov-complexity
---


# Question
Title: Complexity of while loop Average,Best,worse case
```
int[]A;
int L=A.length-1;
int index=(L-1)/2;

int k=2*index+1;
while(k<n){
        if(k+1<n){
            if(A[k]<A[k+1]) k=k+1;}
        if(A[index]<A[k]){
            int t=A[index];
            A[index]=A[k];
            A[k]=t;
            index=k;
            k=2*index+1;
        }else break;

```

# Answer
I think your code tries to do heap sorting. Im saying "tries" because youre missing some code.

If you want to know the complexity of the entire algorithm then here it is: Best case: n\* log(n) Worst case: n*log(n) Average: n*log(n)

Where log(n) is the logarithm of n in base 2.

But if youre interested in only the complexity of YOUR while, then it is: Best case: log(n) Worst case: log(n) Average: log(n)

If you want to read more about heaps, try some youtube videos, the wikipedia link, or this link : https://www.geeksforgeeks.org/time-complexity-of-building-a-heap/

Please vote my answer if i helped you.
> 0 votes

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


title: Language to regex

text:
# Question
Title: Language to regex
Let A={a,b}. So the question is to write regular expression such that L(r) which consists of all words.

My answer is this:

```
L(r)= (a+b)* a* b* (a+b)*

```

Is this correct?

Also another solution is:

```
L(r)=(a+b)*

```

Is this correct?

Is (a+b)\* same as (a,b)\* ?

# Answer
> Is (a+b)\* same as (a,b)\* ?

Close, but try not to mix domains. If the regular expression $r$ is the string $(a{+}b)\*$, then the language of $r$ is the set of all strings over $\\{a,b\\}$, or $L(r) = \\{a,b\\}^\*$.

So, $(a{+}b)\*$ and $\\{a,b\\}^\*$ denote the same set of strings. The first one as regular expression, the second one in set notation.
> 1 votes

---
Tags: automata, finite-automata, regular-expressions, discrete-mathematics
---


# Question
Title: Interpolation: How to generate 3D objects from 2D cross-sections?
Consider a sphere sitting on an $xy$-plane, and take 2D slices parallel to the $xy$-plane at various heights of z. Suppose we take 10 slices, evenly spaced along the $z$-axis, and now have 10 images of circles each with a corresponding $z$.

My goal would be a function that could learn from these 10 slices, such that if I were to input a new value of z, it would draw a circle (that is ideally close to the correct circle at that height).

Would there be a way to train something like a neural network to take the height z as the input, and output circles corresponding to the slice of a sphere at a particular height?

Such a method should scale to multiple dimensions. For example, if I had some multidimensional object I wished to reconstruct using slices of that object. Note that the parameter corresponding to slices may now be a vector.

EDIT: The goal is to interpolate between 2D shapes that do not have simple analytic solutions. For example, one image is a circle and another is a rectangle.

The problems I am facing are where there are no simple analytic solutions for new shapes as a function of z. Imagine that there exists a very rugged non-linear 3D object (like the cross section of a person) - but we can only determine a few slices of this object as it is computationally expensive for some reason. We wish to interpolate between these few slices and generate a 3D object. Such a solution should also work for strange multidimensional shapes beyond 3D.

# Answer
> 1 votes
A neural network is not a good choice for this. For this task, you can get a much better solution by analytically solving for the unknown radius of the sphere. In particular, if the radius of the sphere is $s$, then a slice at height $z$ will have radius $r$, where these three variables satisfy the equation

$$(s-z)^2 + r^2 = s^2.$$

Re-arranging, we find

$$s = {z^2 + r^2 \over 2z}.$$

So, you can solve immediately for the radius of the sphere. Once you know the radius of the sphere, you can predict the radius of other slices at any height of your choice, using the above equations a second time.

---

You could certainly train a neural network to interpolate, given enough training data. For instance, the input to the neural network might be 6 images: the three slices "above" z, and the three "below", and the output is a bunch of slices interpolated between the one above z and the one below; where each image is a picture of the slice. However I'm not sure how well this will work, and it will likely require a *lot* of training data to have any chance whatsoever of being useful, so you might do better to look for some other solution.

# Answer
> 0 votes
Let's consider the simplest case: There are only two slices and these are closed figures. (More slices would potentially just be an iterative application of the following.) Consider the larger slice. For simplicity divide the perimeter of this slice into 4 line segments with 4 points dividing them. For each of these 4 points find the nearest point in the perimeter of the smaller slice. With these you have a kind of boxy interpolation (bordered by 4 new trapezoids) of the volume of the interpolated shape between the two slices. It's pretty rough though. Well, now divide the line segments in two, and now you have a finer approximation. For the interpolated volume, you can look at the relative error between two successive approximations. When the error gets smaller than some threshold you choose, you can perhaps say that the interpolated volume is good enough. This is a numerical approach, and a rough one at that (being strictly linear), but it gives you an idea. You could use fancier line fittings if you use multiple consecutive slices and fit a polynomial curve line between the corresponding points.

---
Tags: machine-learning, computational-geometry, graphics
---


# Question
Title: How to delete a node from BST tree with 2 chidren?
I googled, read several tutorials and watched several BST node deletion algorithm explanations before posting this question. For some reason, I cannot find a complete explanation of BST node deletion algorithms.

I've found 4 algorithms to remove the node with 2 children from Binary Search Tree:
1) Find the smallest node from right sub tree and replace it with the node which we want to delete.
2) Find the biggest node from left sub tree and replace it with the node which we want to delete.
3) Find the deepest leftmost node from the right sub tree and replace it with the node which we want to delete.
4) Find the deepest rightmost node from the left sub tree and replace it with the node which we want to delete.

Apparently, none of those algorithms works for the next use case (most likely because I am missing or don't understand something). The use case is to remove element 5 from the next tree:

For the first algorithm we would chose element 6 and would lose its right sub tree. For the second algorithm we would chose element 4 and would lose its left sub tree. For the 3rd algorithm we would chose element 7 and which would violate BST rules. For the 4th algorithm we would chose element 3 which would also violate BST rules.

What is the right algorithm for such a use case?

# Answer
> 2 votes
You are right, in BST usually the case where a node has two children is reduced to the case where a node has one child.

Consider a node with two children. Swap this node with its predecessor in the BST (that is the rightmost node in the left subtree), or --totally symmetric-- swap with the successor (the leftmost node in the right subtree).

The node to be removed now has at most one child (in case we went for the predecessor it cannot have a right child). If it has no children we delete the node, and we are done.

In case the node has a single child, we remove the node and replace it by its subtree. We again obtain a BST.

In your example we want to remove 5 and swap it with its predecessor 4. Now 4 is in the root, and 5 has left child 3. Finally we remove 5 and put its child 3 on its place. Now 3 is the right child of 2.

PS. This method is sometimes called "deletion by copying", because values are copied from one node to another. Some do not approve of this process for two reasons. First copying might be an expensive operation, and second references are lost (if another datastructure points to a node with a certain value). Instead one only changes the pointers.

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


title: Is Kolmogorov Complexity Universal?

text:
# Question
Title: Is Kolmogorov Complexity Universal?
> Is the Kolmogorov complexity of any piece of information with respect to a certain predefined encoding for all pieces of information, or can the encoding vary for each piece of information?

There are different encoding mechanisms for representing data, and different ways of compressing the encoded data. If Kolmogorov complexity was encoding agnostic, then wouldn't the shortest computer program to describe each information be "0" or "1" and a call to the encoding system where each encoding system maps "0" or "1" to pieces of information of arbitrary length (the number of encoding systems would be $\frac{n}{2}$, where $n$ is the umber of pieces of information being considered). We could also increase the length of the description string, and reduce the number of encoding systems, but I think my point stands. This seems like a trivial notion of Kolmogorov complexity--is there anything I'm missing?

# Answer
> 4 votes
The formal version of your statement is known as the invariance theorem, which states (informally) that any two definitions of Kolmogorov complexity differ by at most a constant. This issue is covered on any textbook or lecture notes on Kolmogorov complexity.

# Answer
> 0 votes
What I think you might be getting at is something like the following: One might get the bright idea of building a lot of complexity into a given universal Turing machine. Let's say that we make it so that the quicksort algorithm only requires a few bits. Hey, maybe there are other algorithms we can similarly build in as well! One problem is that the more we do this, the fewer short codes there are to map to them. All the other operations start to pay the price. It's like trying to get everyone rich by rigging the lottery for each person in town. Each time someone gains big, many more lose a little. It's possible that some restrictions could be placed on universality, so that no nontrivial algorithms have a lot of mutual information with a purported universal machine, but I don't think that is necessary for the Invariance Theorem.

There just have to be diminishing returns on "cheating"--that is, when universal machines have lots of unnecessary bells and whistles that go beyond being 'Turing complete.' You'll be able to reduce the apparent K-complexity of the code, but unless you handpick your universal machine to do so, you won't know whether a program could be encoded with a deceptively small code because the only way for that to happen is to smuggle some sophisticated algorithms into the given universal machine just for that purpose. Your universal machine is specialized now for making certain kinds of programs really small by allowing many more programs to be much bigger than they need to be for most universal machines.

Looking at it another way, I could write a special version of UnZip that would produce the entire contents of Windows 10 when it "unzips" a special 8-byte long code. But it is not really unpacking information from the input, it would already have almost the entire contents of Windows 10 built-in already. This zipping utility would be substantially larger than comparable unzip utilities, and it would not demonstrate that the K-complexity of Windows 10 is 8 bytes.

---
Tags: kolmogorov-complexity
---


# Question
Title: Kolmogorov Complexity of String Concatenation
For all bit strings $x$, $y$ and Kolmogorov complexity $K$, is $K(xy) \> K(x)$?

# Answer
> 7 votes
Let $w = 0^{2^n}$, so that $K(w) = O(\log n)$. The string $w$ has $2^n+1$ prefixes, and so some prefix $x$ satisfies $K(x) \geq n$. This example strongly violates your inequality.

On the other hand, given $xy$ and $|x|$, we can easily extract $x$. This shows that $K(x) \leq K(xy) + O(K(|x|))$. In particular, if $|x| = n$ then $K(xy) \geq K(x) - O(\log n)$.

# Answer
> 0 votes
While this example might have to be tweaked a little, consider a bitstring of 8192 zeroes followed by 273 ones. Let's call this string *x*. Now let's have *y* equal to 7919 ones.

Now concatenate: The string *xy* is 2^13 zeroes followed by 2^13 ones. It has a shorter description than *x* or *y*, and one can probably write a shorter algorithm to generate it that to generate either *x* or *y* alone.

Following an approach like this, for any given constant *c*, I think one could make an example where K(xy) \< K(x) - c and K(xy) \< K (y) - c.

---
Tags: kolmogorov-complexity
---


title: A special case of subset sum

text:
# Question
Title: A special case of subset sum
I came across the following problem in my complexity-theory course:

Given a set of numbers $A := \\{a\_1, \dots, a\_n\\} \subset\_{\mathrm{finite}} \mathbb{N}$ and a number $b$ also in $\mathbb{N}$ such that the following condition applies: $a\_i$ divides $a\_{i+1}$ for all $i \< n$ and $a\_i \< a\_{i+1}$. Prove that this special case of subset-sum is decidable in P.

Due to the given condition, $b$ has to be a multiple of the first $a \neq 1$. Taking $a\_1 \neq 1: b = a\_1 \cdot x$. Finding this x takes me back to the subset-sum problem though which is surely not in P.

Any help would be appreciated.

# Answer
In short, the greedy algorithm works, where in each step you find the largest number in $A$ and subtract it from $b$. If $b$ becomes zero, you get a solution. If you reach a point where all numbers in $A$ are greater than $b$ output no.

---

In the following I list a formal description of the algorithm and a proof of correctness.

Here is a formal description of the algorithm. Let $A\_0 = A, b\_0 = b$ and $b\_i$ be the value of $b$ after the $i$-th iteration. Let $A\_i$ be the numbers left in $A$ after the $i$-th iteration. Then the algorithm goes as follows. In each step $i = 1,\dots$ find the largest number $a\_j$ in $A\_{i-1}$ not greater than $b\_{i-1}$. If no such number exists output no. Otherwise, set $b\_{i} = b\_{i-1} - a\_j$ and $A\_i = A\_{i-1} \setminus \\{a\_j\\}$. If $b$ becomes equal to zero then output yes, else iterate.

**Claim 1.** The previous algorithm output the correct answer of the given instance of the restricted case of the subset sums described in the question.

Before we prove the claim we prove an auxiliary claim.

**Claim 2.** Let $a\_1, \dots a\_n$ be the numbers in $A$ in ascending order. Then $\sum\limits\_{i=1}^{k-1}a\_i \< a\_k$ for all $k \in \[n\]$.

**Proof.**(Claim 2). Proof with induction over $k$. For n = 1, the sum is empty. Now we prove it for $k$. $$\sum\limits\_{i=1}^{k-2}a\_i + a\_{k-1} \< 2a\_{i-1} \leq a\_i,$$ where the first inequality holds due to the induction hypothesis and the second one holds by assumption since $a\_{k-1}$ divides and is smaller than $a{k}$.

**Proof.**(Claim 1) If the algorithm outputs yes, then it is clearly a yes-instance, since it only chooses numbers from the given sets and subtract there values from $b$.

Now we prove that, if our algorithm outputs no, the given instance is a no-instance. To this end we prove that if at step $i$ we choose an element $a\_j$, then any solution of the given instance must contain this element. We prove this by induction over $i$. Note that any $a\_j', j'\>j$ is strictly greater than $b\_i$ and hence can never be included, assuming by induction hypothesis, all previous selections of $a$ were a part of a solution if there exists one. Now using Claim 1, $\sum\limits\_{i=1}^{j-1}a\_j$ \< $a\_j$ and since we only remove elements, $A\_i$ contains no other elements smaller than $a\_j$ and hence, if we do not choose $a\_j$ choosing all smaller elements will not suffice to get a sum equal to $b$. Hence, we have to choose $a\_j$.
> 2 votes

# Answer
Consider the following further special case of your problem: $a\_i = c^{i-1}$ for some $c \ge 2$. For example, if $c = 10$, then we have $a\_1 = 1, a\_2 = 10, a\_2 = 100, a\_3 = 1000, \dots, a^n = c^{n-1}$.

In this case, there is a solution if and only if $0 \le b \< c^n$ and the base $c$ representation of $b$ contains no digits other than 0 and 1. In particular, there can be a solution even for some $b$ that are not multiples of $c$, contradicting your second-to-last paragraph.

See if this helps you think about the problem.
> 0 votes

---
Tags: algorithms, complexity-theory, undecidability, decision-problem
---


# Question
Title: Computing the Kolmogorov complexity of a string
What would be the implications for complexity theory if you could compute the Kolmogorov complexity of a string generated by a psuedorandom generator?

# Answer
If we're talking about a generator who can handle any length $n$ seed (perhaps this is more cryptographic PRG oriented), and stretch it to some length $n'\>n$ pseudorandom string, then the answer is no. The reason actually has nothing to do with the properties of PRGs, but simply relies on the fact that the output of the generator is computable, and that its range is infinite.

Kolmogorov's complexity isn't computable on any infinite recursively enumerable set of strings. To show this you can follow the standard proof of uncomputability of Kolmogorov's complexity. Since the set is infinite, it contains strings of arbitrarily high Kolmogorov's complexity, so you can write a program which enumerates them until it finds some string of high enough complexity, and then stop and output it. This was also answered in this math.se question.
> 2 votes

# Answer
If the string you are talking is the potentially infinite sequence of 1s and 0s that are generated, the K-complexity of that string is the K-complexity of the generator plus the K-complexity of the seed. I don't know exactly what the implications of *that* are, because different generators of the same K-complexity do not necessarily have the same crypticity or even the same appearance of randomness. There is a generator called the Mersenne Twister where the underlying order is much more difficult to exploit than most algorithms of comparable length. Generally speaking, a small enough K-complexity of the generator could mean that there is a severe limitation on the crypticity of the sequence, but I don't believe that it's easy to characterize that relationship. In theory, I think one could make the output of a PRNG so cryptic so that one would need either a very long portion of the sequence or details of the algorithm in order to distinguish it from a typical result of a true random process.

In principle, there is no algorithm that can reliably distinguish the difference between a pseudorandom sequence and a random sequence just as there is no algorithm that can reliably estimate the K-complexity for very cryptic strings. If you tried to compress a PDF where the pages were stocked with the first billion digits of pi, the actual K-complexity would be much smaller than the size of the zip file. If this is closer to what you are asking, then perhaps you are actually asking what would happen if there were an algorithm for accurately computing K-complexity for ANY string based on some universal machine M? In that case I would expect it might force some contradictory results for computer science and make complexity theory incomprehensible. I don't see how you can necessarily categorize PRNGs as categorically different from general programs that output strings.
> 0 votes

---
Tags: complexity-theory, kolmogorov-complexity
---


# Question
Title: Is Kolmogorov-random nonsensical for small numbers?
The Wikipedia definition of Kolmogorov-random defines a string (usually of bits) as being random if and only if it is shorter than any computer program that can produce that string.

Aren't nearly1 all strings shorter than a certain length2 going to be Kolmogorov-random?

1. If a random Turing machine is chosen, then programs that output short strings will almost always be longer than the strings. If the programming language used for measurement is optimized for outputting a short string, then only the complexity of a subset of short strings can be made lower than their length. For example, if a Turing complete language defines $0$ as an operation that outputs `0` and halts, the program for outputting `1` and halting is forced to be longer than the length of its output.
2. The exact length below which this occurs will depend on the programming language chosen. The length is 41 bits using 5 state, 2 symbol Turing machines.

# Answer
> 5 votes
> Is Kolmogorov-random nonsensical for small numbers?

Although one *could* pick a *specific* description language to make Kolmogorov complexity into
a function from  {0,1}*  to  {0,1,2,3,...} ,  most people don't pick as described  (  ,  ,  ,  ) ,
so basically:

Kolmogorov complexity is only defined up to an additive (1), so one
needs an infinite set of strings to make sense of Kolmogorov randomness.
In particular, **yes**, Kolmogorov-randomness is nonsensical for small numbers.

# Answer
> 0 votes
I think that K-complexity, at least as an indication of randomness, becomes much more meaningful above the "water line" of string size N where you start having K(x) \< N/10, although I'm not sure where that water line should sit. You might look into a concept called algorithmic specified complexity, which is a kind of randomness deficiency like computational depth. For an appropriate probability measure, a short but "random" K-complexity might still be a meaningful idea but not necessarily as randomness *per se*.

---
Tags: kolmogorov-complexity
---


# Question
Title: Formal definition of stable sorting algorithm
Suppose $a$ is an array and $cmp$ is a "compare function" that is a function which outputs $true / false$ values. I say that an algorithm $A$ which takes in input $a$ and $cmp$ is a stable sorting algorithm if $b=A(a,cmp)$ satisfies the following conditions:

*Sorting conditions:*

1) exist a permutation $p$ such that $a \circ p= b$ ($\circ$ is composition)

2) $\forall i\<j \to cmp(b\[j\],b\[i\])=false$

*Condition of stability:*

3) $\forall i\<j$ $cmp(b\[j\],b\[i\])=false \to p\[i\]\<p\[j\]$

In substance: cmp() is only a boolean function like in STL library C++ it takes two elements a,b and $cmp(a,b) \in \\{true, false\\}$ while $p$ is bijective function on {1,...,length(a)}

Further, I have two claims.

1) Exist and there could be many $b$ whose satisfy 1-2. So, any sorting anlgorithm (not necessarly stable) $A$ gives me a particular $b$.

2) Exist and is unique $b$ who satisfies 1-2-3.

Are my conditions and claims correct?

# Answer
There are two major issues I see:

* cmp() is not formally defined, so it could be anything, meaning that b isn't necessarily a sorted version of a.
* p is not formally defined either.

So I'd say that neither your conditions, nor your claims derived from those conditions are correct. But, if you'd fix your definitions, I think your claims would follow from it.
> 0 votes

---
Tags: sorting
---


# Question
Title: Does pre-emption of a process occur when that process is busy waiting?
I was reading about Peterson's Solution for Synchronisation. Let's assume the two shared variables to be `int bool flag[2]` and `turn`. Lets also consider the two processes as P0 and P1.

Initially, P0 executes causing - `flag[0] = true` and `turn = 1`. Now lets assume P0 is pre-empted by P1 causing - `flag[1] = true` and `turn = 0`

Now, busy waiting condition of P1

`while(flag[0] == true && turn == 0);`

puts P1 on an indefinite wait until P0 resumes its execution, completes it and turns `flag[0] = false`. But wouldn't this again require P1 to be pre-empted, and bring back P0 from 'Ready' to 'Running' and get it executed ? So does a process pre-empt if it's busy waiting?

# Answer
There are two broad concepts at play here: "synchronization" and "pre-emption". To make sure both processes run mutually exclusively, they first try to make sure the other one executes in the hope that in the future, the other process will ultimately unblock them by setting their respective flags.

To make sure both processes run to completion on this premise, the OS or any scheduler for that matter, should ensure that both processes are given their share on the CPU. Now coming to your question:

> So does a process pre-empt if it's busy waiting?

Yes, absolutely. If the scheduler (OS) upholds multi-tasking (say round-robin scheduling?) then the busy-waiting process will indeed pre-empt at some point in time. But keep in mind things get a little complicated when features like process priorities are added into play.

The other question:

> But wouldn't this again require P1 to be pre-empted, and bring back P0 from 'Ready' to 'Running' and get it executed ?

follows the answer to previous question that P1 would be pre-empted and eventually, P0 will run to completion thereby allowing P1 to also run to completion.

Final thoughts:

This is a basic synchronization primitive and a great example to help understand synchronization/mutual exclusion concepts. But, it doesn't take into account performance and busy-waiting is definitely not good performance-wise. There are other primitives that operate in post-wait fashion instead of busy-wait (Semaphores, for instance) which could be a better option.
> 1 votes

# Answer
*So does a process pre-empt if it's busy waiting?* \- yes. From the perspective of a pre-emptive scheduler it is yet another process consuming CPU cycles, and can be swapped out.

*But wouldn't this again require P1 to be pre-empted, and bring back P0 from 'Ready' to 'Running' and get it executed ?* \- No, this will not be required.

Let's consider the following for reference, (from Sec. 2.3 Modern Operating Systems 4th edition by Andrew S. Tanenbaum & Herbert Bos)

```
#define FALSE 0
#define TRUE 1
#define N 2 /*number of processes*/
int turn; /*whose turn is it?*/
int interested[N]; /*all values initially 0 (FALSE)*/
void enter_region(int process); /*process is 0 or 1*/
{
    int other; /*number of the other process*/
    other = 1-process; /*the opposite of process*/
    interested[process] = TRUE; /*show that you are interested*/
    turn = process; /*set flag*/
    while (turn == process && interested[other] == TRUE) /*null statement*/;
}
void leave_region(int process) /*process: who is leaving*/
{
    interested[process] = FALSE; /*indicate departure from critical region*/
}

```

Initially both `interested[0]` and `interested[1]` are `FALSE` (interested here is the `flag` in your code) - indicating that no one is interested in entering the critical region initially.

As you mentioned, let's suppose process `0` needs to enter the critical region and calls into `enter_region` first. It sets `interested[0]` to `TRUE`, and `turn` to `0`. Let's suppose process `0` is pre-empted now - before it could execute the `while` loop condition.

Process `1` needs the critical region and calls `enter_region` now, sets `interested[1]` to `TRUE` and `turn` to `1`. The `while` loop condition is

```
while (turn == 1 && interested[0] == TRUE)

```

Think of this is as, "if it's my turn but someone else is interested in getting in - be nice to them, let them in and wait here". (it is not `while (turn == 0 && interested[0] == TRUE)` like you've mentioned) process `1` enters the loop and cannot return.

Suppose the scheduler decides to pre-empt process `1` and process `0` gets a chance to run. It returns from `enter_region` immediately to enter the critical region. Remember that the loop condition for process `0` is `turn == 0 && interested[1] == TRUE` which is certainly not true at this time as `turn` is `1`.

After some time let's suppose process `0` exits the critical region and calls `leave_region` \- it sets `interested[0]` to `FALSE` indicating that it is not interested in the critical region anymore.

Later when process `1` gets to run again, it fails `turn == 1 && interested[0] == TRUE` (as `interested[0]` is `FALSE`), and enters the critical region - as you can see, process `1` did not have to wait for process `0` here.
> 0 votes

---
Tags: operating-systems, process-scheduling, synchronization
---