title: Computer graphics: Linear Interpolation

text:
# Question
Title: Computer graphics: Linear Interpolation
I have two vector points $p\_1$ and $p\_2$. Each point has a color value $c\_1$ and $c\_2$. Now using *linear interpolation*, I would like to get the color value at point $p\_3$.

Concrete example:

$\qquad \displaystyle p\_1 = (1, 3) \text{ with } c\_1 = (2, 4, 1)$
$\qquad \displaystyle p\_2 = (4, 4) \text{ with } c\_2 = (3, 1, 2)$

What color does $p\_3 = (2,3)$ have?

# Answer
Normally in graphics, you interpolate values across a line like so:

Point $A$ has value $V\_A$ and point $B$ has value $V\_B$, then you want to blend the value/color linearly between them as $C$ moves between $A$ and $B$. To do this, you first calculate the ratio (or percentage) of how far $C$ lies across the line $\overline {AB}$. This is equal to $\overline{AC}$ over $\overline {AB}$. Thus the ratio is calculated as follows:

$$ t=\frac {(C-A)}{(B-A)} $$

Once you have this ratio, you can use it to find the interpolated value between $V\_A$ and $V\_B$, since they should have the same ratio.

$$ t=\frac {V\_C - V\_A}{V\_B - V\_A} $$

The unknown variable here is $V\_C$, so solving for $V\_C$:

$$ (V\_B - V\_A)t=V\_C-V\_A\\ V\_C=(V\_B - V\_A)t+V\_A $$

However, this assumes that point $C$ lies on the line $\overline {AB}$. If it is not on the line, then you can't really "interpolate" in this way without some additional definition of *what* you want to interpolate. For example, if $C$ lies far below the line, then you can't really compare $\overline {AC}$ to $\overline {AB}$ like this; the ratio can be greater than 1, even though $C$ is "in between" them. So in your example, point $(2,3)$ is off the line. You have many possible variants.

**For instance:**

* You can interpolate between the distances of $\overline {AC}$ and ${BC}$. You would thus create a new straight line, $\overline {ACB}$ (even though in the graph it would be an angle) and do the above interpolation on that.
* You can interpolate a particular color to a dimension. For example, you take the values $A\_x$, $B\_x$ and $C\_x$, and interpolate $\overline {A\_xC\_x}$ over $\overline {A\_xC\_xB\_x}$, and use that for Red, then use $y$ for Green etc. However this works better for 3 dimensions, where each dimension can correlate to a color.
> 4 votes

# Answer
Not sure what you mean, but here is an idea.

First you have to express $p\_3$ as a linear combination of $p\_1$ and $p\_2$. This can be done by solving a linear system say

$$ \lambda p\_1 +\mu p\_2 =p\_3. $$

In your case you want to solve $$ \begin{align} \lambda + 4\mu &= 2 \\ 3\lambda + 4\mu &= 3 \end{align}. $$

Then you use the parameters $\lambda$ and $\mu$ to compute $c\_3$ by $$c\_3=\lambda c\_1 +\mu c\_2.$$
> 1 votes

---
Tags: graphics
---


# Question
Title: Can $f$ be not computable even if $L$ is decidable?
I am trying to teach myself computability theory with a textbook. According to my book, a function $f$ over an alphabet $A=\\{a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z\\}$ is only computable iff the language

