# Question
Title: What do CPUs do when a program aborts with an error?
If a very severe interrupt occurs, say a divide by zero, this will quit the program. How is this done, is there a special instruction in the processor or is it a software routine? And after quitting the program, where will the CPU jump to?

# Answer
There are traps, faults and aborts. Divide-by-zero is a fault which means that it is potentially fixable.

On x86, the CPU will save some registers on the stack (CS, EIP, EFLAGS, SS, ESP) and maybe an error code and then start the fitting Interrupt Service Routine. The adress of the ISR is found in the Interrupt Vector Table which is located in the first kilobyte of RAM and is setup by the OS. From here on the OS takes over. After the handling is done, the OS may make the CPU return to the program that caused the error.
> 3 votes

# Answer
CPUs don't have a notion of “program aborting”. Some CPUs have features that help operating system manage separate programs, but the concept of separate programs exists primarily at the level of the operating system.

The specification of the CPU specifies what happens for each instruction for all data. For example, it might specify that `div r1, r2, r3` divides the integer value stored in `r2` by the integer value stored in `r3`, stores the result into `r1`, and then moves the instruction pointer to the next instruction. It might furthermore specify that in case `r2` is zero, the CPU executes a trap — this is what most CPUs do on a division by zero. Typically, on a trap:

* The CPU saves the current value of the program counter into a register assigned to this purpose.
* The CPU sets the reason for the trap (a constant that means “division by zero”) into a register assigned to this purpose.
* The CPU reads an address from somewhere and sets the program counter to this address. This address is called the trap vector. This “somewhere” is usually either a register, or a memory location which is calculated from a value in a register.
* The CPU switches to a privileged mode (e.g. kernel mode, ring 0).

(Note that details vary from CPU to CPU, I am only describing typical behavior.) Traps are very similar to interrupts; the difference is that a trap is due to an event happening in the CPU whereas interrupts are triggered by external events.

The operating system decides what happens when a trap occurs by providing some code and setting the trap vector to its address. The trap handling code typically analyses the reason for the trap and decides what to do, which may or may not include terminating the current process. For example, some operating systems allow application code to react to trap (e.g. with signal handlers on Unix) — then the kernel's trap handler looks up the address of the application trap handler in some internal kernel data structure and jumps to that after setting the processor in the appropriate mode.

An example of a trap which often doesn't result in the death of the application is a memory fault, when the application tries to access a virtual address which is not mapped in the MMU. On operating systems that implement swap, the trap handler looks up the virtual address to see if there is actually data that is mapped there in the application but that is currently swapped out to disk. If that is the case, the trap handler loads the content of the page from disk and updates its memory management data structures. Then it jumps back to the application, arranging to cause the application to execute the memory access instruction again. This time the instruction will succeed, and the application is unaware that the first attempt fails (except via some indirect means such as timing).

If the trap handler decides to terminate the program, it does so in pretty much the same way as if the program had called the `exit` system call: it frees the resources allocated to the process, then invokes the scheduler to execute whatever other threads have something to do.
> 4 votes

# Answer
A processor usually have several modes. Let's take a modern processor, with no legacy of 16-bits mode while being on a 64-bit processor (ie: get rid of x86). On an ARM Core, you've got the following modes:

* User
* FIQ
* IRQ
* Supervisor
* Abort
* Undefined
* System

Usually, programs run as User. When something happens on the hardware (incoming IP packet, for instance), you get an interrupt, and you go either on IRQ or FIQ (the difference between IRQ and FIQ doesn't matter here). The OS uses System and Supervisor modes (once again, we don't care about the difference between those two). Abort and Undefined are used for error handling.

What does an OS ? It manages resources and prepare User mode in order to run processes. This includes setting stacks, MMU mapping, and so on.

When a runs an undefined, CPU detects the error and goes in Undefined mode. OS set a routine on Undefined, it may checks for an handling mechanism (for instance, this may be a call to a co-processor, the OS may power it up, and then re-run the instruction). If there is no such mechanism, it marks the program as dead, and then goes to Supervisor mode. On supervisor mode, the OS code is run, it frees the dead task memory, loads an other task, and goes back on User mode on the newly loaded task.

Each mode has its own stack, memory, and place to run. OS are designed to protect their own memory from the User mode tasks (commonly named User land), if the hardware allows to do so.

And what if there is an issue in Undefined routine ? If there is an undefined instruction in the Undefined routine, the processor return to the first instruction of the Undefined routine, and there is an infinite loop. Bugs in the OS are painful.
> 1 votes

---
Tags: computer-architecture, operating-systems
---


# Question
Title: What do we know about NP ∩ co-NP and its relation to NPI?
A TA dropped by today to inquire some things about NP and co-NP. We arrived at a point where I was stumped, too: what does a Venn diagram of P, NPI, NP, and co-NP look like assuming P ≠ NP (the other case is boring)?

There seem to be four basic options.

1. NP ∩ co-NP = P

In particular, co-NPI ∩ NPI = ∅
2. NP ∩ co-NP = P ∪ NPI

In particular, co-NPI = NPI?
3. NP ∩ co-NP ⊃ P ∪ NPI ∪ co-NPI

A follow-up question in this case is how NPC and co-NPC are related; is there an overlap?
4. Something else, that is in particular some problems from NPI are in co-NP and others are not.

Do we know which is right, or at least which can not be true?

The complexity zoo entries for NPI and NP ∩ co-NP do not inspire much hope that anything is known, but I'm not really fluent enough in complexity theory to comprehend all the other classes (and their impact on this question) floating around there.

# Answer
> 13 votes
The fact that P ≠ NP does not preclude the possibility that NP = co-NP, in which case NP ∩ co-NP = NP. So to further the discussion, let us assume that NP ≠ co-NP. In that case, Corollary 9 in Schöning's A uniform approach to obtain diagonal sets in complexity classes shows that there exists some language in NP – co-NP which is NP-intermediate. So NPI strictly contains (NP ∩ co-NP) - P (note that every language in NP ∩ co-NP is in P ∪ NPI). This is your option (4).

In summary, assuming P ≠ NP and NP ≠ co-NP, we get this:

<sup>\[source\]</sup>

---
Tags: complexity-theory, reference-request, complexity-classes, np
---


# Question
Title: Fastest possible way to check what of X is in a string
I am trying to speed up one of my application, one of the places where I can speed up is in my test if a string contains an array of strings.

example: I have the matches "dog", "cat" "apple" and the string "The dog chases the cat".

In this example would I like an algorithm that returns "dog" and "cat". I do not care, how many times, or where in the string it is, I just want to know what of my matches exists.

The fastest algorithm i can think of for this is $\mathcal{O}(nm)$ where $n$ is the length of the string, and $m$ is the count of matches.

But my question is are there an algorithm out there, there can do this faster then $\mathcal{O}(nm)$?

# Answer
> 3 votes
You can do that using Knuth/Moris/Pratt(kmp), the build table portion of algorithm is $O(m)$ and the search part is $O(n)$, being n the size of text and m the size of the pattern, to be more accurate, if you have 3 potential pattern, you'll do that in $3 * O(n+m)$, because you'll probably have to search it 3 times and build 3 tables.

As you problem is about having the pattern or not, once you find one, you can break the loop and that ofc counts as an optimization. If the pattern are static, by this I mean, they probably are always the same, you may store the prefix-table content of each pattern and that will make $O(m)$ one time, next time it'll just be $O(n)$.

# Answer
> 2 votes
If you are interested in the fastest way, then **KMP is NOT the way to go**, because what happens is that you have $K$ patterns you have to pre-compute and later search for each of them starting from the beginning. Also note that some pattern may overlap some other pattern which KMP does not utilize. Obviously, if you have $K$ patterns (each of length $N$) and a text of length $M$, then your time complexity is $\mathcal{O}(KM)$ for the search and $\mathcal{O}(KN)$ for preprocessing.

However, you can do better by utilizing the relationship between the patterns. You can use the Aho-Corasick data structure which is exactly what you are searching for.

Preprocessing time: $\mathcal{O}(KN)$
Searching: $\mathcal{O}(M)$

In general, the construction is very similar to McCreight's suffix tree construction where suffix links are utilized to make building the suffix tree fast enough.

What I would suggest is to implement a naive construction of the Aho-Corasick automata and then write the search function. Later modify the construction to the fast one where suffix links are used.

P.S.
If you are to use an algorithm like KMP which is rather naive for the multiple string matching problem, you are better off using Crochemore's pattern matching algorithms since it doesn't use any extra space.

# Answer
> 0 votes
As a worst case, consider string `abc...xyz` and patterns `z, yz, xyz,...`

I think you can't do better than $\mathcal{O}(np)$, with $p$ number of patterns.

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


# Question
Title: Can there be two different left most derevations for a grammar?
Suppose there is a CFG with the rules

```
S--> Aa
A--> Bb
B--> A
B--> Epsilon

```

To my best understanding the left most derivation would go like this..

```
 S==> Aa ==>  Bba ==> Aba ==> Bbba ==> bba

```

or

```
 S==> Aa ==>  Bba ==> Aba ==> Bbba ==> Abba ==> Bbbba ==> bbba

```

or

```
 S==> Aa ==> Bba ==> ba

```

Of these which is the true left most derivation of the language? If it is true that all of them are valid left most derivations,why is it that many text book talk about left most derivations of a language rather than a final string??

# Answer
A leftmost derivation of a string in the language defined by a grammar $G$ characterizes a parse-tree for that string. It is a way of describing the parse tree, which is unique for each parse tree.

But to answer the specifics of your question, there is no lefmost derivation of a language, only of the strings of a language. Furthermore, since a leftmost derivation is a sequence of grammar rules applications to produce the string, a leftmost derivation is necessarily defined with respect to a specific grammar. Indeed, the language does not really matter, only the grammar and a string derived with that grammar.

If a string has only a single derivation for a grammar $G$, it is said *unambiguous* for that grammar. When it has several, it is said *ambiguous* for that grammar. When it has none, it does not belong to the language generated by the grammar.

A grammar is ambiguous if it generate at least one ambiguous string. It is unambiguous if every string in its language is unambiguous.

The grammar in your question is unambiguous. Each of the derivations you give is a leftmost derivation, but each for a different string in the language of the grammar.

Actually, this grammar is so simple that it has only leftmost derivations, because there is at most one non-terminal in each rule right-hand side. But a grammar can have only leftmost derivations and be ambiguous.
> 7 votes

