# Question
Title: Time interval correction for step detection algorithm
I am currently going over this paper, and in fact have already tried to implement it:

https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4634483/ \[1\]

Paper looks at the amplitude of the step and the time between the swings. ALthough I seem to understand the general idea, I am slightly confused about one of the formulas, which describes time between steps, namely:

*"To extract only one valley from a gathered group of valley candidates in a very short time range, every valley candidate is validated by checking the time distance to the recent valley using the following threshold.*

*$Th\_v = \mu\_v - (\sigma\_v/\beta)$*

*where $\mu\_v$ and $\sigma\_v$ represent the average and the standard deviation of the time interval between adjacent valleys in the magnitude of acceleration, respectively. These averages and the standard deviations are calculated for recent M peaks or valleys.*"\*

Except time threshold obviously magnitude is also taken into consideration.

So I have produced magnitudes that I obtain from my sensor:

where red dots correspond to initially discovered valleys and purple to points that should re-evaluate last valley.

So what I currently have is something like this:

**1)** I obtain valley at point 20. I obtain valley at Point 49. This *should* mean that the average distance between two valleys is 29 readings, and therefore I set my $\mu\_v = 29 and \sigma = 0$, which yields me a value of $Th\_v=29$ ( my $\beta = 1/3$). I also store the difference (29).

**2)** Then I get to point 51, which should update the $Th\_v$ value. So now I calculate the mean, which I think means $(29 + (51-49))/2 = 15.5$

And calculate standard deviation, which equals $19.09$. So then when I actually plug these values in the formula above I get $Th\_v = -41.909$, which should not be possible as I believe this value should be always positive to indicate the time between two valleys.

Am I dong something incorrect or do you have any idea what's wrong with my or paper's approach?

References:

**\[1\]: Lee H, Choi S, Lee M. Step Detection Robust against the Dynamics of Smartphones. Wang X, ed. Sensors (Basel, Switzerland). 2015;15(10):27230-27250. doi:10.3390/s151027230.**

# Answer
> 0 votes
I managed to solve the problem of the algorithm by using a different approach. Algorithm is not clear on what is happening with the initial values or how to reliably capture a set of peak/valley candidates and how to deal with them.

Therefore, we decided to use only magnitude part of the paper, which radically simplifies the whole algorithm, and in fact works great ( assuming you are getting reasonable sensor readings).

---
Tags: algorithms
---


# Question
Title: Computing Hamming Distance Between Binary Vectors
Consider the following problem:

**Input:** We are given a set $S$ of $n$ binary vectors. A binary vector is of the form $(b\_0, b\_1, ... b\_n)$, where $b\_i \in \\{0, 1\\}$. Therefore, there are $n$ vectors of size $n$.

**Output:** For each vector in $S$, we would like to (efficiently) compute a list of binary vectors from $S$ whose Hamming distance is within some predefined constant $c$.

**Output (alternative):** Find the pair of vectors with minimum Hamming distance.

---

Clearly, the above can be done in $O(n^3)$ by computing the Hamming distance pairwise between each vector in *S* ($\frac{n\*(n+1)}{2}$ pairwise combinations and $O(n)$ to compute the Hamming distance). However, I am looking for something more efficient, since $n$ can take large values (say, $n=10^6$).

To speed up the computation, one could use some form of hashing, where we place the binary vectors into $N$ buckets, where every vector in the $i^{th}$ bucket contains exactly $i$ ones. This could work, but in my particular case, one could expect that all binary vectors have approximately the same number of ones, so not much would be gained from such hashing. One could also look to perform some sort of compression on binary vectors and perform Hamming distance computation on the smaller compressed vectors as a bound on the distance, but I suspect there are better approaches.

Another hashing approach would be to subdivide the space into hypercubes and place each vector in one of the cubes. I believe similar approaches are used in physics simulations, where space would be divided in a number of 2D- or 3D-cubes and then compute the interaction of elements within cubes and neighboring cubes.

I have seen variations of the above in many applications, but I am not sure what is the name of the problem or how to efficiently compute the solution. It is worth noting that in my particular case the solutions does not need to be "exact", that is, there can be some errors in the output as long as "most" of it is correct. The main issue seems to be how to avoid computing the distance between vectors that are clearly far apart.

(The structure of the binary vectors in $S$ can be diverse. In some cases, there are few bits set in each vector, while in other cases the vectors can be dense. For the sparse case, the Hamming distance computation can get greatly sped up, but the bottleneck is the $\frac{n\*(n+1)}{2}$ comparisons that need to be made.).

# Answer
You say in the comments that we might have $c \approx 15$ or so. There should be very efficient algorithms in this case, using locality sensitive hashing.

For example, here is a simple LSH. Randomly choose a set of about 10,000 indices (out of the 1,000,000). Hash each vector by computing some standard hash of the 10,000 bits in those positions (ignoring the other 990,000 bits entirely). Store all the vectors in a hashtable using this hash. Now look for all pairs of vectors that have the same hash. This can be done by storing all the vectors in a hashtable using this hash and looking at all collisions within a single hash bucket, or by sorting the hashes and looking at adjacent pairs.

Suppose the pair of vectors $b\_i,b\_j$ are at distance $\le 15$. Then with probability about 0.86, they will agree in the selected 10,000 positions and thus have the same hash. In other words, about 86% of the pairs of vectors at distance $\le 15$ will be found in this way.

Now you can repeat this multiple times to ensure you find all of the pairs, with high likelihood. If you repeat this about 10 times with a different random set of indices each time, then only about $10^{-8}$ of the pairs that are close will be missed. If you repeat it 100 times, each close pair has only a $10^{-85}$ probability to be missed. That probability is so low it can be safely ignored: essentially, all close pairs will be found.

The running time is $O(n^2)$: $O(n)$ time to compute each hash, and then you do that $n$ times for $n$ different vectors. In practice it might be even faster than that if you can take advantage of the fact that most of the bit positions are ignored during the hashing.
> 3 votes

---
Tags: algorithms, hamming-code, binary
---


# Question
Title: What is the recurrence form of Bubble-Sort
I understand how bubble sort works and why it is O(n^2) conceptually but I would like to do a proof of this for a paper using the master theorem.

As an example: The recurrence form for merge sort is T(n) = 2T(n/2) + O(n) which, using the master theorem, gives us O(n log(n)).

I am unsure of how to do this process with Bubble sort. What equation allows us to see that it is O(n^2)?

# Answer
Bubble sort uses the so-called "decrease-by-one" technique, a kind of divide-and-conquer. Its recurrence can be written as

$$T(n) = T(n-1) + (n-1).$$
> 4 votes

# Answer
As user fade2black points out in their comment, Bubble Sort is not an algorithm that employs the typical divide-and-conquer strategy to solve the problem of sorting. Having said that, let us now derive the running time of Bubble Sort. Before that, let's look at the algorithm itself:

> **Input**: An array $A\[1,\cdots,n\]$
> **Output**: array $A$ sorted in order of non-decreasing elements.
>
> $\mathsf{BubbleSort(A)}$:
> $\quad n = A.length$
> $\quad \mathsf{for}\ i = 1\ \mathsf{to}\ n$
> $\qquad \mathsf{for}\ j = 1\ \mathsf{to}\ n-i$
> $\qquad \quad \mathsf{if(}A\[j\]\>A\[j+1\]\mathsf{)}$
> $\qquad \qquad \mathsf{swap(}A\[j\],A\[j+1\]\mathsf{)}$
> $\mathsf{END}$

Now firstly, if we measure running time as the number of comparisons performed by $\mathsf{BubbleSort}$, then we observe that for each iteration of loop variable $i$, there are $n-i$ comparisons being made. Thus, total number of comparisons performed is: $\sum\_{i=1}^nn-i = \frac{n(n-1)}{2} \in \Theta(n^2)$

Suppose instead of measuring performance/running time by number of comparisons, we want to do so by the number of $\mathsf{swap(x,y)}$ operations performed. It is difficult to estimate the average running time as measured in number of $\mathsf{swap}$ operations without making assumptions on the nature of distribution of the input set.

However, it is fairly simple if our interest is in the worst case performance - for any input size $n$, we try to choose the array $A$ that maximises the number of swaps. Clearly, we can't have more $\mathsf{swap}$ operations performed than the number of comparisons we make(convince yourself of this).

Thus, total number of $\mathsf{swap}$ operations required by a run of $\mathsf{BubbleSort}$ is $\leq \frac{n(n-1)}{2}$.

Now all that remains is to show that this is a tight bound and to do so, consider input of the form $A = \[n,n-1,\cdots,1\]$ i.e., in the input $A\[i\]=n-i+1$. It is easy to verify that this particular input *requires* exactly $\frac{n(n-1)}{2}\ \mathsf{swap}$ operations to produce the output. Thus, in the worst case, running time of $\mathsf{BubbleSort}$ measured in terms of $\mathsf{swap}$ performed is $\frac{n(n-1)}{2} \in \Theta(n^2)$.

In otherwords, agnostic to exact input, running time is $O(n^2)$
> 2 votes

---
Tags: time-complexity, recurrence-relation, master-theorem
---


# Question
Title: Minimal Deterministic Buchi Automata Product
**Problem:**

Let $\varphi = \varphi\_1 \land \varphi\_2$ be Deterministic Buchi Automata (DBA) expressible LTL formulas.

Let $A$, $A\_1$ and $A\_2$ be translated DBAs such that ${\cal{L}}(A) = {\cal{L}}(A\_1) \cap {\cal{L}}(A\_2)$.

What can be said about the relation between the number of states in $A$ and that in the synchronous product $A\_1 \otimes A\_2$?

**Some background:**

I found two definitions of the Buchi product, the one given by Vardi in An Automata-Theoretic Approach to Linear Temporal Logic that uses $S = S\_1 \times S\_2 \times \\{1, 2\\}$ while the one demonstrated in this presentation uses $S = S\_1 \times S\_2 \times \\{1, 2, 3\\}$.

Also, Ehlers has proposed an approach to minimize the DBA in this paper.

However, I have been unsuccessful in finding any rigorous mathematical relation between the sizes of translated DBA $A$ and the minimal synchronous product of $A\_1 \otimes A\_2$.

**My question:**

I would like to know about

1. Any work regarding the size of Minimal DBA Product
2. Any work about the relation between the number of states.
3. How to construct the minimal DBA Product, given $A\_1$ and $A\_2$.

# Answer
> 4 votes
This is only a partial answer (as I believe that the state of the art is insufficient to answer your questions completely - I am happy to be proven wrong here), but I hope that it helps you anyway.

