# Question
Title: Using Loop Dependence analysis for vectorization
How exactly Loop Dependence Analysis helps in vectorization ? Are there any standard rules of safety criterias for parallizing such loops ?

# Answer
I found a few resources which helped me to understand the more complex algorithms for use of loop dependence analysis.

The basic way in which the result from Loop Dependence Analysis is utilized is through various tests such as

Dependence Test of various types such as GCD Test, Conservative Test etc. help in determining if the dependency exists and they can further be utilized to test if the Loop Transformation is safe or not.

Following are a few references which helped:

1) http://www.cs.cmu.edu/afs/cs/academic/class/15745-s09/www/lectures/lect6-deps.pdf

2) http://www.cs.utsa.edu/~qingyi/cs6363/slides/Ch02Dependence.pdf

3) http://www.cs.arizona.edu/~collberg/Teaching/553/2011/Handouts/Handout-33.pdf
> 1 votes

---
Tags: compilers, parallel-computing, program-optimization
---


# Question
Title: Polynomially related lengths under two different encodings
I'm reading through `"Computers and Intractability: A guide to the Theory of NP-Completeness" by Michael R. Garey and David S. Johnson, p. 20` and I came across this concept of a function that is polynomially related to input lengths obtained using some encoding scheme. Let $$Len:D\_{\Pi}\rightarrow \mathbb Z^+$$ be a function that maps instances $\in D\_{\Pi}$ (the set of instances of decision problem $\Pi$) to positive integers (lengths). Let $x$ be the string obtained from $I\in D\_{\Pi}$ under some encoding $e$. If there exist polynomials $p$ and $p'$ such that $$Len(I) \le p(|x|)$$ and $$|x| \le p'(Len(I)),$$ We say that $Len$ is polynomially related to the input lengths obtained by the encoding $e$. I cannot digest that; my understanding is that two encodings are polynomially related if converting from one another requires a polynomial amount of time. Can anybody clarify things a bit?

# Answer
> 4 votes
Garey and Johnson are referring to the fact that any encoding scheme for some instance $I$ of a problem $\Pi$ will only differ in length (i.e. number of bits) by a polynomial amount. For example, consider two possible ways to encode a graph: adjacency matrix, and adjacency list.

It is not possible to obtain a super-polynomial speedup by using one encoding over another for various instances of problems. Again, this notion relies on the fact that encodings are *reasonable*. That is to say, we are not unnecessarily padding our encoding with some "junk" information.

---
Tags: complexity-theory, polynomial-time, encoding-scheme
---


title: Predicate Logic Paradox

text:
# Question
Title: Predicate Logic Paradox
> **Possible Duplicate:**
> Negation of nested quantifiers

The problem is:

∃x∀y(x ≥ y)

With a domain of all real positive integers.

The negation is:

∀x∃y(x \< y)

so, if y = x + 1

the negation is true.

That means the negation of the negation (or, the original problem) is false.

My question is, that if the original problem is ∃x∀y(x ≥ y), why can't x = y and prove the problem true?

# Answer
Your base predicate states that there exists some real number that's larger than or equal to all other real numbers (i.e that *there is a highest real number*).

The inverse states that every real number has a number larger than it (i.e. that *there is no highest real number*).

Your test cases don't produce a paradox because feeding `x=y` into the first predicate means that you're no longer working with R+. If all you have in your test set is a single number, then of course there's a maximum value. All you show with this test is that:

**In a set containing a single real number, there exists a highest value**

All that having been said, I'm sure you'll get a better answer on math.stackexchange.com!
> 0 votes

# Answer
This question was answered by M. Alaggan at cs.stackexchange. Below is the original answer:

"I'll start with your last question (in the comments); namely "Why doesn't x = y satisfy the initial problem".

The answer is in the quantifiers. Read from left to right. It starts with "there exists" X. So pick an X in your head. Say X = 5. We can not pick Y here because it doesn't have a value yet and we MUST pick a value for X NOW. Now proceed to read the next quantifier which reads "for all Y". Oops. We can't say for all Y because we already set Y = X.

Actually if you are going to look for a solution that satisfies the original formula, it should be of the form "X=(some positive integer)", with Y not involved at all, as it is a bound variable (as opposed to being a free variable which we can choose).

However, the formula says "there is a (single, and specific) positive integer X which all integers are less than or equal to it" which is clearly false because given any positive integer X, X+1 is a positive integer which is not less than nor equal to it (which is what the negated formula says!)."

shareedit answered 9 hours ago

M. Alaggan 1614
> 0 votes

---
Tags: logic, discrete-mathematics
---


# Question
Title: Using a step-counting function in a Turing Machine construction
I have an question relating to the elementary foundations of Turing Machine theory. I would like to have a clarification of the status of a function $\phi$ (a mapping between TM indexes) I shall introduce in the formal question after the preamble. First to the preamble.

Let us assume that we have a fixed Turing Machine language and corresponding Universal Turing Machine. Thus ${TM\_i}$ is an enumeration of machines, with UTM say as the Universal Machine in that enumeration. Let us also introduce a numerical parameter **c** for this example: (for example **c** = 500).

Now execution of any TM can be simulated on UTM.

**EDIT (Explaining notation)** I am using some notation in this question which I shall outline here. Let S be an arbitrary input string for TM, then I shall write:

$$UTM(TM\_i; S)$$

to indicate that $TM\_i$ is using S as its input. So we will have the equation: $$UTM(TM\_i; S) = TM\_i(S)$$ since UTM is Universal, and its purpose is simply to simulate TMs on their input. If S is a composition of x,y I shall write: $$UTM(TM\_i;x,y)$$

(End notation discussion.)

Let us modify UTM to UTM2 (and using the above notation) with the following property when a given $TM\_i$ is executed on UTM2:

$UTM\_2(TM\_i;c,x) = UTM(TM\_i;c,x) = TM\_i(x)$ if $TM\_i$ requires **c** steps or less to compute the output

$UTM\_2(TM\_i;c,x)=0$ if $TM\_i(x)$ requires at least **c** steps for computation

**EDIT** The original question with this second condition has been answered. In this edit I would like to modify the condition to the following (introducing UTM3 which also meets the first condition):

$UTM\_3 (TM\_i; c, x) = \[s\]$ if $TM\_i (x)$ requires at least **c** steps for computation.

In this expression \[s\] is the string on the tape which results after **c** steps of computation by $TM\_i$ on Input. (EDIT The corresponding state of $TM\_i$ will not be a Final state (ACCEPT or REJECT), but just an arbitrary state $q\_j$. This is because UTM3 stops executing after **c** steps, ignoring the Turing Machine convention requiring termination only in Final states.) As a result (almost) all input strings x, including those with |x| \> c will be modified (in a maximum of c string positions) - expressed in Language terms many such strings will just have their ACCEPTANCE calculation prematurely terminated in a non-Final state - but some strings of arbitrary length will still be ACCEPTED by some Turing Machines in less than **c** steps (IE those for which ACCEPTANCE requires examining less than the first **c** terms.)

So under UTM2/3 the output is determined partly by a (hidden) step counting function. Here UTM2/3 has taken on some of the role of an operating system, by monitoring the actual steps taken by the simulated machines, and using some step-counting variable to behave as above.

(EDIT: We show below that UTM2/3 is a Universal Machine)and so capable of *executing* any TM - on any argument - it is provided with, at least as far as **c** steps. Despite this limitation I believe that an infinite number of (TM,input) pairs will result in a non-zero output. So most TMs executed on UTM2/3 will not behave as they do on UTM. In UTM3 the outputs will explicitly depend on x,i and c.(End preamble.)

The question is whether any given $TM\_i$ can be modified into $TM\_{\phi (i,c)}$ with the property that (generalising to arbitrary c):

$UTM\_3(TM\_i; c, x)$ = $UTM (TM\_{\phi(i,c)}; x)$ (for all $x$ and $c$)

**EDIT2\phi** Both questions for the $\phi(i,c)$ have been answered. For reasons discussed below I want to modify the definition to $\phi(i)$. This new definition is:

$UTM\_3(TM\_i; c, x)$ = $UTM (TM\_{\phi(i)}; c,x)$ = $TM\_{\phi(i)}(c,x)$ (for all $x$ and $c$)

This condition is meant to ensure that $TM\_{\phi (i)}$ is a correct simulation of $TM\_i$. The specific questions to be proven about $\phi: (i) \rightarrow i$ are: (i) Is $\phi$ well defined and non-trivial; (ii) Is $\phi$ recursive; (iii) Is $\phi$ non-recursive?

In the LHS of the above definitions c is an input, which is ignored by $TM\_i$ but used by UTM3 to determine the stopping stage. Asking for $\phi(x,c)$ made this a *fixed* parameter built into the definition of $TM\_{\phi(x,c)}$. However the correct UTM simulation will be given **c** as in the modified equation RHS. This parameter needs to be used by $TM\_{\phi(i)}$ along with its own input x, to construct the correct simulation. (EDIT) Of course since the UTM is a regular Universal Machine it simply simulates the execution of $TM\_{\phi(i)}$ - the parameters on *its* tape - like **c** \- are meant for its TM's only.

Note that a special symbol **u** could be introduced switching off the UTM3 counts, and so

$$UTM3(TM\_i;u,x) = UTM(TM\_i;u,x) = TM\_i(x)$$

Also the same problem can be formulated for the original UTM2 (with modified $\phi$).

This question is a simplification of a problem I am trying to understand (I am a math but not a CS major, but have some textbooks like Hopcroft/Ullmann), and I hope that I can get some clarification on this piece.

# Answer
The answer is yes.

A possible quick approach: UTM2($TM\_i$,c,x) $\neq 0$ only on $|x| \leq c$ so you can build $TM\_{\phi(i,c)}$ simply simulating $TM\_i$ on all inputs and hard encoding its output on the finite input strings $|x| \< c$, the index of the resulting TM is the value of $\phi(i,c)$

**EDIT2**: another approach that can work to simulate tape content (UTM3 in your last edit) is the following:

* from $TM\_i$ build $TM\_{\phi(i,c)}$ using $|Q|\*c$ states, where Q is the set of states of $TM\_i$.
* every $(q\_j,a) \rightarrow (q\_k,b,L)$ transition of $TM\_i$ is mapped to $c$ transitions on $TM\_{\phi(i,c)}$ in this way: $(q\_j^m,a) \rightarrow (q\_k^{m+1},b,L)$ with $(1 \leq m \leq c-1)$
* make state $q\_j^m$ accepting if the corresponding $q\_j$ in $TM\_i$ is accepting

This guarantees that $TM\_{\phi(i,c)}$ runs exactly for $c$ steps and the tape content is the same of $TM\_i$
> 3 votes

---
Tags: complexity-theory, computability, turing-machines
---


# Question
Title: Is there a repository for the hierarchy of proofs?
I am self-learning proof assistants and decided to start on some basic proofs and work my way up. Since proofs are based on other proofs and so form a hierarchy, is there a repository of the hierarchy of proofs?

I know I can pick a particular proof-assistant and analyze its library to extract its hierarchy, however if I want to find the next proof in a chain to prove, I can't when it is not in the library.

In my mind I picture a graph, probably a DAG, of all of the known mathematical proofs that can be expressed using English statements, not proofs using pictures. This would be the master map (a map in the sense of starting at one point and traveling to another point via intermediate points), and for a particular proof assistant, one would have a subgraph of the master map. Then if one wanted to create a proof using a proof assistant found on the master not on the subgraph, by comparing the two graphs one could get an idea of the work needed to create the missing proof(s) for the proof assistant.

