# Question
Title: Finding the interior of a connected graph
I'm designing software that produces images such as the following:

Regions of interest are circumscribed by red pixels. I am interested in extracting the fully-enclosed pixel regions. Ultimately, I would like to calculate the approximate center, width, and height of the regions. Ideally, I would even like to eliminate interior loops--that is, only preserve the largest enclosing body of a region (a "region" being an isolated pixel group).

I have experience implementing search algorithms, so my first instinct is to traverse the edges until a loop is detected (arrival at the start); however, I recognize the potential for multiple solutions--alternate, valid loop possibilities--and then I would require a way to decide between them. Perhaps the one that is longer or encloses the greatest number of pixels.

# Answer
If you are given the red pixels, try decomposing the pixels into strongly connected components (SCC), where two pixels are in the same SCC if they are adjacent and neither one is red. Then each SCC represents a region. This is a standard technique in computer vision. Another way to think about this: try using flood fill from each possible starting point.

If you're not given the red pixels: you have a blob finding / segmentation kind of problem. Try looking at existing methods for block detection. You should also look at the watershed algorithm for image segmentation. There are also methods based upon max flow (i.e., minimum graph cuts).

Doing some searches using these keywords will probably find you many more resources.
> 3 votes

---
Tags: algorithms, graphs
---


# Question
Title: Number of path with given length within an unrooted Tree
Given a Tree (without a root) function w : v -\> N and a number C - How can we count the number of verticies with distance between them equal to C.

I was thinking about some smart vertice numbering so we could use dynamic programing to do it but after some thinking it is no good.

I would be really thankful for any tips.

# Answer
Hint: divide-and-conquer. How many paths are there of length C in the left subtree of the root? How many in the right subtree? How many others not covered by either of those two cases?
> 1 votes

---
Tags: graphs, trees
---


# Question
Title: Paxos: Accepting Proposals With Different Values and Consensus in Paxos
I have a number of questions about Paxos which I can't answer in full confidence from reading the paper (Paxos Made Simple).

My questions are loosely based around the following quote:

> In Paxos, a value is chosen when a single proposal with that value has been accepted by a majority of the acceptors. However, we can allow for multiple proposals to be chosen, but we must guarantee that all chosen proposals have the same value.

The first property, P1, states:

> P1: An acceptor must accept the first proposal that it receives.

Therefore, if we have an proposer, which sends an prepare(n) statement to a majority of acceptors, this majority can always respond to a prepare request, and because this is the first proposal, the majority *must* accept this proposal.

However, in the case where multiple proposals are proposed at about the same time, it can be possible that no single value is accepted by a majority. For this reason, it is necessary for an acceptor to be able to accept multiple proposals.

**Question 1**: This means that an acceptor can accept a proposal with a value `v2` after it has accepted a proposal with value `v1`. Otherwise, I don't see how it can be guaranteed that a majority of acceptors accept proposals with the same value. Is this correct?

Now, if we look at P2B:

> If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v.

And then later:

> If the proposer receives the requested responses from a majority of the acceptors, then it can issue a proposal with number n and value v, where v is the value of the *highest-numbered proposal among the responses*...

**Question 2**: Does this mean that if a proposer proposes a value, v1, that is accepted by a majority, it is now impossible for the same proposer, or another proposer, to propose another value, v2? If they want to make a proposal, they must propose the same value, v1? The only way they could propose a different value would be to start a new instance of Paxos. The reason you would want to make a proposal with the same value as the chosen value is because the chosen value might not have been received by any of the learners. Is this correct?

**Question 3**: Can an acceptor respond to a proposer with a promise if consensus has already been reached?

**Question 4**: The promises guarantee that a majority of acceptors will always accept a value, because the proposer must receive a promise from the majority of the acceptors before it can send an proposal, correct?

# Answer
> **Question 1:** This means that an acceptor can accept a proposal with a value $v\_2$ after it has accepted a proposal with value $v\_1$. Otherwise, I don't see how it can be guaranteed that a majority of acceptors accept proposals with the same value. Is this correct?

Yes, it is possible for an acceptor to accept a proposal with number $n\_2$ and value $v\_2$ after it has accepted a proposal with number $n\_1$ and value $v\_1$. Consider the following scenario where there are two proposers $p\_1$ and $p\_2$ and three acceptors $a\_1, a\_2,$ and $a\_3$:

1. $p\_1$ proposes $\texttt{propose}(n\_1,\*)$ to $a\_1$ and $a\_2$.
2. both $a\_1$ and $a\_2$ respond to $p\_1$ with *(a)* a promise never again to accept a proposal numbered less than $n\_1$ and *(b)* no proposal because they have not accepted any ones.
3. $p\_1$ receives the two responses from $a\_1$ and $a\_2$. Now $p\_1$ is free to select its own value $v\_1$. $p\_1$ sends $\texttt{accept}(n\_1, v\_1)$ to $a\_1$ and $a\_2$.
4. $a\_1$ accepts $(n\_1, v\_1)$ *but* $a\_2$ does not (maybe this message to it has been lost; note that an acceptor can ignore any request without compromising safety).
5. $p\_2$ proposes $\texttt{propose}(n\_2, \*)$ to $a\_2$ and $a\_3$ ($n\_2 \> n\_1$).
6. Because, in 4, $a\_2$ does not accept $\texttt{accept}(n\_1,v\_1)$ from $p\_1$, both $a\_2$ and $a\_3$ respond to $p\_2$ with a promise never again to accept a proposal numbered less than $n\_2$.
7. $p\_2$ receives the two responses from $a\_2$ and $a\_3$ and is also free to select its own value $v\_2$. $p\_2$ sends $\texttt{accept}(n\_2, v\_2)$ to $a\_1$ and $a\_3$.
8. $a\_1$ can now accept the proposal $(n\_2, v\_2)$ from $p\_2$.

---

> **Question 2:** (1) Does this mean that if a proposer proposes a value, $v\_1$, that is accepted by a majority, it is now impossible for the same proposer, or another proposer, to propose another value, $v\_2$? (2) If they want to make a proposal, they must propose the same value, $v\_1$? (3) The only way they could propose a different value would be to start a new instance of Paxos. (4) The reason you would want to make a proposal with the same value as the chosen value is because the chosen value might not have been received by any of the learners. Is this correct?

For (1): yes; For (2), yes. The invariant $\texttt{P2B}$ in Paxos is the key to its correctness.

For (3): I think you have confused an **instance** of Paxos with a **round** in an *instance* of Paxos. They are two important concepts. We call a *round* the collection of all messages labeled with some particular proposal $n$. An *instance* of Paxos consists of multiple *rounds*, each round corresponding to a proposal with a different number. If you consider multiple *instances* of Paxos, please refer to Section 3 "Implementing a State Machine" in the paper. It is often called "multi-Paxos".

For (4): in page 6, it reads `"A proposer can make multiple proposals, so long as it follows the algorithm for each one. It can abandon a proposal in the middle of the protocol at any time"`. That is to say, as a proposer, you are free to make multiple proposals as you want, for no matter what reasons. However, a major reason would be to learn the value already chosen: at phase 2(a), you will have to select the value chosen, if any.

---

> **Question 3:** Can an acceptor respond to a proposer with a promise if consensus has already been reached?

Yes, it does no harm. Again, the invariant $\texttt{P2B}$ works.

---

> **Question 4:** The promises guarantee that a majority of acceptors will always accept a value, because the proposer must receive a promise from the majority of the acceptors before it can send a proposal, correct?

Are you discussing about the correctness of Paxos? Are you regarding the "promise mechanism" as the key to success? If so, you are *almost* right: however, it is hard to identify a single factor in Paxos. If it must be done, once again, it is the $\texttt{P2B}$ invariant.
> 3 votes

---
Tags: distributed-systems
---


# Question
Title: Why is Comb-sort (aka Dobosiewicz-sort) faster than Cocktail-sort (aka shake-sort)?
According to wikipedia, Cocktail-sort has an average performance of $O(n^2)$, whereas Comb-sort's average performance is $Ω(n^2/2^p)$, where $p$ is the number of increments.

There's no explanation given for this substantial difference between two similar algorithms, both variants of Bubble-sort. Can anyone help explain it?

# Answer
Sorting is all about removing inversions.

Combsort is much faster than cock-tail sort because it does more "long range" comparisons and exchanges; exchanging two out-of-order elements that are far apart will (on average) remove (a lot more) more inversions than exchanging two that are close together.

As for the formula you quote... well, Wikipedia's wrong. Combsort isn't *that* much faster. The formula you quote is a (very) weak *lower bound* on the average number of comparisons (try substituting p=2.log2(n) into the formula. Combsort can't possibly require only O(1) comparisons to perform the whole sort because... it's obviously had to do about pn, *before* the insertion sort phase, at the end of the sort, even begins).

\[I think that formula has been (mis)quoted on the Wikipedia Combsort page since something like 2008, and I don't think anyone bothered to point out, even on Wikipedia's Combsort talk page, that the paper being referenced gave it as a formula, only for a *lower bound*, before June 2013.\]

In *practice*, unless you are sorting billions of records, if you use increments that are relatively prime and have a growth ratio of 1.25 or so, Combsort will require (on average) about 3\*log2(n)\*n comparisons (and will generally run somewhere between 2 and 3 times slower than a quicksort or a mergesort, if you are sorting, say, integers).

You are unlikely to run into Combsort's (quadratic) worst case unless you deliberately engineer an input that will cause it.
> 2 votes

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


title: Consequences of $NP=coNP=BPP=RP$

text:
# Question
Title: Consequences of $NP=coNP=BPP=RP$
What is complexity theoretic implication of following possibilities - $NP=coNP=BPP=RP$ or $coNP\neq NP=BPP=RP$ (consensus is these seem impossible)?

# Answer
> 3 votes
Unless I'm missing something obvious (it is getting late here), the second isn't possible - $BPP = coBPP$, so $NP=BPP \rightarrow NP = coBPP \rightarrow NP = coNP$.

In the first case, some of the consequences would be:

* "Feasible" algorithms for $NP$-complete problems, for at least the randomised version of feasible.
* $PH \subseteq NP$
* Unless $P = NP$, adding randomness adds computational power.
* Strong pseudorandom number generators do not exist (nor do one way functions). (we would need $BPP = P$ for them to exist, but that would imply $P=NP$, in which case they don't).

# Answer
> 3 votes
Have a look at Impagliazzo's 5 worlds \[1\], especially Algorithmica. In Algorithmica, $\sf P = NP$, or some "moral equivalent" of that holds, like $\sf NP = RP$.

You might also be interested in a relevant question on CSTheory.

---

\[1\] Russell Impagliazzo. A Personal View of Average-Case Complexity. 1995 Complexity Conference.

---
Tags: complexity-theory
---


# Question
Title: Huffman code optimal substructure property
I am learning about Greedy Algorithms and we did an example on Huffman codes. To prove the correctness of our algorithm, we had to have the greedy choice property and the optimal substructure property.

Here is what my professor said about the optimal substructure property:

Let C be an alphabet and x and y characters with the lowest frequency.

Let C' = C-{x,y}U{z} where z.frequency = x.frequency + y.frequency

Let T' (a binary tree) be an optimal prefix code for C' She then drew these pictures

Let T be constructed from T' by replacing z with an internal node with children x and y. Then T is an optimal prefix code for C

And I don't really understand what/how this proves anything. All I see that she is doing is like..working backwards. First she replaced x and y with z, and now she is replacing z with x and y. What exactly is this showing? I'm really bad with proofs sometimes so I am just completely lost as to how this showed me anything about anything

# Answer
Your teacher are proving:

> **Lemma:** If $T'$ is optimal for $C' = C \setminus \\{ x, y \\} + \\{ z \\}$, then $T$ is optimal for $C$.

Once you have this lemma, you can prove the correctness of Huffman algorithm by mathematical induction on the cardinality of the alphabet $|C|$.

* **Base Case:** The base case of $|C| = 2$ is trivial.
* **Inductive Hypothesis:** Suppose Huffman algorithm is correct for any $|C| \< n$.
* **Inductive Step:** Consider the case of $|C| = n$. According to Huffman algorithm, you reduce the problem to constructing $T'$ on $C'$ where $|C'| = n -1$. By inductive hypothesis, $T'$ is optimal for $C'$. By the lemma above, $T$ is then optimal for $C$.
> 3 votes

---
Tags: greedy-algorithms
---


title: Applications of queues

text:
# Question
Title: Applications of queues
Let suppose a simple (FIFO) queue, where elements enter at a side and exit at the other side.

I know the classical use of queues in everyday life and computer networking. I would like to know more specific uses, for instance in distributed applications.

Are there client-server applications where we need to investigate elements of the queue which are not at its extreme sides ? (that is, elements which are not the first and the last of the queue).

Thank you.

# Answer
Here is an application of FIFOs in multiprocessor computers. A multiprocessor computer can be regarded as a distributed system.

To make a multiprocessor computer that correctly executes multiprocess programs, two requirements are given by Leslie Lamport \[1\]. The second one reads,

> *Requirement R2:* Memory requests from all processors issued to an individual memory module are serviced from a single **FIFO queue**. Issuing a memory request consists of entering the request on this queue.

---

For what it concerns applications of non-FIFO queues, I am confused about your requirement: Why do you use a queue if you don't need its features?

Anyway, is the priority queue an application in which we need to investigate elements of the queue which are not at its extreme sides?

---

\[1\] How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs. By Leslie Lamport. IEEE Transactions on Computers, 1979.
> 1 votes

---
Tags: dictionaries
---


# Question
Title: How to create DFA from regular expression without using NFA?
Objective is to create DFA from a regular expression and using "Regular exp\>NFA\>DFA conversion" is not an option. How should one go about doing that?

I asked this question to our professor but he told me that we can use intuition and kindly refused to provide any explanation. So I wanted to ask you.

"Regular exp\>NFA\>DFA conversion" is not an option because such a conversion takes a lot of time to convert a rather complex regular expression. For example, for a certain regex "regex\>NFA\>DFA" takes 1 hour for a human being. I need to convert regex to DFA in less than 30 minutes.

# Answer
Since you want "to convert regex to DFA in less than 30 minutes", I suppose you are working by hand on relatively small examples.

In this case you can use **Brzozowski's algorithm** $\[1\]$, which computes directly the Nerode automaton of a language (which is known to be equal to its minimal deterministic automaton). It is based on a direct computation of the derivatives and it also works for extended regular expressions allowing intersection and complementation. The drawback of this algorithm is that it requires to check the equivalence of the expressions computed along the way, an expensive process. But in practice, and for small examples, it is very efficient.

**Left quotients**. Let $L$ be a language of $A^\*$ and let $u$ be a word. Then $$ u^{-1}L = \\{v \in A^\* \mid uv \in L \\} $$ The language $u^{-1}L$ is called a *left quotient* (or *left derivative*) of $L$.

**Nerode automaton**. The *Nerode automaton* of $L$ is the deterministic automaton $\mathcal{A}(L) = (Q, A, \cdot, L, F)$ where $Q = \\{u^{-1}L \mid u \in A^\*\\}$, $F = \\{u^{-1}L \mid u \in L\\}$ and the transition function is defined, for each $a \in A$, by the formula $$ (u^{-1}L)\cdot a = a^{-1}(u^{-1}L)=(ua)^{-1}L $$ Beware of this rather abstract definition. Each state of $\mathcal{A}$ is a left quotient of $L$ by a word, and hence is a language of $A^\*$. The initial state is the language $L$, and the set of final states is the set of all left quotients of $L$ by a word of $L$.

**Brzozowski's algorithm**. Let $a, b$ be letters. One can compute the left quotients using the following formulas: \begin{align\*} a^{-1}1 &= 0 & a^{-1}b &= \begin{cases} 1 &\text{if $a = b$}\\ 0 &\text{if $a \not= b$}\\ \end{cases}\\ a^{-1}(L\_1 \cup L\_2) &= a^{-1}L\_1 \cup u^{-1}L\_2,& a^{-1}(L\_1 \setminus L\_2) &= a^{-1}L\_1 \setminus u^{-1}L\_2,\\ a^{-1}(L\_1 \cap L\_2) &= a^{-1}L\_1 \cap u^{-1}L\_2, & a^{-1}L^\* &= (a^{-1}L)L^\* \end{align\*} \begin{align\*} a^{-1}(L\_1L\_2) &= \begin{cases} (a^{-1}L\_1)L\_2 &\text{si $1 \notin L\_1$,}\\ (a^{-1}L\_1)L\_2 \cup a^{-1}L\_2 &\text{si $1 \in L\_1$}\\ \end{cases}\\ %\\v^{-1}(u^{-1}L) &= (uv)^{-1}L. \end{align\*}

**Example**. For $L = (a(ab)^\*)^\* \cup (ba)^\*$, we get successively: \begin{align\*} 1^{-1}L &= L=L\_1\\ a^{-1}L\_1 &=(ab)^\*(a(ab)^\*)^\*=L\_2\\ b^{-1}L\_1 &= a(ba)^\*=L\_3\\ a^{-1}L\_2 &= b(ab)^\*(a(ab)^\*)^\* \cup (ab)^\*(a(ab)^\*)^\*=bL\_2 \cup L\_2=L\_4\\ b^{-1}L\_2 &=\emptyset \\ a^{-1}L\_3 &=(ba)^\*=L\_5\\ b^{-1}L\_3 &=\emptyset \\ a^{-1}L\_4 &= a^{-1}(bL\_2 \cup L\_2)=a^{-1}L\_2=L\_4 \\ b^{-1}L\_4 &= b^{-1}(bL\_2 \cup L\_2)= L\_2\cup b^{-1}L\_2 = L\_2 \\ a^{-1}L\_5 &= \emptyset\\ b^{-1}L\_5 &=a(ba)^\*=L\_3 \end{align\*} which gives the following minimal automaton.

$\[1\]$ J. Brzozowski, Derivatives of Regular Expressions, J.ACM 11(4), 481–494, 1964.

**Edit**. (April 5, 2015) I just discovered that a similar question: What algorithms exist for construction a DFA that recognizes the language described by a given regex? was asked on cstheory. The answer partly addresses complexity issues.
> 21 votes

# Answer
J.-E. Pin provides the better answer in terms of formality and completeness, but I think there's something to be said for the "intuition" that your professor is hinting at.

In most of these cases, the easiest thing to do is to look at a regular expression, understand what language it's accepting, then use your creativity/cleverness to construct a DFA accepting that language.

There's no straightforward way to do this, other than the algorithms others have given, but here are some guidelines that might prove useful.

1. Ask yourself, could I write a program that accepts this RE using only boolean or very small integer variables? Then write that program, and convert it into a DFA where there's a state for every combination of values.
2. Look for parts of the regular expression that you know you can accept deterministically, where you know "If I see this, then I must be matching this part of the RE." There won't always be tons of these, but identifying these parts can show the parts that will be easy to make a DFA, so you can spend more time on the parts that really require non-determinism.
3. The subset construction for NFA-\>DFA isn't actually that complicated of an algorithm. So if this is an assignment, not an exam question, it might be faster to just code up an implementation, and let your program convert NFA to DFA. If you used your own code, there shouldn't be any plagarism issues.

Remember that no matter what you do, any technique will blow up exponentially in the worst case (unless you find a polynomial algorithm for this, in which case, congratulations, you've proved $P=NP=PSPACE$ and you're now a millionaire.)

Try to "look ahead," cut corners when you can use your intuition in places when the algorithm would require many steps but its result is clear.
> 2 votes

# Answer
Though this is not the correct way but it works most of the time.

**First Step** : Find the smallest string that can be accepted by the Regular Expression. **Second Step** : Draw necessary states with the transaction of the minimum string accepting machine. **Third Step** : For all states draw the remaining alphabets transactions.

For Example : Regular Expression (0 + 1)\* 1 "String ending with 1" Step 1: Smallest String : 1 Step 2: two states Q0 and Q1. having the transaction of 1 from Q0 to Q1. and Q1 is the accepting state. Step 3: for Q0 State Q0 1 transaction is to Q1. Now make 0 transaction in Q0 itself. For Q1 State Q1 1 transaction will remain in Q1. And 0 transaction will go in Q0.
> -2 votes

---
Tags: automata, finite-automata, regular-expressions, simulation
---


title: DFA Minimization

text:
# Question
Title: DFA Minimization
I am currently in a class that deals with DFA's and their minimization. However I believe I have reached a DFA where the method of minimization we were taught doesn't work.

I have the following DFA (in JFLAP)

Using the method given in class I do the following see if their are any non dissimilar states and if so collapse them together.

```
 | q0  q1  q2  q3  q4  q5
-------------------------
a| q1  q1  q2  q3  q4  q5
b| q3  q2  q5  q4  q5  q5

```

However there are no states where both a and b go to the same state, therefore no collapse states.

However when doing it in JFLAP it gives the following

The only way I can see you getting what JFLAP does is just thinking and having to realize bother q1 and q3 can be joined as well as q2 and q4.

# Answer
> 6 votes
Your method of DFA minimization is incorrect. You start with assuming all states to be different and merge the indistinguishable ones, this may not give the correct minimization. The correct way is to assume all to be same states and separate those which are distinguishable. Look at this for exact algorithm.

---
Tags: finite-automata
---


title: Return values of Probabilistic Programs

text:
# Question
Title: Return values of Probabilistic Programs
Syntax and semantics section of this paper on probabilistic programming mentions that the return expression of the program is a function f satisfying $ f : \sum \rightarrow \mathbb{R}^{\inf}\_{\geqslant0}$ where $\sum$ is the set of states. I do no not see the need of $\geqslant0$. Why can't the return values be negative?

# Answer
> 2 votes
The function $f$ is a probability sub-distribution, which means that it's a like a probability distribution, only its integral can be less than $1$ (due to the `observe` statements). The `return` statement normalizes $f$ back to a bona fide probability distribution.

Outside of quantum computing, probabilities are non-negative.

---
Tags: programming-languages, probability-theory
---


# Question
Title: Minimal Number of Fixed Size Sets to contain all Sets
My problem is very similar to the one posted here. Instead of finding one set covering the maximum of subsets, I need to find the minimal number of sets to cover all subsets.

I have $U = \\{1, 2, ..., 1000\\}$ and $S \subseteq \\{A \subset U |\space|A| \leq 15\\} $. I know that $|S| \< 1000$. I need to find a minimal number of sets of fixed size (e.g. 25) such that each set in $S$ is a subset of at least one of the fixed size sets.

It is not necessary that I have the minimum number of sets, a minimal number is sufficient.

I guess the problem can be split in those two steps:

1. Remove all sets that are subsets of other sets
2. Find minimal number of sets (of fixed size) that contain all given sets

It doesn't make the problem easier. How would I go about it? What are good algorithms for the two steps?

# Answer
> 1 votes
If the sets are chosen randomly, then for the parameters you chose, the problem can be solved efficiently. In particular, the following trivial algorithm will output the correct answer with high probability: take each set of $S$, pad it by adding 10 random elements, and output the result (all sets of $S$, padded).

This might sound wasteful, but for the parameters you mentioned, if the sets are chosen randomly, it's unlikely you can do better. You can only do better if there exist two sets $s,t \in S$ that can be covered by a 25-element set, i.e., such that $|s \cup t| \le 25$. This happens only if $s,t$ have at least 5 elements in common (i.e., $|s \cap t| \ge 5$).

Now when $s,t$ are chosen uniformly at random from all possible sets of size 15, the probability that they have two elements at random is very small. It is approximately ${15 \choose 5}^2/1000^5 \approx 9 \times 10^{-9}$. Also, there are ${1000 \choose 2}^2$ possible pairs $s,t$, so by a union bound, the probability that there exist two such sets $s,t$ is about $0.0045$. This means there is only a small probability that you can cover two sets from $S$ by a single set of size 25, if the sets of $S$ are chosen randomly.

In general, for your problem, one approach would be to find all pairs of sets $s,t \in S$ that overlap in at least 5 elements. Build a graph where $S$ is the vertex set and you add an edge between $s,t$ if $|s \cap t| \ge 5$. Find a maximum matching in this graph. Then you can use this to build a set of 25-size sets (one 25-size set per edge in the matching, plus one set per vertex not touched by the matching). However, if the sets are generated randomly, this is unnecessary as it is unlikely to find any pair of sets that overlap in at least 5 elements.

Anyway, if the sets are chosen uniformly at random, the problem is uninteresting for the parameters you gave. If the sets aren't chosen uniformly at random and have some structure, I recommend that you edit the question to describe this structure.

---
Tags: algorithms, optimization, sets
---


title: Does "contains only" imply "contains"?

text:
# Question
Title: Does "contains only" imply "contains"?
Written in English, does "the set S contains *only* members of set T" imply that S does contain some member of set T?

How would this relationship be written formally?

# Answer
My view is that vernacular would consider that S is not empty, i.e. $\emptyset \neq S\subseteq T$, while mathematical language would consider that S can be empty, i.e. $\emptyset\subseteq S\subseteq T$.

Lay people do not speak of empty sets, while mathematicians are aware of their role in their work.

That means that the sentence is not ambiguous, but the meaning depends on the community where it is used.

Of couse, people aware of the two readings can play games with it. But that is yet something else.

You may notice that I did not specifically mention English, because the same is probably true of many "languages".

To think that English (or German, or French) is a well defined language is unrealistic. Actually, I doubt you can find two people who agree on what is English and the meaning, or on the ambiguity, of its sentences,

It might be interesting to ask the linguists.
> 7 votes

# Answer
It's ambiguous whether "contains only elements of $T$" implies that it must contain at least one element. Formally, you could write $\emptyset\subset S\subseteq T$ or $\emptyset\neq S\subseteq T$ or say "the non-empty set $S$ contains only elements of $T$."
> 3 votes

---
Tags: terminology, computability, sets
---


title: A question on RSA

text:
# Question
Title: A question on RSA
Why were primes which are $1$ modulo $4$ considered to be weak for use in RSA cryptography (http://en.wikipedia.org/wiki/Blum\_integer)? Was there a time it was considered there could be an efficient algorithm if these primes be utilized (if so, then what exact reasons were these)?

# Answer
They're not weak for use with RSA. You don't cite where you got that misconception from, so it's hard for me to respond or identify the source of your confusion -- but you have a faulty premise. Given that the premise is false, the question evaporates.

For instance, see Wikipedia: https://en.wikipedia.org/wiki/RSA\_%28cryptosystem%29#Key\_generation. The description of the key generation algorithm has no mention of choosing $p$ or $q$ to be 1 mod 4.
> 2 votes

---
Tags: cryptography
---


# Question
Title: Find interval sums with minimum number of operation
Input:

* A list $A=a\_1,\ldots,a\_n$, with $\oplus$ a associative operation on $M$, and $A\subset M$.
* pairs $(s\_i,t\_i)$ for all $1\leq i\leq m$.

Output: The list $b\_1,\ldots,b\_m$, where $b\_i = \bigoplus\_{j=s\_i}^{t\_i} a\_j$.

We want an efficient algorithm to compute the output, such that it uses minimum number of $\oplus$ operations.

For example, if we have $m=2$ and want to find the sum on interval $(1,n-1)$ and $(2,n)$, then the best way is to first compute $t = a\_2\oplus \ldots \oplus a\_{n-1}$, then compute $b\_1 = a\_1\oplus t$ and $b\_2 = t \oplus a\_n$, using $n-1$ operations.

Note it is possible that we have to use $\omega(n)$ operations, consider we have the input that contain all pairs $(i,j)$, where $1\leq i\leq j\leq n$. This would require at least ${n \choose 2}$ operations, because there could be ${n \choose 2}$ different values.

Assume all elements in $M$ take $O(1)$ space. We also want to use as little additional memory as possible.

# Answer
> 1 votes
This problem was solved recently. The naive greedy algorithm works.

David Basin, Felix Klaedtke, Eugen Zălinescu, Greedily computing associative aggregations on sliding windows, Information Processing Letters, Volume 115, Issue 2, February 2015, Pages 186-192, ISSN 0020-0190

---
Tags: algorithms
---


# Question
Title: What do you mean by minimum height of a Binary Search Tree?
I came across the term "minimum height of a Binary Search Tree" (in Java) in class, but I don't fully understand. Could someone please elaborate on: (a) What it is ? (b) How to determine/find it ?

# Answer
Binary Search Trees(BST)are a class of data structures which are used to implement dynamic sets. They kind of store data pieces, whic are known as keys, and they also allow fast insertion and deletion of these keys. Also, they checkwhether a key is present in a tree.

I did not get your (b) part. Are you asking to determine whether a tree is BST or not?
> -2 votes

---
Tags: binary-trees, java
---


title: Execution time estimation

text:
# Question
Title: Execution time estimation
I've been trying to wrap my head around the following question for ages, its part of my revision for the upcoming end of year exam, however I fail to see how there is a link from the number to the letter, how will one cycle from 1 to a and iterate to get there? if that makes any sense! We were told that when estimating execution time of a loop, it is likely to be the number of times the loop executes, so therefor a list of length n would take approximately n units of time to execute, that makes sense, its just the cycle from 1-a, then 1-b? like, how many iterations will the loop run to get from 1 to a? it just confuses me! anyhow here it is as on the practice paper:

```
z := 0
for i from 1 to a
  for j from 1 to b
    for k from 1 to c
      z := z + a*b*c

```

• How long does it take to compute the k-loop?

• How long does it take to compute the j-loop?

• How long does it take to compute the i-loop?

• How long does it take to compute the algorithm?

# Answer
There's no list here. In this problem, $a, b, c$ are simply numbers, so the $k$ loop will iterate $c$ times, taking the values $k=1, k=2, \dotsc,k=c$ for any values of $i$ and $j$. Working outwards, the $j$ loop will iterate $b$ times and each time will perform a complete $k$ loop. In other words, the total amount of work done by the $j$ loop will be $bc$: $b$ iterations of the $j$ loop, each involving $c$ steps of the inner $k$ loop, no matter what the $i$ value is. Finally, in a similar way, the outer $i$ loop will iterate $a$ times, each time doing $bc$ work. The total number of iterations, then, will just be $abc$.

For example, with $a=2, b=3, c=2$ the $(i, j, k)$ values will be, in order, $$\begin{array}{c} (1,1,1) \\ (1,1,2) \\ (1,2,1) \\ (1,2,2) \\ (1,3,1) \\ (1,3,2) \\ (2,1,1) \\ (2,1,2) \\ (2,2,1) \\ (2,2,2) \\ (2,3,1) \\ (2,3,1) \\ \end{array}$$
> 1 votes

---
Tags: algorithms, time-complexity
---


title: About codes over $\mathbb{F}_2$

text:
# Question
Title: About codes over $\mathbb{F}_2$
I was looking through these notes but I am not sure I can locate the answer to these questions of mine - it would be great if someone can just even point out what to look for!

* So any set of binary vectors can be seen as "code"?
* Let $M$ be a $d\times m$ matrix over $\mathbb{F}\_2$ and let $X(M)$ be the graph on the binary vectors of length $d$, where two vectors are adjacent if their difference is a column of $M$. (does this mean that before comparing when one is taking a bit-wise difference of the vectors one is equating $-1$ to $1$ as would be inside $\mathbb{F}\_2$?)

Does this above construction have a name? Any motivations?
* What is this NP-hard question about finding a "minimum weight code" among a set of binary vectors? Can someone kindly give the precise definition?

# Answer
1. A binary code is a set of vectors in $\mathbb{F}\_2^n$ for some $n$.
2. Presumably the context in which you encountered this construction is a motivation for it. It's a particular case of a more general construction known as a *Cayley graph*, though perhaps this particular case has a specific name. You are right that all arithmetic is done in $\mathbb{F}\_2$.
3. There are several NP-complete problems related to codes; Madhu Sudan has an entire lecture on these. One of them is, given a generator matrix for a linear code, determine the minimum weight of a non-zero codeword (i.e., the minimum distance).
> 4 votes

---
Tags: complexity-theory, coding-theory, error-correcting-codes, code-generation
---


# Question
Title: How to cover maximum points with a fixed length line segment?
The problem is defined as:

> Given a set of $N$ points $(x\_1, x\_2, x\_3, \ldots, x\_n)$ and $L$ the **fixed** length of a segment.
>
> Find the number of maximum points which you can cover with a segment line of length $L$.
>
> # Ranges
>
> $1 \leq N \leq 100 000$
>
> $1 \leq L \leq 10^{10}$
>
> $0 \leq x\_i \leq 10^{10}$

I call sub-optimal ranges, ranges which are in the form $\[x\_n,x\_n+L\]$. The optimal range is the one which contains the maximum points of all ranges.

I've tried to consider the problem using that algorithm (pseudo-code):

```
Let be S, the set which contains all the N points.
Let be R, the set which contains ranges.
Let be maxPoints, the number of maximum points that we can have (set it to 0).
For all points p I have in my set S
     Store in R the range $[p, p+L]$
For all ranges r I have in my set R
     nPoints = 0
     For all points p I have in my set S
         If the point p is in the range r, then increment nPoints
     maxPoints = maximum value between maxPoints and nPoints
Display maxPoints

```

I think that the complexity of this algorithm is $O(N^{2})$, is there a way to make it faster? And is it really correct (in the sense, that it solves all cases of this problem).

# Answer
> 2 votes
You haven't explained how to implement `how many there is point in the range r`. You do this operation N times, so unless it takes $O(1)$, your algorithm won't be $O(N)$.

There is a simple algorithm that runs in time $O(N\log N)$:

1. Sort the input points.
2. Go over all the points in order, maintaining a data structure keeping track of the points at distance at most $L$ from the current point.

You can implement each iteration of the second step in amortized $O(\log N)$ using a balanced binary search tree.

Can we do it asymptotically faster? In many restriction computation model, the problem of *element uniqueness* (given a list of integers, determine whether they are all unique) requires $\Omega(N\log N)$ operations. Since element uniqueness reduces to your problem, in these models your problem requires $\Omega(N\log N)$, so the algorithm broadly outlined above is asymptotically optimal.

Of course, in practice you might benefit from algorithms which are more sensitive to the input distributions. In fact, assuming the answer is $M$, the algorithm outlined above runs in time $O(N\log M)$. If you expect $M$ to be very small, it might be worthwhile to use a list rather than a balanced binary search tree.

---
Tags: algorithms
---


title: Deadlock Solutions: Lock Ordering

text:
# Question
Title: Deadlock Solutions: Lock Ordering
This is from a textbook on operating systems. This is not homework, just part of the chapter on deadlocks.

```
transaction(Account from, Account to, Number amount):
    mutex lock1 = getlock(from)
    mutex lock2 = getlock(to)

    acquire(lock1)
    acquire(lock2)
        withdraw(from, amount)
        deposit(to, amount)
    release(lock2)
    release(lock1)

```

Deadlock is possible if two threads simultaneously invoke thetransaction() function, transposing different accounts. That is, one thread might invoke

```
transaction(checkingaccount, savingsaccount, 25)

```

and another might invoke

```
transaction(savingsaccount, checkingaccount, 50)

```

What is a good solution to this problem? One I can think of is to use a witness program that will alert the user that a deadlock has occurred, but there must be a better solution implementable by modifying the code. Any ideas?

# Answer
You simply need to place a total order on the accounts and always lock the accounts in that order.

You define a `<` operator on `Accounts` and then change the beginning like this:

```
mutex lock1 = getlock(from)
mutex lock2 = getlock(to)
if (from < to)
    mutex lockSwap = lock1
    lock1 = lock2
    lock2 = lockSwap

```

It doesn't matter what order you choose, it just has to stay the same through the whole program. In C, and other low level languages it is particularly easy to make this kind of `<` operator because you can just convert the addresses of the objects to integers and do the `<` on the integers.
> 3 votes

---
Tags: operating-systems, mutual-exclusion, deadlocks
---


# Question
Title: Running time of recursive algorithm with geometric series
What is the complexity of the recurrence $T(n) = 3T(\frac n2) + O(n)$?

So far I have:

$ O(n) \le cn$ for some constant $c$

Hence:

$$T(n) \le 3T(\frac{n}{2}) + cn$$

After a recursion:

$$T(n) \le 3(3T(\frac{n}{4}) + \frac{cn}{2}) + cn$$ $$= 9T(\frac{n}{4}) + \frac{3cn}{2} + cn$$

After another recursion:

$$T(n) \le 9(3T(\frac{n}{8}) + \frac{cn}{4}) + \frac{3cn}{2}+ cn$$ $$= 27T(\frac{n}{4}) + \frac{9cn}{4} + \frac{3cn}{2} +cn$$

The general term is:

$$T(n) \le 3^{k}T(\frac{n}{2^k}) + \frac{\sum\_{i = 0}^k{3^i}}{\sum\_{i = 0}^k{2^i}}cn$$

For some $k$

Now:

$$\sum\_{i = 0}^k{(\frac{1}{2})^i} = \frac{1}{1-\frac{1}{2}}$$ $$ = 2$$

Hence:

$$T(n) \le 3^{k}T(\frac{n}{2^k}) + 2\sum\_{i = 0}^k{3^i}cn$$

I do not know how to proceed from here.

This question is from *Algorithms; Dasgupta, Papadimitriou, Vazirani; 1st Edition.* Question 2.3 (a)

Thank you.

# Answer
$$T(n) \le 3^{k}T(\frac{n}{2^k}) + \sum\_{i = 0}^k{(3/2)^i} cn$$

**The recursion will reach the base case** when $2^k = n$ (i.e., $k = \log n$). And it is common to suppose the base case is $T(1) = 1$ (or $T(1) = d \textrm{ for some constant } d$).

Then (please check the details),

$$T(n) \le 3^{\log n} + \sum\_{i = 0}^{\log n}{(3/2)^i} cn = n^{\log 3} + 3cn^{\log 3} - 2cn = (3c+1) n ^{\log 3} - 2cn$$
> 0 votes

---
Tags: algorithms, algorithm-analysis, time-complexity, recurrence-relation
---


# Question
Title: About Control Unit in CPU and Clock Cycle
I've been studying about CPU and I am trying to implement a small CPU, like *MU0*.

Control unit gets instruction and generates and gives several control signals to other parts of CPU, such as ALU, PC, ACC, etc. And I know that these works in one clock cycle.

But I have some quetions.

1. Meaning of Signals (0 or 1) in Clock Cycle

Each one clock cycle has signal 1 first and has 0 next. Since CPU is an electronic equipment, 1 would mean current is flowing (so, "turn on") and 0 would mean no current flow (so, "turn off").

So, does each control signals connected to the clock cycle circuit turn off when the clock cycle is 0 at the same time, if we ignore delays of the circuit?

If not, i.e., if control signals can be 1 although clock cycle is 0, I can state my hypothesis:

Clock signal is only meaningful and only used when signal toggles 1→0 or 0→1. Control unit can not work when its signal stays in the same value since it can not recognize time is going.

Is that true or false?

2. Timing to Control each Control Signals

<sub>(source: tistory.com)</sub>

Here is the structure of MU0, one of simple CPUs.

If we want to store data from memory with the address in PC to IR and increase PC by 1 (i.e., PC = PC + 1), the manual says that setting control signals as below would do that.

* 0 : Asel, Bsel, ACCce, ACCoe
* 1 : PCce, IRce, MEMrq, RnW
* with ALU function B+1.

Note that the value of PC goes in ALU and the output of ALU is PC+1 since Asel(A selector), Bsel are 1.

But, since PCce(PC chip enabler) is 1, PC change the value by the input of PC, which is the output of ALU.

It seems good to make PC as PC+1. But my questions is:

This is an infinite loop theoritically since PC+1 would goes into ALU and PC+2 would save in PC, and then PC+2 would goes into ALU and PC+3 would save in PC, ... so and on until one clock cycle ends.

To avoid this, controlling timings would be different for each control signals. Is this really true, or is there another solution?

Thanks.

# Answer
> 1 votes
**1.)** (Almost) every component of the CPU needs to be synchronized by the clock, which means they all do their work only if the clock is high (1); never when it's low (0) (or alternatively only during rising edge). This could for example be implemented using an AND-gate, with the input to the component as first and the clock signal as second input. So the component will only get its new input if the clock is currently high, else it does nothing. And because the clock speed is set above the longest time any signal needs to propagate through any circuit in the CPU, this system is preventing signals from arriving before other signals are ready and thus keeps everything safe and synchronized. The control signals can be set at any time, but they will only be accepted during high clock.

**2.)** This is no loop, since the PC is actually a register which is egde triggered. This means, like mentioned above, that it is changing its state only one time per cycle for a short period of time. At an earlier time, the last output from ALU (PC + 1) is just waiting at the input of the PC. Then, at the next cycle, the PC takes its input. This is when PC = PC + 1 actually happens.

