# Question
Title: What is meant by superlinear speedup? Is it possible to have superlinear speedup in practice?
In parallel computing, I know the speed up equation is

$$ \frac{1}{ s + \frac{1-s}{p} } $$

But what is meant by superlinear speed up? Is it something theoritical? Could you explain it with equations?

# Answer
> 13 votes
With equation: not really.

Superlinear speedup comes from exceeding naively calculated speedup even after taking into account the communication process (which is fading, but still this is the bottleneck).

For example, you have serial algorithm that takes $1t$ to execute. You have $1024$ cores, so naive speedup is $1024x$, or it takes $t/1024$, but it should be calculated like in your equation taking into account memory transfer, slight modifications to the algorithm, parallelisation time.

So speedup should be lower than 1024x, but sometimes it happens that speedup is bigger, then we call it $superlinear$.

Where it comes from?
From several places: cache usage (what fits into registers, main memory or mass storage, where very often more processing units gives overall more registers per subtask), memory hit patterns, simply better (or a slightly different) algorithm, flaws in the serial code.
For example, a random process that searches space for a result is now divided into $1024$ searchers covering more space at once so finding the solution faster is more probable. There are byproducts (if you swap elements like in bubble sort and switch into GPU it swaps all pairs at once, while serial only up to point).

On the distributed system communication is even more costly, so programs are changed to make memory usage local (which also changes memory access, divides problem differently than in sequential application).

And the most important, the sequential program is not ideally the same as the parallel version - different technology, environment, algorithm, etc. so it is hard to compare them.

**Excerpt from "Introduction to Parallel Computing" Second edition by Ananth Grama, 2003**

> Theoretically speedup can never exceed the number of processing elements $p$.
> If the best sequential algorithm takes $T\_s$ units of time to solve a given problem on a single processing element, then a speedup of $p$ can be obtained on $p$ processing elements if none of them spends more than time $T\_s/p$.
> A speedup greater than $p$ is possible only if each processing element spends less than time $T\_s/p$ solving the problem.
> In this case, a single processing element could emulate the $p$ processing elements and solve the problem in fewer than $T\_s$ units of time.
> This is a contradiction because **speedup, by definition is computed with respect to the best sequential algorithm**.

So the name "superlinear" in this context comes from the definition of speedup.

# Answer
> 0 votes
My layman explanation can help with the imagination of how it works.

Certain types of algorithms lead to superlinear speedup if HPC interconnect architecture makes it possible to have references between internal states of cores. The reason is information (and thermodynamic) theoretical and can be simply explained with the following description.

Take two systems containing 3 bits of possible states in each:

`011` and `101`

The maximum number of possible states of this system is 2 * 2^3 = 16.

Now let's combine these two ensembles into a composed one, simply having 6 bits of possible state space:

`011101`

The maximum number of possible states of this system is 2^6 = 64. Combined system has available entropy increase of 64 / 16 = 4 times.

Composition of ensembles having bigger variety of internal states leads to exponentially bigger "speedups", because cores can hypothetically have more mutual references.

In chemistry, energy is released when systems combine (think nuclear fusion). That energy comes exactly from the possibility to address more states for combined systems.

The sources I've read were all describing parallel algorithms on isolated cores, where there were no ability to have mutual references between state bits of different cores. From the point of view of entropy increase of combined states, I can imagine how superlinear speedup is possible.

For information-theoretical details, see "The mixing paradox" in the Wikipedia article https://en.wikipedia.org/wiki/Gibbs\_paradox on the exact thermodynamic nature of this behavior.

This has some philosophical implications for human-human communication and the importance of live speech conversations versus typing text and reading books.

---
Tags: parallel-computing, multi-tasking
---


title: Without Rare Metals

text:
# Question
Title: Without Rare Metals
One often sees assertions that these are "necessary" for modern military and consumer computing applications. I presume that without these rare metals, the devices could be manufactured, but would be larger and/or more expensive. Is this true?

# Answer
Sort of, it seems.

First, I am not an expert at this topic at all. I started to use google and first found this article Computers without rare earths are huge which suggests that computers CAN be build without the use of rare earths, but would be significantly bigger. This may have a huge impact as today every vehicle, airplane or device is packed with multiple tiny computers. Large computers mean we can't utilize computational power to support/improve navigation, life support, etc. on airplanes and surely cant carry our smartphone with us. Furthermore the article suggests, that rare earth also improve efficiency of computing devices.

Then I found these articles Alternatives to rare earths More alternatives which suggest that one can indeed achieve the same or a similar level of size reduction and efficiency with alternative materials. As the supply of rare earths is not guaranteed long term (mining is not environmental friendly, there are territorial disputes etc.) researchers are working on the two obvious possibilities:

1. Develop the current technology to work without rare earths (or materials not yet considered rare earths)
2. Engineer new elements that have a similar effect (i.e. in magnets)

To sum it up: it seems like its not possible at the moment, but might become feasible in a few years (or decades).

Disclaimer: please be aware that neither this answer nor the articles provided are scientific evidence. (I am also not sure if this is the right forum to ask this)
> 0 votes

# Answer
It's not that it's not possible, it's that it won't be cheap. I'm going to focus on a very specific rare earth metal - Tantalum. This is used to make Tantalum capacitors. Tantalum capacitors are special not because they work better **as capacitors** than the basic, cheap caps you can buy, but because they have very tightly controlled properties. One of the big ones is called In-Series Resistance (ISR) - a capacitor isn't just a capacitor, it has a resistance as well. This resistance needs to be tightly controlled, especially at high speeds/power, since a resistor in series with a capacitor can affect timing among other things. Tantalum caps are just easy to manufacture to more tightly controlled standards. They are much more expensive, however.

So what you'd need is to create a capacitor using non rare earths that also are produced in a tightly controlled way to emulate the ISR of a tantalum cap. That's probably not impossible, but the manufacturing methods would have to be refined and I'll wager that it would cost more due to the stricter tolerances needed on cheaper materials.

There are other examples of metals being used in the circuits of a computer because they have desirable electrical properties. It is highly likely that the average computer user might not even notice if you replaced, say, the gold plating of a CPU's pins with cheaper tin, but there would be performance hits all around.

Ultimately, a computer can be built from many things, so creating a rare earth free computer is probably not a huge technical challenge. Instead, it's far more likely that the absolute cutting edge of speed, size, power, and weight would have to be rolled back a few generations.
> 0 votes

---
Tags: memory-hardware
---


# Question
Title: What is the index of the leftest child of node in a k-nery heap?
Suppose the root node‘s index is 1, what is the index of the leftest child of a node e in a k-nery heap? What is the parent‘s index of a node in k-nery heap?

All questions regarding my problem I found talk about binary heaps, I just can’t think of a simple solution.

# Answer
Let's assume you store the nodes by level and then from left to right. Here are the first few levels:

1. Root: $1$
2. Children of root: $2,\ldots,k+1$
3. Grandchildren of root: Children of $2$: $k+2,\ldots,2k+1$; Children of $3$: $2k+2,\ldots,3k+1$, ...

Let us guess that just like in the binary case, the formula for the leftmost child of $v$ is of the form $\alpha v + \beta$.

If we consider two adjacent nodes at the same level, their leftmost children will differ by $k$ (for example, leftmost child of $2$ is $k+2$, whereas leftmost child of $3$ is $2k+2$), hence $\alpha = k$.

We can find $\beta$ by considering the root: $k \cdot 1 + \beta = 2$ implies that $\beta = -(k-2)$. Overall, we get $$ kv-(k-2) = k(v-1) + 2. $$ This works for the root by construction. When $v = 2$, we get $k (2-1) + 2 = k+2$, which also works out. My guess it that this formula works out, and you should be able to prove it by induction. That's where you come in...
> 0 votes

---
Tags: data-structures, heaps
---


title: Can Earley parser work in parallel?