1. First of all, note that when taking the conjunction of two automata with $n$ and $m$ states, the result having $nm - o(n) - o(m)$ states cannot be avoided. This follows pretty much from the fact that for deterministic automata over finite words, such a blow-up can also not be avoided. At the same time, we have an upper bound on $2nm$ many states for the product. For automata theory researchers, this is actually pretty tight.
2. The constructions given in the Vardi paper and the one given in the slide set you referred to are slightly different. Both have counters for keeping track of for which automaton an accepting state has to be visited next. In the slide set construction, after both automata have seen accepting states, goes to the counter value of 3, where in the product an accepting state is visited and then switches back to 1. Vardi (who attributes the construction to earlier work by another researcher) does it differently. In a nutshell, the idea is to recycle the accepting states from the factor automata, and to switch the counter only *after* an accepting state has just been seen. In this way, the "3" counter value is not neccessary, and the construction still works anyway.
3. As far as I know, there is no research that answers your questions completely. But you may be interested in Schewe's paper that shows that minimizing deterministic Buchi automata is NP-hard (The ArXiV version of the paper can be found here). I would not be surprised if you could base a proof that your problem 3 is NP-hard on his proof ideas. For the case that the factor automata are not already minimal, this proof would be trivial, but I assume that you want to start with minimally-sized automata.

---
Tags: automata, reference-request, formal-methods, linear-temporal-logic, buchi-automata
---


# Question
Title: Is it possible to write a wait free leader election algorithm?
I want to understand if there exists an algorithm which is wait free and operates on non-shared memory, asynchronously.

Finally I want to know how to derive the consensus number of this algorithm. Googling did not work.

# Answer
I believe that leader election derives from consensus algorithm, not other way around. When electing leader you need consensus about who was chosen.

I'm not sure what you understand by "wait free". All communication in distributed system is asynchronous, and you always need to *wait* for reply.

You could start all nodes with ordered list of all possible leaders. When leader goes down all nodes could just pick next one from the list. But again, to notice that leader goes down you need to ping it, and *wait* for response. And probably coordinate (create consensus) that we changed a leader (if not, you will have a problem when encountering partitions).

So, last option is to choose one leader at start (trough config) and not allow any change. But this does not fulfills requirements of most distributed system or leader election problem.
> 1 votes

---
Tags: distributed-systems, synchronization, consensus
---


# Question
Title: How to prove that for a full binary tree $T$ there's a series of frequencies such that Huffman alg. will produce $T$?
> How to prove that for a full (each node that's not a leaf has 2 nodes) binary tree $T$ of $n$ leaves there's a series of frequencies $f\_1,f\_2,...,f\_n$ such that if we use Huffman algorithm on the series we'll get $T$?

First in order to get frequencies from $T$ we can assign the probability of $\frac{1}{2^d}$ to each node where $d$ is the depth of a given node. The root node will have the probability of $1$ which means $100$%. After one traversal of $T$ we could fill the array with the frequencies of the leaves of $T$ (only leaves correspond to the the actual values to be encoded).

I'm not sure how to prove that if we apply Huffman algorithm to the frequencies one of the trees will happen to be $T$. It seems like if we build a tree from the frequencies each time such that the new tree is different (if possible) from the previous tree we'll eventually build $T$. Also we know that Huffman tree is always a full tree.

The Huffman algorithm is as follows (as described in Algorithm Design by Jon Kleinberg, Eva Tardos):

```
Huffman(S) {
  if |S|=2 {
    return tree with root and 2 leaves
  } else {
    let y and z be lowest-frequency letters in S
    S’ = S
    remove y and z from S’
    insert new letter ω in S’ with f_ω=f_y+f_z
    T’ = Huffman(S’)
    T=add two children y and z to leaf ω from T’
    return T
  }
}

```

# Answer
The proof is by induction. The case $n = 1$ is clear. For $n \> 1$, choose two leaves at maximal depths, and merge them. Huffman's algorithm could have chosen these two leaves at the first step and merged them. Now apply the inductive hypothesis to complete the proof.

Note that Huffman's algorithm, as described in your textbook, is non-deterministic in the sense that at any step there could be many valid choices. Any actual implementation of the algorithm will use a tie-breaking rule to arbitrarily choose which two leaves of minimal probability to merge at any given step.
> 2 votes

---
Tags: algorithms, graphs, trees, huffman-coding
---


# Question
Title: If $L$ is recursive then so is $L^*$, and vice versa
Given a language $L$ over the alphabet $\\{0,1\\}$. Let $L^\*= \\{ w\_1w\_2...w\_n | n \ge 0, w\_1,...,w\_n \in L\\}$.

Prove:

1. If $L$ is recursive, then $L^\*$ is recursive as well.
2. If $L^\*$ is recursive, then $L$ is recursive as well.

For the first proof I have this idea:
If $L$ is recursive, then a turing machine $M\_L$ can decide all the words $\\{w|w \in L\\}$. So $M\_L$ can decide $\\{w\_1,...,w\_n | w\_1w\_2...w\_n \in L^\*\\}$ and appearently it can decide $L^\*$ as well.

For the second proof I tried the same but actually it does not work that way. Any hints and ideas?

# Answer
The second claim is wrong. Let $$ L = \\{0,1\\} \cup \\{010^n : \text{the $n$th Turing machine halts}\\}. $$ Then $L^\* = \\{0,1\\}^\*$ is recursive, but $L$ isn't recursive.

For the first claim, your proof is not convincing. You need to explain how a Turing machine can decide whether a given word $w \in \\{0,1\\}^\*$ can be written as a sequence of words from $L$. One way is to consider all possible partitions into non-empty subwords, and check whether one of them has the property that all subwords are in $L$.
> 4 votes

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


# Question
Title: DFA for even number of As, odd number of Bs and precisely one C
Exactly as the title says, I'm looking for a DFA for an even number of A, odd number of B, and exactly one C, can anyone help with this?

Thanks

# Answer
Divide and conquer. You could design a DFA over the alphabet $\Sigma = \\{A,B,C\\}$

* for an even number of A, call it $M\_1$
* for an odd number of B, call it $M\_2$
* accepting exactly one C, call it $M\_3$

Then design a new DFA equivalent to $M\_1 \cap M\_2 \cap M\_3$ (by closure properties of regular languages).
> 1 votes

# Answer
A common idiom for problems like this is to use the states to remember what has been seen so far: are there an even number of A's or not; are there an even number of B's or not; are there 0, 1, 2 or more C's?

For example, having seen the input ABAABCA, we would be in state (even A's, even B's, 1 C) and then if we see an A we would pass to state (odd A's, even B's, 1 C). I'll leave it to you to determine which of the twelve states should be the start and which should be the final state.
> 1 votes

---
Tags: finite-automata
---


# Question
Title: Finding a string with some specified hamming distances from other strings
I'm searching the space of length $n$ strings (a-z lowercase), which I suppose we could represent as a large graph of strings and hamming distances between the strings.

I'm given some pairs of strings and distances $v\_i, d\_i$ . I need to find a string which has distance $d\_i$ from each each string $v\_i$ .

Does there exist an efficient algorithm for finding this? Perhaps it's possible to triangulate to the right string?

# Answer
Your problem is likely hard. I will consider a decision version of your problem in which the goal is to ask whether there exists any solution. I will show that the binary variant is NP-complete, and the same ideas probably imply that this decision version of your problem is also NP-complete.

Other decision versions of your problem are likely also hard, though perhaps not NP-hard. For example, consider the problem in which you are promised that a unique solution exists, and your goal is to determine the value of its first bit. This problem cannot be NP-hard since it has the same complexity as its complement. Nevertheless, it is probably hard in some other, appropriate sense.

The decision version of your problem that I will analyze asks whether there is an answer. The problem is clearly in NP, and we prove that it is NP-hard by reduction from X3SAT, a variant of 3SAT in which a formula is satisfiable if every clause contains *exactly* one satisfied literal. Given a 3CNF on $n$ variables $x\_1,\ldots,x\_n$, we will consider strings of length $2n$ which encode a truth assignment: a 1 in position $2(i-1)+1$ encodes that $x\_i$ is true, and a 1 in position $2(i-1)+2$ encodes that $x\_i$ is false.

In order to force that any solution must have exactly one 1 in each of the positions $2(i-1)+1,2(i-1)+2$, we ask that it have distance $n$ from the strings $(00)^n$ and $(00)^{i-1}(11)(00)^{n-i}$ for $1 \leq i \leq n$. In order to force any solution to satisfy all clauses, for every clause we take the string which has 1s in the positions corresponding to the literals in the clause, and we ask that the solution be at distance $(n-3)+2$ from this string. A string satisfies these $n+m+1$ constraints (where $m$ is the number of clauses) if and only if it is a satisfying assignment to the given 3CNF.
> 2 votes

---
Tags: complexity-theory, graphs, strings
---


title: Short quiz about Myhill-Nerode theorem

text:
# Question
Title: Short quiz about Myhill-Nerode theorem
Given is DFA M:

1.) `abb` and `bbb`

2.) `baa` and `ab`

3.) `a` and `ε` (where `ε` is the empty word)

4.) `abb` and `baa`

If I understood correctly, `x` and `y` are equivalent to each other (in terms of Nerode), if you add the same suffix for both such that they can be read by the DFA, e.g. they are in `L(M)`

Thus 1.) is false because `abb` throws us into the "endless" state `5`, there is no escape and thus no suffix.

2.) Is true, simply add suffix `aa` and both words will still be accepted.

3.) True, take `a` as suffix.

4.) False, same reason as 1.) you get into the endless state and there is no escape, thus no suffix.

---

Can you confirm if this is correct? Or did I understand the entire concept wrong? :o

# Answer
> 2 votes
You are mistaken. Strings $x$ and $y$ are equivalent modulo the language $L$ iff for **all** suffixes added to the words the results are both in or both outside of the language:

$x\sim\_L y$ iff $xw\in L \iff yw\in L$ for every $w$.

In particular, when the strings $x$ and $y$ end in the same state for the (deterministic) automaton $M$, then $x\sim\_{L(M)} y$, as they can be extended by exactly the same strings. This also holds for the dead-end state where no strings can extend the original string to acceptance.

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


# Question
Title: Why 2 way DFA have the same power as one way DFA?
I was looking through some papers online on the equivalence of 2-way DFA and 1-way DFA and I couldn't find a simpler explanation on why 2DFAs are no more powerful than ordinary DFA. I wanted to write a simpler explanation of why this is the case so anyone who is new to the topic could understand without much trouble.

It would be helpful if someone could point me to some resources on the topic that are simple to understand

# Answer
The intuitive explanation why two-way DFA and NFA are not more powerful than DFA is that all these variations have finite memory. A non-deterministic or two-way automaton has more memory per state than a basic DFA, but as long as there's only a finite amount of memory, a fancy automaton is no more powerful than a DFA with perhaps more states.

A two-way DFA can retrace its steps, but it has no memory of it. When the automaton is at a certain position in the input, the only thing that encodes how it got there is the state, and it's taken from a finite state. So there's no way for the automaton to behave differently based on the position or the movement history.

Let's look a bit more precisely at how a DFA can simulate a two-way DFA, i.e. how the memory of a two-way DFA can be represented in a DFA. The states of a DFA represent all that is known about the input after reading a prefix of the input. Reading a word $uv$ can be decomposed into 1. reading $u$ from the initial state and 2. reading $v$ from the state reached after reading $u$. The information about the partial input $u$ that the DFA remembers is simply the state reached after reading $u$.

