# Question
Title: Why does the NP completeness of the Hartree-Fock method not lead to difficulty in practical calculation?
I read Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory. In appendix, it is claimed that

> In the following, we show that approximating the ground state energy using the Hartree-Fock method is an NP-complete problem

As far as I know, if a problem being NP-hard, it is unlikely to be solved within polynomial time. If Hartree-Fock is NP-complete, computation for large system is unlikely to be possible. However, experience seems to suggest that Hartree-Fock could always be done within polynomial time. There are vast applications of Hartree-Fock method on various many-electron system: atoms, molecules, and solids. The claim from the arxiv paper is rather in contraction with my experience

My question is, why the Hartree-Fock method is applicable to wide class of many-electron system while it is NP-complete? Is that because its average complexity is low or any other reason?

# Answer
There is plenty of precedent for problems that are NP-hard (in worst-case complexity) but can often be done in practice on many instances that arise in practice (e.g., because their average-case complexity is low, or for other reasons).

NP-hardness relates to the worst-case complexity of a problem. However, worst-case hardness isn't always representative of typical-case hardness. Sometimes typical instances are much easier than the worst-case instances. Therefore, NP-hardness results aren't always an indication that the problem can't be solved acceptably well in practice.

As Yuval Filmus explained so well in a comment:

> I'm not sure there is any better answer than the fact that the algorithms work on real-world instances. NP-hardness is a worst-case concept, and sometimes the worst case is simply irrelevant. It is a challenging problem to characterize which properties of real-world instances render the problem solvable. Smooth analysis is one answer, and there might be others in the non-rigorous literature.

I recommend you take a look at Dealing with intractability: NP-complete problems for an overview of common methods for dealing with NP-hardness: i.e., for figuring out ways to solve a problem good enough for practical purposes, when we know it is NP-hard.
> 4 votes

# Answer
taking the wikipedia definition & working from that & taking a physics POV:

> In computational physics and chemistry, the Hartree–Fock (HF) method is a method of approximation for the determination of the wave function and the energy of a quantum many-body system in a stationary state.

therefore this problem is closely connected to solving quantum-mechanical setups which is likely to be tightly coupled with the complexity of quantum computing. notice that even Feynman felt intuitively that classical systems could not solve quantum mechanical systems as fast as quantum mechanics itself, and this was some of the original rationale for quantum computing theory/foundations (while still widely held/believed, this is still currently an open conjecture spanning physics/CS).

another way to look at this is to study the transition point phenomenon in NP complete problems which is tightly connected with physical systems namely spin states in ferromagnetic systems. imagine transition points occurring in physical setups for Hartree-Fock equations & they likely will translate into the theoretical hardness variations.

another angle is to look up research into "creating hard instances for NP complete problems". it actually takes quite a bit of contrived logic at times to generate these instances, and there is not a large amount of research in this area (outside of the transition point in SAT). in other words, hard instances do not occur much at random (very rarely) and require some ingenuity to "artificially fabricate" algorithmically.

in other words visualize the problem as a large number of possible physical setups, a "parameter space", maybe many of which are solvable in P time, but a narrow section of "weird/ unusual/ pathological / contrived/ anomalous" (etc) cases that take abnormally long to solve.
> 2 votes

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


title: Trigonometry in computer science

text:
# Question
Title: Trigonometry in computer science
What's the use of studying trigonometry in computer science? I mean, is it essential? Does it have a specific application in computer science? Because I can't seem to muster enough motivation for learning it.

# Answer
> 13 votes
* **Rotations**: that arise in Computer Graphics and Robotics , through rotation matrices, Quaternions, etc.
* Cordics for computing these functions on a Microprocessor / FPGA
* Transforms in Image Compression and elsewhere , e.g. FFT computation in $O(n \log n)$ time
* Anything to do with the interface between CS and Signal Processing
* Pretty much anywhere in navigation and tracking, e.g. anything involving a GPS, IMU,etc.
* Somewhat indirectly in Computational Geometry (CG), in its application like in coverage & localization in wireless sensor networks.

.. to name a few! So if you want to really avoid trig functions, you should learn CG :-)

# Answer
> 4 votes
I assume laziness is not an issue here and you are interested in pursuing computer science and therefore want to be laser-sharp. But even then, our basic sciences seem to crop up everywhere later in higher studies, especially mathematics. And trigonometry comes up in mathematics a little too much to be ignored. If you want to go anywhere in any field, a minimum basic knowledge of related fields is a must.

Since computer science is fundamentally just mathematics, especially discrete algebra, strong mathematical roots don't hurt. I can imagine graphics could be one are where trigonometry can be directly applied.

Moreover, Trigonometry is nothing but a bunch of functions and their applications; how difficult can it be?

# Answer
> 3 votes
Interpolation. If by computer science you include numerical computing, any why the hell not, you often use trig functions in interpolation.

Sometimes you have a sampled version of a function, say a sampled signal, $\<u\_0, u\_1, ...\>$. You would like to find a function $f(t)$ such that $f(n\*T) = u\_n$, for some time period, $T$. Or maybe you don't care that $f(n\*T)$ matches the $u\_n$s exactly, but that it's in some sense the best approximation in its class. You could make $f$ a polynomial, say $f(t) = \sum\_{k=0}^N a\_k t^k$. But it turns out to be numerically superior to choose use the Chebyshev polynomials. These can be defined by $T\_n(x) = \cos(n \arccos(x))$.

# Answer
> 0 votes
If you stick to applications of computer science strictly in the field of simple accounting (requiring some mastery of the four arithmetic operations) or classical database management (possibly enough with addition and subtraction), you can probably spend a whole carrier without ever requiring trigonometry.

For anything else, you'll need it someday.

---
Tags: education, mathematical-analysis, applied-theory
---


# Question
Title: How to implement the regret matching algorithm?
My question is the following: How to calculate the regret in practice?

I am trying to implement the regret matching algorithm but I do not understand how to do it.

