title: What does being Turing complete mean?

text:
# Question
Title: What does being Turing complete mean?
I see that most definitions of what it is to be Turing-complete are tautological to a degree. For example if you Google "what does being Turing complete mean", you get:

> A computer is Turing complete if it can solve any problem that a Turing machine can...

While it is very well defined whether different systems are Turing complete or not, I haven't seen an explanation of what the implications/consequences of being Turing complete are.

What can a Turing machine do that where no non-Turing machine exists that can also perform the same task? For example a computer can perform simple calculations like `(1+5)/3=?`, but an ordinary calculator can also do them, which is non-Turing complete if I am correct.

Is there a way to define the capabilities of Turing Machine without just saying "being able to simulate another Turing Machine"?

# Answer
I pondered a while whether to add yet another answer. The other answers focus on the middle of his question (about "turing complete", "tautology" and so on). Let me grab the first and last part, and thus the bigger and slightly philosophical picture:

# But what does it mean?

> What does being Turing complete mean?
>
> Is there a way to define the capabilities of Turing Machine without just saying "being able to simulate another Turing Machine"?

Informally speaking, being Turing complete means that your mechanism can run *any* algorithm you could think of, no matter how complex, deep, recursive, complicated, long (in terms of code) it is, and no matter how much storage or time would be needed to evaluate it. It goes without saying that it only succeeds if the problem is computable, but if it *is* computable, it *will* succeed (halt).

(N.B.: to find out why this is "informal", check out the Church-Turing thesis which goes along those lines, with more elaborate wording; being a thesis, it could or could not be correct, though. Thanks to @DavidRicherby for pointing this little omission out in a comment.)

"Algorithm" means what we commonly understand as computer algorithm today; i.e., a series of discrete steps manipulating storage, with some control logic mixed in. It is not, however, like an Oracle machine, i.e., it cannot "guess".

# Example for a practical non-t.c. language

If you have programmed yourself, you probably know regular expressions, used to match strings to some pattern.

This is one example of a construct that is *not* Turing Complete. You can easily find exercises where it is simply impossible to create a regular expression that matches certain phrases.

For example (and this has surely vexed many programmer in actual real applications), it is theoretically and practically impossible to create a regular expression that matches a programming language or a XML document: it is impossible for a regexp to find the block structure (`do ... end` or `{ ... }` in languages; opening and closing tags in XML documents) if they are allowed to be arbitrarily deep. If there is a limit there, for example you can only have 3 levels of "recursion", then you could find a regular expression; but if it is not limited, then it's a no go.

As it is obviously possible to create a program in a Turing-complete language (like C) to parse source code (any compiler does it), regular expressions will never be able to simulate said program, hence they are by definition not Turing-complete

# Motivation

The idea of the turing machine in itself is nothing practical; i.e., Turing certainly did not invent it to create a real computer or something like that, as opposed to Charles Babbage or von Neumann, for example. The point of having the concept of the Turing Machine is that is *exceedingly* simple. It consists of almost nothing. It reduces possible (and actual) computers to the barest imaginable minimum.

The point of this simplification, in turn, is that this makes it easy(ish) to ponder about theoretical questions (like halting problems, complexity classes and whatever theoretical computer science bothers itself with). One feature in particular is that it is usually *very* easy to verify whether a given language or computer can simulate a Turing Machine by simply programming said Turing Machine (which is so easy!) in that language.

# To infinity

Note that you never need *infinite* time or storage; but both time and storage are unbounded. They will have a maximal value for every single computable run, but there is no limit on how large that value can become. The fact that a real computer will eventually run out of RAM is glossed over here; this is of course a limit for any physical computer, but it also is obvious and of no interest to the theoretical "computing power" of the machine. Also, we are not interested about how long it actually takes, at all. So our little machine can use arbitrary amounts of time and space, which makes it absolutely impractical.

# ... and beyond

One astounding last point, then, is that such a simple, simple thing can do *everything* any conceivable real computer could *ever*, in the whole universe, accomplish (just very much slower) - at least as far as we know today.
> 13 votes

# Answer
It's not tautological at all.

A model of computation is Turing-complete if it can simulate all Turing machines, i.e., it is at least as powerful as Turing machines.

One thing that Turing machines can do is simulate other Turing machines (via the universal Turing machine). That means that, if your model of computation can't simulate Turing machines, it can't do at least one thing that Turing machines can do, so it doesn't satisfy the definition, so it isn't Turing complete. There's no circularity because we didn't define Turing-completeness in terms of itself: we said that Turing-completeness is the property of being able to do everything that Turing machines can.

But there are plenty of other things that models of computation might fail to do. For example, no deterministic finite automaton (DFA) can recognize the class of strings consisting of some number of $a$s followed by the same number of $b$s. Turing machines, on the other hand, can recognize that class of strings. Hence, DFAs are not Turing-complete.

> Is there a way to define the capabilities of Turing Machine without just saying "being able to simulate another Turing Machine"?

I'm not sure what you mean by "define the capabilities of Turing machines". The capabilities are defined in terms of the finite state automaton operating on the infinite tape. (I'll not repeat the full definition but you can find it, e.g., on Wikipedia.)
> 39 votes

# Answer
Turing's model of computation is just one of many equivalent models of computation. It has the same power as Gödel's recursive functions and Church's lambda calculus, which were proposed around the same time, as well as other models such as the pointer machine. You can therefore state that

> A computer is Turing-complete if it can solve any problem that Excel can.

This works since Excel is also Turing-complete. I recommend taking a look at Wikipedia's page on the Church-Turing thesis, and at a survey paper of Blass and Gurevich, Algorithms: A Quest for Absolute Definitions.

---

Regarding your question, what can a Turing machine do that a non-Turing machine cannot, in general the answer unfortunately depends on the non-Turing machine.

It is possible, however, to define non-trivial notions of Turing-complete problems, for example:

> A language $L$ is Turing-complete if for every computable language $A$ there exists an "efficiently computable" function $f$ such that $a \in A$ iff $f(a) \in L$.

Under this definition, suitable encodings of the halting problem are Turing-complete, and so for a reasonable class of machines (depending on the definition of "efficiently computable"), the machine is Turing-complete iff it can realize some (equivalently, all) Turing-complete language.

There are many other Turing-complete problems captured by this formalism, depending on the definition of "efficiently computable", such as the Turing correspondence problem, and problems concerning Wang tiles and the Game of Life. Any of these problems can function as a benchmark instead of the halting problem.
> 16 votes

# Answer
First of all I wish to point out that the definition of Turing-completeness isn't tautological at all. Not only proving a computational model Turing-complete is an interesting result in itself, but it also allows you to immediately extend all the results from computability theory to this other computational model; for example: 2-counter machines are Turing-complete, Turing machines cannot solve the halting problem, therefore neither 2-counter machines can.

A simple characterization of the functions computable by a Turing machine is given by the $\mu$-recursive functions, the minimal set of functions closed under composition, primitive recursion and minimization operator that contains the constantly zero function, the identity and the successor function.

Such class incorporates those functions that are "intuitively computable", that is, which computation could be carried out by a human following a precise algorithm with pencil and paper.

Obviously "intuitively computable" isn't really a formal definition, the identification of "intuitively computable" with "Turing computable" is known as the Church-Turing thesis. Since many formal attempts to characterize computability ultimately converge to a computational model that is Turing-complete, although there will never be a formal proof of such an assertion in a mathematical sense, there are strong reasons to believe it.
> 4 votes

# Answer
A Turing machine has the can compute the same set of functions as a universal quantum computer, which can simulate any physical system:

https://www.cs.princeton.edu/courses/archive/fall04/cos576/papers/deutsch85.pdf

As such, a Turing machine is capable of doing any information processing allowed by the laws of physics, although it won't always do such processing as efficiently as possible.
> 0 votes

---
Tags: turing-machines, turing-completeness
---


# Question
Title: Help on the notation of the 2-bit operation: $\frac 12{(I+Z_1Z_0)}$
This was adapted from Quantum Mechanichs for Computer Scientists. On this equation, we have $I$ representing the identity operator, with $Z$ being defined for 1 bit as:

$$ Z|0⟩ = |0⟩, \quad Z|1⟩ = -|1⟩\\,.$$

The operation $\frac 12{(I+Z\_1Z\_0)}$ acts as the identity for the two-bit states $|00⟩$ and $|11⟩$ while returning $0$ for the states $|01\rangle$ or $|10\rangle$.

I'm assuming the operator addition is the linear algebra definition, but I can't understand the $\frac 12$ fraction and its effect on the operation.

Could you point me to what concept I am missing, so I can derive the resulting states of this operation?

# Answer
> 2 votes
The operation $I$ on two bits can be written as the identity matrix, $$ I = \begin{pmatrix} 1 & 0 & 0 &0 \\ 0 & 1 & 0 &0 \\ 0 & 0 & 1 &0 \\ 0 & 0 & 0 &1 \end{pmatrix}\\,. $$

The operation $Z\_0Z\_1$ that performs $Z$ on both qubits can be written as $$ Z\_0Z\_1 = \begin{pmatrix} 1 & 0 & 0 &0 \\ 0 & -1 & 0 &0 \\ 0 & 0 & -1 &0 \\ 0 & 0 & 0 & 1 \end{pmatrix}\\,. $$

Now, the operation that you ask about, $\frac12(I+Z\_0Z\_1)$ is simply the operation described by

$$ \frac12(I+Z\_0Z\_1) = \frac12 \begin{pmatrix} 1 & 0 & 0 &0 \\ 0 & 1 & 0 &0 \\ 0 & 0 & 1 &0 \\ 0 & 0 & 0 &1 \end{pmatrix} + \frac12 \begin{pmatrix} 1 & 0 & 0 &0 \\ 0 & -1 & 0 &0 \\ 0 & 0 & -1 &0 \\ 0 & 0 & 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 &0 \\ 0 & 0 & 0 &0 \\ 0 & 0 & 0 &0 \\ 0 & 0 & 0 &1 \end{pmatrix}\\,. $$ This indeed performs as you describe. If the $1/2$ wasn't there, we would get that $|0\rangle$ becomes $2|0\rangle$. Note that his operator is not unitary (it returns "$0$" for $|01\rangle$ and $|10\rangle$, which means the qubit "disappears", this shouldn't be allowed by quantum mechanics.)

# Answer
> 0 votes
The concept you're missing is simply that the operators are matrices.

---
Tags: quantum-computing, notation
---


title: Description of a TM

text:
# Question
Title: Description of a TM
What does it mean if I'm given a description of a TM? Does that mean, that since I'm given I know exactly what M will accept/reject/loop?

Not sure exactly of what to think

# Answer
> 1 votes
A *description of a TM* is the Turing machine encoded under some fixed formal encoding. Think of it like the "source code" for the Turing machine.

In particular, the only information given to you is the definition of the Turing machine. Its properties are up to you to find out.

---
Tags: turing-machines, automata
---


# Question
Title: How was multiprogramming brought into computer languages
I am going through the book operating system principles by Hansen . Hansen begins the third chapter on concurrent programming by discussing interleaving of the machine instructions of processes being run at the same time .

Then it begins with providing the language notation for multiprogramming and writes the following program whose purpose is to copy records from one sequence to another .

```
procedure copy (var f, g: sequence of T);
var s, t: T;
     completed: boolean;
begin
    if not empty(f)
    then
        begin
            completed:= false;
            get(s, f);
            repeat
                 t:= s;
                 cobegin
                       put(t, g);
                       if empty(f)
                       then
                            completed:= true
                       else
                            get(s, f);
                 coend
            until completed;
        end
 end

```

