# Question
Title: Why is the Turing Machine a popular model of computation?
I am a CS undergraduate. I understand how Turing came up with his abstract machine (modeling a person doing a computation), but it seems to me to be an awkward, inelegant abstraction. Why do we consider a "tape", and a machine head writing symbols, changing state, shifting the tape back and forth?

What is the underlying significance? A DFA is elegant - it seems to capture precisely what is necessary to recognize the regular languages. But the Turing machine, to my novice judgement, is just a clunky abstract contraption.

After thinking about it, I think the most idealized model of computation would be to say that some physical system corresponding to the input string, after being set into motion, would reach a static equilibrium which, upon interpretation equivalent to the the one used to form the system from the original string, would correspond to the correct output string. This captures the notion of "automation", since the system would change deterministically based solely on the original state.

**Edit**:

After reading a few responses, I've realized that what confuses me about the Turing machine is that it does not seem minimal. Shouldn't the canonical model of computation obviously convey the essence of computability?

Also, in case it wasn't clear I know that DFAs are not complete models of computation.

Thank you for the replies.

# Answer
Well, a DFA is just a Turing machine that's only allowed to move to the right and that must accept or reject as soon as it runs out of input characters. So I'm not sure one can really say that a DFA is natural but a Turing machine isn't.

Critique of the question aside, remember that Turing was working *before* computers existed. As such, he wasn't trying to codify what electronic computers do but, rather, computation in general. My parents have a dictionary from the 1930s that defines computer as "someone who computes" and this is basically where Turing was coming from: for him, at that time, computation was about slide rules, log tables, pencils and pieces of paper. In that mind-set, rewriting symbols on a paper tape doesn't seem like a bad abstraction.

OK, fine, you're saying (I hope!) but we're not in the 1930s any more so why do we still use this? Here, I don't think there's any one specific reason. The advantage of Turing machines is that they're reasonably simple and we're decently good at proving things about them. Although formally specifying a Turing machine program to do some particular task is very tedious, once you've done it a few times, you have a reasonable intuition about what they can do and you don't need to write the formal specifications any more. The model is also easily extended to include other natural features, such as random access to the tape. So they're a pretty useful model that we understand well and we also have a pretty good understanding of how they relate to actual computers.

One could use other models but one would then have to do a huge amount of translation between results for the new model and the vast body of existing work on what Turing machines can do. Nobody has come up with a replacement for Turing machines that have had big enough advantages to make that look like a good idea.
> 77 votes

# Answer
You are asking several different questions. Let me briefly answer them one by one.

**What is so important about the Turing machine model?**

During the infancy of computability theory, several models of computation were suggested, in various contexts. For example, Gödel, who was trying to understand to which proof systems his incompleteness theorem applies, came up with the formalism of *general recursive functions*, and Church came up with the $\lambda$ calculus as an attempt at paradox-free foundations for mathematics. Turing himself was motivated by a problem of Hilbert, who asked for a "purely mechanical process" for determining the truth value of a given mathematical statement.

At the time, Turing's attempt at defining computability seemed as the most satisfactory. It eventually turned out that all models of computation described above are *equivalent* – they all describe the same notion of computability. For historical reasons, Turing's model came out as the most canonical way of defining computability. The model is also very rudimentary and so easy to work with, compared to many other models including the ones listed above.

The usual computer science teaches Turing machines as the definition of computability, and then uses them also to explore complexity theory. But algorithms are analyzed with respect to a more realistic model known as the RAM machine, although this issue is usually swept under the carpet as a secret for the cognoscenti.

**Aren't DFAs a better model?**

This was the original motivation behind Rabin and Scott's famous paper, Finite automata and their decision problems:

> Turing machines are widely considered to be the abstract prototype of digital computers; workers in the field, however, have felt more and more that the notion of a Turing machine is too general to serve as an accurate model of actual computers. It is well known that even for simple calculations it is impossible to give an a priori upper bound on the amount of tape a Turing machine will need for any given computation. It is precisely this feature that renders Turing's concept unrealistic.
>
> In the last few years the idea of a finite automaton has appeared in the literature. These are machines having only a finite number of internal states that can be used for memory and computation. The restriction of finiteness appears to give a better approximation to the idea of a physical machine. Of course, such machines cannot do as much as Turing machines, but the advantage of being able to compute an arbitrary general recursive function is questionable, since very few of these functions come up in practical applications.

It turned out, however, that whereas Turing machines are too strong, DFAs are too *weak*. Nowadays theoreticians prefer the notion of *polynomial time computation*, though this notion is also not without its problems. That said, DFAs and NFAs still have their uses, chiefly in compilers (used for lexical analysis) and network devices (used for extremely efficient filtering).

**Isn't the Turing machine model too limited?**

The Church–Turing thesis states that Turing machines capture the physical notion of computability. Yuri Gurevich has led an attempt at proving this thesis, by formulating a more general class of computation devices known as abstract state machines and proving that they are equivalent in power to Turing machines. Perhaps these machines are analogous to your idealized model.
> 59 votes

# Answer
The underlying significance is about the idea of Turing-equivalence. The exact model isn't important, as long as it is Turing-equivalent. But it's better to use a simpler model so you could prove equivalence to other models easier.

More exactly, it's better to make it easier to simulate this model in other models, as we know most of the advanced programming languages are Turing-equivalent (with certain assumptions about memory addresses) and can be used to simulate other models.

There are other models, such as the lambda calculus and (string rewriting) grammars. But it's easier to define time and space constraints in a Turing machine. You could also use a programming language such as Brainfuck, but it requires unnecessary work to for example redefine the symbols to get a logically trivial modification sometimes.

So, the Turing machine seemed to be quite appropriate to me if you have to learn a single model for everything. But if you are going to learn multiple models anyway, I see nothing wrong to learn lambda calculus for the idea of Turing-equivalence, Brainfuck for proving other models Turing-equivalent, and practical programming languages (better with accessible stack and no hidden variables) for time / space constraints, and only consider the Turing machine a tool to prove these things equivalent if nobody is bothered to find a way around it. This naturally happens if you didn't start with learning the underlying theory first, but only did it when you found them useful.
> 17 votes

# Answer
I'd like to respond to this part of the question, added in an edit:

> "Shouldn't the canonical model of computation obviously convey the essence of computability?"

One of the remarkable things that Turing did in his original paper -- the one which introduced what we now call "Turing machines" -- was that he constructed a *single* Turing machine that can simulate every other Turing machine. Once this "universal Turing machine" is built, it works by making an input tape which has two independent features: first, an encoding of the Turing machine $T$ that one wishes to simulate; then, a copy of the input tape that one would have inserted into the Turing machine $T$, if one happened to have $T$ sitting around. In semimodern jargon: first, one inserts a program which the universal Turing machine compiles; then, one inserts the input which the universal Turing machine runs using the compiled program.

That's one of the essences of computability: Whatever general notion of computability one has in mind, there should be a single machine which does it all. That's exactly what a universal Turing machine does. It's also what modern computers do (subject to the physically unrealistic idealization of having infinite memory).

Another way of putting this, which directly addresses your concern that Turing machines are not minimal, is that they are just as minimal as they can be, subject to the requirement that they describe a general notion of computability for which there exists a universal machine.
> 14 votes

# Answer
Turing Machines are not meant to be used literally; programming in them is something one would only do once as an exercise, to understand how they work.

They are specifically not made to "do" anything. They do not need to be minimal, they do not need to be comfortable to work with.

They are simply a model of a machine you *could* build, which would be as expressive and powerful as any other machine you could ever build in the physical universe (as far as we know today).

They were defined by Turing the way they are for these main reasons:

* To be able to prove that they encompass *any and all* algorithm we could ever think of.
* To work on the halting problem / decision problem.
* To be able to reduce any other machine/language to this one.

Would it have been possible to pick another language? For sure! Any of the turing complete languages we know today could have been used. But it would have been *much* harder to build the theoretical groundwork on a more complex machine.

I would argue that they are not even a "popular model of computation"; nobody would ever compute anything with a Turing Machine. It is a purely theoretical concept, made by theoretic computer scientists, for t.c.s's.
> 5 votes

# Answer
**Why is it popular, maybe the most popular?** You must remember that Turing inevented this "machine" a lot of years before electronic computers. The TM is operated with a paper, a pen, a rubber and last but not least, a human brain. So everybody is able to run a "computation" with this machine. Everybody means a person who never learned computers, programming langages. It is simple to use. When you think it about, you discover a paradox: this machine is a assembly of almost nothing but you can operate everything. To my opinion the paradox of "almost-nothing/versus/everything" is the reason why it is popular. I would notice that the TM does not explicitly explain recursion, teh TM only deals with "jump". That feature (explicitly talking about recursion) may be a source of headhache for rookies, for instance in lambda-calculus the concept of Y-combinator is almost un-understandable; More precisely, the TM is popular because the paradox of "almost-nothing/versus/everything" without the recursion headhache.
> 5 votes

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


# Question
Title: Evolutionary algorithm - is there a relation between minimum iterations and size of decision variables
I am solving an optimization problem using SPEA2, my problem has three cases with decision variables 25, 50 and 100 in each case. I want to ask if there is some relationship between the number of variables and iterations of evolution process. I mean to say I run algorithm fewer times when decision variables are 25 than once they are 50. Thanks in advance.

# Answer
> 0 votes
As a very general heuristic, it's likely true that bigger problems are harder than smaller ones and benefit from more searching. Bigger populations, longer runs, etc. can be beneficial in that case.

The real question is whether your algorithm is converging or not. If you're converging before you find a good answer, more generations isn't going to help.

---
Tags: optimization, genetic-algorithms, evolutionary-computing
---


# Question
Title: How to express a structure of a 5-colorable graph in logic
A graph can be expressed as an structure $G = \<A,R\>$ satisfying the axioms $ \forall xy R(x,y) \rightarrow R(y,x)$ and $ \forall x \lnot R(x,x)$.

How to extend the structure and/or axioms to express a 5 colourable graph?

# Answer
General ideas:

* Require that each vertex ($\forall x \ldots$) satisfies at least one color predicate (Use $\lor$ among five color predicates).
* Also require that no vertex ($\lnot\exists x \ldots$) has two distinct colors (you can enumerate all the ten distinct pairs: $\lnot({\sf red}(x)\land{\sf blue}(x))\land \lnot(\ldots)\land \cdots$).
* For each color (repeat this axiom five times, once for each color), require that if $x$ has that color and $R(x,y)$ then $y$ has not that color (e.g. $\forall x y.\ {\sf red}(x)\land R(x,y) \implies \lnot{\sf red}(y)$).
> 2 votes

---
Tags: graphs, logic
---


title: video shape recognition in real time

text:
# Question
Title: video shape recognition in real time
I believe from common sense that video shape recognition problems (identifying shape of a moving object) is of natural interest in many real world situations. The process of identifying is understood as recognizing/finding one selected changing shape/signal among all the present shapes/signals. Ideally, it should be possible to track the shape.