I am aware that mathematical proofs are not necessarily easily convertable for use with a proof assistant, however having a general idea of what to do is much better than none at all.

Also by having the master map, I can see if there are mulitple paths from one point to antoher and choose a path that is more amenable for the particualr proof assistant.

EDIT

In searching I found something similar for mathematical functions. I did not find one for proofs at the NIST

# Answer
The Mizar system is a huge repository of math proofs. See the wikipedia page and the official website.

> of all of the known mathematical proofs that can be expressed using English statements

From wikipedia/Mizar\_system#Mizar\_language:

> The distinctive feature of the Mizar language is its readability

Proofs are written as articles, of which there are more than a thousand articles, and more than 50,000 proven theorems. The wikipedia page mentions some interesting ideas of the "QED manifesto", and how Mizar might be on its way to accomplishing this.
> 11 votes

# Answer
ProofWiki contains a decent amount of proofs from various areas of mathematics. It is by no means complete, but is a good starting point for what you want.
> 9 votes

# Answer
Metamath has a large selection of proofs, built right up from their core in propositional logic.

That said, it is painfully lacking in terms of CS theory. Feel free to expand it!
> 8 votes

# Answer
See the TPTP archive, Thousands of Problems for Theorem Provers. It is somewhat standard in the field. This is more the "nodes" of the theorem graph you are asking about. Some papers referring to the archive may have explored the edges in this graph.

Note that in the field of ATM, automated theorem proving and assisted theorem proving, the proofs are symbolic and it's not really feasible or plausible to study "proofs in the English language" as you visualize.

However you might learn about Richard's paradox which started out as a language formulation and was later formalized symbolically. It is said to be the inspiration for "antimonies" (contradictions) found in early set theory which historically even paved the way to Gödel's incompleteness theorem.
> 4 votes

---
Tags: reference-request, logic, proof-assistants
---


# Question
Title: Value of constants in Big Theta notation
In Big Theta notation used for defining the running time of an algorithm, are the constants $c\_1$ and $c\_2$ *different* for every value of $n$?

Definition:

$\qquad \displaystyle \Theta (g(n)) = \\{ f(n): \exists\\, c\_1,c\_2,n\_0\>0. \forall n \geq n\_0.\ \ c\_1g(n) \leq f(n) \leq c\_2g(n) \\}.$

# Answer
No, the constants $c\_1,c\_2$ are the same for all values of $n$. If they could depend on $n$ then the definition would be meaningless since $\Theta(g(n))$ would contain all positive functions. Indeed, suppose $f,g$ are two positive functions. Then for all $n$, $$c\_1g(n) \leq f(n) \leq c\_2g(n) \text{ for } c\_1 = c\_2 = \frac{f(n)}{g(n)}.$$
> 10 votes

# Answer
Actually the answer lies already in your question. You write:

> ... are the constants $c\_1$ and $c\_2$ different for every value of $n$?

A quantity $c$ is a *constant* only if its value is unaffected by changes to the asymptotic variable (i.e. $n$). Therefore, $c$ must have the same value for all values of $n$.
> 2 votes

# Answer
Read the notation aloud. "There exist constants $c\_1, c\_2$ that are greater than $0$ such that for all $n$ greater than some $n\_0$, $c\_1g(n)$ is less than or equal to $f(n)$ and $f(n)$ is less than or equal to $c\_2g(n)$.

Hence, $c\_1$ and $c\_2$ are constants that apply for all $n \> n\_0$.
> 0 votes

---
Tags: terminology, asymptotics, mathematical-analysis, landau-notation
---


# Question
Title: Impossibility condition in the Byzantine Generals problem
I am unable to understand why there is a requirement of 3m+1 generals overall given m traitors. As per my understanding, the steps are as follows:

1. Each general decides a strategy and forwards their strategy to all the other ($3m$) generals.
2. Each general forwards a vector containing the strategies (of all the other generals they received) to all the generals ($m$)
3. Now, each general has a list of vectors corresponding to the vote made by each general and using a majority criteria (majority vote) decides each general's strategy and thus, the strategy that it itself chooses.

If there are $3m+1$ generals then, with $m$ (loyal) generals choosing to 'attack' and $m+1$ (loyal) generals choosing to 'defend' and $m$ traitors, then since every loyal general forwards the message correctly, each of the $m$ 'attacking' generals will receive $m-1 + m$ (from the other 'attacking' generals and the $m$ 'defending' generals) confirmations of attack for all the other $m-1$ 'attacking' generals, similarly $m-1 + m$ confirmations of 'defend' for the strategy adopted by each one of the defending generals. The traitors however can alter either by sending whatever they'd like (different bits) to the attackers and the defenders \[send `d` for all the defenders and `a` for all the attackers, but send conflicting values — `d` to the defenders and `a` to the attackers — for all the traitors' values\], thus making them follow a different plan (defenders will defend, while attackers will attack).

This can't be right, because all the papers and presentations I've gone through state that $3m+1$ with only $m$ traitors will definitely give you the correct solution (all loyal generals follow the same plan). Can anybody go through my understanding, find the flaw and re-explain it to me?

Also, I have understood the $m = 1$ example, it would be nice if someone could explain to me how it fails when $m = 2$ and there are 6 generals and how it succeeds if $m = 2$ and there are 7 generals... I've tried a lot and am stuck.

# Answer
> all the papers \[...\] state that $3m+1$ with only $m$ traitors will *definitely* give you the correct solution

They should actually state that when $3m+1$ then correct algorithms *exist*, but not all algorithms are correct.

Algorithms are like cooking recipes (in fact recipes are algorithms): Consider the problem of baking bread. There are books that tell you that you require flour, water and yeast (or similar). But not every recipe of the three will at the end resemble bread. Consider this one: Mix a spoon yeast, a spoon of flour and 5 litres of water, fill in glasses and refrigerate overnight, serve cold... Definitely not bread ;-)

What your example shows is that the algorithm given in 1),2),3) is not one that solves the Byzantine Generals problem. (Note that it is well known that a correct algorithm will (in the worst case) need at least m+1 rounds.)

**Answer to original question on CSTheory:**

I think your miss-conception lies in the assumption

> m+1 loyal generals should vote the same way

Why should this hold?

Assuming you are talking about the problem as defined in LSP82: For simplicity let's set $m=1$. Then with just $2m+1=3$ generals you have one commanding general and two lieutenant generals. When the commanding general is correct, he and the correct general will vote the same way. So in this case your assumption holds. But what if the commanding general himself is Byzantine? Then he can give different instructions to the two correct (lieutenant) generals, and they are no longer guaranteed to vote the same way.

In general, if the proposer/commanding general is faulty then there is no way to guarantee that all correct processes will vote in the same way.
> 1 votes

---
Tags: distributed-systems, fault-tolerance
---


title: Complexity inversely propotional to $n$

text:
# Question
Title: Complexity inversely propotional to $n$
Is it possible an algorithm complexity decreases by input size? Simply $O(1/n)$ possible?

# Answer
> 12 votes
Consider an algorithm with some running time bounded by $f(n)$ and suppose that $f(n) \in O(1/n)$. That means that there is some constant $c$ such that for sufficiently large values of $n$, it holds that $$f(n) \leq c\frac{1}{n}.$$ Clearly, for any fixed $c$ and sufficiently large $n$, the right side will be strictly less than $1$, which requires $f(n)=0$, since $f$ maps to $\mathbb{N}$. In my understanding, even an algorithm that immediately terminates, takes at least $1$ step (namely to terminate), i.e., $\forall n\colon f(n)\ge 1$. So no such algorithm can exist.

# Answer
> 2 votes
Bucket sort's insertion sort step is O(1/n) on average.

Reference - CLRS Section 8.4

```
BUCKET-SORT(A)
1 n ← length[A]
2 for i ← 1 to n
3     do insert A[i ] into list B[nA[i ]]
4 for i ← 0 to n − 1
5     do sort list B[i ] with insertion sort
6 concatenate the lists B[0], B[1], . . . , B[n − 1] together in order

```

$T(n) = \theta(n) + \sum\_{i=0}^{n−1} O(n\_{i}^{2})$

Taking expectations of both sides and using linearity of expectation, we have

$E\[T(n)\] = \theta(n) + \sum\_{i=0}^{n−1} O(E\[n\_{i}^{2}\])$

It is proved that $E\[n\_{i}^{2}\] = 2 − 1/n$

Hence step 5 takes $2 - 1/n$ time. Overall complexity of bucket sort is

$\theta(n) + n\cdot O(2 − 1/n) = \theta(n)$.

# Answer
> 2 votes
By definition, all functions (even the trivial) must perform at least 1 operation. It is impossible to perform half of a step; computers are discrete machines, and work incrementally. As such, the complexity $\Omega(1)$ is the lower time bound of all computational operations. In addition, for any operation accepting any N inputs, it must deal with at least a constant number of them at once (even if that number is zero). It's impossible to start at using one unit of space and halve that space infinitely; at some point your algorithm will reach the atomic unit of space for the computation (one bit, one electron, one string, whatever) and from that point you will use either zero or one of those atomic units, thus arriving at a constant base case. Thus, $\Omega(1)$ is also the lower space bound of all algorithms.

Now, it is possible, trivial even, for an algorithm to produce an output on that order of magnitude or cardinality. Given N elements, you can return 1/N of them (`array[x]` produces an output 1/N the size of the input `array`). But, this takes constant time (calculate the location of the element by offsetting the address of the array by the number and size of its elements, and return the bits beginning at that offset and continuing for sizeof(elementType)).

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


# Question
Title: How much can we reduce the number of clauses by converting from $k$-SAT to $(k+m)$-SAT?
If we suppose that we start with an instance of $k$-SAT, and try converting the problem to an instance of $(k+m)$-SAT, where there are $(k+m)$ literals per clause, can we guarantee a reduction in the total amount of clauses?

*I realized after posting that we can't guarantee that the number of clauses can be reduced. However, I wonder if we have $n$ clauses, could we get something like $n/k + O(1)$ clauses by some "reduction" technique?*

If so, how much can we guarantee the total number of clauses can be reduced by? For instance, if we start with $k$-SAT with $n\_k$ clauses, what is the smallest guaranteed $n\_{k+m}$, the new amount of clauses, that will result if we convert this instance to $(k+m)$-SAT?

More importantly, how do we carry out this conversion?

# Answer
> 5 votes
One type of conversion is simply the reverse of the k-sat-to-3-sat conversion:

**Recall, the conversion of k-sat to "j"-sat, $j\<k$:**

$$\begin{eqnarray\*} && (x\_1 \vee x\_2 ... \vee x\_j \vee ... \vee x\_k)\\ \rightarrow && (x\_1 \vee x\_2 ... x\_j \vee d) \wedge (\overline d \vee x\_{j+1} \vee x\_{j+2} ... x\_k)\\ \end{eqnarray\*}$$

Here, $d$ is a dummy variable, which means something like "This clause isn't true, but another clause I know is". The other clause being the next clause that was split off of the original. The above is an example where $2j \geq k$, otherwise the 2nd split node will still be larger than $j$, and we must split that one again, in the same way.

**Reversing the conversion**

$(x\_1 \vee x\_2 ... x\_j) \wedge (\overline x\_j \vee x\_{j+1} \vee ... x\_k)$ then you can combine the clauses into:

$(x\_1 \vee x\_2 ... x\_{j-1} \vee x\_{j+1} \vee x\_{j+2} \vee ... x\_k)$

Notice the missing $x\_j$ in this new formula.

Of course, you aren't *guaranteed* to find clauses like this in an arbitrary formula so the smallest guaranteed $n\_{k+m}$ is equal to $n\_k$.