$$ L = \\{s\\#^j\sigma : s\in A^\*, \sigma \in A, \text{ the }j\text{'th symbol of } f(s)\text{ is } \sigma\\}$$

is decidable. Why is that? Couldn't a function $f$ be not computable even if $L$ is decidable?

# Answer
If $L$ is decidable then you can use it's decider to compute $f$: for the first symbol of $f(s)$ run the decider on the input $s\\#x$ for any $x\in A$. For **one** of them, the decider will answer *YES*--this is the first letter in $f(s)$.

Continue doing this (e.g., for the second letter, decide if $s\\#\\#x \in L$, etc.), and reveal $f(s)$ letter-by-letter until the time where the decider answers *NO* for all $x\in A$, which means you reached the end of $f(s)$.

So if $L$ is decidable, $f$ is computable. Conversely, if $f$ is not computable, it can't be that $L$ is decidable.
> 6 votes

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


title: Runtime of the binary-GCD state machine

text:
# Question
Title: Runtime of the binary-GCD state machine
I am doing self study from MIT OCW exercises and I could not understand this question.

> The following rules define the *binary-GCD state machine* working on states in $\mathbb{N}^3$ with start state $(a,b,1)$ for $a\>b\>0$. If multiple rules apply, smaller numbers have precedence.
>
> Provided $\min(x,y) \>0$, then $(x,y,e) \to $
>
> 1. $(1,0,ex)$ if $x=y$
> 2. $(1,0,e)$ if $y=1$
> 3. $(x/2,y/2,2e)$ if $2|x \land 2|y$
> 4. $(y,x,e)$ if $y\>x$
> 5. $(x,y/2,e)$ if $2|y$
> 6. $(x/2,y,e)$ if $2|x$
> 7. $(x-y,y,e)$ otherwise

The binary-GCD state machine computes the GCD of $a$ and $b$ using only division by $2$ and subtraction, which makes it run very efficiently on hardware that uses binary representation of numbers. In practice, it runs more quickly than the Euclidean algorithm state machine.

Each execution of a command (one of rules 1-7 according to algorithm) is a transition and the current state $(x,y,e)$ is stored in registers $A,B,E$. At first the values in the registers $a,b,1$

Here is the question I am having trouble with:

> Prove that the machine reaches a final state in at most $3+2\log(\max(a,b))$ transitions.
>
> **Hint:** Strong induction on $\max(a,b)$

* First, why does this state machine assume it halves the $\max(a,b)$ at every two transitions beacuse we can apply rule 4 and 7 and one extra rule to halve the $\max(a,b)$, which is more than two transitions/steps. I know it is not a common case but a case is a case unless proved.
* Next I don't see where an extra 3 comes from in $3+2\log(\max(a,b))$.

# Answer
> 1 votes
Unless I've done this example wrong, this question is asking you to prove something that isn't true. Consider $(x,y) = (381,192) = (3\cdot 127,3\cdot 64)$. What happens when you run the algorithm?

> $(3\cdot127,3\cdot 64,1) \rightarrow (3\cdot127,3\cdot 32,1) \rightarrow \ldots \rightarrow (3\cdot 127,3,1)$
> $ (3\cdot 127,3,1) \rightarrow (3\cdot 126,3,1) \rightarrow (3\cdot 63,3,1) \rightarrow \ldots \rightarrow (3,3,1) $
> $ (3,3,1) \rightarrow (1,0,3) $

So starting with $( 3\cdot (2^k -1), 3 \cdot 2^{k-1}, 1)$, the first set of steps applies the 5th rule $k-1$ times, resulting in $(3 \cdot (2^k-1), 3, 1)$. We then alternately apply the 7th rule and the 6th rule. Each time we do this, we go from $(3\cdot (2^j-1),3,1)$ to $(3\cdot (2^{j-1}-1),3,1)$, until we reach $(3\cdot(2^1-1),3,1)$. This takes $2(k-1)$ transitions. Finally, we apply the 1st rule once, for a total of $3k-2$ transitions. But the original value has $\log\_2 \max(x,y) \approx {k}$, so we needed $3 \log\_2 \max(x,y) - C$ transitions total for some constant $C$.

It's certainly true, and not hard to prove, that the algorithm runs in $O(\log \max(x,y))$. But the question has the constant wrong.

---
Tags: algorithms, finite-automata, proof-techniques
---


# Question
Title: Why can't we use a hash tables for collision resolving in hash tables?
To prevent collisions, hash tables with open addressing use a methodology to chain the contents. Why can't we use another hash table allocated to each slot of the primary hash table?

# Answer
The method you propose is, as far as I know, the historically first one for "perfect" hashing in linear space. In perfect hashing, lookup takes $O(1)$ time in the worst-case. (Recall that in most simple hash tables, lookup takes $O(1)$ time only in expectation.)

The idea is to use chaining (rather than open addressing), but make each chain a hash table of size $\Omega(m^2)$ where $m$ is the number of items in the bucket.

This is sometimes called "FKS", after the initials of the inventors. Here are some freely available resources:
> 8 votes

# Answer
The short answer is that this is, more or less, equivalent to having one hash table. Let's say you're hashing $n$ items into $m$ slots, and each slot has its own hash table of size $c$. You propose first hashing into one of the $m$ slots using some function $h$, then hashing again into one of the $c$ slots using some function $g$. This is more or less equivalent to hashing to any of the $cm$ slots initially, with a new hash function that combines your initial two hash functions. In other words, instead of taking $h(x)$ for which of the $m$ slots to hash it to and then $g(x)$ to find the appropriate slot in the subtable, you can take $f(x) = h(x)m + g(x)$ and get the same answer with a new hash function $f$.

Something else to consider is what you do if there are collisions in the second hash. You need...some sort of methodology to chain the contents! So you're back where you started with linear probing/chaining/etc, and all you've done is increase your hash table size from $m$ to $cm$.
> 4 votes

---
Tags: data-structures, hash-tables
---


# Question
Title: To prove Turing-completeness, is it enough to prove capability of producing arbitrary output?
Turing completness is being typically proved via reduction to already proved Turing-complete machine.

Can the same be obtained by showing, that the machine in question is capable of generating arbitrary output – if proper input is given?

# Answer
Turing-completeness means that the machine model in question can compute everything that is computable. That means that for every computable function $f$, there is a corresponding program for your model which behaves "like" $f$, where I put the quotes since the input and output may look differently.

Showing that the machine can generate arbitrary output is hardly enough - consider the machine model which executes only one program, copying its input to its output.
> 4 votes

---
Tags: simulation, turing-completeness
---


# Question
Title: Find non-regular $L$ such that $L \cup L^R$ is regular?
I've been studying for an exam I have tomorrow, and I was looking through some previous sample exam questions, when I came across this problem:

> Give a non-regular language $L$ such that $L \cup L^R$ is regular.

I've been sitting here and thinking and thinking, and I can't seem to come up with a situation where this is valid. I've determined a few things based on my understanding of non-regular languages, as well as the problem itself:

* $L$ must be infinite.
* $L$ must involve some kind of counting.
* $L$ must contain multiple letters (i.e. it cannot be composed of entirely $a$s).

Given this, I went through a few basic possibilities:

* $a^ib^i$ : This would result in $L \cup L^R$ being irregular also.
* $(ab)^i(ba)^i$ (or something else palindromic) : Again, this would result in $L \cup L^R$ being irregular also. (Any palindrome would, as $L = L^R$.)
* $a^pb^q$ (where $p$ and $q$ are prime) : This, too, would result in $L \cup L^R$ being irregular also, though it would be a very much broader language, which I think is a step in the right direction.

After I got this far, I think the key is in creating some language that, when unioned with itself, forms something akin to $a^\*b^\*$ or $(ab)^\*$. The broader the words within the language, the easier it seems to define. But I can't seem to quite wrap my head around doing this.

Does anyone have a hint/spoiler or possible solution to this?

*(NB: My professor does not post solutions.)*

# Answer
Hint: try to come up with a language $L$, such that $L \cup L^R = \Sigma^\*$.

Hint2:

> Try to think on complements of known non-regular languages.

Solution:

> Let $C = \\{a^nb^n \mid n\>0\\}$, and define $L$ to be all the strings EXCEPT for those in $C$. That is, $L = \Sigma^\*\setminus C$. It is easy to see that $L$ is not Regular (closure under complement). Now let's think about $L^R$. It contains all the strings in $\Sigma^\*$, EXCEPT for strings of the form $b^na^n$.
> Finally, $L\cup L^R = \Sigma^\*$. Strings of the form $a^nb^n$ are not in $L$ but they are in $L^R$. Strings of the form $b^na^n$ are not in $L^R$ but they are in $L$.. al the rest of the strings appear in both languages. Since $\Sigma^\*$ is regular, we are done.
> 9 votes

# Answer
Another quick solution: use two letters ($\Sigma = \\{a,b\\}$) and use $b$ only as a separator, then make $L$ irregular using a counting argument in such a way that in $L \cup L^R$ the counting argument "disappears" ...

Solution:

> if $L = \\{a^nba^m | n \geq m \\}\\;$, then $L^R =\\{a^nba^m | n \< m \\} $
> and therefore $L \cup L^R = \\{a^\*ba^\*\\}$
> If your professor complains that there are too few $b$s out there (a cheat :-), then $L = \\{a^nb^pa^m | n \geq m \\}$ works equally well.
> 8 votes

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


# Question
Title: Proving the language of words with equal numbers of symbols non-context-free
> **Possible Duplicate:**
> How to prove that a language is not context-free?

I'm having a hard time figuring this out, any help is appreciated.

Let EQUAL be the language of all words over $\Sigma = \\{a,b,c\\}$ that have the same number of $a$’s, $b$’s and $c$’s

$\qquad \text{EQUAL} = \\{ w \in \Sigma^\* \mid |w|\_a = |w|\_b = |w|\_c \\}$

The order of the letters doesn't matter. How can you prove that EQUAL is non-context-free?

# Answer
It is known that the intersection of a context-free language with a regular language is context-free. If EQUAL were context-free, so would be its intersection with $a^\*b^\*c^\*$, which is the well-known non-context-free $\\{a^nb^nc^n : n \in \mathbb{N}\\}$.
> 3 votes

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


# Question
Title: How to correlate a matrix of values to get a coordinated point?
I got a n\*m matrix updated in realtime (i.e. about every 10ms) with values between 0 and 1024, and I want to work out from that matrix a multitouch trackpad behaviour, which is:

* generate one or more points on the surface given the values on the matrix,
* make this or those point as big as the value can be.

For example here is a few lines of a 9x9 matrix updates, and we can consider the following matrix as an example (with a touch in the middle):

```
[ [ 12,  7,12 ],
  [ 12,129,19 ],
  [ 12, 11,22 ] ]

```

The goal is to mimic the behaviour of a common touchpad (like on every smartphone, or laptop). So, I'm getting values from a evenly distributed matrix of capacitive sensors on a physical object, which are processed by a microcontroller into a matrix, and I want to get coordinates and weight of one or several points.

The idea would be to get something like this (of course, I don't expect to have more than 2 or 3 detected points, and that level of precision with a matrix that small).

Here are a few example raw logs:

**Edits**:

Thinking about my problematic made me consider this idea: I think I should make some kind of interpolation to augment the definition of the matrix, and in some way make the new values additive.

i.e. imagine we have the following matrix :

```
[ [ 200, 200, 150 ],
  [ 150, 150,  80 ],
  [  80,  80,  40 ] ]

```

and we want to interpolate it somehow into something that would look like (I'm inventing the values, but it's to expose the idea):

```
[ [ 200, 400, 200, 175, 150 ],
  [ 175, 200, 175, 150, 125 ],
  [ 150, 170, 150, 125,  80 ],
  [ 100, 125, 100,  80,  60 ],
  [  80,  80,  80,  60,  40 ] ]

```

I've looked at interpolation algorithms, and it looks like the one we want that is the closer to our needs is the hermite interpolation. But though I have RTFM on interpolation methods, I don't know how I can apply it to a matrix.

# Answer
> 0 votes
I finally managed to get what I want. I used python's scipy's

```
interpolate.RectBivariateSpline(x,y,z,kx,ky)

```

to create a 60x60 matrix out of the 3x3 matrix. And out of that, I used opencv libraries to detect blobs (mainly, `findContours()` and `fitEllipse()`), so now I got a list of ellipses matching the several touches I have.

---
Tags: algorithms, matrices
---


# Question
Title: How do you go about designing a vector processor architecture for the sum of matrix products?
The following equation is a matrix expression where $B\_i$ and $C\_i^T$ are $n\times n$ matrices and k is a positive integer:

$$P = \sum\_{i=1}^k B\_i C\_i^T $$

So $P = B\_1 C\_1^T + B\_2 C\_2^T + \cdots +B\_k C\_k^T $

If $B\_i $ and $C\_i$ are $n\times n$ matrices themselves, we have a total of 2 $\times$ k matrices that some how need to be stored in this vector architecture.

So this means P will end up being an $n\times n$ matrix after all the computation has completed.

What is the simplest possible vector processor architecture that is required to perform the matrix computation above?

Is there any literature or articles out there that discuss how this can be done?

Would appreciate all / any advise

# Answer
From talking to the OP, algorithms that handle parallel matrix multiplication are apparently acceptable answers. Matrix multiplication and parallel algorithms for it are a highly studied problem in CS partly because of its widespread application e.g. in scientific computing. There are other ways to parallelize the problem given in the question, e.g. an obvious "map-reduce" that maps the separate matrices to separate processors and the reduce step does the addition.

Note also the new "scicomp" stackexchange for questions on scientific computing.
> 1 votes

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


title: How to implement AO* algorithm?

text:
# Question
Title: How to implement AO* algorithm?
I have noticed that different data structures are used when we implement search algorithms. For example, we use queues to implement breadth first search, stacks to implement depth-first search and min-heaps to implement the A\* algorithm. In these cases, we do not need to construct the search tree explicitly.

But I can not find a simple data structure to simulate the searching process of the AO\* algorithm. I would like to know if constructing the search tree explicitly is the only way to implement AO\* algorithm? Can anybody provide me an efficient implementation?

# Answer
Regarding this article every time you expand a node in the AO\* algorithm you must go backwards to update all of its predecessors’ estimated cost.

When you use linear data structure to contain the nodes you must traverse the data elements sequentially and only one data element can be directly taken (stack, queue, priority queue …).

In AO\* each time a node is taken for expansion based on its estimated cost the algorithm iterates over all of the nodes that are its predecessors(to update their estimated cost). That means that sometimes you should take element based on its estimated cost and sometimes based on its successor. There is no sequence order that can meet both of these conditions in the general case. Probably there is a way to use "nested" linear data structures, but it should just imitate a tree structure, and it will be better to build the search tree instead.
> 1 votes

# Answer
I'm just going off that description you linked to, but what about a BST? You might be able to construct it to balance out unsolved nodes. That could save you time on step 2, and would help keep the overall time down depending on the number of traversals. Of course, if you balanced/sorted your tree according to unsolved nodes, you'd probably be at least better than a more simplistic data structure, potentially keeping in/around logarithmic time.

http://en.wikipedia.org/wiki/Self-balancing\_binary\_search\_tree
> 0 votes

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


# Question
Title: Modulo hash function and multiples of three
This is a textbook based question. In The Art of Computer Programming Volume 3, Knuth says that for a hash function $h(k) = k \bmod M$, $M$ should not be a multiple of $3$.

The explanation given is:

> If keys are alphabetic, two keys that differ only by permutation of letters would differ in numeric value by a multiple of 3. This occurs because $2^{2n} \bmod 3 = 1$ and $10^{n} \bmod 3 = 1$)."

I'd be grateful, if someone can clarify why this is so, and how that equation is connected to alphabetical keys and $M$ being a power of $3$.

# Answer
> 1 votes
Observe that $2^{2n} = 4^n \equiv 1^n\equiv 1 \mod 3$ and $10^n \equiv 1^n\equiv 1 \mod 3$. The relevance of $2^{2n}$ is that exchanging two characters (stored in bytes with even numbers of bits) amounts to multiplying one part of a key by $2^{2n}$ for some $n$, and dividing another part by a like amount. (Also note, powers of 3 ($3^k$ for some $k$) are multiples of 3 ($3\cdot m$ for some $m$ if $k\>0$) but multiples of 3 are much more common than its powers.)

---
Tags: data-structures, hash-tables, hash
---


# Question
Title: Base of logarithm in runtime of Prim's and Kruskal's algorithms
For Prim's and Kruskal's Algorithm there are many implementations which will give different running times. However suppose our implementation of Prim's algorithm has runtime $O(|E| + |V|\cdot \log(|V|))$ and Kruskals's algorithm has runtime $O(|E|\cdot \log(|V|))$.

What is the base of the $\log$?

# Answer
To expand on what David Eppstein said, you can assume it's in any base.

If the log were initially in base $b$, it is asymptotically the same as if it were in base $k$:

$$O(\log\_b n) = O\left(\frac{\log\_k n}{\log\_k b}\right) = O(\log\_k n)$$

because $k$ and $b$ are both constants; $\log\_k b = O(1)$.

The logs in any two bases are the same in big-O notation.
> 8 votes

---
Tags: algorithms, time-complexity, graphs, algorithm-analysis, runtime-analysis
---


title: Quantum computing 'amplitudes'

text:
# Question
Title: Quantum computing 'amplitudes'
As far as I understand, you receive an output from a quantum computer for an algorithm in the form of an amplitude, which is one of the many states your qubits may be in, however this amplitude is a complex number.

I understand that you have to square the amplitude to find the probability of finding that amplitude, but how do you convert that original amplitude into something relevant to the problem (i.e. that 3\*5=15)? Is there coding within the algorithm to change the amplitude into a malleable answer?

# Answer
> 3 votes
The state of a qubit, or of a collection of qubits, is given by a state vector. However, most people would say that the *output of a quantum computer* is in fact the result of a measurement, which transforms the state into one which indicates a single outcome.

There are many ways to approach this, but the simplest one to describe mathematically is *complete measurement in the standard basis*. In this case, you transform a quantum state on $n$ qubits into an $n$-bit string.

Suppose that you have a state $|\psi\rangle \in \mathbb C^{2^n}$ on $n$ qubits, given by $$ |\psi\rangle \\;=\\; \sum\_{x \in \\{0,1\\}^n} \\!u\_x \\;|x\_1 x\_2 \cdots x\_n \rangle \\;, \quad \text{such that } \sum\limits\_{x\in\\{0,1\\}^n} \\!|u\_x|^2 = 1 .$$

In order to get a classical output from a quantum computer, one thing you can do is to perform a complete measurement in the standard basis. What this means is that we collapse the state to some single output vector $y \in \\{0,1\\}^n$. We get different bit-strings $y$ with different probabilities, governed by the formula $$ \Pr\nolimits\_\psi(y) \\;=\\; \Bigl| \langle y | \psi \rangle \Bigr|^2 \\;=\\; \left| \sum\_{x \in \\{0,1\\}^n} \\!u\_x \\; \langle y\_1 y\_2 \cdots y\_n | x\_1 x\_2 \cdots x\_n \rangle \right|^2 \\;=\\; \left| u\_y \right|^2 \\;. $$ The outcome is then just a random output string $y \in \\{0,1\\}^n$, where the probabilities are given by the non-negative real numbers $|u\_y|^2$. Afterwards, you can compute with the measurement result $y \in \\{0,1\\}^n$ however you like, with a classical computer.

It's possible to describe performing a measurement only on a single bit, or with respect to bases other than the standard basis, but that's not really necessary to answer your question; measuring all of the qubits is certainly something you can do, and it's enough to get classical outputs from quantum computations.

# Answer
> 1 votes
Let me answer by an example that might be helpful for understanding this issue (without formally answering your question).

Assume that you put "15" as an input into a quantum-algorithm that factors numbers.

Now, the output $\lvert \phi \rangle \in (\mathbb{C^2})^{\otimes3}$ is a 3-qubit state (representing an integer in \[1,8\] in the computational basis), which has the following probabilities ("amplitudes") when measured ($M$) in that basis:

> $\lvert \phi \rangle \stackrel{M}{\to} 1$ w.p. $p\_1=0$
> $\lvert \phi \rangle \stackrel{M}{\to}2$ w.p. $p\_2=0$
> $\lvert \phi \rangle \stackrel{M}{\to}3$ w.p. $p\_3=0.5$
> $\lvert \phi \rangle \stackrel{M}{\to}4$ w.p. $p\_4=0.001$
> $\lvert \phi \rangle \stackrel{M}{\to}5$ w.p. $p\_5=0.499$
> $\lvert \phi \rangle \stackrel{M}{\to}6,7,8$ w.p $p\_6=p\_7=p\_8=0$

(numbers are just for fun.. Not real numbers)

Does it make sense how the output's probabilities are actually very relevant to the problem?

---
Tags: quantum-computing, computation-models
---


title: Maximum number of nodes with height h

text:
# Question
Title: Maximum number of nodes with height h
How is $\frac{n}{2^{h+1}}$ the maximum possible number of nodes at height $h$ for a binary search tree or heap tree? I saw this as proof to asymptotically bound the `build_heap` function in the book, but I don't get it.

# Answer
> 9 votes
I actually touched upon this in response to your previous question, but the general idea is that there are $n$ nodes in a binary tree, and starting from the root, at each depth there is: 1, 2, 4, 8, 16 ... maximum nodes. We see that at the greatest depth, there is (at most) half of all nodes ($n/2$). Remember that the height of a node is the distance from the node to a leaf, such that the height of a leaf is 0 (and the height of the root is the height of the tree). So for a leaf, $\frac{n}{2^{0+1}}=n/2$. For the root, $h=\log\_2 n$, so $\frac{n}{2^{\log\_2 n+1}}=n/n=1$. And the rest of the tree follows from there.

# Answer
> 0 votes
I think it should be a full binary tree to support maximum number of nodes at a particular height.

A full binary tree (sometimes proper binary tree or 2-tree or strictly binary tree) is a tree in which every node other than the leaves has two children.

At successive level, number of nodes would be $1, 2, 4, 8,\ldots,n/2$.

For $h=0$, nodes = $\frac{n}{2^{0+1}} = \frac n2$.

For $h=\log\_2n$, nodes = $\frac{n}{2^{\log\_2n+1}} = 1$.

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


title: Context Free Grammar for language

text:
# Question
Title: Context Free Grammar for language
The language is $L = \\{a^{i} b^{j} c^{k} \\;|\\; k \neq 2j\\}$. I'm trying to write a grammar for this language, what I have so far is:

$S \rightarrow AT\_{1} \\;|\\; AT\_{2} \\;|\\; AT\_{3} \\;|\\; AB \\;|\\; AC$

$A \rightarrow aA \\;|\\; \varepsilon$

$B \rightarrow bB \\;|\\; \varepsilon$

$C \rightarrow cC \\;|\\; \varepsilon$

$T\_{1} \rightarrow bbB'T\_{1}c \\;|\\; \varepsilon $ (for $2j \> k$)(1)

$B' \rightarrow bB' \\;|\\; b$

$T\_{2} \rightarrow bT\_{2}ccC'\\;|\\; \varepsilon$ (for $2j \< k$)

$C' \rightarrow cC' \\;|\\; c$

$T\_{3} \rightarrow bT\_{3}c \\;|\\; \varepsilon$ (for $j = k$)

the problem that I am having is, the string $bbccc$ can't be generated although valid, in that case $j = 2$ and $k = 3$ so $2\times 2 \> 3$ corresponding to production rule (1), how can I fix this?

# Answer
> 4 votes
Production for $\\{b^jc^k\\; |\\; j\neq 2k \\}$ can be written as

$B\rightarrow bBcc\\;|\\;bB\_1\\;|\\;cB\_2$

$B\_1\rightarrow bB\_1\\;|\\;b\\;|\\;c\\;|\\;\epsilon$

$B\_2\rightarrow cB\_2\\;|\\;c\\;|\\;\epsilon$

You can see that it can't accept $bbcccc$. We can use $B\rightarrow bBcc$ twice but the final $B$ would have to be substituted with either `b` or `c`.

It accepts $bbccc$ as $B\rightarrow (bBcc) \rightarrow b(bB\_1)cc \rightarrow bb(c)cc$

For even number of `c`s $B\rightarrow bBcc$ can be used. For odd number of `c`s, an extra $B\_1\rightarrow c$ can be used.

So $\\{a^ib^jc^k\\; |\\; j\neq 2k \\}$ has the following grammar

$S\rightarrow AB$

$A\rightarrow aA \\;|\\; \epsilon$

$B\rightarrow bBcc\\;|\\;bB\_1\\;|\\;cB\_2$

$B\_1\rightarrow bB\_1\\;|\\;b\\;|\\;c\\;|\\;\epsilon$

$B\_2\rightarrow cB\_2\\;|\\;c\\;|\\;\epsilon$

**Note:** `i` can be `0` but `j` and `k` can not be `0` simultaneously.

# Answer
> 2 votes
Here is my version of a grammar for $\\{a^ib^jc^k \mid k\neq 2j \\}$. It is based on the very straight-forward grammar for $\\{a^ib^jc^k \mid k= 2j \\}$, but then it requires to have either an additional (non-empty) sequence of `b`s or an additional (non-empty) sequence of `c`s to show up in the proper place. There is on special rule that produces $a^\*bc$.

$S\rightarrow AbBE \mid AECc \mid Abc$

$A\rightarrow aA \mid \varepsilon$

$B\rightarrow bB \mid \varepsilon$

$C\rightarrow cC \mid \varepsilon$

$E\rightarrow bEcc\mid \varepsilon$

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


title: Construction of binary random variable

text:
# Question
Title: Construction of binary random variable
We throw two coins in a row and thus get the event space $\\{ZZ, WW, ZW, WZ\\}$. Each of the 4 elementary events has a probability $1/4$. how can I construct 3 binary random variable $x\_1$, $x\_2$, $x\_3$ about this event space, which are 2-fold independent, but not independent.

# Answer
> 4 votes
Let $E = \\{ZZ,WW,ZW,WZ\\}$. A *binary random variable* is a mapping $X\colon E \rightarrow \\{0,1\\}$. The *probability* of an event, say $X=0$, is defined as $$ \Pr\[X = 0\] =\frac{|\\{e \in E : X(e) = 0\\}|}{4}. $$ For example, let $C\_1(ZZ)=C\_1(ZW) = 0$, $C\_1(WZ)=C\_1(WW) = 1$. Then $\Pr\[C\_1=0\]=1/2$.

Two (binary) random variables $X\_1,X\_2$ are *independent* if for every $b\_1,b\_2 \in \\{0,1\\}$, $$\Pr\[X\_1 = b\_1 \text{ and } X\_2 = b\_2\] = \Pr\[X\_1 = b\_1\] \Pr\[X\_2 = b\_2\]. $$ For example, if $C\_2(ZZ) = C\_2(WZ) = 0$ and $C\_2(ZW) = C\_2(WW) = 1$, then you can check that $C\_1$ and $C\_2$ are independent, by checking that $\Pr\[C\_1 = b\] = \Pr\[C\_2 = b\] = 1/2$ and $\Pr\[C\_1 = b\_1 \text{ and } C\_2 = b\_2\] = 1/4$. On the other hand, $C\_1$ and $C\_1$ are not independent since $\Pr\[C\_1 = 0 \text{ and } C\_1 = 0\] = 1/2$.

Similarly you can define when more than two random variables are independent. It should be clear that there are no three binary random variables $X\_1,X\_2,X\_3$ with $\Pr\[X\_1 = 0\] = \Pr\[X\_2 = 0\] = \Pr\[X\_3 = 0\] = 1/2$ which are independent, since that would imply $\Pr\[X\_1 = X\_2 = X\_3 = 0\] = 1/8$, which is impossible (the only values that $\Pr$ can obtain are $0,1/4,1/2,3/4,1$). On the other hand, any three constant random variables are independent.

A set of random variables is $k$-wise independent if any $k$ of them are independent. The question asks you to find three random variables $X\_1,X\_2,X\_3$ so that any two are independent, but all three aren't. My hint is that there is a solution with $X\_1 = C\_1$ and $X\_2 = C\_2$.

# Answer
> 0 votes
Consider an Exclusive-OR gate with inputs (logical variables) $x$ and $y$ and output $z = x\oplus y$. Suppose $x$ and $y$ are equally likely to take on values $0$ and $1$ and are *independent*, that is $$P\\{x = a, y = b\\} = P\\{x = a\\}P\\{y = b\\} = \frac{1}{4} ~~\text{for all} ~a, b \in \\{0,1\\}.$$ Then, $P\\{z = 1\\} = P\\{x = 1, y = 0\\} + P\\{x=0, y = 1\\} = \frac{1}{2}$ and so $$P\\{x = 1, z = 1\\} = P\\{x = 1, x\oplus y = 1\\} = P\\{x = 1, y = 0\\} = \frac{1}{4} = P\\{x = 1\\}P\\{z=1\\},$$ that is, $x$ and $z$ are also independent. Thus, we are led to the remarkable conclusion that the *output* $z$ of an Exclusive-OR gate is *independent* of its *input* $x$. A similar calculation shows that the output $z$ is also independent of input $y$, that is, the output of an Exclusive-OR gate is independent of its inputs!

> Lest we accept the moral principle that the output of an Exclusive-OR gate does not depend on its inputs, let me say that this independence disappears if $P\\{x = 1\\}$ is *not exactly* $\frac{1}{2}$ but differs from $\frac{1}{2}$ by even an infinitesimal amount.

---
Tags: probability-theory, sampling
---


title: Modification of Hamilton Path

text:
# Question
Title: Modification of Hamilton Path
Although I know that the Hamilton Path problem is ${\sf NP}$-complete, I think the following variant can be solved in polynomial time:

> Given a planar graph with vertex set $V$, edge set $E$, start node $S$ and target node $F$, our task is to find the Hamiltonian path from $S$ to $F$ or write that the path doesn't exist.
>
> *Last condition*: In the path, in addition to selecting the directly connected vertices, we can also choose those connected to exactly one neighbor.
>
> **Edit**: The degree of any vertex is at most four ($\deg(v\_i) \le 4$).

Does anyone have any ideas how to prove that this can be solved in polynomial time?

It can be hard to understand, so I will give an example:

In the left example, for $S=1,F=12$, the solution is the path $1, 11, 8, 7, 5, 9, 2, 10, 4, 6, 3, 12$.

In the right example, for $S=1,F=15$, there is no Hamiltonian path.

# Answer
> 2 votes
Perhaps the problem is still NP-complete; this reduction should work: given a planar graph $G$ and two nodes $s$ and $t$ (start and end), expand it to a new graph $G'$ in this way: for every node $u$ of $G$ add two nodes $u\_1,u\_2$ and two edges: $(u,u\_1),(u\_1,u\_2)$ (informally add a *tail* made with two new nodes).

There are only two ways to traverse the three node gadget with a valid Hamiltonian path (i.e. cover the three nodes):

a) $out \rightarrow u \rightarrow u\_2 \rightarrow u\_1 \rightarrow out$ and its reverse

b) $out \rightarrow u\_1 \rightarrow u\_2 \rightarrow u \rightarrow out$