---
Tags: computer-architecture
---


# Question
Title: How many zeros should be in front of two's complement model?
**The Problem** Convert 256 to its 2's complement representation.

**My Work**

I know that 256's representation in unsigned binary is 100000000. What I know from working with two's complement model is that the most significant digit represents the sign of the number. So in this case, 100000000 cannot be 2's complement representation as well because that would mean that the original number, 256 is negative.

Is there a specified number of zeros I should add to the front of the binary representation? Would it be acceptable to just add one zero to the front, say 0100000000?

# Answer
Two's complement is a representation of a number. Using different bases, encodings, a number (as a mathematical object) can be represented in many ways.

There is no "specified number of zeros". It is rather than, if you have 10 bits, they can represent 1024 values. It can be unsigned numbers between 0 and 1023 It can be signed numbers between -512 and +511 if you use two's complement.

"0100000000" is indeed 256 both as unsigned and two's complement signed 10 bits numbers.
> 2 votes

---
Tags: arithmetic
---


# Question
Title: About having analytic control over any algorithm which finds perfect matchings.
A trivial algorithm to decompose a degree-d (n,n)-bipartite graph into d disjoint perfect matchings is this : direct all the edges from left to right and put capacity one on each of them - then add a super-source and a super sink with appropriately directed edges from them to each of the vertices on their side with capacity one - now run max-flow on it and that picks out a perfect matching - now remove this perfect matching and repeat - continue doing this till you have exhausted all the original edges - this clearly gives you the needed decomposition of the original graph into disjoint perfect matchings.