# Answer
A *derivation* is a "proof" that a certain word is generated by a certain grammar. The grammar itself doesn't have a left-most derivation. Each word in the grammar has left-most derivations, possibly more than one if the grammar is ambiguous.
> 2 votes

---
Tags: context-free, formal-grammars, ambiguity
---


# Question
Title: The XOR cut-set structure, and combinatorial designs
Given a graph $G(V,E)$ and a subset of vertices $T \subseteq V$, define $\mathsf{cutset}(T)$ = the set of edges connecting a vertex at $T$ with a vertex at $V\setminus T$.

Our goal is to preprocess $G$ such that, given any set $T$, we can quickly return an edge in $\mathsf{cutset}(T)$, or reply that $\mathsf{cutset}(T)$ is empty. The structure should have space complexity $\widetilde{O}(|V|)$, i.e. we are not allowed to keep all the edges. The query complexity should be $\widetilde{O}(|T|)$.

Kapron et al suggest the following neat solution, which works when the size of each cutset is at most 1.

Give each edge a unique number. For each vertex $v$, keep $\mathsf{xor}(v)$ - the binary XOR of the numbers of all the edges adjacent to it. Given a query on $T$, calculate $\mathsf{xor}(T)$ - the binary XOR of all vertices in T. Every edge which is internal to $T$ (i.e. has both endpoints inside $T$) is XORed twice, and hence is not included in $\mathsf{xor}(T)$. So, $\mathsf{xor}(T)$ is actually a XOR of all edges in $\mathsf{cutset}(T)$.

If the size of each cutset is at most 1, then there are two options: either $\mathsf{xor}(T)=0$, which means that $\mathsf{cutset}(T)$ is empty, or $\mathsf{xor}(T)$ is the number of the single edge in $\mathsf{cutset}(T)$.

The authors then go on and describe a complex, randomized structure to handle the case in which $\mathsf{cutset}(T)$ contains more than a single edge.

But in the conclusion, they say that:

> It is not hard to see that the technique described here can be made deterministic with an additional $\widetilde{O}(k)$ factor in the update time, if we know the cuts are of size no greater than $k$, through the use of combinatorial designs".

Unfortunately, for me this seems to be hard... I don't understand: how can combinatorial designs can be used to solve the problem when the size of all cutsets is at most $k$?