In both cases the node $u$ must be traversed and cannot be reused in another part of the path.

Now, in order to force one of the two traversals in every node, add two tails to $s$: $(s,s\_1), (s\_1,s\_2)$ and $(s,s\_3), (s\_3,s\_4)$ and pick as starting node of $G'$ the node $s\_1$. The only way to traverse and leave $s$ is $s\_1 \rightarrow s\_2 \rightarrow s \rightarrow s4 \rightarrow s3 \rightarrow out$. This forces traversal (a) on all remaining nodes (gadgets) of $G'$. Pick $t\_2$ as the ending node in $G'$.

So the original graph $G$ has an Hamiltonian path from $s$ to $t$ if and only if $G'$ has a "modified" (one node jumps allowed) Hamiltonian path from $s\_2$ to $t\_2$.

**EDIT:**

* If $deg(v\_i) \leq 4$ the above reduction still works because Hamiltonian path is NP-complete even in planar cubic graphs. In a planr cubic graph $deg(v\_i) = 3$, so nodes can be extended with the tails as described above. If the starting node has degree 3, just add another node $s'$, an edge $(s,s')$ and add two tails to $s'$.
* But, if $deg(v\_i) \leq 3$ then the problem falls in $\mathsf{P}$, the following algorithm *should* work (but I didn't think about it too much):

calculate the shortest path from $s$ to $t$: $s \rightarrow u\_1 \rightarrow ... \rightarrow u\_m \rightarrow t$, then expand the path using a depth first search from every node; this will lead to a spanning tree having the shortest path as a "backbone". For each $u\_i$ of the shortest path there is only one branch $u\_i,b\_1,b\_2,...,b\_k$(because the degree of $v\_i$ is $\leq 3$) and it can be covered using jumps:

$u\_i \> b\_2 \> b\_4 \> ... \> b\_k \> b\_{k-1} \> ... \> b\_3 \> b\_1 \> u\_{i+1}$ if $k$ is even
$u\_i \> b\_2 \> b\_4 \> ... \> b\_{k-1} \> b\_k \> b\_{k-2}... \> b\_3 \> b\_1 \> u\_{i+1}$ if $k$ is odd

The only problem is if $s$ and/or $t$ have degree 3. In that case the above procedure must be repeated several times using only one incident edge of $s$ (and eventually only one incident edge of $t$).

In order to formally prove that the algorithm is correct one must prove that every Hamiltonian path (with jumps) from $s$ to $t$ in a $deg(v\_i) \leq 3, deg(s)=1, deg(t)=1$ graph can be transformed to an Hamiltonian path (with jumps) of the above form (a spanning tree from the shortest path). It is not immediate but it seems intuitive (but perhaps I'm just wandering :).

---
Tags: algorithms, complexity-theory, graphs, np-hard
---


# Question
Title: Simplification of regular expression and conversion into finite automata
This is a beginners question. I and reading the book "Introduction to Computer Theory" by Daniel Cohen. But I end up with confusion regarding simplification of regular expressions and finite automata. I want to create an FA for the regular expression

$\qquad \displaystyle (a+b)^\* (ab+ba)^+a^+\\;.$

My first question is that how we can simplify this expression? Can we we write the middle part as $(ab+ba)(ab+ba)^\*$? will this simplify the expression?

My second question is whether the automaton given below is equivalent to this regular expression? If not, what is the mistake?

This is not a homework but i want to learn this basic example. And please bear me as a beginner.

# Answer
> 6 votes
At the point of writing, your NFA is still a bit off. One version of a correct answer looks like this:

So this NFA is design in an ad hoc manner, but there's still some basic organisation to it. You can see that there's three basic bits, the $a,b$ loop on the start state, a forced $ab|ba$, followed by two 2-step loops, then a forced $a$ to the final state, with an $a$ loop. The first loop takes care of the $(a+b)^{\ast}$, the next little clump does the $(ab+ba)^{+}$, then the tail end does the $a^{+}$.

The key thing to practice when doing things this way is breaking the RE down into a sequence of smaller REs, that you then stick together. This is essentially a 'casual' version of the systematic method.

The systematic way is simple, but a bit fiddly. It's a relatively long explanation as to how to do it systematically, and as you haven't reached that bit in your reading yet, I'll refrain from working through the details here, however just as a quick reference, this explanation is pretty thorough and reasonably well explained.

---
Tags: formal-languages, automata, finite-automata, regular-expressions
---


# Question
Title: How many different max-heaps exist for a list of n integers?
How many different max-heaps exist for a list of $n$ integers?

Example: list `[1, 2, 3, 4]`

The max-heap can be either `4 3 2 1`:

```
    4
   / \
  3   2
 /
1

```

or `4 2 3 1`:

```
    4
   / \
  2   3
 /
1

```

# Answer
> 27 votes
I did not find a closed form, but according to this entry in the Online Encyclopedia of Integer Sequences the sequence starts with

1, 1, 1, 2, 3, 8, 20, 80, 210, 896, 3360, 19200, 79200, 506880, 2745600, 21964800, 108108000, 820019200, 5227622400, 48881664000, 319258368000, ...

You can find a not-so-nice recursion in the OEIS database. Basically the idea is as follows. The root of an $n$-ary heap is always the maximum. The two subtrees hanging off the root are again maxheaps. Their size depends on $n$, is a bit tedious to compute the sizes $n\_1,n\_2$ (see the OEIS entry), clearly $n\_1+n\_2=n-1$. We can now pick, which elements go to the left heap and which go to the right heap. There are ${n-1 \choose n\_1}$ ways how to distribute the elements. This gives the recurrence

$$ a(n)= {n-1 \choose n\_1} a(n\_1)a(n\_2).$$

---
Tags: data-structures, combinatorics, heaps
---


# Question
Title: Hardness of ambiguity/non-ambiguity for context-free grammars
A grammar is *ambiguous* if at least one of the words in the language it defines can be parsed in more than one way. A simple example of an ambiguous grammar $$ E \rightarrow E+E \ |\ E\*E \ |\ 0 \ |\ 1 \ |\ ... $$ because the string 1+2\*3 can be parsed as (1+2)\*3 and 1+(2\*3). For context free grammars (CFGs) ambiguity is not decidable \[1, 2\]. This implies that non-ambiguity is also not decidable. Moreover, at least one of ambiguity and non-ambiguity cannot even be recursively enumerable, for otherwise ambiguity of a given CFG $G$ could be decided by running the enumeration of ambiguity and non-ambiguity together and seeing which one contains $G$ (and one of them must).

So which problem is harder in this sense? Ambiguity or non-ambiguity?

1. D. G. Cantor, On The Ambiguity Problem of Backus Systems.
2. R. W. Floyd, On ambiguity in phrase structure languages.

# Answer
Ambiguous grammars can be enumerated, since each ambiguous grammar has a proof of ambiguity, namely a word with two different parses.
> 9 votes

---
Tags: computability, formal-grammars, context-free, undecidability, ambiguity
---


# Question
Title: Robustness of Turing Machines - 3 dimensional case
How can one show that a machine with a three dimensional memory arranged in an infinite grid can be simulated by a single-tape Turing machine? I'd imagine there's some sort of mapping possible from three dimensional coordinates to single coordinates (eg. (0,0,0) -\> 0, (1,0,0) -\> 1, (-1,0,0) -\> 2, ...) but I can't figure it out. Or maybe there's some clever way to separate the points using special symbols. Either way, I'm at a loss.

# Answer
If you are not concerned with efficiency this trivial and *time-wasting* approach can also work (*it only shows how it can be done without taking too much care of coordinate-mappings ... in other words the bad way to do it :-)*).

Use the single tape to store a *list* of quadruples $...\\#x,y,z,v\\#...$.

Each quadruple holds the value $v$ stored on the 3D tape at point $(x,y,z)$. Initially the single tape is filled with a *finite* list of the non-blank values of the 3D tape along with their coordinates, and the head is on the left of the quadruple that represents the head position in the 3D tape.

Every step of the original 3D machine can be simulated in the following way:

1. apply the original transition, and update the value $v$ to $v'$ in $(x,y,z,v)$
2. now, suppose that the head must move to the adjacent 3D point $(x',y',z')$, then search in the tape from left to right for a quadruple that matches its coordinates;
\- if you find it, then move the head on it and go to (1);
\- if you don't find it, just append a new quadruple $(x',y',z',blank)$ to the end of the tape, move the head on it and goto (1)

For every state of the original 3D machine you must have many states on the single tape machine in order to perform the operations at step 2 and at the same time keep track of the current state of the original machine.
> 4 votes

# Answer
Let's begin with a 2D infinite memory. point (0,0) is 0. Then, we go in "circles" around the (0,0) so that we cover all the plane. Each "step" increases the image index by one.. $walk \equiv (x,y) : (0,0) \to (1,0) \to (1,1) \to (0,1) \to (-1,1) \to \cdots$

See the image in:

<sup>(it might be copyrighted, so I just give a link. If somebody finds a free picture, I'd be grateful if you could add it here).</sup>

Now, the specific order doesn't really matter, as long as you eventually cover all the points, and have a systematic way to describe your mapping.

Generalizing to 3D space is not a big deal. Begin with (0,0,0), and cover all the points around in some order.

For instance, for a fixed $z$ value, we reduce the problem to a 2D-plane which can be covered like following the series $walk$ above. To cover the entire space, we change $z$ at each step, so that every value will be chosen infinitely many time. For instance, let $z$ be (along the first few steps): 0,1,0,1,2,0,1,2,3,.... Actually, $z$ should be also negative, so it could look like $z: 0,1,-1,0,1,-1,2,-2,0,1,-1,2,-2,3,-3,...$. For every choiceof $z$ we have a fresh copy of $walk$, which we denote $walk\_z$, that determines the next value of $x$ and $y$ for that plane (i.e., $walk\_z = (0,0,z)\to (1,0,z) \to (1,1,z)\cdots$). At every step, we choose a specific plane (value of $z$) and pick the next value of the series $walk\_z$ that hasn't been picked before.

(if somebody finds a 3D pic (or can draw one), please add it..)
> 3 votes

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


# Question
Title: Lower bounds: queues that return their min elements in $O(1)$ time
First, consider this simple problem --- design a data structure of *comparable* elements that behaves just like a stack (in particular, push(), pop() and top() take constant time), but can also return its min value in $O(1)$ time, without removing it from the stack. This is easy by maintaining a second stack of min values.

Now, consider the same problem, where the stack is replaced by a queue. This seems impossible because one would need to keep track of $\Theta(n^2)$ values (min values between elements $i$ and $j$ in the queue). True or false ?

Update: $O(1)$ amortized time is quite straightforward as explained in one of the answers (using two min-stacks). A colleague pointed out to me that one can de-amortize such data structures by performing maintenance operations proactively. This is a little tricky, but seems to work.

# Answer
> 10 votes
Yes, it can be done in *amortized* O(1) time (enqueue, dequeue, minimum). Have a look at the code and explanation given here.

Here are the most relevant parts quoted from the above link (emphasis mine; and of course, all credits for the solution go to the original author, Keith Schwarz):

> A FIFO queue class that supports amortized O(1) enqueue, dequeue, and find- min. Here, the **find-min returns (but does not remove) the minimum value in the queue**. This is *not* the same as a priority queue, which always removes the smallest element on each dequeue. The min-queue simply allows for constant-time access to that element.
>
> The construction that enables the min-queue to work is **based on a classic construction for creating a queue out of two stacks. ... we apply this construction to two min-stacks instead of two regular stacks**. The minimum element of the queue can then be found by looking at the minimum element of the two stacks taken together.

# Answer
> 3 votes
When returning the min element, I assume you also want to remove it from the data structure? Otherwise it's trivial to just always keep track of the least element when you alter the data structures via any of the other operations.

I'm not entirely sure how much cheating you allow, but you could keep two additional queues, such that on insertion to your data structure, you also use as much time as you need to keep a queue sorted with the least elements in the first-outs position.

Let Q be your main queue, S your sorted queue and A an (empty) additional queue. When you receive a new element, e, to Q, you push all your elements in S less than e into A, then you push e to A, and then you empty the rest of S into A. Finally you push all of A into S. This takes O(n) time, you use only queues, and you can find the minimal element in constant time. If you also need to be able to remove it from the main queue, you can keep pointers from the elements in S to the positions in Q.

---
Tags: data-structures, priority-queues, lower-bounds
---


title: Comparing Time complexity?

text:
# Question
Title: Comparing Time complexity?
How would I solve these problems involving time complexity:

1. Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size $n$, insertion sort runs in $8n^2$ steps, while merge sort runs in $64n \log\_2 n$ steps. For which values of $n$ does insertion sort beat merge sort?
2. What is the smallest value of n such that an algorithm whose running time is $100n^2$ runs faster than an algorithm whose running time is $2^n$ on the same machine?
3. For each function $f(n)$ and time $t$ , determine the largest size $n$ of a problem that can be solved in time $t$, assuming that the algorithm to solve the problem takes $f(n)$ microseconds.

(a) $n! = 1$ second

(b) $n \log\_2 n$ = 1 second

# Answer
Problems comparing the time complexity of different algorithms are usually concerned with asking which algorithm takes less time (that is, less steps). So when the problem asks which one is "beats" the other or is "faster" for a given size of input $n$, it is asking which would take less steps (and hence less time); i.e. which would result in a smaller number.

In the context of your problems, some algorithms will outperform others for small $n$ (in terms of time) but be outperformed for large $n$. The questions ask for the size $n$ at which it insersects/switches.

How would you determine that intersection point?
> 1 votes

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


title: Iterative binary search analysis

text:
# Question
Title: Iterative binary search analysis
I'm a little bit confused about the analysis of binary search. In almost every paper, the writer assumes that the array size $n$ is always $2^k$. Well I truly understand that the time complexity becomes $\log(n)$ (worst case) under this assumption. But what if $n \neq 2^k$?

For example if $n=24$, then we have 5 iterations for 24
4 i. for 12
3 i. for 6
2 i. for 3
1 i. for 1

So how do we get the result $k=\log n$ in this example (I mean of course every similar example whereby $n\neq2^k$)?

# Answer
> 7 votes
$n=2^k$ is a simplifying assumption that ensures binary search "goes through" properly. If the array has a length that is not a power of two, you have to break ties when choosing middle elements, "halves" are not equally large and not all decisions lead to the same number of steps.

The worst-case number of steps on an array of size $n$ can certainly bounded from above by the maximum number of steps on an array of size $2^k$, $n \leq 2^k$. If we choose $k$ as small as possible, we obtain $k = \lceil \log n \rceil$.

With $\lceil \log n \rceil \leq \log(n) + 1$ we see that the worst-case number of steps is indeed asymptotically equal to $\log n$.

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


# Question
Title: Algorithm to minimize distance variance between 2D coordinates
I've been looking around for an algorithm that would optimize the distance between 2 list of coordinates and choose which coordinate should go together.

Say I have List 1:

```
205|200
220|210
200|220
200|180

```

List 2:

```
210|200
207|190
230|200
234|190

```

Calculated Distance between Coords:

```
205|200 to 210|200 == 5.00
205|200 to 207|190 == 10.20
205|200 to 230|200 == 25.00
205|200 to 234|190 == 30.68

220|210 to 210|200 == 14.14
220|210 to 207|190 == 23.85
220|210 to 230|200 == 14.14
220|210 to 234|190 == 24.41

200|220 to 210|200 == 22.36
200|220 to 207|190 == 30.81
200|220 to 230|200 == 36.06
200|220 to 234|190 == 45.34

200|180 to 210|200 == 22.36
200|180 to 207|190 == 12.21
200|180 to 230|200 == 36.06
200|180 to 234|190 == 35.44

```

This Algorithm would pick:

```
205|200 to 230|200 == 25.00
220|210 to 207|190 == 23.85
200|220 to 210|200 == 22.36
200|180 to 234|190 == 35.44

```

The Algorithm would pick these numbers as they would be the group that would have the littlest variance between the distance. Conditions:

1. A Coordinate may only be used ones from each list
2. If List 1 or List2 is larger than it still only uses each coordinate once, but it tries to get the smallest distance variance and does nothing with the unused coordinates.

If you need more clarification please ask.

P.S. I've looked at the Hungarian algorithm and it seems like it will sort of do the job, but not exactly how I was expecting. The Hungarian algorithm will only try and make the least distance from all the coordinates, which can mean the smallest variance, but not every time as variance is more important here then least distance optimization.

**Additional Information**

I will have an array of List1, List2, and then the distances:

```
Distance[List1_item_0][List2_item_0] = 5;
Distance[List1_item_0][List2_item_1] = 10.20;
Distance[List1_item_0][List2_item_2] = 25.00;
Distance[List1_item_0][List2_item_3] = 30.68;

Distance[List1_item_1][List2_item_0] = 14.14;
Distance[List1_item_1][List2_item_1] = 23.85;
Distance[List1_item_1][List2_item_2] = 14.14;
Distance[List1_item_1][List2_item_3] = 24.41;

Distance[List1_item_2][List2_item_0] = 22.36;
Distance[List1_item_2][List2_item_1] = 30.81;
Distance[List1_item_2][List2_item_2] = 36.06;
Distance[List1_item_2][List2_item_3] = 45.34;

Distance[List1_item_3][List2_item_0] = 22.36;
Distance[List1_item_3][List2_item_1] = 12.21;
Distance[List1_item_3][List2_item_2] = 36.06;
Distance[List1_item_3][List2_item_3] = 35.44;

```

From the Distance\['List1\_item\_#\] I would need to pick a distance. Once that distance is picked the \[List2\_item\_#\] CANNOT be picked by a different \[List1\_item\_#\]. The distances picked for each \[List1\_item\_#\] element would need to be picked in a way that the variance between them all is minimal. So distance for each \[List1\_item\_#\] should be as close as possible to each other without reusing a \[List2\_item\_#\] more than once.

# Answer
So here is a rather simple approach to solve this problem. You know that there are $O(n^2)$ different distances that matter. You can characterize the solution of your problem by the smallest and the largest distance ($d\_\min$,$d\_\max$) between your matched points. This gives you a set of $O(n^4)$ *candidates*.

So suppose you want to test, if there exists a matching where all distances are between $d\_\min$ and $d\_\max$. In other words, you want to solve the decision problem. This can be modeled as a perfect matching in a bipartite graph. Let $(u\_1,\ldots,u\_n)$ be the points in the first list and $(v\_1,\ldots,v\_n)$ be the points in the second list. Consider the bipartite graph that has an edge $(u\_i,v\_j)$ if and only if the distance between $u\_i$ and $v\_j$ is contained inside $\[d\_\min,d\_\max\]$. If this graph has a perfect matching, then there is an point-to-point assignment for the given distance constraints. Such a test can be done by the Hopcroft-Kahn algorithm, which needs $O(n^{2.5})$. A slightly faster solution can be achieved with fast matrix multiplication.

So you are left with trying out the candidates. This gives a $O(n^{6.5})$ algorithm. You can save a bit of running time by trying out all $d\_\min$ values but then do a binary search for each $d\_\max$ value. Now you have to solve only $O(n^2 \log n)$ decision problems (you also have to sort all distances, which is dominated by the overall running time) and hence the running time is only $O(n^{4.5}\log n)$.
> 1 votes

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


# Question
Title: Why is $\sum_{j=0}^{\lfloor\log (n-1)\rfloor}2^j$ in $\Theta (n)$?
I am trying to understand summation for amortization analysis of a hash-table from a MIT lecture video (at time 16:09).

Although you guys don't have to go and look at the video, I feel that the summation he does is wrong so I will attach the screenshot of the slide.

# Answer
If you have a series of numbers that are consecutive power of 2s, like $1+2+4+8+16+\cdots+2^k$ you get as sum $2^{k+1}-1$. You can either see this by looking at the formula for the geometric series or you can prove this by induction.

Then the statement of the lectures follows, since here $k=\lfloor \log (n-1) \rfloor$. Therefore the sum is less than $2n$.
> 4 votes

---
Tags: algorithms, data-structures, algorithm-analysis, mathematical-analysis, discrete-mathematics
---


title: Commonly used Error Correcting Codes

text:
# Question
Title: Commonly used Error Correcting Codes
We know error correcting codes are parameterized as (n,k,d) codes. I wanted to know the values of these parameters for some commonly used error correcting codes in computer memories or in DRAMs, etc.

I just wanted to see some values for these parameters, used in real life applications.

# Answer
> 3 votes
I'm sure this greatly varies according to the application and the specific code in use.

Though not for DRAMs, maybe this will give you some insights:

> For CDs encoding, a (28,24)-Reed Solomon code is used.
> For DVDs, it is a (208,194)-Reed Solomon code.

Symbols are over $GF(2^8)$, that is, 8 bits per symbol. The notation is $(n,k)$-ReedSolomon for a linear $\[n,k,d\]$ code ($k$ being the dimension). RS is an MDS code and has $d=n-k+1$.

(I think this was the source, but maybe you can find it online):
*Stephan Wicker and Vijay Bhargava (eds.), **Reed-Solomon Codes and their Applications**, IEEE Press, 1994*

# Answer
> 2 votes
Specifically for Memories, try google **ECC memories**. It seems that the main trend is to correct a single bitflip per memory address. For that purpose a distanse of $d=3$ is enough and a Hamming code can be used.

* Here is an AMD memory, where each 64 bits are encoded via Hamming code ($d=3$, fixing a single bit flip).
* TI's TMSx70 controller, uses a modified Hamming code which corrects up to one error but detects up to two errors (SECDED -single error correction and double error detection). If I read it correctly, they add 8 bits to any 128bit code.

---
Tags: computer-architecture, error-correcting-codes
---


# Question
Title: Is it more effective to vote for a woman?
A certain political party wants to encourage women to participate in their primary elections, so they decide, that the 4th position is reserved for a woman. That is, if there is no woman in the top 4 positions, then the woman with the largest number of votes will be promoted to the 4th position, and the candidates at positions 4 and below (5, 6, 7...) will be demoted one position (of course, if there is initially a woman in one of the top 4 positions, then no promotion/demotion will take place).

There are two candidates that I support equally, one is a man and the other is a woman. Is it true that, if I vote for the woman, my vote is more effective?

In a more extreme case, where the 1st position is reserved for a woman, it's clear that my vote is most effective when I give it to the woman, because this is my only chance of sending my favorite candidate to the 1st position; voting for the man, in this case, will never bring my favorite candidate to the 1st position.

Intuitively, it seems to be the same with the 4th position reserved, because, if I vote for the man and he enters position \<=4, he might be demoted, but if I vote for the woman and she enters position \<=4, she might be promoted, so my single vote may be worth a lot.

However, I am looking for a formal proof that this is the case (or maybe a disproof?)

# Answer
Here is my attempt to solve this - comments are welcome:

* Mark our favorite candidates with M and W.
* Our vote is obviously effective only when the candidate I vote for is in tie, either before or after the vote. Assume that in case of tie the order is decided at random; in this case, our vote increases the chance that the candidate will be promoted by 50%.
* If the tie is in positions 1, 2 or 3, then there is no difference between voting for M or for W - in any case, our vote will promote the candidate in 1 position (with 50% probability).
* Also, if another woman got more votes than the candidates in the tie, then there is no difference between M and W, because only the first woman is promoted.
* If the tie is in positions 4, 5, 6, ... and there is no woman that got more votes, then there may be a difference:
    + If the tie is with another man, then it's useless to vote for W, because she will win the 4th position anyway. Voting for M will promote him 1 position (with 50% probability).
    + If the tie is with another woman, then it's useless to vote for M, because the woman will win the 4th position anyway. Voting for W will promote her 1 **or more** positions (with 50% probability), directly to the 4th position.

If the probability of these latter two cases is equal, then voting for W is more effective, because it may promote her more than 1 position.

However, without further information about how other people are going to vote, the only information we can use is the relative number of women and men candidates:

If the number of men candidates is larger, the first case (tie with a man) is more probable, however, there are fewer women candidates, so in the second case (tie with a woman), the distance between W and the 4th position may be larger, so the promotion will be more effective.

Intuitively, it seems that the two effects cancel, so, the "expected number of promoted positions" is equal whether we vote for M and for W. Again, I am not sure. What do you think?
> 1 votes

# Answer
Consider the following cases when you are the marginal voter (i.e. you decide the election):

* Two men $m\_1$ and $m\_2$ have $\>n$ votes, two other men $m\_3$ and $m\_4$ have $n$ votes, and one woman $w\_1$ has $\<n$ votes. If you support $m\_3$ and $w\_1$ equally and support $m\_4$ less, then you should vote for $m\_3$, such that both $m\_3$ and $w\_1$ will be in the top four.
* Three men have $\>n+1$ votes, one man $m\_x$ has $n$ votes and two women $w\_1$ and $w\_2$ have $k\<n$ votes each. If you support $m\_3$ and $w\_1$ equally, you should vote for $w\_1$ regardless of $x$ because $m\_x$ will definitely lose, and $w\_1$ will only win with certainty with your vote.
* Men $m\_3$ and $m\_4$ have $n$ votes, two women $w\_1$ and $w\_2$ have $k\<n$ votes. What happens in the case of a tie is unclear, and (given one vote) it will end in a tie either way.

Thus, it seems as though there is **no advantage** to voting for either a woman or a man over the other.
> 7 votes

---
Tags: game-theory, voting
---


# Question
Title: Resolution and incomplete Knowledge Base
Assume I have an incomplete knowledge base, for example:

```
(rich(dave), poor(dave))  // dave is either poor or rich

(not rich(dave), not poor(dave))  // dave is not poor and rich at the same time.

```

My questions are: 1. If I do resolution on the above clauses, will I get the empty clause? and 2. If Yes, Does that mean my knowledge base is inconsistent?

# Answer
The theory is not inconsistent and trivially admits two different models :

* a first one in which dave is rich but not poor;
* a second one in which dave is poor but not rich.

You're maybe confusing the "empty clause" which contains no literal, thus being always false, with the "true clause" which contains both a literal and its negation, thus being always true. Applying resolution leads to the "true clause" resolvent, not the "empty clause".
> 1 votes

---
Tags: logic, knowledge-representation, reasoning
---


# Question
Title: Recursive-Descent Predictive Parser for $S \rightarrow 0S1\ |\ 01$
I am having difficulty with one of the exercises in the *Dragon Book*:

> **Exercise 2.4.1(c):** Construct recursive-descent parsers, starting with the following grammars:
>
> $$S \rightarrow 0S1\ |\ 01$$

Yet, for constructing a feasible parser, it is required that for two productions $A \rightarrow \alpha\ |\ \beta$, their FIRST sets are disjoint. But since:

> $$FIRST(0S1) = \\{ 0 \\} \hspace{2em}\\&\hspace{2em} FIRST(01) = \\{ 0 \\}$$

this is not the case. How does one proceed here? Just state it is not feasible due to the stated conflict or is there alternative approach, like modfying the grammar?

# Answer
You may need to modify the grammar. In general this is not necessarily possible (not every CFG is an LL(k) grammar - the class suitable for recursive descent predictive parsing). In this case we can modify the grammar to:

$$\begin{align\*} &\mathtt{1.} & S &\rightarrow 0SA \\ &\mathtt{2.} & S &\rightarrow \varepsilon \\ &\mathtt{3.} & A &\rightarrow 1 \\ \end{align\*}$$

Then we have an unambiguous first and follow set for each combination of terminal and non-terminal. So the parsing table looks something like:

$$\begin{array}{l|l|l} & 0 & 1 \\ \hline S & \mathtt{1.} & \mathtt{2.} \\ \hline A & & \mathtt{3.} \\ \end{array}$$

This gives an LL(1) grammar - one that can be parsed with one symbol of lookahead. It is possible to parse the original grammar without modification using 2 symbols of lookahead (making it an LL(2) grammar), Raphael explains that approach excellently in his answer.

The details are all in the dragon book of course (what isn't!), and better explained there than I can do here.
> 2 votes

# Answer
You can grant your parser more than one symbol lookahead. I am not sure whether the term "recursive descent" applies in all definitions, but there is likely no big difference in the actual implementation.

Consider this recursive-descent acceptor:

```
S(input : String, start : int) : int {
  if ( start + 1 >= input.length ) {
    return -1;
  }
  if ( input[start, start + 1] == "00" ) {
    int sub = S(input, start + 1)
    return sub != -1 && sub + 1 < input.length && input[sub + 1] == '1'
           ? sub + 1
           : -1
  }
  else if ( input[start, start + 1] == "01" ) {
    return start + 1
  }
  else {
    return -1
  }
}

```

`input` is the whole input string, `start` is the starting index of the portion the current call is supposed to match. `-1` encodes that the (sub)word could not be parsed, otherwise the return value is the last consumed index. That is, `input` is generated by the grammar iff `S(input,0) == input.length-1`.
> 1 votes

---
Tags: context-free, compilers, parsers
---


# Question
Title: Minimum s-t cut in weighted directed acyclic graphs with possibly negative weights
I ran into the following problem:

Given a directed acyclic graph with real-valued edge weights, and two vertices s and t, compute the minimum s-t cut.

For general graphs this is NP-hard, since one can trivially reduce max-cut to it by simply reversing the edge weights (correct me if I'm wrong).

What is the situation with DAGs? Can min-cut (or max-cut) be solved in polynomial time? Is it NP-hard and, if so, are there any known approximation algorithms?

I tried to find work on this but wasn't able to (maybe I'm just using wrong keywords in my searches), so I was hoping somebody may know (or find) something about this.

# Answer
You've refined your problem some more in the comments. To be more specific, you have a DAG with all edges flowing away from the source $s$ and towards the sink $t$ (that is, all edges are on a path from $s$ to $t$). You want to find the minimum cut between two pieces of the DAG, where the first piece is connected to $s$, and the second connected to $t$. For this problem, a variation of the standard linear-programming algorithm for MIN-CUT works, even with negative edge weights.

We use the same notation as in Wikipedia. The cost of edge $(i,j)$ is $c\_{ij}$. We put a potential function $p\_i$ on each node, and let $d\_{ij} = p\_i - p\_j$. The LP is $$ \begin{align\*} \mathrm{minimize\ } & \sum\_{(i,j) \in E} c\_{ij} d\_{ij} \\ \mathrm{subject\ to\ } & \ \ \ d\_{ij} = p\_i - p\_j \ \ \forall (i,j) \in E \\ &\ \ \ d\_{ij} \geq 0 \ \ \ \ \ \ \ \ \ \ \ \\, \forall (i,j) \in E \\ & \ \ \ p\_s\\, = 1 \\ & \ \ \ p\_t \\, = 0 \end{align\*} $$

These equations guarantee that $0 \leq p\_i \leq 1$, since every vertex is on some $s$–$t$ path. Similarly, since $d\_{ij} = p\_i - p\_j$ is non-negative, the potentials on any path from $s$ to $t$ are decreasing. We still need to show that there is an optimal solution to the LP with all $p\_i$ either $0$ or $1$. This follows from the fact that the value to a solution of the LP above is the expected value of the cut $C\_w$, where $w$ is chosen randomly in $\[0,1\]$, and where cut $C\_w$ is obtained by putting all vertices $i$ with $p\_i\geq w$ in the first set of vertices, and all vertices with $p\_i \< w$ in the second set.
> 10 votes

---
Tags: algorithms, complexity-theory, graphs, weighted-graphs
---


# Question
Title: Can a graph have a cycle containing all nodes but not Hamiltonian?
Is it possible for a graph to have a cycle that goes through all the nodes, but it does not have a Hamiltonian cycle (i.e. the cycle goes through some nodes more than once)? If yes, can anyone prove it? If not, can anyone give a counterexample?

# Answer
Just pick a tree which - by definition - doesn't have any *simple cycle*, but is connected, so you can visit all the nodes and return to the starting one but you must pass on some nodes more than once.

There are also graphs which have an Eulerian cycle (a cycle that traverses every *edge* exactly once) but not an Hamiltonian cycle. For example pick a graph made with two triangles having one vertex in common.
> 7 votes

---
Tags: graphs
---


# Question
Title: First-order logic arity defines decidability?
I've read first-order logic is in general undecidable, and that could be decidable only when working with unary operators. (I think that's propositional logic, correct me if I am wrong)

The question is **why arity leads to undecidable problems?**

I would like to see some reference material, or at least some simple *example* of it, as a way to think in this passage from unary to n-ary and why it leads to undecidable problems.

# Answer
Logic with unary *predicates* (not operators), is called *monadic*. The thing that is called *propositional* logic only has *nullary* predicates, i.e., constants `true` and `false`, and no quantifiers.

The undecidability of predicate logic follows because predicate logic (with at least one binary predicate) is powerful enough to describe how a Turing machine works, and so we can express in the logic sufficiently complicated statements about Turing machines to get undecidability. In contrast, in monadic logic, where we only have unary predicates, we cannot describe the working of a Turing machine. I am being deliberately vague here to give an idea without getting bogged down in technicalities.
> 12 votes

# Answer
As Raphael pointed in a comment you are probably asking about the decidability of the classical decision problem for fragments of first order logic with unary predicates.

The search of syntactically restricted fragments of first-order logic where validity of formulas is decidable was an active field of research for over 100 years. It was understood very early that it is the dependencies between variables that make the decision problem difficult. And dependencies are best expressed when two variables occur within the arguments of a predicate. Therefore binary predicates or functional symbols (if you allow functional symbols) are essential for undecidability.

It was Löwenheim who in 1915 gave a decision procedure for first-order logic with unary predicates. If you are interested, you might find intriguing an exposition paper titled "On the Classical Decision Problem" written by Yuri Gurevich in the form of a dialog of two fictitious characters. The paper was first published in the Bulletin of EATCS.

The paper not only introduces the problem but explains how the search developed into finding a complete classification of decidable and undecidable fragments in terms of quantifier prefixes.
> 1 votes

---
Tags: reference-request, logic, undecidability, satisfiability, first-order-logic
---


title: Stochastical algorithm

text:
# Question
Title: Stochastical algorithm
We have a stochastic random source. This gives the bit $0$ (or $1$) with probability $1/2$. We want to generate a uniform distribution on the set S = $\\{0, 1,..., n-1\\}$.

Which algorithm gives with probability $1/n$ the value $i\in S$. And how many bits are needed.

# Answer
If $n$ is a power of two, then you can simply determine the value $i$ by determine bit per bit in the binary representation. So if $n=8$ then you ask your source 3 times. Suppose you get as result $1,1,0$ then you would map this event to the event that you have selected $i\leftarrow\text{bin}(110)=6$. Clearly you need $\log n$ bits.

If $n$ is not a power of two, then things a are more tricky You can definitely can get an approximate uniform distribution, if you follow the method above. Say you sample $k$ bits, and you get the $k$-digit binary number $b$, then you can pick $$i\leftarrow \frac{b}{2^k}n.$$

The more bits you sample, the closer you approach the uniform distribution. I am sure there are more involved methods for case wehere $n\neq 2^k$
> 3 votes

---
Tags: algorithms, randomness, sampling
---


# Question
Title: Levenstein distance and dynamic time warp
I am not sure how to draw parallel between the Wagner–Fischer algorithm and dtw algo. In both case we want to find the distance of each index combination (i,j).

In Wagner–Fischer, we initiate the distance by the number of insert we'd have to do from one empty string to another.

```
let wagnerFischer (s: string) (t: string) =
   let m, n = s.Length, t.Length
   let d = Array2D.create (m + 1) (n + 1) 0

   for i = 0 to m do d.[i, 0] <- i
   for j = 0 to n do d.[0, j] <- j

   for j = 1 to n do
       for i = 1 to m do
          d.[i, j] <- List.min [
                           d.[i-1, j  ] + 1;
                           d.[i  , j-1] + 1;
                           d.[i-1, j-1] + if s.[i-1] = t.[j-1] then 0 else 1; ]
   printfn "edit matrix \n %A" d
   d.[m,n]

```

in the DWT we initiate the boundary at +infinity because we dont want to 'skip' any numbers of the sequence, we always want to match with another item.

What I dont see is what changes between the DWT and the WF algo that prevent use to update the distance in homogeneous way. In DWT we systematically add the cost, whereas in the WF algo, we have this non homegenous function wrt different cases

I understand both algo, but dont make the connexion between those differences in the cost function update .. Any idea to understand the difference intuitively ?

```
let sequencebacktrack (s: 'a seq) (t:'a seq) (cost:'a->'a->double) (boundary:int->double)  =
   let m, n = s |> Seq.length, t |> Seq.length
   let d = Array2D.create (m + 1) (n + 1) 0.

   for i = 0 to m do d.[i, 0] <- boundary(i)
   for j = 0 to n do d.[0, j] <- boundary(j)

   t |> Seq.iteri( fun j tj ->
            s |> Seq.iteri( fun i si ->
                        d.[1+i, 1+j] <- cost tj si + List.min [d.[1+i-1, 1+j  ];
                                                               d.[1+i  , 1+j-1];
                                                               d.[1+i-1, 1+j-1]; ] ))
   printfn "edit matrix \n %A" d
   d.[m,n]
//does not work
let wagnerFischer2 (s: string) (t: string) =
   sequencebacktrack s t (fun a b -> if a = b then 0. else 1.) (id >> double)

let b = wagnerFischer2 "ll" "la"

```

# Answer
> 5 votes
There is in fact a whole bunch of related algorithms. In modern context I believe "time warp" would be called sequence alignment. Depending on whether you want to match complete strings or optimal substrings one gets *Needleman-Wunsch* and *Smith-Waterman*.

In your latter algorithm the costs seem to vary, that is one can attribute different costs for deletion and insertion of a character, as well as for changing characters. Your first algorithm seems to fix these costs to $1$ for all three possible changes.

---
Tags: algorithms, dynamic-programming, string-metrics, edit-distance, time-series-analysis
---


# Question
Title: Some questions regarding compilers and assemblers
Lots of basic questions are there in my mind. I need to clear them.

**Statement 1:** A compiler converts a human-readable codes to object codes, and those are converted to a machine code (executable) by linker.

Am I right here?

At wikipedia, it is written that

```
Object files are produced by an assembler, compiler, or other language
translator, and used as input to the linker.

```

**Question 1:** An assembler converts assembly language code (`MOV A, B` `ADD C`) to machine code. In case of high-level language like C++, that is generated by linker above. So assembler is not used anywhere. So how can it create an object file as written above?

Intermediate code is generated to make the code run on different architectures.

**Question 2:** Are \*.class (bytecode) files created by java compiler object files? If yes, then can we say that the JVM that runs them is a type of linker (however its not creating the executable)?

**Question 3:** When we compile a C++ program in Turbo C++, we get \*.obj files which are the object files. Can we use them to generate the executable in some other architecture?

# Answer
> 1 votes
I'll try to give a quick answer:

Question 1: compiling a high-level language like C requires these steps:

```
source codes --(preprocessing)--> "bare" *.c without # stuff
             --(compiling)------> assembler files
             --(assembling)-----> object files
             --(linking)--------> executable

```

Nowadays all these steps are usually "hidden" (and not necessarily performed by distinct programs) and the user simply click "compile" on his favourite IDE. However you can set some options on the compiler and see all the intermediate files like object files.

Question 2: a JVM is an interpreter so you can think of .class files like object codes (bytecode) that are loaded, linked and executed (interpreted) at the same time by the JVM.

Question 3: though in principle one can convert an object file to a different target architecture the practical answer is no: it's much easier to start from the source code and run the entire compiling process targeting a different architecture.

# Answer
> 2 votes
I agree with Raphael, don't look too far for a precise meaning of those terms. AFAIK, there is none. (And that rule is also true for terms which have a precise meaning, often the same word in used with a different precise meaning in different contexts).

> A compiler converts a human-readable codes to object codes,

I'd say that *compiler* is used for translators which lower the abstraction level or do deep restructuring. The source doesn't have to be human-readable (but often is), it was common for compiler to generate assembler and not object code (gcc still does it even if it call the assembler itself) and compilers generating C are quite common.

> and those are converted to a machine code (executable) by linker.

I don't think making a difference between *machine code* and *object code* is common (and I'm not even sure which difference you are making). That makes your question 1 irrelevant. Traditionally, the linker doesn't convert, it takes several object files and resolves symbolic references between them. But pushing things traditionally part of the compilation to link time is more and more common in order to take advantage of the knowledge of the whole program.

> Question 2: Are \*.class (bytecode) files created by java compiler object files? If yes, then can we say that the JVM that runs them is a type of linker (however its not creating the executable)?

The JVM contains a type of linker as it is able to combine several .class files.

> Question 3: When we compile a C++ program in Turbo C++, we get \*.obj files which are the object files. Can we use them to generate the executable in some other architecture?

You could write a translator doing that (Apple did for the 68000 at the time of its transition to PowerPC for instance). Machine language is a programming language. Depending on the amount of transformation you are allowing yourself, you could even call that a compiler.

---
Tags: terminology, compilers, code-generation
---


title: Reduction of A_LBA to E_LBA

text:
# Question
Title: Reduction of A_LBA to E_LBA
I have a rather interesting one to ponder and would love if I could get an answer for it. We were discussing the topic of mapping reduction today in my Computing theory course and I was wondering why this reduction can't exist, $A\_{LBA} \leq\_{m} E\_{LBA}$, since both of them are linear bound automata (LBAs). I do realize that $E\_{LBA}$ is undecidable, $A\_{LBA}$ is decidable, and the normal proof uses $A\_{TM}$, or $E\_{TM}$, to prove the undecidibility of $E\_{LBA}$. I am just curious why the proof is using a TM to prove an LBA. But, my Professor could not come up with a solution to my confusion. I was wondering is this possible, if so, why or why not.

**Definitions:**

$A\_{LBA} = \\{\langle M, w\rangle \mid \text{$M$ is a linear bound automaton that accepts the string $w$}\\}$

$E\_{LBA} = \\{\langle M \rangle \mid \text{$M$ is a linear bound automaton with $L(M)=\emptyset$}\\}$

$A\_{TM}$ and $E\_{TM}$ are the equivalent problems for Turing Machines.

# Answer
You have your mapping the wrong way around. As it stands, it would be a reduction from a decidable problem to an undecidable problem. It's certainly possible (see below), but it doesn't tell us anything.

Recall that if $A \leq\_{m} B$, then an algorithm solving $B$ (or deciding membership in this case) can be used to solve $A$ (decide membership in $A$). So the reduction you're looking at would tell us that any decider for $E\_{LBA}$ could be used to decide $A\_{LBA}$. We happen to also know that $E\_{LBA}$ is undecidable, but this doesn't prevent there being some decider for $A\_{LBA}$ that doesn't decide $E\_{LBA}$.

In fact, the reduction that can't exist is $E\_{LBA} \leq\_{m} A\_{LBA}$, as this would imply that we could decide $E\_{LBA}$, which we know we can't.

For the second part, the proof (or rather, one of the possible proofs) that $E\_{LBA}$ is undecidable is via constructing the mapping $A\_{TM} \leq\_{m} E\_{LBA}$, so again a decider for $E\_{LBA}$ would give us a decider for $A\_{TM}$, but we already know that $A\_{TM}$ is undecidable so $E\_{LBA}$ must also be undecidable.

As to *why* the proof uses a language that involves Turing Machines to show something about linear bound automata, it's because it works.

**A Reduction**

As $A\_{LBA}$ is decidable, we can take the input LBA $M$ and string $w$, and run the decider on $\langle M, w\rangle$. If it accepts, we map this to an LBA $M\_{rej}$ that immediately rejects. If the decider rejects, we map it to an LBA $M\_{acc}$ that immediately accepts. Thus $M\_{acc}$ accepts all input and is not in $E\_{LBA}$, and $M\_{rej}$ rejects all input and is in $E\_{LBA}$.

Note of course that this reduction is in a sense trivial, and the subset of $E\_{LBA}$ it maps to is finite and therefore decidable (even regular!).

**Another Perspective**

Given two languages $A$ and $B$ such that $A \leq\_{m} B$, there's two basic (useful) things we *might* be able to say:

* If $B$ is *decidable* then $A$ is also decidable.
* If $A$ is *undecidable* then $B$ is also undecidable.

In our case $A$ is decidable, and $B$ is undecidable, which matches neither of these possibilities, so the reduction $A\_{LBA}\leq\_{m}E\_{LBA}$ doesn't tell us anything about the decidability of either.
> 2 votes

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


title: what is semantics?

text:
# Question
Title: what is semantics?
There are many popular languages. But, computer scientists tell us that in order to understand the behaviour of programs in those languages definitely and unambiguously argue upon program behavior (e.g. prove their identity), we need to translate them into another, well understood language. They call such language "a semantics". Authors propose one of many semantics. They explain the meaning of their constructions and how you can translate your language into their. Once you do that, everybody will understand your program certainly, they say.

Looks good, yet, I do not understand something. Do they tell us that they introduce another language to understand the first one? Why do we understand it better than the original one? Why this semantics is better than that? Why not to learn semantics of C right away instead of inventing another language, for describing semantics of C? The same applies to the syntax. Why don't I ask the same question regarding the syntax?

**PS** In the comments I hear that semantics does not mean another language or translation into it. But Formal Semantics for VHDL says that if you understand something in only one way then you do not understand it and "meaning of meaning" can be specified if we supply a language with a mechanism that translates it into another (known) language. That is, "semantics is a Relation between formal systems". Hennessy, in Semantics of Programming Languages, says that semantics allows for formal processing of the program "meaning", when semantics is supplied as BNF or Syntax Diagram. What is a formal system if not a language?

**PS2** Can I say that HW synthesis of given HDL program into interconnection of gates, is a process of semantics extraction? We translate (high-level) description into the (low-level) language that we understand, afterwards.

# Answer
> 15 votes
> Why not to learn semantics of C right away instead of inventing another language, for describing semantics of C?

Because in order to define the semantics of C you need some kind of language, for example English. English can be ambiguous, and especially is the C99 semantics.

The computer science notion of semantics is generally a mathematical description of a program, and this description is not exactly a translation. There are several kind of semantics, that can be about different things:

1. about which mathematical function the program computes (denotational semantics), $$ ⟦ \verb!lambda x: x + x !⟧ = (x \mapsto 2x)$$
2. about properties that shall hold before and after the program (axiomatic semantics), $$ \\{\verb.a. \> 0\\} \quad \verb! x = a; y = 0; while(1 \< x){ x = x/2; y++; } ! \quad \\{\verb.y. = \lfloor\log(\verb.a.)\rfloor\\} $$
3. about how the program will reduce (operational semantics). $$ (σ, \verb! while(x){x--;y++;}!) ⇒ σ' $$ where $σ, σ'$ represents your memory before and after. In this case $σ=(x↦a,y↦b)$ and $σ'=(x↦a+b,y↦0)$ if $x$ and $y$ are the memory cells for $\verb.x.$ and $\verb.y.$, and if $a∈ℕ$.

A little sadly for now, universally understanding a program through its semantics is neither easy nor the intention of it all. It is not the former because, well, those math can be messy. It is not the latter because semantics provide indeed provide a common and unambiguous description, but it is not used to understand a program.

If reading the semantics is not that much meaningful, reading and agreeing on the semantics on the basic elements of the language is very important, for example to explain unambiguously how C's $\verb.continue.$ primitive works.

In conclusion:

> Do they tell us that they introduce another language to understand the first one?

Technically no, the language is math. Also it is basically the same for all programming languages, so even introducing a new language, if it is the same for all, would be pretty much OK.

> Why do we understand it better than the original one?

Because it is math so it may be harder to understand, but it is way more precise and complete.

> The same applies to the syntax.

There are works on verified parsers, but the question of what would mean a semantics of a parser is not trivial.

---
Tags: formal-languages, semantics
---


title: Breadth First Search with cost

text:
# Question
Title: Breadth First Search with cost
Looking for some tutorials / references that discuss Breadth First Search that takes into consideration the cost of paths, but could not find much information.

Could someone refer a tutorial?

# Answer
From a general point of view: there are tons, but I do sincerely recommend you the latest volume on Heuristic Search: Heuristic Search: Theory and Applications by Stefan Edelkamp and Stefan Schroedl.

From a specific point of view: in spite of the graph being directed or not, breadth-first search taking costs into account

1. **If no heuristics are available**, then it amounts to either *Dijkstra* or *Uniform Cost Search*. An excellent discussion between these two algorithms is presented in Felner, Ariel, "*Dijkstra's Algorithm versus Uniform Cost Search or a Case Against Dijkstra's Algorithm*", Symposium on Combinatorial Search, Barcelona (Spain), 2011.
2. **If heuristics are available** Then there are also a number of interesting alternatives: A$^\*$ is the usual one but RBFS also expands the same nodes in the same order with a linear consumption of memory. For these, I do strongly recommend the book by Stefan Edelkamp and Stefan Schroedl.

Hope this helps,
> 2 votes

---
Tags: algorithms, reference-request, graphs, search-algorithms
---


title: Reduce the following problem to SAT

text:
# Question
Title: Reduce the following problem to SAT
Here is the problem. Given $k, n, T\_1, \ldots, T\_m$, where each $T\_i \subseteq \\{1, \ldots, n\\}$. Is there a subset $S \subseteq \\{1, \ldots, n\\}$ with size at most $k$ such that $S \cap T\_i \neq \emptyset$ for all $i$? I am trying to reduce this problem to SAT. My idea of a solution would be to have a variable $x\_i$ for each of 1 to $n$. For each $T\_i$, create a clause $(x\_{i\_1} \vee \cdots \vee x\_{i\_k})$ if $T\_i = \\{i\_1, \ldots, i\_k\\}$. Then and all these clauses together. But this clearly isn't a complete solution as it does not represent the constraint that $S$ must have at most $k$ elements. I know that I must create more variables, but I'm simply not sure how. So I have two questions:

1. Is my idea of solution on the right track?
2. How should the new variables be created so that they can be used to represent the cardinality $k$ constraint?

# Answer
> 15 votes
It looks like you are trying to compute a **hypergraph transversal** of size $k$. That is, $\\{T\_1,\dots,T\_m\\}$ is your hypergraph, and $S$ is your transversal. A standard translation is to express the clauses as you have, and then translate the length restriction into a cardinality constraint.

So use your existing encoding, i.e., $\bigwedge\_{1 \le j \le m} \bigvee\_{i \in T\_j} x\_i$ and then add clauses encoding $\sum\_{1 \le i \le n} x\_i \le k$.

$\sum\_{1 \le i \le n} x\_i \le k$ is a cardinality constraint. There are various different cardinality constraint translations into SAT.

The simplest but rather large cardinality constraint translation is just $\bigwedge\_{X \subseteq \\{1,\dots,n\\}, |X| = k+1} \bigvee\_{i \in X} \neg x\_i$. In this way each disjunction represents the constraint $\neg \bigwedge\_{i \in X} x\_i$ - for all subsets $X$ of $\\{1,\dots,n\\}$ of size k+1. That is, we ensure that there is no way that more than k variables can be set. **Note that this is not polynomial size in $k$**

Some links to papers on more space-efficient cardinality constraint translations **which are polynomial size in $k$**:

If you are actually interested in solving such problems, perhaps it is better to formulate them as pseudo-boolean problems (see wiki article on pseudo-boolean problems) and use pseudo-boolean solvers (see pseudo-boolean competition). That way the cardinality constraints are just pseudo-boolean constraints and are part of the language - hopefully the pseudo-boolean solver then handles them directly and therefore more efficiently.

# Answer
> 7 votes
If you're not absolutely set on the normal SAT, your idea is already a reduction to MIN-ONES (over positive CNF formulae), which is basically SAT, but where you can set at most $k$ variables to true (strictly it's the optimization version where we minimize on the number of true variables).

Similarly if you head in a Parameterized Complexity direction, then you've already basically got WSAT($\Gamma\_{2,1}^{+}$), where $\Gamma\_{2,1}^{+}$ is the class of all positive CNF formulae (same as before, the notation might help your investigations though). In this case you'd have to start looking at what parameterization would be useful in your case.

I assume you're looking for an explicit reduction, but if not, you can always just fall back to the Cook-Levin Theorem.

---
Tags: complexity-theory, reductions, np-hard
---


title: NP-Completeness - Proof by Restriction

text:
# Question
Title: NP-Completeness - Proof by Restriction
I'm reading Garey & Johnsons *"Computers and Intractability"* and I'm at the part *"Some techniques for solving NP-Completeness"*. Here's the text about Proof by Restriction:

> Proof by restriction is the simplest, and perhaps most frequently applicable, of our three proof types. An NP-completeness proof by restriction for a given problem $L \in NP$ consists simply of showing that $L$ contains a known NP-complete problem $L'$ as a special case. The heart of such a proof lies in the specification of the additional restrictions to be placed on the instances of $L$ so that the resulting restricted problem will be identical to $L'$. We do not require that the restricted problem and the known NP-complete problem be exact duplicates of one another, but rather that there be an "obvious" one-to-one correspondence between their instances that preserves "yes" and "no" answers."

And I'm trying to learn this technique by example, but need some help.

(If you have the book, my example is on page 65, 27th printing)

They prove that *Multiprocessor Scheduling* is NP-complete with the following proof:

(Paraphrasing):

> Restrict to PARTITION by allowing only instances in which $m = 2$ and $D$ $=$ half the total sum of the "lengths".

Here $m$ is the number of processors and $D$ is the maximum allowed sum of "lengths" per processor.

This is obviously a special case of multiprocessor scheduling which is solvable by solving the PARTITION problem, and there's no confusion there.

But, I'm not sure why this proof holds.

Excerpt from above: *"The heart of such a proof lies in the specification of additional restrictions to be placed on the instances of $L$ so that the resulting restricted problem will be identical to $L'$ ".*

The way I see it that means we have to find the special case, and then find restrictions that show us that this problem can always be reduced to the special case. What we're trying to do here is show that Problem $A$ (MS) is at least as hard as Problem $B$ (PARTITION), so why would a simple special case be enough here? Is it because there's an obvious way to map to this special case that I'm missing? Or perhaps because $m = 1$ is trivial and we know that the problem will only get harder with a higher $m$, and that $D$ is always arbitrary, therefore $A$ must be at least as hard as $B$ (I feel like I'm just guessing now :p)