So one can think of this algorithm as basically returning you a set of d disjoint permutations on the set of n elements.

* Can one say what permutations will be returned? (Will it always return the same set of permutations in the same sequence?)
* Its possible that the answer to the above question is implementation dependent and in that case is there some "standard" implementation for which one can analytically write down the permutations that would be returned as a function of the input graph?
* Or is there any other way to solve this question where one analytically knows the permutations that will be generated?

# Answer
> Will it always return the same set of permutations in the same sequence?

No. If you call the algorithm twice with the same input, it's not necessarily guaranteed to give the same output both times. Many standard max-flow algorithms are non-deterministic, so there is no such guarantee. For instance, consider any algorithm based on selecting augmenting paths. If at any iteration there are multiple augmenting paths that would be acceptable, the max-flow algorithm will typically select one of them arbitrarily. Consequently, it is not deterministic.

However, any such algorithm can easily be made to be deterministic by simply specifying a deterministic rule for resolving all non-deterministic choices. For instance, whenever there are multiple acceptable choices, you can sort all of the acceptable options using some pre-specified order (say, lexicographic order) and always take the first.
> 1 votes

---
Tags: complexity-theory, algorithm-analysis, bipartite-matching, matching
---


# Question
Title: Is it possible to make N-way Controlled-NOTs out of Toffoli gates, without extra work bits?
I'm working on exercise 4.29 of Nielsen and Chuang:

> Find a circuit containing *O(n^2)* Toffoli, CNOT, and single qubit gates which implements a $C^n(X)$ gate (for n \>3), using no work qubits.

As part of solving this exercise, I'm trying to figure out if the task of making a NOT-controlled-by-N-bits is possible classically (i.e. without using single qubit gates, except the NOT gate).

This is trivial to do if you have work bits initialized to 0 available, but I haven't been able to figure out how to do it without work bits. I'm also not sure how to approach an impossibility proof.

The main thing I've figured out is that, if I could make $Increment$ and $Decrement$ gates, then I could do it like this:

```
   ____    ____
--|    |--|    |---    --•--
--|    |--|    |---    --•--
--| +1 |--| -1 |--- == --•--
--|    |--|    |---    --•--
--|    |--|____|---    --•--
--|____|-----------    --X--

```

But I also can't figure out how to make those gates, at least not without the many-controlled-not gate I'm trying to make.

Is this even possible (the limited-to-classical case, not the exercise)?

# Answer
It's not possible.

A reversible computation always corresponds to a permutation of the state space. When working on three bits, a Toffoli corresponds to a single swap in the state space (it swaps 111 for 110). When working on four or more bits, a Toffoli gate always corresponds to an even number of swaps in the state space. This is because it performs a swap for each possible state of the uninvolved bits, and there are an even number of such states. For example, a Toffoli applied to the first three bits of a four bit system swaps 111\_0 for 110\_0 and swaps 111\_1 for 110\_1. Even number of swaps.

Permutations have a parity. A permutation that can be implemented with an even number of swaps has even parity. Permutations that can be implemented with an odd number of swaps have odd parity. The composition of two even parity permutations will also be an even parity permutation. Odd parity permutations can't be reached by composing even parity permutations.

This means the Toffoli gate can't perform a CCCNOT without workspace, because the action of the CCCNOT on the state space is an odd parity permutation but the action of the Toffoli is an even parity permutation. The single CNOT and NOT gates have the same problem. You need an extra work bit (or quantum gates like $X^{1/8}$) to break the parity barrier.
> 3 votes

# Answer
Slight twist on this not being possible.

If you have any ancilla bits, even ones in an unknown state that you don't own, you can create a $C^3$NOT from $C^2$NOTs. Do this:

```
C1 ─•───•─── C1
    │   │
C2 ─•───•─── C2
    │   │
C3 ─┼─•─┼─•─ C3
    │ │ │ │
 T ─┼─X─┼─X─ T + (C1 * C2 * C3)
    │ │ │ │
 E ─X─•─X─•─ E

```

So *in practice* you can make higher CNOT gates out of Toffoli gates. You just use any other bits that happen to be in the circuit as working space. You don't need the extra bits to be initialized to 0, and you won't trash them, but they do need to be present (they're catalysts).

So, in an $M$ bit circuit, you can at least make up to $C^\left\lceil \frac{M}{2} \right\rceil$NOT gates out of Toffoli gates by using the other half of the bits as workspace. You can also keep re-using one extra bit and the target bit as alternating workspaces, letting you get up to $C^{M-1}$NOTs, but that seems to require a quadratic number of gates.
> 2 votes

---
Tags: circuits, reversible-computing
---


# Question
Title: Why doesn't the binary fraction representation match the decimal fraction representation?
**The Problem:** What value does the hexadecimal number x55544552 represent in data type IEEE floating point?

**My Work**:
I first wrote out that hexadecimal number in binary and got

```
0101 0101 0101 0100 0100 0101 0101 0010

```

Now I have my three different sections, the sign, 0, the exponent 10101010 - 127, or 170 - 127, 43, and the fraction portion 101 0100 0100 0101 0101 0010, or 5522770.

Now I can write out my IEEE floating representation as
1.552270 $\*$ 2 $^{43}$
To simplify that expression, I decided to move the decimal point 23 slots to the right(the whole exponent proportion) and got
(1 101 0100 0100 0101 0101 0010) * 2 $^{20}$) or 13911378 * 2$^{20}$.

To me, all my math made sense. When I checked my answer on Hex to IEEE Float, everything matched up but I couldn't figure out this part on the web application.
The web application has a specified section called fraction which represents the fraction of the floating point representation. In binary, the fraction is 1 .10101000100010101010010 but in decimal, the web application says the fraction is 1.6583655. When I converted 10101000100010101010010 to decimal, I got 5522770. Shouldn't the fraction decimal representation be 1.5522770 or am I missing something?

# Answer
No, that's not how binary fractions work. A decimal such as $0.13$ represents $$0.13\_{\mathrm{dec}} = 1\times 10^{-1} + 3\times10^{-2} = \frac{13}{100}\\,.$$

Similarly, a binary fraction such as $0.1101$ represents $$0.1101\_{\mathrm{bin}} = 1\times 2^{-1} + 1\times 2^{-2} + 0\times 2^{-3} + 1\times2^{-4} = \frac{13}{16}\\,.$$ $1101\_{\mathrm{bin}} = 13\_{\mathrm{dec}}$ but $$0.1101\_{\mathrm{bin}} = \frac{13}{16}\neq\frac{13}{100}=0.13\_{\mathrm{dec}}\\,.$$

Another way to see that you can't convert fractions into binary by forgetting that they're fractions is to note that $0.3=0.30$, but $3\neq 30$. So it can't possibly be that you convert $0.3$ in decimal to binary by saying "$3$ in binary is $11$, so $0.3$ in binary is $0.11$", since $0.3=0.30$ in decimal, so they should be equal in binary, too. But $30$ in binary is $11110$.
> 6 votes

---
Tags: arithmetic, floating-point
---


title: DNF to CNF conversion: Easy or Hard

text:
# Question
Title: DNF to CNF conversion: Easy or Hard
In relation to the thread Proving that the conversion from CNF to DNF is NP-Hard (and a related Math thread):

How about the other direction, from DNF to CNF? Is it easy or hard?

On Page 2 of this paper, they seem to hint that both directions are equally hard when they say "*We are interested in the maximal blow-up of size when switching from the CNF representation to the DNF representation (or vice versa)*".

But DNF-SAT is in **P** and CNF-SAT is **NP**-complete. So given a DNF expression $\phi\_1$, there should be an *equisatisfiable* CNF expression $\phi\_2$ whose length is polynomial in the length of $\phi\_1$. And the $\phi\_1 \to \phi\_2$ conversion can be done in poly time. Is this correct?

Edit: Changed *equivalent* to *equisatisfiable* (that is, additional variables are allowed in $\phi\_2$).

# Answer
If you are willing to introduce additional variables, you can convert from DNF to CNF form in polynomial time by using the Tseitin transform. The resulting CNF formula will be equisatisfiable with the original DNF formula: the CNF formula will be satisfiable if and only if the original DNF formula was satisfiable. See also https://en.wikipedia.org/wiki/Conjunctive\_normal\_form#Conversion\_into\_CNF.

If you don't want to allow introduction of additional variables, converting from DNF to CNF form is co-NP-hard. In particular, testing whether a DNF formula is a tautology is co-NP-hard. However, testing whether a CNF formula is a tautology can be done in polynomial time (you just check separately whether every clause is a tautology, which is easy as each clause is a disjunction of literals). Therefore, if you could convert from DNF form to CNF form in polynomial time, without introducing new variables, then you would obtain a polynomial-time algorithm for testing whether a DNF formula is a tautology -- something which seems unlikely, given that we expect P is not equal to co-NP. Or, to put it another way, converting from DNF to CNF form without introducing additional variables is co-NP-hard.

This is the difference between equivalence vs equisatisfiability. Equivalence requires the two formulas to have the same set of solutions (and thus does not allow introducing additional variables). Equisatisfiability only requires that either both formulas are satisfiable or both are unsatisfiable (and thus does allow introducing additional variables).
> 16 votes

---
Tags: complexity-theory, logic, satisfiability, normal-forms
---


# Question
Title: A good-enough version of good-enough? When should I stop iterating?
I am studying Abelson and Sussman's *Structure and Interpretation of Computer Programs*, 2/e. I solved the exercise 1.7, which asks for a better stopping criteria for an iterative function to calculate the square root function, and then checked my solution against one that I found on this site: http://community.schemewiki.org/?sicp-ex-1.7

The original function iterated until $|\mathtt{guess}^2 - \mathtt{x}| \< 0.001$, but the book points out that something better is needed because this does poorly both for very large and for very small `x`.

The solution on schemewiki.org iterates until $|\mathtt{improve(guess, x)-\mathtt{guess}}| \< .001\\; \mathtt{guess}$, following the book's suggestion of watching "how `guess` changes from one iteration to the next and stopping when the change is a very small fraction of the guess." (The `improve` function takes a guess and `x` and generates a better guess by averaging the guess with `x`/guess.)

While I instictively went for a precision relative to the magnitude of the radicand. $|\mathtt{guess}^2-x| \< 0.001\\;\mathtt{x}$.

Both functions seem to yield similar results. Mine seems more obvious and efficient to me. Maybe too obvious... I suppose there is something I missed ?

# Answer
I did not check the code used in Abelson and Sussman's book or wiki. My guess is that the recursive (or iterative) procedure will somehow organize to compute `improve(guess,x)` only once. In a recursive procedure, you just compare the formal parameter which is the previous guess with the actual value (current guess) that you would pass for a recursive call, in order to decide whether actually do the call rather than return it. There may be a difference of one (wasted) iteration depending on how you do the test.

Regarding the fact that you do the test on $x$ or on $\sqrt x$, or rather $\mathtt{guess}^2$ or $\mathtt{guess}$, that does not give you the same precison if you look for the same difference.

One way of explaining it is that $|\mathtt{guess}^2-x|= |\mathtt{guess}^2-{\sqrt x}^2| = |\mathtt{guess}-\sqrt x|(\mathtt{guess}+\sqrt x)$
since the second factor has to be positive (at least when relative imprecision gets small).