text:
# Question
Title: Can Earley parser work in parallel?
Since Earley parser finds all possible application variants for a token, can it parse text in parallel, unlike the usual parser like stack-based, etc. You just need to modify the start of each parallel chunk of tokens, then while going backwards while constructing a table you combine and validate the found rules like in standart Earley approach. But since vector operations are done there, it is possible to parallel this too. And splitting on tokens also. So its (theoretically, i haven't see project like that) GPGPU support for Earley parsing.

# Answer
> 3 votes
Yes, Earley's algorithm can be parallelized, but not in the way that you are thinking.

# Earley's Algorithm In Particular

You ask about Earley's algorithm *specifically*. Parallelizing the algorithm in the way you suggest is unlikely to be faster. Researchers Peter Ahrens, John Feser, and Robin Hui report:

> We first tried to naively parallelize the Earley algorithm by processing the Earley items in each Earley set in parallel. We found that this approach does not produce any speedup, because the dependencies between Earley items force much of the work to be performed sequentially.

The reason Earley's algorithm in particular is difficult to parallelize is because of interdependencies within the computation. To answer how successfully Earley's algorithm parallelizes, we need to solve this demarcation problem: What should be call Earley's algorithm? Seth Fowler and Joshua Paul explain:

> There are several published algorithms (see, for example, Hill and Wayne\[6\]) for parallelizing a variant of the the Earley algorithm, the CYK algorithm. Unfortunately, in practice CYK has a much longer running time than Earley (even though it has the same worst-case complexity of $O(n^3)$), and so it is not typically used.

Most researcher's agree that there are few successful parallelizations of the algorithm, however. Fowler and Paul continue:

> For the Earley algorithm itself, there are very few parallelization methods published (though there are many optimizations—see, for example, Aycock and Horspool \[1\]). One such method by Chiang and Fu \[3\] uses a decomposition similar to the one we develop,but goes on develop the algorithm for use on a specialized VLSI. Similarly, Sandstrom\[7\] develops an algorithm based on a similar decomposition....

Nonetheless, there are parallel versions. Peter Ahrens, John Feser, and Robin Hui who we cited earlier present "the LATE algorithm, which uses additional data structures to maintain information about the state of the parse so that work items may be processed in any order. This property allows the LATE algorithm to be sped up using task parallelism." The researchers claim a "120x speedup over the Earley algorithm on a natural language task."

# Parallel parsing in general - usually impractical

Parallel parsing techniques have been studied for decades. Other parsing algorithms are more amenable to parallelization, such as the CYK algorithm mentioned above. But parallelizing parsing is only rarely a practical strategy. Most parsing tasks you are likely to encounter are much more efficiently performed serially, that is, in the old fashioned single-threaded way.

The reason parallel parsing algorithms are generally impractical is because parallelism has a lot of overhead that needs to be recouped by the gain in speed, while most parsing tasks can be performed incredibly quickly. (See parallel slowdown.) Quoting from *Parsing Techniques: A Practical Guide*, by Dick Grune and Ceriel J. H. Jacobs:

> From a practical point of view, parallel parsing is interesting only for problems big enough to require considerably more time than a fraction of a second on a single processor. There are three ways in which a parsing problem can be this big: the input is very long (millions of tokens); the grammar is very large (millions of rules); or there are millions of inputs to be parsed. The last problem can be solved trivially by distributing the inputs over multiple processors, where each processor processes a different input and runs an ordinary, sequential, parser. Examples of very long inputs requiring parsing are hard to find. All very long parsable sequences occurring in practice are likely to be regular: generating very long CF sequences would require a place to store the nesting information during sentence generation. ...
>
> The situation is different for parsing with very large grammars. These are found most often in linguistics. They are especially bothersome there since most linguistic applications require general CF parsing techniques, the speed of which depends on the grammar size.

### References

Seth Fowler and Joshua Paul. "Parallel Parsing: The Earley and Packrat Algorithms." (2009). Note that this is a student project report for an undergraduate course.

Peter Ahrens and John Feser and Robin Hui. "LATE Ain’T Earley: A Faster Parallel Earley Parser." (2018) The arXiv, 1807.05642.

Grune D., Jacobs C.J.H. (2008) Parallel Parsing. *Parsing Techniques.* Monographs in Computer Science. Springer, New York, NY.

---
Tags: parsers
---


# Question
Title: Why are four context sensitive grammar (CSG) rules needed to represent AB -> CD?
In Wikipedia of Kuroda normal form, it says

> A straightforward technique attributed to György Révész transforms a grammar in Kuroda's form to Chomsky's CSG: AB → CD is replaced by four context-sensitive rules AB → AZ, AZ → WZ, WZ → WD and WD → CD.

Why are four rules needed here? Aren't three rules: AB → AZ, AZ → CZ, CZ → CD enough?

# Answer
> 5 votes
With three steps we are not forced to complete all the steps before continuing interacting with other context around the two initial letters.

In fact, Révész himself answers this question, in his Introduction to Formal Languages at archive.org, with the following example.

> Note that three rules like AB → A'B, A'B → A'D, and A'D → CD are not enough to replace the rules AB → CD. For example, if we have the rules S → AB, B → DE, AB → CD in the original grammar, then this replacement makes the derivation
>
> S ⇒ AB ⇒ A'B ⇒ A'DE ⇒ CDE
>
> possible, though CDE is not derivable in the original grammar. Such parasitical derivations are often quite difficult to avoid when we are trying to transform a grammar into an equivalent one.

---
Tags: formal-grammars, context-sensitive
---


# Question
Title: How can I write a genetic programming algorithm, given that the Halting problem is unsolvable?
I am learning genetic programming and to practice I want to write a simple algorithm which evolves a program that solves a simple function (say, square root). I intend to represent programs as abstract syntax trees.

However, one of the functors is the while loop. Of course, in assesting a tree's fitness, I have to evaluate the program: but the halting problem is unsolvable. How can I tell if a given tree stops? Of course I can't, so what are some practicals ways to approach this problem?

Should I make my simple tree-language not turing complete? Or maybe give a timeout to each tree?

# Answer
It is very unlikely indeed that finiteness is truly what you are looking for. Would you *really* be happy with a program that takes $10^{10^{40}}$ steps to complete?

If I am right, "non-haltingness" is not the real quality you are looking for. It is "halting within a reasonable time".

The best way to express this is not as a pure timeout, but by defining a measure of utility which declines with an increasing number of steps. That will give your evolutionary mechanism a steady "push" in the right direction. As for whether it is $1/n$, $1/\sqrt n$, $2^{-n/c}$, that is something you can decide.

Of course in practice a program that takes more than a certain number of steps is going to carry on going for ever. But you can encapsulate this intuition into the algorithm by saying that if, after $n$ steps, the overall utility has declined to a point when it is too low to be worth considering *and* it is never going to increase if you carry on stepping. Thus the timeout is still there, but as an implementation detail and not as a primary principle-in-itself.
> 2 votes

---
Tags: halting-problem, genetic-algorithms
---


# Question
Title: How to give a context-sensitive grammar for a^nba^nba^nb?
I am struggling on this problem since days: $L = \\{a^nba^nba^nb \mid n \in \Bbb N\\}$. I have to give for this language a context-sensitive grammar.

# Answer
> 4 votes
One possible grammar is:

\begin{align} S&\rightarrow Tb &(1)\\ T&\rightarrow AXY &(2)\\ T&\rightarrow ATXY &(3)\\ YX&\rightarrow YZ &(4)\\ YZ&\rightarrow WZ &(5)\\ WZ&\rightarrow WY &(6)\\ WY &\rightarrow XY &(7)\\ AX &\rightarrow AbA\_X &(8)\\ A\_XX&\rightarrow A\_XA\_X &(9)\\ A\_XY&\rightarrow A\_XbA\_Y &(10)\\ A\_YY&\rightarrow A\_YA\_Y &(11)\\ A&\rightarrow a &(12)\\ A\_X&\rightarrow a &(13)\\ A\_Y&\rightarrow a &(14) \end{align}

We can generate $A^n(XY)^n$ using Rule (1) to (3). Rule (4) to (7) are used to change $YX$ to $XY$, thus we can generate $A^nX^nY^n$. At last, using Rule (8) to (14) we can generate $a^nba^nba^nb$.

Note we needn't worry that in a pattern $YX$, $Y$ yields to $A\_Y$ (or $bA\_Y$) before we exchange $X$ and $Y$, because otherwise there is no rule to eliminate $X$ in this pattern.

# Answer
> 3 votes
**Lemma 1**: The non-contracting rule $XY\rightarrow YX$ can be rewritten as context-sensitive rules.
**Proof**: We can replace $XY\rightarrow YX$ with the following four context-sensitive rules,
$\quad XY\rightarrow UY$,
$\quad UY\rightarrow UV$,
$\quad UV\rightarrow UX$,
$\quad UX\rightarrow YX$,
where $U, V$ are new non-terminals.

**Lemma 2**: The non-contracting rule $XY\rightarrow aX$ can be rewritten as context-sensitive rules.
**Proof**: Similarly to lemma 1, we can replace $XY\rightarrow aX$ with the following four rules,
$\quad XY\rightarrow UY$,
$\quad UY\rightarrow UV$,
$\quad UV\rightarrow aV$,
$\quad aV\rightarrow aX$,
where $U, V$ are new non-terminals.

Because of the lemmas, we will include rules like $XY\rightarrow YX$ or $XY\rightarrow aX$ in our context-sensitive grammar with the understanding that each of them represents four context-sensitive rules.

---

The outline of the idea to build the grammar is to let non-terminal $T\_1$ "travel" from the left-hand side of ${A\_1}^n{A\_2}^n{A\_3}^n$ all the way to the right-hand side, **t**ransforming each $A\_1$, $A\_2$, and $A\_3$ to $a$ along the way, as well as updating itself to $T\_2$ and then $T\_3$ to indicate different phases.

Here is the strategy.

1. $S$ becomes $T\_1A$ .
2. $A$ is blown up to ${A\_1}^n(A\_2A\_3)^n$ by rules $A\rightarrow A\_1AA\_2A\_3\mid A\_1A\_2A\_3$.
3. $A\_3A\_2$ is transformed to $A\_2A\_3$ repeatedly so that $(A\_2A\_3)^{n}$ becomes ${A\_2}^n{A\_3}^n$.
4. $T\_1A\_1$ is transformed to $aT\_1$ repeatedly so that $T\_1{A\_1}^n$ becomes $a^nT\_1$.
5. $T\_1A\_2$ becomes $bT\_2A\_2$.
6. $T\_2A\_2$ is transformed to $aT\_2$ repeatedly so that $T\_2{A\_2}^n$ becomes $a^nT\_2$.
7. $T\_2A\_3$ becomes $bT\_3A\_3$.
8. $T\_3A\_3$ is transformed to $aT\_3$ repeatedly so that $T\_3{A\_3}^n$ becomes $a^nT\_3$.
9. $T\_3$ is changed to b.

Here is the strategy in terms of formal derivation.

$$\begin{aligned} S &\Rightarrow T\_1A\\ &\Rightarrow^\* T\_1A\_1^n(A\_2A\_3)^n\\ &\Rightarrow^\*T\_1{A\_1}^n{A\_2}^n{A\_3}^n\\ &\Rightarrow^\*a^nT\_1{A\_2}^n{A\_3}^n\\ &\Rightarrow^\*a^nbT\_2{A\_2}^n{A\_3}^n\\ &\Rightarrow^\*a^nba^nT\_2{A\_3}^n\\ &\Rightarrow^\*a^nba^nbT\_3{A\_3}^n\\ &\Rightarrow^\*a^nba^nba^nT\_3\\ &\Rightarrow a^nba^nba^nb \end{aligned}$$

Here is the context-sensitive grammar, where each of rule (3), rule (4), rule (6), and rule (8) stands for four context sensitive rules as given by the lemmas above. In the case when $0\in\Bbb N$, we should add rule $S\rightarrow bbb$.

\begin{align} S&\rightarrow T\_1A &(1)\\ A&\rightarrow A\_1AA\_2A\_3 \mid A\_1A\_2A\_3 &(2)\\ A\_3A\_2&\rightarrow A\_2A\_3 &(3)\\ T\_1A\_1&\rightarrow aT\_1 &(4)\\ T\_1A\_2&\rightarrow bT\_2A\_2 &(5)\\ T\_2A\_2 &\rightarrow aT\_2 &(6)\\ T\_2A\_3 &\rightarrow aT\_3A\_3 &(7)\\ T\_3A\_3 &\rightarrow aT\_3 &(8)\\ T\_3&\rightarrow b &(9)\\ \end{align}

---

**Exercise 1.** Explain why the strings generated by the grammar above must be of the form $a^nba^na^nb$.

**Exercise 2.** Write a grammar for $\\{a^nb^{2n}a^{3n} \mid n \in \Bbb N\\}$.

**Exercise 3.** Write a grammar for $\\{a^{n+n^2} \mid n \in \Bbb N\\}$.

# Answer
> 1 votes
I like the feature sensitive grammar notaion, means for each term is a set of features assigned, what must be matched inside a rule. The rule will be just:

S\[a\_count = n\]-\> a{n}b a{n}b a{n}b ,

Compare it to notations above with 10 rules. While matching the feature rule, parser will mach amount of a's and assign the value to S.a\_count field. Dont forget, a parser is a turing complete program in praxis.

Further, arithmetical expression are possible :

S\[a\_count = n\]-\> a{n}b{2\*n}c{3\*n},

Exercise 3 is not possible with this notation, it is something like :

S\[a\_count = m\]-\> a{m} : m == n + n\*n , n in N

so equasion must be solved here

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


# Question
Title: Reduction to proof undecidability of the problem: machine M and N accept infinitely many words
I am struggling with the following problem: Decide whether this problem is decidable or not: For two given Turing Machines M and N, there exists infinitely many words accepted by both machine M and machine N. In other words, is language `{ encodedMachine(M)#encodedMachine(N) | intersection of language of M and language of N is infinite }` decidable?

Intuitively it feels like this is undecidable problem and halting reduction might be used to proof this, but I have no idea how to start this reduction.

# Answer
> 1 votes
Here is the reduction from the halting problem, whether a given TM halts on empty input, as given in Yuval's comment.

For a TM $M$, let $K$ be the same as $K$ but ignoring inputs. That is, for any input, $K$ will first erase the input so that it looks like an empty input is given. Then $K$ will simulate $M$ on empty input. When the simulation halts, $K$ accepts. Now consider whether $\langle K\rangle\\#\langle K\rangle$ is in the language specified in the question.

**Exercise.** Construction a reduction from the other halting problem, whether a given TM halts on a given input $x$.

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


title: Maximum Flow in a Network

text:
# Question
Title: Maximum Flow in a Network
Let $N = (V, E)$ be a network in which the capacity of each edge is either $12$ or $18$.

**Prove or disprove:** The value of a maximum flow for $N$ can’t be $56$.

I'm trying to figure out how to definitely prove this. I think that this is not possible because of no combination of $12X + 18Y$ (where $X$ and $Y$ are integers) will ever $= 56$. Is there a better way of saying this? Am I right to say that an integer solution to $12X + 18Y = 56$ is what the Fold-Fulkerson algorithm implies?

# Answer
By the max flow min cut theorem, the maximum value of a flow equals the minimum capacity of a cut. The capacity of a cut is of the form 12x+18y, which can’t equal 56 because 56 is not a multiple of 6.
> 1 votes

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


# Question
Title: How does a Turing machine with one tape read its input?
It's often implicitly assumed that we don't have to pay much attention to the difference between the program (which specifies the function being computed) and the input (the value on which that function is evaluated) when reasoning about Turing machines. In particular, people are often happy to assume that the program and inputs are encoded on the same two-sided tape. How this actually works out okay isn't obvious to me though.

Let's say I have a UTM, $\Phi\_f$, which has a partially filled two-sided tape specifying a program for calculating the function $f$. Since the program is a finite set of symbols, it begins on cell $b$ and ends on cell $e$ where $b \< e$. Now I want to encode the input on the same tape, so I begin at cell $b-1$ and work in the negative direction to encode my specific input, taking up as much space as I need.

My understanding is that as long as the encoding methodology I use to specify the inputs is computable and fixed in advanced, I can use any input encoding I want. The fact that it needs to be fixed in advanced is clear, since the actual program for calculating $f$ for two different encodings is very likely different. Intuitively, it makes sense that I can use any encoding I want because if we fix some standard "base" encoding then computing $f$ on an input encoded by the function $g$ is the same as computing $f(g^{-1})$ on an input encoded by the base encoding.

I have two questions:

1. Is the above correct? In particular, is it always possible to pick an encoding and a function, and then find a *single program* that computes $f$ on an arbitrary input using that encoding?
2. On the tape, what does the operation of the TM look like? The symbols used to encode the input have a meaning to the TM as a program (or can), and that seems like it could cause problems. For example, the (2, 18) UTM has symbols that always result in the head moving left and others resulting in the head always moving right. It seems like if you chose those symbols to encode the input you could run into problems where the UTM could never escape the input section of the tape.

**EDIT:** You can read about the (2, 18) UTM I mention for free here. The table presented on page 237 of the journal / page 23 of the PDF shows the table defining the machine. It's a bit hard to read, but it's two main columns each with three subcolumns. A row of $q\_1\\;1c\_2\\;Lq\_1$ is read "if you are in state $q\_1$ and read the symbol $1$ write the symbol $c\_2$, move Left, and transition to state $q\_1$. The row with a dash instead of a transition is the halting condition.

# Answer
The situation here is that we would like to a construct universal Turing machine UTM $U$ with a two-sided tape. Let $T$ be a given arbitrary Turing machine (of certain kind) that computes a partial function $f$. ($T$ is call a "program" in the question.)

The question is how we will run $U$ to simulate $T$. In particular, how will we encode the input to $T$ so that the encoded input will be put on the tape of $U$ and how $U$ will be able to read that input.

Following the receipt given in the question, as a first step, we will fill a part of the tape, called the program section, to encode the transition rules of $T$. It begins on cell $b$ and ends on cell $e$ where $b \< e$. Suppose we want to encode $J$, an input to $T$ on the same tape, so we begin at cell $b-1$ and work in the negative direction to encode that input, taking up as much space as we need. The head of $U$ will be put on cell $b-1$.

The first issue we encounter is how $U$ can tell the part of the tape that encodes the transition rules of $T$. We can design $U$ to solve this easily by the following one of the simple techniques.

* Put one or more special symbols around cell $b$ and cell $e$ inside the program section so that $U$ will know when $U$'s head is coming in or out of the program section.
* We can require the program section be encoded in a set of symbols that is disjoint with the set of the symbols that is used to encode the input to $T$.

I hope that above make it clear how $U$ can read the input $J$ to $T$.

> Is it always possible to pick an encoding and a function, and then find a single program that computes $f$ on an arbitrary input using that encoding?

I am not sure what you are asking exactly. Given an effective injective encoding (that can be decoded effectively), we can always use that encoding as the encoding of $J$ for some particular UTM, as long as that UTM has enough states and capable transitional rules to differentiate the input and program section.

> On the tape, what does the operation of the TM look like?

I assume you meant for the UTM $U$. Its behavior is rather simple conceptually at a high level for all universal machines in the article as shown by the following excerpt.

> (i) On the first stage, the UTM searches the code $P$, corresponding to the code $A\_r$, and then the UTM deletes the codes $A\_r$, and $A\_s$, (i.e. it deletes the mark between them). (ii) On the second stage, the UTM writes the code $P\_r$ in $Q\_R$ of the tape in the reversed order. (iii) On the third stage the UTM restores its own tape for a new cycle of modelling.

More generally, $U$'s head read what is the symbol that should be read by $T$. Make a marker on the tape to indicate that cell of the tap is the current cell the head of $T$ is on. Then $U$'s head goes back to the program section to find the rule the corresponds to that symbol for $T$ and $T$'s state (that can be recovered from $U$' state). The result of the transition rule of $T$ is encoded in the $U$' state. Then $U$'s head locates the cell that contains that current symbol for $T$. Then according to the transition rule of $T$ encoded in $U$'s state, modify the cell and goes to the next cell.

