# Question
Title: Lambda Calculus inductive substitution definition
I'm reading **Lambda-Calculus and Combinators: An Introduction**, and there's the following definition of $\lambda$-substitution:

* $FV(P)$ stands for the set containing all free-variables from $P$.

> **Definition 1.12 (Substitution)** For any $M, N, x$, define $\[N/x\]M$ to be the result of substituting $N$ for every free occurrence of $x$ in $M$, and changing bound variables to avoid clashes. The precise definition is by induction on $M$, as follows ***(after \[CF58, p.94\])***.
>
> (a) $\[N/x\]x \equiv N$
>
> (b) $\[N/x\]a \equiv a$ for all atoms $a \not \equiv x$
>
> (c) $\[N/x\](PQ) \equiv (\[N/x\]P)(\[N/x\]Q)$
>
> (d) $\[N/x\](\lambda x.P) \equiv (\lambda x.P)$
>
> (e) $\[N/x\](\lambda y.P) \equiv P$ if $x \not \in FV(P)$.
>
> (f) $\[N/x\](\lambda y.P) \equiv \lambda y. \[N/x\]P$ if $x \in FV(P)$ and $y \not \in FV(N)$.
>
> (g) $\[N/x\](\lambda y.P) \equiv \lambda z. \[N/x\]\[z/y\]P$ if $x \in FV(P)$ and $y \in FV(N)$.

I do understand that:

* $(a), (b)$ are the base cases for this induction.
* $(d)$ exists per definition, as one is not allowed to substitute bound variables.
* $(g)$ prevents a bound variable from changing to a free one. It does this by first substituting a **bound variable**.

My question is: **If one deletes $(d)$ and allows bound variables to be substituted, is $(g)$ strong enough to handle it without messing up everything?**

I'm asking this because $(d)$ seems to prevent the following $\alpha$-equivalent substitutions.

$$ \[y/x\] ~~ \lambda x. x \equiv \lambda y.y $$

# Answer
> 5 votes
> "If one deletes $(\mathrm{d})$ and allows bound variables to be substituted..."

The problem here is that *substitution* of a bound variable makes little sense, since one substitutes a variable (let's forget for a moment it should be free) with a *term*, which may very well be an abstraction or application, but not a variable.

Let me illustrate this by example. What if we are trying to substitute a bound variable with a term, which is not a variable? Like this: $$\[(y\\; y)\ / \ x\]\ \lambda x. x.$$ What should we do?

* Produce $\lambda (y\\; y). (y\\; y)$? It is not a well-formed term, so the answer is no.
* Another choice would be to leave the binding instance intact and make $\lambda x. (y\\; y)$ a result. Let's not take into account if it makes sense, at least it is syntactically correct. This variant causes us major troubles too: it will mess up scopes and render $\beta$-reduction useless. And our end goal is to define $\beta$-reduction via substitution.

> $(\mathrm{g})$ prevents a bound variable from changing to a free one. It does this by first substituting a bound variable.

It does not use substitution, it uses renaming, which is a different notion.

> "...is $(\mathrm{g})$ strong enough to handle it without messing up everything?"

$(\mathrm{g})$ does not tell us anything about substitution of bound variables, since it has the condition $x \in \mathrm{FV}(P)$

# Answer
> 4 votes
First of all, you can't always define a substitution for bound variables. Having $\[x/y\](\lambda y.\ y) = \lambda x.\ x$ may look appealing, but there's no real way to replace the bound variable in $\[(xx)/y\](\lambda y.\ y)$ since $\lambda$ wants a variable, not a term. (As Anton Trunov points out above)

It is true however that the $\lambda$ rules in the definition of substitution $(d,e,f,g)$ consider a lot of cases, which could be combined at the cost of a few more $\alpha$-conversions. For instance, we could replace all the $\lambda$ rules with this one: $$ \qquad \[N/x\](\lambda y.\ P) = (\lambda z.\ \[N/x\]\[z/y\]P) \qquad \mbox{where $z$ is the first variable not free in $x N (\lambda y.\ P)$} $$ This rule *always* renames bound variables to fresh ones, even when it is not necessary to do so. Moreover, it *always* distributes the substitution inside the lambda, even when $x \notin FV(P)$ and the substitution has no effect.

The result of the rule above is the same of what you get using rules $(d,e,f,g)$ up to $\alpha$-conversion. Hence, it only differs from the rules in the book by performing more renamings.

Rules $(d,e,f,g)$ can be seen as a "smarter" way of performing substitution, stopping as soon as there is no more $x$ around, and renaming variables only as needed.

---
Tags: lambda-calculus, induction
---


# Question
Title: Determine whether a context-free language is deterministic or not
I define language $L = \\{a^k a^m b^m c^k \\} \cup \\{a^n b^n b^k c^k\\}$ and I want to determine if it's deterministic context free language or it is nondeterministic. so I tried to create pushdown automata for this language like below.

first I read $a$ and push it to stack till it ends. right know number of $a$ in the stack is $x = k + m$ or $x = n$. now for each $b$ we can erase a $a$ from stack and there will appear tree case

* **case 1:** stack will be empty and we can still read $b$ so the string should be in $\\{a^n b^n b^k c^k\\}$
* **case 2:** stack will be contain some $a$s and string should be in $ \\{a^k a^m b^m c^k \\}$
* **case 3:** stack will be empty and there is no $b$ to read so $k$ should be zero.

in case one we can push $b$ into stack and after that we have $k$, $b$s in the stack and we can pop each one of $b$ instead of reading a $c$. in case two the number of $a$ in the stack is $k$ and like case one read $c$ and pop $a$ until stack will be empty. so I think this $DPDA$ should accpet language $L$ but I heard from someone that this language is not deterministic context free language. is my $DPDA$ wrong? where is the problem?

# Answer
The language that is usually cited as not accepted by any DPDA is $\\{a^mb^nc^nd^m\\} \cup \\{a^mb^mc^nd^n\\}$. This is because we don't know whether to push or pop when $b$ arrives. The language you describe seems to be accepted by the DPDA you have constructed.
> 3 votes

---
Tags: context-free, pushdown-automata
---


title: NFA with epsilon transition

text:
# Question
Title: NFA with epsilon transition
I need to understand the epsilon transition for NFA, for example I have an NFA with four states `q0`, `q1`, `q2` and `q3` the latter is an accepted state.

In particular the transition function is:

```
{q0, a}= {q1}
{q1, eps}= {q2}
{q2, b}= {q3}

```

I would implementing this behavior in java.

I have the string 'ab' and I have to see if it is accepted. I begin reading the character 'a' and arrival in the state `q1`, the next character is 'b' but the state `q1` don't have transition for 'b'.

I have to run the epsilon transition as I read the character 'a'? I do not know how to do this in my application, can you help me?

Thanks

# Answer
You seem to be misconstruing what an $\epsilon$-transition is. If we have, say, a transition rule $\delta(q\_1,\epsilon)=\\{q\_2\\}$ it means that the FA can switch from state $q\_1$ to $q\_2$ *without reading any input*. In your example, on input $ab$ the FA reads the $a$ and so passes from $q\_0$ to $q\_1$. It can then (in one reality) stay in $q\_1$ or (in another), pass to state $q\_2$. Then, on seeing the $b$, there is indeed no move from $q\_1$ (in one reality) but there is a move (in another reality) to $q\_3$, so since the NFA reaches a final state in one reality, the input $ab$ is accepted by the NFA.
> 1 votes

---
Tags: automata, nondeterminism
---


# Question
Title: Using Headpose Vector and 2D Points to Compute Distances
I have a frame taken from a video. The frame contains a face and I have the (x, y) locations of the features (corners of lips, edge of eyebrows, etc.) and the headpose vector (pitch, yaw, roll), which shows the direction that the face is looking in degrees ((0, 0, 0) would be at the camera).

I need to calculate distances between specific points in real (3D) space. How can I map the feature locations to 3D space?

# Answer
> 1 votes
You don't have enough information to calculate 3D points for anything--all your information is relative right now. You need something that establishes a measurement, and some way to determine depth. If you know how far a point is from the camera (or can estimate it), then you can at least start calculating locations of features you know to be within the vertical plane containing that point. Or if you know how large a feature is, then you can calculate the sizes of features also assumed to be in the same vertical plane. Alternatively, if you can use information from other frames, then you can assume a rigid model for certain facial features and begin to make estimates, but it's still all scale-free until you can pin down a distance *somewhere*.

---
Tags: computer-vision
---


# Question
Title: Algorithm to convert rendered number back into symbolic form
If you have a number such as $3.14626437$ and you need to know what symbols create it, as far as I know, there are two tools:

1- ISC

2- wolframalpha

and the answer is $\sqrt2+\sqrt3$

I am wondering what algorithm these websites are using and how much is their complexity?

# Answer
RIES is another method for finding closed-form expressions; its web page describes the algorithm it uses.

If you do a Google search for `algorithm for inverse symbolic calculator`, you will find Wikipedia's page on algorithms for finding integer relations between multiple real numbers (as the page describes, you look for an integer relation between $x$, the number you care about, and a list of other standard mathematical constants).
> 3 votes

---
Tags: algorithms, algorithm-analysis, mathematical-programming
---


title: Where Can I Find DFA Practice?

text:
# Question
Title: Where Can I Find DFA Practice?
Where can I find a web site or book where I can practice drawing DFAs from a language like " {w| w has at least three a’s and at least two b’s} ". It will be important to have access to the answer so as to check myself. I need the practice.

# Answer
Well you have a little problem between your hands. The problem is that creating a DFA that generates some language $L$ have more than one solution. In fact if $L$ is regular then it have infinite solutions. If you are searching a book with answers it may not be usefull because your answer can be correct even though it is different from the one in the book.

There is some methods to prove the correctness of a DFA using proof by induction but it is fairly difficult. If you are having problems generating DFA I wouldn't reccommend to try proving the correctness until you are more experienced into this topic.

My teacher told me that the best you can do to be sure that your DFA is correct(when you skipping the proof of correctness) is do it in a sistematic way and understandable for anyone that reads it.
> 3 votes

---
Tags: finite-automata
---


# Question
Title: Hough transform: difference in cartesian to polar equation
According to Wikipedia and most other resources on the internet, the relation between cartesian coordinate and polar coordinate parameters are described by the equation $x\cos{\theta}+y\sin{\theta}=d$.

However, the computer vision course in Udacity used $x\cos{\theta}-y\sin{\theta}=d$ instead, as shown in this short video https://youtu.be/2oGYGXJfjzw?t=4s.

What is the difference?

# Answer
> 2 votes
There's no fundamental difference. The difference is merely one of convention, namely, where you consider the origin to be in your $(x,y)$ coordinates. If you consider $(0,0)$ to be in the upper-left (with increasing $y$ values corresponding to going downwards), use one formula. If you consider $(0,0)$ to be in the lower-left (with increasing $y$ values corresponding to going upwards), use the other. Ultimately, the two are equivalent, up to a flip of the plane (reflection across the x axis).

# Answer
> 0 votes
I've been told that if you define theta as becoming bigger when you go from the x axis to the y axis you can use "regular" formulas instead of special formulas for when the y axis points down.

---
Tags: computer-vision
---


title: Why IS is not in NL, only in NP?

text:
# Question
Title: Why IS is not in NL, only in NP?
All we need to do is guess $k$ vertices. We look at vertex $v\_1$, and make sure $v\_1$ is not connected to $v\_2...v\_k$. Then, we "throw" $v\_1$, and look at $v\_2$. We do this to all vertices.

Meaning that we only need to guess $k$ vertices, and in our working memory (which determinates NL or NP) we only need to keep 2 vertices.

Where is my mistake?

# Answer
First, $NL\stackrel{?}{=} NP$ is still open, so $IS\in NL$ is possible (within our current knowledge, though we believe that they are different).

The problem with your proof, is that when you "guess $k$ vertices", you have to write them in your memory (when we say "guess", we mean that we write a vertex in the working tape, where at each step our machine writes either $0$ or $1$). Keeping $k$ vertices simultaneously (where $k$ is part of the input), requires more than logarithmic space.
> 3 votes

---
Tags: np
---


# Question
Title: If the strings of a language can be enumerated in lexicographic order, is it recursive?
If the strings of a language L can be effectively enumerated in lexicographic order then is the statement "L is recursive but not necessarily context free" is true?

# Answer
> 5 votes
Lexicographic order is not such a good order since its order type is not $\omega$. Instead of explaining formally what that means, let me give an example. Consider the language $(a+b)^\*$. If you enumerate the words in lexicographic order, you get $$ \epsilon, a, aa, aaa, \ldots, ab, \ldots $$ The first $\ldots$ signify *infinitely many terms*. So it isn't really clear what it means to enumerate a language in lexicographic order. There could be two interpretations: either the language $L$ doesn't suffer from this problem, or you really mean a slightly different order. Since the precise answer doesn't matter for all that follows, we will just assume that you can effectively enumerate $L$ in some (effective) order whose order type is $\omega$ (i.e., when the problem above doesn't happen).

