# Question
Title: Provide some help regarding the "Dining Philosophers Problem"?
I have an assignment based on operating systems and the question is divided into two sub-questions.

The first is: Prove any seating arrangement of lefties and righties, with at least one of each avoiding deadlock.

The second: Prove any seating arrangement of lefties and righties with at least one of each avoiding starvation.

I understand the concept behind this problem and that I can use semaphores, or monitors etc. but the resources I have found online mainly explain in coding, but I need help understanding which is the best way to answer this question in theory by choosing one of the ways to prevent deadlock and starvation.

# Answer
Righties: will never try to acquire the left fork before they have the right one.

Lefties: will never try to acquire the right fork before they have the left one.

**Deadlock:** Assume that you reached deadlock, this means that none of the philosophers can eat (so each philosopher holds at most one fork, and cannot pick up the other one). Sine you have both righties and lefties, there exists two adjacent philosophers with opposite orientation, lets denote them by $p\_r,p\_l$. Notice that $p\_r,p\_l$ cannot pick up any forks, if one of them holds the fork in between, $f\_{p\_r,p\_l}$ , then it means he already got the other fork, since $f\_{p\_r,p\_l}$ lies right to the leftie $p\_l$ and left to the rightie $p\_r$. So $f\_{p\_r,p\_l}$ is available, and thus if $p\_r$ or $p\_l$ can pick up the other fork, they can pick up $f\_{p\_r,p\_l}$ and eat, contradicting deadlock. $p\_l$ cannot pick up the fork to his left, hence (because the system is in deadlock) the philosopher left to $p\_l$ is a rightie, and already picked up the fork to his right (or to $p\_l$'s left). Let us denote the $k'th$ neighbor to $p\_l$ from the left by $p\_l^k$, so we have shown $p\_l^1$ is a rightie and owns the fork to his right. $p\_l^2$ (left neighbor of $p\_l^1$) must also be a rightie and own his right fork, otherwise either he or $p\_l^1$ can eat. It is easy to see (by induction) that for all $k$, $p\_l^k$ is a rightie owning his right hand fork. however $p\_r=p\_l^{n-1}$ (where $n$ is the number of philosophers), so $p\_r$ is a rightie owning his right fork, contradicting the fact that $p\_r,p\_l$ do not own any forks.

This is illustrated in the following figure. Red squares are forks, arrow from a philosopher to a fork indicates that he is waiting to use this fork (not ownership). All philosophers left of $p\_l$ are righties waiting to use their left fork (already owning their right one). This goes on until you reach $p\_r$, who you know is waiting for his right fork and not the left one (which leads to contradiction).

**Starvation:** Starvation means that there exists a philosopher which is stuck waiting to eat. Suppose that some right hand philosopher $p\_r$ is stuck waiting to pick up his right fork (the proof is very similar in case he's waiting for his left). Let us denote by $p\_r^k$ the k'th neighbor of $p\_r$ to the right. We know that the protocol is deadlock free, so there exists minimal $m$ such that $p\_r^m$ is eating. We can see by induction that all $p\_r^{j}$ for $j\<m$ are lefties holding their left fork. This is clear for $p\_r^1$ (otherwise $p\_r^1$ would be either eating or leaving the fork right of $p\_r$ available, in any case $p\_r$ will eventually be able to pick up the fork to his right). Suppose $j,j+1\<m$ and $p\_r^j$ is a leftie holding his left fork. Since both $p\_r^j,p\_r^{j+1}$ are not eating (by minimality of $m$), $p\_r^{j+1}$ is a leftie holding his left fork. When $p\_r^m$ is done eating, $p\_r^{m-1}$ will be able to pick his right fork and eat, when he's done $p\_r^{m-2}$ will be able to pick his right fork and eat,... Finally, $p\_r^1$ will be done eating, allowing $p\_r$ to pick his right fork, contradicting the fact that he is stuck.
> 4 votes

---
Tags: operating-systems, synchronization, deadlocks
---


# Question
Title: Equivalence in finite sets of turing machines
I have this exercise and I really don't know how to complete it:

```
Prove that for all finite sets S of Turing Machines it is decidable
whether or not given any two Turing Machines M1 and M2 in S they
recognize the same language, that is, L(M1)=L(M2)

```

I know that the problem of equivalence of languages is undecidable in general, but the additional hypothesis of the finiteness of the set S of machines does not suggest me any reason why this case should be different. Can somebody help me?

# Answer
> 3 votes
Hint: Since $S$ is finite, there are finitely many legal queries, and we can hardcode the answers to all of them.

---
Tags: formal-languages, turing-machines, formal-grammars
---


title: what does term "emit" in compiler mean?

text:
# Question
Title: what does term "emit" in compiler mean?
In lots of textbooks and papers, authors often state: compiler emits ...

I want to know why they prefer to use emit? (not return, not produce)

Does this have anything to do with the emitter of a compiler?

thanks

# Answer
It is mostly used in the sense of "writing instructions to the program being built". Note that what is being "emitted" might still be massaged before ending up in the compiler output.
> 5 votes

---
Tags: terminology
---


# Question
Title: Automated optimization of 0-1 matrix vector multiplication
**Question:**

Is there established procedure or theory for generating code that efficiently applies a matrix-vector multiplication, when the matrix is dense and filled with only zeros and ones? Ideally, the optimized code would make systematic use of previously computed information to reduce duplicated work.

In other words, I have a matrix $M$ and I want to do some precomputation based upon $M$, that will make computing $Mv$ as efficient as possible when I later receive the vector $v$.

$M$ is a rectangular dense binary matrix that is known at "compile time", whereas $v$ is an unknown real vector that is only known at "run time".

**Example 1: (sliding window)**

Let me use an easy small example to illustrate my point. Consider the matrix, $$M = \begin{bmatrix}1 & 1 & 1 & 1 & 1\\ & 1 & 1 & 1 & 1 & 1 \\ & & 1 & 1 & 1 & 1 & 1\\ & & & 1 & 1 & 1 & 1 & 1\end{bmatrix}.$$ Supposing we apply this matrix to a vector $v$ to get $w = Mv$. Then the entries of the result are, \begin{align} w\_1 &= v\_1 + v\_2 + v\_3 + v\_4 + v\_5\\ w\_2 &= v\_2 + v\_3 + v\_4 + v\_5 + v\_6\\ w\_3 &= v\_3 + v\_4 + v\_5 + v\_6 + v\_7\\ w\_4 &= v\_4 + v\_5 + v\_6 + v\_7 + v\_8 \end{align}

Doing a standard matrix-vector multiplication will compute exactly this way. However, a lot of this work is redundant. We could do the same matrix computation at less cost by keeping track of a "running total", and adding/subtracting to get the next number: \begin{align} w\_1 &= v\_1 + v\_2 + v\_3 + v\_4 + v\_5\\ w\_2 &= w\_1 + v\_6 - v\_1\\ w\_3 &= w\_2 + v\_7 - v\_2\\ w\_4 &= w\_3 + v\_8 - v\_3 \end{align}

**Example 2: (hierarchical structure)**

In the previous example, we could just keep track of a running total. However, usually one would need to create and store a tree of intermediate results. For example, consider $$M = \begin{bmatrix}1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 \\ & & & & 1 & 1 & 1 & 1\\ 1 & 1 \\ & & & & 1 & 1 \\ & & 1 & 1 \\ & & & & & & 1 & 1\end{bmatrix}$$ One could compute $w = Mv$ efficiently using a tree of intermediate results:

1. Compute $w\_5$ and $w\_7$, and add them to get $w\_3$.
2. Compute $w\_4$ and $w\_6$, and add them to get $w\_2$.
3. Add $w\_2$ and $w\_3$ to get $w\_1$

The structure in the examples above is easy to see, but for the actual matrices I'm interested in, the structure is not so simple.

**Example 3: (low rank)**

To clear up some confusion, the matrices are generally not sparse. Specifically, a method solving this problem needs to be able to find efficient methods to apply matrices where large blocks are filled with ones. For example, consider

$$M = \begin{bmatrix}1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & & \\ 1 & 1 & 1 & 1 & & \\ 1 & 1 & 1 & 1 & & \end{bmatrix}.$$

This matrix can be decomposed as a difference of two rank-1 matrices, $$M = \begin{bmatrix}1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1\end{bmatrix} - \begin{bmatrix}& & & & & \\ & & & & & \\ & & & & 1 & 1 \\ & & & & 1 & 1 \\ & & & & 1 & 1\end{bmatrix}$$

so its action on a vector $w := Mv$ can be computed efficiently by, \begin{align} w\_1 &= v\_1 + v\_2 + v\_3 + v\_4 + v\_5 + v\_6 \\ w\_2 &= w\_1 \\ w\_3 &= w\_2 - v\_5 - v\_6 \\ w\_4 &= w\_3 \\ w\_5 &= w\_4. \end{align}

**Motivation:**

I'm working on a numerical method for some image processing, and there are several large dense $0-1$ matrices with different structures that are fixed for all time. Later these matrices will need to be applied to many unknown vectors $v\_i$ that will depend on the user's input. Right now I'm using pencil-and-paper to come up with efficient code on a per-matrix basis, but I'm wondering if the process can be automated.

***Edit: (postscript)***

All of the answers here so far (as of 9/5/15) are interesting, but none answer the question as satisfactorily as I had hoped. Probably it turns out that this is a hard research question, and no one knows a good answer.

Since time has run out I am awarding the bounty to EvilJS's answer since it addresses the right question. However, I wish the answer contained more clear and detailed explanations.

tranisstor's answer makes a connection between this question and the Online Boolean Matrix-Vector Multiplication (OMv) problem, but the connection is not exactly what this question is asking. In particular, the following assumption doesn't really fit (bold emphasis mine),

> Now assume that **for all $n \leq n\_0$ and all $n \times n$ matrices $M$** we know an algorithm $A\_{n,M}$, that for all vectors $v$ computes $Mv$ in truly subquadratic time, i.e. in time $O(n^{2 - \varepsilon})$ for some $\varepsilon \> 0$.

Whether or not there exist subquadratic algorithms for all matrices is orthogonal to the question of finding an algorithm for a specific matrix that is as fast as possible. Most 0-1 matrices look like random noise and (if I were to guess) probably don't have subquadratic algorithms. However, the fact that there are really bad matrices out there doesn't prevent me from finding a fast algorithm on a good matrix, for example, a "sliding window" matrix.

vzn's answers, first answer, second answer are interesting (and in my opinion don't deserve so many downvotes), but they don't apply to the question for reasons discussed in the comments there.

# Answer
If it is possible try to exploit banded tridiagonal nature of matrix.
Otherwise if the matrix contains only a constant number of distinct values (which surely is being binary), you should try Mailman algorithm (by Edo Liberty, Steven W. Zucker In Yale university technical report #1402): optimized over finite dictionary
Common Subexpression Elimination is know for some time like Multiple Constant Multiplication, but going down to gate-level is an option - patterns used here could be used separately as solution or merged with other methods, the paper for this "Improving Common Sub-expression Elimination Algorithm with A New Gate-Level Delay Computing Method" by Ning Wu, Xiaoqiang Zhang, Yunfei Ye, and Lidong Lan published in "Proceedings of the World Congress on Engineering and Computer Science 2013 Vol II WCECS 2013, 23-25 October, 2013, San Francisco, USA" Gate level CSE

There is also crude but working method, to generate symbolic matrix with constants, vector with variables and plug it to Static Single Assingment (SSA) from compilers, which automates process of writing matrices by hand.

**new algorithm prototype**
What you did with running sum: \begin{align} w\_1 &= v\_1 + v\_2 + v\_3 + v\_4 + v\_5 \\ w\_2 &= w\_1 + v\_6 - v\_1 \\ w\_3 &= w\_2 + v\_7 - v\_2 \\ w\_4 &= w\_3 + v\_8 - v\_3 \end{align}
Gives 10 *operations*, and with my initial idea to use Thomas it is equivalent.
For now I am still writing and testing new algorithm, also runtimes are **nasty**, but first test result gave me surprising answer:

\begin{align} tmp\_1 &= v\_2 + v\_3 + v\_4 + v\_5 \\ w\_1 &= v\_1 + tmp\_1 \\ w\_2 &= tmp\_1 + v\_6 \\ w\_3 &= w\_2 + v\_7 - v\_2 \\ w\_4 &= w\_3 + v\_8 - v\_3 \end{align}
Which gives 9 *operations*, defining them as + or - is 1, and = is 0.

\begin{align} w\_1 &= v\_1 + v\_2 + v\_3 + v\_4 + v\_5 + v\_6 \\ w\_2 &= w\_1 \\ w\_3 &= w\_2 - v\_5 - v\_6 \\ w\_4 &= w\_3 \\ w\_5 &= w\_4. \end{align}

This gives 7 *operations*, my algorithm result gave:
\begin{align} tmp\_1 &= v\_1 + v\_2 + v\_3 + v\_4 \\ tmp\_2 &= v\_5 + v\_6 \\ w\_1 &= tmp\_1 + tmp\_2 \\ w\_2 &= w\_1 \\ w\_3 &= w\_2 - tmp\_2 \\ w\_4 &= w\_3 \\ w\_5 &= w\_4. \end{align}
Which gives 6 *operations* For now I can tell that I am using Hamming distance, & and | bitwise operations, counting usages and making something like Cocke–Younger–Kasami (CYK) - "a parsing algorithm for context-free grammars, named after its inventors, John Cocke, Daniel Younger and Tadao Kasami. It employs bottom-up parsing and dynamic programming." - from Wikipedia This is the same technique I use to build blocks of variables.
> 5 votes

# Answer
This is related to an open research question, which is known as the "Online Boolean Matrix-Vector Multiplication (OMv) problem". This problem reads as follows (see \[1\]): Given a binary $n \times n$ matrix $M$ and $n$ binary column vectors $v\_1, \dots, v\_n$, we need to compute $M v\_i$ before $v\_{i+1}$ arrives.

Notice that the problem from the question is somewhat more general: It allows for $m \times n$ matrices and real-valued vectors. Observe that the problem with $n \times n$ matrices and Boolean vectors is "easier", as it presents a special case.

Clearly, the naïve algorithm for the Online Boolean Matrix-Vector Multiplication problem (which just uses standard matrix-vector-multipliction) takes time $O(n^3)$. There is a conjecture (see e.g. \[1\]) that this cannot be done truly faster than $O(n^3)$. (In more detail, this conjecture goes as follows: There exists no truly subcubic algorithm, which solves the Online Boolean Matrix-Vector Multiplication Problem, i.e. there is no algorithm with running time $O(n^{3 - \varepsilon})$ for $\varepsilon \> 0$).

It is known that Williams's algorithm solves this problem in time $O(n^3 / \log^2 n)$. See \[2\] for more details.

It would be a breakthrough in the area of conditional lower bounds, if one could prove or disprove the above conjecture.

\[1\] Unifying and Strengthening Hardness for Dynamic Problems via an Online Matrix-Vector Multiplication Conjecture. by Henzinger, Krinninger, Nanongkai and Saranurak
\[ http://eprints.cs.univie.ac.at/4351/1/OMv\_conjecture.pdf \]

\[2\] Matrix-vector multiplication in sub-quadratic time: (some preprocessing required). by Williams
\[ http://dl.acm.org/citation.cfm?id=1283383.1283490 \]

**Update**

One of the questions in the comments was as follows: We know $M$ at compile time. Can't we adjust our algorithm to suit $M$, so the OMv problem (conjecture) does not apply? We will see that this is not the case, unless the OMv conjecture fails.

The proof idea is simple: Assume we could give fast algorithms for all matrices up to some certain size (e.g. distinguishing all possible cases). After this certain size we use divide and conquer.

Here are the details:
Fix some $n\_0 \in \mathbb{N}$, which (without loss of generality) is a power of 2 and bigger than 2. Now assume that for all $n \leq n\_0$ and all $n \times n$ matrices $M$ we know an algorithm $A\_{n,M}$, that for all vectors $v$ computes $Mv$ in truly subquadratic time, i.e. in time $O(n^{2 - \varepsilon})$ for some $\varepsilon \> 0$. (Notice that this allows an individual algorithm for each matrix up to size $n\_0 \times n\_0$.)

Now we will solve OMv in truly subcubic time:
Given a binary matrix $M$ of size $n \times n$, where $n = 2^k$ for some $k$ and $n \> n\_0$, we use a divide and conquer strategy. We divide $M$ into four submatrices $M\_1, M\_2, M\_3, M\_4$ of sizes $2^{k-1} \times 2^{k-1}$. If $2^{k-1} \leq n\_0$, then we use algorithm $A\_{2^{k-1},M\_i}$, otherwise, we recurse. (As $n\_0$ is some fixed number, we can pick the correct algorithm in constant time.)

Notice that we will need at most $O(\log n)$ recursion steps. Also, for $n$ vectors $v\_1, \dots, v\_n$, we will $n$ computations. Thus, to process all matrix-vector multiplications we will need a total computation time of $O(n^{3 - \varepsilon} \log n)$.

It is well known that the logarithm grows slower than any polynomial (in particular slower than any root). Fixing some $\tilde \varepsilon \> 0$ with $\tilde \varepsilon \< \varepsilon$, we see that our total computation is running in truly subcubic time (in particular, in time $O(n^{3 - \tilde \varepsilon})$). Thus, the OMv conjecture would be wrong.

(If $M$ has size $m \times n$ and $m$ and $n$ are not powers of 2, then the bounds on the running times still apply, as we could just increase $n$ and $m$ to the next powers of 2.)

Conclusion: If you could make use of case distinctions on the input matrices to derive fast algorithms, then you could improve the OMv conjecture.
> 8 votes

# Answer
this is essentially research-level CS, the problem is studied in at least two guises, one of multiplication of sparse matrices (example paper just cited), and also the special case of "binary sparse matrices" is also studied. the 2nd case is known to be related to optimizing straight-line programs. minimal programs may also be like DAGs with two types of "gates", addition and multiplication, so some circuit minimization literature may connect with this, and possibly "off the shelf" software could be adapted for the purpose. here is a specific ref on the 2nd case and also the same question on cstheory with some basic initial empirical study.
> -2 votes

# Answer
not sure if this problem has been studied exactly but this research is related & seems a reasonable lead/ start. it looks at hypergraph decomposition for sparse matrix multiplication. binary matrices are a special case of this approach. this approach will find more optimal strategies than the "straight" multiplication method. further optimizations (within this framework) might be possible based on the binary matrix property.
> -3 votes

---
Tags: linear-algebra, matrices, program-optimization
---


title: recursive function as circular funciton

text:
# Question
Title: recursive function as circular funciton
I recently learnt that a recursive function is also referred to as a circular function.

See, the recursive function cannot be a circular function because even if there is a call to function itself, it does not happen indefinitely. There is always a base case (or condition) from where the function is supposed to exit in one way or the other (either by displaying some message or returning some value).

So, is calling recursive function, a circular function not a misnomer ?

# Answer
I agree that it's a misnomer. Consensus from the comments seems to be that "circular function" is not a commonly used term for a recursive function. I think the person you saw using the term was using the wrong word, perhaps because of translation issues.
> 3 votes

---
Tags: terminology
---


title: Recurrence Relation(with Square root)

text:
# Question
Title: Recurrence Relation(with Square root)
I came across a very peculiar recurrence relation :

> $\sqrt {T(n)} = \sqrt {T(n-1)} + 2 \sqrt {T(n-2)} $

with initial values $T(0) = T(1) = 1$

Any helps on how to find it

# Answer
Let $f(n)=\sqrt{T(n)}$, $f$ satisfies the linear recurrence relation $f(n)=f(n-1)+2f(n-2)$. The characteristic polynomial is $x^2-x-2$ and it's roots are $-1,2$, so $f(n)$ is a linear combination of $(-1)^n,2^n$. After substituting the initial conditions you get $f(n)=\frac{1}{3}(-1)^n+\frac{2}{3}2^n$.
> 6 votes

---
Tags: recurrence-relation, discrete-mathematics
---


# Question
Title: Does a reentrant list for signal queue in a single-thread environment exist?
I need to handle Unix signals in a single-threaded application with the following goals:

1. Signals doesn't mask on receive (thus, the signal handler *must* be reentrant).
2. I am not allowed to lose signal data (thus, if a new signal comes before the handler of the previous returned, it also must be handled correctly).

I have the common multi-threaded primitives (spinlocks, semaphores, etc). But they doesn't seem enough, because my higher-level data structures (even a such simple as a list) aren't thread-safe.

My initial idea was the following:

1. I use a *list*, in which I store the data of the incoming signal fast,
2. and process them (call the possibily much slower running handlers) later, out of the critical section.

The main problem with that, that the list data structure isn't thread safe. If I lock it, I can't store a second signal anywhere. I can't wait until the previous handler exits, because on the second signal it is essentially suspended in a critical section.

Simply I don't have any idea, how to handle the following scenario:

1. *signal1* comes, the process suspends, and the handler of *signal1* starts
2. *signal2* comes, the handler of *signal1* suspends, and the handler of *signal2* starts
3. Handler of *signal2* returns, execution returns to the handler *signal1*
4. Handler of *signal1* returns, execution returns to the main program.

After thinking a lot on it, I have an impression, maybe my problem is unsolvable. Am I right? How do operating systems handle similar problems (for example, possibily bursting interrupts from hardware)?

# Answer
Finally I found a solution, which handles the whole problem at once. It is relatively easy. They key to the solution: *we can use the signal stack as a "to-do stack"*.

Important to remember, that although this problem is also about race condition eliminiation, its solution differs significantly from the "lock everything what you use, do your task, release everything" solutions. It is because *it is not about parallelisation*, it is about *reentrancy*. The common lock-based solutions would lead to deadlock here, because the parent (in the example) *signal1* handler will be surely suspended while the whole execution of the handler of *signal2*.

So, this is a disadvantage, but it is an advantage as well. We can *guarantee*, that *signal1* won't do anything while our *signal2* runs. We can't simply lock things, but we also don't need to do them.

So, that blocking locks are closed out, only the nonblocking locks left. What I invented, is the following C code:

```
#define STORE(a, b) __atomic_store(&(a), &(b), __ATOMIC_SEQ_CST)
#define SWAP(a, b) __atomic_exchange(&(a), &(b), &(b), __ATOMIC_SEQ_CST)

// action handler wrapper
void ss_wrapper(int signum, siginfo_t* siginfo, ucontext_t* ucontext) {
  // currently top element on the signal stack
  static struct ss_hit *top = NULL;

  struct ss_hit *hit = ss_hit_new(signum, siginfo, ucontext);
  struct ss_hit *bkp;

  again:

  bkp = hit;
  SWAP(top, hit);
  if (!hit) { // we got the lock, we are the master
    ss_fire(bkp);
    SWAP(top, &bkp->next); // release the lock, find out if there is new element
    if (bkp->nxt) { // there IS

      hit = bkp;
      free(bkp);
      goto again;

    } else
      free(bkp);
  } else { // we didn't got the lock, but we got the top in hit
    STORE(hit->next, bkp);
  }
}

```

As we can see, it had been very beautiful to have a separated, reentrant stack (and not list) data structure.

The main problem was to understood, that

* adding new element in the stack, AND testing if it is empty, they should be done in a single atomic operation (this is why `top` serves as both of spinlock and pointer to the top of the stack)
* similarly, removing element from the stack, and to know, if it is now empty, should be done also atomically.

I also learned from this some days of thinking, that * constructing reentrant algorithm is *much* harder as to contrust a multithread * the most important thing is that reentrant algos should have only *very* *few* variables to interact eachother through them, and *all* operation should be atomic on them.
> 0 votes

---
Tags: data-structures, threads, deadlocks
---


# Question
Title: What is the difference of temporal dynamics in RNNs and the NEF
Both spiking neural networks created with the Neural Engineering Framework (NEF) and Recurrent Neural Networks (RNNs) can be connected recurrently to exhibit neural dynamics. What is the difference between the set of dynamics that they can approximate and/or exhibit?

# Answer
> 2 votes
There can be a lot of different ways in which recurrent neural networks can be used. RNNs can have any activation function (logistic sigmoid is most commonly used), and they can be multilayer. There are different algorithms which can be used to train them e.g., backpropagaion and different optimization techniques e.g., hessian free optimization which can be used to optimize the networks for a particular problem.

NEF has been used for simple recurrent connections (for implementing memory circuit), however, we need to do some work and try out multi-layer networks in order to truly figure out what the differences in dynamics would be.

We have also tried hopfield networks with pre-calculated weight matrices, and using sigmoid neurons and were able to achieve similar dynamics forming attractors. However, implementing hopfiled with dynamic learning of weight matrices is something which needs to be tried out.

I suspect that using sigmoid activation functions in NEF and applying the same learning algorithms should give results very similar to RNNs (there might be some differences caused by synaptic filtering). However, if one uses an LIF curve as an activation function, then there is a possibility of greater differences.

---
Tags: neural-networks
---


# Question
Title: Does removal of unit production from the grammar may increase number of total production?
There are m variable in a grammar. The number of productions after removal of unit productions in the worst case is ,(Assume there are no null productions)

(a) O(m)
(b) O($m^2$)

(c) O($k^m$)

(d) O($2^m$)

---

My attempt:

He asked about number of total production remains in the minimized grammar , so , if the there is no null production , it is advantage , as you know when we convert a grammar without null production , generally , removal of all production introduces new production in the resultant grammar (it can be upto set of all subset of given max RHS number of variable , so exponetial ) .

But , in given grammar , you don't have null production , so you are removing only unit production (i.e. A---\>B type productions ) , resultant grammar maximum 'm' production , where m is number of variable . example :- S----\>A A----\>B B----\>a/b/c resultant grammar , S----\>a/b/c So , it is O(m) time .

> Can you explain in formal way, please?

# Answer
Hint: Consider the grammar $$S \to \overbrace{X\cdots X}^{\text{$n$ times}} \\ X\to a|b$$ What happens when you remove unit productions?
> 3 votes

---
Tags: context-free, formal-grammars, normal-forms
---


title: Bottleneck TSP with MST

text:
# Question
Title: Bottleneck TSP with MST
There is a problem I don't know the answer too. The 3 approximation for the bottleneck TSP that involves first getting the MST. I have not been able to come up with the right "shortcut" method so far.

To be more specific.

The problem comes from Cormen's Introduction to Algorithms 3rd edition . The problem is

> In the bottleneck traveling-salesman problem, we wish to find the hamiltonian cycle that minimizes the cost of the most costly edge in the cycle. Assuming that the cost function satisfies the triangle inequality, show that there exists a polynomial time approximation algorithm with approximation ratio 3 for this problem. (Hint:Show recursively that we can visit all the nodes in a bottleneck spanning tree, as discussed in Problem 23-3, exactly once by taking a full walk of the tree and skipping nodes, but without skipping more than two consecutive intermediate nodes. Show that the costliest edge in a bottleneck spanning tree has a cost that is at most the cost of the costliest edge in a bottleneck hamiltonian cycle.)

I can prove that the MST is also a bottleneck spanning tree, however when I search online and Google scholar for the step where we walk on the bottleneck spanning tree, all of the articles are on much better approximations, and I can't seem to find any reference to this type of argument online.

# Answer
You need to prove by induction the following claim:

> Let $T$ be a tree rooted at $r$ with at least two vertices. You can list the vertices of $T$ in a sequence such that the distance (in $T$) between two adjacent vertices (including the first and the last) is at most $3$, and furthermore the vertex following $r$ is adjacent to $r$ (in $T$).

(The induction is on the number of vertices.)

Given this, you argue as follows. Suppose that there is a Hamiltonian cycle with heaviest edge having weight $w$. Then there is a spanning tree whose heaviest edge has weight $w$. So the heaviest edge in the bottleneck spanning tree has weight at most $w$. Apply the claim to that tree, and consider the corresponding Hamiltonian cycle. Since the tree distance between adjacent vertices is at most $3$ and thanks to the triangle inequality, the heaviest edge in the resulting cycles weighs at most $3w$.
> 1 votes

---
Tags: complexity-theory, graphs, approximation, traveling-salesman, minimum-spanning-tree
---


# Question
Title: Understanding the one-writer, many-readers problem?
I need some help understanding the implementation of the one-writer many-readers problem shown below as I am new to this concept:

I have a rough idea that there will be starvation/deadlock among the readers as there is one writer that multiple readers are trying to access at once. Can anyone please provide some further insight regarding the problems with the implementation of this situation?

I am not looking for any coding, that was just the sample code (pseudocode) I am working with. I am looking for the problem of the implementation. Upon further research I have assumed the following (based on the line: `if readcount == 1 then semWait(wrt);` :

* There is one writer and many readers
* The readers have priority over the writers
* The possible problem: The writers cannot write until the reader has finished reading therefore starvation occurs

However upon re-evaluation of the code I have also assumed the following based on the lines:

```
semWait(mutex);
readcount := readcount - 1;
if readcount == 0 then up
semSignal(mutex);

```

Could I not also say that only one reader may read at a time therefore the other readers will be starved?

Therefore would either of these be the correct way of interpreting the coding to the problem is of the implementation or would I be wrong?

# Answer
First,I would suggest (in the future as well) to write the pseudocode yourself (the commands for the readers/writers), It will be cleaner and easier to read than the image. Also, i would suggest briefly explaining the semantics of your operations (wait/signal/up, since you used all three in the code).

To your answer, readers not being able to read simultaneously does not mean starvation, although simultaneous reading ability is an additional requirement, at least in the classical formulation of the problem (moreover, readers can read simultaneously in this protocol). Starvation means that there exists a process stuck waiting while other processes share the resource (if one reader $r\_1$ has to wait until $r\_2$ is done, then he might read after $r\_2$, who eventually will be done reading, so $r\_1$ is not stuck).

This protocol (as it seems to me) is the same as the one described here (under First readers-writers problem). It is easy to see (as mentioned in the link) that writers can be starved here. Suppose $r\_1,r\_2$ are reading at the same time, so the count is $2$. Imagine a scenario where whenever $r\_1,r\_2$ read together, the first to finish (and decrements the counter to $1$) immediately requests reading again (so the counter is back to $2$). This way the counter will never reach $0$ and the writer will be starved (stuck waiting).
> 2 votes

---
Tags: concurrency, synchronization
---


# Question
Title: How Can we make $O(N)$ order statistic queries with Fibonacci heap in $O(N)$?
We have a Fibonacci heap with $N$ unique elements we want to make $O(N)$ order statistic queries (e.g., what is the element number 7 in this collection if it was sorted). Moreover, we know that the order statistic queries would be made in order (e.g., for $O(N)$ queries: what is elements number $1,3,5,\ldots,N$) .

How can we do it in $O(N)$ time ? We can't change the data structure in any way.

My thoughts: 1)The naive way is just to do delete min $N$ times but it would take $O(N \log N)$ so its not good enough.

2) if we could somehow use increase-key (if its min heap or decrease-key if its max heap) we would be able do find min in constant time increase its key so its larger than anything else in the heap we could avoid delete-min and its amortized bound of $O(log(n))$ entirely, but we are not allowed to modify the data-structure .

EDIT: sorry i didn't make it clear the heap don't have trees that waiting to be melded , otherwise its not possible since the heap could have N degree 0 trees and we cant sort N items in $O(N)$ time.

# Answer
Well, you can build a Fibonacci heap in $O(N)$ time. Assuming you will get the proposed order statistic also in $O(N)$ time for the index set $\\{1,2,3,\ldots,N\\}$, then we can sort the stored set in linear time.

You probably know that (comparision based) sorting takes $\Omega(N \log N)$ time. Since you have no information about the universe of your elements you cannot use tricks like bucket sort or sorting on the word ram to get a linear time sorting algorithm. So you can't solve your problem in $O(N)$ time.
> 3 votes

---
Tags: data-structures
---


# Question
Title: give potential function - binary heap - extract-min in amortized const time and insert in log amortized time
Consider an ordinary binary min-heap data structure with n elements supporting the instructions INSERT and EXTRACT-MIN in O($\lg n)$ worst-case time. Give a potential function $\Phi$ such that the amortized cost of INSERT is $O(\lg n)$ and the amortized cost of EXTRACT-MIN is $O(1)$.

I try to solve it, but I got in stuck:

**Attempt**
Let $c\_i$ denotes real cost of $i-th$ operation, and $a\_i$ denotes amortized cost.
Let $\Phi(D\_i) = \text{number of elements after i operations}$
INSERT:$$a\_i=c\_i+ \Phi(D\_i) - \Phi(D\_{i-1}) \le \log(i) + (i)\log(i) - (i-1)\log(i-1) \le 3\log(i+1) = O(\log(i))$$
EXCTRACT-MIN:$$ a\_i=c\_i + \Phi(D\_i) - \Phi(D\_{i-1}) \le \log(i) + i\log(i) - (i+1)\log(i+1) =\log(i) + i\log(i) - i\log(i+1) - \log(i+1) \< 0 $$

As you can see, my problem is that I get number lower than $0$. Can you help me ?

# Answer
Let's review the potential function method. Suppose that the $i$th operation costs $c\_i$ and the value of the potential function at time $i$ is $\Phi\_i \geq 0$, and that $\Phi\_0 = 0$ (the potential at the beginning). Define the amortized operation costs by $a\_i = c\_i + \Phi\_i - \Phi\_{i-1}$. Then $$ \sum\_{i=1}^n a\_i = \sum\_{i=1}^n (c\_i + \Phi\_i - \Phi\_{i-1}) = \sum\_{i=1}^n c\_i + \Phi\_n - \Phi\_0 \geq \sum\_{i=1}^n c\_i. $$ This means that the total amortized cost $\sum\_{i=1}^n a\_i$ is an upper bound on the actual cost $\sum\_{i=1}^n c\_i$, which is what we want.

In this argument there is no need to assume that the amortized costs are non-negative – the argument works even if they can be negative. However, if some amortized costs are negative, then you can probably improve the amortized analysis.

Back to your case. Suppose that inserting the $n$ element costs $\log n$, and extracting the minimum when there are $n$ elements also costs $\log n$. This suggests a charging argument in which we charge the insertion of the $n$th element by $2\log n$, and discharge the extra $\log n$ when extracting the minimum the next time that there are exactly $n$ elements. This gives an amortized time of $O(\log n)$ for insertion, and $0$ for extract-min.

We can give a similar argument using a potential function. We choose a potential function of the form $\sum\_{i=1}^n \log i$, where $n$ is the current number of elements. Under this potential function, insertion costs $2\log n$ and extract-min costs $0$.

Note that $\sum\_{i=1}^n \log i = \log n! \approx n\log n$, so this differs from your suggestion (appearing in the comments) of using $n$ as a potential function; your suggestion doesn't work, since under it extract-min costs $$ \log n + n - (n-1) = \log n - 1. $$ Taking a closer look at your question, you are actually using the potential function $n\log n$, which is very similar to what I suggest. This potential function does work.
> 4 votes

---
Tags: amortized-analysis
---


# Question
Title: undecidable problem and its negation is undecidable
A lot of "famous" undecidable problems are nonetheless at least semidecidable, with their complement being undecidable. One example above all can be the halting problem and its complement.

However, can anybody give me an example in which both a problem and its complement are undecidable and not semidecidable? I thought about the diagonalization language Ld, but it does not seem to me that the complement is undecidable.

In that case, does that mean that a Turing Machine M can "lose" some strings that instead should be recognized, since they're part of the language we're trying to indentify?

# Answer
Consider the following language:

$$L\_2 = \\{(M\_1,x\_1,M\_2,x\_2) : \text{$M\_1$ halts on input $x\_1$ and $M\_2$ doesn't halt on input $x\_2$}\\}.$$

$L\_2$ is undecidable and not semi-decidable, and same is true of its complement. Why? The intuition is "$M\_2$ doesn't halt on input $x\_2$" isn't semi-decidable, so $L\_2$ is not semi-decidable; and when you look at the complement of $L\_2$, the same thing happens for $M\_1$. This can be formalized more carefully using reductions.

More generally, if $L$ is a language that is undecidable and not semi-decidable, then

$$L' = \\{(x,y) : x \in L, y \notin L\\}$$

meets your requirements: $L'$ is undecidable and not semi-decidable, and the same is true of the complement of $L'$.
> 15 votes

# Answer
Note that the overwhelming majority of problems fit the criterion you're looking for: both the problem and its complement are not semi-decidable. This is because there are only countably many semi-decidable problems but there are uncountably many problems.

For an example, let $H$ be the halting problem for Turing machines and let $\cal{M}$ be the class of Turing machines with an oracle for $H$. Let $H\_2$ be the halting problem for $\cal{M}$. I claim that neither $H\_2$ nor $\overline{H\_2}$ is semi-decidable

We can show that $H\_2$ is not decided by any machine in $\cal{M}$: the argument is the same as the argument that the ordinary Turing machine halting problem $H$ is not decided by any ordinary Turing machine. Now, suppose for contradiction that $H\_2$ is semi-decided by some ordinary Turing machine $T$. Well, with an oracle for $H$, we can test whether $T$ halts for any particular input, contradicting the fact that no machine in $\cal{M}$ decides $H\_2$. So $H\_2$ is not semi-decidable.

It remains to show that $\overline{H\_2}$ is not semi-decidable. First, note that it is semi-decided by a machine in $\cal{M}$: again, the argument is the same as $H$ being semi-decided by an ordinary Turing machine. $\overline{H\_2}$ cannot be semi-decided by some machine in $\cal{M}$ because, if it was, $H\_2$ and $\overline{H\_2}$ would both be semi-decided by machines in $\cal{M}$, so both languages would be decided by machines in $\cal{M}$. But we already know that $H\_2$ is not decided by any machine in $\cal{M}$. Therefore, $\overline{H\_2}$ is not semi-decided by any machine in $\cal{M}$. Further, $\overline{H\_2}$ is not semi-decided by any ordinary Turing machine, since $\cal{M}$ contains every ordinary Turing machine. (An ordinary Turing machine is a Turing machine with an oracle for $H$ that never uses that oracle.)
> 7 votes

# Answer
Here are some natural examples:

* The language of all Turing machines halting on *all* inputs, sometimes denoted TOT. This language is $\Pi\_2^0$-complete.
* The language of all Turing machines halting on *infinitely many* inputs, sometimes denoted INF. This language is also $\Pi\_2^0$-complete.
* The language of all Turing machines halting on *arbitrarily long* inputs, sometimes denoted COF. This language is $\Sigma\_3^0$-complete.

$\Pi\_2^0$ and $\Sigma\_3^0$ are levels of the arithmetical hierarchy. The completeness results imply, in particular, that these languages are neither semidecidable nor co-semidecidable.
> 7 votes

---
Tags: formal-languages, computability, turing-machines, undecidability, semi-decidability
---


# Question
Title: Difference between the two regular expression
I came across a question to create a regular expression to check whether there are even number of b's in a string of language {a,b}. The expression I came up with is (a+ba\*b)\*. However I found the solution online to be a\*(ba\*ba\*). Is there any difference? If any where?

Also I know that (a+b)\* is equivalent to (a\*b\*)\*. So my solution comes out to be (a\*(ba\*b))\*. So why that extra a\*?

# Answer
Your regular expression **(a+ba\*b)\*** won't match the string *a* which contains zero *b*'s, an even number. It also won't match the strings *bb* or *bbbb*, because the expression requires one or more *a*'s before any occurring *b*'s and requires at least one *a* between any two pairs of *b*'s.

The regular expression **a\*(ba\*ba\*)\*** is the correct solution. It allows any number of leading *a*'s and then demands that there if there are *b*'s present there be at least two *b*'s among the remaining *a*'s. Thereafter *b*'s are matched in groups of two among the *a*'s and matching will fail if a *b* occurs outside such a pair.

The regular expression **a\*(ba\*b)\*** is wrong because it won't match strings with *a*'s between pairs of *b*'s, such as the string *bbaabb*.
> 2 votes

---
Tags: regular-languages, regular-expressions
---


# Question
Title: Minimising sum of consecutive points distances Manhattan metric
I have two sets $X$ and $Y$ of 2-dimensional points. The points are floating point numbers. The objective is to sort them in such way that sum of differences in distances of consecutive sorted points is minimal.

I tried to solve this problem by localisation (dividing the plane by smaller grids of sorted points) and then connecting clusters - but this is a greedy and an approximate approach - the problem here is in setting grid size, but this is not guaranteed to give any bounds on how optimal the solution is, and it is rather time consuming (without a well-defined objective function).

Another attempt was to sort them by the x-coordinate, then find the minimum. But this approach fails. Normal sorting by two coordinates fails and is highly unstable.

The problem resembles the TSP problem, but the "path" is not closed and metric used is L1 (Manhattan, TaxiCab).

The solution I am looking for will probably be approximate. Finding the minimal and the second minimal distance from every point and connecting them gives good but for sure not minimal sum.

**The problem I am having is with giving the objective function.**

# Answer
It turns out that it is indeed the Traveling Salesman Path Problem (TSPP). There are well suited approximation algorithms:
> 3 votes

# Answer
Your problem is very close to TSP on the plane with the L1 metric. For this problem, there is a PTAS due to Arora, while the problem itself is probably NP-hard. Practically speaking, if your goal were indeed TSP rather than its "Hamiltonian path" variant, you could apply any approximation algorithm that works for metric TSP.
> 4 votes

---
Tags: algorithms, optimization, sorting, approximation
---


# Question
Title: Proving equality between foldl recursive and iterative fold
Hi I have two definitions of fold. I will call them foldl which is recursive and fold$\_{itr}$ which is iterative.

I am looking for an **algebraic proof** that the two definitions are equal ideally through **structural induction**.

**Definition for foldl**

```
foldl(c,h) nil = c

foldl(c, h) (list, element) = h (foldl (c, h) list, element)

```

**Definition for fold$\_{itr}$**

fold$\_{itr}$ (c, h) nil = nil

fold$\_{itr}$ (c, h) (element, list) = fold$\_{itr}$ (h(c, element), h) list

# Answer
The two definitions are **not equal**. Consider $h$ defined by \begin{align\*} h(c, a) = 10 \cdot c + a \end{align\*} and $c = 0$. Then $$\mathsf{foldl} \\, (c,h) \\, \[1,2,3\] = 321$$ but $$\mathsf{fold}\_{itr} \\, (c,h) \\, \[1,2,3\] = 123.$$
> 2 votes

---
Tags: functional-programming, correctness-proof, induction
---


# Question
Title: For every 'evil' regex, does there exist a non-evil alternative, or is the devil in the grammar?
Apparently, ReDos attacks exploit characteristics of some (otherwise useful) regular expressions ... essentially causing an explosion of possible paths through the graph defined by the NFA.

Is it possible to avoid such problems by writing an equivalent 'non-evil' regex? If not (thus, the grammar can't be handled in practical space/time by an NFA), what parsing approaches would be better? Why?

# Answer
It depends upon whether you've got a regular expression or a regexp: regexps are evil, but regular expressions are a thing of beauty and will never turn evil on you.

By regexp, I mean a modern regular expression: i.e., a regular expression with additional modern features such as backreferences -- e.g., a Perl-compatible regular expression. This is more powerful than a classical regular expression from a formal languages / automata theory textbook, as classical regular expressions don't allow backreferences, lookahead, lookbehind, and so on.

For a classical regular expression, if you have a good implementation for the matcher, then no regular expression is too evil. In particular, a standard algorithm for matching is to convert the regular expression to a NFA and then executing the NFA on an input string. For this algorithm, the worst-case running time to test a $n$-character string is $O(n)$, when the regular expression is fixed. This means that the running time can't explode too rapidly. There is no string that will cause an exponential increase in running time. Thus, if you're using a matcher that uses this algorithm, no classical regular expression will be evil.

This does depend on the implementation of the regular expression matcher. If you have a naive or poor implementation of the matcher, then matching could take exponential time; there are certainly algorithms with that property. But the best answer to that is probably not to change the regular expression; it's probably better to pick a better matcher, if you are concerned about denial-of-service attacks.

In comparison, some modern regexps are unavoidably evil. If you have a modern regexp, then matching can require exponential time. In particular, regexps with backreferences can recognize NP-hard languages. Consequently, under plausible assumptions, there exists a class of evil regexps where testing for a match takes exponential time. Thus, some modern regexps are unavoidably evil: there is no feasible way to find an equivalent regexp that won't cause exponential blowup in running time to match.

(Such an equivalent might exist and might even be findable in theory, but under plausible assumptions, finding the equivalent regexp will take exponential time, which isn't feasible in practice. If you had a systematic procedure to find the equivalent regexp in polynomial time, then you could solve the NP-hard problem in polynomial time, proving that P = NP. It doesn't do much good for there to exist an equivalent regexp if there's no way actually find it within your lifetime.)

---

Background and sources:
> 14 votes

# Answer
This answer will take a more overarching view of this unusual crosscutting situation, where complexity theory is applicable to cybersecurity and the example contains some of the significant nuance/ subtlety that can occur in this area. This is essentially similar to an "injection attack" where certain unexpected inputs cause pathological behavior either crashing a system or causing it to take an abnormally long time.

Wikipedia has 15 categories of Denial of Service attacks and this attack falls into "application level floods" in that list. Another somewhat similar example is an attack that fills up application logs.

One fix for injection attacks is to "clean the input". The application designer can reevaluate if it is necessary to compile arbitrary regexps supplied by a potentially malicious user. Just stripping off nested expressions in the regexp or some other similar limitation would probably be enough to avoid this attack. While they are intrinsic to a lot of modern software, large amounts of functionality can be provided without evaluating regular expressions. The context matters, some applications would not require such security.

Another approach to improve fault tolerance/ resilience that is applicable here are *timeouts* specified at different levels of the software stack/ hierarchy. The idea would be to specify a time/ cpu or instruction limit on a "average" regular expression evaluation and terminate early if its exceeded. They can be implemented with custom solutions but not very much software or programming languages have built-in timeouts or frameworks for this purpose.

Here is a nice example of the use of timeouts to improve fault tolerance and shows a high-level design/ architecture/ pov to mitigate such issues: Fault Tolerance in a High Volume, Distributed System / Netflix. It has nothing specifically connected to regular expressions but thats the point here: virtually any/ all application level logic can fit into this framework or something similar.

This article points out how backtracking in particular can lead to slow regexp matching. Regexps have many different features and one could attempt to evaluate which ones lead to worst case behaviors.

Here is a nice scientific survey of this particular topic with static analysis solution(s) proposed:

* Static Analysis for Regular Expression Exponential Runtime via Substructural Logics / Rathnayake, Thielecke

> Regular expression matching using backtracking can have exponential runtime, leading to an algorithmic complexity attack known as REDoS in the systems security literature. In this paper, we build on a recently published static analysis that detects whether a given regular expression can have exponential runtime for some inputs. We systematically construct a more accurate analysis by forming powers and products of transition relations and thereby reducing the REDoS problem to reachability. The correctness of the analysis is proved using a substructural calculus of search trees, where the branching of the tree causing exponential blowup is characterized as a form of non-linearity.
> 1 votes

---
Tags: regular-expressions, parsers
---


# Question
Title: How to determine number of instances for resources in a resource allocation graph?
I am struggling to determine the number of instances a resource will have. I have performed extensive research on this, but unfortunately have come up short. I am tasked with drawing a resource allocation graph and I have been provided with the number of processes which is 3 and the of resources which is 5. I have concluded that when drawing the resource allocation graph, I will need to know the number of instances of a resource. Please could someone just help in how I would go about working out or determining the number of instances a resource will have?

# Answer
> 0 votes
The number of instances should technically be specified to you. The best I can suggest is assume that each resource will only have one instance each. But I suggest getting more information on your scenario

---
Tags: resource-allocation
---


# Question
Title: Why is ${n \choose 2}$ a $\Theta(n^2)$ computation?
In Cormen's *Algorithms* textbook, the author casually mentions that ${n \choose 2}$ is $\Theta(n^2)$.

Why is this so? In the calculation

$$ {n \choose 2} = \frac{n!}{(n-2)!2!} $$

there are $n$ multiplication operations in the numerator and $n$ multiplications in the denominator. That means there are at most $2n+1$ computations to here make (one for the division step), no?

# Answer
> 4 votes
You're assuming that $\Theta(\cdot)$ means something it doesn't mean. $\Theta(\cdot)$ is just a comparison between functions. It doesn't matter what those functions are being used to measure.

Saying that $\binom{n}{2}=\Theta(n^2)$ means only that there are constants $c\_1$ and $c\_2$ such that, for all large enough $n$, $c\_1n^2\leq\binom{n}{2}\leq c\_2n^2$. It says nothing at all about how long it takes to compute the function $\binom{n}{2}$ for any value of $n$.

For example, we can define a function $f(n) = n^2$ if the $n$th Turing machine terminates when started with no input and $f(n)=n^2+1$ if it doesn't. The function $f$ isn't even computable but we still have $f=\Theta(n^2)$ because, for all $n\geq 1$, $n^2\leq f(n)\leq 2n^2$.

# Answer
> 5 votes
$\Theta$-notation more generally refers to the growth of a function. In terms of computational complexity this function can be done in $O(1)$ as:

$$\frac{n!}{(n-2)!2!} = \frac{n(n-1)}{2!} = \frac{n(n-1)}{2}$$

Since there are a finite number of multiplications and multiplication is sometimes treated as $O(1)$ this has constant computational time. But, the author is not referring to the computational complexity of this function. Instead he is referring to the growth of the function:

$$\frac{n(n-1)}{2} = \frac{n^2}{2} - \frac{n}{2} \in \Theta(n^2)$$

# Answer
> 3 votes
With the function $f(n) = {n \choose 2}$, it is the case that $f(n) = \frac{n(n-1)}{2} = \frac{1}{2}(n^2 - n) = \Theta(n^2)$. The function itself grows quadratically. Computing it actually only takes one multiplication operation, one subtraction, and one division by 2, so *computing* $f(n)$ can be done in $O(1)$ (assuming constant-time arithmetic operations).

To illustrate the difference -- the travelling salesman problem has $n!$ different paths, so the naive solution has a runtime of $O(n!)$. But computing $n!$ can be done $n$ multiplications.

---
Tags: asymptotics
---


# Question
Title: Why are computable numbers (in Turing's sense) enumerable?
Why are computable numbers (in Turing's sense) enumerable? It must be very obvious, but I'm currently just not seeing it.

# Answer
I'm assuming that your definition of a computable number is this: there is a Turing machine that on input $n$, halts with the $n$th bit of the number.

Suppose there were a recursive enumeration of Turing machines that produce computable numbers. You can use diagonalization to come up with a new computable number which isn't part of this recursive enumeration.

It is tempting to enumerate computable numbers by enumerating Turing machines, but not every Turing machine corresponds to a computable number, and in general deciding whether a Turing machine halts for all inputs (let alone output either 0 or 1) is not computable. It is, however, possible to enumerate all efficient computable numbers, say ones whose running time is polynomial, by using clocked Turing machines.
> 5 votes

# Answer
If by enumerable, you mean that there is a bijection with the natural numbers (i.e., countable), then no, computable numbers are not enumerable.

Let's define the problem more precisely: a "Number-Printing Turing Machine (NPTM)" is a Turing Machine that, for every state transition, may print nothing, or may print any decimal digit, the minus sign, or the period. This is enough to print decimal representations of real numbers.

Lets define a computable real number as any real number that can be printed with arbitrarily long representation, given enough time, by a NPTM starting from an empty tape. Lets also say that a number is computed by a given NPTM iff it either halts after printing a well formed real number (in which case, the number has a finite decimal representation) or will, in a finite amount of time, print well formed number with a decimal point, and will ever increase the precision of the number by printing more digits, given ever more time.

This later condition needed because, if we have a machine that, for instance, prints an infinite sequence of some digit, say `1111111111111111111`..., it cannot be said to be computing any real number, because real numbers only have infinite representation to the right side of the decimal period. On the other hand, if the machine prints `3.14` and then stops printing, but never halts, it cannot be said to be computing any real number simply because the precision of the number is not increasing, thus, this particular machine won't be constructing it further.

These are examples of NPTM that do computes some number. A NPTM that:

* prints `1`, then halts. It computes number 1.
* prints `1.0`, then halts. It also computes number 1.
* prints `1.0000000`, and keeps printing zeros forever. This one also computes number 1.
* prints `3.14`, then halts. It computes number 3.14.
* prints `3.14159`, and goes on forever printing digits of $\pi$. This one computes number $\pi$.
* prints `-42.`, and then halts. It computes number -42.

And these are examples of NPTM that do **not** compute any number. A NPTM that:

* prints `123123123` and then goes on printing the sequence `123` forever. Isn't computing a number because this infinite sequence does not represent any real number.
* prints `1.0.0` and then halts. Isn't because this finite sequence is not well formed.
* prints `....-..---` and then halts. Isn't because this is not a well formed real number either.
* never prints anything, but never halts either. There is no number being constructed.
* never prints anything and immediately halts. No number was constructed.
* prints `3.14`, doesn't halt, but never prints anything else either. Isn't computing a number because its precision isn't increasing with time.

You've got the idea. Then we have two classes of NPTM: those that computes some real number, and those who don't.

The problem with finding some enumeration for the computable numbers is that, even if the NPTM are themselves countable, we can't have a procedure that separates one kind of NPTM from another.

Consider the definition of countable set: for a set $S$ to be countable, there must exist some bijective function $F: \mathbb{N} \rightarrow S$.

To "prove" that the computable numbers are countable, one might be tempted to define such a function from the counting of the NPTM (and this is what people often did, when they believe the computable numbers are countable). Something like this:

The NPTM are countable, so there is a bijective function $E\_\text{NPTM}: \mathbb{N} -\> \text{NPTM}$, thus we can go enumerating forever all NPTM that exists. So, to likewise enumerate all computable numbers, and precisely define the bijective function $E\_\text{Computabe}: \mathbb{N} \rightarrow \text{Computable}$, one must simply enumerate all NPTM, but count only those that do compute some real number. But how do we know it computes some real number?

Well, we don't. Consider a machine that immediately prints `1.0`, and then stops printing and goes on to try to solve an instance of the Post correspondence problem. If it solves the problem, it halts, then the machine just computed the number one. But that problem is undecidable, so it may never halt, and if it never halts, it never computes a real number. But we can't know if it will ever halt, because the Halting problem is also undecidable! So, since there is no way of knowing if this particular machine, and infinitely many other machines, either computes or not some real number, we can't build/define our bijective function in this way.

The naïve way to define the bijection fails, and it is not very difficult to prove that there is no way do it, whatsoever. As Yuval Filmus suggested, diagonalization can be used.
> 2 votes

---
Tags: computability, turing-machines, enumeration
---


# Question
Title: Why are PTAS-Reductions used to establish APX-Hardness?
What's the intuition for PTAS reductions instead of approximation preserving reductions or something of that ilk? I'd expect APX-Hardness to mean something like "finding a constant factor approximation for this problem is as hard as finding a constant factor approximation to any problem in APX" but having just a PTAS reduction from A to B isn't strong enough to imply a constant factor approx to B can be converted into a constant factor approx of A.

# Answer
Let me correct two misconceptions in your question:

* $PTAS$-reductions *are* approximation-preserving
* $APX$ is the class of problems that have constant-factor approximations

The big open question isn't whether $APX$ problems have constant-factor approximations (by definition, they do), but whether they have polynomial time approximation schemes. The meaning of $APX$-complete is "As hard as any problem in $APX$ to find a polynomial time approximation scheme for". A $PTAS$ from $A$ to $B$ reduction allows any polynomial time approximation scheme for $B$ to be used for $A$.
> 5 votes

---
Tags: complexity-theory, reductions, approximation
---


# Question
Title: Expressing iterative version of fold in terms of recursive version
**1st Definition. Recursive definition of fold**

fold$\_{recur}$ (c,h) nil = c

fold$\_{recur}$ (c,h) (cons(a, x)) = h(a, fold$\_{recur}$ (c,h) x)

**2nd definition of fold. Iterative definition**

fold$\_{itr}$ (c, h) nil = c

fold$\_{itr}$ (c, h) (cons (a, x) ) = fold$\_{itr}$ (h (c, a), h) x

How do I express fold$\_{itr}$ in terms of fold$\_{recur}$.

# Answer
> 3 votes
For easier typing let me rename $\mathsf{fold}\_{recur}$ to $\mathsf{foldr}$ and $\mathsf{fold\_{itr}}$ to $\mathsf{foldl}$ (an additional reason for the renaming will soon be apparent).

Then we have $$\mathsf{foldr} \\,(h,c) \\,\[x\_1, x\_2, \ldots, x\_n\] = h(x\_1, h(x\_2, \ldots, h(x\_{n-1}, c) \ldots ))$$ and $$\mathsf{foldl} \\,(h,c) \\,\[x\_1, x\_2, \ldots, x\_n\] = h(\ldots h(h(c, x\_1), x\_2), \ldots, x\_n). $$ That is, your two different folds are also known as the *right* and *left* fold in functional programming languages. You are asking how to get the left fold in terms of the right fold. The short answer is "by reversing the list".

Suppose we had a list reversing function $\mathsf{rev}$. Then we could define $$\mathsf{foldl} \\, (h,c) \\, \ell = \mathsf{foldr} \\, ((\lambda (x,y) . h(y,x)),c) \\, (\mathsf{rev} \\, \ell). $$ We just need $\mathsf{rev}$ expressed in terms of right fold: $$\mathsf{rev} \\, \ell = \mathsf{foldr} \\, (\mathsf{append}, \mathsf{nil}) \\, \ell $$ and $$\mathsf{append}(x, \ell) = \mathsf{foldr} \\, (\mathsf{cons}, \mathsf{cons}(x,\mathsf{nil})) \\, \ell. $$ You can fold all these definitions into one fat definition of $\mathsf{rev}$, if you want to impress your teacher.

# Answer
> 0 votes
Just want to link a similar question on stackoverflow asked in scala to this question

\[https://stackoverflow.com/questions/17136794/foldleft-using-foldright-in-scala\]\[1\]

---
Tags: functional-programming
---


# Question
Title: Can an algorithm that yields $O(n^2)$ answers run in $O(n)$ time?
My question may actually be more broadly described as: can I use the fact that an algorithm is expected to return $(O(f(n))$ answers to show that it may never run better than $O(f(n))$? I would intuitively assume yes, but I am not sure.

Examples of what I'm talking about is algorithms to calculate all the paths that pass through a set of points. I can easily calculate a higher bound $O(f(n))$ on how many those paths are. Will that tell me the algorithm must be no better than $\Omega(f(n))$?

Thanks

# Answer
> 8 votes
> Can an algorithm that yields $O(n^2)$ answers run in $O(n)$ time?

Yes. The following algorithm yields $O(n^2)$ answers (remember what $O(\cdot)$ means!) but it runs in time $O(n)$.

```
halt;

```

You probably meant to ask if an algorithm that yields $\Theta(n^2)$ answers can run in time $O(n)$. The answer to that is no. Whatever exact definition you choose for "yielding an answer", yielding one answer must take at least one computation step in any reasonable model of computation, so writing $\Theta(n^2)$ answers must take $\Omega(n^2)$ steps.

# Answer
> 4 votes
If the algorithm (modelled, say by a Turing Machine writing the output on a special output tape) generates at least $f(n)$ output, its running time can't be less than the time required to write it out, i.e., it's $\Omega(f(n))$.

Can't say anything about an upper bound. Think for example about the problem of determining if an array is sorted, the result is clearly just "yes" or "no", while the running time is at least the size of the array, and that isn't $O(1)$.

# Answer
> 1 votes
The upper bound of an algorithm usually has little bearing on it's lower bound. Take for example the following Bubble Sort algorithm:

```
for(i=0;i<n;i++){
    for(j=0;j<n-i;j++){
        if(arr[j]>arr[j+1]){
            swap(&arr[j],&arr[j+1]);
            flag=1;
        }
    }
    if(!flag) break;
}

```

This algorithm typically has an upper bound of $O(n^2)$. But in case the input is a sorted array, then the flag is never set to 1 in the first pass and we break out only after n comparisons. So this algorithm is $\Omega(n)$,ie it has a lower bound of $O(n)$.

You may want to consider tight bounds on an algorithm. An algorithm that has $\Theta(f(n))$ will have an upper bound of $O(f(n))$ and a lower bound of $\Omega(f(n))$.

# Answer
> -3 votes
In essence, the running time depends on the size of the data and the format in which data is provided to the algorithm.

Otherwise, there seems to be a little correlation between the complexity of algorithm under different set of inputs.

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


# Question
Title: What are algorithms for computing contours from given edges?
Let's say I have a set of edges which makes the contour, however there are too many of them and some are too long. I have to remove edges, and shorten them to make contour. I *cannot* add new edges!

I am looking at least for the name of the algorithm to further look how this problem is solved.

Here is the example (please don't mind the grid) -- input:

and output **in pink** (the pink is the real output, the rest is left for comparison -- it should be removed by algorithm I am looking for):

As you can see I have a lot of redundant edges, too long, internal ones. Note also that this is not the convex hull problem; my shape is not convex.

*The question:* what are known algorithms for solving this problem?

# Answer
> 2 votes
How about tracing the contour, something like this?

Find one point $p\_1$ on the contour (e.g., the vertically highest point). Find all the edge incident to $p\_1$. Sort them around $p\_1$ and identify an extreme edge $e\_1$ (defining "extreme" here is a bit tricky). Follow $e\_1$ until you reach either its endpoint or another edge intersecting $e\_1$. Call that point $p\_2$. Repeat.

# Answer
> 3 votes
This problem is not surprisingly called Concave Hull
You might be also interested in alpha shapes CONCAVE HULL: A K-NEAREST NEIGHBOURS APPROACH FOR THE COMPUTATION OF THE REGION OCCUPIED BY A SET OF POINTS by *Adriano Moreira and Maribel Yasmina Santos*

# Answer
> 2 votes
I'm not sure this problem is so well specified. For example, what happens when parts of edges "poke out" from the contour? You've said you can't remove edges so the only way the contour is well defined is if the contour has no "burrs".

Regardless, the algorithm you probably want to look at is called the Vatti clipping algrithm. Vatti's algorithm does arbitrary boolean operations (union, intersection, difference, xor) on two dimensional polygons. My apologies, I'm having trouble finding the run time through a cursory glance but I believe it's linear (or maybe $O( V\ ln(V))$) in the number of total polygon vertices, $V$. It uses a sweep line approach so besides whatever structures are used to store, sort, search, etc., the fundamental operation is scanning through the vertices which probably isn't much worse than linear.

By interpreting your problem as trying to find a (potentially convex) contour of many thin rectangles in the plane, you can use Vatti's clipping algorithm to get the contour. Here is one such way:

* Do a large union of all the rectangles in the plane
* Discard all 'holes' and consider only the outer contours
* Do another union on all the outer contours

The reason for the multiple applications of Vatti's algorithm is that you can have polygon 'islands' that are completely enclosed (and not part of) an outer polygon contour. Discarding the holes will ensure the middle will get 'filled in' and the resulting polygon will be the union of all the contours. If there's a simple way to determine what the 'outer contour' is, then that would obviously be better but I don't know of any way to accomplish that without re-inventing Vatti's algorithm.

One can also imagine using some type of polygon offsetting to either fill out breaks in the contour or make the contour smoother.

Implementing Vatti's algorithm (and any fundamental geometry algorithm) is technical and often very subtle. Though I would never dissuade anyone from personal discovery or deprive anyone the joy of implementing algorithms but if you're more concerned with the end goal of finding the contour and aren't as concerned with personal development, I highly recommend Angus Johnson's Clipper library. The Clipper library has C++ bindings (among others) and there's even a JavaScript port of it. Clipper uses integers for it's representation, so there's less of a concern of round off error. This often means premultiplying your input to a desired resolution, applying Clipper operations on it, then dividing at the end. Clipper is offered under a free license (Boost). I've used Clipper for my own projects and have been quite happy with it.

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


# Question
Title: Why is least fixed point (lfp) important in program analysis
I am trying to get a big picture on the importance of least fixed point (lfp) in program analysis. For instance abstract interpretation seems to use the existence of lfp. Many research papers on program analysis also focus heavily on finding least fixed point.

More specifically, this article in wikipedia : Knaster-Tarski Theorem mentions that lfp are used to define program semantics.

Why is it important? Any simple example helps me. (I am trying to get a big picture).

**EDIT**

I think my wording is incorrect. I donot challenge the importance of lfp. My exact question (beginner) is: How does computing lfp help in program analysis? For e.g., why/how abstract interpretation uses lfp? what happens if there is no lfp in the abstract domain?

Hopefully my question is more concrete now.

# Answer
> 13 votes
Any form of recursion or iteration in programming is actually a fixed point. For instance, a `while` loop is characterized by the equation

```
while b do c done  ≡  if b then (c ; while b do c done)

```

which is to say that `while b do c done` is a solution `W` of the equation

```
W  ≡  Φ(W)

```

where `Φ(x) ≡ if b then (c ; x)`. But what if `Φ` has *many* fixed points? Which one corresponds to the `while` loop? One of the basic insights of programming semantics is that it is the *least* fixed point.

Let us take a simple example, this time recursion. I will use Haskell. The recursive function `f` defined by

```
f :: a -> a
f x = f x

```

is the everywhere undefined function, because it just runs forever. We can rewrite this definition in a more unusual way (but it still works in Haskell) as

```
f :: a -> a
f = f

```

So `f` is a fixed point of the identity function:

```
f ≡ id f

```

But *every* function is a fixed point of `id`. Under the usual domain-theoretic ordering, "undefined" is the least element. And indeed, our function `f` is the everywhere undefined function.

**Added on request:** in the comments OP asked about the partial order for semantics `while` loops (you presumed it was a lattice but it need not be). A more general question is what is the domain-theoretic interpretation of a procedural language which can manipulate variables and has the basic control structures (conditionals and loops). There are several ways of doing this, depending on what exactly you want to capture, but to keep things simple, let's assume that we have a fixed number $n$ of global variables $x\_1, \ldots, x\_n$ that the program can read and update, and nothing else (no I/O or exceptions, or allocation of new variables). In that case a program can be seen as a transformation of the initial state of the variables to the final state, or the undefined value if the program cycles. So, if each variable holds an element of a set $V$, a program will correspond to a mapping $V^n \to V^n \cup \\{\bot\\}$: for every initial configuration $(v\_1, \ldots, v\_n) \in V^n$ of the variables, the program will either diverge and yield $\bot$, or it will terminate and produce the final state, which is an element of $V^n$. The set of all maps $V^n \to V^n \cup \\{\bot\\}$ is a domain:

* we use the flat ordering on $V^n \cup \\{\bot\\}$ which has $\bot$ at the bottom and all the elements of $V^n$ "flat" above it, and then $V^n \to V^n \cup \\{\bot\\}$ is ordered pointwise,
* the least element is the function which always maps to $\bot$, corresponding to the program `while true do skip done` (and many others),
* every increasing sequence has a supremum

Just to give you an idea of how this works, the semantics of the program

```
x_1 := e

```

would be the function which takes as input $(v\_1, \ldots, v\_n) \in V^n$, calculates the value $v\_e$ of the expression `e` in state $(v\_1, \ldots, v\_n)$, and returns $(v\_e, v\_2, \ldots, v\_n)$.

# Answer
> 6 votes
Here is the intuition: least fixed points help you analyze loops.

Program analysis involves executing the program -- but abstracting away some details of the data. This is all good. The abstraction helps the analysis go faster than actually running the program, because it allows you to ignore aspects you don't care about. For instance, that's how abstract interpretation works: it basically simulates execution of the program, but only keeping track of partial information about the state of the program.

The tricky bit is when you get to a loop. The loop could execute many, many times. Typically, you don't want your program analysis to have to execute all of those iterations of the loop, because then the program analysis will take a long time ... or might not even terminate. So, that's where you use a least fixed point. The least fixed point basically characterizes what you can say for sure will be true after the loop finishes, if you don't know how many times the loop will iterate.

That's what the least fixed point is used for. Because loops are present throughout programs, least fixed points are used throughout program analysis. Least fixed points are important because loops are everywhere, and it's important to be able to analyze loops.

Incidentally, recursion and mutual recursion are just another form of loop -- so they too tend to be handled with a least fixed point.

---
Tags: programming-languages, finite-model-theory, fixed-point
---


title: Applying algorithms on large data

text:
# Question
Title: Applying algorithms on large data
Is there any book or tutorial that teaches us how to efficiently apply the common algorithms (sorting, searching, etc.) on large data (i.e. data that cannot be fully loaded into main memory) and how to efficiently apply those algorithms considering the cost of block transfer from external memory ? For example, almost all algorithm textbooks say that B and B+-trees can be used to store data on disk. However, actually how this can be done, especially handling the pointers where the data is present on disk is not explained. Similarly, though many books teach searching techniques, they do not consider data present in secondary memory.

I have checked Knuth's book. Although it discusses these ideas, I still did not understand how to actually apply them in a high-level language. Is there any reference that discusses these details?

# Answer
Database books are good example. However, have a look at the field I/O efficient data structures (and algorithms). To my knowledge, there are some courses about this topic, but very few books.

Check this book: U. Meyer, P. Sanders, and J. Sibeyn (eds.), Algorithms for Memory Hierarchies, Lecture Notes in Computer Science 2625, Springer, 2003.

Check these courses: http://www.win.tue.nl/~hermanh/teaching/2IL35/ http://www.daimi.au.dk/~large/ioS12/

and these slides: algo2.iti.kit.edu/sanders/courses/algen09-10/rdslides.pdf
> 2 votes

# Answer
Ramkrishnan and Gehrke's database book discusses these things in some detail.
> 1 votes

# Answer
Probably what you are looking for in one neat book:Algorithms and Data Structures for External Memory by Jeffrey Scott Vitter.
> 1 votes

# Answer
Nowadays this field is known as **big data**, and it is evolving very rapidly and quickly based on the strong connection with virtualization and relational database technology is only seen as a subset. Also as comments note, key/value databases and NoSQL are where much new innovation and momentum is moving. But from your comments, you seem to be more interested in **relational database design** principles and techniques. Try the following refs:
> 0 votes

---
Tags: algorithms, efficiency, memory-management, big-data
---


# Question
Title: Short notation for Turing machine configurations
I'm writing about Turing machines and often need to denote the tape. I'm using exponential tapes, i.e. a repetition count for each symbol.

I usually use something similar to $(x\_k^{e\_k})\_{1 \leq k \leq m} \text{ Q } (x\_k^{e\_k})\_{m+1 \leq k \leq n}$ (latex: `$(x_k^{e_k})_{1 \leq k \leq m} \text{ Q } (x_k^{e_k})_{m+1 \leq k \leq n}$`) with $x\_k$ the symbols and $e\_k$ their exponents. The head in state $Q$ is at position $m$.

What (very slightly) annoys me about this is the need to include $Q$. Without it, it would just be $(x\_k^{e\_k})\_{1 \leq k \leq n}$ (latex: `$(x_k^{e_k})_{1 \leq k \leq n}$`) , which is must easier to read.

The transitions may change various symbols and exponents at the same time, while $Q$ almost always stays in the same spot.

How should I note this down? Is there an easy to understand (and parse) notation which is shorter but still carries the same information? I could not find a solution in the papers I read. Or maybe I should just carry on, because this isn't an issue at all?

# Answer
> 4 votes
This is just a convention. You can write a configuration as the tuple that has the same information. Eg, a possible way to write a configuration is as the tuple $$Config= (tape,state,pos)$$

where $tape$ is the non empty tape content, $state$ is the current state, and $pos$ is the position of the head.

This is fully equivalent to the method you use, which makes sense for other succinct description of configurations. Tho only thing to bear in mind, is that people are used to the 1-string-head-inside convention you describe in the question, so if you change it, you need to be very clear and explicit about it.

---
Tags: turing-machines, notation
---


# Question
Title: Algorithm for constructing BST from post-order traversal
Given a post-order traversal of Binary Search tree with $k$ nodes, find an algorithm that constructs the BST.

***My Algortihm***

> Let $n$ represent the next element to be inserted.
>
> Let $P(y)$ represent the parent of node $y$.
>
> 1. We will read the traversal in reverse. The last element of the traversal is the root. Let $l = root$. $l$ will represent the element last inserted in the BST (except for the 3rd case below- where it will change to the parent).
>
> *Loop the following till there's no element left to be inserted*
>
> 1. if $l\<n$ then $n$ is the right child of $l$. For the next insertion, $l$ changes to it's right child and $n$ becomes the next element(in reverse order of traversal ).
> 2. else, if $l\>n$ and $P(l)\<n$ then $n$ is the left child of $l$. For the next insertion, $l$ changes to it's left child and $n$ becomes the next element(in reverse order of traversal).
> 3. else, if $l\>n$ and $P(l)\>n$ then $l$ becomes $P(l)$.($n$ hasn't been inserted - we loop with $l$ changed)
>
> \[Let $P(root)=- \infty$, so that the $2^{nd}$ case applies\]

Complexity Analysis : Every element may contribute at max 3 comparisons, 1 each for - left child, right child and for finally leaving i.e. subtree has been constructed. Even if I missed a comparison or two, It should be constant no. of comparisons per element and no. of operations for node construction will also be constant per element. Hence, giving $O(k)$ time complexity.

**Actual Question**

If the algorithm is correct, I need the **correctness proof** for it. Yes, I thought I had the proof but then brain got fried and I am stuck and unable to reason succinctly.
If the algorithm is incorrect, then why? And what is time complexity of the most efficient algorithm for the same question?

Also, is the $O(k)$ complexity correctly calculated - irrespective of the correctness of the algorithm?

# Answer
You are in the right track. But the algorithm is incomplete. You missed the case inserting element on the left sub tree and back.

Here is the modified algorithm: (Changes marked in bold)

> Let $n$ represent the next element to be inserted.
>
> Let $P(y)$ represent the parent of node $y$.
>
> **Let $g=G(y)$ represent the first node g on the path $y\to root$ such that $P(g)\<g$.**
>
> 1. We will read the traversal in reverse. The last element of the traversal is the root. Let $l = root$. $l$ will represent the element last inserted in the BST (except for the 3rd case below- where it will change to the parent). **Let $g=root$ tracking $G(l)$, initialize empty stack $stkG$ storing previous $g$'s on current path.**
> 2. *Loop the following till there's no element left to be inserted*
>
> 1. if $l\<n$ then $n$ is the right child of $l$. For the next insertion, $l$ changes to it's right child and $n$ becomes the next element(in reverse order of traversal ). **Push $g$ on $stkG$, and let $g=l$.**
>     2. else, if $l\>n$ and $\textbf{P(g)\<n}$ then $n$ is the left child of $l$. For the next insertion, $l$ changes to it's left child and $n$ becomes the next element(in reverse order of traversal).
>     3. else, if $l\>n$ and $\textbf{P(g)\>n}$ then $l$ becomes $\textbf{P(g)}$ **and pop $g$ from $stkG$**.($n$ hasn't been inserted - we loop with $l$ changed)
>
> \[Let $P(root)=- \infty$, so that the $2^{nd}$ case applies\]

For correctness, you can prove the following loop invariant:

1. Root is the first inserted element. for each insertion except root, the parent element has been inserted before.
2. Each insertion $n$ correctly maintains the order between $n$ and $l$. ($n\<l$ if $n$ is left child of $l$, $n\>l$ otherwise)
3. After backtracking step 3, the next insertion always occurs on the left branch.

1 and 3 ensures the post-order traversal, while 2 ensures the BST.

For complexity:

1. insertion cost: each element is inserted exactly once.
2. traversal and comparison: the algorithm actually performs a post-order traversal in reverse order, with $O(1)$ comparison on each step.
3. $g$,$stkG$ maintain cost: each node, which is right child of parent, is pushed and popped from $stkG$ at most once.

Thus the time complexity is $O(k)$.

## Alternative algorithm:\[1\]

Using a recursive procedure:

```
procedure BST_from_postorder(post, len, target)
/*
input: post[0..len-1] -- (partial) postorder traversal of BST
       len -- length of post to be processed.
       target -- a cutoff value to stop processing
Output: tree_ptr -- pointer to root of tree/sub tree constructed from post[len_rest..len-1]
        len_rest -- remaining length that has not been processed.
*/
 1. if len <= 0 or post[len-1] <= target, then return null.
 2. root <- new Node created from from post[len-1].
 3. (root->right, new_len) <- BST_from_postorder(post, len-1, post[len-1])
 4. (root->left, rest_len) <- BST_from_postorder(post, newlen, target)
 5. return (pointer to root, rest_len)

/* BST_from_postorder(post, length of post, -infinity)
 will return the BST construct from given postorder traversal. */

```
> 3 votes

---
Tags: algorithms, algorithm-analysis, runtime-analysis, correctness-proof
---


title: FPT algorithm for point line cover

text:
# Question
Title: FPT algorithm for point line cover
In the "Covering Things with Things" paper from Langerman and Morin, they mention the BST-Dim-Set-Cover, which is a FPT algorithm for point-line-cover, at page 666.

The algorithm chooses each point p from a set S and then subdivides it into k-lines.

This can be seen as a special case of set cover. All points (each *p* belongs to P) are in a cartesian plane, and the algorithm needs to find if they can be covered by *k* lines (where each line *l* belongs to L). This image below clarifies it further:

My question is around what is written in the paper linked above at page 666 regarding where is p taken from: At some point during the text it says "Otherwise, the algorithm chooses an element p ∈ S'". However, further down in the algorithm it says "choose p ∈ S" (without the prime symbol).

Is p taken from S or S' (S prime)?

Thanks!

# Answer
The algorithm should say "choose $p \in S'$", that is, the text is the correct version, rather than the pseudocode.

Note how the algorithm works:

* $S',S\_{1},\ldots,S\_{k}$ form a partition of $S$ (i.e. every element of $S$ is in exactly one of $S',S\_{1},\ldots,S\_{k}$).
* At each step it chooses which $S\_{i}$ to put $p$ into.
* Initially $S' = S$, and $S\_{i} = \emptyset$ for all $i$.

So $S'$ is the set of points that still need to be covered, and $S\_{i}$ is the set of points covering by hyperplane $i$, in some abstract sense. Thus the algorithm, at each iteration, picks an uncovered element from $S'$, and puts it in some $S\_{i}$.

Interestingly, this error made it all the way to the journal version.
> 6 votes

---
Tags: algorithms, algorithm-analysis, parameterized-complexity
---


# Question
Title: that there would be no perfect strategy for poker
In my opinion, every imperfect information game where there is the possibility of bluffing lacks a perfect (or winning) strategy, for the simple reason that knowing your opponent's strategy will let you beat him easily (even if his strategy isn't 100% deterministic).

So why do the guys that developed 'Cepheus' claim that they made a program playing poker with a perfect strategy, claiming that their AI 'is guaranteed to not lose money in the long run' ?

I'm pretty sure I can create a strategy winning versus Cepheus, because I know its strategy.

Where am I wrong ?

# Answer
Nash proved that every zero-sum game has a perfect strategy called a Nash equilibrium. This is a possibly randomized strategy for both players such that given that one player follows the strategy, it doesn't pay the other player to deviate from her strategy. As an example, consider the game *rock, paper, scissors*. One Nash equilibrium here has both players choosing their signal randomly. If one player does that, there is no point for the other player to follow any other strategy (though it doesn't hurt).

Since Poker is a symmetric zero-sum game (both players are treated the same by the game), the *value* of the game is zero, and any Nash equilibrium on average results in zero expected profit for both players. According to Wikipedia, Cepheus is an approximation to such a strategy. As such, Cepehus' strategy may be randomized.

What about bluffing? Let's consider a variant of rock, paper, scissors in which players can bluff. Say each player writes their choice on a piece of paper, and then there is some structured dialog in which players announce their choice and offer the other player to capitulate. The random strategy is still perfect, in that if one player follows it, it doesn't pay for the other player to deviate from it.

While Cepehus (if it were perfect) shouldn't lose on the long run, it is not guaranteed to be a good strategy in practice, since it only promises you a small negative expected profit. Perhaps when playing against good human players it will just break even on average. That doesn't mean that humans are any better than it, just that they're not any worse. Another possibility is that while in theory the only guarantee is that it breaks even, in practice it wins against sub-optimal humans. This is an empirical question that the developers are testing right now through their website.
> 4 votes

---
Tags: artificial-intelligence, game-theory
---


title: Binary code with constraint

text:
# Question
Title: Binary code with constraint
Suppose I have an alphabet of n symbols. I can efficiently encode them with $\lceil \log\_2n\rceil$-bits strings. For instance if n=8:
A: 0 0 0
B: 0 0 1
C: 0 1 0
D: 0 1 1
E: 1 0 0
F: 1 0 1
G: 1 1 0
H: 1 1 1

Now I have the additional constraint that each **column** must contain at most p bits set to 1. For instance for p=2 (and n=8), a possible solution is:
A: 0 0 0 0 0
B: 0 0 0 0 1
C: 0 0 1 0 0
D: 0 0 1 1 0
E: 0 1 0 0 0
F: 0 1 0 1 0
G: 1 0 0 0 0
H: 1 0 0 0 1

Given n and p, does an algorithm exist to find an optimal encoding (shortest length) ? (and can it be proved that it computes an optimal solution?)

**EDIT**

Two approaches have been proposed so far to estimate a lower bound on the number of bits $m$. The goal of this section is to provide an analysis and a comparaison of the two answers, in order to explain the choice for the *best answer*.

Yuval's approach is based on entropy and provides a very nice lower bound: $\frac{logn}{h(p/n)}$ where $h(x) = xlogx + (1-x)log(x)$.

Alex's approach is based on combinatorics. If we develop his reasonning a bit more, it is also possible to compute a very good lower bound:

Given $m$ the number of bits $\geq\lceil log\_2(n)\rceil$, there exists a unique $k$ such that $$ 1+\binom{m}{1} + ... +\binom{m}{k} \lt n \leq 1+\binom{m}{1} + ... + \binom{m}{k}+\binom{m}{k+1}$$ One can convince himself that an optimal solution will use the codeword with all bits low, then the codewords with 1 bit high, 2 bits high, ..., k bits high. For the $n-1-\binom{m}{1}-...-\binom{m}{k}$ remaining symbols to encode, it is not clear at all which codewords it is optimal to use but, for sure the weights $w\_i$ of each column will be bigger than they would be if we could use only codewords with $k+1$ bits high and have $|w\_i - w\_j| \leq 1$ for all $i, j$. Therefore one can lower bound $p=max(w\_i)$ with $$p\_m = 0 + 1 + \binom{m-1}{2} +... + \binom{m-1}{k-1} + \lceil \frac{(n-1-\binom{m}{1}-...-\binom{m}{k}) (k+1)}{m} \rceil$$

Now, given $n$ and $p$, try to estimate $m$. We know that $p\_m \leq p$ so if $p \lt p\_{m'}$, then $m' \lt m$. This gives the lower bound for $m$. First compute the $p\_m$ then find the biggest $m'$ such that $p \lt p\_{m'}$

This is what we obtain if we plot, for $n=1000$, the two lower bounds together, the lower bound based on entropy in green, the one based on the combinatorics reasonning above in blue, we get:

Both look very similar. However if we plot the **difference** between the two lower bounds, it is clear that the lower bound based on combinatorics reasonning is better overall, especially for small values of $p$.

I believe that the problem comes from the fact that the inequality $H(X) \leq \sum H(X\_i)$ is weaker when $p$ gets smaller, because the individual coordinates become correlated with small $p$. However this is still a very good lower bound when $p=\Omega(n)$.

Here is the script (python3) that was used to compute the lower bounds:

```
from scipy.misc import comb
from math import log, ceil, floor
from matplotlib.pyplot import plot, show, legend, xlabel, ylabel

# compute p_m
def lowerp(n, m):
  acc = 1
  k = 0
  while acc + comb(m, k+1) < n:
    acc+=comb(m, k+1)
    k+=1

  pm = 0
  for i in range(k):
    pm += comb(m-1, i)

  return pm + ceil((n-acc)*(k+1)/m)

if __name__ == '__main__':
  n = 100

  # compute lower bound based on combinatorics
  pm = [lowerp(n, m) for m in range(ceil(log(n)/log(2)), n)]
  mp  = []
  p = 1
  i = len(pm) - 1
  while i>= 0:
    while i>=0 and pm[i] <= p: i-=1
    mp.append(i+ceil(log(n)/log(2)))
    p+=1
  plot(range(1, p), mp)

  # compute lower bound based on entropy
  lb = [ceil(log(n)/(p/n*log(n/p)+(n-p)/n*log(n/(n-p)))) for p in range(1,p)]
  plot(range(1, p), lb)

  xlabel('p')
  ylabel('m')
  show()

  # plot diff
  plot(range(1, p), [a-b for a, b in zip(mp, lb)])
  xlabel('p')
  ylabel('m')
  show()

```

# Answer
There is an additional lower bound we can build, that will address cases like what @user3017842 mentioned in their comment on Yuval's answer. (Cases where $p$ is particularly small.) Suppose we knew $m$ already: Then we have $pm$ bits high total across all codewords. Since we're interested the cases where $p$ is small, we view these high bits as our limiting resource, and want to build a code with it (and see how many codewords we can possibly get out). We can have 1 codeword with all 0s, then $m$ codewords with a single 1, then $m \choose 2$ with two 1s, etc. If we call the highest number of bits in a codeword $k$, then $$pm = 0\cdot 1 + 1\cdot m + 2\cdot {m \choose 2}+... \le \sum\_i^k i{m \choose i}$$ While our number of codewords $n$ is similarly bounded by $$n \le \sum\_i^k {m \choose i}$$ If we look at the case where $p \le m$, then $k \le 2$ is already implied by the first inequality. ($pm = m^2 = m + 2{m \choose 2}$). So then the code would consist of the $0$-word, $m$ single-$1$-words, and $(p-1)m/2$ two-$1$-words. Thus $$ n \le 1 + m + (p-1)m/2 $$ or inverting $$ m \ge \frac{2(n-1)}{p+1} .$$ This will yield the tight lower bound of $m\ge 5$ on the example you provide, but as mentioned before, will probably only be very useful while $p \approx m$ (or $p \approx \sqrt n$).
> 3 votes

# Answer
Here is a lower bound and an asymptotically matching construction, at least for some ranges of the parameters. Denote by $m$ the number of columns, and suppose for simplicity that $p \leq n/2$.

We start with a lower bound on $m$. Let $X$ be the encoding of symbol chosen uniformly at random. Let $X\_1,\ldots,X\_m$ be the individual coordinates, and let $w\_i \leq p$ be the weight of the $i$th column. Then $$ \log n = H(X) \leq \sum\_{i=1}^m H(X\_i) = \sum\_{i=1}^m h(w\_i/n) \leq m h(p/n). $$ Therefore $$ m \geq \frac{\log n}{h(p/n)}. $$ Here $H$ is the entropy of a random variable $H(X) = -\sum\_x \Pr\[X=x\] \log \Pr\[X=x\]$ and $h$ is the entropy function $h(x) = -x\log x-(1-x)\log(1-x)$. (You can use whatever base for the logarithm you want.)

The asymptotically matching construction, that should work for $p = \Omega(n)$, chooses $m$ a bit larger than this lower bound, and chooses a random encoding scheme, each bit being set to $1$ with some probability $q/n$ which is a bit smaller than $p/n$. Choosing the parameters correctly, we should get that this results in a legal encoding (all codewords are different and all column weights are at most $p$) with positive probability.
> 4 votes

# Answer
Here is a simple search methodology. We start from some lower-bound on the number of bits and then try to find a legal encoding. Specifically.

Let m be the current number of bits. Encode symbol i as bi1, bi2, ..., bim.

Constraints: bi xor bj isn't 0 - in other words each symbol's encoding is unique

For all j: sum\_i bij \<= p.

This is a pseudo-boolean satisfiability problem (well it can easily be encoded as a standard satifiability problem). So just keep increasing m until you find one that is satisfiable (or do a binary search using lower and upper bounds to find the minimal m).

Of course, this doesn't guarantee that in practice you'll be able to actually find the minimal m, the SAT check could timeout.
> 0 votes

---
Tags: coding-theory
---