# Question
Title: Floating Point Systems - Rounding Error in Taylor series
I have a question about rounding error. I have created a function to approximate exp(x) by summing the terms of its taylor series until the sum stops changing. (That is, 1 + x + x^2/2! ...).

This function works well for seemingly any positive value of x that i have tried, but when i try for instance -30, it does not give me anything even close to what exp(-30) gives me.

I am aware of how to solve this problem, but I'm more curious as to why this happens. Does it have something to do with the alternating + and - signs when summing the series? Thank you.

# Answer
Yes, that's exactly why: it's due to floating-point roundoff error, due to the alternating signs.

Suppose you have $x=10^{100}$ and $y=10^{100}-1$, and you ask your computer to subtract $x-y$. We know what the correct answer should be: it should be $1$. However, when $x$ and $y$ are represented as floating-point numbers, you don't get $1$ as the answer. Floating-point representation is not exact for large numbers, so $10^{100}$ will get rounded off to the nearest number that *can* be represented in the floating-point representation. As a result, $x$ won't be exactly $10^{100}$; it'll be a bit larger or a bit smaller -- and while the relative error will be very small ($\< 0.1\\%$), the absolute error might be very large ($x$ might be $10^{100}+\delta$ where $\delta$ is in the billions or much larger). The same is true for $y$. Thus, when you subtract $x-y$, the result won't be exactly $1$; it could be off by an absolute error of billions or much more. As a result, computing $x-y$ in floating-point arithmetic will give you answer that is wildly wrong.

In contrast, if you compute $x+y$ where $x=10^{100}$ and $y=10^{100}-1$, the answer will be reasonable. It won't be exactly correct, but it will be very close to correct.

To put it another way: suppose you compute $x+y$ and $x-y$ where $x \approx y$ and $x,y$ are very large. Then $x+y$ will be reasonably accurate, but $x-y$ will be wildly inaccurate. In particular, suppose that the closest representable floating-point number to $x$ is $\tilde{x}$, and the closest representable floating-point number to $y$ is $\tilde{y}$. We know that floating-point arithmetic has small relative error, so $\tilde{x} = x \times (1+\epsilon\_x)$ where $\epsilon\_x$ is small (say, $|\epsilon\_x| \le 2^{-20}$), and $\tilde{y} = y \times (1+\epsilon\_y)$ where $\epsilon\_y$ is small. Now

$$\tilde{x} - \tilde{y} = x - y + x \epsilon\_x - y \epsilon\_y \approx x-y + x \times (\epsilon\_x - \epsilon\_y),$$

so the absolute error could be as large as $x \times (\epsilon\_x- \epsilon-y)$. We know that $\epsilon\_x - \epsilon\_y$ will be no bigger than $2^{-19}$ or so, but if $x \approx 10^{100}$, their product will be enormous: the absolute error could be as large as $10^{100} \times 2^{-19}$, which is enormous. Since the correct answer is $x-y \approx 0$, the relative error will also be enormous.

In contrast,

$$\tilde{x} + \tilde{y} = x+y x \epsilon\_x + y \epsilon\_y \approx x+y + x \times (\epsilon\_x + \epsilon\_y),$$

and here $x \times (\epsilon\_x + \epsilon\_y)$ might be as large as $10^{100} \times 2^{-19}$ or so, which is enormous. So, the *absolute* error in this case is also large. However, the *relative* error is small: $10^{100} \times 2^{-19}$ is quite small compared to the correct answer, $x+y \approx 2 \times 10^{100}$. In particular, the relative error will be on the order of $2^{-19}$ when computing $x+y$ using floating-point math.

So, that's why absolute signs cause problems but the same sign doesn't cause problems.

---

For further explanation, you might enjoy reading the following article, especially Section 1.4:

What Every Computer Scientist Should Know About Floating-Point Arithmetic. David Goldberg. ACM Computing Surveys, 23:1, March 1991.

---

Separately, one other thing to know about Taylor series approximations is to have a feeling for the range where they are likely to be accurate. In practice, we always truncate the Taylor series after a finite number of terms -- the full Taylor series is infinite, so we can't sum the entire series; instead, we sum just the first $n$ terms, for some finite $n$.

If you truncate the Taylor series for some function $f(x)$ after $n$ terms, you get an approximation to $f(x)$. How good an approximation is this? There are various bounds on the error of this approximation. One bound is

$$\text{error} \le {|x-a|^{n+1} \over (n+1)!} \times \max \\{f^{(n+1)}(v) : a \le v \le x\\},$$

where we're using the first $n$ terms of the Taylor series approximation around $a$, and where we evaluate this at $x$ for some $x\ge a$. So, if you can upper-bound the value of the $n+1$-th derivative of $f(x)$, you can get a bound on how good an approximation the truncated Taylor series will be. You can read more about this at https://en.wikipedia.org/wiki/Taylor\_series#Approximation\_and\_convergence and http://norsemathology.org/wiki/index.php?title=Taylor\_Series\_as\_Approximations and https://en.wikipedia.org/wiki/Taylor%27s\_theorem#Example.

In general, when you use a Taylor series approximation centered around $a$, you usually want to choose $a$ to be near $x$: the closer it is to $x$, the more accurate the approximation will be. Also, the more terms in your sum, the more accurate the approximation will be.

Once you have an upper-bound for the quality of the Taylor series approximation, you can now figure out how many terms you need to sum. Note that this analysis assumes infinite-precision numbers and ignores the issues due to floating-point round-off. So, to get an accurate answer, you need to ensure two things: (a) pick a Taylor series approximation with enough accuracy that it would give a good answer if you used infinite-precision numbers, and (b) you need to account for round-off error, to ensure that when you do the calculation with floating-point numbers you get a result that is close enough to what you would have gotten with infinite-precision math.
> 4 votes

# Answer
The Taylor series for the exponential function converges (mathematically) for any input value to the correct result. The problem is that with this particular series, the terms that you add will be *huge* compared to the final result. Rounding errors for addition are roughly proportional to the magnitude of each the result, so adding the Taylor series even for slightly negative arguments like -2 or -3 is less precise than you would want in this case, and for an argument like -30 you will be adding *huge* values and the rounding error will be larger than the actual result.

So you want to avoid the Taylor series as a method to evaluate a function if the individual terms are large compared to the result (exp (+100) for example is no problem there; the individual terms will be huge, but so is the result; the rounding error will be large, but not large compared to the result). In the case of exp (), trivially exp (-x) = 1.0 / exp (x), so the problem is easily avoided.

You will also notice that when the Taylor series *is* useful, the first terms or middle terms are usually large compared to the last terms that you add (because the Taylor series converges). Since each addition gives rounding errors proportional to the result of that addition, you should add the values starting with the smallest ones and add the largest ones last. Or not add the terms at all, but use the Horner scheme which does this automatically.
> 2 votes

---
Tags: arithmetic, floating-point, numerical-algorithms, error-estimation
---


# Question
Title: How can I compare two different neural networks, from a theorical point of view?
Let's say I have a problem (i.e. Given f(x), find x) and two neural networks(i.e. feedforward and recurrent). I would like to know if one works better than the other one. I could run the twos on a computer, but other programs might interfere and I wouldn't know if the implementations I'm running are really the best ones humankind could create. Moreover, how could I be sure that the feedforward network worked better than the recurrent, when it might have just been "lucky"?

So, here is the question: can I compare the efficiency of two neural networks(with known sizes, structures and functions) from a theorical point of view? And if the answer is yes, how?

Thank you in advance.

# Answer
> 4 votes
Essentially, no. The only way to know which neural network is going to give you better accuracy is to try them on a realistic data set. The theory we have is not well-enough developed to allow us to reliably predict which will do better on a particular data set.

---

A secondary remark. When you remark "other programs might interfere", that's not correct. Even if other programs are running (on a multi-tasking machine), they won't affect the accuracy. They might take the process of running or training the neural network on your data set take longer, but they won't affect the results.

# Answer
> 1 votes
I don't know if it is relevant to answer question after 1 year of being open, but here is my thought on the topic.

In order to avoid the "being lucky", I would advise to run the network on different parts of the data set.

I don't know if you already to this, but in order to improve your network, you start to divide your data in the training data (lets say 80% of the data) and the rest is your validation data.

The network will train itself on the training data, but since it is possible that overfitting occurs, you will have to check your network on the validation data and when this error is the lowest, you have with high probability the best network. Now, since this 80% of the data is random, do this multiple times for different sets and measure the calculation time for each of them. This might give you an averaged performance and thus a correcter conclusion.

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


# Question
Title: Is it possible to get information from websites as a human?
If I want to read any websites and get some information as names (or dates) on some part of the site as a human. What solution I could use in order to get these datas using deep learning or machine learning?. Is it possible?.. it is not necessary artificial inteligence? .... or maybe it might be as a part of a Phd thesis about machine learning?... If someone has a PAPER about it, could you share it with me?.

Sorry I dont know a lot about this topic.

# Answer
The comments by David and D.W. are accurate. Your question is way too broad. But to give you a hint were you might start to dive deeper into the field, here is a very general answer to your question:

Yes, it is possible. Although, the methods we have are at the moment not as good as human performance (not surprisingly—the task is very hard; side note: If you restrict the text genre and the kind of information you are looking for strongly enough (say gene interactions in biomedical texts) then it is actually possible to achieve near-expert performance).

The name of the task you are describing is information extraction.

An excellent text book which covers elementary methods of it (as well as lots of basics in natural language processing you need to know for that) is this one. There should be free pdf version around in the web as well.
> 0 votes

---
Tags: machine-learning, artificial-intelligence, natural-language-processing, research
---


# Question
Title: How to extract parent, child and grandchild from a treeview fomatted string?
I have a long string that contains data formatted in the following way:

```
var str = "parent /n /t child /n /t child /n /t /t grandchild /n parent";

```

If you print this out you get a tree structure like directories. I am trying to figure out a way/algorithm to individually extract every parent and child and children of the aforementioned and store them in an array for each of them so that I can access them later for other useful purposes. I was thinking of using a regular expression to extract the substrings since there is some sort of pattern but I am not an expert in that field and do not know if it is worth the time. Any other ways to approach this problem or is this the best way?

Notes:

A child is always preceded with \n\t

A child's child "" "" "" \n\t\t (possibly spaces between the literals)

If the string is searched the substrings that have been searched should be stored somehow for compiling the node later.