What happens can be somewhat more complex when $U$'s modifies the program section and restore it afterwards from time to time.

> The symbols used to encode the input have a meaning to the TM as a program (or can), and that seems like it could cause problems. For example, the (2, 18) UTM has symbols that always result in the head moving left and others resulting in the head always moving right. It seems like if you chose those symbols to encode the input you could run into problems where the UTM could never escape the input section of the tape.

Yes, problems could happen if the transition rules for $U$ is not specified correctly. However, I cannot find any problem like that with the U(2,18) of that article.
> 3 votes

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


# Question
Title: Understanding proof of upper bound on complexity of recursive computation of graph chromatic polynomial
This question is about section 2.3 of Wilf's \`\`Algorithms and Complexity''

https://www.math.upenn.edu/~wilf/AlgoComp.pdf

in which he analyses the complexity of a recursive computation of the chromatic polynomial of a graph, based on the relation \begin{equation} \label{eq: recurrence} P(K;G)=P(K;G-\\{e\\})-P(K;G/\\{e\\}) \qquad (1). \end{equation} Here $P(K;G)$ is the number of \`\`proper colourings'' of $G$ with (as I understand it) at most $K$ colours (that is, colourings of the vertices using at most $K$ colours, such that no adjacent pair of vertices shares the same colour). The graph $G-\\{e\\}$ is the result of deleting edge $e$ from graph $G$, and the graph $G/\\{e\\}$ is the result of contracting edge $e$ in graph $G$. It turns out that $P(K;G)$ is indeed a polynomial in $K$, of degree equal to the number of vertices of $G$.

By defining $F(V,E)$ as the maximum cost (over all such graphs) of applying to a graph $G$ with at most $V$ vertices and at most $E$ edges, this recursive algorithm to compute $P(K;G)$, Wilf deduces from (1) that \begin{equation} \label{eq: F recurrence} F(V,E) \leq F(V,E-1)+cE+F(V-1,E-1) \qquad (2), \end{equation} with $F(V,0)=0$. Here the term $cE$ accounts for the effort of contracting the edge $e$, which requires us to modify the descriptions of any edges adjacent to the vertex that gets deleted.

Wilf seeks an upper bound of the form $F(V,E)\leq f(E)c$, and notes that the unique $f$ satisfying $f(E)=2f(E-1)+E$ and $f(0)=0$ will provide such a bound. He computes the exact solution $f$ of this last recurrence relation, which solution he approximates by $f(E)\sim2^{E+1}$.

He then derives another upper bound on $F$, by defining $\gamma(G)=|V(G)|+|E(G)|$, the sum of the number of vertices and the number of edges of $G$, and observing that $\gamma(G-\\{e\\})=\gamma(G)-1$ and $\gamma(G/\\{e\\})\leq \gamma(G)-2$. Then, letting $h(\gamma)$ denote the maximum amount of work done by the algorithm on any graph $G$ for which $\gamma(G)\leq \gamma$, Wilf claims that \begin{equation} \label{eq: h recurrence} h(\gamma)\leq h(\gamma-1)+h(\gamma-2) \qquad (3) \end{equation} for $\gamma \geq 2$. With $h(0)=h(1)=1$, the solution of this last recurrent inequality is that $h(\gamma) \leq F\_{\gamma}$, the Fibonacci number.

Finally, combining the two bounds, he obtains that the time complexity of the algorithm is \begin{equation} O \left ( \min(2^{|E(G)|}, \phi^{|V(G)|+|E(G)|}) \right ), \end{equation} where $\phi$ is the golden ratio. Provided the ratio of $|E(G)|$ to $|V(G)|$ is large enough, the second bound is sharper than the first.

My question is, how in (3) was Wilf able to omit a term like $cE$ from (2) ?

# Answer
> 1 votes
You are correct that a term was omitted in the RHS of (2.3.10), but the final asymptotic bound $O(\phi^n)$ holds for the augmented RHS also. Perhaps it might be easier for you to see this if you just work out the solution for the nonhomogeneous recurrence relation from scratch rather than use Wilf's Theorem 1.4.1 on the epsilons, as shown below. Essentially, we are adding a linear term $an+b$ to the exponential $\phi^n$, which gives $\phi^n + an+b = O(\phi^n)$, where $\phi$ is the golden ratio.

More specifically, suppose that before the two recursive function calls to the chrompoly function, the edge set needs to be modified, and for the given value of $\gamma = |V|+|E|$, the cost for modifying the edge set is $\gamma$. (You can also take this cost to be $c \gamma$ for some other $c$, if you wish.)

Then, the recurrence $h(n) = h(n-1)+h(n-2)+n$ needs to be solved. From the theory of linear nonhomogeneous recurrence relations, the solution $h(n)$ is the sum of a generation solution and a particular solution, where (1) the general solution has the form $h\_1(n) = c\_1 \alpha^n + c\_2 \beta^n$, where $\alpha , \beta$ are roots of the characteristic equation (one of them containing the golden ratio), and (2) the particular solution has the form $h\_2(n) = an+b$ because the nonhomogeneous part is polynomial of degree $1$. (If the nonhomogeneous part was $7n^2 3^n$, then the particular solution would take the form $(an^2+bn+c)3^n$. If $3$ was a single root of the characteristic equation, then the particular solution would take the form $n(an^2+bn+c)3^n$. If $3$ appeared as a root with multiplicity $m$, then the extra factor would be $n^m$.)

Thus, $h(n) = O(c \phi^n +an+b) = O(\phi^n)$ because the linear terms grow more slowly than the exponential and can be ignored in asymptotic notation.

---
Tags: graphs, runtime-analysis, recursion
---


# Question
Title: 0/1 Knapsack problem with real-valued weights
Is there a known solution for the 0/1 knapsack problem that allows the weights of the objects to be real numbers? The only algorithm I can think of is a brute force search. I have tried searching for a solution but couldn't come across any. When weights are natural numbers, the most common solution uses dynamic programming by caching solutions $V\[i,w\]$ to the subproblems in an $N\times W$ table, where $N$ and $W$ are the number of objects and weight limit of the knapsack. When the weights are real numbers, the dynamic programming solution breaks down: how do you define the table now? Granted there will be $N$ rows, but what about the columns?

# Answer
Sort the items by density such that $p\_1/w\_1\geq p\_2/w\_2\geq\cdots\geq p\_n/w\_n$ for profits $p$ and weights $w$. Let $W(k)=\sum\_{1\leq i\leq k} w\_i$ be the total weight of the first $k$ items in this order. Then for capacity $c$ an optimal fractional solution is to choose items $1,\ldots,i^\*$ where $i^\*$ is the largest number s.t. $W(i^\*)\leq c$ , and additionally a fraction of $(c-W(i^\*))/w\_{i+1}$ of item $i^\*+1$.

**Update**: I misread your question. For solving the $0$/$1$ version with real-valued weights you can either round them, or apply branch-and-bound algorithms that were designed for real values, e.g. Martello and Toth's MT1R.
> 2 votes

# Answer
If the weights have a fixed finite precision, you could multiply them by a big number, to turn them into integers.

If the weights have arbitrary precision, it's NP-hard, also known as subset sum problem. There isn't an algorithm taking polynomial time unless P=NP.

Practically, the weights may have a finite, but very high precision, making dynamic programming infeasible. You may have better chance by optimizing a search algorithm, possibly using dynamic programming as a heuristic.

This assumes the values have the same type as the weights. If values are integers or have smaller precision, you could swap values and weights in the algorithm and find the minimum weights by each value.
> 1 votes

# Answer
Well, if it is ***0/1** Knapsack problem* (i.e. an item is included or not), than it seems trivial to solve it for real-valued weights, provided you have a solution to integer-valued weights variant.

GeeksforGeeks gives a solution for integer weights. You really only need to replace *int* to *double* wherever appropriate.
> -1 votes

---
Tags: knapsack-problems
---


title: CYK result de-transformation

text:
# Question
Title: CYK result de-transformation
Suppose we have a rules derived from a treebank. And in order to get a syntax tree of a given sentence we use the cyk algorithm. In order to use the cyk we should convert the rules into chomsky normal form, Such that all of my rules are A -\> B C or A -\> a (A,B,C are non-terminals and a is a terminal). From the cyk we get the most probable tree, constituted from the cnf rules. But what if we want to de-transform the tree to be constituted from the original rules? We can expand very easily the Binary rules into the original. But what about unit productions? for example; A-\>B-\>a transformed into A-\>a in cnf, how do we get the original unary rules path A-\>B-\>a? Any ideas will be helpful.

# Answer
I don't think you can recover a unit production, unless (and this is probably the common case) the unit production is unambiguous. If there is only one derivation from a non-terminal to a particular terminal -- and it should be easy to figure that out while you are doing the transformation to CNF -- then you can record that derivation and reinsert it when you find the collapsed derivation in the CYK parse.
> 0 votes

---
Tags: parsers, natural-language-processing
---


# Question
Title: Algorithm for automatic construction of natural deduction proofs
I was wondering if there exists any algorithm for automatic construction of nautral deduction proofs. I'm interested in propositional logic and first order logic.

If there is no algoritm, can you provide some proof of this fact?

PD0: I'm not interested in any page for solving these kind of problems. My question is more theorical.

PD1: This is not homework, just personal interest.

# Answer
> 3 votes
Usually we require the theorems of a proof system to be recursively enumerable, so you can at least write an algorithm that will eventually produce a proof of any theorem. This is usually a relatively easy algorithm to implement. Of course, if you give it something that is a non-theorem, you won't be able to tell with this approach.

For classical propositional logic, we could, of course, use truth tables to check whether something is a tautology first, and then do this search for a proof. This would give a computable (i.e. recursive) algorithm. It would be more direct and efficient to use a constructive proof of completeness for classical propositional logic though. There are certainly even more direct and efficient ways to search for a classical propositional logic proof.

For intuitionistic propositional logic, there is the proof system LJT described in Contraction-free sequent calculi for intuitionistic logic and implemented in tools like Djinn.

Theoremhood for a first-order theory in (classical or intuitionistic) first-order logic is generally not computable. Some particular first-order theories are decidable, but most aren't. They are at least semi-decidable via the argument in the first paragraph. There are, of course, tons of automated theorem provers that will *attempt* to find proofs, but they may fail. For theorems, they may fail due to resource limitations1. For non-theorems, they just don't have a way of showing that something is contingent. They could find a proof for the negation of your formula, but that technically doesn't rule out your formula being a theorem since your theory could be inconsistent. Model checking techniques could be used to attempt to find counter-models to show that some formula can't be a theorem (but may still be contingent). Most model checking tools are not aimed at full first-order logic though. They have essentially the same theoretical and practical limitations as automated theorem provers.

1 Just because something is computable doesn't mean it's computable within our universe.

---
Tags: logic, first-order-logic, propositional-logic, natural-deduction
---


# Question
Title: Online algorithm for finding of clique of size k
I am trying to write an online algorithm that can detect cliques of size k. I first start out with a set of vertices. For each iteration, I add an edge. The algorithm will detect the first time an edge would create a clique of size k. What is an efficient algorithm that can complete this task, and what is the time complexity?

# Answer
Since I don't have enough points for a comment:

This problem is not going to have a very efficient solution. Looking at the $k=3$ case should be good start. In this case one can solve this problem with $O(|E|)$ space by keeping an (online) adjacency set for each vertex and when an edge $(u,v)$ arrives comparing the adjacency sets of vertices $u$ and $v$ for a collision (in time linear in the size of the smaller set) and then adding $(u,v)$ to the sets of vertex $u$ and $v$.

The run time of this algorithm would be $\sum\_v d(v)^2$, where $d(v)$ is the degree of vertex $v$ in the final graph. This is never bigger than $O(n^3)$, where $n$ is the number of vertices in the final graph.

It is unknown whether triangle detection (i.e., a clique of size 3) can be done in less than $n^3$ time even if you had the entire graph before you. See this, for instance.
> 1 votes

---
Tags: graphs, time-complexity, clique
---


# Question
Title: How MO'S algorithm with update query works?
MO'S algorithm is used to answer queries related to a given array by dividing it into blocks(https://blog.anudeep2011.com/mos-algorithm/) .Though i understood general MO'S algorithm but i am facing difficulty to understand MO'S algorithm with updates (https://www.youtube.com/watch?v=gUpfwVRXhNY)

Since articles related to MO'S algorithm with updates is rare can someone who knows this algorithm can explain it.

# Answer
> 3 votes
A short (or long?) recall: Mo's algorithm is used for problems, when you want to answer a lot of range queries over an array, in which it is not possible to generate an efficient data structure like a Segment tree, because combining multiple nodes can be very inefficient. The famous problem is to count the number of distinct elements in ranges $(l, r)$. Precomputing some ranges, like in a Segment tree, would not help, because combining two ranges is not efficient, and in general is an $\Omega(n)$ operation.

To answer such queries efficient, we need two ideas:

* Mo's algorithm uses the fact that we know all queries at the start, so we can answer them *offline* (in any order we like). We order the range queries by the tuple $\left(\left\lfloor\frac{l}{B}\right\rfloor, r\right)$ with $B = \sqrt{n}$ and compute the answers for them in this order. This means we split the array into $\sqrt{n}$ blocks of size $\sqrt{n}$. First answer all range queries that start in the first block (sorted by their range ends), then all range queries that start in the second block, an so further.
* The second idea is to use a data structure that represents a specific range $\[L, R\]$, can give us the answer to its range quickly, and it's possible to add/remove single numbers quickly to modify it's range. And we will maintain this data structure the entire time, starting with the empty range $\[0, 0)$.

E.g. in the example we just use a set together with the information how often each number appears in the current range. Adding a number will increases the count of the number (or adds the number with count 1 if it doesn't exit), and removing a number just decreases the count (or removes the number from the set). Assuming that the data structure currently maintains the range $\[L, R\]$, and the next query covers the range $\[l, r\]$. Then we just need to individually add the parts of the array, that were not covered by the old range but are covered in the new range, to the data structure: $\[l, r\] / \[L, R\]$, and remove the parts that were covered before and are now not covered $\[L, R\] / \[l, r\]$. It can be easily be proven, that we only add/remove $\sqrt{n}$ numbers on average per query (if we assume that we have $Q \approx n$ queries).

---

To handle updates we have to handle a new dimension: time. Because an identically query $(l, r)$ asked multiple times, can give different answers depending on the updates in the time between them. So we represent each query as a tuple $(l, r, t)$. The first query gets $t = 1$, the second $t = 2$, and so on.

Again as before, we just order the queries, this time by $\left(\left\lfloor\frac{l}{B}\right\rfloor, \left\lfloor\frac{r}{B}\right\rfloor, t\right)$ with $B = n^{\frac{2}{3}}$. So here we have blocks of size $B$ for $l$ and $r$, and answer them accordingly. First all with $\left\lfloor\frac{l}{B}\right\rfloor = 0$ and $\left\lfloor\frac{r}{B}\right\rfloor = 0$ (sorted by $t$), then all queries with $\left\lfloor\frac{l}{B}\right\rfloor = 0$ and $\left\lfloor\frac{r}{B}\right\rfloor = 1$ (sorted by $t$), and so on.

But now, if the data structure currently represents the range $\[L, R\]$ at timepoint $T$, and we want to answer the query $\[l, r\]$ at timepoint $t$, then we additionally to adding the parts $\[l, r\] / \[L, R\]$ and removing the parts $\[L, R\] / \[l, r\]$, perform the updates in the time range $(T, t\]$ if $T \< t$, or undo the updates in reverse if $T \> t$. It can be proven, that we add/remove/update $n^{\frac{2}{3}}$ numbers on average during each query.

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


title: Are Finite Automata Turing Complete?

text:
# Question
Title: Are Finite Automata Turing Complete?
Something is Turing Complete if it can be used to simulate any Turing Machine.

So, can a Finite Automaton simulate a Turing Machine?

On the question Can regular languages be Turing complete? they say a Regular Language can be Turing Complete, but it does not make sense to me. I am not talking about the Language being parsed, but the Finite Automaton itself.

Finite Automatons and Regular Languages are not Equivalents. Finite Automatons are machines which accept or reject some Language. But Regular Grammars and Finite Automata are equivalents because I can convert one to another. Then, the question is, are Regular Grammars Turing Complete? Are Type 0 grammars Turing Complete? i.e., can I use a Regular Grammar or a Type 0 Grammar to do any computation I would like?

Can I write a Finite Automaton to do anything a Full-Featured General Purpose Computer can do?

# Answer
No finite automaton can simulate a Universal Turing machine, so finite automatons are not Turing complete. This falls out immediately from them having a *finite* number of states. Universal Turing machines require an unbounded amount of space to work.

The *source code* of an Jot program can be recognized with a finite automaton. That automaton doesn't *evaluate* the program (and thus doesn't play the role of a Turing machine), it just determines whether or not it is well-formed enough *to be run*.

This is in contrast with most programming languages. For example, because JavaScript has nested `()` and `{}`, it's necessarily not regular (but is, at least approximately, context free). Indentation sensitive languages like Python aren't even context-free (without preprocessing of identation).

This isn't that interesting of an observation. For example, the following is a Turing-complete a subset of syntactically-valid JavaScript programs that is recognizable with a regular expression:

```
/^eval\("[^\n\"]+"\)$/

