# Question
Title: Applying Expectation Maximization to coin toss examples
I've been self-studying the Expectation Maximization lately, and grabbed myself some simple examples in the process:

From here: There are three coins $c\_0$, $c\_1$ and $c\_2$ with $p\_0$, $p\_1$ and $p\_2$ the respective probability for landing on Head when tossed. Toss $c\_0$. If the result is Head, toss $c\_1$ three times, else toss $c\_2$ three times. The observed data produced by $c\_1$ and $c\_2$ is like this: HHH, TTT, HHH, TTT, HHH. The hidden data is the result of $c\_0$. Estimate $p\_0$, $p\_1$ and $p\_2$.

And from here: There are two coins $c\_A$ and $c\_B$ with $p\_A$ and $p\_B$ being the respective probability for landing on Head when tossed. Each round, select one coin at random and toss it ten times; record the results. The observed data is the toss results provided by these two coins. However, we don't know which coin was selected for a particular round. Estimate $p\_A$ and $p\_B$.

While I can get the calculations, I can't relate the ways they are solved to the original EM theory. Specifically, during the M-Step of both examples, I don't see how they're maximizing anything. It just seems they are recalculating the parameters and somehow, the new parameters are better than the old ones. Moreover, the two E-Steps don't even look similar to each other, not to mention the original theory's E-Step.

So how exactly do these examples work?

# Answer
> 14 votes
(This answer uses the second link you gave.)

$\newcommand{\Like}{\text{L}}\newcommand{\E}{\text{E}}$Recall the definition of likelihood: $$\Like\[\theta | X\] = \Pr\[X| \theta\] = \sum\_Z \Pr\[X, Z | \theta\]$$ where in our case $\theta = (\theta\_A, \theta\_B)$ are the estimators for the probability that coins A and B respectively land heads, $X = (X\_1, \dotsc, X\_5)$ being the outcomes of our experiments, each $X\_i$ consisting of 10 flips, and $Z = (Z\_1, \dotsc, Z\_5)$ being the coin used in each experiment.

We want to find maximum likelihood estimator $\hat{\theta}$. The Expectation-Maximization (EM) algorithm is one such method to find (at least local) $\hat{\theta}$. It works by finding the conditional expectation, which is then used to maximize $\theta$. The idea is that by continually finding a more likely (i.e. more probable) $\theta$ in each iteration we will continually increase $\Pr\[X,Z|\theta\]$ which in turn, increases the likelihood function. There are three things that need to be done before going forward designing an EM-based algorithm.

1. Construct the model
2. Compute Conditional Expectation under the model (E-Step)
3. Maximize our likelihood by updating our current estimate of $\theta$ (M-Step)

**Construct the Model**

Before we go further with EM we need to figure out what exactly it is we are computing. In the E-step we are computing exactly the expected value for $\log \Pr\[X,Z|\theta\]$. So what is this value, really? Observe that $$\begin{align\*} \log \Pr\[X,Z|\theta\] &= \sum\_{i=1}^5 \log\sum\_{C\in \\{A,B\\}}\Pr\[X\_i, Z\_i=C| \theta\]\\ &=\sum\_{i=1}^5 \log\sum\_{C\in \\{A,B\\}} \Pr\[Z\_i=C | X\_i, \theta\] \cdot \frac{\Pr\[X\_i, Z\_i=C| \theta\]}{\Pr\[Z\_i=C | X\_i, \theta\]}\\ &\geq \sum\_{i=1}^5 \sum\_{C\in \\{A,B\\}} \Pr\[Z\_i=C | X\_i, \theta\] \cdot \log\frac{\Pr\[X\_i, Z\_i=C| \theta\]}{\Pr\[Z\_i=C | X\_i, \theta\]}. \end{align\*}$$ The reason is that we have 5 experiments to account for, and we don't know what coin was used in each. The inequality is due to $\log$ being concave and applying Jensen's inequality. The reason we need that lower bound is that we cannot directly compute the arg max to the original equation. However we can compute it for the final lower bound.

Now what is $\Pr\[Z\_i=C|X\_i,\theta\]$? It is the probability that we see coin $C$ given experiment $X\_i$ and $\theta$. Using conditional probabilities we have, $$\Pr\[Z\_i=C| X\_i, \theta\] = \frac{\Pr\[X\_i, Z\_i = C|\theta\]}{\Pr\[X\_i|\theta\]}.$$

While we've made some progress, we're not done with the model just yet. What is the probability that a given coin flipped the sequence $X\_i$? Letting $h\_i = \\#\text{heads in } X\_i$ $$\Pr\[X\_i, Z\_i = C| \theta\] = \frac{1}{2} \cdot \theta\_C^{h\_i} (1 - \theta\_C)^{10 - h\_i},\ \text{ for } \ C \in \\{A, B\\}.$$ Now $\Pr\[X\_i|\theta\]$ is clearly just the probability under both possibilities of $Z\_i=A$ or $Z\_i=B$. Since $\Pr\[Z\_i = A\] = \Pr\[Z\_i = B\] = 1/2$ we have, $$\Pr\[X\_i|\theta\] = 1/2 \cdot (\Pr\[X\_i |Z\_i = A, \theta\] + \Pr\[X\_i |Z\_i = B, \theta\]).$$

**E-Step**

Okay... that wasn't so fun but we can start doing some EM work now. The EM algorithm begins by making some random guess for $\theta$. In this example we have $\theta^0 = (0.6,0.5)$. We compute $$\Pr\[Z\_1=A|X\_1,\theta\] = \frac{1/2 \cdot (0.6^5 \cdot 0.4^5)}{1/2 \cdot ((0.6^5 \cdot 0.4^5) + (0.5^5 \cdot 0.5^5))} \approx 0.45.$$ This value lines up with what is in the paper. Now we can compute the expected number of heads in $X\_1 = (H,T,T,T,H,H,T,H,T,H)$ from coin $A$, $$\E\[\\# \text{heads by coin }A | X\_1, \theta\] = h\_1 \cdot \Pr\[Z\_1=A|X\_1,\theta\] = 5 \cdot 0.45 \approx 2.2.$$ Doing the same thing for coin $B$ we get, $$\E\[\\# \text{heads by coin }B | X\_1, \theta\] = h\_1 \cdot \Pr\[Z\_1=B|X\_1,\theta\] = 5 \cdot 0.55 \approx 2.8.$$ We can compute the same for the number of tails by substituting $h\_1$ for $10 - h\_1$. This continues for all other values of $X\_i$ and $h\_i$ $1 \leq i \leq 5$. Thanks to linearity of expectation we can figure out $$\E\[\\#\text{heads by coin } A|X ,\theta\] = \sum\_{i=1}^5 \E\[\\# \text{heads by coin }A | X\_i, \theta\]$$

**M-Step**