# Answer
Don't use regexes. A tree is a recursively defined structure, and regexes don't do recursion (they can't match nested parens for the exact same reason).

You can easily build a tree structure by using a LIFO stack of nodes and maintaining an integer `currentDepth`, initially 0. For each line, pop `nTabsAtStartOfLine - currentDepth - 1` nodes off the stack, create a new node, make it the child of the current top-of-stack, push it on the stack, and set `currentDepth = nTabsAtStartOfLine`.
> 1 votes

---
Tags: algorithms, search-algorithms, substrings
---


title: Deleting edges from complete graph

text:
# Question
Title: Deleting edges from complete graph
I have a complete undirected graph with $V$ vertices and $\frac{V(V - 1)}{2}$ edges. Then, I remove $K$ edges $(a\_i, b\_i)$. I want to know if the graph is still connected after performing all the operations (so I want to delete those edges and then answer the question). Is there any faster way to do this than performing BFS/DFS algorithm? Those are linear time algorithms but in terms of edges which may be quite big to compute on a home PC for graphs with approximately $10^6$ vertices. $K$ of course will not be too big, let's say up to $10^6$.

# Answer
To disconnect a complet graph $G=(V,E)$ into $V\_1,V\_2$ you have to remove at least $|V\_1|\*|V\_2|$ edges (all the edges between elements of $V\_1$ and elements of $V\_2$).

Thus if $K\<m\*(|V|-m)$ you are sure that either the resulting graph is connected or there is a set of vertices $V\_1$ such that $|V\_1|\<m$ which is disconnected.

Hence to check if your graph is connected you only need to check whether each vertex is connected to at least $m$ vertices. Thus you have to check only $m\*|V|$ edges, which is better than BFS depending on $m$ (hence on $|K|$)
> 2 votes

# Answer
What you are looking for is called connected component labelling or connected component analysis. Withou any additional assumption on the graph, BFS or DFS might be best possible, as their running time is linear in the encoding size of the graph, namely `O(m+n)` where `m` is the number of edges and `n` is the number of vertices. That being said, if the number `k` is sufficiently small (namely smaller than the edge connectivity of the input), the graph still is connected after the edge removal.
> 1 votes

---
Tags: algorithms, graphs, lower-bounds
---


title: Is A mapping reducible to B if B = A?

text:
# Question
Title: Is A mapping reducible to B if B = A?
Is A mapping reducible to B if B = A?

Let's say A is undecidable but Turing-recognizable and also Turing reducible to its complement.

# Answer
To say that $A\le\_M B$ is to say that there is a function $f:\Sigma\_A^\*\rightarrow \Sigma\_B^\*$ such that $x\in A\Longleftrightarrow f(x)\in B$. If we have $A=B$, then the identity map will certainly fill the bill, so the answer is "yes".
> 2 votes

---
Tags: computability, reductions
---


# Question
Title: How to efficiently determine whether a relation is total?
I have a set $S$ of pairs $(x\_1,x\_2)$ with $x\_1,x\_2 \in X$ for some set $X$.

I want to know whether this defines a total relation on $X$. In other words, whether:

* If $(a,b)$ in $S$ and $(b,c)$ in $S$, then $(a,c)$ in $S$. (*transitivity*)
* Exactly one of $(a,b)$ and $(b,a)$ is in $S$ unless $a=b$, in which case they are both an element of $S$. (*totality* and *antisymmetry*)

Brute-force would take $O(|X|^3|S|)$ steps (I think), because there are $|X|^3$ triples $(a,b,c)$ and looking up whether something is an element of an array costs $O(|S|)$.

# Answer
A good first step is to construct a certain matrix corresponding to your relation, which I will let you figure out. Constructing this matrix takes time $O(|X|^2 + |S|)$ (or just $O(|S|)$, depending on your exact model). Given this, you can check antisymmetry in time $O(|X|^2)$, and transitivity in time $O(|X|^3)$.

You can improve the running time of transitivity checking to $O(|X|^\omega)$, where $\omega$ is the matrix multiplication constant; I'll let you figure out how.
> 4 votes

# Answer
If $S$ is a total (order) relation, then $|S|=|X|(|X|+1)/2$. If you start by checking that $S$ has at least size $|X|(|X|+1)/2$, then you don't really lose anything by constructing a matrix corresponding to your relation as Yuval suggested. Checking antisymmetry (and reflexivity) is no issue either. You can then try to sort $X$ according to $S$ as represented by the matrix with a suitable well behaved sorting algorithm (for example the $n \log n$ algorithms merge sort or heap sort would work). We can check in time $O(|X|^2)$ whether the result is sorted. If that algorithm succeeded in sorting $X$, then $S$ is a total (order) relation, otherwise it is not. The total runtime is $O(|S|)$ if $|S|\<|X|(|X|+1)/2$ and $O(|X| \log |X| + |S|+|X|^2) = O(|S|)$ otherwise. This is optimal, if $S$ is given as a list. (On the other hand, if $S$ is given as the transitive closure of a given DAG, then it is sometimes possible to do this faster.)
> 0 votes

---
Tags: algorithms, partial-order
---


# Question
Title: Relation between Lattice and Boolean Algebra
In discrete math, I have read that lattice is a generalized form of boolean lattice. But those places where boolean algebra is mentioned, they don't tell about lattices (digital logic, binary,...). Whether the **meet** and **join** is same as **and** and **or** in *boolean logic*? If we are thinking in terms of lattices how you define **1 and 0 = 0**? We consider only a two element lattice?

# Answer
I would hardly describe a lattice as a generalized form of boolean algebra, since there are *many* more things that a lattice can describe.

A better description would be to say that boolean algebra forms an extremely simple lattice. It has two elements, $\top$ and $\bot$, with $\bot \sqsubset \top$. The meet corresponds to conjunction (AND), and the join corresponds to disjunction (OR), though you can make a dual lattice with these flipped.

But, we don't teach this with boolean algebra for the same reason we don't teach group theory when teaching children about the whole numbers.

Lattice theory is *way* more than you need to understand booleans, and while it's a neat fact that booleans form a simple lattice, the mechanics of lattice theory, fixpoints, continuity, etc. were made to solve much harder problems than arise with booleans.
> 4 votes

---
Tags: discrete-mathematics, boolean-algebra, lattices
---


# Question
Title: Dynamic programming: how to solve a problem with multiple constraints?
I've got a real-world issue that I'm trying to come up with a dynamic programming algorithm to solve. It's similar in appearance to the knapsack problem, but it has more constraints, which has got me stumped. A simplified version of the problem:

Suppose I need to fill a basket with an arbitrary number of items c. The items have four properties: w, x, y, and z, each of which has a positive or negative number, with z being equal to the mean of the other three properties. My goal is to pick items such that the average z of my c items is at a maximum, but also

min(avg(w), avg(x), avg(y)) \> d

for some arbitrary value d.

So, for example, c items each with w, x, and y (respectively) of (1000, 1000, -1), would have a very high average z (666.3), but would fail the second constraint if we set d \>= 0, as the average y is -1.

The input would be the set of items from which to choose and the values of c and d, and the output would be a list of the c items I need to select to make the optimum full basket. Note that an item can only be selected once (no duplicates).

As I mentioned, I can see an obvious similarity to the knapsack problem, but I'm having trouble wrapping my mind around how to modify its basic structure to account for these different constraints. Or perhaps I am barking up the wrong tree trying to use the knapsack problem as a model?

Any input/pseudocode would be appreciated!

# Answer
The practical solution is to formulate this as an instance of **integer linear programming** and apply an ILP solver. There will be a clean formulation as ILP, and it might work pretty well. For each item, you have an associated variable $v\_i$ that is zero or one according to whether item $i$ is included in the basket or not (one means that it *is* included); then every one of your requirements can be expressed as a linear inequality on the $v\_i$'s.

For example, the requirement that you have exactly $c$ items in the basket corresponds to the linear equality

$$v\_1 + v\_2 + \dots + v\_n = c.$$

The requirement that min(avg(w), avg(x), avg(y)) \> d is equivalent to the requirements that the sum of the $w$-fields is at least $c \times d$, and the sum of the $x$-fields is at least $c \times d$, and the sum of the $y$-fields is at least $c \times d$. The former can be expressed as

$$w\_1 \cdot v\_1 + w\_2 \cdot v\_2 + \dots + w\_n \cdot v\_n \> c \times d,$$

where $w\_i$ is the value of the $w$-field for the $i$th possible item. Note that $w\_1,\dots,w\_n,c,d$ are all constants (known from the problem statement), and $v\_1,\dots,v\_n$ are the variables, so this is a linear inequality. Similarly for the sum of the $x$-fields and $y$-fields.

Finally, the goal of maximizing the average of the $z$-fields is equivalent to maximizing the sum of the $z$-fields of the selected items. This corresponds to maximizing the following (linear) objective function:

$$z\_1 \cdot v\_1 + \dots + z\_n \cdot v\_n.$$

All of these are linear. Finally, you can express the requirement that each $v\_i$ must be either 0 or 1 by adding linear inequalities $0 \le v\_i \le 1$ and requiring that $v\_i$ be an integer.

---

The **dynamic programming** solution involves subproblems of the following form:

* What's the maximum achievable value for the sum of $z$-fields, when restricted to choosing exactly $i$ of the first $j$ items, such that the sum of the $w$-fields is at least $\alpha$, the sum of the $x$-fields is at least $\beta$, and the sum of the $y$-fields is at least $\gamma$.

You get a subproblem for each combination of values for $i,j,\alpha,\beta,\gamma$. That's a lot of subproblems, so the dynamic programming algorithm will probably be very slow.
> 1 votes

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


# Question
Title: Two-head one way finite memory machine accepts non-regular languages
I'm having trouble proving, or understanding why a two-head one-way finite memory machine could accept a non-regular language– for instance, $(w \mid w \in (a,b)^{\*}, w= a^i b^i, i\geq 0)$.

For clarity, a two-head one-way finite memory machine works as follows – it has a finite control and a read-only input tape. The input tape contains a string, with a special blank symbol at the right end. The machine starts in the start state with both heads on the first symbol of the input string. In one step the machine reads the current symbols under the two read heads, moves one or both of the heads one position to the right, and changes state. Each step of the machine is uniquely determined by its current state and the symbols read by the two heads. (That is, the machine is deterministic.) The machine accepts the input string if it reaches an accepting state.

# Answer
> 7 votes
Just a "visual" Hint :-D

```
H1: v
    A A A B B B $
H2: ^

H1:   v
    A A A B B B $
H2: ^

H1:     v
    A A A B B B $
H2: ^

H1:       v        // found "B" ... let's
    A A A B B B $  // count both sides
H2: ^

H1:         v
    A A A B B B $  // ... go on ...
H2:   ^

H1:           v
    A A A B B B $  // ... go on ...
H2:     ^

H1:             v
    A A A B B B $  // H1 is on $, H2 on (the first) B ...
H2:       ^

```

---
Tags: automata, computation-models
---


# Question
Title: Does it matter for this function if the set we check membership of is finite?
I have the following problem.

> Let $\Phi$ be an admissible numbering of the single-parameter partially-recursive functions. That is, $\Phi(i, x) = f\_i(x)$ with $f\_i$ the $i$th partially-recusive function with one parameter. Denote with $f(x)\\!\uparrow$ that $f(x)$ is undefined in the sense that its computation does not halt.
>
> Now let $B$ be a partially computable set (finite or infinite) so that $\Phi(i,i)\\!\uparrow$ for all $i \in B$.
>
> Show that
>
> $\qquad H\_1(x) = \begin{cases}1 \text{ if } \Phi(x,x)\downarrow \\ 0 \text{ if } x \in B \\ \uparrow \text{ otherwise}\end{cases}$
>
> is partially recursive.

I know from here that there is even an infinite set. I am preparing for an exam, so just assume that they give an suitable infinite set. How would the program differ if B is a finite set like $B= \\{b\_1,b\_2,\cdots,b\_n\\}$?

Also a function obtained from composition, recursion is partially computable. So since definition by piecewise is primitive recursive , Could I say $x \in B$ is partially computable if $B$ is finite or would it be better to comeup with a program. I don't know how using just these four instructions, one could say $x \in B$ or not.

\begin{array} \\ \\;\\;\\;\\;\\;\\;\\;\\;\\;Y \gets 0 \\ \\;\\;\\;\\;\\;\\;\\;\\;\\;\text{IF } X \neq 0 \text{ GOTO } A \\ \[E\] \\;\\;\\;\text{ GOTO } E \\ \[A\]\\;\\;\\;\\; Y \gets Y+1 \end{array}

I am using the Davis book of Computability where this is mentioned in page 70 of second edition.

# Answer
> 2 votes
You can solve this problem in a straight-forward way: give an algorithm that (semi-)computes $H\_1$.

Here is a rough sketch that you have to expand into appropriate detail in the model you want to work with and then show correctness and computability.

Let $M\_B$ be a semi-decider for $B$.

1. Compute $\Phi(x,x)$ and $M\_B(x)$ simultaneously.
2. If $\Phi(x,x)$ terminates first, return $1$.
3. If $M\_B(x)$ terminates first (and accepts), return $0$.
4. Otherwise, loop.

*Hints*

* > In step 1, use dovetailing.
* > Steps 2 and 3 can not disagree.
* > Step 4 only happens when it should.

You can show the necessary lemmas using the assumptions on $B$.

As you see, we don't care at all if $B$ is finite as we do not care what $M\_B$ looks like; we just use it as a black box.

---

*Aside:* I am not sure that infinite $B$ with all the properties as listed in the question exist. We can ignore this, though: the problems is stated such that we show something for each such $B$ -- if there is none, we are good.

---
Tags: computability, semi-decidability, mu-recursion
---


# Question
Title: How does data travel in a butterfly network?
I'm trying to learn how communication works in a butterfly network.

The following is a butterfly network of order 3. I'm given the following description:

> Each processor is connected to an output switch in rank 0 and to an input switch in rank k (in this case 3). In other words the switch in column j and rank 0 gets its input message from processor j and the switch in column j and rank k delivers its message to processor j. Messages only travel in one direction - towards switches of increasing rank.

I'm having trouble interpreting what it means by the input and output switches. At first I thought the messages were traveling from bottom to top, but the last statement makes it sound like it's traveling from top to bottom. Is the processor j mentioned found on top in rank 0? I'm trying to grasp how messages travel from one processor to another.

# Answer
> 1 votes
The description you were given is indeed phrased in a confusing way. I suspect they're talking about messages travelling from top to bottom.

I suspect by "output switch" they might mean "output from the processor" (input to the butterfly network), which *is* pretty confusing. That explanation could have been phrased better.

Butterfly networks are described in many places. You might want to find another description of butterfly networks and read that.

---
Tags: graphs, parallel-computing
---


# Question
Title: What is the expansion of the regular expression $(a^*b^*)^*$
Consider the regular expression $(a^\*b^\*)^\*$

Does this mean that there are zero or more occurences of the term $(a^\*b^\*)$ before the term is expanded or that there are zero of more occurences of the term $(a^\*b^\*)$ after the term itself has been expanded?

Here is an example of what I'm try to say

zero or more occurences of $(a^\*b^\*)$ BEFORE expanding $(a^\*b^\*)$ $(a^\*b^\*)^\* = a^\*b^\*a^\*b^\*a^\*b^\* = aababbab$

or

Zero or more occurences of $(a^\*b^\*)$ AFTER expanding $(a^\*b^\*)$ $(a^\*b^\*)^\* = (aab)^\* = aabaabaab$

# Answer
Expand the outer starred expression first and *then* expand the terms. If $r$ is a regular expression, then $r^\*$ denotes the language consisting of zero or more copies of $r$, concatenated together, so $r^\*$ could take the form $\epsilon$ (the empty string, resulting from no copies of $r$) or $r$ or $rr$ or $rrr$, and so on.

In your example, with $r=a^\*b^\*$, then $r$ denotes all the strings consisting of zero or more $a$'s, followed by zero or more $b$'s, and so $(a^\*b^\*)^\*$ will denote all possible concatenations of terms $(a^\*b^\*)$. For example, one possible concatenation would be $(a^\*b^\*)(a^\*b^\*)(a^\*b^\*)$ and then after expanding each term, we might have $(abb)(aab)(bbb)=aabaabbbb$.

By choosing to expand the inner term and then concatenating the results you will likely miss the general form. If, for example, we chose a particular string in $r$ and then concatenated them, we might replace $r=a^\*b^\*$ with $abb$. Then, if we concatenated just those terms three times, we'd have $(abb)(abb)(abb)$. While this is in the language $(a^\*b^\*)^\*$, it is of a special form that doesn't capture the full generality of strings in the language.

---

While it's not directly related to the question you asked, it's worth noting that $(a^\*b^\*)^\*=(a\mid b)^\*$ (some authors would write $(a\mid b)$ as $(a\cup b)$ or $(a+ b)$). In other words, $(a^\*b^\*)^\*$ denotes the language consisting of all possible strings over $a$ and $b$. Can you see why?
> 5 votes

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


# Question
Title: Modal logic axiom S4, transitive and reflexive frame, tableaux solver
I have a difficult problem to solve which as mentioned in the title is related to **modal logic axiom S4.** So, here is some background knowledge that can be useful:

* S4 axiom is a class of transitive and reflexive frames
* S4 satisfiability problem is PSpace-Complete
* lastly solver for S4 does not terminate without a trick which will allow it to return a finite model.

Knowing all this, I have implemented a solver for propositional modal logic S4 and it also terminates with a finite model. In general solver uses Tableaux approach and generates graph in which the input formula is true. So, to outline what the algorithm does we have the following:

1. algorithm start by creating a graph with a single node with the input formula.
2. then we solve alpha, beta, gamma and delta formulas until each sub-formula is marked as being visited.
3. for termination part of the algorithm, every time a new node is about to be created (which is caused by delta formulas) we check whether the same node already exists in the graph. If yes, then we do not create a new node but we add an edge to the node that has that value.

This is enough to see what the algorithm does. What I am trying to do next is to prove that the algorithm is correct and will always work. For this purpose I will need to structure a formal proof.

**So is anyone familiar enough with the topic to suggest what technique can be used to with the proof? What should be used bisimulation or filtration?** Furthermore, it would be great if you could sketch out the proof if possible.

Any help would be very very appreciated.

# Answer
> 1 votes
To find a descriptive answer to this post, please see my thesis which presents background information of various modal logics including S4. It also contains detailed implementations of the algorithms used along with implementations in python.

I have also proved that NPSpace problems such as S4 or K4 are terminating in finite time without infinite looping. Here is the link to full report -\> Link to the pdf file located on my website. I would recommend reading it fully and following the research papers which were used to make sure full knowledge is transferred onto you :).