```

...just most of these will immediately throw a runtime error because `eval` will not parse its single argument -- essentially we can define a programming language to treat *all* inputs as "syntactically valid" by just defining a new runtime behavior for all the syntactically invalid ones.

What is maybe more interesting about Iota is that its grammar also naturally parallels the actual structure of programs, instead of being a weird encoding trick like the above.
> 19 votes

# Answer
> Can I write a Finite Automaton to do anything a Full-Featured General Purpose Computer can do?

Your computer *is* a finite automaton. It's state can be uniquely described by the content of its registers, RAM, SSDs, etc. Every input (including the system clock) causes a transition from one state to the next, in a deterministic manner. Conceivably, you could enumerate all the possible states, and draw the arcs between them, forming a deterministic finite automaton (DFA). There are maaaaany states, but they are finite.

However, this only works because the infinite memory requirement of Turing machines (TMs) is often ignored (exactly because it would never be achievable, so it's of little pragmatic use).

Pushdown automata (PDAs) and TMs can be thought to have two separate components.

1. A "decision making" part, that decides how one state should transition to a next, analogous to a CPU.
    * In a PDA, this is the automaton
    * In a TM, it's the rule set by which symbols are evaluated
2. They also have a "working memory", whose job is to contain most of the state of the system, analogous to RAM.
    * In a PDA, this is the push-down stack
    * In a TM, it's the tape

DFAs have both of these components rolled into one. The automaton is responsible both for all decision making, and for all state-keeping. As a consequence, the state can never be bigger than the DFA.

There is an asymmetry here: PDAs and TMs are granted use of infinite storage (bottomless push-down stacks, infinite tapes), whereas DFAs are not, by definition. If a DFA was given the same affordance for infinite state-keeping (by allowing it to have infinite states), it would no longer be a deterministic *finite* automaton. It would be a deterministic infinite automaton!

Interestingly, infinite state-automata are not only Turing Complete, but they're actually *more powerful* than Turing Machines. With infinitely many states allowed, *any* langauge can be expressed as an automaton with one start node, one accepting state, and one non-accepting state. For every string in the language, an arc is made to the accepting state. For every other string, an arc is made to the non-accepting state.
> 9 votes

# Answer
> can a Finite Automaton simulate a Turing Machine?

No. Some Turing machines don't halt on some inputs, but every finite automaton halts on every input.

Also, I'd say that your question contains a category error. Turing completeness is a property of systems analogous to programming languages. You're asking about whether a model of computation is Turing-powerful.
> 1 votes

# Answer
# No

Finite Automata are *not* Turing Complete because they have a *limited* amount of memory. If that limit of memory were to be removed, the Finite Automaton in question would be Turing Complete.

Let's take a Finite Automaton which is a Turing Machine except it is restricted to 10 states. This would *not* be able to be Turing Complete because it wouldn't be able to simulate every program with 11 states. Even if you extend it to 10,000,000 states, it will not be able to simulate an optimal program using 1,000,000 states (a program with the minimum states being used being 10,000,000 without being able to be golfed anymore) except with a 10,000,001st state being to move right. Therefore, a Finite Automaton must not be Turing Complete due to memory constraints.

Many programming languages like Malbolge or C are affected by this because they have a limited memory.
> 1 votes

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


# Question
Title: What does exactly theoretical computer science entail?
I am confused by the term "theoretical computer science". How can I distinguish which part of computer science are considered "theoretical" and which not?

To expand further, take Machine Learning. Is the study of Machine Learning Theoretical Computer Science? To me it is, because we are studying the computational qualities of learning, without declining our study into a particular technology or application, but usually, I hear machine learning spoken as a part of applied CS or engineering.

# Answer
CS isn't neatly divided into "applied" and "theoretical". Work that seeks to build systems and solve practical problems tends to get described as "applied"; work that seeks to increase our knowledge of computation tends to get described as "theoretical". Machine learning covers a spectrum that includes both.

If somebody said to me "I'm a theoretical computer scientist", I probably wouldn't assume they did machine learning – but only because people who do machine learning tend to say "I do machine learning."
> 1 votes

# Answer
I am not an expert - so feel free to correct me. For what I know (from my Bsc) theoretical computer science entails multiple fields of studies, which the more prominent ones are:

Complexity theory - the study of how much reources in terms of time/space an “algorithm” (or any program) needs. (Based on the Turing machines model)

Computation - can a certain problem be computed with plausible resources

Algorithms - how to compute a solution for a specific problem

Data structures- the algorithms building blocks, how to hold data efficiently with consideration to time and space.

Of course there are many other topics, which also rely on these above. But in most Bsc/BA Computer Science degrees - these are considered as the theoretical courses.

And a nice quote to sum up, as Edsger Dijkstra (a very influential computer scientist who invented one of the best shortest path algorithms and the Semaphore) “Computer Science is no more about computers than Astronomy is about Telescopes ”
> 0 votes

---
Tags: terminology
---


# Question
Title: Solving recurrence relation with square root
I am trying to solve the following recurrence relation :-

$T(n) = T(\sqrt{n}) + n$ using masters theorem.

We can substitute $n = 2 ^ m$

$T(2^m) = T(2 ^ {\frac{m}{2}}) + 2^m$

Now we can rewrite it as

$S(m) = S(\frac{m}{2}) + m$

The big $O$-notation for $S(m)$ will be $O(m)$.

Hence, $T(n) = T(2^m) = S(m) = O(m)$.

So we can say that $T(n) =O(\log n)$ as $n=2^m$.

But the answer is $O(\log\log n)$ . What is wrong with my approach ?

# Answer
> 8 votes
The answer cannot be $O(\log\log n)$. Already without applying any recursion we have the inequality $T(n) = T(\sqrt{n}) + n \ge n$. So the complexity cannot be smaller than $O(n)$.

---

But now to your computation. Setting $n=2^m$, we obtain as you did $$ T(2^m) = T(\sqrt{2 ^ m}) + 2^m=T(2 ^ {\frac{m}{2}}) + 2^m.\tag{1}\label{eq1}$$ You defined $$S(m) = T(2^m).$$ Then equation $\eqref{eq1}$ should become the following equation, which is different from $S(m)\\,$$= S(\frac{m}{2})\\,$$ + m$, the wrong equation in the question.

$$S(m) = S\left(\frac{m}{2}\right) + 2^m.$$

The equation above falls into the third case of the master theorem, therefore $S(m) \in \Theta(2^m)$. And from this follows $T(n) \in \Theta(n)$.

# Answer
> 2 votes
The transformation:

You define $S(m) = T(2^m)$ which is absolutely fine.

$T(m) = T(m^{1/2}) + m$, so $T(2^m) = T(2^{m/2}) + 2^m$.

Therefore $S(m) = T(2^m) = T(2^{m/2}) + 2^m = S(m/2) + 2^m$. That's the mistake you made, the last term is $2^m$ and not $m$.

Try $n = 2^{1024}$: $T(2^{1024}) = T(2^{512}) + 2^{1024} = T(2^{256}) + 2^{512} + 2^{1024}$ and so on. All the bits you add up are negligible compared to the $2^{1024}$.

# Answer
> -5 votes
Complexity of above recurrence is O(m) which is O(log m) and now n = 2 ^m so m = log n and hence complexity is O(log log n).

---
Tags: asymptotics, recurrence-relation, master-theorem
---


# Question
Title: Does there exist an undecidable problem such that the answer is YES for exactly one input to a UTM, and NO for all others?
Suppose I have a universal Turing Machine (UTM) which accepts some input in binary. Is there a computational problem such that the answer to the problem is YES (accepting) for exactly one input (and hence NO for all others), but determining which input is the accepting one is undecidable? Or is there a fundamental reason this cannot happen? Or is determining if this problem exists undecidable?

I assume this is equivalent to asking: is there a property of TMs such that this property is true for exactly one TM and not true for all others such that determining which TM this is true for is undecidable?

# Answer
> 0 votes
For every Turing machine over some language L, there is a set of words that it will halt and accept on and a set of words it will halt and reject on, if it does halt.

If $|L| = 1 $ then the Turing machine will accept on exactly one input.

Given an arbitrary M and some input, we cannot decide whether the program will halt; halting problem. However, since M is not arbitrary, it’s fixed,this is not the Halting problem. I believe an algorithm would only need to check if the input is equal to the first element in L.

# Answer
> 0 votes
We can enumerate all possible inputs, giving them numbers 1, 2, 3, 4, ...

We can then write a program that systematically checks if one of the first n inputs is accepted in n steps, for n = 1, 2, 3 etc. This will in finite time find the input that halts.

I wasn't qute sure if I would call the approach of user679128 to be "cheating" since the question was about a situation where the only element of $L$ was presumably hard or impossible to find. So we see it is easy (but likely very time consuming) to find, so the algorithm of user679128 can then easily be implemented in practice.

Where my approach doesn't work is a situation like "assume the answer is YES for a finite number of instances", unless you give me the exact number of instances. Even "assume the answer is YES for either one or two instances" doesn't allow me to find all instances where the answer is YES. IF there are two instances I will find them eventually, but if there is only one instance I wouldn't know when to stop searching.

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


# Question
Title: How making non LL, non LR grammar a valid LL grammar, also makes it a valid LR grammar? Is there any connection between LL and LR conflicts?
I might unncecessarily overthinking here, but I had this weird possibly meaning less doubt:

> When grammar is neither LL nor LR, it means, both LL and LR parsing tables involve conflicts. LL parsing table may involve FIRST-FIRST and/or FIRST-FOLLOW conflicts, whereas LR parsing table may involve SR and/or RR conflicts. When we use left factoring (or any other approaches) to eliminate conflicts from LL parsing table, it becomes valid LL grammar, and hence also a valid LR grammar. Does this means, eliminating LL conflicts also somehow eliminates LR conflicts? If yes how this happens? Or in other words, how LL conflicts are mapped to LR conflicts? (I believe there should have some minimum connection between LL conflicts and LR conflicts, shouldnt there be?)

# Answer
> 2 votes
> When we use left factoring (or any other approaches) to eliminate conflicts from LL parsing table, it becomes valid LL grammar, and hence also a valid LR grammar.

To say that the grammar "becomes a valid LR grammar" implies that it was not a valid LR grammar before. But I will argue that if a mechanical procedure is used to transform a non-LL grammar $G$ into the LL grammar $G'$, then it is likely that both $G$ and $G'$ are LR grammars. In other words, the elimination of the LL conflict did not have any effect on LR conflicts, because there weren't any.

I'm not going to attempt to prove this assertion for all possible mechanical procedures. Indeed, it might not be correct for all heuristics. But it's pretty clear that the assertion is correct for the procedure used to left factor a grammar, because failure to left factor does not introduce any LR conflicts.

Both types of LR conflicts require that at least one production be reduceable. If left-factoring involves a factor which is not an entire right-hand side, then it does not apply to any SLR state including a reduceable production, and thus substituting a new non-terminal for the non-common part of the right-hand sides has no effect on any hypothetical LR conflict. Of course, it is possible that the factor is the entire right-hand-side of one production $A\to\beta$, and there is another production $A\to\beta\gamma$. So left-factoring will use a newly-created non-terminal $A'$ to produce:

$$\begin{align}A&\to \beta A'\\ A'&\to\gamma\mid\epsilon\\ \end{align}$$

The new grammar no longer has a prediction conflict on $A$, but there is no guarantee that the result is LL. For it to be LL, the parser needs to determined which alternative for $A'$ to use, which requires that $FOLLOW(\gamma)$ and $FOLLOW(A')$ be disjoint. But if that is true, there is no LR conflict; the shift and reduce actions are clearly differentiated by the lookahead.

So, if left-factoring results in an LL grammar, the grammar was originally LR. Left-factoring has not "made the grammar LR".

Left-recursion elimination is a bit more complex. To start to come to terms with that, consider a very simple left-recursive grammar $G\_{sub}$:

$$\begin{align}S &\to E\\ E &\to T\\ E &\to E - E\\ T&\to 0|1|2|3|4|5|6|7|8|9 \end{align}$$

That grammar is ambiguous because $5 - 2 - 1$ has two parses: (for clarity, I put the subnode evaluation \[brackets\] beside each operator, to indicate that the two different parses lead to different program semantics):

```
     - [4]                        - [2]
   /   \                        /   \
  /     - [1]                  - [3] \
 /    /   \                  /   \    \