I believe that this process (of recognising) might be computationally expensive (depends on the resolution). I would very much appreciate a survey level paper that summarises achievements so far.
It would be even better if the paper would point out to existing limits due to engineerical/hardware/technological restrictions. I am sorry that the question is a bit fuzzy.

# Answer
One standard approach is to use object detection / objection recognition / object localization on each individual frame of the video. This means we can apply algorithms for doing that on a single image. For speed, once you have detected an object in one frame, we can use object tracking to keep track of where it moves to in the next frames, and we don't need to use an expensive object detection algorithm on the next frame. For instance, we might apply object detection on every 10th frame, and then use object tracking to track its motion for the next 9 frames.

That should give you enough keywords that you can search and find lots of information on each of those techniques.
> 1 votes

---
Tags: optimization, computational-geometry, pattern-recognition
---


# Question
Title: Is Blum's theorem for acceptable enumerations of partially computable functions bidirectional?
Theorem II.5.8 in P. Odifreddi's *Classical Recursion Theory* states that

> If $\\{\psi\_e\\}\_{e\in\omega}$ is an acceptable system of indices, then there is a recursive permutation $h$ such that $$ h(\psi\_e(x)) = \varphi\_{h(e)}(h(x)) . $$

where $\varphi$ is the standard enumeration of p.c. functions.

My question is whether the converse case holds: For the standard enumeration $\varphi$, some permutation $h$ and some computable enumeration of p.c. functions $\psi$, if we have $h(\psi\_e(x)) = \varphi\_{h(e)}(h(x))$, then $\psi$ is an acceptable enumeration.

---

Some possible approaches:

1. Prove this simpler form and then prove it is equivalent to question:

For some computable permutation $h$ and standard enumeration $\varphi$, $\theta\_e(x) = h(\varphi\_e(x))$ is also an acceptable enumeration.

2. H. Rogers' *Theory of Recursive Functions* p54, defines a *universal partial function* to be a partial computable function $\psi$ for which exists a computable function $f$ of two variables, such that $\forall x; \varphi\_x = \lambda y.\psi f(x,y)$. So $f$ *codes* both index and argument and $\psi$ takes it as its single input. Then it proves that

> If $\psi$ is universal and $g$ and $h$ are recursive permutations, then $\eta = g^{-1}\psi h$ is universal.

Is this statement, for $g=h$, equivalent to the mentioned converse above?

It seemed very obvious to me at first, though I couldn't manage to prove it. What am I possibly missing?

---

**Update** Removed the second question as an intermediate approach to solve the main question.

# Answer
> 0 votes
For the standard enumeration $\varphi$ and some computable permutation $h$, $$\forall e;~ \psi\_e = h^{-1} \varphi\_{h(e)}h ~~~~(\*)$$

We want to prove that such $\psi$ is an acceptable enumeration. It suffices to find computable functions $f$ and $g$ such that for all $e$, $\psi\_e = \varphi\_{f(e)}$ and $\varphi\_e = \psi\_{g(e)}$.

$h^{-1} \varphi\_{h(e)}h$ is partial computable. So by *s-m-n theorem*, there is a computable function $f$ such that for all $e$, $h^{-1} \varphi\_{h(e)}h = \varphi\_{f(e)}$, therefor by $\*$ we have, $\psi\_e = \varphi\_{f(e)}$

$h \varphi\_e h^{-1}$ is also partial computable. So again by s-m-n theorem, there is computable $g'$ such that for all $e$, $h \varphi\_e h^{-1} = \varphi\_{g'(e)}$. Define computable function $g$ as $g = h^{-1} g'$. In $\*$ replace $e$ with $g(e)$ to get $$\psi\_{g(e)} = h^{-1} \varphi\_{hg(e)}h ~.$$ By definition of $g$, we have $h g = h h^{-1} g' = g'$, so $$\psi\_{g(e)} = h^{-1} \varphi\_{g'(e)}h ~.$$ By definition of $g'$ $$\psi\_{g(e)} = h^{-1} h \varphi\_e h^{-1} h ~,$$ and thus $$\psi\_{g(e)} = \varphi\_e ~. ~~\Box$$

---
Tags: computability
---


title: Transitivity of quasi-reducibility

text:
# Question
Title: Transitivity of quasi-reducibility
A set $A$ is quasi-reducible to $B$ ($A \leq\_Q B$) if there is a recursive function $f$ such that $$x \in A \iff W\_{f(x)} \subseteq B$$ Or equivalently $$ x \in \overline{A} \iff W\_{f(x)} \cap \overline{B} \neq \emptyset $$ Where $W\_{e}$ is the domain of the recursive function of index $e$, i.e. $W\_{e} = \\{y : \varphi\_{e}(y) \downarrow\\}$.

Everywhere I look it says the transitivity of the relation is easy to see, but for some reason it doesn't click for me.

# Answer
Ok I think I have found it.

Let $A$, $B$ and $C$ such that $A \leq\_Q B$ and $B \leq\_Q C$, respectively by the recursive functions $f$ and $g$. Let \begin{align\*} h : x,y \mapsto & \text{ find } b \in W\_{f(x)} \text{ and } c \in W\_{g(b)} \text{ such that } y = c \\ & \text{ return } 0 \end{align\*} By $s$-$m$-$n$ we have a recursive function $s$ such that $\varphi\_{s(x)}(y) = h(x,y)$.

Assume $x \in A$. If $y \in W\_{s(x)}$, then $\exists b \in W\_{f(x)}$ and $\exists c \in W\_{g(b)}$ such that $y = c$ so $b \in B$ and $c \in C$ by the assumed reductions, so $y \in C$ and $W\_{s(x)} \subseteq C$.

Now if $x \in \overline{A}$, then $\exists b \in W\_{f(x)} \cap \overline{B}$ and $\exists c \in W\_{g(b)} \cap \overline{C}$, so $h(x,c)\downarrow$ and $c \in W\_{s(x)} \cap \overline{C}$.

So we can conclude $A \leq\_Q C$.

Let me know if you think there's a problem with this.
> 1 votes

---
Tags: computability, reductions
---


# Question
Title: Testing two distributions, both accept null hypothesis
I have a sample that is collected to verify the accuracy of a new random number generator. Applying the goodness of fit test to check if this sample comes from the Standard Normal Distribution and Uniform Distribution, I found out that both of these accept null hypothesis although they are contradicting to each other. Is it theoretically possible? Why?

# Answer
> 1 votes
Hypothesis tests don't accept the null hypothesis. Instead, they fail to reject the null hypothesis. That's not the same thing. For instance, if your sample size is small enough, it's certainly possible to fail to reject both null hypotheses. All that the tests are saying is that the hypotheses "this data came from a standard normal" and "this data came from a uniform distribution" both seem plausibly consistent with the data, and that's not impossible.

---
Tags: statistics, sampling, random-number-generator
---


# Question
Title: What is the difference between a block and a procedure?
A procedure is a sequence of program instructions that perform a specific task, packaged as a unit (Techopedia).

We use block structure to make our code more readable by using indentations and spaces.

Now, is one block the same as a procedure and is vice versa true?

# Answer
Such terminology is language specific. In programming languages I've seen, they are not the same.

A procedure (or function) definition is a block of code with a header, that specifies 0 or more arguments, and a name. It allows the procedure to be called by specifying its name and a list of argument values. In many languages, anonymous functions or procedures can be defined, which have a block of code and a header with arguments, but no name. In some languages, a block can act as an anonymous procedure or function without arguments; in other languages, it cannot.

For instance, in C, Java and C#, a block just serves to group statements and create a scope for local variables; it cannot be used as a procedure/function.

In Perl, on the other hand, blocks can be used in contexts that expect procedures/functions (subroutines), and in PostScript, a block denotes a code object (a procedure) that can be bound to a name.

I've never used blocks in Lisp, but apparently, the situation is much the same there: a Lisp procedure (*function*, in Lisp) contains a block, implicitly, but a block by itself does not constitute a procedure. It cannot be called by giving its name and values for its arguments, if I understand correctly.
> 1 votes

---
Tags: lisp
---


# Question
Title: Partitioning in time complexity of the sum
We all know the partitioning problem: Given a super-set S of integers, can we partition S into 2 subsets with the same sum. And of course this problem is NP-complete.

My question is - let's denote M as the sum of all numbers in S. Is O(M) considered to be polynomial in this case?

I will clarify: I want to prove that a certain problem is NP-hard, and in order to do so I use a reduction from partitioning that uses O(M) nodes in a graph. Is this considered to be a polynomial build?

# Answer
> 2 votes
A Turing machine $T$ runs in polynomial time if there is a polynomial $p$ such that the running time of $T$ on an input of length $n$ bits is at most $p(n)$. The same definition works for other machine models such as the RAM machine.

Whether $O(M)$ is polynomial time or not depends on the way you encode the input. If the input is encoded in binary, then $O(M)$ isn't polynomial time, since the input could be of length as low as $O(\log M)$. If the input is encoded in unary (i.e., a number $x \geq 0$ is encoded as $1^x$) then $O(M)$ is polynomial time. It is part of the definition of the problem to specify the way the input is encoded.

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


# Question
Title: Algorithm Comparison with Theta-notation
We consider two algorithms, Algo1 and Algo2, that solve the same problem. For any input of size n, Algo1 takes time $T\_1(n)$ and Algo2 takes time $T\_2(n)$.

Prove or disprove each of the following statements.

To prove a statement, you should provide a formal proof that is based on the definitions of the order notations. To disprove a statement, provide a counter example and explain it.

Suppose that $T\_1(n)$ ∈ $\theta(n^2)$ and $T\_2(n)$ ∈ $\theta(n^3)$.

Does it imply that there exists $n\_0$ such that for $n$ ≥ $n\_0$, Algo1 runs faster than Algo2 on inputs of size $n$?

By definition of $\theta$-notation,$\\\$

If $T\_1(n)$ ∈ $\theta(n^2)$, then $c\_1 n^2 \leq T\_1(n) \leq c\_2 n^2$ for all $n \geq n\_1$for $c\_1, c\_2, n\_1 \> 0$.

If $T\_2(n)$ ∈ $\theta(n^3)$, then $d\_1 n^3 \leq T\_2(n) \leq d\_2 n^3$ for all $n \geq n\_2$ for $d\_1, d\_2, n\_2 \> 0 $.

We choose $n\_0 = max(n\_1, n\_2)$

Then, $\\\$ $\frac{c\_1 n^2}{d\_1 n^3} \leq \frac{T\_1(n)}{T\_2(n)} \leq \frac{c\_2 n^2}{d\_2 n^3} \text{ for all } n \geq n\_0$

$\lim\_{n \rightarrow \infty} \frac{c\_1 n^2}{d\_1 n^3} = 0$ and $\lim\_{n \rightarrow \infty} \frac{c\_2 n^2}{d\_2 n^3} = 0$

Hence, by Squeeze Theorem, $\lim\_{n \rightarrow \infty} \frac{T\_1(n)}{T\_2(n)} = 0$. Therefore, Algo1 runs faster than Algo2 for $n \>= n\_0$