Please note that this was a research project which I have now finished. Nevertheless, if anyone wants to expand on my work or would like me to get involved on similiar topic, please get in touch in any way possible.

---
Tags: logic, proof-techniques, satisfiability, correctness-proof, modal-logic
---


title: Is this formula valid?

text:
# Question
Title: Is this formula valid?
is this formula valid ??, if it is not what interpretation could i use ?

(∀ x: P(x) -\> ∀ x: Q(x)) -\> ∀ x: (P(x) -\> Q(x)).

PS : i know that the other implication is valid.

# Answer
> 0 votes
I finally found a solution in a book, (Introduction to discrete mathematics 6th Edition by Elliott Mendelson page 425 ).

Assume this interpretation : the domain is N , P(x) means x is even , Q(x) means x is odd. The hypothesis is always true ( False implies False) but the Goal is always false (x even implies w odd) which is absurd.

---
Tags: logic, first-order-logic
---


title: insertion sort basic computation steps

text:
# Question
Title: insertion sort basic computation steps
Here is insertion sort:

```
for i = 1 to length(A)
    x = A[i]
    j = i - 1
    while j >= 0 and A[j] > x
        A[j+1] = A[j]
        j = j-1
    end while
    A[j+1] = x
end for

```

My lecture notes say that the total number of basic computation steps is about

$$T = 1 + ( 5 + t\_1 \times 3 ) + \dots + ( 5 + t\_{n-1} \times 3 )\\,,$$

where $t\_i$ represents how many times the inner loop needs to run (anything between $0$ and $i$). $5$ for the basic operations in the outer loop, and $1$ for testing whether to enter the outer loop.

I understand the "1" and the "5" but not the "3". Because I think $t\_i$ is not always anything between $0$ and $i$? Like say a number needs to move from position $5$ to position $1$, it repeats the inner loop meaning there will be more steps? The steps in the inner loop can possibly repeat for $n-1$ times?

So what is the basic computation steps?

# Answer
You asked why the "3" is there in that equation. Here's the explanation.

$t\_i$ counts the number of iterations of the inner loop, for a particular value of $i$. Each iteration executes 3 instructions (3 steps). Therefore, the total number steps of computations consumed by the inner loop, for a particular value of $i$, is $3 \times t\_i$.
> 1 votes

# Answer
I believe to make it easy to understand it is necessary to set it as a task. So here it is:

TASK: Insertion Sort INPUT: $a\_{1}, a\_{2},...,a\_{n} \in {\rm I\\!R}\ or\ {\rm I\\!N} $

OUTPUT: $b\_{1}, b\_{2},...,b\_{n}$ the $a\_{i}s $ in increasing order.

Insertion sort algorithm solves above task as follows. On the first iteration we have the sequence $a\_{1},...,a\_{n}.$ On the $j^{th}$ iteration we have the sequence $c\_{1},...,c\_{j},a\_{j+1},...,a\_{n}$. Note that $c\_{1},...,c\_{j}$ are the numbers $a\_{1},...,a\_{j}$ in increasing order. Trivially, on the first iteration $c\_{1}=a\_{1}$ and on the last we have sorted list of numbers.

So to construct $c\_{1},...,c\_{j},c\_{j+1},a\_{j+2},...,a\_{n}$ from the previous iteration $c\_{1},...,c\_{j},a\_{j+1},...,a\_{n}$ we do the following;

compare $a\_{j+1}$ with $c\_{j},c\_{j-1},...$ in this order and stop when its place is found. That is when $c\_{i} \< a\_{j+1} \<= c\_{i+1}$. We then insert that $a\_{j+1}$ between. When $a\_{j+1} \< c\_{j}$ then $a\_{j+1}$ becomes the first element on the next iteration, and when $a\_{j+1} \> c\_{j}$ then $c\_{j+1} = a\_{j+1}$ and there are no more comparisons required.