Before studying this for a 2DFA, let's do it for an NFA. An NFA reads its input sequentially from left to right like a DFA, but at each stage, any set of states of the NFA may potentially be reached. Thus, the information about a partial input that the NFA remembers is the set of reached states. There are at most $2^n$ sets of states in a world with $n$ states, and therefore an NFA with $n$ states can be simulated by a DFA with at most $2^n$ states. This is in fact a tight bound.

In an NFA with $n$ states, the amount of information in the system is encoded in the set of reachable states. Each new input character triggers a transition from a set of states to a new set of states. Since there are $2^n$ sets of states, an NFA can be converted to a DFA that recognizes the same language and that has at most $2^n$ states.

Let's now turn to a two-way DFA with $n$ states. After reading some input $u$, the 2DFA remembers what state it has reached. In addition, after reading more input, the 2DFA may backtrack into $u$ and, perhaps, come back out. We want to abstract $u$ away completely, so we need to count all the ways to backtrack into $u$ and come back. If the 2DFA ever backtracks into $u$, it may do so from any state $q$ amongst its $n$ states. When it comes back out, it will have reached some other state $q'$ (perhaps the same, it doesn't matter). The state $q'$ depends on $q$ and $u$, but it doesn't depend on what comes after $u$, since by definition $q'$ is the state reached after working through $u$ in a deterministic automaton. Therefore each prefix $u$ defines a mapping from $q$ to $q'$. The information stored in the 2DFA after processing $u$ consists of the initial exit state (which state is reached immediately after reaching the end of $u$) and the mapping from reentry state to subsequent exit state. (I don't claim that all mappings are possible.) There are $n$ initial exit states, and $n^n$ mappings of state to state. Thus the information in a 2DFA after processing some prefix consists of at most $n \times n^n$ different possibilities. This means that a 2DFA can be simulated by a DFA with at most $n \times n^n = n^{n+1}$ states.

The tight bound is in fact $n \times (n^n - (n-1)^n)$. I don't have an intuition for the second term.
> 5 votes

---
Tags: automata, finite-automata
---


# Question
Title: Are synchronous message sends a subset of async. ones?
Imagine any object oriented PL based around the idea of message sends: some method basically performs something like this:

```
send(target=someTarget, sender=self, message=someMessage)

```

Also, most of the PL allow for async message communications, where you can issue multiple messages to multiple targets and then "yield" to scheduler.
My question is: are synchronous communcations a subset of asynchronous ones?
In my head you can break down any synchronous message send into something like this:

```
asyncSend(target=someTarget, sender=self, message=someMessage)
target.setNotify(self)
self.setBlocked()
yield

```

Which will be totally aquivalent to a synchronous message send, BUT:

The problem I currently see if you try to mix these two together. When some method issues an async message send and then, before yielding, performs a synchronous message send, which gets kinda messed up. Hence the question :)

Also, sorry if this is wrong stackexchange. I don't think this question applies to the usual SO.

EDIT1: rephrasing the question: which of both concepts is more general? can you even say that?

# Answer
> 3 votes
There are several possible semantics for asynchronous message passing, so there isn't a single answer to this question. It depends how the scheduler works.

From a theoretical perspective, the simplest model (for some version of simple) is to not have a scheduler. Once a message has been emitted, it may be received at any time when the receiver is ready. All the parts of the system work in parallel. This is the principle of process calculi, of which there is a rich theory.

The notion of synchronicity then depends on what the continuation of a send operation is. In the pi calculus, which is arguably the most important model of concurrency, sending is a synchronous operation, with a continuation. $\bar a\langle x\rangle.P$ (“send $x$ on $a$ then do $P$”) blocks until some other part of the system is ready to receive a message on $a$. An asynchronous send operation is represented by doing the send in parallel with something else:

```
asyncSend(target=a, message=x);
stuff();

```

is represented by $(\bar a\langle x\rangle. 0) \mid \mathtt{stuff}$ (send $x$ on $a$, then do nothing; all of this in parallel with `stuff`).

The join calculus is another process calculus inspired from the pi-calculus. It defines both asynchronous and synchronous messages. Synchronous messages act like function calls — they're remote procedure calls. Asynchronous messages have no continuation: once the order to send the message has been given, the message will sit around until it gets received; the only way to know that the message has been received is to take action on the receiver. The snippet above is represented by $a\langle x\rangle \mid \mathtt{stuff}$. The notation $a\langle x\rangle$ means “send $x$ asynchronously on $a$”; there's no continuation for the send operation: $\color{red}{a\langle x\rangle; Z}$ is not even syntactically valid. A synchronous call can be encoded with asynchronous calls by having the receiver reply. If the receiver sends an acknowledgement: $$ a\langle x\rangle \mapsto \mathtt{ack}\langle\rangle \mid \ldots$$ then the sender can wait for this acknowledgement: $$ a\langle x\rangle \mid (\mathtt{ack}\langle\rangle \mapsto \ldots) $$ models

```
syncSend(target=a, message=x);
...

```

In the join calculus, synchronous and asynchronous operations are distinguished in the syntax. Therefore there's no possibility of “getting messed up”.

The mess comes from trying to force concurrent behavior into a sequential framework. Since you mention object oriented languages (which have absolutely nothing to do whatsoever about asynchronous message passing), you're probably thinking of implementations of these concepts in languages like Java and C#. I'm not familiar with those libraries, but as far as I know, they introduce additional complications by forcing the programmer to be explicit about threads. Threads are not a natural concept in process calculi: if things happen in a certain order, it's because of how the information is propagated, not because the language describes how a scheduler will do its job. A call like `asyncSend` may have additional constraints on when it takes place relative to other things that are going on in the same thread. If there is some constraint between an asynchronous send and a subsequent synchronous send, that's a limitation of the library which defines when the asynchronous send may take place. A true asynchronous send would not have such a constraint.

---
Tags: concurrency, object-oriented, message-passing
---


# Question
Title: Given an integer n, print all integers from 1 to 2^n. Why does this not prove that P!=NP?
I only just recently learned about the P=NP problem in introduction to algorithms class, and I'm still trying to wrap my head around it. I thought of this situation while cleaning my room today and couldn't think of a way to disprove it to myself. Perhaps it

Obviously, the algorithm described in the title would have to iterate 2^n times to print all numbers from 1 to 2^n. As a result, this algorithm would never be able to be done in polynomial time and P is indeed a proper subset of NP. What is the error in my reasoning here? Is it that this problem is not in NP?

# Answer
> 3 votes
NP is the set of problems that can be *verified* in polynomial time, i.e. there is a polynomial-time algorithm that can verify a purported solution. P is the set of problems that can be *solved* in polynomial time, i.e. there is a polynomial-time algorithm that can *find* a solution.

“The problems in NP are those not able to be solved in polynomial time” is completely wrong. This is not at all what NP means. The N in NP is for “nondeterministic”, not for “not”. A problem in NP may be solvable in polynomial time — P is a subset of NP. The question “P = NP?” is in fact whether *all* problems in NP are solvable in polynomial time.

The set of problems that cannot be solved in polynomial time is the complement of P.

Note that “problem” has a specific technical meaning: it's a decision problem, i.e. an function from some input space to $\\{\mathrm{yes}, \mathrm{no}\\}$.

Counting is not a decision problem, so it doesn't fit in the classification that includes P and NP.

If you found a decision problem that cannot be solved in less than $2^n$ steps where $n$ is the size of the input, then that problem would not be in P. It might not be in NP either: it would only be in NP if there was a way to verify a solution in polynomial time.

---
Tags: algorithms, p-vs-np
---


# Question
Title: Showing the predicate $n \leq \sqrt2 < n+1$ is primitive recursive
Let h(x) be the integer n such that $n \leq \sqrt2 \< n+1$ Show that h(x) is primitive recursive.

I know how primitive recursive functions are defined, but showing an integer is primitive recursive is throwing me off. I need some help starting the proof.

# Answer
This relation can be written as $$n \leq \sqrt{2} \text{ and } n+1 \> \sqrt{2}$$ or equivalently $$ ((n^2 \< 2) \text{ or } (n^2 = 2)) \text{ and } ((n+1)^2 \> 2)$$ In terms of functions $$h(n) = and\[or\[ls(sqr(n),2), eq(sqr(n),2)\], gr(sqr(n+1),2)\]$$ So, we have exponentiation (squaring), increment by $1$ (i.e. $n+1$), less than, equal to, greater than, conjunction, and disjunction. They are all primitive recursive whose composition result in the primitive recursive predicate $h(n)$ equal to $1$ if $n \leq \sqrt{2} \text{ and } n+1 \> \sqrt{2}$, and $0$ otherwise.

**On @chi's hint**:

In fact this predicate is true for only $n=1$. So this predicate is drastically simplified and takes the following form $$h(n)=eq(1,n)$$
> 3 votes

---
Tags: computability, primitive-recursion
---


title: Flows with Negative Values?

text:
# Question
Title: Flows with Negative Values?
Define a "non-standard" flow to be a flow where the quantity flowing through an edge may be negative.

> Formally, given a directed graph $G$, and two designated and distinct vertices $s$ and $t$ (such that no edges are leaving $t$, and no edges are entering $s$), a non-standard flow $f : G\_E \to \mathbb{R}$ is a valuation on the edges such that
>
> For each $v \in G\_V\setminus \\{s, t\\}$, the sum of the values of $f$ on the edges entering $v$ is equal to the sum of the values of $f$ on the edges leaving $v$.

Assuming all the capacities are positive, does the Max-Flow Min-Cut theorem still hold for non-standard flows?

Furthermore, is there a network with positive edge capacities, such that the maximum non-standard flow through the network is larger than the maximum (standard) flow through the network?

The standard proof for Max-Flow Min-Cut theorem uses the non-negativity of the flow to claim that each flow is smaller than each cut. I would guess that this tells us that the counterexample (if any) would have a cut that has negative flow into its incoming edges.

# Answer
> 4 votes
The maximum flow calculated using only positive flow values on each edge can indeed be smaller than the maximum if flow can also be negative. You can easily see why in a trivial graph with only two nodes and two edges:

```
  ---- capacity 1 --->
A                      B
  <--- capacity 1 ----

```

If `A` is the source node and `B` is the sink, you can obviously see that if only positive flows are allowed, you get a max flow of `1` but if negative flows are allowed you'd get `2` (with the bottom edge flowing "backwards").

As I commented, the way to figure out the capacity of a graph that allows negative flows as well as positive ones is to restate the problem. Instead of allowing negative flows, add an additional reversed edge everywhere there's a normal edge in the original graph. Then solve the problem with only positive flows. In the trivial example above, you'd have two edges running each direction, and when you found the maximum using only positive flows, you'd get the right answer, `2`.

---
Tags: network-flow
---


# Question
Title: Hackerearth practice problem not able to understand
I am not able to understand below problem, mainly the example. I have tried to ask explanation in their website but not received help yet.

how they are calculating 36 and 43? and why 36+43 = 30$ is written?

Can I get a diagram visualizing this, because I think wood cutter should cost 12$ because only 3\*4 area is needed.

**Practice Problem on HackerEarth:-**