This is my solution, and I am wondering if this is right way to solve this question.

Any help is appreciated, thank you,

# Answer
If $T\_1(n) = \Theta(n^2)$ and $T\_2 = \Theta(n^3)$, then since $n^2 = o(n^3)$, it follows that $T\_1(n) = o(T\_2(n))$. In particular, $T\_1(n) \< T\_2(n)$ for large enough $n$. In fact, for every $C\>1$, $T\_1(n) \< CT\_2(n)$ for large enough $n$ (how large depends on $C$).
> 0 votes

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


# Question
Title: $\mathsf{PSPACE}$ membership in exponentially many steps?
I am trying to argue that a certain problem is in $\mathsf{PSPACE}$ and my question is, essentially, whether it is ok to have an algorithm that takes an exponential number of steps as long as, overall, the whole thing stays in polynomial space.

The context for this is that I have a naive algorithm which, it seems to me, shows $\mathsf{PSPACE}$ membership, but I am not entirely certain of the logic behind it.

I can be more concrete. Say we have a set $M$ and a transitive binary relation $\>$ on $M$. $M$ is exponentially large (think all possible assignments), and $\>$ can be partial and have cycles. If $a\>b$, for $a,b\in M$, then we say that *$a$ dominates $b$*. If $a$ dominates every element in $M$ (including itself), we say that *$a$ is dominating*.

I know that, given $\>$ and some $a\in M$, determining whether $a$ is dominating in $\>$ is $\mathsf{PSPACE}$-complete. Call this the $\mathsf{DOMINATING}$ problem, and we can take it as a given that it is $\mathsf{PSPACE}$ complete.

The problem I am faced with is now is what we could call the $\exists\mathsf{DOMINATING}$ problem: given $\>$, determine whether there exists a dominating element in $\>$.

My naive algorithm for $\exists\mathsf{DOMINATING}$ is as follows: take every element in $M$, ask whether it is dominating in $\>$, and stop if one is found. This, it seems to me, is in $\mathsf{PSPACE}$: even though we might have to go through an exponential number of $\mathsf{PSPACE}$ queries, we stay in polynomial space throughout.

# Answer
> whether it is ok to have an algorithm that takes an exponential number of steps as long as, overall, the whole thing stays in polynomial space.

Yes, of course. Polynomial space means exactly what it says.

The only reason you should worry is if you think that your algorithm takes more time than $2^{n^c}$ for all $c$. In that case, it must either use more than polynomial space or loop forever since, there are only $|\Sigma|^{n^k}$ configurations of a tape of length $n^c$ using alphabet $\Sigma$, only $n^k$ possible head positions and only a constant number of possible states. That means there are only $|Q|n^k|\Sigma|^{n^k} \leq 2^{n^c}$ (for large enough $c$) possible configurations for a polynomial space Turing machine so if it runs for more than that many steps, it must have seen the same configuration twice so it must be in an infinite loop.
> 3 votes

---
Tags: complexity-theory
---


# Question
Title: How to simulate a bidirectional TM on a regular one with time factor four?
In *Computational Complexity A Modern Approach*, one claim says that if $f$ is computable in time $T(n)$ by a bidirectional TM $M$, then it is computable in time $4T(n)$ by a unidirectional TM $\tilde{M}$. How to work out the constant $4$?

In my opinion, in addition to "go over the edge" operation, one transition in $M$ corresponds to one transition in $\tilde{M}$, so where does constant $4$ come from?

# Answer
> 1 votes
In the book you mentioned above you simulate a infinitely long bidirectional TM increasing the number of symbols and by **"“folding” it in an arbitrary location"**. Thus each cell in the unidirectional TM will represent 2 symbols or a pair. So this can be **x/(symbol or blank), x/y or (symbol or blank)/x**. Now T(n) is the worst case scenario. Let us assume that the current state of the TM is as follows

^ symbol for blank.

e/h|l/^|l/^|o/^|!/^|?/^ (this is equivalent to h|e|l|l|o|!|? in a bidirectional TM, basically bend on the first position itself). with head pointing to **?/^**, now if I want to write to the position I have to write as a pair. But I cannot read the second symbol in the pair without iterating to the left most position and then to the right again. So from the head position **?/^** we have to iterate **6 times to the left and 5 times to the right** to read **"^"**. Once we read **"^"** we have to return, so **iterate back so 6 times to the left and then 5 times to the right**. Now that we know the second symbol in the pair, we can write the new symbol for ex . **"u/^"**. In a more generalized sense to write something in a Tape in the above state we have iterate the length of the tape(n) 4 times. So it will take 4 times more time to halt on a regular TM in the worst case, so t(n) = 4t'(n).

---
Tags: turing-machines, simulation, computation-models
---


# Question
Title: $O(n\log n)$- algorithm for finding tree root
All numbers from $1$ to $n = 2^k-1$ are written in unknown way in a full binary tree of height $k$. We say that a number $t$ lies between $i$ and $j$ if after removing $t$ from the tree we obtain that $i$ and $j$ are in different connectivity components. Propose an algorithm for determining a number in the root of tree asking $O(n\log n)$ questions of the type "Is $t$ lies between $i$ and $j$"? The answer may be "yes" or "no".

I will be gratefull for hints and ideas.

# Answer
**Routine 1** Firstly, observe that only the root node disconnects the tree into exactly two equal connected components of size $2^{k-2}-1$. All other nodes disconnect the tree into three or zero connected components. We have the following $\mathcal{O}(n)$ approach to check if a given node is the root.

1. Let the node to check be $x$.
2. Pick another node $y \not= x$
3. Iterate through all other nodes $z \not\in \\{x,y\\}$ and ask if $x$ disconnects $y$ from $z$.
4. If there are $2^{k-2}-1$ nodes in the connected component of $y$, then $x$ is a root, else it isn't.

**Routine 2** Now, let's present an $\mathcal{O}(n)$ algorithm to identify leaves. Observe that a random node has $\ge 0.5$ probability of being a leaf node. Hence our algorithm is -

1. Pick a random node in the tree, say $x$.
2. Pick another random node $y$.
3. If $x$ does not disconnect $y$ from $z$, for all valid $z$, then $x$ is a leaf node in the tree.
4. Repeat steps 1, 2 and 3 till you obtain a leaf.

The expected number of queries used by this algorithm is $\mathcal{O}(n)$.

**Routine 3** Now let's make the next observation. There are $2^{k-1}$ nodes in the last level of this complete binary tree. Colour these leaf nodes with two colours, red and blue. A leaf is coloured red if it belongs in the left sub tree of the root and blue otherwise. Using **Routine 2**, we will try to find a pair of leaf nodes one of which is red and the other is blue in $O(n)$ queries. Here is how -

1. Find any leaf node using the algorithm in **Routine 2**. Call this leaf node $u$.
2. Find a different leaf node, call this $v$.
3. $u$ and $v$ are of different colour if and only if exactly $2k-1$ nodes can disconnect $u$ from $v$, i.e., the nodes on the path that connect $u$ to $v$ (We assume that deleting $u$ will disconnect $u$ from $v$). This can be verified in $\mathcal{O}(n)$ queries as well by iterating over all nodes once.
4. Repeat steps 2 and 3 till you find the desired leaf node.

The probability that a random node is a leaf node and is of a different colour than $u$ is $\ge 0.25$. Hence the expected number of queries asked in this algorithm is also $\mathcal{O}(n)$.

Now that we have our two leaf nodes of different colours, we are ready to make the final observation, i.e., the root node must be one of the $2k-1$ nodes that can disconnect $u$ from $v$. Thus there are $2k-1 = \mathcal{O}(\log{n})$ candidates for the root node. We can iterate through each of them and check if they are the root using **Routine 1**.

Thus this algorithm uses $\mathcal{O}(n\log n)$ queries.

**EDIT** The final step can be improved to $\mathcal{O}(\log^2{n})$ by running **Routine 1** on just the $2k-1$ candidates to find the node that splits the path from $u$ to $v$ into two equal connected components. Thus the problem can be solved in $\mathcal{O}(n)$ queries as well.
> 3 votes

---
Tags: algorithms, algorithm-analysis, data-structures, trees, binary-trees
---


# Question
Title: How does reducing the Halting problem prove the reduction cannot exist?
For example, take the problem "Does M Halt on the Blank Tape?".

My approach was to reduce the halting problem to prove this problem is also undecidable. I generated a Mw by

1. Writing w on the tape
2. Moving to the leftmost blank
3. Running M

Then, of course there is the M-halt-on-blank function:

```
if(Mw halts)
    true
else false

```

Where I am having difficulty is understanding how this "proves" the halting problem. The halting problem is supposed to take in an input w and a machine M and tell if M halts on w. If we are creating Mw by taking w and modifying it, and running M on the modified tape, then M isn't really running on w at all. Instead, it is running on this modified tape. This would mean there is an infinite amount of w's that cannot even be run on M. So by using M-halt-on-blank as a decider, how is that solving the halting problem, and thus proving itself to be undecidable?

I understand there are a few similar posts but I am more concerned with the ends than the means for this problem, and I didn't find previous posts to answer this.

# Answer
First, I think you're confused about some terminology.

* You don't "prove the halting problem". In computer science, problems are computational tasks: you don't prove tasks; you perform them. Or, in this case, you you prove that there is no algorithm that decides the halting problem.
* You don't "reduce the halting problem". A reduction is a conversion between two problems so, when you talk about reductions, you need to say what you're reducing from and what you're reducing to.

Second, you've confused which way this reduction is going. You're trying to prove that the blank-tape halting problem is undecidable, and you do this by proving that a problem that is known to be undecidable (in this case, the halting problem) reduces to it. That is, you prove that, if you could solve the blank-tape halting problem, you could solve the ordinary halting problem.