# Answer
> 5 votes
You can use a linear code with distance $2k$ or so. The parity check matrix of the code has the property that the XOR of any set of at most $2k-1$ columns is non-zero. This means, in particular, that given the XOR of at most $k$ columns, you can determine (not necessarily efficiently) how many columns were XORed (since if you couldn't you would obtain a set of at most $2k-1$ columns which XORs to zero). The cost of this encoding is the number of rows of the parity check matrix. If you choose the parameters correctly and an efficiently decodable code (recall that the parity check matrix of a code is the generator matrix of its dual), then you probably obtain the conclusion stated in the remark.

---
Tags: data-structures, combinatorics
---


# Question
Title: How to balance doing a literature review and just solving the problem yourself
I work for a company that has several projects involving computer vision. The literature rarely has papers on the exact problems we are solving. Furthermore, the state of the art in much of computer vision is often not reproducible or not ready for actual applications. Furthermore, the rate at which new papers come out in the areas we are interested in would make it very time consuming to digest most, let alone all of them.

On the other hand, we often get stuck and would like to get answers or at least inspiration from existing work.

Our goal in the end is to get to solutions as fast as possible. Does anyone have any guidance on how to balance time spent reading vs doing?

# Answer
Before trying to solve the problem yourself, it is always a good idea to search the literature, to see if somebody else has already solved it, or at least has worked on something similar. This is especially true in computer vision. A good strategy is to allocate some reasonable amount of time to read papers. If you find nothing useful in that time, then you give up and try to come up with your own solution.

Yes the number of computer vision papers published every year is staggering. So a good strategy is to try to keep up with a few top conferences, such as CVPR, ICCV, ECCV, and BMVC, and a few top journals, such as PAMI and IJCV.

Also, it is good to find researchers and research groups who are working in your particular area of computer vision, and follow their progress, and the papers which cite them.
> 3 votes

---
Tags: computer-vision
---


# Question
Title: Is there a correlation of zip compression ratio and density of information provided by a text?
I'll phrase my question using an intuitive and rather extreme example:

**Is the expected compression ratio (using zip compression) of a children's book higher than that of a novel written for adults?**

I read somewhere that specifically the compression ratio for zip compression can be considered an indicator for the information (as interpreted by a human being) contained in a text. Can't find this article anymore though.

I am not sure how to attack this question. Of course no compression algorithm can grasp the meaning of verbal content. So what would a zip compression ratio reflect when applied to a text? Is it just symbol patterns - like word repetitions will lead to higher ratio - so basically it would just reflect the vocabulary?

**Update:**

Another way to put my question would be whether there is a correlation which goes beyond repetition of words / restricted vocabulary.

---

Tangentially related:

Relation of Word Order and Compression Ratio and Degree of Structure

# Answer
Shannon's noisless coding theorem is the formal statement that the size of an optimally compressed data stream is equivalent to the amount of information in that data stream.

But you are also right that the definition of "amount of information" depends on your probability model for the data stream. If you have a correct table of letter probabilities before you start the compression then Huffman coding gets within a constant factor of optimal, Arithmetic coding gets even closer to optimal. But if there are correlations between neighboring symbols (which there are in real human produced text) you can do better by choosing codes for pairs of letters. And you can do even better if you look at triples, and so on. Additionally, you typically don't have a very good probabilistic model of your data stream when you start, so you need to adaptively construct the probability table and then assign variable length symbols depending on the probabilities as you learn more.

The kinds of compression used in zip/gzip, compress, and 7-zip are all variants of Lempel-Ziv coding. Lempel-Ziv coding is adaptive, builds probability tables over varying length chunks of letters, and is optimal in the sense that given an infinite random stream that is *ergodic* (the probabilities are stable over time) it will, *in the limit*, adaptively find a table that takes into account correlations over arbitrary distances, and then use that table to produce a stream that approaches optimally coded.

Of course, neither children's books nor novels for adults are infinitely long ergodic random processes (although some of them may seem like they are) so the conditions of the theorems don't hold.

Here's an interesting interview with Jacob Ziv where he talks a little about the universality of Lempel-Ziv coding: http://www.ieeeghn.org/wiki/index.php/Oral-History:Jacob\_Ziv#Lempel-Ziv\_algorithm.2C\_Viterbi\_algorithm.2C\_and\_Ziv-Zakai\_bound.
> 8 votes

# Answer
I'd say this sounds highly likely. Suppose you take a fairly large sample of children's literature and a similarly-sized (in characters) sample of adult literature. It seems entirely reasonable to suspect that there is a greater variety of words in the adult literature, and that these words may be longer or may rely on more unusual diphthongs than words used in children's literature. This may further imply that children's literature has more whitespace and possibly more punctuation than adult literature. Taken together, this seems to point towards children's literature being much more homogenous at the scale of 5-10 characters when compared to adult literature, so compression techniques that can take advantage of homogeneity at the scale of up to at least a dozen or so characters should be able to compress children's text more efficiently than they could adult literature.

Of course, this makes some assumptions about what is considered children's literature and what is considered adult literature. What do you consider "Gulliver's travels", for instance? My discussion above assumes that we're considering books that are clearly for young children and books that are clearly for adults; compare "Goodnight, Moon" to "1984", for instance.
> 6 votes

# Answer
I do not know about the direct connection between compression ratio and level of writing. It seems logic though.

There is a nice suggestion to use zipping data to find the relative distance between texts (or DNA, languages): Cilibrasi, R. - Vitányi, P.M.B. Clustering by compression 2005 - IEEE Transactions on Information Theory, 51, p.1523–1545.

"*we determine a parameter-free, universal, similarity distance, the normalized compression distance or NCD , computed from the lengths of compressed data files (singly and in pairwise concatenation).*"
> 1 votes

# Answer
Each letter is correlated with a binary representation (based upon ASCII value), in your example the amount of data would result in a larger compression file of the adult book v. children's book, but the density of the data for compression is equivalent in binary which is demonstrated by comparing, say, 0110 and 0010. The compression is not affected by the interpretation of data, but by the fact that the strings themselves incorporate more characters and therefore longer ASCII values, which in turn determines the number of octets and therefore the size of the compressed folder.

A frequency distribution I developed in algorithmic form several years ago is expressed as a Bayesian inference engine of the probability of a feature detected letter given the range of letters and their correlated values attributed to them.

I gave a lecture on this at Augustana's annual symposium in 2010:

http://youtu.be/BPdQjBSW0\_w

The video explains how a natural language parser can operate with feature detection within the context of the pairing of associated letters recognized by assigning numerical values to the feature of the letter.

The analysis of my data shows that yes, the relationship between associated letters in a word, phrase and sentence can be formalized and implemented into a system based on the decomposition of the elements of a specific letter.

The correlation is based upon the lexicon programmed in the system coupled with decomposition of the elements of a letter such that:

A diagonal line has a value of 0.5 for each diagonal, a horizontal line has a value of 1 and a vertical line has a value of (1.5), a semi-circle has a value of 2 and a full circle has a value of 3. These values are then added and compared to the results of associated letters in the word, entered into a Bayesian inference engine and finally calculated to reach a given threshold to allow for the accept state.
> 1 votes

# Answer
Well, I don't think anyone has studied this particular problem and the answer is unlikely to be possible on purely theoretical grounds... However, some things can be said:

* Odds are very good the the longer text will compress better \[in terms of compression ratio, not in terms of absolute length, of course\] no matter if it is adult or child literature. (A point already mentioned by Peter Shor in a comment above.)
* Even the best LZ-based text compression algorithms (which use actual words unlike the run-of-the-mill zip) get beaten by stock bzip2 on text compression ratio; bzip2 does something seemingly "very dumb" \[actually very smart\] in that it \[reversibly\] scrambles the text into gibberish stings but with many repeated letters; this is the Burrows-Wheeler transform. I do not expect that the frequency of words will matter much for bzip2-style compression, but instead the letter frequency probably would; it is much harder to guesstimate if there's a difference with respect to the latter between child and adult literature, but I suspect they don't differ substantially on letter frequencies.

Both points can be seen \[on general texts, not child vs. adult\] in tables 2-3 (p. 43) of the paper "Text Compression: Syllables" by Jan Lansky and Michal Zemlicka (sorry for leaving out the diacritics in their names). Mind you, this is for English and Czech text \[beware that table 3 has an incorrect caption, "bytes" should be "bits", same as in table 2\], and you can see that bzip2 does less well on the latter almost surely because there are more symbols in base alphabet for Czech compared to English. So for (say) Chinese (using a native encoding, not via Romanization), I would not bet on bzip2 anymore...

Strangely enough, Salomon's *Handbook of Data Compression* \[5th ed. 2010\], where I found ref to the aforementioned paper and a fairly ample \[re\]presentation on pp. 1122-1127, doesn't mention the sequel \[which was promised in the conclusion section of Lansky and Zemlicka\]: Syllable-Based Burrows-Wheeler Transform (2007). Alas the results are underwhelming: you need fairly large documents (\>200-500kB) for syllable-based BWT to overtake the letter-based BWT, and even the then the improvements are fairly small. The word-based BWT, also tested in there, never wins, although the max document size was 5MB. I think this shows that word repetition is not the major factor in the text compression ratio (if done right) compared to letter and syllable repetition (frequencies), at least for the usual book-sized documents. So I think answers the question negatively (as in probably no difference) for same-size documents and only some difference in word repetition (like child vs. adult literature would entail) when using stock bzip2 or the experimental syllable-based BTW. Perhaps if you compress something much more vast like the whole Wikipedia (or to particularize to this case, two vast collections of literature, one for adults for one children), then word repetition might be the key factor in getting good compression (and you would want a word-based BTW).

A couple more twists to this:

* The research cited above assumes a single choice of syllable/word/letter as "predictor". Context mixing (CM) algorithms (pioneered by PAQ) actually use several (adaptively weighted) predictors; for example PAQ use both a previous-word and bit-level PPM predictor (among others). The previous word may seem rather unlikely to work much, but on a 1GB sample of Wikipedia, it actually works quite well because there are some bot-generated articles with templated text, like those based on US census data. (See the 3rd image, "repeated string analysis" and commentary in http://mattmahoney.net/dc/dce.html#Section\_22. Finding all of them requires a large amounts or RAM though; the best performing derivative of PAQ \[called cmix\] on that dataset uses ~30GB of RAM.) I would expect a CM algorithm \[which uses previous words as one of the predictors\] to do better on texts with smaller vocabularies (like children stories) all other things being equal.
* If you're willing to apply text-only transforms (BWT is not so), then you can do better than BWT; see the (somewhat improperly named) "word replacing transformation" (WRT) paper which actually consists of a whole bunch of little tweaks that make words matching each other more likely, like case conversion, replacing \[in a reversible manner\] end-of-lines with spaces, inserting spaces before punctuation etc. It doesn't seem like any of that would favor smaller vocabularies, but there are a lot of techniques listed in there and I haven't read that paper thoroughly.

In a way combining the two previous points, one can actually use a word-based (word as in natural-language word) compression as a pre-processing step for a general-purpose (including LZ-based) compressor. I'm a bit surprised this hasn't been tested much before the 2009 paper by Farina et al. This idea does pretty well when the base compressor is gzip, but the compression ratio improvements for bzip2, 7zip, or PPMd as backends are rather modest. Perhaps the most notable thing about this precompression is that it increases overall compression speed. Percentage-wise, this was most notable for 7zip as it saw a 3x-4x compression speed improvement! 7zip is LZMA-based, so roughly speaking LZ on steroids: a very large dictionary and with range encoding instead of Huffman used in gzip/DEFLATE. (Tables 6-8 have the gist of the results.)
> 1 votes

---
Tags: information-theory, data-compression
---


title: Are neural networks dynamical systems?

text:
# Question
Title: Are neural networks dynamical systems?
Dynamical systems are those whose evolution can be described by a rule, evolves with time and is deterministic. In this context can I say that Neural networks have a rule of evolution which is the activation function $f(\text{sum of product of weights and features})$ ?

Are neural networks

1. dynamical systems,
2. linear or nonlinear dynamical systems?

Can somebody please shed some light on this?

# Answer
> 1 votes
A particular neural network does not evolve with time. Its weights are fixed, so it defines a fixed, deterministic function from the input space to the output space.

The weights are typically derived through a training process (e.g., backpropagation). One could imagine building a system that periodically re-applies the training process to generate new weights every so often. Such a system would indeed evolve over time. However, it would be more accurate to call this "a system that includes a neural network as one component of it".

Anyway, at this point we are probably descending into quibbling over terminology, which might not be very productive. This site format is a better fit for objectively answerable questions with some substantive technical content.

# Answer
> 2 votes
The type of neural networks you have in mind (where each neuron is a threshold function taking on $0$ or $1$ values), with $n$ neurons is a dynamical system with state space $\\{0,1\\}^n$. After every tick of the clock, the neural network is in some new state, defined by the current values of its neurons.

Because the state space is discrete, I don't think your second question makes sense here. Linear vs. non-linear are terms applied to continuous-time dynamical systems.

# Answer
> 1 votes
There are many different forms that a neural network can take. Some neural networks are trained before they are actually used in 'real world' scenarios. Other neural networks adjust themselves as they run, for instance a neural network with some sort of feedback loop or basic memory retention.

As for your second question, again there are different types of neural networks that can be either! If you consult the wikipedia page for Neural Networks there are lots of types of ANNs that are described:

http://en.wikipedia.org/wiki/Types\_of\_artificial\_neural\_networks#Dynamic\_neural\_networks

If you would like to do some further reading on types of neural networks, then I would suggest the book "Machine Learning" by "Tim Mitchel". It has a large section on Neural Networks and is reader friendly for beginners in this area.

---
Tags: terminology, artificial-intelligence, neural-networks
---


# Question
Title: Difference between BSP model and synchronous round model in distributed computing
I've recently learned about distributed computing and the synchronous model where, assuming a complete network and no crashes, in each round the following happens:

1. every node can send a message to all other nodes,
2. all of these messages are received by all nodes by the end of the current round, and
3. at the start of the next round, every node performs some local computation (taking into account received messages).

It seems to me that this model is a more specific variant of the classic BSP model of Valiant where the cost of the barrier synchronization and the local computation is ignored.

Am I missing something else that distinguishes the distributed model from the BSP model?

# Answer
> 1 votes
In the **CONGEST** model of distributed computing, the topology of the computer network is a graph $G$. In each round, each node can send a message to each of its neighbours in $G$. Typically, we assume that $G$ is unknown, we interpret the structure of $G$ as the input, and we are interested in solving graph problems related to the structure of $G$.

This is the key difference. In BSP there is no underlying graph topology that limits communication; in CONGEST there is a graph that determines who can talk directly with whom.

---

However, things get interesting if we set $G = K\_n$ in the CONGEST model. That is, the network topology is a complete graph on $n$ nodes. This way we arrive at a model called the **congested clique**.

The congested clique is very closely related to the BSP model. The key difference is the following:

* Congested clique: the bandwidth constraints are on the edges; for each pair of nodes $u$ and $v$, in each round $u$ can send at most $b$ bits to $v$.
* BSP: the bandwidth constraints are on the nodes; for each node $u$, in each round $u$ can send at most $B$ bits in total to all other nodes, and receive at most $B$ bits in total from all other nodes.

Clearly, any congested clique algorithm is trivial to simulate in the BSP model if we have $B = nb$, with only a constant overhead. \[I am ignoring some issues related to the local computation.\]

Lenzen (2013) shows that the *converse is also true*: any BSP algorithm can be simulated in the congested clique model if we have $B = nb$, with only a constant overhead.

In summary, if we eliminate $G$ from the CONGEST model, we basically arrive at the BSP model. Hence the graph $G$ is the *only* difference between the models.

---
Tags: distributed-systems, parallel-computing, computation-models
---


# Question
Title: Why are long block lengths commonly assumed/used in channel coding proofs?
As the title states, why are long block lengths commonly assumed or used in channel coding proofs?

# Answer
One reason is that this allows a small fixed overhead per block. With a sufficiently large block, the effect of this becomes minimal (it's amortized out over the length of the block).
> 1 votes

# Answer
Shannon's source coding theorem shows that you can encode at the rate of entropy. Shannon's channel theorem shows that you can transmit data at the rate of channel capacity. In both theorems, both quantities – source entropy and channel capacity – are only approached in the limit of a large block size. If you limit the size of your block, the theorems are not true anymore. The only way to get a clean theory is by allowing the block size to grow unboundedly.
> 1 votes

---
Tags: information-theory, coding-theory
---


# Question
Title: Removing arbitrary element from Max Heap
Which of the following strategies is more feasible?

* Strategy 1: Remove the element from the array, compress the array and reheapify.
* Strategy 2: Update the value of this node to the current maximum value in the heap + 1, then delete\_max.

# Answer
> 1 votes
I assume that "compress the array" means to shift the elements to the left until the gap is gone, right?

Then strategy 2 is clearly better than strategy 1: While you have a worst case complexity of $\mathcal{O}(n)$ in the first case (in the worst case, you need to shift every remaining element of the array to the left), you only need two "standard" heap operations in the second strategy, both of which only need $\mathcal{O}(\log n)$ time.

---
Tags: data-structures, heaps
---


title: Hates Pepole Nice Algorithm

text:
# Question
Title: Hates Pepole Nice Algorithm
Some people in `n` groups, hates from each others. the hates relation are symmetric. (a hates b, b hates a, also). suppose we know list of all people that hates from others. (which one hates from which ones...). we want to divide these people into two groups such that no one in each group hates from others in the same group. which is the fast algorithm that detect and solve this problem is :

1) O(N^2)

2) O(N^3)

3) O(N^4)

4) there is no poly time solution.

anyone could help me to solve this 2012 Local Informatic Olympiad of China?

# Answer
> 0 votes
This is equivalent to check if the "hate" graph is bipartite. Which can be done in linear time with respect to number of edges. Thus $O(n^2)$.

---
Tags: algorithms, assignment-problem, algorithm-design
---


# Question
Title: Books on how to approach an IT research subject?
Are there any recommended books or other sources about research in IT?

For example, I want to do some research on the subject 'Internet of things'. What would be the best way to approach this? What methods should I use?