The proof that $L$ is recursive can be a bit subtle, due to a certain ambiguity: what happens if $L$ is a finite language? There are two reasonable interpretations of effective enumerability in this case: either the enumerator will eventually halt, or it won't, but at some point would stop outputting strings. Fortunately, this ambiguity doesn't affect the proof.

For the proof that $L$ is recursive, we consider two cases. If $L$ is finite, then it is trivially recursive. If $L$ is infinite, then to decide whether $x \in L$ and wait until either $x$ is output, or a string larger than $x$ is output (if $x \notin L$ then this will happen eventually since $L$ is infinite). In the first case $x \in L$, in the second $x \notin L$.

To see that $L$ is not necessarily context-free, you can consider your favorite non-context-free language $\\{c^nb^na^n : n \geq 0\\}$ which is effectively enumerable in (plain vanilla) lexicographic order.

---
Tags: formal-languages, computability, context-free, enumeration
---


# Question
Title: Winning strategy of Nim game when picking from multiple piles is allowed
I am studying with Game theory right now. In Nim game, in any turn, a player can move any number of stones from any ***one*** pile. I am wondering what might be the winning strategy of first player if in any move, a player can pick any number of stones from ***one or more*** piles? In this case, how the *`xor = 0`* rule will work? Both are playing optimally.

# Answer
> 3 votes
*The answer assumes that you have to take the same amount of stones from each pile that you choose. Otherwise the first player always wins as long as the piles are not all empty.*

The rule "xor = 0" doesn't work. In particular, there is a winning position with xor = 0 (easy exercise; be creative).

In order to analyze the game, you can compute which positions are winning and which are losing recursively (surely you have been shown how to do that in your course). Then you can look at which positions are winning and which are losing, and try to guess a rule; you will then need to prove that your rule works.

In this particular case, however, the analysis will be quite difficult. The case of two piles is known as Wythoff's game, and is already pretty non-trivial to analyze.

---
Tags: algorithms, game-theory
---


title: TSP Edge Removal

text:
# Question
Title: TSP Edge Removal
Are there any papers/algorithms for finding edges in a graph that can be removed with affecting the graph's optimal TSP tour length?

For instance, in a Euclidean TSP instance, many edges could be ruled out for being too long (i.e., jumping between very far apart nodes) given a decent upper bound on the optimal tour length. Is there some efficient heuristic algorithm for eliminating edges like this?

# Answer
See "Edge elimination in TSP instances", Hougardy and Schroeder, 2014, http://arxiv.org/abs/1402.7301
> 1 votes

---
Tags: algorithms, graphs, optimization, traveling-salesman
---


# Question
Title: About randomness and minmax algorithm with alpha beta pruning
Will choosing the child of a node randomly in the alpha beta algorithm have a better chance to get a cut off than choosing them in order?

Here's the pseudocode with my addition marked with \***.

```
function alphabeta(node, depth, α, β, maximizingPlayer)
     if depth = 0 or node is a terminal node
         return the heuristic value of node
     arrange childs of node randomly ***
     if maximizingPlayer
         v := -∞
         for each child of node
             v := max(v, alphabeta(child, depth - 1, α, β, FALSE))
             α := max(α, v)
             if β ≤ α
                 break (* β cut-off*)
         return v
     else
         v := ∞
         for each child of node
             v := min(v, alphabeta(child, depth - 1, α, β, TRUE))
             β := min(β, v)
             if β ≤ α
                 break (* α cut-off*)
         return v

```

I ran a small sample with this on a connect four game and it does seem to run a little faster, but when I actually count the cutoffs with and without randomness, there are more cutoffs without randomness. That's a little odd.

Is it possible to prove that it's faster (or slower)?

# Answer
Adding on Yuval Filmus' answer, when testing the time performance of a program, you have to consider that a shallow search with a complex, optimal move ordering heuristics applied everywhere can take more time than a fast, random order search.

This is the for the same reason under which a $O(n)$ algorithm can be faster than a $O(log(n))$ for small inputs.

Usually, for games, the "crosspoint" isn't very large. Anyway many well crafted implementations take advantage of this using different move ordering logic depending on search depth.

Citing Wikipedia:

> As the number of positions searched decreases exponentially each move nearer the current position, it is worth spending considerable effort on sorting early moves. In practice, the move ordering is often determined by the results of earlier, smaller searches.

Many aspects of this tradeoff are better understood studying the Iterative Deepening technique (initially adopted for time management, it has proved surprisingly beneficial as far as move ordering is concerned in alpha-beta).
> 2 votes

# Answer
It's neither faster nor slower, since it depends on your order. Your order might be the best possible order, in which case randomness hurts; or it might be the worst possible order, in which case randomness helps.

If you want to guarantee not hitting a worst case behavior, you can use randomness. But it might be better to choose the order heuristically using less than full randomness.
> 4 votes

---
Tags: algorithms, artificial-intelligence, randomness
---


# Question
Title: Greedy algorithm for submodular optimzation
In these notes, https://courses.engr.illinois.edu/cs598csc/sp2011/Lectures/lecture\_3.pdf 4.2.1 exercise 1, the following argument works if $f$ takes values in the integers, but I don't know how to deal with it if $f$ can take values in the reals.

Problem: Given a monotone submodular function $f$ (whose value would be computed by an oracle) on N = {1, 2, . . . , m}, find the smallest set S ⊆ N such that f(S) = f(N).

A greedy algorithm for this problem is as follows:

1. $S \leftarrow\emptyset$
2. while $f(S) \neq f(N)$ {
3. \____find $i$ to maximize $f(S+i)-f(S)$
4. \____set $S \rightarrow S\cup \\{i\\}$
5. }
6. return $S$

Question: Show that this is a $1+\ln f(N)$ approximation algorithm.

An argument is as follows: If $O$ is an optimal set, we can show that for the $i$ chosen in line 3 of the algorithm,

$$ f(S+i) - f(S) \geq \frac{f(N)-f(S)}{|O\setminus S|} \geq \frac{f(N)-f(S)}{|O|} $$

Now letting $S\_k$ denote the set $S$ after the $k$'th iteration (so $S\_0=\emptyset$), and $z\_k = f(N)-f(S\_k)$ i.e., $z\_k$ the "amount left" after the k'th iteration (so $z\_0=f(N)$), the above inequality implies

$$ z\_k \leq z\_{k-1} - \frac{z\_{k-1}}{|O|} = \left(1-\frac{1}{|O|}\right)z\_{k-1} $$

And therefore $$ z\_k \leq \left(1-\frac{1}{|O|}\right)^{k}f(N) \leq f(N)\exp(-k/|O|). $$ Setting $k=|O|(1+\ln f(N))$, we have $z\_k\<1$, and because $f$ takes only integral values, it must be that $z\_k=0$.

But the question does not stipulate $f$ take only integral values. How can you deal with an $f$ that takes non-negative reals?

# Answer
> 1 votes
The claim isn't true in general. Given a monotone submodular function $f$ and a positive constant $C$, let $g = f/C$. The algorithm is oblivious to the change from $f$ to $g$, and on the other hand $1 + \ln g(N) = 1 + \ln f(N) - \ln C$. In particular, by choosing $C$ large enough, you can get that the approximation ratio is any small enough number (even smaller than one or smaller than zero!).

---
Tags: optimization, approximation
---