I hope it is clear where I get lost.

**TLDR; Why is it enough to find a special case that is solvable by an NP-Complete problem? Don't we need some reduction to complete the proof?**

# Answer
There is an implicit (trivial) reduction, from each instance of the restricted version to itself, really just relabelling it as an instance of the unrestricted problem.

To give an example that I think is more illuminating than Partition and Multiprocessor Scheduling, we can look at Vertex Cover and Hitting Set:

> **Vertex Cover**
> Input: A graph $G=(V,E)$, a positive integer $k$.
> Question: Is there a set $V'\subset V$ of size at most $k$ such that for every $uv \in E$ either $u\in V'$ or $v\in V'$ or both?
>
> **Hitting Set**
> Input: A hypergraph $H=(X,E)$, a positive integer $k$.
> Question: Is there a subset $X'\subseteq X$ of size at most $k$ such that for every $e \in E$ there exists an $x \in X'$ such that $x \in e$?

So we can easily see that Vertex Cover is just Hitting Set where the size of the edges is exactly two. As Vertex Cover is NP-hard (indeed, complete), Hitting Set must also be NP-hard. As Hitting Set is also in NP, it is therefore NP-complete.

So we have a "reduction" from Vertex Cover to Hitting Set, but it's just the identity mapping. The graph remains unchanged (as does $k$), we just call it a hypergraph, and call the edges hyperedges.