So to find the new place for $a\_{j+1}$ and to complete the $j^{th}$ iteration it takes at most j comparisons. So the total number of iterations is at most $ \sum^{n-1}\_{j=1}j = n(n-1)/2 = O(n^2).$ Thus we end up with a conclusion that the complexity of the Insertion sort algorithm is $T(n) = n(n-1)/2$.

Hopefully this will help you understand the pseudo code above a bit better. I know from my experience as a Computer Scientist that these can be unclear at the start.
> 0 votes

---
Tags: algorithm-analysis
---


# Question
Title: Counting an integer's divisors without just enumerating them (or estimating if not possible)?
I'm trying to count the number of divisors an integer $n$ has. **The simple way** to do this is to just enumerate all integers from 1 to $\sqrt{n}$, and count how many integers evenly divide $n$.

**For example**, 28 has six divisors (1, 2, 4, 7, 14, 28). 15 has four (1, 3, 5, 15). I want to, say, figure out how many divisors 242134575355654335549798955848371716626563756785 has.

I'm **not trying to factor** the integer; I don't care about what two numbers or what three numbers and so on I can multiply to get $n$.

**How can I count (or estimate, if need be) the number of divisors an integer has other than by enumerating them?** I don't need the actual values for each divisor; I just want to count them faster than by just enumerating them. **If that's not possible**, I'd be OK with **estimating** the number of divisors (and, even better, **using that estimate** to help me find the **actual number** of divisors).

# Answer
As far as I know we don't know a smart method of distinguishing between numbers which have $a$ divisors and numbers which have $b$ divisors, unless (say) $a$ is prime (in which case necessarily the number is an $(a-1)$th power of a prime, and we can use root extraction and primality testing). On the other hand, if you factor $n = \prod\_i p\_i^{d\_i}$ then you can compute the number of factors using the formula $\prod\_i (d\_i + 1)$.
> 3 votes

# Answer
See Yuval Filmus's answer.

Thus, to count an integer's divisors, one can factor that integer into primes.

Although this question is about the number of *prime factors*, what you're
asking about will be at least as hard as that for cubefree numbers,
regardless of whether or not the prime factors are counted with multiplicity.
> 3 votes

# Answer
The fastest way for not very large integers is to factor into powers of primes. And if you for example factor x = $p^a · q^b · r^c$ for distinct primes p, q, and r, then the number of divisors of x is (a + 1) (b + 1) (c + 1).

To see why: First, if x and y have no common divisors other than 1 then the number of divisors of xy equals the number of divisors of x, times the number of divisors of y. Second, $p^a$ has (a + 1) divisors: 1, p, $p^2$, ..., $p^a$.

To find an upper bound: For example, when factoring you usually continue until you have a prime divisor candidate p, and the remaining unfactored number x is less than $p^2$, so you conclude p is prime. Instead stop factoring when x is less than $p^3$; at that point either x = 1, or x is a prime, or the square of a prime, or the product of two primes, so it has at most four divisors. Assuming it has four divisors instead of continuing to look for factors will give you an upper bound. Or you might stop when $x \< p^4$ and conclude that x has at most eight factors, if that is good enough.

Of course you can at some point use some method to either prove that x is prime or that it is composite. If $x \< p^3$ has no factors up to p and is composite then it has 4 factors unless x is an exact square.

In general, counting the number of divisors is at least as difficult as testing if a number is prime, since a number is prime iff the number of divisors is 2.
> 1 votes

# Answer
Based on the other answers, there are two plausible approaches:

* **Approach 1.** Check whether $n$ is prime or not. If it is not, factor it, then use the factorization of $n$ to compute the number of divisors of $n$. (As suggested by Yuval Filmus and Ricky Demer.)
* **Approach 2.** Check whether $n$ is prime or not. If it is not, find all prime factors that are at most $n^{1/3}$, and write $n=rs$ where all prime divisors of $r$ are at most $n^{1/3}$ and all prime factors of $s$ are larger than $n^{1/3}$. Check whether $s$ is prime or not. Use the known factorization of $r$ and the primality status of $s$ to compute the number of divisors of $n$. (As suggested by gnasher729.)

Approach 1 is asymptotically faster, as I will show below.

In particular, Approach 1 requires factoring arbitrary large numbers. According to current knowledge, the asymptotically fastest algorithm for this is the general number field sieve (GNFS). Its worst-case running time is

$$L\_n\[1/3, \sqrt\[3\]{64/9}\] = \exp((\sqrt\[3\]{64/9} + o(1)) (\ln n)^{1/3} (\ln \ln n)^{2/3}).$$

(You can check whether a number is prime or not in polynomial time, and very efficiently in practice, so the time to do that will be far smaller than the time to do everything else.)

Approach 2 requires finding all prime factors of $n$ that are at most $n^{1/3}$. This doesn't necessarily require fully factoring $n$. However, no faster algorithm is known for doing this than to fully factor $n$. According to current knowledge, the asymptotically fastest algorithm for doing this (without trying to fully factor $n$) is the elliptic curve factorization algorithm (ECM). Its worst-case running time is

$$\begin{align\*} L\_{n^{1/3}}\[1/2, \sqrt{2}\] &= \exp((\sqrt{2} + o(1)) (\ln n^{1/3})^{1/2} (\ln \ln n^{1/3})^{1/2})\\ &= \exp((\sqrt{2/3} + o(1)) (\ln n)^{1/2} (\ln \ln n)^{1/2}). \end{align\*}$$

If you compare the two expressions, you will discover that the former is asymptotically faster.

Moreover, I expect that in practice the crossover point will be at a point where $n$ is small enough that you can fully factor $n$ without too much difficulty, so in practice I expect Approach 1 is reasonable for all ranges of $n$. Therefore, I recommend Approach 1: fully factor $n$, using the best available algorithm for that, and then use its factorization to derive how many divisors it has.
> 1 votes

---
Tags: arithmetic, number-theory, integers
---


title: Least Common Non-Divisor

text:
# Question
Title: Least Common Non-Divisor
Basically, the problem is: For a set $S$ of positive numbers, find a minimal number $d$ that is not a divisor of any element of $S$, i.e. $\forall x \in S,\ d \nmid x$.

Denote $n = |S|$ and $C = \max(S) $. Consider the function $F(x) = $ the least prime number not dividing $x$. It is easy to see that $F(x) \leq \log x$. And for a set $S$, let $F(S) = $ the least prime that doesn't divide any element of $S$. We have an upper bound

$$F(S) \leq F(\operatorname{lcm}(S)) \leq F(C^n) \leq n \log C.$$

Therefore a simple brute-force algorithm, which enumerates all numbers from $1$ to $n \log C$ and checks if it doesn't divide any element of $S$, is polynomial and has time complexity $O(n^2 \log C)$.

The other way to solve the problem is to compute all factors for every element of $S$ and use them in brute-force algorithm to check if $x$ is an answer in $O(1)$ time. This algorithm has time complexity $O(n \cdot \min (\sqrt{C}, n \log C) + n \log C)$ and uses $O(n \log C)$ memory, because we don't need to compute and store factors greater than $n \log C$. For small $n$ and $C$ it performs better.

In detail, the algorithm consists of two parts:

1. Construct a set $\hat{S}$ composed of all factors of all elements of $S$, i.e. $$\forall x \in S\ \forall f \le n \cdot \log C, \ (f \mid x \rightarrow f \in \hat{S})$$ This can be done in $O(n \cdot \min (\sqrt{C}, n \log C))$ time and $O(n \log C)$ memory. (Where does this come from? For any element of $S$, we can factor it using either trial factorization with all numbers up to $\sqrt{C}$ or all primes up to $n \log C$, whichever is smaller; thus each element of $S$ can be factored in time $O(\min (\sqrt{C}, n \log C))$ time.)
2. Find minimal number $d \notin \hat{S}$. This step requires $O(|\hat{S}|) = O(n \log C)$ time, if checking whether $x \in \hat{S}$ can be done in $O(1)$ time.

I have two questions that I'm interested in:

1. Is there a faster algorithm to solve the problem?
2. For given $n$ and $C$, how can we construct a set $S$ with maximal least common non-divisor?

# Answer
It is possible to improve on your second algorithm by using better algorithms for integer factorization.

There are two algorithms for integer factorization that are relevant here:

* GNFS can factor an integer $\le C$ with running time $O(L\_C\[0.33,1.92\])$.
* ECM can find a factors $\le n \log C$ (if any exists) with running time $O(L\_{n \log C}\[0.5,1.41\])$; finding all factors will take $O(\log C / \log(n \log C))$ times as long (which is relatively small compared to the running time of ECM).

Here $L\_n\[\alpha,c\] = \exp\\{c (\log n)^\alpha (\log \log n)^{1-\alpha}\\}$.

That's a pretty horrendous-looking expression for the running time, but the important fact is that this is faster than the methods you mentioned. In particular, $L\_C\[0.33,1.92\]$ is asymptotically much smaller than $\sqrt{C}$, i.e., GNFS is much faster than trying all possible factors $\le \sqrt{C}$. Also $L\_{n \log C}\[0.5,1.41\]$ is asymptotically much smaller than $n \log C$, i.e., ECM is much faster than trying all possible factors $\le n \log C$.

So, the total running time for this method is roughly $\tilde{O}(n \min(L\_C\[0.33,1.92\], L\_{n \log C}\[0.5,1.41\]))$, and this is asymptotically better than your first method and asymptotically better than your second method. I don't know if it is possible to do even better.
> 6 votes

# Answer
The least common non-divisor may be as large as N log C, but if the N numbers are randomly distributed then the least common non-divisor is probably a lot smaller, probably a lot less than N. I'd build tables of which primes are divisors of which numbers.

For each prime number p we have an index $k\_p$ which means all numbers up to that index have been examined for divisibility by p, and we have a list of all of those numbers which were divisible by.

Then for d = 2, 3, 4, ... we try to find a number divisible by d, or show there is none. We take the largest prime factor p of d. Then we check all numbers that were divisible by p whether they are also divisible by d. If none are found, then we check further numbers with indices \> $k\_p$ for divisibility by p, updating $k\_p$ and the list of numbers divisible by p, and checking if each number is divisible by d.

To check if there is a number divisible by p, we check on average p numbers. Later if we check if there is a number divisible by 2p, there's a 50% chance that we need to check only one number (the one that is divisible by p), and a 50% chance for checking on average 2p more numbers. Finding a number divisible by 3p is quite likely fast and so on, and we never check more than N numbers for divisibilty by p, because there are only N numbers.

I would hope this works out with about $N^2 / log N$ divisibility checks.

PS. How large would the result be for random numbers?