Since $\mathtt{guess}$ is supposed to be very close to $\sqrt x$, we know that $\mathtt{guess}+\sqrt x$ is very close to $2\sqrt x$ or $2\\;\mathtt{guess}$.

Hence $|\mathtt{guess}^2-x|$ is close to $2\sqrt x\\;(\mathtt{guess}-\sqrt x)$, so that the condition $|\mathtt{guess}^2-x| \< 0.001\\;x$ can be replaced by $2\sqrt x\\;|\mathtt{guess}-\sqrt x| \< 0.001\\;x$, i.e.
$|\mathtt{guess}-\sqrt x| \< 0.0005\sqrt x$ or, still using the same approximation:
$|\mathtt{guess}-\sqrt x| \< 0.0005\\;\mathtt{guess}$

This can be further formalized, but the above informal reasonning gives you the idea.

However, I did not check how fast this conputation is converging, and what is the difference between $|\mathtt{improve(guess, x)-\mathtt{guess}}|\\;$ and $|\mathtt{guess}-\sqrt x|$, i.e. how fast one gets closer to the exact answer with each new iteration (assuming the precision of the arithmetics is still good). Their ratio should also be accounted for. It depends on the formula used for computing the approximation, which I did not look at.
> 3 votes

---
Tags: numerical-analysis
---


# Question
Title: How to find the Context-free grammars for this language
give a context-free grammar describing the language L={w∈{a,b}∗∣w is of the form xby, where |x|\>|y|}.

I had one solution like this

```
S -> AYCbY|AYbY|YCbY
A->aB|bB
B->aB|bB|_
C->aD|bD
D->aD|bD|_
Y->aY|bY|_

```

but it was complaining that it accepts the language **babbabaaaaa** which is not belonging to the language. Anyone knows how to solve this? and I have no idea how it produces babbabaaaaa, if each time both Ys follows the same rule.

# Answer
One helpful technique is to decompose a problem like this into the concatenation of two subproblems, each of which can be generated by a simpler grammar. In this case, a string $xby$ with $|x|\ge|y|$ can be written as $uvby$ with $|u|\ge 1$ and $|v|=|y|$. The reason for doing this is that the $u$ part (all strings over $a,b$ of length at least 1) can be generated by $$ A\rightarrow aA\mid bA\mid a\mid b $$ and the $vby$ part (where $v$ and $y$ have the same length) can be generated (from inside out, starting with the central $b$) by $$ B\rightarrow aBa\mid aBb\mid bBa\mid bBb\mid b $$ Now just make a grammar from the concatenation of the $A$ part followed by the $B$ part.

You might want to look at this answer.
> 3 votes

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


# Question
Title: Guessing the structure of a finger tree from the number of elements
I'm writing a data structure library, and I want to write an efficient algorithm for adding many elements to a finger tree (from an iterable sequence). I'm going to do this by constructing a finger tree from the sequence efficiently, as described below, and then concat it to the original finger tree. Concat is a very cheap operation compared to adding many elements.

To construct the finger tree, I put the elements into an array, and get its length. Then I build the finger tree from the bottom up, starting with the deepest deep tree and working outwards. This should be much, much more efficient.

In order to do this, I must guess the structure of the resulting finger tree from the number of elements to be added, and I'm not sure how to do this.

# Answer
> 4 votes
From first principles, every 2-3 tree is a finger tree viewed from another angle, so you could solve the problem by solving the somewhat easier problem of "What shape are the valid 2-3 trees of size $n$?"

You can also look at many existing finger-tree libraries. The first one created, was, of course, the Haskell one. The function you are looking for is `replicate`, which takes a value $v$ and size $n$, then creates a finger tree of size $n$ containing $n$ copies of $v$. The real work of `replicate` is done in `applicativeTree`, which has individual cases for $n \leq 8$ and recurses for larger $n$.

---
Tags: data-structures, trees, functional-programming, persistent-data-structure
---


title: Online supervised learning algorithm

text:
# Question
Title: Online supervised learning algorithm
I have labeled examples coming in on the fly, thus I need to create a classifier from sequential data instead of a static example set. Incoming data is fully labeled, there are no unlabeled examples. Each incoming example has a number of features.

E.g. let X by an incoming example with 3 features

```
X := (day = sunday, weather = sunny, season = summer, label = go to the beach)

```

I want to incrementally train a classifier such that whenever I see the next occurance of (sunday, sunny, summer) I want the classifier to suggest going to the beach.

Due to memory restrictions I am unable to keep the entire set of training examples.

Can you point me to adequate online/incremental learning algorithms for such a particular problem?

# Answer
> 3 votes
Wikipedia has an overview of online machine learning; I suggest you start there and then look at some of the references linked there, and take a trip to your library to check out some books.

One approach is to use learning algorithms that allow you to iteratively update the learned model, as you receive each training point.

Another approach might be to use an ensemble classifier: you learn multiple weak classifiers, each of which outputs its own prediction at the label, and then to classify any point you run all of the weak classifiers and you take a majority vote of their predictions.

One simplistic method would be to periodically train a new weak classifier and add it to your ensemble. For instance, suppose you have storage for $n$ points. You could add each point to storage as you receive it, then when your storage gets full, train a weak classifier on all $n$ of those points, add it to the ensemble, and clear out your storage.

It might be better to bias your storage strategy towards remembering points that you have classified wrong. For instance, as a simple example, you could reserve $n/3$ storage slots for remembering past points that were misclassified and $2/3$ storage slots for storing the last $2n/3$ points you received. When the latter gets full, you could train a new weak classifier on all of those $n$ points, add it to the ensemble, then classify all $n$ of those points with the ensemble classifier, discard all the ones that were correctly classified by the ensemble classifier, and keep a random sample of size $n/3$ chosen from the remaining points (moving them into the $n/3$ slots for misclassified points and emptying out the $2n/3$ slots for new points).

Finally, you might also be able to adapt boosting methods to an online setting. Boosting methods assign a weight to each training point; the higher the weight, the harder the weak classifier tries to classify that point correctly (i.e., the greater the penalty for misclassifying that point). The idea is that points which have been classified wrong in the past will receive a higher weight, and so future weak classifiers will be biased towards trying to classify those points correctly. Rather than trying to store all training points you've ever seen, I could imagine trying to store a random sample of the training points, where each point is selected with probability proportional to its weight. Thus, you could store $n$ training points and their weights; after you train each new weak classifier, you can update the weights of all $n$ remembered points and then sample $n/2$ of them (say, the $n/2$ with highest weights, or take a random sample with distribution given by the weights).

I don't know how well these methods would work, but you could give them a try in your setting and see. But start by exploring the literature. You know what they say: a week in the computer lab can save you a day in the library.

---
Tags: machine-learning, classification, online-algorithms
---


# Question
Title: LCA from children using bottom up approach?
I'm interested in finding the LCA of two distinct Nodes in a (not necessarily binary) tree from the bottom up without using depth.

How would I go about traversing the tree, starting from any 2 arbitrary nodes, each of which points to a previous node as shown without a depth variable?

# Answer
Here is one approach. Given leaves $\alpha,\beta$, first compute the depths $d(\alpha),d(\beta)$ of both leaves (to compute the depth of a leaf, measure how many times you need to apply the parent operation until you reach the root). Suppose without loss of generality that $d(\alpha) \geq d(\beta)$. Replace $\alpha$ with $\alpha$'s $(d(\alpha) - d(\beta))$'th parent. The least common ancestor doesn't change, and so we can assume without loss of generality that $\alpha$ and $\beta$ are at the same depth.

If $\alpha = \beta$, then $\alpha$ is the least common ancestor. Otherwise, replace both $\alpha$ and $\beta$ with their parents. This doesn't change the least common ancestor. Continue like that, and eventually you will find the least common ancestor.
> 6 votes

---
Tags: algorithms, graphs, trees, graph-traversal
---


# Question
Title: What is the complexity of multiplying a matrix by a scalar?
I would like to know the complexity of multiplying a matrix of $n\times m$ size by a scalar $\alpha$?

In fact, I have a directed graph $G=(V,E)$ represented by an incidence matrix $M$. I would like to calculate the transpose of this graph, i.e., inverse the directions of the edges. I think that if I multiply $M$ by $-1$ I will get the transposed graph. Am I right?

* If I am right, what is the complexity of multiplying a matrix by a scalar?
* If I am not, where is my mistake and what is the complexity of multiplying a matrix by a scalar anyway?

I think the complexity is $\Theta(n\cdot m)$.

Thanks.

# Answer
In general, if you have an $n\times m$ matrix $A=(a\_{i,j})$ with $1\le i\le n$ and $1\le j\le m$ then there will be $nm$ entries in the array. To multiply $A$ by a scalar $c$ you multiply each element by c, which (assuming multiplication can be done in constant time) will take $nm$ multiplications. That's not the way to go, though, if $A$ is the adjacency matrix of a directed graph.

For your peoblem, if $A$ is the adjacency matrix of a digraph $G$ on $n$ vertices, then $A$ will be an $n\times n$ matrix $(a\_{i, j})$ with $a\_{i,j}=1$ when there is a directed edge $e=(i, j)$ from vertex $i$ to vertex $j$ and $a\_{i,j}=0$ otherwise. You correctly note that the reversed graph $G'$ will have an adjacency matrix $B=(b\_{i,j})$ which is the transpose of $A$, so we'll have $b\_{i, j} = a\_{j, i}$, since $G'$ will have an edge from vertex $v\_i$ to vertex $v\_j$ if and only if $G$ has an edge from $v\_j$ to $v\_i$. To get the transpose of $A$, then, we'll swap $a\_{i, j}\leftrightarrow a\_{j, i}$ entries of $A$. There will be $n(n-1)/2$ swaps needed, since we swap every element above the main diagonal with its corresponding entry below the main diagonal.

Note that multiplying $A$ by $-1$ won't work, since the entries of an adjacency matrix must be only $1$ or $0$.
> 2 votes

# Answer
Of course, as previously noted by other users, you cannot transpose a matrix by a simple multiplication by a scalar. Transposition is an operation of its own.

**The complesity of matrix operations depends on the way the matrices are represented.**

The cost of matrix operations is very dependent on the way matrices are actually represented in your algorithm. While the most obvious representations can have a cost $O(nm)$ (or $O(n^2)$ for a square matrix) for scalar multiplication or for transposition, other representations can be chosen, depending on the algorithm it is used for, with a lower cost.

The complexity of multiplying a matrix by a scalar $\alpha$ in the usual way does imply multiplying each of its $n\times m$ elements by $\alpha$, and hence has a cost $O(nm)$. However, in general, the cost depends on the way you actually represent matrices, and it is conceivable to use representations where the cost might be constant, if the matrix is represented up to scalar multiplication together with a scalar factor. The computational cost can also be lower in the case of a sparse matrix representation that allows iterating only on the useful (or non-zero) elements.