To think about it from the other end, if we have a problem $\Pi$ where a restricted subproblem $\Pi'$ is already NP-hard, and we had a PTIME algorithm for $\Pi$, then we could use it to solve all the instances of $\Pi'$ in polynomial time and hence everything in NP would have a polynomial time algorithm. Thus $\Pi$ must be NP-hard (and if $\Pi \in$ NP, NP-complete).
> 3 votes

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


# Question
Title: Mathematical model on which current computers are built
It is said that "The Turing machine is not intended as practical computing technology, but rather as a hypothetical device representing a computing machine. Turing machines help computer scientists understand the limits of mechanical computation." \[Wikipedia\]

So on which model current machines are built?

# Answer
The one closest to typical CPUs is probably the *register machine* or *random access machine* (RAM). A RAM has

* an infinite number of registers, each of which stores an arbitrarily large number,
* a set of operations on these registers (typically $\\{+ 1, = 0\\}$),
* a programming language including these operations as well as control structures for looping/branching (until/if some register holds $0$) and
* a program counter pointing to the next operation (in some program).

Real CPUs are quite similar, with some changes:

* There are only finitely many registers (which may exist only virtually), and each stores only numbers of bounded size.
* There are more operations.

Apart from that, it's very close indeed. It is common to extend the RAM model to account for memory hierarchy, which makes results a lot more applicable.
> 5 votes