5    2     1                5     2    1

```

Since $G\_{sub}$ is ambiguous, it cannot be LR, and indeed when we try to construct the parsing automaton we find a shift-reduce conflict on lookahead $-$ in the state $\\{\[E\to E\bullet-E\], \[E\to E-E\bullet\]\\}$. The ambiguity also implies that the grammar cannot be LL, but in this case we can immediately see that it is not LL because no LL grammar has a left-recursive production.

We might chose to eliminate ambiguity by adding a precedence specification and using the precedence algorithm implemented in Yacc (and other parser generators). The precedence algorithm does not perform a transformation on the grammar. Rather, it transforms the parse automaton generated by the LR algorithm by removing all but one action from each conflict. (Hence, it is only applicable to LR parsing.) The resulting automaton could be transformed back into a deterministic CFG, but this is rarely done because the parse automaton is sufficient to implement a parser. (The procedure to convert a DPDA to a DCFG is outlined in Sipser, *Introduction to the Theory of Computation*, in Theorem 2.57; you can take that as an exercise.)

$G\_{sub}$ has only a single operator, $-$, so there are only two possible precedence declarations: either we declare the operator to be left-associative or we declare it to be right-associative. Normally, we would choose left-associativity, since that is how we were taught in school to understand expressions like $5 - 2 - 1$. That produces the parse tree on the right above, the one which evaluates to 2.

But right associative operators are also plausible. For example, in many programming languages, assignment is right associative, because $a = b = 7$ must be evaluated by first setting $b$ to 7 (subexpression on the right) and only then setting $a$ to the result of the first assignment.

As I said, actually constructing the parse automaton, removing the conflicts, and then turning it back into a grammar is a bit tedious, although it is probably a good exercise; for the purposes of this answer, I didn't do it. But I can provide CFGs which will produce the same parses, and probably differ from the full procedure only in minor details.

Here is the usual left-associative grammar: $$\begin{align}S &\to E\\ E &\to T\\ E &\to E - T\\ T&\to 0|1|2|3|4|5|6|7|8|9 \end{align}$$

And here is the right-associative grammar: $$\begin{align}S &\to E\\ E &\to T\\ E &\to T - E\\ T&\to 0|1|2|3|4|5|6|7|8|9 \end{align}$$

The only difference from the original ambiguous grammar is the second production for $E$. In the ambiguous grammar it is $E\to E - E$. The left associative grammar turns that into a left-recursive production $E\to E - T$, and the right associative grammar tuns it into a right-recursive production $E\to T - E$.

Both of the above associative grammars are LR, and neither is LL. The right-associative grammar can easily be transformed into an LL grammar by left factoring:

$$\begin{align}S&\to E\\ E&\to T E'\\ E'&\to - E\\ E'&\to\epsilon\\ T&\to 0|1|2|3|4|5|6|7|8|9 \end{align}$$

Again, this is an example of turning an non-LL grammar *which was LR* into an LL grammar (which is still LR).

To turn the left associative grammar into an LL grammar, we could try eliminating left recursion:

$$\begin{align}S&\to E\\ E&\to T E'\\ E'&\to - T E'\\ E'&\to\epsilon\\ T&\to 0|1|2|3|4|5|6|7|8|9 \end{align}$$

In this case, the resulting grammar is indeed LL. (And once again, both the original and the transformed grammar are LR.)

But here is something interesting. Left-factoring the right-associative grammar and eliminating left-recursion from the left-associative grammar produced virtually the same result. The only difference is that the first one has the production $E'\to - E$; in the second one, this production has had the $E$ pre-expanded, so it reads $E'\to - T E'$. Evidently, these two grammars parse the every input in the same way, despite the fact that we started with two grammars which produced different parses.

That's because the left-recursion-elimination algorithm *does not preserve the parse tree*. Or, to put it another way, you can turn a left-associative grammar into an LL grammar, but you sacrifice left-associativity.

Interesting though that is, it's really a side issue, since the point here was to try to find a relationship between LL and LR conflicts. And so far, we have found nothing even vaguely similar to a relationship. To close the circle, lets go back to the ambiguous grammar $G\_{sub}$, which was neither LL nor LR, and try to turn it into an LL grammar by eliminating left-recursion. We get

$$\begin{align}S&\to E\\ E &\to T E' \\ E'&\to - E E' \\ E'&\to\epsilon \\ \\ T&\to 0|1|2|3|4|5|6|7|8|9 \end{align}$$

That successfully removed the left-recursion, but the resulting grammar is still not LL. We did not remove the ambiguity, and the resulting grammar is neither LL nor LR.

In summary:

* An ambiguous grammar is neither LL nor LR. There will be conflicts produced by both algorithms, but it may be that they manifest in different ways.
* If you can transform a non-LL grammar to an LL grammar using standard heuristics, then it probably had not LR conflicts to begin with.
* LL and LR conflicts are completely different phenomena.

---
Tags: formal-languages, automata, formal-grammars, compilers, parsers
---


# Question
Title: Is function `number of TM which terminates on an empty word` computable?
> Let f: N → N be a function where `f(n) = number of Turing Machines over input alphabet {0, 1}, states: {0, 1, ..., n} and work alphabet {_ (blank), 0, 1, ... n} which terminates on a empty word`.
>
> Is `f` computable?

Let's call a TM which solves this problem `K`.

It feels like this problem is uncomputable. If we can't even determine if particular TM halts on an empty word (Halting problem reducing to the blank tape halting problem), then intuitively finding number of TMs with this property should be even harder. But I can't think of any reduction since this problem doesn't utilize any particular TM in input, its input is just a number (in the question I linked above - BLANKHALT, TM takes a machine as an input so we can provide a specific machine - anything we want - for example machine from instance of the HALT problem, but this is not a case in this problem).

At first I wanted to reduce BLANKHALT problem: I wanted to measure its number of states, alphabet, run the `K` TM with number of states BLANKHALT instance has and while counting the number of TMs which terminated on empty word, check if this is BLANKHALT machine I have just asked for. **BUT** I cannot do this, since I cannot assume K even enumerates the TMs, right? If `K` existed, it might have a magical way to solve the question, without checking all possible TMs one-by-one, right?

# Answer
> 2 votes
*Is that proof correct?*

Let's assume `f` is computable. Then I can show a TM which solves halting problem, actually even more - a TM which prints all halting TMs of given size.

This TM works as following:

1. Using blackbox for `f`, calculate `f(n)`
2. Iterate through ALL possible TMs of input alphabet {0, 1}, states {0, 1..., n}, work alphabet {\_, 0, 1, .... n}
3. Simulate each machine on empty input **BUT** we don't check TM machine one by one. We check TMs STEP BY STEP. That means for each TM we make its one step.
4. When TM terminates, add 1 to counter
5. When counter reaches f(n), then we know which machines terminates and which don't. We have solved halting problem. **Contradiction**

The key is we don't simulate TM machines one by one, but step by step, thus we don't get looped and we always terminate.

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


title: IP addresses and CIDR suffixes

text:
# Question
Title: IP addresses and CIDR suffixes
I'm somewhat confused about IP addresses and subnet masks. Can a same IPv4 address have two different CIDR suffixes ? for example 95.100.252.115/28 and 95.100.252.115/26 ?

If not, how is the CIDR suffix determined by the IPv4 address?

# Answer
> 1 votes
Yes there can be different suffixes, and the IP absolutely does not determine the suffix. You determine the suffix based on how many other computers you want networked together in that subnet group.

---
Tags: computer-networks
---


# Question
Title: Could we define the decimal notation of a natural number as a series of operations applied to 0?
People have made mistakes. For that reason, there probably is a demand by some people for a computer program that's easier to verify makes the calculations properly. I think that according to the conventional definition, for the 10's column, you add 10 times the digit, for the 100's column, you add 100 times the digit and so on. We could alternatively define the decimal notation as follows. Start from 0. Multiply by 10 then add the first digit then multiply by 10 and add the second digit then multiply by 10 and add the third digit and so on.

I think in Polish notation, operations such as + proceed the operands but you still write numbers in decimal notation normally so people use spaces to make notations unambiguous. That's because if they didn't use spaces, +222 could mean 2 + 22 or 22 + 2 so they instead write + 2 22 to mean 2 + 22 and + 22 2 to mean 22 + 2. I think that in addition to that, we could also describe natural numbers as a series of operations applied to 0 each of which is of the form of left multiplying by 10 then left adding a number between 0 and 9. For a reason I will described later, spaces might not even be needed. Also, you'll see later why I'm using the character ∅ instead of the character 0 to represent 0. We could let ∅ denote the number zero, S, the successor operation, + the addition operation and $\times$ the multiplication operation. So 2 + S(2 + 2) would be denoted +SS∅S+SS∅SS∅. Now how do we denote the method of getting the number 122 by starting from 0 then multiplying by 10 and adding 1 then multiplying by 10 and adding 2 then multiplying by 10 then adding 2? It's by writing +SS∅×SSSSSSSSSS∅+SS∅×SSSSSSSSSS∅+S∅×SSSSSSSSSS∅∅. To make it more compact, we could invent 10 single digit characters each of which is short hand for a string of characters as follows:

* 0 means +∅×SSSSSSSSSS∅
* 1 means +S∅×SSSSSSSSSS∅
* 2 means +SS∅×SSSSSSSSSS∅
* 3 means +SSS∅×SSSSSSSSSS∅
* 4 means +SSSS∅×SSSSSSSSSS∅
* 5 means +SSSSS∅×SSSSSSSSSS∅
* 6 means +SSSSSS∅×SSSSSSSSSS∅
* 7 means +SSSSSSS∅×SSSSSSSSSS∅
* 8 means +SSSSSSSS∅×SSSSSSSSSS∅
* 9 means +SSSSSSSSS∅×SSSSSSSSSS∅

Note that each of those strings of characters can be considered a unary operation so the 10 digits can be considered short hand for those operations. Then the expression 2 × 1008 can be denoted ×2∅8001∅. It's so much more straight forward than interpreting the standard Polish notation where you would probably write × 2 1008. I know that according to my notation, 8×2∅2∅ is also a valid notation for the number 48 even though there's no notation in standard Polish notation that's analogous to it. My question is

> Could this notation be a nice simple way to tell a computer to make calculations on numbers given in decimal notation? A human using a Python like program could type in ×2∅8001∅ to be given the answer 6102∅ and know how to interpret it as meaning 2 × 1008 = 2016. They can put simple problems to the test to verify whether it actually gave the answer they would expect it to give.

# Answer
Your question appears to be a very long version of "Could we add some sort of punctuation to Polish notation so that it's unambiguous where each numerical operand ends?" Yes, of course you could. Normally, we use a space and write the numbers most-significant digit first but, sure, if you want to use the symbol ∅ and write the digits in the opposite order, there's no law against that.

> Could this notation be a nice simple way to tell a computer to make calculations on numbers given in decimal notation? A human using a Python like program could type in ×2∅8001∅ to be given the answer 6102∅ and know how to interpret it as meaning 2 × 1008 = 2016.

Computers are very good at performing simple, repetitive tasks, such as transforming data from one representation to another. I find it hard to imagine a situation where it is better to make the user do that work instead of the computer. The format you propose seems to have no benefit to the computer itself, since computers work in binary, not decimal.
> 2 votes

---
Tags: proof-techniques, python
---


# Question
Title: Binary search uneven split number of queries?
For even split binary search (repeated halving) number of queries is log with base 2. According to Skiena's Algorithm Design Manual, if the split in binary search is by ratio 1/3:2/3 instead of 1/2:1/2, then number of queries is log with base 3/2. Why is this so? Would someone please help me get an intuitive understanding of why this works?

# Answer
The number of queries in the question is assumed to mean the exact upper bound of the number of queries in the worst case. So, **only the worst case** is considered except in exercise 3. That is, the wanted element will be in the "2/3" part after each query.

Suppose we have $3m$ ordered items currently. After a split by ratio 1/3:2/3, we will be left with $2m$ choices. So each query reduces the number of choices by a ratio of $3m:2m=3:2$.

After $k$ queries, the number of choices will be reduced by a ratio of $(3/2)^k$. In order to have only one choice left after $k$ queries, we should have $\frac{n}{(3/2)^k}\approx 1$, where $n$ is the number of original items. So the number of queries, $k$ is about $\log\_{3/2}n$. That is the simple intuition.

Of course, the above reasoning is not rigorous since we could have $3m+1$ ordered items. The number of items left after one query will be $2m$ or $2m+1$ (depending on how we round the fractional item), which is approximately $(2/3)(3m+1)$.

Or we could have $3m+2$ ordered items. The number of items left after one query will be $2m+1$ or $2m+2$, which is still approximately $(2/3)(3m+2)$.

It turns out that the number of queries will be between $-3+\log\_{3/2}n$ and $1+\log\_{3/2}n$ for all $n\>1$. So there is not much error to say the number of queries is log of $n$ with base 3/2.

**Exercise 1.** How many queries are needed if we binary search 26 items with splitting ratio $1/3:2/3$? ( Answer: 6 for floor, 7 for rounding or 8 for ceiling.)

**Exercise 2.** Write the approximate formula for the number of queries needed if we binary search $n$ items with splitting ratio $1:t$.

**Exercise 3.** Write the approximate formula for the number of queries needed in the best case if we binary search $n$ items with splitting ratio $1/3:2/3$.
> 3 votes

# Answer
On a side note, the complexity still remains in the order of Log. This is very well discussed in Brian Dean's paper on Randomized Reduction Lemma. https://dl.acm.org/citation.cfm?id=2677251
> 1 votes

---
Tags: algorithms, binary-search
---


# Question
Title: Confusion with first condition of Chomsky Normal Form
I had a very quick question when it comes to CFG (more specifically the attributes of CNF). I've been browsing over some examples and I've come across a few that confuse me. One such example is this:

$$\begin{align}S&\to XA|BB\\ B&\to b|SB\\ X&\to b\\ A&\to a\\ \end{align}$$

It is stated that this is indeed in CNF, but my confusion lies in the fact that under most rules it is stated that if the starting state $S$ exists in some RHS (in this case $B\to b|SB$) we must create a rule that states $S'\to S$.

Since that doesn't exist in this example, why is this considered to be in CNF? I also understand the rules of CNF, I also see that this example technically satisfies all those rules, so I am wondering if that is the reason?

***Rules:*** $$\begin{align}A&\to a\\ A&\to BC\\ \end{align}$$

Thank you for the help in advance!

Here is the link to the question for reference ( it deals with CFG TO GNF) https://www.geeksforgeeks.org/converting-context-free-grammar-greibach-normal-form/

# Answer
> 3 votes
**Yes**, your context-free grammar is in Chomsky Normal Form.

A grammar is in CNF whenever its rules are of one of two types, either $A\to BC$ or $A\to a$, where $A,B,C$ are nonterminals, and $a$ is a terminal symbol.

This means that every context-free grammar is equivalent to a cf grammar in CNF, up to the empty word. This means that by conversion into CNF one might loose the empty word. Nobody cares. Wikipedia refers to Hopcroft and Ullman as the source for CNF, and here is what H&U write:

> **Theorem 4.5** (*Chomsky normal form, or CNF*) Any context-free language without $\epsilon$ is generated by a grammar in which all productions are of the form $A\to BC$ or $A\to a$. Here, $A$, $B$, and $C$, are variables and $a$ is a terminal.

Except that some people with a wretched feeling for precision did not like this idea. They came up with a complicated formulation, just to capture the empty string. Probably something like "If the language contains $\epsilon$ then we allow the production $S\to \epsilon$, where $S$ is the axiom, and $S$ does not occur on the right-hand side of productions."

Well, your example grammar does not generate $\epsilon$ anyhow, so I would not bother. Chomsky didn't, Hopcroft and Ullman didn't. However, this is not legal advise. So, if someone is checking your exams, then I would consult that person.

Fun fact, Chomsky called "his" normal form "regular grammars"(!) and added a more restrictive condition: no two rules $A\to \alpha$ and $A\to \beta$ could share a common symbol in their right-hand sides $\alpha$ and $\beta$ (unless of course $\alpha =\beta$). (Definition 8, page 149, in the 1959 Chomsky paper linked at wikipedia).

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


# Question
Title: For every undirected unweighted graph is every MST also a SPT
I have a feeling this might be wrong an I'm looking for a counter example, however, I couldn't find one yet.. can anyone guide me in the right direction?

# Answer
Counter example: `V={a,b,c,d}, E={(a,b), (a,c), (a,d), (b,c)}`. A MST of this graph, rooted at `a`, could be: `{(a,b), (a,d), (b,c)}`. But this is not a SPT because the path `a->c` is of length 2 instead of 1 (`a` and `c` are directly connected in the original graph).
> 2 votes

# Answer
Shortest-path tree is defined for a graph and a root vertex.

Edit: My previous example was for a weighted graph, but still you can find counter-examples by choosing the root vertex carefully.
> 0 votes

---
Tags: graphs
---


# Question
Title: How to jump directly from level 0 to level 5 in a Gaussian pyramid without having the levels 1, 2, 3, and 4?
I am current studying the Laplacian Pyramid as a compact image code by Peter J Burt and Edawrd Hudson.

I understood all the concepts but I am having trouble with the equivalent weighting function. I understand how it works but i can't find the relation between $h(n,m)$ and $w(n,m)$.

Here is the link for the paper. The equations are at the end of page 2.

# Answer
> 1 votes
$w$ is effectively defined by $$g\_l(i,j) = \sum\_{m=-2}^2 \sum\_{n=-2}^2 w(m,n) g\_{l-1}(2i+m, 2j+n)$$ and $h\_l$ by $$g\_l(i,j) = \sum\_{m=-M\_l}^{M\_l} \sum\_{n=-M\_l}^{M\_l} h\_l(m,n) g\_0(i2^l+m, j2^l + n)$$ Some straightforward substitution of the second into the first gives $$\sum\_{m\_l=-M\_l}^{M\_l} \sum\_{n\_l=-M\_l}^{M\_l} h\_l(m\_l,n\_l) g\_0(2^l i+m\_l, 2^l j + n\_l) = \\ \sum\_{m=-2}^2 \sum\_{n=-2}^2 w(m,n) \sum\_{m'=-M\_{l-1}}^{M\_{l-1}} \sum\_{n'=-M\_{l-1}}^{M\_{l-1}} h\_{l-1}(m',n') g\_0(2^l i+2^{l-1}m+m', 2^l j+2^{l-1}n + n')$$ We conclude firstly that $M\_l = 2^l + M\_{l-1}$, and since $M\_1 = 2$ (and $h\_1 = w$), we have $M\_l = 2^{l+1}-2$. Secondly, that

$$h\_l(m\_l, n\_l) = \sum\_{\substack{-2 \le m \le 2 \\ |m\_l - 2^{l-1}m| \le M\_{l-1}}} \sum\_{\substack{-2 \le n \le 2 \\ |n\_l - 2^{l-1}n| \le M\_{l-1}}} w(m,n) h\_{l-1}(m\_l - 2^{l-1}m, n\_l - 2^{l-1}n)$$ by identification of weights of the same pixel of $g\_0$.

---
Tags: image-processing
---


# Question
Title: Algorithm to compute sum of cost of all path between pair of unique vertices of a tree
Given tree is undirected graph. It has n vertices and n-1 edges. The algorithm should compute the sum of cost of all path between pair of unique vertices.

Thus, there are total nC2 or n(n-1)/2 such pairs. The time complexity of the mentioned algorithm is n(n-1)/2. Please suggest an algorithm with better space and time complexity if possible. Below is the pseudocode.

```
//Final Result
sumAllPair = 0;

