# Question
Title: Is it possible to build a computer whose "ALU" is a single NAND gate?
I am not asking about if it is possible to build a computer using only NAND gates, since that question has been asked infinite times. I wonder if it is possible to replace the “ALU” in the cpu of a computer, with just a single NAND gate. And, then implement the rest of the ALU with software.

CPU seems to basically get an instruction, feed something into ALU, get something out. Then get another instructions, feed into ALU, get something out. It seems like it should work identically if the ALU is a single NAND gate. And, just like n-bit computation can be implemented on less than n-bit architecture, seems like a single NAND gate "ALU" might be able to scale up to compute on n-bit words.

An ADD instruction, would implement an adder with software that executes on the “ALU”. For a half adder, A and B are fed into a NAND, this result could be used both in the sum and the carry bit. For the carry, the result is inverted by passing the result into both inputs of the logical execution unit. For the sum, the result is passed through the rest of the XOR gate software implementation on this logic unit.

I am still learning the basics of computer architecture. This question probably has an easy answer, but I do not have enough oversight of how things can be pulled from registers and fed into “ALU” to be able to answer if the “ALU” can be reduced like this.

Also, if it is possible, has it been done? Any documentation of such a CPU architecture being used or experimented with historically?

# Answer
I have to study the following computer architecture more, but it looks exactly what I asked about, and that proves the question was actually very good, so, I will share this here right away. The single NOR gate computer, https://hackaday.com/2020/11/23/a-cpu-less-computer-with-a-single-nor-gate-alu/. Also, this article seems to describe a similar thing, with a single NAND gate instead, http://www.inf.fu-berlin.de/inst/ag-ki/rojas\_home/documents/tutorials/SmallestCPU.pdf. It also mentions a 1945 computer that was very similar.

Why is this relevant? It is "philosophically" relevant to anyone wanting to understand what a computer is. I also, without having the expertise to know if there is any truth in that, like the idea of moving more of the computer into software. I recall reading that IBM said in 1960s that "software was overrated, it is all in the hardware", and then that statement was proven wrong, and most computer architecture seems to me that it is based on what existed at that time. But, I lack expertise to know that, so will claim the "philosophy" angle for now.
> 1 votes

# Answer
CPU usually can have a lot of logical gates to perform operations, since any gate can be expressed as NAND-gate, so it's possible to build computers with NAND-gates only, although this will not be efficient.

Now if I understand your question, instead of building a CPU with NAND-gate**s** you want to build it with 1 single NAND-gate. In other words, you are looking to reduce the number of gates (and therefore transistors) in your CPU, such CPU will probably be unusable, slow, no parallelism and it won't be able handle large operations. It may also require a huge amount of ram to compensate for the speed loss and to store intermediate results.
> 0 votes

---
Tags: computer-architecture, cpu
---