# Answer
Von Neumann machine, and if you prefer something more mathematical, look instead at RAM machine.
> 3 votes

---
Tags: turing-machines, computer-architecture, machine-models
---


title: Equivalence of GFp and Gp in LTL

text:
# Question
Title: Equivalence of GFp and Gp in LTL
In linear time logic, is $\mathbf{GF}p$ equivalent to $ \mathbf{G}p$ ?

*$\mathbf{GF}p$ means that it is always the case that p is true eventually.*

Let $\mathbf{G} p$ be defined as: $\forall j \ge0,\ p$ holds in the suffix $q\_j, q\_{j+1}, q\_{j+2},\ldots$

and since: *formula $φ$ holds for state machine $M$ if $φ$ holds for all possible traces of $M$*

Isn't $\mathbf{G}$ in $\mathbf{GF}p$ redundant then?

# Answer
> 5 votes
No, not equivalent and not redundant.

Consider $p$ being true if and only if $j$ is even. $\mathbf{G}p$ is not true (obviously, since $p$ is false in every odd state), but $\mathbf{GF}p$ is always true.

---
Tags: logic, linear-temporal-logic
---


# Question
Title: BPP search: what does boosting correctness entail?
It is not really clear to me, how and if I can do boosting for correctness (or error reduction) on a BPP (bounded-error probabilistic polynomial-time) search problem. Can anyone of you explain me how it works?