//Total Number of vertices
N

//Adjacency List
adjacencyList: array of linked list

//Weighted Graph Matrix
weightedGraph: two dimensional integer array N*N

//Initialize Matrix
loop ii from 0 to N-1 {
    loop jj from 0 to N-1 {
        if(ii equals jj) {
            weightedGraph[ii][jj] = 0
        }else {
            weightedGraph[ii][jj] = INFINITY
        }
    }
}

currentVertex = 0
visitedSet: LinkedHashSet of Size N
lastVisitedVertex = -1
call allVertexPairSum(weightedGraph, adjacencyList, currentVertex, visitedSet, lastVisitedVertex)

print sumAllPair

/*
 * Say graph has vertices 1,2,3,4,5,6,7
 *
 * allVertexPairSum() will compute sum of cost of all path between pair of unique vertices like this:
 *              21 + (31+32) + (41+42+43) + (51+52+53+54) + (61+62+63+64+65)+(71+72+73+74+75+76)
 *              where ij represents cost of path from vertex i to vertex j
 *
 * Time Complexity:
 *      N(N-1)/2 or Combination(N,2)
 */
function allVertexPairSum(weightedGraph, adjacencyList, currentVertex, visitedSet, lastVisitedVertex) {

    for each  visitedVer in visitedSet{
        cost = weightedGraph[visitedVer][lastVisitedVertex] +  weightedGraph[lastVisitedVertex][currentVertex]
        sumAllPair = sumAllPair + cost
        weightedGraph[visitedVer][currentVertex] = cost
        weightedGraph[currentVertex][visitedVer] = cost
    }

    add currentVertex to visitedSet

    for each neighbourVert in adjacencyList[currentVertex] {
        if(neighbourVert not equals lastVisitedVertex) {
            //neighbourVert becomes currentVertex
            //currentVertex becomes lastVisitedVertex
            call allVertexPairSum(weightedGraph, adjacencyList, neighbourVert, visitedSet, currentVertex)
        }
    }
}