Assume I have N random numbers. Probability that one of N numbers is divisible by d is 1 - (1 - 1/d)^N. I assume the probability that each of the numbers 1 ≤ d ≤ k is a factor of one of the random numbers is calculated by multiplying these probabilities (Ok, that's a bit dodgy, because these probabilities are likely not quite independent).

With that assumption, with N = 1000, there's a 50% chance that one of the numbers 1..244 doesn't divide any number, and one in a billion that every number up to 507 divides one of the numbers. With N = 10,000 there's a 50% chance that one of the numbers 1..1726 doesn't divide any number, and one in a billion that every number up to 2979 divides one of the numbers.

I would propose that for N random inputs, the size of the result is a bit larger than N / ln N; maybe something like N / ln N * (ln ln N)^2. Here's why:

The probability that at least one of N random numbers is divisible by a random d is $1 - (1 - 1/d)^N$. If d is around N, then $1 - (1 - 1/d)^N$ is about 1 - exp (-1) ≈ 0.6321. That's for a single divisor; chances that each of several numbers d ≈ N is a divisor of at least one of N numbers are quite slim, so the maximum d will be significantly smaller than N.

If d \<\< N, then $1 - (1 - 1/d)^N ≈ 1 - exp (-N / d)$.

If d ≈ N / ln N then $1 - exp (-N / d) ≈ 1 - exp (- ln N) = 1 - 1/N$.

We would add these probabilities for about N / ln N values d, but for most d the result will be significantly larger, so the largest d will be somehow larger than N / ln N but significantly smaller than N.

PS. Finding a number divisible by d:

We pick the largest prime factor p of d, and then we first examine the numbers that were already known to be divisible by p. Say d = kp. Then on average we only check k numbers that are divisible by p while checking this particular d, and we check at most all N values for divisibility by p overall, for all d divisible by p. Actually, we most likely check less than N values for most primes p, because after checking all N values the algorithm most likely ends. So if the result is R, then I expect less than N values being divided by each prime less than R. Assuming R ≤ N, that's about N^2 / log N checks.

PS. Running some tests

I ran this algorithm a few times with N = 1,000,000 random numbers \> 0. The least common non-divisor was between 68,000 and 128,000 with the huge majority of runs between 100,000 and 120,000. The number of divisions was between 520 million and 1800 million which is a lot less than (N / ln N)^2; the majority of cases used between 1000 and 1500 million divisions.
> 3 votes

---
Tags: algorithms, number-theory
---


# Question
Title: Why do we need epsilon-transitions in Thompson's construction?
So as learned every DFA is an NFA. I feel like I understand DFA much better than NFA, so I try to convert my regular expressions to DFA, but I want to understand both sides.

For example a|b (a Union b):

However, are we losing anything if we eliminate the epsilon from these expressions, every DFA is an NFA right so what are we losing if we don't include it?

# Answer
> 7 votes
What you're looking at there is what's known as Thompson's construction. The idea is that any node in the regular expression parse tree corresponds to an NFA with a single entry and exit point. To see why the epsilon transitions are useful, try applying the construction to, say, $(a \cup b^\*)c$.

Thompson's construction is particularly easy to understand and implement but it is also, as you rightly say, a bit wasteful. It is possible to construct Thompson's automaton with the epsilon transitions removed using Glushkov's method. You may also be interested in Xing's construction.

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


# Question
Title: Algorithm to build a "hand" calculation for riichi mahjong game
I would like to discuss an algorithm to build a "hand" calculation for riichi mahjong game.

I will simplify terms to focus on the algorithm and not on the game specific terms.

Let's imagine that we have a card deck with three suits. Each suit contains cards from 1 to 9 and each card has four copies.

So card deck looks like this:

111122223333444455556666777788889999a (a is a first suit) 111122223333444455556666777788889999b (b is a second suit) 111122223333444455556666777788889999c (c is a third suit)

Each player has 14 cards in his hand and hand should contains four sets and one pair to be able win. Set can be built from three consecutive cards (123a) or from three same cards (444a).

Input data: 14 cards.

Output data: all possible variants of 4 sets and one pair.

Examples:

Input: 123678a234678b44c

Output: \[123a 678a 234b 678b 44c\]

Input: 233445a 44556677b

Output: \[123a 345a 456b 456b 77b\], \[123a 345a 567b 567b 44b\]

Also, it can be cases with 5-10 possible variants of the hand.

I tried to build it with recursion, but I wasn't successful. The main question how to determine that we don't have remaining variants?

Thanks for your help in advance.

# Answer
> 2 votes
Pretty much any approach will be fine. The trick is to focus on generating *all* possible ways to partition the hand into groups of size 4+4+4+2, then test each candidate to see whether it is valid. If you've enumerated all possible ways in the first step, then you'll know you've found all possible variants/solutions.

Even a totally dumb, unoptimized brute-force approach will probably be fast enough: enumerate all partitions of the 14 cards into groups of size 4+4+4+2, and for each, check whether it's valid. There are

$${14 \choose 4} \times {10 \choose 4} \times {6 \times 4} /6 = 525,525$$

different such partitions. Therefore, you should be able to enumerate all partitions and for each check whether it satisfies the rules.

Of course there are likely much faster algorithms. For instance, you can enumerate all possibilities for the first card in the first "set", then enumerate all ways to complete the first "set" (usually there won't be that many, given the restrictions on a valid "set"), then enumerate all possibilities for the first card in the second "set" out of the remaining cards, then enumerate all ways to complete the second "set", and so on. In practice this will probably be even faster.

It's easy to find all variants with this kind of approach. You just test each possible partition/grouping, and output each one that is valid.

As another optimization, it's easy to figure out the suit that you must use for the "pair". Count the number of cards you have in each suit. For there to exist a valid combination, two of these numbers must be $0 \bmod 3$ and one must be $2 \bmod 3$. The latter is the suit that the pair must come from. Try all possibilities for how to choose the pair (from that set) -- there usually won't be that many possibilities, as there usually won't be many repeated cards in that suit. For each such possibility, try all ways to divide the remaining 12 cards into 3 "sets".

As another optimization, after you've chosen and removed the pair, if you have a suit that contains exactly 3 cards, you know that if there is any valid combination, those 3 cards must be placed together in a set -- you have no choice (it's forced). This further cuts down on the number of possible combinations you must examine. If there's a suit that contains exactly 6 cards, there are only ${6 \choose 3} = 20$ ways to divide it into two groups of 3; you can check each candidate division to see which ones are comprised of two valid "sets". These two cases will cover most hands. The only difficult case is where there's a single suit that contains exactly 9 or 12 cards (after removing the pair), and you can fall back to enumerating all partitions for those (rare) hands, or devise alternative strategies for handling those specific cases.

---
Tags: algorithms, graphs, recursion
---


# Question
Title: Can languages that are not closed against the Kleene star be regular?
I've been working on finding a regular expression for the following language for quite some time now ($\Sigma =\text{{0, 1}}$):

> $ \text{L = {w | the difference between the number of 0's and 1's in each prefix of the word is less than or equal to 1}}$

I haven't been able to find an expression for this particular language so far, so I was wondering if the language is regular at all.

The following came to mind, but I'm pretty dubious about its validity :

> Since $010$ belongs to said language, and by concatenation $010010$ does not, it would follow that this language isn't closed under Kleene star, hence it's not regular.

Am I wrong? If so, could you help with finding the solution to this problem?

Regarding the meaning of prefix in this context, the prefixes of the string $abcd$ are $\text{{$abcd, abc, ab, a$}}$.

# Answer
> 5 votes
No, your argument is not correct.

The "hence it's not regular" doesn't follow. Not every regular language is closed under Kleene star. Some regular languages aren't closed under Kleene star. I think you've misunderstood the closure property: the closure property states "If $L$ is regular, then $L^\*$ is regular". Note that you can still have a regular language where $L \ne L^\*$.

To learn how to solve this question correctly, you may want to check out our reference questions. See especially How to prove a language is regular?, Show whether the language with almost as many 0 as 1 in every prefix is regular, Language where every prefix has almost equal a's and b's.

# Answer
> 3 votes
The language $L'=\\{1\\}$ is not closed under the Kleene's star (e.g. $11\not\in L'$), but is regular (use a FSA with two states).

The closure property states that when $L''$ is regular, then $L''^\*$ (which is another language) must be regular as well. It does not imply $L''^\* = L''$.

For your language $L$, try writing a decider in your own favorite programming language. If it turns out that the decider's variables only assume finitely many values, you can convert that into a FSA, proving $L$ regular.

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


# Question
Title: Quadratic algorithm for Matrix Chain Multiplication
I have an algorithm that supposedly solves the matrix chain multiplication problem in $O(n^2)$ time. I have tested it only on trivial cases and they turned out to be correct.

By no means, am I a genius, but I was wondering if you guys could point out where this algorithm lacks.

The algorithm:

```
Base case:
     MCM(A) = 0;
     MCM(AB) = nrow(A) * ncol(A) * ncol(B)
Otherwise:
     MCM(AB....JK) = min(MCM(B...K) + cost_of_mul(A, B...K),
                     MCM(A...J) + cost_of_mul(A...J, K),
                     MCM(AB) + MCM(C...K) + cost_of_mul(AB, C...K),
                     MCM(A...I) + MCM(JK) + cost_of_mul(A...I, JK));

where MCM is a nxn matrix that stores the minimum number of scalar products needed for the sequence from i to j (MCM[i][j])

```

The rationale behind this is that each grouping takes care of at least two matrices, and that is being handled when considering the minimum.

# Answer
Your algorithm has lower complexity than the straightforward standard version of the dynamic programming solution, because it scans only a (strict) subset of the subproblems it needs to consider.

Say there are $n$ matrices at some point. Your algorithm checks five specific parenthetizations: between first and second, between penultimate and last, etc. It's possible that the optimal parenthetization is between the element at $\left\lfloor \frac{n}{2} \right\rfloor$ and $\left\lfloor \frac{n}{2} \right\rfloor + 1$, for example, but your algorithm doesn't check that.

It's possible that you tested it on a few test cases and it worked, because the optimal sub-solutions *might* appear in the restricted subsets which you check.

Of course, you could expand your solution to check for *all* parenthetizations. In that case, though, you'll reach the regular conclusion for the (straightforward version of the) dynamic programming solution for this problem - filling up the $n^2$ entries needed for the solution takes $\Theta\left(n^3\right)$ time.
> 1 votes

---
Tags: algorithm-analysis, runtime-analysis, dynamic-programming, matrices
---


# Question
Title: What is the error when using Levenshtein distance on flattened binary trees?
I need to calculate the edit distance between many pairs of binary trees. Unfortunately this is computationally expensive.

The trees are stored as a flattened list of indices into node and terminal lookup tables. The particular flattening structure is the pre-order encoding format (pseudo code: `flat(tree) = [id(root)] + flat(left) + flat(right)`).

If I calculate the Levenshtein distance between the flattened trees, rather than between trees:

* How big will my error be? (Difference to tree based distance)
* Would other flat structures be more accurate?

# Answer
This approximation is essentially arbitrarily bad.

Suppose you have a complete binary tree $T$ containing $2^k - 1$ nodes, of which the bottom $2^{k-1}$ are leaves. Let $u$ and $v$ be the left and right child of the root, and $U$ and $V$ be the subtrees rooted at these vertices, respectively. Let $w$ be the rightmost leaf in $U$. To transform $T$ into a tree in which the locations of the leaf $w$ and the entire subtree $V$ have been swapped (so that the new tree has height $2k-1$) requires $2^{k-1}-1$ deletions of all nodes in $V$, the deletion of $w$, followed by the same number of insertions -- but the Levenshtein distance between the corresponding strings is just 2: delete the single list element corresponding to $w$ (from just before the half-way point of the string) and append it to the end.

(Well, possibly up to 2 tree-edits can be saved by turning pairs of insertions and deletions into substitutions.)
> 1 votes

---
Tags: trees, string-metrics, edit-distance
---


# Question
Title: Parsing CFLs (simulating PDA vs CYK algorithm)
We can simulate the PDA and parse the language with the following operations (vaguely):

> 1. Read the input symbol and top of stack - $O(1)$
> 2. Check all the transition rules (must check all for non-determinism) - $O(|Transition rules|)$
> 3. Update the stack and the set of states - $O(1)$

Due to non-determinism, the problem size increases and so does the complexity.

However, for **deterministic context free languages**, the complexity of this algorithm seems to be $O(n|Transition rules|)$ which is linear.

The complexity of CYK algorithm is $O(n^3|G|)$. From various sources it seems that the complexity of CYK algorithm is polynomial for deterministic languages. http://people.csail.mit.edu/madry/docs/linear.pdf

$|Transition rules|$ has a maximum value of around $|G|$ I think.

So, is this method really better than the CYK algorithm for deterministic CFLs or am I making a mistake in my analysis? If so, then where?

I'm assuming that $|G|$ = Number of production rules in grammar.

# Answer
Wikipedia mentions that the class of deterministic context-free languages can be parsed in linear time, using an LR parser. In contrast, the fastest algorithm for parsing general context-free languages, Valiant's modification of the CYK algorithm, runs in time $O(n^\omega)$ (where $\omega$ is the matrix multiplication constant), and there is evidence due to Lee that any practical implementation of Valiant's algorithm will run in time proportional to $n^{2.43}$ at best (substitute $\epsilon = 3-2.81$ in Lee's paper; here $2.81$ is the exponent of Strassen's algorithm), and in time proportional to $n^3$ for most values of $n$ occurring in practice.

Context-free grammars used in practice tend to be deterministic, precisely because DCFLs can be parsed faster than CFLs. Indeed, even more restricted variants are commonly used (LALR languages) for reasons of efficiency.
> 5 votes

---
Tags: pushdown-automata, efficiency, parsers
---


# Question
Title: Are there any type constructors which are *not* functors?
So I'm almost done teaching myself category theory. One of the main take-aways for me is that type constructors (higher-kinded types) are endo-functors.

But it this *always* the case? What's throwing me off is Haskell's `Functor` typeclass:

```
class Functor f :: * -> * where
   fmap :: (a -> b) -> (f a -> f b)

```

If all type constructors were *a priori* functors, there would be no need to define a special type-class. But I can't think of any type-constructors that fail to satisfy the `Functor` type-class: product, sum, function, list, set, option, etc.

I also cannot imagine the utility of a type-constructors that is "one-half" of a functor, i.e. it has a map from objects to objects, but no map between morphisms.

# Answer
> 11 votes
One obvious counterexample is a binary search tree. You cannot freely substitute the values in a binary search tree because a substitution might change the ordering (relative to `Ord`), or even replace the values with a type which is not an instance of `Ord` at all.

A possibly less-obvious example is a *contravariant* endofunctor. Consider:

```
data Tricky a = Tricky (a -> String)

```

Try writing a `Functor` instance for this.

But that doesn't mean you can't construct a functor-like class which it the type does satisfy. This `Tricky` type, after all, is a contravariant functor:

```
-- Somebody has probably already implemented this in a library
-- somewhere, with a better name.
class ContraFunctor f :: * -> * where
    contramap :: (b -> a) -> (f a -> f b)

instance ContraFunctor Tricky where
    contramap f (Tricky t) = Tricky (t . f)

```

and like `fmap`, it must satisfy some axioms which are left as an exercise.

What's interesting, though, is that you can usually come up with a functor-like class (and its axioms, of course) which applies type substitutions in a principled way, from the *types* of the functions which comprise their API.

The full details are beyond the scope, but it's based on a remarkable property of a polymorphic function is known as the "free theorem". Any polymorphic function has a theorem that it satisfies simply by virtue of being polymorphic, and the theorem is mechanically derivable from its type.

What the theorem essentially states is that a polymorphic function commutes with a type substitution. This is what "polymorphic" really means.

Let's take `reverse` as an example:

```
reverse :: forall a. [a] -> [a]

```

There are no constraints whatsoever on the type of `a`, so it will commute with any type substition:

```
forall f :: A -> B. fmap f . reverse = reverse . fmap f

```

(Remember, `.` is function composition in Haskell.)

This is true for any types `A` and `B`. In a deep sense, this is what the "forall" actually means in the type of `reverse`.

Now consider `sort`:

```
sort :: forall a. Ord a => [a] -> [a]

```

The problem here is that `Ord` is a constraint on the type of `a`. What this means is that this is a constraint on any type substitution: it must be a homomorphism of `Ord`.

```
forall f :: A -> B.
    (forall x y : A, compare x y = compare (f x) (f y))
    => fmap f . sort = sort . fmap f

```

That extra precondition, that `f` is an `Ord`-homomorphism, intuitively means that `f` is a function which preserves the order. This should make sense: if a type substitution doesn't change the ordering of elements, then that type substitution commutes with `sort`.

But here's my favourite example of all. Suppose that `F` and `G` are functors. Now consider this function:

```
eta :: forall a. F a -> G a

```

The free theorem of this function is:

```
forall f : A -> B.  fmap f . eta = eta . fmap f

```

Note that the two `fmap`s are different instances; the first one is the instance for `G` and the second is the instance for `F`. What this is saying is that `eta`, *by virtue of its type alone*, is a natural transformation.

---
Tags: type-theory, category-theory, haskell
---


# Question
Title: Height and depth of every node in Path Compression
If we have an union-find(disjoint-set) data structure and we are doing an union by rank and path compression for a ***find*** operation, how would the depth and height of every node change after the ***find*** operation?

I am trying to find the amortized cost of the find operation using the potential function:

$$phi(x) = \sum\_{x} height(x) $$

I know this is not the right potential function, however, i am trying to learn more about amortized analysis and i am just practicing by analyzing more data structures.

# Answer
> 2 votes
I assume that the height of a node $\small x$, denoted as $\small h(x)$, is recursively defined as: $$ \small h(x) = \begin{cases} 0 & \text{ if $x$ is a leaf} \\ 1+\max\\{h(y) \mid y\text{ is child of } x\\} & \text{ otherwise } \end{cases} $$ Let the value of the potential function before calling $\small \texttt{Find}(x)$ be $\small \Phi$ and the value after the call be $\small \bar{\Phi}$. Similarly we can define $\small h(x)$ and $\small \bar{h}(x)$ respectively. Denote as $\small P\_x$ the path from $\small x$ to the root $\small r$ of the corresponding tree. By path compression, nodes in $\small P\_x$ (except $\small r$) are all set to point to $\small r$. Therefore, generally $\small \bar{h}(y) \leq h(y)$ for $\small y \in P\_x$, since $\small y$ may have one child removed.

The amortized cost of $\small \texttt{Find}(x)$ is: $$ \small \mathcal{O}(|P\_x|) + \bar{\Phi} - {\Phi} = \mathcal{O}(|P\_x|) + \sum\_{y \in P\_x}\\{\bar h(y) - {h}(y)\\} $$ where $\small |P\_x|$ is the # of nodes in $\small P\_x$ and $\small \mathcal{O}(|P\_x|)$ is the actual cost of $\small \texttt{Find}(x)$. Now look at term $\small \bar h(y) - {h}(y)$, by the discussion above, its value is no greater than $\small 0$. Unfortunately, there are special cases where $\small \bar h(y) = h(y)$ for all $\small y \in P\_x$. Therefore, what we can say about the amortized cost, using sum of heights as potential function, is the amortized cost is $\small \mathcal{O}(|P\_x|)$, which is the same as the worse-case bound.

---
Tags: algorithm-analysis, data-structures, amortized-analysis, union-find
---


# Question
Title: Why does Fleury's algorithm have to return to the starting node?
Recently, I am reading the Fleury's Algorithm part of the document \[1\]. There is a sentence on page 3 of this document:

> Note that, when the algorithm terminates, we must return to $v\_{start}$ because every vertex has an even degree.

I don't understand why we must return to $v\_{start}$. Could anyone please teach me?

---

1. Eulerian circuits by Ethan Kim (accessed Oct 14, 2016)

# Answer
> 3 votes
Suppose you end up at a vertex different from the start. You may have visited the vertex before, say $k$ times. Each time you visited the vertex you used up one edge to enter it and one edge to leave it. So $2k$ edges, an even number. When you enter it for the last time, you used up $2k+1$ edges, an odd number. Since the degree of all nodes is even, there must be an edge left over which you can leave the vertex and the algorithm wouldn't have stopped.

The start vertex is special because you don't need to enter it to visit it the first time (right at the start).

Note that a graph can also be eulerian if it has exactly two vertices with odd degree. Then you have to choose one of them as a start vertex and you will end up at the other odd-degree vertex at the end of the algorithm. I leave it to you to prove why this is the case.

---
Tags: algorithms, graphs
---


# Question
Title: Why multiple return values is not a common thing?
I would like to ask a question about multiple return values, why this construct is not preferrable in programming languages (conceptual and/or technical difficulties). I've heard something about stack frames and how they reserve memory for return value and variable return values could make this problematic, but if someone could explain this better, this would be much appreciated.

In conctanetative languages (like FORTH), having multiple return values from a function is a common and very useful thing, and I imagine something like this in java/c-like languages would be useful too (a very basic example):

```
x, y = multRet(5);
multret(int x) {
    return x+1;
    return x+2;
    exit;
}

```

To clarify: I am not asking how to return multiple values (this is a known question with known answers), but I want to get a clarification about why this practice is not common in programming languages.

# Answer
Functions are traditionally thought of as returning a single value - in math. Of course several values form a tuple, but oftentimes in math we are dealing with real-valued functions. I suspect that this origin of functions is the reason why multiple return values are not so common. That said, it's easy to emulate them in several ways (by returning a tuple, or by having several output parameters, i.e. ones passed by reference), and some common modern languages (such as Python) natively support this construction.
> 6 votes

# Answer
**Having multiple return values *is* preferable**. Lacking them is bad design, plain and simple. However, we should clear up the misconception that such a thing even exists in the sense you are thinking of.

In languages based on the typed lambda-calculus (the progenitor programming languages), e.g. ML-family, Haskell, a function (lambda abstraction) only accepts a single argument and "returns" (more formally, evaluates to) a single result. So how can we create a function that seems to take or return multiple values?

The answer is that we can "glue" values together by using *product types*. If *A* and *B* are both types, then the product type $A \times B$ contains all tuples of the form $(a, b)$, where $a: A$ and $b: B$.

Thus, to create a function `multiply` that multiplies two integers together, we give it the type `multiply: int * int -> int`. It accepts a *single* argument which happens to be a tuple. Likewise, a function `split` that splits a list into two would have type `split: a list -> a list * a list`.

Maybe 30 years ago implementation was a valid concern in including such a feature. According to the C calling convention *cedl* (and it is just that, a *convention* \- no god ordained it), the return value is stored in a special register, usually `EAX`. Certainly, this is extremely fast to read and write, so the idea has some merit.

But it is too limiting, as you point out, and there is no reason we need to follow this rule nowadays. For example, we could instead use the following policy: for a small number of return values, use a set of specified registers (we have more registers for use now than in the 80s). For larger data, we could return a pointer to a location in memory. I don't know what's best; I'm not a compiler writer. But the archaic C calling convention should have no influence on the semantics of modern languages.
> 6 votes

# Answer
Syntax is not necessary when simple patterns do the job better and your proposed syntax would be historically confusing to a lot of people. This means your syntax is hard to learn and will lead to problems when people switch between your language and others.

The simple pattern that solves this problem is defining a Variable named "returnValue" at the start of your method and then assign values to it. If you need multiple values, then simply use a collection of some sort and add the values instead. Then return this Variable. Problem solved.

Your syntax would mean that you would by default have to handle collections. This is frustrating for function that only return 1 value.

And what if someone does something wrong ? Eg.

```
x, y = multRet(5);
multret(int x) {
    return x+1;
    exit;
}

```

or

```
x = multRet(5);
multret(int x) {
    return x+1;
    return x+1;
    exit;
}

```

Is the compiler supposed to catch that? What if you have a loop?

At best this would be syntactic sugar. Something that doesn't add new features but instead only makes current patterns more comfortable and shorter in code.

At worst this would lead to horrible, horrible error in code. Null pointer exception in masses.
> 1 votes

# Answer
It is mostly because of syntactical reasons; in your own example the first return statement would return one value and return, and never reach the second return statement.

There are nowadays a few languages that allow returning a tuple, that is zero, one or more values of arbitrary types, packaged together to be a single value. Still, they are returning *one* value, just a slightly more complicated value. Usually such languages would also have a way to assign a tuple to zero, one or more matching variables, often with an easy way to ignore some elements of the tuple. This could look like this:

Assign tuple to another tuple:

```
x = multRet(5); // x is a variable of type tuple (int, int)
multret(int x) {
    return (x+1, x+2);
}

(x, y) = multRet(5); // x, y are variables of type int
multret(int x) {
    return (x+1, x+2);
}

(x, _) = multRet(5); // x is a variable of type int, second component ignored.
multret(int x) {
    return (x+1, x+2);
}

```

That syntax wouldn't be compatible with C, where (x, y) is a comma expression in parentheses. On the other hand, receiving two values is much easier than in C, where you either pass the two values using pointers, or you declare a struct for this purpose, fill it, and return it. Using pointers, the third example where the caller is only interested in one value is a pain, so this method of returning tuples is *very* useful.
> 1 votes

---
Tags: programming-languages, compilers
---


# Question
Title: Proving $L = \{a^iba^j|i\ge2j\ge0\}$ isn't regular
I need to prove the following language is not regular, I think I need to use the pumping lemma. The trouble I am having is that there is multiple variables and I am not used to that. Could someone tell me if the pumping lemma is the correct proof by contradiction of $$L = \\{a^iba^j|i\ge2j\ge0\\}$$

I took $xyz = a^{2p+1}ba^p $ so $|xy| = 2p+2$ which is greater than $p$ and must be false. Is this solution correct?

# Answer
As noted, you need to be careful making assertions about $xy$. Recall that the pumping lemma says that if $L$ is a regular language, then there is a positive integer $p$ such that any string $s\in L$ can be written as $s=xyz$ where

1. $|xy| \le p$,
2. $|y| \> 0$,
3. $xy^iz\in L$ for all $i=0,1,\dotsc$.

so in your example all you know is that $|xy|\le p$. You certainly can't assert that $|xy|=2p+2$.

All is not lost, though. If you assume that $L$ is regular and let $s=a^{2p}ba^p$ (notice that I chose a different string to pump), then since $|xy|\le p$, you know that $xy$ "lives" among the first group of $a$'s, and so $xy=a^k$, for some $k\le p$. Hence $y=a^t$ for some $0\<t\le p$ and so the PL assures us that $xy^iz\in L$ and we have $xy^iz=a^{2p+(i-1)t}ba^p$. \[Do you see why?\] Now all you have to do is pick some $i$ so that $xy^iz\notin L$ to establish a contradiction and thus show that $L$ isn't regular.

I'll leave the rest for you: what $i$ can you use to show that $xy^iz\notin L$?
> 0 votes

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


# Question
Title: Solve Travelling Salesman once you know the distance of the shortest possible route
I am trying to solve the `TSP (Travelling Salesman Problem)`, but not in a traditional way. I am following these steps.

> **1)** First I change the TSP to a **true / false** problem.

The definition of this problem is now: "Is there a route by all the cities with a total distance less or equals than `k`?" Let's assume I have an algorithm `TSP_tf(k)` to solve it.

> **2)** Then I search the minimum **k**.