# Answer
> 1 votes
You do not do research on a topic out of the blue. You must have read enough, understand the basic concepts, the type of problems and the technology, and hopefully be proficient enough to form your own views of how things works, possibly how they should work, how they might be improved or completed. Work can be theoretical (devising new algorithms for faster or more reliable solutions). I may involve developing new concepts, evolving or unifying existing ones, finding new answers to old problems, finding new problems, and hopefully solving them. It may also concern new applications. It may be mostly abstract, or be mostly implementation (if it includes new techniques for achieving results), though it should ideally blend both abstraction and implementation. I probably forget many aspects.

In other words, it is essentially varied and undescribable, depending very much on you own relation with the topic, and the orientation of your necessarily deep knowledge of it.

It may occur that your adviser will serve you a good topic on a plate, with user manual and guidelines to achieve the research and get a PhD. But I would not count on it too much.

So I have 3 advices

* read
* experiment with existing systems
* and read a lot more.

And while doing it, always keep an open and critical mind. Question any assertion you find, take notes, make sure you understand what is being said or implied. And do not expect everything to be true. It is not that people cheat (though a few actually do) but we all make mistakes or take unwarranted shortcuts, with the best of intentions.

If you are mature enough to do research in your chosen area, you no longer need to ask your question.

The way I started most of my research was unexpected. I wanted to learn on a topic. I started reading, and after a while thought I would do something differently and started developing my own idea. Sometime I was already very knowledgeable on the topic, but reading critically a paper, I thought that more could be done. New ideas come often from absorbed knowledge. When you have lots of knoledge on a topic, you can also try to unify it, condense it, and it may yield unexpected new results.

Regarding what you should read. I do not know. If you start working on the topic, you will quickly find out from citation and discussions on the Internet. But recall that there are also hidden gems that no one talks about, that may be the key to interesting work. Books are useful to get started on a topic, to get an overview and basic knowledge. But it is not likely that they will be enough to start doing research. For that, you generally need to read research papers, and that may be less easy (people are still struggling with new concepts), but it can be very rewarding.

So you may take any book with some reputation (and possibly pedagogy) to get started on basics. After the first, you should be able to choose the next on your own, in directions you are interested in. But start reading recent research papers as soon as you can, and look at their references. The rest should come on its own.

You can be a great teacher without being a great researcher. The converse is also unfortunately true. But both need to read a lot. Great teachers can write great textbooks.

---
Tags: books, research
---


# Question
Title: Generalisation of pancake sorting with arbitrary flipped slices?
In pancake sort, the primary operation is: flip all pancakes **above** a given position. What about flipping all pancakes **between** two given positions? Anybody knows if this has been studied?

To illustrate the problem, here is a quick brute-force, greedy implementation in Python 2.7 (not quite sure it always converges though):

```
def sort(a):
    entropy = 0
    for i in range(len(a) - 1):
        entropy += abs(a[i] - a[i+1])
    while True:
        max_improvement = 0
        for i in range(len(a) - 1):
            for j in range(i + 1, len(a)):
                improvement = 0
                if i > 0:
                    improvement += abs(a[i] - a[i-1]) - abs(a[j] - a[i-1])
                if j < len(a) - 1:
                    improvement += abs(a[j] - a[j+1]) - abs(a[i] - a[j+1])
                if improvement > max_improvement:
                    max_improvement = improvement
                    (next_i, next_j) = (i, j)
        if max_improvement == 0:
            if a and a[0] > a[-1]:
                a[:] = a[::-1]
                print a
            return
        entropy -= max_improvement
        a[next_i:next_j+1] = a[next_i:next_j+1][::-1]
        print a

a = [7, 1, 3, 8, 6, 0, 4, 9, 2, 5]
print a
sort(a)

```

Output:

```
[7, 1, 3, 8, 6, 0, 4, 9, 2, 5]
[7, 6, 8, 3, 1, 0, 4, 9, 2, 5]
[7, 6, 8, 9, 4, 0, 1, 3, 2, 5]
[7, 6, 8, 9, 4, 5, 2, 3, 1, 0]
[9, 8, 6, 7, 4, 5, 2, 3, 1, 0]
[9, 8, 7, 6, 4, 5, 2, 3, 1, 0]
[9, 8, 7, 6, 5, 4, 2, 3, 1, 0]
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

```

# Answer
> 3 votes
Yes, it has been studied quite a lot. The general problem is called *sorting by reversal*. It is important as it is related to finding the similarity between genomes of two species that have the same genes, but in different order.

There are two variants of the problem, one where the orientation of the pancake \[= gene\] also matters. This is modelled using so-called signed permutations. See also the last paragraph and references in the Wikipedia page you quote.

There is a very precise characterization of the number of reversals needed for signed permutations in terms of the structure of a certain graph. For the unsigned variant, which you use in your question, the problems seems NP-hard (see the Wiki page) and even hard to appoximate.

---
Tags: algorithms, sorting
---


# Question
Title: Mutex implementation on top of a minimalistic preemptive scheduler
In this question, I'm implementing some synchronization primitives in the standard library of an operating system. Specifically, I want to implement mutexes and condition variables. This is on top of a microkernel with a preemptive scheduler (a thread has no way to prevent the scheduler from preempting it). I'm exploring how minimalistic the system can get while remaining powerful and efficient enough for my needs.

From the hardware, I get a basic atomic primitive such as compare-and-swap or load-link/store-conditional. You can assume that the word size for these instructions is large enough to store a pointer or a thread identifier. Furthermore all threads see the same memory.

From the kernel, I get three primitives:

* `sleep()`: suspend the current thread until a thread has called `wake(t)` where `t` is the current thread. If the current thread's wake-up flag is already set then `sleep()` returns immediately. Returning from `sleep` clears the wake-up flag.
* `wake(t)`: wake thread `t` if it's asleep. If `t` isn't asleep then its wake-up flag is set and `t`'s next call to `sleep` will return immediately. Note that non-participating threads may call `wake` — as far as the locking mechanism is concerned, it's thus possible for a thread's wake flag to become set non-deterministically.
* `yield()`: give all other threads that are not asleep a chance to run.

How can I implement a mutex and condition variable API on top of these primitives?

* `lock(m)`: if `m` is taken, sleep until it is free. Mark `m` as taken.
* `unlock(m)`: mark `m` as free. If some other thread is waiting for it to become free, that thread is woken up.
* `wait(c, m)`: wait for the event `c` to happen. If `c` has already happened, don't block. When `wait` returns, it atomically locks the mutex `m`. When a thread notices `c`, the event is cleared.
* `signal(c)`: signal an event on the condition `c`. This wakes up one thread that's waiting on `c`.

A good solution must avoid starvation: if a thread tries to lock a mutex, it must eventually get it provided that every thread that acquires it releases it eventually. Preferably, threads should obtain the lock on a first-come, first-served basis. (To give a counter-example, a last-come, first-served system would be bad because one thread could hog the mutex if it keeps acquiring it immediately after releasing it.)

A solution is better if it avoids scheduling a thread that ends up doing no useful work. For example, systematically waking up all threads when something happens is not good enough.

What is an efficient algorithm for implementing **mutexes and synchronization variables**? (Note that I am not asking how to implement a spinlock! A spinlock is probably involved, but I expect answers to this question to explain how to set up wait queues and not just handwave that part.) Efficiency may vary based on the amount of contention; the kind of systems I work on tend to have low contention in practice (but must not overly drain the battery when there is contention).

(I expect answers to explain the algorithm in sufficient detail that a programmer could understand it, but a reference would be appreciated as well.)

# Answer
## Mutex

For the mutex I'm going to propose a modification of the MCS spinlock that uses your `sleep/wake` primitives to block instead of spin while waiting to acquire the mutex. The MCS lock was introduced in

> Mellor-Crummey, John M; Scott, Michael L: Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors, *ACM Trans. on Comp. Sys.* (TOCS), 9(1):21-65, 1991.

The MCS lock was specifically designed to eliminate the undesirable coherence traffic associated with spin locks in large-scale cache-coherent shared memory multiprocessors (which is not your concern) but I'm suggesting it because of the analogy between inter-processor coherence messaging in multiprocessors and your `sleep` and `wake` primitives.

Essentially we are keeping a linked-list of waiters for the lock. The lock itself is a pointer to the tail of the list. The head of the list is the thread that currently has the lock. The tricky part is that there are two pointers to the tail so you need to be careful about the lack of atomicity when adding or removing the tail node.

I'm going to use the same pseudo-code notation used in the paper, which is Pascal-based (it was 1991, give them a break), so the pointer notation may be unfamiliar to many readers. `I: ^qnode` means, "the variable `I` has the type 'pointer to `qnode`'," and `I^` means, "that which `I` points to."

`compare_and_swap(addr, old, new)` is defined as (atomically) `if addr^ != old return false; addr^ := new; return true`. `atomic_swap(addr, new)` is defined as (atomically) `old := addr^; addr^ := new; return old`.

```
type QNode = record
  owner    : Boolean
  threadId : ThreadIdentifier
  next     : ^QNode

type lock = ^QNode    // locks start initialized to "nil" (the null pointer)

// The qnode I needs to be allocated in an outer scope

procedure acquire_lock (L : ^lock, I : ^qnode)
  I->threadId := myThreadId
  I->next     := nil
  predecessor : ^qnode := atomic_swap(L, I)
  if predecessor != nil                    // queue was non-empty
     I->owner := false
     predecessor->next := I                // put myself on the tail
     repeat sleep() while not I->owner

procedure release_lock (L : ^lock, I : ^qnode)
  if I->next == nil                        // no known successor
     if compare_and_swap(L, I, nil) return true  // L agrees that there's no successor
     else repeat (spin) while I->next == nil     // else spin wait for race to clear itself
  I->next->owner := true                   // there is a successor, wake it
  wake(I->next->threadId)

```

The only spinning is (1) in the (hopefully extremely rare) condition that the queue is empty except for the lock holder, and the lock holder tries to release at exactly the same time some other thread is trying to add itself to the queue or (2) when a thread waiting to acquire the lock receives a spurious wake up.

## Condition Variable

Given a working mutex implementation with `lock(m)` and `unlock(m)`, it is possible to do a relatively naïve but working implementation of a condition variable. This design is based on