```

Here is an example:

# Answer
Let's build some recursive function. We start picking any vertex of the tree $T$ and call it $R$ as root. If $R$ was removed, you would get a forest of several sub-trees. Every subtree $T\_k$ has a vertex $k$ connected to $R$ in $T$.

Now there are 3 types of paths contributing to the sum of cost of paths $N(R)$:

* $I(R)$, the cost of all inner paths of the sub-trees (computed with recursion),
* $S(R)$, the cost of all paths starting on $R$: $(R, i)$ for any $i \ne R$,
* $C(R)$, the paths between the different sub-trees.

Once you recursively have computed the 3 components for each of these vertex $k$ in its own sub-tree $T\_k$. Let's call $E(k, R)$ the cost of the edge $(k, R)$ and $n\_k$, the number of vertices in $T\_k$.

You can compute $N(R)$:

* $I(R) = \sum\_k N(k)$
* $S(R) = \sum\_k S(k)+n\_k E(k, R)$,
* $C(R) = \sum\_{k1, k2, k1 \ne k2}(S(k1)+n\_{k1}E(k1, R))(S(k2)+n\_{k2}E(k2, R))$

Note that if $R$ is connected to only one other vertex, $C(R) = 0$. You also can track $n$ with $n\_R = \sum\_k n\_k + 1$.

This has a linear time and space complexity.
> 2 votes

---
Tags: graphs, time-complexity, trees, space-complexity, weighted-graphs
---


# Question
Title: Counting number of states from a regular expression
Given the regular expression: $r=ab+((a+\epsilon)c^\*)^\*$. Let A be a non-deterministic automaton that accepts the language of r. How many states are in A? Answer the question without building A explicitly, explain how you got the answer.

I'm having trouble figuring this question out. The answer that was given is: $5\*2+4\*2=18$

With the explanation that for the $\epsilon$ regular expression we build an automaton with 2 states.

for each $\sigma \in \Sigma$ for the regular expression $\sigma$ we build an automaton with 2 states

For concatenating we do not add states and for each union or star operation we add 2 states.

But even with this explanation I'm not quite sure did they reach this answer.

I can understand that we have $\epsilon$, so we have 2. Plus we have $\Sigma = \\{a,b,c\\}$ so we do $2\*3$.

Even with the stars, how do we reach $5\*2$?

Also I haven't seen this kind of calculation before, are there any additional rules when trying to calculate states from a regular expression?

# Answer
The rule for the $\sigma\in \Sigma$ must be applied each time a letter appears in the regular expression, not only once per letter : you must build a different automata each time the letter appears. If you see it as some kind of digital circuit, you do not want to use the circuit that recognizes $a$ in $ab$ for the circuit that recognizes $a$ in $a + \epsilon$.

So you have five letters that appear in $r$, that's $5\*2$ states. Then you have 2 concatenations, two unions and two stars. That's $2 * 0 + 2\*2+2\*2 = 4\*2$ states.
> 1 votes

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


# Question
Title: Mistake in a proof of termination phase of Simplex algorithm in CLRS?
There is a pseudo-code for Simplex algorithm in CLRS:

The proof consists from three-part loop invariant:

> Proof We use the following three-part loop invariant:
>
> At the start of each iteration of the while loop of lines 3–12,
>
> 1. the slack form is equivalent to the slack form returned by the call of INITIALIZE-SIMPLEX,
> 2. foreach $i \in B$, we have $b\_i$ \>= 0, and
> 3. the basic solution associated with the slack form is feasible.

The initialisation and maintenance phases are clear for me. But, the termination case seems(not sure) wrong to me:

***So, my question is:***

It is unclear for me that $\bar{x\_i} = \infty $ if $i = e$. But, if we look at the pseudo-code, it is obvious that such thing happens only if $x\_e \leq 0$. What am I missing ?

# Answer
Because of line 9, $\Delta\_l$ is going to be $\infty$ if and only if **all** the $\Delta\_i$ with $i \in B$ are $\infty$. This can happen only when **all** the $a\_{ie}$ with $i \in B$ are $ \le 0$. Hence, by construction the solution $\bar{x}$ satisfies $\bar{x}\_i \ge 0$ for **all** $i$. Therefore it is both feasible and it has unbounded objective value.

If you are confused by the $\infty$, as Marcus Ritt mentioned in a comment you can replace the $\infty$ in the definition of $\bar{x}$ with a very large value $M$ and consider what happens as $M$ tends to $\infty$.
> 3 votes

---
Tags: algorithms, linear-programming, correctness-proof
---


# Question
Title: Prove that $T(n) \leq 8n^2$ or find value of $n$ when statement is not true (recurrence relation)
We have a function $T: \mathbb{N}\to\mathbb{N}$ defined recurrently:

$$T(n)=\begin{cases} 0 &\text{ if } n=0,\\ 3T(\lfloor{n/2}\rfloor) + 2n^2 &\text{otherwise.} \end{cases}$$

Prove that for each $n\in\mathbb{N}\_0$: $T(n) \leq 8n^2$

How can I prove such statement? I was thinking of using the Master Theorem to get asymptotically tight bounds of the recurrence but I think that is not a right approach. Any help appreciated

# Answer
> 1 votes
> I was thinking of using the Master Theorem to get asymptotically tight bounds of the recurrence but I think that is not a right approach.

You are correct. While the master theorem can yield asymptotically tight bounds, the question asks you to prove an exact inequality, $T(n) \leq 8n^2$ for all for $n\in\mathbb{N}\_0$.

Since this is a proposition on natural numbers, we should use mathematical induction. Because $T(n)$ is related to $T(\lfloor n/2\rfloor)$, we will use strong induction.

**Base case.** $n=0$: $T(0)=0\le 8\cdot0^2$.

**Inductive step.** Assume for all $k \< n$, prove for $n \>0$:

$$T(n)=3T(\lfloor{n/2}\rfloor) + 2n^2\le3\cdot8(\lfloor{n/2}\rfloor)^2 + 2n^2\le24(n/2)^2+2n^2=8n^2$$

Note that since $\lfloor{n/2}\rfloor\lt n$, we can apply the induction hypothesis to obtain $T(\lfloor{n/2}\rfloor)) \leq 8(\lfloor{n/2}\rfloor)^2$.

**Exercise 1.** Show that $T(n) \lt 8n^2$ for all $n \>0$.

**Exercise 2.** What is the largest $n$ such that $T(n) \le 7n^2$?

**Exercise 3.** Show that $\dfrac{T(n)}{n^2}\to8$ when $n\to\infty$.

# Answer
> 1 votes
You cannot use master Theorem (at least not as a black-box) as it only provides an asymptotic bound on the growth of $T(n)$, while you're interested in bounding the multiplicative constant too.

You can prove an upper bound your to your recurrence by induction on $n$.

The case $n=0$ is trivial as $T(0) = 0 = 8n^2$.

For $n \ge 1$ you have (notice that $\lfloor n/2 \rfloor \< n$): $$ T(n) = 3T\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + 2n^2 \le 3 \cdot 8\left(\left\lfloor \frac{n}{2} \right\rfloor\right)^2 + 2n^2 \le \frac{24 n^2}{4} + 2n^2 = 8n^2. $$

Edit: this is essentially the same as Apass.Jack's answer :)

---
Tags: asymptotics, proof-techniques, recursion, master-theorem
---


# Question
Title: Calculating millisecond and avoiding float numbers
I have a variable which increases/decreases from `0` to `255` every `(X) millisecond`. so:

```
(X) x 255 = time in millisecond / 60000 = minute