However, on ordinary formulas, a variable and its negation will appear in the formula; otherwise you can perform pure-literal-elimination (described here). For simplicity, lets also assume that $k+m \geq 2k-2$. Then we can combine any two clauses that contain a literal in one and its negation in the other. Since every literal should have another clause with a negation, one can empirically guess that you should be able to approximately halve the number of clauses (you might get stuck with some literals and their negations in already joined clauses, and thus you will be stuck with some unjoinable clauses at the end; optimally joining clauses like this might be another interesting problem).

**EDIT:**

After reflection, I realized that $x\_j$ must be free and not used elsewhere in the formula in order to collapse the two clauses that it belongs to. Therefore, these type of clauses (one containing a literal, and the other its negation, with this literal not being used elsewhere in the formula) is much rarer than I previously thought above. So the real answer is, there is no guarantee of how much we can reduce the number of clauses in the formula.

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


title: Converting function to bitwise only?

text:
# Question
Title: Converting function to bitwise only?
I have a function to count upper bits of a 32 bit value. So if a number is 11100011111..., the result is 3 as there are 3 ones in the most significant place before a 0 is hit.

I need to convert the function to use only bitwise operations (no if statements or while loops) and the total number of operations should be lesser than 50.

Question: How can this be converted to bitwise operations only while keeping less than 50 ops?

Here is the Code:

```
  int count = 0;
  int i = 28;

  while(i >= 0) {
    int temp = (x>>i) & 0xF;
    i-=4;
    if(temp == 0xF) count+=4;
    else {
      int mask = 0x1;
      int a = (temp>>3) & mask;
      int b = (temp>>2) & mask;
      int c = (temp>>1) & mask;
      int d = temp & mask;

      if (a != 1) break;
        count+=1;
      if (b != 1) break;
        count+=1;
      if (c != 1) break;
        count+=1;
      if (d != 1) break;
        count+=1;
    }

```

# Answer
<sub> Notations: I'll use the C notations for bitwise operations: $a \mathbin\\& b$ (bitwise and), $a \mathbin| b$ (bitwise or), $a \mathbin\ll b$ (shift left), $a \mathbin\gg b$ (shift right). The shift operators are left-associative (e.g. $x \mathbin\gg m \mathbin\gg n = (x \mathbin\gg m) \mathbin\gg n$). The shift operations put zeroes in newly created bit positions: $a \mathbin\ll b = a \times 2^b$ and $a \mathbin\gg b = \lfloor a \times 2^{-b} \rfloor$. Sequences of digits with a line above (e.g. $\overline{11101000}$, $\overline{z^4z^3z^2z^1z^0}$) represent a number written in base 2 (binary). </sub>

<sub> If $x$ is an integer between $0$ and $2^N-1$, we say that $x$ is an $N$-bit number, and write $x = \overline{x^{N-1}x^{N-2}\ldots x^1x^0}$, i.e. $x^k$ is bit $k$ of $x$. Bits $k-1$ through $0$ constitute the $k$ least significant bits of $x$, and bits $N-1$ through $N-k$ constitute the $k$ most significant bits of $x$ (where $x$ is considered as an $N$-bit number). </sub>

---

### Intuition

With 32 bits and 50 operations, an approach that looks at one bit of the input at a time isn't going to work. The next obvious thing to try is a recursive (dive-and-conquer approach) where you work on half the bits at a time. There are two simple ways to divide an $N$-bit number: into the $N/2$ most significant bits and the $N/2$ least significant bits, or into odd and even positions. Most/least significant looks promising, because the result counts how many most significant bits are 1.