With BPP search, I mean a problem that can have false positive-negative, correct solution, and no-solution. Here's a definition:

A probabilistic polynomial-time algorithm $A$ solves the search problem of the relation $R$ if

* for every $x ∈ S$, $Pr\[A(x) ∈ R(x)\] \> 1 - μ(|x|)$
* for every $x ∉ SR$, $Pr\[A(x) = \text{no-solution}\] \> 1 - μ(|x|)$

were $R(x)$ is the set of solution for the problem and $μ(|x|)$ is a negligible function (it is rare that it fails).

So now I would like to increase my probability of getting a good answer, how can I do it?

---

~ ".. boosting for correctness.." : a way to increase the probability of the algorithm (generally by multile runs of the probabilistic algorithm), i.e., when the problem have a solution then the algorithm likely return a valid one.

# Answer
> 4 votes
If the relation $R$ lies in the complexity class P (or even BPP), then boosting works by running your algorithm many times, and testing whether its output satisfies $R$. When $x \in S$, this fails with probability $\mu^N$, where $N$ is the number of times you run $A$. When $x \notin S$, this never fails. This way you can boost $\mu$ from $1-1/\mathrm{poly}(n)$ to $2^{-\mathrm{poly}(n)}$.

Edit: if $R$ is in BPP rather than P, with constant error probability $\mu$, then this approach doesn't work. You can decide whether $x \in S$ or not using the usual majority trick, but if $x \in S$, it's not clear how you'd find a correct witness whp.

---
Tags: probabilistic-algorithms, search-problem
---