Ad-optimization team is moving to their new office Safina Towers :) . But the problem is Safina towers don't have furniture, but you have wood-sheet. You are given a wood-sheet of length L . Since everyone wants to create their desk in their own style you have to give them some amount of wood. So, you are given N mark-down points (since ad-optimization team have n members) from that points you have to cut the wood sheet. But the problem is wood-cutter will cost (Xleft) + (Y right) for cutting the wood (where left and right is the size of the remaining parts of the wood after cutting). For example you want to cut a wood sheet of length 10 and X=3 and Y=4 and you want to cut at point 7 then left segment size = (7-1) =6 and right segment size = (10-7) = 3 then wood cutter will cost 36+43 = 30$ .

Question Link

# Answer
Most simple explanation: The problem has been written down *at hackerearth* in some markup "language" not mastered by the author. Multiplication has been denoted using an asterisk `*` instead of a multiplication sign `×` (regrettably common since the introduction of type-writers). The markup seems to define that as a toggle between "normal" and "stand-out" text modes: there is a multiplication sign missing everywhere the text alternates between standard and italics. My stab at correction:

> Ad-optimization team is moving to their new office Safina Towers :). But the problem is Safina towers don't have furniture: You are given a wood-sheet of length *L*. Since everyone wants to create their desk in their own style you have to give them some amount of wood. So, you are given *N* mark-down points (since ad-optimization team has *N* members). From that points you have to cut the wood sheet. But the problem is wood-cutter will cost (X×*left*) + (Y×*right*) for cutting the wood (where *left* and *right* is the size of the remaining parts of the wood after cutting).
> For example you want to cut a wood sheet of length 10 and X=3 and Y=4 and you want to cut at point 7 then *left* segment size = (7-1) = 6 and *right* segment size = (10-7) = 3 then wood cutter will cost 3×6+4×3 = 30.
>
> As Amazonian you have to follow frugality leadership principal, you want to give wood cutter a minimum amount of money and want to cut wood-sheet from every marking point between 1 to *L* (exclusive). please note that in all the test case first mark point=1 and last mark point = size of sheet (*L*). Please output minimum amount of money needed for every test case.
>
> Input Format: T: number of test cases (1≤T≤5) For each test case:
>
> First line contains X and Y. (X: multiplier for *left* segment, Y: multiplier for *right* segment)
> 2≤X≤100 2≤Y≤100
>
> Second line Contains N: Number of marking points (2≤*N*≤100)
>
> Third line contains marking point : m(0), m(1) … , m(n-1) marking points on wood sheet, where m(0)=1, m(n-1)=*L* and 2≤*L*≤200000
>
> Output: For each test case : Minimum amount of money you have to pay to wood cutter. Each test case answer must be printed on a new line.
> 2 votes

---
Tags: algorithms, minimum-cuts
---


# Question
Title: How can you define the notion of "state" using only a type theory language?
The notion of state I'm referring to is the one described in this wikipedia page : https://en.m.wikipedia.org/wiki/State\_(computer\_science)

Which defines it in this way: "a program is described as stateful if it is designed to remember preceding events or user interactions; \[1\] the remembered information is called the state of the system."

My question is: Does there exist one or more formal definitions/descriptions that correspond to this notion of "state", in a formal system of Type theory (might be system F , simply typed lambda calculus or any other)

# Answer
> 0 votes
I am not sure what your question exactly covers. But to have a more formal definition of "State" it could be useful to look at the State Monad in Haskell. Haskell is a functional programming language which operates different compared to a imperative programming language (like Java or C).

---
Tags: formal-languages
---


# Question
Title: What will be T(n) after second step in a Recurrence Relation
T(n) = 2T(n-1) + n

Using back Substitution at first step we get

T(n) = 4 T(n-2) + 2(n-1) +n

If i go further one more step then what i am getting is

T(n) = 16 T(n-4) + 8(n-3) +4(n-2) + 2(n-1) +n

# Answer
Let's consider a simpler recursion:

$$ T(n) = T(n-1). $$

Using back substitution, we get $T(n) = T(n-2)$, $T(n) = T(n-3)$, $T(n) = T(n-4)$, and so on.

What you do is go first to $T(n) = T(n-2)$, and then substitute this equation into itself to get $T(n) = T(n-4)$. So you're skipping a step.
> 0 votes

# Answer
What you get is correct, but you haven't gone further one more step, but two more steps.

T(n) = 2T(n - 1) + n

First :

T(n - 1) = 2T(n - 2) + (n - 1)

T(n) = 4T(n - 2) + 2(n - 1) + n

Second :

T(n - 2) = 2T(n - 3) + (n - 2)

T(n) = 8T(n - 3) + 4(n - 2) + 2(n - 1) + n

Third :

T(n - 3) = 2T(n - 4) + (n - 3)

T(n) = 16T(n - 4) + 8(n - 3) + 4(n - 2) + 2(n - 1) + n
> 1 votes

---
Tags: algorithms, algorithm-analysis
---


# Question
Title: Is there a regular grammar for the language $\{ w : |w|_0 = |w|_1 \}$?
I need to prove whether the language $ L = \\{w \in \\{0,1\\}^\* \mid |w|\_0 = |w|\_1 \\}$ can be written as a regular grammar. Obviously it can, but how do I prove it?

# Answer
A language can be described by a regular grammar if and only if it is regular. Your language is nor regular, hence it cannot be described as a regular grammar.
> 0 votes

# Answer
That's not a formal proof, but some intuition that can be used sometimes to distinguish between regular & no-regular languages :

The constraint is : number of 0s equals number of 1s. Since we can have any number of 0s, and if we want to assign a state that tells how much 0s we have generated, we would have an infinite number of states. Thus, we can't use states to guide us, we need something like a memory to remember how much 0s we have at a certain instant. Knowing that regular languages are those that are recognized by FA's, in addition with the fact that FA's don't have memory, it's impossible to build a finite automaton to recognize that language. We can conclude prematurely that the language isn't regular.
> 0 votes

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


title: Vertex deletion to perfect matching

text:
# Question
Title: Vertex deletion to perfect matching
You are given a Graph G and an integer k.

The question is: Does G contain a vertex set X of size at most k such that deleting X results in a graph of degree at most 1?

Design an FPT (or a kernelization) algorithm for this problem and argue why it is correct.

Hint: Observe that vertices of higher degree must be "dealt with" somehow.

