# Question
Title: Is there any development in continuous-value computers?
Is there anything that hints at the possibility of a (modern) continuous-value computer, since modern computers are based on discrete arithmetic?

I guess the old analog computers were of this continuous-value type, but is there any modern development?

Do you know something about the issues regarding computability on such machine?

# Answer
Since you asked about computability and computational complexity for computers working on continuous values, you might be interested in research on computational complexity for the reals. In particular, there is a great deal of research on computational complexity for computations that work with real numbers ($\mathbb{R}$).

Normally, we think of algorithms as operating on discrete values (which can be expressed using bits). However, one can also study algorithms that work with real numbers, where the algorithm can use standard operations on real numbers: addition, multiplication, comparison, etc. Imagine that each basic operation on real numbers takes $O(1)$ time. Now we can talk about the running time of algorithms that use these basic operations, and talk about the class of polynomial-time algorithms. We can also look at a computational task, and ask about its complexity: about the running time of the best algorithm for that task. For example, a task might be something like: given a polynomial $p(x)$ with real-valued coefficients, determine whether it has a real root or not.

One can then define an analog of P, namely, $P\_\mathbb{R}$ -- the class of problems that have a polynomial-time algorithm, where the algorithm is allowed to do basic operations on real numbers. One can also define an analog of NP, namely, $NP\_\mathbb{R}$. This lets one ask interesting questions, like whether $P\_\mathbb{R} = NP\_\mathbb{R}$. Anyway, there is a rich literature on this, pioneered by Blum, Cucker, Shub, Smale, and others. It is known as complexity and real computation, and sometimes known as the BSS model. If you search the research literature, you'll find lots of work in this area.

The BSS model does have significant limitations. It assumes that all computations on real numbers can be done in $O(1)$ time, to infinite precision, with no error. Real analog computers won't have that property. But it's still a useful and interesting theory, nonetheless.

To learn more, you can look at https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale\_machine and https://cstheory.stackexchange.com/q/2119/5038 and https://cstheory.stackexchange.com/a/2062/5038 and https://cstheory.stackexchange.com/q/31626/5038 and https://cstheory.stackexchange.com/q/27508/5038.
> 2 votes

# Answer
I am considering that by "continues-value" you mean real values.

In terms of computability, there is a field called computable analysis and you might find some useful in these notes: http://eccc.hpi-web.de/resources/pdf/ica.pdf

This field studies the computability of real functions. I suggest you to go through extensions of theorems in computability theorem (all mentioned in the attached link) in order to understand the idea.
> 1 votes

# Answer
It seems that the discovery of memristor have fueled such efforts recently. I have two examples, the paper Boolean Logic Gates From A Single Memristor and a news of a memristor-based computer implementing a basic artificial neural network.
> 1 votes

# Answer
what you refer to is known generally as "analog computation". electronic and mechanical analog computers exist and are widespread but are "specialized". binary computing handles the problem of imprecision/ noise in the computation which tends to be difficult otherwise. here are two possible/ particular angles for "modern research" into analog computing that come to mind, both have much related material & further refs.

an excellent modern reference/ survey on the capabilities/ potentials of analog computing is the following. it is focused on NP complete computation but can be regarded as quite general wrt physical machine models.

another broad area of theoretical and applied investigation is modern implementations of Babbages analytical/ calculating engine which can be generally regarded as a mix of analog and digital elements. a massive working version has finally been built for the first time in centuries by intrepid designer(s) and toured at various museums internationally. see eg
> 0 votes

---
Tags: computer-architecture
---


# Question
Title: Calibration and overlay of RGBD with a thermal camera
I have a thermal camera that I would like to overlay automatically to the output of a RGBD camera (e.g., Kinect).

I can retrieve the intrinsic parameters of the thermal camera by using a special board I built, that allows the thermal camera to give as output a series of points similar to the ones obtained with a visible sensor and a typical calibration chessboard.

Once the intrinsic parameters of the thermal camera are obtained, what would the next steps be to align all the cameras? It's important to take into account that the two cameras deeply differ from each other, because they operate in different wavelengths.

# Answer
> 2 votes
I suggest that you obtain both the intrinsic and extrinsic parameters for both cameras. The extrinsic parameters will include information like the offset/distance between the two cameras and the relationship between their two headings, which is needed to relate their images. (If only the relative position and orientation/heading of the two cameras is known, that will be enough.)

Once you have these parameters, you'll be able to map each pixel in the RGBD image to its corresponding pixel in the thermal image. This will let you align those two images. Then, depending upon the specific setup, you might need to do fine-grained image stabilization (e.g., if they are not on tripods).

It's not clear why the different wavelengths would have any impact on alignment of the two images.

See also https://en.wikipedia.org/wiki/Camera\_resectioning.

---
Tags: computer-vision
---


title: Bringing images into alignment

text:
# Question
Title: Bringing images into alignment
I observe a scene with two cameras, c1 and c2, that produce two images i1 and i2, respectively. What I now want is to bring i1 and i2 into alignment, that is I want to know where pixel (x,y) in i1 is in i2. This "alignment-matrix" should be valid in general, that is not only for i1 and i2, but also for further images of the cameras c1 and c2 as long as they haven't been moved. I believe this problem is called "correspondence problem".

I have now read quite a bit about camera calibration, image rectification, essential and fundamental matrix. But there are still open questions and I would not know how to achieve my task.

So, the **question** basically is:

The essential matrix E and the fundamental matrix F both only give constraints for the correspondence problem (point p in i1 must lie on line l in i2). How do I actually solve the problem?

Thanks a lot for your time and answers!

# Answer
For 2D cameras, you can't. There's a reason why the matrices only give constraints that let you say that point p in i1 must lie on line l in i2 -- that's because that's all you can say.

In particular, for a particular point p in image i1, with 2D cameras, you don't know the depth of the corresponding object. The depth affects where it appears in image i2, so without knowing the depth, you can't know which pixel in i2 corresponds to p. If the object is very close, then there might be a very large offset; if the object is very far away, there might be a very small offset.

This is in fact the basis of binocular vision. Some 3D sensing methods work by somehow finding the correspondence using various heuristics (e.g., image similarity metrics), and then using this to infer the depth of the object.

So, the intrinsic and extrinsic parameters are not enough to uniquely deduce the correspondence, if both cameras are 2D cameras. With a 3D camera, this problem can be solved.
> 2 votes

---
Tags: computational-geometry, image-processing, computer-vision
---


title: Good mathematical book on algorithms

text:
# Question
Title: Good mathematical book on algorithms
I’m a sucker for mathematical elegance and rigour, and now am looking for such literature on algorithms and algorithm analysis. Now, it doesn’t matter much to me *what* algorithms are covered, but very much *how* they are presented and treated.¹ I most value a very clear and precise language which *defines* all used notions in a stringent and abstract manner.

I found that the classic *Introduction to Algorithms*, by Cormen, Leiserson, Rivest and Stein is pretty neat, but doesn’t handle the mathematics well and is quite informal with its proofs and definitions. Sipser’s *Introduction to the Theory of Computation* seems better in that regard, but still offers no seamless transition from mathematics to algorithms.

Can anyone recommend something?

---

¹: The algorithms should at least invole the management of their needed data using classical non-trivial abstract data structures like graphs, arrays, sets, lists, trees and so on – preferably also operating on such data structures. I wouldn’t be too interested if the issue of usage and management of data structures was ignored altogether. I don’t care much about the problems solved with them, though.

# Answer
> 7 votes
Hendrik Lenstra wrote in 1992:

> Although it is, from a rigorous mathematical point of view, desirable that I define what I mean by an algorithm and its running time, I will not do so. My main excuse is that I do not know these definitions myself. Even worse, I never saw a treatment of the appropriate theory that is precise, elegant, and convenient to work with. It would be a laudable enterprise to fill this apparent gap in the literature.

I do not know whether any progress has been made since then, or whether this is even considered a "gap" by the consensus. But the point remains that at least some eminent mathematicians have been dissatisfied with the mathematical rigour of the derivation of algorithms. So, it may be there exists no book with the OP's desired level of formalism.

The cornucopia of *practical perspectives* we have due to Knuth, Gries, Stepanov, and others are intended to aid programmers more than mathematics and so inevitably fall short on rigor and long on subjectivity.

Nonetheless, Stepanov's work is widely acclaimed in Silicon Valley as one of the best attempts at a scientific synthesis.

In *Elements of Programming*, Alexander Stepanov and Paul McJones attempt to lay the abstract algebraic foundations of algorithms. The book begins with admittedly somewhat *informal* axiomatic definitions of entities, values and their attributes, but in 288 pages progresses deductively via a series of lemmas to the foundations of the Standard Template Library.

The TOC, preface and a sample chapter on *Transformations and Their Orbits* can be found here, and an introductory lecture here.

Stepanov's more recent and relaxed book, *From Mathematics to Generic Programming*, is structured more by a roadmap of the history of mathematics, building from Egyptian multiplication to monoids, semigroups, and Lagrange's theorem, eventually developing modern data structures with their iterators and algorithms used in the STL.

# Answer
> 7 votes
I think the book you describe has a name. It is in seven volumes, only three and half of which have been published. It is called The Art of Computer Programming, (TAOCP) and is written by Donald Knuth.

It may be though that he will sometimes describe applications. But you can always skip that, and I doubt it makes much of the content. You should not be too disappointed with the maths.

---
Tags: algorithms, algorithm-analysis, reference-request, books
---


# Question
Title: Train Neural network with infinite amount of data
Does a sufficiently complex neural network guarantee to find the optimal solution, given an infinite amount of data and the back propagation technique for training?

In other words, given an infinite amount of training data, can neural network get out of local minima and approaches optimal state?

The question is purely theoretical.

Update: It is obvious that a proper neural net with optimal set of weights (in some occasions num of neurons should go to infinity though) can approximate any well-defined function. However, in practice we do not have that optimal set of weights. Those weights are approximated by a training method of choice. The most commonly used method is back-propagation. Now the question was when the number of training samples grows, does the neural net converge to the Bayes rule? In other words, is it a universally consistent classifier? the answer seems to be no. When it gets stuck in local minima no matter how much you increase the training set, it will never get out of it (when using BP as a training method).

you may wanna look at this paper: , (Farago,93)"strong universal consistency of neural network classifiers"

Update2: Perhaps, my update was not clear since I keep getting wikipedia pages as answer: Hope this one finally clarifies:

As I said in my original question, stochastic gradient descent (or perhaps other more complex choices) with back-propagation is going to be used to train the network. This means the weights are not optimal (optimality in the sense that the network may not obtain the Bayes err rate). We also have infinite amount of data which translates to learning in the limit or online learning framework. But to keep it simple, instead of having infinite amount of data, we may assume we have finite but arbitrary large set of data.