# Question
Title: Are AVL&RB Trees without additional storage for balance information in each node feasible?
One advantage claimed for scapegoat trees over other balanced trees like AVL or red-black(RB trees - just mentioning AVL henceforth) is not needing to store additional balance information.
But can't an AVL tree node do without additional storage for balance information?
(I'm not considering possibilities to hide it in "the payload" (*item*, considered "immutable for the tree handling").)

# Answer
One frequent characterisation of the storage for the balance information for an *AVL tree node* (henceforth *node*) is *2 bits*:
either for *balance factors* (differences between children's heights) of -1, 0, or 1,
or *leftIsTaller*&*rightIsTaller*.

More than half the nodes being leaves, it is possible to reduce this to one bit:
The balance of nodes with less than two children is obvious; for two children, *push down the bits left&right*.

Customarily, AVL trees are described (&implemented) with targeted access to each child as *left* or *right* child.
Keeping that, it should be possible to encode one bit in either having the children in their proper place as implied by *key order*, or exchanged.
There would seem to be a problem with leaves, but those can be detected to be leaves in constant time, the parent leaning their way if there is no sibling; the sibling's way if that is not a leaf.

(The implementation for "0-overhead (balanced) trees" haunting me being
two *maps* from *parent item* to *left child item* and right.)
> 0 votes

---
Tags: binary-trees, balanced-search-trees, avl-trees, red-black-trees
---


# Question
Title: Bisimulation and the Knaster–Tarski theorem: What does the least fixed point mean?
Given a suitable lattice and a monotonic function $F$, we can compute the bisimilarity of a labeled transition system (its greatest bisimulation) by computing the greatest fixed point of $F$ using Knaster–Tarski. I was wondering if the least fixed point of $F$ has any meaning to us or if it's worth computing. It is clearly *not* the smallest bisimulation, so what does it mean?

# Answer
Let me start by pointing out that, as Janmar mentioned, an empty set is always the least fixed point of $F$. But since bisimulation is often required to be non-empty (to avoid the silly situation that every two transition systems are bisimilar), it makes sense to re-define $F$ as a mapping

$$F^\*:(\mathcal{P}(S\times S) \backslash \\{\varnothing\\}) \to (\mathcal{P}(S\times S) \backslash \\{\varnothing\\})$$

Now, the simple reason that people compute greatest fixed point instead of least fixed point is that the least fixed point doesn't always exists. To see this, consider (for instance) the following transition systems:

1. $(\\{p\_0,p\_1,p\_2,p\_3\\},\\{\alpha\\},\\{(p\_0,\alpha,p\_1),(p\_2,\alpha,p\_3)\\})$
2. $(\\{q\_0,q\_1,q\_2,q\_3\\},\\{\alpha\\},\\{(q\_0,\alpha,q\_1),(q\_2,\alpha,q\_3)\\})$

Viewing these transition systems as disjoint unions of two smaller transition systems, there is a bisimulation $R\_1 = \\{(p\_0,q\_0),(p\_1,q\_1)\\}$ between the transition systems $(\\{p\_0,p\_1\\},\\{\alpha\\},\\{(p\_0,\alpha,p\_1)\\})$ and $(\\{q\_0,q\_1\\},\\{\alpha\\},\\{(q\_0,\alpha,q\_1)\\})$, and there is also a bisimulation $R\_2 = \\{(p\_2,q\_2),(p\_3,q\_3)\\}$ between $(\\{p\_2,p\_3\\},\\{\alpha\\},\\{(p\_2,\alpha,p\_3)\\})$ and $(\\{q\_2,q\_3\\},\\{\alpha\\},\\{(q\_2,\alpha,q\_3)\\})$. Both of these are fixed points of $F^\*$, and furthermore $R\_1 \cap R\_2 = \varnothing$. Thus $F^\*$ does not have, in this case, a least fixed point.

More generally (and loosely) speaking, the various fixed points of $F^\*$ can be interpretated as bisimulations between local parts of the relevant transition systems.
> 2 votes

---
Tags: lattices, fixed-point
---


title: Quasilinear time algorithm for 3-SAT

text:
# Question
Title: Quasilinear time algorithm for 3-SAT
Is it consistent with the current knowledge that there is an algorithm solving a 3-SAT instance in $n$ clauses in quasilinear time in $n$?

# Answer
> 2 votes
The phrase "*consistent* with the current knowledge" is the key here.

For a proposition to be *in*consistent with our current knowledge, there would have to be a contradiction between that proposition and something else that we already know. In other words, we would have to already know a conclusive *disproof* of it.

There are many things "consistent" with our current knowledge that we might still think are probably false. It's consistent with our current knowledge that I will live to be 500. Maybe highly unlikely, given that no human ever has, but who knows what medical advances could be discovered between now and then. I haven't died *yet*, so at the moment we don't have a conclusive disproof of that proposition, and cannot completely rule it out.

So, in choosing your answer to this question, consider carefully:

* Do we have a proof that *no* quasilinear time algorithm for 3-SAT *could ever* exist?
* Or, do we just lack such an algorithm *so far*? Even if we consider that it "almost certainly" doesn't exist, could we still be *tremendously* surprised by a future discovery?

---
Tags: complexity-theory, time-complexity, np-complete, satisfiability, 3-sat
---


# Question
Title: A computable language with a non-computable language that is prefix-free
We say that a language $L$ is prefix-free if for every word $s\in L$ there does not exist a nonempty string $w\in\Sigma^\*$ such that $sw\in L$ (i.e. no word in the language is a prefix of some other word in the language). For any given language there is a smallest prefix-free sub-language constructed by finding any two words $s,t\in L$ such that $s$ is a prefix of $t$, and removing $t$ from $L$.

Question: Is there a computable language such that its smallest prefix-free sub-language is not computable?

---

My attempt: I started trying to think of computable languages where "deciding" whether, for any string that is accepted, there exists a longer string which is also accepted, takes infinite time to check. None of the simple examples that come to mind work: If you take for instance any language which accepts finitely many strings, then it and its prefix-free sublanguage are computable. If you take the language of strings that ends in a 1, it and its sublanguage are computable because every string you could accept is a prefix to another accepting string so the sublanguage would be empty.

After trying to come up with simple examples I started thinking maybe I need to work in reverse, and think of a noncomputable language which is the prefix-free sublanguage of a computable language. The obvious language to pick here is the language of machine-input pairs such that the given machine halts on the given input. But I don't see how I could construe this as the prefix-free sublanguage of some other larger computable language. And I've thought a little about a few other noncomputable languages but that hasn't helped at all.

# Answer
No, since the change from a language to its smallest prefix-free sub-language is computable.

Suppose language $L$ is computable. That is, we can list all words in $L$ in nondecreasing length. Scanning the list, we will keep only the words that are not an expansion of any word that have been scanned. The list of words left, $P$, is the smallest prefix-free sub-language of $L$. Note that they are also in nondecreasing length. So $P$ is also computable.
> 5 votes

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


title: Optimal stacking of bricks

text:
# Question
Title: Optimal stacking of bricks
I need an algorithm to optimally stack a set of bricks in a 2D plane so that the resulting wall is as vertically short as possible. Bricks are defined as a pair of integers $(x\_1, x\_2)$ corresponding to the horizontal span of $\textit{width} = x\_2 - x\_1$ and are of equal height. Bricks cannot be translated left or right, they are only allowed to "fall" in place vertically from their original horizontal position. This is conceptually similar to a game of Tetris where instead of moving bricks, the player decides the order in which they fall.

For example, in the following figure, arrangement A is the worst possible while B and C are equally optimal. The numbers inside the bricks indicate a possible stacking order.

Bricks can number in the thousands so exhaustive evaluation of all possible permutations is not conceivable.

# Answer
Consider a graph whose vertices are the intervals, and whose edges correspond to intersecting intervals. This is an example of an interval graph.

In a solution, all intervals on a given row of the solution are non-intersecting. Therefore, if we color each interval according to the line it is on, we get a valid coloring of the graph. Conversely, given a valid coloring of the graph, we get a solution to your problem whose height is the number of different colors: simply drop all intervals colored 1, then all intervals colored 2, and so on.

In other words, your problem is reducible to interval graph coloring, which can be solved efficiently.
> 18 votes

---
Tags: algorithms
---


# Question
Title: Can any known sub-Turing-complete model of computation enumerate precisely the set of prime numbers?
I wish there were more, but the subject pretty much captures my whole question.

Is there a non-Turing-complete model (some constrained term rewriting system or automaton or what have you) which is known to be able to enumerate the prime numbers, all of the prime numbers (well, til you pull the plug on the algorithm), and only the prime numbers?

To be clear, one of the criteria I'm imposing is that this algorithm would be **non-halting**, and so long as it is left running, it will continue intermittently outputting prime numbers. This seems to necessitate an unbounded working memory, which gets you a lot of the way towards Turing-complete already.

Furthermore, this must be a model with a *finite* description, meaning no cute "consider the system mapping the natural numbers to the primes" answers, please. Even if technically correct, what I'm really after is whether it seems probable that prime enumeration would be a strong indicator of Turing completeness.

**Edit:** As for the objection that Turing machines can't yield values at will, I consider that semantics and not relevant to the spirit of the question. A Turing machine could certainly record all prime numbers found thus far on its tape, which we could presumably examine at will.

# Answer
There is an important class of primitive recursive functions. Citing Wikipedia,

> \[P\]rimitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined before entering the loop).

They are powerful enough to check primality: to check primality of $n$ it suffices to loop from $1$ to $n$, where $n$ is a known upper bound. Then you can define the function "$i$-th prime": it can be bounded by, say, $2^i$ due to Bertrand's postulate, then you can check all numbers from $1$ to $2^i$ and find the $i$-th.

On the other hand, they are less powerful than Turing machines, the separating example being the Ackermann function.

Wiki page on primitive recursive functions is quite comprehensive for the introduction.
> 24 votes

# Answer
The primes can be recognized in linear space by a Turing machine. Linear space-bounded Turing machines are not universal. So, I think I have to disappoint you.
> 8 votes

# Answer
*Belated citation add: see Fischer or Gordon for more on essentially this line of thought.*

---

As observed above, "locally" the problem of enumerating primes is very easy: the function sending $n$ to the $n$th prime, $n\mapsto \mathsf{thprime}(n)$, is primitive recursive (and of course that's massive overkill).

However, you specifically want a framework which allows programs to run forever. This complicates things a bit: in some sense we want the pseudocodish expression

> for i in Nat: print$(\mathsf{thprime}(i))$

to live inside some simple context despite the unbounded for-loop.

There is in fact something we can do here, which may be highly unnatural from a CS perspective but is quite natural from a *logic* perspective: require our programs to **come with proofs of niceness** (in the appropriate sense, over some fixed appropriate theory). For example, let a **ZFC-tame program** be a *pair* $(p,\pi)$, where:

* $p$ is a program in the usual sense, and
* $\pi$ is a formal $\mathsf{ZFC}$-proof that $p$ prints infinitely many things (so there's no "running forever without doing anything").

Of course this is still a bit vague but the point should be clear.

It turns out that this will always fall well short of Turing completeness:

> There is no ZFC-tame program $(p,\pi)$ which prints the sequence $(k\_i)\_{i\in\omega}$, where $k\_i$ is the $i$th output of the $i$th ZFC-tame program in some appropriate enumeration.

*(Compare with the "theory-free" result that the set $\mathsf{Tot}$ of indices of total computable functions is not computably enumerable.)*

This *despite* the fact that we can very simply enumerate the ZFC-tame programs! This old MSE answer of mine discusses essentially this point.
> 7 votes

# Answer
Yes. Friant \[1\] proved that the language $\\{ a^p \mid p \text{ is prime}\\}$ is a context-sensitive language, which is far stronger than recursively enumerable. My grandfather Benny Brodda \[2\] then gave an improved grammar for this purpose in 1968, which:

> contains a smaller number of rules; the rules are not so context-dependent; and finally, there are no \`dead-ends' in the grammar, i.e., irrespective of the order in which the rules are applied, the grammar either ends up in generating a prime number or stops.

This seems to be precisely what you want. Note that the language $\\{ a^p \mid p \text{ is prime}\\}$ is well-known not to be context-free.

${}$

**References**

1. *Friant, J.*, Grammaires generatives pour l’ensemble des nombres premiers, Rev. Roum. Math. Pures Appl. 14, 473-488 (1969). ZBL0187.27901.
2. *Brodda, Benny*, **A variant of the Friant grammar**, Bulletin mathématique de la Société des Sciences Mathématiques de la République Socialiste de Roumanie Nouvelle Série, Vol. 12 (60), No. 4 (1968), pp. 19-23.
> 6 votes

# Answer
I admit that this is a contrived example, but perhaps it is useful for the thought experiment.

Consider a machine that has two registers, A and B, each of which can store an integer of arbitrary size. This means that they must be implemented with infinite storage, but direct access to that storage is not available to the machine.

It also has only the instructions needed to implement the following program:

```
0: Store A = 3, B = 1                      (A is prime to test, B is divisor)
1: Increment B
2: Conditional branch to 5 if A % B == 0   (not a prime)
3: Conditional branch to 1 if B != A       (loop through all B)
4: Output A                                (found a prime!)
5: Increment A
6: Set B = 1
7: Branch to 1

```

Now the question becomes whether this machine is Turing complete or not.

As pointed out by Nathaniel, this is close to a two-counter machine, which is known to be Turing complete. The "successor machine" instruction set of CLR, INC, JE is close to the instruction set above. However, there is an important limitation we can apply: the `A` register never needs to decrease in our machine.

That stops the conversion of two counters into four counters. There is still a question whether the addition of a `JDIV` instruction could allow Turing completeness by other means.
> 2 votes

# Answer
Here is one that I think works, and is arguably not all that unnatural.

We will start with a language along the lines of Hofstadter's BlooP. This is a simple imperative language in which the only looping construct is `for` loops, which require the number of iterations to be specified when the loop starts executing. There is no way to jump out of a loop conditionally. Let us say that this language has a `print` type statement, so that it can return results before it finishes executing.

Such a language can be simpler than the original BlooP. All you need is basic arithmetic operations (just incrementing and decrementing registers will do), some basic `if` type of conditional statement, and `for` loops and `print` statements as described above. If such a language is set up correctly then it is not Turing complete and can only compute primitive recursive functions. I will leave the details to the reader.

Now, you want to be able to run indefinitely, printing out results as the program runs. So let us augment this language with another looping construct, `infinite_loop`. This is like `while (True)`. It enters an infinite loop and never returns, no matter what - the language should provide no way to break out of such a loop.

This is in a sense just an extension of the `for` loops the language already has - it's still a loop where the number of iterations has to be known in advance, it's just that now we allow an infinite number of iterations as well.

Now you can write a simple program along the lines of

```
n=0
infinite_loop:
   print(nth_prime(n))
   n += 1

```

where `nth_prime` is a (primitive recursive) subroutine that returns the `n`th prime number. This program satisfies your requirement of printing primes indefinitely.

However, the language provides no way of breaking out of an infinite loop conditionally. This means that *all* it can really do is (optionally) enter an infinite loop and then compute a primitive recursive function repeatedly, without ever returning. (You can nest infinite loops, but that doesn't change anything, since you'll never get to the second iteration of the outer one. You can store state in between invocations of your primitive recursive functions, but that doesn't change anything either, since calling a primitive recursive function `n` times with stored state still results in a primitive recursive function.)

So this language isn't Turing complete, but it can output prime numbers indefinitely, and it arguably isn't completely unnatural as a model of computation.
> 2 votes

# Answer
At a high level, that seems straightforward: have an infinite tape, with each cell representing a nonnegative integer. The state of all cells is initially empty, save cell 1 which is filled. Cells can be empty, filled, or chosen. Have an infinite pile of bots (tape heads?) on cell 1. Each bot contains two values, TEMPER and PATIENCE, both initialized to 1.

Every "tick", a bot departs to the right, moving one cell per tick (all the other bots move one to the right too.) Initially it is in mode Child, in which it increments TEMPER every tick. If it advances to an empty cell, it sets the cell to chosen and transitions itself to mode Adult.

In mode Adult, it decrements PATIENCE. If it runs out of PATIENCE, it has a fit on the spot, filling in the cell if it was empty. But then it calms down, takes a deep breath, and copies TEMPER to PATIENCE.

The set of chosen cells represents the prime numbers.

(The less fun version: there's an infinite pile of Adult bots before the beginning of the tape, each with TEMPER initialized to each consecutive integer starting at 2. Proceed as above, but start them all simultaneously rather than letting one go every tick.)

Perhaps this is cheating, but I don't see why an infinite supply of bots / tape heads is any different from an infinite tape. And the per-bot logic is dead simple; there's no way I can see to get a universal Turing machine out of it. Then again, I'm not sure what the dividing line is between "UTM" and "nonprogrammable TM with a single program"? I guess I could provide a set of operations, and the only movement operation is "unconditionally advance by 1 cell".
> 1 votes

# Answer
We can enumerate the prime numbers with just two nested loops, with the number of iterations of the inner loop known beforehand and the iterations of the outer loop limited to N if we want to find all primes \<= N.

That’s very restrictive. For a Turing-complete programming language the number of iterations should have no prior limit.
> 0 votes

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


# Question
Title: Prove that the class of regular languages is closed under three operation
We define an operation three on strings as three(c1c2c3c4c5c6...) = c3c6... then the above-described definition is extended to languages. Prove that the class of regular languages is closed under this operation.

# Answer
> 1 votes
Let $Q$ be a $DFA$ recognizing $L$. To show that $\mathrm{three}(L)$ is regular, you only need to construct a $NFA$ deciding $\mathrm{three}(L)$ (this suffices, since any $NFA$ can be transformed to an equivalent $DFA$). Now, the key idea is that if the $NFA$ is reading, say, the first character $c\_3$, then it can *guess* what two characters $c\_1,c\_2$ occurred before it.

More formally, suppose that $Q = (\Sigma,S,s\_0,\delta,F)$. Given a string $\overline{x} \in \Sigma^\*$ and states $s,s' \in S$ we will use $s,\overline{x} \to s'$ to denote the fact that $Q$, starting from state $s$ while reading the first character of $\overline{x}$, ends up in state $s'$ after reading the entire string $\overline{x}$. Consider now the following non-deterministic finite automata $Q' = (\Sigma,S\cup \\{s\_0'\\},s\_0',\delta',F)$, where $s\_0' \notin S$ and the transition function $\delta$ is defined as follows:

* For every $s\in S$ and $z\in \Sigma$ we define $$\delta(s,z) := \\{s' \in S \mid \exists x,y \in \Sigma : s,xyz \to s'\\}$$
* For every $z\in \Sigma$ we define $$\delta(s\_0',z) := \\{s'\in S \mid \exists x,y \in \Sigma:s\_0,xyz \to s'\\}$$

It is straightforward to verify that $L(Q') = \mathrm{three}(L)$.

# Answer
> 0 votes
You might use closure properties of the regular languages: (inverse) homomorphisms and intersection (by regular languages).

Assuming the language is over the alphabet $\Sigma$, make two copies $\Sigma\_i = \\{ \sigma\_i\mid \sigma\in\Sigma \\}$ of that alphabet, $i=0,1$.

The homomorfism $h$ maps elements from $\Sigma\_0\cup\Sigma\_1$ onto their original $h:\sigma\_i\mapsto\sigma$. The inverse morphism $h^{-1}: \Sigma^\* \to (\Sigma\_0\cup\Sigma\_1)^\*$ nondeterministically chooses a $0$ or $1$ copy for each symbol.

Now let $g$ be the homomorfism on $\Sigma\_0\cup\Sigma\_1$ that deletes symbols from $\Sigma\_0$ and maps symbols from $\Sigma\_1$ onto their original.

Now the following composition keeps every third symbol, while deleting the other symbols $w\mapsto g(\\;h^{-1}(w) \cap (\Sigma\_0\Sigma\_0\Sigma\_1)^\*(\Sigma\_0^0\cup\Sigma\_0^1\cup\Sigma\_0^2)\\;)$.

This method has the advantage that it also works for context-free languages.

---
Tags: formal-languages, regular-languages, finite-automata, closure-properties
---


# Question
Title: Computational Complexity of an 'equivalent' 3SAT instance problem
Given a random $3SAT$ instance $(S\_0)$ with $C\_0$ clauses, $I\_0$ variables.

**Objective:** For any given value $C\_1$ ($C\_1\<C\_0$), create an 'equivalent' $3SAT$ instance $(S\_1)$ with $I\_0$ variables, $C\_1$ clauses such that:
For any set of values for variables $I\_0$, $S\_0$ is satisfiable iff $S\_1$ is satisfiable.

What is the computational complexity of this problem? It doesn't seem to be $NPComplete$ since there is no obvious way to verify the equivalence of two instances $S\_0$ and $S\_1$. Or I am missing something? Any refernces please?

# Answer
Suppose that your problem can be solved in polynomial time. Then you can obtain an algorithm that solves 3SAT as follows.

Given an instance $\phi$ of 3SAT with $n \ge 3$ variables and $m \ge 9$ clauses, invoke a polynomial-time algorithm for your problem with $C\_1=8$.

If your algorithm answers with a formula $\phi'$, then you can test at most $2^{24}$ instantiations of the (at most) $24$ variables involved in the $8$ clauses of $\phi'$ to decide whether $\phi$ is satisfiable.

If your algorithm determines that no such formula $\phi'$ exists, then $\phi$ is necessarily satisfiable since you can always build a non-satisfiable 3SAT formula if you are allowed to use at least $3$ variables and $8$ clauses.
> 1 votes

---
Tags: complexity-theory, time-complexity
---


# Question
Title: Write n in terms of multiplication of numbers from A=[1,...,n] such that the total cost of chosen number is maximum
We want to write n in terms of multiplication of numbers from A = \[1,...,n\] such that the total cost is maximum. The cost of choosing the ith number is `cost[i]`. Note that `cost[1] = 0` and we can choose 1 number **multiple times**.

For example :

```
n = 12
A = [1,2,3,4,5,6,7,8,9,10,11,12]
cost = [0,1,2,0,0,0,0,0,0,0,0,20]
12 = 1*2*2*3(Cost = 0+1+1+2 = 4)
.
.
.
12 = 1*12(Cost = 0 + 20)
So the maximum of total cost is 20.

```

My attempt:

I tried to form a table from factors of n.

# Answer
For $i = 2, \dots, n$ define $C\[i\]$ as the maximum cost that can be attained if the product of the selected factors must be $i$ and $c\_i$ as the cost of selecting $i$.

Given $i$, let $P\_i$ be the multiset of prime factors of $i$ (with multiplicity) and notice that $|P\_i|=O(\log n)$. You have:

$$ C\[i\] = \max \left\\{ c\_i, \max\_{\substack{S \subset P\_i \\ |S| \le |P\_i|/2}} \left( C\left\[\prod\_{s \in S} s\right\] + C\left\[\prod\_{s \in P \setminus S} s\right\] \right) \right\\}. $$

This immediately gives you a polynomial-time dynamic programming algorithm.
> 0 votes

---
Tags: dynamic-programming
---


title: About Steiner tree problem in graphs

text:
# Question
Title: About Steiner tree problem in graphs
In the paper (p. 3) and the slides presents the formulation of the Steiner problem on graphs via so called *Steiner cuts*. But according to the definition, the number of *Steiner cuts* and so the number of constraints grows exponentially with the number of vertices in the graph.

**First question**: How to solve the problem in this cut-formulation? After all, we have too many constraints? For example, to solve the problem in the formulation through the multi-commodity flow described in the first article, we have only 'number of terminals' * 'number of vertices' constraints, and this can be solved.

**Second question**: Is there any practical benefit to solve the LP-relaxed problem, and then improve it with metaheuristics? Or is it the same to build a first Steiner tree aproximation with a greedy algorithm and then improve it?

# Answer
> 3 votes
The LP-relaxation can be solved efficiently (in polynomial time) by using cutting planes, see, e.g., "Solving Steiner tree problems in graphs to optimality" by Koch and Martin for the separation algorithm. This approach is also highly relevant in practice. Often, the LP-relaxation provides already an optimal solution, and if not, branch-and-bound can be used. This approach is used in the currently most successful solver for Steiner tree problems, see https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/8003

---
Tags: graphs, optimization, approximation, linear-programming
---


# Question
Title: Is language $a^mb^nc^n, m \not= n$ context free
I need to say Is language $a^mb^nc^n, m \not= n$ context free

I managed to find a grammar for $L1 = $ { $a^lb^mc^n | l=m$ or $m = n$ }, but I couldn't find the one I needed. Maybe it is impossible, but than why? If it may be helpful, that is the grammar for L1 wich i found: $A \rightarrow \epsilon |aAb, B \rightarrow \epsilon|bBc, S1 \rightarrow A|S1c, S2 \rightarrow B|aS2, S\rightarrow S1|S2$

I think that is not context free at all but I don't know how to proof.

# Answer
The reason that $L\_1$ is context-free is that one needs to keep track of only two numbers at the same time: either $l=m$ or $m=n$. The 'or' is handled using union, we patch two languages together. The difference of the two numbers $l-m$ or $m-n$ can be stored on the stack while reading the string.

Your language $L=\\{a^mb^nc^n \mid m\neq n\\}$ is not context-free. Intuitively because we need to handle three numbers, and there is no way to store two differences.

The formal proof of non-context-freeness can be done using the pumping lemma for context-free languages. As the specification involves the unequality of $m$ and $n$ a specific trick is needed, which involves a factorial. An example of this trick is shown here for nonregularity: Prove if $L=\\{0^m1^n∣m≠n\\}$ is regular or not. The approach is basically the same.
> 3 votes

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


# Question
Title: Finding the number of ways to reach a particular position in a grid from a starting position (given some cells which are blocked)
I came across this question in a job interview and I couldn't solve it.

In a n\*m matrix some cells are blocked.The robot can only move in direction of `(x-1,y+2)` or `(x+2,y-1)`. Is it possible to reach B from A? If yes how many minimum paths exists?

# Answer
> 0 votes
First, we can get an early rejection: if (A.y - B.y) + (B.x - A.x) modulo 3 is non-zero, B is not reachable from A, regardless of where the obstacles may be. (Try drawing the cells you can reach via sequences of those two moves. They form a set of parallel diagonal lines, leaving gaps of unreachable cells in between)

Similarly, if 2(A.y - B.y) \> (B.x - A.x), B is again not reachable from A. The only way we can decrease our Y is by increasing our X by twice as much, making anything below the line $\Delta y = -\frac 1 2 \Delta x$ unreachable.

That quickly rules out two thirds or more of the matrix for us.

If B is potentially reachable according to the test above, then a simple way to find one/all minimum paths to it (if any exist) is using breadth-first search.

Execute your graph search from A, taking only the moves (x-1, y+2) or (x+2, y-1) from each cell, and aborting any move that takes you to a blocked cell. Record for each cell you reach this way the number of hops it took to get there (ie. the number you recorded for the cell you reached it from, +1, with A having the value 0)

If the search terminates (has no new reachable cells to visit) without ever visiting B, you can conclude that B is not reachable from A.

If you reach B, stop. The value you write here is the length of a minimal path.

Now you can retrace your steps to count the paths. There are two possible cells that could have reached B. You can tell if they're part of a minimal path by checking if the hop count to reach that cell is exactly 1 less than the hop count to reach B. (Since breadth-first search iterates cells in non-decreasing order of hop count, you can be sure all possible stepping stones to reach B have been written to before B).

You can repeat this recursively to find the hops that lead to those penultimate cells, and the hops that lead to their predecessors, all the way back to A. Summing the routes you find at each stage gives you the total number of minimal paths - and you can even exhibit all of them if you like.

---
Tags: recursion, memoization
---


# Question
Title: Pre-computing min/max for interval queries?
I'm basically trying to figure out if the following problem has a common name and/or a standard solution in computer science.

Let assume we're given $N$ two-dimensional tuples $(x\_i, y\_i)$. This data is fixed/static and we want to pre-compute a data structure that allows to run interval queries returning the max or min w.r.t. $y$ in the specified $x$ interval. For instance, for a given interval $\[x\_{lower}, x\_{upper}\]$ the query should return the min or max $y\_i$ for all tuples satisfying $x\_{lower} \leq x\_i \leq x\_{upper}$.

The obvious solutions are:

* A naive linear scan, which would have a complexity of $O(N)$.
* A brute-force pre-computing solution would pre-compute the min/max for all possible $\[x\_{lower}, x\_{upper}\]$ pairs, which would have $O(N^2)$ in terms of runtime and memory complexity.

It feels like there should be a smart solution achieving sub-linear query complexity without the $O(N^2)$ complexity of a brute-force pre-computation?

# Answer
> 1 votes
One simple approach would be to store the tuples in a balanced binary search tree, using $x$ as the key. Augment that data structure to store in each node the maximum and minimum value of $y$, among all tuples that are stored in the subtree rooted at that node. You can construct such a data structure in $O(N \log N)$ time (preprocessing). Once you've done so, this data structure will allow you to answer interval queries in $O(\log N)$ time. If you also want to support interval queries on $y$, make a second tree, this one using $y$ as the key.

---
Tags: data-structures
---


# Question
Title: How many knights can be placed on an n-by-m chessboard?
I have a task, and its essence is as follows: how many knights on an $n \times m$ board can be set so that they do not attack each other. I am wondering if there is any mathematical solution to this problem, except for the algorithmic one.

# Answer
> 2 votes
For an 8\*8 chess board,

1. You need to observe that when 2 knights beat one another they lie on cells of different colors.
2. We can generate a solution by placing 32 knights in the 32 white cells so that no 2 knights beat each other.
3. To prove that this is the optimal solution, we can group our rows into pairs (1,3),(2,4),(5,7),(6,8). Let us consider the row pair (1,3). Consider the pairs of cells (R1C1,R3C2) and (R1C2,R3C1). We can see that we can place only 1 knight in the cell pair (R1C1,R3C2) and only 1 knight in the cell pair (R1C2,R3C1). Continuing this idea, we can show that we cannot place more than 32 knights in an 8X8 chessboard.
4. We already have an arrangement of 32 knights from point 2. Hence, the solution described in point 2 is optimal.

Expanding the above idea, below are the maximum no. of knights that can places such that no 2 beat each other on any N\*M chessboard.

1. If *both N and M are odd*, then the solution is **((N\*M)+1)/2**
2. If *either N or M is even*, then the solution is **(N\*M)/2**

# Answer
> 1 votes
A knight on a black field cannot take a knight on a white field, and vice versa. So we can just put all the knights on the same colour. Calculate the number of white and black squares and take the maximum. This gives a lower bound. For an n\*m rectangle where either n or m are even, the number is (n * m) / 2. If n and m are both odd, then we have (n * m + 1) / 2 fields of one colour and (n * m - 1) / 2 fields of the other colour, so we can place (n * m + 1) / 2 knights.

To prove that this is optimal you need to prove that any k knights on one color will threaten k or more squares of the other colour. That might not be true for more interesting shapes then rectangles.

For example take a board of n x n squares rotated by 45 degrees, n odd, which would have more squares of one color, and another which has more squares of the other color, then join them at a corner.

We can fit more knights on narrow rectangles by putting knights on different colour squares. You can put n knights on a 1 by n board. And for a 2 by n board, if n = 4k+2 then we can put k+1 blocks of 4 knights in a square separated by k empty 2x2 squares. That's (n * m + 4) / 2 knights. For n = 4k+1 or 4k+3 we can also fill (n * m + 2) / 2 squares. That's either two more or one more knights than the general formula leads us to expect.

Example: 16 knights instead of 14 or 15, 14 knights instead of 13:

```
XX__XX__XX__XX
XX__XX__XX__XX

XX__XX__XX__XX_
XX__XX__XX__XX_

XX__XX__XX__X
XX__XX__XX__X

```

# Answer
> -2 votes
```
if(r==1 || c==1)
        ans=r*c;
    else if(r==2 || c==2)
        ans= 4*int(max(r,c)/4)+2*min(2,max(r,c)%4);
    else if(r%2==1 && c%2==1)
        ans=((r*c)+1)/2;
    else
        ans=(r*c)/2;

```

Note: Here r is row and c is column.

---
Tags: algorithms
---


# Question
Title: Minimal Steiner Tree in unweighted directed graph
I have an unweighted directed graph $(V, E)$ and a subset $T \subseteq V$ of these vertices. I want to find the minimum tree $(V',E')$ that contains all these $T$ vertices (minimize in number of nodes $|V'|$).

In my problem all vertices $t \in T$ have no leaving edges: $$\left\\{(t,w) \in E \mid t \in T\right\\}=\emptyset$$

This is a specific case of the Directed Steiner Tree problem.

What's the best algorithm and it's complexity to find the exact solution to the Directed Steiner Tree problem? (Or, if there is, a better solutions to this specific case of the Directed Steiner Tree)

What are the most used approximations for this problem?

# Answer
This problem is still NP-hard. You can reduce the (NP-hard) unweighted, undirected Steiner tree problem to the directed one by replacing each edge by two anti-parallel arcs. You can reduce any unweighted directed Steiner tree problem to the problem that you describe by adding for each terminal t other than the root a terminal t' and an arc (t,t'). The directed Steiner tree problem is also hard to approximate, see, e.g., "Polylogarithmic inapproximability" by E. Halperin and R. Krauthgamer. However, if you look for a fast practical algorithm to get an optimal solution, the probably best option is this one: https://scipjack.zib.de/ Should give you an optimal solution to problems even with order 10000 arcs within minutes.
> 2 votes

---
Tags: graphs, trees, np-hard, approximation
---


# Question
Title: Algorithm to find the shortest path and its length for moving between many geometries
I have a set of 2D geometric figures in Cartesian space, as shown in the image. Each geometric figure has a start point and an end point (among other characteristics). For closed geometries, such as a circle, the start and end points are the same and for open geometries, such as lines, both points are different.

I need an efficient way to find the shortest path and its length (red lines), to go from one geometry to the next, starting from an origin O (usually a corner of the bounding box of all geometries) and returning to the same origin point. I already know the length of the geometries (black lines) if needed.

Criteria I have to consider:

1. I can have many more geometries in space than those in the example.
2. Each geometry is visited only once
3. To go from the starting point to the end point of each geometry (or vice versa), you can only go through the geometry itself, that is, to go from point A to point B, you can only go through the path of the circle; to go from point E to point G, you can only go through the path of the curve EG; to go from point J to point F, you can only go through the straight line FJ.
4. Once the start or end point of a geometry is reached, the geometry must be traversed from end to end (this is especially relevant for open geometries since the start and end points are different.)
5. The path must begin in the geometry whose starting point is closest to the origin.

What I currently do is:

* Put all unique points (A, C, E, F, G, H, J) in a list of points. I know that the pair of points E and G or F and J belong to the same open geometry, respectively.
* Calculate the Euclidean distance of all the points in the list, with respect to the current origin O, obtain the closest one and save it (A, in the example of the image).
* As we know that A is part of a closed geometry (a circle), it is taken out of the list of points and A is the new origin point used to find the next closest point and save it (E, in this example).
* Since we know that E is an end of an open geometry, we remove E from the list of points and the new origin point is G (the other end of the same open geometry). This is due to considerations 3 and 4 mentioned above.
* The next closest point is calculated with respect to G (getting H, in the example). And the process is repeated, until the list of points is exhausted.
* At the end, I add up the distances of the line segments OA, AE, GH, HJ, FC, CO.

The problem is that this approach is slow, especially when there are many geometries, since for each iteration I have to calculate the Euclidean distances of each point in the list with respect to the current origin and then obtain the point with the smallest distance.

I wonder if anyone knows of a better approach or an algorithm to find the shortest path (taking into account the above considerations) that might be useful to solve this problem in a better way.

# Answer
> 1 votes
There's actually an easy way to represent the open geometries within an ordinary TSP instance:

* Represent each closed geometry as a single "endpoint" vertex.
* Represent each open geometry as 3 vertices: Two "endpoint" vertices, and a "middle" vertex that is connected *only* to these two endpoints. (If the TSP solver you use expects a complete graph, you can just assign extremely large values to all but these two distances.)

All endpoint vertices are connected by an edge to all other endpoint vertices.

Because each middle vertex is reachable only from its two endpoints, and in the TSP problem, every vertex must be visited, every valid solution must visit each middle vertex immediately after one of its corresponding endpoints and immediately before the other one. That is, each middle vertex must be traversed in one of two "directions" from its endpoints. The solver is able to choose whichever combination of directions works out best overall.

(Notice that simply representing an open geometry as 2 vertices connected by an edge isn't guaranteed to work, since the solution is not required to contain that edge.)

This means your problem is no *harder* than TSP -- but as BlueRaja - Danny Pflughoeft pointed out, TSP is already NP-complete, so don't expect a fast (polynomial-time) optimal solution. That said, very large instances of TSP have been solved to optimality by Concorde, though in practice you would probably settle for one of the many good, fast heuristics.

---
Tags: algorithms, computational-geometry, shortest-path
---


# Question
Title: Probability of certain symbols in a mapping of symbol and code word
Let's say you have this mapping of symbols and codewords:

$$ \begin{array}{cc} \hline \text { Symbol } & \text { Codeword } \\ \hline \text { A } & 101 \\ \text { B } & 100 \\ \text { C } & 01 \\ \text { D } & 00 \\ \text { E } & 110 \\ \text { F } & 111 \\ \hline \end{array} $$

How is it possible to determine the probability of the occurrence of a symbol like A? Unfortunately, I have not found anything on this and would be thankful for tips.

# Answer
> 0 votes
You could *estimate* the probability of occurrence by working out the probability that a randomly generated string of bits makes a code word that lands at A.

Here that would be a 50% of a 1, then a 50% chance of a zero, then a 50% chance of a 2 again, for a 12.5% total chance of arriving at A after this random walk along the encoding tree.

That doesn't tell you the probability of A occurring in the *original* string, only the best *approximation* the coding table was able to capture.

It's possible all 6 of these symbols occur equally frequently in the input text, and that C & D were chosen arbitrarily to get shorter code words just because we didn't need all 8 combinations of 3 bits for this alphabet. Or it could be that C and D are significantly more likely to occur, and were given shorter code words to reflect that. This table alone doesn't tell us which scenario is true, or to what degree.

As long as no symbol has probability \> 33.333%, we'd arrive at an encoding table like this one even if A had a vanishingly small probability in the input (arbitrarily close to zero). There just wouldn't be any savings in encoding it with 4 characters unless we could drop a very high-probability character down to a 1-character code. So all we can say with confidence is that A's probability in the source was somewhere in the range \[0%, 16.667%\], with 12.5% being a middle-of-the-road guess.

---
Tags: encoding-scheme
---


title: Red-Black tree height from CLRS

text:
# Question
Title: Red-Black tree height from CLRS
The lemma 13.1 of CLRS proves that the height of a red black tree with $n$ nodes is

$$h(n) \leq 2\log\_2(n+1)$$

There's a subtle step I don't understand. The property 4 reported at the beginning of the chapter states:

> If a node is red, then both its children are black.

And because of such property it is later stated

> According to property 4, at least half the nodes on any simple path from the root to a leaf, not including the root, must be black. Consequently, the black-height of the root must be at least $h/2$.

I can intuitively agree, but as exercises I'd like to prove it, but I can't manage how to actually do it. Why is that property true? I'm not actually neither able to set up the problem, the only think I could think of was that I if I have $r + b = h$ nodes, where $r$ is the number of red nodes and $b$ is the number of black nodes I can have a total of

$$ k = \frac{h!}{r!b!} $$

And I'd like to prove from here that if $b \< r$ than I have the contradiction, but I need something more that this probably. Any help?

# Answer
> 2 votes
I'd prove it this way (sorry for being too late, hope it'll be useful for other people).

Let $bh(x)$ be a fixed black height.

The minum height we can have is when we have only black nodes, hence $$bh(x) = h(x)$$ so $$bh(x) \ge \frac{h(x)}{2}$$ holds.

The maximum height we can have is when we alternate a black and a red node. In other words, for each black node there is a red node (at maximum), so we'll have: $$ 2\times bh(x) = h(x) $$ hence $$bh(x) \ge \frac{h(x)}{2}$$ holds.

$\square$

**Update requested:**

The maximum height of a tree rooted in the node $x$ is reached when we alternate a black and a red node because one of the properties of a RB tree states *"A red node does not have a red child."* So if we add a red node we shall violate this property, if we add a black node we shall increase the black height.

# Answer
> 3 votes
**step 1** : At first let me say that , property 4 which states that children of a red node , should be black , comes from the definition of red-black tree , because 2 (or more) red nodes can't come after each other .
**step 2 : For the statement that is a result of property 4** : let's consider a path from root to a leaf , which consists of 2K nodes, and the number of Red ones, is more than the number of black ones, so at least number of red nodes must be K+1 and therefore number of black nodes is K-1. From property 4 we shouldn't put 2 (or more ) red nodes consecutively , so between every 2 red nodes , we should put a black one and since we have (at least) K+1 red node and (at most) K-1 black nodes , after we put the Kth red node , we will run out of black nodes and we have to put the (K+1)th red node right after the Kth red node , so we get two red nodes placed consecutively (you can prove it by induction )and this is in contradiction with Red-Black tree definition. so ***"at least half the nodes on any simple path from the root to a leaf, not including the root, must be black"***
**step 3 : For the Height of the tree : <br>** we know that the height of a tree , is the number of edges in the longest path from root to a leaf and from what we proved in step 2 , at least half of the nodes on this path can be black , so if we have the height of h , at least we have h/2 black nodes , which comes to say that the black-height is at least h/2 .
**step 4** :
And for your solution , I guess you are being too general , in my idea you'd better consider number of red and black nodes , in **an arbitrary path** from root to a leaf rather than in the whole tree .
Hope it works as an idea not the whole solution :)

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


# Question
Title: Linear deterministic algorithm for finding spanning tree T with minimal maximum edge
Given an undirected connected graph $G = (V, E)$ with weights $w : $E → $R$$^+$, define for a spanning tree T the value $λ$(T) = $max\_e$$T${w(e)} (the maximal edge weight in T ).

I need to find a linear deterministic algorithm of finding a spanning tree T with minimum maximum edge e. We were given a hint of using binary search.

I already proved that for MST of G, $λ$(MST) \<= $λ$(T) for every T spanning tree of G.

The problem that using Prim or Kruskal algorithm is not linear, and I'm trying to find a special property for such tree.

I already tried:

(In assumption I get the edges sorted): use binary search with the next comparator: remove all edges with weight above current weight. use BFS. If the graph is connected, "move left" (possible connected graph with a lighter edge) else, "move right" (can't connect the graph with only the edges that are in weight of the current weight and lighter).

the problem is that it is O(ElogE) because we need logE iterations for the binary search and E for BFS each time.

# Answer
> 1 votes
As it looks like a homework problem, I will not give you a complete solution rather than a hint.

We need to find such $W$ that the graph with edges of weight $\leq W$ is connected. Consider an edge with median weight $M$, like you do in the binary search.

* What if the graph with all edges with weight $\leq M$ is connected? Can we discard some edges completely and reduce the problem to the one where the graph has twice as less edges?
* What if the graph will all edges with weight $\leq M$ is not connected? Can we take some edges unconditionally now, process the graph somehow and reduce the probem to the one where the graph has twice as less edges?

---
Tags: algorithms, graphs, weighted-graphs, spanning-trees
---


# Question
Title: Real world applications for Steiner Tree Problem?
Are there real-world applications of the Steiner Tree Problem (STP)?

I understand that VSLI chip design is a good application of the STP. Are there any other examples of real world problems that people can suggest of that could be formulated in terms of the STP?

Background: I am beginning my PhD research and I am looking at using hybrid metaheuristics and primal-dual methods for the decomposition and solution of large-scale combinatorial optimisation problems. I find the STP fascinating, and I'm wondering if there is much real-world motivation for studying it, or if it is primarily of theoretical interest.

# Answer
> 4 votes
I am currently writing my PhD proposal, which is about finding ways to apply theory from parameterized complexity, primarily tree decompositions, to realistic network optimization problems. But I mainly plan to work with Steiner Tree, not in the last place because its simple and there are a lot of papers/benchmarks available.

Stumbled on this question because I too have some trouble finding practical motivations for studying it. I think its practical relevance is more easily motivated by the enormous amount of optimization problems that are generalizations of the vanilla STP but are more flexible. There is a nice list here: http://theory.cs.uni-bonn.de/info5/steinerkompendium/netcompendium.pdf

I think some of the problems mentioned with phylogenetic trees can be directly formulated as STP but I haven't read the papers thoroughly.

This algorithm for connected facility location and single source rent-or-buy is also interesting: http://sma.epfl.ch/~eisenbra/Publications/jcss08cfl\_final.pdf Though not directly modeled as an STP, solutions to these problems have a core that is a Steiner Tree and the algorithm makes use of a STP approximation algo directly to solve that part.

Also regarding heuristics for the STP you might be interested in this page: http://dimacs11.cs.princeton.edu/workshop.html There are quite a few new competitive algorithms that have been presented there.

---

**Edit:** You might also want to take a look at this book by William Cook:

In Pursuit of the Traveling Salesman

It is about the TSP, but that one is similarly theoretical. Chapter 3 contains really a load of concrete practical uses, not just the trivial tour finding stuff, but unexpected problems that can be solved by solving a TSP, including some biology problems as I mentioned. Part of the reason of the applicability seems to be the fact that there is a very powerful and accessible TSP solver out there, making it convenient to rephrase design problems as TSP's. I found it really inspiring as the same type of applications could be found for the STP I think (but there is no 'industry standard' solver for it so it doesn't happen in reality). Some of the chapter is free on Google books, though I recommend getting you hands on the full version cause some of the best examples are left out.

# Answer
> 1 votes
My apologies up front for not having more detail on my comment here. But I too have considered an approach of using STP in solving routing information. In fact, there are already some applications in the polynomial space where least distant routing adds vertices to direct someone, say off of an inter-state highway to surface streets, to reach shorter distances routes (directions). They may not be faster based on speed or traffic conditions.

The calculations strictly considered distance. It was partially rejected as an application since the trucking industry was not able to utilize residential streets for example, or alleys, for routing. But biking, walking, hiking could. There does seem to be some inclusion of this in Google maps now as you can choose you mode of transportation and I believe, this allows for more refined points on a greater number of qualifying routes. For example, traveling on city bus, bike or by foot, would not normally route to the interstate.

There used to be some info in the Google API, older versions, covering this routing. Not sure if it is still there, this was about 3 years ago. Good Luck.

# Answer
> 0 votes
The classic Steiner tree problem in graphs is for example used for the design of telecommunication networks, see the following link for some real-world instances: https://homepage.univie.ac.at/ivana.ljubic/research/STP/ "the edges of the input graph typically correspond to the local street map, with the edges vertices representing street intersections and the location of potential customers. The cost c associated with an edge is the cost of establishing the connection, i.e., of laying the pipe or cable on the corresponding street segment."

But you also find applications of the classic Steiner tree problem in quite different areas, such as cloud computing: https://dl.acm.org/doi/10.5555/3154580.3154595

If you consider also close relatives of the classic Steiner tree problem, such as the prize-collecting Steiner tree problem, then there are a large number of additional applications, ranging from computational biology to machine learning. See the following paper for some examples: https://onlinelibrary.wiley.com/doi/10.1002/net.22005

---
Tags: graphs, reference-request, optimization, combinatorics, applied-theory
---


# Question
Title: m-ary tree relation between vertices and leaves
A full $m$-ary tree with $n$ vertices and $i$ internal vertices has $n = m \cdot i + 1$ vertices and $l = (m − 1)i + 1$ leaves.

How can I prove it?

I know that **$m$-ary tree** is a rooted tree such that every internal vertex has no more than $m$ children. The tree is called a **full $m$-ary tree** if every internal vertex has exactly $m$ children. An $m$-ary tree with $m = 2$ is called a binary tree.

# Answer
> 1 votes
A vertex is either an internal vertex or a leaf. Since the number of all vertices is $n$ while the number of internal nodes is $i$, the number of leaves, $l$ is $n-i$.

Every vertex is identified as a child of an internal node except the root. Since there are $i$ internal node, each of them having $m$ children, the number of vertices, $n$ is $m\cdot i + 1$.

Since $i= n-l$, we also have $n = m\cdot (n-l) + 1$. Or $$(m-1)n = m\cdot l - 1,$$ which is the relation between the number of vertices and the number of leaves in a full $m$-ary tree.

---
Tags: graphs, trees
---


# Question
Title: Arguing that the inverse of Ackermann function is upper bounded by a logarithmic function (i.e. $\alpha(n) = O(\lg n)$)
The text *Introduction to Algorithms* by *Cormen, et. al.* defines the Ackermann Function $A$ as follows: For integers $k \geq 0$ and $j \geq 1$, we define the function $A\_k(j)$

$$A\_{k}(j) = \begin{cases} j+1 &\quad\text{if } k=0\\ A\_{k-1}^{(j+1)}(j)&\quad\text{if } k \geq 1\\ \end{cases}$$

The inverse of the function $A\_k(n)$, for integer $n \geq 0$,is defined by

$$\alpha(n) = \min \\{k : A\_k(1) \geq n\\}$$ .

$$\alpha(n)=\begin{cases} 0 \quad\text{ for } 0\leq n\leq 2 \\ 1 \quad\text{ for } n=3\\ 2 \quad\text{ for } 4\leq n\leq 7\\ 3 \quad\text{ for } 8\leq n\leq 2047\\ 4 \quad\text{ for } 2048\leq n\leq A\_4(1)\\ \end{cases}$$ ***It is only for impractically large values of $n$ (greater than $A\_4(1)$, a huge number) that $\alpha(n) \> 4$, and so $\alpha(n) \leq 4$ for all practical purposes.***

From the above analysis we can say that for $n$ (with in practical limits), we have $$\alpha(n) \leq 4 \leq \lg n \text{ for all } n \geq 16$$

Hence we can say that $\alpha (n)= O(\lg n)$, when $n$ is within practical limits.

This is the analysis that I thought of, but what bugs me is that asymptotic analysis should be for $n$ when it is arbitrarily high, i.e. when $n \rightarrow \infty$. In this case though $A\_4(1)$ is a very very large number but it is after all finite and in the analysis we assumed $n$ to be at most $A\_4(1)$. In that case, isn't my analysis flawed or abuse of asymptotic Big-Oh notation? If so (which I guess definitely is) how to process correctly?

# Answer
Yes, it is an abuse of big-O notation.

**Hint:** To actually prove the theorem for **all** $n$ (not only those within practical limits), try to show instead that the ackerman function is $\Omega(2^n)$. This will help you to prove that $\alpha(n) = O(\log(n))$.
> 1 votes

---
Tags: algorithms, asymptotics, mathematical-analysis
---


title: LALR lookahead is wrong, why?

text:
# Question
Title: LALR lookahead is wrong, why?
I am studying LALR(1) parser and I have this question:

Consider the following Grammar

S - \> V = E

E - \> F | E+F

F - \> V | int | (E)

V - \> id

Construct the LALR(1) parsing table for this Grammar.

While generating the item-set DFA for this problem, I encountered a problem in the fifth set.

According to this website, http://jsmachines.sourceforge.net/machines/lalr1.html, the lookaheads for productions with F and V on the LHS have only \\$ in the lookahead whereas I am getting $ and + in all. Could someone please explain which is correct?

# Answer
I entered your grammar in that tool:

```
S -> V = E
E -> F
E -> E + F
F -> V
F -> int
F -> ( E )
V -> id

```

And it reported state 3 (**GOTO**(*S1*, **=**)) as (spaced out a bit for readability):

```
{
 [S -> V =.E,  $];
 [E -> .F,     $/+];
 [E -> .E + F, $/+];
 [F -> .V,     $/+];
 [F -> .int,   $/+];
 [F -> .( E ), $/+];
 [V -> .id,    $/+]
}

```

which seems to agree with your notebook.

Like most online grammar tools, that one is pretty picky about input format. Also, like most online grammar tools, there is no easily accessible documentation about what input format it expects. So I can't tell you exactly what format it wants, but I'm pretty sure that it doesn't accept the `|` operator, and that it requires syntactic elements to be separated by spaces.
> 0 votes

---
Tags: formal-grammars, compilers, parsers
---


# Question
Title: Integral solutions to circulation problem
Suppose we have a circulation problem (with only one commodity), where all lower bounds, upper bounds, and costs are integers. Are we guaranteed that if there is a solution, then there is an integral solution? Is there an algorithm that can find one in polynomial time?

For standard network flow, we know that there is a max flow that is integral, and there are polynomial-time algorithms that can find such an integral flow. I'm wondering if the same is true for circulation problems, which are a generalization of max-flow.

# Answer
> 6 votes
Circulation problems are not just a generalization of max-flow, there is a reduction backwards as well. Suppose we have some directed graph $G = (V, E)$ with edge costs, capacities, and lower bounds.

Any edge $u \to v$ in $G$ with we can replace with two nodes $s, t$ and two edges $s \to v$ and $u \to t$ where one of the edges has the original cost, capacities, and lower bounds and the other is free and unlimited. Call this graph $G'(e)$, where $e = u\to v$ is the edge that was replaced.

Then if a flow with a certain cost exists in $G'(\cdot)$, it must also exist as a circulation in $G$ with the same cost. Vice versa, if a circulation exists in $G$ and it uses edge $u \to v$, then that flow also exists in $G'(u\to v)$ with the same cost.

Therefore to solve the circulation problem we can pick an arbitrary edge $e$, calculate $G'(e)$ and use a traditional network flow algorithm to find the optimal flow. By the traditional arguments, this optimal flow is integral. We then pick another edge (avoiding edges that were part of a previous optimal flow) and repeat, keeping the best solution, until no more unknown edges are left.

Since in the worst case this adds a factor of $|E|$ to the complexity of the polynomial complexity, this is still polynomial. And of course the optimum from all integral flows found is itself integral.

To handle the lower bounds on the edges of $G'$, one can either note that the linear programming constraint matrix is unimodular (see these MIT lecture notes), from which it follows that there exists an integral solution if there is any solution; or one can use a standard reduction to eliminate the lower bounds (see, e.g., Ahuja et al, Network Flows, page 39) and then solve with a standard algorithm for network flow.

# Answer
> 1 votes
These lecture notes also mention the reduction from the *circulation problem* to the *max-flow problem* (Theorem 2), and reduction from *network flows with lower bounds* to the *max-flow problem* (Theorem 5). The proofs are of a few lines.

---
Tags: network-flow
---


title: Stability of QuickSort Algorithm

text:
# Question
Title: Stability of QuickSort Algorithm
**Def**: the stability of algorithm is defined in case of the algorithm preserves same value elements while sorting as the following shows:

So for this QuickSort algorithm:

```
public class QuickSort {

    public static int[] sortedData;

    public static void sort(int[] data, int low, int high){
        sortedData = data;
        int i = low;
        int j = high;
        int mid = low+(high-low)/2;
        int pivot = data[mid];

        if(i>j) return;

        while(i<=j){
            while(data[i]<pivot)
                i++;
            while(data[j]>pivot)
                j--;
            if(i<=j){
                int temp = data[i];
                data[i] = data[j];
                data[j] = temp;
                i++;
                j--;
            }
        }

        if(low<j)
            sort(data, low, j);
        if(high>i)
            sort(data, i, high);
    }

}

```

**Problem**: We can make it stable by changing condition `while(i<=j)` to `while(i<j)`. What do you think please? What advantages this will bring please? It will reduce time by constant factor and $O(n)$ in worst case if all elements are equal other than that I am not sure what are the advantages of stability condition of algorithm please?

# Answer
One huge advantage of a stable sorting algorithm is that a user is able to first sort a table on one column, and then by another.

Say that you have a website like Wikipedia with some tabular data, say a list of sorting algorithms, two of the columns being *year discovered* and *name*. If you want that table sorted by year, and then alphabetically by name, you can sort the table first by name, then by year.

This is only guaranteed to work with stable sorting.
> 9 votes

# Answer
You can’t make Quicksort stable easily. Say you have an array with a million non-negative integers, and say five percent are zeroes. Quicksort will during the first partitioning move all zeroes from the second half to the first half, in reverse order, and that would be very hard to prevent.

As far as using a stable algorithm for sorting by multiple columns, I’d say sorting *once* with a more complex sorting criteria will be much more efficient.
> 0 votes

---
Tags: algorithms, sorting, quicksort
---


# Question
Title: Expected linear-time algorithm for finding MST with probability for sampling an edge other than 1/2
I'm trying to understand this algorithm : https://en.m.wikipedia.org/wiki/Expected\_linear\_time\_MST\_algorithm

As described in the wiki article, it works in 5 steps to find the MSF for a graph $G = (V, E)$:

1. Do two iterations of Boruvka resulting in a graph $G'= (V', E') $
2. Select each edge from $E'$ with probability $1/2$ and get set of selected edges $E''$
3. Call yourself recursively on the graph $G'' = (V', E'')$ and get an MST $F = (V', E''') $
4. Find the set $L$ of all F-light edges
5. Call yourself recursively on the graph $G''' = (V', E''' \cup L) $

I understand the correctness and the expected performance for this. However, if I change the probability in step 2 from 1/2 to some other probability $p$, the time analysis breaks down for me and I can no longer prove that it will work in expected linear time. How do I reason about $p$? Does $p$ need to be exactly 1/2 for the algo to work in linear time? Why?

# Answer
> 1 votes
Here is performance analysis adapted slightly from section $\S7.14$ of **State-of-the-Art Algorithms for Minimum Spanning Trees** by *Jason Eisner*, (1997). It corrects some very mild mistakes in that Wikipedia article as well as in the original paper (1995) by the inventors of the algorithm.

Let $\langle m, n\rangle$ denote a call of the algorithm on a graph (not necessarily connected) with $n$ nodes and $m$ edges. The initial call is $\langle m\_0, n\_0\rangle$.

A call $\langle m, n\rangle$ takes time $O(m+n)$, exclusive of the recursive calls at step 3 and step 5. So the total running time is proportional to the total number of edges plus the total number of vertices over all calls.

Let we consider the binary tree of recursive calls: each call $\langle m, n\rangle$ (with $n\gt1$) spawns both a left-child call, which is the step 3 and a right-child call, which is the step 5.

These child calls have at most $n/4$ vertices apiece, thanks to the two Borůvka passes at step 1. So the call tree has $O(n\_0)$ vertices total.

Now consider the total number of edges in the call tree.

The call $\langle m, n\rangle$ has a left child of expected size $\langle m/2, n/4\rangle$ or smaller, and a right child of expected size $\langle n/2, n/4\rangle$ or smaller. We have two observations.

* At depth $d$ in the tree, there are $2^{d−1}$ right children of expected size at most $\langle 2n\_0/4^d, n\_0/4^d\rangle.$
* The call $\langle m, n\rangle$ together with all its left-spine descendants has at most $m + m/2 + m/4 + \cdots= 2m$ expected edges.

Every call is a left-spine descendant of the root or of a right child.

* The root and its left spine descendants expect at most $2m\_0$ total edges.
* A right child at depth $d$ and its left-spine descendants expect at most $2 · 2n\_0/4^d=n\_0/4^{d-1}$ total edges.

Summing these bounds over the root and all right children, we obtain a bound on expected edges of $2m\_0 +\sum^\infty\_{d=1}2^{d-1}n\_0/4^{d-1}=2m\_0 + 2n\_0$. So the expected tims is $O(m\_0)$.

#### What happens if we change probablity from $1/2$ to $p$?

What we need to reconsider is the total number of edges in the call tree.

The call $\langle m, n\rangle$ has a left child of expected size $\langle mp, \frac n4\rangle$ or smaller, and a right child of expected size $\langle \frac n{4p}, \frac n4\rangle$ or smaller. We have two observations.

* At depth $d$ in the tree, there are $2^{d−1}$ right children of expected size at most $\langle \frac {n\_0}{4^dp}, \frac{n\_0}{4^d}\rangle.$
* The call $\langle m, n\rangle$ together with all its left-spine descendants has at most $m + mp + mp^2 + \cdots= \frac m{1-p}$ expected edges.

Every call is a left-spine descendant of the root or of a right child.

* The root and its left spine descendants expect at most $\frac {m\_0}{1-p}$ total edges.
* A right child at depth $d$ and its left-spine descendants expect at most $\frac{\frac{n\_0}{4^dp}}{(1-p)}$ total edges.

Summing these bounds over the root and all right children, we obtain a bound on expected edges of $$\frac{m\_0}{1-p} +\sum^\infty\_{d=1}2^{d-1}\frac{\frac{n\_0}{4^{d}p}}{(1-p)}=\frac{m\_0}{1-p} + \frac{n\_0}{2p(1-p)}.$$ So the expected tims is still $O(m\_0)$.

---
Tags: time-complexity, randomized-algorithms, minimum-spanning-tree
---


# Question
Title: Word that describes text transformation into a code with data loss
I am working with a piece of software code which transforms a character array into a single integer. For example, if I have the array `[ a, b, c ]`, then it becomes 97 + 98 + 99 = 294, for ASCII 'a' = 97, et cetera.

So this code converts an arbitrary-length sequence of characters into a single number. The transformation has the following properties:

* It accepts arbitrary-length input;
* A transformed input cannot be reversed (well, there may be multiple possible inputs to a transformed output, for example, `[a, b, c]` → 294, but also `[b, b, b]`);
* The output is stored into a fixed-size binary number,

I am looking for a word that fits best here. The terms *digest*, *checksum*, *encrypted value/code/text*, *obfuscated text*, *hash*, *cypher*, *encoding*, *lossy compression* or just *transformation* came into my mind.

The transformation *looks* like it is an application of *lossy compression*. However, I think the algorithm is not meant to compress in order to save space, but instead to encrypt, obfuscate, or at least make sure that humans cannot read the stored value, or have a hard time doing so.

Which word should I use here?

Example usage: "Finally, the input is compared to the \___, and if they're equal, then the access is granted."

# Answer
What you are describing sounds a lot like a "hashing function", some examples of which are MD5 and SHA-1, and is the correct wording in the computer science-perspective. The result of a hashing function (= output) is the hash, which follows standardized characteristics (usually length and possible characters) per hashing function.

A key feature of hashing functions is the one-way transformation, meaning that for a given output you can't go back to the initial input with certainty - you can only find "collisions", as in your example for \[a b c\] and \[b b b\] producing the same output.

Based on the terms given in your example, I would like to counter some of them:

* "digest" is (afaik) mostly used for the output of the hashing function
* "checksum" describes one specific use case of hashing functions, which is controlling for errors when transferring large arrays / files of data. However, as this is a use case instead of the act of transofrming your input into the output, I would advise against that
* "encrypted value/code/text" are relying on "encrypted" which is functionally different from hashing, as an encryption can be reversed, providing the initial input without uncertainty. Hashing offers no way to reverse it and it is therefore not possible to get back to the input from a given output.
* "obfuscated text" relies on obfuscation, which is usually done with code. "Obfuscated code" means that the code has been actively and willingly made harder to read for humans (e.g. by introducing random jumps that complicate understanding how the computer executes the code). As the "obfuscation" is transparent to machines, the code will behave functionally similar to the original - which is not true for your example.
* "hash" is the output of a hashing function, hence almost there
* "cypher" (or cipher) is usually used as a word in cryptography, and describes the algorithm used to encrypt and decrypt, which is not what your function is able to do
* "encoding" as a process is always accompanied by "decoding", which will return the input
* "lossy compression" is somewhat coming close, but compression implies that the data has been reduced in size but can still be used for similar applications. Your described function will significantly reduce the size but prevents most applications. After all, putting a poem through your function will not result in a presentable poem.
* "transformation" is ok as it is generic, but provides very little information as to what is actually happening
> 4 votes

---
Tags: terminology
---


# Question
Title: Is it necessary that Minimum/Maximum Heap must be a Binary Heap?
I find this extremely wrong, that a lot of books, articles, video tutorials, online courses or trainers define Minimum/Maximum Heap data structure as a particular type of the Binary Heap data structure.. however! according to the definition of what is `Heap` Data Structure, that's wrong! Heap can be perfectly fine either Binary or non-Binary.

I have also read this in some Google Engineer's blog, that my thoughts are correct on this.

Any take? maybe I'm wrong? nothing, at all, restricts the Minimum/Maximum Heap that they must be necessary Binary Heap variations. Node can have 3 children, and it would still fit the Minimum/Maximum Heap definition.

Question is: how do you think? am I wrong or not? what's your take on this?

# Answer
> 1 votes
A heap can be binary or k-ary, so it's fine to think like you do, in my opinion. Binary heaps are more common to think about. The time complexities for the different heap operations change for the better or worse as we vary k.

# Answer
> 0 votes
Instead of "heap", think "priority queue". A priority queue is a data structure where elements can be inserted in any order, but are removed in key order.

We will suppose that the priority queue uses a comparison operator (say, less-than) to determine key order. (This need not be the case; if the keys are integers, for example, you could use a radix operator.) We will further suppose that it is a min-queue, where elements are removed in ascending order (that is, the first element is the minimum).

Then simply reversing the sense of the comparison operator gives a max-queue.

Heaps (in their many forms) are one way of implementing priority queues, just like how balanced binary search trees (in their many forms) are one way of implementing key-value dictionaries. But they are not the only way.

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


# Question
Title: What class is the language $(C,(v_i)_{i=1}^m,x)$ complete to s.t. $C(x)$ is a boolean circuit with $m$ gates with values $\{v_i\}_{i=1}^m$
Given the following language: $$ L=\left\\{\\,(\\,C,\\,\\{v\_i\\}\_{i=1}^m, \\,x\\,) \enspace :\enspace \substack{C(x) \text{ is a boolean circuit with } m \text{ gates} \\i\text{'th gate value is } v\_i \text{ on input } x} \right\\} $$ I need to find out to what known class $L$ is **complete** to with respect to *logspace* reductions.

I think that it is impossible to reduce $\text{CVAL}$ to $L$ because if we can compute gate's values $\\{v\_i\\}\_{i=1}^m$'s we could solve $\mathrm{CVAL}$ in logspace which would imply $\mathbf{P = LOG}$.

I also think that $L\in\mathbf{P}$ because we can calculate $C(x)$ and of course all the gates $\\{v\_i\\}\_{i=1}^m$ using BFS as in computing every boolean circuit value.

Please advise. Thank you.

# Answer
The language $L$ is $\mathbf{LOG}$-complete.

All we need to check is for each gate, its value (from the $(v\_i)\_{i=1}^{m}$ input) is consistent with its connected gates (i.e. children).

In other words, just iterate all the gates and make sure the $(v\_i)\_{i=1}^{m}$'s are consistent.

This can be done in *logspace* because we just need to hold the pointer to the gate we are currently checking.

$L$ is complete because every language in *logspace* is complete.
> 1 votes

---
Tags: complexity-theory, reductions, circuits
---


# Question
Title: Matching two noisy / lossy versions of the same data stream to each other
Say I have two noisy / lossy streams of symbols of the same data. Essentially, I want to match up the two streams as best as possible. For example, say I have:

```
s1 = 1 2 6 3 8 0 4 3 2 7 6 2 ...

s2 = 1 2 3 6 3 9 3 2 7 6 2 ...

```

and I'm essentially trying to end up with this:

```
s1 = 1 2   6 3 8 0 4 3 2 7 6 2 ...
     | |   | |       | | | | |
s2 = 1 2 3 6 3 9     3 2 7 6 2 ...

```

This feels like the kind of problem for which a well-known algorithm was invented in the 60s that's a household name with whoever knows what it is or something. But I haven't been able to find it, possibly because I don't know how to express the problem other than by my example above.

Any help or pointers to what such an algorithm might be -- or even what the problem is called so I could research it myself -- would be wonderful :)

# Answer
Sequence Alignment is exactly what I was looking for -- thank you @Yuval Filmus!

This is commonly used in Genetics to line up genes, etc. Best I can understand, these typically require a fixed alphabet which I don't have, which means I can't do it as a stream. But if I give up on trying to do it as a stream and just collect both streams in their entirety before beginning, I can construct my alphabet by just observing what symbols appear in each stream before beginning.

A handy Python package which implements this out of the box is python-alignment.
> 3 votes

---
Tags: subsequences, streaming-algorithm
---


title: Arithmetic hierarchy via oracles

text:
# Question
Title: Arithmetic hierarchy via oracles
My professor gave an introduction to the arithmetic hierarchy via Turing reductions, stating that, for instance, $\Sigma\_2 = \text{r.e.}^\text{r.e.}$ (namely an $\text{r.e.}$ pseudocode with access to an $\text{r.e.}$ oracle) or $\Pi\_3 = \text{co-r.e.}^{\text{r.e.}^\text{r.e.}}$. Later, the equivalent formulation via alternating quantifier descriptions was discussed, but I found it difficult to link the two definitions. I have not been able to find any references describing the connection between the above definitions, with everything I've seen having solely to do with the quantifier-based description. Are there any texts/notes that might cover what I'm looking for?

# Answer
> 2 votes
I found Dexter Kozen's book "Theory of Computation" to contain a very understandable introduction to these topics.

---
Tags: computability, reference-request
---


# Question
Title: Smallest 3-SAT problem that no one has been able to solve?
In number theory progress is sometimes guided by people stating a specific Diophantine equation that they don't know how to solve.

Is there anything similar in the field of Boolean satisfiability?

More specifically what is the smallest 3-SAT instance (measured by fewest number of variables) that people have tried to solve (by exhibiting a satisfiability or an unsatisfiability certificate) but no one has succeeded in solving either way?

If one could do $10^{30}$ operations per second (which I assume won't be possible for a long time) and if there was a 3-SAT algorithm with performance of $1.1^n$ (which I assume won't be available for a long time) then for $n=1000$ it would run for a millennium or so, so it seems plausible there might exist a concrete example of a 3-SAT instance with 1000 variables that no one knows how to solve. As indicated at Is there an instance of 3-SAT in less than 100 variables that no one has been able to solve?, it seems unlikely that such an instance exists for $n=100$, so it is likely that the smallest such instance uses more than 100 variables.

# Answer
> 3 votes
Small and hard SAT instances in the literature typically are *crafted benchmarks*, instances generated specifically to exploit weaknesses of existing SAT solvers and solving methods. As such, unlike a tough Diophantine equation plucked from the mathematical firmament, the satisfiability or unsatisfiability of such crafted instances is already known. So there's no smallest instance with no known resolution. The instances are interesting only in how they highlight either the weakness of existing solver methods or a weakness in how we encode some conceptually simple problems.

Creating a smallish infeasibly hard SAT instance is relatively easy. Generate a random 3-SAT instance of 1,000 variables with a clause/variable ratio a little bit above the critical ratio to ensure the instance is unsatisfiable with high probability. You might want to avoid triangles, as in "Generating Difficult SAT Instances by Preventing Triangles", but you probably won't need to. The instance's unsatisfiability ensures there will be no lucky early termination and the variable count is high enough to push the expected runtime well beyond human lifetimes for even the best solvers.

---
Tags: np-complete, satisfiability, 3-sat
---


# Question
Title: Which is the equivalent processing of human brain in terms of computer processing?
How many flops my brain can process, or how many GHz is a human brain capable of? Is it valid to think that each celular brain is like a small cpu? (like cuda architecture). Our brains works in parallel, right?

# Answer
> 6 votes
Here is what we know for sure. The largest neuronal network simulation to date was achieved using the K Japanese supercomputer (see the Top500) during summer 2013, a few months ago.

Using the open-source software NEST, the scientists simulated a network consisting of 1.73 billion nerve cells connected by 10.4 trillion synapses. To realize this feat, the program recruited 82,944 processors of the K Computer and used 1 petabyte of memory. The process took 40 minutes, to complete the simulation of 1 second of neuronal network activity in real, biological, time. Although the simulated network is huge, it only represents 1% of the neuronal network in the brain.

K is a peta-scale supercomputer, so, we need an exa-scale machine to completely simulate the whole human brain. These machines will be (probably) available between 2017-2020.

# Answer
> 4 votes
Here's my 2 cents on the question, please take it with many grains of salt as I'm not a neuro scientist.

If we make the assumption that every change in neuronal state is equal to a floating point operation then we get:

* For full nervous system: $200 \times 86e9 / 1e9 = 17200$ GFLOPS
* For the cerebral cortex alone: $200 \times 23e9 / 1e9 = 4600$ GFLOPS

This simplification might be grossly underestimating the amount of computation that is going on in the brain. If you think about the very abstracted model of neurons that is commonly used in machine learning, where a neuron performs an operation of the form $$out = f(\sum\_i w\_i in\_i)$$, you see that a biological neuron performs a very large number of floating point operations to arrive at it's output. This number seems to be roughly proportional to the number of synapses ($10e4$ to $10e5$ on average). If we take that into account then:

* For full nervous system: $172e6$ to $1720e6$ GFLOPS
* For the cerebral cortex alone: $46e6$ to $460e6$ GFLOPS

Just for comparison the K80 GPU from NVIDIA can do 8740 GFLOPS while the current fastest supercomputer clocks at 33 PFLOPS (33e6 GFLOPS).

# Answer
> 4 votes
> Ralph Merkle, a computer scientist at Xerox PARC, published a paper in 1989 evaluating intellectual processing power. He measured it in three different ways.
>
> Method One: There are about 1 quadrillion synapses in the brain. They process about 10 nerve impulses per second. Therefore the brain carries out about 10 quadrillion synapse operations per second.
>
> Method Two: The human retina (which has its own processing power and is relatively well understood) contains about 100 million nerve cells performing about 10 billion addition operations per second. The brain is bigger than the retina by a factor of somewhere between 100 and 10,000. Therefore the brain must process between 1 and 100 trillion operations per second.
>
> Method Three: The human brain consumes about 25 watts of energy, of which about 10 watts are used directly for mental processes. We know the power consumption of a single synapse and can estimate the average distance between synapses. This means we can figure the maximum number of synapse operations that can be supported by the brain's "power supply." The upper limit turns out to be 2 quadrillion synapse operations per second.
>
> Averaging out these estimates, it looks as if the brain may run at around 1 quadrillion synapse operations per second.

from: http://archive.wired.com/wired/archive/5.01/ffgenome.html?pg=9&topic=

Merkle's paper: http://www.merkle.com/brainLimits.html

# Answer
> 3 votes
This is an apples and oranges comparison. There is no known way to measure the CPU power of a neuron because it is "apparently" not computing in a way that computers do. However, there are some scientists who are willing to extrapolate somewhat using estimates based on the retina processing images vs computer algorithms doing the same, and so on. Of course this should be taken as a "SWAG". For example:

> The 1,500 cubic centimeter human brain is about 100,000 times as large as the retina, suggesting that matching overall human behavior will take about 100 million MIPS of computer power.

–Moravec, When will computer hardware match the human brain, page 2, 1997

Also, the trends of Moore's law can be used to estimate the arrival of such computing capacity (also with the counterissue that some think it may be slowing).

Abstract of the Moravec paper:

> This paper describes how the performance of AI machines tends to improve at the same pace that AI researchers get access to faster hardware. The processing power and memory capacity necessary to match general intellectual performance of the human brain are estimated. Based on extrapolation of past trends and on examination of technologies under development, it is predicted that the required hardware will be available in cheap machines in the 2020s.

However, this is evading the key issue because while the picture may be somewhat understandable for **hardware** it is not known what (or, strictly, *whether*) **algorithms (software)** can "create" or "exhibit" intelligence. In fact, it is quite conceivable that Google or some other company (say Amazon) right now has the magic threshold of 100 M-MIPS cloud computing capacity. For this reason it is quite plausible to conjecture that if machine intelligence is ever constructed it will first be exhibited in a supercomputer or a computing cloud.

# Answer
> 0 votes
\[Since I can't add a comment above...\]

http://www.wsj.com/articles/amazons-spending-leads-to-another-loss-1414095239 suggests that Amazon is spending on the order of 5% of revenue on data centers. Revenue was around \\$90 billion/year in 2014, so \\$4.5 billion. Their servers will be replaced every two or three years, so let's use two years of revenue to estimate the cost of their data centers and equipment: \\$8 billion. Take around half of that for operations (electricity). Then we'll estimate around \\$4,000 per server. Assume a server has a couple of hefty cpus, 128GB of ram, 10Gb networking, a few terabyte hard drives. So you get a million servers using that approach.

\[This estimate is probably within an order of magnitude or two. Amazon probably doesn't spend \\$400 or \\$40,000 per server, and probably doesn't spend either \\$400 million or \\$40 billion on their server hardware, and probably doesn't have either 16GB or 1TB of ram per server.\]

Moravec suggests that a typical computer will balance memory and computational capacity to the tune of 1MB/Mips. So a server is 128Gips. Total computation capacity would them be around 128 billion Mips. Using the Moravec estimate, that's about 1,000 humans. Merkle suggests it might be as low as 10 humans.

# Answer
> 0 votes
*While this answer may not be appreciated by some, it is worth recognizing that the question I answer is not a computer science question, but, one that makes assumptions about biology (a different field, although many "technologists" often like to believe they master it because they master a particular branch of the practical discipline engineering. )*

I'll contribute a factor many might miss. Moore's law is roughly defined as an inherent movement towards transistors approaching the smallest possible scale they can be, to still operate as on/off switches (electrons still being able to do that. ) The idea that this inherent trend exists in the "appendage" of Homo sapien that is technology, but not in biology itself, is very improbable and lacks basics of normal ability to reason. Neurons as cells are humongous, their diameter are 10000x the diameter of modern transistors, and modern transistors are close to what is assumed to be some type of minimal size. The alternative to the absurd (but popular) theory that the brain is a hundred billion switches with a thousand connections each, is that there is a lower level information system with transistors the size that is predicted from inherent evolution towards minimization. There has for more than 70 years been a candidate for such a transistor, tubulin in microtubules, 4.5x8 nm and organized into a lattice structure, with very strong and interesting proof in the CAMKII protein.

# References

Craddock TJA, Tuszynski JA, Hameroff S (2012) Cytoskeletal Signaling: Is Memory Encoded in Microtubule Lattices by CaMKII Phosphorylation?. PLOS Computational Biology 8(3): e1002421. https://doi.org/10.1371/journal.pcbi.1002421

---
Tags: terminology, human-computing, computer-vs-human
---


# Question
Title: How can we construct algorithm to evaluate logarithm of a real positive number
How can we construct the algorithm to evaluate the logarithm of a real positive number bit by bit in the base 2 system? I have first expressed any number as $x\cdot2^n$, where $x \in \[1,2\]$, by shifting the binary points. But after that, I am not sure what to do.

# Answer
Consider $x$ with $1 \le x \< 2$. We need to find $f = \log x$ (log base is 2). Denote the binary form of $f$ as $(0.b\_1 b\_2 b\_3 \ldots)$ . Each $b\_i$ is a bit.

$f = \log x \quad\quad (1)$

$\Leftrightarrow$ $2f = \log x^2$

$\Leftrightarrow$ $(b\_1. b\_2 b\_3 \ldots) = \log x^2$

So, $x^2 \ge 2$ implies $b\_1$ must be $1$, and $x^2 \< 2$ implies $b\_1$ must be $0$. Thus, $b\_1$ can be deduced just by comparing $x^2$ with $2$.

After finding $b\_1$, subtract it from both sides of above to obtain equation similar to $(1)$. Repeat the process to deduce bit $b\_2$. Repeat this to deduce as many bits as required.

You can read further about this algorithm in this article (written by me).
> 0 votes

---
Tags: algorithm-analysis, logic
---


# Question
Title: Transitions of Turing machine in Cook Levin theorem proof
I am looking at the proof of the Cook-Levin theorem in `Computers and Intractability: A Guide to the Theory of NP-Completeness`. In particular, I find one thing unclear. He constructs the statement that is satisfied if and only if transition from step $i$ to step $i+1$ is correct. It goes as follows:

So essentially these statements say that when we are in state $q\_k$ at time $i$ and the head is on the square $j$ and reads from it symbol $s\_l$, then in the time $i+1$ our head will be at the square $j+\Delta$, we will be in state $k'$ and we will write $s\_{l'}$ to the previous square. But I am worried since at no point we check what happens to the rest of the squares, namely if for example we had $ID\_i$ to be $0000q\_0000$ and $ID\_{i+1}$ to be $11111q\_511$, shouldn't all the conditions above be satisfied, however this isn't a valid transition?

# Answer
This part is guaranteed by the first subgroup of $G\_6$, described in the page 42:

> The first subgroup guarantees that if the read-write head is *not* scanning tape square $j$ at time $i$, then the symbol in square $j$ does not change between times $i$ and $i+1$. The clauses in this subgroup are as follows: $$\\{\overline{S\[i, j, l\]}, H\[i, j\], S\[i+1, j, l\]\\}, 0\leqslant i\<p(n), -p(n)\leqslant j\leqslant p(n) +1, 0\leqslant l\leqslant v$$

The group $G\_6$ is made of the subgroup you quoted and the subgroup above.
> 2 votes

---
Tags: algorithms, complexity-theory, formal-languages, np-complete
---


title: Ip address release/renew

text:
# Question
Title: Ip address release/renew
When you release your IP address using the ipconfig/release command and then renew with ipconfig/renew, the computer will request and receive the same address you had previously. Why is this so?

How would you (what commands would you use) so that your computer will not request the same address?

# Answer
> 5 votes
The DHCP protocol spec, RFC 2131, encourages a DHCP server to remember client configuration parameters when an IP address is released in the hope that the parameters can be reused when the same client requests a new address. So a conforming DHCP server implementation will typically offer the same IP address to a returning client if that address is still available. This is generally desirable to avoid having to (for example) update DNS records.

# Answer
> 1 votes
Although this doesn't answer the question directly, I think it may be relevant for some readers.

Because DHCP is optional, you can set whatever IP address you want for your device. Beware it's up to you to choose an address not already in use, also DHCP servers don't usually notice if a device is using an address in their pool and may assign the address you choose to some other device later on.

*note I'm mostly talking about IPv4 since that's mostly where DHCP is relevant, v6 is somewhat different.*

In some situations, you are locked into using an automatic address because you don't really control the device (ISP controlled devices, mobile networks).

In others (Corporate/School networks, LANs) you typically can configure the device to use a specific IP address (\*nix: `ifconfig [devname] 10.11.12.13`, windows: Adapter settings gui \> TCP/IP???).

Devices find each other by IP address independent of the DHCP server assigning an address. See Address Resolution Protocol.

If you manually set an IP address, it may at first seem like you have no access to the internet because DHCP can also provide your device with 'gateway' and DNS settings.

The gateway is the IP address to send traffic bound for addresses not in the local network. Without this your device will report that any IP outside your LAN is unreachable, even if name resolution (DNS) works. Default Gateway

The DNS server setting is the IP address that the device will query when attempting to turn domain names into ip addresses (name resolution). Without this (but with a good gateway, or directly on the internet) you will be able to connect to the ip address of public hosts (if you know the IP address) but won't be able to use names like 'www.google.com' to connect to another machine. DNS

If you just need to set your device IP address without using DHCP, you can copy the gateway and DNS settings from the DHCP assigned configuration to your manual configuration and set the IP address to anything within the same subnet as your gateway.

---
Tags: ip
---