Or we could approach the problem the other way: the result is a number between 0 and 32, a 6-bit number (for all but one input values, it's a 5-bit number). Can we find the bits of the result, one at a time?

Let $a$ be the input (a 32-bit number) and $z$ the output. Bit $5$ of $z$ is 1 iff $a$ is all-bits-1. Bit $4$ of $z$ is 1 iff the 16 most significant bits of $a$ are all 1 and $a$ is not all-bits-1. What about bit $3$? We have to discriminate on bit $4$: if it's 0, we look at the $8$ most significant bits of $a$ (with an exception when $a$ is all-bits-1); if it's 1, we look at bits $8$ through $15$ instead.

### Expression in terms of bitwise operations

Let's express this in terms of bitwise operations. For the time being, assume we have a primitive operation $A\_N$ on $N$-bit numbers such that $A\_N(x) = 1$ if $x = 2^N-1$ (i.e. $x$ is all-bits-1) and $A\_N(x) = 0$ otherwise.

* $z^5 = A\_{32}(a)$
* if $z^5 = 0$ then $z^4 = 0$, else
$z^4 = A\_{16}(a \mathbin\gg 16)$
* if $z^5 = 0$ then $z^4 = 0$, else
if $z^4 = 0$ then $z^3 = A\_8(a \mathbin\gg (16+8))$, else
$z^3 = A\_8((a \mathbin\\& \overline{1111111100000000}) \mathbin\gg 8)$

That's not very orderly: at this point we're looking to express $z^4$ and $z^3$ in similar way so that a recursion pattern can emerge. Furthermore we've used conditional statements which we're going to have to eliminate somehow. What seems constant is that $z^k$ is $A\_{2^k}$ of some number. So what number? At each stage, we cut some number which is a slice of $a$ in half. To compute the next bit of the result we're looking at the most significant half of one of the halves from the previous step. Let's write $a\_{k+1}$ for the input to the step that computes $z^k$ (so that we start with $a\_6 = a$ to compute $z\_5$). Then, leaving aside for a moment the case when $a = 2^{32}-1$ (in other words, we leave aside the case when $z^5=1$):

* $a\_5 = a\_6$
* $z^4 = A\_{16}(a\_5 \mathbin\gg 16)$
* If $z^4 = 1$ then $a\_4 = a\_5 \mathbin\\& (2^{16}-1)$, else $a\_4 = a\_5 \mathbin\gg 16$. It's awfully tempting to turn that 16 into $z^4 \mathbin\ll 4$, but it's on the wrong side. We could flip a bit (using xor), but this complicates the expression; instead, let's shift the other way: $a\_4 = (a\_5 \mathbin\\& (2^{16}-1)) \mathbin\ll (z^4 \mathbin\ll 4) \mathbin\gg 4$.

And thus a pattern emerges: $$\begin{align\*} z^k &= A\_{2^k}(a\_{k+1} \mathbin\gg 2^k) \\ a\_k &= (a\_{k+1} \mathbin\\& (2^{2^k}-1)) \mathbin\ll (z^k \mathbin\ll k) \mathbin\gg k \\ \end{align\*}$$

### A simpler recursion

The initial case $z^5$ isn't right. It would be a simple matter to adjust the recursion pattern to accommodate it, but before doing that, I prefer to tweak the notation to reduce the number of shifts. When we compute $a\_k$, we're aligning the extracted number to the right. Let's instead align to the left. Furthermore, let's drop the masking: we'll use a new predicate $B\_m$ instead of $A\_m$ which looks only at the appropriate bits. Define $$ b\_{k-1} = b\_k \mathbin\ll (z^k \mathbin\ll k) $$ Define $B^n\_m(x) = 1$ if the $2^n$-bit number $x$ has its $m$ most significant bits all set, and $B^n\_m(x) = 0$ otherwise. $$ z^k = B^n\_{2^k}(b\_k) $$

For a 32-bit number ($n=5$), we start with $b\_5 = a$ and $z^5 = B^5\_{32}(b\_5)$ (check all 32 bits). Next we compute $b\_4 = b\_5 \mathbin\ll (z^5 \mathbin\ll 5)$; when $z^5=1$ (i.e. $a=2^n-1$) that sets $b\_4 = 0$. We can then compute $z^4 = B^5\_{16}(b\_4)$ (look at the most significant 16 bits), then either $b\_3 = b\_4$ or $b\_3 = b\_4 \mathbin\ll 16$ depending on $z^4$, and so on until we find $z^0$.

### Testing for all-bits-1

We're getting close. We still need to express that $B$ function in terms of bitwise operators. Note that so far, we've used 10 operations (2 shifts per step to compute $b\_4$ through $b\_0$). That leaves 40 operations to do the all-bits-1 check.

$B^n\_1$ is easy: take the most significant bit and shift it into place, i.e. $B^n\_1(x) = x \mathbin\gg (2^n-1)$. For $B^n\_2$, we need to and the two most significant bits of $x$ together: $B^n\_2(x) = (x \mathbin\gg (2^n-1)) \mathbin\\& (x \mathbin\gg (2^n-2))$. Going on, we have $B^n\_3(x) = (x \mathbin\gg (2^n-1)) \mathbin\\& (x \mathbin\gg (2^n-2)) \mathbin\\& (x \mathbin\gg (2^n-3))$. A recursive pattern emerges, but it's expensive: one shift and one and per bit. Linear is too slow, we need to go exponential.

Above we were taking the and of a single bit at a time. This is a waste: we can operate on $2^n$ bits in one go. Take $x$, shift left by $m$ and and with $x$: the result has its $m$ most significant bits all-1 iff $x$ has its $2m$ most significant bits all-1. Or in other words: $$B^n\_{2m}(x) = B^n\_m(x \mathbin\\& (x \mathbin\ll m))$$ Recall that $B^n\_1(x) = x \mathbin\gg (2^n-1)$. We can compute $B^n\_{2^k}$ in $2k+1$ operations. Thus we can compute $z^k$ from $b\_{k+1}$ in $2k+1$; for $z^0$ through $z^n$, that's a total of $\sum\_{k=0}^n (2k+1) = (n+1)^2$ operations.

### Optimizing some shifts

We have a complete algorithm now, but it's a bit slow, we need to do a little optimization. Notice that we only ever use $z^k$ in the expression $z^k \mathbin\ll 2^k$. So instead of computing $z^k$, we'll directly compute that bit at its final position: $$y\_k = z^k \mathbin\ll k = \hat B^n\_{2^k}(b\_k) \mathbin\\& (1 \mathbin\ll k)$$ where $\hat B^n\_{m}(b\_k)$ is computed as described above for $B^n\_{2^k}(b\_k)$, except that for the last shift (resulting from the expansion of $B^n\_{1}(c)$ for some $c$), instead of taking $c \mathbin\gg (2^n-1)$, we take $c \mathbin\gg (2^n-1-k)$. Note that $b\_{k-1} = b\_k \mathbin\ll y\_k$.

The cost so far:

* one operation per result bit except the most significant one to compute $b\_k$ (one shift) → $n$
* 1 operation per result bit except one to or everything together ($z = y\_5 \mathbin| y\_4 \mathbin| \ldots \mathbin| y\_0$) → $n$
* $(n+1)^2$ operations to compute the $B^n\_{2^k}(b\_k)$ values as seen above, plus one more to get $\hat B^n\_{2^k}(b\_k)$. That's one shift plus one and, times $(k+1)$ for each $k$, with $k$ ranging from $0$ to $n$. → $(n+1)(n+2)$

The total is $C(n) = (n+1)^2 + 3n + 1$ operations. For $n=5$, that's 52. We're almost there!

### Further optimizations in the last steps

Let's see the last few operations once we get to $b\_1$ (given here with $n=5$ as an example, but you can generalize to any $n \ge 2$). $$\begin{gather\*} c\_1 = b\_1 \mathbin\\& (b\_1 \mathbin\ll 1) \\ y\_1 = (c\_1 \mathbin\gg 30) \mathbin\\& \overline{10} \\ b\_0 = b\_1 \mathbin\ll y\_1 \\ y\_0 = (b\_0 \mathbin\gg 31) \mathbin\\& \overline{1} \\ \end{gather\*}$$ Let's make this more concrete: let $u = b\_1^{31}$ and $v = b\_1^{30}$ be the two most significant bits of $b\_1$ (i.e. $b\_1 = \overline{uv\ldots}$ as a 32-bit number). We need to obtain $y\_1 = 2$ if $u=v=1$ and $y\_1=0$ otherwise; and $y\_0 = 1$ if $u=1$ and $v=0$ and $y\_0$ otherwise. At this stage, we can save some operations by aligning on the right instead of on the left. We take advantage of the fact that if you right-shift a 32-bit number by 30, you get a 2-bit number. The sequence of operations above can be replaced by the following sequence: $$\begin{gather\*} w = b\_1 \mathbin\gg (2^n-2) \\ y\_1 = w \mathbin\\& (w \mathbin\ll 1) \\ b\_0 = b\_1 \mathbin\ll y\_1 \\ y\_0 = b\_0 \mathbin\gg (2^n-1) \\ \end{gather\*}$$ That's 5 operations instead of 7, bringing us down to 50 for $n=5$, and more generally to $C'(n)=(n+1)^2+3n-1$.

### Remarks

By the way, the computation of $b\_{k-1}$ from $b\_k$ can be done with just two temporary variables. When we obtain $y\_k$, we can or it into an accumulator to obtain $z$. So we can do the whole computation with four $2^n$-bit registers.

---

### Code

Here's the 32-bit case played out in Python syntax. The `ck_j` variables are temporaries used to compute $\hat B^5\_{2^k}(b\_k)$. I used a single-assignment style, you can get a classical imperative program by stripping all number suffixes from the variable names.

```
#!/usr/bin/env python
import sys

# Python does bignum arithmetic, but we absolutely need modulo 2^32 arithmetic
# in a few places.
def trim(x): return x & 0xffffffff
def bin5(x): return bin(0x100000000 | trim(x))[3:]

def f5(a, trail_optimization=True, trace=False):
    (y1, y0) = (None, None) # bring these variables to function scope
    b5 = a
    c5_5 = b5
    c5_4 = c5_5 & (c5_5 << 16)
    c5_3 = c5_4 & (c5_4 <<  8)
    c5_2 = c5_3 & (c5_3 <<  4)
    c5_1 = c5_2 & (c5_2 <<  2)
    c5_0 = c5_1 & (c5_1 <<  1)
    y5 = (c5_0 & (2**31)) >> (31 - 5)
    z5 = y5
    b4 = b5 << y5
    c4_4 = b4
    c4_3 = c4_4 & (c4_4 <<  8)
    c4_2 = c4_3 & (c4_3 <<  4)
    c4_1 = c4_2 & (c4_2 <<  2)
    c4_0 = c4_1 & (c4_1 <<  1)
    y4 = (c4_0 & (2**31)) >> (31 - 4)
    z4 = z5 | y4
    b3 = b4 << y4
    c3_3 = b3
    c3_2 = c3_3 & (c3_3 <<  4)
    c3_1 = c3_2 & (c3_2 <<  2)
    c3_0 = c3_1 & (c3_1 <<  1)
    y3 = (c3_0 & (2**31)) >> (31 - 3)
    z3 = z4 | y3
    b2 = b3 << y3
    c2_2 = b2
    c2_1 = c2_2 & (c2_2 <<  2)
    c2_0 = c2_1 & (c2_1 <<  1)
    y2 = (c2_0 & (2**31)) >> (31 - 2)

    z2 = z3 | y2
    b1 = b2 << y2
    if trail_optimization:
        b1 = trim(b1)
        w = b1 >> 30
        #if trace: print 'w=' + bin5(w)[-2:],
        y1 = w & (w << 1)
        b0 = b1 << y1
        b0 = trim(b0)
        y0 = b0 >> 31
    else:
        c1_1 = b1
        c1_0 = c1_1 & (c1_1 <<  1)
        y1 = (c1_0 & (2**31)) >> (31 - 1)
        b0 = b1 << y1
        c0_0 = b0
        y0 = (c0_0 & (2**31)) >> (31 - 0)
    z1 = z2 | y1
    z0 = z1 | y0
    if trace: print 'b5=' + bin5(b5), 'y5=' + str(y5),
    if trace: print 'b4=' + bin5(b4), 'y4=' + str(y4),
    if trace: print 'b3=' + bin5(b3), 'y3=' + str(y3),
    if trace: print 'b2=' + bin5(b2), 'y2=' + str(y2),
    if trace: print 'b1=' + bin5(b1), 'y1=' + str(y1),
    if trace: print 'b0=' + bin5(b0), 'y0=' + str(y0),
    return z0

if __name__ == '__main__':
    for i in xrange(33):
        x = (1 << 32) - (1 << i)
        print bin5(x), f5(x, trace=True)
        if 0 <= i <= 31:
            x = x - 1
            print bin5(x), f5(x, trace=True)

```
> 7 votes

# Answer
Comments in the codes.

```
#include <assert.h>
#include <stdio.h>

unsigned int should_still_count_next_time[256] = {
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1
};

unsigned int byte_left_ones_count[2][256] = {
  {
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
  },
  {
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
     3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
     4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 7, 8
  }
};

unsigned int countrbits32(unsigned int v)
{

  assert (((0xffffffff | v) == 0xffffffff)
          && "v has > 32-bit value");

  //Split the number into four bytes.
  unsigned char msb0_byte = (v >> 24);
  unsigned char msb1_byte = (v >> 16) & 0xff;
  unsigned char msb2_byte = (v >> 8) & 0xff;
  unsigned char msb3_byte = v & 0xff;

  //This is a flag, for each byte we will count the 1s in the byte,
  //but only if we've not encountered any zeros in a previous byte.
  int still_counting = 1;

  int count = 0;

  //Add the number of ones in this byte.
  //The @c still_counting flag will determine if we actually add
  // anything at all, or if we just add 0.
  //@c byte_left_ones_count[1][*] is a lookup into all numbers in
  // range [0-255] and how many 1s there are on the left.
  //For example, @c byte_left_ones_count[255] == 8, because
  // 255 == 0b11111111 while @c byte_left_ones_count[254] == 7,
  // because 254 == 0b11111110.
  //@c byte_left_ones_count[0][*] = 0. So if @still_counting == 0,
  // this will add nothing to @count.
  count += byte_left_ones_count[still_counting][msb0_byte];

  //If we encounter a 0 in this byte, we should stop counting for
  // future bytes.
  //@c should_still_count_next_time[255] == 1 because 255=0b11111111,
  // and has no zeros. The rest of @c should_still_count_next_time
  // is filled with zeros.
  still_counting &= should_still_count_next_time[msb0_byte];

  //On to the next byte.
  count += byte_left_ones_count[still_counting][msb1_byte];
  still_counting &= should_still_count_next_time[msb1_byte];

  count += byte_left_ones_count[still_counting][msb2_byte];
  still_counting &= should_still_count_next_time[msb2_byte];

  count += byte_left_ones_count[still_counting][msb3_byte];
  still_counting &= should_still_count_next_time[msb3_byte];

  return count;
}

int main(int argc, char**argv)
{
  printf( "countrbits32(0xfff0000a): %d\n", countrbits32(0xfff0000a));

  return 0;
}

```
> 2 votes

# Answer
In order to achieve the goal you need to parallelize the operations:

```
      Input n = 11100010
First group by 2 bits and count:
0 0 -> 00  no leading 1s
0 1 -> 00  no leading 1s
1 0 -> 01  1 leading 1
1 1 -> 10  2 leading 1
This can be done using the following operations:
                  n = 11 10 00 10
               mask = 01 01 01 01
               n>>1 = 01 01 00 01
A = (n >> 1) & mask = 01 01 00 01
now add bit 0 of each pair ANDed with the bit 1:
                     mask2 = 10 10 10 10
B = (n & ((n & mask2)>>1)) = 01 00 00 00
              A + B = 10 01 00 01  (count: 2 1 0 1)
A + B stores the leading 1s for each pair of bits.
Now repeat the same reasoning to groups of 4 bits
mask = 0011 0011, mask2 = 1000 1000
A + B = 0011 0000 (leading 1s for each group of 4 bits)
.... and so on for groups of 8 and 16 bits ....

```

(sorry for the quick description, but it takes more than write the code :-).

This is the *magic* (and working) function in Java (in C replace `long` with `unsigned int`):

```
// count number of leading 1s in a 32bit value
// (0 <= i <= 0xFFFFFFFFL)
public long count(long i) {
    long t = i & 0xaaaaaaaa;
    i = ((i>>1) & 0x55555555) + (i & (t >> 1)) ;
    t = i & 0x88888888;
    i = ((i >> 2) & 0x33333333) + (i & ((t>>2)
            | (t >> 3)));
    t = i & 0x40404040;
    i = ((i >> 4) & 0x0f0f0f0f) + (i & ((t>>4)
            | (t >> 5) | (t >> 6)));
    t = i & 0x08000800;
    i = ((i >> 8) & 0x00ff00ff) + (i & ((t>>8) | (t>>9)
            | (t >> 10) | (t >> 11)));
    t = i & 0x00100000;
    i = ((i >> 16) & 0x0000ffff) + (i & ((t>>16) | (t>>17)
            | (t>>18) | (t >> 19) | (t >> 20)));
    return i;
}

```

It has 50 operators (  `>>, |, +, &`  ) and can be further optimized grouping the ORed-SHIFTs.
> 2 votes

---
Tags: algorithms, integers, binary-arithmetic
---


# Question
Title: NP-complete proof from Dasgupta problem on Kite
I am trying to understand this problem from Algorithms. by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, chapter8, Pg281. Problem 8.19

A *kite* is a graph on an even number of vertices, say $2n$, in which $n$ of the vertices form a clique and the remaining $n$ vertices are connected in a “tail” that consists of a path joined to one of the vertices of the clique. Given a graph $G$ and a goal $g$, the KITE problem asks for a subgraph which is a kite and which contains $2g$ nodes. Prove that KITE is NP-complete.

Any pointers to start with this problem? I am completely lost with it.

# Answer
> 14 votes
You can reduce CLIQUE ($G$ has a clique of size $k$) to KITE: given $G=(V,E)$ and $k$, just build in polynomial time a new graph $G'$ in this way: for each node $v\_i$ add a tail of $k$ new nodes.

If $G'$ has a kite of size $2k$ then the $G$ has a clique of size $k$ (the kite without the tail). Added nodes cannot introduce new cliques on G′, so $G$ contains exactly the same cliques of $G'$.

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


# Question
Title: Proving that the conversion from CNF to DNF is NP-Hard
How can I prove that the conversion from CNF to DNF is NP-Hard?

I'm not asking for an answer, just some suggestions about how to go about proving it.

# Answer
Informally:

In DNF, you can pick *any* clause to be true, to make the formula true. This means that a DNF that is equivalent to a certain CNF, is basically an enumeration of all the solutions to boolean sat on the CNF. Note, there can be an exponential number of solutions. Since solving boolean sat for CNF for a *single* solution is NP-complete, converting to DNF essentially means solving for *every* solution. So it is at least as hard as Boolean SAT, and is thus NP-hard.
> 18 votes

---
Tags: complexity-theory, np-hard, satisfiability, sat-solvers, normal-forms
---


# Question
Title: Two definitions of balanced binary trees
I have seen two definitions of balanced binary trees, which look different to me.

1. A binary tree is balanced if for each node it holds that the number of inner nodes in the left subtree and the number of inner nodes in the right subtree differ by at most 1.
2. A binary tree is balanced if for any two leaves the difference of the depth is at most 1.

Does every tree that satisfies def. 1 also satisfy def. 2? What about the other way round?

# Answer
> 18 votes
Definition 1. is also known as *weight-balancedness*¹ and definition 2. as *height-balancedness*.

Height-balancedness does not imply weight-balancedness; examples are both AVL- and Red-Black-Trees. See here and here for proofs, respectively.

Weight-balancedness does imply height-balancedness, though. This can be proven by showing the following stronger fact by induction (over height): a weight-balanced tree is complete on all levels but the deepest². The essential argument in the inductive step is that the subtrees can't have a height difference of more than one because -- both having the claimed property by induction hypothesis -- they would then not be weight-balanced.

---

1. The article gives a different, more general definition.
2. In other words, such a tree of height $k$ without the leaves at level $k$ is a perfect tree of height $k-1$.

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


# Question
Title: On-line simulation of a two-head tape Turing machine using single-head tape(s)
I have a question and I haven't been able to figure out the answer yet. I need to do the on-line simulation of a two-head tape Turing machine using single-head tape(s). I've found some online articles for the fact that one single-head tape doesn't suffice for this problem and the simulation should be done using two single-head tapes, but I haven't been able to present an accurate simulation of two-head TM using these single-head tapes. Are there any thoughts on how to do so? Thanks,

# Answer
> 2 votes
Two heads on a single tape are more powerful (in real time) than two single heads on two distinct tapes.

See T. Jiang, J.I. Seiferas and P.M.B. Vitanyi, 1994, "Two Heads Are Better than Two Tapes"

**EDIT**: I just read the proof and it is not trivial (and I didn't read/understand the details :-):

The language $L = \\{ x2x' | x \in \\{ 0,1 \\}^\* $ *and $x'$ is a prefix of $x$* $\\}$ can be easily recognized by a two-head single tape TM in real time: one of the two heads stays on the beginning of the input, the second moves right and as soon as it reads the 2 both move right and check whether $x'$ is a prefix of $x$.

But $L$ cannot be recognized by a two single-head tapes TM in real time. In a TM with two single-head tapes one of the two tapes is empty and trivially if the first head scans the input while the other copies it, when the 2 is read, the prefix of $x$ is far from both heads.

Hence the prefix(es) of $x$ should be made "quickly" available at every time using a so called "holographic" representation (see fig. 1 of the paper). But if $x$ is incompressible this cannot be achieved and when it is time to check the prefix one of the two heads must move too far from its current position (the number of moves cannot be bound by a constant).

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


# Question
Title: Coverage problem (transmitter and receiver)
I try to solve the following coverage problem.

> There are $n$ transmitters with coverage area of 1km and $n$ receivers. Decide in $O(n\log n)$ that all receivers are covered by any transmitter. All reveivers and transmiters are represented by their $x$ and $y$ coordinates.

The most advanced solution I can come with takes $O(n^2\log n)$. For every receiver sort all transmitter by it distance to this current receiver, then take the transmitter with shortest distance and this shortest distance should be within 0.5 km.

But the naive approach looks like much better in time complexity $O(n^2)$. Just compute all distance between all pairs of transmitter and receiver.

I am not sure if I can apply range-search algorithms in this problem. For example kd-trees allow us to find such ranges, however I never saw an example, and I am not sure if there are kind of range-search for circles.

The given complexity $O(n\log n)$ assumes that the solution should be somehow similar to sorting.

# Answer
> 4 votes
You can use the Voronoi diagram, together with Kirkpatrick's data structure to solve this problem.

Like Raphael and Syzygy suggested, you can use Fortune's (sweepline) algorithm to create the Voronoi diagram. Worst case time: $\mathcal{O}(n \log n)$.

The Voronoi diagram will have a bunch of polygons, each one containing a transmitter. Any point within the polygon is closest to that transmitter. Thus, if you can find out which polygon contains the receiver, you can find the closest transmitter to it by somehow finding out which polygon it is in. After that, you check if that transmitter is within $1\ \text{km}$.

To determine which Voronoi polygon contains the receiver, you first triangulate each polygon in the diagram. Now you have a triangle mesh. Next you use Kirkpatrick's data structure to locate any triangle containing a given point in $\mathcal{O}(\log n)$ time, worst case. Constructing Kirkpatrick's data structure takes $\mathcal{O}(n\log n)$ worst case. Once you know the triangle, you will know the polygon that contains it, and thus the closest transmitter. Doing this for all the receivers will be $\mathcal{O}(n\log n)$, worst case.

> Each cell in a Voronoi diagram is a convex polygon, possibly unbounded.
>
> ...
>
> The number of vertices \[of a Voronoi diagram of n sites\] V ≤ 2n-5
>
> www.cs.arizona.edu

Each polygon in a Voronoi diagram is a convex polygon. Therefore, since triangulation of a convex polygon takes $\Theta(v)$ time, $v$ being the number of of sides, we can triangulate each cell efficiently. If you fear that triangulation can be pathological (that we might have $n$ cells, each with $n$ sides), then consider this. The Voronoi diagram has $\mathcal{O}(n)$ vertices (see quote above). The triangulation of the Voronoi diagram is planar, and so is a sparse graph, and thus has $\mathcal{O}(n)$ edges and faces. Thus triangulation of a particular cell might take $\mathcal{O}(n)$, but the overall triangulation also takes $\mathcal{O}(n)$. (Basically, we will not encounter many cells with $\mathcal{O}(n)$ sides, this would result too many triangles for a planar graph).

---
Tags: algorithms, computational-geometry, search-problem
---


# Question
Title: What if a formal grammar cannot be terminated?
I'm currently in a class on Computability and we just finished looking at formal grammars before moving onto finite automata. We were given an several examples of a formal grammar, and one stuck out in particular:

```
V: { S, A, B, C }
T: { a, b, c }
P: {
    S -> aA | λ | ASA
   AA -> aA | a
}

```

My professor described the result as "any number of `a`s". This makes sense if you never use the first `S` or `AA` rule; you can simply replace `S` with `ASA` as many times as you like, then replace each `S` with `λ` (getting some even-length string of `A`s); you can then replace all `AA`s with `a`s.

But what if I picked the first rule? So, I start with `S`, then replace `S` with `aA`. I now have a string that contains neither `S`, nor `AA`, so the final terminal string should be `aA`. (This could also be done with `S -> ASA -> AA -> aA`.)

Is this allowed? If so, what is the result called? Since it still contains a variable, is this just a rejected/invalid result?

*NB: I did ask my professor about this. He explicitly said to "ignore the first rules of each 'S' and 'AA'", and could not give me any further explanation on why to do this.*

# Answer
> 10 votes
When you are given a grammar $G$, then the language it produces, $L(G)$, is all the (finite) words it can generate. All the other "derivations" that don't yield any legal word, can be ignored.

For instance, for the grammar $G\_1$:

> S -\> SS | Sa | aS

the language that the grammar produces is $L(G\_1)=\emptyset$, as no derivation ever terminates.

# Answer
> 3 votes
You can apply any rule in the set of productions P. The result is called a **sentential form**. A sentential form belongs to the language recognized by the grammar if it consists of terminal symbols only. Variables that derive no terminal strings can be removed safely (without changing the language).

---
Tags: formal-grammars
---


# Question
Title: Recommended Reading for non-CS undergraduate student doing a research Project on Travelling Salesman Problem
I am an undergraduate student in Industrial Engineering. I have taken the topic of Travelling Salesman Problem as a Research Project for my final year. More specifically, I am focusing on **Convex Hulls for solving the Euclidean TSP**.

I have gone through the published literature and have found that there are no approximation bounds for solving TSP using this method. I have just a little background in TheoCS (Started reading for fun since the last 3 months).

**My Question:**

Additional Books / Papers needed for achieving a good understanding of the mathematical rigor of the problem.

Here's what I am currently going through:

* Approximation Algorithms - Vazirani
* Introduction to Algorithms - CLRS
* Introduction to Graph Theory - Douglas West
* Randomized Algorithms - Motwani and Raghavan

I have also completed an introductory online course on Algorithms by Udacity.

I think I may need some background reading in Computational Geometry (Currently I do not know more than what I read in the chapter from Cormen)

This is my first question here, so sincere apologies in case my question does not conform to the Community Standards.

EDIT:

A resource I stumbled across today: In Pursuit of the Traveling Salesman - Mathematics at the Limits of Computation. This is a good book for popular reading, providing a survey of the problem and various methods that have been used to solve it.

# Answer
There are a few good books on the TSP problem where you are likely to find some relevant information:

Lawler et al., eds. The traveling salesman problem: A guided tour of combinatorial optimization. Wiley, 1985.

G. Reinelt. The traveling salesman: computational solutions for TSP applications. Springer, 1994.

G. Gutin and A. P. Punnen, eds. The traveling salesman problem and its variations. Kluwer, 2004.

Good luck with your research!
> 5 votes

# Answer
I have attempted concentric convex hulls to solve the TSP before, but I discovered that if a vertex happened too close to a hull, it distorts the form of the hull where it is located, so the result is not optimal. I got better results if I removed those vertices from the graph, then added them latter.

I got my best results when I started from one single convex block that was the perimeter of the entire area (covered all vertices in the map), then I proceeded to slowly reduce the radius of the block until I found the "outermost" inner vertex, then modified the "perimeter" line to connect to that vertex.

That method works as long as there are no two or more vertices at the same distance of the center. If that happens, there could be the case that the problem has multiple solutions, or you have found one of the "hard" instances of the problem.

Wish you luck!
> 1 votes

---
Tags: reference-request, optimization, books, traveling-salesman
---


# Question
Title: How does a single-track Turing machine simulate a multi-track Turing machine?
It's easy to see how a multi-track Turing machine can simulate a single-track Turing machine; it does so by ignoring all but the first track. But how does it work the other way? I need a specification of a transition function that does the job. If there are $k$ tracks, then we can think of symbols as being vectors and arrange them one after another in the tape; but again, what's the transition function like in the equivalent single-track machine?

# Answer
> 4 votes
If $\Sigma = (x\_1,...,x\_n)$ is the alphabet of the $m$-tracks $TM$, just use an expanded alphabet $\Sigma' = \Sigma \times ... \times \Sigma$ for the single-track $TM'$ ($|\Sigma'| = n^m$).

Every vector $\bar{x}\_i$ of $m$ symbols from $\Sigma$ can be mapped to a unique alphabet symbol $u\_i$ in $\Sigma'$: $\bar{x}\_i = (x\_{i\_1},x\_{i\_2},...,x\_{i\_m}) \rightarrow u\_i \in \Sigma'$

Hence every transition of $TM$ $(q\_h,(x\_{i\_1},x\_{i\_2},...,x\_{i\_m}))\rightarrow (q\_k,(x\_{j\_1},x\_{j\_2},...,x\_{j\_m}),dir)$ can be mapped to an equivalent transition in $TM'$ where the "read vector" $\bar{x\_i}$ and "write vector" $\bar{x\_j}$ are replaced with the corresponding alphabet symbols in $\Sigma'$: $(q\_h,u\_i)\rightarrow (q\_k,u\_j,dir)$

---
Tags: computability, turing-machines, simulation
---


# Question
Title: What is the difference between halting, accepting, and deciding in the context of Turing machines?
Does accepting mean that the TM will read and recognize a char from the cell it's currently reading from? And is it the case that a TM halts iff the input is decidable?

# Answer
Accepting and rejecting the state a Turing machine may eventually enter, is based on the string read from the tape, not just the symbol from one cell. Of course, the decision about entering an accepting or rejecting tape is ultimately made on the basis of one symbol.

A Turing machine can either eventually enter an accepting state, enter a rejecting state, or loop forever. If it enters either an accepting or rejecting state, then it halts.

A Turing machine is said to be total if it halts on all inputs.

The language accepted by a Turing machine is the set of all words that that, when provided as input to the Turing machine, cause the Turing machine to enter an accepting state.

A language is said to be decidable if and only if there exists a total Turing machine that will accept the language.
> 11 votes

---
Tags: terminology, turing-machines, undecidability
---


# Question
Title: Help Finding Loop Invariant From For Loop
I have created the algorithm below...

```
        String A = v[0];
        int val = 1;

        for (int i = 1; i < v.length; i++) {
            if (val == 0) {
                A = v[i];
                val++;
            } else if (v[i].equals(A))
                val++;
            else
                val--;
        }

```

The goal of the algorithm is to find the item that occurs in more than half the array.

Let v = {"one", "two", "one", "three", "one", "two", "two", "one", "one"}

The string "one" occurs 5 out of 9 times. So, at the end of the loop, the String A will be equal to "one".

I'm lost as to how to derive a loop invariant from this. Could someone provide me with some direction?

# Answer
See this question on Stack Overflow. You should provide reference for an algorithm when you did not write it, at least explain how you came up with it if you "created" it.

Terminology: this question is about finding the **majority element** of an array.

The invariant at step $i$ is:

* `A` occurs at least in `val` cells of `v[0..i]`
* The remaining `(i + 1 - val)` cells can be discarded without changing the majority element.

The algorithm is easy to accept as correct when you understand that if you remove two different elements of the array, then it keeps its majority element.
> 3 votes

---
Tags: algorithms, loop-invariants, correctness-proof
---


# Question
Title: Is star closure of reverse of language equivalent to reverse of closure of that language
is the following true $ (L^R)^\* = (L^\*)^R $

I tried the following to prove it true. let u,v belong to L then $ L^\* = \\{ u,v, uu, vv, uv, vu ... \\} $ and $ (L^\*)^R = \\{ u^R, v^R, u^Ru^R, v^Rv^R, v^Ru^R, u^Rv^R ... \\} $

now $ L^R = \\{ u^R, v^R \\} $ so $(L^R)^\* = \\{ u^R, v^R, u^Ru^R, v^Rv^R, u^Rv^R, v^Ru^R ... \\} $

# Answer
> 3 votes
Take any $w\in {(L^\*)}^R$. Then $w$ can be writen as $w=(u\_1\cdot u\_2\cdots u\_n)^R$, with $u\_i\in L$. We have

$$ w =(u\_1\cdot u\_2\cdots u\_n)^R =u\_n^R \cdot u\_{n-1}^R \cdots u\_1^R, $$

and therefore $w\in (L^R)^\*$.

Assume now that $w\in {(L^R)}^\*$, then by the same argument $$ w =u\_1^R \cdot u\_{2}^R \cdots u\_n^R= (u\_n\cdot u\_{n-1}\cdots u\_1)^R , $$ and hence $w\in {(L^\*)}^R$.

As a consequence ${(L^\*)}^R={(L^R)}^\*$

---
Tags: formal-languages, automata
---


# Question
Title: n*log n and n/log n against polynomial running time
I understand that $\Theta(n)$ is faster than $\Theta(n\log n)$ and slower than $\Theta(n/\log n)$. What is difficult for me to understand is how to actually compare $\Theta(n \log n)$ and $\Theta(n/\log n)$ with $\Theta(n^f)$ where $0 \< f \< 1$.

For example, how do we decide $\Theta(n/\log n)$ vs. $\Theta(n^{2/3})$ or $\Theta(n^{1/3})$

I would like to have some directions towards proceeding in such cases. Thank you.

# Answer
If you just draw a couple of graphs, you'll be in good shape. Wolfram Alpha is a great resource for these kinds of investigations:

Generated by this link. Note that in the graph, log(x) is the natural logarithm, which is the reason the one graph's equation looks a little funny.
> 3 votes

# Answer
$\log n$ is the inverse of $2^n$. Just as $2^n$ grows faster than any polynomial $n^k$ regardless of how large a finite $k$ is, $\log n$ will grow slower than any polynomial functions $n^k$ regardless of how small a nonzero, positive $k$ is.

$n / \log n$ vs $n^k$, for $k \< 1$ is identical to: $n / \log n$ vs $n / n^{1-k}$

as $n^{1-k} \> \log n$ for large $n$, $n / \log n \> n^k$ for $k \< 1$ and large $n$.
> 10 votes

# Answer
For many algorithms, it sometimes happens that the constants are different, causing one or another is faster or slower for smaller data sizes, and are not as well-ordered by algorithmic complexity.

Having said that, if we only consider the *super-large* data sizes, ie. which one eventually wins, then `O(n^f)` is faster than `O(n/log n)` for `0 < f < 1`.

A large part of algorithmic complexity is to determine which algorithm is eventually faster, thus knowing that `O(n^f)` is faster than `O(n/log n)` for `0 < f < 1`, is often enough.

A general rule is that multiplying (or dividing) by `log n` will eventually be negligible compared to multiplying (or dividing) by `n^f` for any `f > 0`.

To show this more clearly, let us consider what happens as n increases.

```
   n       n / log n         n^(1/2)
   2        n/ 1              ?
   4        n/ 2             n/ 2
   8        n/ 3              ?
  16        n/ 4             n/ 4
  64        n/ 6             n/ 8
 256        n/ 8             n/16
1024        n/10             n/32

```

Notice which decreases more rapidly? It is the `n^f` column.

Even if `f` was closer to 1, the `n^f` column will just start slower, but as n doubles, the rate of change of the denominator speeds up, whereas the denominator of the `n/log n` column appears to change at a constant rate.

Let us plot a particular case on a graph

Source: Wolfram Alpha

I selected `O(n^k)` such that `k` is quite close to 1 (at `0.9`). I also selected the constants so that initially `O(n^k)` is slower. However, notice that it eventually "wins" in the end, and takes less time than `O(n/log n)`.
> 3 votes

# Answer
Just think of $n^f$ as $\dfrac{n}{n^{1-f}}$. So for your example, $n^{2/3}=n/n^{1/3}$. Then it is easy to compare the growth of

$$ \frac{n}{\log n} \quad \text{vs.} \quad \frac{n}{n^{1-f}}.$$

Remember that $\log n$ grows asymptotically slower than any $n^\varepsilon$, for every $\varepsilon\>0$.
> 3 votes

# Answer
When comparing running times, it always helpful to compare them by using big values of n. For me, this helps build intuition about which function is slower

In your case think of n = 10^10 and a = .5

```
O(n/logn) = O(10^10/10) = O(10^9)
O(n^1/2) = O(10^10^.5) = O(10^5)

```

Hence, O(n^a) is faster than O(n/logn), when 0 \< a \< 1 I have used just one value, however, you can use multiple values to build intuition about the function
> 1 votes

# Answer
Let $f \prec g$ denote "f grows asymptotically slower than g", then you can use the following easy rule for polylogarithmic? functions:

$$n^{\alpha\_1}(\log n)^{\alpha\_2}(\log \log n)^{\alpha\_3} \prec n^{\beta\_1}(\log n)^{\beta\_2}(\log \log n)^{\beta\_3} \Longleftrightarrow (\alpha\_1, \alpha\_2, \alpha\_3) \< (\beta\_1, \beta\_2, \beta\_3)$$

The order relation between the tuples is lexicographic. I.e. $(2, 10) \< (3, 5)$ and $(2, 10) \> (2, 5)$

Applied to your example:

$\mathcal{O}(n/\log n) \Rightarrow (1, -1, 0)$

$\mathcal{O}(n^{2/3}) \Rightarrow (2/3, 0, 0)$

$\mathcal{O}(n^{1/3}) \Rightarrow (1/3, 0, 0)$

$$(1/3, 0, 0) \< (2/3, 0, 0) \< (1, -1, 0)\\ \Rightarrow \mathcal{O}(n^{1/3}) \prec \mathcal{O}(n^{2/3}) \prec \mathcal{O}(n/\log n)$$

You could say: powers of n dominate powers of log, which dominate powers of log log.

Source: Concrete Mathematics, p. 441
> 1 votes

---
Tags: asymptotics, mathematical-analysis, landau-notation
---


# Question
Title: What is the difference between decidability and computability?
If they are different, what are the typical problems in each that do not fall on the other category? Or are the mutually exclusive or does one completely capture the other?

# Answer
A function over finite strings is called computable if it can be computed by a program (more formally, a Turing machine).

A set of finite strings is computable if it membership problem in that set (given $x$, is $x \in L$?) can be decided algorithmicaly (more formally using a Turing machine).

They are used for different kind of objects.

The word "computable" can be used for a set. When we say that a set is computable we mean that the set is decidable (which is equivalent to saying that the characteristic function of the set is computable).

It makes no sense to say a function is decidable.
> 8 votes

---
Tags: computability, terminology
---


# Question
Title: What constitutes one operation/cycle/move in the RAM model?
I saw a RAM model diagram that displayed an input tape, output tape, the program (read-only), the instruction pointer, and the memory registers. However, when I look at questions of time complexity, it is relevant how much time the program needs to spend on one action. Say you want to read one integer symbol from the read tape, add it to an integer from a memory register, and then squish the result into the write tape cell, and then move the read head one to the right and the write head one to the left. How much time or how many moves did I just waste?

# Answer
Complexity is usually defined using Turing machine model to avoid the issue of the amount of resources taken during a complicated operation like adding integers.

You can use different notation of complexity of a RAM machine and that depends on what you are trying to do. If you want to be able to compare it with standard complexity classes which are defined using Turing machines then you should assign to each operation an amount of resource usage that a Turing machine would require to simulate that operation. The answer also depends on what kind of operations your RAM machine supports.

The standard RAM model consists of a finite control where a program is stored, one or more accumulator registers $Acc$, an instruction counter, and an infinite collection of memory registers $R\[0\], R\[1\],\ldots$. The instruction can be divided to four categories:

* flow-control: unconditional jump, Accept, Reject, Halt, conditional jumps (the "conditions" are simple like $Acc = 0?$);
* input/output: read, write;
* data-transfer between accumulator and memory: load, save;
* arithmetic: $Acc := 0$, add $R\[i\]$ to $Acc$;

Two more common costs are uniform and logarithmic. The two are related quadraticaly for the instruction set above (i.e. to convert the uniform to logarithmic you need to square the running time). Logarithmic means taking cost to be logarithm (i.e. the number of bits) of the inputs to the operation whereas uniform means that all operations are considered to take unit time.
> 4 votes

---
Tags: algorithms, time-complexity, algorithm-analysis, machine-models
---


# Question
Title: Successful applications of fuzzy logic to reasoning in AI?
I've done some searching and it seems that fuzzy logic is used in (electronic) controllers. I'm interested in seeing how well it fares as a tool for reasoning. Are there any robots or programs that do clever things with it?

# Answer
There are plenty of papers on fuzzy logic, and applications of it.

Fuzzy logic models a piece-wise control function, and is regarded as a non-linear controller. Generally, fuzzy logic can approximate any non-linear function if you divided the state-space into enough fuzzy sets.

Because it is non-linear, it is generally useful if it is controlling a non-linear system. If it were a linear system, a linear controller would be able to control it optimally already.

It is appropriate when you want to control things like movement or position (which is often the case in robots). When a system can rotate, the rotation will create the non-linearity that fuzzy logic may try to control.

In any case, the success of fuzzy logic more often has to do with how well you select the fuzzy sets (ie. their boundaries and membership functions), and how well you tune the fuzzy logic controller. In general, any controller can be successful if appropriately tuned - though their ideal performance may differ. And the most difficult part is probably tuning it - although it is not hard to get something that works, it may be hard to get something close to optimal.

If you are thinking of using a fuzzy controller, it may be a good choice if:

* your system is moderately non-linear (if it is close to linear, a linear controller is sufficient)
* your system is not mathematically modelled (if it is modelled, look at LQR and perhaps gain scheduling or SDRE)
* or you are unsure of the parameters of your system
* and any intuition of what the controller should do would be useful when trying to select the fuzzy sets and their appropriate control responses
> 3 votes

---
Tags: reference-request, artificial-intelligence, reasoning
---


# Question
Title: Kolmogorov complexity of string concatenation
If $K(s)$ is the Kolmogorov complexity of the string $s \in \\{0,1\\}^\*$,

> Can we prove (or disprove) the following statement:
> "Every string $s$ is a prefix of an incompressible string; i.e. for every string $s$ there exists a string $r$ such that $K(sr) \geq |sr|$" ?

In a very informal (and perhaps not too meaningful) way: we know that $K(r) \leq |r| + O(1)$; if we pick a large enough incompressible string $r$, can we "use" the $O(1)$ to "mask" the compressibility of the given string $s$ ?

A similar (but different) result is that for any $c$, we can find $s$ and $r$ such that: $K(sr) \> K(s) + K(r) + c$

# Answer
> 4 votes
Your conjecture is wrong. For some constants $C,D$, it holds that $K(sr) \leq 2K(s) + K(r) + C \leq 2K(s) + |r| + D$ (proof: use a universal Turing machine to generate $s$ and then $r$; you need somewhat more than $K(s)+K(r)$ to store both programs, though $2K(s)+K(r)$ is an overkill). Therefore if $2K(s) + D \< |s|$, your conjecture doesn't hold. Such easy strings $s$ certainly exist, for example $K(0^n) = O(\log n)$.

---
Tags: computability, kolmogorov-complexity
---


# Question
Title: Why isn't converting from an NFA to a DFA working?
I am just beginning to learn computation theory. I wrote up a non-deterministic finite automata that accepts strings that contain the substring "abba":

I tried to convert it to a DFA by putting together sets of states in the NFA to be states of the DFA:

However, I just realized that my DFA doesn't accept strings such as "abbaa" that do not end in "abba." That means that my methodology was wrong. Why? I thought it would make sense to combine states of the NFA to make states of the DFA.

# Answer
Your methodology for creating the DFA from the NFA is fine. The problem is that you started with the wrong NFA (you'll notice that your NFA doesn't accept abbaa either). Try this one instead:
> 12 votes

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


# Question
Title: What is the probability of friendship conditioned on the number of mutual friends
Let Alice and Bob be two users chosen uniformly at random from a social network (e.g. Facebook). What is the probability that they are friends assuming that they share $k$ mutual friends?

I am interested both in the experimental values (or estimates) from currently existing social networks (e.g. Facebook) and values predicted by random graph models for these social networks.

# Answer
Okay, this is my approach to this problem. I think the key concept here is the **clustering coefficient** $c$. The value of $c$ is denotes how likely it is that two nodes are connected by an edge, if the have a common neighbor. In SN-friendship graphs the clustering coefficient is usually high compared to classical random graph models, such as Erdös-Rényi.

What is known about the clustering coefficient of the facebook-graph? If you follow the presentation of this paper, for a node of degree 100, we have $c=0.14$. Assuming that you have 100 friends is a reasonable assumption than it is close to the median degree (about 99, see here) and the average degree (might be around 95, see here).

Lets make the bold assumption, that the events that a tie between two nodes $A$ and $B$ is present if they have friend $X$ in common, are independent. Then we get

$$\begin{align} P\[\text{$A$ and $B$ are friends}\] & = 1 - P\[\text{$A$ and $B$ are not friends}\] \\ &=1-(1-c)^k. \end{align}$$

A plot of this function looks like this:

So if $A$ and $B$ have 5 friends in common it is slightly more likely they are friends, than they are not.

**This is just a rough calculations that ignores several effects.**
> 3 votes

---
Tags: graphs, combinatorics, social-networks, random-graphs
---


# Question
Title: Computing the running time of a divide-by-4-and-conquer algorithm
I write this code in python:

```
def sub(ma):
    n = len(ma); m = len(ma[0])
    if n != m : return
    n2 = int(ceil(n/2))
    a = []; b = []; c = []; d = []
    for i in range(n2):
        a.append(ma[i][0:n2])
        b.append(ma[i][n2:n])
        c.append(ma[n2+i][0:n2])
        d.append(ma[n2+i][n2:n])
    return [a,b,c,d]

def sum(ma):
        if len(ma) == 1 : return ma[0][0]
        div = sub(ma)
        return sum(div[0])+sum(div[1])+sum(div[2])+sum(div[3])

```

Do you know what is a possibly recurrence equation $T(n)$ to the 'sum' method? I suppose that is like that $$T(n) = 4T(n/2) + f(n)$$ what it is $f(n)$ ? Thanks,

# Answer
> 4 votes
The subroutine *sub* quarters the matrix into four parts. This takes time $f(n)$, and so the running-time of *sum* (which sums all entries in its input square matrix in a curious divide-and-conquer fashion) satisfies the recurrence $$ T(n) = \begin{cases} O(1) & n=1 \\ 2T(\lfloor n/2 \rfloor) + 2T(\lceil n/2 \rceil) + f(n) + O(1) & n\>1. \end{cases} $$ The subroutine *sub* is quite simple, and I'm sure you can figure out its running time yourself (though you'll have to be careful about the semantics of list appending in python).

---
Tags: algorithms, algorithm-analysis, runtime-analysis, recurrence-relation
---


# Question
Title: Doubt with a problem of grown functions and recursion tree
I'm confused to conclude the recursion tree method a guess for the next recurrence: $$T(n)=3T\left (\left\lfloor \frac{n}{2}\right \rfloor\right) +n$$ I write some costs for the levels of tree, you can see, but I'm confusing in the final guess. I know for the master theorem that the answer for the guess is like that $$\Theta(n^{\log\_2 3}) $$ but in the steps by tree and I don't belive, you can see my error (?). How can I finished or know the outcome for this method to calculate $T(n)$? thanks, And the final conclusion is (?) $$=2 n^{\log\_2 3}+\Theta(n^{\log\_2 3})\leq cn^{\log\_2 3} \rightarrow \ \ T(n)\in\Theta(n^{\log\_2 3})$$ with $c=3$ ?

# Answer
Instead of having logarithms in the working, I'll substitute $n=2^m$: $$ T(n) = n\sum\_{i=0}^{m} \left(\frac{3}{2}\right)^i = n \frac{\left(\frac{3}{2}\right)^{m+1}-1}{\frac{3}{2}-1} = 2n \left(\left(\frac{3}{2}\right)^{m+1}-1\right) = 2n \left(\frac{3}{2}\right)^{m+1}-2n $$ I believe the previous step is where you didn't expand the $2n$ into the first term. I am also **not** making any guess of what the *master theorem* or order of complexity is. Guesses should not be necessary anyways, since we just assume $T(1) \in \Theta(1)$.

Simplifying by keeping only the first term, and removing constants:

$$T(n) \in \Theta(n 1.5^{\log{n}})$$

Then, with some rearranging:

$$n 1.5^{\log\_2{n}} = 2^{\log\_2{n}}1.5^{\log\_2{n}} = 3^{\log\_2{n}}=2^{\log\_2{3}\log\_2{n}}=n^{\log\_2{3}}$$

Thus:

$$T(n) \in \Theta(n^{\log\_2{3}})$$
> 2 votes

---
Tags: algorithms, asymptotics, runtime-analysis, recurrence-relation
---


# Question
Title: How To Best Learn About Algorithms In Depth
I have been reading this site with a great deal of interest, but I find a lot of it goes over my head. This has made me wish to learn a lot more about algorithms and CS in general. As far as I can tell from my research, there are two main ways of doing this.

1. I can buy a nice thick heavy book and work my way through it slowly but surely.
2. I can "learn by doing" and buy a nice book, but instead of reading it cover to cover, move to parts that interest me and work on implementing and applying algorithms I like.
3. ?

My question is, which of the above did the you use and would you recommend the same approach to someone else?

# Answer
> 15 votes
I learned about algorithms in a university course years ago. But if you are to do algorithms using a book, then you need a good one. Two books stand out for me as the way to get into algorithms:

* The Algorithm Design Manual **by** Steven S. Skiena
* Introduction to Algorithms **by** T Cormen, C Leiserson, R Rivest and C Stein

The first is perhaps more of a hands-on manual, whereas the latter is more like the bible, but with proof.

The strategy you could follow would consist of reading, doing the theoretical exercises, and then implementing as much as you can, focusing on algorithms/problems you find interesting *or* challenging or both. Thus, try to cover all aspects of algorithms, not just implementing them. This will include studying their time and space complexity and proving their correctness. *The study of algorithms is more than just implementing algorithms.*

After you've gained enough experience, start specializing. If you become interested in Computational Geometry or non-blocking algorithms, for example, then start exploring books and research papers in this area.

Specialization is good, but it is also good to sample techniques from other areas, so reading broadly about algorithms (and implementing such algorithms) is a good way of maintaining a broad skill set.

EDIT: After going through the introductory algorithms, you may consult books like ***Randomized Algorithms by Motwani & Raghavan*** or ***Approximation Algorithms by Vazirani***. These books are a survey (and to some extent, a good learning exercise in mathematical techniques) in more advanced algorithm design techniques. They also broaden your insight into many other fields in CS like Graphs and Networks, Data Structure design and Optimization.

# Answer
> 13 votes
**Teach an algorithms class.**

Or perhaps even better:

**write an algorithms textbook.**

# Answer
> 2 votes
Try solving problems based on an algorithm as soon as you read one. Moreover, for understanding algorithms and implementing them better you need to have a better understanding of Data structures. There is very nice book of data structures written by Sahni. You can use that and for algorithms you can solve problems of programming challenges book. Question are pretty nice there.

# Answer
> 1 votes
If you haven't learned about algorithms at university I recommend taking one of the online classes, you may consider signing up for one of the courses at coursera.org or following videos posted by Stanford University.

---
Tags: algorithms, education
---


title: A tentative satisfiability algorithm

text:
# Question
Title: A tentative satisfiability algorithm
General satisfiability (with a few exceptions such as Horn Clauses) is not believed to have an algorithmic solution. However, the following algorithm appears to be a solution for general satisfiability. What exactly is the flaw with the following algorithm?

1. Let $W$ be an empty set which will contain all variables that necessarily have to be true or false.
2. Let $L$ be the set of clauses.
3. Loop through $L$.
4. Every time a non-conditional variable is found, remove it from $L$ and insert it into $W$.
5. If this leaves an empty AND implication, remove all variables in that empty implication from $L$ and insert into $W$.
6. If this leaves an empty OR implication, create new instances of the algorithm, where each instance deals with one variable in the implication (i.e. if the implication is: $x V \implies y$, create one instance where $x$ is inserted into $W$, one where $y$ is inserted into $W$ and one where $x$ and $y$ are inserted into $W$).
7. Set all variables in $W$ to the value they necessarily have to be.
8. Reinsert the variables in $W$ in $L$ with their changed values and check if all clauses are satisfied.
9. If satisfiability is met, then return $L$, else return "Not Satisfiable".

A non conditional variable is defined as a variable that is necessary true or false, e.g. $\implies x$ or $\implies \neg y$.

An empty implication is defined as an implication where one side is empty (e.g. $\implies x \wedge y$) or the other side is necessarily true (e.g. $\mathrm{true} \vee a \implies b$.

To get a more intuitive understanding of the algorithm consider the following set of clauses $L$:

$$\begin{align} a \wedge b &\implies c & \text{(i)} \\ &\implies f \wedge g & \text{(ii)} \\ f &\implies \neg a & \text{(iii)} \\ f \vee a &\implies b & \text{(iv)} \\ &\implies c & \text{(v)} \\ \end{align}$$

The algorithm will do the following:

1) Since $c$, $f$, $g$ are non-conditional variables, the algorithm will insert them into $W$. $W = \\{c, f, g\\}$.

2) Removing $c$, $f$ and $g$ will leave the empty clauses: $\implies \neg a, a \wedge b, b$. These will be added to $W$. $W = \\{c, f, g, b, \neg a\\}$.

3) Reinserting the variables into $L$ will result in the first clauses being violated: $a \wedge b \implies c$. Since $a$ is false, $c$ is false, meaning clause (v) is violated. The algorithm will return "Not Satisfiable"