The question is, whether the performance of a neural network in theory can now converge to Bayes rate? using any known regularization method such as dropout (which somehow is equivalent to bagging), varying the network structure during training (adding or removing layers, increasing the number of neurons etc), early-stopping and any meta algorithm to sample from this large data-set, or anything else you can think of, are allowed.

PS: Many learning methods are universally consistent meaning that as the number of training samples grows, they guarantee to converge to something good (usually Bayes rate or $\epsilon$ neighborhood of it). I am surprised if we don't have any interesting theorem in that respect for Neural Networks.

# Answer
You are asking about an "infinite" set of data. The trouble with this question is that backpropagation (BP) is only applicable to a finite set of data (or a finite *sample* of an infinite population), which is iterated over repeatedly many times in order to converge to a minimum on the error curve. BP is simply not defined for an infinite set of data (outside of batch sampling), because repeated iteration over an infinite set of data is a undefined.

The answer to your question for a *finite* sample of data depends on the weights used to initialize the BP and how you are defining "optimal."

* In the first regard, since the BP algorithm blindly follows the error curve gradient, it is vulnerable to get stuck in local minima, and by definition of the gradient there is no way out unless you reinitialize the weights.
* In the second regard, optimality may be defined many ways. For example, it may simply stipulate producing an output error less than some $\varepsilon$ for all training data presented. Or your definition may reward generality of a model by placing less constraint on the error and instead use a threshold on some economic formula based on the *likelihood* of a data point together with the output error that it produces. Or you might invent some other definition.

Allowing for an infinite number of initial guesses and taking the first definition of "optimal" provided above, then it seems clear to me that Siegelmann and Sontag's theorem of universal approximation guarantees a "yes" answer to the finite-data question. But as D.W. remarked, this isn't very useful in practice.

For a trivial but illuminating example, a neural net may "universally approximate" a completely random stream of data **for some finite set of training points**, and then proceed to fail any and all optimality definitions for data points outside that set. Real world data can contain a sufficient degree of randomness to render the possibility of satisfying an optimality constraint based on non-training data pretty much indeterminate.
> 3 votes

# Answer
There's a standard theorem saying that any function can be approximated arbitrarily well by a multi-layer perceptron-based neural network, if given enough training data and enough layers and enough neurons. However, this theorem isn't terribly useful or relevant to practice, as it doesn't make any promises about how many layers or neurons or training samples are needed. See https://en.wikipedia.org/wiki/Artificial\_neural\_network#Theoretical\_properties.
> 2 votes

---
Tags: machine-learning, neural-networks
---


title: Find variance within one pass

text:
# Question
Title: Find variance within one pass
Given a list of real numbers. Is it possible to find the variance with no more than 1 iteration with constant space complexity?

# Answer
> 4 votes
Yes, it's possible. If you know the count of the number of values, the sum of the values, and the sum of the squares of the values, you can derive the variance. In particular,

$$\text{Var}\[X\] = \mathbb{E}\[X^2\] - \mathbb{E}\[X\]^2.$$

You can calculate the first term from the sum of the squares of the values, and you can calculate the second term from the sum of the values.

However, beware the caveats mentioned here: https://en.wikipedia.org/wiki/Variance#Formulae\_for\_the\_variance

---
Tags: algorithms, arithmetic
---


# Question
Title: Is there any meaning behind the classification of "λ-terms" in classes such as "church number" and "church list"?
λ-calculus terms can be informally/intuitively categorized, such as:

> `(λ f x . (f (f (f x)))))` is a church natural (3)
>
> `(λ a b . a)` is a church boolean (true)
>
> `(λ c n . (c 1 (c 2 (c 3 n))))` is a church list (\[1,2,3\])
>
> `(λ s z . (s (λ s z . (s (λ s z . (s (λ s z . z)))))))` is a peano natural (3)

That is, while the untyped lambda calculus obviously doesn't have explicit types, one can certainly recognize patterns on terms and categorize them based on their behavior - as if those had a type. When you say: *"a church number is a function that applies another function `n` times to an argument"* you are informally characterizing a wide range of λ-terms. My question is: is there any way to formalize that intuition? Any system/theory that meaningfully categorizes (untyped) λ-terms?

# Answer
> 5 votes
Several observations can be made based on your remarks:

1. In System F, every data type can be given an *encoding* using polymorphic types, e.g. $\mathrm{Bool}$ can be defined as the type $$\forall A.A\rightarrow A\rightarrow A$$ On the other hand, certain terms (not all of course) can be given a **principal type** in system F, e.g. $$\lambda ab.a $$ can be given the type $\forall AB.A\rightarrow B \rightarrow A$. But you can now notice that this is a generalization of the type $\forall A.A \rightarrow A \rightarrow A$, and this happens to be the most general type it shares with $\lambda a b.b$, which is of course the polymorphic encoding of $\mathrm{Bool}$. In this way, one can always **attempt** to assign the most general type to a term, and then check to see if this happens to be (a generalization of) the polymorphic encoding of a datatype.
2. Intersection type systems are usually undecidable type systems assigning types to pure $\lambda$-terms that have the remarkable property of **classifying their behavior**: in particular the most simple such system is **complete for strong normalization**: a term has a type iff it is SN.

In intersection type systems, it is always possible to interpret the set of all types of a term (ordered by the sub-typing relation) as a representation of the *behavior* of that term. In particular, there is a close correspondence between the various domain theory models of the pure $\lambda$-calculus and various intersection typing systems. See for example *Intersection Types and Lambda Theories* for an overview.

# Answer
> 5 votes
You are looking for **extrinsic types** which were explained by John Reynolds in his paper on intrinsic and extrinsic semantics.

Briefly, there are two ways in which we can approach types for programs:

1. **Intrinsic:** a program without a typing is meaningless, i.e., we consider *programs together with their types*.
2. **Extrinsic:** a program without typing information is meaningful. We can assign one or many types to it to express that it has certain properties.

Statically typed functional languages such as ML and Haskell insist on intrinsic typing: they refuse to run a program unless they can determine that it has a type. Scheme is untyped, so it will run a program even if no type can be assigned to it, and any types that are assigned to Scheme programs are *extrinsic* (external) to Scheme.

Let us consider an example. In $\lambda$-calculus we may consider the identity function. There are many ways to write it, depending on a particular flavor of the calculus:

* *untyped*: $\lambda x . x$
* *monomorphic*: $(\lambda x : \mathsf{int} . x) : \mathsf{int} \to \mathsf{int}$
* *polymorphic (System F)*: $(\Lambda A . \lambda x : A . x) : \forall A . A \to A$
* *parametric polymorphism (ML)*: $(\lambda x . x) : \alpha \to \alpha$

Under the intrinsic view of types we would insist that $\lambda x . x$ by itself means nothing, and that typing information must be provided. Under the extrinsic view $\lambda x . x$ makes sense by itself, but can be assigned many different types – so long as we explain what it means "to assign a type". A simple way is to say that a type is the same thing as a subset $T \subseteq \Lambda\_0$ of the set $\Lambda\_0$ all closed terms in the untyped $\lambda$-calculus (a better definition would be that a type is a partial equivalence relation on the set of closed terms). Some types that come to mind are:

* the type of terms equal to a Church numeral $$C = \\{t \in \Lambda\_0 \mid \exists n : \mathbb{N} . f \equiv\_{\beta\eta} \overline{n} \\}$$ where $\overline{n}$ is the $n$-th Church numeral.
* given any $A \subseteq \Lambda\_0$ and $B \subseteq \Lambda\_0$, we can define the type of functions $$A \to B = \\{ t \mid \forall u \in A . t u \in B\\}$$.
* if $(A\_i)\_{i \in I}$ is a family of types, we can define their intersection type $\bigcap\_{i \in I} A\_i$.

Now it can be checked that $\lambda x . x$ has the following extrinsic types:

* $C$ because it equals $\overline{1}$,
* $C \to C$
* $A \to A$ for any $A \subseteq \Lambda\_0$
* $\bigcap\_{A \subseteq \Lambda\_0} (A \to A)$

An example that John Reynold liked to give was this: given a real number $c \in \mathbb{R}$, what type does $\lambda x . \cos(c \cdot x)$ have? Under intrinsic semantics the type would presumably be $\mathbb{R} \to \mathbb{R}$ no matter what $c$ is. But under extrinsic semantics it always has the type $\mathbb{R} \to \mathbb{R}$ *and also* the extrinsic type $\mathbb{Z} \to \mathbb{Z}$ when $c = \pi/2$.

# Answer
> 2 votes
Here is a similar list:

* *Bush* is the name of a president.
* *C* is the name of a programming language.
* *Red* is the name of a color.
* *Church* is the name of a mathematician.

Does this amount to a categorization of English nouns?

---
Tags: functional-programming, lambda-calculus
---


# Question
Title: Neural Network Normalization and de-Normalisation of data
I am developing a simple backprop neural network with n inputs and 1 output. I am using a sigmoid activation function. \[Aforge.Net\]

I have read that it is good to normalise the input and output data prior to training, which I have done using a simple linear relation (max/min mapping) to normalise between \[0, 1\].

My question is, what happens when upon using the NN after training, I get inputs that are larger/smaller than the max/min of the training sets (used for normalisation)? Should I be storing new max/mins and using these to re-normalise my new inputs? or do I just normalise the data with the parameters used in the training set and simply give the network inputs that may be greater than 1 or less than 0?

# Answer
> 2 votes
You should definitely not be storing new max/mins after training is finished since that will mess up the values for the values that are within the old max and min.

You're network might not do very well on any of these new values anyway since they are more extreme than anything it saw during training. You should scale everything using the max/min you found during training. You could cap anything more extreme than that to be either 0 or 1.

# Answer
> 0 votes
I only want to add a few things to Aaron answer: Experimentally, I found it to be more effective to normalize the data with its variance and mean, i.e., given feature X, (X\_new X-mean(X))/var(X)^.5.

Anyway, I have to point out that normalization is NOT a necessary step for neural net training, by initializing the weights with very small values you can easily handle the non-normalized datasets, though normalization usually increase the training speed.

---
Tags: neural-networks
---


# Question
Title: Why is a quantum computer not capable of solving more problems than a classical computer?
On the Wikipedia page for quantum algorithm I read that

> \[a\]ll problems which can be solved on a quantum computer can be solved on a classical computer. In particular, problems which are undecidable using classical computers remain undecidable using quantum computers.

I expected that the fundamental changes that a quantum computer brings would lead to the possibility of not only solving problems that could already be solved with a classical computer, but also new problems that could not be solved before. Why is it that a quantum computer can only solve the same problems?