* First, I have $n$ players with the joint action space $\mathcal{A}=\\{a\_0, a\_1,\cdots,a\_m\\}^n.$
* Then, I fix some period $T$. The action set $A^t\in\mathcal{A}$ is the action set chosen by players at time $t$. After the period $T$ (every player has chosen an action). So I get $u\_i(A^t)$.
* Now the regret of player $i$ of not playing action $a\_i$ in the past is: (here $A^t\oplus a\_i$ denotes the strategy set obtained if player $i$ changed its strategy from $a'\_i$ to $a\_i$) $$\max\limits\_{a\_i\in A\_i}\left\\{\dfrac{1}{T}\sum\_{t\leqslant T}\left(u\_i(A^t\oplus a\_i )-u\_i(A^t)\right)\right\\}.$$ I do not understand how to calculate this summation. Why there is a max over the action $a\_i\in A\_i$? Should I calculate the regret of all actions in $A\_i$ and calculate the maximum? Also, In Hart's paper, the maximum is $\max\\{R, 0\\}$. Why is there such a difference?

I mean if the regret was: $\dfrac{1}{T}\sum\_{t\leqslant T}\left(u\_i(A^t\oplus a\_i )-u\_i(A^t)\right),$ the calculation would be easy for me.

The regret is defined in the following two papers \[1\] (see page 4, equation (2.1c)) and \[2\] (see page 3, section I, subsection B).

---

1. A simple adaptive procedure leading to correlated equilibrium by S. Hart et al (2000)
2. Distributed algorithms for approximating wireless network capacity by Michael Dinitz (2010)

I would like to get some helps from you. Any suggestions step by step how to implement such an algorithm please?

# Answer
> 5 votes
The index set of the max operation is $A\_i$, the actions of player $i$. The formula says: take each such action $a\_i \in A\_i$ and compute its regret (with the sub-formula you say you can implement easily), and then take the maximum of those regrets.

The reason for the $\max(R,0)$ is that actions with negative regrets are performing *worse* than the action currently chosen.

To implement this in code, just set a temporary variable $t$ to be 0. Now loop through the actions one by one, and for each action $a$, compute its regret $r$, and set $t$ as $\max(r,t)$. Note that this approach includes the $\max(R,0)$ operation; to do this without that, set $t$ initially to $-\infty$.

---
Tags: machine-learning, game-theory, learning-theory
---


# Question
Title: Maximum length path between any two nodes in a tree with possible negative edge weights
Is there an efficient way to find the longest path between any two nodes in a tree. Given that edges can have negative weights. I know about the diameter problem which finds the longest path in a graph with edge weights 1 but that won't work here.

All I can think of is going for a $O(N^2)$ approach with LCA but thats a glaringly bad approach for huge trees ($N \sim 100000$)

# Answer
> 2 votes
You can find this path in linear time:

1. If the tree is unrooted, pick an arbitrary node as root.
2. Traverse the tree in postorder and for each node:

2.1. Find the longest and second longest path ending in the current node by maximizing over all children and extending the longest path ending in the child by the edge between parent and child.
If there are no two children that result in paths of positive length, set the second longest (and if necessary also the longest) path as starting and ending here (length 0).

2.2. Find the longest path in the subtree that starts at the current node by maximizing over the longest paths in all subtrees below the current one and the path resulting from joining the two paths found in the previous step.

Now the longest path in the subtree started at the root is the one you are looking for.

# Answer
> -1 votes
Note that the longest path between any two nodes in a tree is also the shortest path (indeed a tree only has one path between any pair of nodes)

Now, you cannot do this in sub-quadratic time since in order to obtain the distances between all pairs of nodes you need to compute $O(n^2)$ of data.

---
Tags: algorithms, graphs, search-algorithms, trees, weighted-graphs
---


# Question
Title: What is a good design for expanding opcodes?
Are there any tutorials on YouTube or good text tutorials on designing expanding opcodes? I always make mistakes on switching from one line to another and "counting" in binary. I pretty much know how to design them, but I don't really understand it and I make so many mistakes. I also don't have any examples to go by and check my answer. Here's one example of what kind of designing and exercises I need: Design 1 three-address instruction, 10 two-address instr, 7 one-address instr and 4 zero-address instr. The addresses are 8 bits each and 2 bits for an instruction (style: 00 xx yy zz)

So I went about doing designing it like this:

```
00 xx yy zz

00 00 yy zz
00 01 yy zz
00 10 yy zz
00 11 yy zz
10 00 yy zz
10 01 yy zz
10 10 yy zz
10 11 yy zz
11 00 yy zz
11 01 yy zz

11 10 00 zz
11 10 01 zz
11 10 10 zz
11 10 11 zz
11 11 00 zz
11 11 01 zz
11 11 10 zz

11 11 11 00
11 11 11 01
11 11 11 10
11 11 11 11

```

and the last one is all 1s so I guess it's correct. Maybe if there are no tutorials on YouTube, someone can simplify it or explain it here in text?

# Answer
It looks like this is simply the problem of mapping a set of possible values (i.e., possible instructions) to some bit encoding.

You haven't specified whether all instruction encodings need to have the same length.

* If they can have different lengths, usually you'll want them to form a prefix-free encoding (no encoded value is a prefix of any other).
* If all instruction encodings must have the same length,any mapping that gives different instructions different encodings is acceptable.

Your solution doesn't look OK to me. `00 00 yy zz` is a prefix of `00 xx yy zz` if `xx`, `yy`, and `zz` are the addresses `00000000`.

Editorial comment: the exercise is a bit boring and trivial, and doesn't involve much in the way of deep concepts. It's just a matter of "bit-packing".
> 2 votes

# Answer
When designing a variable-length opcode you are doing the equivalent of *Huffman coding*. In the case that the opcodes have known, independent, and identically distributed probabilities then Huffman coding gives you the optimal symbol-by-symbol prefix code.

As @DW points out, what you need here is a *prefix code*. A code such that no opcode is the prefix of any other opcode. Prefix codes are equivalent to binary trees where each leaf of the tree is an opcode. So take any tree with the correct number of leaves, label each leaf with an operation, then the opcode for each operation is the path from the root to the leaf. (Where "going left" in the path is a "0" and "going right" in the path is a "1".)

If you know the probabilities of the operations you are encoding then you can create a Huffman tree by keeping a *priority queue* of nodes, where the "priority" here is the probability of the node. You start with the queue filled with the leaves (operations), each with its probability. On each iteration you pull out the two lowest priority nodes, create a parent for them, make the two low-priority nodes the children of the parent, and give the parent the probability that is the sum of the children. Then you insert the parent back into the priority queue and repeat until you have only one node left.

Alternatively, if you don't know the probabilities, but you are trying to design an encoding where operations with many operands have shorter opcodes and operations with fewer operands have longer opcodes, then you are trying to design an unbalanced tree with a specific number of leaves at each level. Start with the operations that need the fewest operands and build upwards.

In your example, you know you need 4 operations with zero operands, so start by creating a balanced tree with 4 leaves, 2 intermediate nodes and one root. Now you need 7 operations with one operand (plus the 4 operations with zero operands) so you build a balanced tree with 8 leaves, attach your "zero operand" tree to one of the leaves, and label the other 7 leaves with your 7 one-operand operations.

Next you need 10 two-operand operations. Just repeat the process of tree building from the bottom up, and eventually you will be finished. Then just read off the opcodes for each operation by following the path from root to the leaf corresponding to the operation.
> 2 votes

---
Tags: computer-architecture
---


# Question
Title: How do I reconstruct the forest of syntax trees from the Earley vector?
Using the Earley vector as a recognizer is quite straightforward: when the end of the string is reached, you just have to check for a completed axiomatic production started at position 0. If you have at least one, then the string is accepted.

Using the Earley vector to reconstruct the parsing tree(s) is less obvious. Actually, I cannot figure out how an algorithmic procedure would work, moreover the only references I found were either vague or super-technical. Could anybody shed some light on it?

# Answer
I am using terminology and notations from Earley's paper. It is possible that the description you read is different.

It seems frequent that general CF parsing algorithms are first presented in the form of a recognizer, and then the information management needed to actually build parse trees and parse forests is sort of added as an afterthought. One reason may be that keeping the information needed to construct the shared forest require cubic space $O(n^3)$ where $n$ is the length of the input string being parsed, but the space requirement is only square $O(n^2)$ for recognition, when this information is not preserved. The reason for this space complexity increase is quite simple: the parse forest size can be cubic.

The worst case time complexity is $O(n^3)$, as is well known.

The best reference for Earley's algorithm is of course Earley's paper, but it is not very explicit about building the parse forest. This can actually be a messy business, much more so than the fast talk of section 7 page 101 will let appear. To be true, Earley does not talk of parse forest, or of forest, but of "*a factored representation of all possible parse trees*". And there is a good reason for that: if he tried to produce a forest according to his grammar, his space (hence time) complexity bound would climb to $O(n^{s+1})$ where $s$ is the size of the longest rule right-hand-side. This is why other algorithms use grammars in binary form (not necessarily Chomsky Normal Form (CNF)).

Actually, *Earley uses binary form implicitly*, because that is necessary for the cubic time complexity. This is one of the major roles of the rule dot in states. But this implicit binary form produces parses and forests according to the binarized grammar, not to the original one, which, I fear, is a major source of obscurity. This is detailed further below.

One good way to understand how the forest is obtained is probably to look at it in a simpler case, the CYK algorithm. It is also often described as a recognizer, and the parser aspect is added at the end. You can look at the description in wikipedia. *The information needed to build the forest is what they store in the table of "backpointers".* Backpointers are essentially pointers to substrings (an associated symbol) that form the constituents of a string according to some rule. They give all possible ways of parsing a substring. Recall that CYK uses binary form, usually CNF, so that things are simpler. The CYK parser has fundamentally the same dynamic programming structure as Earley, but is much simpler. So understanding it well can be a significant help.

Going back to Earley's algorithm, I do not believe you need Earley vector to decide acceptance or to build parse trees and forests. What Earley calls vector in his paper appears only in page 97, in third paragraph of implementation. It is only a device to speed up the search of states pointing back at some given string position k, in order to get a better complexity. But all the information is in the state sets, implemented as lists of states. However, this information is not sufficient to build the forest of parse trees, because the algorithm does not keep track of the way(s) a state may be obtain. Indeed, the vector is even used to efficiently discard a state already found, independently of how it was found.

In section 7 of Earley's article, he explains that in order to "make the recognizer into a parser", i.e. to be able to recover parse trees, it is necessary to keep track of the way completions are done.

> Each time we perform the completer operation adding a state $E\rightarrow \alpha D.\beta \\; g$ (ignoring lookahead) we construct a pointer from the instance of $D$ in that state to the state $D\rightarrow \gamma. \\; f$ which caused us to do the operation. This indicates that $D$ was parsed as $\gamma$. In case D is ambiguous there will be a set of pointers from it, one for each completer operation which caused $E\rightarrow \alpha D.\beta \\; g$ to be added to the particular state set. Each symbol in $\gamma$ will also have pointers from it (unless it is terminal), and so on, thus representing the derivation tree for $D$.

Note that in this text, $f$ and $g$ are indices in the parsed string, pointing where the recognition of the rule left-hand side started (as the right-hand side symbol had been predicted. So $f$ is the string index where the recognition of $D\rightarrow \gamma$ started, and it ended at index $g$. These "completion pointers" are the Earley equivalent of the backpointers described (not too well in wikipedia) for the parser version of CYK.

From such a pointer (as described in the quote) we know that the $D$ in the rule instance $E\rightarrow \alpha D.\beta \\; g$ can itself be developped into a tree (or forest) that parses the input string $w$ from index $f+1$ to index $g$, which we note $w\_{f+1:g}$. The nodes immediately below $D$ are given by the rule $D\rightarrow \gamma$. By looking for the completion that lead to $D\rightarrow \gamma. \\; f$ we can then find other such pointers that tell how the last symbol of $D$ was obtained, and hence more information on the possible parse trees. Also by looking at the completion that recognized the symbol before last in an earleir state sets, you find how it was obtained, and so on.

Assuming you kept all the needed pointers as indicated in the paper, you can get all the shared tree representations starting from the last symbol recognized by the parser, which is of course the initial symbol of the grammar.

But I also skipped **the messy part**. Suppose you have a rule $U\rightarrow XYZ$, which I choose with a right hand side longer than 2 symbols, and another rule $W\rightarrow UV$, for an ambiguous grammar.

It may well happen that the parser will parse $w\_{f+1:g}$ into $X$, $w\_{g+1:h}$ into $Y$ and both $w\_{h+1:i}$ and $w\_{h+1:j}$ into $Z$. So, with the rule $U\rightarrow XYZ$, Both $w\_{f+1:i}$ and $w\_{f+1:j}$ parse into $U$.

Then it may also be that both $w\_{i+1:k}$ and $w\_{j+1:k}$ both parse into $V$. Then, with the rule $W\rightarrow UV$, the string $w\_{f+1:k}$ parse into $W$ in two different way, which correspond to an ambiguity of the grammar.

Of course, to avoid repeating computations, Earley's algorithm will attempt to share as much as possible of the two parsing computations. What it will actually share is obviously the recognition (and parsing) of $w\_{f+1:g}$ and $w\_{g+1:h}$ into $X$ and $Y$. But it will actually do a bit more: it will also share the beginning of the two distinct parses that recognize $U$ with the rule $U\rightarrow XYZ$. What I mean is that the state $U\rightarrow XY.Z \\; f$ will be found only once (with respect to what I am describing), in state set $S\_h$. It will be a common part of the two parses. Of course, things will temprarily diverge while parsing the $Z$ since they correspond to distict substrings, until they converge again when everything parses into W, when the state $W\rightarrow UV. \\; f$ is produced twice in state set $S\_k$.

So the forest of syntax trees can be a very strange one, with kind of siamese twin subtrees that may share the first two edges of some node, but not the third edge. In other words, it may be a very awkward structure. This may explain why Earley calls it "*a factored representation of all possible parse trees*", without being more specific.

Any attenpt to surgically separate the siamese twins, without changing the grammar will result in increased complexity. The right way to do it is to binarize the grammar.

I hope this will help you. Let me know. But I do insist that a good understanding of CYK parsing can help. There are other algorithms, simpler than Earley's, that can parse all CF languages efficiently.

You may find more general info on this parse forest issue in two other answers I gave: https://cstheory.stackexchange.com/questions/7374#18006 and https://linguistics.stackexchange.com/questions/4619#6120. But they do not go into specific details of Earley's algorithm.
> 10 votes

---
Tags: context-free, dynamic-programming, parsers, ambiguity, syntax-trees
---


# Question
Title: Minimum number of tests to identify subset of modules that trigger a bug?
I have an ordered set of $M$ software modules compiled together. The interaction of some $N$-tuple of these modules is causing a bug when the program is run.

I can run the program with any desired subset of the modules enabled/disabled, so I can test the program by running it with a certain subset of modules enabled and seeing whether it crashes or not (call that "a test"). I would like to identify which $N$ modules are causing this issue with the minimal number of tests. Assume that any particular test will lead to a crash if and only if it includes all of the $N$ problematic modules (and possibly others; but at least those $N$).

$N$ is known ahead of time.

For $N=1$, I can efficiently identify the culprit in $\log\_2(M)$ tests by binary search.

For other values of $N$, what approach can I take to identify the $N$ culprits?

# Answer
Now that the question has been edited to make it clearer what you are asking, there is a simple and elegant answer. The solution is: delta debugging. Delta debugging solves exactly this problem.

Let me elaborate.

## Problem statement

I am interpreting your question as asking about the following problem:

* We have $M$ software modules, and some way to run the program in a way where only a subset of them are active (and we can choose the subset freely).
* There is a subset $S$ of $N$ of the modules. There's a fault that is triggered whenever we run the program with all of those modules active. In other words, if the set of active modules is a superset of $S$, a fault will occur; otherwise, no fault will occur.
* The fault is perfectly reproducible and detectable.
* Now, we want to find the set $S$ using as few tests (invocations of the program) as possible.

## Solution: delta debugging

Delta debugging will solve this problem. If you have $M$ software modules, and some subset of $N$ of them are responsible for the fault, delta debugging can find the minimal subset that trigger the fault.

Delta debugging works by starting with all of the modules active, and gradually removing some of them. It picks out some chunk of modules, and tries running the program with those modules inactive. If the fault still occurs, then we know that none of them are responsible for the fault, so they can be permanently deactivated in all future tests. Delta debugging starts with large chunks, and gradually reduces the chunk size: it first tries deactivating the first $M/2$ modules, then deactivating the second $M/2$ modules; if neither of those offers any progress, then it tries deactivating the first $M/4$ modules, then the second $M/4$ modules, then the third $M/4$ modules, and then the last $M/4$ modules; then it moves on to chunks of size $M/8$; and so on.

For more details, allow me to point you to a nice description of delta debugging.

## Delta debugging is efficient

Delta debugging is expected to take about $O(N \lg M)$ tests, to find the subset.

You might notice how this is a nice generalization of binary search. When $N=1$, binary search needs $O(\lg M)$ tests, just as delta debugging does. The difference is that delta debugging also scales nicely when $N\>1$.

You might also notice that this is close to optimum. We can prove a $\Omega(N \lg(M/N))$ lower bound (roughly). In particular, there are ${M \choose N}$ possibilities for the subset $S$, and each test provides one bit of information (either it triggers a fault or not), so it is easy to see that we need at least $\lg {M \choose N}$ tests. Now

$$\lg {M \choose N} \approx \lg (M^N/N!) \approx N \lg M - N \log N \approx N \lg M - 0.7 N \lg N \ge N (\lg M - \lg N).$$

Therefore, delta debugging is approximately asymptotically optimal, in terms of the number of tests required.

For a more detailed performance analysis, see this analysis by Jesse Ruderman.

## Discussion

That said, I am somewhat skeptical of whether this will be useful in practice. A crucial assumption here is that you could run the program with a chosen subset of its modules active, and the rest artificially deactivated. I don't see how to do that in practice. Therefore, I do not see how this can be applied in practice.

I suspect your theoretical model of the problem probably needs to be adjusted, but since you didn't tell us anything about your particular application setting or the justification for your model, I don't have enough information to specify how to fix the model.

Typically, delta debugging is used for a different purpose. Normally, delta debugging is used to reduce the size of the test case (not the size of the program). Say you have a test case with $M$ lines that crashes your program, but only a subset of $N$ of the lines are actually necessary to trigger the crash (the rest are all irrelevant), and you want to find the minimal subset of lines needed. In other words, given a long complex test case that crashes your program, you want to "minimize" it: to find a smaller, shortest test case that also crashes the program -- because small test cases usually make the debugging process easier. Then delta debugging can be used to solve that problem; in fact, that's what it was invented for, and what it's most commonly used for.
> 4 votes

# Answer
The answer depends upon whether you are interested in this as a theoretical exercise or if you have a practical problem to solve.

## The theory

There are tons of theory papers written about how to select a set of such tests. The standard catchphrase is "combinatorial testing". You should easily be able to find tons and tons of research papers, white papers, tools, and written material explaining the approach. It is known in the literature how to design tests that involve the minimum number of tests possible. See also "pairwise testing", which is basically the special case where $N=2$.

Incidentally, it is *not* correct that for $N=1$, $O(\lg M)$ tests suffice. Typically, $N$ tests will be needed, since all you have is an oracle that says "found the bug" or "that wasn't the bug". Binary search can only be applied if you have a way to also get ordering information (e.g., "the bug is in a higher-numbered component"), which usually isn't available in software testing.

## A practical perspective

Don't get too caught up in the theory. The practical value of these methods is dubious.

A short summary of the research literature is: the fancy methods don't perform much better than random testing. Combinatorial test design gives at most an $N$ reduction in the number of tests, compared to random/exhaustive testing. Since $N$ is usually small (e.g., $N=2$), this is a small improvement. (When $N$ is large, you usually can't use exhaustive combinatorial testing anyway, since there are too many combinations.) And combinatorial testing is complicated, whereas random testing is very easy to implement. Usually, generating a few extra test cases isn't that hard. Therefore, the extra developer time and effort needed to implement combinatorial testing often isn't worth it. Generating test cases is cheap; but developer time is expensive. So, in most software development settings, combinatorial testing just isn't a win in most cases.

Pragmatically, it's often better to just generate random tests, use them to find reproducible failures, and debug from there.

Also, you shouldn't assume that the world will be so clean as your model indicates. Let's say the bug involves modules D and Q. It doesn't necessarily mean that any input that activates modules D and Q will necessarily find the bug; typically, there are other complex conditions. Also, usually obtaining full coverage of even a single module is quite challenging, so the premises of the theoretical model tend not to fit the real world very well.

## More resources

See, e.g., the following questions on the Software Quality Assurance & Testing StackExchange site:
> 1 votes

# Answer
The problematic set of modules is an $N$-tuple. Checking every distinct $N$-tuple would take $\binom{M}{N}$ tests (an upper bound).

You can do binary search on the union of $N$-tuples, which takes $\log\_2 \binom{M}{N}$ tests - at the expense of some temporary storage to hold the tuples.

This reduces the problem to the $N=1$ case in the problem statement.

**Aside:**

(It can be done in $M$ tests even for unknown $N$ by leaving all modules enabled, and running $M$ tests each with one module disabled.)
> -1 votes

---
Tags: time-complexity, search-algorithms, software-testing, binary-search
---


title: Is the Calibron 12 puzzle NP-hard?

text:
# Question
Title: Is the Calibron 12 puzzle NP-hard?
So, I was analyzing the Calibron 12 puzzle and to me it looks like a bin-packing problem. Is this puzzle actually a bin-packing problem and thus NP-hard for the perfect solution?

Basically, you can make your own calibron 12-ish puzzle by doing the following:

Take a rectangular piece of wood. Cut the wood into randomly sized rectangles. Jumble the pieces. Now put it back together into the exact same shape. (note there are technically 4 solutions, due to mirroring vertically or horizontally also fitting the exact shape)

# Answer
> 2 votes
It depends what you mean by this puzzle. If you mean specifically Calibron 12 then no, there is no growth factor (there are only ever 12 pieces) so the solution can be found in constant time (a very slow constant).

If however you want to know about puzzles of this nature it is hard to determine. The problem could potentially be phrased as, Is there some arrangement of these $n$ objects that can completely fill this square. Now to me this does not seem likely to be polynomial-time in nature (I am speculating based on the permutations of arrangements, but I do not have a proof).

The bin packing comparison does not really work however since this has almost nothing to do with separating $n$ objects into the smallest number of bins. This is a category of questions called tiling problems.

Here is a paper that deals with Rectangle tiling, which is a related problem.

# Answer
> 2 votes
In order to answer this question you need to generalize the puzzle. The following generalized version of the puzzle is NP-complete:

> **Packing puzzle**
>
> Given a set of $n$ rectangles given by their widths and heights $(w\_1,h\_2),\ldots,(w\_n,h\_n)$ is it possible to pack them in to a $W\times H$ rectangle?

Membership in NP is trivial. One possible reduction to show completeness is from 2-Partition, which asks if it is possible to divide a set of numbers $x\_1,\ldots,x\_n$ with sum $2M$ in to two sets so that both sets sum to $M$.

The reduction is obtained by setting $W=M$ and $H=4M$, and for every number $x\_i$ making an input rectangle $(x\_i,2M)$. Any solution of the puzzle is then also a solution to the partition problem, since the pieces only fit in to the rectangle in a vertical orientation. A solution will consist of two horizontal rows of pieces, and the pieces that are in each row correspond to the partition.

---
Tags: time-complexity, np-hard
---


# Question
Title: Is there a PDA for every Type 3 Grammar?
we learned that for every type 2 grammar G exists a PDA A with L(A) = L(G). But does for every type 3 grammar G exist a PDA A\_G with L(A\_G) = L(G)? I think it does, because type 2 grammar is a subset of type 3 grammar. Am I wrong?

# Answer
> 3 votes
You need to check the definitions: type-3 (regular) is a (proper) subset of type-2 (context-free). Therewith, every type-3 language has a PDA that accepts it.

Essentially, you take a finite automaton for your type-3 language, add the stack but never use it. Up to minor definitory differences (e.g. w.r.t. acceptance), this gives you a PDA for the language. This is also one way to prove that all regular languages are context-free!

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


# Question
Title: Proof that finite automata is closed under intersection
I'm looking at a proof that says that: If $M\_1=(Q\_1, \Sigma , q\_1, A\_1, \delta)$ and $M\_2=(Q\_2, \Sigma , q\_2, A\_2, \delta)$ are two finite automata(FA) then $M=M\_1 \cup M\_2$ is also an FA. We define $M=(Q, \Sigma , q, A, \delta)$ where $Q=Q\_1 \times Q\_2$, $q\_0=(q\_1,q\_2)$ and $\delta((p,q),\sigma)=(\delta(p,\sigma),\delta(q,\sigma))$.

I'm just having one problem. We have to prove that $\delta^\*((p,q),x)=(\delta^\*(p,x),\delta^\*(q,x))$. (x is a string in $\Sigma^\*$) We do it by induction. I've already proven the base case, and I'm now trying to prove it holds for $x'=x\sigma$. This is what I've gotten so far:

$\delta^\*((p,q),x')=\delta(\delta^\*((p,q),x),\sigma)=\delta(\delta^\*(p,x),\delta^\*(q,x)),\sigma)$

I don't really know how to proceed from here. Can someone help?

# Answer
> 3 votes
A possible source of your confusion is that the transition functions of $M\_1$, $M\_2$ and $M$ are different functions, yet you call all of them $\delta$. If instead you use $\delta\_1$ resp. $\delta\_2$ for the transition function of $M\_1$ resp. $M\_2$, the definition of $\delta$ changes to $\delta((p,q),\sigma)=(\delta\_1(p,\sigma),\delta\_2(q,\sigma))$. You should be able to add the subscripts in the appropriate positions of your partial proof yourself.

Now, after noting that $\delta\_1^\*(p,x)\in Q\_1$ and $\delta\_2^\*(q,x)\in Q\_2$, the proof can be completed by a straightforward application of the definitions of $\delta$ and $\delta\_i^\*$.

---
Tags: automata, finite-automata, closure-properties
---


# Question
Title: Disruption in the context of Genetic Algorithms
I'm trying to do a homework problem which references "disruption" in Genetic Algorithms.

> True or false? For 1-point and 2-point crossover, the schemata which have bits that are close together on the string encoding are more likely to be disrupted by crossover.

I think that it is referring to is the creation of children distinct from their parents.

For example, combining the following two parents at a single crossover point at the second digit would just create the same parents again. Thus, no disruption would occur.

```
p1: 00000
p2: 00001

```

However, combining the following two parents at a single crossover point at the second digit would create some disruption.

```
p1: 00000
p2: 01001
c1: 01000
c2: 00001

```

By intuition, I would measure disruption as the number of bits that are different in a child as compared to the two parents. However, I have no formal definitions of this, despite turning to Google. The closest I've come is to Holland's Schema Theorem, which I think is related, but I would still like a definition or an explanatory reference.

# Answer
According to my professor, my intuitive description of disruption is correct, however one does not measure the "degree of disruption". It is a binary measure. Either you have disruption or you do not.

Still can't find an official source for this, so edits to this answer and other answers are welcome.
> 0 votes

---
Tags: algorithms, genetic-algorithms
---


# Question
Title: criterion for two line segments intersecting
I have two line segments $\[(x\_1, y\_1),(x\_2, y\_2)\] $ and $\[(x\_3, y\_3),(x\_4, y\_4)\] $ and I want to know if they intersect.

My current algorithm tries the following:

* the line $\[(x\_1, y\_1),(x\_2, y\_2)\] $ is determined by $\boxed{f(x,y) = \frac{y - y\_1}{x - x\_1} - \frac{y\_2 - y\_1}{x\_2 - x\_1} = 0}$.
* I reasoned that if $y = mx+b$ is my line, I want a point such that $y \> mx+b$ and one such that $y \< mx+b$.
* I want to check if that $f(x,y)$ has opposite signs if I set it on $(x\_3,y\_3)$ and $(x\_4, y\_4)$. So the criterion I check right now is: $$ \frac{f(x\_3,y\_3)}{|f(x\_3,y\_3)|}\\; \frac{f(x\_4,y\_4)}{|f(x\_4,y\_4)|} = -1 $$ Unfortunately in my visualization, I still see line segments intersecting.

Is there something wrong with my algorithm? What is a correct way to check that two line segments intersect?

# Answer
> 4 votes
You need to know about the orientation test.

For any three points, compute the determinant

$$\Delta\_{123}=\left| \begin{array}{ccc} x\_1 & y\_1 & 1 \\ x\_2 & y\_2 & 1 \\ x\_3 & y\_3 & 1 \end{array} \right|.$$

This is twice the signed area of the triangle $123$. When it is $0$, it tells you that the three points are aligned. Otherwise, it tells you on what side of the line joining two points the third lies.

In your case, there is an intersection if $1$ and $2$ are on either sides of $34$, while $3$ and $4$ are on either sides of $12$: $$(\Delta\_{134}\>0)\ne(\Delta\_{234}\>0)\land(\Delta\_{123}\>0)\ne(\Delta\_{124}\>0).$$

It is up to you to decide what to do in cases of perfect alignments.

As an extra goodie, the $\Delta$'s can be used to compute the coordinates of the intersection. (Let $P$ be the intersection point, interpolated along the segment $P\_1P\_2$: $P=(1-t).P\_1+t.P\_2$; it is easy to show that $(1-t)\Delta\_{134}+t\Delta\_{234}=0$ and to find the value of $t$.)

# Answer
> 3 votes
The vector equation:

$$P\_1 + \alpha * (P\_2 - P\_1) = P\_3 + \beta * (P\_4 - P\_3)$$

where $P\_1 = (x\_1, y\_1)$ etc., should have a solution in the unit square:

$$0 \le \alpha \le 1, 0 \le \beta \le 1$$

then these two segments $(P\_1, P\_2)$ and $(P\_3, P\_4)$ do intersect. However, there are many corner cases here (for example, $P\_1 = P\_2$ etc.). Also, you can get wrong answers because of the limited precision of your data representation in computer.

---
Tags: computational-geometry
---


# Question
Title: Algorithm for creating a directed graph using flat data input
Given flat data like this:

```
01001, Butter, salted
01002, Butter, whipped, with salt
01145, Butter, without salt
04601, Butter, light, stick, with salt
04602, Butter, light, stick, without salt

```

What's the best approach to convert into this:

```
Butter (01001, 01002, 01145, 04601, 04602) -> salted (01001)
                     -> whipped (01002) -> with salt (01002)
                     -> without salt (01145)
                     -> light (04601, 04602) -> stick  (04601, 04602) -> with salt (04601)
                                                                      -> without salt (04602)

```

I was thinking of recursive sorting first, but I realized there may be a lot of string comparisons to be efficient.

# Answer
> 1 votes
It looks like you're making a tree based on elements after the first. Some quick pseudocode for this might look like:

```
 1. Start with a tree containing only the root.
 2. Set the current node to the root.
 3. Read a line of input = (ID, tail)
 4. For each object in tail, do
 5.     if the current node has a child equal to the current object, then
 6.         move to that child node
 7.         add the current ID to the list of IDs associated with that node
 8.     else,
 9.         add a new child node corresponding to the current object
10.         start a list of associated IDs using the current ID as the first entry
11. Repeat from step 2. until there is no more input

```

Showing this on your example:

```
Initial:
Root

Pass 1: (ID, tail) = (01001, (Butter, salted))
Root
- Butter (01001)
  - salted (01001)

Pass 2: (ID, tail) = (01002, (Butter, whipped, with salt))
Root
- Butter (01001, 01002)
  - salted (01001)
  - whipped (01002)
    - with salt (01002)

Pass 3: (ID, tail) = (01145, (Butter, without salt))
Root
- Butter (01001, 01002, 01145)
  - salted (01001)
  - whipped (01002)
    - with salt (01002)
  - without salt (01145)

...

```

Basically, you're constructing a *tree*, one *branch* at a time.

---
Tags: algorithms, search-trees
---


# Question
Title: Is the "subset product" problem NP-complete?
The subset-sum problem is a classic NP-complete problem:

> Given a list of numbers $L$ and a target $k$, is there a subset of numbers from $L$ that sums to $k$?

A student asked me if this variant of the problem called the "subset product" problem is NP-complete:

> Given a list of numbers $L$ and a target $k$, is there a subset of numbers from $L$ whose product is $k$?

I did some searching and couldn't find any resources that talked about this problem, though perhaps I missed them.

Is the subset product problem NP-complete?

# Answer
> 13 votes
A comment mentions a reduction from X3C to SUBSET PRODUCT attributed to Yao. Given the target of the reduction it wasn't hard to guess what the reduction was likely to have been.

Definitions:

> EXACT COVER BY 3-SETS (X3C)
>
> Given a finite set $X$ with $|X|$ a multiple of 3, and a collection $C$ of 3-element subsets of $X$, does $C$ contain an exact cover $C'$ for $X$, where $C' \subseteq C$ and every element in $X$ occurs in exactly once in $C'$?
>
> SUBSET PRODUCT
>
> Given a list of numbers $L$ and a target $k$, is there a subset of numbers from $L$ whose product is $k$?

To reduce an X3C instance to a SUBSET PRODUCT instance:

1. Establish a bijective mapping between the members of $X$ and the first $|X|$ prime numbers. Replace the members of $X$ and the $C$ subsets with the mapped primes.
2. For each subset in $C$, multiply its members together; the resulting list of products is $L$ for the SUBSET PRODUCT instance. Because prime numbers are used for the mapping in step 1, the products are guaranteed to be equivalent iff the subsets are equivalent by the unique factorization theorem.
3. Multiply the members of $X$ together; the resulting product is the value $k$ for the SUBSET PRODUCT instance.

The prime factors of $k$ are exactly the members of $X$. The prime factors of the numbers in $L$ correspond exactly to the members of the $C$ subsets. Therefore any solution to the new SUBSET PRODUCT instance can be transformed into a X3C solution by mapping the solution members of $L$ back to the subsets in $C$.

Each of the 3 transformation steps involves operations that are polynomial to the size of the input $|X|$ or the size of a member of $X$. The first $|X|$ primes can be generated in time O($|X|$) using the sieve of Eratosthenes and are guaranteed to fit into $O(|X|^2 \ln |X|)$ space by the prime number theorem.

# Answer
> 9 votes
According to \[\]: Yes it is

I also cite the same reference: Comments: There is a subtle technical distinction between this and Problem 42: the former case has a pseudo-efficient algorithm obtained by allowing numbers to be represented in unary; unless all NP-complete problems can be solved by fast algorithms, however, the Subset Product Problem, cannot be solved by \`efficient' methods using even this unreasonable input representation.

have a look on \[2\] for a reduction. \[2\]: Fellows, Michael, and Neal Koblitz. "Fixed-parameter complexity and cryptography." Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (1993): 121-131.

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


# Question
Title: why negative cycle exists if we can relax the edges one more time after running the Bellman Ford Algorithm
We know Bellman Ford is an algorithm to find the negative cycle. And here is the algorithm for Bellman Ford Input: Given a graph G(V,E) and w(e) is weight Output: Return Yes if negative cycle exists.

```
1: set d(s) = 0 and d(v) = 1 for all v (- s
2: for i = 1 ... n-1 do
3:      for every edge (u, v) in G do
4:        if d(v) > d(u) + w(u,v) then
5:           d(v) = d(u) + w(u,v)
6:      end for
7: end for
8: for every edge (u, v) in G do
9:     if d(v) > d(u) + w(u, v) then
10:       return True
11:return False

```

Line 8 - Line 11 is the doing one more relax to detect the negative cycle, but why these lines guarantee detect the negative cycle if have one in the graph?

# Answer
If there is a negative cycle, then it is guaranteed that $d(v)$ will decrease on each iteration for each vertex $v$ in a negative cycle, since as we do more iterations of Bellman-Ford we're considering paths that traverse that negative cycle more and more times. The more you traverse a negative cycle, the more negative the length of that path becomes. Therefore, it's guaranteed that if the graph has a negative cycle, then this algorithm will detect it, because it'll see the value of some $d(v)$ decrease.

This should be covered in standard textbooks and lecture notes on Bellman-Ford. There's not much point in having us reiterate those standard proofs again; if we don't know why you didn't understand the standard explanation, it's hard for us to write an explanation that you will help you.
> 1 votes

---
Tags: algorithms, dynamic-programming, shortest-path, correctness-proof
---


title: Shortest-depth routing algorithm

text:
# Question
Title: Shortest-depth routing algorithm
This problem came up in a graph network routing context, it can be expressed as follows:

> Let $n, m \> 0$ be integers. Find any smallest list of positive integers $\langle a\_1, \cdots, a\_k \rangle$ such that:
>
> $$1 + \sum\_{i = 1}^k \prod\_{j = 1}^i a\_j = n$$
>
> With the added condition that $a\_i \leq m$ for all $1 \leq i \leq k$.
>
> (for a challenge, add the constraint "with the least number of $1$'s", but the above would suffice)

Graphically, if you picture a tree of depth $k$ (with a single root) with branching factors $a\_i$ at each level, the algorithm asks for the shortest such tree containing exactly $n$ nodes in it, with each branching factor at most $m$. For instance, taking $n = 12$ and $m = 5$ as an example, we see that $\langle 1, 1, 3, 2 \rangle$ is a solution, since:

$$1 + (1) + (1 \cdot 1) + (1 \cdot 1 \cdot 3) + (1 \cdot 1 \cdot 3 \cdot 2) = 1 + 1 + 1 + 3 + 6 = 12$$

Which corresponds to the tree with branching factors $1, 1, 3, 2$ shown below:

But there is a shorter solution, given by $\langle 1, 2, 4 \rangle$, as illustrated by the tree:

And there is no shorter solution with $m = 5$, in fact the only other solution of length $3$ is $\langle 1, 5, 1 \rangle$. Note the solutions need not start with $1$, e.g. $\langle 4, 3, 1 \rangle$ for $n = 29$ (the order is clearly very important).

---

We are talking $n \approx 10^8$, $m \approx 10^4$ in my case (but asymptotic algorithms are welcome!)

I solved it quickly using a brute force approach, which is pretty inefficient, running in exponential time. Is there an easy lower/upper bound on the length of the smallest solution in terms of both $n$ and $m$, and an efficient algorithm to find one such solution? My first thought was a backtracking algorithm, but it doesn't seem to help since you usually get stuck at the leaves of the tree where you realize you can't find a branching factor that will make it add up to $n$, perhaps there is a clever number-theoretic algorithm to select good branching factors as you go?

One optimization I came up with is that if you are at depth $i$ in the tree, then you can calculate the number of nodes you've already added as $x$, then the branching factor for the next tree level must necessarily divide $n - x$, so it might be efficient to go for branching factors that lead to prime values of $n - x$, then we can build a set of optimal solutions for small primes and look them up as needed to complete the tree (going for primes with shorter solutions first). But that doesn't appear to guarantee a shortest solution...

Well, it does reduce the number of $a\_i$ candidates to explore down to $O(\log(n))$, but in the absence of a better bound or a procedure to not have to explore fully the tree of possibilities for $a\_{i + 1}, a\_{i + 2}, \cdots$, this does not make for an efficient algorithm, even if the length of the shortest solution is (probably) upper-bounded by $O(\log(n))$.

Thanks!

PS: I wasn't totally sure what to tag this, so I filed it under combinatorics - please retag if there is a better category for this kind of problem!

# Answer
> 1 votes
## Problem statement

Define the function $f$ by

$$f(a\_1,\dots,a\_k) = \sum\_{i=0}^k \prod\_{j=1}^i a\_i.$$

In other words,

$$f(a\_1,\dots,a\_k) = 1 + a\_1 + a\_1 a\_2 + a\_1 a\_2 a\_3 + \dots + a\_1 \cdots a\_k.$$

Given $n$, you are looking for $a\_1,\dots,a\_k$ that form a solution to the equation

$$f(a\_1,\dots,a\_k) = n.$$

## A useful lemma

Let me point out a useful property of the function $f$:

$$f(a\_1,a\_2,\dots,a\_k) = 1 + a\_1 f(a\_2,\dots,a\_k).$$

This follows immediately from the identity

$$1 + a\_1 + a\_1 a\_2 + a\_1 a\_2 a\_3 + \dots + a\_1 \cdots a\_k = 1 + a\_1 (1 + a\_2 + a\_2 a\_3 + \dots + a\_2 \cdots a\_k).$$

## An algorithm for your problem

Now we get a reasonable algorithm for your problem, using dynamic programming.

Each subproblem is indexed by $(i,n')$, and records the best sequence $a\_i,a\_{i+1},\dots,a\_k$ such that $f(a\_i,a\_{i+1},\dots,a\_k)=n'$. Now we can find the best solution to the original problem by enumerating all possible values for $a\_1$, then looking for a solution to the $(2,(n-1)/a\_1)$-subproblem. And, we can solve the $(i,n')$-subproblem by enumerating possible values of $a\_i$ and looking for a solution to the $(i+1,(n'-1)/a\_i)$-subproblem. Of course, as a straightforward optimization, we can limit our search to only values of $a\_i$ that are a divisor of $n'-1$.

How many subproblems are there, in all? A simple bound is that there are at most $kn$ subproblems, so the running time of this algorithm is at most $O(kn^2)$. Using the optimization, I expect the running time will be much less in practice, as most values of $n'$ have only a limited number of divisors. (See also this question for a math question that is related to the efficiency of this dynamic programming algorithm.)

## Another optimization

Here is one more optimization you could apply. You could use modular arithmetic to quickly filter out subproblems that have no solution.

Suppose we have a small prime $p$, and we have fixed values of $k,n$. Then if there exists a solution to $f(a\_1,\dots,a\_k) = n$, then there exists a solution $f(a\_1,\dots,a\_k) \equiv n \pmod p$; conversely, if there is no solution to $f(a\_1,\dots,a\_k) \equiv n \pmod p$, then there is no solution to $f(a\_1,\dots,a\_k) = n$.

So, we could pick a small prime $p$, and then tabulate for which values of $(i,n')$ the $(i,n')$-subproblem has a solution. Note that we only care about the value of $n'$ modulo $p$, so there are only $kp$ such subproblems, and we can enumerate which ones have a solution in $O(kp^2)$ time using dynamic programming. (We cannot use the divisibility optimization any longer.)

So, we could precompute a table of size $kp$ and use it to filter out subproblems. Before trying to solve the $(i,n')$-subproblem, we first look up $(i,n' \bmod p)$ in our table to see whether it has a solution modulo $p$. If it doesn't have a solution modulo $p$, we don't try to explore that subproblem (we don't try to look for a solution in the integers; we know it'll fail).

We can build a table for each of a handful of small primes, say $p=2,3,5,\dots,17$, and check against each of these tables before exploring a subproblem. This might reduce the number of subproblems that have to be explored, and thus improve efficiency.

Can we use this idea plus the Chinese remainder theorem to solve the original problem? Unfortunately not: the requirement that $a\_i \le m$ does not behave well under modulo arithmetic. Thus, if all we wanted to know is whether there exists some sequence of positive integers $a\_1,\dots,a\_k$ satisfying $f(a\_1,\dots,a\_k)=n$, then we could solve that in $\text{poly} \log (n)$ time by looking for a solution modulo a set of small primes whose product exceeds $n^k$, then applying the Chinese remainder theorem. However, your question asks whether there exists a sequence $a\_1,\dots,a\_k$ satisfying $f(a\_1,\dots,a\_k)=n$ such that $a\_i \le m$ for each $i$, and that cannot be solved efficiently in such a way. If you were willing to drop the requirement that $a\_i \le m$, then your problem could be solved a lot more efficiently.

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


title: Why was Alan Turing important?

text:
# Question
Title: Why was Alan Turing important?
What is the importance of Alan Turing? What were his inventions or innovations and why are they so influential?

# Answer
He laid down the foundations to understanding "computing" from a mathematical perspective. His paper about what is today called the Turing Machine shows his reflections on a model, in mathematical terms, of how the human\_brain/thought\_process works.

Based on that, he develop a theory of computation (with the aim of automating math thinking; kind of similar to previous work done until his days based on formal methods, i.e. logic) and found very interesting "phenomena":

* He described what is now called a Universal Turing Machine, i.e. that it is possible to develop a machine where the workings of any other machine could be simulated. In today's terms, he discovered computers were possible (i.e. a universal programmable machine).
* Then he solved, in the negative, the halting problem: the impossibility of writing an algorithm (in Turing Machine language) to determine whether a given program is going to stop or not.

This later result, if you think about it, is kind of similar to Gödel's incompleteness result in logic: say you have a machine that given a first-order logic formula $P(x)$ for natural numbers, starts from 0 and stops where it finds a number $n$ where $P(n)=0$, i.e. *false*. If we had a halting machine, then it is possible to determine the truth of $\forall n P(n)$ for all formulas $P$ by simply running our halting machine with that iterating machine with input $P$; this contradicts Gödel's result.

The interesting part is that Turing's proof is actually quite simple. So, if you think that Turing truly captured the nature of the human thought, then this result is even more fundamental!

Also, his theory laid the foundation to explore a related problem, measuring/modelling computing time and memory consumption; nowadays called complexity theory.

You also want to know that there were similar theories around his time: von Neumann's register machines and Church's lambda calculus (all of them later proved to be equivalent). Interestingly enough, although modern computers are based on von Neumann's model, Turing's theory was the preferred (as far as I remember) method to study algorithms and complexity, and is still used today as reference model for the still open Millenium's P vs NP problem, which has an unclaimed prize tag of one million dollars!

Hope the above complements good enough what you can already find in wikipedia.
> 8 votes

---
Tags: history
---


# Question
Title: Correct term for “string consisting of words”
In a paper I am writing I want to make distinction between (1) *string consisting of any characters* and (2) *string consisting of a chain of words from known language, with possible delimiters*. My intuitive idea is to simply use *string* for meaning (1) and *text* for meaning (2). It sounds a bit naive, but this terminology could work, given that I define it properly in my paper.

Yet I have an uneasy feeling that meaning (2) has fancier name in fields of computer science or computational linguistics. So, what are the precise terms to make distinction between the two types of strings?

**UPDATE**

Suppose we have an alphabet `Σ = {a, b, c, ~}`, where `~` is a delimiter symbol, and language `L = {aaa, bbb, abc}`.

Now, the following strings satisfy definition (1), but **not** (2):

* *cba*
* *a*
* *aaaa*
* *a~b~~*

And the following strings would satisfy **both** definitions (because they are made of the words of language L).

* *aaabbbabc*
* *abc*
* *aaa~bbb~aaa~~~aaa*
* *~*
* (an empty string)

In some applications my strings could be actual text in a human language like English, Lithuanian or Esperanto. But this is not required. It could also be a DNA chain, a binary file, or anything else. Also keep in mind, that in practical applications the strings would most likely be long (like a journal article, or entire corpus for that matter), so calling it a "sentence" would be a bit of understatement. Meaning of the text is entirely irrelevant here.

So, regarding definition (1) all is clear - I just call it a *string* on alphabet Σ. Now the core question is this: what do I call the strings from the second example to make them distinct from the first example. My initial idea is to call it a "text". One of the answers proposed "word string", which I like even better. Maybe you have seen other terms being used for such purpose in the literature?

It might seem that I'm in extreme hair splitting mode here. Yet that term will be all over my PhD thesis, very likely including the title. Therefore I really want to get my terminology straight.

# Answer
> 4 votes
If definition (1) is intended for any sequence of characters, I would simply call it *string* as you suggest, but I would call it *word* or *lexeme* if it is intended to be words of a language.

Regarding definition (2), it depends again on what you are expecting to consider. If it is any sequence of words, usually meaningless, with a variety of separators, the name *text* would do fine, and I would not worry too much about computational linguistic since the only meaningless piece of text that matters in CL is "*Colorless green ideas sleep furiously*".

If it is actually intended to be a sentence of a language, then you might call it *sentence*. I feel that *text* would rather be used for larger pieces of discourse. You should be careful though that is is not confused with *sentence* meaning a string of words. Speech processing people may speak of *utterance*, but it may be inappropriate for your use. They use also *sentence*, which they structure into *word lattice* when the separators are not clearly identified, which amounts to a *word sequence* or *word string* if they are clearly identified.

This disctinction may also depend on whether your separators are one or many, and whether they have a role.

In other words, it is hard to give you a precise answer without more details on what you are doing. I first tried, and then realized that it led me to make unwarranted assumptions about what you are doing.

The one thing that is really important is that you are very clear about your definitions. And if you can motivate your terminology choices, that may help the reader. I am still wondering why the *borogoves* had to be so *mimsy*.

# Answer
> 0 votes
Lets assume you are defining sets using your definition. It is obvious that the set defined by (2) is a subset of the set you are defining by (1) right now. But that is offtopic.

I am quite sure that there is no fancy word for what you are calling a text, since your definition is very vague. As a text you are defining a list of words contained in a dictionary, separated by delimiters. I would certainly not call this a text. If your "text" has a meaning which is based on an under-laying grammar you can call it a sentence, a statement or a paragraph.

# Answer
> 0 votes
What you're looking for is a bag of words. It has a Machine Learning connotation as it is where the concept is used, though.

---
Tags: terminology, strings, computational-linguistics
---


# Question
Title: Understanding the symbolic computation of a derivative
I've been watching the sicp videos lectures by Hal Abelson and Gerald Jay Sussman and am lost on lecture 3b. Can someone explain to me what's going on in this video?

https://www.youtube.com/watch?v=X21cKVtGvYk

What is numerical approximation vs exact expression?

# Answer
> 1 votes
After watching a whole minute with the speakers off.

It is using the language Lisp, or more probably Scheme, which is very close, to program a system that does calculus. For example it can take a function on the reals and compute its derivative. The function being differentiated is also written in Lisp. This is permitted by the fact that all Lisp entities, including programs, have a syntactic representation that can be manipulated by Lisp programs. This is actually where the idea of abstract syntax (tree) comes from, even though it is most rudimentary in Lisp. It permitted to write tools to transform programs, or to compute new programs (such as the derivative), and then maybe execute them, which led to all kinds of applications. If you see a relation with Turing machines taking the Gödel number of other Turing machines as argument ... there is hope. BTW The book by Abelson and Sussman is excellent reading, even though it is old.

---
Tags: programming-languages
---


# Question
Title: Dynamic Programming Solution to 0,1 KnapSack Problem
I am trying to understand the DP solution to the basic knapsack problem.However even after reading through a variety of tutorials ,its still beyond my comprehension.I am taking an algorithmics course and need to solve questions based on the classic knapsack problem.However unless I understand the classic problem clearly , I won't be able to make any headway to the advanced ones.Please help pointing me out in the right direction.

The recursive equation is way too confusing for me.

# Answer
The key to understanding a dynamic programing problem is understanding the recursive definition and this can be daunting. For this problem we start with n objects labeled 1 to n.

We define $O(K,W)$ to be the optimal value for the first k items with a total weight W, we need to be able to define this in terms of subproblems now since without that, dynamic programming does not work. To add some quick definitions $W\_k$ is the weight of the kth item and $V\_K$ is its values.

So we define the recursive formula in 2 cases:

The first case is $O(K,W) = O(K-1,W) \quad \text{if $W\_k$\>W}$, meaning the k'th item weighs more then are target weight so it cannot be added even if nothing else was in the bag.

The second case is the decision case, $O(K,W) = MAX(O(K-1,W),O(K-1,W-W\_k)+V\_k)$ it means that either we don't add Item K to our set, in which case our best so far is $O(K-1,W)$, or we do add it, in which case we only have $W-W\_k$ weight remaining to be filled with items 1 to k-1 and our total value is $O(K-1,W-W\_k)+V\_k$, which is our recursive value plus the value of the new Item.

The optimal solution is then $O(n,MaxWeight)$

Now for the dynamic programing part, the best way to start out is with our standard grid, we have our horizontal portion as k, so at any $i$ point we have the first $i$ items available, and our vertical as the total weight from zero to the weight the question was asking. The first row and columns will have a value of zero since with no weight or items, our bag has no value. Below I have put good walk through example. We walk through the algorithm by moving down each column, one column at a time. So at any grid location we check 3 other grid points which correspond to the values from the recursive definition, If we are at grid point $k,W$ and item k has a weight of$W\_k$ and a value of $V\_K$ we first check if $W\<W\_K$, if it is we use the square above it, since our item is too big, this is $O(K-1,W)$, if the item is not too big you check locations $k-1,W$ which is $O(K-1,W)$ and compare it to $K-1,W-W\_k$ which is $O(K-1,W-W\_k)+ V\_k$, since we are going column by column from smallest to largest these are already calculated. If we keep doing this we will eventually get to the bottom right corner, which is the solution to the problem. The trick to this is we start at the smallest values and save the answers so for larger one the recursion is only a quick lookup instead of a full call.
> 8 votes

---
Tags: dynamic-programming, knapsack-problems
---


# Question
Title: Master Method to solve recurrences is 'a' related to 'b'?
The master method allows us to solve certain recurrences of the form

$$T(n) = aT(n/b)+f(n)\\,,$$

where $a\ge1$ and $b\>1$ are constants and $f(n)$ is a positive function with some further restrictions that aren't important for this question.

The above recurrence describes the running time of an algorithm that divides a problem of size $n$ into $a$ subproblems, each of size $n/b$. This is intuitive in the case that $a=b$ (for example, merge sort divides the list into two parts of size $n/2$) but are there any examples of recursive algorithms that follow this schema but where $a\neq b$?

# Answer
No it's not always the case that $a=b$, since you might not necessarily use every sub-problem. Consider for example, the binary search algorithm. In the algorithm, you have a sorted array that you break into two sub-problems of the same size ($b=2$), but only recurse on one of them ($a=1$). In this case, the recurrence would look like: $$T(n) = T(n/2) + O(1)\\,.$$

For an algorithm like merge-sort however, not only is the problem broken into two sub-problems of equal size, but you recurse on both sub-problems before merging the results. In this case, you have that $a = b = 2$, and so, the recurrence looks like: $$T(n) = 2T(n/2) + O(n)\\,.$$
> 7 votes

---
Tags: algorithm-analysis, recurrence-relation, master-theorem
---


# Question
Title: Computing the number of bits of a large power of integer
**Given two integers $x$ and $n$ in binary representation, what is the complexity of computing the bit-size of $x^n$?**

One way to do so is to compute $1+\lfloor \log\_2(x^n)\rfloor=1+\lfloor n\log\_2(x)\rfloor$ by computing an approximation of $\log\_2(x)$ with sufficient precision. It appears that computing $\log\_2(x)$ with $k$ bits of precisions can be done in $O(M(k)\log k)$ where $M(k)$ is the time needed to compute the product of two integers of length $k$. This yields a (not specially simple) algorithm of complexity approximately $O(s\log^2 s)$ if $s$ is a bound on the bitsize of both $x$ and $n$ (if I made no error).

**Can we beat $O(s\log^2(s))$ where $s$ is the size of $x$ and $n$ (in the case where they have comparable sizes)? Is there a simple algorithm to get this complexity or better?**

Note: I am interested in the complexity in a theoretical model such as Turing machines.

# Answer
**\[edit\]** As suggested, I edit my answer to give more details.

The answer to my second question is **no**:

**Proposition.** Computing $\log(x)$ up to precision $k$ is at least as hard as computing the bit-size of $x^{2^k}$.

**Proof.** Let $|y|$ denote the bit-size of an integer $y$. First notice that for a nonnegative integer $y$, the bit-size of $y$ is $1+\lfloor \log y\rfloor$.

Thus, $\left|x^{2^k}\right| = 1+\lfloor 2^k\log x\rfloor$. Now $2^k\log(x)$ is $\log(x)$ shifted $k$ positions to the left. Thus one can compute $\log(x)$ to precision $k$ by simply subtracting $1$ to the bit-size of $x^{2^k}$ and shifting the result $k$ positions to the right.
> 1 votes

---
Tags: complexity-theory, time-complexity, binary-arithmetic
---


# Question
Title: How do we find the optimal modulus q in Rabin-Karp algorithm?
I asked a similar question here on Rabin Karp algorithm. My present question is, how do we find the best $q$ (i.e modulus)? What is the criterion? We need to choose a $q$ which will be quick to calculate and also must result in lesser number of spurious hits, right?

Wow do we ensure these things?

# Answer
> 5 votes
The Rabin-Karp algorithm looks for a substring by computing a rolling hash, of the form $h(a\_{n - 1} a\_{n - 2} \ldots a\_0) = \sum\_{0 \le k \le n - 1} a\_k q^k$ for a prime $q$. Note that the algorithm works just the same if $h$ is computed modulo the word size, so using e.g. `unsigned int` in C would be wise. What we'd like is $q^{n - 1}$ not too large (so the needed $q^{n - 1} a\_{n - 1}$ doesn't overflow, and computations are in normal unsigned integers). Clearly $n$ (the length of the pattern) is limiting here, so you want a smallish prime. One option is to use the largest prime $q$ such that if $w$ is the word size and $A$ the largest character value (for UTF-8 it's essentially $2^8$) $$ 2^w \> q^{n - 1} A $$ This guarantees no collisions, but is very restrictive. Perhaps just taking $q = 3$ or $q = 5$ is enough (the hash value is still a full word, so collisions should be rare anyway). As they have just 2 bits one (Fermat primes, next one is 17, then 257), perhaps the compiler (or even the programmer) replaces the multiplication by the constant prime by shift and add, but if that is a net gain depends on architecture...

Note that the cited article says this makes sense only for multiple pattern search, as there are faster alternatives for single patterns.

To *really* answer you'd have to run tests with representative haystacks and patterns

# Answer
> 3 votes
Although @vonbrand has given a satisfactory explanation, in simple words if

* $d$ is the number of characters in alphabet
* $q$ is modulus

then $dq$ should be representable in the available word size.

---
Tags: algorithms, search-algorithms, strings
---


title: Computational complexity theory books

text:
# Question
Title: Computational complexity theory books
I recently attended a lecture on an introduction to computation complexity and I am looking to find out more, I haven't studied computer science or discrete mathmateics at university and I was wondering if anyone could recommend any relatively simple books or reading material that could help me understand the topic more

# Answer
Classic texts on computational complexity include Hopcroft & Ullman's text {1} and Sipser's text {2}. With patience, they should both be accessible.

---

{1} Hopcroft, John E., R. Motwani, and J. D. Ullman. "Introduction to Automata Thoery, Language, and Computation (2nd edition)". Addison-Wesley, Reading (2001).

{2} Sipser, Michael. Introduction to the Theory of Computation. Cengage Learning, 2012.
> 3 votes

# Answer
You may also be interested in scanning answers to the following questions on the TCS site:

https://cstheory.stackexchange.com/questions/3253/what-books-should-everyone-read

and

https://cstheory.stackexchange.com/questions/3540/what-are-the-recent-tcs-books-whose-drafts-are-available-online

They contain further pointers, and many comments.

But the two books suggested by Ari Trachtenberg are certainly a good start.
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: Syntax checking expressed mathematically
1) Set B is the finite set of all rules for a particular programming language.

2) Set A is the infinite set of all valid strings of that language and is defined by Set B.

I'm having a problem defining expressing that mathematically.

My so far unsuccessful idea:

* Define a set C - the set of all possible strings.
* set A is a finite union between infinite sets A\_i such that for every rule B\_i

$B\_i ( C ) = A\_i$

can It be defined with an implication ? for every rule B\_i of B applied to every string c\_i of C, if $B\_i ( c\_j ) \implies c\_j$

# Answer
The standard approach to formalize the syntax of a programming language involves using context-free grammars and context-free languages. I suggest reading a standard compilers textbook; it will discuss how to express the syntax of the programming language using techniques like context-free grammars, and that will provide you a lot of helpful context.

In particular, programming language syntax is typically formalized not by a set of "rules", but rather by a context-free grammar/language. The source code of a program must be in that language to be syntactically valid; if it isn't in the context-free language, it has a syntax error. See also Backus-Naur notation.

Take you a little while to read the material, and then I suspect you'll be in a better position either to make sense of this, or to pose a more specific question.
> 1 votes

---
Tags: compilers, mathematical-foundations
---


# Question
Title: What is the state of the art in efficient boolean function operations?
How do you most efficiently combine boolean functions with a large number of variables using AND, OR, and NOT? The most up-to-date work that I can find on this subject is about 20 years old (Efficient data structures for Boolean functions). Which search terms should I be using to explore this question?

Edit:

I am starting from about 200 simple boolean functions. These are combined with each other using AND, OR, NOT, and XOR to give other boolean functions, which are then also combined using AND, OR, NOT, and XOR. The process repeats about 3000 times, until a final combination gives me a single boolean expression. I'm interested in that final expression.

Representing the functions as DNF or CNF makes certain operations (NOT and XOR) slow. Representing the functions as ROBDDs is an option - are there any drawbacks here? I'm not sure whether SMT solvers are useful here, because I am interested in the final equation rather than whether the equation is satisfiable. What else should I be looking at?

# Answer
The obvious method is to use BDDs.

Given a BDD for two boolean functions $f,g$, you can form a BDD for $f \land g$, $f \lor g$, $\neg f$, $f \implies g$, $f \oplus g$ (xor), and many other binary operations on them. Also, given BDDs for $f,g$, you can test whether $f$ and $g$ are the same boolean function.

The worst-case behavior is that their size might grow to be exponential in $n$, the number of boolean variables, but empirically, the size often remains manageable in many real-world applications, e.g., when there is suitable structure in the underlying boolean functions. In the model-checking world, designs with 50-200 boolean variables are routinely handled using BDDs.

It's also possible to manipulate boolean expressions in symbolic form, and then use SAT solvers or SMT solvers to test for equivalence. This is another plausible alternative.

My advice is: try BDDs first, then if they don't scale well enough for your needs, you can try SAT-based solutions. If that still doesn't work, come back to ask for more suggestions (providing more details about your specific setting and what you've tried).
> 2 votes

# Answer
try also ZDDs (Zero-suppressed Decision Diagrams) for "sparse" functions where most evaluations are zero and subject to more recent research. Knuth has researched/implemented them and regards them highly, and compressions can be dramatically better in some applications. see also Minato for a survey/ contrast with BDDs & a database application.
> 0 votes

---
Tags: reference-request, boolean-algebra
---


# Question
Title: exponential lower bound on boolean formula conjunctions, what complexity class?
This new paper A Lower Bound for Boolean Satisfiability on Turing Machines by Hsieh asserts an exponential lower bound for a TM time complexity on a problem of finding whether a solution exists to a conjunction of boolean formulas. obviously this problem is not in NP, or it would be a P≠NP proof. But the paper does not give its known complexity class.

> What time complexity class is this problem of finding solutions to conjunctions of boolean formulas in?

Also looking for any other context wrt known theory to place this paper result in, i.e. How does it mesh with other known results etc.

# Answer
Assuming your boolean formulas have no quantifiers (just AND, OR, NOT, etc.), testing validity of a conjunction of boolean formulas is in NP. It is in fact NP-complete.
> 0 votes

---
Tags: complexity-theory, time-complexity, complexity-classes, lower-bounds
---


title: Why is $BPP$ closed under complement?

text:
# Question
Title: Why is $BPP$ closed under complement?
Why is $\text{BPP}=\text{co-BPP}$?
I tried to find a proof online but couldn't.
Can anyone please provide a quick explanation (if it's trivial and I just can't see it) or a link to a proof?

# Answer
It follows directly from the definition of BPP.

The definition says that a problem with a yes-or-no answer is in BPP if there is a randomized algorithm that gets the correct answer with probability $\ge 2/3$ on all possible instances. This means that on all instances where the correct answer is YES, the algorithm has to output YES with probability at least $2/3$; and on all instances where the correct answer is NO, the algorithm has to output NO with probability at least $2/3$.

Therefore, if a problem $P$ is in BPP, its negation is also in BPP. Take the algorithm for $P$, and just flip its output. That will be a valid algorithm for the negation of the problem.
> 18 votes

---
Tags: complexity-theory
---


# Question
Title: Check constraint under some condition in linear programming
I would like to minimize linear pseudo-boolean function

$$\mathrm{obj} = \sum\_i c\_i \mathrm{sel}\_i$$

subject to $$\sum\_i c\_i sel\_i \geq \mathrm{Value} \qquad\qquad(1)$$ where

$c\_1,\dots c\_5, \mathrm{Value}$ are some constants;

$\mathrm{sel}\_1,\dots,\mathrm{sel}\_5$ are sort of selector variables, $ 0 \leq \mathrm{sel}\_i \leq 1$

Everything is pretty straightforward, but I need to check constraint (1) if and only if some of $\mathrm{sel}\_i = 1$. In the other words, if $\mathrm{obj} = 0$, that is OK with me, but if some or all of $\mathrm{sel}\_i$ are picked up, I need to check $\mathrm{obj} \geq \mathrm{Value}$. Currently I'm using SAT to solve similar problem, but I prefer to study something else. Maybe I need consider different framework for this task? Any directions will be very useful. Thanks in advance.

# Answer
This can be solved by case-splitting, depending upon whether any of the $sel\_i$ are 1 or not, and then solving each case separately. Each case can then be handled using integer linear programming, so you might like to read about ILP solvers.

There are only two cases. We'll optimize for each, separately. The two cases are:

* **Case 1: No selector is $=1$.** In this case, $sel\_i \< 1$ for all $i$, and the linear inequality can be skipped. So the problem is to minimize the objective function subject to the requirement that $sel\_i \< 1$ for all $i$.

You *could* solve this using an integer linear programming solver, but actually that's shooting a fly with a cannon. Since each $sel\_i$ is required to be an integer in the range $0 \le sel\_i \le 1$, this means you know that $sel\_i = 0$ for all $i$. So, this case really covers only one possible assignment to the selectors: the all-zeros assignment. You can simply evaluate the value of the objective function at $sel\_i=0$; in particular, this means that the objective function takes on the value $0$. So the value $0$ is always attainable.
* **Case 2: At least one selector is $=1$.** In this case, there exists at least one index $i$ such that $sel\_i = 1$ for all $i$, and the linear inequality cannot be skipped. So now we have some kind of knapsack-like problem: we are looking for a sum of a subset of the $c\_i$'s that is as small as possible, subject to the requirement that it be greater than $Value$.

This could be handled with integer linear programming. Each $sel\_i$ is an integer unknown, and you have linear inequalities and want to minimize a linear objective function. Adding the extra constraint $sel\_1 + sel\_2 + \dots + sel\_5 \ge 1$ will ensure that at least one of the selectors is $=1$, as needed for this case. This means that you could just feed the problem to an ILP solver and see what solution it gives you.

You might be able to find better algorithms, by borrowing techniques used for the subset sum problem or knapsack problem. In fact, it looks like this is a kind of reverse knapsack. If we just negate the constants, then we're looking for a subset of the negated constants whose sum is as large as possible, subject to the constraint that it be $\le Value$. That sounds like a knapsack problem; each negated constant is the weight and value of some object, and $Value$ represents the capacity of the knapsack. The one twist is that now your objects might have negative weight/value.

Since we're in the special case where weight = value, this is in fact an instance of a subset sum kind of problem. The decision version of youur problem is: given $\alpha$, we want to know whether there is any subset of the constants whose value is in the range $\[\alpha,Value\]$. If we can solve the decision version, then we can serve your optimization problem by using binary search over $\alpha$.
> 1 votes

---
Tags: optimization, satisfiability, linear-programming
---


# Question
Title: How to synchronize a 2d cellular automaton in $\Theta(\sqrt{n} \log n)$ steps
Let's assume we have given a two dimensional cellular automaton with an initial configuration where alls cells are in an quiescent state, expect for one square of cells. Let $n$ be the number of cells in that square. We want to synchronize all cells in the square, so we basically want to solve the firing squad synchronization problem.

Synchronizing all cells in $\Theta(\sqrt{n})$ is rather easy: All cells at the left and right border of the square serve as generals and we synchronize each row separately with any standard 1-dimensional FSSP algorithm. A row of $k$ cells with generals at both ends can be synchronized in $\Theta(k)$ steps (in our case: $k=\sqrt{n}$).

What I want to do, is to synchronize the whole square in $\Theta(\sqrt{n} \log n)$, so I need to slow down the synchronization process by a factor of $\log n$. But I have no idea how to do so.

# Answer
> 2 votes
A naive solution could be that each general first launch a binary counter in its row and counts the current time until $k\log(k)$ steps and then run the FSSP. To do this you just need to detect the value of $k$ and compute $k\log(k)$ in less than $k\log(k)$ steps: sending a signal back and forth toward the other end while incrementing a binary counter gives you k written in binary in roughly $2k+\log(k)$ steps, so you also know $\log(k)$ (length of the counter). Within the $\Theta(k\log(k))$ steps left you have much more time than necessary to compute the product $k\times \log(k)$. And you're done.

I'm pretty sure that (1) there are more elegant solutions, (2) there is a general acceleration/slowdown theorem that could also be used here.

---
Tags: synchronization, cellular-automata, algorithm-design
---


# Question
Title: Difference in Sorting 32- and 64-bit Integers
In 2007, Barrack Obama was interviewed at Google.

The question was, "What is the best way to sort a million 32-bit integers?" Does the fact that the size range of the integer was specified elude to a different way to sort integers of different sizes (i.e., 64- or 32-bit)?

# Answer
Yes. For instance, sorting a million 5-bit integers is a lot easier: use counting sort. And sorting a million long strings is a different question than sorting a million 32-bit integers.

In the case of this particular question, one crucial inference you can draw is that all million 32-bit integers would fit into RAM, so it would be appropriate to use an in-memory sorting algorithm (e.g., quicksort) rather than an external sorting algorithm. If we didn't know the size of the items we were sorting, we wouldn't know whether they would fit in memory and thus wouldn't know whether it's more appropriate to use an in-memory sorting algorithm or an external sorting algorithm.
> 7 votes

---
Tags: sorting, integers
---


# Question
Title: Does the Bible solve an NP-hard problem?
In the Bible, a census is taken of the 12 tribes of Israel:

Simeon: 59,300 Levi: 22,000 Judah: 74,600 Issachar: 54,400 Joseph: 72,700 Benjamin: 35,400 Reuben: 46,500 Gad: 45,650 Asher: 41,500 Zebulun: 57,400 Dan: 62,700 Naphtali: 53,400

In the book of Deuteronomy 27: 12-13, the tribes are partitioned into two groups, the first group consisting of Simeon, Levi, Judah, Issachar, Joseph, Benjamin, and the second group consisting of Reuben, Gad, Asher, Zebulun, Dan, Naphtali.

Someone mentioned to me that this particular partition is the optimal in the sense that it minimizes the absolute value of the total number of people in the first group minus the total number of people in the second group. This partition problem is an NP-hard problem. http://en.wikipedia.org/wiki/Partition\_problem

Is this calculation correct?

# Answer
The partition provided in that passage is not optimal:

(Simeon + Levi + Judah + Issachar + Joseph + Benjamin) - (Reuben + Gad + Asher + Zebulun + Dan + Naphtali) = 318400 - 307150 = 11250

(Asher + Benjamin + Joseph + Reuben + Simeon + Zebulun) - (Dan + Gad + Issachar + Judah + Levi + Naphtali) = 312800 - 312750 = 50
> 6 votes

---
Tags: np-complete
---


# Question
Title: Loop-invariant code motion with unsafe operations
There are well-known algorithms LICM, and they work well. Unfortunately, there are certain cases when these optimizations can cause runtime failures with code that was initially correct. Consider the following example:

```
read a
read_array bs
for (b in bs) {
    if (a != 0) {
        c = 5 / a
        print b * c
    }
}

```

applying loop-invariant code motion we find that `c = 5 / a` is loop-invariant and therefore can be moved out of loop. These may cause runtime error when `a == 0`, though original code works fine.

What to do then? I am not certain, but I have several ideas.

1. We can refuse from optimizing potentially unsafe instructions
2. We can apply loop unswitching before loop-invariant code motion. But I would not rely on this optimization, since it must be applied carefully to avoid code bloating.
3. When moving unsafe instructions out of loop body we add range checks. However, it again causes code bloating (but not as great as in the previous case). Also this approach harder to implement, since we can't put these checks into single basic block, unless we have a special division instruction that does not cause runtime error.
4. Perform range analysis before applying LICM. If divisor is never equal to zero, don't perform LICM.

Are there best practices to deal with such unsafe operations? Notice, that I am looking primarily for algorithms appropriate for SSA form.

# Answer
This kind of optimization is more difficult than typical data-flow based transformations, because you need to actually change the branching structure of the control flow graph.

You need something more than SSA (or something more than the dataflow graph you get from reaching definitions.) That "something" is the control dependence graph (which relies on the same (post)dominator analysis that you use to construct the SSA graph. (Google for "program dependence graph" (which is the combination of the control-dependence graph and the SSA data-flow graph).) Loop invariants (including loop invariant conditionals) are "obvious" in the program dependence graph. A loop invariant is any node all of whose data and control dependences come from outside the loop.

Unfortunately, in the general case, rebuilding a control-flow graph from the program-dependence graph is somewhat involved. (Google for "percolation scheduling" and "gated SSA form" if you are interested. Also (self promotion) my dissertation gives a (*terse*) overview of a method for converting from PDG back to CFG.) You can, luckily, do something substantially simpler if you are willing to restrict your transformation to specific structured control flow (in your case, an `if-else` block inside a `do-while` block.) This is the same simplification that loop unswitching makes.

So working through the steps. First convert `while` and `for` loops to `if-do-while`

```
read a
read_array bs
b = bs.first
if (b is not bs.end):
  do:
    if (a != 0):
      c = 5 / a
      print b * c
    more stuff
    b = b.next
  while (b is not bs.end)

```

Then (as with loop unswitching) you see that `a != 0` is loop invariant, so the `if` statement is loop invariant, so any statements inside the `if` block that are loop invariant (`c = 5/a`) can be moved out of the loop (along with the conditional that protects those statements.) Essentially what you are doing is breaking each invariant conditional block into the parts that are and are not loop invariant:

```
read a
read_array bs
b = bs.first
if (b is not bs.end):
  do:
    if (a != 0):
      c = 5 / a
    if (a != 0):
      print b * c
    more stuff
    b = b.next
  while (b is not bs.end)

```

Then you can move the entirety of the blocks that are completely loop-invariant out of the loop:

```
read a
read_array bs
b = bs.first
if (b is not bs.end):
  if (a != 0):
    c = 5 / a
  do:
    if (a != 0):
      print b * c
    more stuff
    b = b.next
  while (b is not bs.end)

```
> 5 votes

# Answer
The loop invariant that can be moved is

```
if (a != 0) {
    c = 5 / a
}

```

The loop variant that needs to be kept is

```
if (a != 0) {
    print b * c
}

```
> 0 votes

---
Tags: program-optimization, loop-invariants
---


# Question
Title: Can quantified renamable Horn formulas be identified using the same procedure as unquantified formulas?
> Definition: A **renamable Horn formula** is a Boolean formula that can be transformed into a Horn formula by flipping the polarity of every instance of one of more of its variables.

Example:

$\qquad (x\_1 \lor x\_2 \lor x\_3)\land (\lnot x\_1 \lor \lnot x\_2 \lor x\_3)$

This formula is renamable Horn because flipping the polarity of $x\_2$ and $x\_3$ produces the Horn formula

$\qquad (x\_1 \lor \lnot x\_2 \lor \lnot x\_3)\land (\lnot x\_1 \lor x\_2 \lor \lnot x\_3)$

Can I extend the test procedure for identifying renamable Horn formulas, as described in the Harry Lewis paper "Renaming a Set of Clauses as a Horn Set", to quantified formulas?

The paper states: Let $S$ be a set of clauses, say $S = (C\_1 ..... C\_m)$, where each $C\_i = (L\_{i1} .... , L\_{il})$. Then define $S^\*$ to be the set of clauses

$\qquad \bigcup\_{i=1}^m \bigcup\_{1\leq j \<k\leq l} ((L\_{ij}, L\_{ik}))$.

Then $S$ is renamable-Horn if and only if $S^\*$ is satisfiable.

Is this procedure applicable to quantified Boolean formulas also?

# Answer
Yes. The quantifiers can be ignored for the sake of the test since a quantified Horn formula is syntactically identical to an unquantified one except for the quantifiers. That is, a quantified Horn formula still consists of only of clauses with zero or one positive literals. The test only determines whether any combination of polarity flips could produce a Horn formula.

In order for the test to be useful for quantified formulas, it only remains to show that a quantified formula can be renamed and remain equisatisfiable with the original formula.

For unquantified formulas renaming a variable leaves satisfiability unchanged because a solution to the renamed formula is the same as a solution to the original formula except that the renamed variable has its value negated in compensation for the polarity change. The same is true for existentially quantified variables in a quantified formula, and for the same reason. For universally quantified variables, observe that the universal quantifier already requires satisfiability to survive a polarity flip because any solution has to encompass both true and false values for any universally quantified variable. That is, $\forall x(x)$ and $\forall x(\lnot x)$ offer the same solution constraint; the clause must be satisfied with $x$ taking both the true and false values.
> 4 votes

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


title: Finding hit ratio of a cache

text:
# Question
Title: Finding hit ratio of a cache
Consider an array A\[100\] & each element occupies 4 word. A 32 word cache is used and divided into 8 word blocks. What is the hit ratio for the following statement. Assume one block is read into cache in case of miss:

```
for(i=0;i<100;i++)
  A[i]=A[i]+10

```

each array element is of 4 word & each cache block size is 8 words, so we load 8 words into cache.

When program tries to read A\[0\], for the first time it will be miss. Hence it will be brought to memory (& also A\[1\]). Next, A\[1\] will be hit. So, it will be like :

* A\[0\] - Miss
* A\[1\] - Hit
* A\[2\] - Miss
* A\[3\] - Hit
* .....

So hit ratio is 50% ? Am I wrong anywhere ?

I also have one more doubt. First when it tries to access A\[0\], it will be miss. And then when it brings A\[0\] to cache, CPU tries to access A\[0\] again, now it should be considered as hit ? Like,

* A\[0\] (Read) - Miss
* A\[0\] (Write) - Hit
* A\[1\] (Read) - Hit
* A\[1\] (Write) - Hit

If above is correct, then Hit ratio will be 75%.

Any help regarding this is appreciated.

# Answer
> 1 votes
Since there is 8 word block, 2 element can stay in one block. Now notice that each element is refered twice, one read and one write operation. So when in a block when 1st element is refered for read, it will be miss, and hence that block will be copied to cache. Now 2nd reference to that 1st element will be hit, as well as both reference to 2nd element will also ne hit sience block has 2 elements. So out of 4 reference, 1 miss and 3 hit for one block. Gets repeated for each and every block. So hit 3/4 and miss 1/4

# Answer
> 1 votes
Since the line size is 8 words, 2 consecutive elements are loaded into the cache per miss. Now notice that each element is accessed twice, once for a read and once for a write. So for every even $i$th element, when it is first read, it will be a miss, and hence the corresponding cache line - containing elements $i$ and $i+1$ - will be read into the cache. Now the write to element $i$ will be a hit, as well as both references to element $i+1$. So for every 4 references, there will be 1 miss and 3 hits. Thus the hit rate is 75% and the miss rate is 25%.

---
Tags: computer-architecture, cpu-cache
---