With our expected values in hand, now comes the M step where we want to maximize $\theta$ given our expected values. This is done by simple normalization! $$\theta\_A^1 = \frac{E\[\\#\text{heads over } X \text{ by coin } A|X ,\theta\]}{E\[\\#\text{heads and tails over } X \text{ by coin } A|X ,\theta\]} = \frac{21.3}{21.3 + 9.6} \approx 0.71.$$ Likewise for $B$. This process begins again with the E-Step and $\theta^1$ and continues until the values for $\theta$ converge (or to some alloweable threshold). In this example we have 10 iterations and $\hat{\theta} = \theta^{10} = (0.8, 0.52)$. In each iteration the value of $\Pr\[X,Z|\theta\]$ increases, due to the better estimate of $\theta$.

Now in this case the model was fairly simplistic. Things can get much more complicated pretty quickly, however the EM algorithm will always converge, and will always produce a maxmimum likelihood estimator $\hat{\theta}$. It may be a *local* estimator, but to get around this we can just restart the EM process with a different initialization. We can do this a constant amount of times and retain the best results (i.e., those with the highest final likelihood).

---
Tags: probability-theory, statistics
---


# Question
Title: Difference between pattern matching and pattern searching in terms of DFA/Regex
E.g.

**Matching Problem** The DFA of regex `good` is like a chain.

```
match:     "good"
not match: "people do not give good comments are not good people"

```

**Searching Problem** The DFA used in searching regex `good` could be:

```
1 matching:  "good"
2 matchings: "people do not give good comments are not good people"

```

Here are the questions:

1. In the above two problems, it seems the searching problem's DFA is the matching problem's DFA plus some backedges and an additional state (here state `0`). Is this the difference in general?
2. What is the regex of searching problem in this case?

# Answer
This is true in general, in a way. Consider a regex $r$. You can construct a DFA (or NFA) for the matching problem. Denote this NFA by $A$.

To solve the searching problem, you can proceed in several ways. First, you can just solve the matching problem for the regex $\Sigma^\*\cdot r\cdot \Sigma^\*$.

Alternatively, you can construct an equivalent NFA for the latter regex. The form of such an NFA would be an initial state that guesses when $r$ starts (at which point there is a transition to the initial states of $A$), and every accepting state of $A$ moves to an accepting sink.

This NFA can be thought of as a generalization of the situation you describe. Indeed, when you determinize it, the equivalent DFA essentially tracks $r$, and whenever it fails the DFA "resets". This is not exact, since it strongly depends on $r$.

When $A$ is a chain, then indeed determinizing the NFA yields a DFA that follows the chain, and whenever there is a "mistake" (that is, $r$ is not met), it resets to the initial state. However, it could be that resetting might not go as far as the initial state. For example, when searching for $aba$, if you see $aa$, then the second $a$ should not reset all the way back, but rather to the second state, since the second $a$ may be the start of the regex's occurrence.
> 3 votes

---
Tags: finite-automata, regular-expressions, search-algorithms
---


title: Time units required for Interrupt Cycle

text:
# Question
Title: Time units required for Interrupt Cycle
I am reading William Stallings Computer Organization & Architecture to understand about control unit & micro-operations.

Stallings explain that interrupt cycle requires 3 time units to complete :

```
t1 : MBR <- (PC)
t2 : MAR <- Save_Address
     PC <- Routine_Address
t3 : Memory <- (MBR)

```

t1 : Save the current PC value to MBR

t2 : Save\_Address provides the memory location where the value of PC has to be stored. It is saved in MAR.

Routine\_Address gives the address for Interrupt Service Routine

t3 : The MBR (which has old value of PC) is stored to memory location (whose address provided by MAR)

But this is how I am thinking, the above operations can be completed in only 2 time units.

```
t1 : MBR <- (PC)
     MAR <- Save_Address
t2 : PC <- Routine_Address
     Memory <- (MBR)

```

I checked twice & I find no dependency among micro-operations performed in time unit t1 & t2.

So, is my approach correct ?

# Answer
Your approach will work. There are no hard and fast rules in micro-op scheduling. The number of micro-ops that can be executed in parallel depends on the internal organization of the CPU. Clearly, we cannot reload the program counter (PC) until we save its contents, but there is nothing stopping us from saving its contents on the leading of the clock signal and loading new contents on the trailing edge.
> 1 votes

# Answer
Maybe the transfers in t1 and t2 share some component in the datapath, such as a bus for making the transfer. Where does Save\_address come from?
> 0 votes

---
Tags: computer-architecture
---


# Question
Title: An example where Knuth-Morris-Pratt Algorithm is faster than Boyer-Moore?
This page about Knuth-Moriss-Pratt Algorithm compared to Boyer-Moore describes a possible case where the Boyer-Moore algorithm suffers from small skip distance while KMP could perform better.
I'm looking for a good example (text,pattern) that can clearly demonstrate this case.

# Answer
Well these patterns will make KMP work faster:

T=aaaaaaaaaa P=aaaa KMP will try 10 compare steps were Boyer-Moore will take 28

Another example:

T=aaaaaaaaaa P=abab KMP will try 8 compare steps where BM will try 12.
> 4 votes

# Answer
There is a paper that did a good experiment over these string matching algorithms for different patterns: "Comparison of string matching algorithms: an aid to information content security"

Also there is a study of these string matching algorithms for Japanese language: Comparison and Improvement of String Matching Algorithms For Japanese Texts

I hope these are useful to get a sense about algorithms efficiency!
> 3 votes

---
Tags: algorithms, substrings, matching
---


# Question
Title: A vector-like data structure with allocation table; O(1) indexing time required
I am a beginner in data structures and recently came across a vector implemented on an array, which is extended on demand. Of course the table cannot be extended "in place", we must allocate a new array, then copy elements from the previous one which is a linear operation itself (invoked log(n) times, where n is the number of insertion operations). Are there better implementations of such data structure while preserving constant item access time? For example, how about implementing a concept known from disk file systems - an allocation table; whenever we need to extend our array, an allocation table entry is created for newly reserved memory, without touching previously inserted items. Indexing time could still be constant, if only the allocation table would be implemented wisely (for example with using constant "page" size) What I've written could be complete nonsense; it's just an idea.

# Answer
> 7 votes
The indexing time is always O(1) for an array whether you reallocate or not! Reallocating is not a bad idea if the table size doubles each time the array overflows, insertion takes constant time amortized.

Your idea is no different from a linked list of arrays of fixed size (correct if I'm wrong). If the list gets really large, looking for an element will take a lot of time.

---
Tags: data-structures, efficiency, arrays
---


title: How to understand the SR Latch

text:
# Question
Title: How to understand the SR Latch
I can't wrap my head around how the SR Latch works. Seemingly, you plug an input line from R, and another from S, and you are supposed to get results in $Q$ and $Q'$.

However, both R and S require input from the other's output, and the other's output requires input from the other other's output. What comes first the chicken or the egg??

When you first plug this circuit in, how does it get started?

# Answer
A flip-flop is implemented as a bi-stable multivibrator; therefore, Q and Q' are guaranteed to be the inverse of each other except for when S=1, R=1, which is not allowed. The excitation table for the SR flip-flop is helpful in understanding what occurs when signals are applied to the inputs.

```
S R  Q(t) Q(t+1)
----------------
0 x   0     0
1 0   0     1
0 1   1     0
x 0   1     1

```

The outputs Q and Q' will rapidly change states and come to rest at a steady state after signals have been applied to S and R.

```
Example 1: Q(t) = 0, Q'(t) = 1, S = 0, R = 0.

State 1: Q(t+1 state 1)  = NOT(R OR Q'(t)) = NOT(0 OR 1) = 0
         Q'(t+1 state 1) = NOT(S OR Q(t)) =  NOT(0 OR 0) = 1

State 2: Q(t+1 state 1)  = NOT(R OR Q'(t+1 state 1)) = NOT(0 OR 1) = 0
         Q'(t+1 state 2) = NOT(S OR Q(t+1 state 1))  =  NOT(0 OR 0) = 1

Since the outputs did not change, we have reached a steady state; therefore, Q(t+1) = 0, Q'(t+1) = 1.

Example 2: Q(t) = 0, Q'(t) = 1, S = 0, R = 1

State 1: Q(t+1 state 1)  = NOT(R OR Q'(t)) = NOT(1 OR 1) = 0
         Q'(t+1 state 1) = NOT(S OR Q(t))  = NOT(0 OR 0) = 1

State 2: Q(t+1 state 2)  = NOT(R OR Q'(t+1 state 1)) = NOT(1 OR 1) = 0
         Q'(t+1 state 2) = NOT(S OR Q(t+1 state 1))  =  NOT(0 OR 0) = 1

We have reached a steady state; therefore, Q(t+1) = 0, Q'(t+1) = 1.

Example 3: Q(t) = 0, Q'(t) = 1, S = 1, R = 0

State 1: Q(t+1 state 1)  = NOT(R OR Q'(t)) = NOT(0 OR 1) = 0
         Q'(t+1 state 1) = NOT(S OR Q(t)) =  NOT(1 OR 0) = 0

State 2: Q(t+1 state 2)  = NOT(R OR Q'(t+1 state 1)) = NOT(0 OR 0) = 1
         Q'(t+1 state 2) = NOT(S OR Q(t+1 state 1))  = NOT(1 OR 0) = 0

State 3: Q(t+1 state 3)  = NOT(R OR Q'(t+1 state 2)) = NOT(0 OR 0) = 1
         Q'(t+1 state 3) = NOT(S OR Q(t+1 state 2))  = NOT(1 OR 1) = 0

We have reached a steady state; therefore, Q(t+1) = 1, Q'(t+1) = 0.

Example 4: Q(t) = 1, Q'(t) = 0, S = 1, R = 0

State 1: Q(t+1 state 1)  = NOT(R OR Q'(t)) = NOT(0 OR 0) = 1
         Q'(t+1 state 1) = NOT(S OR Q(t)) =  NOT(1 OR 1) = 0

State 2: Q(t+1 state 2)  = NOT(R OR Q'(t+1 state 1)) = NOT(0 OR 0) = 1
         Q'(t+1 state 2) = NOT(S OR Q(t+1 state 1))  = NOT(1 OR 1) = 0

We have reached a steady state; therefore, Q(t+1) = 1, Q'(t+1) = 0.

Example 5: Q(t) = 1, Q'(t) = 0, S = 0, R = 0

State 1: Q(t+1 state 1)  = NOT(R OR Q'(t)) = NOT(0 OR 0) = 1
         Q'(t+1 state 1) = NOT(S OR Q(t)) =  NOT(0 OR 1) = 0

State 2: Q(t+1 state 2)  = NOT(R OR Q'(t+1 state 1)) = NOT(0 OR 0) = 1
         Q'(t+1 state 2) = NOT(S OR Q(t+1 state 1))  = NOT(0 OR 1) = 0

We have reached a steady; state therefore, Q(t+1) = 1, Q'(t+1) = 0.

With Q=0, Q'=0, S=0, and R=0, an SR flip-flop will oscillate until one of the inputs is set to 1.

Example 6: Q(t) = 0, Q'(t) = 0, S = 0, R = 0

State 1: Q(t+1 state 1)  = NOT(R OR Q'(t)) = NOT(0 OR 0) = 1
         Q'(t+1 state 1) = NOT(S OR Q(t)) =  NOT(0 OR 0) = 1

State 2: Q(t+1 state 2)  = NOT(R OR Q'(t+1 state 1)) = NOT(0 OR 1) = 0
         Q'(t+1 state 2) = NOT(S OR Q(t+1 state 1))  = NOT(0 OR 1) = 0

State 3: Q(t+1 state 3)  = NOT(R OR Q'(t+1 state 2)) = NOT(0 OR 0) = 1
         Q'(t+1 state 3) = NOT(S OR Q(t+1 state 2)) =  NOT(0 OR 0) = 1

State 4: Q(t+1 state 4)  = NOT(R OR Q'(t+1 state 3)) = NOT(0 OR 1) = 0
         Q'(t+1 state 4) = NOT(S OR Q(t+1 state 3))  = NOT(0 OR 1) = 0

As one can see, a steady state is not possible until one of the inputs is set to 1 (which is usually handled by power-on reset circuitry).

```
> 7 votes

---
Tags: circuits, sequential-circuit
---


# Question
Title: Asymptotic Properties of Functions in Complexity Analysis
When dealing with the analysis of time and space complexity of algorithms, is it safe to assume that any function which has tight bounds ( i.e. $f(n)=\Theta(g(n))$ is asymptotically positive and asymptotically monotonically increasing. I mean that for all $n$ greater than or equal to some $n\_0$ both those properties hold?

# Answer
> 8 votes
It is safe to assume that $f$ is everywhere positive, hence, asymptotically positive. You can't use negative time or space.

It is not safe to assume that $f$ is asymptotically monotonically increasing, since this excludes constant functions, i.e., those which are $\Theta(1)$.

It isn't even safe to assume that $f$ is asymptotically monotonically non-decreasing; this precludes functions that oscillate. A good question might be "do any useful algorithms have asymptotically oscillating time or space complexities," but certainly you could create an algorithm that did.

I suppose a more rigorous answer would ask what your definition of "asymptotically monotonically increasing" means. If it means that it's $\Theta(g(n))$ where $g(n)$ is monotonically increasing for positive $n$, then the answer would be yes, by definition.

# Answer
> 4 votes
No. There are complexity functions that oscillate, for example runtime of Mergesort.

It is not even true that every meaningful complexity function is in $\Theta$ of a monotonically increasing function; see this answer to your older question.

---
Tags: time-complexity, asymptotics, landau-notation
---


# Question
Title: Is there a "sorting" algorithm which returns a random permutation when using a coin-flip comparator?
Inspired by this question in which the asker wants to know if the running time changes when the comparator used in a standard search algorithm is replaced by a fair coin-flip, and also Microsoft's prominent failure to write a uniform permutation generator, my question is thus:

Is there a comparison based sorting algorithm which will, depending on our implementation of the comparator:

1. return the elements in sorted order when using a *true* comparator (that is, the comparison does what we expect in a standard sorting algorithm)
2. return a uniformly random permutation of the elements when the comparator is replaced by a fair coin flip (that is, return `x < y = true` with probability 1/2, regardless of the value of x and y)

The code for the sorting algorithm must be the same. It is only the code inside the comparison "black box" which is allowed to change.

# Answer
> 3 votes
The following deterministic (without the comparator) algorithm works for an input tuple $(a\_1,\dots,a\_n)$:

1. Do the Fisher-Yates shuffle using your comparator with some static pair (say $a\_1 \< a\_2$) as a coin flip (doing acceptance-rejection sampling). If the comparator outputs $1$ the first time, use it inverted to avoid an endless rejection loop in the deterministic case.
2. (optional speedup: Try a single pair $n$ times, where $n$ is the length or your input. If any two of the outputs differ return the permutation obtained in (1))
3. Sort your array using merge sort.

Given a deterministic order relation as comparator this algorithm sorts an array in time $\mathcal{O}(n \log n)$ since the Fisher-Yates shuffle runs in $\mathcal{O}(n)$ using maximal $\mathcal{O}(\log n)$ nonrandom "random bits" (e.g. calls to your comparator) in each step and merge sort has the same asymptotic complexity. The result of (1) is totally useless in this case, but since it's followed by a real sort, this does no harm.

Given a real coin flip as comparator (1) permutes the array with equal probability for each permutation and if you really have to do (3) (you left out (2) or (2) failed to determine the randomness), this is no harm because the distribution of its result only depends on the order of its input which is uniformly distributed among all permutations because of (1), so the result of the entire algorithm is also uniformly distributed. The number of times each acceptance-rejection sampling has to be repeated is geometrically distributed (reject with probability $\< \frac{1}{2}$) and therefore it has an expected value $\< 2$. Each repetition uses at most $\log n$ bits, so the runtime analysis is nearly the same as in the deterministic case, but we only get an **expected runtime** of $\mathcal{O}(n \log n)$, with the possibility of nontermination (terminates only **almost surely**).

---

As Joe pointed out: If you don't like the test for the first bit in (1), do (3) then (1) and use $a\_n \< a\_1$ which is always $0$, since the array is already sorted in the deterministic case. Additionally you have to subtract your random number from the upper bound on the range in the loop, because the upper bound for the random number yields the identical permutation. But be aware that (2) is forbidden then, because you always have to do the shuffle in the ransom case.

---

You can even use the same calls to your comparator for (1) and (3), but then proving that the result is uniformly distributed is at least a lot harder, if possible at all.

---

The following algorithm is has no distinct phases to shuffle and sort, but is asymptotically slower. It's essentially **insertion sort** with **binary search**. I will use $a=(a\_1,\dots,a\_n)$ to denote the input and $b\_k=(b\_{k,1},\dots,b\_{k,k})$ to denote the result after the $k$-th round: 1. Set $b\_{1,1} = a\_1$
2. If $a\_2 \< a\_1$ then $b\_2 = (a\_2,a\_1)$ and $(c,d):= (2,1)$ else $b\_2 = (a\_1,a\_2)$ and $(c,d):= (1,2)$. In either case $a\_d \< a\_c$ will always be $0$ (i.e. false) for a nonrandom comparator.
3. To obtain $b\_{k}$ for $k \geq 3$ obtain $b\_{k-1}$ first.
4. Let $l=\lceil log\_2 k \rceil$ and $k' = 2^l$, i.e. $k'$ is the least power of $2$ not smaller than $k$.
5. Let $i\_0 = 0$. For every $j \in \\{1,\dots,l\\}$ let $$i\_j = \begin{cases} i\_{j-1} + 2^{l-j} & i\_{j-1} + 2^{l-j} \> k-1 \wedge a\_d \< a\_c\\ i\_{j-1} & i\_{j-1} + 2^{l-j} \> k-1 \wedge \neg (a\_d \< a\_c)\\ i\_{j-1} + 2^{l-j} & i\_{j-1} + 2^{l-j} \leq k-1 \wedge b\_{k-1,i\_{j-1} + 2^{l-j}} \< a\_k \\ i\_{j-1} & i\_{j-1} + 2^{l-j} \leq k-1 \wedge \neg(b\_{k-1,i\_{j-1} + 2^{l-j}} \< a\_k) \\ \end{cases}$$
6. If $i\_l \> k$ repeat (5.) else $b\_k=(b\_{k-1,1},\dots,b\_{k-1,i\_l -1},a\_k,b\_{k-1,i\_l},\dots,b\_{k-1,k-1})$
7. Output $b\_n$

Random case: 5 + the if clause of 6 is essentially acceptance-rejection sampling. The rest of the algorithm is a naive shuffle: shuffle the first $k-1$ elements and add the $k$-th element to each position with equal probability. If we used the normal insertion sort, we would get a binomial distribution instead.

Note that this algorithm is inefficient in both modes compared to the Fisher-Yates shuffle and merge sort as inserting an element to an arbitrary position is expensive if using an array and binary search needs linear time if using a list. But perhaps a modification of heap sort or tree sort in a similar way could lead to a faster algorithm.

# Answer
> 4 votes
No, this is impossible unless $n \leq 2$. The probability that a permutation is generated by your algorithm using a random comparator is dyadic, i.e. of the form $A/2^B$, whereas the probability should be $1/n!$. When $n \> 2$, there is no way to write $1/n!$ in the form $A/2^B$.

---
Tags: sorting, randomized-algorithms, permutations
---


title: Weighted sum of last N numbers

text:
# Question
Title: Weighted sum of last N numbers
Suppose we're receiving numbers in a stream. After each number is received, a weighted sum of the last $N$ numbers needs to be calculated, where the weights are always the same, but arbitrary.

How efficiently can this done if we are allowed to keep a data structure to help with the computation? Can we do any better than $\Theta(N)$, i.e. recomputing the sum each time a number is received?

For example: Suppose the weights are $W= \langle w\_1, w\_2, w\_3, w\_4\rangle$. At one point we have the list of last $N$ numbers $L\_1= \langle a, b, c, d \rangle\>$, and the weighted sum $S\_1=w\_1\*a+w\_2\*b+w\_3\*c+w\_4\*d$.

When another number, $e$, is received, we update the list to get $L\_2= \langle b,c,d,e\rangle$ and we need to compute $S\_2=w\_1\*b+w\_2\*c+w\_3\*d+w\_4\*e$.

**Consideration using FFT** A special case of this problem appears to be solvable efficiently by employing the Fast Fourier Transform. Here, we compute the weighed sums $S$ in multiples of $N$. In other words, we receive $N$ numbers and only then can we compute the corresponding $N$ weighed sums. To do this, we need $N-1$ past numbers (for which sums have already been computed), and $N$ new numbers, in total $2N-1$ numbers.

If this vector of input numbers and the weight vector $W$ define the coefficients of the polynomials $P(x)$ and $Q(x)$, with coefficients in $Q$ reversed, we see that the product $P(x)\times Q(x)$ is a polynomial whose coefficients in front of $x^{N-1}$ up to $x^{2N-2}$ are exactly the weighted sums we seek. These can be computed using FFT in $\Theta(N\*\log (N))$ time, which gives us an average of $Θ(\log (N))$ time per input number.

This is however not a solution the the problem as stated, because it is required that the weighted sum is computed efficiently *each* time a new number is received - we cannot delay the computation.

# Answer
> 6 votes
Here is an elaboration of your approach. Every $m$ iterations, we use the FFT algorithm to compute $m$ values of the convolution in time $O(n\log n)$, assuming that the subsequent $m$ values are zero. In other words, we are computing $$ \sum\_{i=0}^{n-1} w\_i a\_{t-i+k}, \quad 0 \leq k \leq m-1, $$ where $w\_i$ are the $n$ weights (or the reverse weights), $a\_i$ is the input sequence, $t$ is the current time, and $a\_{t'} = 0$ for $t' \> t$.

For each of the following $m$ iterations, we are able to calculate the required convolution in time $O(m)$ (the $i$th iteration needs time $O(i)$). So the amortized time is $O(m) + O(n\log n/m)$. This is minimized by choosing $m = \sqrt{n\log n}$, which gives an amortized running time of $O(\sqrt{n\log n})$.

We can improve this to worst-case running time of $O(\sqrt{n\log n})$ by breaking the computation into parts. Fix $m$, and define $$ b\_{T,p,o} = \sum\_{i=0}^{m-1} w\_{pm+i} a\_{Tm-i+o}, \quad C\_{T,p} = b\_{T,p,0}, \ldots, b\_{T,p,m-1}. $$ Each $C\_{T,p}$ depends only on $2m$ inputs, so it can be computed in time $O(m\log m)$. Also, given $C\_{\lfloor t/m \rfloor-p,p}$ for $0 \leq p \leq n/m-1$, we can compute the convolution in time $O(n/m + m)$. The plan therefore is to maintain the list $$ C\_{\lfloor t/m \rfloor-p,p}, \quad 0 \leq p \leq n/m-1. $$ For each period of $m$ inputs, we need to update $n/m$ of these. Each update takes time $O(m\log m)$, so if we spread these updates evenly, each input will take up work $O((n/m^2) m\log m) = O((n/m) \log m)$. Together with computing the convolution itself, the time complexity per input is $O((n/m)\log m + m)$. Choosing $m = \sqrt{n\log n}$ as before, this gives $O(\sqrt{n\log n})$.

---
Tags: algorithms, data-structures, online-algorithms
---


title: How hard is a variant of Sudoku puzzle?

text:
# Question
Title: How hard is a variant of Sudoku puzzle?
Sudoku is well known puzzle which is known to be NP-complete and it is a special case of more general problem known as Latin squares. A correct solution of the $N \times N$ square consists of filling every row and every column with numbers from $1$ to $N$ under the condition that every number appears exactly once in any row or any column.

I define a new problem. The input is a correct solution of $N \times N$ Sudoku puzzle (more generally Latin square problem). I would like to decide whether there is permutation of rows and permutation of columns such that no row and no column contains consecutive triples.

An examples for a row without consecutive triple is 9 5 6 2 3 8 4 7 1. An example for a row with consecutive triple is 8 9 5 2 3 4 7 6 1. The triple is 2 3 4.

I suspect the problem is NP-hard but I was not able to find a reduction.

How hard is solving this variant of Sudoku puzzle? Is it NP-complete?

**EDIT** : To clarify, the same permutation must be applied to the columns and the rows.

# Answer
> 4 votes
When the row and column permutations are different and the consecutive triples have to be increasing: The answer is always YES.

Suppose the matrix has size $N\times N$. Consider a random permutation of the columns. Each row (by itself) is a random permutation. The probability that the numbers $i,i+1,i+2$ appear in positions $t,t+1,t+2$ is $1/(N(N-1)(N-2))$. There are $N-2$ choices for $t$ and $i$, and $N$ different rows. Therefore the expected number of consecutive triples is $N(N-2)^2/(N(N-1)(N-2)) \< 1$. We conclude that there is some permutation of the columns, under which there are no consecutive triples in any of the rows. Now repeat the same argument for the columns - note that permuting the rows cannot create a consecutive triple in any of them.

When the row and column permutations are the same, and consecutive triples can be either increasing or decreasing: The answer is still YES, for large enough $N$.

The idea is to use the lopsided version of the Lovász local lemma, via Lu and Székely's paper Using Lovász local lemma in the space of random injections. In the earlier proof, we considered events $X\_{\ell,i,t,\sigma}$ for $\sigma \in \\{\pm 1\\}$, which for a line $\ell$ (either a row or a column), state that $\ell(i+\sigma\delta)=t+\delta$ for $\delta \in \\{0,1,2\\}$. These are examples of the *canonical events* considered by Lu and Székely: if the random permutation (permuting both rows and columns) is $\pi$, then they are of the form $\pi(t)=j\_0,\pi(t+1)=j\_1,\pi(t+2)=j\_2$, where $j\_\delta = \ell^{-1}(i+\sigma\delta)$. Two events $X\_{\ell,i,t,\sigma},X\_{\ell',i',t',\sigma'}$ *conflict* if $\\{t,t+1,t+2\\} \cap \\{t',t'+1,t'+2\\} \neq \emptyset$ or $\\{j\_0,j\_1,j\_2\\} \cap \\{j'\_0,j'\_1,j'\_2\\} \neq \emptyset$ (this is actually only a necessary condition). Each event conflicts with at most $2N\cdot 2\cdot 2\cdot 5 - 1= 40N-1$ other events ($2N$ lines, two orientations, two ways to conflict, five conflicting positions). While non-conflicting events are in general dependent, using the lopsided version of the Lovász local lemma we can ignore this, and let our dependency graph include edges only for conflicting events. Since the probability that each event happens is $p = 1/(N(N-1)(N-2))$ and the size of each neighborhood is $d \leq 40N-1$, the lemma applies whenever $ep(d+1) \leq 1$, that is $$ 40eN \leq N(N-1)(N-2). $$ This condition is satisfied for $N \geq 12$. We conclude that for $N \geq 12$, the required permutation always exists. Using the recent constructive version of LLL, we can even find it efficiently.

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


# Question
Title: Complexity of transposing matrices represented as list of row or column vectors
Given \[\[1,4,7\],\[2,5,8\],\[3,6,9\]\] which is a list of the column vectors of matrix

```
|1, 2, 3|
|4, 5, 6|
|7, 8, 9|

```

is $ \Omega(n^2) $ a lower bound for transposing? Assume the matrix is not always square. I have to touch each element at least once, because going from 2 x 5 to 5 x 2 matrix for example, will mean going from a list of 5 lists to a list of 2 lists, so I can't really do any tricks with the array indices, right?

Is there a faster way to transpose matrices?

# Answer
If the matrices are stored in the usual way, that is as long vectors, then the complexity is $\Theta(n^2)$. The reason is that if all the off-diagonal entries in the matrix are different, you will need to change all of them, and there are $n^2-n$ of them.
> 5 votes

---
Tags: algorithms, lower-bounds, matrices
---


# Question
Title: Evaluation metric for an ordering algorithm
There is a sentence with N words.

The words are randomly shuffled.

I have a heuristic algorithm that tries to restore the original order.

I want to evaluate my algorithm on a dataset of several hundred long sentences from the internet.

The main goal of the algorithm is that humans looking at the restored sentence will be able to easily know what the original sentence was. So I can evaluate my algorithm by asking humans to grade the quality of the restored order. However, this is very expensive.

Another option is to count the number of words that are in their correct position in each sentence, and divide by the total number of words in all sentences. However, this is not a good measurement of the quality, because, for example, if the only mistake of my algorithm is that it put the last word first, the resulting sentence will get a score of 0, although it is quite similar to the gold standard, and a human will easily notice this.

A third option is to find the minimum number of word moves that need to be done on the algorithm output in order to achieve the gold standard. However, this seems like a non-trivial task in itself.

Can you suggest a measurement that will be both meaningful and easy to implement?

# Answer
One standard measure is the Kendall tau distance, which is the number of "inversions", i.e. positions $i \< j$ such that $\pi(i) \> \pi(j)$. It is also the number of transpositions $(k \\; k+1)$ you need to apply to sort $\pi$, or vice versa, the number of such transpositions needed to generate $\pi$. (So it's the distance metric in the Cayley graph of $S\_n$ with respect to the transpositions $(k \\; k+1)$, which form a generating set.)
> 1 votes

---
Tags: natural-language-processing, string-metrics
---


# Question
Title: Why is the subset of palindromes of a regular language context-free?
Why is $A(L) = \\{x \in L \mid x = x^R \\}$ context-free if $L$ is a regular language?

Trying to understand the approach to determining whether a regular language is context-free.

# Answer
> 5 votes
Regular language is always context-free (but not vice-versa). The language you ask for, $A(L)$, is based on a regular language $L$, but need not be regular.

To show that $A(L)$ (or any other language) is context free, you need to come up with either a context-free grammar that generates $A(L)$, or a PDA that accepts $A(L)$ (or use closure properties of CF languages, as Yuval suggests).

As for the language $A(L)$ in the question, here's a hint for a PDA:

> The PDA non-deterministically decides what is the middle-point of the input. during the first half it pushes the input to the stack, and then pops it (in reverse order) and compares it to the rest of the input. In parallel (i.e, using "cross-product" construction), it runs the DFA of $L$ on the input.

# Answer
> 5 votes
Hint: The intersection of a context-free language with a regular language is still context-free.

---
Tags: formal-languages, regular-languages, context-free, closure-properties
---


title: Union of two automata

text:
# Question
Title: Union of two automata
I need to find a minimal DFA given the following information:

> $ \\{a^nb : n\geq 0\\} \cup \\{b^na: n \geq 1\\}$

Now, maybe I'm not seeing this properly, but I don't see how this is possible: the first one will take 0 or more a's followed by one b, whereas the second one will take a 1 or more b's followed by one a.

Drawing the combined automata only brought me to trap states. Any suggestions?

# Answer
> 3 votes
As @vonbrand suggested, using one automata (without attempting to combine them) is sufficient. Combining them will prove to be more work than it's worth.

Basically, here's the idea:

* If you get an $a$, begin looping on $a^nb$. If you get a $b$ after this, accept. But anything further goes to the trash can.
* If you get a $b$, accept for $a^0b$. If you get another $b$, you can then loop on $b$ under $b^na$. At any point in the loop, if you get an $a$, accept. But if you get anything after that $a$, go to the trash can.

Here is a textual representation (`t` is the "trash can" or trap state; `+` represents an accept state).

```
  | 0   | 1   | 2+  | 3+  | 4+  | 5
a | 1   | 1   | 4   | t   | t   | 4
b | 2   | 3   | 5   | t   | t   | 5

```

And here is a generated visual version:

(*I'm not 100% sure this is minimal, but if it's not, it's a good exercise.*)

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


# Question
Title: How to prove polynomial time equivalence?
Define the problem $W$:

> **Input:** A multi-set of numbers $S$, and a number $t$.
>
> **Question:** What is the smallest subset $s \subseteq S$ so that $\sum\_{k \in s} k = t$, if there is one? (If not, return `none`.)

I am trying to find some polytime equivalent decision problem $D$ and provide a polytime algorithm for the non-decision problem $W$ assuming the existence of a polytime algorithm for $D$.

Here is my attempt at a related decision problem:

> $\mathrm{MIN\text{-}W}$:
>
> **Input:** A multi-set of numbers $S$, two numbers $t$ and $k$.
>
> **Question:** Is there a subset $s \subseteq S$ so that $\sum\_{k \in s} k = t$ and $|s| \leq k$?

Proof of polytime equivalence:

Assume $W \in \mathsf{P}$.

```
solveMIN-W(S, t, k):
1. S = sort(S)
2. Q = {}
3. for i=1 to k:
4.     Q.add(S_i)
5.     res = solveW(Q, t)
6.     if res != none and res = t: return Yes
7. return No

```

I'm not sure about this algorithm though. Can anyone help please?

# Answer
> 0 votes
The problems you mention here are variations of a problem called SUBSET-SUM, FYI if you want to read some literature on it.

What is $S\_i$ in your algorithm? If it's the $i$-th element, then you assume that the minimal set will use the smaller elements, which is not necessarily true - there could be a large element that is equal to $t$, in which case there is a subset of size $1$. So the algorithm doesn't seem correct.

However, as with many optimization problems that correspond to NP-complete problems, you can solve the optimization problem given an oracle to the decision problem.

First, observe that by iterating over $k$ and calling the decision oracle, you can find what is the minimal *size* $k\_0$ of a subset whose sum equals $k$ (but not the actual subset).

After finding the size, you can remove the first element in $S$, and check whether there is still a subset of size $k\_0$ - if not, then $s\_1$ is surely in a minimal subset, so compute $t-s\_1$, and repeat the process with the rest of $S$.

If $s\_1$ does not effect the size $k\_0$, then repeat the process with $S\setminus \\{s\_1\\}$.

It is not hard to verify that this process takes polynomial time.

---
Tags: complexity-theory, reductions, p-vs-np
---


# Question
Title: How do you apply Context-Free Pumping Lemma to these problems, and how do the approaches differ?
How are these Context-Free Pumping Lemma Approaches differ? Maybe this might help understand pumping lemma better

$(a^{i}b^{i}c^{j}d^{j} \mid i, j \geq 0$}

$(a^{i}b^{j}c^{i}d^{j} \mid i, j \geq 0$}

$(a^{i}b^{j}c^{j}d^{i} \mid i, j \geq 0$}

I understand we use contradiction with these conditions

1. $|vwx| \leq p$
2. $|vx| \geq 1$
3. for every $i \geq 0$, $uv^{i}wx^{i}y \in L$.

# Answer
Not all three languages are in fact non-context-free. Try to spot those that have a CF-grammar, and apply pumping to the remaining example(s). That is the difference you mean, I presume?

(added) The grammars you give in a comment seem correct to me. General hints for applying the pumping lemma are given in various answers at this site, see in particular How to prove that a language is not context-free?
> 2 votes

---
Tags: context-free, pumping-lemma
---


# Question
Title: Proving NP Completeness of a subset-sum problem - how?
So I'm trying to understand P/NPC problems. The one I'm trying to tackle now is subset sum (we have a collection of integers $S$ and a $k$ param: is there a subset of $S$ that sum of all it's elements is equal to $k$?) problem and the proof that ss is an NPC problem by reduction from 3SAT.

I've found two PDF's that attempt to solve that, but the problem is, I don't have the foggiest idea how to 'explain in in my own words'.

Okay, some links ahead and questions related to them:

Here, on page 4th, there's a logic table for 3SAT clause that apparently proves why ss is NPC, but I don't get it - what exactly are those s and t values, and how does that table proves NPC'ness? And how k is computed in that table? It's simply not clear to me :(

Another link on pages 5 and 6 there are another tables that appear out of nowhere with no explanation that I could understand.

So, if anybody knows what I'm talking about and could help me, please answer :). Or, if it's possible, can anybode give me a simple and straightforward proof why subset sum is NPC?

# Answer
> 3 votes
The trick to the reduction is to use numbers to encode statements about the 3CNF formula, crafting those numbers in such a way that you can later make an arithmetic proposition about the numbers that is only true if the original 3CNF formula is satisfiable. Using the 3SAT -\> SUBSET SUM reduction from your lecture notes:

The $y$ values encode statements about which variables have positive literals in which clauses. The $z$ values encode statements about which variables have negative literals in which clauses.

The $s$ value is crafted the same way for each clause; put a one in the digit position corresponding to that clause, and zeroes everywhere else. The $t$ value will be the same as the $s$ value for each clause.

The $k$ value is always 1111... followed by 33333.... where the number of ones is the same as the number of distinct variables in the formula and the number of threes is the number of clauses in the formula. Note that the required sum $k$ has a one in each digit position corresponding to the variables. This means that any solution to the subset sum problem can include only encoded statements about either a positive instance of the variable or a negative instance in each clause, not both. Note also that sum $k$ has a three in the digit position corresponding to each clause. The $s$ and $t$ values for each clause will sum to two, but to complete the sum a third one will have to come from one of the $y$ or $z$ values. All three ones could come from the $y$ and $z$ values, but the fact that $s$ and $t$ will only sum to two for any clause guarantees that any empty clause in the 3CNF formula forces the subset sum problem to become unsatisfiable.

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


# Question
Title: Complexity of algorithm inserting an element in a circular linked list at the front end
In a circular linked list, if an elements needs to be inserted at front \[just before the node pointed by head\], can be done in O(1) (see the answer here)

But in a book currently, I have, it is mentioned that it is done in O(n) (the usual method). I also saw few lecture ppts, they all mention the usual method of traversing the list & adding an element.

My question is :

1. In practical scenarios which method is used ?
2. I am about to attend an exam, which consists of MCQs, if above question is asked shall I mark O(n), since that is the standard answer ?

# Answer
> 0 votes
The method used in practical scenarios depends on the scenario (and on the programmer). There are several possible issues influencing the choice of implementation:

1. Whether the algorithm is known to the programmer.
2. Ease of coding (it's easiest if it's already implemented in some library you can use).
3. Speed - that depends on how the data structure is used.
4. Space overhead taken by the data structure.

An intelligent programmer should take all of these into account, and try to make themselves more knowledgeable of various algorithms and data structures.

---
Tags: data-structures, efficiency, linked-lists
---


# Question
Title: Polytime and polyspace algorithm for determining the leading intersection of n discrete monotonic functions
Some frontmatter: I'm a recreational computer scientist and employed software engineer. So, pardon if this prompt seems somewhat out of left field -- I routinely play with mathematical simulcra and open problems when I have nothing better to do.

While playing with the Riemann hypothesis, I determined that the prime gap can be reduced to a recurrence relation based on the intersection of all $n-1$ complementary functions formed by the multiples of each previous prime number (keen observers will note this is a generalization of the Sieve of Eratosthenes). If this makes absolutely no sense to you, don't worry -- it's still frontmatter.

Seeing how these functions related, I realized that the next instance of each prime can be reduced to the first intersection of these functions, recurring forward infinitely. However, I could not determine if this is tractable in polytime and polyspace. Thus: **what I'm looking for is an algorithm that can determine the first intersection of $n$ discrete (and, if applicable, monotonic) functions in polynomial time and space. If no such algorithm currently exists or can exist, a terse proof or reference stating so is sufficient.**

The closest I can find so far is Dykstra's projection algorithm (yes, that's R. L. Dykstra, not Edsger Dijkstra), which I believe reduces itself to a problem of integer programming and is, therefore, NP-hard. Similarly, if one performs a transitive set intersection of all of the applicable points (as they're currently understood to be bounded), we must still constrain ourselves to exponential space for our recurrence due to the current weak bound of $\ln(m)$ primes for any real $m$ (and therefore, $e^n$ space for each prime $n$).

Globally, I'm wondering if my understanding of the reduction of the problem is wrong. I don't expect to solve the Riemann hypothesis (or any deep, open problem in this space) any time soon. Rather, I'm seeking to learn more about it by playing with the problem, and I've hit a snag in my research.

# Answer
Determining whether two monotone functions given as programs intersect is non-computable. Similarly, determining the first intersection under the promise that it exists is "arbitrarily hard" (definitely not polytime).

Given a program $P$, define a function $f\_P$ which, for input $n$, is $1$ if $P$ stops after $n$ steps or less. The first intersection of $f\_P$ and the constant function $1$ is the running time of $P$, if $P$ halts. So no program can decide whether $f\_P$ and $1$ intersect.

Similarly, the time hierarchy theorem shows that for no recursive time bound $T$, the first intersection point can be found in time $T$, even under the promise that it exists. Using the space hierarchy theorem, you can get the same for space.
> 5 votes

---
Tags: algorithms, reference-request, discrete-mathematics
---


# Question
Title: Can a recurrence relation be translated to a composite function of itself?
Perhaps this is a question for stackoverflow because its practical nature, but I am not aware of any general method to relate recurrence relations and recursive functions.

Having as an example this recurrence relation:

$\qquad \begin{align}a\_0 &= a\_1 = 1 \\ 2a\_n &= 3a\_{n-1}-2a\_{n-2}\end{align}$

I would like to transform it into a recursive *function* $f$, able to be called to itself a number of times (composite), i.e. $f \circ f \circ f \circ \dots \circ f$ ($n$ times), getting the same result as with the $a\_n$ relation.

Any ideas about it?

# Answer
```
 static float f(int n,int m)
      {
         if((n==1)||(m==0)) return (1,1);
         return ((3*n - 2*m)/2,n);
      }

```

That way $\underbrace{f\circ f\circ \dots \circ f}\_{\text{n times}} (1,0)=(a\_n,a\_{n-1})$.

Is that what you wanted?
> 2 votes

# Answer
If I understand your question correctly, the function

$\qquad f(x) = \langle \frac{1}{2} \cdot (3x\[1\] - 2x\[2\]) , x\[1\] \rangle$,

with $\langle \cdot \rangle : \mathbb{N}^2 \to \mathbb{N}$ an encoding of tuples so that $a = \langle b, c \rangle \iff a\[1\] = b \land a\[2\] = c$, does the job in the sense that

$\qquad (\underbrace{f \circ \dots \circ f}\_{n-1 \text{ times}})(\langle 1,1\rangle)\[1\] = a\_n$

for $n \geq 2$. As implementation of $\langle \cdot \rangle$, you can use for instance Cantor's pairing method.

Note how above idea generalises easily: for a recurrence of degree $k$

$\qquad a\_n = g(a\_{n-1},\dots,a\_{n-k}) + h(n)$,

use

$\qquad f(x) = \langle g(x\[1\], \dots, x\[k\]) , x\[1\], \dots, x\[k-1\] \rangle$.
> 2 votes

---
Tags: recurrence-relation, recursion
---


title: DFS miniumum spanning tree

text:
# Question
Title: DFS miniumum spanning tree
Just a quick question,

If i were to alter the general DFS algorithm to do this:

```
minDFS(Vertex v)
{
   if (!v.getVisted())
   {
       v.setVisited();
       Vertex temp = findClosestVertex();
       graph.addEdge(v, temp);
       minDFS(temp);
   }
}

```

Would I eventually (at the end of DFS) get minimum spanning tree? I know there are other ways of getting the MST (Kruskal's, Prim's etc..),but I was just wondering if this would work.

# Answer
No. Consider the counterexample $C\_4$

$V = \\{1,2,3, 4\\}, E = \\{ \\{1,2\\}, \\{2,3\\}, \\{3, 4\\}, \\{1,4\\} \\}$

with $c(1,2) = 1, c(2,3) = 100, c(3,4) = 1, c(1,4) = 2$.

Obviously the MST is the one ST not containing $\\{2,3\\}$, but if your algorithm starts at 1, it goes to 2, then to 3 and then to 4 and finds a suboptimal ST containing $\\{2,3\\}$.

The main problem of your algorithm is that it always computes a path (i.e if there is no path of length $|V| - 1$ your algorithm can terminate without finding a ST), which the MST must not always be.
> 2 votes

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


# Question
Title: Is detecting "doubly" arithmetic progressions 3SUM-hard?
This is inspired by an interview question.

We are given an array of integers $a\_1, \dots, a\_n$ and have to determine if there are distinct $i \lt j \lt k$ such that

* $a\_k - a\_j = a\_j - a\_i$
* $k - j = j - i$

i.e, the sequences $\\{a\_i, a\_j, a\_k\\}$ and $\\{i,j,k\\}$ are both in arithmetic progression.

There is an easy $O(n^2)$ algorithm for this, but finding a sub-quadratic algorithm seems elusive.

Is this a known problem? Can we prove 3SUM-hardness of this? (or maybe provide a sub-quadratic algorithm?)

If you like, you can assume $0 \lt a\_1 \lt a\_2 \lt ... \lt a\_n$ and that $a\_{r+1} - a\_{r} \le K$ for some known constant $K \> 2$. (In the interview problem, $K = 9$).

# Answer
> 13 votes
## **This is an open problem.**

Possibly some weak form of 3SUM-hardness could be proved by adapting a result from Mihai Pătrașcu's STOC 2010 paper "Towards Polynomial Lower Bounds for Dynamic Problems". First, let me define a sequence of closely related problems. The input to each problem is a sorted array $A\[1..n\]$ of distinct integers.

* **3SUM:** Are there distinct indices $i,j,k$ such that $A\[i\] + A\[j\] = A\[k\]$?
* **Convolution3SUM:** Are there indices $i\<j$ such that $A\[i\] + A\[j\] = A\[i+j\]$?
* **Average:** Are there distinct indices $i,j,k$ such that $A\[i\] + A\[j\] = 2 A\[k\]$?
* **ConvolutionAverage:** Are there indices $i\<j$ such that $A\[i\] + A\[j\] = 2A\[(i+j)/2\]$? (This is the problem you're asking about.)

In my PhD thesis, I proved that all four of these problems require $\Omega(n^2)$ time in a decision-tree model of computation that allows only queries of the form "Is $\alpha A\[i\] + \beta A\[j\] + \gamma A\[k\] + \delta$ positive, negative, or zero?", where $\alpha,\beta,\gamma,\delta$ are real numbers (that don't depend on the input). In particular, any 3SUM algorithm in this model must ask the question "Is $A\[i\] + A\[j\]$ bigger, smaller, or equal to $A\[k\]$?" at least $\Omega(n^2)$ times. That lower bound doesn't rule out subquadratic algorithms in a more general model of computation — indeed, it is possible to shave off some log factors in various integer RAM models. But nobody knows what sort of more general model would help more significantly.

Using a careful hashing reduction, Pǎtrașcu proved that if 3SUM requires $\Omega(n^2/f(n))$ expected time, for any function $f$, then Convolution3SUM requires $\Omega(n^2/f^2(n\cdot f(n)))$ expected time. Thus, it's reasonable to say that Convolution3SUM is "weakly 3SUM-hard". For example, if Convolution3SUM can be solved in $O(n^{1.8})$ time, then 3SUM can be solved in $O(n^{1.9})$ time.

I haven't ground through the details, but I'd bet that a parallel argument implies that if Average requires $\Omega(n^2/f(n))$ expected time, for any function $f$, then ConvolutionAverage requires $\Omega(n^2/f^2(n\cdot f(n)))$ expected time. In other words, ConvolutionAverage is "weakly Average-hard".

Unfortunately, it is not known whether Average is (even weakly) 3SUM-hard! I suspect that Average is actually **not** 3SUM-hard, if only because the $\Omega(n^2)$ lower bound for Average is *considerably* harder to prove than the $\Omega(n^2)$ lower bound for 3SUM.

---

You also ask about the special case where adjacent array elements differ by less than some fixed integer $K$. For 3SUM and Average, this variant can be solved in $O(n \log n)$ time using Fast Fourier transforms as follows. (This observation is due to Raimund Seidel.)

Build a bit vector $B\[0..Kn\]$, where $B\[i\]=1$ if and only if the integer $A\[1\]+i$ appears in the input array $A$. Compute the convolution of $B$ with itself in $O(Kn\log Kn) = O(n\log n)$ time using FFTs. The resulting array has a non-zero value in the $j$th position if and only if some pair of elements in $A$ sum to $2A\[1\] + j$. Thus, we can extract a sorted list of sums $A\[i\]+A\[j\]$ from the convolution in $O(n)$ time. From here, it's easy to solve Average or 3SUM in $O(n)$ time.

But I don't know a similar trick for Convolution3SUM or ConvolutionAverage!

---
Tags: algorithms, complexity-theory, lower-bounds
---


# Question
Title: A procedure for Topological sort, proof for its correctness
**Definition:** A preserved invariant of a state machine is a predicate, $P$, on states, such that whenever $P(q)$ is true of a state, $q$, and $q \rightarrow r$ for some state, $r$, then $P(r)$ holds.

**Definition:** A line graph is a graph whose edges are all on one path.

**Definition:** Formally, a state machine is nothing more than a binary relation on a set, except that the elements of the set are called “states,” the relation is called the transition relation, and an arrow in the graph of the transition relation is called a transition. A transition from state $q$ to state $r$ will be written $q \rightarrow r$.

**DAG**: Directed Acylic Graph

> The following procedure can be applied to any directed graph, $G$:
>
> 1. Delete an edge that is in a cycle.
> 2. Delete edge $\<u \rightarrow v\>$ if there is a path from vertex $u$ to vertex $v$ that does not include $\<u \rightarrow v\>$.
> 3. Add edge $\<u \rightarrow v\>$ if there is no path in either direction between vertex $u$ and vertex $v$.
>
> Repeat these operations until none of them are applicable.

This procedure can be modeled as a state machine. The start state is $G$, and the states are all possible digraphs with the same vertices as $G$.

**(b)** Prove that if the procedure terminates with a digraph, $H$, then $H$ is a line graph with the same vertices as $G$.

Hint: Show that if $H$ is not a line graph, then some operation must be applicable.

**(c)** Prove that being a DAG is a preserved invariant of the procedure.

**(d)** Prove that if $G$ is a DAG and the procedure terminates, then the walk relation of the final line graph is a topological sort of $G$.

Hint: Verify that the predicate $P(u,v)$:: there is a directed path from $u$ to $v$ is a preserved invariant of the procedure, for any two vertices $u, \ v$ of a DAG.

**(e)** Prove that if $G$ is finite, then the procedure terminates.

Hint: Let $s$ be the number of cycles, $e$ be the number of edges, and $p$ be the number of pairs of vertices with a directed path (in either direction) between them. Note that $p \leq n^2$ where $n$ is the number of vertices of $G$. Find coefficients $a,b,c$ such that as+bp+e+c is nonnegative integer valued and decreases at each transition.

> ***My Problems:***
>
> I got stuck with problems $d$ and $e$ but solutions to other problems are welcome too.
>
> At problem $d$, **I could not understand the hint and why it is given, how it helps**.

In my way for proving $d$, I am trying to show that given procedure always preserves the order of vertices, which are associated with edges, on the start graph $G$. So a line graph is automatically a topological sort since the "precedence order" of the vertices are preserved.

> But procedure number $3$ is problematic, **how to show it preserves precedence ?**

# Answer
b. As operation $1$ cannot be performed, $H$ must be a DAG. Consider a topological sort of $H$. As $3$ cannot be performed, if $u$ precedes $v$ in the topological sort, there is a path from $u$ to $v$. Start at the initial vertex in the sort and keep moving forward until we find a vertex which has more than one outgoing edges (if each vertex has only one outgoing, then it is a line graph). Let $u$ have edges to $v$ and $w$ and let $v$ precede $w$. Then there is path from $v$ to $w$, which gives a path from $u$ to $w$ that doesn't include $u \rightarrow w$, a contradiction as operation $2$ can be performed here.

c. As deleting edges will not alter DAG property, we only need to check $3$. A cycle is formed only when we add an edge $u \rightarrow v$, when there was a path from $v$ to $u$ already. As $3$ doesn't add such edges, DAG is maintained.

d. Let $H$ be obtained from $G$ by a single operation. We show that any topological sort of $H$ is also valid for $G$ (note that the converse need not be true). For this we need to show that if there was a path from $u$ to $v$ in $G$, then there is path from $u$ to $v$ in $H$ too. Some path can be broken only when we are removing edges. So clearly operation $3$ will not cause any problem here. Also, in $2$, we are only removing those edges $u \rightarrow v$ where there is already a path from $u$ to $v$. So for any path from $w$ to $z$, containing that edge, we can just replace that edge by the path from $u$ to $v$, maintaining a path from $w$ to $z$ in $H$. And $G$ is DAG, so $1$ never happens.

e. First observe how each of $s$, $e$ and $p$ change with each operation. With operation $1$, $s$ reduces by at least $1$, $e$ reduces by $1$ and $p$ can decrease by close to $n^2$ (almost all paths might be broken). With $2$, $s$ might reduce by $1$ (not necessary though), $e$ reduces by $1$ and $p$ is unchanged. With $3$, $s$ doesn't change, $e$ increases by $1$ and $p$ increases by at least $1$. Notice that as we are going towards line graph, we are trying to reduce number of edges ($e$), remove cycles ($s$) while increasing $p$. So in $as+bp+de+c$, we expect $a$ and $d$ to be positive and $b$ to be negative. The worst case changes in $s,e,p$ for each operation are

$$ \begin{array}{cccc} & s & e & p \\ 1. & -1 & -1 & -n^2 \\ 2. & 0 & -1 & 0 \\ 3. & 0 & 1 & 1 \end{array} $$

As $s$ never increases, we can make $a$ as large as we want. As we can scale $a,b,d$ by a constant, lets keep $d=1$. With these observations we can get one possible set of values for $a,b,d$ as $2n^2$, $-2$ and $1$ respectively. And pick $c$ as negative of the value at line graph.
> 2 votes

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


# Question
Title: Difference between the languages accepted by two DFAs with different initial state/accepting states?
*Recently, I asked a question on Math SE. No response yet. This question is related to that question, but more technical details toward computer science.*

Given two DFAs $A = (Q, \Sigma, \delta, q\_1, F\_1)$ and $B = (Q, \Sigma, \delta, q\_2, F\_2)$ where the set of states, the input alphabet and the transition function of $A$ and $B$ are the same, the initial states and the final(accepting) states could be different. Let $L\_1$ and $L\_2$ be the languages accepted by $A$ and $B$, respectively.

There are four cases:

1. $q\_1 = q\_2$ and $F\_1 = F\_2$.
2. $q\_1 \neq q\_2$ and $F\_1 = F\_2$.
3. $q\_1 = q\_2$ and $F\_1 \neq F\_2$.
4. $q\_1 \neq q\_2$ and $F\_1 \neq F\_2$.

My question is

> > What are the differences between $L\_1$ and $L\_2$ in cases 2, 3 and 4?

I have a more specific question along this line,

The transition monoid of an automaton is the set of all functions on the set of states induced by input strings. See the page for more details. The transition monoid can be regarded as a monoid acting on the set of states. See this Wiki page for more details.

In many literatures, an automaton is called strongly connected when the monoid action is transitive, i.e. there is always at least one transition (input string) from one state to another state.

> > If $A$ and $B$ are strongly connected automata, what are the differences between $L\_1$ and $L\_2$ in cases 2, 3 and 4 above?

Any literatures discussing these issues in details?

I have searched many books and articles and found nothing helpful so far. I believe I don't have the appropriate key words yet. Thus I am seeking help. Any pointers/references will be appreciated very much.

# Answer
> 8 votes
Since $A,B$ are strongly connected, then if $q\_1\neq q\_2$, there exist words $p\_1,p\_2$ such that $\delta(q\_1,p\_1)=q\_2$ and $\delta(q\_2,p\_2)=q\_1$.

Consider case 2, then $w\in L(A)$ iff $p\_2w\in L(B)$, and $x\in L(B)$ iff $p\_1 x\in L(A)$. So you can add a prefix to switch between languages.

Consider case 3, then again - by strong connectivity there at most $|F\_1|$ words $s\_1,...,s\_k$ such that for every $q\_i\in F\_1$ you have that $\delta(q\_i,s\_i)\in F\_2$, and similarly for the other direction (from $B$ to $A$).

Thus, you can compose suffixes to switch between languages.

Combining these you can characterize the differences using prefixes and suffixes. For example, in case 4, $w\in L(B)$ iff $p\_1 w s\_i$ in $L(A)$ for some $s\_i$ in a predetermined finite set.

In fact, you can even say something interesting about these words: define $C$ to be the DFA where $q\_1$ is the initial state and $q\_2$ is the final state, then in case 2 you have $L(B)=L(C)\cdot L(A)$ (and similarly for the other direction).

As for the suffixes, things are more involved, since you cannot predetermine in which final state you will end. I'm not sure you can write this as a concatenation, but you can write $L(B)=\bigcup\_{q\in F\_1}L(A\_q)\cdot L(E\_q)$ where $A\_q$ is the DFA obtained from $A$ be setting $F=\\{q\\}$, and $E\_q$ is a DFA that starts in $q$ with final states $F\_2$.

For case 4 you can combine the two.

You may be concerned that this is not a real answer, but rather just a characterization of properties using words rather than states, but this is a typical answer in this field (similarly to the Myhill-Nerode theorem).

---
Tags: formal-languages, reference-request, finite-automata
---


title: Minimal-envy land division

text:
# Question
Title: Minimal-envy land division
There is a land divided to $D$ districts.

There are $C$ citizens.

We want to divide the land to the citizens, such that each citizen receives a single land-plot in a single district.

Each citizen prefers certain districts, however, the preference also depends on the size of plot. For example, Johnny prefers a plot of 1 dunam in the North to a plot of the 1 dunam in the South, however, he also prefers a plot of 1 dunam in the South to a plot of 0.5 dunams in the North.

Ideally, we would like to divide the land in an envy-free manner, such that no citizen thinks that the plot given to another citizen is better (according to his subjective preferences) than the plot given to him.

However, this is not always possible. For example, suppose there are 2 districts (North and South), each of size 1 dunam, and 3 citizens, all have the same preferences as Johnny. If two of them get a plot in the North and the third gets a plot in the South, then the first two get only 0.5 dunam each, and so they envy the third who gets 1 dunam. The other divisions are even worse (In the singular case where all citizens get 1/3 dunam in the North and the South remains empty, assume that it is invaded by a fourth citizen, so that all 3 citizens now envy the invader).

So, I am looking for a procedure that will minimize the envy - whatever that means.

Note that, in contrast to the standard envy-free cake-division algorithms, I am not interested in geometric cuts of the land - the division of land to districts is pre-determined, and each person can get a plot in only one district.

# Answer
> 1 votes
If the number of citizens is large enough, such that the effect of one citizen changing his/her selection is negligible, then an envy-free division is equal to a Nash equilibrium in a congestion game.

Specifically, Igal Milchtaich's papers are relevant to this problem.

Additionally, Yonatan Aumann and Yair Dombb define several quantitative measures of unfairness: alpha-unproportionality, alpha-envy and alpha-inequitability, which may also be relevant.

---
Tags: reference-request, game-theory
---


title: How to reduce from subset-sum problem?

text:
# Question
Title: How to reduce from subset-sum problem?
I have this problem which is described as follows:

Input: You are given a multi-set $M$ (a set that can contain duplicates), and two numbers $P$ and $T$. $M = {(x\_1,y\_1), (x\_2,y\_2), ..., (x\_n,y\_n)}$. Each $x$ and $y$ is an integer $\>= 0$. $P$ in an integer $\>= 0$. $T$ is an integer $\> 0$.

Question: Is there a subset $G$ of $M$, such that the sum of every $x$ value of $G$ is $\> P$ and the sum of every $y$ value of $G$ is $\< T$? (Note: You are basically taking from $M$. For example: if $M$ has two $(1,1)$'s then $G$ can contain at most two $(1, 1)$'s)

I want to reduce it to from the subset sum problem, but I am not sure how because there's two conditions to solve for...

Can anyone help with this problem?

# Answer
> 2 votes
Suppose that you have an instance of SUBSET SUM:

$0 \leq x\_1, x\_2, ..., x\_n$ and an integer $0 \leq t$

You must find $b\_i \in \\{0,1\\}$ such that $b\_1\*x\_1+b\_2\*x\_2+...+b\_n\*x\_n = t$

Which is equivalent to:
$b\_1\*x\_1+b\_2\*x\_2+...+b\_n\*x\_n \geq t$ AND $b\_1\*x\_1+b\_2\*x\_2+...+b\_n\*x\_n \leq t$

$b\_1\*x\_1+b\_2\*x\_2+...+b\_n\*x\_n \> t-1$ AND $b\_1\*x\_1+b\_2\*x\_2+...+b\_n\*x\_n \< t+1$

pick $P=t-1$, $T=t+1$, $M = \\{ (x1,x1),....,(x\_n,x\_n)\\}$

# Answer
> 1 votes
I think to be the same problem as with the sum of the series.
So, for example, if there is a set $G\_1$, such that the sum of all x \> P ($G\_1=\\{(x,y): \sum{x} \> P\\}$) and then a set of $G\_2$ such that the sum of all y \< T ($G\_2=\\{(x,y): \sum{y} \< T\\}$), then i think the set of G is the intersection of these two sets ($G = {G\_1\bigcap{G\_2}}$). These sets can be more, depending on the sum of the many ways to create.
And if it depends on which element is to be taken, it should be a set of sets such that if $ G = {G\_1\bigcap{G\_2}} = {(x\_1, y\_1),(x\_2, y\_2),...: (x\_1, y\_1)\space contained\space k\_1 times, (x\_1, y\_1)\space contained\space k\_2\space times,...}$, then you can create $k\_1k\_2k\_3...$ sets.
I think this depends on the specific need for the processing of the result(s).
If $M=\\{(1, 1), (1,1)\\}$, and $P=1$, $T=3$ then $G\_1=\\{(x,y): \sum{x} \> 1\\} = M$, $G\_2=\\{(x,y): \sum{y} \< 3\\} = M$ and $G = G\_1\bigcap{G\_2} = M$.
If $M=\\{(1, 1), (1,1)\\}$, and $P=1$, $T=2$ then $G\_1=\\{(x,y): \sum{x} \> 1\\} = M$, $G\_2=\\{(x,y): \sum{y} \< 2\\} = {(1,1)}$ and $G = G\_1\bigcap{G\_2} = {(1,1)}$ and is irrelevant if $G$ contains first or second pair.

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


# Question
Title: Get the running time of forest disjoint sets
If you have a forest implementation of disjoint sets, and have the union by weight/rank heuristic where you append the smaller one. Then why is the worst case running time Θ(m log n)? (m is the number of disjoint sets and n is the number of Make Set operations.)

# Answer
> 7 votes
You've asked two questions:

* Why is the tree height Θ(log n)?
* Why is the runtime Θ(m log n)?

This answer addresses both questions. I'll start off with a review of the ranks of the different trees to go over some basics, then discuss these time bounds.

---

One trick that might be useful here is to think of the minimum number of nodes that can be in a tree of height n. Once we have that insight, we can try to relate the maximum runtime to the maximum height of any tree in the forest.

When we initially create all of the trees, they each have height 0 and have a total of 1 node in them. Now, suppose we want to create a tree of height 1. The only way to do that would be to merge together two trees of height 0 to form a new tree of height 1. This would have a total of 2 nodes in it, and that's the minimum number of nodes possible.

Next, suppose we want to create a tree of height 2. To do that, we have to merge together two trees of height 1. Each of those trees has a minimum of 2 nodes in them, so the minimum number of nodes possible in a tree of height 2 would be 4.

To make a tree of height 3, we need to merge two trees of height 2, each of which has at least 4 nodes. This means that we would end up with eight nodes in the tree.

If we look so far, we see this pattern:

* Height 0: At least 1 node.
* Height 1: At least 2 nodes.
* Height 2: At least 4 nodes.
* Height 3: At least 8 nodes.

It looks like a tree of height n will have at least 2n nodes in it. This makes intuitive sense - the only way to make a tree of height n + 1 is to merge together two trees of height n, so the minimum number of nodes in a tree of height n + 1 should be at least double the number of nodes in a tree of height n.

---

So now let's suppose we do a series of n different union operations to link trees together. What is the largest possible tree we can make?

Suppose that we want to make a tree of height k. In order to do that, we first need to make two trees of height k - 1. Each of those trees are formed from two trees of height k - 2 each, and those trees are formed from two trees of height k - 3 each, etc. Eventually, we bottom out at trees of height 0.

If we work out a recurrence relation, we get the following expression for the total number of union operations required to get at tree of height k:

* U(0) = 0
* U(k + 1) = 2U(k) + 1

If we expand out the terms in this recurrence, we get

* U(0) = 0
* U(1) = 1
* U(2) = 3
* U(3) = 7
* U(4) = 15
* ...
* U(k) = 2k \- 1

In other words, if we want to get to a tree of height k, we need to do 2k \- 1 link operations. This means that if we do a total of n union operations, the maximum tree height we can possibly make has height Θ(log n).

This explains the runtime bound you were curious about. Creating the disjoint set forest takes time O(m), where m is the number of elements. Each union operation requires us to walk up to the root of a tree whose height is at most Θ(log n), so if we do a total of n of these, the overall runtime is at worst Θ(m + n log n).

Note that this is different from the bound you've proposed. However, if you make the assumption that m = Θ(n) (that is, you do about the same number of union operations as there are nodes in the graph), then we get that Θ(m + n log n) = Θ(n + n log n) = Θ(n log n) = Θ(m log n), which matches the bound you've described.

Hope this helps!

---
Tags: data-structures
---


title: Relationship between L and PSPACE

text:
# Question
Title: Relationship between L and PSPACE
I have a question have to answer, so that, if anyone have the answer, please help me.

The problem is: Give a self-contained proof that $\mathsf{L} \neq \mathsf{PSPACE}$ where:

$\qquad \mathsf{L} = \\{ L \mid L \text{ is a language decidable in logarithmic space} \\}$ and

$\qquad \mathsf{PSPACE} = \\{ L \mid L \text{ is a language decidable in polynomial space}\\}$.

# Answer
> 2 votes
You might start with wikipedia: Space hierarchy theorem.

---
Tags: complexity-theory, space-complexity
---


title: Synchronization using serialization

text:
# Question
Title: Synchronization using serialization
How can someone synchronize two or more threads using serialization? According to my professor's slides and code assignments you can use serialization to solve the synchronization problem. (He doesn't explain what serialization is).

I tried to do my research but serialization means that you put data in a specific order. I would understand that it means the same thing in this case (Running threads in a specific order). But what I most confused about is the syntax of the question. My question is:

Does serialization mean synchronization? How would one synchronize threads using serialization?

# Answer
> 3 votes
Two or more threads executing *concurrently* require synchronization if and only if at least one of the threads accesses and modifies one or more variables (write access) accessed by the remaining threads (either read or write access). Therefore, if all of the threads access the same set of variables only for reading their values (read access), no synchronization is needed. You probably know that the access to variables by multiple threads when at least one of them writes at least one of the variables, must happen in a so-called *critical section* (or critical region) of code. You then synchronize the access by providing *mutual exclusion* using for instance a Posix mutex lock. This permits concurrent execution of multiple threads, so that the execution preserves correctness when updating one or more of the variables involved.

Of course, concurrent execution of multiple threads is the most efficient way of writing code in general. However, you may also imagine a different execution, in which the operations associated to each thread are executed sequentially and not concurrently, one after the other, in an order that is *strictly equivalent* to a concurrent, correct execution. This is called *serialization of execution*. What does it mean "strictly equivalent" ? Serialization must provide as a requirement exactly the same results that will be provided by a concurrent, correct execution. Note that there are multiple possible concurrent and correct executions, but the outcome must be one and only one.

Now, do you really want to use serialization to synchronize your threads ? The answer is no, because a serialized execution is in general slower than a concurrent execution (obvious, since execution is sequential and not concurrent). In practice, serialization just gives you a *criterion* for correctness. You want your threads to execute concurrently, for performance reasons, however, you must ensure that the outcome is correct independently of the actual concurrent execution that took place.

As an example imagine two threads accessing a variable which is the amount of money you have deposited in your bank. If both threads just want to read that amount of money, no issue arises. However, if one or both the threads want to modify that value, a problem arises and you need to synchronize the access. For instance, one thread may be depositing money to your account (you in your bank), and the other thread ma be withdrawing money from your account (your wife from an ATM). In these cases, access to the variable holding the amount of money must be synchronized. Serialization in this case is simple: you must either first withdraw the money and then add the money, or, vice-versa, you first add the money to your bank account and then withdraw the money. In both cases, serialization provides the correct outcome. To grant a correct outcome in the case of a concurrent execution, you must instead protect the variable using a mutex lock, so that access to the variable is mutually exclusive for both the threads. Otherwise, the value of the variable when accessed from both threads without proper synchronization is actually undefined, which is very bad for your money! You may, for example loose part or all of of your money.

Another type of synchronization is not related to mutual exclusion. Imagine, for instance, that one thread can execute its operations only after another thread has completed. Another example: a thread can execute only when a specific condition is true, and this condition depends on another thread (this includes the previous example, but is a more general requirement, based on the evaluation of a predicate). For instance, you may synchronize threads in this way by using Posix mutex locks and condition variables.

Serialization has been thoroughly studied in the context of database transactions. A *serialized schedule* provides a criterion for correctness of execution of concurrent transactions in databases, and there are protocols that ensure proper synchronization (e.g., two-phase locking). But the concept applies equally well to threads as well.

---
Tags: concurrency, synchronization
---


title: Faster Algorithm for Computing Norm

text:
# Question
Title: Faster Algorithm for Computing Norm
Can anyone suggest an algorithm faster than $\Theta(n^{2})$ for computing the following function:

$$||n||:=\frac{1}{\max\\{k \in \mathbb{N}: 1|n, 2|n,\ldots,k|n\\}}$$

# Answer
> 1 votes
Store a list of all "factorials" (least common multiplies of $\\{1,\ldots,k\\}$) and use binary search. That reduces the number of divisions in the worst case. If the numbers $n$ you are getting are "random" then you might want to start with smaller trial divisions, or perhaps with an exponentially growing $k$, i.e. try $1,2,4,8,\ldots$ until you find some $k$ for which the LCM does not divide $n$, then take it from there using binary search.

By the way, since the LCM grows exponentially, even your algorithm only requires $\log n$ divisions. Each division takes time $\tilde{O}(n)$, so in total both your algorithm and mine are $\tilde{O}(n)$.

---
Tags: algorithms, discrete-mathematics, number-theory
---


# Question
Title: Destination-based vs source-based routing
I understand that destination-based routing builds the "route" from the destination backwards to the source (e.g. if using a spanning tree, then the tree is routed at the destination). With source-based routing the opposite is true: the route is build from the source onwards towards the destination.

However I don't understand the practical difference. How does it make a difference if I base my decision on the source or on the destination. Say, a shortest path algorithm such as Dijkstra's should give the same result regardless?

Could someone explain?

# Answer
Destination-based routing is the typical, most common type of routing. For this, each message that we send contains the address of the destination and the forwarding decision process makes its forwarding decision solemnly based on this address (and independent of the original sender). i.e. We don't care about who sent the message, only about where it is supposed to go.

So, when constructing a routes, one thing we can do is root a spanning tree at the destination. This creates a path from all possible sources to that destination. This is called a "sink tree".

Source-based routing is the reverse of destination-based routing. The decision process is based on the source address. So, when sending a message, we only include the address of the sender (and not of the destination). The decision on where to forward the message is based on this source address. This means that the source could be sending the message to any host (we don't know exactly who). Therefore we create a spanning tree routed at the source (this is known as a "delivery tree") and the message is thus sent to every child in this tree.

Source-based routing is only really useful for doing some kind of broadcast / multicast (e.g. consider a delivery tree when building a multicast group).
> 1 votes

---
Tags: algorithms, distributed-systems, shortest-path, routing
---


# Question
Title: Why is this true: “There are countably many Turing Machines”
It is said that there are uncountably many languages but only countably many Turing Machines. Could someone make this clear to me? And this doesn't mean that the set of TM is finite, yes?

# Answer
A quick informal answer:

* a Turing Machine (states, transitions, ecc.) can be encoded using a string of $0$'s and $1$'s;
* so you can pick all the binary strings in lexicographic order (0,1,00,01,10,11,000,001,...) and *enumerate* the Turing machines (i.e. build a one to one corrispondence between natural numbers and Turing machines) repeating the following steps:

1) start with $i=1$, $m=1$
2) generate the next binary string $s\_i$
in lexicographic order
3.1) if $s\_i$ is a valid encoding of a Turing machine then output $s\_i$ as the $m$-th Turing machine and set $m = m+1$;
3.2) if $s\_i$ is not a valid encoding of a Turing machine then ignore it
4) set $i = i+1$ and goto step 2

In this way *each natural number* ($m= 1,2,3,...$) corresponds to a Turing machine, and *each Turing machine* has a corresponding $m$, because you scan all possible binary strings. So the set of Turing machines is countable.

On the other side consider all possible strings $S$ over alphabet $\\{0,1\\}$:
$S =\\{0,1\\}^\* = \\{\epsilon,0,1,00,01,10,11,000,001,...\\}$

A language $L$ is a subset (possible infinite) of $S$: $L \subseteq S$.

So the set of all languages is exactly the power set of $S$:
$2^S = \\{ \\{\epsilon\\}, \\{0\\}, \\{1\\}, \\{0,1\\}, ... \\}$

But the power set of a countably infinite set is uncountable (it can be easily proved using the diagonalization method).

You can also apply the diagonalization method directly to the set of languages: suppose that the languages are countable, then we can arrange all of them in a table in which every (infinte) row $i$ represents the elements of the language $L\_i$ and the columns represent the string over the alphabet $\\{0,1\\}$ ($(i,j)=1$ if and only if string $j$ is in $L\_i$):

```
    0 1 00 01 10 11 ...
L1  0 0  1  0  1  0
L2  1 1  0  1  0  1
L3  0 1  0  0  1  0
...

```

Then define a new language changing the "membership flag" of the elements $(i,i)$:

```
    0  1 00 01 10 11 ...
L1 [1] 0  1  0  1  0
L2  1 [0] 0  1  0  1
L3  0  1 [1] 0  1  0
...

```

The new language $L\_{new} = \\{0,00,...\\}$ built from the modified diagonal is different from every language $L\_i$: $0 \notin L\_1, 0 \in L\_{new}$, $1 \in L\_2, 1 \notin L\_{new}$, $00 \notin L\_3, 00 \in L\_{new}$, .... But this is a contraddiction because by hypothesis the above table should be an enumeration of all languages.
> 21 votes

# Answer
A Turing machine always has a finite description. So there are finite number of states, transitions and tape symbols for each Turing machine. We can map these to a canonical representation, e.g. a string, which will be finite in length.

The set of all finite length strings is still countable, and the set of valid Turing machine string literals is a subset of all finite length strings.
> 3 votes

# Answer
Countable means finite or can be counted (can be put in one-to-one correspondence with the set of natural numbers $\mathbb N$). Uncountable means not countable (not finite and can't be put in one-to-one correspondence with $\mathbb N$).

A language is a set of strings (let's restrict ourselves to the alphabet $\Sigma=\\{0,1\\}$). The set $\Sigma^\*$ is countable so the set of all languages is $2^{\Sigma^\*}$ and it's uncountable. The previous result is a know theorem (if $S$ is countably infinite, then $2^S$ is uncountable)$^1$. This proves that the set of languages is uncountable.

I'll let somebody else answer the other part.

---

$^1$ I can write a proof if you want.
> 1 votes

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


# Question
Title: Unable to understand control flow in KMP algorithm
I am facing problem in understanding the KMP algorithm as given in the book "Introduction to Algorithm" by Cormen et. al. (Chapter 32):

With respect to the above algorithm, I have following question:

1. In both the algorithms, where exactly (which line number?) while loops, if and for loop ends? It is difficult to visualize the functioning of the algorithm without knowing the 'end' for each loop and conditional statements.
2. On line number 6 in KMP-MATCHER() and COMPUTE-PREFIX-FUNCTION(), what is the need of checking q\>0 and k\>0, when we know q and k will always be 0 or positive. Or do the authors want to test q!=0, k!=0?
3. If q=0 and i=1 in KMP-MATCHER(), from 6 to 10 which line will be executed (If I get answer to 1- above then I can find this)

# Answer
1. As explained in the comments, indentation marks code blocks. It is a standard way to denote them. `while` of line 6, repeats line 7, but has nothing to do with the `if` on line 8.
2. Indeed it only matters whether `q` and `k` are not zero.
> 2 votes

---
Tags: algorithms, terminology, strings
---


# Question
Title: How to analyze the Steiner tree problem?
I have a problem where I am supposed to analyze the `Steiner tree problem` by doing the following 3 steps.

1) Look up what the Steiner tree problem is.

2) Find a polynomial time reduction to it from one of these 8 known NP-complete problems:

* 3-col
* subset-sum
* clique
* hampath
* Uhampath
* sat
* 3-sat
* vertex-cover.

3) Prove that it is NP-complete.

---

My first problem is that I don't understand what the Steiner tree problem is. I can't find the problem anywhere. Wikipedia has a page on it, but doesn't really describe it in simple terms.

Can anyone help me out on this, and also give me hints for number 1, 2 and 3?

# Answer
> 6 votes
Short answer: You are given a graph with some special vertices, and are asked to connected them using as few (or cheap) edges as possible. By connecting them, we mean that you will *use* only those edges.

More formally, you are given a graph $G = (V,E)$ and a set $S \subseteq V$ of vertices. These vertices are often refered to as *terminals*. You are also given some number $k \in \mathbb{N}$.

I ask you now: Can you find a set of edges $F \subseteq E$ such that (a) $|F| \leq k$ and (b) in the graph $G' = (V, F)$, $S$ belongs to the same connected component.

Now, if such a set $F$ exists and you take a subset minimal $F'$, the graph $G' = (V,F')$ is a forest, and the component containing $S$ is called a Steiner tree.

This is the *unweighted* decision version. It is not hard to come up with the optimization or weighted version. The weights are on the edges.

Edit: When it comes to your next question, I would go for Vertex Cover. Hint: Subdivide every edge and make the new vertices the terminals. Then the number of edges in a Steiner tree is some function of the $E$ and the number of vertices in the vertex cover in the original graph.

And to show that the problem is *in* NP should be quite easy.

---
Tags: complexity-theory, graphs, np-complete, reductions, trees
---


# Question
Title: Minimize the total execution time of jobs executed by 3 processors in sequence
There are 3 processors: $P\_1$, $P\_2$, $P\_3$. $P\_1$ can execute only one job while the other two can execute any number of jobs in parallel.

Each job consists of 3 parts, and each part is processed by their respective processor (eg. part 1 by $P\_1$). Furthermore part 2 can be executed only after $P\_1$ finishes executing part 1, and part 3 can be executed only after $P\_2$ finishes executing part 2.

Suppose there are $n$ jobs, and again each job has 3 parts. The processor $P\_k$ takes time $T\_{i\\,k}$ to complete part $k$ of job $i$. Can anyone suggest an algorithm that takes set of $n$ jobs and determines the the jobs should be processed so that the total time is minimized?

This is a homework problem and I don't know where ti start

# Answer
Well since no one else is giving an answer, here goes:

Assume the jobs are represented as $J=\\{x\_1,\ldots,x\_n\\}$

Since $P\_1$ must process only one job at a time, it doesn't matter which order the jobs are processed, the time taken by $P\_1$ is always the same, $\sum\_{i=1}^n t\_{i,1}$, each job's 3 parts are represented as $(t\_{i,1},t\_{i,2},t\_{i,3})$. So to minimize the total time, we only need to consider the order that affects $P\_2$ and $P\_3$. Since both of them can execute any number of jobs in parallel, to minimize their time we want the jobs that need longer time to be processed first. So you arrange the jobs in decreasing order of $t\_{i,2}+t\_{i,3}$. Now to prove that this is optimal.

We need to show that in any optimal solution to the problem, if the ordering of the jobs is not the same as the ordering described above, we can convert it to our ordering without increasing the total time.

Let $C$ be an optimal ordering. Assume $C$ does not have the same ordering as that given by the algorithm. Which means, there exists jobs $x\_i$ and $x\_j$ such that $t\_{i,2}+t\_{i,3}\<t\_{j,2}+t\_{j,3}$ and $x\_i$ is listed immediately before $x\_j$ in $C$, call such a pair of jobs an inversion. Consider the ordering $C'$ obtained from $C$ by swapping the position of $x\_i$ and $x\_j$. Thus $x\_j$ would appear finish earlier here.

We can see that in $C'$, $P\_2$ starts on job $x\_i$ exactly when $P\_2$ starts on job $x\_j$ in $C$. This is independent of how long the first parts of $x\_i$ and $x\_j$ require. Since $t\_{i,2}+t\_{i,3}\<t\_{j,2}+t\_{j,3}$, it's clear that in $C'$ job $x\_i$ finishes sooner than job $x\_j$ in $C$. So the total time taken by $C'$ is no larger than the time taken by $C$.

Repeat the above till all inversions are removed from $C$ and we have an ordering which is the same as that of the algorithm. Thus, the ordering returned by the algorithm is optimal.

Running Time: It's clear that the running time is $O(n\log n)$, I don't think I need to elaborate on that.

Hope this helps! Cheers!
> 2 votes

---
Tags: algorithms, scheduling
---


# Question
Title: Polynomial time reductions using binary search
There are many NP-complete decision problems that ask the question whether it holds for the optimal value that OPT=m (say bin packing asking whether all items of given sizes can fit into m bins of a given size). Now, I am interested in the problem whether OPT\>m. Is this a decision problem or an optimization problem? It seems to be that it lies in NP (a NTM can guess a solution and it can be verified in polynomial time that the bound is met). Is it also NP-complete?

I would have said yes, because having a polynomial algorithm, we could find a solution in polynomial time for the original problem (asking whether OPT=m) by using binary search and repeatedly using the polynomial algorithm to test if OPT larger than some bound.

However when I try to construct a proper solution, I always see the complication that the oracle (that asks whether OPT\>m') would need to be queried more than once, and this is forbidden in the polynomial time Karp reduction.

Any solutions or remarks? Would it make a difference if I ask whether OPT\>=m?

Thanks in advance

# Answer
> 1 votes
**Is OPT = m?** is a coNP decision problem. A "no" answer has a certificate verifiable in polynomial time, the certificate being a valid bin packing that uses fewer than $m$ bins.

The same is true for the question **Is OPT \> m?**. There is no polynomial-time verifiable certificate for the "yes" answer to either of these questions unless NP = coNP.

**Is OPT \< m?** is an NP decision problem. A "yes" answer has a certificate verifiable in polynomial time, the certificate being a valid bin packing that uses fewer than $m$ bins.

# Answer
> 1 votes
One way to show hardness of the decision version of an optimization problem (i.e., $OPT \geq m'$) given that the standard decision version (i.e., $OPT = m$) is NP-complete is by using Turing reductions in both directions.

Therefore, you need to do two things:

(1) Show that if you have a poly-time oracle that can solve the $OPT = m$ problem, then with a polynomial number of calls to it, you can solve the $OPT \geq m'$ problem. This is usually the non-trivial part of these reductions.

(2) Show that if you have a poly-time oracle that can solve the $OPT \geq m'$ problem, then with a polynomial number of calls to it, you can solve the $OPT = m$ problem. This is trivial using binary search in most cases.

**Just a side note:** Of course it is not always true that if $OPT=m$ is hard, that $OPT \geq m'$ is also hard. One simple example is the subset product problem -- it is hard to tell if there is a subset with product $= T$, but easy to tell if there is a subset with product $\geq T'$ (just multiply all terms together, this is the MAX product you can get).

However, if you state the optimization problem as finding the largest product $T'$ that is smaller than $T$, the problem is hard again. So, how you state your optimization problem is very important.

---
Tags: complexity-theory, terminology, np-complete, optimization, decision-problem
---


# Question
Title: Find a vertex that is equidistant to a set of vertices?
I need help with the following problem:

> **Input:** An undirected, unweighted graph $G = (V,E)$ and a set of vertices $F \subseteq V$.
>
> **Question:** Find a vertex $v$ of $V$ such that the distance from each vertex of $F$ to $v$ is the same and all the distances are minimized? Return `None` if there is no such $v$.

The runtime should be $O(|V| + |E|)$.

My thoughts were to do a breadth-first search for each vertex in $F$, so for each vertex in $F$, you store all vertices with their distances, then find the intersection of all these.

Is there a better way?

# Answer
Starting with $i=0$ and going up, for every $f \in F$ consider a subset of $V$ containing points at the exact distance of $i$ from $f$. Look at intersection of all of those subsets. If you're lucky, as $i$ grows, you'll find this intersection non empty - those will be the solutions.

For the actual implementation, I'd suggest removing vertices closer than $i$ to any of $f$ at every iteration. To find intersection you could simply increment a counter on a vertex, whenever it is included in one of the subsets. When for some vertex `v.count = |F|`, you are done.

One way to implement it could be as follows

```
For each v in V, v.count = 0.

For each f in F,
    f.subset = {f},
    f.count = f.count + 1
    if f.count = |F|, return f.

While V is not empty,
    For each f in F,
        old_subset = f.subset,
        f.subset = the set of neighbors of vertices in old_subset,
                   (consider only vertices in V and not in old_subset)

        For each v in old_subset,
            if v.count == 1, remove v from V,
            else v.count = v.count - 1

        For each s in f.subset,
            s.count = s.count + 1
            if s.count = |F|, return s.

return "no such vertex"

```

While the running time of the above algorithm depends a lot on chosen graph representation, it can be as good as $O(|V| + |E|)$ assuming that you can find the neighbors of a vertex $v$ and remove it from the graph in $O(\deg(v))$ time. In that case, because $\sum\_{v \in V} \deg(v) = 2 |E|$, most of the cost of the algorithm is covered by the $|E|$ term.
> 5 votes

# Answer
Assume $n = |V|, m = |E|, k = |F|$. Solve the SSSP for all $v \in F$ and annotate nodes with the respective distances (time $\Theta(k(n + m))$). Iterate over all nodes and find one all annotations of which are the same and minimal among all candidates (time $\Theta(nk)$).

This can be sped up by using depth-first search to solve the SSSP and executing all $k$ runs in parallel and in phases (by distance), observing the following rules.

* In any given phase, if we find a node in some runs but not in others, remove them from consideration.
* In any given phase, if a node is found in all runs (simultaneously), return it and stop.

Now the runtime depends on the minimal distance to be found and the density of the graph.
> 5 votes

# Answer
One easy but most likely not most efficient approach is this:

1. Reorder the vertices such that all vertices in $F$ come first.
2. Use the Floyd-Warshall algorithm to compute the Matrix $M$ of all distances.
3. Look at all columns where the first $|F|$ entries contain the same value $k$ and choose the one with the minimal $k$.

The worst case runtime is in $\mathcal{O}(|V|^3)$, since it's dominated by the Floyd-Warschall algorithm.

---

Another algorithm:

1. Let $M$ be the adjacency matrix of $G$ (again with the vertices in $F$ first)
2. If $F=\\{v\\}$ return $v$, if $F=\emptyset$ return an arbitrary $v \in V$, now $|F|\>1$, so we know $v \notin F$.
3. Compute $M^i=MM^{i-1}$ and flag every $v \in V\setminus F$ s.t. some but not all of the first $F$ rows are nonzero (i.e. there is a path of length $i$). Such a vertex can't be $v$ since at least 2 distances differ.
4. Stop if you found a non flagged vertex $v$ that has all entries in the first $|F|$ rows nonzero and return $v$ or if all vertices in $V\setminus F$ are flagged and return "no such $v$ exists".

Note that we don't need the actual $M^i$ so we can speed up the expensive matrix multiplication to some extent.
> 2 votes

---
Tags: algorithms, graphs, search-algorithms, shortest-path
---