# Question
Title: does cpu time reflect BigO time complexity
## QUESTION

**does CPU time reflect Big O time complexity?**

### WHAT I MADE

I implemented two Fibonacci functions in C programming language. The former has recursive behaviour while the latter has iterative behaviour.

I found out that the worst case scenario for the recursive version is exponential time (i.e. $2^n$) and linear time for the iterative one - since I have a simple loop within.

I then computed the CPU time for both the version using the `time.h` C library.

### WHAT I EXPECT

I expect those CPU values to be somehow related with that time complexity. Generally speaking, I expect way larger CPU times for the recursive version.

### WHAT I GOT

I got the foregoing plot using MATLAB (that is a loglog plot of cpu times as function of $n$).

Seems like the CPU time for the recursive function has an exponential behaviour - that is what I was expecting. Though, I'm not completely sure about CPU time for the iterative version since that function does not look like this one (section log-log graphs).

I'd like to answer myself without doubts but I'm quite newbie.

# Answer
> 3 votes
There are really two questions here:

1. How does CPU time relate to time complexity?
2. Can you use a plot of CPU time to understand time complexity?

Let me answer each in turn.

## Time complexity

Time complexity refers to the *total time* it takes for the algorithm to finish.

If by "CPU time" you just mean the time it took for this particular program to run, excluding the time for other programs or the operating system, then yes, these are the same.

If by "CPU time" you meant the time spent on computation but not time spent on I/O, then it might or might not match what is meant by time complexity. In practice, I/O is often slower than computation -- maybe by a significant factor. Normally, in theoretical work where we measure time complexity, we don't try to account for that distinction, as it's "only a constant factor".

## The plot heuristic

Plotting the running time as a function of the size of the input can definitely be a useful *heuristic* to form an *informed guess* about what the asymptotic time complexity of the an algorithm is. It's often a good guide. However, be warned that it is not 100% reliable: there are some cases where it can be misleading.

I'd like to refer you to the following three questions for more on this topic:

## Bottom line

In summary: yes, basically, plotting CPU time as a function of input size can be a helpful way to assess asymptotic time complexity, as long as you keep in mind the caveats.

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


title: Semi-Thue system, which terminates

text:
# Question
Title: Semi-Thue system, which terminates
I observed that with rewrite rules:

$abb \rightarrow bab $

$baa \rightarrow aba $

Every derivation ends, moreover, if there is same amount of $a$'s and $b$'s in input, then derivation ends in $(ab)^\*+(ba)^\*$.

Why do these two properties hold?

# Answer
> 4 votes
Consider the potential function $$ \Phi(w\_1 \ldots w\_n) = \sum\_{i=2}^n 2^i 1\_{w\_i = w\_{i-1}}. $$ Applying one of the rewrite rules always decreases the potential: if we change $abb$ to $bab$ at positions $i,i+1,i+2$, then we lost $2^{i+2}$ and might have gained $2^i$. Since the potential is non-negative, every derivation ends.

Suppose now that the initial word contained an equal number of $a$'s and $b$'s. The same is true for the final word, since the rules don't change the number of $a$'s or $b$'s. It therefore suffices to prove that any word that has $n$ letters $a$ and $n$ letters $b$, and doesn't contain $abb$ or $baa$, has the form $(ab)^n$ or $(ba)^n$. We prove this by induction.

The base cases $n=0,1$ are trivial, so suppose that $n \geq 2$. Assume without loss of generality that the final word ends with $b$. It must have a suffix of the form $ab^k$ (since it contains at least one $a$). Since it contains no $abb$, we must have $k = 1$. Remove the suffix $ab$ and apply induction to deduce that the word is either $(ab)^n$ or $(ba)^{n-1}ab$. The latter case cannot happen since it contains $baa$, and so the word must be $(ab)^n$.

We can slightly strengthen this result by noticing that the rewrite rules never change the final letter of the word. So we reach $(ab)^\*$ if the original word terminated with $b$, and reach $(ba)^\*$ otherwise.

---
Tags: term-rewriting
---


# Question
Title: how to understand time complexity from a plot?
This is my first question here. I'm not a CS at all, so it might be quite trivial.

I have written a program in C where I allocate memory to store a matrix of dimensions *n-by-n* and then feed a linear algebra subroutine with. I'm having big troubles in understanding how to identify time complexity for these operations from a plot. Particularly, I'm interested in identify how CPU time scales as a function of *n*, where *n* is my size.

To do so, I created an array of n = 2, 4, 8, ..., 512 and I computed the CPU time for both the operations. I repeated this process 10000 times for each *n* and I took the mean eventually. I therefore come up with a second array that I can match with my array of n.

I've been suggested to print in double logarithmic plot, and I read in Wolfram that, using this way, *"powers shows up as a straight line"*. This is the resulting figure (*dgesv* is the linear algebra subroutine I used).

Now, I'm guessing that my time complexity is $O(a^n)$ since I get straight lines for both my operations (I do **not** take into consideration the red line). I saw the shapes differences between, say, linear complexity, logarithmic complexity etc. But I still have doubts if I should say something about the time complexity of *dgesv*, for instance. I'm sure there's a way that I don't know at all, so I'd be glad if someone could help me in *understanding how to look at this plot properly*.

# Answer
No, you can't prove asymptotic properties from finite samples. See here and here for more on this.

Plots *can* give you hints towards the real properties of the running-time function, though, which you can then go ahead and try to prove.
> 1 votes

---
Tags: algorithms, asymptotics, runtime-analysis, experimental-analysis
---


# Question
Title: On computing the factor-free basis of a regular language
The problem is as follows.

**Background:** Given an alphabet $\varSigma$. If $u,v,w,x \in \varSigma^\*$ and $w=uxv$ then $x$ is a factor (substring or infix) of $w$. A language $L$ is factor-free if, for all distinct words $x, y \in \varSigma^\*$, $x \in L$ and $y \in L$ imply that $x$ and $y$ are not factors of each other. Given a regular language $L$, we define $basis(L)$ as $L' \subseteq L$ such that $L'$ is factor-free and for every word $x \in L$ there exists a word $y \in L'$ such that $y$ is a factor of $x$.

**Question:** Is $basis(L)$ efficiently computable, given (say) a DFA for $L$? If so, do you have any ideas about the algorithm that computes it?

**Example:** Consider the language $L=\\{ab,abab,ababab,abababab,\ldots\\}=\\{(ab)^i|i\>0\\}$. Then, $basis(L)=\\{ab\\}$.

Let me give you my insights on the subject, it may help.

It has been proven that checking factor-freeness is tractable for regular languages1.

Also, in a trivial way, $L=basis(L)$ if $L$ is factor-free. This leads to the fact that $basis(L)$ is not always finite. Because for an infinite factor-free language the basis is also infinite. Here is an example from the Handbook of Formal Language Theory (vol. 1, p. 19): $L=\\{ba^ib | i \> 0\\}$.

For finite languages, it seems that a basis always exists because a language $L$ is either factor-free thus $basis(L)=L$ or not factor-free. The latter necessarily means that $L$ contains a sublanguage $L'$ for which some words are factors of each others, consequently $basis(L)=basis(L') \cup (L \setminus L')$.

1 Han YS, Wang, YJ , Wood, D. Infix-free regular expressions and languages. International journal of foundations of computer science. 2006.

# Answer
> 3 votes
A language $L$ is infix-free if $$ L \cap (\Sigma^+L\Sigma^\* \cup \Sigma^\*L\Sigma^+) = \emptyset. $$ (This deep observation, which I made independently, appears in reference \[1\] to the paper you cite.) This gives a simple algorithm for deciding whether a regular language $L$ (given as a DFA, NFA, or regular expression) is infix-free.

Similarly, the basis of $L$ is $$ L \setminus (\Sigma^+L\Sigma^\* \cup \Sigma^\*L\Sigma^+). $$ This gives a simple algorithm for computing the basis of a regular language (as a DFA, NFA, or regular expression).

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


# Question
Title: Can we express the program to find last element of a list as a catamorphism?
So I've got a bit of category theory under my belt, and I am reading a few papers about calculating functional programs. I've expressed programs like summing a list as a catamorphism, and I've fused some catamorphisms, too.

I thought it might be interesting to see how far I could take what I now know about catamorphisms by applying it to 99 Haskell Problems . It turns out that I can't take it very far at all because the first problems have me stumped.

I'm aware that the old saying "if the only tool you have is a hammer, then every problem looks like a nail" applies to me. But if we are asked to provide a program that finds the last element of a list, can we express that program as a catamorphism? If not, then why?

Thanks in advance!

# Answer
> 5 votes
I'm a bit old-fashioned so I'll let Erik Meijer do most of the talking here.

Let's look at the classical definition of a list-catamorphism. More commonly, we call these functionals "folds" over some operator, because you can visualize it as bamboo scroll being folded into each other. (Except in this analogy, when we fold one piece into the other, we're left with a single piece).

Given a list over type $\alpha$ to fold over, an operation $\otimes : \alpha \times \beta \to \beta$, and an initial value $b : \beta$, we can define the $(b, \otimes)$ induced catamorphism $h : \alpha \textrm{ list} \to \beta$ as \begin{align\*} h(\[\]) &= b \\ h(a :: l) &= a \otimes h(l) \end{align\*}

In Meijer's (in)famous notation, we'll say that $h = (\\!|b, \otimes|\\!)$. We can do this because every catamorphism is uniquely determined by such a pair, and every pair defines a catamorphism, so we have an equivalent representation.

So let's now see whether there's some pair $(\\!|b, \otimes|\\!)$ such that the induced catamorphism finds the last element of the list. First, let us define the `last` function. You'll immediately notice a problem: \begin{align\*} \textrm{last}(\[\]) &= \bot \\ \textrm{last}(a :: l) &= \dots \end{align\*}

`last` is a partial function! Catamorphisms are by definition total functions, so we immediately see that a straightforward translation is impossible.

However, if we're allowed to use isomorphic representations, then we can consider the `Maybe`/`Optional`/`Point` functor that designates a special $\bot$ point that can be treated as the least element of the partial order. Let's say that the pointed type $\beta\_{\bot}$ is either $\textrm{Some } b : \beta\_{\bot}$ or $\bot\_{\beta}$. The question now is whether there is some $(\\!|a\_{\bot}, \oplus|\\!) : \alpha \textrm{ list} \times \alpha\_{\bot} \to \alpha\_{\bot}$ that models the `last` function. Some equational reasoning will quickly give a derivation