This is, I search "which is the distance of the shortest possible route".

An efficient algorithm to solve it would be with a dichotomic search. I begin with `k=1`, and I call `TSP_tf(k)`. If it returns false, I multiply `k` by 2, and keep calling `TSP_tf` until true is returned. When this happens, search the minimum `k` that returns true in the interval `(k/2 - k]`, also with a dichotomic search.

I will get then the minimum distance `min_k`.

> **3)** Return the shortest route of the TSP knowing its distance is **min\_k**.

And here is where my question comes. How would be an efficient algorithm to solve this? By efficient I mean a good approach :) It is obvious that `TSP` will remain being NP.

# Answer
I managed to solve it finally.

Suppose we have a graph `g` which represents the cities and their conections of the `TSP`. A node represents a city and a weighted edge represents that there is a connection between both cities with the corresponding distance of its weigth.

In order to get the shortest route given its distance, let's delete one to one the edges, and see if they are part of the shortest route. How can we know it? If we delete an edge `e` from the graph and we call `TSP_tf` with the known shortest distance `min_k`, two things can happen:

* `TSP_tf(min_k) == false`. This is, deleting `e` makes not possible to obtain a route with `min_k` distance. `e` is part of the shortest route.
* `TSP_tf(min_k) == true`. Without the connection `e`, it's still possible to obtain a route with the same minimum `min_k` distance. `e` doesn't take part of the shortest route.