# Question
Title: Is function application actually a memory manipulation algorithm?
I thought about how in lambda calculus (and many implementations of functional programming languages) function (lambda) application and lambda itself, as a construct, are "primitive things", usually somehow implemented by an interpeter. Then I thought, can you "boil-down" these two things to more primitve stuff. For instance, we have a following expression (apply is usually implicit by the syntax convetions, but whatever)

(apply (\x.\y.x) (a b))

The interpreter:
1. Constructs a new environment, where arguments are bound to lambda's terms, i.e. *new\_env = this\_env.append({"x":a, "y":b, "body":"x"})*
2. Performs a rewrite of the whole application term with lambda's body, i.e. *new\_env\["body"\]*

Given only the environment manipualtion "primitives", like: "construct", "append", and "get", doesn't that make whole lambda calculus just a clever trick to hide memory ("tape") mutations? Now I know that turing machine and lambda calculus are equivalent, but is there something more to LC than just what I've described? What have I missed?

# Answer
That seems reasonable to me, although I've never thought of other that way. The critical point is that LC essentially involves variables and substitution. So I wouldn't say it "hides" memory ops, exactly, that's just how LC substitution translates to Turing machinery. On the other hand, substitution is not primitive - combinatory logic eliminates both variables and substitution. So you might say LC introduces rather than hides something.
> 1 votes

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


title: Origin of the concept of types

text:
# Question
Title: Origin of the concept of types
About the state of art that I'm running ahead of Type Theory I have the these questions all related about history of Types.