Without going into details, matrix transposition can also be done in constant time, i.e., complexity $O(1)$, if you choose to represent a matrix as a pair composed of an appropriate memory structure of elements, and an indexation function for accessing them, given the row and column number. Then transposition can be achieved in constant time simply by changing the indexation function.

*Note*: this is a matter of representation, not of *model of computation* (the expression *computational model* being ambiguous). But I am not sure what is intended by Tom van der Zanden'comment.
> 1 votes

---
Tags: algorithms, matrices
---


# Question
Title: Which fingerprinting/hashing algorithms support compounding?
The definition of fingerprinting algorithms in Wikipedia describe a property called compounding as you can see here as:

> Some fingerprinting algorithms allow the fingerprint of a composite file to be computed from the fingerprints of its constituent parts.

I suspect compounding is not a commonly used term for describing this capability. I have failed to find any other algorithm that allows

```
hash(x + y) = hash(x) + hash(y)

```

Wikipedia is not always the most reliable source of information but the article for fingerprinting seems to imply that there are algorithms other than Rabin's fingerprinting method that support compounding. I'm probably not using the right terms for search but I could not find any.

So are there any hash functions (or fingerprinting algorithms) out there that supports this property?

# Answer
> 4 votes
This falls into a general class of hash functions known as homomorphic hash functions.

Your question is not entirely clear about what definition you are using for $+$. If you want the hash function to satisfy $h(x+y)=h(x)+h(y)$ where both instances of the $+$ operator refers to addition in a suitable group (e.g., addition of integers, xor), then such a hash is called *linear*. A CRC hash is an example of a linear hash function.

It's important to distinguish concatenation from addition. If you are looking for a hash that satisfies

$h(x||y) = h(x)+ h(y)$,

where $||$ denotes concatenation and $+$ denotes addition, then that's a different beast. I don't know of any standard name for it. This is a very restrictive property. Such hash function will always necessarily have the form

$h(x) = \sum\_i h(x\_i),$

where $x\_i$ is the $i$th character of the string $x$. Consequently, the only way to achieve such a property is as follows: you choose some lookup table that maps from a single character to an integer; then you apply this to all the characters in the string and sum them up. Unfortunately, such a hash is less than ideal, as a hash function, as any two strings that have the same characters in a different will yield the same hash value. Thus if you use this as a hash function for a hash table, you might find an increased rate of collisions. However, it would be easy to construct such a hash function.

There are other generalizations. For instance, maybe you want a hash function with the property that

$h(x||y) = F(h(x), h(y))$

where $F$ is some associative function. There are standard constructions of such a hash. For instance, CRCs achieve this (though here $F$ depends on the length of $x$).

I suggest you also look at rolling hashes, the Rabin-karp rolling hash, Buzhash, AdHash, and MulHash. See also the following resources:

# Answer
> 2 votes
All the hash function mentioned below are not cryptographic hash function. This might give you an idea what I am talking.

If $+$ is addition, then you have very limited choices. As

```
hash(x + y) = hash(x) + hash(y)

```

for all $x,y$ if and only if *hash* is a linear function.

If the first $+$ is concatenation, then Rabin–Karp string hashing is a good choice. Consider the following hash $h: \mathbb F^\* \to \mathbb F$ ($\mathbb F$ should be a finite field) $$ h(x) = \sum\_{i=1}^{|x|} x\_i p^i $$ if $p\in\mathbb F$ is randomly chosen and $|x| \ll |\mathbb F|$, $h$ is a good hashing *for same input length*. For any $x,y \in \mathbb F^n$, $\Pr\[h(x) = h(y)\] \leq n/|\mathbb F|$. It's easy to find collision between inputs of different length. So you might want to pad the input length as part of the hash value. $$ \hat h(x) = (h(x),|x|) $$
As $h$ is linear, it's easy to compute hash of coord-wise addition, $$ h(x+y) = h(x) + h(y). $$ It's also easy to compute the hash of concatenation, $$ h(x \text{ concat } y) = h(x) + p^{|x|} h(y). $$

# Answer
> 1 votes
A parity bit and simple modular checksum have the property. If you know the length of the first, or maybe second, message then you can do so with CRCs even, but the polynomial division involved takes as long as redoing a checksum.

Any cryptographic or secure hash function should not allow this because it'd enable a combined replay and extension attack. And it'd leak considerable information about message contents.

If you need stranger hash function properties then you could ask cstheory perhaps.

---
Tags: algorithms, information-theory, hash
---


# Question
Title: How to solve a Simple Linear Equation using a binary tree data structure
i am currently working on a school project that takes in a simple linear equation and has to return the value of x, the code i have transforms x + 3 = 3x - 2 into a binary tree format like so:

```
        =
     /     \
    +       -
   / \     / \
  x   3   *   2
         / \
        3   x

```

now that i have the expression in this format could someone please explain how can i obtain the value of x, any help is appreciated and if you have an alternative method that may make it easier i would love to hear it thank you

# Answer
> 3 votes
You don't really want to solve the equation using this representation. You want to convert it into a normal form such as $ax+b = 0$, from which you can read the solution. The first step would be to replace $P = Q$ with $P - Q = 0$. The second step would be to normalize $P - Q$ to some standard form, say a polynomial (or in you case, perhaps $ax+b$). One way to do this is to convert each subexpression into normal form recursively, using rules for handling leaves such as numerical constants and $x$, and mathematical operations such as $+,-,\times$.

---
Tags: binary-trees, linear-algebra
---


# Question
Title: About being able to sample a permutation of a finite set uniformly at random
I was looking at this question.

* So if I understand the above discussion right then it concludes that if say one had access to an oracle which can uniformly at random sample from a finite set then one can't using this uniformly at random sample a permutation of another finite set (chosen may be adversarially) and also have the algorithm be guaranteed to halt.

Is the above summary right? Is there a reference to a proof of the above?
* Is there a fundamental understanding of this impossibility?
* If one is allowed say (1) exponential space or (2) the oracle was picking the numbers with some bias then can we get across this impossibility?
* What are the consequences if hypothetically one could do the above?

# Answer
**Claim.** Given access to finitely many samples of the uniform distribution over $\\{1,\ldots,N\\}$, you can sample uniformly from $\\{1,\ldots,M\\}$ iff $M \mid N^k$ (read: $M$ divides $N^k$) for some $k$.

**Proof.** Suppose first that $M \mid N^k$ for some $k$. Combine $k$ samples of $\\{1,\ldots,N\\}$ to get a uniform sample $x$ of $\\{1,\ldots,N^k\\}$, and return $x \pmod{M}$, which is understood to return a value in $\\{1,\ldots,M\\}$ rather than the more usual $\\{0,\ldots,M-1\\}$. There are exactly $N^k/M$ preimages of each $y \in \\{1,\ldots,M\\}$, namely $y,y+M,y+2M,\ldots,y+(N^k/M-1)M$. Therefore $x \pmod{M}$ is a uniform sample from $\\{1,\ldots,M\\}$.

Suppose next that using $k$ samples you can sample uniformly from $\\{1,\ldots,M\\}$. As before, we can think of the $k$ samples as a uniform sample from $\\{1,\ldots,N^k\\}$. Let $A$ be the preimage of $1$, that is the set of $x \in \\{1,\ldots,N^k\\}$ which cause the algorithm to return $1$. Since the algorithm returns $1$ with probability $1/M$, we must have $|A|/N^k = 1/M$ and so $|A| = N^k/M$, which can only happen if $M \mid N^k$. $\qquad\square$

Sampling a permutation on $M$ elements is the same as sampling a number in the range $\\{1,\ldots,M!\\}$. This is possible using finitely many samples from $\\{1,\ldots,N\\}$ if and only if $M! \mid N^k$ for some $k$.

This proof is quite elementary, so you can probably find many references, though none are really needed.
> 3 votes

# Answer
No, the summary is not correct. Your "if...then...." statement cannot possibly be correct, as we *do* know ways to sample a permutation of a finite set uniformly at random (under reasonable assumptions). For instance, one method is to repeatedly ($n$ times) sample without replacement. What that question is saying is that there is no number $t$ such that we can say with sure that the algorithm will terminate after at most $t$ steps; there will always be some tiny chance it takes longer than $t$ steps. However, the probability it will take longer than $cn^2$ steps (say) is exponentially small in $c$, so this is basically just a theoretical quibble -- for all practical purposes, the running time is $O(n^2)$.
> 1 votes

---
Tags: complexity-theory, randomized-algorithms, halting-problem, randomness
---


# Question
Title: The use of modal logic in computer science
I have a tentative understanding of modal logic. Can anyone explain modal logic as it is used in computer science?

# Answer
> 2 votes
I think you can find many good examples if you search a bit online. Some very-easy-to-find examples are in the following list:

From Stanford Encyclopedia

> In computer science, labeled transition systems (LTSs) are commonly used to represent possible computation pathways during execution of a program.

Wikipedia has some examples in its article modal logic:

> Versions of temporal logic can be used in computer science to model computer operations and prove theorems about them. In one version, ◇P means "at a future time in the computation it is possible that the computer state will be such that P is true"; □P means "at all future times in the computation P will be true". In another version, ◇P means "at the immediate next state of the computation, P might be true"; □P means "at the immediate next state of the computation, P will be true".

Also, if you go to Logic in Action, you will find several examples, e.g.:

> \[Chapter 6\] introduces dynamic logic, a system that was introduced in computer science for reasoning about the behaviour of computer programs, by Vaughan Pratt and others, in the 1970s.
>
> In \[Chapter 10\] it is explained how predicate logic can be used for programming. The chapter gives an introduction to concepts used in automating logical theorem proving. This leads to computational tools underlying the well known logic programming language Prolog, popular in AI an in computational linguistics. The inferential mechanism behind Prolog is called SLD-resolution. This is the reasoning engine for a natural fragment of predicate logic (the so-called Horn-fragment).

# Answer
> 0 votes
Modal logic is useful for verification of reactive systems

> A reactive system is a system that responds (reacts) to external events. Typically, biological systems are reactive, because they react to certain events. However, the term is used primarily for describing human-made systems. For example, a light consisting of a bulb and a switch is a reactive system, reacting to the user changing the switch position.

Specification of such systems may be given as a labelled transition system (LTS) or by some process algebra expressions (CCS for example).

In this context, both safety and livenss properties are important:

> In distributed computing, **safety** properties informally require that "something bad will never happen"
>
> In distributed computing, **liveness** properties informally require that "something good eventually happens"

**Safety properties:**

* At most 1 process in critical section using a mutex
* No deadlocks

**Livness properties:**

* A request is eventually followed by a grant
* Every packet sent must be received at destination