If we apply it progressively to all the edges of the graph, we can obtain the exact shortest route (or better said, one of the shortest routes, because there may be more than one solution).

```
// min_k is the distance of the shortest path of the TSP represented by the graph g.
Graph TSP(Graph g, int min_k)
    Graph shortestPath = g;
    For (Edge e in g)
        // Delete the edge e.
        shortestPath -= e;
        // e is part of the shortest path.
        If (TSP_tf(shortestPath, min_k) == false)
            shortestPath += e;
        EndIf
    EndFor
    Return shortestPath;
EndTSP

```

As we know, the maximum number of nodes of a graph is $1/2 * |V| * |V-1|$, being $|V|$ the number of nodes. A `TSP_tf` call is done for each node, so the number of calls to `TSP_tf` has a peak $O(|V|^2)$, being an efficient algorithm.
> 0 votes

# Answer
You try to find a tour of length ≤ K. What would likely happen: If K is very large then a tour is easy to find. If K is very small then it is easy to prove that a tour doesn't exist. The closer you move K to the critical point (where a tour of length K exists, but K-1 doesn't exist), the harder it will be to either find a tour or prove it doesn't exist. You don't beat NP-completeness that way.

And actually, since NP-completeness is about decision problems (problems with a yes/no answer), that's what the travelling salesman problem actually is: Deciding whether or not there is a tour of length K or ≤ K.
> 1 votes

---
Tags: algorithms, np, traveling-salesman
---


# Question
Title: Why contraction and weakening rules are the upside down?
On the A taste of linear logic paper, the author claims that:

> A rule consists of zero or more judgements written above a line, and one judgement written below. If all the judgements above the line are derivable, then the judgement below is derivable also.

He then proceeds to show the following rules:

He then describes those rules as:

> Contraction expresses that any hypothesis may be duplicated, and Weakening expresses that any hypothesis may be discarded.

That looks upside down. Reading the "Contraction" rule in English, we have that *"if assumptions Γ, A, A imply B, then assumptions Γ, A also imply B"* \- notice that we discarded an assumption instead of duplicating it. Similarly, the "Weakening" rule adds an assumption to the conclusion, rather than discarding one from the premises as the author seems to suggest. Why?

# Answer
Contraction is called contraction because it *contracts* the two hypotheses into one: $A, A$ is contracted into $A$. Weakening is called weakening because it allows one to deduce a weaker fact: $\Gamma \vdash B$ is stronger than $\Gamma, A \vdash B$ since fewer hypotheses are needed to obtain the conclusion. The names come from forward reasoning: deducing facts from other facts. When you're deducing new truths, you can take already-proven truths and add hypotheses or remove duplicated hypotheses.

When you look at contraction from the point of few of backward reasoning, i.e. examining why a fact might be true, then the contraction duplicates a hypothesis. Similarly the weakening rule discards a hypothesis. When you're trying to prove a goal, you can duplicate or discard hypotheses to get a new goal whose truth implies the truth of the original goal.
> 7 votes

---
Tags: logic
---


# Question
Title: How do computers remember where they store things?
When a computer stores a variable, when a program needs to get the variable's value, how does the computer know where to look in memory for that variable's value?

# Answer
> 33 votes
I'd suggest you look into the wonderful world of Compiler Construction! The answer is that it's a bit of a complicated process.

To try to give you an intuition, remember that variable names are purely there for the programmer's sake. The computer will ultimately turn everything into addresses at the end.

Local variables are (generally) stored on the stack: that is, they're part of the data structure that represents a function call. We can determine the complete list of variables that a function will (maybe) use by looking at that function, so the compiler can see how many variables it needs for this function and how much space each variable takes.

There's a little bit of magic called the stack pointer, which is a register which always stores the address of where the current stack starts.

Each variable is given a "stack offset", which is where in the stack it's stored. Then, when the program needs to access a variable `x`, the compiler replaces `x` with `STACK_POINTER + x_offset`, to get the actual physical place it's stored in memory.