1. Where did the idea of *Type* come from? (It seems that all start when Russell and Whitehead propose a way to avoid the contradiction that we know today as Russell's Paradox, am I right?)
2. Before considering the type concept, was there something similar? (Maybe a refinement of a set, but I don't find a reference distinct of Russell).
3. Who was the first person to put it on formal terms? (Was Russell with this paper of 1908 or ?

# Answer
Depends on how deep you want to go. I believe Russell was the guy who introduced the concept in a specifically set-theoretic context, but the concept itself is as old as the hills, it's really the notion of universals and particulars expressed in a modern mathematical / computational form. I wouldn't be surprised if Liebniz did something vaguely like types, if you look at his stuff in the right way.

You might have better luck at the History of Math and Science exchange.
> 1 votes

---
Tags: type-theory, history
---


# Question
Title: Show that language generated by grammar is regular
We have grammar with nonterminals $ X\_1,...X\_n$ terminals $V\_t$ and rewriting rules of form:

$X\_i \rightarrow a \in V\_t $

$X\_i \rightarrow X\_jX\_k, \ i \ge j , \ i \> k $

How can I show that language generated by this grammar is **regular**?

I don't think this is duplicate question, because:

* I don't have concrete language, but set of nonterminals and set of terminals
* I have to show, that for every possible combination of terminals and nonterminals I get only language which is regular

If I had been given particular language, I could prove it by giving DFA, showing that rules are only of linear type,etc....

# Answer
Prove by backwards complete induction that each $X\_i$ generates a regular language (backwards induction means that you first prove it for $X\_n$, then for $X\_{n-1}$, and so on, until you reach $X\_1$; complete induction means that when proving this for $X\_i$, you can use the induction hypothesis for all of $X\_{i+1},\ldots,X\_n$).

Perhaps the easiest way to carry out the inductive proof is to give a regular expression for the language generated by each $X\_i$.

The only non-trivial part is handling productions of the form $X \to XY$. Here you need to use Arden's rule, which states that if the only productions having $X$ at the left-hand side are $X \to XY \mid Z$ then $$ L(X) = L(Z)L(Y)^\*, $$ where $L(X)$ is the language generated by $X$.
> 1 votes

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


# Question
Title: Find all shortest paths in a graph where path has even number of edges and greater than 6
> Let $G=(V,E)$, a directed with non-negative weights ($w:E\to\mathbb{R}^+$). Describe an algorithm, finds all shortest paths in the graph from a source vertex, $s\in V$, such that, each paths has an even number of edges and the number of edges is greater-equal to $6$.

So I know I need to use *Dijkstra* algorithm on a modified graph. Somehow I need to "count" the number of edges. I think I need to add some vertices for each vertex which will make the "count" but I can't figure it out completely.

I'd be glad for help.

Thanks.

# Answer
Hint: Use an appropriate layered graph. If you find the problem difficult, try solving it under only one of the conditions (only an even number of edges, or only at least 6 edges).
> 0 votes

---
Tags: algorithms, shortest-path
---


# Question
Title: The range of significance in Type Theory
What exactly does "Types as ranges of significance of propositional functions. In modern terminology, types are domains of predicates" mean?

**Update:** I found in this paper (Pag 14 or 234) by Russell, where he defines what is *ranges of significance*, not exactly including types else propositions.

> A function is said to be significant for the argument $x$ if it has a value for this argument. Thus we may say shortly *$\phi x$ is significant*, meaning *the function $\phi$ has a value for the argument $x$*. The range of significance of a function consists of all the arguments for which the function is true, together with all the arguments for which it is false.

# Answer
> 1 votes
I believe this is simply referring to old terminology, as the quoted text implies.

When using a formula such as $\sqrt{x-5}$, it is common to specify what $x$ is intended to be so that the formula makes sense. That is, we could let $x$ to be a real number $\geq 5$, so that the square root is defined. Only when $x$ "ranges" over the values satisfying such condition the formula is meaningful, or "has significance". Hence, the "range of significance" of a formula essentially is the class of the values the variables must be in so that the formula makes sense.

This is true in propositions, too. If a propositional formula involves variables, as in $f(x) \< 4 \implies f(x) \< 0$, then we can regard the formula as a function mapping the value of its (free) variables $f,x$ to a proposition. This is why it can be called a "propositional function". Its "range of significance" are the values $(f,x)$ which make the proposition meaningful. We can't let e.g. $f = 5$ and $x = \mathbb{N}$, so that pair is outside the range.

In modern terms, indeed, this is what we usually call "domain of a predicate".

# Answer
> 2 votes
Comes from Russell, and it's actually about the domain, not the codomain, if I understand ol' Bertie correctly. A propositional function like "x\>3" only has significance if we limit the possible values of x to numbers. Today we would call that the domain, but his choice of words is defensible: the range of significance of a propositional fn is the set of values that make it meaningful - i.e. true or false - as opposed to meaningless nonsense, like "Pegasus\>3". The range of significance of a numeric fn is the set of values for which it yields a value, rather than crashing, so to speak.

The relation to types is fairly obvious: the range of significance of a fn $f: A\rightarrow B$ is just the "values" of type $A$ to which $f$ can be meaningfully applied. The concept and term "type" is just a more commodious way of expressing the same basic concept. Google "propositional function range of significance" and you'll get links to his original paper and lots more.

---
Tags: type-theory
---


# Question
Title: If graph isomorphism yields a polynomial time algorihtm
Greeting I'm studying computing theory and are trying to grasp the concept of complexity classes.

If graph isomorphism (suspected NPI) turns out to have polynomial time solution. What possible implication it has or what can we possibly deduce?

Thanks for any explanation

# Answer
> 2 votes
Nothing bad is known to happen if Graph Isomorphism can be solved in polynomial time; see this question on cstheory. On the other hand, problems in the complexity class GI will all have polynomial time algorithms.

---
Tags: complexity-theory, time-complexity, graph-isomorphism
---


# Question
Title: Smallest real root of a polynomial in a range
I'm trying to numerically find the smallest real root of a polynomial in a given range. My initial plan was to shift the polynomial so that the bottom of the range was 0, expand the resulting expressions to find the new coefficients, then use the Jenkins-Traub algorithm until it finds the first (smallest) root or increases out of the range. However, the Wiki page says that it only **generally** finds the roots in increasing order, so it sounds like that's not guaranteed. Is there a way to guarantee finding the first root? If not, what is the most efficient way to solve the problem?

Finding all the roots then sorting is possible, but is inefficient as the degree of the polynomial gets larger, and, I hope, unnecessary. The bisection method is another common algorithm, but consider the polynomial: $-5x^2+5x-1$ with a range of (0,2), which would cause the angle bisection to fail. The best answer is one that guarantees success with the fastest time for a reasonable degree polynomial (less than say 10).

# Answer
I would like to propose mix of Sturm algorithm (to split range into ranges to know how many roots are there) and then run Newton method, which converges very fast with good initial guess.

Of course for Sturm - only up to first root range found.

Housholder is very tempting, but please check the runtime first to tweak the degree (and there is chance that it will in fact be Newton after all, when degree is equal one).

The main idea behind that is local root finding methods are faster than global ones, but they might diverge to some other place, but you are interested in the first one, so providing good initial guess will put Newton method in the radius of convergence.

The things to add: there might be many roots in small distance, so the main idea was to "pick one" range and start finding it, your idea of finding the slope is very neat, and if you merge the slope finding with initial range picking it seems like boosted Newton for very small cost.
The idea is to also show Newton method which root you are after (otherwise it might go after surrounding one).

About binary search, if you want to apply it until there is one root - yes, indeed, but if the idea is to check more ranges - I would cut it for resources savings.
> 1 votes

---
Tags: algorithms, numerical-algorithms
---


# Question
Title: How to improve the accuracy of automatic conflict resolution?
**A little background information from my previous question**:https://english.stackexchange.com/questions/318528/conflict-resolution-how-to-decide-if-two-words-are-generally-unmistakable

When a court reporter strokes 2 different words with the same keys, this creates a conflict. Normally, the reporter will fix the error later, but sometimes there is a way for the court reporting software to fix the error for you. This can be referred to as automatic conflict resolution.

My court reporting software's system for accomplishing this is by recording the parts-of-speech before and after the conflicting words.

So for example, if my two conflicting words are *Tallahassee* and *shake* and I type the following sentences it will look something like this:

I eat at `Tallahassee / shake` all the time. (Prep - Determiner)

I eat a `Tallahassee / shake` all the time. (Article - Determiner)

At first it will make me choose between the two, but after I chose it will then automatically add its defined part of speech in a database, so that if I type something like this...

I eat in Tallahassee every afternoon. (Prep - Determiner)

my computer should correctly pick "Tallahassee" since I already told it that "Tallahassee" occurs after a Prep and before a Determiner. The rule for this is simply `pos word pos`

I tested the practicality of this conflict-resolution system with 79 random conflicts using parts of ANC's pos-tagged corpus and Excel VBA.

* As the data shows, only 10 out of the 79 conflicts showed up with 0 *collisions* total. This means that in the entirety of the corpus, none of these conflicts had conflicting parts-of-speech which had caused an error.
* 36/79 conflicts showed up with 5 or less collisions.
* 32/79 had 10 or more collisions
* Each collision represents 1 guaranteed error of *real-time translation* given the `pos word pos` rule (per the parsed text from ANC, which was about 4.5 million words long)

These results aren't very good for the kind of real-time accuracy I hope to achieve. It would be much better if I could get at least 30/79 (as opposed to only 10) to have 0 "guaranteed errors."

---

**How can I improve this system so that I will have fewer real-time translation errors?**

My best thought is to change the rule from `pos word pos` to `pos pos word pos` in the case of a collision, but that's all I've got. I'm not very experienced on this subject, so I'm not necessarily opposed to the idea of starting over with something fresh.

# Answer
There are many candidate approaches you could consider. I would suggest you be creative about what features you could use, to make predictions about which candidate is more likely to be the intended one.

---

One approach is to use a language model for the prevalence of different phrases. For instance, if $w, x$ are two words, define

$$r(x | w) = {P(w \\; x) \over P(w) \times P(x)}.$$

(Here $P(w \\; x)$ represents the prevalence of the 2-gram $w \\; x$ in some large corpus, and $P(w)$ represents the prevalence of the 1-gram $w$ in the corpus.)

Now if the previous word is $w$ and the next word is either $x$ or $y$, compare $r(x | w)$ to $r(y | w)$ to see which is larger, and use that to resolve the conflict.

For example, comparing $r(\text{Tallahassee} | \text{at})$ to $r(\text{shake} | \text{at})$ using the Google n-gram viewer, we find that the former is much larger. In particular, the former is $1.2 \times 10^{-6}/(0.3 \times 8.5 \times 10^{-5}) \approx 0.05$, while the latter is $4.8 \times 10^{-8}/(0.3 \times 9.7 \times 10^{-4}) \approx 10^{-4}$, which is much smaller. We conclude that "Tallahassee" is much more likely to follow "at" than "shake", so the conflict should be resolved by the former.

You can generalize this to use any number of tokens of previous history (e.g., the previous 2 words instead of the previous 1 word).

---

Another approach would be to use something similar, but replace words with their parts of speech.

For instance, Google's n-gram viewer supports part-of-speech queries. You can quickly see that "*ADP* Tallahassee" (basically, a preposition followed by Tallahassee) is more common than "*ADP* shake", so "I eat at" is more likely to be followed by "Tallahassee" than "shake". In contrast, you can see that "*DET* shake" is more common than "*DET* Tallahassee"; so "a" (an article) is more likely be to be followed by "shake".
> 1 votes

---
Tags: algorithms, regular-languages, artificial-intelligence
---


title: TSP problem with a benchmark data

text:
# Question
Title: TSP problem with a benchmark data
I've got a test Travel Salesman Problem's data with known optimal solutions. It's in a form of set of 2D points. Particularly, this is a tsplib format; sources are here and here.

I'd started a simple test with the "Western Sahara - 29 Cities" (wi29) and found that my algorithm rapidly found a few better particular solutions than the proposed optimum.

---

I checked one of them manually and didn't find an error. So, I guess, here're the three options.

1. I did a mistake.
2. Wrong optimum.
3. Different problems were solved.

---

1 and 2. My solution tour is:

> 17\>18\>19\>15\>22\>23\>21\>29\>28\>26\>20\>25\>27\> 24\>16\>14\>13\>9\>7\>3\>4\>8\>12\>10\>11\>6\>2\>1\>5

*(will list my checking calculations if requested)*

Rounded length: 26040.76. Optimal reference value: 27603.

3. I can't find a particular task descriptions and especially rounding policy for the TSPLib examples optimums. This is important, because they're looking rounded or discretized in another manner, but simple result rounding isn't looks like it.

# Answer
In the TSPLIB norm, the travel cost between each pair of cities is the Euclidean distance between the points rounded to the nearest integer (not the distance rounded to two decimal places).
> 2 votes

# Answer
While comparing your solutions with the TSPLib's proposed optimal solutions be assured that you're solving the same problem.

I'd found here two important points about it.

1. In TSPLib, the 2D data is rational pairs accurate to the 4th decimal place, but the distance function is Euclidean metrics result rounded to integer values.
2. They're solving the traveling salesman problem with returning to the start.

This was obtained from hints here and confirmed by diving into their code.

Later, I found a useful FAQ for solving all my problems without diving into the library's code, hope it saves time for readers. TSPLIB FAQ
> 1 votes

---
Tags: algorithms, graphs, optimization, randomized-algorithms, traveling-salesman
---


# Question
Title: Imagine a red-black tree. Is there always a sequence of insertions and deletions that creates it?
Let's assume the following definition of a red-black tree:

1. It is a binary search tree.
2. Each node is colored either red or black. The root is black.
3. Two nodes connected by an edge cannot be red at the same time.
4. Here should be a good definition of a NIL leaf, like on wiki. The NIL leaf is colored black.
5. A path from the root to any NIL leaf contains the same number of black nodes.

---

### Question

Suppose that you have implemented the `insert` and `delete` operations for the red-black tree. Now, if you are given a valid red-black tree, is there always a sequence of `insert` and `delete` operations that constructs it?

---

### Motivation

This question is motivated by this question and by the discussion from this question.

Personally, I do believe that if you imagine a valid red-black tree consisting only of black nodes (which implies that you are imagining a perfectly balanced tree), there is a sequence of `insert` and `delete` operations that constructs it. However,

1. I do not know how to accurately prove that
2. I am also interested in the more general case

# Answer
> 3 votes
The insert and delete operations in a red-black tree **include** the balancing needed to maintain the red-black properties.

The problem with non(left- or right-) leaning red black trees is that there are multiple ways to restore the red-blackness after the basic delete or insert.
It is not the insert or the delete that transforms the tree, but the rebalancing and rotation that happens afterwards to preserve/restore the red blackness of the tree.

The basic description of the red-black tree does not prescribe which of the possible routes to take.
It may not be possible to figure out how to **exactly** reconstruct a given red black tree, because the rebalancing need not be deterministic.

This has been 'solved' with left-leaning red black trees.
There is only one way the balancing is done. So any given leaning red black tree can be reconstructed using inserts and deletes, because the rebalancing/rotations are done in a specific deterministic way.

This does not mean that left-leaning RB-trees are better or more efficient, what they gain on one hand by using deterministic balancing rules, they lose on the other by more complex balancing code.

As per @Anton's comment:
There is an algorithm which uses the operation insert and delete to construct a valid red-black tree consisting only of black nodes. It uses $(h+2)⋅2^{h}−1$ insertions/deletions to create a tree of height $h$. First, we can create a perfectly balanced red-black tree in breadth-first manner using $2^{h+1}−1$ insertions, then using $h∗2^{h-1}$ insertions and the same amount of deletions repaint it into a completely black tree. The trick here is to move up $h$ times the lowest red layer up the tree until it reaches the root.

I think a complete balancing algorithm like Day-Stout-Warren would be more efficient though.

---
Tags: data-structures, search-trees, balanced-search-trees
---


# Question
Title: What Measure of Disorder to use when Analysing Quicksort
I'm trying to understand why quicksort using Lomuto partition and a fixed pivot is performing erratically, but overall poorly, on randomly generated inputs. I'm thinking that even though the inputs are randomly generated, there may be a lot of order to the sequences, but I'm not sure how to measure the level of disorder in the sequences. I thought about using the number of inversions, but I saw from this other question I asked that that's not really a good measure in this case.

The reason I suspect that my random sequences have a lot of "order" to them is that randomizing the pivot fixes the performance problem. But theoretically there shouldn't be any performance problem on these supposedly "random" input sequences.

# Answer
**Lomuto vs Hoare**
Lomuto partition suffers when sorting equal keys, whilst Hoare partition does not.
Both partition schemes suffer equally when using a pivot distant from the median.

**Measure of disorder**
The measure of disorder to choose for the purposes of quicksort is simple.
**A: How far removed from median is the fixed pivot, compared to random data?**
If you insist on using Lomuto partition and if you assume duplicate values are allowed you need to add the following test against randomness:
**B: How many duplicate elements are there, compared to random.**

*Of course it is rather silly to assume that duplicate values are allowed in your data set and still evaluate Lomuto partition, so you should probably either eliminate duplicates beforehand or switch to Hoare partition or assume duplicates are rare.*

Both measures are trivial to quantify using statistics.

**We can rule out pathological data**
Any other deviations from randomness will not matter for the purposes of analysing quicksort. As long as the pivot is close to the median it will perform well on all data that is not pathological.
The distance from random would have to be great indeed to be quicksort-pathological, so we can rule that out.

**Never use any fixed pivot(s) in real code**
Do note that if you write real code with a fixed pivot<sup>\*)</sup> (whatever that pivot may be) you are opening yourself up to a denial of service attack, because an attacker can insert a pathological value at just that point and thus you should always choose a random element as pivot.

\*) or multiple pivots if you choose best of x pivots.
> 1 votes

---
Tags: algorithms, sorting
---


# Question
Title: Is this decidable language a subset of this undecidable language?
I think I understand the theoretical definition of decidable and undecidable languages but I am struggling with their examples.

A(DFA) = {(M, w): M is a deterministic finite automaton that accepts the string w}

A(TM) = {(M, w): M is a turing machine that accepts the string w}

I know that A(DFA) is decidable and A(TM) is not. But, is A(DFA) a subset of A(TM)?

# Answer
> 4 votes
No, A(DFA) is not necessarily a subset of A(TM). When you write "(M, w)" you actually refer to some encoding of M in some alphabet (usually {0,1}). These encodings of DFAs and TMs can be very different.

For a simple example: Let $A\_1, A\_2, \dots$ be an enumeration of all DFAs, and let $M\_1, M\_2, \dots$ be an enumeration of all TMs. You could say that you encode $A\_i$ as the word $0 \text{bin}(i)$ and $M\_i$ as $1 \text{bin}(i)$, where $\text{bin}(i)$ is the binary representation of the number $i$. Then the two langauges you presented are disjunct.

As it seems that this is part of your question: Being a subset and being computationally easier do not relate. Take the set $\Sigma^\*$ of all possible words. It is easily decidable (even by a DFA) but every language, even undecidable ones, are subsets of it.

---
Tags: undecidability
---


title: Rigorous Books on Algorithms

text:
# Question
Title: Rigorous Books on Algorithms
I thoroughly enjoyed my algorithms class but I felt that it lacked rigor. Most of the time I was able to intuitively understand why the algorithms presented worked and why they had the time complexity that was presented but I'd like to be able to prove such things. As such, I'd like a book that goes over lots of common algorithms and has a focus on proving the correctness and time complexity of the algorithms. Any good recommendations?

# Answer
**Note: please edit this answer and add to it, do not create new answers**

Rigorous books:

The Art of Computer Programming by Knuth

A Discipline of Programming by Dijkstra

Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein

Algorithms by Sedgewick and Wayne

Dr Dobb's Essential Books on Algorithms and Data Structures
This also includes `introduction to algorithms`

Algorithms + Data Structures = Programs by Wirth and its followup:
Algorithms and Data Structures

The Science of Programming by Gries and
A Logical Approach to Discrete Math by the same author

Algorithms on Strings, Trees and Sequences by Gusfield

Concrete Mathematics: A Foundation for Computer Science by Graham, Knuth, and Patashnik

The Theory of Parsing, Translation, and Compiling (part I and II) by Aho and Ullman

The Design and Analysis of Computer Algorithms by Aho, Hopcroft, and Ullman

Introduction to Automata Theory, Languages and Computation by Hopcroft and Ullman

Obviously the list can be extended quite a bit.
Note that as the field of computer science has expanded, books are unable to keep up and thus you'll have to turn to research papers.
> 5 votes

---
Tags: algorithms, education, books
---


# Question
Title: What's the time complexity of Monte Carlo Tree Search?
I'm trying to find the time complexity of Monte Carlo Tree Search (MCTS). Googling doesn't help, so I'm trying to see how far I get calculating it myself.

It does four steps for `n` iterations, or before the time runs out. So we'll have

> O(n\*(selection+expansion+simulation+backpropagation))

Expansion just adds a child to the currently selected node. Assuming you're not using a singly linked list or something like that to store tree children, this can happen in constant time, so we can exclude it:

> O(n\*(selection+simulation+backpropagation))

Given the branching factor `b`, and `d` as the depth of our tree, I'm assuming the selection phase runs in O(b\*d), because at each level, the selection phase goes to all the children of the previous node.

So our time complexity becomes

> O(n\*(b\*d+simulation+backpropagation))

Backpropagation takes time proportional to the depth of the tree as well, so that becomes:

> O(n\*(b\*d+simulation+d))

But now I'm not sure how to add the simulation phase to this. It'll be proportional to the depth of the tree, but for each iteration, the running time depends heavily on the implementation as far as I know.

# What's monte carlo tree search

Monte Carlo Tree Search (MCTS) is a tree search algorithm that tries to find the best path down a decision tree, mostly used for game playing. In games with a high branching factor, it can often go deeper than algorithms like Minimax, even with Alpha-Beta pruning, because it only looks into nodes that look promising. For a certain number of iterations (or a certain amount of time), the algorithm goes through these four phases:

**Selection** Starting at the root node, go down the tree until you find a node that is not fully expanded, or a leaf node. At each level, select the child that looks most promising. There are many ways of making this selection, but most implementations (including mine) use UCB1.

**expansion** Expand the selected child by looking at one of its unexplored children.

**simulation** Simulate a "rollout" from the newly discovered child. Again, there are many ways to do this, but many implementations just take a random child until it reaches an end node. Take note of whether the simulation resulted in a success or a failure (win or loss in the case of a game).

**backpropagation** update the information about this node, and all nodes along the path back to the root. Most implementations store two values at each node: the number of times it was part of a selection path that lead to a success, and the total number of times it was part of a selection path. These values are used during the selection phase.

After you've run this for as long as you can, the child node of the root that looks most promising is the action to take next.

# Answer
According to http://stanford.edu/~rezab/classes/cme323/S15/projects/montecarlo\_search\_tree\_report.pdf

> **Time Complexity**
> The runtime of the algorithm can be simply be computed as $O(mkI/C)$
> where $m$ is the number of random children to consider per search and $k$ is the number of parallel searches, and $I$ is the number of iterations and $C$ is the number of cores available.
>
> **Memory Complexity**
> The memory complexity is $O(mk)$ since in each iteration we map $mk$ states over the cluster.
> 1 votes

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


# Question
Title: Turing Machine that always returns a blank tape
Is it possible to construct a Turing Machine such that given any finite input on a tape $s$, it clears the tape in a finite amount of time?

I have used such a TM as an intermediate step to show a reduction from the State Entry Problem to is $w \in L(M)$ problem but I don't know if it is feasible to construct one.

Even if we assume that the head of the TM always starts at the leftmost character on the tape and keep moving write, clearing each symbol we encounter, if the tape is infinite, how will we know when to stop moving right?

# Answer
> 2 votes
While the tape is infinite, the amount of characters written on it is finite at any given point in time.

As sasha indicates in their comment, we usually assume that the tape is initialized with a special blank character. Given a Turing machine, you can modify it so that whenever it visit a cell having the special blank character, it replaces it with some other blank character, which it treats the same as the special blank character. Now at any given point in time you can find the (finite) extent of tape which has been visited, and clear it if you wish.

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


title: Convert non-integer decimal to octal

text:
# Question
Title: Convert non-integer decimal to octal
I follow a course in Computer Architecture and I'm making exercises on number conversions. Now one of the questions asks me to convert 251.5625 to octal and hexdecimal base. No further info is given. Would this mean that I have to convert it and just ignore the point? Or what's the convention on something like this?

# Answer
Every non-negative real number can be represented in any integer base $b \geq 2$ as a string of the form $$ x\_{n-1} \ldots x\_0.x\_{-1} x\_{-2} \ldots, $$ where $x\_i \in \\{0,\ldots,b-1\\}$, and the string is interpreted as having the value $$ x\_{n-1} b^{n-1} + \cdots + x\_0 b^0 + x\_{-1} b^{-1} + x\_{-2} b^{-2} + \cdots. $$ For example, 251.5625 in base 10 is the number $$ 2 \times 10^2 + 5 \times 10^1 + 1 \times 10^0 + 5 \times 10^{-1} + 6 \times 10^{-2} + 2 \times 10^{-3} + 5 \times 10^{-4}. $$ (You can extend this to negative numbers as well by allowing negation, e.g. -3.)

It is a basic result of arithmetic that *every non-negative real number has a base $b$ expansion*. In general, every number has infinitely many expansion: for example, 251.5625 can also be written as 0251.5625 or as 251.56250. If we don't allow leading and trailing zeroes then some numbers have a unique expansion, for example 0.33333…, and some numbers have two expansions, for example 251.5625 = 251.562499999….

A number is of the second form (has two expansions) if and only if it has a *terminating expansion*, that is one which is finite (for example 251.5625). The only number in base $b$ with this property are those of the form $N/b^k$ for integers $N,k \geq 0$. For example, 251.5625 = 2515625/104.

In your case, notice that 251.5625 = 4025/24. This shows that your number has a terminating expansion in any even basis, and in particular in base 8 (octal) and base 16 (hexadecimal). There are known algorithms to convert between bases, that you can find off the internet.

If you already know how to convert integers among bases, then you really also know how to convert non-integers, as long as they have a terminating expansion in the target base. To illustrate the method, consider the number 2.25. We want to convert it to base 4. Note that 2.25=9/4. Now 9 in base 4 is 214 (the subscript is how we indicate the base), and so 9/4 in base 4 is 2.14, since moving the decimal mark one digit to the left (from 21. to 2.1) is tantamount to dividing by the base (similarly, moving it to right corresponds to multiplying by the base).

Hopefully this theoretical information suffices for your problem.
> 1 votes

---
Tags: computer-architecture, base-conversion
---


title: Building an undecidable T-Grammar

text:
# Question
Title: Building an undecidable T-Grammar
I am asked, "Show that these T-Grammars constitute a set of languages that are undecidable. Do this by building a T-Grammar for a Turing machine description. For a starting point you might think about machine configurations."

I am not sure how configurations is suppose to help, but the grammar that I built:

$$ abc \to def; d \to a; e \to b; f \to c $$

Is this undecidable?

# Answer
> 1 votes
Presumably, a T-grammar is undecidable if you cannot decide its *word problem*: given a word $w$, to decide whether the grammar generates $w$.

(Another option is that we want to show that the following problem is undecidable: given a T-grammar $G$ and a word $w$, decide whether $G$ generates $w$. This slightly simplifies the plan of attack suggested below.)

There are basically two ways to show that a certain problem is undecidable:

1. Diagonalization.
2. Reduction to the undecidability of another problem.

Here it's not clear how to diagonalize, so we want to use the second method. We want to come up with some problem P which we already know is undecidable, and construct a grammar G, such that if you could solve the word problem for G, then you could solve problem P.

The hint suggests to use the following class of problems. For each Turing machine T, we can consider the problem to decide, given a word $w$, whether T halts on the input $w$. There exists a Turing machine T for which this problem is undecidable.

This suggests the following course of action: show a method to transform a Turing machine T into a T-grammar G such that T halts on $w$ iff $G$ generates $w$. If we could do that, then we will have proved that the word problem is generally unsolvable for T-grammars.

How do you convert a Turing machine T into a T-grammar G? It is here that machine configurations could become helpful. I'll leave the rest for you to ponder.

---
Tags: turing-machines, formal-grammars
---


# Question
Title: Machine learning algorithm for predicting binary decisions on a large, underrepresented dataset
I would like create a classifier which works on a relatively large (about 30k samples) dataset with circa 20 attributes and a binary decision, however such, which contains relatively small amount of samples with, say, "Yes" decision. That is, the data for building a classifier seems underepresented.

My question is, are there any algorithms which work well with these kinds of datasets? So far I have tried C4.5 (J 48 actually), some basic SVM algorithms, Naive Bayes and MLP, hovewer each method failed to learn the dependencies in the data well (accuracy was at the level of about 90% and this underrepresented decision was... unrepresented by the classifier too). I'm using Weka if this makes any difference.

# Answer
When you have many more "No" samples than "Yes" samples, this is known as the "class imbalance" problem. Dealing with class imbalance is challenging: many machine learning algorithms don't work as well in this situation.

There are many techniques for dealing with class imbalance, including using class weights, oversampling the "No" samples, or undersampling the "Yes" samples. I suggest doing a little bit of reading about techniques for dealing with class imbalance on Stats.SE, then trying them to see if they help. Their effectiveness may depend on the data set and on which type of classifier you use.
> 2 votes

---
Tags: machine-learning
---


# Question
Title: What is wrong with this reasoning that finding the genus of a degree 3 bipartite graph is NP-complete?
Finding genus of a biparite graph is $NP$-complete and finding genus of a degree $3$ graph is $NP$-complete and so finding genus of a degree $3$ bipartite graph is $NP$-complete.

Though implication could be right is there any harm in reasoning this way on $NP$-completeness?

# Answer
> 6 votes
You cannot reason in this way. Try proving it formally to see what goes wrong.

Also, consider the following example (which is admittedly slightly different than yours). Chromatic number is NP-complete, even for planar graphs. The 4-coloring problem (i.e., the chromatic number problem with the number of colors fixed at 4) is NP-complete. However, the 4-coloring problem for planar graphs is in P.

# Answer
> 5 votes
What is wrong with the reasoning is that you are placing additional restrictions and thus simplifying the class of problems. Even if each of the conditions alone grants $NP$-completeness, their intersection may make the result simpler.

What would work as a minimal example of the fault in the reasoning for me:

1) It takes an infinite time to list all primes.