> Birrell, Andrew D; Impliementing Condition Variables with Semaphores, in *Computer Systems, Theory, Technology, and Applications*, Andrew Herbert and Karen Spärck Jones, editors, pp. 29-37, Springer Monographs in Computer Science, 2004.

and in particular, Birrell's advice that the condition variable should do the queueing itself, rather than relying on some other primitive. Birrell's version additionally makes use of the observation that each thread can be waiting for at most one condition variable, so each qnode can be allocated as part of the thread control block when the thread is created. (Which seems a bad idea to me, because then you have a dangling pointer when a thread gets killed while waiting for a condition variable.)

Start with a non-atomic queue of integers data type with `push_tail(q, t)` and `pop_head(q)` and `is_empty(q)`.

```
type CVar = record
  q : Queue
  qm : Mutex   // private mutex to protect the queue

// precondition: caller holds mutex m
procedure wait(cv : ^CVar, m : ^Mutex)
  lock(cv->qm)
  push_tail(cv->q, myThreadId)   // atomically add caller to the queue
  unlock(cv->qm)
  unlock(m)
  sleep()
  lock(m)

procedure signal(cv : ^CVar)
  lock(cv->qm)
  if not is_empty(cv->q)
    wake(pop_head(cv->q))
  unlock(cv->qm)

```

This implementation does suffer from spurious wakeups, but that's standard for condition variable implementations. It is assumed that you are using condition variables to wait for some precondition (described by predicate `P()`) to become true and that you are thus using the condition variable like this:

```
m  : Mutex
cv : CVar

lock(m)
while not P()
  wait(cv, m)
// at this point P() is true and m is acquired

```
> 3 votes

---
Tags: operating-systems, concurrency, synchronization, threads, mutual-exclusion
---


# Question
Title: Primitive recursive functions and unbounded quantifiers
From what I know If the predicate $P(t,x\_1,...,x\_n)$ belongs to some PRC class $\zeta$ then so do the predicates

$(\forall t)\_{\le y}$ $P(t,x\_1,...,x\_n)$

$(\exists t)\_{\le y}$ $P(t,x\_1,...,x\_n)$

But what about the unbounded quantifier? what difference does it make if I replace $(\forall t)\_\le$ with $(\forall t)$ and also $(\exists t)\_\le$ with $(\exists t)$ ?

Davis in his book page 43 says:

> **Theorem 3.3:** A function is primitive recursive if and only if it belongs to every PRC class

I saw a problem related to what I said that I couldn't solve, here it is :

> If $P(x)$ and $Q(x)$ are primitive recursive predicates which one of the following may **not** be primitive recursive:

1. $P(x) \rightarrow Q(x)$
2. $Q(z) \wedge P(\[\sqrt{x}\])$
3. $\forall x(x \le y \rightarrow P(x))$
4. $\exists x(P(x) \wedge Q(x)) $

Since only one of the above choices is right, so I don't know 3 is the answer or 4!

# Answer
> 4 votes
If $P(t,x\_1,\dots,x\_n) \in \zeta$, then clearly $(\forall t)\_{\le 0}P(t,x\_1,\dots,x\_n) = P(0,x\_1,\dots,x\_n) \in \zeta$.

Moreover, if for some $y$, we have $(\forall t)\_{\le y}P(t,x\_1,\dots,x\_n) \in \zeta$, then it can easily be shown that $(\forall t)\_{\le y+1}P(t,x\_1,\dots,x\_n) = P(y+1,x\_1,\dots,x\_n) \land (\forall t)\_{\le y}P(t,x\_1,\dots,x\_n) \in \zeta$, noting that taking the logical *and* is a primitive recursive operation.

By induction, we have that for any $y$, $(\forall t)\_{\le y}P(t,x\_1,\dots,x\_n) \in \zeta$. Things work similarly for $(\exists t)\_{\le y}$. However, this reasoning doesn't extend to unbounded quantifiers, and in the general case, $\forall t P(t,x\_1,\dots,x\_n) \notin \zeta$.

If you think of PRC predicates as *things that can be checked by a computer in finite time*, the underlying meaning is that

* if it takes finite time to check whether a given proposition is true for any given value, then it also takes finite time to check whether it's true for any/all values in a finite set (at most the sum of the finite times taken to check for each element in the set)
* on the other hand, it's not necessarily possible to check that it's true for any/all values in an **infinite** set. Naively checking for $0$, then $1$, then $2$, etc..., could take forever.

The answer to your second question is proposition 4. Indeed, in proposition 3, the universal quantifier over $x$ is bounded by the free variable $y$, which is a finite value. In other words, proposition 3 could be rewritten as $(\forall x)\_{\le y}P(x)$.

# Answer
> 3 votes
Agree with David that 3 is primitive recursive, but depending on what is meant exactly, the predicate in 4 is also primitive recursive - as a predicate, $\exists x(P(x) \wedge Q(x))$ has zero arguments and therefore is simply a truth value - and thus trivially primitive-recursive. On the other hand, if you took primitive-recursive predicates $P(x,y), Q(x,y)$ with (say) two arguments, then $\exists x(P(x,y) \wedge Q(x,y))$ is indeed in general not primitive-recursive. Furthermore, while $\exists x(P(x) \wedge Q(x))$ is a constant, there is no computable method for determining its value from the definitions of $P(x)$ and $Q(x)$. This contrasts with bounded quantification, where a primitive-recursive definition for the result can be obtained computably from the definitions of the input predicate.

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


title: Perturbation of a vector

text:
# Question
Title: Perturbation of a vector
Given a vector $x=(x\_1,\cdots,x\_n)$ such that $0\leq x\_i \leq1$ and $\sum\_{i=1}^n x\_i=1$. I would like to find a vector $x^\*$ such that ($l\_1$ norm ) $||x-x^\*||\_1\leq \delta$, where $\delta \>0$.

How can we generate the $x\_i^\*$ so that still $\sum\_{i=1}^n x^\*\_i=1$?

# Answer
> 2 votes
Set $\delta' = \frac{\delta}{2(n-1)}$. You can nudge each $x\_i$ except for the last one by a random value in $\left\[-\delta', +\delta'\right\]$, and then adjust the last value to get the sum to be $1$.

**Pseudocode:**

> 1. $x \leftarrow (x\_1,...,x\_n)$
> 2. $\delta' \leftarrow \frac{\delta}{2(n-1)}$
> 3. $y \leftarrow (y\_1, \ldots, y\_n)$
> 4. **for each** $i$ **until** $n$ **do**
> 5. $\quad y\_i \ \leftarrow \ (\\,x\_i + \mathsf{randomBetween(-\delta',+\delta')}\\,)$
> 6. **endfor**
> 7. $y\_{n+1} \leftarrow (1-\sum y\_i)$

Using $y$ instead of $x^\*$, the last line guarantees tha $\sum y\_i = 1$.

We need to check that $|| x - y || \< \delta$:

For $i=1,2,\ldots, n-1$ we have $|x\_i - y\_i| = \delta\_i'$. Since the original $x$ vector sums to $1$, we also have $$|x\_n-y\_n| = \left|x\_n - 1+\sum\_{i=1}^{n-1} (x\_i + \delta\_i')\right| = \left|\sum\_{i=1}^{n-1}\delta\_i'\right|$$.

So $$|| x- y|| = \sum\_{i=1}^{n-1} | \delta\_i'| + \left| \sum\_{i=1}^{n-1} \delta\_i'\right| \le 2\sum\_{i=1}^{n-1} | \delta\_i'| \le \delta$$ using the triangle inequality.

---
Tags: approximation
---


# Question
Title: Is 95% of code really non-semantic fluff?
According to A Study of Wheat and Chaff in Source Code, 95% of code is "chaff", or "non-core functionality", whatever that means. Is this really a sensible study? Does the IT World article correctly represent the original paper? It's hard to believe 95% of the code I write is "non-core". Maybe an example would help.

The original paper is *A Study of “Wheat” and “Chaff” in Source Code* by Martin Velez, Dong Qiu, You Zhou, Earl T. Barr and Zhendong Su.