Note that, this is why you get a pointer back when you use `malloc` or `new` in C or C++. You can't determine where exactly in memory a heap-allocated value is, so you have to keep a pointer to it. That pointer will be on the stack, but it will point to the heap.

The details of updating stacks for function calls and returns are complicated, so I'd reccomend The Dragon Book or The Tiger Book if you're interested.

# Answer
> 24 votes
> When a computer stores a variable, when a program needs to get the variable's value, how does the computer know where to look in memory for that variable's value?

The program tells it. Computers do not natively have a concept of "variables" - that's entirely a high-level language thing!

Here's a C program:

```
int main(void)
{
    int a = 1;
    return a + 3;
}

```

and here's the assembly code it compiles to: (comments starting with `;`)

```
main:
    ; {
    pushq   %rbp
    movq    %rsp, %rbp

    ; int a = 1
    movl    $1, -4(%rbp)

    ; return a + 3
    movl    -4(%rbp), %eax
    addl    $3, %eax

    ; }
    popq    %rbp
    ret

```

For "int a = 1;" the CPU sees the instruction "store the value 1 at the address (value of register rbp, minus 4)". It knows where to store the value 1 because the program tells it.

Likewise, the next instruction says "load the value at address (value of register rbp, minus 4) into register eax". The computer doesn't need to know about things like variables.

# Answer
> 2 votes
When the compiler or interpreter encounters the declaration of a variable, it decides what address it will use to store that variable, and then records the address in a symbol table. When subsequent references to that variable are encountered, the address from the symbol table is substituted.

The address recorded in the symbol table may be an offset from a register (such as the stack pointer) but that's an implementation detail.

# Answer
> 0 votes
The exact methods depend on what specifically you are talking about and how deep you want to go. For example, storing files on a hard drive is different than storing something in memory or storing something in a database. Although the concepts are similar. And how you do it at a programming level is a different explanation than how a computer does it at the I/O level.

Most systems use some sort of directory/index/registry mechanism to allow the computer to find and access the data. This index/directory will contain one or more keys, and the address the data is actually located in (whether that be hard drive, RAM, database, etc.).

**Computer Program Example**

A computer program can access memory in a variety of ways. Typically the operating system gives the program an address space, and the program can do what it wants with that address space. It can write directly to any address within its memory space, and it can keep track of that how it wants. This will sometimes vary by programming language and operating system, or even according to a programmer's preferred techniques.

As mentioned in some of the other answers, the exact coding or programming used differs, but typically behind the scenes it uses something like a stack. It has a register that stores the memory location where the current stack starts, and then a method of knowing where in that stack a function or variable is.

In many higher level programming languages, it takes care of all that for you. All you have to do is declare a variable, and store something in that variable, and it creates the necessary stacks and arrays behind the scenes for you.

But considering how versatile programming is, there isn't really one answer, since a programmer can choose to write directly to any address within its allocated space any time (assuming he is using a programming language that allows that). Then he could store its location in an array, or even just hard code it into the program (i.e. the variable "alpha" is always stored at the beginning of the stack or always stored in the first 32 bits of allocated memory).

**Summary**

So basically, there has to be some mechanism behind the scenes that tells the computer where data is stored. One of the most popular ways is some sort of index/directory that contains key(s) and the memory address. This is implemented in all sorts of ways and is usually encapsulated from the user (and sometimes even encapsulated from the programmer).

Reference: How do computers remember where they store things?

# Answer
> 0 votes
**It knows because of templates and formats.**

The program/function/computer doesn't actually know where anything is. It just expects something to be in a certain place. Let's use an example.

```
class simpleClass{
    public:
        int varA=58;
        int varB=73;
        simpleClass* nextObject=NULL;
};

```

Our new class 'simpleClass' contains 3 important variables - two integers that can contain some data when we need them to, and a pointer to another 'simpleClass object'. Let's assume that we're on a 32-bit machine for the sake of simplicity. 'gcc' or another 'C' compiler would make a template for us to work with to allocate some data.

**Simple Types**

Firstly, when one uses a keyword for a simple type like 'int', a note is made by the compiler in the executable file's '.data' or '.bss' section so that when it's executed by the operating system, the data is available to the program. The 'int' keyword would allocate 4 bytes (32 bits), while a 'long int' would allocate 8 bytes (64 bits).

Sometimes, in a cell-by-cell manner, a variable may come right after the instruction that's supposed to load it into memory, so it would look like this in pseudo-assembly:

```
...
clear register EAX
clear register EBX
load the immediate (next) value into EAX
5
copy the value in register EAX to register EBX
...

```

This would end with the value '5' in EAX as well as EBX.

While the program executes, every instruction is executed except for the '5' since the *immediate load* references it and makes the CPU skip over it.

The downside of this method is that it's only really practical for constants, since it would be impractical to keep arrays/buffers/strings in the middle of your code. So, generally, *most variables are kept in program headers.*

If one needed to access one of these dynamic variables, then one could treat the immediate value as if it were a pointer:

```
...
clear register EAX
clear register EBX
load the immediate value into EAX
0x0AF2CE66 (Let's say this is the address of a cell containing '5')
load the value pointed to by EAX into EBX
...

```

This would end with the value '0x0AF2CE66' in register EAX and the value of '5' in register EBX. One can also add values in registers together, so we'd be able to find elements of an array or string using this method.

Another important point is that one's able to store values when using addresses in a similar manner, so that one can reference the values at those cells later.

**Complex Types**

If we make two objects of this class:

```
simpleClass newObjA;
simpleClass newObjB;

```

then we can assign a pointer to the second object to the field available for it in the first object:

```
newObjA.nextObject=&newObjB;

```

Now the program can expect to find the address of the second object within the first object's pointer field. In memory, this would look something like:

```
newObjA:    58
            73
            &newObjB
            ...
newObjB:    58
            73
            NULL

```

One very important fact to note here is that 'newObjA' and 'newObjB' don't have names when they're compiled. They're just places where we expect some data to be at. So, if we add 2 cells to &newObjA then we find the cell that acts as 'nextObject'. Therefore, if we know the address of 'newObjA' and where the 'nextObject' cell is relative to it, then we can know the address of 'newObjB':

```
...
load the immediate value into EAX
&newObjA
add the immediate value to EAX
2
load the value in EAX into EBX

```

This would end with '2+&newObjA' in 'EAX' and '&newObjB' in 'EBX'.

**Templates/Formats**

When the compiler compiles the class definition, it's really compiling a way to make a format, a way to write to a format, and a way to read from a format.

The example given above is a template for a singly-linked-list with two 'int' variables. These kinds of constructions are very important for dynamic memory allocation, along with binary and n-ary trees. Practical applications of n-ary trees would be filesystems composed of directories pointing to files, directories, or other instances recognized by drivers/the operating system.

In order to access all of the elements, think about an inchworm working its way up and down the structure. This way, the program/function/computer doesn't know anything, *it just executes instructions to move data around.*

---
Tags: compilers, memory-access, variable-binding
---


# Question
Title: Why is this problem listed as "Dynamic Programming"
I found a problem in the dynamic programming section of hackerrank but its not clear why dynamic programming should be used to solve it. The problem is as follows:

> Nikita just came up with a new array game. The rules are as follows: Initially, there is an array, , containing integers. In each move, Nikita must partition the array into non-empty parts such that the sum of the elements in the left partition is equal to the sum of the elements in the right partition. If Nikita can make such a move, she gets point; otherwise, the game ends. After each successful move, Nikita discards either the left partition or the right partition and continues playing by using the remaining partition as array . Nikita loves this game and wants your help getting the best score possible. Given , can you find and print the maximum number of points she can score?

In going over the algorithm that would be used to solve the problem, it seemed evident to me that you could simply write a recursive function where each recursive call would be made iff the sums of the elements in both halves of the array are equal. Otherwise, the game (the algorithm) ends. Since you would, in the worst case (running time wise), be dividing the array log(n) times where n is the array length, you would get a running time of O(logn).

The only thing that I could see dynamic programming helping with here may be the recalculation of the sums which I guess could be avoided by calculating the sums from the bottom up but I'm not really seeing an optimal substructure here. Also, you would be increasing the space complexity seemingly unnecessarily.

**So why/how is dynamic programming being used here?**

# Answer
How do you choose which partition is best (there could be several partitions if you allow negative numbers or zeroes), and which side of the partition to choose? You have to examine all partitions and both sides of each partition, and then choose the best one. Naively, the complexity of this algorithm is exponential. With dynamic programming you can find the solution in polynomial time – I'll let you figure out how.
> 2 votes

---
Tags: algorithms, asymptotics, dynamic-programming, recursion
---


# Question
Title: If A is not mapping reducible to B then A is not mapping reducible to the complement of B?
If A is not mapping reducible to B then A is not mapping reducible to the complement of B?

Is this true?

# Answer
> 3 votes
This is false. Let $B = A\_{\mathsf{TM}}$ and let $A = \overline{B}$. Then $A \not\leq\_{\mathrm{m}} B$, since $A$ is not a recognizable language and $B$ is recognizable. But we trivially have that $A \leq\_{\mathrm{m}} A$.

---
Tags: complexity-theory
---


# Question
Title: Using k-NN for Exact Match in Hamming Space (after Multi-index Hashing)
Before the Question: Greene, Parnas and Yao presented a scheme which, for binary data chosen uniformily a random, retrieves all points within Hamming distance r of a given point in time $O(d n^{r/d})$ using $O(d n^{1+r/d})$. The scheme is based on Turán's graph and the complete description can be found here.

I was reading this paper Fast Exact Search in Hamming Space with Multi-Index Hashing. and realised there is nothing written WHEN r=0, that is, how to find an EXACT MATCH using neighbour search.

The question is concerned with EXACT MATCH (r=0) of an exact k-NN search in Hamming Space using Multi-index Hashing. I'm not interested in the first nearest element. I would like a data structure that answer the existence of an element inside a set. Is it possible to make such a data structure?

What is the complexity of the Yao's algorithm or Norouzi's algorithm when r=0? I think it is not only make r=0 in the above complexities to get the answer...

# Answer
You don't need sophisticated data structures or algorithms to handle this case. Exact match (r=0) just means that you want to store a set $S$ of points in a way so that, given $x$, you can test whether $x$ is in $S$. If you have a set $S$ and want to be able to query whether a point $x$ is in the set, then standard data structures suffice. You don't need anything fancy: you can just store all the points of the set in a hashtable. Queries just involve a lookup into the hashtable. Or, you can use a balanced binary tree, or any other standard dictionary data structure.

The running time per query is basically expected $O(d)$ time or $O(d \lg n)$ time, where $d$ is the number of dimensions, if you choose the data structures appropriately. This is essentially optimal, since even just reading the point takes $O(d)$ time. In principle, you could get the running time down to expected $O(\lg n)$ time per query, if you cared, by taking a random projection onto a subset of $O(\lg n)$ coordinates, though I'm not sure whether it'll be significantly faster in practice.
> 2 votes

---
Tags: nearest-neighbour
---