I am aware that the algorithm appears confusing. Please feel free to ask for clarification.

---

From comments I now realize that there is no known *efficient* general satisfiability algorithm. I'm still interested in feedback about my algorithm. Does it work? How does it compare with common algorithms?

# Answer
**Problem 1**

The case of $(x\rightarrow y \vee \overline y)$ should be a "non conditional variable" with respect to $x$ (ie. that $\overline x$ should now be inserted into $W$). If this is not true, then your algorithm needs an extra step to infer this. Assuming $(x\rightarrow y \vee \overline y)$ is a "*non conditional variable*", we continue.

**Problem 2**

**NOTE:** this is one problem I noticed; there may very well be other problems.

The problem is with the "*empty OR implication*" split into two algorithms, is that in its current form, the split does not cover all cases. In particular:

You start with $(x \vee c \rightarrow y)$, then $c$ is removed and we are left with an *empty OR implication* of $(x \vee \[\] \rightarrow y)$. You suggest now splitting it into two new problems and solving each of them; one with $x=T\wedge y=T$ and one where $y=T$. But this does not cover all cases. What about the case when $x=F\vee y=F$. However, your algorithm never considers the possibility that $y$ is false.

I think you might be able to fix this by formulating the two new problems as one with $y$ and one with $\overline x$.