The reduction works like this. Suppose there is an algorithm that decides whether a Turing machine that's given as its input halts when started with a blank tape. The input to this algorithm is a description of the Turing machine (its "source code", if you like) and it somehow analyzes its input and says either "Yes, that machine halts when started with a blank tape" or "No, it doesn't." We'll use this machine to determine if a given Turing machine $M$ halts when started with input $w$ (i.e., to solve the ordinary halting problem). The new algorithm is this: we take the description of $M$ and the string $w$ and we produce a new Turing machine description $N$. The source code for $N$ says, "First, delete your input. Then, write $w$ to the tape, one character at a time. Then, rewind the tape to the start and do exactly what $M$ does (i.e., it then includes a copy of $M$'s source code)." Note that each different value of $M$ and $w$ will give a different machine $N$. Now, we just ask our algorithm for the blank-tape halting problem if $N$ halts when given no input, and that tells us whether $M$ halts when given input $w$.

That is, we've used the blank-tape halting problem to solve the ordinary halting problem. However, we know that the ordinary halting problem is undecidable so something must have gone wrong. The translation of $M$ and $w$ to $N$ is completely fine: it's just some small edits to a machine's source code. So the impossible thing must have been the assumption that we have an algorithm for the blank-tape halting problem. There must be no such algorithm, which is the very definition of the problem being undecidable.
> 5 votes

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


title: Provide a derivation from backwards on?

text:
# Question
Title: Provide a derivation from backwards on?
Suppose you have to provide a derivation by natural deduction, e.g.

$((A \rightarrow B) \rightarrow A) \rightarrow A$

Is it a good advice to start from backwards on in general? I mean doing the derivation from bottom to top. The required premises or hypothesis should arise by itself.

# Answer
In general, proof crafting is a dark art. There is no simple universal strategy which in all cases leads to a proof, in the shortest way, with the least effort. One usually relies on instinct and experience (doing several exercises helps greatly).

Trying to reconstruct the derivation bottom-up is often a good strategy. However, note that in natural deduction (unlike some other systems) going bottom-up one needs to cope with infinitely many possibilities.

For instance, if I have to prove $A$, I could try to deduce it through modus ponens / implication elimination:

$$ \dfrac{\dfrac{\vdots}{B\rightarrow A} \qquad \dfrac{\vdots}{B}}{A} $$

However, formula $B$ above could be anything! I have to chose among infinitely many formulas, which is not easy.

Worse, in some cases it is needed to exploit some rule like double negation elimination

$$ \dfrac{\lnot\lnot A}{A} $$

It is not obvious when this is needed. For instance, I know that using this rule (or something equivalent like the law of excluded middle) is needed to prove $((A \to B)\to A)\to A$, but I can see this only because this is a very famous logical formula (called Peirce's Law).

At the end of the day, one can try a few heuristics, but should expect to have to backtrack a few times. In general the problem is very hard, but fortunately the exercises which one finds in books / exams usually are solvable with some intuition and little backtracking.
> 2 votes

---
Tags: logic
---


title: Manipulating Adjacency matrix

text:
# Question
Title: Manipulating Adjacency matrix
I have created an adjacency matrix which looks something like this

```
    A   B   C   D   E   F   G   H   I
A   0   0   0   0   0   0   0   0   0
B   1   0   0   0   0   0   0   0   0
C   1   0   0   0   0   0   0   0   0
D   0   0   0   0   0   0   0   0   0
E   1   1   0   1   0   0   0   0   0
F   1   1   1   1   1   0   0   0   0
G   0   0   1   1   0   0   0   0   0
H   0   1   0   0   0   0   1   0   0
I   1   1   0   0   0   1   0   0   0

```

I am trying to manipulate this matrix such that an indirect link between two alphabet will replace the direct link. e.g. In the graph, C is connected to A and F is connected to both A and C (among others) and I is connected to both A and F. How do I go about removing the direct connections such as A and F, A and I since there are indirect connection between (C to A and F to C, C to A and F to C and I to F).

I tried using loop but it seems like more the indirect connection, the number of loop required increases as well. What type of algorithm should I use for this type of problem? Would adjacency list be a better alternative?

# Answer
> 1 votes
If I understand you correctly, one solution to your problem would be to compute a spanning forest. A spanning forest of a graph is a smallest possible (in terms of number of edges) graph such that there's a path between two vertices in the forest if, and only if, there's a path between them in the original graph.

---
Tags: algorithms, adjacency-matrix
---


# Question
Title: Better algorithm for aggregating data from various LDAP systems
I have 10 LDAP systems which contain users and groups in the form of objects. Each user / group is identified by a `distinguishedName` like `name/systemName` where name is name of user or group.

Group objects store which users are members of the group.

```
GroupA = {UserA, UserB, UserC ....}
GroupD = {UserF, UserB, UserK ....}

```

This information is not stored in the users object. User objects have user related attributes.

```
UserA = {name="ABC", dob="x/x/x", }
UserB = {name="PQR", dob="x/x/x", }

```

I want to make a system, which will query all systems to get user and group objects and show them on GUI this way

```
UserA = {name="ABC", dob="x/x/x", memberOf=[GroupA]}
UserB = {name="ABC", dob="x/x/x", memberOf=[GroupA, GroupB]}

```

There are millions of users and millions of groups in these systems overall. The software I have created runs on various machine simultaneously. The software is written in Java.

I am using this **approach** to achieve this:

* Start my program on one machine - Machine#1
* Get all group objects from all the systems one by one and store them in memory store with key as user and value as list of group names
* Once all the groups are queried and stored in memory store, then fire my program on other machines too
* Other machines will copy the memory store created on Machine#1 to their machine (using third party lib - ehcache)
* Program on each machine will query some set of Systems (Machine#1 will query system 1,2,3; Machine#2 will query 4,5,6 .. and so on)
* Get all user objects and as I receive each user object, query memory store to see if user has any groups attached. If yes, pick them and store in DB?
* Once all the programs on all machines are finished, we have result in DB which can then be shown anywhere

This approach has following **disadvantages**:

* Consumes lot of memory (memory stores uses 20 GB RAM on one machine)
* Memory store which needs to be replicated on other machines is not so stable process
* Memory store is only built on single machine. This takes about 3 hrs to complete. During this time, other machines are idle, which is waste of resources.

**End goals** of application should be:

* Best performance possible
* Minimal wastage of computing time
* Data (user objects showing groups) should be available in said format. The format cannot be changed as there is dependency with other downstream systems.

**Is there a better approach to achieve the same ?**

# Answer
Your algorithms seem fine. I don't think you need better algorithms; I suspect what would help most is more on the engineering and implementation side.

At a high level, I would say that your design seems good enough as is. If the primary objection is that it requires 20GB of RAM, well, buying RAM is a lot cheaper than spending a day of a software developer's time to implement a more memory-efficient solution. So my primary advice would be to order some more RAM and call it good enough.

But if you still want to push on, I'll offer some other reactions...

Millions of users and groups is a fairly small data set. 20GB of RAM seems excessive for that. Suppose there are 5M users, and each user is a member of 5 groups on average (say), and each group name is 10 characters long on average. That corresponds to 50 bytes of data per user. Add some overhead and round up and I'd estimate something like 80 bytes per user. Yet your current data structure seems to be using 4KB per user. That seems 50x too large; I would have expected something like 400MB would be sufficient.

Therefore, I'd suggest you do some memory profiling and look into why your in-memory store is taking up so much memory. Perhaps you are using an unnecessarily inefficient data structure or hashmap implementation. Keep in mind that you don't need to store the entire user object and group object (with all their attributes) in memory. All you need to store in memory is the name of the user (a string) and the names of the groups they are in (a list of strings); the attributes can be stored in the database. There are other techniques for reducing memory, such as sharding the data structure across multiple machines, but that hardly seems necessary or worth the effort.

Also, I wonder whether it's really necessary to run on multiple machines. With only a few million users, I would have expected one machine to be more than adequate. So if you care about the time to completion, you might want to look into that. If you can do it on one machine, that will be simpler to implement, simpler to deploy, simpler to maintain, simpler to manage, and will reduce your stress about tying up 20GB of RAM on multiple machines. I would have expected that the rate-limiting step is the number of LDAP queries you can make per second, so you could investigate what is keeping that down. Perhaps you can have multiple threads making LDAP queries in parallel. Perhaps you can reuse the same connection for multiple queries, to avoid connection setup and teardown costs. Maybe you can run this on the same machine as the LDAP server to reduce network overhead. Maybe you can think of some other speedups.

But overall, my guess is that this is a problem better solved by a beefier hardware rather than a software developer's time to optimize the code; and if you do want to improve the software, you're more likely to see gains from focusing on quality of implementation rather than algorithms.

---

Based on your comments, here is an alternative data structure that might save memory. Assign each user and each group a unique integer ID (incremented by one for each new user/group). Keep a mapping from name of user -\> ID of user (with a hashtable) and a mapping from user ID -\> user name (with an array); this is probably doable with 2-4GB, based on your numbers. Do the same for groups; that's probably much less. Then, keep a mapping from user ID -\> array of group IDs that the user is in; that's probably doable with another 2-4GB. All in all, I'd expect this could reduce your memory consumption to 4-8GB instead of 20GB. You might be able to get further reduction by storing names in UTF-8 rather than UTF-16.
> 2 votes

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


# Question
Title: The "complexity" of the Turing machine state specification
Suppose we want to represent some arbitrary Boolean function $f(x\_1,x\_2,...,x\_N)$ on $N$ bits. We can explicitly specify such a representation using the disjunctive normal form. For "most" Boolean functions, this representation will be of length exponential in $N$, and incompressible (as per Shannon). We will assume we have chosen such an incompressible function.

We can build a Turing machine corresponding to this circuit, which ACCEPTs an input $\mathbf{x}$ if and only if $f(\mathbf{x}) = 1$. We can then ask what complexity such a Turing machine would have.

Now, the subtlety is: since our function is incompressible, any attempt to physically represent it must, naively, be "exponentially large"... in some sense. But we can "hide" the "exponentialness" of this in various places based on how we define our Turing machine, which would appear to change its computational complexity.

How does complexity theory handle this case?

Now, if we *were* treating the DNF as part of the input, we could create a Turing machine and feed our DNF and some bitvector to evaluate as an "exponential-length" input. We would then know that our Turing machine would take time $O(2^N)$ just to *read* the DNF, so accounting for everything relative to $N$, we're in (at least) exponential time.

But, as we are "building the circuit into" the specification of the Turing machine itself, we can recognize this language in $O(N)$:

* Check if the first bit is 0 or 1. Then, we have a branch to two states corresponding to $f(0,x\_2,...,x\_N)$ and $f(1,x\_2,...,x\_N)$, and transition according to the input.
* Repeat with the second bit. For each possibility, we have two more states, yielding four states total: $f(0,0,...,x\_N)$, $f(0,1,...,x\_N)$, $f(1,0,...,x\_N)$, and $f(1,1,...,x\_N)$.
* Continue branching until the end, and then ACCEPT/REJECT according to the specification of our function.

Of course, our Turing machine is "pathological" in that it now requires an exponential number of states. But, technically, since time complexity does not take this into account, it looks like we've gone from $O(2^N)$ to $O(N)$.

We can "fix" this to obtain a Turing machine with only one nontrivial state that recognizes the language in $O(1)$! Simply change the alphabet to be of size $2^N$, so that bitvector is viewed "atomically" as a single entry in the alphabet. Then we encode membership in our Boolean function by a single state transition to ACCEPT or REJECT based on the input. Of course, now the problem is that our "$O(1)$ machine with one state" has an exponentially large state transition table.

**My question**: What is the complexity of our language, expressed relative to $N$? Naively, I would like to say it's in EXPTIME, since the "exponential speedups" given by the last two Turing machines are clearly pathological, but I don't normally see this metric accounted for anywhere in complexity theory.

In general, how does complexity theory handle this? Are such pathological machines explicitly excluded in the main results of the field, and if so, what criterion do we use for excluding them?

# Answer
Complexity theory typically handles asymptotics, not finite cases. In particular, complexity theory looks at the asymptotic running time *as a function of $N$*. If you have only a single fixed $N$, then the standard framework doesn't apply. It's not possible to talk about the running time being asymptotically an exponential function of $N$, because with only a single value of $N$, it is just a fixed constant; it's not a function of anything. Complexity classes like EXPTIME are defined in terms of these asymptotics, so they aren't applicable if you have just a single function you want to compute, for a single fixed value of $N$.

So, if you want to apply the machine of complexity theory, you need to consider a family of boolean functions, one for each $N$, and a single Turing machine that computes all of them. *Then* you can characterize the running time of that Turing machine as a function of $N$ (the length of the input). At that point, there is no opportunity to "hide exponentialness" in the definition of the Turing machine, because you need to pick a single fixed Turing machine that computes all of them, and your idea for "smuggling exponentialness" can't be done if you have a fixed Turing machine. Whatever you do, you only get a constant-factor speedup.

---

I have seen some formalizations that characterize the complexity not by the running time of the machine, but by the running time plus the length of the machine specification. For instance, in the RAM model, you can use the running time of the algorithm plus the length of the code of the program. Then, you can measure how this behaves as a function of $N$. You can even characterize it for a single $N$, but then you're not dealing with asymptotics or complexity theory or complexity classes like EXPTIME; you're just saying that the least-complexity program to implement this one function has time+size equal to such-and-such. For instance, this approach is sometimes used in theoretical cryptography (called "concrete security"), where we care about a single value of $N$, rather than the asymptotic behavior as $N \to \infty$. But again, then you can't talk about complexity classes like P or EXPTIME.
> 3 votes

---
Tags: complexity-theory, turing-machines, time-complexity
---


# Question
Title: Find the nearest sum to a given number of two elements in sorted matrix
Given a sorted $n\times n$ matrix $A$ of real values. That is $a\_{ki}\<a\_{kj}$ and $a\_{it}\<a\_{jt}$, when $i\<j$. Propose and algorithm, finding **two** elements of this matrix with the sum nearest to a given value $q$. The restriction of memory is $\mathcal{O}(n)$. It is not allowed to change a given matrix.

The naive approach is $\mathcal{O}(n^4)$ brute force algorithm.

Also I can propose $\mathcal{O}(n^3)$ algorithm. Which use the following idea. Let we have two sorted arrays $c\_1\leq c\_2\le \cdots \leq c\_{k}$ and $d\_1\leq d\_2\le \cdots \leq d\_s$ and we need to find a sum of the form $c\_i$ + $d\_j$ nearest to a given $q$. We can do this by $\mathcal{O}(k+s)$ algorithm by imaginary merging two arrays: $$ c\_1\leq c\_2\leq \cdots \le c\_{k}; \ \ q-d\_s\leq q-d\_{s-1}\leq \cdots\le q-d\_{1} $$ in one array. So to solve the problem we can iterate the set of row-pairs of our matrix and to use the above idea. Of course this algorithm will have a complexity $\mathcal{O}(n^3)$.

> **My question.** How can we do this more effectively?

# Answer
> -1 votes
Try something like binary search since it is sorted i.e. check a\[n/2,n\]+a \[n/2 +1,1\] if equal done -smaller check the lower half -greater check the upper half (Keep the last checked value to compare how close with the next one) Probably O ( log n2)

---
Tags: algorithms, optimization, arrays, matrices, nearest-neighbour
---


title: Data Structure - Array of Array

text:
# Question
Title: Data Structure - Array of Array
Suppose that we have a family $F=\\{a\_1,\dots,a\_s\\}$ of sorted arrays to merge. Our strategy is to choose two of them, say $a\_i$ and $a\_j$, remove them from $F$, merge them and put the resulting array back into $F$; we keep doing that until there is only one array in $F$. We will use a greedy strategy: at each step, we choose $a\_i$ of minimal length in $F$, and $a\_j$ of minimal length in $F-\\{a\_i\\}$.

What data structure would you use to store $F$?

Obviously, I assumed F $F$ be an array of array as each element of F is an array of integers.

However, I think it is asking about Abstract Data Structures that were taught at a class. We are taught about Priority Queue ADT, Stack ADT, Queue ADT, and heap so far.

Can F be one of them? If so, please explain why F can be such structure.

Thank you,

# Answer
> 1 votes
You would like to have the ability to extract the minimal array (in terms of length), then extract the next minimal, merge them, and insert them back to the data structure.

Since you want the best performance possible, you now would like to ask yourself how much each operation would cost?

If you use a stack you would have the option to $pop$, which is good if you assume your stack is given you with the arrays already sorted by length (will be $O(1)$). So, you will be able to $pop$ the first two arrays and then merge them. But now, what will you do with the merged array? You have no guarantee that the new array is indeed the shortest one. A simple queue won't do as well.

So, a better option would be to use a priority queue, implemented as a heap. You will have a heap where the values are the length of the arrays. To get the two shortest array you will use $extract-min$. You can use Fibonacci heaps which will give you $O(\log n)$ amortized for extraction. Next, after merging the arrays you can insert it back with $O(1)$ amortized time complexity.

\*Note that the complexity times I wrote here are disregarding the length of the arrays themselves. I treated them as simple elements for simplicity, since the question focuses on the use of the data structure.

---
Tags: algorithms, algorithm-analysis, data-structures
---


title: Union of two non-context-free languages

text:
# Question
Title: Union of two non-context-free languages
Let L1 = L2 union L3 find values such that L1 is context free and L2 and L3 are not.

So far I have: L1 = $a^nb^n$ L2 = $a^\*b^\*$ L3 = $a^+b^+$

Is this acceptable?? Since L2 covers everything including epsilon and L3 is the same but does not include epsilon?

I know L2 is regular so I guess that is also not a CFL. Another problem is that the a's and b's aren't linked in L2 and L3, so either one can always have more a's than b's and vice versa.

# Answer
**Hint**. For any language $L$, $$A^\* = L \cup (A^\* - L).$$ Now, choose an appropriate language $L$ to solve your problem.
> 3 votes

# Answer
Here is another construction: for every language $L$ over $\\{0,1\\}$, $$ (0L \cup 1\Sigma^\*) \cup (1L \cup 0\Sigma^\*) = \Sigma^+. $$
> 2 votes

---
Tags: algorithms, context-free
---


# Question
Title: How does in-order traversal in Binary search tree works (recursion)
I visit some question but their implementations are slightly different and my doubt is not like theirs. I have this code in Javascript.

The code is typical BST implementation with methods to support in-order traversal. The code that is the most relavant for this question is the the inOrderTraverse and inOrderTraverseNode. I cannot understand how this code work.

```
function BinarySearchTree() {

    var Node = function (key) {
        this.key = key;
        this.left = null;
        this.right = null;
    };

    var root = null;

    this.inOrderTraverse = function (callback) {

         inOrderTraverseNode(root, callback);
    }

    this.insert = function (key) {

        var newNode = new Node(key);

        if (root === null) {
            root = newNode;
        }
        else {
            insertNode(root, newNode);
        }

    }

    var insertNode = function (node, newNode) {

        if (newNode.key < node.key) {
            if (node.left === null) {
                node.left = newNode;
            } else {
                insertNode(node.left, newNode);
            }
        } else {
            if (node.right === null) {
                node.right = newNode;
            } else {
                insertNode(node.right, newNode);
            }
        }

    };

    var inOrderTraverseNode = function (node, callback) {

        if (node !== null) {
            inOrderTraverseNode(node.left, callback);
            callback(node.key);
            inOrderTraverseNode(node.right, callback);
        }
    }
}

```

The code that will use the BinarySearchTree "class".

```
function printNode(value) {
    document.writeln(value);
}

var tree = new BinarySearchTree();

tree.insert(11);
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(3);
tree.insert(9);
tree.insert(8);
tree.insert(10);
tree.insert(13);
tree.insert(12);
tree.insert(14);
tree.insert(20);
tree.insert(18);
tree.insert(25);
tree.insert(6);

tree.inOrderTraverse(printNode);

```

This will generate a BST like this:

taken from the book Learning Javascript Data Structure and Algorithms by Loiane Grone

I will explain how I think the in-order functionality works.

```
    var inOrderTraverseNode = function (node, callback) {

    if (node !== null) {     //checks if the node is null, 11 is not null so it continues
        inOrderTraverseNode(node.left, callback);     //keep executing this code until it finds a node with left null
        callback(node.key);      //3, the node with left null is printed
        inOrderTraverseNode(node.right, callback);     // checks if the 3 node has a right node, it doesn't have, so the execution finishes
    }

}

```

11 the root node is passed to the inOrderTraverseNode, it checks to see if the left is a null, if it is not it continues passing the left node until the left node is null. When a left null node is found Then it prints the value, callback(node.key) will execute as callback(3), so the 3 will be the first item printed on the screen. The execution then continues to inOrderTraverseNode(node.right, callback), 3 don't have a right child so execution will go on and that's that.

in my mind the output would be 3 only.

How do the in-order traversal get from 3 to the 5?

# Answer
> 2 votes
The important part is to consider the entire call stack.

When you're calling inOrderTraverseNode on the root, what happens first is it calls it on its left child, and so on.

So at the point that we call it on 3, the call stack above us looks like

```
inOrderTraverseNode(Node(11), callback)
 inOrderTraverseNode(Node(7), callback)
  inOrderTraverseNode(Node(5), callback)
   inOrderTraverseNode(Node(3), callback)

```

Eventually, the inOrderTraverseNode on the node with value 3 returns (after calling it on the null children).

At this point, the current point in code execution is at:

```
  if (node !== null) {     //checks if the node is null, 11 is not null so it continues
      inOrderTraverseNode(node.left, callback);     //keep executing this code until it finds a node with left null
    > callback(node.key);      //3, the node with left null is printed
      inOrderTraverseNode(node.right, callback);     // checks if the 3 node has a right node, it doesn't have, so the execution finishes
  }

```

But now the node in question is 5, we've returned back up a level, so the stack is:

```
inOrderTraverseNode(Node(11), callback)
 inOrderTraverseNode(Node(7), callback)
  inOrderTraverseNode(Node(5), callback)

```

So the callback is called on 5, and now we continue execution, recursively traversing the right subtree. After that, that code returns, and eventually we have the stack:

```
inOrderTraverseNode(Node(11), callback)
 inOrderTraverseNode(Node(7), callback)

```

And now we're finished with the left subtree, so we call the callback with 7.

And so on. So imagine the stack growing every time you call it on a subtree. Then you go back up, process that node, then head back down to the other subtree (growing the stack again), and processing that.

So what you're neglecting from your explanation is that after execution finishes, it goes back to the code that called it. So although it makes it down to 3, and processes fully there, that code was called from the call at 5, so it has to finish processing that call. Likewise for each further call up. This is the same process that brings you back to where you were after you call it.

# Answer
> 3 votes
Consider **indorder** as a command in military. Let the binary tree be the hierarchy among the soldiers.

The general shouts "inorder!" and that means, when a subordinate receives the order, he tells it to his "left" subordinates. If he has no subordinates on the left side, then he yells out his name, and only then he commands his right subordinate to execute the order.

> **Inorder!** command means "tell your first subordinate, do it yourself, and then tell your right subordinate. Afther you are finished, report to your superior."

The general is the root of the binary tree. He shouts out "inorder!"

That means his left subordinate gets the order, and shouts out "inorder!" himself. This process goes on until the order reaches to a soldier who has no left subordinate. Then, he **yells out his name** and gives the order to his right subordinate.

After all his right subordinates are done, he reports back to his immediate superior. The superior, like him, **yells out his name** and gives the order to his right subordinate.

When all the left side is done, the general (**root of the binary tree**) yells out his name and gives the order to his right side.

Now, consider this tree
(taken from https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/):

The general is 1. He shouts "inorder!"

2 recieves the order, and he shouts "inorder!"

4 receives the order. He has no left child, and thus shouts his name: **4**

He has also no right child, and thus reports to 2.

Left side of 2 is done, and this 2 shouts his name: **2**, and then gives the order to the right side.

This process goes on, until the root is notified a second time.

---
Tags: binary-trees, recursion
---


title: Subtlety of a bar in introduction rule

text:
# Question
Title: Subtlety of a bar in introduction rule
I am going through the following lecture notes by Frank Pfenning :

http://www.cs.cmu.edu/~fp/courses/15317-f17/lectures/02-natded.pdf

In page no 5 I cam across the introduction rule .

The rule reads that $A$ is contained in $B$ if $B$ is true under the assumption that $A$ is true .

But in the text a subtle point about the beginning bar of the proof is mentioned which are a below in the images :

Why would it be incorrect to say that "The truth of A leads to the truth of B " . Even if the truth of A has been introduced durng the process of proving the truth of B , it surely means that the truth of A leads to truth of B . As in the graph or pictorial representation there are no other statement which are in conjuction with "A" anywhere .

What is the subtlety here in emphasing a misconception or a misleading picture obtained from omiting the bar ?

P.S : I did go through the following paragraphs illustrating the proof of a statement . This paragraph emphasizes on some phenomenon called discharging of assumptions , which I feel would require a detail understanding and might come up in the next question that I would be posting so as to gain a better understanding of the content . But for the time being , I would try to understand the matter in this question with the hope that it might help while understanding the following topics .

# Answer
> 4 votes
Let's try an example. Let's say you're trying to prove the following:

Simple Theorem over the natural numbers: If $n$ is even, then $n+1$ is odd.

What he's trying to say is that you don't need an independent proof that $n$ is even. In the natural numbers, this isn't even true, since not all numbers are even. What he's trying to say is that when trying to prove an implication like the Simple Theorem above, you're allowed to introduce the assumption that $n$ is even, and from that assumption, together with whatever other axioms you're using, try to prove that $n+1$ is odd. If you succeed in this, you can now correctly conclude that the implication is true.

From his paper:

> The rule makes intuitive sense, a proof justifying A ⊃ B true assumes, hypothetically, the left-hand side of the implication so that A true, and uses this to show the right-hand side of the implication by proving B true. The proof of A⊃B true constructs a proof of B true from the additional assumption that A true.

The whole painful stuff with the bars and labels is a variation of the pain that comes with other deduction systems when you're trying to create a proof context to hold the introduction of an assumption. When these contexts get nested in a complicated proof, it requires machinery analogous to lexical variable scoping rules in programming languages. The assumptions have to come and go properly so they don't allow unsound deductions in other parts of the proof.

EDIT: per request of original poster.

OK, let's dig into this some more. I'm going to use some different notation. The notation

$$ \Gamma \vdash \sigma $$

means some set of axioms $\Gamma$ proves some formula $\sigma$, where the turnstile $\vdash$ means "proves". Now the inference rule we're looking at can be written like this. We can conclude

$$ \Gamma \vdash A \rightarrow B $$

if we can prove

$$ \\{\Gamma; A\\} \vdash B $$

where the semicolon means we've added formula $A$ to the set of axioms $\Gamma$. Note that this also creates what I've been calling a "proof context" where we're keeping track of assumptions we've been making. The Pfenning paper uses labels on bars to do the same thing.

Let's try it on a complicated example with nested proof contexts: prove the tautology

$$ A \rightarrow (B \rightarrow (C \rightarrow B)) $$

In our notation, proving this tautology looks like this:

$$ \\{\\} \vdash A \rightarrow (B \rightarrow (C \rightarrow B)) $$

That is, $\Gamma$ is empty since we're proving a tautology.

Here we go, using our rule of inference.

We can prove

$$ \\{\\} \vdash A \rightarrow (B \rightarrow (C \rightarrow B)) $$

if we can prove

$$ \\{A\\} \vdash B \rightarrow (C \rightarrow B) $$

Let's keep going.

We can in turn prove

$$ \\{A\\} \vdash B \rightarrow (C \rightarrow B) $$

if we can prove

$$ \\{A, B\\} \vdash (C \rightarrow B) $$

One more application of our rule:

We can prove

$$ \\{A, B\\} \vdash (C \rightarrow B) $$

if we can prove

$$ \\{A, B, C\\} \vdash B $$

But this follows easily: since B is already an axiom, it follows that we can prove it. But we only got this axiom from our inference rule that allowed us to add it safely.

# Answer
> 2 votes
To state the obvious, proving the implication $A \implies B$ (written $A \supset B$ in the notes you refer to) usually goes by assuming $A$ and proving $B$. Or in other words, proving $B$ under a new assumption $A$. Of course, this new assumption must only be used in the proof of $B$, which is the meaning of *discharging of assumption*. Thus, when you prove an implication you obtain an additional *axiom* (note the bar above the first derivation in your question), which can only be used in the branch of the proof that corresponds to the implication you want to prove.

---
Tags: logic
---


# Question
Title: Are the implications of the diagonalization language different from those of the halting problem?
**Revised:** In my previous question, I was confused about the implications of the diagonalization language. I concluded that it proves there are languages for which there are no recognizable turing machine. However, how is this implication different from the halting problem? Do they both just reinforce the limitations of computability?

**Old post:**

I'm in an introductory computer theory course. The professor went over the diagonalization argument and showed how the diagonalization language is not decidable.

The diagonalization language is the set of all pairs of turing machines and strings that they accept. In other words, $L = \\{ (s\_i, M\_i) | M\_i$ accepts $s\_i \\}$. We can encode each turing machine as a binary string and sort them in lexographic order. We can then fix an alphabet $\Sigma$ and then put $\Sigma^\*$ in lexographic order. By creating a table with these lists, where the values in the table are either 1 for accept or 0 for reject, we define a language to be any diagonal row in the table. Now we consider the complement of the diagonal language, which takes the complement of each value in the main diagonal. We quickly see that there is no turing machine that recognizes this language - as we switch every accept value to reject. Thus we have proved that exist languages for which there is no recognizing turing machine.

In class the professor actually said that this argument proves undecidability.

I don't see the more general implications of this argument. For the purposes of a intro course on CS theory, what are the implications of the existence of undecidable languages on our understanding of turing machines? Do they mention it to show that there are limits to what is computable (but isn't that the purpose of the halting problem)?

I'm truly trying to understand why this proof is used in every textbook, because I don't grasp how it connects to the other sections about turing machines.

# Answer
> 3 votes
I think that "limits of computation" is a good entry point. Usually, computer scientists learn how to solve problems in an logical and algorithmic way. The whole concept of undecidability is to show that there are problems which cannot be solved in this way, which may sounds surprising but also exciting, that there is an actual limit to what is possible with computers (even with infinite memory).

You actually do not need the diagonalization language to show that there are undecidable problems as this follows already from a combinatorical argument: You can enumerate the set of all Turing machines (sometimes called Gödelization). Thus, you have only countable many decidable languages. But the set $2^{\\{0, 1\\}^\ast}$, i.e. the set of all languages over $\\{0, 1\\}$, is uncountable, so there have to be undecidable languages.

The diagonalization language (I assume $D = \\{\langle M \rangle \mid M \text{ halts on } \langle M \rangle\\}$ is by all means very constructed but the proof that this language is undecidable is a good stating point because the proof via diagonalization is easy and the usual variations of the halting problems are not really far away. The next steps are probably Turing reductions from this language to some of these variations.

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


# Question
Title: Do the classes $P$ and $NP$ include problems faster then polynomial?
I have being reading up on complexity classes (in Rieffel & Polak, 2011; pg149). I am slightly confused about something. Does for example $P$ (DTime($n^k$)) include all problems that can be solved faster then polynomial in time (e.g. logarithmic) on a deterministic Turing? And likewise for e.g. PSpace (DSpace($n^k$)) and NP (NDTime($n^k$)) etc.?

# Answer
> 3 votes
We have $$\mathsf{P} = \bigcup\_{k \in \mathbb{N}} DTIME(n^k)$$ And e.g. $\log n \in \mathcal{O}(n)$. Thus, problems which are solvable in deterministic logarithmic time are in $\mathsf{P}$ since they are in $DTIME(n)$.

---
Tags: complexity-theory, terminology
---


# Question
Title: Is there way to calculate $\sum_{i<j<k\leq n} A_i \cdot A_j \cdot A_k$ faster than $O(n^3)$
Given array $A$ of size $n$, we want to calculate $\sum\_{i\<j\<k\leq n} A\_i \cdot A\_j \cdot A\_k$. Is there way to speed this up rather than the standard $O(n^3) $ calculation with 3 for loops. I haven't worked with sums so I don't know their properties, but I was thinking if there is some way to rewrite the formula to get faster calculations.

# Answer
> 9 votes
Let $A = \sum\_{i=1}^n A\_i$. We have $$ \begin{align\*} A^3 &= \sum\_{i=1}^n A\_i^3 + 3\sum\_{i=1}^n \sum\_{j \neq i} A\_i^2 A\_j + 6 \sum\_{i \< j \< k} A\_i A\_j A\_k \\ &= \sum\_{i=1}^n A\_i^3 + 3 \sum\_{i=1}^n A\_i^2 (A - A\_i) + 6 \sum\_{i \< j \< k} A\_i A\_j A\_k. \end{align\*} $$ This gives a linear time algorithm.

More generally, the theory of symmetric polynomials ensures that *every* symmetric polynomial can be computed in linear time, since it is a polynomial in the quantities $B\_d := \sum\_{i=1}^n A\_i^d$. For example, $$ \sum\_{i\<j\<k} A\_i A\_j A\_k = \frac{B\_1^3+2B\_3-3B\_1B\_2}{6}. $$

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


# Question
Title: Why can't a compiler create universal N-bit code (e.g. 32-bit, 64-bit, etc.)
It is my understanding from what I have read that you need to compile separate executables for 32 bit and 64 bit machines. So if I compile a C program for example I need to compile 2 different binaries for 32-bit and 64-bit machines.

However, it seems like intuitively a compiler should just be able to compile down to instructions that say "allocate N bits of space" and similar for other related instructions rather than "give me 32-bits of space" or "give me 64 bits of space"?

Why is this not the case (looking for some intuition at a high level)?

# Answer
> 7 votes
The instruction set for a 32-bit processor is different from the instruction set for a 64-bit processor. The 64-bit instructions can't be executed on a 32-bit processor. So, the program really does need to be compiled to something different: if you take a program compiled for a 64-bit processor, and try to run it on a 32-bit processor, the processor won't run it, because it doesn't understand the new 64-bit instructions.

# Answer
> 2 votes
> However, it seems like intuitively a compiler should just be able to compile down to instructions that say "allocate N bits of space" and similar for other related instructions rather than "give me 32-bits of space" or "give me 64 bits of space"?

Only if those instructions exist, and that's the decision of the instruction set designers rather than the compiler designers. Besides, the width of the instructions varies between instruction sets, as do things like the number of registers (very important for an optimising compiler).

In principle it would be possible to write some clever code which executes correctly in two different instruction sets and jumps to different places. You could then use this as a kind of "loader", placing it at the start of the executable to pack a 32-bit and a 64-bit version into the same file. However, then you run up against a problem which is not easily worked around, which may be considered the "real" answer, although perhaps not at the level of abstraction you want.

Executables have headers with metadata, which includes a flag for the instruction set. For example, the Windows Portable Executable format has a COFF header which requires you to choose one of a list of machine types:

```
0x0000 IMAGE_FILE_MACHINE_UNKNOWN
0x01d3 IMAGE_FILE_MACHINE_AM33
0x8664 IMAGE_FILE_MACHINE_AMD64
0x01c0 IMAGE_FILE_MACHINE_ARM
0xaa64 IMAGE_FILE_MACHINE_ARM64
0x01c4 IMAGE_FILE_MACHINE_ARMNT
0x0ebc IMAGE_FILE_MACHINE_EBC
0x014c IMAGE_FILE_MACHINE_I386
0x0200 IMAGE_FILE_MACHINE_IA64
0x9041 IMAGE_FILE_MACHINE_M32R
0x0266 IMAGE_FILE_MACHINE_MIPS16
0x0366 IMAGE_FILE_MACHINE_MIPSFPU
0x0466 IMAGE_FILE_MACHINE_MIPSFPU16
0x01f0 IMAGE_FILE_MACHINE_POWERPC
0x01f1 IMAGE_FILE_MACHINE_POWERPCFP
0x0166 IMAGE_FILE_MACHINE_R4000
0x5032 IMAGE_FILE_MACHINE_RISCV32
0x5064 IMAGE_FILE_MACHINE_RISCV64
0x5128 IMAGE_FILE_MACHINE_RISCV128
0x01a2 IMAGE_FILE_MACHINE_SH3
0x01a3 IMAGE_FILE_MACHINE_SH3DSP
0x01a6 IMAGE_FILE_MACHINE_SH4
0x01a8 IMAGE_FILE_MACHINE_SH5
0x01c2 IMAGE_FILE_MACHINE_THUMB
0x0169 IMAGE_FILE_MACHINE_WCEMIPSV2

```

I suppose you *might* be able to get away with using a clever loader if you choose machine type `0x0000`, but I wouldn't count on Windows agreeing to execute your program. And technically you really ought to implement support for *every* CPU on the list if you do that.

---
Tags: computer-architecture, compilers
---


# Question
Title: Understanding Bellman-Ford and Floyd-Warshall Algorithms as Dynamic Programming Algorithms
From my understanding, a problem amenable to a dynamic programming solution has these two properties:

1. **Overlapping Subproblems** — The same subcase (a subsection of the overall problem) keeps reappearing. Thus, memoization can be used to boost performance.
2. **Optimal Substructure** — The problem can be broken down into smaller components, which can then be solved independently and the results combined to produce the answer to the overall problem. This allows for subproblems and possibly overlapping subproblems.

I've read that Bellman-Ford and Floyd-Warshall are dynamic programming algorithms, but how do I think of them in terms of the two properties given above?

# Answer
**Floyd–Warshall algorithm**

You can prove inductively that on the $k$th iteration, the algorithm computes, for each pair of vertices $i,j$, the shortest path between $i$ and $j$ that passes through the vertices $1,\ldots,k$. How does it do that? When $k = 0$, you can read this off the adjacency matrix. For larger $k$, there are two possibilities:

1. The shortest path from $i$ to $j$ through $1,\ldots,k$ doesn't use $k$. In this case it equals the shortest path from $i$ to $j$ through $1,\ldots,k-1$.
2. The shortest path does use $k$. In this case you can break it up to two parts: a part from $i$ to $k$, and a part from $k$ to $j$. In both parts, the path only goes through $1,\ldots,k-1$.

You can therefore compute the shortest past from $i$ to $j$ through $1,\ldots,k$ using shortest paths that go through $1,\ldots,k-1$. Taking $k = n$, we obtain the unrestricted shortest paths.

**Bellman–Ford algorithm**

Let us consider first a parallel version of the Bellman–Ford algorithm which updates all weights simultaneously. In this case, you can show that on the $k$th iteration, the algorithm computes, for each pair of vertices $i,j$, the shortest path between $i$ and $j$ that is of length at most $k$. When $k = 1$, this is easy. For larger $k$, there are two possibilities:

1. The shortest path of length at most $k$ actually has length at most $k-1$.
2. The shortest path of length at most $k$ has length exactly $k$. Let $v$ be the penultimate vertex in one such path. Then the length of shortest path from $i$ to $j$ of length at most $k$ is the length of the shortest path from $i$ to $v$ of length at most $k-1$, plus the length of the edge from $v$ to $j$.

Once again, this can be computed by induction on $k$. Taking $k = n-1$, we obtain the unrestricted shortest paths (assuming no negative cycles).

The usual algorithm, which is sequential, is a bit different, but you can show that it is *at least as good* as the parallel algorithm.
> 2 votes

---
Tags: algorithms, graphs, dynamic-programming, shortest-path
---


title: Does Floyd–Warshall work on all graphs?

text:
# Question
Title: Does Floyd–Warshall work on all graphs?
Floyd–Warshall calculates minimum distance between any two vertices in the graph.

```
for(int k=0;k<n;k++){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
        }
    }
}

```

So, it basically calculates distance between every two nodes i,j having 1 intermediate node in the shortest path, then having 2 intermediate nodes in the shortest path and so on until there are N intermediate nodes in the shortest path.

So, basically this algorithm uses the previous computed distances to compute the new shortest distances.

But, for a graph like 0-\>2-\>3-\>1. It wouldn't be able to compute the shortest between 0 and 1 because in starting it doesn't know the shortest distances from 0 to 3 or 2 to 1 in the distance matrix.

In dynamic algorithms, we start from shorter problems and then use them to compute solution to larger problems. But, here we don't know which one are our shorter problems.

So, how are we able to use this algorithm here?

# Answer
> 2 votes
The way to answer this kind of question is to simulate the algorithm with pencil and paper to see what it actually does.

Initially, we have `dist[i][i] = 0` for all `i`, `dist[0][2] = dist[2][3] = dist[3][1] = 1` and every other entry is infinite.

When we consider `k = 0`, nothing changes, since `dist[i][k] = ∞` for all `i` except `i = 0`.

When we consider `k = 1`, nothing changes, since `dist[k][j] = ∞` for all `j` except `j = 1`.

When we consider `k = 2`, we have `dist[0][2] + dist[2][3] = 2 < dist[0,3] = ∞`, so we set `dist[0,3] = 2`; nothing else changes.

When we consider `k = 3`, we have `dist[0][3] + dist[3][1] = 3 < dist[0,1] = ∞`, so we set `dist[0,1] = 3`; nothing else changes.

So the algorithm has correctly computed the shortest path from `0` to `1`.

The point is that we're not really using dynamic programming based on the length of the intermediate path but on the highest-numbered vertex along that path. Suppose you want to compute the shortest path from `a` to `b`. That path must pass through some highest-numbered vertex – call it `c`. Because that's the highest-numbered vertex on the path, we know that all the vertices on the paths `a-c` and `c-b` have lower numbers. So, in particular, by the time we reach the `k = c` iteration of the outer loop, we've already calculated all shortest paths between all vertices that use only vertices `0...c-1` as intermediate vertices. And that's enough information to calculate the shortest paths `a-c` and `c-b` and, hence, the shortest path `a-b`.

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


# Question
Title: Is the outer loop in typical bubble sort algorithm precise?
I analized the bubble sort algorithm and I cannot see why they "implemented this way". I wrote down the results as the two loops performed their works and, with my small testing arrays, the outer loop condition to stop was always too much (the array was sorted when "i" was like 2, when the loop conditon to stop was 5.

```
this.bubbleSort = function(){
     var length = array.length;

      for (var i=0; i<length; i++){ //this loop seems too much

         for (var j=0; j<length-1; j++ ){

            if (array[j] > array[j+1]){

               swap(array, j, j+1);
               }
             }
           }
        };

```

Is there a possibility that the outer loop will have to reach its limit? I mean the "i - 1 \< length" will be necessary to sort. Is the array length on the outer loop really a precise choice or just a good choice, because it gives a clue of how many inner loop iterations will be needed with some leftover if necessary?

For me it means that the algorithm could be written, somehow, like this

```
var length = array.length;

  for (var i=0; i< 10; i++){ //I used 10 instead of the array length

     for (var j=0; j<length-1; j++ ){

        if (array[j] > array[j+1]){

           swap(array, j, j+1);
           }
         }
       }
    };

```

# Answer
Let's assume that the input has is a reversed array like a = 5 4 3 2 1. every iteration of the outer loop all the 5 - 1 - i smallest elements will be shifted one cell to the right(i is zero in the first iteration) and the 5 - i th element will be moved to the 5 - i th cell. as one can see it takes 4 iteration to sort this.

at every iteration of the outer loop, the n - i th element will be moved to the n - i th cell so it will take at most n - 1 iteration and the worst case (descending array) will always take that many iteration ( the last element will be sorted by itself).
> 1 votes

---
Tags: algorithms, sorting
---


title: Object qualification algorithm

text:
# Question
Title: Object qualification algorithm
I need to develop algorithm for one task.

I have 500 types of object, each type is represented by a group of qualifiers (about 20 for each type, the same qualifier can be used for different types), where qualifier is a simple predicate (but calculation of the predicate can take some time, as you have to check data in data base). When all qualifiers for particular type return true then object has such type.

For now I just came up with idea to use cache and go through all types trying to do qualification. For each type firstly I go through predicates without calculation and check that no of them failed before if some failed I skip the type, otherwise I go through qualifiers and do calculations (for each predicate I take data from cache if I did the same qualifier before).

I think may be there are some data structures for such task, or common approaches how to do that better.

---

A small **update** to the question. The classification data I have, has special structure, like not all attributes of the object mentioned for each class.

For example Type **European** transaction:

* Country one of DE, FR, ES
* Color : Blue
* Serial type: 2
* Currency : EUR

Type **UK** transaction:

* Country: UK
* Serial type: 1

It just example out of my head, each object has much more attributes. The main point here that some attributes can present for some objects but not for others. So if we create data set on the objects to build qualification tree, the value of such attributes could be marked as **ANY** value, that way it's impossible to do qualification, since we can get to the branch where we have two ways to go.

Thanks.

# Answer
Sure. Caching is a standard optimization that can be applied in many situations. I'm not sure there's much more to say there.

The other optimization that might be useful here is to choose the order in which you test the predicates. I would suggest using ID3 to construct a decision tree that identifies which predicates you test, and in what order. This may reduce the number of predicate computations you need to do, to determine the type of an object.
> 1 votes

---
Tags: algorithms
---


# Question
Title: What do Arora and Barak mean by $x|_S$ in their definition of certificate complexity?
I am having much trouble understanding the following definition (of certificate complexity - for decision trees) from Arora and Barak's book *Computational Complexity: A Modern Approach*. Perhaps there is a typo in it:

> Definition 12.3 (page 262). Let $f : \\{0,1\\}^n \to \\{0, 1\\}$, and $x \in \\{0,1\\}^n$. A 0-certificate for $x$ is a subset $S \subseteq \\{0,1\\}^n$, such that $f(x') = 0$ for every $x'$ such that $x'|\_S = x|\_S$ (where $x|\_S$ denotes the substring of $x$ in the coordinates in $S$$)\ldots$

So, given that $S$ is a subset of $\\{0,1\\}^n$, what on earth does $x|\_S$ mean? (Their parenthetical remark is not clear to me.)

> Is there in fact a typo in what $S$ is?

I've looked online at a few other authors' definitions of certificate complexity, and it seems to me that $S$ should actually be a subset of $\[n\] = \\{1,2,\ldots,n\\}$. Is this correct? If so, then $x|\_S$ would make sense.

Finally, I'll note that I have looked online for an errata list, but I could not find anything very comprehensive.

# Answer
> 3 votes
It is a typo. $S$ indeed should be a subset of $\[n\] = \\{1,2,\ldots,n\\}$. On page 263, in the second sentence of their proof of Theorem 12.5, they list a 0-certificate (or 1-certificate) as a subset of $\[n\]$.

Because $S \subseteq \[n\]$, it is easy to understand $x|\_S$ (as is stated in the question). This is just the usual notation for the restriction of a function on a subset of its domain. Note that an $x \in \\{0,1\\}^n$ can be thought of as a function from $\[n\]$ to $\\{0,1\\}$.

---
Tags: complexity-theory, decision-tree
---


title: Runtime analysis of while-loop analysis

text:
# Question
Title: Runtime analysis of while-loop analysis
```
s = n
while (s > 4)
  s = s / 2
else
  s = s - 1

```

Let $T(n) = \Theta(S(n))$ where $S(n)$ is number of while-loop runs.

$S(n)=1 + S(n/2)$ if $n$ is even

$S(n)=1 + S(n-1)$ if $n$ is odd

$S(n)=0$ if $n \leq 4$

By converting n to a binary number, and I think

if $n \< 2^k$, then $S(n) \leq k - 1$

I have come to this relationship, yet can't figure out how to approach to $\Theta $ bound.

Any help or guidance is appreciated.

# Answer
> 1 votes
It is a strange grammar that `while` is combined with `else` in your pseudocode. There is such grammar in Python but it is obviously not the case. I guess you mean

```
s = n
while (s > 4)
  if (s is even)
      s = s / 2
  else
      s = s - 1

```

Anyway, let's start with your recursion formula.

Consider $n\>4$. Note if $n$ is even, $S(n)=1+S(n/2)=1+S(\lfloor n/2\rfloor)$, and if $n$ is odd, $S(n)=1+S(n-1)=2+S((n-1)/2)=2+S(\lfloor n/2\rfloor)$. So anyway, for $n\>4$ we have

$$1+S(\lfloor n/2\rfloor)\le S(n)\le 2+S(\lfloor n/2\rfloor).\quad (1)$$

Suppose $2^{k-1}\le n \< 2^k$, you can prove

$$ k-2\le S(n)\le 2(k-2).$$

using mathematical induction (the formal proof is left to you as an exercise). So $S(n)=\Theta(k)=\Theta(\log\_2 n)$.

---

From (1) we can write $S(n)=S(\lfloor n/2\rfloor)+f(n)$ where $1\le f(n)\le 2$, i.e. $f(n)=O(1)$. Then Master Theorem applies.

---
Tags: algorithms, algorithm-analysis, asymptotics, runtime-analysis, loops
---


title: Sorting by Comparisons Proof

text:
# Question
Title: Sorting by Comparisons Proof
I came across this question while solving past papers and I'm not very sure as to how to construct my proof for the second and third question. I understand the concept that can be applied here would be that the lower bound for any sorting via comparisons based algorithm is always $n\log n$.

It would be impractical to find the factorial of 12 and try to see the number of levels in the decision tree. Is there an easy way I can go about doing the same?

# Answer
Computing $\lceil \log\_2 12!\rceil = \lceil \log 479{,}001{,}600 \rceil = 29$ is not very difficult, even by hand. The $\log\_2$ becomes easier if you recall that $2^{30} = (2^{10})^3 \approx (1{,}000)^3 = 1{,}000{,}000{,}000$.

Anyway, this gives a lower bound of $29$ for the number of comparisons you need to make. Hence, using the bound you brought up, Ben is clearly mistaken somewhere.

Is Tiffany right? It's not very easy to tell. While $29$ is provably a lower bound, it's actually a lower bound on the number of binary queries *of any type* that must be made to sort the 12 items. But Tiffany is restricted to only making *comparison* queries, so it's plausible that she might need significantly more queries to narrow things down to the exact right permutation.

As it turns out, $30$ queries is both necessary and sufficient to sort $12$ items, so Tiffany's implementation is also bugged. While mergesort witnesses that $30$ queries suffice \[Knuth '98\], the necessity of that many queries is far from obvious. At least initially, the matching lower bound was proved using a brute force search on a computer \[Wells '64\].

I'm not sure if a new, more simple proof has been discovered since, but in any case it's definitely not a-priori self-evident whether or not you should trust Tiffany.
> 2 votes

---
Tags: algorithms, sorting
---


title: Confluent directed acyclic graph

text:
# Question
Title: Confluent directed acyclic graph
> A directed acyclic graph $G$ is *confluent*, if any two vertices ${v\_1},{v\_2}$ in $G$ which have a common ancestor $u$ also have a common successor $w$. (I.e. if there are paths from some $u$ to both ${v\_1}$ and ${v\_2}$, then there are also paths from ${v\_1}$ and ${v\_2}$ to some $w$. Vertices $u,{v\_1},{v\_2}$ and $w$ do not need to be distinct, thus e.g. a single "line" of vertices is trivially confluent) Design a **linear-time algorithm** that determines whether a given DAG $G$ is confluent.

Is the "line" with $3$ vertices $u \to v \to w$ s.t. ${v\_1} = {v\_2}$ trivially confluent? Or is it nesseccary to have ${v\_1} \ne {v\_2}$ and thus the smallest number of vertices such line may have is $4$ $u \to {v\_1} \to {v\_2} \to w$?

Edit: Solved the problem.

# Answer
> 0 votes
Yes, the "line" $u \to v \to w$ is trivially confluent, and so are the empty graph, the graph with a single node, and the "line" $u \to w$. In the case of a graph with a single node $v$ there is only one case to consider, with $v\_1 = v\_2 = v$. The common ancestor is then $v$ itself, and the common successor is also $v$.

---
Tags: graphs
---


title: Binary Tree Node Insertion

text:
# Question
Title: Binary Tree Node Insertion
I was trying to implement a Binary Search Tree using this article as a reference: Binary Search Tree in JavaScript.

I was thinking especially about the node insertion method. Here's my implementation:

```
class BinaryTree {
// ... initialization
add(val) {
    if(this.root === null) {
        this.root = new Node(val);
        return ;
    }
    this.addNode(val, this.root);
}
addNode(val, node) {
    if(!!!this.comparator) throw new Error('this.comparator cannot be undefined.');
    let comp = this.comparator(val, node.val);
    if(comp === -1) {
        if(node.left === null) {
            node.left = new Node(val);
            return ;
        }
        this.addNode(val, node.left);
    }
    else if(comp === 1) {
        if(node.right === null) {
            node.right = new Node(val);
            return ;
        }
        this.addNode(val, node.right);
    }
}
// ... other methods
}

```

where `this.comparator = (v1, v2) => { return (v1 <= v2) ? -1 : 1; };`

My questions are:

* Is there a way to modify this `add` method such that it can balance the tree after every addition?
* If so, by factor would the time complexity of `add` be growing?

# Answer
> 1 votes
Search & read on AVL trees that follow the BST rules while keeping a worstcase balance difference of 1 between subtrees. read knuth sorting & searching

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


# Question
Title: Algorithm to find best combination of datasources (Quality and price)
I have some sources of data, and each one of this sources have a cost per request. I know wich data attributes each one of these sources have, and what are the best sources for each attribute.

Given a list of attributes, I have to decide the best group of datasources to consume, thinking about Quality of the data first, and secondly about costs.

Its common to make requests to multiple datasources, getting just some attributes from each one, but i will give a simple example below:

Say I have something like this:

DATASOURCE A costs $0.50 returns NAME (good), BIRTHDAY (good), ADDRESS (good)

DATASOURCE B costs $1 and returns NAME (good), MONTHLY INCOME (good), ADDRESS (medium)

DATASOURCE C costs $0.70 returns MONTHLY INCOME (good), NAME (medium)

If i want NAME, it would be better to consume DATASOURCE A (quality and cost of NAME).

If i want MONTHLY INCOME, it would be better to consume DATASOURCE C. (quality and cost of MONTHLY INCOME)

If i want NAME and MONTHLY INCOME, now it would be better to consume DATASOURCE B (because NAME and MONTHLY INCOME are GOOD).

But if i want NAME, MONTHLY INCOME and ADDRESS, I need to consume DATASOURCE A (for NAME and ADDRESS) but will consume DATASOURCE B too for MONTHLY INCOME.

Im trying to make some algorithm that makes sense to do it, but its getting very messy hehe. I would love any help with the logic. Maybe in javascript, java, c# or anything else I could read and have good idea about the best way to solve this.

Any help will be apreciated.

edit

some things to note:

I will have only 3 types of Quality here, and always prefer the best quality, so If i know any datasource has quality GOOD for the attribute, i can filter all other datasources with quality lower than Good for this attribute.

I know that in my case, we will have something like 5 or 10 datasources at all, and only 2 or 3 will have the same attribute.

# Answer
What you're asking reminds me of some of the work I did a Linear Programming course and made me think of the Hungarian Algorithm. I hope this helps!
> 0 votes

---
Tags: algorithms
---