Liveness properties should be specified and verified to ensure that the system makes progress and is "alive", while safety ensures that no bad state is reached.

Such properties can be specified using a (temporal) modal logic, such as CTL

---
Tags: logic, modal-logic
---


title: synchronization (test-and-set)

text:
# Question
Title: synchronization (test-and-set)
I have benn wondering about the following possibility: if I have multiple hardware threads on the same core, and then someone decides to use shared register to allow fast synchronization among threads that run on the CPU, and implements test-and-set on the register instead of doing it in main memory. Will this work? and if it works, why?

# Answer
> 2 votes
Synchronization based on test-and-set requires a shared data storage location that all the involved threads can read and modify. Your shared register is a shared data storage location.

The reason synchronizing on a register when the threads are running on different CPUs is that the register would not be shared (not be visible) to one of the threads. You should think of registers as memory locations with some features removed to make them faster.

In fact, something similar to your scenario was possible on SPARC processors. The SPARC had a large register file (something like 64 or 128 registers) with 8 registers that were always visible and then 24 register "windows" into the rest of the register file. Usually these windows were used to implement fast stack frames, but there were several experimental runtime systems that used the windows to support multiple threads.

---
Tags: operating-systems, synchronization, threads
---


# Question
Title: Lower bound for finding majority element in a sorted array
Suppose $A$ is a sorted array with $n$ elements. I want to know whether we can determine if there are majority elements in $A$ with time complexity $O(1)$.

Recall that a majority element of $A$ is an element which appears over $n/2$ times in $A$.

I can find a $O(\log(n))$ algorithm to solve this problem. But I'm not sure whether this can be done in $O(1)$. I was trying to use the adversary method, but I don't know how to construct it.

# Answer
Any algorithm would need $\Omega(\log n)$ queries.

To see this, define $f(k)$ to be the number of queries needed for deciding whether an element $x$ appears at least $a$ times in a sorted array $A$. We assume that $x$ appears in $A\[m\],A\[m+1\],\dots,A\[M\]$, and that $k\triangleq\min\\{a, m-1, n-M\\}$.

Notice that in these notations we are looking to bound $f(\lfloor n/2 \rfloor)$.

Claim: $f(k)\ge \log k$.

Proof:

Consider the first query made by the algorithm.

If it was done within radius $k/2$ of the interval (i.e. somewhere in $\[m-k/2,\ldots,M+k/2\]$), and found the median at the spot, then we still need at least $f(k/2)$ queries to decide the problem.

If it was done outside that radius, consider the case where the queried cell did not contain the median. Once again, this leaves us with at least $f(k/2)$ queries to be made.

Continue with induction and you get the $\Omega(\log n)$ bound.
> 6 votes

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


# Question
Title: Why are there $(2kn+1)^{kn}$ Turing Machines with $k$ symbols and $n$ states?
I've seen a few references \[1\], \[2\], \[3\] that say that for a Turing Machine with transition function defined by:

$\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \\{L, R\\}$

the number of turing machines with $n$ states and $k$ tape symbols is $(2kn+1)^{kn}$.

However, looking at the definition, shouldn't it be $(2kn)^{kn}$ instead?

# Answer
Perhaps they are counting the number of Turing machines with *at most* $n$ states. In any case, it's not a big difference. Usually one is only interested in an upper bound, and from that perspective there is no difference between the two expressions.
> 4 votes

---
Tags: turing-machines, combinatorics
---


# Question
Title: Difference between substitution, morphism, and homomorphism
In closure properties, I got confused between substitution and morphism.

1) According to Wikipedia, string substitution means to map letters in a set of alphabets to languages (possibly in a different alphabet), that is, $f(a) = L\_a$. Does that means to replace a letter with a language? Or replace 1 letter from a set of alphabets with 1 letter another set of alphabets?

2) According to Wikipedia, string homomorphism means to replace each letter with a single string, that is, $f(a) = s$, where $s$ is a string. What does 'a single string' mean? Does this mean the letter 'a' may be replaced by a string such as 'owl'? A webpage says that homomorphism is a group maps, which make me even more confused. What's the difference with substitution?

3) I thought that if $\left| f(a) \right|=1$, it's called morphism. Then this is not a string but only a letter. Are morphism and homomorphism the same thing?

I am a beginner and really confused. Hope somebody can help me clear this confusion, as well as the difference in proving the closure properties of substitution, homomorphism, and morphism. Your knowledge and help are very appreciated.

# Answer
Indeed morphism and homomorphism are the same in formal language theory. They are letter-to-string mappings $h:\Sigma \to \Delta^\*$, and then extended to string-to-string mappings $h:\Sigma \to \Delta^\*$ in a morphic way: $h(\varepsilon) = \varepsilon$, and $h(xy) = h(x)h(y)$ for strings $x,y\in \Sigma^\*$.

A substitution is a letter-to-language mapping, which is likewise extended to a string-to-language mapping. By identifying a singleton language $\\{x\\}$ to the string $x$, morphisms are seen as special case of substitutions.

A letter-to-letter morphism is sometimes called a coding.
> 5 votes

---
Tags: formal-languages, formal-grammars, closure-properties
---


# Question
Title: What are the examples of the easily computable "wild" permutations?
I am looking for the function $y=f(x)$ that would map the integer interval $\[0,n)$ into itself $\[0,n)$. The function must be bijective, so it is a permutation of n elements. It should "randomize" the input variable, ie.

* for every $x\_1$ and $x\_2$ that are close $|x\_1 - x\_2| \< 100$ the outputs of the function should differ very much $|f(x\_1) - f(x\_2)| \> n/{100}$
* changing any digit in the input should change most of digits in the output
* Shannon's Confusion and diffusion: http://en.wikipedia.org/wiki/Confusion\_and\_diffusion
* There should be very little or no fixed points (for every $x$: $f(x) \neq x$).

or any combination of the above conditions.

I don't need the inverse function. It should also be easy to compute from the closed form expression (a maximum of a few thousands simple computer operations like addition, multiplication, modulo etc.) for $n=10^{100}$.

I found some examples in Google:

1. Linear congruential generator. Equation:

$X\_{n+1} = (aX\_n + c) \mod m$

Wikipedia states that: "Provided that the offset $c$ is nonzero, the LCG will have a full period for all seed values if and only if:

* $c$ and $m$ are relatively prime,
* $a - 1$ is divisible by all prime factors of $m$,
* $a - 1$ is a multiple of 4 if $m$ is a multiple of 4.

I've tried using another function $f(x) = (ax + c) \mod m$, because I wanted to get rid of the recursion, and as long as $m$ is prime and $a \ge 1$ I get the permutation. However the result is not that "wild" or "chaotic" as I expect it to be.

2. Minimal perfect hash function

The concept is similar to what I'm looking for, but if I understand correctly the computation of this kind of function is very complicated and time-consuming and it cannot be expressed in a closed form as a simple expression for $n=10^{100}$.

3. Substitution-permutation network

I am not sure how to apply S-boxes and P-boxes to the interval \[0,n), but maybe it could be used.

The question is: Could you give me some examples of functions that satisfy the above conditions (or some pointers like the mathematical term for the object I am looking for)?

# Answer
Yes, such things exist. They have been studied in the cryptographic literature: the key name is "format-preserving encryption".

To learn about this subject, I suggest taking a look at https://en.wikipedia.org/wiki/Format-preserving\_encryption and https://crypto.stackexchange.com/q/16561/351 and https://crypto.stackexchange.com/q/504/351 and https://crypto.stackexchange.com/q/20035/351 and https://crypto.stackexchange.com/q/18988/351 and https://crypto.stackexchange.com/questions/tagged/format-preserving. You could also construct a suitable block cipher yourself using a Feistel construction, but it's probably better to use a standard scheme that has been analyzed in the literature.

There are many constructions. The best one will depend on the specific value of $n$ in your application. Take a look at the schemes in the cryptographic literature, then if you have a more specific question about how to use one of those schemes, you can ask either here or on Crypto.SE.
> 3 votes

---
Tags: cryptography, hash, one-way-functions
---


title: Approximating the diameter of graph G

text:
# Question
Title: Approximating the diameter of graph G
Anyone has an idea how to solve this problem:

Let G be an undirected, unit-weighted connected graph. Design a linear-time algorithm to obtain a 2-approximation of the diameter of G. I.e., the largest shortest-path distance between a pair of vertices of G.

I thought about running BFS from an arbitrary node, in the worst case it should be half of the graph diameter (radius), but how can I prove it?

Thanks.

# Answer
Constructing a breadth-first tree is the correct way to go. This gives you the running time of $\Theta(n+m)$ where $n$ is the number of vertices and $m$ the number of edges respectively.

One of the central facts needed is that a breadth-first tree $T$ rooted at vertex $r$, in an \[undirected,\] unweighted (equivalent to unit weight) graph $G$ is also a *shortest path tree*. That is, for every vertex $v$, the length of the shortest path between $r$ and $v$ in $G$ is equal to the length of the path from $r$ to $v$ is $T$.

So we pick (arbitrarily) a starting vertex $r$, and construct our tree $T$. What does this tell us about the diameter of $G$?

* The diameter is the length of the longest shortest path, so any shortest path provides a lower bound for the diameter.
* If $v$ is the furthest vertex from $r$ in $T$ (and hence in $G$), at distance $d(r,v)$ then $d(u,w) \leq 2\cdot d(r,v)$.

Thus the length of the longest shortest path is between $d(r,v)$ and $2\cdot d(r,v)$. That is, the diameter $D$ is at least $d(r,v)$, thus $2\cdot D \geq 2 \cdot d(r,v)$. Which gives our factor two approximation.

You can make it a little tighter (sort of) and take the two longest distances $D'$ and $D''$ from $r$ in $T$. Without loss of generality assume $D' \leq D''$. Then $D'' \leq D \leq D'+D'' \leq 2\cdot D''$. The worst case is that $D' = D''$, so we don't prove anything further though.
> 4 votes

---
Tags: algorithms, graphs, approximation
---


# Question
Title: Why don't we use simple binary values to compress data?
In Huffman's algorithm, we form a tree and than replace each character with the tree value of 1 and 0. Why don't we simply use the binary digits like $a=0$, $b=1$, $c=10$, $d=01$, $e=11$ and so on than replace them with the characters and when decompressing aplly the reverse and replace the binary digits with the alphabets?

# Answer
Suppose we code, as you suggest, $a=0$, $b=1$, $c=10$, $d=01$, $e=11$, etc., and I send you the message $1001$. You can't tell if I said $10\\,0\\,1=cab$, $1\\,0\\,01=bad$. The point of the Huffman scheme is that it's a prefix code, so it's uniquely decodable (and, further, you can always decode the start of the message based on the bits you've already seen, without having to look into the future).
> 8 votes

---
Tags: data-compression
---