I do not exactly know where to start. I suppose that some reduction rules can be applied first, but not so sure what those can be (probably something that "deals with" vertices of higher degree.

Any ideas?

# Answer
> 1 votes
I'm not sure about the FPT algorithm, but I have an idea for the kernelization.

All vertices with degree \> k + 1 must be in X, since otherwise you would have to pick all but one of its neighbours which would make |X| \> k. So you can delete a vertex with degree \> k + 1 and rerun the algorithm with the remaining graph and k = k - 1.

You can also delete any vertices with degree 0, as their deletion doesn't change the degree of any other vertices.

---
Tags: graphs, kernel-functions
---


# Question
Title: Does the following algorithm has amortized constant time per element?
Consider the following streaming \`\`algorithms'':

1. When an element $x$ arrives, flip a fair coin until it shows \`\`heads''.
2. Fix a random hash function $h:U\to\\{0,1\\}^\infty$ (i.e., it maps elements into infinite bit strings). When an element $x$ arrives, do $LZ(h(x))$ operations, where $LZ$ is the number of leading zeros in $h(x)$. Notice that for any element $x$, the distribution of time spent is same as in (1).

Clearly, both algorithms spend in expectation $O(1)$ time per element, and their worst case is unbounded.

The key difference is that algorithm (1) makes the coin flips independently for each arrival, and (2) fixes a distribution such that every time $x$ arrives, it spends the same amount of time.

(1) should clearly be called amortized constant time. (2), however, might spend more than constant time if the input consists of many appearances of an element $x$ for which $LZ(h(x))$ is large.

> **Would you consider (2) to have an \`\`amortized'' constant time?**

If not, is there anything more accurate than saying that it has "expected constant time per element"?

---

While these \`\`algorithms'' are clearly useless, there exist algorithms with a runtime similar to (2) (e.g., see here).

# Answer
I wouldn't use the word amortized in this context, since there is no change of state between different operations (this is unlike classic examples for amortized analysis such as dynamic arrays). In that case amortized and worst case analysis will agree.

The first case is a randomized algorithm, so you can talk about the expected or worst case complexity (where in the former, the expectation is over the inner randomness of the algorithm). The worst case complexity is unbounded, while the expected number of operations is indeed constant.

In the second case, you have a fixed function $h$ which you use for all inputs, so again there isn't actually a change of state and thus there is no sense in talking about a recurring bad input. Note that the algorithm is not randomized (it does not toss coins after seeing the input), so the question you're looking for now is what is the average case complexity of your algorithm, where the expectation is over the choice of $x$ (relative to some distribution over $U$), and the random choice of $h$. For a completely random $h$, you will get the same answer as in the first case.
> 1 votes

---
Tags: algorithms, time-complexity, amortized-analysis
---


# Question
Title: Asymptotic Question - Determining average case runtime of linear search with summation formula
My confusion arises when solving the average case. I thought that it would be: 1/n * (number of elements)

But in the solution, they do 1/n * (sum of all the elements). I know that this all goes down to N when in big-o notation but why are they summing all elements of the array and how did they get to just the sum formula? I ended up with the same answer but my thought process was different.

**Question:** Consider linear search again. How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to be any element in the array? How about in the worst case? What are the average-case and worst-case running times of linear search in Θ-notation? Justify your answers.

**TextBook Answer**

The average should look for (n + 1) / 2 elements

The worst case is n

Assuming equal probability of occurrence 1/n, average number of elements which need to be checked is 1/n * (1 + 2 + ... +n) = (n+1)/2. Running time is Θ(n)

Worst case, the element to search is dead last in the array. In that case n elements need to be searched. Running time is Θ(n)

So all are Θ (n).

# Answer
> 2 votes
Suppose that it can be any element of your array. You'll have to consider, for $ 1 \<= i \<= n $ , what will be the cost if the searched element were at position $i$. If the element were in first position, it would cost $1$ iteration, at second $2$ iterations, and so on. So, if it were at position $i$, it would cost $i$ iterations. In addition, we have $n$ elements, with same chances, so the average cost is the average of the costs that's we have calculated. That's why it's $(1 + 2 + ... + n) / n$.

If you know about probabilities, costs for each element represent a discrete probability distribution, and the average cost is the expected value.

---
Tags: asymptotics
---


# Question
Title: Show $USELESS_{TM}=\{ M | M$ is a Turing machine with at least one useless state$\}$ is recursively enumerable?
I know $USELESS\_{TM}$ is undecidable, but am having trouble showing that it is recursively enumerable. I wanted to reduce $USELESS\_{TM}$ to the halting problem, which would show that $USELESS\_{TM}$ is recursively enumerable but don't see a way to go about doing this. (I think I would need to check every possible input to see if a state is not entered which I don't know how to simulate using a halting problem subroutine.)

# Answer
> 1 votes
The reason you are struggling to reduce USELESS to the Halting problem might be that it is not recursively enumerable after all. Since you already have a proof of undecidability, it is enough to see that USELESS is co-ce:

Given some TM M, we enumerate all its states as $s\_1$ ... $s\_n$. We can search through potential inputs $w\_0,w\_1,\ldots$ and mark each state that one of the computation visits. If we ever mark all states, we halt. This gives a procedure that recognizes exactly the complement of USELESS.

# Answer
> 0 votes
Have you used Rice theorem to show that's it's undecidable ? If so, it also shows that the problem can be transformed to the halting problem, because the proof of Rice theorem contains that transformation. You can easily find that proof and see how the transformation is accomplished.

But, are you sure that reducing your set to the halting problem shows that it's recursively enumerable ?

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


title: Clarification on class $SPP$?

text:
# Question
Title: Clarification on class $SPP$?
A language $L$ is in $SPP$ if there is a $GapP$ function $f$ such that

$x\in L\implies f(x)=1$ and $x\not\in L\implies f(x)=0$.

By $x\not\in L$ I think we mean $x\not\in SPP$ correct?

I would have thought $x\not\in L$ if there is no such $f$. Why is it not defined this way? In this case we have $x:f(x)\not\in\\{0,1\\}$. Is such $x\in L$ or $x\not\in L$?

I guess my query is it is not clear that in this case $x\in L$ and $x\not\in L$ cover all strings?

# Answer
> 0 votes
$\mathsf{SPP}$ is a class of languages, so we can ask whether a language is in $\mathsf{SPP}$, not some input in $\Sigma^\*$. The function $f$ is fixed before seeing the inputs, as it defines the language. You don't look at the input and then ask if there exists some function.

Think of it this way, $\mathsf{SPP}$ is the class of languages decidable by a certain class of nondeteministic polynomial time machines, namely those for which the difference between the number of accepting and rejecting paths takes values in $\\{0,1\\}$ (for all inputs). Note that for a general NP machine, given input $x$ this difference can take values in $\\{0,1,...,2^{poly(|x|)}\\}$. Given such a machine $M$, the associated $\mathsf{SPP}$ language is the set of all inputs for which the difference is $1$.

---
Tags: complexity-theory, complexity-classes
---


# Question
Title: Is the $x$ in $\frac{\mathrm{d}}{\mathrm{d}x}$ a symbol in the sense of Harper's PFPL?
The role of $x$ in $\frac{\mathrm{d}}{\mathrm{d}x} y$ not only confuses my calculus students, it has also puzzled some well known mathematicians. Questions one might ask are:

* Does the $x$ in the denominator bind the $x$ in $y$? (Clearly no, since $\frac{dx^2}{dx}=2x$.)
* Can one substitute for $x$ in the denominator? (Looks like not, what should $\frac{dx^2}{d3}$ mean?)
* Is the $x$ in the denominator itself bound?

I was wondering if interpreting that $x$ as a *symbol*, in the sense of Bob Harper's *Practical Foundations for Programming Languages* (Chapter 1.2 on abstract binding trees) might solve these riddles, and if this had already been worked out by someone?

Here's a quote from PFPL:

> It will often be necessary to consider languages whose abstract syntax cannot be specified by a fixed set of operators, but rather requires that the available operators be sensitive to the context in which they occur. For our purposes it will suffice to consider a set of *symbolic parameters*, or *symbols*, that index families of operators so that as the set of symbols varies, so does the set of operators. \[...\] The only difference between symbols and variables is that the only operation on symbols is renaming; there is no notion of substitution for a symbol.

# Answer
Some mathematicians find it natural to substitute for the variable in the denominator of a derivative, writing things like $\frac{d \log V}{d\log p}$. This suggests that the $x$ in the denominator $\frac{dy}{dx}$ is neither bound nor binding nor a symbol.

Rather $\frac{dy}{dx}$ seems to be an operation on "variable quantities" $y,x$ requiring some side conditions, similar to how the usual division $a/b$ requires $b\neq 0$, or how the operation $\frac{v}{v\_1^0\ldots v\_i^1\ldots v\_n^0}$ in my comment requires $v\_1,\ldots,v\_n$ to be linearly independent and $v$ to lie in their span.

I suspect that the side condition for $\frac{dy}{dx}$ should be analogous: $dx$ needs to be linearly independent and $dy$ has to be a multiple of $dx$.

With these side conditions we are not allowed to substitute a constant for $x$ in $\frac{dy}{dx}$ since then $dx=0$ and so $dx$ is not linearly independent. That would explain why we are not allowed to write $\frac{d x^2}{d3}$ or to take the derivative of equation $x=0$ w.r.t. to $x$ to conclude $1=0$.

I'd be interested in hearing if someone sees an immediate problem with this interpretation.

(I see some subtlety in the fact that $d(x|\_{x=3})$ cannot mean the same as $(dx)|\_{x=3}$, since otherwise I'd expect $\frac{dy}{dx}|\_{x=3}$ to be the same as $\frac{d(y|\_{x=3})}{d(x|\_{x=3})}$ which would not be allowed by the side condition. On the other hand, that is not so strange from a differential geometric point of view if we read $|\_{x=a}$ as restriction: there is a difference between restricting a differential form and pulling it back. But I need to think more about this.)
> 2 votes

# Answer
# Functions of a single variable

We can define a operator $\mathcal{D}$ on functions $f: \mathbb{R} \to \mathbb{R}$ so that $\mathcal{D}(f)$ is the first derivative of $f$. It is common to write this operator without parentheses, i.e., write it as $\mathcal{D} f$ instead of $\mathcal{D}(f)$ and write $\mathcal{D} f(x)$ instead of $(\mathcal{D}(f))(x)$ or $\mathcal{D}(f)(x)$.

What about functions of multiple variables? We can define a operator $\mathcal{D}\_1$ on functions $f: \mathbb{R}^n \to \mathbb{R}$ so that $\mathcal{D}\_1(f)$ is the partial derivative of $f$ with respect to its first argument, i.e., $(\mathcal{D}\_1 f)(x) = {\partial f \over \partial x\_1} f(x\_1,\dots,x\_n)$. Then $\mathcal{D}\_1(f)$ is a function with signature $\mathbb{R}^n \to \mathbb{R}$.

These operators $\mathcal{D},\mathcal{D}\_i$ have a clear interpretation that avoids the ambiguities you mentioned.

On to interpret more standard notation. Here's the thing about standard notation. When someone writes $x^2$ in a math textbook, there are two things they might mean. If $x$ is taken as a free variable, this might represent a function, namely the function $\lambda x . x^2$. Or, if $x$ is taken as a bound variable, it might represent a number: it is the value of $x$, squared. Since the same notation is used for both, the reader has to infer which was intended based on the surrounding context. That's OK for mathematical exposition, but problematic for programming languages, where we need expressions to have an unambiguous meaning.

And the same ambiguity infects notation surrounding functions and derivatives. The expression $f(x)$ sometimes is used to represent the function $f$, and sometimes to represent the value obtained by evaluating $f$ at the input $x$. The expression ${df \over dx}$ is sometimes intended to represent the function $\mathcal{D} f$, and sometimes to represent the value of that function evaluated at the input $x$, i.e., $(\mathcal{D} f)(x)$.

When you see someone write something like ${d \over dx}f(x)$ or ${df \over dx}(x)$ where $f$ is a function of one variable, that might be intended to represent $\mathcal{D} f$ or $(\mathcal{D} f)(x)$: you have to look at context to guess what was intended. Mentioning "$x$" in the denominator is a bit sloppy since $x$ is a bound variable of the expression defining $f$; the $\mathcal{D}$ notation makes it clearer that $\mathcal{D}$ is an operator that takes a function and returns another function. This operator doesn't really care what name you give the bound variable.

What about ${dy \over dx}$ or ${d \over dx} y$? Sometimes, the context makes clear that $y$ is implicitly a function of $x$, i.e., $y = f(x)$. Then, this notation might refer to the function $\mathcal{D} f$, or it might refer to the number $(\mathcal{D} f)(x)$ -- you have to guess from context. Or, if you prefer, it might represent $\mathcal{D} \lambda x . \cdots x \cdots$, where "$\cdots x \cdots$" is some expression that describes how $y$ is computed as a function of $x$, or it might represent $(\mathcal{D} \lambda t . \cdots t \cdots)(x)$. In other words, $y$ might represent either a function (of $x$) or a number. In the former case, we are basically writing $y$ as a shorthand for $\lambda x . \cdots x \cdots$; the context has made clear how $y$ varies as a function of $x$, so in communication with humans we don't bother writing it out a second time.

# Functions of multiple variables

What about functions of multiple variables? When you see someone write something like ${\partial \over \partial x\_1} f(x\_1,\dots,x\_n)$, this is implicitly the same as either $(\mathcal{D}\_1 f)(x\_1,\dots,x\_n)$ or $\mathcal{D}\_1 f$ (you have to guess from context which was intended). Everything should now follow from the discussion above.

If we take this understanding that ${d \over dx}$ is syntactic sugar for $\mathcal{D}$ and $\mathcal{D}\_i$, then it becomes clearer how to answer your questions. In particular, we only need to answer your questions for the $\mathcal{D}$ operators. And most of your questions go away, because $\mathcal{D}$ no longer mentions a variable $x$, so we don't need to answer whether $x$ is bound or not, whether you can substitute for $x$ in the denominator, etc.

Last question: is $\mathcal{D}$ a symbol in the sense that Harper meant? I don't know. You'll have to check the definition in that paper.
> 1 votes

---
Tags: programming-languages, mathematical-programming, variable-binding
---


# Question
Title: How can I sum pixel values over a rotated rectangle?
I have an optimization problem in which I need to sum pixel values in an image over a rectangular region. This is a core component of the optimization so it will be done often and the naive solution is not fast enough.

The region can be rotated arbitrarily so that I can't use an integral image; integral images only work for axis-aligned rectangles.

Does someone know a generalization of the integral images for that problem or has a different idea?

Update:

* The rectangles have different rotations, so that I can't rotate the rect.
* The rectangles have a size similar to the one of the full image (each ~20%)

# Answer
> 5 votes
One simple technique that's probably not optimal, but is better than naively enumerating all pixels in the rotated rectangle, is to use "integral columns" (thanks to Yves Daoust for the name):

Preprocessing: Let $I\[\cdot,\cdot\]$ be the image. For each $x$ value, build a 1D integral image for $I\[x,\cdot\]$. In other words, we build a table $S\[\cdot,\cdot\]$ where $S\[x,y\] = S\[x,0\] + S\[x,1\] + \dots + S\[x,y\]$. This can be done in linear time.

Answering a query: Given a rotated rectangle $R$, we find the range of $x$-values of pixels within $R$ (i.e., the leftmost part of $R$ and rightmost part of $R$). This can be done in $O(1)$ time. Next, for each $x$ in that range, we find the range $\[y\_\ell,y\_u\]$ of $y$-values such that $(x,y)$ is in $R$ for each $y\_\ell \le y \le y\_u$. We sum the pixel values of those by computing $S\[x,y\_u\] - S\[x,y\_{\ell}-1\]$. This takes $O(1)$ time per $x$-value, so the total running time to sum the pixels in a rectangle is proportional to the width of $R$ (in contrast, the naive method's running time is proportional to the area of $R$).

As a trivial optimization, you can precompute sum tables for both $x$ and $y$; for each $R$, you can check which is smaller, the width or height of $R$, and then decide whether to enumerate $x$-values or $y$-values.

# Answer
> 3 votes
Continuing my comment on the excellent answer of D.W.:

The integral images allow summation in constant time over an axis-aligned rectangle because they are the Cartesian product of two intervals.

You can speedup the summation over an arbitrary shape by partitioning it in a minimum number of axis-aligned rectangles. As shown on the figure, the possibilities are quite limited on a rotated rectangle.

In the worst case, rotation by $45°$, rectangles larger than one pixel are just impossible. There can be larger rectangles for small rotations, but in practice they are not really worth the effort. Note that it is not the area of the rectangles that matters, but their number.

Generally speaking, the total workload must be proportional to the length of the outline in the worst case. A comparable result (if not the same in disguise) is developed in "Yang, Luren, Albregtsen, Fritz, Fast and exact computation of moments using discrete Green's theorem. NOBIM-konferansen. 1994".

---

Integral images can be adapted to other angles, by summing in non axis-parallel directions, allowing to sum inside parallelograms.

Anyway, this is of little use as it doesn't lower the number of pieces required in the decomposition of arbitrarily rotated rectangles.

# Answer
> 2 votes
There is a quite fresh publication about Line Histogram which is beneficial to use, as this technique is less expensive than rotating image and uses simple line based histograms - which gives computational boost while still being flexible with given angles.

# Answer
> 0 votes
a quite old article

Exact Integral Images at Generic Angles for 2D Barcode Detection

abstract: We propose a novel solution to elegantly compute integral images at generic angles. Our method is exact in the sense that no approximations are used to derive it and it is vulnerable only to the unavoidable aliasing effects of discretization.

In their paper, the determination of a block sum for an arbitrary angle, is as same as the conventional one

block\_sum = A - B - C + D

which is elegant, in my point of view.

---
Tags: computational-geometry, computer-vision
---


title: Possible orderings with constraints

text:
# Question
Title: Possible orderings with constraints
Given variables **{A, B, ,,,,,Z}** We want to sort these varibles according to given constraints.

The constrains are in below format:

***X Y Z***

* meaning the third variable (**Z**) is not in the range between first and second variables (**X, Y)**
* **X \> Y** or **X \> Y**, we don't know. and **Z** can be greater than both **X** and **Y** or smaller than both which we don't know either
* for example **XYZ**, **ZXY**, **YXZ**, **ZYX** are all valid ordering given this constraint
* We are given at least 200 of such constraints such as:
**A B C
E B K
X Y Z**
....

We want to generate possible orderings of **{A, B, ,,,,,Z}** as many as possible Also the algorithm has to be faster than **O(N!)** (N is the number of variables)
I'm not sure how can I approach this problem, we don't have to generate all possible ordering but the more the better.

# Answer
> 0 votes
This may not directly answer your question, but can help. The problem you are looking at is complement to the Betweenness (https://en.wikipedia.org/wiki/Betweenness) problem. In your problem, for the constraint $X,Y,Z$ you do not want to generate sequences where-: 1. no sub-sequence beginning with X and ending with Y contains Z somewhere in between or 2. sub-sequence beginning with Y and ending with X contains Z somewhere in between. For the betweenness problem wit variables $X, Y, Z$ and constraint $X, Z, Y$ means $X, Z, Y$ and $Y, Z, X$ are the only valid solutions. So, one can look at efficient solution techniques for the betweenness problem and simply remove all those solutions to the betweenness problem from the $N!$ possible orderings.

---
Tags: algorithms, np-complete, sorting, constraint-satisfaction
---


# Question
Title: Determining time complexity of this function in python
I would like to determine the time complexity of this function, in $\mathcal{O}$-Notation.

```
def g(x):
   if x == 0:
      return 1
   elif x == 1:
      return 2
   else:
      x_div = x//2              # // is integer division
      x_mod = x % 2
      return g(x_div)*g(x_mod)

```

Because it's recursive, I think it's $\mathcal{O}(\log{}n)$. Is this correct? A small explanation would be great.

Another question, is there a relation between the return value of the function and the binary representation of $n$?

# Answer
Yes, it ist $O(\log\_2 n)$, because only the first recursive call `g(x_div)` matters, and the argument is halved each time. The remainder of a divison by 2 is at most 1, which leads to $O(1)$ for this part of the recursion.

The result is the next greater power of 2 compared to the double of the number of bits of the input.
> 0 votes

# Answer
Let $T(x)$ denote the running time of the algorithm. The following recurrence captures the running time of the algorithm:

> $T(x)=T(\frac{x}{2})+c,\ x\geq3,\ c \in O(1)$
> where $T(0) = T(1) = a \in O(1)$

Solving this we get, $T(n) \in O(log\_2 x)$
> 1 votes

---
Tags: time-complexity, runtime-analysis, python
---


title: Push Down automata:- Basic doubt

text:
# Question
Title: Push Down automata:- Basic doubt
I was reading CFG's and PDA's. I need to understand one basic point in that.I have solved some questions on final state acceptance by PDA.But in every answer,the string always end with epsilon(means that there is always a transition when string ends which by reading epsilon takes to final state and mostly it invloves checking that current stack TOP is same as initial symbol).

Do we assume that there is some end of string marker in PDA?I have not seen such thing in DFA/NFA.If the string ends,then there is no need to read epsillon in that,but what is the requirement for this in PDA?Or does this depends on the problem in context?

# Answer
> 1 votes
In general we do not assume that push-down automata have an end-of-string (or end-of-input) marker.

PDA have two modes of acceptance, with final state and with empty stack. Even when the automata are written for final state acceptance it is helpful in the design to check that the stack is empty. That ensures no data is unprocessed.

The PDA on wikipedia for the language $\\{0^{n}1^{n}\mid n\geq 0\\}$ has transitions: $(p,0,Z,p,AZ)$, $(p,0,A,p,AA)$, $(p,\epsilon ,Z,q,Z)$, $(p,\epsilon ,A,q,A)$, $(q,1,A,q,\epsilon )$, and $(q,\epsilon ,Z,r,Z)$. Initial state $p$ and final state $r$. This indeed is of the form you describe.

The same language can be accepted without $\epsilon$-transitions at all.

$(p,0,Z,q,Z)$, $(q,0,Z,q,AZ)$, $(q,0,A,q,AA)$, $(q,1,A,r,\epsilon)$, $(q,1,Z,s,\epsilon)$, $(r,1,A,r,\epsilon)$, $(r,1,Z,s,\epsilon)$. Initial state $p$ and final states $p$ \[to accept $\epsilon$\] and $s$.

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


# Question
Title: Difference between spanning tree and a tree?
Strictly in the context of computer science, what is the difference between a spanning tree, and minimum spanning tree? I read this posts but was unsatisfied with the answer because it did not seem relevant to computer science. My professor in my algorithms class makes the distinction between a spanning tree and a regular tree; but never says what the difference really is. The only thing I notice is that he uses the word **spanning tree** when he is talking about graphs.

Is a spanning tree simply when a graph takes on a tree structure? In other words, the raw data structure under the hood is a graph, but it takes on some characteristics of a tree? Or is it something else?

# Answer
Given a graph $G$, a spanning tree is a subgraph of $G$ that (i) is a tree, and (ii) has all the vertices in $G$.

There can be many spanning trees for $G$. If you put weights on the edges, one of these spanning trees will have a minimal sum of weights. This is the minimal spanning tree.

Regular (sub)tree is just subgraph which is a tree - it doesn't have all the nodes in $G$: it satisfies property (i) above, but not necessarily property (ii).
> 6 votes

# Answer
There are several species of trees.

A spanning tree in a graph is an undirected tree connecting all the nodes in a graph. Undirected trees on their own are graphs with the property the graph is connected and does not have cycles.

Trees as often used in computer science have a root, the node usually depicted at the top. They also are considered as directed graphs, all edges pointing downwards, away from the root. This direction sometimes is left implicit in pictures.

Binary trees are a class of their own. A single child may either be "left" or "right", which differs from ordinary directed trees, as in those trees we do not distinguish left and right.

So, sometimes we distinguish trees for technical reasons. This is not always explicitly stated, and the terminology for all trees is rather similar.
> 1 votes

# Answer
In graph theory, a substructure of a graph $G$ is said to be *spanning* if it includes every vertex of $G$. So a spanning subgraph is one that includes every vertex. This is equivalent to say that it was made only by deleting edges, whereas subgraphs in general are made by deleting edges and vertices. Similarly, a spanning matching would be what everybody actually calls a perfect matching.

Hence, a spanning tree of a graph $G$ is a subgraph of it that is a tree (connected and contains no cycles) and is spanning (includes every vertex of $G$).
> 0 votes

---
Tags: terminology, trees, spanning-trees
---


# Question
Title: How to find spanning tree of a graph that minimizes the maximum edge weight?
Suppose we have a graph G. How can we find a spanning tree that minimizes the maximum weight of all the edges in the tree? I am convinced that by simply finding an MST of G would suffice, but I am having a lot of trouble proving that my idea is actually correct. Can anyone show me a proof sketch or give me some hints as to how to construct the proof? Thanks!

# Answer
> 5 votes
*What follows is taken from Tsuyoshi Ito's comment.*

If you know Kruskal’s algorithm for the minimum spanning tree, it is an easy exercise to show that the output of Kruskal’s algorithm is a minimum bottleneck spanning tree. (I think that it is easier than showing that the output of Kruskal’s algorithm is a minimum spanning tree.)

# Answer
> 2 votes
Given a graph $G(V, A)$, we know that any spanning tree contains an edge in every cutset. Let $S\_{min}^{max}$ and $S$ be the minimax weight spanning tree of $G$ and minimum weight spanning tree of $G$ resp. Any edge $e \in S$ is associated with a cutset $C$. Corresponding to cutset $C$,$S\_{min}^{max}$ must also contain an edge, say $e'$. Then if $w(e') \< w(e)$, we know that replacing $e$ with $e'$ in $S$ will produce a new spanning tree with lower overall weight, thus contradicting our assumption of optimality of $S$. Hence, we can see that the weight of every edge in $S$ is no greater than the weight of a corresponding edge (obtained from the cutset) in $S\_{min}^{max}$. Since, we have compared every edge in $S$ but perhaps possibly may not have compared every edge of $S\_{min}^{max}$ in the above process for comparison, the max weight edge in $S\_{min}^{max}$ has to be atleast as much as much as the max weight in $S$. Hence we can conclude that $S$ itself produces a minimax weight spanning tree.

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


# Question
Title: Why pointer dereference was once called "decrement"?
I'm reading McCarthy's paper *Recursive Functions of Symbolic Expressions And Their Computation by Machine*, where when the author describes the machine implementation of lists, he writes this:

> a. *Representation of S-Expressions by List Structure.* A list structure is a collection of computer words arranged as in figure 1a or 1b. Each word of the list structure is represented by one of the subdivided rectangles in the figure. The left box in the rectangle represents the *address* field of the word and the right box represents the *decrement* field. An arrow from a box to another rectangle means that the field corresponding to the box contains the location of the word corresponding to the other rectangle.

From further reading it isn't clear why would he use the word "decrement" to mean "a pointer to a memory location where the data associated with the given list element is stored". It doesn't exactly translate into "dereference" as used today when describing languages s.a. C, but if, in C terms, you were to treat the contents of "decrement" field as a pointer, and then dereference it, you'd get the value of the element.

So, why "decrement"? Was something really decremented? Was it due to some particular features of memory layout of IBM 704?

# Answer
OK, I found a lead. Just needed to know what to search for: https://en.wikipedia.org/wiki/CAR\_and\_CDR

> The 704 and its successors has a 36-bit word length and a 15-bit address space. These computers had two instruction formats, one of which, the Type A, had a short, 3-bit, operation code prefix and two 15-bit fields separated by a 3-bit tag. The first 15-bit field was the operand address and the second held a **decrement or count.** The tag specified one of three index registers. **Indexing was a subtractive process** on the 704, hence the value to be loaded into an index register was called a "decrement".\[2\]:p. 8 The 704 hardware had special instructions for accessing the address and decrement fields in a word.\[2\]:p. 26 As a result it was efficient to use those two fields to store within a single word the two pointers needed for a list.\[3\]:Intro.

Still, this memory model is very foreign to me, so I wouldn't mind if anyone explained how this would work.
> 1 votes

---
Tags: terminology, history, lisp
---


# Question
Title: Algorithms : most lightweight circle in directed graph that goes through specific vertex
I have directed Graph G(V,E) with weight function w. so that weight of each (u,v) is a positive value. I need to find the most lightweight circle in the graph that vertex k' is part of it.

I've also given an algorithm i can use which can find the most lightweight path for a graph with positives weights ( i can use it only once).

I thought about creating a sub graph G' where all vertices and edges that are strongly connected components. find the graph which k' is part of it. then find for the most lightweight adjacent edge from k' to some v of vertices. from that v i can run the algorithm given and find the lightweight path then add the weight of the vertex missing ( (k',v) ).

is that seems correct ? I'm in the beginning of this course and I feel i'm not there yet.

# Answer
Just add a node k1 to your graph, that has exactly the same connections as k, with the same weights (you can keep only the edges going to k1 if you'd like), and query the shortest path from k to k1 in your (slightly) extended graph. Your cycle is exactly this path, only replacing back k1 with k at the end of the path.

Your algorithm would be slower and would not always give the right answer: even if v is the closest node to k, maybe it is not in the best cycle (you could for instance have k-\>v cost 1, v-\>k cost 100, and k-\>u and u-\>k both cost 2 or some u).
> 0 votes

---
Tags: algorithms, weighted-graphs
---


# Question
Title: Is square numbers written in binary a regular language?
I'm having problem trying to determine if all square numbers (1, 4, 9, 16, ...) written in binary form (1, 100, 1001, ...) is a regular language.

After some attempts to find a common pattern of those numbers, I found out that for any square number $n^2$, $n^2 mod 4$ either equals to 0 or 1, and so I am able to draw a DFA graph with 4 states to recognize this language. But apparently, the DFA I drew actually recognizes a superset of the square number language in question. I'm stuck here.

Anyone could give me some clues on this problem? If it's not a regular language, how should I prove it?

I am also very interested to know how I should approach to this kind of question the best way in the future. I know that in many cases, if we have the intuition that the automata has to keep a track of what is has seen already (like $a^i b^i$), then there's an undetermined states needed for the automata to compute, thus it's not finite or regular. We can then use Pumping lemma to prove it's not regular. However, I can't tell if this language is regular yet, so I don't really have an idea what to do next.

Thanks!

# Answer
> 9 votes
Here is a high-tech solution. Denote your language by $L$. Szalay showed that $$ L \cap 10^\*10^\*1 = \\{ 10^n10^{n+2}1 : n \geq 0 \\} \cup \\{110001, 1000010001\\}. $$ From here it's pretty easy to show that $L$ is not regular, by reduction to $\\{a^nb^n : n \geq 0\\}$.

# Answer
> 2 votes
Well, this is the third time I rewrite this answer. User Yuval Filmus pointed two very very silly mistakes I made in the previous two versions.

Well I finally found a simple solution to the problem. I think it works.

First we have that words of this type:

$1(00)^p1(00)^p001$

Are square numbers.

Proof:

I´ve looked information about square numbers and then I found about "centered octagonal numbers" which are numbers that are formed by layers of multiples of eight, but not the first layer. The first layer is one, the second eight, the third sixteen and so on.

So each layer has an "eight" more than the previous one. The number of eights in a centered octagonal number can be calculated by using gauss formula:

$\frac{n^2 + n}{2}$

We then multiply by eight and add one, this is because the first layer is only a dot.

$\frac{8(n^2 + n)}{2}+1$

Simplyfying:

$4(n^2 + n) + 1$

That formula gets us the odd square numbers for every n.

I´m going to calculate the formula for the number four and all powers of four.

First we square the number, this simply doubles the zeroes of the number. Then we add the number to the product. This puts a "one" at position $\lceil|n|/2\rceil$ starting from the right. $|n|$ is the length of the binary word.

Right now we have words of this form:

$1(00)^p1(00)^p0$

We multiply by four, this simply adds two zeroes at the end of the number. Finally we sum one. We are done.

**Pumping**

I set $i=0$.

**First the easy case**

If we let $x$ empty, then we take the number one and one or more zeroes. This gives us words with hamming weight two (the number of ones is two). There is only an uneven number with hamming weight two, the number nine (the only odd square number of the form 2n + 1 is 9, I saw this in wikipedia: see here). As all numbers we are pumping are bigger than nine, we proved this case.

**Hard case**

We let the first "one" in its place and we take out zeroes only. We can take out up to $p-1$ zeroes.

The word will look like this:

$10(00)^m1(00)^n001$.

Where $m$ and $n$ are integers bigger or equal to one and $n \> m$

I will first believe that the number obtained is a square, then I will show that´s false:

Since we know that all odd square numbers can we obtained with this formula:

$4(n^2 + n) + 1$

We start decomposing the number, we substract one, this simple sets the last one to zero and then, we divide by four, this removes two zeroes at the end of the binary word.

Then we´ll have words like this:

$10(00)^m1(00)^n0$, $n$ and $m$ are integer numbers bigger or equal to one and $n \> m$. These words are a prefix of the complete word.

Since we are believing that this chain is part of a square number, the word had to be formed by doing this formula:

$(n^2 + n)$

**$n$ can´t be even**

We'll look again at this formula:

$n^2 + n$

Since we are believing that the words we have pumped are square numbers. We call the words we have pumped $m$ and we have that:

$m = n^2 + n$

Also, we have that $m$ can be represented as the sum of two binary numbers, $m\_1$ and $m\_2$, each of them is a power of two. And we have that $\sqrt{m\_1} \< m\_2$ and $m\_1 \> m\_2$

The first thing that we notice is that $n$ has to be less than $m\_2$. This is because $m\_2$ is bigger than the square root of $m\_1$, if $n$ was equal to $m\_2$, then $n^2$ will be bigger than $m$.

Now, when we square an even binary number, we have that the number squared has "more zeroes" to the right of the first "one" than the original number had. So "the rightmost one" inside $n^2$ is at the left of the "rightmost one" inside $n$. If we add $n$ to $n^2$ , we have that the "rightmost one" inside $n^2 + n$ is the "rightmost one" in $n$. Since $n$ is smaller than $m\_2$. We have that the "rightmost one" inside $n^2 + n$ is to the right of the "rightmost one" in $m$. Therefore $m \neq n^2 +n$ . But since we said that $n^2 + n = m$ we have reached a contradiction and therefore $n$ can´t be even.

**$n$ can´t be uneven**

Again, we have that $m$ is a number made by adding $n$ to $n^2$, so $m = n^2 + n$

Then we notice that $(n + 1)^2 - (n + 1) = n^2 + n$; This is because:

$(n + 1)^2 - (n + 1) = n^2 + 2n + 1 -n -1$;

And then:

$(n + 1)^2 - (n + 1) = n^2 + n$.

Another way to see this, is to imagine $n^2$ as a square with sides of length $n$. This square is formed by smaller squares of size one. Then, when we add $n$ squares of size one to the previous square, the previous square is now a rectangle whose sides are $n$ and $n+1$. Now, we can imagine $(n + 1)^2$ as another square with sides of of length $n + 1$. This square is also formed by smaller squares of size one. If we remove $n + 1$ squares to it, we have a rectangle of sides $n$ and $n+1$.

We have that $n + 1$ is an even number and the proof follows the same as before for all odd numbers $n$ less than $m\_2 - 1$

Again, when we square an even binary number, we have that the number has "more zeroes" to the right of the first "one" than the original number had. So "the rightmost one" inside $(n + 1)^2$ is at the left of the "rightmost one" inside $n + 1$. If we substract $n + 1$ to $(n + 1)^2$, we have that the "rightmost one" inside $n^2 + n$ is the "rightmost one" in $n + 1$. Since $n + 1$ is smaller than $m\_2$. We have that the "rightmost one" inside $n^2 + n$ is to the right of the "rightmost one" in $m$.

If $n = m\_2 - 1$.

Again, we have that $n^2 + n = (n + 1)^2 - (n + 1)$. Since $m\_2^2$ ($m\_2$ squared) is a number that is a power of two, it has only a single leading "one" and then zeroes. When we substract $m\_2$ to $m\_2^2$, we are turning all zeroes to the left of the leftmost digit of $m\_2$ inside $m\_2^2$ into "ones" and the resulting number is not like the words we are pumping, there should be at least a "zero of separation" between the ones.

Therefore $m \neq n^2 +n$ . But since we said that $n^2 + n = m$ we have reached a contradiction and therefore $n$ can´t be uneven.

As $n$ can´t be even or uneven, we have that $n$ doesn´t exist as an integer. Therefore the words we pumped are not the product of the formula for odd square numbers. Since all the words we are pumping are odd, they can´t be square numbers.

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


# Question
Title: Construct a TM for $L = \{ M | M$ is a Turing machine with no useless states}
I'm trying to construct a recursively enumerable TM for this language. (Useless state: one that is never entered during a computation on any input).

The TM L: Write out all of M's states, generate input in lexicographical order one at a time, and after one is generated, simulate M on the input and mark down which states M has entered. If M enters all states, halt, if M halts without entering all states, generate the next input in lexicographical order and repeat the process. (Keeping the list of entered states between simulations, since once a state is entered for any input, it is not considered useless).

My question is, what happens if M does not halt on input $w\_i$ but will halt and in fact enter all states on $w\_{i+1}$? Then L will get stuck in an infinite loop on $w\_i$ and not realize that M's behavior on $w\_{i+1}$ means L should actually accept--thus L will not eventually halt and accept.

Is there a way to deal with this problem or is this TM just not the right way to show this language is recursively enumerable?

# Answer
> 0 votes
You need dovetailing. This is quite common in such problems.

As you pointed out, we can not simply run $M$ on an input $w$, since that might diverge. To avoid that, we enumerate all the possible pairs $(w,k)$ where $w$ is an input word, and $k$ is a natural. For each such pair, we run $M$ on input $w$ for at most $k$ steps. This will never diverge because $k$ bounds the computation. If $M$ within that bound visits all states, we accept. Otherwise, we try the next pair.

Note that, in order to enumerate all such pairs, we need a computable bijection $(\mathbb N\times \mathbb N) \to \mathbb N$ (or, equivalently, $(\Sigma^\*\times \mathbb N) \to \mathbb N$). The existence of such a dovetailing function is one of the standard computability results.

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


# Question
Title: Maximize the number of satisfied disjunctions
I have ~4000 variables that are used in ~5000 logical formulas, where each formula consists only of conjunctions of the (non-negated) variables. I want to find the maximum number of satisfied formulas, given the number of variables that I can set to 1.

Does this problem have a name? Is it equivalent to the MAX-SAT problem? Which algorithm would be applicable to solve it exactly or using heuristics?

# Answer
You are addressing a problem of the same type. if you use De Morgan law your problem will become MIN-SAT which is NP-HARD

checkout THE MINIMUM SATISFIABILITY PROBLEM
> 3 votes

---
Tags: optimization, dynamic-programming, satisfiability
---


# Question
Title: What defines negative and non-negative type operators?
I'm working through some exercises in Robert Harper's "Practical Foundations for Programming Languages" and I'm not certain I understand what makes an occurrence of a type operator non-negative or negative in the general case.

I understand that positive type operators occur in the range of a function type, and that negative type operators occur in the domain of a function type, but I'm not sure how to generalize the additional category of non-negative based on the single given example `t. (t -> bool) -> bool`, which is only described as an occurrence in the domain of the domain without any mention of the interactions of further nesting. That also complicated my understanding of what makes an occurrence negative (must the occurrence on the left be positive, or just non-negative?), so now I'm just plain not sure what defines non-negative and negative type operators in the context of a function type.

For anybody who owns the book (second edition) this is chapter 14.

# Answer
> 5 votes
I can explain the mathematical background. Suppose we have a type operator $F$ that takes a type $A$ to a type $F(A)$, and we want to extend it so that it also maps functions. It should take a function $f : A \to B$ to a function $F(f) : F(A) \to F(B)$. This can often be done, for example if $$F(X) = X + (C \to X)$$ for a fixed $C$, then we may define $$F(f) : A + (C \to A) \to B + (C \to B)$$ in a natural way as \begin{align\*} F(f)(\mathtt{inl}(a)) &= \mathtt{inl}(f(a)) \\ F(f)(\mathtt{inr}(g)) &= \mathtt{inr}(f \circ g) \end{align\*} We say that $F$ acts **covariantly** on functions.

But sometimes the direction gets reversed! Consider $$F(X) = X \to C$$ for a fixed type $C$. Then $f : A \to B$ can be mapped to $$F(f) : (B \to C) \to (B \to A)$$ by $$F(f) = \lambda g . g \circ f.$$ This time the direction was reversed. We say that $F$ acts **contravariantly** on functions.

In some cases we are stuck, for instance if $F$ mixes things up. An example would be $F(X) = X + (X \to C)$.

If $F$ takes several arguments it may act covariantly on some of them and contravariantly on others.

Covariance and contravariance are important mathematical concepts which show up in many places: category theory, physics, analysis, you name it.

The positive and negative occurrences of a type variable in a type expression tell you whether the corresponding type constructor acts covariantly (positive) or contravariantly (negative) in that position.

For example, in $F(X) = (X \to C) \to C$ we have a *positive* occurrence of $X$, and indeed $F$ acts on $f : A \to B$ covariantly to give $F(f) : F(A) \to F(B)$ defined by $$F(f) = \lambda \phi : (A \to C) \to C . \lambda g : B \to C . \phi(g \circ f).$$

# Answer
> 2 votes
Assume we have an occurrence of $t$ in a type formed by type constants, products, sums, and arrows/functions/exponentials. Count the number of arrows where such occurrence occurs in the *left* argument (possibly zero). If such number is even, the occurrence is positive, otherwise it is negative.

More precisely, the types types $P$ containing a positive occurrence of $t$ can be defined as those of the form $$ t, T \to P, N \to T, P \times P, P + P $$

where types $N$ containing a negative occurrence of $t$ are those of the form $$ P \to T $$ where $T$ is any type.

(The exact definition depends on the type system at hand, which might have more of fewer type constructors. Still, the overall idea holds.)

A more direct mnemonic is: an arrow $\to$ introduces a negation on its left argument, and double negations cancel out.

---
Tags: type-theory
---


# Question
Title: Bipartite graph matching with multiplicities
Let's say we have N people, each of them holds several colored cards (for each color and person pair the number cards held is no more than one). We want algorithm determine how to take exactly one card from each person (denote this set of taken cards S), so the following function would be maximal: number of colors satisfying condition - there is at least k cards of this color in S.

In case of k=1 it's well-known problem of maximal matching in bipartite graph.

In case of k\>1 this "matching" must have vertices of degree k on on side of bipartite graph. (It can be reformulated as a problem of finding maximal disjunct covering subset of specific set of coverings (in general case i think it's NP-complete?).

Does anyone know if this problem for k\>1 NP-complete or can be solved in polynomial time (specifically for k=2)?

# Answer
For k=2 it's Rainbow\_matching, so it's NP-complete.

For all colors X make cliques of all people holding color X, and color it's edges with X.
> 1 votes

---
Tags: graphs
---


# Question
Title: Simplex Algorithm: Why must the optimal value of the LP lie on the face or vertex of a polyhedron?
> The feasible region of a Linear Program (LP) is $\\{x \in {\bf R}^n: Ax \le b, x\ge 0 \\}$. This is an intersection of halfspaces, a polyhedron. If the LP is bounded and feasible, its optimal value will be attained on some face of the polyhedron, typically a vertex. A vertex is a point determined by the intersection of n hyperplanes bounding the halfspaces with linearly independent normal vectors. There might be more than n hyerplanes through a vertex. A basis is any subset of bounding hyperplanes that determines a vertex. Some inequalities will be the nonnegativity inequalities, the corresponding variables are called nonbasic and the rest basic. Only the basic variables can take nonzero values.

These are some lecture notes that I'm struggling to understand. Why does the optimal value not lie in say, the center of the polyhedron? Why must the optimal value be on the face or on a vertex? It seems arbitrary to me because there are so many points that lie on the faces. The center makes more sense to me.

Could anyone give me an intuition?

# Answer
> 2 votes
Suppose $P = \lbrace x: Ax \leq b \rbrace$ is the polyhedra, where $x \in \mathbb{R}^n$. Further assume $P$ is full dimensional, then let $x\_0$ be some interior point in P. Let $c \in \mathbb{R}^n$ (and $c \neq 0$) be the objective function you are interested to minimize (say). Then since $x\_0 \in int(P)$, there exists a ball $B$ centered at $x\_0$ with radius $\epsilon \> 0$ s.t. $B \in int(P)$. Now consider any unit vector say $u \in \mathbb{R}^n$ s.t. $c^t u \neq 0$ (notice that it is always possible to select such a $u$), then both ($x\_0 + \epsilon * u$) and ($x\_0 - \epsilon * u$) are in $B$, so by extension also in $P$. Now evaluate the function at 3 points, namely $x\_0, x\_0 + \epsilon * u, x\_0 - \epsilon * u$. The objective you would get are-: $c^T x\_0 , c^T x\_0 + \epsilon (c^T u) , c^T x\_0 - \epsilon (c^T u) $. Clearly if since $c^T u \neq 0 $, one of $c^T x\_0 + \epsilon (c^T u) , c^T x\_0 - \epsilon (c^T u)$ must be lower than $c^T x\_0$. This illustrates that the objective at $x\_0$ is greater than some other point on the ball, hence $x\_0$ cannot be optimum. You can repeat this argument for every other interior point and claim that such an interior point cannot give the optimum. Hopefully this gave you the intuition. More generally, suppose a point $x \in P$, can be represented as convex combination of 2 other points $y, z \in P$, we can repeat the same type of argument and say that the objective at $x$ cannot be strictly lesser than the objectives at both $y$ and $z$. A vertex is an example of a point that cannot be represented as convex combination of 2 other points from the same polyhedron.

---
Tags: linear-programming, polygons
---


# Question
Title: Polynomial Computation of the probability of a number of independent events
Suppose to have $n$ independent events $E\_1, E\_2,..., E\_n$, where the probability of occurrence of event $E\_i$ is $p\_i$ (i.e., each event has its own probability of occurrence). We can easily define new events of type $N\_k\equiv$"exactly $k$ events occur".

The probability of event $N\_k$ can be computed as $$\Pr(N\_k) = \sum\_{I \in \mathcal{I\_{n,k}}}\prod\_{i \in I}p\_i \prod\_{i \notin I} (1-p\_i)$$ where $\mathcal{I\_{n,k}} = \lbrace I \subseteq \lbrace 1,2,\ldots,n \rbrace :|I|=k \rbrace$. However, this calculation requires exponential time w.r.t. $n$.

Is there an algorithm with **polynomial** time complexity w.r.t. $n$ to compute the probability of each $N\_k$, for $k=0,1,...,n$?

# Answer
You can use dynamic programming. For parameters $m,\ell$, define $$ q\_{m,\ell} = \sum\_{I \in \cal I\_{m,\ell}} \prod\_{i \in I} p\_i \prod\_{i \in \[m\] \setminus I} (1-p\_i). $$ This satisfies the recurrence $$ q\_{m,\ell} = p\_m q\_{m-1,\ell-1} + (1-p\_m)q\_{m-1,\ell} $$ with initial values $q\_{0,0} = 1$ and $q\_{m,\ell} = 0$ for $\ell \< 0$ and $\ell \> m$. This gives an $O(n^2)$ time algorithm.

The same idea can be expressed using generating functions: $$ \prod\_{i=1}^n (1-p\_i + p\_i x) = \sum\_{k=0}^n \Pr(N\_k) x^k. $$
> 3 votes

---
Tags: algorithms, time-complexity, combinatorics, probability-theory
---


title: How to compute moving unique item

text:
# Question
Title: How to compute moving unique item
Imaging I am running a forum and I continuously have log in of members. A member can log in simultaneously many times

So I have :

```
Tom Jerry Jack Tom Joe Kay Neo Tom ...

```

each log in comes with a time stamp

I want to have an algorithm that can count how many UNIQUE names have logged in the past 1 minute.

How to design an algorithm like this?

My design is to use a std::map then continuously update/trim the map

I am wondering if there is any smarter solution here.

Any insight?

# Answer
Keep a hash table that stores a histogram of the items that have appeared in the past minute, as well as a counter for the number of unique items, initialized at zero. Also keep a circular queue with the actual timestamped list of items.

Every time you see a new item or query the number of unique items, go over the circular queue and delete all items which are older than one minute. For each one that you delete, update the histogram. If a cell in the histogram reaches zero, decrement the unique items counter, and delete the cell. If you are adding a new item, update the histogram, and if the item did not appear in the hash table, increase the unique items counter.
> 1 votes

---
Tags: algorithms
---