* If $$ \textrm{last}' = (\\!|a\_{\bot}, \oplus|\\!) : \alpha \textrm{ list} \times \alpha\_{\bot} \to \alpha\_{\bot} $$ then $a\_{\bot} : \alpha\_{\bot}$ and $\oplus : \alpha \times \alpha\_\bot \to \alpha\_\bot$.
* Expanding the definition of a catamorphism out, we have \begin{align\*} \textrm{last}'~\[\] &= a\_{\bot} \\ \textrm{last}'(a :: l) &= a \oplus (\textrm{last}' ~l) \end{align\*}
* The true `last` function ought to satisfy the equations \begin{align\*} \textrm{last} ~ \[\] &= \bot\_{\alpha} \\ \textrm{last}(a :: l) &= \textrm{match } \textrm{last}~l \textrm{ with} \\ &~~~~~ \mid~ \bot \to \textrm{Some } a \\ &~~~~~ \mid~ \textrm{Some } a' \to \textrm{Some } a' \end{align\*}

Equating `last'` and `last` then gives \begin{align\*} a\_\bot &= \bot\_{\alpha} \\ a \oplus a' &= \textrm{match } \textrm{last}~l \textrm{ with} \\ &~~~~~ \mid~ \bot \to \textrm{Some } a \\ &~~~~~ \mid~ \\\_ \to a' \end{align\*}

which uniquely defines the pointed `last'` function as a catamorphism. To get the partial `last` function, just compose it with the partial function $\textrm{get}\_{\alpha\_\bot} : \alpha\_\bot \to \alpha$.

Now, this proposal of returning to partiality has an interesting structure: $$ \textrm{last} = \textrm{get}\_{\alpha\_\bot} \circ (\\!|\bot\_{\alpha}, \oplus|\\!) $$

The astute reader may point out that this seems to be of a form that is amenable to the catamorphic fusion law. And you are right, it has the correct syntactic form. To quote Meijer again, the fusion law is the extensional (since it is (usually) not an intensional reduction rule) equality that $$ f \circ (\\!|a, \otimes |\\!) = (\\!|b, \oplus |\\!) \Leftarrow b = f~a \wedge f~(x \otimes x') = x \oplus (f ~ x') $$ Unfortunately, neither of these conditions hold. In particular, $\textrm{get}\_{\alpha\_\bot} \bot$ is not valid (since get is partial at $\bot$).

---
Tags: functional-programming
---


# Question
Title: Determine whether a TM visits each of its states exactly once during computation
> (Decidable or not?) Formulate the following problem as a language: Given a Turing machine $M$ and a string $w$, determine whether $M$ visits each of its states exactly once during the computation with input string $w$. Prove your answer.

So the problem above is what I am trying to solve. I am looking for a general direction to solve this so far this is what I am thinking but I may be completely wrong.

My Thoughts: This problem is decidable because the Turing machine can have a list of all possible paths ,$E^\*$, and we could check $E^\*$ to ensure that each state was visited once and only visited once within the computation. However this doesn't seem like nearly enough and I am not sure what direction to head.

# Answer
> 1 votes
Hint: If a Turing machine has $m$ states and it visits each of them exactly once, then it terminates after $m$ steps.

---
Tags: turing-machines, undecidability, decision-problem
---


# Question
Title: Doesn't a quantum algorithm being deterministic contradict the superposition principle?
How can the EQP quantum complexity class exist? I mean, doesn't the superposition principle imply it is not possible to know with probability 1 whether a quantum algorithm will return a solution?

For if a quantum computer’s state is in superposition, quantum measurement implies the state we obtain when we read the computer's state is random - with the probabilty we will obtain any particular state being based on its probability amplitude at the time of measurement. Thus unless some state has probability amplitude 1 (which would mean the system wasn't in superposition, so can't have been a quantum algorithm, as any quantum algorithm must use superposition), we cannot know whether we will obtain a solution state at any quantum computation's completion.

# Answer
> 4 votes
If the algorithm has no error, then the system is not in a superposition *when it is measured*, but it is possible it was in a superposition during the computation, after which it was cleverly interfered constructively on the right answer(s) and interfered destructively on the wrong one(s).

For example, Deutsch's algorithm has this property, the way he initially introduced it: the system is put into a superposition without entanglement, then it is operated on to produce a superposition in which the two qubits are entangled, and then it is operated on some more so that the final measurement is deterministic.

One way to understand why some deterministic quantum algorithms use superposition is to see that an algorithm is a map from input vectors to output vectors. A good algorithm goes from the input vector to the output vector via the shortest path. The only steps that it can take are elementary gates (Hadamard, CNOT, X, Y, Z, etc.). Sometimes, the shortest path happens to be one in which the intermediate states are in a superposition, even if the final state is not. If this is the case, if all shortest paths involve superposition, then this problem is solvable more quickly by a quantum computer than by a classical computer, which cannot take those paths.

# Answer
> 1 votes
This is a bit like asking "doesn't the ability to rotate objects prevent me from ever getting them right-side-up again?".

Yes, if you initialize a qubit into the $|\text{Off}\rangle$ state and (for example) rotate it by 180 degrees around the X+Z axis (i.e. apply a Hadamard gate) the qubit ends up in the state $\frac{1}{\sqrt 2}|\text{Off}\rangle + \frac{1}{\sqrt 2}|\text{On}\rangle$. But you know what happens if you apply *another* Hadamard? Yeah, you rotate by another 180 degrees for a total of 360. You end up right back where you started, in the $|\text{Off}\rangle$ state.

A physical experiment that nicely demonstrates this principle is the Mach–Zehnder interferometer. Beam splitters create superpositions of paths, but they can also put them back together:

---
Tags: complexity-theory, quantum-computing, probabilistic-algorithms
---


# Question
Title: Two labelled transition systems feeding each other
Assume we have two LTSs, say DFA with labels over the transitions (though the question can be generalized to more sophisticated automatons), define the input to each system to be as usual just the input word, and define the output of each system to be the sequence of labels of visited transitions.

Now assume that the two systems are wired directly to each other: every output letter (i.e. non-epsilon transition) in system A becomes instantly an input letter to system B, and output of B becomes input of A.

I'm looking for some analysis of this construction. Maybe anyone happen to be familiar with research topic that discuss such?

EDIT: Special case - if we have labelled pushdown automatons (context free grammars), then is the combined system as powerful as a two-pushdown machine (Turing powerful)? Or is strictly weaker?

# Answer
Transducers, or finite automata with output, are very powerful when they can be iterated. After all a step of a Turing machine on a tape (or better a instantaneous description, with the state assumed to be marked on the tape) is just a simple local rewrite, and iterating that is a computation.

With two transducers $T\_M$ and $T\_e$ we can mimick that iteration. Assume $T\_e$ just echos what it reads. $T\_M$ starts on empty input by writing the initial configuration and marker $\\#w\_0$, which it then gets as input via $T\_e$. Then $T\_M$ computes the next configuration of TM $M$ and writes $\\#w\_2$, etcetera. In that way $T\_M$ writes a complete computation of $M$ in the form $\\#w\_1\\#w\_2\\#w\_3\dots$. If TM $M$ cleans its tape before halting, and if $T\_M$ stops (and accepts) when it reads empty tape with halting state of $M$, the system has a halting computation iff the TM has one. Quite powerful.

In a simpler example $T$ gets a string $a^n\\#$ as input. If $n$ is even it halves $n$ and outputs $a^{n/2}\\#$, if $n$ is odd $T$ blocks (halts in a negative state, or runs off in a never halting sequence of epsilon moves), except when $n$ equals $1$, then it will accept and halt. Observe that when the output if $T$ is fed back as input, the system will only halt when the initial value of $n$ was a power of two.

In fact, what is obtained is a so-called fixed point language of the transducer $T$: strings $w$ such that $T$ writes $T$ on input $w$. If I recall well, the fixed point languages of \`rational functions' (finite state transducers that are not necessarily deterministic, but have only one output on a given string) are co-context-free, complements of context-free languages. Prefix and equality languages of rational functions are co-context-free, Information Processing Letters, 1988, doi:10.1016/0020-0190(88)90167-6,
> 2 votes

---
Tags: automata
---


# Question
Title: Reducing "multiple satisfiability" to normal SAT
I have to prove the NP-completeness of the following set: QUADRUPLE-SAT:={F is Formula in CNF|F has at least 4 satisfying interpretations}

My idea so far has been to reduce the problem to the normal SAT by constructing a new formula, copying the original formula 4 times and using a new set of literals in every copy, then adding clauses to ensure that the 4 sets of literals are pairwise differently interpreted (there is at least 1 literal which is flipped). Such a formula is easy to find, I'm unable to get it to CNF though.

I might also be on the completely wrong track on this one, if you know another NP-complete problem this could be reduced to more easily, that would be great as well.

# Answer
> 0 votes
CNF-SAT can be reduced to QUADRUPLE-SAT by adding two new variables, $x\_1$ and $x\_2$, and adding the following CNF clauses.

$(x\_1 \lor \lnot x\_1)$

$(x\_2 \lor \lnot x\_2)$

Because $x\_1$ and $x\_2$ can take any value and not affect satisfiability, if the original formula had at least one solution then the new formula will have at least four. And if the original formula had no solutions then the new formula will still have none.

Since CNF-SAT is NP-complete, then this reduction to QUADRUPLE-SAT proves the NP-completeness of the QUADRUPLE-SAT.

---
Tags: complexity-theory, logic, satisfiability
---


title: Contingent sentences can always be true

text:
# Question
Title: Contingent sentences can always be true
I have a question about contingent sentences. To my knowledge, contingent sentences are sentences that are neither tautologies nor contradictions.

In a textbook I read that a sentence might always be true and still be contingent.

The example given was as follows: If there never were a time when the universe contained fewer than seven things, it follows that the sentence "At least seven things exist" would always be true. Yet the sentence is contingent; its truth isn't a matter of logic. There is no contradiction in considering a possible world in which there are less than seven things.

Could someone please explain why this is the case? As well as explain the example to me?

# Answer
In mathematical logic - the discipline of logic that has interested computer scientists the most - there is a difference between proof-theoretic truth and model-theoretic truth.

Beyond metaphor (of which we are by no means innocent), neither has anything to do with reality, experienced or imagined, and with the idea of truth that is dealt with by empirical scientists, natural philosophers and historians, to which you allude in your question.

Contingent is, to us, another name for a sentence that is satisfiable, but not a tautology. This has to do with its truth equivalence being dependent on the axioms and rules of inference available (proof-theoretic aspect), or on the valuation of its symbols (model-theoretic aspect).

Gödel showed us that these two aspects do not necessarily go together very well, though. Caution is advised.
> 5 votes

---
Tags: logic, propositional-logic, logical-validity
---


# Question
Title: How to modify semantic actions when removing left-recursion from a grammer
Is there any algorithm that tells us how to modify semantic actions associated with a left-recursive grammar? For example, we have the following grammar, and its associated semantic actions:

$ S \rightarrow id = expr $ { S.s = expr.size }

S $\rightarrow$ if expr then $S\_1$ else $S\_2$ { $S\_1.t = S.t + 2; $ $S\_2.t = S.t + 2;$ $S.s = expr.size + S\_1.size + S\_2.size + 2;$ }

S $\rightarrow$ while expr do $S\_1$ { $S\_1.t = S.t + 4;$ $S.s = expr.size + S\_1.s + 1;$ }

S $\rightarrow$ $S\_1$ ; $S\_2$ {$S\_1.t = S\_2.t = S.t;$ $S.s = S\_1.s + S\_2.s; $ }

Clearly the non-recursive version of the grammer is:

S $\rightarrow$ id = expr T

S $\rightarrow$ if expr then $S\_1$ else $S\_2$ T

S $\rightarrow$ while expr do $S\_1$ T

T $\rightarrow$ ; $S\_2$ T

T $\rightarrow$ $\epsilon$

But we also need to change the semantic actions accordingly. Any ideas how this can be done?

# Answer
From what I have discovered, there is no general technique to modify the semantic actions while removing left-recursion. Instead, the best method is to take a representative example, draw its parse tree, and then checking which semantic actions give us the same result as the previous grammar.
> 0 votes

# Answer
I have a partial solution (I'm seeking a general one). If your grammar has NO epsilon productions, then no nonterminals are nullable. This means the algorithm to remove left recursion goes through (though it introduces epsilon productions).

If you add semantic actions of the form Action (label, count) which recognise the empty string, and use a shift/reduce parser, and examine all\** alternatives, there is no need at all to reorganise the parse tree. When parsing, if a terminal is recognised it pushes an attribute onto the parser stack, this is a shift action. When an action is encountered, it pops N values off the stack, and pushes a node with the specified label and the values popped off the stack, in reverse, as children. This is the reduce action.

The parser must propagate the current position and parser stack, and the operations of shift and reduce should be done with functional updates not mutations. It is then clear than refactoring the grammar does not change the sequence of shift and reduce actions, so the resultant parse tree is invariant under refactoring.

This means if you generate an AST rather than a parse tree you must refer to the attributes by number. The machinery works because the parser stack and control stack are decoupled and refactoring only changes the control stack. The difficulty is that the grammar must be epsilon free initially because the Reduce action terms are themselves nullable.

\** The assumption all alternatives are examined is made so that the order of consideration is immaterial. Although refactorings produce equivalent grammars, there is no automatic assurance the resultant parse trees will be the same unless all possibilities are examined. In that case the ordering remains indeterminate, but the set of results will be equal.
> 0 votes

---
Tags: formal-grammars, compilers, semantics, left-recursion
---


# Question
Title: NP-completeness of the exact distance problem
I am currently learning about NP-complete problems and I want to make sure my understanding is correct.

Here is a problem I am working on currently:

> The exact distance problem is, given an edge-weighted graph $G = (V,E)$, vertices $v\_1,v\_k$, and a distance $D$, is there a simple path from $v\_1$ to $v\_k$ with length exactly $D$?

The first part of my solution is proving that the problem is in NP. I did this by picking a solution to the problem and proving that we can verify the solution in polynomial time. My proof showed that we can verify the solution in $O(mn)$ time, where $m$ is the number of edges and $n$ is the number of vertices.

The next part is showing that a problem we know to be NP-complete can be reduced to the exact distance problem. I am having trouble deciding on an easy NP-Complete problem to use in this part. Would the Hamiltonian Path problem be a good choice?

# Answer
> 2 votes
Yes.  Keep in mind *exactly* what the inputs to each problem are.

---
Tags: np-complete, np, hamiltonian-path
---


title: Definition of integers needs explaining

text:
# Question
Title: Definition of integers needs explaining
Zero and one are defined by the successor function.

$$ \begin{align\*} &0 ≡ λsz.z \\ &1 ≡ λsz.s(z) \end{align\*} $$

But why? $λsz.z$ is irreducible to a value. If I call this function on some value, I get back $z$, which is merely a variable in itself. If I call the function on two values, I get back the second value, which is not necessarily zero.

And yet we're just assigning the function the value $0$? Why? Why not assign zero to say $λs.(λz.xyt)$. This seems arbitrary.

This is from the arithmetic section of: http://www.inf.fu-berlin.de/lehre/WS03/alpi/lambda.pdf

# Answer
The natural numbers don't exist natively in the world of lambda calculus, and so if we want to use them, we have to define them somehow. You are describing the Church numerals, one possible definition which supports arithmetic. Church defines $n$ to be the function $(s,z) \mapsto s^{(n)}(z)$ that maps a pair $(s,z)$ into an $n$-fold application of $s$ to $z$. In particular, when $n = 0$ we get $(s,z) \mapsto z$.

Why this definition and not any other one? No reason. It is just a common definition, but you can use any other definition you like, or even come up with a new one. This particular definition supports arithmetic – you can define addition, multiplication and so on. See Wikipedia for the details.
> 5 votes

---
Tags: lambda-calculus
---


title: Is Graph 2-Coloring NP-Complete?

text:
# Question
Title: Is Graph 2-Coloring NP-Complete?
I know there is a polynomial time algorithm for 2-coloring. But should the answer be "No" or should it be "Maybe"? Since 2-coloring is in NP and we dont know if there is a reduction of any NP-complete to 2-color.

# Answer
> 5 votes
Since graph 2-coloring is in P and it is not the trivial language ($\emptyset$ or $\Sigma^\*$), it is NP-complete if and only if P=NP.

---
Tags: graphs, np-complete, np, colorings
---


title: boolean expression syntax checking

text:
# Question
Title: boolean expression syntax checking
i am trying to formulate an algorithm for syntax checking for simple boolean expression like (var1 = 10) or (var2 \> 100). evaluation part seems to be easy as i will convert infix to postfix and evaluate postfix without 'paren()'.

i am not fully sure which method should i be using.

can any one point me to a book with algorithm or a link.

# Answer
> 2 votes
What you are describing is part of the area of knowledge known as *compiler theory*, specifically *parsing*. One of the classical books is the dragon book. Parsing and evaluating expressions like yours is usually done in three interlocked steps:

1. Lexical analysis. This part is in charge of converting the input into a sequence of "lexemes". It will convert your example into the lexemes "(" VARIABLE "=" NUMBER ")" "or" "(" VARIABLE "\>" NUMBER ")". This step is implemented using regular automata.
2. Syntax analysis. This part construct a parse tree of your expression. In your case, the parse tree (generated using Miles Shang's online tool) will be:  This step is implemented using context-free languages, either using a table-based approach or using recursive descent.
3. Semantic analysis. In your case, this part will evaluate the expression recursively using the parse tree, making use of *attributes* stored at the meta-lexemes VARIABLE and NUMBER.

---
Tags: reference-request, compilers, parsers
---


# Question
Title: Operation of the Ford–Fulkerson algorithm given an almost maximum flow
I have been assigned the question:

> Let $G$ be a flow network and $f^\*$ be the maximum flow computed by the Ford-Fulkerson algorithm. Consider a new flow network $G'$ constructed by increasing the capacity of exactly one of $G$'s edges by one.
>
> Using the maximum-flow and minimum-cut theorem, argue that if we run the Ford-Fulkerson algorithm on $G'$ with $f^\*$ as the initial flow, the while-loop shall terminate in at most one iteration.

But I feel like the loop can run more than once...

Considering a base case where $G$ has one edge between the sink and source with a capacity of 1.

Then $G'$ will have one edge with a capacity of 2.

So then when we run the Ford–Fulkerson algorithm with an initial flow of $f^\* = 1$, the first loop will leave a residual graph with an edge with a capacity of 1, and therefore the loop will run for a second time.

# Answer
> 0 votes
You are interpreting the question too literally. The question claims that only one *augmentation step* will be performed. In your example, we augment $f^\*$ by pushing one more unit of flow, and then we reach the maximum flow of the updated network.

---
Tags: network-flow, ford-fulkerson
---


# Question
Title: There are n numbers. Find the maximal set of pairwise NON coprime numbers
I have to take input in an array(no. of elements in array \<=10^5). For ex:- Let the array be {2,3,4,16,9,45,81,27}
Now I need to find the order of the maximal set such that any pair of elements in the set have gcd \> 1.
In the example:- {3,9,45,27,81} is such a set.It's order is=5, hence 5 is my ans. Note that {2,4,16} also has pairwise gcd's \>1 but it is not maximal (5\>3).

What I did:- I tried to find every possible set which meets the condition and then see the maximum order but that doesn't seem to work(works in some cases, but fails in majority).

The input numbers are \<=10^7 so this needs to be fast.

# Answer
Your problem is NP-complete, I will show a reduction from maximum independent set to your problem. Let $G = (V, E)$ be an undirected graph, and let $G'$ be the complement graph of $G$. Label each edge $uv$ of $G'$ with a prime number $p\_{uv}$ such that for each pair of edges $uv, wx \in E$ it holds that $p\_{uv} \neq p\_{wx}$ Now, label each $v \in V$ with $$ \prod\_{u \in Adj(v)} p\_{uv}\\,.$$

Now, take the set of the labels. A subset of it is the maximum set of non-parwise coprime numbers if and only if it is a maximum clique in $G'$, if and only if it is the maximum independent set of $G$.
> 4 votes

---
Tags: algorithms, optimization, integers
---


title: How does universal calculator work?

text:
# Question
Title: How does universal calculator work?
As I understand, the concept 'computation' started dependent on hardware (like looms for instance).

The Hardware defines (physical cascades) what happens between input and output. I think I saw in a CS class, a mention about universal calculation where software is not limited by hardware?

It's hard to find a succint answer. What makes a universal calculator, universal?

(I'm not a CS major, so forgive my unprofessional terms and wordings) Thank you.

# Answer
I think you're asking about universal Turing machines? The machine is universal, in the sense that it can compute anything that any other Turing machine can compute. This is interesting is that Turing machines seem to be a very good model of what can be computed by physical devices, such as actual computers. In particular, we're not aware of any physical computation process (i.e., any mechanism we could use to build a computer) that can compute something that a Turing machine can't. So, in practice, the Turing machine is taken as the definition of what can be computed. (See also the Church–Turing thesis.)
> 3 votes

---
Tags: computation-models, turing-completeness
---


title: How to prove 3CLIQUE is decidable

text:
# Question
Title: How to prove 3CLIQUE is decidable
From our computational complexity, there's a question asking to prove 3CLIQUE is decidable.

The definition of 3CLIQUE is:
$$\\{(V,E) : G = (V,E)\text{ is an undirected graph that contains a clique of size 3}\\}.$$

I know this is an NP problem, and NP is a set of problems that easy to verify but hard to solve, but I don't know how to prove. Is there anyone who can help me on this?

# Answer
> 3 votes
In fact, NP is *not* the set of problems that are easy to verify but hard to solve. It is just the set of problems that are easy to verify. NPC, the set of NP-complete problems, is the set of problems that are easy to verify but seem hard to solve.

Your problem is in NP but it isn't NP-complete (unless P=NP), since it's also in P. That is, it can be solved in polynomial time. To prove this, you need to give a polynomial time algorithm that, given a graph $G=(V,E)$, determines whether it contains a clique of size 3. I trust that you are able to do it yourself.

# Answer
> 2 votes
You just need to come up with an algorithm – any algorithm, no matter how dumb or inefficient – to solve the problem. By proving that there's an algorithm, you've proved that it's decidable, since that's what decidable means.

---
Tags: graphs, computability, clique
---


# Question
Title: Algorithm : Select maximum number of Boxes to lift from N boxes
There are $N$ boxes and every box has some weight(non-zero). We start from $Box$ $1$ and move towards the $Box$ $N$ one by one. Now there are 2 option ,either to lift that box or leave it. We want to lift the maximum number of boxes possible.

But there is a condition that must be fulfilled for the lifted boxes. For every pair of the lifted boxes, the $GCD$ of the weights of those should be greater than $1$.

```
Eg 1:
N=7
Weights - 13 2 8 6 3 1 9
Answer - 5

```

We can lift the boxes $2, 3, 4, 5, 7$ in this order. These boxes have following weight- $2, 8, 6, 3,9$ respectively. Note that $gcd(2, 8), gcd(8, 6), gcd(6, 3),gcd(3, 9)$ $\>1$.

```
Eg 2
N=6
Weight - 1 3 3 5 5 1
Answer- 2

```

We can lift boxes numbered $2, 3$ as $gcd(3, 3) = 3 \> 1$.

There is one more possible solution: We can lift boxes numbered $4, 5$ as $gcd(5, 5) = 3 \> 1$.

I thought of a naive solution to check $GCD$ of every successive pair and eliminating that box with whom $GCD$ of next box will be equal to $1$. But this will be very time consuming and not efficient at all. It's time complexity will be quadratic or polynomial.

Now I can't figure out any better and efficient solution/algorithm to find the answer. Any help will be appreciated. Also I would like to keep the time complexity less than quadratic time like maybe $O(N\*LOGN)$.

# Answer
> 0 votes
You could answer the question "what is the highest number of boxes that we can lift starting at box #k", for k = N, N-1, N-2, ..., 1 in that order.

For k = N the answer is obviously 1, and for every k the answer is obviously at least 1. To get the answer for one k, find the next box with gcd \> 1; if none is found the answer is 1. If you found a box with gcd \> 1 you examine further boxes that might improve the answer. Total time worst time is calculating n^2 / 2 GCD's.

In practice, you would set up some data structures to find out quickly whether a solution can be beaten. In your example, you would find that you can lift 4 boxes starting with box #3 but 3 or fewer starting with any later box, so when you see that gcd of box #2 and #3 is \> 1, you know you can lift 5 boxes starting at #2, and you know this cannot be beaten.

---
Tags: algorithms, optimization
---


# Question
Title: what is weak extensionality in $\lambda$-calculus?
I was reading the book lambda calculi, encountered an equality theory called "the rule of weak extensionality", which is shown as follows.

$\frac{M \\, = \\, N}{\lambda x.M \\, = \\, \lambda x.N}$

Yes, it is obviously true.

But why it is called the rule of weak extensionality? what is weak? what is extensionality here means?

I think the reason should be interesting.

# Answer
> 6 votes
There are different kinds of equality. Equality is said to be *extensional* when things are equal when their parts are equal, so to speak:

1. Equality the elements of $A \times B$ is extensional if, for all $u, v : A \times B$, $u = v$ if and only if $\pi\_1(u) = \pi\_1(v)$ and $\pi\_2(u) = \pi\_2(v)$. Here $\pi\_1$ and $\pi\_2$ are canonical projections. That is, $u$ and $v$ are equal if they have the same components (parts).
2. Equality of elements of $A \to B$ is extensional if, for all $f, g : A \to B$, $f = g$ if and only if $f(a) = g(a)$ for all $a : A$. That is, $f$ and $g$ are equal if they have the same values (parts).
3. Equality of sets is equal if, for all sets $S$ and $T$, $S = T$ if and only if $x \in S \Leftrightarrow x \in T$ for all $x$. That is, $S$ and $T$ are equal if they have the same elements (parts).

Equality which is not extensional is called *intensional*. For instance, if by $A \to B$ we mean *programs* (pieces of code) which take inputs $A$ and produce outputs $B$ then equality of functions could simply mean equality of the code.

The rules of the $\lambda$-calculus do *not* specify whether equality is extensional or intensional. They allow for both possibilities. With this in mind we see that it is not entirely clear whether the $\xi$-rule (that's what it's called) $$\frac{M = N}{\lambda x . M = \lambda x . N} \tag{$\xi$}$$ should be part of $\lambda$-calculus. Normally it is, but we could envision a situation in which $\lambda x . M$ gets compiled differently from $\lambda x . N$ for some reason. So much about it being "obviously true".

Personally, I would not call the $\xi$-rule "weak extensionality" because that conveys the wrong idea. It is a *congruence* rule expressing the fact that $\lambda$-abstraction preserves equality. Another congruence rule is $$\frac{M\_1 = M\_2 \qquad N\_1 = N\_2}{M\_1 N\_1 = M\_2 N\_2}.$$

If we insist, we can think of the $\xi$-rule as weak form of extensionality in the sense that two $\lambda$-abstractions are equal if their bodies (parts) are equal.

---
Tags: lambda-calculus
---


# Question
Title: Why does this grammar derive into $\beta \alpha ^*$ instead of $\alpha ^* \beta$?
In this video clip the teacher presents a grammar $A \rightarrow A \alpha | \beta$ and after providing the parse tree explains that the regular expression for the language generated is represented as $\beta \alpha ^\*$.

Why isn't it $\alpha ^\* \beta$ instead? Isn't the grammar left-recursive into terminal $\alpha$ and once terminal $\beta$ is reached the string ends?

# Answer
Try some derivations:

* $A\Rightarrow \beta$
* $A\Rightarrow A\alpha\Rightarrow \beta \alpha$
* $A\Rightarrow A\alpha\Rightarrow A\alpha\alpha\Rightarrow \beta \alpha\alpha$

The pattern is clear: starting from $A$, we'll generate strings of the form $\beta\alpha\dotsc\alpha$, in other words, $\beta\alpha^\*$. Since at any stage we have $A$ on the left of the sentential form, we'll eventually generate strings with $\beta$ on the left.

If the grammar had been $A\rightarrow \alpha A\mid \beta$, then we'd derive strings of the form $\alpha^\*\beta$.
> 4 votes

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


title: Random Walk on the Integer Line

text:
# Question
Title: Random Walk on the Integer Line
Suppose we are doing a random walk on the infinite integer line and that we take $2n$ total steps. At every step of this walk, the position of the walker is an integer point on this line. For the next step of this walk, the walker moves to one of the two adjacent/neighboring integer points with equal probability (assume we start at integer 0). Let $S\_l$ and $S\_r$ be random variables denoting the number of leftward steps and rightward steps made over the whole $2n$-step walk, respectively.

There are two things I would like to show:

(1): For any $t \> 0$, there exists a constant $c \> 0$ such that Pr$\[|S\_l - S\_r| \> c\sqrt{n}\] \leq t$.

(2): Derive a bound on $\beta$ given that Pr$\[|S\_l - S\_r| \> \beta\] \geq 1 - \frac{1}{n}$ (i.e., find a bound on $\beta$ that gives us a high probability guarantee).

One approach I'm considering is that we can take $|S\_l - S\_r|$ as a random variable $D\_{2n}$ denoting the distance from the origin after $2n$ steps. Now we can compute $E\[D\_{2n}\] \approx \sqrt{\frac{2}{\pi}} \sqrt{2n}$. I'd imagine that at this point I'd either need to apply a Chernoff bound or the Chebyshev inequality, but I'm not sure how to apply either in this context.

# Answer
> 4 votes
Hint: $S\_l - S\_r$ is the sum of $2n$ independent variables $X\_1,\ldots,X\_{2n}$, with $\Pr\[X\_i = 1\] = \Pr\[X\_i = -1\] = 1/2$.

---
Tags: probability-theory, random-walks
---


# Question
Title: How to draw a clearly arranged DFA of a language with modulo rules?
I know how to draw a DFA, but I have problems with this specific one:

${L = \\{ w \in \\{a,b,c\\}^\* \mid \ |w|\_a \equiv |w|\_b - 2|w|\_c \mod \ 5 \\} }$

This language is regular and there has to exist a DFA (It would be great if someone could leave a comment WHY a language like this one is regular). Finally, I got a solution, but I'm not really satisfied with my solution. How can I present the DFA in a more clearly way? (is it possible to draw a "Planar graph" of it?)

# Answer
Here is the minimal DFA. It keeps track of $|w|\_a-|w|\_b+2|w|\_c\bmod 5$.
> 3 votes

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


# Question
Title: What is the Big O time complexity of this algorithm?
We are given $m$ arrays of $n$ elements each. For 90% of these arrays we run an $\mathcal O(n)$ algorithm and for the other 10% an $\mathcal O(n\log n)$ algorithm. What is the total time complexity? I think it is $\mathcal O(m n \log n)$ but I am not sure.

# Answer
The O(n log n) eventually grows faster than the O(n) algorithm. We always take the fastest growing component of the algorithm when deciding the complexity, so you're right that the total complexity of the algorithm is O(m n log(n))
> 1 votes

# Answer
Ok, i dont speak English so i will be concise:

m * 90 / 100 = m'

m * 10 / 100 = m''

=\> O(m'·n·log(n)) + O(m''·n) = O(m'·n·log(n) + m''·n)

=\> O(m'·n·log(n))
> -2 votes

---
Tags: algorithm-analysis, runtime-analysis
---


# Question
Title: Total number of bits of storage for direct mapped cache
I have a homework assignment dealing with caches. We are asked to compute the total number of bits of storage required for the cache, including tags and valid bits. Then compute the overhead for the cache incurred by the tags and valid bits.

Info given: Consider a direct-mapped cache with 16KBytes of storage and a block size of 16 bytes. Assume that the address size is 32 bits.

So I've done the calculation and get a total number of 32 bits required. We were given the following formula:

```
(bits/tag) + (bits/index) + (bits/block offset) = total number of bits

```

I am unsure about my number of sets. I did this by:

* 16 byte blocks is 2^4, so 4 bits for block offset
* 2^32 / 16 bytes per frame gives us 2^28 blocks
* 2^28 blocks / 65536 sets gives us 2^12 blocks/set, so we need 2^12 unique tags
* Add them together: 12 (bits/tag) + 16 (bits/index) + 4 (bits/block offset), which gives us 32 bits

I got my number of sets from 2^size, which is 2^16.

The second issue I'm running into is now calculating the overhead, given those numbers.

We were provided the formula

```
(Address size - bit offset - bit block offset) * number of frames = kbits of tags

```

When doing this, I get the following:

```
(32 - 16 - 4) * 65536 = 12 * 65536 = 786432bits
= 786432bits / 1024 = 768 KBits
= 768 * 0.125 = 96 Kbytes
= (96KBytes / 16KBytes)
= 600% overhead

```

Which obviously does not make sense.

I believe my issue is the number of sets, but from what I can gather from online and our lecture notes, the number of sets (in a direct-mapped cache) is equal to the size of the cache, so that would be 2^16, so 65536.

We have lecture notes that describe how to do this, but they were with 8byte blocks and we were told the number of sets (in the case of the notes, the size was 256, which is 2^8, which I can only presume is 2^block size).

Any insight will be of help!

# Answer
> 0 votes
I'll give these hints without actually solving it for you

1) You do not need to provide tags for all memory, only for the memory that is in the cache.

2) As the block (cache line) is 16 bytes, you only need one tag for each of these.

3) The valid bit are also only for the cached I guess.

---
Tags: cpu-cache
---


# Question
Title: I/O bound processes over CPU bound processes
will an OS which favors I/O bound processes over CPU-Bound processes, experience less average waiting time? If yes, why?

# Answer
Take a sheet of paper.

Assume you have one process that uses an I/O device for 5ms, then the CPU for 5ms, and so on, a total of one million times (5000 seconds I/O, 5000 seconds CPU). Assume another process uses the CPU for 5000 seconds.

Using that sheet of paper, check the progress of both processes if (1) process A is given higher CPU priority, (2) process B is given higher CPU priority, (3) both are given equal priority.
> 2 votes

# Answer
As a first year studen I was pretty sure it was CPU-bound that was the right answer as that silly I/O could wait, my calculations were more important.

As a second year student I was convinced that it was the I/O bound that should be prioritized because of the longer latencies.

Later I would calculate with O(X) and determine the "right" answer.

Now many years later I would say you have to measure it for your specific setup.
> 0 votes

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


# Question
Title: Why quicksort instead of a B-tree construction?
As far as I know (despite some variations which provide empirical average-case improvements) quick-sort is worst case $O(n^2)$ with the original Hoare partition scheme having a particularly bad behavior for already sorted lists, reverse-sorted, repeated element lists.

On the other hand a B-Tree has $O(\log n)$ insertions, meaning worst-case $O(n\log n)$ to process an array of $n$ elements. Also an easy optimization to memoize the memory-address of the lowest and highest nodes (would make it possible to process sorted / reverse-sorted / repeated-element lists in $O(n)$).

While there are more favored sorting algorithms than quicksort now (e.g. timsort) what originally favored its use? Is it the susceptibility to parallelization (also in place swaps, lower memory complexity)? Otherwise why not just use a B-tree?

# Answer
A B-tree has one significant disadvantage on the fastest deep cache machines, it depends on pointers. So as the size grows each access have a greater and greater risk of causing a cache-miss/TLB-miss. Effectively getting a K value of z\*x, x=sum(cache/TLB-miss per access, L1-TLB misses are typically size of tree / total cache size), z ~= access time of least cache or main memory that can hold the entire tree.

On the other hand the "average case" quicksort streams memory at maximum pre-fetcher speed. Only drawback here is the average case also cause a stream to be written back. And after some partitions the entire active set sit in caches and will get streamed quicker.

Both algorithms suffers heavily from branch mis-predictions but quicksort, just need to backup a bit, B-Tree additionally needs to read in a new address to fetch from as it has a data dependency which quicksort doesn't.

Few algoritmes are implemented as pure theoretically functions. Nearly all have some heuristics to fix their worst problems, Tim-sort excepted as its build of heuristics.

merge-sort and quick-sort are often checked for already sorted ranges, just like Tim-sort. Both also have an insertion sort for small sets, typically less than 16 elements, Tim-sort is build up of these smaller sets. The C++ `std::sort` is a quicksort hybrid with insertion sort, with the additional fallback for the worst case behaviour, if the dividing exceed twice the expected depth it changes to a heap-sort algorithm.

The original quicksort used the first element of the array as pivot, this was quickly abandoned for a (pseudo)random element, typically the middle. Some implementations changed to median-of-three (random elements) to get a better pivot, recently a median-of-5-median (of all elements) was used, and last I saw in some presentation from Alexandrescu was a median-of-3-medians (of all elements) to get the a pivot that was close to the actual median (1/3 or a 1/5 of the span).
> 3 votes

# Answer
Consider the following general question:

> Here is an $O(n\log n)$ sorting algorithm. Why use quicksort (or timsort, or whatever is used in some library) rather than my algorithm?

There are several possible types of answers:

1. Your algorithm is worse than quicksort in some sense, say it is slower on average.
2. Your algorithm has similar performance to quicksort. Libraries need only one algorithm, so they chose quicksort for historical reasons.
3. Your algorithm is better than quicksort in some sense (say worst case complexity), but worse in some other sense (say average case complexity). Libraries prefer the tradeoffs of quicksort.
4. Your algorithm is better than quicksort, but is not widely known and so not implemented in libraries.
5. Your algorithm is implemented in some libraries, but they are too obscure for you to realize.

But the real answer is:

> Library designers implement some sorting algorithm they know. Later on, other people might implement a different algorithm. Nobody is claiming that whatever algorithm is implemented is the best algorithm in all (or even some) applications. People for whom this is important implement their own algorithms.
> 1 votes

---
Tags: algorithms, sorting, efficiency
---


title: Breadth-first forest

text:
# Question
Title: Breadth-first forest
I was reading CLRS about BFS and DFS, and the algorithms presented therein, which I take to be somewhat standard, construct a forest with DFS that includes all the nodes, whereas BFS only constructs a tree from a chosen node $s$, and leaves out all the other nodes that are not reachable from $s$.

It seems BFS can be adapted to construct other trees to include non-reachable nodes from $s$ and form a "BFS forest", analogous to the operation of DFS. What is the reason for constructing a forest in DFS but only a tree (that excludes unreachable nodes) in BFS?

# Answer
This asymmetry reflects a "philosophical" difference between the two algorithms. Let us think for a moment about what each of them is trying to achieve.

DFS investigates properties related to the *structure of the graph as a whole*: a few examples among the many are finding strongly connected components, topological sorting, finding cycles, testing biconnectivity, testing planarity. In all those cases the output forest has a very direct and concrete meaning. For example, the usual classification of the edges as tree, forward, back or cross tells us something about what these edges "do" in the graph we are exploring.

On the other hand, BFS is normally used to determine *distances w.r.t. a pre-selected node*; even applications that do not explicitly mention such distances, such as testing bipartiteness, are somewhat related to the general idea of counting the steps taken in a path.

However, distances from different sources behave somewhat inconsistently: reachability sets of different nodes may be intersecting, and distances from the two original roots could be drastically different. Furthermore, when running DFS we don't care where we started searching -- as emphasized by the fact that DFS takes no input other than the graph itself -- but the output of a BFS is a function of its starting node: what would a BFS forest even mean?

Perhaps you might be able to build a structure along the lines of a depth first forest considering the minimum pairwise distances between all nodes, but it would be something very different and you wouldn't be able to get that kind of information from a single breadth first search, anyway.
> 4 votes

---
Tags: algorithms, graphs, graph-traversal
---


# Question
Title: Determine what is the best order for running filters on a dataset
I'm trying to figure out what is the optimal order for running a sequence of tasks in a pipeline.

Each task filters a percentage of the dataset.

Assuming I got the tasks *t1, t2, t3, ..., ti* and a dataset. Each task have an execution time per item in the dataset denoted as *e1, e2, e3, ..., ei* and each task filters a certain percentage of the dataset denoted as *f1, f2, f3, ..., fi*.

What is the optimal sequence of tasks to achieve the minimum running time ?

I've first tried to examine two tasks - *t1* and *t2* with their representative execution time and filter percentage - *e1, f1* and *e2, f2*.

I want to find the ordering predicate for getting e1 + f1\*e2 \< e2 + f2\*e1. I'll get the condition *e1 / (1 - f1) \< e2 / (1 - f2)*. And I guess that from here I'll need to prove it in induction, but I'm stuck because the equation is some kind of recursion.

# Answer
> 4 votes
You can prove that the optimal ordering is according to ascending order of `e(i)/f(i)`.

**Proof:**

Let `r(i) = 1 - f(i)`. The total cost of an ordering is: `e(1) + e(2)*r(1) + e(3)*r(2)*r(1) + ... + e(N)*r(N-1)*...*r(1)`

Now, assume that there's an optimal ordering that *doesn't* follow the rule above. It follows that there are two adjacent tasks t(i) and t(i+1) such that `e(i)/(1-r(i)) > e(i+1)/(1-r(i+1)) => e(i)*(1-r(i+1)) > e(i+1)*(1-r(i))` swapping these two will change the value of only two expressions in the total cost expression, resulting in a delta of:

```
e(i) * r(i-1)*...*r(1) + e(i+1)*r(i)*...*r(1) -
[e(i+1)*r(i-1)*...*r(1) + e(i)*r(i+1)*r(i-1)*...*r(1)] =
r(i-1)*...*r(1)*[e(i) + e(i+1)*r(i) - e(i+1) - e(i)*r(i+1)] =
r(i-1)*...*r(1)*[e(i)*(1-r(i+1)) - e(i+1)*(1-r(i))] > 0

```

The delta is positive, meaning that the original configuration is more expensive than the outcome of the swap, therefore we have a contradiction.

---
Tags: algorithms
---


# Question
Title: Algorithms that achieve better compression for more data
I'm interested in compression algorithms where the compression ratio increases as the amount of data to be compressed increases. Let's call this "super compression". Could super compression be achieved through recursive compression algorithms?

Here's the kind of algorithm I'm contemplating. The binary file is first scanned, to identify patterns. After this, the file is rewritten such that the patterns are encoded, e.g., if there is a sequence of 100 $0$'s, it could be represented as $xxx 0$ where $xxx$ represents that the $0$ occurs 100 times.

After this is done, the algorithm is then called on the generated compression file, until a file with no patterns is produced. The header of the file will contain how many times the algorithm was run, so the file can be decompressed. Will this work to achieve super compression?

# Answer
Compressing compressed data only benefits you if the original compression wasn't very good. Good compression essentially removes all the patterns, leaving very little for any future round of compression to exploit.

There is a fundamental limit as to how well any particular lossless compression scheme can compress. In particular, if a compression scheme could make every file smaller, you could indeed run it repeatedly and you could keep going until the file you started with had become one bit long. Since there are only two compressed files and the decompression program is deterministic, the decompression program can only have two possible outputs, but it's supposed to be able to produce whatever file was actually compressed.

In fact, you can't even compress all files *once*. There are $2^n$ $n$-bit files, but only $\sum\_{i=0}^{n-1}=2^n-1$ files of length strictly less than $n$. So, if you had an algorithm that could make every file of length $n$ strictly smaller, there would have to be two different files that compress to the same thing, by the pigeonhole principle. But now the decompresser doesn't know how to decompress that file.

And it gets worse. Any fixed lossless compression scheme can't compress half of the possible files by even one bit. When we talked about compressing $n$-bit files in the previous paragraph, we didn't mention that there are also files of length less than $n$, which need to be compressed, too. There are $2^{n+1}-1$ possible files whose length is in the range $0$–$n$ bits. If we could compress all of those by even one bit, we'd have to be able to write $2^{n+1}-1$ different files of length at most $n-1$ bits, but there are only half that number of $(n-1)$-bit files, so it simply cannot be done.

Note that you can't get around this by saying "If algorithm A compresses the file, I'll use that and, otherwise, I'll use algorithm B." Even if it were guaranteed that every file could be compressed by one of those two algorithms, you'd have to write a header to the file to say which one was used. So, now you need to compress by at least two bits so that the compressed file plus the header is shorter than the original file. But no single algorithm can compress more than a quarter of files by two bits, so your combination of A and B still can't compressed half your files.

You can't get around it by using multiple files because the total length of those files will still obey the same rules that we already discussed. Since, in reality, files on disks are stored in blocks so storing $k$ files means you need to allocate at least $k$ blocks, which isn't efficient when the files are small. Multiple files does allow you to cheat slightly, since it means you don't need any delimiter between your metadata in one file and the data in the second. However, that data still has to be stored in the directory entry so you're not really saving any space.

Note that everything above applies to *all* possible compression algorithms. It doesn't use any properties of whatever algorithm you could think of: the argument is just about the number of files of different lengths. The scheme you're thinking of – looking for patterns and representing them using some language – is no different. It cannot win because nothing can win. Taken to the ultimate degree, you're moving towards Kolmogorov complexity, which essentially compresses a file into the shortest program that will output that file when it's run. Still, this doesn't let you get around the fundamental bounds. Indeed, it's the tool that's used to prove a lot of the more interesting fundamental bounds. And it turns out that, for most files, the shortest program is `print "[literal string containing the file contents]";`, which is, essentially, one bit longer than the file you started with.
> 6 votes

---
Tags: algorithms, information-theory, data-compression
---


# Question
Title: Push down automata acceptance by Empty stack and final state
I have a very basic question. Can we have a PDA which can accept a string by both final states and empty stack? Can the same PDA accept by the two modes simultaneously ? If there are final states for acceptance and in addition to that at some point in time the input string is read completely and simultaneously the stack is empty but the state is non-final. Will it be accepted in that case ?

# Answer
Yes, that is possible. If you start with one that accepts by final state, you can change that one into an automayon that accepts by final state and empty stack as follows.

First create a *new* final state $f$. From every old final state have an epsilon transition to the new state $f$. Add transitions to $f$ that empty the stack.

It seems best to keep the old final states. A computation of the old automaton might end in one of the old final states with an empty stack, in which case it should be accepted, but we have no contents of the stack, so we cannot move to $f$.
> 1 votes

---
Tags: automata, pushdown-automata
---


# Question
Title: Why can useless states in TMs not be found by traversing the state graph?
Can anyone explain why can't we use a Turing machine's transition diagram? For e.g. The definition of a USELESSTM is as follow:

> A useless state in a TM is one that is never entered on any input string.
>
> > USELESSTM = { ⟨ M, q⟩ ∣ q is a useless state in M }

I know this problem can be proved to be undecidable by reducing ETM to it, but I want to know why can't we do a breadth first search of the Turing machine's state diagram to find states that are unreachable. Then based on whether or not we found any unreachable states, we can say that there are or there are not any useless states.

# Answer
Your proposed algorithm finds *some* useless state, but not all of them.

Remember that you have *tape content* to deal with. Say, for instance, a state is reachable when there's a symbol `2` on the tape. It *is* reachable in the state graph, but if the TM gets only binary input (and never write a `2` itself) it will never be attained by the machine.

The proof you have tells you that there is no way to fix this.

Note that this problem is similar to detecting dead code; maybe this metaphor works better for you.
> 7 votes

# Answer
A state $q$ in a Turing machine $M$ with start state $q\_0$ is useless if there exists no input $w$ and no configuration $u\_1qau\_2$ such that we can reach $u\_1qau\_2$ when starting in configuration $q\_0w$.

Intuitively, to find a useless state, we would need to explore not the finite transition diagram of $M$ but *all possible computations of $M$* that begin with a starting configuration $q\_0w$.

More precisely, we can reduce the emptiness problem for Turing machines to that of asking if a given state is useless. To do this, given a machine description $\langle M \rangle$, we simply ask if the state $q\_{\mathrm{accept}}$ is useless for $M$. This is the case iff $L(M) = \emptyset$. Since the emptiness problem is not Turing-recognizable, neither is the useless-state problem.
> 2 votes

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


# Question
Title: Running time of sparse matrix multiplication
Given a sparse matrix $M \in \mathbb{R}^{n \times m}$ with $n \ll m$ and $\mathsf{nnz}$ being the number of non-zero-components. What is the running time of computing $M M^T$?

# Answer
The question doesn't make any sense. It doesn't make sense to ask for the running time of a computation, unless you specify an algorithm for that computation. So *how* would you calculate this product? That's the first thing you need to do: Specify an algorithm how you calculate the product.

The next step: Assuming that many array elements are zero, can you reduce the amount of work that this algorithm would be doing? For example, if you know that x = 0, then it's pointless to multiply x*y because you know the result is 0. And it's pointless to add x*y to z, because that doesn't change z. So how can you take advantage of many array elements being zero? What's the runtime if you do that?

The next step: Assuming that many array elements are zero, can you reduct the amount of work further? Would you need some clever data structures? If yes, which ones?
> 1 votes

---
Tags: complexity-theory, matrices, linear-algebra, numerical-algorithms, sparse-matrices
---


# Question
Title: Does a distance matrix have to be Euclidean in order to be clustered by an average-linking algorithm (UPGMA)?
What are the exact assumptions behind the use of UPGMA? Can I use a non-Euclidean metric? This may result in a non-Euclidean distance matrix. What kind of bias may I encounter if I do so? References are appreciated.

# Answer
> 1 votes
While you can modify any algorithm as you see fit, in its pure form UPGMA has the following underlying assumptions at work:

**UPGMA** (*Unweighted Pair-Group Method with Averages*), arithmetic average - the average distance between elements of each cluster (weighted by the number of elements).

For example, (AB) and C+(DE) = (55+3x45)/3 = 63.33

**Additional Comparative Algorithmic Context**

Below is a list of algorithms and their general framework as it relates to each algorithm:

* **SINGLE** (*Single-link method*) – brings together the closest elements.
* **WPGMA** (*Weighted Pair-Group Method with Averages*), arithmetic average (not weighted by the number of elements).
* **WPGMC** (*Weighted Pair-Group Method with Centroid Average*), centroid average (assumes dissimilarity).
* **WPGMS** (*Weighted Pair-Group Method with Spearman Average*), Spearman's average (assumes correlation).

**Reference for Modifying UPGMA**

The paper below is a wonderful resource for "what-if" scenarios as it relates to UPGMA:

Vavrek, M. J. (2016). A comparison of clustering methods for biogeography with fossil datasets. PeerJ, 4, e1720. http://doi.org/10.7717/peerj.1720

---
Tags: algorithms, data-mining, clustering
---


# Question
Title: Possible results of two programs running on a symmetric multicore system
This question is from Patterson and Hennessy's Computer Organization and Design.

> Consider the following portions of two different programs running at the same time on four processors in a symmetric multicore processor (SMP). Assume that when this code is run, both $x$ and $y$ are 0.
>
> Core 1: $x = 2$;
>
> Core 2: $y = 2$;
>
> Core 3: $x = x + 1$;
>
> Core 4: $z = x + y$;
>
> What are all the possible resulting values of $x$, $y$, and $z$? You will need to examine all possible interleaving of instructions.

The given answer is, for $(x, y, z)$: $(3, 2, 5), (3, 2, 4), (3, 2, 3), (3, 2, 2), (3, 2, 0), (2, 2, 4), (2, 2, 3), (2, 2, 2), (2, 2, 1), (2, 2, 0).$

I understand how $x$ is either 2 or 3 and why $y$ is forced to be 2, but I don't know how $z$ takes those values.

# Answer
> 1 votes
x has 4 possible values throughout the execution of the program, but only two after execution is finished. x could be x = 2, or x = 0 + 1, or x = 2 + 1, or x = 0. If x = 0 + 1 executes first, then x = 2 executes second and x will be 2, but if x = 2 executes first, then x will be 3. But z could either receive 0, 1, 2, or 3 for x. Y is only ever either 0 or 2, with 2 being the value at the end always. So you have z = 3 + 2, z = 2 + 2, z = 1 + 2, z = 0 + 2, z = 3 + 0, z = 2 + 0, z = 1 + 0, or z = 0 + 0.

---
Tags: computer-architecture, parallel-computing, semantics
---


title: Upper bounding randomized k-SAT solver

text:
# Question
Title: Upper bounding randomized k-SAT solver
*Problem*:

Consider a k-SAT solver that assigns values independently uniformly at random to all the variables. Given the formula has $m$ clauses provide an upper bound for the probability of a random assignment to be unsatisfiable.

---

The issue is that I have no clue from where to start. Both Markov, Chernoff, Chebyshev and McDiarmid's inequalities seem to be not applicable in this situation as the probability of a particular clause to be unsatisfiable depends on the probability of other clauses with overlapping variables to be unsatisfiable.

For every clause the probability of it to be unsatisfiable is $${1 \over {2^k}}$$

There are $m$ clauses in total, so if there are all independent, the answer would be $$P(\mathit{assignment~is~unsatisfiable}) = (2^{-k})^m$$

If somebody would help me a bit with at least some kind of hint I would be extremely grateful.

# Answer
> 2 votes
Hint: Use a union bound.

Note that for $m \geq 2^k$ you cannot provide any non-trivial bound, since there are formulas with $2^k$ clauses of width $k$ that are unsatisfiable. The same example shows that the bounded hinted above is tight (for all $m \leq 2^k$).

---
Tags: satisfiability, upper-bound
---


title: About the definition of a balanced tree

text:
# Question
Title: About the definition of a balanced tree
(Note: I couldn't put "balanced tree" in the tags ; this topic isn't about balanced search trees, just balanced trees.)

Let $A$ a binary tree.

We have the relation: $log(|A|+1) \leq h(A) \leq |A|-1$ where $|A|$ denotes the size of A (the number of nodes) and $h(A)$ its height.

Then I was told that A is balanced if $h(A) = O(log|A|)$. I don't really understand what that means. I know the symbol $O$ when we use it in maths with "$n$" stuff. For exemple $u\_n = O(v\_n)$ when $n \to +\infty$ or $f = O(g)$ at a certain point $x$. But there, how can we told that the tree $A$ "evolves"?

Applying the definition, it would mean that $\frac{|A|}{log|A|} \leq M$ but for a given tree, this is always true. So do we fix set the tree's size and have the relation for any size or do we fix the size and have the relation for any height, or something else?

Thanks.

# Answer
You're right – a single tree cannot be balanced, or rather, is trivially balanced. A collection of trees can, however, be balanced meaningfully: there exists a constant $M$ such that all trees in it have height at most $M\log n$, where $n$ is the number of elements in the tree.

For example, take any algorithm that uses a binary tree. We know that operations on binary tree take time $O(h)$, where $h$ is the height of the tree. Suppose now that the algorithm maintains the property that the tree is balanced; that is, the set of all trees that occur in all executions of the algorithm forms a collection of balanced trees. Then we can bound the running time of operations on the tree at a certain point in time by $O(\log n)$, where $n$ is the number of elements in the tree at that point.

In practice, we "misuse notation" by calling a single tree balanced. What we mean that the set of all "instances" of the tree are balanced. Usually what set is meant is clear from context.
> 2 votes

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


# Question
Title: Decidability of language containing strings of length equal to that of some substring of 1s in $\pi$?
I read that the following language is decidable.

$\\{w | w \in \\{0, 1\\}^\* \text{ and } 1^{|w|} \text{ is a substring in binary expansion of } \pi \\}$

The proof has been given by considering the two possible cases

* Suppose it is true that there exists a minimal integer $N$ such that the binary expansion of $\pi$ only contains substrings of 1 having length at most $N$. That is, it contains substring $1^N$ but not $1^{N + 1}$. Define a corresponding turing machine $M\_N$ such that it accepts the input string if it is of length $N$, otherwise rejects it. This machine decides the given language.
* Suppose the binary expansion of $\pi$ contains substrings of $1$s of all lengths. Then the Turing machine that accepts all strings decides the given language.

We are not able to construct a single Turing machine that decides the language given, but one of these machines thus constructed will decide it but we do not know which. I don't quite understand how this language is decidable?

# Answer
> 5 votes
You are confusing knowledge and truth. Something may be true without us knowing precisely why. An object may exist without us being able to construct it.

If you belive in classical logic, then it is true that the maximum length of consequtive 1's in the expansion of $\pi$ is either finite or infinite. In each case, there exists a decision procedure for your language. Therefore a decision procedure exists.

But we do not *know* which of the cases happens, and so we not not *know* a particular decision procedure, even though one exists. If you don't like this line of reasoning, then you should ask for a *constructive* proof of decidability of your language.

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


# Question
Title: What are some real world examples of nearly sorted lists
I found that sorting algorithms such as Insertion Sort and Djikstra's Smoothsort approach O(n) complexity when the list is nearly sorted. What are some real world scenarios where a list is nearly sorted?

# Answer
> 2 votes
What about log files described in AWStats logfile analyzer 7.5 Documentation?

> An error log file is not always completely sorted but only "nearly" sorted because of cache and writing log engines used by a server.

---
Tags: algorithms, sorting
---


# Question
Title: Is a Turing Machine "by definition" the most powerful machine?
I agree that a Turing Machine can do "all possible mathematical problems". But that is because it is just a machine representation of an algorithm: first do this, then do that, finally output that.

I mean anything that is solvable can be represented by an algorithm (because that is precisely the definition of 'solvable'). It is just a tautology. I said nothing new here.

And by creating a machine representation of an algorithm, that it will also solve all possible problems is also nothing new. This is also mere tautology. So basically when it is said that a Turing Machine is the most powerful machine, what it effectively means is that the most powerful machine is the most powerful machine!

> Definition of "most powerful": That which can accept any language.
> Definition of "Algorithm": Process for doing anything. Machine representation of "Algorithm": A machine that can do anything.

Therefore it is only logical that the machine representation of an algorithm will be the most powerful machine. What's the new thing Alan Turing gave us?

# Answer
> 143 votes
> I agree that a Turing Machine can do "all the possible mathematical problems".

Well, you shouldn't, because it's not true. For example, Turing machines cannot determine if polynomials with integer coefficients have integer solutions (Hilbert's tenth problem).

> Is Turing Machine “by definition” the most powerful machine?

No. We can dream up an infinite hierarchy of more powerful machines. However, the Turing machine is the most powerful machine that we know, at least in principle, how to build. That's not a definition, though: it is just that we do not have any clue how to build anything more powerful, or if it is even possible.

> What's the new thing Alan Turing gave us?

A formal definition of algorithm. Without such a definition (e.g., the Turing machine), we have only informal definitions of algorithm, along the lines of "A finitely specified procedure for solving something." OK, great. But what individual steps are these procedures allowed to take?

Are basic arithmetic operations steps? Is finding the gradient of a curve a step? Is finding roots of polynomials a step? Is finding integer roots of polynomials a step? Each of those seems about as natural. However, if you allow all of them, your "finitely specified procedures" are more powerful than Turing machines, which means that they can solve things that can't be solved by algorithms. If you allow all but the last one, you're still within the realms of Turing computation.

If we didn't have a formal definition of algorithm, we wouldn't even be able to ask these questions. We wouldn't be able to discuss what algorithms can do, because we wouldn't know what an algorithm *is*.

# Answer
> 71 votes
You are not correct when you repeatedly make the statements about this or that being "just a tautology". So allow me to put your claims into a bit of historical context.

First of all, you need to make the concepts you use precise. What is a problem? What is an algorithm? What is a machine? You may think these are obvious, but a good part of the 1920's and 1930's was spent by logicians trying to figure these things out. There were several proposals, one of which were Turing machines, which was the most successful. It later turned out that the other proposals were equivalent to Turing machines. You have to imagine an era when the word "computer" signified a person, not a machine. You are just riding the wave and the consequences of the brilliant inventions by brilliant minds from a hundred years ago, without being aware of it.

Turing machines are described concretely in terms of states, a head, and a working tape. It is far from obvious that this exhausts the computing possibilities of the universe we live in. Could we not make a more powerful machine using electricity, or water, or quantum phenomena? What if we fly a Turing machine into a black hole at just the right speed and direction, so that it can perform infinitely many steps in what appears finite time to us? You *cannot* just say "obviously not" – you need to do some calculations in general relativity first. And what if physicsts find out a way to communicate and control parallel universes, so that we can run infinitely many Turing machines in parallel time?

It does *not* matter that at present we cannot do these things. What is important, however, is that you understand that Turing *had to think about what was physically possible* (based on the knowledge of physics at the time). He did not just write down "a mere tautology". Far from it, he carefully analyzed what computation means in an informal sense, then he proposed a formal model, argued very carefully that this model captures what people understood by "computation", and he derived some important theorems about it. One of these theorems says that Turing machines cannot solve all mathematical problems (contrary to one of your false statements). All of this, in a single paper, written during summer vaccation, while he was a student. His theorem about the existence of universal machines *was* the invention of the idea of the modern general purpose computer. After that it was only a simple matter of engineering.

Does that answer what Turing contributed to humanity beyond a mere tautology? And did you actually read his paper?

# Answer
> 23 votes
That "anything that is solvable can be represented by an algorithm" is not obvious, at all.

This has been the object of intense debate, since Alan Turing, reworking ideas of Alonzo Church, proposed a definition of computable numbers that took the form of the machine you are referring to. Importantly, those were not the only people working on this kind of thing, at that time.

We still call it a thesis - or a conjecture - since "anything that can be calculated" is clearly not a precise mathematical object, whose structure and range could be studied in a non-speculative way.

# Answer
> 19 votes
First, it is important to keep in mind that Turing Machines were initially devised by Turing not as a model of any type of physically realizable computer but rather as an ideal limit to what is computable by a *human* calculating in a step-by-step mechanical manner (without any use of intuition). This point is widely misunderstood -- see \[1\] for an excellent exposition on this and related topics.

The finiteness limitations postulated by Turing for his Turing Machines are based on postulated limitations of the human sensory apparatus. Generalizations of Turing's analyses to physically realizable computing devices (and analogous Church-Turing theses) did not come until much later (1980) due to Robin Gandy -- with limitations based on the laws of physics. As Odifreddi says on p. 51 of \[2\] (bible of Classical Recursion Theory)

> Turing machines are theoretical devices, but have been designed with an eye to physical limitations. In particular, we have incorporated in our model restrictions coming from:

* > (a) ATOMISM, by ensuring that the amount of information that can be coded in any configuration of the machine (as a finite system) is bounded; and
* > (b) RELATIVITY, by excluding actions at a distance, and making causal effect propagate through local interactions. Gandy \[1980\] has shown that the notion of Turing machine is sufficiently general to subsume, in a precise sense, any computing device satisfying similar limitations.

and on p. 107: (A general theory of discrete, deterministic devices)

> The analysis (Church \[1957\], Kolmogorov and Uspenskii \[1958\], Gandy \[1980\]) starts from the assumptions of atomism and relativity. The former reduces the structure of matter to a finite set of basic particles of bounded dimensions, and thus justifies the theoretical possibility of dismantling a machine down to a set of basic constituents. The latter imposes an upper bound (the speed of light) on the propagation speed of causal changes, and thus justifies the theoretical possibility of reducing the causal effect produced in an instant t on a bounded region of space V, to actions produced by the regions whose points are within distance c\*t from some point V. Of course, the assumptions do not take into account systems which are continuous, or which allow unbounded action-at-a- distance (like Newtonian gravitational systems).
>
> Gandy's analysis shows that the THE BEHAVIOR IS RECURSIVE, FOR ANY DEVICE WITH A FIXED BOUND ON THE COMPLEXITY OF ITS POSSIBLE CONFIGURATIONS (in the sense that both the levels of conceptual build-up from constituents, and the number of constituents in any structured part of any configuration, are bounded), AND FIXED FINITE, DETERMINISTIC SETS OF INSTRUCTIONS FOR LOCAL AND GLOBAL ACTION (the former telling how to determine the effect of an action on structured parts, the latter how to assemble the local effects). Moreover, the analysis is optimal in the sense that, when made precise, any relaxing of conditions becomes compatible with any behavior, and it thus provides a sufficient and necessary description of recursive behavior.

Gandy's analysis gives a very illuminating perspective on the power and limitations of Turing Machines. It is well-worth reading to gain further insight on these matters. Be forewarned however that Gandy's 1980 paper \[3\] is regarded as difficult even by some cognoscenti. You may find it helpful to first peruse the papers in \[4\] by J. Shepherdson, and A. Makowsky.

\[1\] Sieg, Wilfried. Mechanical procedures and mathematical experience.\[ pp. 71--117 in Mathematics and mind. Papers from the Conference on the Philosophy of Mathematics held at Amherst College, Amherst, Massachusetts, April 5-7, 1991. Edited by Alexander George. Logic Comput. Philos., Oxford Univ. Press, New York, 1994. ISBN: 0-19-507929-9 MR 96m:00006 (Reviewer: Stewart Shapiro) 00A30 (01A60 03A05 03D20)

\[2\] Odifreddi, Piergiorgio. Classical recursion theory. The theory of functions and sets of natural numbers. With a foreword by G. E. Sacks. Studies in Logic and the Foundations of Mathematics, 125. North-Holland Publishing Co., Amsterdam-New York, 1989. xviii+668 pp. ISBN: 0-444-87295-7 MR 90d:03072 (Reviewer: Rodney G. Downey) 03Dxx (03-02 03E15 03E45 03F30 68Q05)

\[3\] Gandy, Robin. Church's thesis and principles for mechanisms. The Kleene Symposium. Proceedings of the Symposium held at the University of Wisconsin, Madison, Wis., June 18--24, 1978. Edited by Jon Barwise, H. Jerome Keisler and Kenneth Kunen. Studies in Logic and the Foundations of Mathematics, 101. North-Holland Publishing Co., Amsterdam-New York, 1980. xx+425 pp. ISBN: 0-444-85345-6 MR 82h:03036 (Reviewer: Douglas Cenzer) 03D10 (03A05)

\[4\] The universal Turing machine: a half-century survey. Second edition. Edited by Rolf Herken. Computerkultur \[Computer Culture\], II. Springer-Verlag, Vienna, 1995. xvi+611 pp. ISBN: 3-211-82637-8 MR 96j:03005 03-06 (01A60 03D10 03D15 68-06)

# Answer
> 7 votes
The best popular discussion of this question that I've ever read is MIT professor Scott Aaronson's essay Who Can Name the Bigger Number?, in which he explores, among other things, the implications of super-Turing machines, super-duper-Turing machines, and super-duper-pooper-Turing machines.

# Answer
> 4 votes
No, TMs are not most powerful. Two examples:

a) There could be other machines that compute the same results as a TM but algorithmically faster (e.g. quantum computers computing prime factors). "Faster" is a type of power.

b) TMs cannot represent general Real numbers with perfect precision. But an Analog Computer (AC) might be able to represent and do arithmetic with Real numbers with perfect precision. This would be more powerful than any TM.

---

Of course (b) requires our universe to have some continuous properties (gravity?) which the AC can use to represent Real values. Maybe every physical property, including gravity, is quantized. But we can speculate about machines in a continuous universe. So TMs are not most powerful "by definition".

# Answer
> -5 votes
If you look at computational complexity, a Turing Machine is the most powerful machine - because it has unlimited memory, and no real machine has that. Any real machine cannot solve problems of arbitrary size; they cannot even *read* a problem, much less solve it.

On the other hand, if you tried to implement a real Turing Machine, let's say with the provision that it stops and sounds an alarm if it runs out of tape, you would find that it would take many more steps for doing any kind of computation than let's say the real machine in a cheap phone, and would be much much slower at solving real problems. You would also find that writing an answer on a tape is not a very good user interface. And you would find that lots of people use computers not for solving problems, but for sending nude photos to their friends and for watching cat videos, and a Turing Machine isn't any use for that at all.

---
Tags: algorithms, turing-machines, automata, computation-models
---


title: Binary Search Tree Traversals

text:
# Question
Title: Binary Search Tree Traversals
I have a clue as to how this code/traversals work but I'm still confused.

For example, in the first traversal (Preorder), it prints 31, 12, 25 but then it backtracks all the way to 68? How does it know to do this? My professor referenced a stack but I am still a bit confused.

As for the other codes, I don't know how to backtrack on them at all. I understand the first one quite a bit but for the next 2, not so much.

# Answer
The rules for traversing a tree are, to visit all nodes of a tree you do this:

* **Preorder**: (1) visit the root node, then (2) visit all the nodes in the left subtree of the root, then (3) visit all the nodes in the right subtree of the root. In steps (2) and (3), use the same rule as above.
* **Inorder**: (1) visit all the nodes in the left subtree, (2) visit the root node, (3) visit all the nodes in the right subtree.
* **Postorder**: (1) visit all the nodes in the left subtree, (2) visit all the nodes in the right subtree, (3) visit the root.

For example, to do an inorder traversal of your tree,

1. Visit the nodes, $(12, 25)$, in the left subtree.
2. Visit the root, $31$.
3. Visit the node in the right subtree, $(68,50,72,39,56,42,53,60)$

In step (1) we use the same rule: visit the left subtree of 12 (nothing there), then the root, 12, then the right subtree $(25)$. So now you've done task (1), having visited the nodes $12, 25$ in that order.

In step (2) we visit $(31)$, so now we've visited $12,25, 31$.

In step (3) we need to visit the nodes in the right subtree, using the rule Left-Root-Right, as we did before. It turns out that we'll visit the right subtree's nodes in order 39,42,50,53,56,60,72.

Doing this traversal by hand is complicated and prone to error. While computers are easily able to use these recursive rules, humans aren't so good at this. Fortunately, there's a three-step technique that's easy for people to apply.

1. Draw an upward-pointing triangle around each node in your tree.
2. "Shrink-wrap" the whole tree by drawing a closed circuit around the whole tree, making your circuit follow the tree as closely as possible, like this:

3. Starting at the root node, trace the circuit counter-clockwise, listing a node as visited when: for a **preorder** traversal, you encounter the node for the first time (that is, when you travel along the left side of the node's triangle); for an **inorder** traversal, mark the node as visited when you encounter the node for the second time (that is, when you travel around the base of the node's triangle); for a **postorder** traversal, mark the node as visited when you encounter it for the last time (when you travel along the right side of the node's triangle).

Try it for your tree and each of the three traversals and you'll see what happens.
> 5 votes

# Answer
These are recursively defined traversal methods, as you can see from your code. A stack is useful if you want to write an implementation without recursion. Wikipedia has some explanation of the three traversals, and proposes code for the stack implementations.
> 2 votes

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


title: How can words instruct machines?

text:
# Question
Title: How can words instruct machines?
How words can instruct hardware to do an operations . I understand that these are converted to 0s and 1s . But still I can't intuitively understand How it works . A detailed explanation would be appreciated .

# Answer
When converted to 0s and 1s, they're not words anymore, they are a configuration for the machine. In a way, they are words only as a help to our human understanding. As it often happens, we end up confusing our own conceptions with reality.

Computer networks, distributed systems and interactive computing add other layers of complexity to this picture. Since you cannot consider standalone computer as closed systems of hardware and software, it becomes even more tempting to see programs as transcendent writings, whose meaning commands the machines were they run.

It is definitely not the case. Words are aids, nothing more.

To put it differently: a program, or any kind of source code, is already given to the compiler as a sequence of 0s and 1s. Even if not directly composed of machine instructions, this sequence of bits can be deterministically converted to machine code. That's what a program translator (compiler, interpreter, emulator, etc.) does.
> 1 votes

---
Tags: programming-languages
---


# Question
Title: Show that the following algorithm doesn't always find the optimal matching
Consider the following algorithm for the maximum matching problem:

1. Sort all nodes by their $\deg(v)$
2. Take the node with minimal $\deg(v)$
3. Take a random edge $(u,v)$ $\in$ $E$
4. Add $(u,v)$ to $M$
5. Delete all edges of $u$ and $v$ in $E$

I have to show that the algorithm isn't correct for undirected graphs with maximum degree 3. (It does find the maximum matching if the maximum degree is 2.)

To prove that the algorithm does not find a maximal matching for a graph $G$, I have to give a counterexample.

My problem is that I am drawing and drawing graphs, but the algorithm is always able to find the optimal matching. Could somebody help me to find a graph where the algorithm cannot find the optimal matching?

# Answer
> 7 votes
Consider a graph consisting of two triangles connected by an edge (a total of seven edges). Using this graph, Besser and Poloczek show that no greedy-like algorithm for maximum matching can be optimal even on graphs with maximum degree 3.

---
Tags: graphs, matching
---


title: Data Structure with multiple indexes

text:
# Question
Title: Data Structure with multiple indexes
Apologies if a duplicate. New to this community and did try to search.

I want to create a mapping document that equates defect severity levels together so it looks like

```
|| System 1 || System 2 || System 3 ||
| level1-1 | level1-2 | level1-3 |
| level2-1 | level2-2 | level2-3 |

```

So that I can effectively do a lookup with a key of "level2-2" and get the row back. Similar I guess to a SQL row and being able to match on a column

Is there a name for this data structure?

# Answer
There are many data structures you could use for this purpose.

One possibility is a relational database (just like you've shown).

Another possibility is any data structure for storing equivalence relations; for instance, the standard Union-Find data structure would do. Here you'd be storing that `(System 1, level1-1)` is equivalent to `(System 2, level1-2)`, and so on. That would work, too.

---

\[ General advice for asking in the future: Don't worry too much about "names" for something. Names matter a lot less than finding a reasonable solution. Instead, think of the task you're trying to accomplish, what your requirements are, what you're trying to optimize, and then ask how to do that. You might get back an answer that says "read up on this standard thing"; or you might get back an answer that just directly describes a solution to your problem. Either way, you win! \]
> 1 votes

---
Tags: data-structures
---


# Question
Title: If a language is m-reducible to a regular language, does it mean that this language is also necessarily a regular language?
I've been going back and forth with this for a dew days, can't quite be sure.

When I look at the pumping lemma method, I think a context-free language could possibly be reduced to a regular language.

# Answer
> 1 votes
The answer to your question is no. There's a general result you can use in this case:

**Theorem**. If $A$ and $B$ are any decidable languages and $B\ne\varnothing$ and $B\ne\Sigma^\*$, then $A\le\_\text{M} B$.

This says that any nontrivial decidable languages are mapping reducible to each other. In other words, mapping reducibility tells you nothing about decidable languages.

Here's an example. Let $L=\\{0^n1^n\mid n\ge 0\\}$. This is a well-known non-regular language. Now let $R$ be, say the regular language $\\{0\\}$. Then $L\le\_\text{M} R$ by the mapping $f:\\{0, 1\\}^\*\rightarrow\\{0, 1\\}^\*$ defined by $$ f(s) = \begin{cases} 0\quad\text{if $s=0^n1^n$ for some $n\ge 0$}\\ 1\quad\text{otherwise} \end{cases} $$ It's obvious that $f$ is Turing-computable and that $s\in \\{0^n1^n\\} \Longleftrightarrow f(s)\in R$, which is exactly what you need to show that this non-regular language is mapping reducible to this regular language.

---
Tags: complexity-theory, formal-languages, reductions
---


# Question
Title: Calculating gradient in a neural net using batches
I am a CS student learning about neural nets. Currently I am confused about how to train a neural net in batches. If I calculate error in a batch, I will get a vector of errors e.g. real1 - predicted1, real2 - predicted2, etc... How do I then calculate a single gradient value to adjust the weights with?

# Answer
> 2 votes
This is known as *stochastic gradient descent*. I suggest you read some background material on stochastic gradient descent; then I think you will understand. There is lots written on that subject in many standard places.

Compare:

* In standard gradient descent, we let $E(w)$ denote the total error across all training samples (as a function of the weights $w$), compute the gradient of $E(w)$ (with respect to $w$), and use that gradient to update the weights.
* In stochastic gradient descent (in its simplest form), we pick a single training sample at random, let $E\_1(w)$ compute the error on just that training sample (as a function of the weights $w$), compute the gradient of $E\_1$ (with respect to $w$), and use that to update the weights. We repeat this many times. In each iteration, we pick a different randomly chosen training sample.

$E\_1(w)$ can be thought of as a noisy approximation to $E(w) $, so the gradient of $E\_1(w)$ can be thought of as an approximation to the gradient of $E(w)$. Thus, in each iteration of stochastic gradient descent, we are moving in a direction that is roughly correlated with the direction standard gradient descent will take, but with some noise; over enough iterations, hopefully this noise will average out. A crude intuition might be that $kn$ iterations of stochastic gradient descent are roughly comparable to $k$ iterations of standard gradient descent, if $n$ is the number of samples in the training set.
* Stochastic gradient descent with batches is a more sophisticated form of stochastic gradient descent, where we randomly choose a batch of training samples (more than one sample, but less than all of them), sum the total error across the batch, compute the gradient, and use that to update the weights.

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