```

`(X) millisecond` is a variable which increases only by it self, for example after each button press:

```
(X) + (X) x 255 = time in millisecond / 60000 = minute
(X) + (X) + (X) x 255 = time in millisecond / 60000 = minute
etc

```

What number should we use in (X) so every time it increases i get `+1` minute in output. I want an integer number not a float.

*The language is C++ if it helps in anyway...*

# Answer
> 0 votes
So you want to find a value for $X$ in milliseconds so that $X \times 255$ is equal to $60000$ milliseconds which is one minute. And you want $X$ to be an integer.

Well, $60000 = 235 \times 255 + 75$. So you can either use $X=235$ milliseconds, in which case $X \times 255$ is 75 milliseconds less than one minute. Or you can use $X=236$ milliseconds, in which case $X \times 255$ is $180$ milliseconds more than one minute. But you cannot find an integer value for $X$ which makes $X \times 255$ exactly $60000$.

---
Tags: algorithms
---


# Question
Title: Learning Specific Topics In Machine Learning
I am a beginner in machine learning and I already have a good linear algebra/calculus background.

I am interested in being able to eventually understand and implement convolutional neural networks, feature-based classifiers, and boosting algorithms. Where should I start, and what steps should I take to reach my goal?

Thanks in advance.

# Answer
First I'll say, because you didn't mention it, that you also need a strong probability and statistics background.

A good place to start with CNNs is (in my opinion) the highly praised Stanford course:
https://www.youtube.com/playlist?list=PL3FW7Lu3i5JvHM8ljYj-zLfQRF3EO8sYv

If you are looking for more practical stuff (and on more than just CNNs), there are many guides for different machine learning models in Kaggle, where you can also join challenges which you can learn a lot from.
https://www.kaggle.com/

If you are interested in theory, this book might help - but might also be difficult without a strong statistical background:
http://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/index.html
(the book is free to download from there)
> 2 votes

---
Tags: algorithms, machine-learning
---


title: Is halts-if-valid decideable?

text:
# Question
Title: Is halts-if-valid decideable?
I have a suspicion that Turing's famous proof that the halting problem is undecidable may not prove exactly what people assume that it proves.

It may only prove that it is possible to limit the interface of a program such that it can't give you the most useful information about its inputs.

This counterargument is motivated by the idea that the human brain may be Turing-equivalent, if we're allowed to ignore issues of unlimited storage and execution time. It's also motivated by the observation that if Turing himself was Turing-equivalent he had a lot more to say about the question of halting than he would have if *he* were constrained by a boolean return interface.

If we have a program g(), and Turing is attempting to decide whether g() halts or not, and if we don't limit Turing's output vocabulary to a single boolean, and g() calls Turing on itself in a sneaky attempt to generate a paradox, Turing's output might be: "I see what you're doing, g(). I pwn you." Or more likely he might output a peer-reviewed journal article and (nowadays) a TED talk.

To return to the land of artificially constrained vocabulary, a more difficult problem than the original halting problem might be to add just one more possible outcome:

Given a program g(), and a program halts\_if\_valid() that inspects g() and g()'s inputs and can return one of HALTS, DOESNT, or INVALID, can we prove that halts\_if\_valid() isn't decideable?

I think a proof that relies on something like the original proof doesn't offer much.

```
// If halts_if_valid() returns INVALID, it can possibly exist as a valid program.
g() {
  if(halts_if_valid(g) == HALTS) loop_forever();
}

```

My limited ability with formal proofs doesn't offer me an immediately useful approach to tackling the decidability of halts\_if\_valid.

So my questions are:

Has anybody done any research on the decidability of the halts-if-valid problem or something similar? And is there anything in the literature that addresses the idea that Turing's proof may be more about limited interface vocabulary than the essence of the decidability of the halting problem?

I assume I'm not the first one to ask these questions; they seem like obvious quiestions to ask. However, I haven't found anything exactly like them by googling, so I'm probably not googling the right terms.

And, to be clear, my assumption is that halts-if-valid *is* still undecidable. Certainly in the general case (where we have infinite storage and execution time), but also in many or all practically-interesting finite cases. For instance, the case of finite programs that can't modify their own code. Or even the slightly more constrained set of finite programs that can't modify their own code and aren't interpreters. (*That* would be a fun set to formally specify.)

It would be a highly useful program if it could exist, and therefore it probably can't. I'm just unhappy with a proof that hinges entirely on an overconstrained vocabulary.

# Answer
A stronger result than Turing's halting problem is Rice's theorem: the determination of *any* nontrivial property of programs is undecidable.

To be precise, that's a semantic property, i.e. any property of programs determined by their behavior and independent of exactly how the program is expressed: the property has to have the same value for any two programs that have the same behavior. For example, “this program halts” is a semantic property, but “this program begins with `p`” is not a semantic property so Rice's theorem wouldn't apply to it. “Non-trivial” excludes properties that are true for every single program, or false for every single program.

It doesn't matter what set of answers you use for any variant of the Halting problem, as long as the possible number of answers is finite (e.g. YES/NO/INVALID) you can consider that as three properties ($P \in \text{YES}$, $P \in \text{NO}$, $P \in \text{INVALID}$) and its undecidable to be able to determine which one of these is correct for all possible $P$.
> 2 votes

---
Tags: computability, undecidability, halting-problem
---