# Answer
Because a quantum computer can be simulated using a classical computer: it's essentially just linear algebra. Given a probability distribution for each of the qubits, you can keep track of how each quantum gate modifies those distributions as time progresses. This isn't very efficient (which is why people want to build actual quantum computers) but it works.
> 23 votes

# Answer
Classical computers are already Turing complete, i.e. they can calculate everything that a Turing machine can (a theoretical computer model from Computer Science). According to the Church–Turing thesis Turing completeness includes all functions which can be calculated using any mechanical process. So if this thesis is true, *any* computer you could possibly build could never solve more problems than a classical one (disregarding efficiency).

P.S.: Even if you *could* build a computer that would solve more problems that a classical one, you would never know if that machine is working correctly, because if the machine could generate a proof for the solution for every input verifiable by a classical computer (or a turing machine or a human), the classical computer could just create all possible texts until one text describing such a proof is found.
> 11 votes

# Answer
Actually, it depends of what you mean by "solving a problem". As previously stated, a classical computer is already Turing complete and can decide any decidable problem in finite time. ~~There is no such thing of a computer able to decide an undecidable problem in finite time (that would actually lead to a contradiction).~~
\[Edit: as David Richerby stated in the comments, that hasn't been proved (only conjectured)
However most of the undecidability proofs can be repeated for any reasonable kind of computer (this doesn't prove the conjecture, but in my opinion it's a good hint)
The good argument regarding why a quantum computer couldn't decide more problems than a classic Turing machine has already been given by David Richerby (you can simulate a quantum Turing machine with a classical Turing machine)\]

Hence a classical computer can theoretically solve any "reasonable" problem... given enough time (it will be finite, it doesn't mean it will be fast).

The wikipedia quote doesn't talk about time at all, and a quantum computer is expected to solve some problems faster than a classical computer. By "faster", i mean that some problems which would have taken millenia to decide on a classical computer could be solved in minutes on a quantum computer (provided such a computer can be built, we don't know for sure yet, although there are promising results, and provided BQP != BPP which is a weaker hypothesis than NP != P if i'm not mistaken).

For instance, the famous Shor's algorithm shows that factoring an integer in its prime factors is in BQP (Bounded error Quantum Polynomial time) whereas that problem isn't believed to be in P (Polynomial time) or BPP (Bounded error Probabilistic Polynomial time). That doesn't mean factoring an integer on a classical computer is impossible, but it will be a time consuming task, and for sufficiently big numbers the computation may exceed any reasonable time limit (like the age of the universe; of course that's true of almost any computation given a sufficiently big entry, but that would happen much faster for problems outside of BPP on a classical computer than for problems inside of BPP).

So, even though all decidable problems can be solved on classical computers, some problems are still practically out of reach because of unreasonable computation times. A quantum computer may allow us to decide such problems in more reasonable time.
> 1 votes

# Answer
**The roadblock to more powerful computers isn't speed; it's space**. Technically, classical computers aren't even really equivalent to Turing machines. The reason for this is that a Turing machine has an infinite tape, and although we can simulate very large tapes, we can't go infinite. This matters more than you might think. **There are entire classes of problems where we know how they could be solved if we had infinite space to work with, but are currently stymied in actually solving them by the finite-space problem**. There are other problems that we can currently solve slowly, but could be solved *much* more quickly if we had infinite space.

A Turing-like machine with a finite tape (the thing we're usually really simulating when we talk about "Turing machines" in this context) is called a *linear bounded automaton*, and it's a closer match for classical computing than true Turing machines are. However, the difference between finite and infinite is pretty stark: LBAs just plain aren't as powerful as true Turing machines.

**Quantum computers don't solve the finite-space problem, and they don't try to**. They can tackle many computations at once, but we can already simulate that on classical machines. Quantum machines don't do *more*; they just do it *faster*.
> 1 votes

# Answer
One thing that quantum computers should be able to do that regular computers will never do is to use quantum entanglement.

Quantum entanglement is a property that allows to communicate instantly across the whole universe, without transmitting anything. The communication cannot be intercepted or tampered with. Also I can communicate several chips. This means that I can communicate the CPU with the RAM and with the SSD instantly.

So you could have super fast computers. And if I buy some special chip, for example from Amazon Quantum Web Servers, then I could use their infrastructure to perform computations AS IF they were running on my machine... no communication overhead... at least theoretically...

Having a CPU perform all computations in parallel like solving the traveling salesman problem... that makes no sense... if a CPU could do that, all possible results would come out at once... a giant map reduce done in a single chip... how do I pick the right answer?

I mean if the correct answer is 5, but it spells out 5,6,7,8,9,10,15,20,30,40,50,60,70,80... etc. at the same time, how can I know that the correct value is 5?
> -5 votes

---
Tags: computability, computation-models, quantum-computing, simulation
---


# Question
Title: Getting the essential from the fundamental matrix
Is it possible to get E from F? I suppose that can't work, because then I could calculate the the extrinsic (and maybe also intrinsic?) parameters of the cameras without a calibration object of known size etc. like so:

1. Pick (8) corresponding points in images i1 and i2
2. Calculate F with the eight-point-algorithm
3. Calculate E from F
4. Determine relative position and orientation of cameras from E (and maybe it is also possible to get the intrinsic parameters, K?)

# Answer
You can only get the essential matrix from the fundamental matrix if you know the camera intrinsics:

E = K' * F * K

where K is the intrinsic matrix and K' is its transpose.
> 3 votes

---
Tags: computational-geometry, image-processing, computer-vision
---


# Question
Title: Do Approximation Algorithms Analyzed in the Worst Case?
From wikipedia:

> For some approximation algorithms it is possible to prove certain properties about the approximation of the optimum result. For example, a $ρ$-approximation algorithm $A$ is defined to be an algorithm for which it has been proven that the value/cost, $f(x)$, of the approximate solution $A(x)$ to an instance $x$ will not be more (or less, depending on the situation) than a factor $ρ$ times the value, OPT, of an optimum solution.
>
> $$\begin{cases}\mathrm{OPT} \leq f(x) \leq \rho \mathrm{OPT},\qquad\mbox{if } \rho \> 1; \\ \rho \mathrm{OPT} \leq f(x) \leq \mathrm{OPT},\qquad\mbox{if } \rho \< 1.\end{cases}$$

For a maximization problem, a $\rho$-approximation algorithm means that, for an instance $x$, $\rho \mathrm{OPT} \leq f(x) \leq \mathrm{OPT}$, for any $\rho\<1$. Is this mean that **in the worst case** the algorithm produces a solution that is at least $\rho \mathrm{OPT}$? Or is this **in the average case**? Because there are some instances where the algorithm find the optimal solution.

I mean, if the algorithm is executed, say $10000$ times (with randomly generated instances) and produces $\mathrm{OPT}$, say $9995$ times and $5$ times it produces a value that is greater than $\rho\mathrm{OPT}$. What can we say about the algorithm then?

# Answer
> 2 votes
It's a worst case guarantee. It can in some cases do better than $\rho OPT$, but it will never do worse.

In your example we can say very little about the algorithm since you've only tested it with relatively few random instances of a given size. On non-random (structured) inputs it might perform much worse.

# Answer
> 0 votes
It is the worst case. $\rho$ can be one sided bound as in examples you provided or bounded on both sides (example is in next paragraph on wikipedia).

This might be the case $$\mathrm(OPT - c) \leq f(x) \leq \mathrm(OPT + c)$$ But still it might be bounded on one side but situation you have is due to roundoff problems of floating point values.

Unfortunatelly we cannot assume anything about algorithm when given finite number of instances.

---
Tags: algorithm-analysis, approximation
---


# Question
Title: Fundamental and essential matrices, value of intrinsic parameters
I observe a scene with two cameras, c1 and c2, that produce two images i1 and i2, respectively. What I ultimately want to do is to use information of image i1 and image2 simultaneously, e.g., for object detection.

As far as I understand it, I would not be required to find the intrinsic parameters of c1 and c2, also I do not need to know their relative position and rotation if I want to rectify i1 and i2. I can "simply" calculate F from a set of corresponding points - with no explicit relation in 3D of the points (like known distances). Which disadvantages would that have for me? I would not be able to do 3D reconstruction then, correct? But apart from that, there is no difference?

Or, asked differently, for rectification I do not need the intrinsic parameters. I only need them to do 3D reconstruction? What are the intrinsic parameters good for?

# Answer
What are the intrinsic parameters good for? They potentially allow mapping objects in the images to locations in the real world (in 3D). For some applications, that can be very useful. For instance, consider pedestrian detection, where we want to detect pedestrians. Usually, it's not enough to detect the presence of a pedestrian: we also want to know exactly where the person is, and how far away they are.

---

Calculating alignment from a set of corresponding points is not an unreasonable approach to aligning two images. The primary disadvantage is that you need a way to identify a set of corresponding points. This typically requires either (a) explicit calibration or (b) heuristic methods.

Explicit calibration is a perfectly fine approach, if it is feasible for your application. However, for some applications we only have images post-facto and we don't have any way to do an explicit calibration, so it's not always an option.

Heuristic methods are another possibility. They try to find corresponding points, e.g., using Lucas-Kanade, optical flow, or other methods. As heuristics, they are not guaranteed to work. Sometimes they might fail to detect corresponding points, or output false detections. Another issue is that their effectiveness depends upon characteristics of the scene that you're capturing: they're more effective for some kinds of scenes than others. But this also could be a valid approach.

---

To be clear: 3D reconstruction requires two cameras (as mentioned in the question) or depth information; just one 2D camera plus its intrinsics are not enough to reconstruct where each object is in the real world, in 3D space.
> 2 votes

---
Tags: computational-geometry, image-processing, computer-vision
---


# Question
Title: When is the concatenation of two regular languages unambiguous?
Given languages $A$ and $B$, let's say that their concatenation $AB$ is *unambiguous* if for all words $w \in AB$, there is exactly one decomposition $w = ab$ with $a \in A$ and $b \in B$, and *ambiguous* otherwise. (I don't know if there's an established term for this property—hard thing to search for!) As a trivial example, the concatenation of $\\{\varepsilon, \mathrm{a}\\}$ with itself is ambiguous ($w = \mathrm{a} = \varepsilon \mathrm{a} = \mathrm{a} \varepsilon$), but the concatenation of $\\{\mathrm{a}\\}$ with itself is unambiguous.

Is there an algorithm for deciding whether the concatenation of two regular languages is unambiguous?

# Answer
Hint: Given DFAs for $A$ and $B$, construct an NFA which accepts words in $AB$ having at least two different decompositions. The NFA keeps track of two copies of the standard NFA for $AB$ (formed by joining DFAs for $A$ and $B$ with $\epsilon$ transitions), ensuring that the switch from $A$ to $B$ happens at two different points.
> 10 votes

# Answer
**Updated** (thanks to Yuval Filmus).

Given two languages $X$ and $Y$ of $A^\*$, let \begin{align} X^{-1}Y &= \\{u \in A^\* \mid \text{there exists $x \in X$ such that $xu \in Y$} \\} \\ YX^{-1} &= \\{u \in A^\* \mid \text{there exists $x \in X$ such that $ux \in Y$} \\} \end{align} I claim that $XY$ is unambiguous if and only if the language $X^{-1}X \cap YY^{-1} \cap A^+$ is empty.

**Proof**. Suppose that $XY$ is ambiguous. Then there exists a word $u$ which has two decompositions over $XY$, say $u = x\_1y\_2 = x\_2y\_1$, where $x\_1, x\_2 \in X$ and $y\_1, y\_2 \in Y$. Without loss of generality, we may assume that $x\_1$ is a prefix of $x\_2$, that is, $x\_2 = x\_1z$ for some $z \in A^+$. It follows that $u = x\_1y\_2 = x\_1zy\_1$, whence $y\_2 = zy\_1$. Thus $z \in X^{-1}X \cap YY^{-1}$.

Suppose now that $X^{-1}X \cap YY^{-1}$ contains some nonempty word $z$. Then there exist $x\_1, x\_2 \in X$ and $y\_1, y\_2 \in Y$ such that $x\_2 = x\_1z$ and $y\_2 = zy\_1$. It follows that $x\_2y\_1 = x\_1zy\_1 = x\_1y\_2$ and hence the product $XY$ is ambiguous.

If $X$ and $Y$ are regular, then both $X^{-1}X$ and $YY^{-1}$ are regular and thus $X^{-1}X \cap YY^{-1}$ is also regular (see Yuval's answer for an automaton accepting this language).
> 9 votes

---
Tags: algorithms, formal-languages, computability, regular-languages, ambiguity
---


# Question
Title: Is there a more efficient algorithm than backtracking/dynamic programming?
Consider the following game:

One day a castle is attacked at sunrise (by surprise) by n soldiers.

Each soldier carries a canon and a rifle.

The castle has strength s.

On the first day each soldier shoots his canon at the castle costing the castle n strength points (i.e. the castle ends the first day with s=s-n strength points). After all the soldiers have fired, the castle sends dpw defenders to battle them.

In the ensuing days the castle and the soldiers battle it out following these rules:

1. All the soldiers fire first. A soldier can fire his canon at the castle or his rifle at one of the defenders (but not both and each soldier can only shoot once). One shot at a defender kills him. One shot at the castle decreases its strength by 1.
2. Then each of the d defenders shoots at one soldier (and only one) killing him.
3. If the castle still has strength points (i.e. s\>0) it sends a new batch of dpw defenders at this point. The total number of defenders in the next round will be d=d+dpw.
4. Repeat 1 through 3 on each new day.
5. If all soldiers are killed by the defenders, the castle wins.
6. If there are zero defenders after the soldiers shoot and the castle strength is zero, the soldiers win.

We would like to know the minimum number of rounds the soldiers need to win the game (or if not possible the minimum number of rounds for the castle to win the game).

We would also like to know the number of soldiers, defenders and castle strength at the beginning of each round for the minimum number of rounds solution.

An easy way to solve this problem seems to me to be by recursive backtracking/depth first search or dynamic programming.

The problem however seems simple enough that a better/faster solution seems likely to exist (one that doesnt involve a large search or maybe even a search at all).

Is it obvious what that better strategy/algorithm might be?

# Answer
> 6 votes
(Throughout this answer I use $\phi = \frac{1+\sqrt{5}}{2}$, which is the Golden Ratio.)

**Solution:**

* If $s\leq n$, the attackers can win in one day.
* If $s+dpw\<\phi^2n$ and $s\<2n$, the attackers can win in $2+\max(k,0)$ days, where $$k=\left\lceil\frac{\log\_\phi{\left(\frac{n+(dpw+s-2n)\phi^{-1}}{n-(dpw+s-2n)\phi}\right)}}{4}\right\rceil.$$
* If $dpw\<n$, the attackers can win in $c+\max(k,0)$ days, where $$c = \left\lceil\frac{\sqrt{dpw^2+4 n\cdot dpw}-dpw+2 n-2 s}{2 (dpw-n)}\right\rceil$$ and $$k = \left\lceil\frac{\log\_\phi{\left(\frac{n+(s + c\cdot dpw-(c+1)n)\phi^{-1}}{n-(s + c\cdot dpw-(c+1)n)\phi}\right)}}{4}\right\rceil.$$
* If the attackers cannot win, the minimum number of days for the castle to win is $2$ (the attackers all fire their cannons and are wiped out on day two).

**Proof:**

For a given day $i$, let $s\_i$ be the remaining castle strength, $a\_i$ be the remaining attacking force, and $d\_i$ be the remaining defending force.

First consider the case that $d\_i = dpw$ (that is, the attackers killed all defenders the day before). Assume that the attackers leave $x$ defenders alive but do not destroy the castle; then $$a\_{i+1} = a\_i-x;$$ $$d\_{i+1} = dpw+x;$$ $$s\_{i+1} = s\_i-(a\_i-(dpw-x)) = (s\_i+dpw)-(a\_i+x).$$ On day $i+1$, the defending force is larger than on day $i$ and the attacking force is smaller than on day $i$. Furthermore, even if the attackers return to the strategy of wiping out the defending force on day $i+1$, $$a\_{i+2} = a\_i-x;$$ $$d\_{i+2} = dpw;$$ $$s\_{i+2} = s\_{i+1}-(a\_{i+1}-d\_{i+1}) = s\_i+2dpw+x-2a\_i.$$ If, instead, the attackers had wiped the defending force on day $i$, the castle's strength would be $s\_i+2dpw-2a\_i$. Therefore, **it is never advantageous to leave both defenders and the castle alive on the same day.** (Note that if $s\_i+2dpw+x-2a\_i\<0$ -- that is, they destroyed the castle on day $i+1$ -- they could have have done the same thing without losing troops; therefore, while it might not always be disadvantageous, it is never advantageous.)

Now the question is, when the attackers do destroy the castle, how many days will it take to kill the remaining defenders (with the obvious assumption that the attackers would not make a final push on the castle unless they can still win)? Assume, without loss of generality, that the castle is destroyed on day $q$ and that there are $x$ defenders remaining alive. So $$d\_{q+1} = x;$$ $$a\_{q+1} = n-x;$$ $$d\_{q+2} = d\_{q+1}-a\_{q+1} = 2x-n;$$ $$a\_{q+2} = a\_{q+1}-d\_{q+2} = 2n-3x;$$ $$d\_{q+3} = d\_{q+2}-a\_{q+2} = 5x-3n;$$ $$\dots$$ From this we can see that $d\_{q+i+1} = Fib(2i+1)x-Fib(2i)n$. Therefore, (finding the closed form of $Fib(\cdot)$ and four pages of algebra later), the attackers will win $$k = \left\lceil\frac{\log\_\phi{\left(\frac{n+x\phi^{-1}}{n-x\phi}\right)}}{4}\right\rceil$$ days after destroying the castle. $x = s'+dpw-n$, where $s'$ is the strength of the castle on the day it is destroyed.

On every day that the attackers *can* make a final push on the castle, the question is, "Would it be advantageous to wait until tomorrow?" Every day (after the first) that the attackers do not make a final push, the castle's strength decreases by $n-dpw$. Therefore, at the beginning of the day of the final push (day $i$), $s' = s-n-(i-1)(n-dpw)$, so $x\_i = dpw-(n-s') = $ $s + i\cdot dpw-(i+1)n$ (where $x\_i$ is the remaining defending force if the attackers pushed on day $i$). It is advantageous to wait another day if $$ \frac{\log\_\phi{\left(\frac{n+x\_{i+1}\phi^{-1}}{n-x\_{i+1}\phi}\right)}}{4} + 1 \< \frac{\log\_\phi{\left(\frac{n+x\_i\phi^{-1}}{n-x\_i\phi}\right)}}{4},$$ that is, when one more than the number of days to destroy the $x$ beginning on day $i+1$ is less than the number of days to destroy $x$ beginning on day $i$. Three pages of algebra later, we find that it becomes advantageous to destroy the castle on the day $$c = \left\lceil\frac{\sqrt{dpw^2+4 n\cdot dpw}-dpw+2 n-2 s}{2 (dpw-n)}\right\rceil.$$

After destroying the castle, we still have to kill the troops, so the total number of days is $c+k$, using $i=c$ to find $k$.

Finally, we must handle the edge case that $dpw \geq n$. Intuitively, the attackers can only be victorious only if they can destroy the castle on the first day of fighting (day 2) with enough troops left to defeat the remaining defenders. This can only happen if $s\<2n$ (they can destroy the castle by the end of the second day) and if $s+dpw\<(\phi+1)n$ (they can destroy the castle and do enough damage that the defenders cannot effectively retaliate); it will take $\left\lceil\frac{\log\_\phi{\left(\frac{n+(dpw+s-2n)\phi^{-1}}{n-(dpw+s-2n)\phi}\right)}}{4}\right\rceil$ days to kill the rest of the defenders.

---
Tags: algorithms, algorithm-analysis, search-algorithms, dynamic-programming, backtracking
---


# Question
Title: "Most Similar Vector Problem" on an Integer Lattice
I am currently working on problem that I think could be expressed as an integer lattice problem, and hoping to find some guidance on this forum.

Given $u \in \mathbb{R}^n$ and a *bounded* integer lattice $L = \mathbb{Z}^n \cap \[-M,M\]^n$, I would like to find an integer vector $v \in L$ such that the angle between $u$ and $v$ is as small as possible. That is, I would like $$v \in \text{argmax}\_{w \in L} \frac{u.w}{\\|u\\|\\|w\\|}$$

Here, the objective function is just the cosine between the vectors $u$ and $w$.

I am wondering if this problem can be formulated as a well-known integer lattice problem (such as a closest vector problem). If so, is there an algorithm that I could use to solve it? Any help or resources would be greatly appreciated.

# Answer
I don't know of a good approach to this, or whether there's any literature on it.

However, if you're completely stuck, one possible approach is to use integer quadratic programming and binary search.

WLOG we can assume $\\|u\\|=1$ (otherwise replace $u$ with $u/\\|u\\|$). Now the decision problem is, given $\alpha$, to determine whether there exists $w$ such that $u \cdot w / \\|w\\| \ge \alpha$, i.e., such that $(u \cdot w)^2 \ge \alpha^2 \\|w\\|^2$. Define

$$\Phi(w) = \alpha \\|w\\|^2 - (u \cdot w)^2.$$

Note that $\Phi$ is a quadratic function in the unknowns $w\_1,\dots,w\_n$, and the decision problem can be solved by maximizing $\Phi(w)$ subject to the constraints $-M \le w\_i \le M$. The answer to the decision problem is yes iff there's a solution to this integer quadratic program where $\Phi(w) \ge 0$. Now if you could solve the decision problem, you could use binary search on $\alpha$ to find the largest $\alpha$ for which a solution exists.

Unfortunately this requires *integer* quadratic programming, which might be very hard. One heuristic approach might be to relax to semidefinite programming instance (with real numbers instead of integers), look for a solution (in the reals), round to the nearest integer point, and see if that gives you a valid solution. This is not likely to give you an exact solution but it's possible it might give you some kind of approximation to the correct answer. Unfortunately, I have no idea how good or bad an approximation it might be.
> 2 votes

---
Tags: reference-request, cryptography, integers, lattices
---


# Question
Title: Can an Earley Parser be made into a fuzzy parser similar to the Levenshtein Automata Algo for DFA?
There's a way to perform fuzzy parsing (accepts strings even with typos to a certain edit distance), with a DFA and a run-time constructed Levenshtein Automata of the input word. Can something similar be done with an Earley parser? I'm finding it hard to understand the algorithm, let alone answer this question.

# Answer
> 8 votes
The answer is yes. However I would not do that with an Earley parser because there are simpler ones with the same capabilities.

Basically, Earley parser belongs to a family of general context-free parsers, that produces all possible parses for a given string, when the grammar is ambiguous.

There are two ways (at least) of understanding these parsers:

* as dynamic programming interpretation of a pushdown automaton corresponding to the grammar on the input string;
* as the the construction of the intersection of the grammar with a finite state automaton.

When parsing a single string, the finite state automaton to be considered is a linear automaton that recognizes only the string $w$ to be parsed, one symbol at a time (number of state is $|w|+1$). If you apply the cross-product construction of a FA $A$ and a CF garmmar $G$ (Bar Hillel, Perlis, Shamir 1961), you get a new CF grammar that is a new grammar $F$ which generates $\mathcal L(A)\cap\mathcal L(G)$. The interesting point usually overlooked is that $F$ preserves the parse-trees used by $G$, up to non-terminals renaming (due to cross-product).

Thus if the FA $A$ generates only your input string, the grammar $F$ will generate only that string (if it is in $\mathcal L(G)$, otherwise it generates the empty language $\emptyset$). Furthermore, it generates it with all the parse-trees that $G$ could use to generate it.

This grammar $F$ is what is usually called a shared parse forest, and all general CF parsing algorithms are a more or less optimized version of the cross-product construction, whether CYK, Earley, generalized LR or LL, or others. So all I am saying applies to them too.

But, as you see, this generalizes to parsing a whole regular set, if anyone is interested in doing that.

That is precisely your question. You have a string $w$. You want to parse it up to some variations defined by a finite state transducer, which in your case is a transducer that produces all strings within some given Levenshtein edit distance of $w$ (but the origin of the transducer is immaterial). The set of those strings is a regular set that can be defined by a FA, with weighted transition that can compute the edit distance of each string.

If you do the cross-product with your grammar $G$, you get a shared parse forest grammar $F$ that generates all the strings in the intersection. Furthermore, you get the weights on some of the rules so that you can compute the edit distance of each of the accepted strings.

If desirable, this can be used to keep only the strings with minimal distance.

However, this can be improved a bit since composition with finite state machines is associative.

If you always use the same, finite state transducer, as is the case in your question, the right way to go about is to compose the Grammar $G$ and the transducer (here the Levenshtein automaton), independently of the input string. This gives you a weighted grammar that you can use to parse the input string $w$. The problem is that parsing with the brutal intersection construction with give you strings at any Levenshtein distance, i.e. $\Sigma^\*$.

It would be easy to prune that construction to get the same result as before, but the best way is a more controlled intersection construction, such as the dynamic programming organization used by most parsers in the literature, including Earley's, and use it to avoid generating useless rule by computing distances and aborting any computational path when it exceeds the desired threshold. Dynamic programming can also be used to compute directly the parse-forest (or parse-tree) for the string that have the shortest distance to the input.

---
Tags: algorithms, context-free, finite-automata, parsers, string-metrics
---


# Question
Title: Are there other interpretations of |G| than |V|, that is |V(G)|?
This may be a basic question, but I'm hoping someone can settle this nagging doubt I'm having. I'm reading up on FPT complexity using a book by Downey and Fellows. It has some introductory examples which detail complexity in terms of $|G|$, which seems to denote $|V|$ as mentioned here.

The sections containing those examples explicitly refer to $|V(G)|$ however, so I wonder if there might be other interpretations of $|G|$ that convey some nuance in terms of complexity I'm missing, or can I safely assume that it does in fact mean $|V|$?

# Answer
> 4 votes
I don't have the book, so I looked through the pages available on Google Scholar. It seems that they use $|G|$ to denote the size of a graph description that is $|V(G)| + |E(G)|$.

For example on page 24 they say that Vertex Cover is solvable in $2^k|G|$ time using bounded search tree method. In fact this method gives $2^kk|V|$ time for graphs with at most $k(|V| - 1)$ edges (it's easy to show that otherwise graph doesn't have Vertex Cover of size $k$). According to this "reverse engineering" $|G|$ corresponds to $k|V|$ that is essentially $|V| + |E|$.

---
Tags: complexity-theory, graphs
---


title: How to read BNF syntax of C?

text:
# Question
Title: How to read BNF syntax of C?
Today I heard of BNF which is a language for languages. Also heard that it specifies the entire syntax of C in four pages. So I thought of checking it out. After reading through this page, I got a fair idea about how to read the syntax.

But I don't understand what the first two lines mean:

```
%token int_const char_const float_const id string enumeration_const
%%

```

Also I am reading BNF just because I am just curious. How should I proceed to understand the formal syntax by reading BNF?

Here is the BNF syntax of C.

# Answer
> 4 votes
Backus Normal Form does not define special syntax for `%token`. So that would be a special syntax custom-added by a particular person or web page or tool. Tool support is off-topic here, but if search for "%token" on the first link you gave, you'll find a brief explanation that appears to describe what `%token` means in the context of that particular example.

In other words: if you only want to understand BNF at a conceptual level, ignore it. That's something that's not part of BNF, but is an add-on that was added for some special purpose. If you want to understand that the specific syntax used by some specific tool (e.g., YACC), your best source is probably the reference manual for that tool.

# Answer
> 1 votes
## The document you are using is not BNF (Backus-Naur Form)

BNF is a language used to specify CF grammars. Like most languages it has a reference syntax. It always possible to define another syntax for the same language.

For example you could use another syntax for Python where all the English keywords are replaced by German keyword, and the semi-colon is replaced by the keyword `semi-colon`. It would work as well, but it would not be considered standard Python. You could even make more drastic syntactic changes without really changing the way it works, including use of `begin` and `end` in place of indentation.

Similarly BNF has a reference syntax which is described in various documents, including this wikipedia page. Their are variants, like EBNF (extended BNF) that allow for the use of regular expressions as the right hand-side of rules.

But basically, BNF is just a standard syntax to write context-free (CF) grammars.

The document you refer to does contain a CF grammar. But the syntax is not BNF (and since BNF is just a standard syntax for CF grammars, the use of the name BNF is abusive).

**NOTE**
I realize (belatedly) that your second link (which I missed) points to a document where the author Pete Jinks takes a different point of view. It only shows that **you should always be careful with information found on the web** (including from myself), and double check it. He calls it a variant of BNF, but it is as much a variant as my caricature of Python (and I could have made it worse) is a variant of Python. Just try to use it to exchange Python programs with other people. Or double check what he and I are saying with other reference information on the web.

## Reading a specification

You are supposed to know how to read a CF grammar.

The *real* BNF syntax may look strange sometimes, because it is a meta-syntax (the syntax of a language for describing the syntax of other languages), and thus it requires various forcing devices, like those needed to include in a string the symbols used as string delimiters, for example with a backslash, or to include a "\*" as symbol in a regex that already uses the same symbol as an operator.

Another aspect is that the syntax of a programming language is usually decomposed in two levels:

* lexical specification usually done with finite stete technology, or regular expressions. It specifies the spelling of terminals of the CF syntax, i.e. what is sometimes called tokens.
* context free syntax, which is often expressed in BNF since the langage Algol 60.

Terminals are usually infinite in number, which does not do well for a finite specification of CF syntax (a formal requirement for CF grammars). Hence most of them are grouped in a finite number of families, called in your exanple: \- `id` for identifiers such as `foobar` \- `int_const` for integer literals such as `23` \- etc...

The syntax of these potentially infinite families is not usually included in the BNF, and use of any such terminal is replaced by the name of the family.

**It is the list of names of these families of terminals (tokens) that is listed in the lines you worry about.**

In standard BNF, they may not be described at all, and left to a complementary specification. Then they can be identified by the fact they they are not the left-hand side of any rule.

Alternatively they can be associated with rules of a regular grammar defining them, also written in BNF. But this may be confusing. One major reason is that the separation between lexical and CF syntax usually plays a role in the interpretation of program layout, especially spaces, tabs and other "invisible" characters.

The most common principle (though not fully used in a language like Python) is that invisible characters can be used arbitrarily as separators of lexical elements, but are ignored at the CF syntactic level. This implies that ther are not to be used in lexical elements unless explicitly permitted by the specification of the lexical family.

Note that all other terminals such as reserved words (`if`, `else`, `while`, ...), operators (`+`, `==`, ...) or punctuation symbols (`;`, `,`, ...) appear directly in the BNF as strings within double quotes.

Of course, as you can see from your own example, people never quite respect standards. Hence **it is always wise to read the tool specific documentation**. But it is useful to have the standard as reference to understand what it means and what it is for.

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


# Question
Title: Kleene star operation on the empty language
In my text book it is mentioned that: $\emptyset^\*=\\{\epsilon\\}$ where $\emptyset$ is an empty language.

However, we know that $L \cdot \emptyset = \emptyset$, where $L$ is any Language.

I am not able to intuitively grasp this concept because the Kleene star operation points towards the fact that $\emptyset^\*=\emptyset^0 \cup \emptyset^1 \cup \emptyset^2 \cup \cdots$ .

So why is $\emptyset^\*$ not equal to $\emptyset$?

# Answer
If you consider now the powers of a language $W$ you have $W^xW^y=W^{x+y}$ If you want this to be consistent over $\mathbb N\_0$, i.e. the non-negative integers, you have to define $W^0=\\{\epsilon\\}$. If you took it to be $\emptyset$ you would have $W^x=W^{x+0}=W^xW^0=W^x\emptyset=\emptyset$ including, among others, for $x=1$. Thus we would have $W^1=W=\emptyset$ for any $W$. Thus this would clearly be inconsistent. A similar inconsistency arises for any other choice than $\\{\epsilon\\}$, which is the identity for language concatenation.

Hence, the only consistent consistent definition of $W^0$ for a non empty set $W$ is $W^0=\\{\epsilon\\}$.

It is then convenient to extend the definition to the case when $W=\emptyset$ as $\emptyset^0=\\{\epsilon\\}$.

This is just a consistent and convenient definition, often adopted in semi-rings but it cannot be proved, unlike thw case when $W\neq\emptyset$ where there is no other consistent definition.

However, other definitions have then to be given in a consistent way, which implies that

$$\begin{align} \emptyset^\*&=\emptyset^0\cup\emptyset^1\cup\emptyset^2\cup\ldots \\ &=\\{\epsilon\\}\cup\emptyset\cup\emptyset\cup\ldots\\ &=\\{\epsilon\\} \end{align}$$

The topic is discussed on many web pages. In the case of the semi-ring of numbers (the lack of precision is intentional) this is discussed at length on this page: Zero to the zero power - Is $0^0=1$?.

The semi-ring of languages is described in this answer.
> 16 votes

# Answer
The concatenation of zero words from $\emptyset$ is the empty word $\epsilon$, so $\epsilon \in \emptyset^\*$. More generally, for a language $L$, the Kleene star $L^\*$ consists of all concatenation of any number of words from $L$, *any number* including *zero words*.
> 3 votes

---
Tags: formal-languages, kleene-star
---


# Question
Title: If recursive Fibonacci is $O(2^N)$ then why do I get 15 calls for N=5?
I learned that recursive Fibonacci is $O(2^N)$.

However, when I implement it and print out the recursive calls that were made, I only get 15 calls for N=5. What I am missing? Should it not be 32 or near abouts? It's like less then half!

```
$COUNT = 0

def fibonacci( n )
   $COUNT +=1
   return  n  if ( 0..1 ).include? n   # Base Case returns 0 or 1
   fibonacci( n - 1 ) + fibonacci( n - 2 ) # Recursive case
end

```

# Answer
You ask,

> I have an $O(2^n)$ runtime, why do I not observe $2^n$ recursive calls for $n=15$?

There are many things wrong in the implied conclusion.

1. $O(\\\_)$ only gives you an *upper bound*. The true behaviour may be of much smaller growth.
2. Asymptotics (like $O(\\\_))$ only give you only something in the *limit*, that is you can only expect the bound to hold *for large $n$*.
3. Since you use $O$ as though it was $\Omega$, note that a (lower) bound on *runtime* does not necessarily translate into a (lower) bound on *recursive calls*, each of which may take $\omega(1)$ time.

Similarly, a *tight* upper runtime bound (which you don't have) may not be a tight upper bound on the number of recursive calls for the same reasons.

You can analyse *exactly* how many recursive calls you need. Just solve the recurrence

$\qquad\displaystyle \begin{align\*} f(0) &= 1,\\ f(1) &= 1,\\ f(n) &= f(n-1) + f(n-2) + 1, \quad n \geq 3, \end{align\*}$

which adds up $1$ for every recursive call your program makes. See here for more detail on how you get to such recurrences.

See here how to do that, or use computer algebra. The result is

$\qquad f(n) = 2F\_{n+1} - 1$;

insert $n=5$ and you will get $f(n) = 15$. It's not that surprising that the Fibonacci numbers $F\_n$ should show up. Inserting their known closed form, we get

$\qquad\displaystyle f(n) = \frac{2}{\sqrt{5}} \cdot \Bigl( \varphi^{n+1} - (1-\varphi)^{n+1} \Bigr) - 1$

with $\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.62$ the golden ratio. This closed form of $f(n)$ implies

$\qquad\displaystyle f(n) \sim \frac{2}{\sqrt{5}} \cdot \varphi^{n+1} \approx 1.45 \cdot 1.62^n$

since $0\< 1 - \varphi \< 1 \< \varphi$. We see that the $O(2^n)$-bound is rather loose -- it has exponential absolute and relative error.
> 13 votes

# Answer
Double-recursion ends when `n<=1`, so it's more like 2^(n-1). As @pjs says, this doesn't change anything.

A function that take 0.1234 * (2^(n-3) + n^400) + 5000 cycles, or operations, or whatever, is still of the O(2^n) complexity class.
> 2 votes

# Answer
In addition to the 3 reasons given by Raphael in his answer, regarding why the aymptotic cost upperbound $O(2^n)$ does not give you $2^n$ recursive calls for $n=15$, I think you should add a fourth one:

4. Asymptotic costs are always defined up to a constant factor, when using Landau notation (big $O$, big $\Omega$, little $\omega$, etc.).

There is a reason for that: the cost unit is undefined. This makes analysis easier and somewhat support independent. As long as all primitive operations have a cost within a bounded interval, the relative cost of the various elementary steps of the algorithm can be ignored.

The price to be paid of course, is that the cost thus evaluated has no absolute meaning, only a relative one.

If we were to assume that:

* $O(2^n)$ is not an upperbound (as indicated by big $O$) but an exact cost function (point 1 of Raphael);
* $O(2^n)$ is not asymptotic but exact cost for all values of $n$ (point 2 of Raphael);
* each recursive call takes constant time (point 3 of Raphael);
* and that furthermore there are no cost other than the constant cost of each recursive call (not including sub-calls), which seems to be your implicit assumption,

we would still be unable to assert that for $n=15$ you should have $2^{15}$ calls, from the simple knowledge of $O(2^n)$ (ignoring how the formula was obtained, of course). The reason is the arbitrary constant factor that does not show in the formula.

At best you would know that there is a factor $k$ such that for each value of $n$ you should have $k2^n$ call. Thus, if you know that for $n=15$ you had $p$ recursive calls, that would imply that $p=k2^{15}$, which would allow you to compute the value of $k$, and then predict the number of calls for other values of $n$.

But this comes only after a lot of other assumptions, none of which is really true. With apologies for awkwardly attemtping to separate issues that really have meaning only together.
> 1 votes

---
Tags: algorithm-analysis, asymptotics, runtime-analysis, recursion
---


# Question
Title: Why is pure literal elimination absent in DPLL-based algorithms like Chaff?
I'm looking into various SAT-solvers and trying to understand how they work and why they are designed in certain ways. (But I'm not in a university at the moment and I do not know anyone who is a professor. So I'm posting here hoping that someone can help me out. I'd really appreciate.)

In Chaff, BCP (Boolean Constraint Propagation) is implemented differently from the original DPLL: it does it by watching two literals at a time (a technique slightly different from one initially suggested in SATO: An Efficient Propositional Prover) according to the 2001 paper, Chaff: Engineering an Efficient SAT Solver. There is, however, no mention of pure literal elimination in this paper.

In The Complexity of Pure Literal Elimination, Jan Johannsen wrote

> The current best implementations of DLL-type SAT solvers, like Chaff or BerkMin sacrifice this heuristic in order to gain efficiency in unit propagation.

where "this heuristic" is referring to pure literal elimination. My understanding of what pure literal elimination does is that it

1. searches for all single-polar (or pure) literals
2. assigns a boolean value to them such that each yields `True`
3. in which case we can now delete all the clauses containing them

---

Here is my question:

How is the sacrifice necessary? Is there a good reason why pure literal elimination is absent in DPLL-based algorithms like Chaff? Can't we just do pure literal elimination in each decision level (or at least do it at the start before branching)?

# Answer
Solvers that use the two-watched-literals algorithm to implement unit propagation don't keep track of which clauses have been deleted (by implication) to produce the subformula implied by the current partial assignment. By not tracking this information, solvers can avoid touching most of the clauses during assignments and avoid touching *any* of the clauses during backtracking. Figuring out which variables are currently pure in the formula means losing these substantial efficiency gains. Meanwhile there's nothing to suggest that pure literal removal will produce conflicts or satisfying assignments early enough to make up for the heavy tracking cost.

Solvers that do formula simplification before starting the search procedure will generally include pure literal removal since it is quite cheap to do as a preprocessing step and could potentially remove many clauses.
> 7 votes

---
Tags: algorithms, sat-solvers
---


# Question
Title: How can a cyclic tag system halt with an output?
For example, we can say we have a abstract program that, given a finite binary string as input, removes all of the zeros (i.e. 0010001101011 evaluates to 111111), which is definitely a Turing-computable function.

How can a cyclic tag system compute this (which it can, by definition of it being Turing-complete) when it only halts when it reaches the empty string? The Wikipedia article gives an example of converting to a 2-tag system, but it adds an emulated halt that the original system does not have.

I can't find any reference to how a cyclic tag system halts meaningfully. What is its output supposed to be? I've considered things like

* Number of steps (but then input restricts possible output without some kind of fancy encoding I can't find)
* The last production (but that only has a finite output range)
* Fixed points (which can't be detected in this system and only exist with very limited production rules and inputs)

but they don't work, at least not in any way I can see.

# Answer
> 6 votes
Neary and Woods describe an efficient simulation of Turing machines using cyclic tag systems, improving on work of Matthew Cook. Turing-completeness is a somewhat fluid and informal notion. A computing system X *simulates* another computing system Y if given each program in Y we can come up with a program in X such that looking at the transcript of the X-program, we can recover a transcript of the Y-program.

You can look at the papers above to see what this means for cyclic tag systems. The basic idea is that when the Turing machine halts, the cyclic tag systems keeps going, forever repeating the same sequence of configurations, representing the halting configuration of the Turing machine. In this sense it can actually compute functions.

---

In an earlier answer I noted that some computation models can only compute decision problems, in the sense that they either don't halt, or they halt with just one bit of output. In that case you can encode general function in at least two ways:

1. Given a function $f$, consider the language of pairs $\langle x,f(x) \rangle$.
2. Given a function $f$, consider the language of triples $\langle x,i,b \rangle$ such that the $i$th bit of $f(x)$ (if any) equals $b$.

As usual, we require that the machine *always* halt.

# Answer
> 4 votes
Although *non-halting* versions of cyclic tag may be of special interest for cellular automata, a cyclic tag system can also be designed to simulate a universal Turing machine in such a way that it halts iff the TM halts, displaying an *output word* that encodes the machine's output:

1. Simulate the TM with a 2-tag system that encodes all of the TM's instantaneous configurations, using a separate "output alphabet" to encode any halting configuration, such that the tag system halts (by erasing this word letter-by-letter) iff the TM halts. (This paper shows in detail how this can be done using a Wang machine formulation of TMs.)
2. Simulate the 2-tag system by a cyclic tag system as described in the Wikipedia article's cyclic tag system section. Since each letter in the 2-tag output alphabet has an empty string as its appendant (causing the 2-tag simulation to halt), the cyclic tag system will have the same halting/output behavior.

The key in this approach is that a designated output alphabet, say $\\{\alpha\_i\\}$, allows each of its letters to have the empty string as its appendant ($\alpha\_i\rightarrow \epsilon$), causing the simulation to erase the dataword and halt.

**NB**: For all three types of system (TM, tag, cyclic tag), the unambiguous identification of output can be ensured by using a specified output alphabet, and this can be done for both *halting* and *non-halting* varieties of these systems. (Given that "standard" TMs are of the halting kind, it is ironic that Turing's original computing machines were of the *non-halting* variety with output alphabet $\\{0,1\\}$.)

---

With the same approach, we can also directly construct a simple 2-tag system to erase any $0$s from a binary string, then simulate that with cyclic tag. The computations quickly get tedious, so we'll only apply it to the input string $101$, halting with the output string $11$. (The symbol `-` will denote the empty string.)

**2-tag**

```
input alphabet {a,b}, output alphabet {c}
input encoding:
<0> = aa
<1> = bb
input = <101> = bbaabb
output decoding: <cc> = 1

```

productions:

```
a -> -
b -> cc
c -> -

```

computation:

```
bbaabb   <-- input word <101>
  aabbcc
    bbcc
      cccc  <-- output word <11>
        cc
         -

```

**cyclic tag**

encoding the 2-tag alphabet:

```
<a> = 100
<b> = 010
<c> = 001
cyclic tag system = [-,001001,-,-,-,-]
cyclic tag input = <bbaabb> = 010010100100010010

```

computation:

```
appendant    dataword
---------    ---------------------------------------------------------------
-            010010100100010010  <-- input word <bbaabb> = <<101>>
001001        10010100100010010
-              0010100100010010001001
-               010100100010010001001
-                10100100010010001001
-                 0100100010010001001
-                  100100010010001001
001001              00100010010001001
-                    0100010010001001
-                     100010010001001
-                      00010010001001
-                       0010010001001
-                        010010001001
001001                    10010001001
-                          0010001001001001
-                           010001001001001
-                            10001001001001
-                             0001001001001
-                              001001001001  <-- output word <cccc> = <<11>>
001001                          01001001001
-                                1001001001
-                                 001001001
-                                  01001001
-                                   1001001
-                                    001001
001001                                01001
-                                      1001
-                                       001
-                                        01
-                                         1
-                                         -

```

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


# Question
Title: How to exclude all points adjacent to a given point from the feasible region of IP
Consider a basic integer program such as:

$$\begin{align} \min\_x & \quad c^Tx \\ \text{s.t.} & \quad Ax \leq b \\ &\quad x\_i \in \\{-100,\ldots,100\\} \end{align} $$

where $x \in \mathbb{Z}^n, A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R^m}$.

Say that I have a feasible point $y \in \mathbb{Z}^n \cap \[-100,100\]^n$ with the property that all points adjacent to $y$ cannot be optimal. In other words, given $y$, all points in the set:

$$\mathcal{A}(y) = \Big\\{ z \in \mathbb{Z}^d ~\big|~ z\_i = y\_i \pm 1 \Big\\}$$

could be excluded from the feasible region of the IP.

I am wondering if there is an elegant way to formulate constraints that will exclude all points that adjacent to $y$ from the feasible region.

# Answer
You can't eliminate all points in $A(y) \setminus \\{y\\}$ without also eliminating $y$, as the conjunction of a bunch of linear inequalities always gives a convex region, and $A(y) \setminus \\{y\\}$ is non-convex.

Here I am assuming we're not allowed to introduce new variables. If we're allowed to introduce new variables, there are many uninteresting ways to achieve it, by taking advantage of the fact that with integer variables you can express any logical predicate you like; however, it seems unlikely that this will be useful for anything in practice.
> 1 votes

---
Tags: optimization, discrete-mathematics, integer-programming
---


title: Solving a bivariate recurrence equation

text:
# Question
Title: Solving a bivariate recurrence equation
I'm dealing with this recurrence equation:

$\qquad\displaystyle T(m, n) = T(m/2, n/2) + T(m, n/2) + O(1)$.

Any idea how to solve this? I've looked in to few advanced resources but the literature on two dimensional recurrence equation seems to be very thin.

# Answer
> 5 votes
## Repeated substitution

Repeatedly substitute in, and look for a pattern:

$$\begin{align\*} T(m,n) &= T(m/2,n/2) + T(m, n/2) + 1\\ &= T(m/4,n/4) + 2 T(m/2,n/4) + T(m, n/4) + 3\\ &= T(m/8,n/8) + 3 T(m/4,n/8) + 3 T(m/2,n/8) + T(m, n/8) + 7\\ &\vdots\\ \end{align\*}$$

Do you see the pattern? The coefficients $1,3,3,1$ should remind you of binomial coefficients. The pattern is

$$T(m,n) = 2^k-1 + \sum\_{i=0}^k {k \choose i} T(m/2^i, n/2^k).$$

You can prove that this holds for all $k$ (by induction on $k$). Then, setting $k=\lg n$, we find

$$T(m,n) = n-1 + \sum\_{i=0}^{\lg n} {\lg n \choose i} T(m/2^i, 1).$$

So it suffices to know how to evaluate $T(m,1)$ for all $m$. That information cannot be deduced from the recurrence you gave us -- it needs to be supplied as additional base cases.

For instance, suppose we are given the base cases $T(m,1) = 1$ for all $m$. Then we find

$$T(m,n) = n-1 + \sum\_{i=0}^{\lg n} {\lg n \choose i} = 2n-1 = \Theta(n).$$

However, if we were given different base cases, the solution might be different.

## Guess-and-check

Another approach is to somehow guess the solution (for instance, by playing with a bunch of examples and looking for patterns), and then check that it holds. For your example, if we assume $T(m,n) = T(m/2,n/2) + T(m,n/2) + 1$ and we assume $T(m,1)=1$ for all $m$, then rubbing our rabbit's foot for luck, we might get lucky and guess

$$T(m,n) = 2n-1.$$

It is then easy to plug in and confirm that this is a valid solution to the recurrence you gave.

However, in general, guess-and-check is often very hard -- you can try many guesses, but sometimes it can be very difficult to find a guess that turns out to be correct.

---
Tags: recurrence-relation
---


# Question
Title: Need help constructing a Deterministic Finite Automata with AT MOST
I am stuck with constructing an DFA that has at most in it.

The question I am stuck with is:

> Design an DFA that accepts all strings over {0, 1} that contain at most two 00’s and at most three 11’s as a substring.

An answer in a form of a graph would be perfect but if someone can explain in plain words, I will appreciate that as well.

# Answer
> 2 votes
You can use states of the form $(i,j)$ where $i$ counts the number of 00s and $j$ counts the numbers of 11s read so far.

# Answer
> 1 votes
This is a sadistic question...

It is easy to build a DFA over a, b for "at most 2 a" or "at most 3 b"; and build a DFA for the intersection (states are pairs of states, one of each automaton; transitions trace the first automaton in the first part of the state and of the second similarly; final states are composed of final states for both).

The same ideas (more complicated, but similar) give "at most two 00" or "at most three 11", and then build the intersection.

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


# Question
Title: Why is there more frequent overflow in normalised Floating Point
I read that overflow is more frequent when we work with normalised mantissas. Why is this? Is it because when we adopt a normalised representation, our range is smaller than in a unnormalised representation?

Source: I read this in: Hwang, K. Computer arithmetic. John Wiley & sons, 1979. Chapter 10 "Advanced topics on floating-point arithmetic (page 323)" It says this:

> The operands are not required to be normalized, overflow may be expected to occur less frequently in unnormalized arithmetic.

# Answer
> 1 votes
**In a nutshell:** *Normalized binary floating point requires the mantissa to start with digit $1$. When there is an underflow on the exponent, the computation may be saved, at the expense of precision, by allowing the mantissa to start with some leading $0$ in what is called subnormal or denormalized numbers.*

It is always a bit chancy to guess the intended meaning of a statement without enough context.

I am not sure either of what you means by

> when we adopt a normalised representation, our range is smaller than in a unnormalised representation.

With these disclaimers, here is my understanding.

A first point to note is that the meaning of qualifier **normalized** depends on context. In scientific notation, wich is close to floating point, it means that the mantissa is represented with a single non-zero digit before the decimal point, for example $2.718\times 10^{24}$.

The definition is different in the IEEE standards for floating points. They specify the number of digits used for the mantissa, with no leading $0$, and with no decimal point (implying it is immediately right of the last digit which can be $0$).

One characteristic of normalized binary representation is that the mantissa (called "significand"or "coefficient" in the IEEE standard). always start with a digit $1$. This gives optimal precision with the mantissa (though the ending $0$'s may not be significant), and can save one bit, since a leading $1$ that is always present does not need to be represented.

However the is a provision for representing **subnormal numbers** (also called **denormal** or **denormalized**) which, as the names indicates, are not normalized.

When there is a need to represent a number such that it requires an exponent smaller than the possible minimum, the normalized computation will cause an underflow exception, which is one of several possible exceptions.

However, this can be recovered, as smaller values (subnormal numbers) can be represented in denormalized format. This requires various tricks as the leading digits of the mantissa can now be $0$ rather than an implicit $1$. Skipping the details, what this amounts to is that underflow can be overcome, to some extent, by using subnormal numbers that have less precision than the normal ones.

Thus if the computation has provision for using subnormal numbers, it is less likely to be aborted by an underflow. But then one should watch for the precision which may not be as good as normally expected.

# Answer
> 1 votes
When you work with normalised mantissas, you should normalised the result of an operation if it is in unnormalised form. This extra step could lead that you cannot represent your number because of an overflow. However if you were working with unnormalised mantissas, the preliminar result you get in the normalised operation is the answer. So you don't need to make the additional step that could make an overflow.

---
Tags: arithmetic, floating-point, normal-forms, number-formats, real-numbers
---


# Question
Title: Turing machine that accepts when a string of x's is followed by the same number of y's
I need to draw a machine's states that accepts (writes a 1) when it reads a string of x's that is followed by the same number of y's and would reject (writes a 0) for anything else. It has to work for all possible input tapes. For example, it would accept xxxyyy but would reject xxyyy and xx. I cannot figure out how to keep track of the number of x's that are read in, and then count the y's that follow without creating an infinite chain. This is what I have come up with for the Turing Machine:

start: State 0, read: x, next: State 1, write: 0, move: right; start: State 1, read: y, next: halt, write: 1, move: neutral

# Answer
> 0 votes
A Turing Machine to accept the language $L = \\{x^n y^n | n \> 0\\}$

```
On input string w
    while there are unmarked x's, do:
         Mark the left most x
         Scan right till the leftmost unmarked y
         if there is no such y then crash
    Mark the leftmost y
done
Check to see that there are no unmarked y's;
    if there are then crash
accept

```

There may be other ways. Better refer to any standard textbook as this problem is quite common.

Edit: The Turing Machine will have the following description.

$Q=\\{q\_0,q\_1,q\_2,q\_3,q\_4\\}$,

$F=\\{q\_4\\}$,

$\sum=\\{x,y\\}$,

$\tau=\\{x,y,1,0,\square\\}$

where all symbols have their usual meanings. Work out the details on your own.

---
Tags: turing-machines
---


# Question
Title: What are the conditions that make the A* algorithm optimal over the other unidirectional search algorithms
I was wondering as what are the specific conditions which make the A\* algorithm - optimal in terms of the node expansion over the other Unidirectional algorithms:

When the same heuristic information is given to all the algorithms.

# Answer
This is a nice question! Indeed, A\* is known to be *asymptotically optimal* in the number of expansions. This is usually understood by saying that any algorithm solving the same problem should expand the same set of nodes at least. A unique property of A\* with regard to its asymptotical behaviour is that, in addition, it never re-expands any nodes ---in contraposition with other algorithms such as IDA\* and RBFS.

But first things first. Before addressing why A\* is asymptotically optimal let me note in passing that A\* is a suitable algorithm not only for the shortest path problem but those problems that actually verify the suboptimal structure, this is, that all the subpaths in the solution are solutions also between their respective start and end nodes. Additionally, A\* is asymptotically optimal not only with regard to evaluation functions $f()$ which are scalar values but, in general, with any that verify the so called *cost algebras*.

In the following I address the question by mentioning the two contributions of A\* that address its asymptotically optimal behaviour and also the role played by the heuristic function $h(n)$.

From the preceding paragraph, the first condition is that $f()$ should be *non decreasing*, i.e., $f(n) \leq f(n')$ where $n'$ is a descendant of $n$. This property is exploited by Raphael, Hart and Nilsson (the authors of A\*) to create a CLOSED list that stores all nodes that have been previously expanded: if a node which is about to be expanded is found in CLOSED, then it is not expanded again even if its $f$-value is larger. The reason is simple: If that node was already expanded, a shortest path cannot go through a more expansive subpath (hope you see here how the principle of suboptimal structure applies). The second contribution of A\* is that all newly generated nodes are inserted in an OPEN list and they are sorted in increasing order of their $f$-value. This guarantees that no node with a $f$-value strictly larger than the cost of the optimal solution is ever expanded.

In general, both conditions are also satisfied by Dijkstra's algorithm and, from here, by any of the so called *Best-first search algorithms*. A\* is different from those however in the design of the $f$ evaluation function which is defined as $f(n)=g(n)+h(n)$. Now, if $h(n)$ is admissible, i.e., it never overestimates the effort to reach the goal then it is non-decreasing and, from here, optimality of the solutions found can be guaranteed.

Note, however, that some nodes with a $f$-value equal to the optimal cost might be expanded by A\* whereas they are not needed at all. Some works, such as EPEA tried to address this issue with the design of specific operator tables.

Hope this helps,
> 1 votes

---
Tags: algorithms, algorithm-analysis, search-algorithms, shortest-path
---


# Question
Title: How to find a symmetric predecessor / successor
Lets say we have a binary tree $T$ and we want to insert key $k$. Now, assuming $k\not\in T$, how do we find the symmetric predecessor/successor of $k$?

Does this relate to (pre/in/post)-order traversals in some way?

# Answer
The symmetric predecessor corresponds to the predecessor in an in-order traversal. So for a key $k$ we may find it's predecessor in two ways:

1. Find the place where $k$ would be inserted and perform an in-order traversal backwards from there on. For the details check this algorithm here which describes the dual problem of finding a symmetric successor: https://www.youtube.com/watch?v=5cPbNCrdotA
2. Call a modified version of floor, which finds the largest value strictly smaller than $k$ in the tree.

Here's how floor and ceil can be implemented: "Floor and ceiling. If a given key key is less than the key at the root of a BST, then the floor of key (the largest key in the BST less than or equal to key) must be in the left subtree. If key is greater than the key at the root, then the floor of key could be in the right subtree, but only if there is a key smaller than or equal to key in the right subtree; if not (or if key is equal to the key at the root) then the key at the root is the floor of key. Finding the ceiling is similar, interchanging right and left."

For further details refer to: http://algs4.cs.princeton.edu/32bst/
> 2 votes

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


# Question
Title: Clique decision problem restricted to a subgraph
I know that the clique problem is NP-complete.

However, what if we change the problem a little bit?

For example,

Given a graph $G(V,E)$, an integer $k$ and a subset $S$ of $m$ vertices, we are given a decision problem to find a clique with size $k$ contained within $S$.

A real world example would be something like a social networking graph. Where each node is a person and an edge represents that they are friends with each other. Now what if we were to find clique with size $k$ amongst the set of teenagers.

Does that change the complexity? Since we are only looking into a subgraph, e.g. less vertices to look for?

Thanks!

# Answer
Formally, time complexity is defined as

> Let T : N → N. A Turing Machine M has time complexity T(n) if $∀ x ∈ \\{0, 1\\}^\*$ , M(x) halts in at most T(|x|) steps.

That is to say, time complexity captures the (relative) amount of time taken for all inputs.

Thus the answer is no, that doesn't change the time complexity at all, because then you would just have an instance of the question: Given a graph $G(V',E)$, where $|V'| = m$, and an integer, $k$, determine if a clique with size $k$ exists.

As $m$ increases, the running time would increase in the way similar to how it would if |V| increases in the original problem.

However, if $m$ is defined to be a constant, then the time-complexity would be $O(1)$ (the TM would halt in at most x steps no matter what the graph is) but the problem itself would not make any sense

> Given a graph G(V,E), and k-integer, determine if a clique with size k exists after checking m vertices, where m is a constant.

because a decision problem is formally defined in terms of set-membership, and a different algorithm (a different way to finding if a clique exists) would yield a different result, for $|V| \> m$.
> 3 votes

---
Tags: complexity-theory, np-complete, decision-problem
---


# Question
Title: The meaning of discount factor on reinforcement learning
After reading of the google deepmind achievements on Atari's games, I am trying to understand the q-learning and q-networks, but I am little bit confused. The confusion arise in the concept of the discount factor. Brief summary of what I understand. A deep convolutional neural network is used to estimate the value of the optimal expected value of an action. The network has to minimize the loss function $$ L\_i=\mathbb{E}\_{s,a,r}\left\[(\mathbb{E}\_{s'}\left\[y|s,a\right\]-Q(s,a;\theta\_i))^2\right\] $$ where $\mathbb{E}\_{s'}\left\[y|s,a\right\]$ is $$ \mathbb{E}\left\[r+\gamma max\_{a'} Q(s',a';\theta^-\_i)\right|s,a\] $$ Where $Q$ is a cumulative score value and $r$ is the score value for the action chosen. $s,a$ and $s',a'$ are respectively the state and the action chosen at the time $t$ and the state and the action at the time $t'$. The $\theta^-\_i$ are the weights of the network at the previous iteration. The $\gamma$ is a discount factor that takes into account the temporal difference of the score values. The $i$ subscript is the temporal step. The problem here is to understand why $\gamma$ does not depend on $\theta$.

From the mathematical point of view, $\gamma$ is the discount factor and represents the likelihood of reaching the state $s'$ from the state $s$.

I guess that the network actually learns to rescale the $Q$ according to the true value of $\gamma$, so why not let $\gamma=1$?

# Answer
The discount factor **does not** represent the likelihood of reaching the state $s′ $from the state $s$. That would be $p(s'|s,a)$, which is not used in Q-Learning, since it is model-free (only model-based reinforcement learning methods use those transition probabilities). The discount factor $γ$ is a hyperparameter tuned by the user which represents how much future events lose their value according to how far away in time they are. In the referred formula, you are saying that the value $y$ for your current state $s$ is the instantaneous reward for this state plus what you expect to receive in the future starting from $s$. But that future term must be discounted, because future rewards may not (if $γ \< 1$) have the same value as receiving a reward right now (just like we prefer to receive \\$100 now instead of \\$100 tomorrow). It is up to you to choose how much you want to depreciate your future rewards (it is problem-dependent). A discount factor of 0 would mean that you only care about immediate rewards. The higher your discount factor, the farther your rewards will propagate through time.

I suggest that you read the Sutton & Barto book before trying Deep-Q in order to learn pure Reinforcement Learning outside the context of neural networks, which may be confusing you.
> 6 votes

---
Tags: artificial-intelligence, neural-networks, reinforcement-learning
---


# Question
Title: Fastest nth root algorithm to a lot of digits?
What is that fastest algorithm that can calculate a lot of digits of a decimal root? For example: 10,000 digits of the 3.56th root of 60.1?

# Answer
An iterative method may be as follows:

$x\_2=\frac{x\_1(n-1)+\frac{x}{x\_1^{n-1}}}{n}$

where $n$ is the root desired, $x\_1$ is a guess of the root of $x$ and $x\_2$ is a better guess.

*The iterative method is given in the book The Art of Programming Embedded Systems by Jack G. Ganssle.*
> 1 votes

---
Tags: algorithms, mathematical-programming
---


# Question
Title: For AVL Trees why is keeping a trit (left heavy, right heavy or balanced) sufficient?
I was listening to Eric Demaine's video lecture on AVL trees and there was a claim that comes up that keeping a trit on each node (to indicate whether the node is left heavy, right heavy or balanced) should be sufficient for all AVL tree operations, so essentially we don't need to keep heights of the node for every node. Can anyone prove to me why that would be the case?

# Answer
> 1 votes
In an AVL tree we aim to make the binary tree height balanced. Say the left subtree of a node has a height of $m$ and the right subtree has a height of $n$. The node therefore has a balance of $b=m-n$. We rotate the tree to restore it's balance if the balance of any node, $|b|\>1$.

So the value of $b$ is either $-1,0, or 1$. Hence storing the balance of each node in a trit becomes much easier than say storing the height of each node, because all we need to do is check the balance.

Also storing the height of the subtree of each node would be a problem. You could not understand if your node is either left-heavy or right-heavy or balanced because all you have is the height of the lowest level leaf. So storing the height of each node will not serve any purpose and seems to be counterproductive.

# Answer
> 2 votes
The core argument is that the balance can never change by more than one when inserting or deleting a single key; of course, since *heights* can only change by at most one.

That way, knowing the old balance (which is in $\\{-1,0,1\\}$) and if (and how) subtree heights changed is enough to know the new balance (which is in $\\{-2,1,0,1,2\\}$). If the balance is $-2$ or $2$ we rotate, of course, and restore balance (in that node).

In order to prove this, simply write out all possible cases of old balances and changes due to insertion or deletion.

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