(If possible please tell me the name of the language ,was it Algol60 ?Anyways let's call it X )

All fine till here , a keyword or statement was introduced into the language X , which would perform multiprogramming. But I would like to know how was the language changed so as to incorporate this new keyword or function for multiprogramming . What changes were done to language X,owing to which X which was capable of supporting one execution at a time could now support more than one at a time ?

P.S : Hansen described about a single -user operating system called "Solo ".There he somehow means Pascal supports development of concurrent programs. The answer to the question in this post can be approximated by an answer to "what were the differences between languages which supported concurrent programs and those who didn't "?

I could have written "what are the differences" in the auxiliary question but I wanted to know how languages started having constructs for concurrent programming ,that's why I wrote "What were the differences".

# Answer
> 1 votes
If you're **really** interested in all that's needed, your best choice would be to look at the standardisation process of C++11 by the ISO Working Group on C++ (WG21). All the relevant papers are available online.

Keywords are *not* important at all. In fact, C++ defined just one new keyword (`thread_local`) and that's mostly for convenience.

What *is* important is the *memory model*. Programs work by altering state, which logically exists in memory. With multi-programming, there are concurrent changes to the state of a program. This requires a reasonably precise definition of said state. To make things more complex, you want a definition of state that is compatible not just with the abstract language definition, but which is also implementable on real hardware. That gets you into problems like registers and caches (state outside ordinary memory), the exact details of which vary significantly between real hardware architectures.

A key insight here is the *sequenced* concept. Two C++ operations can be *sequenced*, which means they cannot operate at the same time. This means they are allowed to use the same data in memory without risk. A special kind of sequencing is *sequenced before*, which means one operations happens before the other. This means a write *sequenced before* a read guarantees that the read sees the value of the write.

With C++11, there are library calls defined which can guarantee such sequencing across different threads of execution.

The comments of @rcgldr suggest that function calls like `WaitForSingleObject` alone are sufficient, but this isn't actually the case. You need an associated memory model. That's why you have Win32 macro's like `InterlockedIncrement` \- these macro's provide the mapping between the language memory model and the hardware memory model. There's no `Read(DWORD*)` macro, though - the language memory model is that aligned `DWORD` reads are atomic, and it's implicitly assumed that the compiler can efficiently map every read to atomic hardware instructions.

---
Tags: programming-languages, concurrency, history
---


title: Examples of Context Free Languages

text:
# Question
Title: Examples of Context Free Languages
I'm having a hard time thinking of context free languages. The only example I've been able to think of is $0^n1^n$, but I'm having a hard time thinking of any others. Can I get some examples?

# Answer
> 4 votes
Here are some of the examples of context free languages

* $\\{ w \in \\{0,1\\}^\*\mid \ w$ contains at least three ones }
* $\\{ w \in \\{0,1\\}^\*\mid \ w = w^{R}$ and $\mid w \mid $ is even }
* $\\{ w \in \\{0,1\\}^\*\mid \ $ the length of $w$ is odd and the middle symbol is $0$ }
* $\\{ a^{i} b^{j} c^{k} \mid \ i,j,k \ge 0 $ and $ i + j = k $ }
* $\\{ a^{i} b^{j} c^{k} \mid \ i,j,k \ge 0, $ and $ i = k $ or $i = k$ }
* $\phi$

**Reference :** https://web.njit.edu/~marvin/cs341/hw/hwsoln05.pdf

# Answer
> 1 votes
More general examples of context-free languages which are not regular are the Dyck languages of balanced parentheses of several types. A 1-type Dyck language contains words such as (), (()), ()(), and so on. A 2-type Dyck language contains words such as (\[\]), ()\[\], \[(\[()(\[\])\])\[\]\], and so on.

The Chomsky–Schützenberger representation theorem states that, in some sense, Dyck languages are the most general type of context-free languages.

---
Tags: context-free
---


# Question
Title: Making a grammar ambiguous by applying a morphism
I have an encoding of an unambiguous grammar $G$. Can I apply a morphism $σ$ so that the grammar becomes ambiguous?

I have no clear concepts about this, only the idea: "grammar $G$ is ambiguous if there's a string $x \in L(G)$ having two different leftmost derivations in $G$". I would like a good explanation and if it's possible, an example.

Morphism:

I will consider two alphabets, $Σ\_1$ and $Σ\_2$, where $\Sigma\_1$ is the terminal alphabet of $G$. A morphism is a function of the form $h\colon Σ\_1^\* \to Σ\_2^\*$ which satisfies: $h(xy)=h(x)h(y)$ for all $x,y \in \Sigma\_1^\*$. When applying the morphism to a grammar on $\Sigma\_1$, the result is a grammar on $\Sigma\_2$ (that is, the morphism is only applied to the terminals in $G$).

# Answer
The answer depends on the grammar $G$. If $G$ generates at most one word, then no morphism will make it ambiguous (prove!). If $G$ generates more than one word, then the morphism sending all characters to the empty string will make it ambiguous (why?).
> 0 votes

---
Tags: formal-languages, formal-grammars, ambiguity
---


# Question
Title: Unrestricted grammar to generate $a^{n^2}$
I have been asked to find a grammar that will generate the language $\\{a^{n^2}:n \ge0\\}$ in an exercise. So far I tried to replicate the previously written characters with my grammar rules but it didn't work. Any idea on how to setup such grammar? Any help will be appreciated.

# Answer
> 2 votes
Set aside $n$ of the $n^2$ characters, and use that $(n+1)^2 = n^2 + 2n +1$.

So at any moment we have (say) $n^2-n$ symbols $A$ and $n$ symbols $B$. We also need endmarkers. $L,R$ count as A$.

$S\to LBBR$

In one linear phase we visit all symbols, and each symbol $B$ will generate two extra $A$'s. Finally we add a $B$.

$L \to LX$; $XA\to AX$; $XB\to AABX$; $XR\to BR$

Nondeterministically end, transforming all symbols into $a$.

# Answer
> 2 votes
Found the answer here. Basically the grammar looks like this: $$ S→LAYR \\ ZA→aAZ \\ Za→aZ \\ ZR→AAYR \\ aY→Ya \\ AY→YA \\ LY→LZ \\ YR→X \\ aX→Xa \\ AX→Xa \\ LX→ε \\ $$

---
Tags: formal-grammars
---


title: The Height of subtree in Heap

text:
# Question
Title: The Height of subtree in Heap
In order to find the recurrence function of *The Height in Heap*, the following figure is drawn.

Question 1: How can we compute the height if Right subtree in form of *Log* in base 3, and why do we have the height of Left subtree as *log* in base 3/2?

Question 2: it is stated that:
**"for a complete binary tree to have the maximum height the last level should be half full."**
i don't grasp the logic behind this line.why?

# Answer
You are asking several question. I will only answer one. If you start with a set of size $n$ and you repeatedly reduce it to at most $rn$ elements, then after $t$ steps, you will have at most $r^tn$ elements. If $r^tn \< 1$, then after $t$ steps you will have no elements. This happens for $t \> \log\_{1/r} n$. This explains where $\log\_{3/2} n$ and $\log\_2 n$ come from.
> 1 votes

---
Tags: data-structures, binary-trees, discrete-mathematics, heaps
---


# Question
Title: What is a simple way of explaining what a linear boolean function means in boolean algebra and relating it to the standard definition of linearity?
I was reading notes on computability theory when I came across the term "Linearity" which I was not familiar with, in the context of boolean functions. I am quite comfortable what linear maps mean in Vector Spaces (say in the context of linear algebra and functional analysis) but I had never seen this term being used in the context of boolean functions. In those other contexts it roughly means the following equation is true:

$$ f(x+y) = f(x) + f(y) $$

however, when I went to wikipedia to find out what linearity means for boolean functions I came across a weird paragraph that seem to define it but didn't seem to have a clear succinct way to define linear functions or its relations to the more standard way of defining linearity.

Can someone explain to me how the definition from wikipedia relates to the more traditional way of defining linearity over Vector Spaces? In other words, why is the detailed definition on wikipedia the way it is?

---

For ease, here is wikipedia's definition:

> In Boolean algebra, a linear function is a function ${\displaystyle f}$ for which there exist $ {\displaystyle a\_{0},a\_{1},\ldots ,a\_{n}\in\\{0,1\\}} a\_0, a\_1, \ldots, a\_n \in \\{0,1\\} $ such that:
>
> $$ f(b\_1, \ldots, b\_n) = a\_0 \oplus (a\_1 \land b\_1) \oplus \cdots \oplus (a\_n \land b\_n), \text{ where } {\displaystyle b\_{1},\ldots ,b\_{n}\in \\{0,1\\}.} b\_1, \ldots, b\_n \in \\{0,1\\}. $$
>
> A Boolean function is linear if one of the following holds for the function's truth table:
>
> -\> In every row in which the truth value of the function is 'T', there are an odd number of 'T's assigned to the arguments and in every row in which the function is 'F' there is an even number of 'T's assigned to arguments. Specifically, f('F', 'F', ..., 'F') = 'F', and these functions correspond to linear maps over the Boolean vector space.
>
> -\> In every row in which the value of the function is 'T', there is an even number of 'T's assigned to the arguments of the function; and in every row in which the truth value of the function is 'F', there are an odd number of 'T's assigned to arguments. In this case, f('F', 'F', ..., 'F') = 'T'. Another way to express this is that each variable always makes a difference in the truth-value of the operation or it never makes a difference.

# Answer
> 3 votes
Linearity for boolean functions means *exactly* linearity over a vector space.

Consider the field $\mathbb{F}\_2$, i.e., the field with two elements $\\{0,1\\}$. Here the "addition" is addition modulo 2, i.e., exclusive xor (xor).

A vector space $V$ over this field is basically a vector of $n$ elements of $\mathbb{F}\_2$. The "sum" of two vectors $v+w$ is obtained by taking the component-wise "sum", i.e., the xor of these two vectors. In this way you can think of the space $\\{0,1\\}^n$ as a vector space over $\mathbb{F}\_2$: just identify $\\{0,1\\}^n$ as the set of $n$-vectors over $\mathbb{F}\_2$, so it becomes a $n$-dimensional vector space.

Now a boolean function $f:\\{0,1\\}^n\to \\{0,1\\}$ is considered linear iff it is a linear function from the vector space $\\{0,1\\}^n$ to the vector space $\\{0,1\\}$. This amounts to saying that

$$f(x\_1,\dots,x\_n) = c\_1 x\_1 \oplus c\_2 x\_2 \oplus \cdots \oplus c\_n x\_n.$$

Here $\oplus$ represents the xor operation.

Why is this equivalent to the usual definition over vector spaces? Recall from linear algebra that if $f:V \to W$ from vector space $V$ to vector space $W$, then it can be represented as multiplication by a $k \times \ell$ matrix, where $k = \dim V$ and $\ell = \dim W$. Here we have a map $f: \\{0,1\\}^n \to \\{0,1\\}$, and $\dim \\{0,1\\}^n = n$, so $f$ can be represented as multiplication by a $n \times 1$ matrix. Here everything is over the field $\mathbb{F}\_2$, so you have to replace the usual addition and multiplication with addition and multiplication modulo 2. Multiplication by the matrix $\[c\_1 c\_2 \cdots c\_n\]$ is equivalent to the definition above, so we obtain the equivalence.

**Caveat: linear vs affine.** If we have $f:V \to W$, a linear function is one that can be represented as

$$f(x) = Mx$$

where $M$ is some matrix. An affine function is one that can be represented as

$$f(x) = Mx+c$$

where $M$ is some matrix and $c$ is some vector. A linear function has the property that $f(x)+f(y)=f(x+y)$. An affine function does not; but it does satisfy the property that $f(x-y+z)=f(x)-f(y)+f(z)$.

Wikipedia's definition claims to be a definition of a linear function, but it's really a definition of an affine function. Sometimes people don't distinguish between linear vs affine (they consider both of them to be linear functions). That can be a bit confusing, especially if you're just learning these concepts. Unfortunately, Wikipedia seems to be one of those places that has lumped both concepts under the name "affine".

In your context, a boolean function $f:\\{0,1\\}^n\to \\{0,1\\}$ is affine iff it is a linear function from the vector space $\\{0,1\\}^n$ to the vector space $\\{0,1\\}$. This amounts to saying that

$$f(x\_1,\dots,x\_n) = c\_1 x\_1 \oplus c\_2 x\_2 \oplus \cdots \oplus c\_n x\_n \oplus c\_0.$$

The difference between linear vs affine is the extra constant term ($\oplus c\_0$) that can appear in an affine function. When Wikipedia provides its definition of a linear function, it is really providing a definition of an affine function. I guess that implicitly Wikipedia is using the word "linear" to include both concepts. Anyway, as long as you understand this little detail, all of the standard machinery of linear algebra applies.

See also https://en.wikipedia.org/wiki/Affine\_transformation#Over\_a\_finite\_field.

---
Tags: computability, boolean-algebra
---


title: Prove count without revealing data

text:
# Question
Title: Prove count without revealing data
Suppose I maintain a proprietary database and claim that it has N records. Before subscribing to my database a client wants a proof that the database is indeed this large. What theoretical protocol can I employ to prove my database size with possibly revealing only a small number of records?

# Answer
I think the usual way of doing this is that you hash each record (with a known cryptographically secure hash) and provide the client with $N$ hash values. The client chooses $k$ out of those hash values and you reply with the corresponding $k$ records. The client can then verify that the hash values match up correctly with the provided records plus whatever record validation they'd like to do. Note that if you have duplicate records in your DB, those duplicates could be inferred from provided hash values (e.g.: the client could get a pretty good estimate of the number of distinct records in your DB). If this is undesirable, then you can salt the hashes.
> 3 votes

---
Tags: cryptography, interactive-proof-systems
---


# Question
Title: New Idea for accessing memory across an inter-network connected system
I have the following idea for a network-based operating system.

Suppose we have two computers *A* and *B* in a network. If computer *B* wants to access the memory of computer *A*, it can access by using the following addressing method which uses Media Access Control (*MAC*) address of the machines,

```
(MAC Address of target machine).(memory address on target machine)

```

This should work both ways as well as all the computers connected in a network. This will also remove the constraint of passing reference of variables in Remote Procedure Call (*RPC*).

Is the above method feasible ? What sort of modifications are required to make this possible, if feasible ?

NOTE:-I am also assuming that there is no MAC spoofing.

# Answer
This would be an instance of a distributed shared memory architecture. There's been *lots* of research on such systems. I would recommend spending some quality time on Google Scholar to read relevant research papers on those kinds of systems, to learn about what's been tried so far.

You might also be interested in the literature on distributed in-memory databases, caches, and data stores.
> 1 votes

---
Tags: operating-systems, distributed-systems, computer-networks, memory-management, memory-access
---


# Question
Title: Asymptotic behavior of functions with not analytic expression
Is it in general acceptable by computer science community, if the run-time or space consumption of an algorithm is derived by experiment and not analytically?

For example let's say we have an algorithm for which it's running time is given by function $f(n)$, where $n$ is the size of the problem. There is no way to derive its asymptotic behaviour (respecting run time) analytically but only using numerical methods. In other words we have no analytical expression for $f(n)$ but we can probe it using specific values for $n$. Making some trials (trying a wide range of n) we see that run time follows for example very closely a line. Let's say that doing least square method we observe that $t= an+b$ is a good fit for the run time t of the problem (of size n). Good fit is a vague term, and I mean that residuals are within acceptable ranges.

So is it safe to say that the run time of this algorithm is $\Theta(n)$, at least in the range we made the trials? Moreover can we state that this algorithm is faster than another one whose asymptotic behavior is for example $O(n^2)$.

If the answer is negative, what other methods should I search for?

# Answer
> 3 votes
Is it *safe*? No, of course, it's not safe. There could always be ways that your experiments are misleading. Maybe the worst case wasn't triggered by your particular workload or in your particular experiments. Maybe there's a quadratic term with a small constant, which is negligible for the values of $n$ you tested in your experiments but becomes dominant for very large values of $n$. You can't rule out those possibilities with experiments.

Are the experiments *good enough*? That depends on the community, and for what purpose you want to use them, and what conclusions you want to support. Can you conclude that the worst-case running time, over all possible inputs, is linear? No. Can you conclude that for workloads that are likely to arise in practice, the running time appears to be linear? Perhaps. Is this enough to conclude that your system or your method has merit or is a significant contribution over the state of the art? Quite possibly.

There is no single answer about what is "acceptable". Instead, I suggest you take a broader, more nuanced view. Understand the strengths and limits of any method of analysis; understand what conclusions you can and can't support, using those methods; understand what claims you want to be able to make; understand the values of your audience nad the community you are targetting; and go from there.

# Answer
> 1 votes
It depends on which part of the computer science community your are aiming for as audience; the computer science community is not monolithic. Theoretical computer science is about *provable* facts, and won't care about your experiments. Other parts could be more accepting toward empirical results.

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


title: Decimal to Binary converter with a flaw

text:
# Question
Title: Decimal to Binary converter with a flaw
Hi I wrote the following recursive decimal to binary function while studying for Andela.

```
def binary_converter(q):
    if q>255 or not isinstance(q, int) or q<0:
        return "Invalid input"
    if q==0:
        return '0'
    elif q!=0:
        q, r = divmod(q, 2)
        return str(r)+binary_converter(q)

```

The code works for the most part, except I haven't figured out a way to get rid of any preceding zeros to the final result.

For example:

> > > binary\_converter(62) '0111110' That's 0111110 with a preceding 0.

How in the world do I get rid of it without breaking the code?

I've tried returning an empty string for the if condition but that breaks my ability to convert the decimal 0 to it's binary which is still 0.

Edit: Here's the working code, updated with D.W's answer

```
def binary_converter_for_realz(q):
    if q>255 or not isinstance(q, int) or q<0:
        return "Invalid input"
    if q==0:
        return ''
    elif q!=0:
        q, r = divmod(q, 2)
        return binary_converter_for_realz(q)+str(r)

def binary_converter(q):
    if q==0:
        return '0'
    else:
        return binary_converter_for_realz(q)

```

# Answer
> 1 votes
Change your code for `binary_converter()` to return the empty string (`''`) instead of `'0'`, when you pass it the input zero.

Then, write a new function `binary_converter_for_realz()`, which checks whether the input is zero; if passed zero, it just returns `'0'`, otherwise it invokes `binary_converter()` and returns whatever it returns.

This basically treats 0 as a special case, which it is: we don't want a leading zero, except when the integer is zero, in which case we do.

---
Tags: recursion
---


title: Proof of linear search?

text:
# Question
Title: Proof of linear search?
Consider the search problem:

> Input: A sequence of $n$ numbers $A=(a\_1, a\_2, \ldots , a\_n)$ and a value $v$.
>
> Output: An index $i$ such that $v = a\_i$ or the special value NIL if $v$ does not appear in $A$

Write pseudocode for linear search, which scans through the sequence, looking for $v$. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.

The algorithm is clearly very simple to prove. However, could someone prove the correctness of the algorithm using a loop invariant? Note the "three necessary properties" are:

* Initialization: It is true prior to the first iteration of the loop.
* Maintenance: If it is true before an iteration of the loop, it remains true before the
* Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.

# Answer
What about using a "goal" variable initialized to NIL and taking as invariant "After iteration i, the goal variable contains an index $0 \leq j \< i$ such that $A\[j\] = v$ if there exists one (in the range $\\{0, \cdots, i - 1\\}$), or NIL otherwise" ?
> 7 votes

# Answer
It's impossible to prove unless you state the algorithm. But, let's say your algorithm maintain a candidate index $j$ for loop iteration, which is update to $j \leftarrow j+1$, if $v\_j \neq v$, and if the loop termination depends on $j$ not updating or reaching $n$ and the output is $j$, then you could say that a valid loop invariant is $v\_i \neq v\_j$ for $1 \leq i \< j \le n $.
> 1 votes

# Answer
So the Initialization condition would be that v is not in our sub array which at the beginning we would consider to be empty.

Then maintenance would be that as we add elements v is not in our sub array still as if we find it we go to termination so we keep iterating if v is not there

The termination would be if we find v or if we reach the end of the array here the meaning full out put is either the index of v or that the counter equals the size of the array From what I gather
> 0 votes

---
Tags: proof-techniques, correctness-proof, loop-invariants
---


# Question
Title: Class of Algorithms where finding output of algorithm can be aided by output of same algorithm given a similar input
Sorry for the confusing title, but I'm trying to find out if a certain algorithm or class of algorithms fits this description. Given an algorithm `A`, computing `A(x)` can be computionally easier if `A(g)` is known, where `g` is close to `x`, and it's easier the closer `g` gets to `x`. So also, the amount of computation `A` has to do grows with respect to the size of the input.

You would also have to be able to calculate the output of `A(x)` given `A(g)`, `x-g`, `A(x-g)`. Does `A` exist for anything other than trivial artithemtic, and if so, is there an entire class of algorithms which `A` belongs to?

# Answer
> 1 votes
It can be algorithms which use initial guess, for example algorithms for finding roots and local minimums/maximum like Newton's method and gradient descend. Here `g` and `x` are functions, and `g` is close to `x` means that they have roots or local minimums/maximums in similar locations, so taking `A(g)` as initial guess, algorithm can converge faster to `A(x)`.

# Answer
> 1 votes
In complexity theory, a problem $A$ is called *self-reducible*, if a $A(x)$ can be computed easily when given the solutions to one or more subproblems $A(x')$ for inputs with $|x'| \< |x|$ for free. What "easily" means depends on the context, in most cases it means "in polynomial time" in the context where $A$ is $\mathsf{NP}$-complete.

The standard example is $SAT$, where the problem of satisfiability of a formula $\varphi$ reduces to the same problem for the two formulas $\varphi\[x:=0\]$ and $\varphi\[x:=1\]$, which are smaller than $\varphi$ after simpification.

---
Tags: algorithms, complexity-theory
---


# Question
Title: Comparing the complexity of algorithms for listing k-cliques
Chiba and Nishizeki showed that it is possible to list all $k$-cliques (cliques on $k$ nodes) in time $O(m \cdot a^{k-2})$ where a is the arboricity of the graph and $m$ the number of edges in the graph. http://www.ecei.tohoku.ac.jp/alg/nishizeki/sub/j/DVD/PDF\_J/J053.pdf

We have designed an algorithm that can do it in time $O(m \cdot \frac{(2a)^{k-2}}{(k-2)!})$.
In practice, on real-world graphs (which have a small arboricity), our algorithm performs much better than the one of Chiba and Nishizeki. We now want to show through theory that it is better.
So the question is, how can we show that $O(m \cdot \frac{(2a)^{k-2}}{(k-2)!})$ is better than $O(m \cdot a^{k-2})$?
Note that we are interested in instances of small $k$, say 10 or less. Is the big O notation relevant here? Or should we work with upper bounds and lower bounds on the number of operations (quantifying the constants in the big O)?

# Answer
$O(m \cdot \frac{(2a)^{k-2}}{(k-2)!})$ is not necessarily better than $O(m \cdot a^{k-2})$, since the big-oh notation $O$ is an upper bound. To compare the two algorithms, you'd better analyze using the $\Theta$ notation. In addition, note that if you set $k$ to some fixed value, terms such as $\frac{2^{k-2}}{(k-2)!}$ are considered to be constants and thus omitted in asymptotic analysis.
> 1 votes

# Answer
I do not think that the big-oh notation is relevant in my case. As I'm interested in the running time when $a$ and $k$ are small, I will upper bound and lower bound the number of operations as a function of $m$, $k$ and $a$ without using the big-oh notation.
> 0 votes

---
Tags: graphs, time-complexity, parameterized-complexity
---


# Question
Title: How to find the number of discrete states possible by current computers?
In his famous article, "Computing Machinery and Intelligence", Allan Turing talks about discrete-state machines and the largeness of the number of states provided by that time "state-of-the-art" machine, "Manchester Machine", which he states is about 2^165,000. Link to the article

Well, that was 1950's. I'm trying to compare it with modern day computers and get an average number of states for a usual commercial machine. How can I find it?

Is it related to memory size (Turing calculates it by the number of "stores", or sheets of paper available)? If so, would this make the number of states tend to infinity due to the current possibility of writing/erasing memory at will?

# Answer
> 1 votes
Acording to the suggestions that were given in the comments to the question, the number of distinct discrete states possible by a machine are related to the size the machine's of memory (or "stores" space, using Turing's nomenclature).

Since a bit has two distinct discrete states, a byte then have $$ 2^{2^3}=2^8 $$ discrete states.

Two bytes, $$2^{2\*2^3}=2^{16}$$

Hence, a commercial availabe 4GB DDR3 RAM machine would roughtly be $$ 2^{2^2\*2^{30}\*2^3} =2^{2^{35}}=2^{34,359,738,368} $$

Further, today's (March 2017) world fastest computer, Sunway TaihuLight, with more than 1 PB memory, would have rougthlty $$ 2^{2^{50}\*2^3}=2^{53}=2^{9,007,199,254,740,992}$$ distinct discrete states.

Correct math if wrong, but the idea is this, taking in account only main memory (disregarding cpu registers, secondary memory and cache, as j\_random\_hacker stated that could be done).

---
Tags: discrete-mathematics
---


# Question
Title: Calculating force between n points placed on the x-axis
There are $n$ charges placed on the x-axis at points $1,2,3,\dots,n$. We need to calculate the force on each charge by every other charge. I need the exact force. Charges can be arbitrary. Inputs are the charges possibly in the form of an array. Force is defined in the usual physical way.

I know an $O(n^2)$ algorithm to do the task. However, it can be done in $O(n\log n)$.

I have read about FFT, but I don't know how to apply it here. I know that we can multiply two degree $n$ polynomials in $O(n\log n)$. This problem is similar to that problem. Any help will be appreciated.

# Answer
> 3 votes
Suppose that the charges are $q\_1,\ldots,q\_n$. You need to calculate, for all $i$, $$ F\_i = q\_i \sum\_{j\>i} \frac{q\_j}{(i-j)^2} - q\_i \sum\_{j\<i} \frac{q\_j}{(i-j)^2}. $$ In matrix form, we get $$ \begin{bmatrix} F\_1/q\_1 \\ F\_2/q\_2 \\ \vdots \\ F\_n/q\_n \end{bmatrix} = \begin{bmatrix} 0 & 1 & \frac{1}{4} & \frac{1}{9} & \cdots & \frac{1}{(n-1)^2} \\ -1 & 0 & 1 & \frac{1}{4} & \cdots & \frac{1}{(n-2)^2} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ \frac{-1}{(n-1)^2} & \frac{-1}{(n-2)^2} & \frac{-1}{(n-3)^2} & \frac{-1}{(n-4)^2} & \cdots & 0 \end{bmatrix} \begin{bmatrix} q\_1 \\ q\_2 \\ \vdots \\ q\_n \end{bmatrix} $$ What the FFT allows us to do is to quickly multiply by a circulant matrix. In order to obtain a circulant matrix, all you have to do is add $n-1$ dummy coordinates: $$ \begin{bmatrix} F\_1/q\_1 \\ F\_2/q\_2 \\ \vdots \\ F\_n/q\_n \\ \ast \\ \vdots \\ \ast \end{bmatrix} = \begin{bmatrix} 0 & 1 & \frac{1}{4} & \frac{1}{9} & \cdots & \frac{1}{(n-1)^2} & \frac{-1}{(n-1)^2} & \cdots & -1 \\ -1 & 0 & 1 & \frac{1}{4} & \cdots & \frac{1}{(n-2)^2} & \frac{1}{(n-1)^2} & \cdots & \frac{-1}{4} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ \frac{-1}{(n-1)^2} & \frac{-1}{(n-2)^2} & \frac{-1}{(n-3)^2} & \frac{-1}{(n-4)^2} & \cdots & 0 & 1 & \cdots & \frac{1}{(n-1)^2} \\ \frac{1}{(n-1)^2} & \frac{-1}{(n-1)^2} & \frac{-1}{(n-2)^2} & \frac{-1}{(n-3)^2} & \cdots & -1 & 0 & \cdots & \frac{1}{(n-2)^2} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ 1 & \frac{1}{4} & \frac{1}{9} & \frac{1}{16} & \cdots & \frac{-1}{(n-1)^2} & \frac{-1}{(n-2)^2} & \cdots & 0 \end{bmatrix} \begin{bmatrix} q\_1 \\ q\_2 \\ \vdots \\ q\_n \\ 0 \\ \vdots \\ 0 \end{bmatrix} $$ We don't really care about the $n-1$ asterisked entries. The new matrix is $(2n-1)\times(2n-1)$, and so FFT still runs in $O(n\log n)$. Of course, if your FFT works only for powers of 2, you need an extra padding step.

---
Tags: algorithms, fourier-transform
---


# Question
Title: How may an algorithm always color optimally connected bipartite graphs?
Let's consider a greedy algorithm for the coloration problem called the **Dsatur algorithm**, designed by Daniel Brélaz in 1979 at the EPFL, Switzerland.. This algorithm is based on an order of vertices which we can obtain from considering the saturation degree of each vertex $v$ from $G$. The saturation degree of a vertex $v$ , which we can write as $DSAT(v)$, is the number of color, the number of different colors used in $v$ neighborhood. The idea is to color first the vertices with a saturation degree high enough to avoid using too many colors.

```
Data : an undirected (*non-orienté*) connected graph $G=(V,E)$.
Output : all vertices of $G$ colored.

SORT the vertices by decreasing order of degrees.
COLOR a vertex of maximum degree with color 1.
While it exists vertices not colored do
  CHOOSEa vertex $v$ with max DSAT
  COLOR $v$ with the smallest possible color
  UPDATE DSAT for all neighbors of v

```

**How to show that DATSUR Algorithm always color optimally connected bipartite graphs ?**

### My attempt

I think I have to prove it by the absurd :

* As far as it is a conected graph it can't be colored by one color solely.
* If there were three colors returned by the algorithm Dsatur, taht would mean that a vertex would return $Dsatur(v)= 2$ (it exists two neighbors with two different colors). Which is impossible. **But why ?**

That would mean that it gives three kind of different colors... But I don't know how to show why this is impossible... Can you help me ?

# Answer
> 2 votes
You can prove an even stronger claim. Consider the following algorithm:

> Let $v\_1,\ldots,v\_n$ be an ordering of the vertices such that for $i\>1$, each $v\_i$ is connected to at least one of $v\_1,\ldots,v\_{i-1}$.
>
> Go over all vertices $v\_1,\ldots,v\_n$ in order, and color each one with the smallest available color.

This algorithm also uses (at most) two colors to color a connected bipartite graph. The property of the ordering that I highlight, which is satisfied by the ordering produced by the Dsatur algorithm, suffices to guarantee that the algorithm uses the minimal number of colors.

To prove that this algorithm works for a connected bipartite graph with bipartition $V\_1 \cup V\_2$, where $v\_1 \in V\_1$, prove by induction that if $v\_i \in V\_j$ then $v\_i$ gets colored $j$.

---
Tags: algorithms, graphs, algorithm-analysis, colorings
---


# Question
Title: An algorithm to generate possible binary grid patterns
This is my first question in this forum. I hope you will help me.

I was asked by a colleague to solve this puzzle. The puzzle goes like this:

I have an `m x n` grid where each cell can be in either of two states: **on** or **off**.

Initially the cells are in **off** state. I would like to have an algorithm that takes an integer input, `l`, and the grid, and gives me all the possible grid patterns where each pattern must have at least one **off-block**, where an **off-block** is a block of `l` contiguous cells all in **off** state.

**Constraints**:

1. There should not be a cell in an **off** state either before or after an **off-block**.
2. The **off-block** can be found not only in the vertical and horizontal orientation but also in the diagonal orientation.

The values of `m` and `n` can be as large as 32 and `l` is typically between 3 and 10 and it cannot be greater than either `m` or `n`.

**Examples**

Let's assume we have a `4 x 4` grid, let `l` be 3, `0` denote the **off** state and `1` denote the **on** state.

**Some valid patterns**

`|---|---|---|---|
 | 0 | 0 | 1 | 0 |
 | 0 | 1 | 0 | 0 |
 | 0 | 0 | 0 | 1 |
 | 1 | 1 | 0 | 0 |
 |---|---|---|---|` has 3 **off-blocks**

`|---|---|---|---|
 | 1 | 0 | 1 | 0 |
 | 1 | 0 | 1 | 1 |
 | 1 | 1 | 0 | 1 |
 | 1 | 1 | 0 | 0 |
 |---|---|---|---|` has 1 **off-block**

**Some invalid patterns**

`|---|---|---|---|
 | 0 | 0 | 1 | 0 |
 | 0 | 0 | 0 | 1 |
 | 0 | 0 | 0 | 1 |
 | 1 | 1 | 0 | 0 |
 |---|---|---|---|` The main diagonal contains 4 (more than 3) contiguous cells in **off** state.

`|---|---|---|---|
 | 1 | 0 | 1 | 0 |
 | 1 | 0 | 1 | 1 |
 | 1 | 1 | 0 | 1 |
 | 1 | 1 | 0 | 1 |
 |---|---|---|---|` Must contain at least one **off-block**

**My approaches**

These are what I have come up so far:

**First approach: Brute force**

My first approach was to list all the possible grid patterns and check each one of them if it satisfies the constraints. I immediately realized that this is not scalable. For instance, for a `4 x 4` grid I will have 2^16 possible grid patterns.

**Second approach:** After each **off-block**, turn **on** the next cell. This procedure is repeated both in the horizontal and the vertical orientations.

Take for instance a `6 x 6` grid, let `l` be 3.

Initially, this is the grid:

`|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 |
|---|---|---|---|---|---|`

Starting from the first row, turn **on** the the cell after each **off-block** along the **horizontal** orientation of each row and we get the following pattern:

`|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 | 0 |
|---|---|---|---|---|---|`

Starting from the first column of the above grid, turn **on** the the cell after each **off-block** along the **vertical** orientation of each column and we get the following pattern:

`|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 |
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 | 0 |
|---|---|---|---|---|---|`

With this approach I can satisfy the first constraint. In order to get the other patterns I need to turn **on** the remaining **off** cells. The only option that I see is to adapt a brute force to deal with the remaining cells.

Moreover, turning a cell **on** may permit turning a neighbouring cell **off**, resulting in a valid new pattern. For example from the following pattern where `l` is 2

`|---|---|---|---|
| 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 |
| 0 | 0 | 1 | 0 |
|---|---|---|---|`

we can get the pattern below by turning **on** the cell at coordinate(1,1) and turning **off** the cell at coordinate(2,2)

`|---|---|---|---|
| 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 |
|---|---|---|---|`

Therefore, even with the second approach I cannot gaurantee to produce all the possible patterns.

I hope the above the description is self-contained to understand the problem.

Thank you

# Answer
> 1 votes
You want the set of grids that contains at least one contiguous off-block.

There is a simple iterative algorithm for this. Enumerate the set of all locations and all orientations for the off-block. For each such, fill in the grid with that off-block, and fill in the two squares on either end of the off-block per your first constraint; then the rest of the squares can be filled in arbitrarily, so enumerate all possibilities for them.

There will be exponentially many such filled-in grids, so this procedure will be computationally infeasible for all but the smallest grids. Moreover, *every procedure* that correctly solves this problem will be computationally infeasible: the output (list of valid solutions) is exponentially long, so it will take exponentially long just to construct that output. No amount of cleverness or algorithmic tricks will let you avoid this. It is an inherent consequence of the problem statement. The problem is simply not solvable (within any reasonable amount of time), except for small grids.

# Answer
> 0 votes
For an off-on matrix $M$, let $\ell(M)$ be the maximum contiguous run (horizontally, vertically, or diagonally, in both diagonal orientations) of off cells. You seem to be asking for the list of all $n\times m$ off-on matrices $M$ with $\ell(M) = \ell$.

One way to generate this list is using the following recursive procedure, which gets as input a *partially filled* off-on matrix $M$:

* If $M$ is complete filled, output it if $\ell(M) = \ell$.
* Otherwise, locate the first unfilled cell in $M$, set it on, and run the procedure recursively.
* Set the same cell to off, and check whether this introduces a contiguous run of off cells of length $\ell+1$. If it doesn't, run the procedure recursively.

Implementing the second step requires an ordering of the cells in the matrix. One possibility is to order the cells top to bottom and left to right.

You run the entire procedure with the empty matrix as input, and then it prints all legal matrices.

In practice I expect this procedure to be quite efficient, since (1) it seems that most of the time a choice which doesn't lead to an immediate run corresponds to a partially filled matrix which can be completed to a legal completely filled matrix, and (2) it seems that most matrices with $\ell(M) \leq \ell$ actually satisfy $\ell(M) = \ell$.

You can test this empirically by comparing the number of generated matrices to the number of recursive calls (divided by $nm$).

---
Tags: algorithms
---


# Question
Title: Adjacency matrix and recognizing hierarchy?
I'm currently learning about graphs and I have some questions regarding adjacency matrices. Given an arbitrary adjacency matrix:

Is there any way to tell if that matrix represents a hierarchal graph structure? Obviously in the above case it's not.

Something like:

I know the rows of and `i x i` adjacency matrix represent the out-degree of `i`th vertex and columns represent the in-degree of the `i`th vertex. But is there any way to tell just by looking at the general structure of the adjacency matrix if the graph is hierarchical (At least, for smaller matrices as above) ?

# Answer
By definition you can check if a graph is a tree (regardless of its representation) with these facts:

1. The graph does not have cycles.
2. It only has a single connected component.

The first condition can be checked with a simple DFS checking if there is a back edge. The connected components can be counted using either DFS or BFS.

Regarding to an adjacency matrix, every tree is a bipartite graph. See this, but keep in mind that proving that a a graph is bipartite does not mean it is a tree.
> 1 votes

---
Tags: graphs, adjacency-matrix
---


title: basic turing machine

text:
# Question
Title: basic turing machine
I'm trying to create a TM that changes all $a$'s to $b$'s and all $b$'s to $a$'s in a given string and then halts on the first blank space it encounters. What I have is:

$$ \langle q\_1,a,b,q\_1\rangle \\ \langle q\_1,b,R,q\_2 \rangle \\ \langle q\_2,a,L,q\_1 \rangle \\ \langle q\_2,b,a,q\_2 \rangle \\ $$

I'm new to Turing machines, so I'm wondering if it makes sense to convert $a$'s to $b$'s and then send $b$'s into a different state; is there a sort of temporal sequencing here that will send the $q\_1$-manufactured $b$'s (former $a$'s) into $q\_2$ as well? If so, how can you get around this problem to construct a suitable machine?

# Answer
Using your convention that the machine EITHER changes symbol OR moves Left/Right, then this is the machine you are looking for:

```
<q1,a,b,q2>
<q1,b,a,q2>
<q2,a,R,q1>
<q2,b,R,q1>

```

In other words, the machine alternates between the 'switch the letter' state and the 'move right' state. *\[I am adopting the convention that the absence of a transition - say on space - is equivalent to halting; otherwise one needs another transition to cover that\]*
> 1 votes

# Answer
I'm unfamiliar with your notation but this is what i came up with given your problem.

---

Edit: **Explanation**

Given a Truing Mashine is a tuple:

> M = (Q, Σ, Γ, δ, q0, qacc, qrej),

Where:

> * Q is the finite set of states,
> * Σ is the finite input alphabet,
> * Γ ⊇ Σ is the finite tape alphabet (we assume ⊳,⊲ ∈ Γ)
> * δ : (Q − {qacc,qrej}) × (Γ∪ {⊳,⊲}) → Q × (Γ∪ {⊳,⊲}) × {L,R} is the transition function
> * q0 ∈ Q is the start state (q0 != qacc and q0 != qrej),
> * qacc ∈ Q is the accept state
> * qrej ∈ Q is the reject state (qrej != qacc)

**Interpretation of transition function:**

> δ( q, a) = (q', b, ∆)

**When in state q and reading the symbol a on the tape the machine:**

* Moves to state q'
* Writes the symbol b on initial tape position.
* Moves the tape one position to the direction ∆(L~left,R~Right)

The notations of the transitions in the picture are actually wrong, should be: a,

> b/R -\> **a/b,R** b, a/R -\> **b/a,R** ⊲, ⊲/R -\> **⊲/⊲,L**
>
> Where ⊲ is the tape symbol for the end of the tape.

And

> Where ⊳ is the tape symbol for the beginning of the tape.

Where `a/b,R` means:

> * Read input symbol a
> * Write b in it's place
> * Move tape right

Where `b/a,R` means:

> * Read input symbol b
> * Write a in it's place
> * Move tape right

Where `⊲/⊲,R` means:

> * Read input symbol ⊲
> * Write ⊲ in it's place
> * Move tape left
> 0 votes

---
Tags: turing-machines, logic
---


# Question
Title: Estimating the run time of a program according to a given CPU performance
When we have a recurrence relation of a program, as an example:

```
 T(N) = N log N + 9N + 55

```

and the CPU capability let's say (10^6) or any other number. What is the formula or the method to estimate the run time (in second) if we run a program represented by a function of N, and a given N "inputs"?

# Answer
> 0 votes
If you determined that the runtime of your code, on a certain computer, is T(N) = N log N + 9N + 55 microseconds, then that equation determines the runtime. Just substitute N into that equation.

---
Tags: algorithms, performance, mathematical-analysis
---


# Question
Title: Find pairs of integers (a, b) in an array such that a = b + k in linear time - elements are not unique
A while ago, I was asked to solve a question similar to this:

> *We are given an array* `arr` *and we would like to find all pairs of items* `(a, b)` *where* `a = b + k`. The items are **NOT** unique and it is also possible to have `k = 0`.

I know that if items are unique, this problem can be solved in linear time by using a hashmap. However, when items are **NOT** unique, I think that the problem becomes very different.

See this example:

```
arr = [1, 1, 1, 1, 1]
k = 0

```

The expected output is:

```
(1, 1), (1, 1), (1, 1), (1, 1) // For the first element
(1, 1), (1, 1), (1, 1)         // For the second element
(1, 1), (1, 1)                 // For the third element
(1, 1)                         // For the fourth element

```

As it is obvious to me, in the worst case (the above example) the output is of size $n \choose 2$, which is $\Theta (n^2)$. How is it possible to have a linear algorithm, when the output size is definitely $\Theta (n^2)$?

My interviewer insisted that it is possible to still solve it in linear time, *if the correct data structure is used*.

# Answer
If you must write out all of the pairs individually, then the overall problem takes quadratic time because the running time of this last post-processing step is $O(n^2)$.

If you are allowed to represent the output in a different way, then you can simply keep track of distinct pairs and associate them with a counter (see run-length encoding). Thus, you can compute the solution in $O(n)$ time using the following algorithm:

1. Initialize an auxiliary array (or hash map) $Aux$.
2. Perform a first linear scan of the input array $Arr$ and use the auxiliary array to keep track of how many times each of the elements appears. For example, $Aux\[2\]=3$ indicates that $2$ appears $3$ times in $Arr$.
3. Perform a second linear scan of the input array $Arr$. During the $i$th iteration, $a=Arr\[i\]$ and you must look for the element $b =a-k$, which appears $c =Aux\[b\]$ times in $Arr$. If $c \gt 0$, then you will add the pair $(a,b)$ to your solution, associated with the count $c$. Two special cases that must be considered at step 3:

* If the pair already exists in your solution, you can simply increment the existing counter by $c$.
    * If $k=0$, you must add the pair $(a,b)$ only if $c \gt 1$. The counter associated with this pair will not be set to (or incremented by) $c$, but, rather, by $c-x-1$, where $x$ stores how many times we have seen $a$ before.
> 1 votes

---
Tags: algorithms, time-complexity, runtime-analysis, search-algorithms, arrays
---


# Question
Title: if $f(n)$ is defined in the domain [0,1] then what $f(n) = O(1/n)$ actually means?
We know that $f(n) \in O(g(n))$ notation means shortly, that $f(n) \leq cg(n)$ for $n\>n\_o$ where n and c are some positive constants. And actually it gives the behavior of $f$ as $n$ goes to infinity.

But in the case $f(n) \in O(\frac{1}{n})$ where n is at most 1, shouldn't be more intuitive to say that the behavior of $f$ as $n$ goes to zero (and not to infinity) is $\frac{1}{n}$?

For example if $f$ gives the space consumption of an algorithm, then $f \in O(\frac{1}{n^2})$ is a lot better from $f \in O(\frac{1}{n})$ if we allow n\>1. But if for any reason algorithm is restricted in the range $n \in \[0,1\]$ then we would like $f$ resembles $\frac{1}{n}$ and not $\frac{1}{n^2}$.

To make things even weirder suppose that $f(n) \leq \frac{1}{n}+\frac{1}{n^2}$. For n\>1 the dominant term is the $\frac{1}{n}$ and someone could easily say that $f(n) \in O(1/n)$. But if we restrict $n$ to be in $\[0,1\]$, the dominant term is the $\frac{1}{n^2}$. In that case is it right to say $f\in O(\frac{1}{n^2})$?

# Answer
> 1 votes
In this context it is clear that big O is taken as $n\to0$, rather than $n\to\infty$ as is more usual for us. For a function $f(x)$ defined on $(0,1)$, we say that $f(x) = O(1/x)$ if there exists a constant $C\>0$ such that $f(x) \< C/x$ (or, depending on the exact definition, $|f(x)| \< C/x$.

This definition is by and large equivalent to the more usual definition which states that $f(x) = O(1/x)$ if there exist two constants $x\_0 \in (0,1)$ and $C\>0$ such that $f(x) \< C/x$ for all $x \leq x\_0$.

If you are confused, note that $f(x) = O(1/x)$ under these definitions iff $g(n) = O(n)$ under the usual definition, where $g(n) = f(1/n)$.

For $n$ in this range, we usually use symbols like $\epsilon$ or $\delta$ to emphasize that we are taking the asymptotics as the variable tends to 0 rather than as the variable tends to infinity.

---
Tags: asymptotics
---


# Question
Title: Algorithm to find out the number of times a number occurs consecutively in an array in a range specified
I have an array say

```
8 3 5 4 4 4 4 4 3 2 7 11 12 7 7 7 7 1 2

```

total =17 elements now you are given a range say \[2,11\] both included ,now you have o find out the element that has occurred the max number of times and the number of times it has occurred

A simple traversing through the array in the range and keeping the track of the each element is one solution but time complexity is O(N) and if we are given N queries time complexity = O(N^2). Any faster algo than this ?

# Answer
> -1 votes
Define a sub problem solution as the range of longest sub series. If there are more than one we solution is 2 at most. The once at the tips of the range. and there are exactly (n^2-n)/2 sub problems here. You can solve each sub problem in o(n).

If you were to remember the results of problems you solved. You can remember all in o(n\*(n^2-n)/2) and it's fine.

But, If you consider Dynamic programming. There is a bottom up series to solve each sub problem in o(1) time.

when trying to solve(i,j) two cases are to consider:

the range is at the tip. so consider increasing the result. the range is at the tip. just return the longest. again up to 2 ranges.

---
Tags: arrays
---


# Question
Title: Proving the loop invariant for a simple program in Hoare logic
I was studying loop invariant and came across Tomas Petricek's example. Here's the equivalent(I believe) program after I revised it a bit for proof in Hoare logic:

```
j = 9;
i = 0;
while (i < 10)
{
    i = i + 1;
    j = j - 1;
}

```

The loop invariant given by Petricek is i + j == 9, which makes sense to me. And the pre-condition and post-condition, seems to me, is (|T|) and (|i = 10 and j = -1|), respectively. Here's my attempt:

```
(| T |)
(| eta[j/9][i/0] |) Implied
  i = 0;
(| eta[j/9] |) Assignment
  j = 9;
(| eta |) Assignment
  while (i < 10)
  {
    (| eta and i < 10|)
    (| eta[j/j-1][i/i+1] |) Implied
      i = i + 1;
    (| eta[j/j-1] |) Assignment
      j = j - 1;
    (| eta |) Assignment
  }
(| eta and not i < 10 |) While
(| i = 10 and j = -1 |) Implied

```

For the three Implied rule, with eta being i + j = 9, the first two are straightforward to me:

```
|- T => 0 + 9 = 9
|- i + j = 9 and i < 10 => i+1 + j-1 = 9

```

But I can't see how do I get from `i + j = 9 and not i < 10` to `i = 10 and j = -1`. Am I setting the wrong post-condition? I could get `j <= -1` trivially, but I don't think that's how it should work, right?

I thought that, without setting j to 9 and i to 0 in first two line, what this while loop does is to set i to 10 and j to j-(10-i). In that case, if we set the initially value of i to 0 and j to 9, j would be set to 9-(10-0) = -1, which is what I intended. I'm not sure what went wrong in my reasoning. May I have a hint? Thanks!

# Answer
> 4 votes
Your invariant, together with the negation of the loop condition, is not strong enough to imply your postcondition. Try adding an additional conjunct to the invariant which, together with $\neg\ i\<10$, implies $i=10$ (the $j=-1$ part then follows from $i+j=9$).

---
Tags: hoare-logic, loop-invariants, check-my-answer
---


# Question
Title: Are there any types of distributed databases which allows untrusted peers, like Blockchain?
Are there any types of distributed databases which allows untrusted peers, like Blockchain? If it exist, can I look its whitepapers and/or implementations?

# Answer
> 3 votes
Distributed Hash Tables (DHT) are key value stores that work in a P2P manner, which is basically a database. There are implementations that don't rely on trust between peers. Obviously this can only be achieved by strong replication and consensus on the current value to a given key. So you face similar problems as with a blockchain.

The Wikipedia Article https://en.wikipedia.org/wiki/Distributed\_hash\_table will give you a good overview. Chord and Tapestry are probably the most famous DHT concepts.

If you want to look at applications instead The DHT approach is mostly used in peer-to-peer file hosting and file sharing.

There might also be other distributed databases or database-like concepts out there. This is just one I know.

---
Tags: distributed-systems, databases
---


# Question
Title: How to prove equivalence relation in this case?
I am working on $\lambda$-terms and trying to prove the $=$ is an equivalence relation on $\lambda$-terms. My problem is proving reflexive relation.

$\frac{}{\theta \vdash x = x}$

$\frac{ \theta,x \\# N, y \\# M \vdash M = \[y := x\]N } { \theta \vdash \texttt{$\lambda x.M$ $=$ $\lambda y.N$} } $

$\frac{\theta \vdash M\_1 = M\_2 \quad N\_1 = N\_2 } { \theta \vdash \texttt{$M\_1 \\, N\_1$ $=$ $M\_2 \\,N\_2$} }$

I put two restrictions on such $\lambda$-terms.First, bound variables are distinct. For example, there are no two terms such as $\lambda x.M$ and $\lambda x.N$. Second, multiple bindings of a variable is not allowed. For example, $\lambda x. \lambda x.M$ should be written as $\lambda y. \lambda x.M$. To sum up, every bound variable should be distinct. $\[y := x\]N$ means variable $x$ replaces variable $y$ in term $N$. $x \\# N$ means $x$ does not occur in $N$. $\theta$ is a set of $\\#$. Also, $\alpha$-equivalence is assumed for the terms. For example, $\lambda x.x = \lambda y.y$

I tried to prove that the $=$ shown in above rules is an equivalence relation on such terms.

For equivalence relation, I have to prove the following three relations.

reflexive: $\theta \vdash M=M$.

symmetric : $\theta \vdash M=N$ implies $\theta \vdash N=M$.

transitive: $\theta \vdash M=N$ and $\theta \vdash N=P$ implies $\theta \vdash M=P$.

The proof of reflexive relation is the following.

when $M$ is a variable such as $x$, then $x = x$.

when $M$ is an application such as $M\_1 \\,N\_1$), then I have $M\_1 \\,N\_1$ = $M\_1 \\,N\_1$, so it is true.

when $M$ is an abstraction such as $\lambda x.M$, from $\lambda x.M = \lambda x.M$, I have $ x \\# M \vdash | M=\[x:=x\]M $, which is not true becuase $x \in M$. Also, as I said, there are no two terms such as $\lambda x.M$ and $\lambda x.M$, so I cannot show $M=M$ for an abstraction.

Since $\alpha$-equivalence is assumed for terms. I assume that $M=\lambda x.M\_1 =\lambda y.M\_2$. Therefore, I will have $x \\# M\_2, y \\# M\_2 \vdash M\_1=\[y:=x\]M\_2$? is this the right way to prove reflexivity?

I would appreciate your kind help.

# Answer
> 3 votes
I will only prove reflexivity $A=A$. We proceed by induction on the structure of $A$.

If $A\equiv x$, then $x=x$ follows from rule 1.

If $A\equiv \lambda x. M$, then by induction hypothesis we can assume $M=M$ is provable. Now, take any $y$ not free in $M$. We have $M \equiv \[y:=x\]\[x:=y\]M$ by construction. Let $N \equiv \[x:=y\]M$. Rule two states

$$ \dfrac{ x\\# N, y\\# M \vdash M=\[y:=x\]N }{ \vdash \lambda x.M = \lambda y.N } $$

We indeed have $x\\# N$, since the $x$ variable was renamed as $y$ in $N \equiv \[x:=y\]N$. We also have $y\\# M$ by our choice of $y$. Induction hypothesis states $M=M$, which is $M=\[y:=x\]N$. Hence, the conclusion of the rule holds, which is $\lambda x. M = \lambda y. \[x:=y\]M$. If terms are identified up-to $\alpha$, then this equality is the same as $\lambda x.M = \lambda x.M$.

If $A=MN$, the induction hypotheses and rule 3 suffice.

---
Tags: proof-techniques, lambda-calculus
---


# Question
Title: How does one implement Dijkstra while skipping an edge
Like let’s say you find the shortest path, but you want to find an alternate path as well. In order to do that, you have to ignore each edge in the shortest path one at a time, and then find the shortest path without using that respective edge. At that point you have a set of alternate paths, of which you want to select the one that is the shortest yet also different enough.

But I don’t know how to find the alternate paths while skipping edges. Could anyone please clear this up

# Answer
Check out Yen's Algorithm for finding the K-shortest paths using any shortest path algorithm. The link provided uses Dijkstra's algorithm as an example
> 3 votes

# Answer
I think you already answered yourself. You should remove an edge each time from your graph, that belongs to the original shortest path and rerun the Dijkstra for the new graph and original source and destination vertices. At the end of an iteration you should restore the previously deleted edge and remove the next one from the original path. Iterate till you reach the destination vertex.

I don't know what do you mean different enough. If you delete an edge from the original path then the new shortest path could be vary from almost identical to completely different path.
> 0 votes

---
Tags: algorithms
---


# Question
Title: Differences between the OS and DB buffer pool?
How does the DB manage a pool of buffers when the operating system ends up controlling what's really in memory? For example, couldn't the operating system decide to evict a page frame from a DB's buffer?

# Answer
Yes, absolutely, that could happen, and it makes it harder for databases to optimize their own performance.

Some databases bypass the operating system's virtual memory management and manage memory themselves. They might request that the operating system pin a range of the address space into memory (and never page it out). Or, they might be designed to be the only application that runs on the machine, and take care of their own memory management so they never use too much memory -- hoping that this will make it unlikely that the OS ever pages out any of their data.
> 1 votes

---
Tags: databases
---


title: Stuck on a combinations algo question

text:
# Question
Title: Stuck on a combinations algo question
There are **x** digits and **y** boxes where **y** is between 1 and x inclusive. I have to print all the possible digits in boxes (combinations) in any order.

For examples, if **x = 5** and **y = 2** we can have the following 4 combinations:

```
1234 5
123 45
12 345
1 2345

```

Similarly if **x = 5** and **y = 3**

```
123 4 5
12 34 5
12 3 45
1 234 5
1 23 45
1 2 345

```

if **x = 5** and **y = 5** then there is only 1 combination

```
1 2 3 4 5

```

Both x and y are variable and I can't figure out even a brute force way of doing this. I have tried using three nested `for` loops but have no luck.

# Answer
> 2 votes
You can print numbers 1 to $x$ and print $y-1$ spaces between them in a brute force manner. The following algorithm does that:

```
function enumerate(string str, int s, int t, int y):
   /* base case: there is no space left and we print the string */
   if (y==0)
      string str2 = "";
      for i=s to t:
         str2.append(i);
       print str+str2;
       return ;

   /* recursive case: add one space and recursively call the function */
   for i=s to t:
      string str2 = "";
      for j=s to i-1:
         str2.append(j);
      str2.append("~");
      if (t-i >= y-1) call enumerate(str+str2, i, t, y-1);

```

You can call `enumerate(str="", s=1, t=5, y=2)` to print all combinations of numbers 1 to 5 and 2 spaces between them, which gives you a sorted embedding of numbers 1 to 5 in **3** boxes.

# Answer
> 2 votes
Expanding on orezvani's hint:

If you have `x` balls and `y` boxes, how many balls can you put in the first box?

* If there is only one box, you have to put all the balls in it.
* Otherwise, you must leave at least `y - 1` to be able to put one in each of the other boxes.

However many you choose, you will be left with a similar problem. Cue recursive function ...

---
Tags: algorithms
---


title: Reduction between parametrized problems

text:
# Question
Title: Reduction between parametrized problems
Can we construct reduction from $k$-sum to $l$-clique or vice versa where $k$ and $l$ are some fixed integers?

That is given two parametrized problems whose unparametrized version is $NP$-complete when can we construct reductions between them?

In general NP complete problems the reductions are polynomial time.

What is the corresponding analogue in parametrized problems?

# Answer
You are asking two questions, I will answer the second. Parameterized reduction from problem $P$ to $Q$ is a function $\phi$ with the following properties :

* $\phi(x)$ can be computed in time $f (k)·|x|^{O(1)}$, where $k$ is the parameter of $x$,
* $\phi(x)$ is a yes-instance of $Q$ if and only if $x$ is a yes-instance of $P$.
* If $k$ is the parameter of $x$ and $k′$ is the parameter of $\phi(x)$, then $k′ ≤ g(k)$ for some function $g$.

> Note that $f(k)$ need not to be a polynomial function in $k$, it could be like $2^k$ or $c^k$, where $c$ is constant.

Example: INDEPENDENT-SET instance $(G,K)$ into CLIQUE instance $(G',K)$ is a parameterized reduction. You can verify all three conditions mentioned above.

**Reference :** http://www.cs.bme.hu/~dmarx/papers/marx-warsaw-fpt3
> 1 votes

---
Tags: complexity-theory, parameterized-complexity
---


# Question
Title: Algorithm - How to show Big O for 2 functions
I believe that Ln(n) is \<= 2^(sqrt(2\*lg(n))), so I am trying to prove it

I know that you can show Big O by showing Little O, so I am trying to take the limit as n approaches infinity of Ln(n)/2^(sqrt(2\*lg(n)))

However I am finding it hard to prove this using the limit definition

I would appreciate any help to see how to solve this! Thanks

# Answer
Interpreting `lg(n)` as `log2(n)`, set `n=2^x` so that the inequality transforms to

```
ln(2)*x <= 2^sqrt(2*x)

```

Now apply the square root,

```
sqrt(2*ln(2)) * sqrt(x/2) <= 2^sqrt(x/2)

```

and we are left to prove that for `y>0`

```
2^y/y > sqrt(2*ln(2))

```

Indeed, the minimum of the left side can be found for `0=ln(2)*y-1` or `y=1/ln(2)` with minimum value `2^(1/ln(2))*ln(2)`. Numerically, the gap between `1.88416938536372` and `1.1774100225154747` is large enough to exclude any floating point errors. Thus all the equivalent inequalities including the original one are true.
> 0 votes

---
Tags: asymptotics
---


# Question
Title: Algorithm for finding connected components checking as few edges as possible
Is there a good algorithm to find connected components in undirected graphs with at the lowest possible costs given as the total weight of the edges being checked?

# Answer
> 2 votes
You are looking for the minimum spanning tree for each connected component.

---
Tags: graphs, weighted-graphs, connected
---


# Question
Title: When a NPDA is constructed from CFG, how many internal states will be used for accepting any string from the grammar?
> Options given were:
>
> (a) 2 (b) 3 (c) 4 (d) 5

This question was a part of my assignment. I think the answer is 2 **internal states - one start state and the other end state/acceptance state**, but I am not sure whether it is correct or not. Please correct me if I am wrong. Thanks.

# Answer
The answer depends.

For every CFG we can construct an equivalent PDA with *empty stack acceptance* that has just a **single** state.

The construction is mentioned in wikipedia. We have single state $1$. For every grammar production $(A\to \alpha)$ add an pda instruction "expand" $(1,\epsilon,A,1,\alpha)$ which means "pop $A$ and push $\alpha$ without reading input". Additionally we have "match" instructions $(1,a,a,1,\epsilon)$ which means "when symbol $a$ is on top of the stack, we must read it from the input, while popping it from the stack". The initial stack symbol is $S$, the axiom of the grammar.

If we instead want *final state acceptance* then we need to distinguish a final state, so it is necessary to use **two** states.

Use a new initial stack symbol $Z$ to mark the bottom of the stack. Just add two instructions, one to push $S$ on the stack $(1,\epsilon,Z,1,SZ)$, the other to move to the accepting state $f$ when the empty stack is reached $(1,\epsilon,Z,f,\epsilon)$.

This however assumes the automaton model that I was brought up with. Certain books do not agree, and consider PDA that start with an empty stack (*brrr*). In that case an additional state is used to start and push $Z$ onto the stack, so we need **three** states.
> 2 votes

---
Tags: formal-languages, automata, context-free, pushdown-automata, nondeterminism
---


title: cannot construct the infinite type

text:
# Question
Title: cannot construct the infinite type
I am trying to learn haskell and could not configure it out, why following code snippet can not get compiled:

```
*Uncurry> applyTwice f x = f f x

<interactive>:14:20: error:
    • Occurs check: cannot construct the infinite type:
        t ~ t -> t2 -> t1
    • In the first argument of ‘f’, namely ‘f’
      In the expression: f f x
      In an equation for ‘applyTwice’: applyTwice f x = f f x
    • Relevant bindings include
        x :: t2 (bound at <interactive>:14:14)
        f :: t -> t2 -> t1 (bound at <interactive>:14:12)
        applyTwice :: (t -> t2 -> t1) -> t2 -> t1
          (bound at <interactive>:14:1)

```

This would be fine:

```
applyTwice f x = f (f x)

```

In haskell function application is left associative, the first code snippet would be apply like:

```
(f f) x

```

why `(f f) x` it is wrong?

# Answer
> 2 votes
Okay, let's look at what we know about the type of applyTwice, $\alpha$:

* It is given two arguments, so $\alpha = \beta\_1 \to \beta\_2 \to \gamma$, and $f$ has type $\beta\\\_1$ and $x$ has type $\beta\_2$
* $f$ is applied to $f$, so $\beta\_1 = \beta\_1 \to \gamma\_2$
* $(f\ f)$ is applied to $x$, so $\gamma\_2 = \beta\_2 \to \gamma$

The kicker here is the second equation, $\beta\_1 = \beta\_1 \to \gamma\_2$. This equation has no finite solution, because $S \to T$ is structurally larger (uses at least one more type constructor) than either $S$ or $T$.

So the only type that satisfies this equation is infinite recursive type $\mu T\ldotp T \to \gamma\_2 = ((\ldots \to \gamma\\\_2) \to \gamma\\\_2) \to \gamma\\\_2) \to \gamma\\\_2) \to \gamma\\\_2) \to \gamma\\\_2)$. But this type doesn't really have any meaning in Haskell or related type systems, and it's pretty hard represent an infinite type in finite memory in a concrete form.

Remember that $f\ f$ is giving $f$ as an argument to $f$. If you want to apply $f$ twice, you could use function composition `(f . f) x`, or $(f \circ f)\ x$ in math notation.

---
Tags: reductions, computer-algebra
---


# Question
Title: Why a separate ALU is needed, since any integer can be represented as floating point numbers?
Most of the operations in computers are using floating-point arithmetic, and why a Floating Point Unit alone is not sufficient? Can we do away with ALU? Is FP operations are resource-intensive alone be the reason for this, over the advantages provided by FP operations?

# Answer
> 3 votes
Any 64 bit integer can be represented as an 80 bit IEEE 754 extended precision floating point numbers. Many processors (PowerPC and POWER, ARM) don't support extended precision floating point, so there is your first argument gone. They can't represent *every* integer number as a floating point number.

Most operations on integers can be done *very cheaply* with integers represented in an integer format, but are much more expensive if you try to implement them with numbers in a floating point format. That will reduce your clock speed and at the same time raise energy consumption, costing you battery life on any portable device.

---
Tags: computer-architecture, floating-point
---


# Question
Title: Algorithm for maximizing correspondence between 2 sets
I am trying to figure out how to solve the following problem: I have 2 sets of objects, set A and set B. I have a metric that calculates how closely a given object from set A corresponds to an object from set B. I'd like to maximize the overall correspondence of the entire set.

What I tried first was a sort of greedy algorithm, where I went through each object in set A and calculated that object's correspondence with each object remaining in set B. I then replaced the object in set B that had the highest correspondence with the object in set A. For the next object in set A, I did the same thing, leaving out the objects in set B that already had a correspondence.

The problem with this approach is that it works very well for the first part of the sets, but as I near the end, there are fewer objects in set B to match with, so objects from set A tend to have worse correspondence with those objects.

I think that it might be better to do a full calculation of the correspondence of each item in Set A to each item in Set B, and from there choose each item from set A that has the highest correspondence of the next item in set B.

However, I'm left wondering if you could have a situation where, for example, object 1 from set A has, let's say an 95% correspondence to object 6 in set B, but it's next best correspondence is only 50% with object 14 in set B. Meanwhile, object 2 from set A has a correspondence of 97% to object 6 from set B, but it has a 96% correspondence to object 28 in set B. In my mind, I think it would be better for object 1 from set A to be matched with object 6 from set B (95% correspondence) and object 2 from set A to be matched with object 28 (96% correspondence) in set B instead of matching object 2 in set A to object 6 in set B and object 1 in set A to match object 14 in set B.

Is there a name for such an algorithm? I feel like it's related to the Knapsack Problem, but is not exactly the same. There will always be the same number of objects in set A and set B. I suppose it's possible that there will be more than 1 set of mappings that are "most optimal". In that case, I don't care which one is chosen.

In my application there will be between a few hundred to 10 or 20 thousand objects in each set. The average will probably be around 5,000 or so.

# Answer
This is known as the assignment problem. There are polynomial-time algorithms for it.
> 2 votes

---
Tags: algorithms
---


title: Algorithms for generating brick walls

text:
# Question
Title: Algorithms for generating brick walls
I'm not sure which StackExchange community is the correct place to ask this so I'm trying this one.

I want to write a code that generates random brick wall type textures. Similarly to what, for example, this commercial software does: http://www.vizpark.com/shop/walls-and-tiles/ .

So far I've thought at least three types of brick wall textures I would like to generate: 1) Periodic and user-defined pattern with one or more predefined brick types (bricks can be different shape an size). This is the simplest case. 2) Completely random pattern with predefined brick types 3) Completely random pattern with random sized bricks.

This is pretty much a mathematical problem that could be rephrased as: what is the way to fill a predefined area with certain shapes (either random or predefined) without leaving gaps?

I would assume that people have thought about this type or problems before, but I don't know how to search for it. I'm not looking for a conclusive answer, but would appreciate links to articles, etc. discussing different variations of this or related problems.

# Answer
I would like to comment this, but reputation...

What you are looking for is a Tessellation.

> A tessellation of a flat surface is the tiling of a plane using one or more geometric shapes, called tiles, with no overlaps and no gaps.

For example, the Penrose Tiling, the Pithagorean Tiling, Domino Tiling or Polyomino Tiling.
> 4 votes

---
Tags: algorithms
---


# Question
Title: if $ b(x) <f(x) \leq g(x)$ where $b, g \in \Theta(x)$ can we state $f(x) \in \Theta(x)?$
I restate the question: if $ b(x) \<f(x) \leq g(x)$ where $b, g \in \Theta(x)$ can we state $f(x) \in \Theta(x)?$ notice that $b(x)\< f(x)$ and not $b(x) \leq f(x)$. In other words what if

$f(x) \in \omega(b(x)) $ and

$f(x) \in O(g(x))$

can we state $f(x) \in \Theta(x)$?

# Answer
b(x) is between $c\_1·x$ and $c\_2·x$ if x is large. g (x) is between $d\_1·x$ and $d\_2·x$ if x is large. So f (x) is between $c\_1·x$ and $d\_2·x$ if x is large, which makes it $\Theta(x)$.
> 1 votes

# Answer
If $ \phi(x) \le \psi(x)$, then $\psi \space \epsilon \space \Omega(\phi)$, so $\Omega(\psi) \space \subseteq \space \Omega(\phi)$.

---

Since $b(x) \le f(x) \le g(x)$, then $\Omega(g) \space \subseteq \space \Omega(f) \space \subseteq \space \Omega(b)$.

And $\Omega(g) \space = \Omega(b)$, so $\Omega(g) \space = \space \Omega(f) \space = \space \Omega(b)$.

Similarly, $\Omega(b) \space = \space \Omega(f) \space = \space \Omega(g)$.

So $\Theta(b) \space = \space \Theta(f) \space = \space \Theta(g)$.
> 0 votes

# Answer
This is much simpler if you use words instead of mathematical stenography:

You have two functions, $b$ and $g$, which draw their values from set $\Theta$. You know that the value of $b$ is always smaller than the value of $g$. Now if you have another function $f$, the values of which are always between the values of $b$ and $g$, $f$ must draw its value from a subset of $\Theta$. Thus, $f(x)\in\Theta$.
> 0 votes

---
Tags: asymptotics
---


title: $2^1 + 2^2 + \cdots + 2^8$ in binary

text:
# Question
Title: $2^1 + 2^2 + \cdots + 2^8$ in binary
Maybe these are silly question. I know almost nothing about computer science, so please let me know in the comment section if I should edit anything or delete it.

1. Let's say I have a function that randomly selects 8 choices of 0 or 1. Would it be written as one byte together? For example, if all choices came out as 1, would it be written as 11111111?
2. Also, let's say another function can select the amount of choices. Any between 1 and 8 choices of either 0 or 1. As an example, if 3 choices were selected and all came out as 1, will it be written as 111? If so, how will the program know when to go to the next function in the case that every function had to select between 1 and 8 choices of 0 or 1?

# Answer
> 1 votes
In the binary system (much like in all numbering systems), order has meaning. If you write $0110$ this means $0\times2^3+1\times2^2+1\times2^1+0\times2^0$. Similarly, $11111111$ means $1\times2^7+1\times2^6+1\times2^5+1\times2^4+1\times2^3+1\times2^2+1\times2^1+1\times2^0=255$.

Now, assuming you had a function that produced a random bit as output, you would have 8 distinct bits if you called that function 8 times, which would form no kind of greater structure (that is, you would have e.g., 8 ones, but they would not mean 255 because they are not in an ordered structure, it's just 8 disjoint pieces of data).

On the other hand, if your function randomly selects the values of 8 bits and returns them, you would just have an array (or vector) of bits, which also do not represent a number.

In that sense, you can have the function output any number of bits you want. If you want two bits, you get 11 or 01 or 00 or 10, if you want three bits you get 111 or 000 or 100 or 010 or 001 or 110 or 101 or 011 etc. Note that in the way that you have phrased the question, these would not actually translate into numbers.

---
Tags: encoding-scheme, number-formats
---


title: Playing to win strategy algorithm

text:
# Question
Title: Playing to win strategy algorithm
Here is the game's setup:

> You're given a formula for a binary expression using and or not as the connectives. The connectives are combining many variables for which two players will assign truth values to them in the order specified beforehand.
> For Example:

```
formula: ((x and y) or ((y and z) or (not y and not z)))
turns: AAB
variables: xyz

```

> In this example Player A will assign a truth to x first, then y, then Player B will assign a truth to z. (The variables will always show up in the order of appearance in the formula).
> After all of the truth values are assigned to each variable, the formula is evaluated and the truth is returned and a winner is declared. Player A is trying to make it False and B is trying to make it True.

Assume that the other player and will always choose the best value for his variable on all of his turns. If there is no way for a player to make the formula win during his turn, or if choosing either true or false would lead to winning, then false is returned if it is player A’s turn, and true is returned if it is player B’s turn.

Our job is to give the best move for the current turn given a formula the previous moves and the order of moves for the game.

What would the strategy for approaching something this look like? I know this is a homework question but I've spent a week trying to figure this out without any avail. If you need further clarification about the problem as I know it's a big pill to swallow just comment below I'll be sure to reply.

EDIT: For further clarification, variables can show up more than once in the formula

# Answer
Your game is equivalent to the PSPACE-complete problem TQBF. The quantified Boolean formula corresponding to your example is $$ \forall x \forall y \exists z (x \land y) \lor (y \land z) \lor (\lnot y \land \lnot z). $$ Since it is PSPACE-complete, in particular it is NP-hard, and you there is no efficient general way to find out who wins in this game.

There is an exponential time strategy which involves constructing the game tree. While this strategy is feasible when the number of variables is small (like in your example), it is not practical when there are many variables.
> 3 votes

---
Tags: algorithms, evaluation-strategies
---


# Question
Title: Graphs with chromatic number $(\chi(G) \ge 3 )$ other than odd cycle (Triangle free)
Chromatic number denoted by $\chi(G)$ of graph $G$ is the minimum number of colours required to properly colour the given graph.

For ODD Cycle chromatic number is 3 and it does not contain triangle as a subgraph. I thought about complete , star, wheel graphs etc, but they don't satisfy the conditions.

I am looking for examples of graphs of $\chi(G)$ $\ge 3$, **but does not contain a triangle or odd cycle as subgraph**.

# Answer
> 3 votes
If a graph contains no odd cycle then it is bipartite and so 2-colorable.

---
Tags: graphs
---


# Question
Title: Is P = NP when solutions length is polynomially bounded by instance length?
I'm currently reading the book "*P, NP, and NP-Completeness*" by Oded Goldreich. I'm currently reading a chapter that's concerned with the "search version" of the P-vs-NP-problem, that is if finding solutions is harder than checking the validity of solutions.

First, the book defines "polynomially bounded relations" as relations (between problem instances `x` and their solutions `y`) where there exists some polynomial `p` such that the length of the solution is polynomially bounded by the length of the related problem instance (that is `|y| <= p(|x|)`).

Both the search problem as well as the checking problem are then defined on such bounded relations.

Now I wonder: Doesn't polynomially bounding the length of possible solutions to a given instance mean that there are only polynomially many possible solution candidates, which, when given an algorithm `C` that checks a solution for its validity in polynomial time, implies that finding a solution can also be done in polynomial time by simply checking each of the possible solutions for its validity?

**This would mean that if I can efficiently check solutions of a problem for validity, then I can also efficiently find solutions to that problem. (So, basically P = NP)**

Is this conclusion - when only looking at polynomially bounded relations - true? (The book of course says that it's not. If I'd need to bet I'd also bet on the book and not on me...)

If not, **where is the error in my reasoning?**

# Answer
You ask

> Doesn't polynomially bounding the length of possible solutions to a given instance mean that there are only polynomially many possible solution candidates?

In fact, the number of binary strings of length $n^c$ is $2^{n^c}$, which is exponential in $n$.
> 2 votes

# Answer
Consider a 3-SAT formula over $n$ variables and you can see that number of possible solution candidates is $\Omega(2^n)$, where as the size of each solution is polynomially bounded in the input size.
> 1 votes

---
Tags: complexity-theory, p-vs-np, search-problem
---


title: CFG for a rather complex language

text:
# Question
Title: CFG for a rather complex language
I'm trying to construct a context free grammar for the language $\\{a^ib^j:2i\neq3j+1\\}$. I found that when $j$ is even, there are no problems. When $j$ is odd, there are some constraints on $i$. Now these are some examples of words that may NOT be parsed by the CFG:

* aab
* aaaaabbb (5 a's and 3 b's)
* aaaaaaaabbbbb (8 a's and 5 b's)
* ...

But I'm completely stuck on finding a CFG for this language. Are there any tips that might help me in finding CFG's for a more complex language? I'm able to find the CFG for simpler languages, but I find this one particularly hard.

# Answer
> 1 votes
Try constructing CFGs for the two related languages $$ \\{a^ib^j : 2i \> 3j + 1\\}, \quad \\{a^ib^j : 2i \< 3j+1\\}. $$ This can be accomplished by constructing a grammar for $$ \\{a^ib^j : 2i = 3j + 1\\} $$ and some related languages.

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


# Question
Title: Is there any demonstrably uncomputable concrete problem which does not rely on diagonalization?
So diagonalization as we all know is an extremely productive way of showing uncomputability, the other main tool used by CS people for this task being reduction.

But it has occurred to me that I do not know a single uncomputable problem whose demonstration of uncomputability does not rely on diagonalization or reduction to a problem which relies on diagonalization.

Is there any example out there?

# Answer
there appear to be "no known examples" of undecidable problems that are not proven through "diagonalization" (precisely formalized), or more strongly, apparently *diagonalization is the only way of showing uncomputability.* in fact diagonalization, formalized, is an even more general property than undecidability, because exactly the same "mechanism" is behind other key mathematical proofs namely Godels theorem and the uncountability of the reals. this is revealed in the Lawvere fixed point formalism/ theorem.\[1\]\[2\]

maybe inadvertently, your question is also related or nearly equivalent to the Church-Turing thesis in some subtle or direct ways. the thesis is, roughly, that anything computable is computable by a Turing machine. therefore, equivalently, anything that is not computable is not computable by a Turing machine and all uncomputable Turing languages are reducible to the halting problem and vice versa.

the idea that there exist computations not captured by TMs is considered at best speculative and at worst verging on a "generally not credible" idea by the majority of computer scientists; see eg summary/ "debunking" by Fortnow which also cites several published/ peer reviewed counterclaims.\[3\] a more recent survey on applicability of Turing machine model and "hypercomputation" etc can be found in \[4\]

\[1\] Halting problem, uncomputable sets: common mathematical proof? / cstheory.se

\[2\] Lawvere, F. William. Diagonal Arguments and Cartesian Closed Categories. Lecture Notes in Mathematics, 92 (1969), 134-145

\[3\] UBIQUITY SYMPOSIUM 'WHAT IS COMPUTATION?' THE ENDURING LEGACY OF THE TURING MACHINE / Fortnow

\[4\] Turing's Titanic Machine? / Cooper, communications ACM
> 2 votes

---
Tags: computability, halting-problem
---