**Problem 3**

What happens when you are left with a bunch of clauses in the form:

$$(a\wedge b \rightarrow c)$$

or

$$(a \rightarrow b \vee c)$$

After reducing everything, these clauses will remain, and you won't be able to test their satisfiability easily.

**Analysis**

**Note**: This "O" notation, $\mathcal{O}(something)$ etc., is called Big O notation. $\Omega(something)$ is called Big-omega.

Supposing the algorithm did work in general, it would run in time of $\Omega(2^m)$ worst case, $m$ being the number of variables. The reason is, each splitting of problem into problems of similar size means that the algorithm runs in exponential time. To visualize this concept, look at the following image of a *full binary tree* (image from here):

Now imagine the original problem is the node on top. We split the problem into two problems on the second level, but they are of similar size (we only get rid of one variable, $x$ or $y$ from the *empty OR implication*, so we will still have lots of *empty OR implication*s to do each level). We will potentially have to split the problem $\mathcal{O}(m)$ times to get rid of $m$ variables. This means we will have to deal with a tree with $m$ levels. A tree with $m$ levels has $2^m$ *leaf nodes* (nodes at the bottom). This is called exponential time, and is informally somewhat on-par with all known boolean satisfiability algorithms. But so is brute force: there are $2^m$ possible assignments of the variables, so by brute force you can guess each assignment and check for satisfiability with similar performance!
> 6 votes