2) It takes an infinite time to list all even numbers.

3) It does *not* take an infinite time to list all even primes.

# Answer
> 5 votes
Intuitively, graphs with property $X$ and graphs with property $Y$ can be very different from graphs with both properties $X$ and $Y$.

For example, consider the following (this is very much along the lines of Yuval's answer). Deciding if there is a dominating set on at most $k$ vertices is NP-complete for bipartite graphs. The same is true for claw-free graphs. But this is certainly not true for bipartite claw-free graphs, as each such graph is a collection of disjoint cycles and paths.

---
Tags: np-complete, proof-techniques
---


# Question
Title: Prove Undecidability Without Using Rice's Theorem
Show that checking if a TM accepts some input string of length greater than some constant $k$ is undecidable. Here the constant $k$ is publicly known.

I tried solving this problem by trying to reduce the "Acceptance Problem" i.e. the problem where we have to check whether a TM $M$ accepts a string $w$ or not.

One idea I had was that we can modify the input $M$ to $M'$ such that $M'$ simply increases the length of the string to become greater than $k$ but that is wrong since by input we strictly mean what was provided and any thing that the TM does cannot be considered as part of the input.

How can I solve this?

# Answer
So the question is, *for a particular constant $k$, is there a TM which decides on input $\langle M\_i \rangle$ whether there exists a string $w$ with $|w|\geq k$ such that $M\_i$ halts on input $w$?* Your reduction is almost correct, let me show you: Suppose that this problem is decidable, then the acceptance problem is decidable.

If the problem is decidable, then if you wanted to know whether TM $A$ accepts $w$, you could build a machine that accepts $1^kw$ only if $A$ accepts $w$, and accepts no other string, and then you would ask your question about that Turing Machine. Let me say this with more detail.

Let $BT$ (for Banach Tarski) be the Turing Machine that decides the problem you describe, and suppose we want to know whether some TM $A$ halts on input $w$ with $|w|\<k$. Then we construct a TM $H\_{A,w}$ as follows: $H\_{A,w}$ checks whether the input is $1^kw$, i.e. $w$ padded at the beginning with $k$ ones (so $w$ is "hard-coded" into this machine). If not, it stops. If the input is $1^kw$, then it moves to the first symbol of $w$ and simulates $A$. Does $H\_{A,w}$ accept any input longer than $k$? If so, then it accepts $1^kw$, because that is the only string it could possibly accept. If it accepts $1^kw$, then $A$ accepts $w$, because we were simulating $A$ on $w$. If it accepts $1^kw$, then you could ask $BT$ the question you describe about $H\_{a,w}$, i.e. run $BT$ with input $H\_{A,w}$. If it returns yes, then $A$ accepts $w$. If not, not.

We have now provided a reduction from the Acceptance Problem to your problem. But we know that the Acceptance Problem is undecidable! So it cannot be that your problem is decidable, because then the Acceptance Problem would be decidable. $\square$
> 2 votes

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


title: Why are loops faster than recursion?

text:
# Question
Title: Why are loops faster than recursion?
In practice I understand that any recursion can be written as a loop (and vice versa(?)) and if we measure with actual computers we find that loops are faster than recursion for the same problem. But is there any theory what makes this difference or is it mainly emprical?

# Answer
The reason that loops are faster than recursion is easy.
A loop looks like this in assembly.

```
mov loopcounter,i
dowork:/do work
dec loopcounter
jmp_if_not_zero dowork

```

A single conditional jump and some bookkeeping for the loop counter.

Recursion (when it isn't or cannot be optimized by the compiler) looks like this:

```
start_subroutine:
pop parameter1
pop parameter2
dowork://dowork
test something
jmp_if_true done
push parameter1
push parameter2
call start_subroutine
done:ret

```

It's a lot more complex and you get at least 3 jumps (1 test to see if were done, one call and one return).
Also in recursion the parameters need to be set up and fetched.
None of this stuff is needed in a loop because all the parameters are set up already.

Theoretically the parameters could stay in place with recursion as well, but no compilers that I know of actually go that far in their optimization.

**Differences between a call and a jmp**
A call-return pair is not very much more expensive then the jmp. The pair takes 2 cycles and the jmp takes 1; hardly noticeable.
In calling conventions that support register parameters the overhead for parameters in minimal, but even stack parameters are cheap **as long as the CPU's buffers do not overflow**.
It is the overhead of the call setup dictated by the calling convention and parameter handling in use that slows down recursion.
This is very much implementation dependent.

*Example of poor recursion handling* For example, if a parameter is passed that is reference counted (e.g. a non const managed type parameter) it will add a 100 cycles doing a locked adjustment of the reference count, totally killing performance vs a loop.
In languages that are tuned to recursion this bad behavior does not occur.

**CPU optimization**
The other reason recursion is slower is that it works against the optimization mechanisms in CPU's.
Returns can only be predicted correctly if there are not too many of them in a row. The CPU has a return stack buffer with a (few) handfuls of entries. Once those run out every additional return will be mispredicted causing huge delays.
On any CPU that uses a stack return buffer call based recursion that exceeds the buffer size is best avoided.

**About trivial code examples using recursion**
If you use a trivial example of recursion like Fibonacci number generation, then these effects do not occur, because any compiler that is 'knows' about recursion will transform it into a loop, just like any programmer worth his salt would.
If you run these trivial examples in a enviroment that does not optimize properly than the call stack will (needlessly) grow out of bounds.

**About tail recursion**
Note that sometimes the compiler optimizes away tail recursion by changing it into a loop. It is best to only rely on this behavior in languages that have a known good track record in this regard.
Many languages insert hidden clean up code before the final return preventing the optimization of tail recursion.

**Confusion between true and pseudo recursion**
If your programming environment turns your recursive source code into a loop, then it is arguably not true recursion that is being executed.
True recursion requires a store of breadcrumbs, so that the recursive routine can trace back its steps after it exits.
It is the handling of this trail that makes recursion slower than using a loop. This effect is magnified by current CPU implementations as outlined above.

**Effect of the programming environment**
If your language is tuned towards recursion optimization then by all means go ahead and use recursion at every opportunity. In most cases the language will turn your recursion into some sort of loop.
In those cases where it cannot, the programmer would be hard pressed as well. If your programming language is not tuned towards recursion, then it should be avoided unless the domain is suited towards recursion.
Unfortunately many languages do not handle recursion well.

**Misuse of recursion**
There is no need to calculate the Fibonacci sequence using recursion, in fact it is a pathological example.
Recursion is best used in languages that explicitly support it or in domains where recursion shines, like the handling of data stored in a tree.

> I understand any recursion can be written as a loop

Yes, if you are willing to put the cart before the horse.
All instances of recursion can be written as a loop, some of those instances require you to use an explicit stack like storage.
If you need to roll your own stack just to turn recursive code into a loop you might as well use plain recursion.
Unless of course you've got special needs like using enumerators in a tree structure and you don't have proper language support.
> 19 votes

# Answer
These other answers are somewhat misleading. I agree that they state implementation details that can explain this disparity, but they overstate the case. As correctly suggested by jmite, they are implementation-oriented toward *broken* implementations of function calls/recursion. Many languages implement loops via recursion, so loops are clearly not going to be faster in those languages. Recursion is in no way less efficient than looping (when both are applicable) in theory. Let me quote the abstract to Guy Steele's 1977 paper Debunking the "Expensive Procedure Call" Myth or, Procedure Implementations Considered Harmful or, Lambda: the Ultimate GOTO

> Folklore states that GOTO statements are "cheap", while procedure calls are "expensive". This myth is largely a result of poorly designed language implementations. The historical growth of this myth is considered. Both theoretical ideas and an existing implementation are discussed which debunk this myth. It is shown that the unrestricted use of procedure calls permits great stylistic freedom. In particular, any flowchart can be written as a "structured" program without introducing extra variables. The difficulty with the GOTO statement and the procedure call is characterized as a conflict between abstract programming concepts and concrete language constructs.

The "conflict between abstract programming concepts and concrete language constructs" can be seen from the fact that most theoretical models of, for example, the untyped lambda calculus, *don't have a stack*. Of course, this conflict is not necessary as the above paper illustrates and as is also demonstrated by languages who have no iteration mechanism other than recursion such as Haskell.

Let me demonstrate. For simplicity, I'll use an "applied" lambda calculus with numbers and and booleans, and I'll assume we have a fixed-point combinator, `fix`, which satisfies `fix f x = f (fix f) x`. All of this can be reduced to just the untyped lambda calculus without changing my argument. The archetypal way of understanding the evaluation of the lambda calculus is through term rewriting with the central rewrite rule of beta reduction, namely $(\lambda x.M)N \leadsto M\[N/x\]$ where $\[N/x\]$ means "replace all free occurrences of $x$ in $M$ with $N$" and $\leadsto$ means "rewrites to". This is just the formalization of substituting the arguments of a function call into the functions body.

Now for an example. Define `fact` as

```
fact = fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 1

```

Here's the evaluation of `fact 3`, where, for compactness, I'll use `g` as synonym for `fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1))`, i.e. `fact = g 1`. This doesn't affect my argument.

```
fact 3
~> g 1 3
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 1 3
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 1 3
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 1 3
~> (λn.if n == 0 then 1 else g (1*n) (n-1)) 3
~> if 3 == 0 then 1 else g (1*3) (3-1)
~> g (1*3) (3-1)
~> g 3 2
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 3 2
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 3 2
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 3 2
~> (λn.if n == 0 then 3 else g (3*n) (n-1)) 2
~> if 2 == 0 then 3 else g (3*2) (2-1)
~> g (3*2) (2-1)
~> g 6 1
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 6 1
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 6 1
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 6 1
~> (λn.if n == 0 then 6 else g (6*n) (n-1)) 1
~> if 1 == 0 then 6 else g (6*1) (1-1)
~> g (6*1) (1-1)
~> g 6 0
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 6 0
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 6 0
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 6 0
~> (λn.if n == 0 then 6 else g (6*n) (n-1)) 0
~> if 0 == 0 then 6 else g (6*0) (0-1)
~> 6

```

You can see from the shape without even looking at the details that there is no growth and each iteration needs the same amount of space. (Technically, the numeric result grows which is unavoidable and just as true for a `while` loop.) I defy you to point out the boundlessly growing "stack" here.

It seems the archetypal semantics of the lambda calculus already does what is commonly misnamed "tail call optimization". Of course, no "optimization" is happening here. There are no special rules here for "tail" calls as opposed to "normal" calls. For this reason, it's hard to give an "abstract" characterization of what tail call "optimization" is doing, as in many abstract characterizations of function call semantics, there is nothing for tail call "optimization" to do!

That the analogous definition of `fact` in many languages "stack overflows", is a failure by those languages to correctly implement function call semantics. (Some languages have an excuse.) The situation is roughly analogous to having a language implementation that implemented arrays with linked lists. Indexing into such "arrays" would then be an O(n) operation which doesn't meet the expectation of arrays. If I made a separate implementation of the language, that used real arrays instead of linked lists, you wouldn't say I've implemented "array access optimization", you would say I fixed a broken implementation of arrays.

So, responding to Veedrac's answer. Stacks are *not* "fundamental" to recursion. To the extent that "stack-like" behavior occurs during the course of evaluation, this can only happen in cases where loops (without an auxiliary data structure) would not be applicable in the first place! To put it another way, I can implement loops with recursion with exactly the same performance characteristics. Indeed, Scheme and SML both contain looping constructs, but both of them define those in terms of recursion (and, at least in Scheme, `do` is often *implemented* as a macro that expands into recursive calls.) Similarly, for Johan's answer, nothing says a compiler must emit the assembly Johan described for recursion. Indeed, nothing says a compiler can't emit *exactly the same* assembly whether you use loops or recursion. The only time the compiler would be (somewhat) *obligated* to emit assembly like what Johan describes is when you are doing something that isn't expressible by a loop anyway. As outlined in Steele's paper and demonstrated by the actual practice of languages like Haskell, Scheme, and SML, it is not "exceedingly rare" that tail calls can be "optimized", they can *always* be "optimized". Whether a particular use of recursion will run in constant space depends on how it is written, but the restrictions you need to apply to make that possible are the restrictions you'd need to fit your problem into the shape of a loop. (Actually, they are less stringent. There are problems, such as encoding state machines, that are more cleanly and efficiently handled via tails calls as opposed to loops which would require auxiliary variables.) Again, the only time recursion *requires* doing more work is when your code isn't a loop anyway.

My guess is Johan is referring to C compilers which have arbitrary restrictions on when it will perform tail call "optimization". Johan also is presumably referring to languages like C++ and Rust when he talks about "languages with managed types". The RAII idiom from C++ and present in Rust as well makes things which superficially look like tail calls, not tail calls (because the "destructors" still need to be called). There have been proposals to use a different syntax to opt-in to a slightly different semantics that would allow tail recursion (namely call destructors *before* the final tail call and obviously disallow accessing "destroyed" objects). (Garbage collection has no such issue, and all of Haskell, SML, and Scheme are garbage collected languages.) In a quite different vein, some languages, such as Smalltalk, expose the "stack" as a first-class object, in these cases the "stack" is no longer an implementation detail, though this doesn't preclude having separate types of calls with different semantics. (Java says it can't due to the way it handles some aspects of security, but this is actually false.)

In practice, the prevalence of broken implementations of function calls come from three main factors. First, many languages inherit the broken implementation from their implementation language (usually C). Second, deterministic resource management is nice and does make the issue more complicated, though only a handful of languages offer this. Third, and, in my experience, the reason most people care about, is that they want stack traces when errors occur for debugging purposes. Only the second reason is one that can be potentially theoretically motivated.
> 17 votes

# Answer
Fundamentally the difference is that recursion includes a stack, an auxiliary data structure you probably don't want, whereas loops do not automatically do so. Only in rare cases is a typical compiler able to deduce that you don't actually need the stack after all.

If you compare instead loops operating manually on an allocated stack (eg. through a pointer to heap memory), you'll normally find them no faster or even slower than using the hardware stack.
> 2 votes

---
Tags: time-complexity, recursion, loops
---


# Question
Title: Implications of Halting Problem being unsolvable?
I came across a confusing situation when reducing the Halting Problem (HP) to the Blank Tape Accepting Problem (BP).

We know that since HP can be reduced to BP, BP is decidable $\implies$ HP is solvable. By contrapositive, we get that if HP is undecidable, then BP is undecidable as well. But now this creates an issue.

BP is just a special case of HP where the input to HP is a Turing Machine and a blank tape. Also, HP is a harder version of BP since we can get all possible tapes as input. So, just because a harder problem is unsolvable, how can we conclude that the more general form is also unsolvable.

It might be possible that we have some TM that can solve BP but cannot solve HP.

I know that both BP and HP are undecidable, but my main question is that how can we conclude via reduction that BP $\implies$ HP?

# Answer
> 1 votes
I have a valid reduction below, but it is all very formal, and it's not the intuition I have for this kind of problem. When I consider, *is this problem decidable/NP-Complete/etc*, I frame it as a challenge: somebody says *I bet BP is decidable!*, and I reply *Oh yeah?! Well, if that were true, then I could solve HP!*. And then I show how I would do that: I suppose that BP is decidable, (i.e. I accept the challenge) and then I use that to solve HP. Granted, acknowledging this takes away some of your street cred, but it does work for me.

Here's a cheat sheet:

* Show a reduction $f$ so that $HP \leq\_f BP$: *Hey I bet HP is decidable!* Reply: *Oh yeah?! Then I can solve BP like $f$*
* Show that Indset is NP-Complete by reduction from 3Sat, i.e. $3Sat \leq\_f IndSet$: *Hey I bet IndSet is easy!* Reply: *Oh yeah?! Well if it were easy, then I could solve 3SAT like so! I would take my arbitrary 3SAT instance $\phi$ and transform with $f$ to an IndSet instance $f(\phi)$ and then we'll let you solve $f(\phi)$ with your supposedly fast IndSet algorithm!*

I hope that if these comments do not make you laugh, at least they help you internalize the notion of what a reduction is supposed to do, and how you are supposed to make one.

Now for a valid reduction. You have reduced HP to BP via a reduction $f$ (like the one I gave for your prevous question), so if somebody asked, *does $M$ halt on $w$?*, then you can reduce the HP instance $\langle M, w\rangle$ to the BP instance $A=f(M,w)$ (e.g. $A$ is a TM that simulates $M$ on $w$ given the blank tape), and ask your BP machine whether $A$ halts on the blank tape. So if BP were decidable, we would have an algorithm for HP, namely the one that I just described. But we don't. So BP is not decidable.

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


# Question
Title: Complexity of Hamiltonian path and clique problem
I came across this question. If we want to check if a graph contains both Hamiltonian path and clique. Would this problem be NPC.

I knew that clique contains a Hamiltonian path and both problems are NPC, but I am uncertain if something would be different if we check it in same time.

# Answer
In the clique problem we are required to determine if there exists a clique of a certain size (given as input), so the observation that every clique contains a Hamiltonian path won't help much (a graph $G$ with $n$ vertices may contain cliques of size $\<n$, but not have a Hamiltonian path).

$Clique=\left\\{\langle G,k\rangle | \hspace{1mm} G \text{ contains a clique of size }\ge k\right\\}$

$HPath=\left\\{G | \hspace{1mm} G \text{ contains a Hamiltonian path}\right\\}$

Since the instances to the problems are not of the same type, it isn't really interesting to talk about their intersection (which is empty), so what you probably have in mind is the set:

$L=\left\\{\langle G,k\rangle | \hspace{1mm} G \text{ contains a clique of size }\ge k \land G \text{ contains a Hamiltonian path}\right\\}$.

$L$ can be shown to be NP-complete using a simple reduction from $HPath$ (think about how to change the instance to the HPath problem, to an instance of $L$, without ruining the properties of the graph).
> 3 votes

---
Tags: complexity-theory
---


# Question
Title: why should I go for logistic regression?
I am a student working on a Database management project with a bit of Python coding involved. The project is about Review Analysis.Basically I am trying to read a review and determine how good or bad it is.

I have a file of good and bad words with its scores like :: good = 2, better =3,best=4;

By this , I have written a code for sentiment analysis of the review which gives me the score of the review considering every single word.

Since the range varied from - infinity to + infinity, I had to scale it down to a range of 0 to 1. A graphical representation must be done on this data; i.e. the score of review ,may it be from -infinity to +infinity or 0 to 1.

I was advised to go for logistic regression plot by my guide. Why logistic regression? Is there a better way?

# Answer
> 1 votes
If you want to know why your advisor advised you with that advise, you should ask your advisor why he advised you thus, as Yuval points out.

If you want to know what makes logistical regression a good method, it is because it takes as input a data set such as the one you have and it outputs a probability (distribution), which is precisely the input-output format you were looking forit; it is simple, widely available, easy to implement, and in practice, it turns out that they do a markedly good job at predicting real-world data. It is also the last step before curve-fitting turns into AI, because neural networks are really just logistic regression on steroids.

There are other methods because world of data analysis is big. You are looking for a classification model. For example, you can use a Bayesian learning algorithm, such as Naive Bayes or Pearl's algorithm. Weka is a freely available software toolkit with 100 (+/- 50) different classification algorithms. It is quite user-friendly. If your data set is large and complex enough, you can consider letting loose a true AI, such as a neural network, or a Deep Learning machine. All these things are freely available.

---
Tags: graphs, database-theory
---


# Question
Title: Decidablity with exponential number of solution
I am trying to understanding this. If a problem has exponential amount of candidate solutions, such as 2^2^n. Is this decidable? To my understanding, as long as its' verfiable, no matter how big the solutions there are, it's.decidable.

Thanks for clarity

# Answer
> 3 votes
If a problem has a *finite* number of possible solutions, then you can enumerate all the potential solutions, and if one of them is correct, halt. Otherwise, halt and reject after checking the last solution.

It does not matter how long this process takes, it may be exponential, or superexponential as in your example of $2^{2^n}$, the only thing that matters is that there is a way to enumerate all candidate solutions.

---
Tags: undecidability
---


# Question
Title: Extracting features for texture classification
I'm a beginner in the field of pattern recognition and computer vision. I'm working on a project right now to classify t-shirt patterns into three categories i.e. solids, stripes and checks. I have close up training images of the t-shirt images. A sample shirt image looks like this

I have looked at a bank of gabor filter features, but they are computationally expensive. It would of great help if someone could point me out in the general direction for working forward. Any help is appreciated.

EDIT - I found the solution in D.W.'s answer below, though my solution is not very good. I'm classifying solid patterns by counting the number of line segments in the image. If they fall below a certain number, I'm classifying them as solid. If not, I further classify them into stripes or checkered using HoG features and a linear SVM. The accuracy achieved was around 91%. It was a little low due to some misclassified samples in the training set.

# Answer
I suggest you try looking at some different simple features and filters, to look for ones that might be useful in distinguishing the shirts, and then feed these feature values into a machine learning algorithm. You can use a training set of images that you've hand-annotated to train the machine learning model.

For instance, one natural feature would be something that looks for short horizontal lines or vertical lines. You could use @Aky's suggestions, and then count the number of locations in the image where such a line has been detected. You could also try filtering your algorithm with an edge detector.
> 1 votes

# Answer
If it is important for you to get a high accuracy, then use a convolutional neural network (ConvNet). These ConvNets hold the state of the art for most visual recognition tasks. If your training set size is small, you should use a pretrained ConvNet as a feature extractor and then apply a support vector machine (SVM) on top of the extracted features.

I can recommend Keras as a good toolbox for ConvNets that is simple to use. You should be able to find a pretrained ConvNet for Keras by searching Google. VGG or ImageNet are names of well-performing ConvNets (particularly the former) so that is worth searching for.
> 3 votes

---
Tags: machine-learning, image-processing, pattern-recognition
---


# Question
Title: What mathematical background is enough to go through the entire Knuth's TAOCP?
I am an undergrad. I can do mathematics fine and am a lot more interested to explore.
I turned towards TAOCP as it is highly mathematically oriented so as to excel at maths and programming at the same time.
But I am stuck. I have only studied calculus, numerical analysis and probability (undergrad level) but the first few pages of the first volume itself is too difficult to get through.
Also, the problems are ranked according to their difficulty level. What all can I do to solve those problems? I really need to get better at mathematics.

What books(mathematics) should one read to be able to understand TAOCP? I am ready to go to a series of books just to get better at it.

Also, any suggestion(s) on how to learn/practice MIX(the TAOCP assembly)?

# Answer
If your only exposure to math is undergrad level calculus, numerical analysis, and probability, you probably don't want to start out with computer science by reading The Art of Computer Programming. This is not an easy set of books. They're also not the hardest books out there in computer science, but they definitely expect some kind of background in discrete math and algorithm analysis. I would start with an easier book, maybe Introduction to Algorithms (CLRS), which is also mathematical and treats its topic formally, but is designed for undergraduate students without previous background in the field. You should also get a more solid background in discrete math—topics such as combinatorics, recursion, Big O, number theory—as well as linear algebra. Knuth co-authored another book called Concrete Mathematics that might help with that.

Working through CLRS and Concrete Mathematics is probably enough to start TAoCP. The first thing you should do is work through the math in Volume 1 of The Art of Computer Programming. Knuth covers several of the topics in combinatorics and discrete math that will reappear in later volumes. However, he typically doesn't spend a ton of time introducing you to the math he uses. He doesn't assume you know everything, but he does dive in pretty quickly. I would solve a bunch of the easier exercises in each topic to get a grasp on it, and leave the harder exercises for a cold winter's evening.

As for MIX, I wouldn't even bother with it. Programming in assembly language is not a terribly useful skill today, and modern assembly languages look nothing at all like MIX because it was designed before CPU architectures had standardized, before everyone was using 32-bit (or 64-bit) binary computers and it was sometimes desirable to support decimal computers or computers with kooky word sizes. In recognition of this, Knuth created MMIX, a more modern-styled assembly language, and he's now porting all the MIX code in earlier books to MMIX. I would just ignore the fake assembly code completely. I found that trying to remember MIX's idiosyncrasies was an impediment to learning the high-level ideas behind algorithm; the pseudocode and the prose were much more helpful. If you want to learn about low-level programming, go learn about computer architecture, and maybe learn some MIPS or ARM assembly, but do it separately from your studies of algorithms; it's a huge topic in its own right, and you won't do yourself any service by trying to learn both at the same time.

If, however, you insist on learning MIX or MMIX, you can hunt down one of the simulators that let you actually run the code, and learn it like you would any other programming language: by figuring out what it can do and solving some simple exercises. (IIRC, the book even has some MIX exercises that you can complete.) Again, though, I wouldn't. As much as I love the books, they were created in an earlier time, and some parts haven't aged well. MIX is one of those things.
> 8 votes

---
Tags: algorithms, education, mathematical-foundations
---


# Question
Title: Find cell neighbors of a given edge in a 2D grid
In the figure below, cells are labeled row wise, and edges are labeled counter clockwise. That is, vertices 1' and 2' form edge #1, vertices 2' and 5' form edge #2, vertices 5' and 8' form edge #7, etc.

* vertices 1' and 2' form edge #1
* vertices 2' and 5' form edge #2
* vertices 4' and 5' form edge #3
* vertices 1' and 4' form edge #4
* vertices 2' and 3' form edge #5
* vertices 3' and 6' form edge #6
* vertices 6' and 5' form edge #7
* vertices 5' and 8' form edge #8
* vertices 7' and 8' form edge #9
* vertices 4' and 7' form edge #10
* vertices 6' and 9' form edge #11
* vertices 8' and 9' form edge #12

> Question: given an edge number (and/or the vertices that form it), is there a way to algorithmically compute its corresponding cell neighbors?

# Answer
> 1 votes
There's no need for any special algorithm. There are only 12 edges, so it's enough to simply use a switch statement with 12 cases. Or, you can use 12 if statements. Any of these will have $O(1)$ running time, since there are only finitely many cases, so they are (asymptotically) as good as any other "algorithm".

---
Tags: computational-geometry, search-algorithms
---


# Question
Title: Looking for a use case of a $k$-$d$ tree with a norm other than $L^2$
In Python's implementation of $k$-$d$ tree it is possible to manually change the norm used for computing distances from $L^2$ to $L^p$.

When would one use a norm other than $L^2$ in a $k$-$d$ tree?

# Answer
For example, when you want to report all the points in distance $r$ from a query point under the $L\_1$ norm, which is a natural case. See https://en.wikipedia.org/wiki/Taxicab\_geometry.
> 2 votes

---
Tags: data-structures, computational-geometry
---


title: Hill Climbing Search - 8 queens

text:
# Question
Title: Hill Climbing Search - 8 queens
In that picture, I am having trouble counting why there are 17 pairs of queens. I can only count 14. I counted 10 diagonal pairs and 5 horizontal pairs. Can someone please elaborate on this?

I am not exactly sure how it was numbered, but I believe the numbers on the board represent the new number of pairs that are attacking each other if a queen in that column were to move to that square.

# Answer
```
5 - Horizontal attacks
9 - Diagonal attacks of slope -1
3 - Diagonal attacks of slope +1
-
Total 17 pairs of queens attacking each other.

```

And yes, the numbers in each square correspond to number of attacking pairs of the queen if the queen in the corresponding column is moves to that location.
> 1 votes

---
Tags: search-algorithms
---


# Question
Title: Satisfiability 2 CNF-SAT to 3 CNF-SAT transformation/reduction
**This Reduction is trying to prove that 2CNF-SAT is also NP-Complete, after proving 3CNF-SAT is NP-Complete.**

If we had a reduction that given an instance of 2CNF-SAT with k clauses over 'i' number of variables, and we create an instance of 3CNF-SAT with 2n clauses by introducing for clause i a new variable y; then for the i'th 2SAT clause we generate two 3SAT clauses. **This is a reduction from a 2CNF-SAT to a 3CNF-SAT.**

Is this not a correct reduction because all of the other clauses after the transformation are still 2CNF-SAT except for the i'th clause?

# Answer
It looks like you are trying to prove either that 2CNF-SAT is NP-Complete, or that 3CNF-SAT has a polynomial algorithm, by reducing 2SAT to 3SAT. But that's not how it goes! If you're trying to do what I think you're trying to do, then you should reduce 3SAT to 2SAT. Unfortunately, if you can reduce 3SAT to 2SAT, then that would imply P=NP, so that's probably very hard.

It's very easy to get confused about which way a reduction should go, and how you should make one. Please read my answer to this related question: Implications of Halting Problem being undecidable, in particular the 'cheat sheet' section, where I try to clear up some confusion around the topic, and let me know if you have questions after reading that, then I might edit this answer tailored specifically to whatever question you have afterwards.
> 2 votes

---
Tags: reductions, satisfiability
---