# Answer
First, note the IT World article grossly simplifies the paper. (This is partly inevitable — if you could summarize the paper in a few accessible paragraph, it wouldn't be a research paper). The 5% figure comes from a particular measure, but the paper considers multiple measures. That being said, I don't think the measures considered in the paper are particularly appropriate.

Let me summarize my understanding of the paper (I've skimmed it, I haven't read it in detail, so I may have made some mistakes or missed important points).

The paper seeks to measure the information density in source code. More precisely, they divide the source code into meaningful units (methods in Java), and they quantify how methods differ from each other, the idea being that if two methods aren't seen to differ then having those two methods instead of just one is content-free overhead (“chaff”).

To extract meaning from source code, they erase distinctions that they consider meaningless. They cut the code of a method into *words* (which they choose to be lexer tokens), then apply an abstraction function $a$ to each word (in other words, they consider words modulo an equivalence relation: $u \equiv v$ iff $a(u) = a(v)$). The abstraction function is the *lexicon*. I'll call the set of abstractions of the words in a method ($A(u\_1\dots u\_n) = \\{a(u\_i) \mid i \in \[1,n\]\\}$ where $u\_1 \ldots u\_n$ are the tokens of a method) its abstraction set.

The choice of lexicon is crucial to the measure. At one extreme, you could stick all tokens into the same equivalence class ($\forall u, a(u) = \top$), and then every non-empty method would have the same minset. At another extreme, you could put all tokens in a separate equivalence class ($\forall u, a(u) = u$), and then the minset of a method would only ignore whitespace, comments, the amount of repetition of each token, and the order of token.

The minset of a method in a corpus captures how its set of words differ. A *corpus* is a set of abstraction sets for all the methods of a set of programs. The minset of a set $S$ in a corpus $C$ is a subset of $S$ (i.e. a subset of the set of words in a method) is a subset $S^\* \subseteq S$ such that $S^\*$ is not a subset of another element of $C$, and which is maximal under these constraints. Intuitively, anything you add to the minset will not help to distinguish that set from other elements of the corpus.

The 5% figure comes from a fine-grained lexicon where the equivalence between tokens is the trivial one ($u \equiv v$ iff $u = v$). The conclusion is that methods in a typical program are 95% similar.

I don't think the conclusions are particularly relevant for several reasons. The minset measure has major flaws.

If a corpus consists of a single method, then if I understand the definition correctly, its minset will be a singleton (it could be any element, the minset computation is non-deterministic). This shows that there is the correlation between the size of the minset and the complexity of the semantics that the code implements is dependent on the corpus. In order to be meaningful, the corpus has to include all the programs that one would possibly want to write, not just all the programs that were uploaded to a particular repository.

As seen above, the minset measure is also very sensitive to the choice of words and abstraction. To give an extreme example, consider binary code split into bytes, or Turing tarpit languages with a minimal set of primitives and no variables. These will have a very small lexicon, but the ways in which the primitives are combined are highly relevant to the semantics of the program. Even if we don't get into “exotic” languages, consider something like numerical code (built on top of a couple of dozen primitives like add, multiple, while, …), or symbolic processing (built on top of a few primitives like let-rec, cons, fold, …). These tend to express a lot of different behavior by combining a few primitives in rich way. The order and structure of the arrangement of primitives matters a lot, the semantics of a program is not given by the mere set of primitives that it uses.

The paper fundamentally lacks any justification for calling information that isn't captured in the minset “non-semantic” or “chaff”. Their analysis is very sensitive to language syntax and the intuitions are clearly wrong in common examples. The conclusion in the ITworld article is chosen for being sensational, not because it's a realistic measure of the semantic content of code.
> 5 votes

# Answer
The paper says:

> The meaning of many sentences survives the loss of words Some words in a sentence, however, cannot be lost without changing the meaning of the sentence.

and:

> For human understanding of the purpose and behavior of source code, we hypothesize that the same holds.

They introduce some techniques for digesting code, but I don't see any discussion of whether the results support the hypothesis, specifically, that the digested code retains it's meaning to a human reader.

Looking at the single sample in the paper, I'm skeptical that any person could reliably understand the purpose and behavior of the code. Try it for yourself, what does this code do:

```
int length = array . for ( i 0 < ; ++ ) { if [ j 1 - ] > temp }

```

While it's true that many languages are verbose, the approach they use to extract the meaning for human understanding is not effective, so I find their claim, which hinges on retaining the meaning, to be not well supported.
> 1 votes

---
Tags: programming-languages, information-theory
---


title: What counts as a pipeline?

text:
# Question
Title: What counts as a pipeline?
From Tanenbaum's Structured Computer Organization:

> Figure 2-4(a) illustrates **a pipeline** with **five units**, also called stages.
>
> If one pipeline is good, then surely two pipelines are better. One possible design for a **dual pipeline** CPU, based on Fig. 2-4, is shown in Fig. 2-5. Here **a single instruction fetch unit** fetches pairs of instructions together and puts each one into its own pipeline, complete with its own ALU for parallel operation.
>
> A different approach is used on high-end CPUs. The basic idea is to have just **a single pipeline** but give it **multiple functional units**, as shown in Fig. 2-6. The definition of ‘‘superscalar’’ has evolved somewhat over time. It is now used to describe processors that issue multiple instructions—often four or six—in a single clock cycle. Of course, a superscalar CPU must have multiple functional units to hand all these instructions to. Since superscalar processors generally have one pipeline, they tend to look like Fig. 2-6.

I wonder what counts as a pipeline?

In Figure 2-4(a), a pipeline consists of 5 stages.

In figure 2-5, two pipelines share the same instruction fetch unit, but why isn't it a single pipeline?

In figure 2-6, a pipeline has multiple functional units, but why isn't it multiple pipelines?

Thanks.

# Answer
In 2-4(a) each stage processes one instruction at a time using one unit for every stage. In 2-5 the instruction fetch unit remains the same but fetches *two* instructions that are then processed parallelly, each with its own unit. So we have two pipelines of cause. They are logically and physically seperated. But as far as I understand, the main difference between 2-5 and 2-6 is that in 2-6 the CPU decides dynamically what the order of execution of the instructions will be (out-of-order-execution) so that it can eliminate dependencies and hazards. The multipipeline approach executes parallel but in-order. But a superscalar CPU will as well need all stages twice. *I personally* think it would be wrong to say a superscalar has one single pipeline.
> 1 votes

---
Tags: computer-architecture
---


title: Random Graph is a good expander

text:
# Question
Title: Random Graph is a good expander
If a (n,d) random graph is a n-vertex graph defined as :

Choose d random permutations $\pi\_1 \ldots \pi\_d $, from \[n\] to \[n\]. Take edge (u,v) if $v = \pi\_i(u)$ for some i. I am trying to prove that, for every n and $d \geq 2$, a (n,d) random graph is a (n,2d,1/10) edge expander with probability 1 - o(1).

For a given S such that $|S| \leq n/2$, I have found the expected value of the number of edges |E(S,S')| between S and V\S. But since this random variable is the addition of random variables which are not independent, I cannot apply the Chernoff bound to say that, the probability of |E(S,S')| being far from its expected value is low.

Is there any other way to prove this ?

# Answer
> 4 votes
Try proving directly that with high probability, no set of size at most $n/2$ has a small edge neighborhood. See for example Ellis's writeup for the complete details.

Another possibility is to try and use a more sophisticated large deviation bound to analyze $|E(S,S')|$. For example, there are versions of Chernoff's bound for negatively dependent random variables, and there is Azuma's bound, which is a martingale version of Chernoff's bound. The classical example is concentration of the chromatic number, appearing in Chapter 7 of Alon & Spencer as well as many other places, such as Bukh's write-up.

---
Tags: complexity-theory, probability-theory, expanders
---


# Question
Title: Getting a variable assignment of a Tseitin transformed formula
Let $\phi$ be a Boolean formula and $\mathrm{Tseitin}(\phi)$ the corresponding Tseitin transformed equisatifiable formula.

It is well-known that one can get a variable assignment for $\phi$ by solving $\mathrm{Tseitin}(\phi)$ and dropping the auxiliary variables. For example, see Wiki, quote: "When a satisfying assignment of variables is found, those assignments for the introduced variables can simply be discarded."

After a long search through SAT papers I just could not find any paper which proves this statement. Because I do not want to re-invent the wheel: **Does anyone know such a reference I can use to cite?**

# Answer
Given a circuit $C$ on variables $V$ which has gates $G$, the Tseitin transformation produces a formula $T(C)$ on the set of variables $V \cup G$, with the property that the formula holds iff

1. The value of every gate variable $g \in G$ is exactly the value of this gate given the assignment to the inputs, and
2. The circuit outputs TRUE.

You can prove property (1) by induction. Property (2) holds since you add a specific clause stating that the top gate in the circuit is TRUE. Given this, there is an assignment causing the circuit $C$ to output true iff $T(C)$ is satisfiable, and moreover you can read this assignment from a satisfying assignment to $T(C)$ — just ignore the gate variables.

The crucial point is that in any satisfying assignment of $T(C)$, the value of the gate variables is completely determined by the value of the input variables.
> 1 votes

# Answer
There is no need to cite anything. This is known in the Tseitin transform and it is well-known in the SAT / formal methods community. Therefore, if you are writing for that community, there's no need to formally cite anything.

It is so well-known that it is covered on Wikipedia: https://en.wikipedia.org/wiki/Tseitin\_transformation. In the theoretical computer science community, this is the classic reduction from CircuitSAT to SAT. That reduction is proven or sketched in many undergraduate textbooks on theoretical computer science / algorithms / textbooks. I think it was also proven in Cook's seminal paper.

If you feel you absolutely want to cite something, you could look at the Tseitin paper cited on the Wikipedia page; that might have the earliest standard description.
> 1 votes

---
Tags: satisfiability, propositional-logic
---


# Question
Title: What happens when you don't use a metric in k-means?
K-means is a clustering algorithm which works like this:

```
def kmeans(int k, Coordinate[] points):
    Step 1: initialize k cluster centers to any (distinct) coordinates
    Step 2: check which points are closest to which cluster centers
    Step 3: move the cluster centers so they are central to their nodes
            e.g. by taking the average coordinate
    Step 4: back to step 2 (with some stop criterion)

```

Usually, the Euclidean metric is used in Step 2. What happens when no metric, but only a (symmetric) function $d: points \times points \rightarrow \mathbb{R}$ is used? Can k-means still produce meaningful results?

# Answer
> 3 votes
You should use k-means when you have coordinates and a euclidian distance metric. Its not just the distance that matters - you need to reassign cluster centers. So if you have coordinates, why use something other than euclidian distance? If you don't have coordinates, you can't use K-means.

# Answer
> 1 votes
In fact, you can use any function that has a property of a distance (symmetric, non-negative, triangle inequality) for clustering with k-means, such as Euclidean distance, Manhattan distance, $l\_n$ norm, and so forth. During each iteration, the cluster centers are assigned by the position that minimizes the sum of the distances to the points currently in its cluster. The Euclidean metric is particularly simple for finding that new cluster center: the center is the mean of the cluster points. However, every proper metric will yield cluster centers that minimize the sum of the distances to all points in the cluster, though it might be just a bit more complicated to calculate this new center.

If your distance function isn't a true metric, then you can get meaningless results, and even non-termination of the algorithm.

Most sophisticated software supports different distance measures in clustering, e.g., *Mathematica*, in which `FindClusters` supports a user-defined `DistanceFunction`.

---
Tags: algorithms, machine-learning, cluster
---


# Question
Title: Combine abstract factory with decorator pattern
I'm working on a simple project of software engineering that should combine two patterns. I choose Abstract Factory and Decorator patterns to modify (dynamically) objects created with the concrete Factory classes. My question is: is delegating object decorations to those Factory classes a design error?

Here's the UML scheme:

# Answer
I don't see that as a problem.

Factory are used to implement the Dependency Injection (DI) pattern, where one wish to dispense a section of code from having to know how to construct objects of a certain class, which could involve other secondary classes and render the aforementioned section of code more coupled to the rest of the codebase. The less coupling, the easier it is to update the code — the client part (that section of code), or the service part (the object being created — `Cake` in your case).

When it comes to decorators, you are essentially describing an algebra on the object: you start from some class instance (`Cake` object), and by applying an operator (the decorator), you obtain another object from the same class (to be precise, it's a subclass, so it's more akin to a refinement operation, but for our purpose, ignoring that part is OK).

The client code needs to know about that algebra, as a part of how it may manipulate the object, so you have to disclose this information. Now it could be in the form of a set of methods on the `Cake` class, a set of functions acting as operators, or methods on a class implementing that algebra.

The 2nd option might be more complicated to implement, if decorators need to share some information on the `Cake` class only available at runtime; you'd have to implement the DI pattern on them, and you would end up with either the first or the 3rd solution.

The remaining options are equivalent from the client code point of view, not adding more dependency either way.
> 0 votes

---
Tags: software-engineering, object-oriented, design-patterns
---


# Question
Title: Method for Creating Any Unambiguous Grammar?
I'm in an undergraduate class where we're studying formal grammars right now. I asked my teacher if there was any known set of rules for creating context free grammars that

1. Was guaranteed to produce an unambiguous grammar.
2. Allows for the creation of any possible unambiguous grammar.

I am well aware that determining whether a grammar is ambiguous is undecidable. I'm not sure if the above stated idea is reducible to that, but after fiddling around with it a bit, I couldn't think of a method for making such a reduction. That said I'm really no expert at reductions or grammars. I tried googling for a while, but I only found pages about undecidability. Does anyone know?

# Answer
> 4 votes
No, and there is indeed a reduction to the undecidability of ambiguity.

First, note that ambiguity is (for context-free grammars) semi-decidable: just keep generating words by different left-derivations and say "ambiguous!" when you first find a word you've seen before.

Now, the method you are proposing allows to semi-decide *unambiguity*. You effectively look for a computable enumeration of all unambiguous grammars. You just generate grammars until you find your given grammar and answer "unambiguous!".

Since semi-decidability and co-semi-decidability imply decidability, this contradicts what you already know. Hence, there can be no "set of rules" as you propose.

---
Tags: context-free, formal-grammars, ambiguity
---


title: A partition algorithm

text:
# Question
Title: A partition algorithm
I have encountered the following problem that I found very interesting to solve:

> Given an array of positive integers $\\{a\_1, a\_2, ..., a\_n\\}$ you are required to partition the array into $3$ blocks/partitions such that the maximum of sums of integers in each partition is the minimum it can be. Restriction: you cannot alter the turn in which the numbers appear (example: if you have $\\{2, 5, 80, 1, 200, 80, 8000, 90\\}$ one partition **CANNOT** be the $\\{2, 80, 1, 90\\}$). The program must output **ONLY** the maximum sum, not the partitions.

So, for example let's have the array $\\{2, 80, 50, 42, 1, 1, 1, 2\\}$. The best partitioning according to the problem is $$\\{\\, \\{2, 80\\},\\, \\{50\\},\\, \\{42, 1, 1, 1, 2\\} \\,\\}$$, so the output of the program in this case would be $82$.

I have already thought of a $\mathcal{O}(n^2)$ algorithm, but isn't there any better ( e.g. $\mathcal{O}(n)$ or $\mathcal{O}(n \log n)$ ) algorithm?

My $\mathcal{O}(n^2)$ algorithm is (it is pseudocode):

> 1. input $n \in \mathbb{Z}$
> 2. **Let** $m \leftarrow -1$
> 3. **Let** $r\_1 \leftarrow r\_2 \leftarrow r\_3 \leftarrow 0$
> 4. **Let** $A \leftarrow (a\_0,...,a\_{n-1})$
> 5. **Let** $S \leftarrow \sum\_{i=0}^{n-1}{a\_i}$
> 6. **for each** $i = 1$ **until** $n-2$ **do**
> 7. $\quad r\_1 \leftarrow (r\_1 + a\_{i-1})$
> 8. $\quad r\_2 \leftarrow 0$
> 9. $\quad$ **for each** $j = (i+1)$ **until** $n-1$ **do**
> 10. $\quad\quad r\_2 \leftarrow (r\_2 + a\_{j-1})$
> 11. $\quad\quad r\_3 \leftarrow S - (r\_2 + r\_1)$
> 12. $\quad\quad \max\_{\mathsf{temp}} \leftarrow \max(\max(r\_1,r\_2),r\_3)$
> 13. $\quad\quad$**if** $(\max\_{\mathsf{temp}} \< m \\, \vee m = -1)$ **then**
> 14. $\quad\quad\quad m \leftarrow \max\_{\mathsf{temp}}$
> 15. $\quad\quad$**endif**
> 16. **return** $m$

# Answer
> 2 votes
Since you find it interesting to solve, I do not want to completely spoil it too much for you. So here is a big hint to solve it in linear time.

You start with two indices $i$ and $j$ which are the first and last indices of central segment.

Initially you set $i=0$ and $j=n$. And you compute the 3 sums in $s\_1$, $s\_2$ and $s\_3$. So initially $s\_1=s\_3=0$.

Then you progressively increase $i$ and decrease $j$, by variations of 1, keeping $s\_1$ and $s\_3$ about the same value (by doing the change on the smallest sum $s\_1$ or $s\_3$), until one becomes bigger than $s\_2$. Each increment or decrement takes constant time (adding or substracting the value of an element to two of the sums, and doing a few comparisons).

When one of $s\_1$ and $s\_3$ becomes larger than $s\_2$, say for example $s\_1$. Then you have $s\_1\geq s\_2 \> s\_3$.

Then you know that the right value for $i$ is either the current value or the previous value. Typically it is the previous value of i, if $s\_1$ has become greater that the previous value of $s\_2$. But things are a bit more subtle. So you note this value of $s\_1$ as $m\_1$, a possibility for the maximum, and then try to see if you could have achieved a lower value for the maximum with the previous value of $i$ and $s\_1$, just before the last increase. So you revert $i$ to that previous value, and you start to decrease $j$ to get the lowest possible maximum for $s\_2$ and $s\_3$ without touching $i$ (that is easy, and recall that $s\_1$ remains lower than both others sums). Let $m\_{2,3}$ be the lowest maximum found. Now, if $m\_{2,3}$ is greater than $m\_1$, then the answer is $m\_1$, else the answer is $m\_{2,3}$.

And you must consider the symmetrical case when $s\_3$ is the first to exceed $s\_2$.

---
Tags: algorithms, arrays, partition-problem
---


# Question
Title: True or False: If $A \subseteq \{0,1\}^* \Rightarrow A^*$ is semi-decidable
Question: Is the following statement true or false?

If $A \subseteq \\{0,1\\}^\* \Rightarrow A^\*$ is semi-decidable

I thought that since every language is automatically of type 0, it follows that $A \in RE$, and since RE is closed under the Kleene star operator, it follows that $A^\* \in RE$ and therefore semi-decidable.

However the solution says it's not true and uses the following counterexample:

If $A = \\{1^n0 | 1^n \not\in H'\\}$, where H' is the unaryly coded halting problem. Since $\overline{H} \leq A$, A is not semi-decidable. If $A^\*$ were semi-decidable then so would be $A^\* \cap \\{1\\}^\* = A$, since $\\{1\\}^\*0$ is semi-decidable and RE is closed under intersection, which is a contradiction.

Since I don't fully understand that line of reasoning, could someone please tell me what's wrong with my argumentation?

# Answer
It is not true that every language is recursively enumerable ("type 0").

Proof 1. Every RE language is semi-decided by some Turing machine. There are only countably many Turing machines (each one can be coded as a finite string, or an integer) but there are uncountably many languages. Therefore, there are uncountably many languages that are not RE.

Proof 2. If a language and its complement are both semi-decidable, they are, in fact, both decidable. The halting problem is semi-decidable. If the complement of the halting problem were semi-decidable then both it and the halting problem would be decidable. But we know that the halting problem is not decidable. Therefore, the complement of the halting problem is not semi-decidable.
> 5 votes

---
Tags: formal-languages, semi-decidability
---


# Question
Title: Does the state of a cell in cellular automata has to be from a finite set?
In most (all I have seen) work on cellular automata, the state of a cell is from a finite set. Such as a cell can take value from a binary set, or from among few colors. Can we define the state to be something more complicated such as a function of the coordinates of the neighbor cells? (assuming there is a initial coordinate value give to at least one cell) So for example in 2-D if my neighbor to the left has coordinate $(x,y)$ my state will take a value $f(x,y)$ where $f$ is same for all cells.

# Answer
> 1 votes
Although Wikipedia mentions a finite set of states (http://en.wikipedia.org/wiki/Cellular\_automaton), I'm sure you could find some interesting models that use infinitely many states. As you suggested, each cell could contain an integer, a continuous value between 0 & 1 (shade of grey), etc.

The idea of basing cell contents upon cell coordinates is interesting and unfamiliar. Of course, you'd have to also include some other inputs in the transition function if you want the pattern to change from step to step. This would create patterns that vary based on their location, which sounds fun to explore.

# Answer
> 1 votes
I'm hardly the expert on these matters (my only point of contact being an artificial life class a while back) but a bit of googling found an interesting application of infinite-state cellular automata: "lattice-gas" cellular automata which apparently are used to solve PDEs by discretizing the diffusion equation. I'm strongly suspect there are more such applications, but like I said, I don't know much about them.

Note another book which says somethig rather obvious namely that the classic cellular automata lie at one extreme end of discretization with space, time and state being all discrete in CAs, while classic PDEs are at the other end with all three continuous. It also notes that there's no reason not to consider mixtures of these; it also gives additional synonyms you can google for continuous-state (but discrete time and space) cellular automata: *coupled map lattices* and *lattice dynamical systems*; on a quick look both terms seem to produce a fairly rich literature. So whether these are (properly) called cellular automata... it depends who you ask, I suppose. (Also I could not help myself LOL at the comment on next page in that book \[which is at its 3rd ed.\] "Obviously, this field is tempting for computer freaks".)

---
Tags: automata, cellular-automata
---


# Question
Title: Unification --- removing equations and updating the solution
This question is concerned with the first order unification. Suppose I have a set $D$ of equations and a solution to these equations. Let this solution be a set $S$ of substitutions. Now, suppose I remove some equations from $D$. Is there an algorithm that just uses these removed equations and quickly updates $D$, or the unification needs to be done from scratch?

(In my application, I tend to have a lot of equations, so that is why I am interested in a solution that does not recompute everything.)

# Answer
If *all* you have is the solution to these equations (the most general unifier for $D$), I don't know of any good algorithm for your problem that will be better than "compute the answer from scratch" in general.

However, if you are willing to save some extra information on the side while you are solving $D$, then yes there are methods to do what you want -- with some caveats. In particular, you can use a persistent union-find data structure to help. Normally, we'd use union-find for unification (to compute the solution, i.e., the most general unifier). Here the idea is to instead use a persistent union-find data structure. This provides the ability to "roll back" some of the union operations and then go forward from there.

See the following research paper:

A persistent union-find data structure. Sylvain Conchon, Jean-Christophe Filliâtre. ACM SIGPLAN Workshop on ML, 2007. See also https://www.lri.fr/~filliatr/puf/ .

Caveats: Their data structure is only semi-persistent, i.e., only partially persistent. This means you can roll back to an earlier version of the data structure and make modifications from there, but you can't do any more than that.

One consequence is that the efficiency of the above approach will depend upon the order in which you process the equations. If you want to remove a few equations that were processed near the end and then compute the new solution, this will be very efficient (with the above data structure). But if you want to remove an equation that was processed near the beginning and then compute the new solution, this will be relatively slow. In other words, suppose your equations are $D=\\{D\_1,\dots,D\_n\\}$ and you compute the solution (most general unifier) by processing the equations in the order $D\_1,D\_2,\dots,D\_n$ (to process an equation you call the Union operation on the union-find data structure). Now suppose you want to remove equation $D\_i$. With the above partially persistent union-find data structure, you can do this by rolling back the state of the union-find data structure to its state after processing $D\_1,\dots,D\_{i-1}$, then processing equations $D\_{i+1},\dots,D\_n$ starting from there. If $i$ is close to $n$, this will be efficient (it will take $n-i$ Union operations), but if $i$ is small, it won't be much better than just starting from scratch.

In principle if we had a confluently persistent union-find data structure we could remove this limitation. However, I don't personally know of any efficient confluently persistent union-find data structure. I'm not sure whether such a thing has been studied in the literature or not; this answer seems to suggest it was an open problem, at least as of 2010. (Here is a survey on confluent persistence.)
> 2 votes

---
Tags: algorithms, logic, unification
---


# Question
Title: Is the number of inequivalent elementary cellular automata rules really 88?
Everywhere from Wolfram's "New Kind of Science" (p. 57) to Wikipedia they say that, out of all possible 256 (=2^8) elementary cellular automata rules, 88 are inequivalent (as defined in the Wikipedia article).

Now, the problem is that I am failing to reproduce the 88 number. No matter how I try - I always get 72.

And it gets worse. Sequence A005418 seems to be defined exactly as Wolfram's inequivalence (see the comment: "Number of bit strings of length (n-1), not counting strings which are the end-for-end reversal or the 0-for-1 reversal of each other as different."). And in that sequence at position 8 they also have 72, not 88.

Off course, there is a chance that my program is wrong and/or I do not fully understand the definition of rule equivalence. Therefore I would like to ask someone to reproduce the computations, and either confirm Wolfram's original number 88, or give me the correct number of inequivalent rules (be it 72, or something else).

This problem is important for a research paper I am working on. And it's not very difficult to implement.

# Answer
I tried it myself with the following Python code:

```
def yflip(a):
    D={0:0,1:4,2:2,3:6,4:1,5:5,6:3,7:7} # Vertical flip
    #D={0:7,1:6,2:5,3:4,4:3,5:2,6:1,7:0} # String reverse

    t=0
    for i in range(8):
        c=(a>>i)&1
        t |= c << D[i]
    return t

def complement(a):
    return a ^ 0xff

def canonical_form(a):
    b=yflip(a)
    c=complement(a)
    d=complement(yflip(a))
    return min(a,b,c,d)

A=set()
for patt in range(256):
    A.add(canonical_form(patt))
print len(A)

```

The dictionary D defines how to do a vertical flip. I think the correct interpretation is to move the state for the case 110 to the state for the case 011. This results in a different arrangement of the bits to just doing a straight string reverse.

Note wikipedia gives us a test case:

> For example, if the definition of rule 110 is reflected through a vertical line, the following rule (rule 124) is obtained:

This works with my dictionary `assert yflip(110)==124`, but not with the string reverse.

The result for this is that with a straight string reverse I get 72 (same as yours).

With my interpretation of the vertical flip I get 80. Unfortunately, this is still not 88 so I am just as confused now...

## UPDATE

I had misunderstood the complementary rule:

The actual complementary rule should be implemented as follows:

```
def complement(a):
    t=0
    for i in range(8):
        # Flip bits in this case
        x = i ^ 7
        # Try case x in the original pattern
        result = 1 & (a>>x)
        # Use the opposite
        result ^= 1
        t |= result << i
    return t

```

this results in 88 cases being found.

Note that you need to exchange 0's and 1's in both the cases, and in the final results.
> 2 votes

# Answer
OK! Peter de Rivaz has confirmed the number $88$ by careful analysis of the two equivalence rules, and a clever script.

Here I will try to repeat the analysis (for my own understanding) and then apply some mathematical magic.

A binary cellular automaton is denoted by a bit string $ABCDEFGH$ where the consecutive letters denote each a bit (next state) for the three bits that encode the configuration at position with its two neighbours, $xyz = 111, 110, 101, \dots, 001, 000$.

The `mirror` operation is the automaton in left-right reverse, meaning that the bit for $xyz$ is now at $zyx$. Thus $A$ at $111$ stays in place, but $B$ at $110$ is swapped with position $E$ at $011$. The new rule is then $AECGBFDH$. There are $64$ rules that stay unchanged under this operation. Says Wikipedia.

The `complement` operation is the automaton with bits swapped, meaning that the bit for $xyz$ is now the negation of bit $\bar x\bar y\bar z$, which looks rather DeMorgan to me. In words, the bits are reversed *and* inverted. The new rule is then $\bar H\bar G\bar F\bar E\bar D\bar C\bar B\bar A$. There are $16$ rules that stay unchanged under this operation. Says Wikipedia.

We can also combine the two rules. `Mirror complement` gives $\bar H\bar D\bar F\bar B\bar G\bar C\bar E\bar A$. Again there are $16$ rules unchanged under this rule. The math is easy, unchanged means $A=\bar H$, $B=\bar D$ etc, finally leaving $4$ free variables.

Applying no operation `identity` keeps all $256$ bit strings unchanged. Also any combination of `mirror` and `complement` will again be one of the four above operations (but you have to convince yourself on that).

The magic is Burnside's Lemma: the number of orbits under a group $G$ of permutations of a set $S$ equals $\frac1{|G|}\sum\_{\psi\in G}|\text{fix}(\psi)|$.

The number of orbits here is the number of inequivalent cellular automata. Let's check the math: $\frac14(256+64+16+16) = 352/4 = 88$. This (again) confirms the number on Wikipedia.
> 3 votes

---
Tags: automata, combinatorics, cellular-automata
---


title: GCD Strongly Polynomial Time

text:
# Question
Title: GCD Strongly Polynomial Time
I don't understand why GCD is not Strongly Polynomial Time?

Can you explain in an example, why the storage size cannot be Polynomial Bounded?

So is GCD in the Complexity Class P?

# Answer
> 3 votes
As Wikipedia mentions, the reason that the Euclidean algorithm for GCD doesn't run in strongly polynomial time is that the number of arithmetic operations is unbounded, although there are always only two inputs. On the other hand, the running time is polynomial in the input size, and so the Euclidean algorithm runs in polynomial time. In particular, GCD is in FP (the class of functions computable in polynomial time).

# Answer
> 3 votes
The GCD *can* be computed in polynomial time. Strongly Polynomial is a much more restrictive classification. Taking the definition from here:

> An algorithm runs in **strongly polynomial time** if
>
> * the number of operations in the arithmetic model of computation is bounded by a polynomial in *the number of integers in the input* instance; and
> * the space used by the algorithm is bounded by a polynomial in the size of the input.

The input to GCD is two integers. Thus, in order to be solvable in strongly polynomial time, GCD would need to be solvable with a constant number of aritmethic operations since the input size is constant.

---
Tags: complexity-theory
---


title: Complexity class of Matrix Inversion

text:
# Question
Title: Complexity class of Matrix Inversion
Is inverting a matrix in the Complexity class $\text{P}$ ?

From the runtime I would say yes $\mathcal{O}(n^3)$ but the inverted matrix can contain entries where the size is not polynomially bounded by the input?

# Answer
> 14 votes
Yes, it can be done in polynomial time, but the proof is quite subtle. It's not simply $\mathcal{O}(n^3)$ time, because Gaussian elimination involves multiplying and adding numbers, and the time to perform each of those arithmetic operations is dependent on how large they are. For some matrices, the intermediate values can become extremely large, so Gaussian elimination doesn't necessarily run in polynomial time.

Fortunately, there *are* algorithms that *do* run in polynomial time. They require quite a bit more care in the design of the algorithm and the analysis of the algorithm to prove that the running time is polynomial, but it can be done. For instance, the running time of Bareiss's algorithm is something like $\mathcal{O}(n^5 (\log n)^2)$ \[actually it is more complex than that, but take that as a simplification for now\].

For lots more details, see Dick Lipton's blog entry Forgetting Results and What is the actual time complexity of Gaussian elimination? and Wikipedia's summary.

Finally, a word of caution. The precise running time depends upon exactly what field you are working over. The above discussion applies if you are working with rational numbers. On the other hand, if, for instance, you are working over the finite field $\mathrm{GF}(2)$ (the integers modulo 2), then naive Gaussian elimination *does* run in $\mathcal{O}(n^3)$ time. If you don't understand what this means, you can likely ignore this last paragraph.

# Answer
> 2 votes
There is a formula for the entries of the inverse matrix which gives each entry as a ratio of two determinants, one of a minor of the original matrix, and the other of the entire original matrix. This should help you bound the size of the entries in the inverse matrix, if you're careful, given a reasonable notion of "size" (note that even if you start with an integer matrix, the inverse could contain rational entries).

That said, often matrix inverse is studied from the point of view of the algebraic complexity theory, in which you count basic operations regardless of magnitude. In this model, one can show that the complexity of matrix inverse is equivalent to the complexity of matrix multiplication, up to polylogarithmic terms; this reduction can perhaps also help you bound the size of the coefficients.

Given the efficient algorithm in the algebraic complexity theory model, one wonders whether it implies a similarly efficient algorithm in the usual model; can it be that although the final entries are polynomial size, the calculation involves larger ones? This is probably not the case, and even if it were, the issue could perhaps be avoided using the Chinese remainder theorem.

---
Tags: complexity-theory
---