# Answer
Before you feel you have a "new" SAT algorithm, please review the standard/classic backtracking/search algorithm in the literature for the problem dating to ~1962, the Davis–Putnam–Logemann–Loveland algorithm. most backtracking/recursive algorithms for the problem will likely end up looking somewhat similar to this algorithm, although it can take quite a while to demonstrate this equivalence.

Serious analysis would involve benchmarking your algorithm against examples (or random instances) vs DPLL.

And so it is helpful merely to summarize how your algorithm differs from it. without reviewing your code, odds are:

* The algorithm has a bug in it. either returning false positives or negatives (ie algorithm returns "formula is satisfiable" when it is not or vice versa, respectively). this can be usually caught by very thorough testing of a large range of randomly generated formulas and checking against another known correct algorithm/*implementation* eg DPLL.
* Your algorithm is not as good as DPLL.
* If it is as good as DPLL or "better", it is generally due to branching and variable selection heuristics/strategies and the distribution of instances under testing.

The algorithm can be easily understood by an intelligent undergraduate however it seems rarely taught at the undergraduate level or in undergraduate textbooks, or perhaps not even often referenced, possibly leading to a mistaken view or impression that basic SAT algorithms are not well understood etc.

Also recently just ran across this "live" site called ToughSat by Yuen and Bebel for generating hard instances for use with benchmarking, some based on factoring \[one of the classic SAT hard instance generation methods\]. there are others eg DIMACs that store archives of hard instances although it may no longer be online.
> -5 votes

---
Tags: algorithms, logic, satisfiability, constraint-programming
---


# Question
Title: What different lines of reasoning and traditions lead to the conclusion that Software Engineering is or isn't part of Computer Science?
**Background:** Some people consider Software Engineering as a branch of Computer Science, while others consider that they are, or should be, separate. The former stance seems to be well presented in written works. On Wikipedia, Software Engineering is classified as Applied Computer Science, along with, e.g., Artificial Intelligence and Cryptography. The ACM Computing Classification system places SE under Software, along with, e.g., Programming Languages and Operating Systems. CSAB has also considered SE as part of Computer Science, and considered that

> \[...\] it includes theoretical studies, experimental methods, and engineering design all in one discipline. \[...\] It is this close interaction of the theoretical and design aspects of the field that binds them together into a single discipline.
> \[...\]
> Clearly, the computer scientist must not only have sufficient training in the computer science areas to be able to accomplish such tasks, but must also have a firm understanding in areas of mathematics and science, as well as a broad education in liberal studies to provide a basis for understanding the societal implications of the work being performed.

While the above seems to reflect my own view, there is also the stance that the term Computer Science should be reserved for what is sometimes called Theoretical Computer Science, such as Computability Theory, Computational Complexity Theory, Algorithms and Data Structures, and that other areas should be split off into their own disciplines. In the introductory courses I took for my CS degree, the core of CS was defined via the questions "what can be automated?" (Computability Theory) and "what can be automated efficiently?" (Computational Complexity Theory). The "how" was then explored at length in the remaining courses, but one could well consider SE being so far from these core questions that it shouldn't be considered part of CS.

Even here on CS.SE, there has been debate about whether SE questions are on-topic, reflecting the problematic relationship between CS and SE.

**Question:** I'm wondering what lines of reasoning and traditions within Computer Science might lead to one conclusion or the other: that SE is, or should be, part of CS or that it is not. (This implies that answers should present both sides.)

# Answer
> 8 votes
(I did some extensive searching and found material that answers my question. I liked Patrick87's answer, but I found this to be more complete.)

The answer to the question lies in a careful examination of the philosophy of Computer Science. In Computer Science, three intellectual traditions meet (or collide, if you wish) in a single discipline: the theoretical tradition; the empirical tradition; and the engineering tradition.

The theoretical tradition concerns itself with creating hypotheses or theorems, and proving them in a mathematical fashion. Its aim is the construction of coherent axiomatic systems of thought.

The empirical tradition concerns itself with forming hypotheses, models, and predictions, collecting data from experiments, and analysing the results. Its aim is to investigate and explain phenomena.

Finally, the engineering tradition concerns itself with stating requirements and specifications, and with designing, implementing, and testing systems based on these requirements and specifications. Its aim is to construct systems and solve concrete instances of problems.

Each of these traditions comes with a set of assumptions about the aims and means of scientific inquiry.

The traditions are not unique to Computer Science; they are general traditions that can be found to differing degrees in other disciplines. Perhaps the clearest examples are mathematics (theoretical tradition), physics (empirical tradition), and construction engineering (engineering tradition). Computer Science, though, operates in the intersection of all three traditions. However, depending on one's particular focus within Computer Science, and one's familiary with other parts of Computer Science, one might emphasize one of these traditions to the degree that the other two appear alien.

As noted in Patrick87's answer, the educational setting can emphasize a certain intellectual tradition which may lead someone to a certain kind of demarcation of Computer Science which either includes or does not include Software Engineering. Similarly, one may later adopt a view of science that includes or excludes one or more of the three traditions, or parts of them. For example, one may consider only the theoretical and empirical traditions to fulfil one's criteria for "science", and consider engineering non-scientific. One may also consider the three traditions to be on a value continuum, with one tradition being superior to the others (e.g. valuing the theoretical tradition most, the empirical tradition less, and the engineering tradition least).

So the lines of reasoning are rooted in the abovementioned traditions. Based on this, the answer to the question is that considering Software Engineering as part or not as part of Computer Science stems from one's understanding of science in general, and of one's understanding of the philosophy of Computer Science in particular.

The following articles go into considerable depth on this issue and summarise a lot of the viewpoints that have been put forward.

> Tedre, Matti (2011) Computing as a Science: A Survey of Competing Viewpoints. Minds & Machines 21(3):pp.361-387.
>
> Tedre, Matti (2009) Computing as Engineering. Journal of Universal Computer Science 15(8):pp.1642-1658
>
> Tedre, Matti (2007) Know Your Discipline: Teaching the Philosophy of Computer Science. Journal of Information Technology Education 6(1):pp.105-122.

# Answer
> 4 votes
One might base such a decision on the kind of education and training expected of practitioners. A good source for investigating differences and similarities in this direction might be the ACM curriculum guidelines for computing professions, including CS and SwE.

Another might be in terms of the economic profile of these professional fields. The latest edition of the US Bureau of Labor Statistics Occupational Outlook Handbook provides a good deal of information comparing these fields' economic and social aspects.

One might take a more philosophical approach and ask what the fields are, in themselves, and how they are similar and different in that respect. The question of how, if at all, to distinguish between science and engineering is a long one, and e.g., David Parnas saw a distinction in this way (see the Computer science Wikipedia page).

---
Tags: software-engineering
---


# Question
Title: References on teaching introductory programming courses
As the new semester starts soon, I am interested in research regarding the teaching of introductory programming courses. I would like to improve my university course and I am looking for scientific papers on that topic.

One trend I have seen is that some students (a smaller group) are interested in computers or they have already some programming background. They are fine and learn a lot. But the majority of students struggle at the first step of programming (hard to set up Eclipse, a lot of errors at the beginning, etc.). Is this just my view or is this documented in literature?

I would like to make this 'first step' into programming as easy as possible for students. As a first start I found "A Gentle Introduction to the Art of Object-Oriented Programming in Java"

# Answer
Here's a survey paper and there are others.

You might want to consider the inverted method also known as outside-in, which differs from the traditional bottom-up approach.

This article on the application of problem-based learning to first year programming reports some successful results, mainly in terms of secondary skills learned by students. The cost is a major investment and restructuring by those involved.
> 5 votes

# Answer
Here is a new ars technica article entitled Is it true that "not everyone can be a programmer"? on teaching programming including academic papers analyzing the efficacy of teaching methods/approaches and capability of students, two stack exchange questions on the subject, Jeff Atwood's opinion etc.
> 2 votes

---
Tags: reference-request, education
---