title: Max cut in cubic graphs

text:
# Question
Title: Max cut in cubic graphs
The following question is related to the max cut problem in *cubic graphs*. In this survey paper Theorem 6.5 states

> A maximal cut of a cubic graph can be computed in polynomial time

Browsing through some other related results (for example this SODA paper) one gets the impression that this problem is actually NP complete even for cubic instances. In particular, the last paper states that this is indeed so if the graph is subcubic.

That makes me wonder.. What's going on? Is the survey paper (and the result cited therein) faulty or is there some point that I am missing?

# Answer
Maximal cut is different from maximum cut (MAX-CUT). In maximum cut, the goal is to find a cut cutting the maximal number of edges. In maximal cut, the goal is to find a local maximum: a cut such that switching the side of any single vertex does not result in more edges being cut. Such a cut exists, since the maximum cut is also maximal. But finding a maximum cut is apparently harder than finding just a maximal cut.
> 3 votes

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


# Question
Title: Is there a crossover operator to cross sections of specific phenotype genes?
For example, I've a chromosome with 10 genes, the first 5 genes represent a specific property of phenotype and the last 5 genes represent another property of phenotype.

So, I need a crossover operator that performs the cross considering this configuration, where the parent1's first 5 genes are cross with parent2's first 5 genes and the same for the last 5 genes.

Is there any paper or description of a crossover operator to perform cross in this kind of chromosome?

# Answer
> 1 votes
Let's say you have two parents. For the sake of clarity, let's say that the first five alleles can be either '\*' or '-', and the second five either 'x' or 'o'. Our parents might then look like the following.

```
- - - - - | + + + + +

x x x x x | o o o o o

```

I'm interpreting the question to mean that you want an operator which only operates on whole phenotypes. As far as I can see, there's only one way to do that, which is to do one-point crossover with the crossover point fixed to the boundary between the two parts.

I question whether this is a good idea. It's a very weak search operator, and in order for it to work reasonably well, I would guess you'd need a very high mutation rate to provide some search power and some sort of elitist selection to keep the mutation from killing your good solutions.

Without more information about your problem, it's hard to say for sure what your needs really are. However, the standard way of handling multiple phenotypic variables is to encode them into a single chromosome, as you've done, but then treat them as one string free of semantics. You just do whatever crossover operator you'd normally do. Yes, that means that your crossover might take part of one property mixed with part of another, but that's what happens in biology as well. In my example, no matter where you put the crossover point, you still get valid offspring. You might do uniform crossover and get children like

```
- x x - x | o + + o +

x - - x - | + o o + o

```

but those are perfectly valid offspring. The result is that crossover can explore a much wider part of the search space.

I'm not aware of a reference off the top of my head that compares the two ideas. Probably someone in the early days of GAs has looked at this. But unless you need to cite an authoritative source to justify your decision, I'd say just implement whichever version seems like the right answer for your problem. Both are trivial to code.

---
Tags: genetic-algorithms
---


# Question
Title: Are 'zero-one' jigsaw puzzles NP-complete?
I'm interested in a slight variant of tiling, the 'jigsaw' puzzle: each edge of a (square) tile is labeled with a symbol from $\\{1\ldots n, \bar{1}\ldots\bar{n}\\}$, and two tiles can be placed adjacent to each other iff the symbol on one tile's facing edge is $k$ and the symbol on the other tile's facing edge is $\bar{k}$, for some $k\in\\{1\ldots n\\}$. Then, given a set of $m^2$ tiles, can they be placed into an $m\times m$ square (rotating but not flipping the tiles) with all edges matching correctly? (There's also a variant on this problem in which four $1\times m$ 'framing' edges are provided and the pieces must fit correctly into that frame).

I know this problem is NP-complete for sufficiently large $n$, but the bounds that I've seen on $n$ seem to be fairly large; I'm interested in the problem for small values of $n$ and in particular for $n=1$, the 'zero-one' case (where every edge is labeled either $0$ or $1$ and edges with a $0$ must be matched to edges with a $1$). Here there are (with rotational symmetry) just six tile types (the all-zeroes tile, the all-ones tile, the tile with three zeroes and a one, the tile with three ones and a zero, and two distinct tiles with two zeroes and two ones, '0011' and '0101'), so a problem instance is just a specification of $m$ and a set of five numbers $T\_{0000}$, $T\_{0001}$, $T\_{0011}$, $T\_{0101}$, $T\_{0111}$ and $T\_{1111}$ (representing the count of each type of tile) with $T\_{0000}+T\_{0001}+T\_{0011}+T\_{0101}+T\_{0111}+T\_{1111}=m^2$. The problem is obviously in NP (with $m$ given in unary) since a solution can simply be exhibited and then checked in polynomial (in $m$) time, but is it known to be NP-complete, or is there some dynamic programming algorithm that can be applied here? What about the 'framed' case where the problem specification also includes the four edges of the square that are to be matched? (Obviously if the unframed case is NP-complete the framed case almost certainly is as well)

# Answer
> 3 votes
Since you mentioned you are interested in solving this problem for small values of $n$, I would suggest that you try implementing this in a SAT solver or as an integer linear program (ILP). Either one will be able to encode the constraints, but in a slightly different way:

* For SAT, there is a very clean encoding of the choice of which tile goes into each square, and a slightly less clean encoding of the constraint regarding the number of each kind of tile (using bit arithmetic).
* For ILP, there is a very clean encoding of the constraint regarding the number of each kind of tile available, and a slightly less clean encoding of the constraints on which tiles can be adjacent to each other (but it is still expressible, since you can express arbitrary boolean formulas in ILP).

I would expect that for small or medium sized $n$, this approach might work efficiently.

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


# Question
Title: short text categorization with spelling correction
I am building a classifier for short texts in a chat system. My features are words and pairs of words.

Naturally, the sentences contain spelling mistakes. If a particular wrong spelling of a certain word hasn't appeared in the training corpus, the classifier has no chance to identify it.

I consider taking an existing spelling corrector, and integrate it with my current classifier, but I am not sure how to do it.

Do you know of a paper that integrates an automatic spelling correction tool with a short text classifier?

# Answer
> 1 votes
Could you not just pre-process the text? Simply pass over the corpus and correct errors via edit-distance or lookup tables. Once this has finished you can then run the classifier.

It you *really* want to incorporate the correction into your model, it would seem that you can re-define edit distance to compute the log-probability of some misspelled word matching another for some mismatch probability $\theta \sim \text{Beta}(\alpha, \beta)$.

The resulting probabilities can then be incorporated into the classifier directly, which would be parameterized by $\theta$. Depending on how complex your internal model is, you could find the ML or MAP estimate $\hat{\theta}$ by some EM algorithm, or if the model allows, analytically.

---
Tags: reference-request, machine-learning, natural-language-processing, classification
---


# Question
Title: Is there a formula to state the number of 'sets' of 'ordered sets within ordered groups'?
I am new to this and an amateur... please help.

**My Question in practical terms:** Given The three following inputs... determine the number of *unique* group arrangements as an ordered set.

**INPUT:** 'a' = Students 'b' = Groups 'c' = students per group

**OUPUT ANSWER:** 'z' as an integer

**OUTPUT RULES:** \- All elements considered are ordered from left to right starting with the smallest number. \- Order is not important... (1,2,3)=(2,3,1)=(3,2,1)=(3,1,2)=(1,3,2)=(2,1,3)...THEREFORE (1,2,3) is the only unique group that is to be counted.

---

**Problem Example #1:** I have 12 students that I need to arrange into 4 groups. I want the 4 groups to each contain 3 students with no student appearing in more than one group. How many arrangements are there? In this instance there are 880 ordered arrangements. \[Output Format: (1,2,3)(4,5,6)(7,8,9)(10,11,12)\]

**Problem Example #2:** I have 12 students that I need to arrange into 3 groups. I want the 3 groups to each contain 2 students with no student appearing in more than one group. How many arrangements are there? In this instance there are 13,860 ordered arrangements. \[Output Format: (1,4)(3,6)(7,11)\]

**Problem Example #3:** I have 24 students that I need to arrange into 3 groups. I want the 3 groups to each contain 6 students with no student appearing in more than one group. How many arrangements are there? In this instance there are 125,847,260 ordered arrangements. \[Output Format: (1,2,3,4,5,6)(9,10,11,12,13)(15,16,17,18,19,20)\]

---

Unless I am mistaken, these are not 'combinations' or 'permutation's or 'complete sets' or 'hoyosa index'. So, for lack of better terms I am calling them *ordered sets within ordered groups* for now.

Is there a known formula to generate the answer without generating all possible solutions and searching?

**20130822---ADDENDUM---** The numbers provided are accurate. The closest description tat I can call relate this to would be "Independent Edge Set AKA Matching"... except that I BELIEVE matching has a limit of two students per group. Sticking to the "Two Students per group" this can be determined using factorials similar to those you have provided. HOWEVER, I cannot find a formula that allows for the three INPUTS a,b,c as provided and ONLY accounts for unique ordered sets.

Using Problem Example #2: 12 Students (a), 2 groups (b), 3 students (c), = 13,860 unique ordered sets Set #1\[(1,2,3,)(4,5,6)\] Set #2\[(1,2,3,)(4,5,7)\] Set #3\[(1,2,3,)(4,5,8)\] ... Set #13,860 \[(7,8,9)(10,11,12)\]

# Answer
> 2 votes
Here the explanation for the numbers we found in the comments, which unfortunately do not match yours. If you have additional explanations I can delete this answer, or perhaps improve.

Goal: given $a$ students, make $b$ groups, each consisting of $c$ persons, $bc \le a$. What is the number of possibilities?

My assumptions, the groups are unordered, so $(1,2,3)$ is the same group as $(3,1,2)$. Also the solution $(1,2)(3,4)$ is equal to $(3,4)(1,2)$

Put your students in a row: $a!$ possibilities. The first $b$ students form the first group, the next $b$ students the second group, etc. The order in the line-up between each group of students does not matter, so we have to divide by th1s number of possibilities which is $(c!)^b$. Again we divide by $(a-bc)!$ the number of permutations of the not chosen ones. Also, the order of the groups themselves does not matter, we additionally divide by $b!$.

Answer: $a!\\;/\\;{(c!)^b (a-bc)! \\;b!}$

Another way of obtaining the same number. Choose a group of $c$ students from total $a$, then a group of $c$ students from the remaining $c-b$, etc. This can be done in ${a \choose c}{a-c\choose c}\dots{a-c(b-1)\choose c}$. Again I divide by the possible orderings of the groups which is $b!$. Thus $\frac{a!}{c!(a-c)!}\frac{(a-c)!}{c!(a-2c)!}\dots \frac{(a-(b-1)c)!}{c!(a-bc)!} / b!$

Your first example $a=12$, $b=4$, $c=3$. You have 880, this number is 15400.

Second example $a=12$, $b=3$, $c=2$. 13680, we agree.

---
Tags: combinatorics, sets, matching
---


# Question
Title: Why are weights of Neural Networks initialized with random numbers?
Why are neural networks initial weights initialized as random numbers? I had read somewhere that this is done to "break the symmetry" and this makes the neural network learn faster. How does breaking the symmetry make it learn faster?

Would'nt initializing the weights to 0 be a better idea? That way the weights would be able to find their values (whether positive or negative) faster?

Is there some other underlying philosophy behind randomizing the weights apart from hoping that they would be near their optimum values when initialized?

# Answer
> 6 votes
The basic intuition behind initializing weight layers into small (and different) values is just so that the bias of the system is broken and weight values can move along and away and apart to different values.

More concretely, you'ld probably want your initial weights to be distinct and have "a small gap" between them, this 'gap' expands out as you go along and forces the weights to be a bit larger at every iteration, and this helps the network to converge faster, i.e. the learning process speeds up.

If you would instead have all your weights to some constant, each weight will be updated at a very slow (~fixed) rate, and this won't help much, specially if the initial values are 'very far' from the final values.

Hope that helps, Have fun learning :)

---
Tags: machine-learning, artificial-intelligence, neural-networks
---


title: Seating Chart Optimization

text:
# Question
Title: Seating Chart Optimization
I'm trying to find an algorithm to solve the seating chart problem. The goal is to place pepole at one (or multiple) tables such that the overall happiness is maximized.

Each seat has neighbors. A person on a seat can talk to persons on neighboring seats (note that these neighbors normally sit next to each other or on the opposite side of the table).

Example of a table with 4 seats on each side:

```
1 2 3 4
8 7 6 5

```

6 has neighbors 2, 3, 4, 5 and 7, 8 has neighbors 1, 2, 7

There's a matrix describing how well two persons get along with each other. This is a value between 0 and 9 (the relation value). Relations are symmetrical.

Example of a relation matrix with four people:

```
  A B C D
A 0 2 0 5
B 2 0 3 6
C 0 3 0 1
D 5 6 1 0

```

The happiness of a single person is the sum of the relation values of all neighboring persons.

How would you find a solution that maximizes the overall happiness?

# Answer
> 3 votes
I use an ILP. I hope there are better solutions available.

Let H be your $n\times n$ happiness matrix. I use $n^2$ 0-1-variables $uv\_{ij}$ per edge $uv$ in the seating graph. $uv\_{ij}$ is 1 if person $i$ sits at place $u$ and person $j$ sits at place $v$.

maximize $\sum\_{uv\in E} h\_{ij} \cdot uv\_{ij}$
s.t.
$\sum\_{i,j} uv\_{ij}=1$ for all $uv$, each edge gets exactly one neighbor configuration
$\sum\_{j} ux\_{ij} = \sum\_{j} uy\_{ij}$ for all edges $ux$ $uy$ that share an endpoint and all i, if $i$ sits at $u$ according to $ux$, they must also sit at $u$ according to $uy$

---
Tags: algorithms, optimization
---


# Question
Title: Order a list of whole numbers so that no two numbers have the average of them sitting between them
Given a whole number N..

Arrange 1 to N in a sequence such that no two numbers have their average sitting between them...

Note - If N=20.. average of 19 and 2 = 10.5 is not a whole number .. hence we do not need to worry about such numbers and their averages.. In other words, if average of two numbers is not a whole number.. we assume that their average does not exist in the list 1 to N..

# Answer
Here's a simple recursive construction for the more restrictive version of the problem. First of all, note that the average of an odd number and an even number is never a whole number; if $a=2i-1$ and $b=2j$, then $\frac12(a+b)=i+j-1+\frac12$. This means that if we put the $\lceil N/2\rceil$ odd numbers $a\_i$ first (in some as-yet-to-be-determined order) and then the $\lfloor N/2\rfloor$ even numbers $b\_j$ (likewise, in some as-yet-to-be-determined order), then we can be guaranteed that the average of a $a\_i$ and a $b\_j$ can never be between them (because it'll never be a whole number), so we've split the problem into two subproblems: one for the set of odd numbers $a\_i$ and one for the set of even numbers $b\_j$.

But note now that if we have two odd numbers $a\_m=2m-1$ and $a\_n=2n-1$, then their average is $2\left(\frac{m+n}2\right)-1$, and so the subproblem of 'sorting' the $a\_i$ correctly is exactly the same as sorting the numbers $c\_i\in 1\ldots n$, where $c\_i=\frac{a\_i+1}{2}$ and $n=\lceil N/2\rceil$; a similar result holds true for the even numbers $b\_j$. This means that we can keep applying the same procedure to both of these groups recursively. For instance, when $N=8$ this construction produces the ordering $15372648$. Note that if we subtract one from these values and look at the numbers $0\ldots(N-1)$, then this ordering is $04261537$; looking at the bit patterns for these numbers ($000, 100, 010, 110, 001, 101, 011, 111$) shows that they're just the bit patterns of the numbers $0\ldots 7$, reversed! This 'bit reversal' shuffle is used by Fast Fourier Transform (FFT) algorithms to correct the output ordering of their data (see, for instance, http://www.cmlab.csie.ntu.edu.tw/cml/dsp/training/coding/transform/fft.html ).

In fact, this construction shows that there are at least $O(2^{N/2})$ such orderings, since at each of the $N/2$ 'internal' nodes we can choose to either put the odd or the even numbers first without spoiling the result. These don't exhaust all of the orderings, though; for instance, we can exchange $2$ and $7$ in the constructed $N=8$ ordering to get the ordering $15327648$ which also clearly satisfies the constraint but can never be constructed by this procedure (since odd and even numbers are 'intermingled'). I don't know how many of the $N!$ orderings of $1\ldots N$ actually satisfy the problem.
> 5 votes

# Answer
An algorithm to make sure that no three numbers(anywhere in the sequence) are in AP, which will yield the answer -

```
Given N
start with array A[] = 1, 2.. N-1, N (AP with diff = 1)
Split A into two APs (with diff =2) A1 and A2 so that no triplet (2 terms in A1 and 1 term in A2 or 2 terms in A2 and 1 term in A1) are in AP.
Apply the same logic on A1 and A2 (now for AP with diff=4 and so on) recursively
Do this until the splitted sequences have a length atmost 2.

```
> 0 votes

---
Tags: algorithms
---


# Question
Title: Complexity of deciding if a formula has exactly 1 satisfying assignment
The decision problem

> Given a Boolean formula $\phi$, does $\phi$ have exactly one satisfying assignment?

can be seen to be in $\Delta\_2$, $\mathsf{UP}$-hard and $\mathsf{coNP}$-hard. Is anything more known about its complexity?

# Answer
Your problem is known as the $\text{UNIQUE-SAT}$ problem which is $\mathsf{US}$-complete. The problem is in $\mathsf{D^p}$ but not known to be $\mathsf{D^p}$-hard under deterministic polynomial time reductions, where the class $\mathsf{D^p} = \\{ L\_1 \cap \overline{L\_2} \mid L\_1,L\_2 \in \mathsf{NP} \\}$.

It was shown by Papadimitriou and Yannakis \[1\] that the set of uniquely satisfiable formulas is contained in $\mathsf{D^p}$. This follows by the definition of $\mathsf{D^p}$: let $L\_1$ be SAT, and let $L\_2$ be the set of formulas with $2$ or more satisfying assignments. Regarding $\mathsf{D^p}$-hardness of $\text{UNIQUE-SAT}$, Blass and Gurevich \[2\] gave a partial answer. For one, they showed a non-relativizing proof technique would be needed to settle the question. However, Valiant and Vazirani \[3\] gave a randomized polynomial time reduction from $\text{SAT}$ showing $\mathsf{D^p}$-hardness of $\text{UNIQUE-SAT}$ under randomized polynomial time reductions .

When it is known that the problem has at most one assignment or no assignments, the promise problem is called $\text{UNAMBIGUOUS-SAT}$. The Valiant–Vazirani theorem states that if there is a polynomial time algorithm for $\text{UNAMBIGUOUS-SAT}$, then $\mathsf{NP}=\mathsf{RP}$. To prove their theorem they showed that the promise problem $\text{UNAMBIGUOUS-SAT}$ is $\mathsf{NP}$-hard under randomized polynomial time reductions. A corollary that follows from the Valiant–Vazirani theorem is that $\text{UNIQUE-SAT}$ is complete for $\mathsf{D^p}$ under randomized polynomial time reductions.

---

\[1\] Papadimitriou, Christos H., and Mihalis Yannakakis. "The complexity of facets (and some facets of complexity)." Proceedings of the fourteenth annual ACM symposium on Theory of computing. ACM, 1982.

\[2\] Blass, Andreas, and Yuri Gurevich. "On the unique satisfiability problem." Information and Control 55.1 (1982): 80-88.

\[3\] Valiant, Leslie G., and Vijay V. Vazirani. "NP is as easy as detecting unique solutions." Theoretical Computer Science 47 (1986): 85-93.
> 11 votes

---
Tags: complexity-theory, complexity-classes, satisfiability
---


# Question
Title: What does it mean when a computer runs 'faster'?
If you have two computers with only one thread, a and b.

And computer a runs twice as fast as computer b.

Does this mean that computer a and can do twice as many operations in a given time in comparison to computer b?

To increase the Hertz of a computer, i.e. the speed of the computer and the number of operations it can achieve with in a given time frame, what has to change in the architecture?

# Answer
The performance of a computer for most programs cannot be simply derived from the computer's capacity to perform operations (i.e., peak performance). As Shitikanth's answer states, the memory system and other bottlenecks can keep performance below the peak.

In addition, processor frequency is not necessarily proportional to processor performance. It is possible to increase performance without increasing frequency and to reduce performance by increasing frequency.

A substantial number of techniques can be used to increase performance.

Increasing the execution width of the processor (how many operations it can perform in parallel) can also increase performance. While increasing width tends to require reducing the frequency and programs rarely fully utilize the extra width at all times, no modern high performance processor only begins executing one instruction each cycle. (Supporting vector operations is somewhat similar, but that requires more support in software. Likewise using multiple processing cores or multiple threads within a single processing core can provide greater parallel operation while requiring more software effort.)

Speculation can also be used to increase performance. By doing work that *might* not have been necessarily, it is possible to increase the amount of parallelism available and to reduce execution delay. In current processors this includes branch prediction, out-of-order execution, and hardware prefetching. By predicting the path taken by a branch, the processor does not have to wait until the branch condition and target address are computed before fetching (and even executing) instructions after the branch.

(Increasing the accuracy of branch prediction can be very helpful for some workloads. Reducing the number of branch mispredictions reduces the amount of useless speculative work done by the processor. This can allow more electrical power/thermal budget to be applied to *useful* work. Such can also allow a deeper pipeline to have an acceptable amount of performance loss from the misprediction penalty. A deeper pipeline allows higher frequency but increases the cost of a branch misprediction--simplistically N pipeline stages of work must be discarded on a misprediction so increasing the number of pipeline stages increases the cost of mispredictions.)

Out-of-order execution allows (usually useful) work to be done while one or more instructions wait for a result from a previous instruction. Increasing the number of "future" instructions that can be considered as candidates for execution increases the processor's ability to tolerate delayed results. Out-of-order execution also allows more operations to execute in parallel by relaxing name dependencies (where an instruction reuses an address/name but does not have a value dependency).

Hardware prefetching speculates that the value prefetched will be used in the near future. Such allows the latency of memory accesses to be reduced. *Theoretically* prefetching could even be used to distribute the use of memory bandwidth through time (by scheduling useful prefetches during low demand access activity), though prefetching is generally a trade-off between latency and bandwidth use. In addition, it is often more bandwidth efficient to fetch multiple cache blocks that are within a single DRAM page. (Scheduling writebacks to memory can also increase effective bandwidth.)

Cache performance is also an area where computer performance can be improved. Placement policies (where a block is allocated within the physical cache--e.g., Non-Uniform Cache Architectures have been proposed and even implemented) and replacement policies (which block to drop from the cache when a new block is brought into the cache) can increase cache performance by reducing latency in more common or more timing critical cases.

Greater integration of the components of a system can also increase performance by reducing communication delay (and power use which is a significant limiter of computer performance).

In addition, specialized hardware can perform operations faster and/or more efficiently than more general-purpose hardware. (E.g., for decades performance-oriented processors have implemented specialized hardware to perform multiplication rather than reusing the hardware provided for addition. More recently, cryptographic and other specialized hardware has been added.)
> 9 votes

# Answer
The actual speed at which a thread runs on a real computer depends on several factors including the CPU speed, the rate at which data can be fetched from RAM/disk to registers, amount and speed of cache available and so on. Often, the other factors become the bottleneck for performance, and a two times increase in CPU power alone would usually not result in a two times increase in speed.
> 2 votes

---
Tags: terminology, performance
---


title: How do computers create 'randomness'?

text:
# Question
Title: How do computers create 'randomness'?
I have just used a function 'rand()' in my algorithm. In fact, it was arc4random() that I used. However, it got me thinking, how is randomness created in a computer system? Can anything ever truly be random when it is produced by a computer?

# Answer
Randomness is a philosophical concept (though there are several mathematical definitions as well). There are two aspect to randomness generated by a computer, unpredictability and pseudorandomness, which correspond to two different demands from a randomness source:

1. Data produced by the randomness source should be unpredictable, even in principle.
2. Data produced by the randomness source should "behave" as a truly random source.

The approach taken by computers to generate randomness is a combination of both of these flavors. Randomness is generate using a *pseudorandom number generator*, which is an algorithm designed to churned up numbers which "look random", in the sense that any program employing a randomness source will behave the same regardless of it being given a truly random source or the output of the pseudorandom number generator. ARC4 (usually known as RC4) is such an algorithm, though the first few random bits are known to be somewhat problematic.

A pseudorandom number generator (PRNG) is seeded by initial randomness, known as either a *seed* or a *key*. Sometimes we want to fix this initial randomness, for example when debugging a program which uses the PRNG. Other times, it is important that this initial randomness be unpredictable - this is the case in cryptographic applications. It used to be the case that PRNGs are seeded using the exact time-of-day as kept by the computer clock. Nowadays systems are more sophisticated, and harvest random bits from other sources such as keystrokes, CPU, internal devices and network usage, commonly known as an *entropy pool*. Therefore modern systems are capable of producing unpredictable random numbers.

If it is important to generate truly random numbers (or rather, numbers which are even less predictable), one can resort to hardware number generators, which usually measure thermal noise generated by electric components such as diodes (in the form of voltage or current fluctuations). However even this random output needs to be filtered (through a *randomness extractor*) to result in a sequence of independent fair coin flips.
> 11 votes

# Answer
Whatever Yuval Filmus said.. In addition to that if you want to learn more about Pseudorandomness, take a look at Sahil Vadhan's awesome monograph on pseudo randomness, available here

Also you can take a look at Marsaglia's KISS99, a nice algorithm (and a C program) that generates 'random' numbers. If you want a short introduction on the this, you can refer to the first chapter of *Handbook of Monte Carlo Methods*

Also for practical advice on implementing your own random number generator you can refer to this article from David Jones.

(i know you only wanted to know if it was indeed random, Yuval Filmus answered that well enough, but why stop there, go on and learn how they are actually done, the theory and math behind it, I am sure you'll have fun) :)
> 5 votes

---
Tags: randomness
---


# Question
Title: Proof of Ramsey's theorem: the number of cliques or anti cliques in a graph
Ramsey's theorem states that every graph with $n$ nodes contains either a clique or an independent set with at least $\frac{1}{2}\log\_2 n$ nodes.

I tried to look it up at a few places (including Sipser) but I could not make out a lot of sense from the proofs. I would appreciate it if someone can give me a proof (or clear intuition) on this.

# Answer
Let $R(s,t)$ be the least integer $k$ such that every graph on $k$ or more vertices contains either a $s$-clique or independent set of size $t.$

It turns out that this number is well defined (called *Ramsey number*) and the statement in your question merely amount to saying that $$R(t,t) \leq 2^{2t}.$$

A well known upper bound for Ramsey number states $$R(s,t) \leq R(s,t-1)+R(s-1,t) \leq {s+t-2 \choose t-1} \\; \\; \\; (1)$$ if $s = t$ then the above reduces to the central binomial coefficient ${2t-2 \choose t-1}$ which is always smaller than $2^{2t}$

To prove $(1)$ one can use induction on $s+t$. Leaving the induction base $R(1,t), R(s,1)$ as an exercise for you let us suppose the inequality holds for all $s+t \< k$ and let $G$ be a graph with $R(s,t-1)+R(s-1,t)$ vertices.

Let $v$ be an arbitrary vertex of $G$ and partition the remaining vertices of the graph into two groups $A,N$ - those adjacent with $v$ and those that are not adjacent with $v.$ Now since $$|A|+|N|+1 = R(s,t-1)+R(s-1,t)$$ we have either $$|N| \geq R(s,t-1) \quad \mbox{ or} \quad |A| \geq R(s-1,t).$$ Now if the first inequality is satisfied then the graph induced by $N$ either contains a $s$-clique or the graph induced by $N \cup \\{v\\}$ contains an independent set of size $t.$ In particular this implies that in this case $G$ either contains a $s$-clique or independent set of size $t.$ The second case is verified analogously and establishes the first part of the stated bound. For the last part observe that $${s+t-3 \choose s-1} + {s+t-3 \choose s-2} = {s+t-2 \choose s-1}.$$
> 6 votes

---
Tags: graphs, proof-techniques, combinatorics, discrete-mathematics
---


title: What is the name of this combinator?

text:
# Question
Title: What is the name of this combinator?
I've recently started casually reading into combinatorial logic, and I noticed that a higher-order function that I regularly use is a combinator. This combinator is actually pretty useful (you can use it to define addition on polynomial equations, for example), but I never gave it a decent name. Does anyone recognise this combinator? (ignoring differences in function currying)

```
unknown = function (h, f, g)
    function (x) h( f(x), g(x) )
}

```

In lambda calculus, the fully curried implementation would be $\lambda h. \lambda f. \lambda g. \lambda x. h (f x) (g x)$. In other words, if $M$ is this mystery combinator, then its defining equation is $M \\, h \\, f \\, g \\, x = h \\, (f \\, x) \\, (g \\, x)$.

If more information is needed, or my question is lacking key information please leave a comment and I will edit my question.

# Answer
> 4 votes
This isn't probably a standard name, but in The Implementation of Functional Programming Languages in Section 16.2.4 Simon Peyton Jones calls it `S'`. It is defined as an optimization combinator

```
S (B x y) z = S' x y z

```

The following example is from the mentioned section. Consider

```
λx_n...λx_1.PQ

```

where `P` and `Q` are complicated expression that both use all the variables. Eliminating lambda abstractions leads to quadratic increase of term sizes in `n`:

```
P Q
S P1 Q1
S (B S P2) Q2
S (B S (B (B S) P3)) Q3
S (B S (B (B S) (B (B (B S)) P4))) Q4

```

etc., where `Pi` and `Qi` are some terms. With the help of `S'` this gets only linear:

```
P Q
S P1 Q1
S' S P2 Q2
S (S' S) P3 Q3
S (S' (S' S)) P4 Q4

```

---
Tags: logic, lambda-calculus, functional-programming, combinatory-logic
---


title: Solving system of linear inequalities

text:
# Question
Title: Solving system of linear inequalities
I am trying to solve a system of inequalities in the following form: $\ x\_i - x\_j \leq w $

I know these inequalities can be solved using `Bellman-Ford` algorithm. But there is also another condition. I want to find the solution that maximizes $\ x\_n - x\_1$

As far as I know the default `Bellman-Ford` algorithm minimizes it. How do I do that?

# Answer
The obvious (but perhaps not optimal) solution would be to give it as input to a LP solver.
> 5 votes

# Answer
The textbook Bellman-Ford algorithm will indeed minimize the span of the variables: $max\_i(x\_i) - min\_i(x\_i)$. It involves adding a supernode and 0-weight edges from the supernode to every other nodes in the graph. This is probably what the op is referring to.

**To maximize $x\_n - x\_1$**, as usual, convert the difference constraints to edges. However, we will not add the super node and its 0 weight edges. Instead, just run Bellman-Ford using the node for $x\_1$ as source:

1. If negative cycle is detected, the constraints can't be satisfied.
2. The result distance $x\_n$ will maximize $x\_n - x\_1$. If $x\_n$ is infinity, that means $x\_1$ and $x\_n$ can be arbitrarily far apart.

Now let's see why it works.

**Why do the $x$s satisfy the constraints?**
Proof: By triangle inequality, same as the textbook Bellman-Ford method. I won't repeat it here.

**Why will the result distance $x\_n$ maximize $x\_n - x\_1$?**
Proof: Consider the shortest path $p = (v\_1, v\_2,...,v\_n)$ from $v\_1$ to $v\_n$, the path corresponds to the following set of constraints:

$x\_2-x\_1\leq w\[1,2\]$
$x\_3-x\_2\leq w\[2,3\]$
...
$x\_n-x\_{n-1}\leq w\[n-1,n\]$

Summing the constraints, we obtain:

$x\_n-x\_1\leq\sum\_2^n w\[i-1,i\]=w(p)$

That is, in any solution that satisfies the constraints, $x\_n - x\_1$ cannot be greater than $w(p)$, the weight of the shortest path from $v\_1$ to $v\_n$. As Bellman-Ford sets $x\_n-x\_1$ to the shortest path value, this implies $x\_n-x\_1$ is as large as possible.
> 4 votes

# Answer
Maximizing $x\_n-x\_1$ is equivalent to minimizing $x\_1-x\_n$. So, if there's a way to use Bellman-Ford to minimize $x\_1-x\_n$, you're done. I don't know whether Bellman-Ford will do that.

**Alternatively:** Another approach would be to use binary search to find the largest number $D$ such that $x\_n - x\_1 \le D$ is consistent with the rest of your system of inequalities. You can use Bellman-Ford to test whether your system, plus the constraint $x\_n - x\_1 \le D\_i$ (for a particular constant number $D\_i$), is feasible, and that tells you whether you should increase $D$ or decrease $D$. Use binary search, and with logarithmically many executions of Bellman-Ford, you'll find this $D$ -- and that's the answer to your original problem.
> 1 votes

# Answer
Your can model this problem as a graph problem: The vertices are called $v\_i$ (one $v\_i$ for every $x\_i$) and you have a directed edge $(v\_i,v\_j)$ with weight $w$ for every constraint $x\_j - x\_i \le w$.

First note that for some feasible solution you can add an offset for all $x\_i$ and get another solution which is equally good. So you can assume that $x\_1=0$. If you have a directed cycle in the graph, you problem becomes unfeasible - so you check this first. What you do next is to perform a single-source shortest path query for $v\_1$, then you set $x\_j:=d(v\_1,v\_j)$.

Why does this work? Assume that there is directed edge $(v\_a,v\_b)$, and assume $d(v\_1,v\_a)\>d(v\_1,v\_b)$. The you have $d(v\_1,v\_a) + d(v\_a,v\_b) \ge d(v\_1,v\_b)$, which gives $$d(v\_a,v\_b)=w \ge d(v\_1,v\_b) -d(v\_1,v\_a) = x\_b - x\_a.$$

Obviously, there is no better solution because you have a "chain of constraints", connecting $v\_1$ with $v\_n$, and if you would increase $x\_n$ one of these constraints would be violated.

Notice that all the weights are the same the is no need to execute the Bellman-Ford algorithm. You can do a Breadth-First-Search instead which has the better running time.
> 0 votes

---
Tags: algorithms, linear-algebra, linear-programming, shortest-path
---


# Question
Title: Find vectors with elements of finite fields that sum up to given value
Given a universe $U$ consisting of k sets of vectors with each vector $\vec{v} \in {\mathbb{F}\_{p^m}}^n $. Given also another vector $\vec{c} \in {\mathbb{F}\_{p^m}}^n$. Now decide if there is a set $X$ with $|X| = |U|$ and $X\_i \in U\_i, i = 1,2,...,k$ such that $\sum\limits\_i X\_i = \vec{c}$. If there is, output this set.

In other words, I want to find a combination of one element out of each set that sums up to the given vector, given that the vectors' entries can only be the results of modulo operation with a given integer. I hope the problem becomes clear.

I want to find an efficient algorithm to solve this problem. It seems to me that it is NP-complete, but I find no other NP-complete problem that I can reduce. If there is one, existing algorithm (if any) to that other problem could be used for this problem.
I looked at integer programming, but I did not find anything with respect to finite fields.

Any ideas?

# Answer
> 2 votes
It looks like subset-sum problem. It should be possible to adapt the pseudopolynomial algorithm.

# Answer
> 0 votes
If $p=2$ and $k\ge mn$, you can solve this efficiently (in polynomial time) using linear algebra.

Here's the algorithm. Keep only two elements in each set $U\_i$, and throw all the rest away, so that $|U\_i|=2$ for all $i$. Now if $U\_i=\\{a\_0,a\_1\\}$, we can write $a\_b = a\_1 + b (a\_0-a\_1)$ (where $b\in \\{0,1\\}$), and the latter expression is linear in $b$. So, we can write $\sum\_i X\_i$ as $\sum\_i a\_{i,1} + b\_i (a\_{i,0} - a\_{i,1})$, which is a linear expression in the $k$-vector $b=(b\_1,\dots,b\_k)$. Let $M$ be the $mn \times k$ matrix over $\mathbb{F}\_{2}$ such that $\sum\_i X\_i = M b$ (expressing each element of $\mathbb{F}\_{2^m}$ as a $m$-vector over $\mathbb{F}\_2$ using some standard basis).

Now our goal is to find a solution to $M b = c$, where $M,c$ are given and our goal is to find $b$. Since this represents $mn$ equations in $k$ unknowns and $k\ge mn$, with high probability $M$ is invertible and some solution exists, so Gaussian elimination suffices to find a solution. The solution to $Mb=c$ immediately yields a solution to your original problem. (If $M$ is not invertible and $Mb=c$ has no solution, go back to the beginning and pick a different random two elements of each $U\_i$ to keep, and try again. We'll only need to try a constant number of times, on average.)

---
Tags: algorithms, combinatorics, discrete-mathematics
---


title: Grammar to Language

text:
# Question
Title: Grammar to Language
Having:

$\qquad \begin{align} S &\to aT \\ T &\to a \mid UTV \\ U &\to ab \mid ba \\ V &\to ac \mid ca \end{align}$

What language would be generated by this?

How can I obtain an $LL(1)$ grammar using factorisation?

I've tried a number of combinations but do not get how to represent the UTV part:

Something like a|ab|ba|ac|ca|aa|a(ab|ba)^n a(ac|ca)^n

# Answer
Hint: $U$ captures the regular expression $ab+ba$, $V$ captures $ac+ca$. The solution to an equation of the form $W \to Y | XWZ$ is $W = X^nYZ^n$.
> 2 votes

# Answer
The problem is obviously with the T non-terminal because of the first set conflict, so let's work on it:

```
T -> a | UTV

```

Replace U:

```
T -> a | abTV | baTV

```

Factor:

```
T -> aP | baTV
P -> bTV | Eps

```

U has now become unreachable, so the LL(1) outcome:

```
S -> aT
T -> aP | baTV
P -> bTV | Eps
V -> ac | ca

```
> 0 votes

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


# Question
Title: Trying to understand a token file for lexical analysis
I am reading this article about compiler. I am facing some problem in understanding the content of the token file. Specifically, what is the meaning of the following lines:

```
    [ \t\n]                 ;
    [a-zA-Z_][a-zA-Z0-9_]*  SAVE_TOKEN; return TIDENTIFIER;
    [0-9]+\.[0-9]*          SAVE_TOKEN; return TDOUBLE;
    [0-9]+                  SAVE_TOKEN; return TINTEGER;

```

What is * and + at the end of the expressions ?

Thanks in advance for explaining me.

# Answer
> 2 votes
`*` means that any number (including zero) of preceding expression can occur

`+` means that at least one instance of preceding expression must occur

# Answer
> 1 votes
What you see there is a common regexp syntax.

* `[ \t\n]` matches any character that is a space, a tab or a new line.
* `[a-zA-Z_][a-zA-Z0-9_]*` matches any string of length at least one consisting of roman letters, digits and underscore that does not start with a digit.
* `[0-9]+\.[0-9]*` matches any number with at least one digit before the (mandatory) period.
* `[0-9]+` matches any number with at least one digit.
* `SAVE_TOKEN; return X` likely tells the compiler generator that when the preceeding expression matches, create a token of type `X` and assign it the matching string.

The input string is processed from left to right and whenever one of the expressions matches the current buffer, the directive associated with the expression is executed and the buffer emptied. Note that there is no `SAVE_TOKEN` directive for the whitespace rule, so all whitespaces are removed. All other matches generate appropriate tokens that can later be used in a (context-free) grammar to parse the program.

Note that one (common, but arbitrary) convention is that rules take precedence from top to bottom. This does not take effect here as the expressions are mutually exclusive.

---
Tags: terminology, formal-grammars, compilers, lexical-analysis
---


# Question
Title: Anomaly/outlier detection using fuzzy clustering
I understand that fuzzy clustering using FCM produces a membership matrix for the set of data points we feed to it. What characteristics will an anomalous cluster produced during this method have? (Considering I only have unlabelled data)

# Answer
As far as I know there is no unique definition for what is an outlier/anomaly. Therefore you'll have to decide by yourself what the characteristics of outlying data points in your data set are. This could be for example: distance to the cluster center (threshold), local neighbourhood (a data point that has no/few data points in its neighgbourhood might be an outlier) or statistical characteristics (an outlier doesn't 'fit' to the distribution of a cluster, e.g. Grubbs' method). You can find a survey of outlier detection methods in A Survey of Outlier Detection Methodologies by Hodge and Austin (2004).
> 3 votes

---
Tags: machine-learning, data-mining
---


title: Formal language without grammar

text:
# Question
Title: Formal language without grammar
Definitions:

* *Alphabet* $Σ$: finite, non-empty set
* *Language*: subset of $Σ^\*$
* *Grammar*: Unrestricted grammar (Chomsky Type 0)
* *Language of a grammar*: all words that can be produced by applying $P$ multiple times, starting from $S$

Grammars are finite, therefore there are only countable infinite of them. But there are uncountably infinite many languages. Each grammar can only describe one language. Therefore, there are **languages without grammars**.

Can you give an **example** for such a language without grammar?

I searched the internet, but strangely, I could not even find the question in context of formal language.

# Answer
> 6 votes
I assume that by "grammar" you mean type-0 grammars. One can probably extend those to capture more languages.

Type-0 grammars are equivalent to Turing machines in expressive power. So, in order to show that a given language does not have a grammar, we can proceed as follows with suitable $L$:

> Assume there was a grammar for $L$. Then, we could semi-decide the word problem of $L$. That contradicts the known fact that $L$ is not recursively-enumerable.

Note the *semi* here; assuming a grammar does not give us decidability, so the halting problem is not a suitable candidate -- we need a problem/language that is not even semi-decidable/recursively enumerable. From your computability background you should know that the *complement* of the (special) halting language, namely

$\qquad \overline{H} = \\{ \langle M \rangle \mid M \text{ loops on } \langle M \rangle \\}$,

is not semi-decidable. Thus, by the reduction outlined above, there is no (Chomsky) grammar for $\overline{H}$.

# Answer
> 3 votes
While the halting problem is a perfectly valid example of a language that a CFG can not capture, there is a huge middle ground of languages that are not context free but recursive (that is they can be solved by a Turing machine but can not be expressed by a CFG).

For example, you can use the pumping lemma for CFGs to show that the language $ L = \\{ a^i b^i c^i| i \in \mathbb N \\} $ is not context free.

# Answer
> 2 votes
Finally, I found an example: The non-halting programs. No Turing machine can determine that a program will not halt.

This is also why the type-0 languages are not closed under complementation.

---
Tags: formal-languages, formal-grammars
---


# Question
Title: What is the purpose of Bayesian networks?
I have seen a lot of explanations of what Bayesian networks are, but I simply cannot wrap my head around their use in code. So here is my three part question.

1. Am I right in my definition of Bayes nets? Bayesian networks are a way to (visually) portray how variables/events are linked and how they will affect each other. Probabilities can be added to each node to give you a greater sense of what will happen. In conjunction with an acting AI, Bayes nets are used to predict the AI's actions and inform what it should be doing, i.e. giving minimax a better prediction.
2. Can you give a pseudo code representation of a Bayes net?
3. Let's get a little more specific. I have a creature simulator, the creature has a home where he sleeps and, there are patches of grass where he eats. There are other creatures out there that he wants to avoid because they will fight him. So his action -\> reaction set is:

{hungry-\>find food -\> eat food
tiered -\> go to shelter -\> sleep
in danger -\> avoid other creature
under attack -\> run to shelter}

I am trying to express this as an mdp so that it will learn what actions are best when; and what are the best spots (most prosperous & least dangerous) on the map.

How, if at all, am I supposed to use a Bayes net? If the situation requires probabilities feel free to add your own, pseudo code also appreciated.

# Answer
> 1 votes
I am trying to state a possible bayes net: What the creature wants to know is what to do next. So the root node is 'ACTION'. Possible actions are (let's say field 1 = home): \[move to field 1, move to field 2, ... move to field n, sleep, eat\] or \[go north, go south, go east, go west, eat, sleep\]. 'ACTION' depends on the creature's 'STATE', that can be \[afraid(by another creature), under attack, hungry, tired\]. 'STATE' depends on 'ANOTHER CREATURE' and 'FOOD AVAILABLE'. The latter two nodes can be \[yes,no\] and both depend on the current 'FIELD', \[field 1, ..., field n\].

```
'FIELD' -> 'ANOTHER CREATURE'

'FIELD' -> 'FOOD AVAILABLE'

'ANOTHER CRATURE' -> 'STATE'

'FOOD AVAILABLE' -> 'STATE'

'FIELD' -> 'ACTION'

'STATE' -> 'ACTION'

```

Each node has a table containing the probabilities p(value|value of dependency1, value dependency2,...). For example the 'ACTION' table holds the probabilities for each combination of p(action to take | value of 'STATE', value of 'FIELD').

I think suitable methods to estimate the model's probabilities are Q-learning or SARSA-learning.

---
Tags: terminology, machine-learning, artificial-intelligence, probability-theory
---


# Question
Title: In general terms, how could the Thompson Hack be implemented in Microcode?
In his lecture *Reflections on Trusting Trust*, Ken Thompson describes a virus that infects a compiler; the infected compiler installs backdoors into programs, but the key part is that the infected compiler also infects all compilers it compiles.

K. Thompson notes that if this was implemented at the Microcode level, it would be almost impossible to stop.

My question is this; in general terms (i.e. I'm not going to ask for details on how to create the most insidious trojan that has ever existed) how can you write microcode that would inject Thompson's trojan into every program compiled on a computer with that microcode.

As far as I can tell, the core of this question (i.e. the most important part, theoretically speaking) is:

> Can the code implementing machine code (such as microcode) detect when the machine code it is implementing is a compiler that is compiling (in order to inject trojans into the compiled program), and if so, how?

# Answer
> 1 votes
In general, it certainly can not; this follows from Rice's theorem. That is, if you want to restrict the set of functions that are compilers in a meaningful way (one might also say that *every* function is a compiler).

In practice, you can of course inspect the sources of popular compilers and include heuristics in your malicious code that detect gcc, javac or any other *known* compiler.

# Answer
> 1 votes
> how can you write microcode that would inject Thompson's trojan into every program compiled on a computer with that microcode

A way to look at it is that the microcode is an interpreter for the public machine code. It is in fact the true machine code (well some machine have a two level microcode ;-) and in theory it can do whatever it want, included inspecting the executed code and replacing it with hacked up version. In practice, there are severe limitation to what you can do in microcode. Three aspects:

* space for the microcode program is usually very limited; I'm not sure there would be enough place there to put the trojan in place (especially that the trojan would have to do more things than in Thompson's case -- you don't know the name of the function you are executing --, especially if you want to avoid the next point)
* performance would probably be impacted and make the insertion of the trojan visible, people making benchmark will ask questions
* in current processors most instructions are executed directly by the hardware without going to the microcode; I'm not sure there is enough hooks to implement such trojan.

(For the conspiracy minded, obviously if the processor is designed to make such trojan possible, all those points are solvable).

---
Tags: computer-architecture, compilers, security
---


# Question
Title: Show that A** subset of A*, where A is a regular language
I do not understand the proof for this. I know that every word in $(A^\*)^\*$ is made up of words from $A^\*$, and that this is made up from words in $A$. But how does this help with showing that $(A^\*)^\*$ is a subset of $A^\*$.

# Answer
> 4 votes
Knowing that $A$ is regular is not relevant.

**Hint**. Just replace "made up of words of $A^\*$" by "is a concatenation of words of $A^\*$" in your sentence and you will have the answer.

# Answer
> 2 votes
A concatenation of words of $A^\*$ gives a word which is in $A^\*$, because of the very definition of $A^\*$. This gives the result.

Moreover, one can prove that $^\*$ is a closure operator, which includes this property.

---
Tags: formal-languages, regular-languages
---


# Question
Title: Classifying infinite languages of encodings of halting Turing machines
Given this question:

> $L$ is an infinite language of encoded Turing machines who always halt.
>
> 1. $L$ might be decidable
> 2. $L$ might be in RE but not in R
> 3. both 1. and 2. are correct

I know the solution to this question is 3., but I seem to lack the understanding on how am I suppose to get to that solution. Could you explain how should I approach this kind of questions? Am I supposed to start drawing TMs? Why is the answer is C? What's the indication of that?

It would help me a lot if you could explain to me your thought process when facing this kind of problem.

# Answer
> 2 votes
There are certainly examples for all "levels":

1. It is easy to give an infinite set of encodings that is decidable.

> Consider all programs of the form `f(x) = x + i` -- definitely an infinite and decidable set.
2. Classic examples (think Halting problem) are semi-decidable but not decidable.

> $L = \\{ \langle M \rangle \mid f\_M(\langle M \rangle) = 1\\}$
3. Other classic examples (think complement of Halting problem) are not semi-decidable.

> $L = \\{ \langle M \rangle \mid f\_M(\langle M \rangle)\uparrow \\}$

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


# Question
Title: What data structure would efficiently store integer ranges?
I need to keep a collection on integers in the range 0 to 65535 so that I can quickly do the following:

* Insert a new integer
* Insert a range of contiguous integers
* Remove an integer
* Remove all integers below an integer
* Test if an integer is present

My data has the property that it often contains runs of integers in the collection. For example, the collection might at one point in time be:

```
{ 121, 122, 123, 124, 3201, 3202, 5897, 8912, 8913, 8914, 18823, 18824, 40891 }

```

The simplest approach is just to use a balanced binary tree like the C++ std::set, however, using that, I am not leveraging the fact that I often have runs of numbers. Perhaps it would be better to store a collection of ranges? But that means a range needs to be able to be broken up if an integer in its middle is removed, or joined together if the space between two ranges in filled in.

Are there any existing data structures that would be well suited for this problem?

# Answer
> 9 votes
I suggest you use a binary search tree, augmented so that leaves can contain an interval (a run of consecutive integers). Maintain the invariant that the intervals do not overlap and are in order (following the search tree invariant). (This can be considered a special case of an interval tree or a segment tree, for the special case where the intervals do not overlap.)

This data structure you can support all of your operations in $O(\lg n)$ time, where $n$ is the number of intervals. Since we're guaranteed $n\le 65535$, I would expect this to be quite efficient. (In particular, yes, you can split an interval into two pieces or merge two adjacent intervals into a single interval in $O(\lg n)$ time.)

# Answer
> 5 votes
First of all, your question is very poorly worded, if for no other reason because "quickly" doesn't mean much. You'll need to provide some metric of what "quick" means.

Beyond that, when trying to come up with a design for a problem you need to first understand the problem very well and ask a lot of *additional* questions. Relevant questions in this case would seem to be (in no particular order):

* Must all these operations be equally quick, or are some more important than others?
* Are there other considerations?
* Is memory a concern at all?
* Is the ability to perform insertions, removals and lookups from multiple threads a concern?
* Is the workload mostly focused on inserting? Removing? Looking up?

Secondly, if your problem domain really is $\[0, 65535\]$ then this discussion seems just silly. Is a smart, fancy algorithm *really* necessary? Especially when a simple array is an excellent option, covering the single integer operations in constant time, the range operations in linear time and costs linear space?

For a little bit more work, you could save on space if that's a concern, at the expense of speed by storing the data as bits in 8192 integers. Although conceptually the single integer operations would still be constant time and ranged integer operations would still be linear time, they would be slower.

So, if this is really your problem, I'd say use an array and move on to other, more important things with the code.

If this isn't really your problem and there are other considerations you haven't relayed (e.g. perhaps the domain isn't really $\[0, 65535\]$ and you were trying to simplify the problem you were asking about) then you'll need to ask your question again, this time telling us the *actual* problem.

# Answer
> 3 votes
You might consider an *Integer data structure* such as a Van Emde Boas tree. An Integer data structure works on a fixed universe $\mathcal{U}=\\{0,\ldots,u-1\\}$. Some of the operations you have mentioned can be implemented very efficiently. In particular, inserting, deleting and requesting a single element runs in $O(\log \log u)$. The other operations (bulk insert/delete) might be more costly, however, using bittricks on the Van Emde Boas tree you should be able to get a speed-up by a factor of about the the word size of your system.

Depending on the structure of your data there might be many clever alternatives how to store your data.

---
Tags: data-structures, efficiency, search-trees, integers
---


# Question
Title: Good way to describe co-RE (co-recursively enumerable)?
I get that R is a set of languages that are decidable by a Turing Machines

And that RE is a set of languages that a each language can be recognized by a TM, that is the machine will halt when given a word from that language and loop otherwise.

But I can't wrap my head around co-RE. Is there a good way to describe it? A good example to convey what it really means?

# Answer
> 16 votes
The class ${\sf coRE}$ contains all languages whose complement is in ${\sf RE}$. Put differently:

* A language $L$ is in ${\sf RE}$ if there exists a Turing machine that can check if a requested word $w$ is contained in $L$ for every word $w\in L$. The machine always tells the truth but it may cycle on inputs $w\not\in L$.
* A language $L$ is in ${\sf coRE}$ if there exists a Turing machine that can check if a requested word $w$ is **not** contained in $L$ for every word $w\not\in L$. The machine always tells the truth but it may cycle on inputs $w\in L$.

An example: The language $\\{ \langle M,w \rangle \mid \text{$M$ cycles on input $w$}\\}$ is in ${\sf coRE}$. Just take a Turing machine that simulates $M$ on $w$ and rejects, whenever the simulation stops.

# Answer
> 11 votes
The definitions are complementary, literally.

* $\mathsf{RE}$ means that there is an algorithm that can (always) answer "Yes" (correctly) after finite time but maybe not "No".
* $\mathsf{coRE}$ means that there is an algorithm that can (always) answer "No" (correctly) after finite time but maybe not "Yes".

You can think of $\mathsf{coRE}$ as recursively enumerating the complement (hence the name). From this you also see that $\mathsf{R} = \mathsf{RE} \cap \mathsf{coRE}$.

# Answer
> 5 votes
It means that the complement of the language is recursively enumerable. In other words, while you can't enumerate the strings that are in the set, you can list all the languages that aren't in the set.

The language of encodings of Turing machines that halt on an empty tape is recursively enumerable; we could write a Turing machine that eventually prints every Turing-machine encoding that halts. For Turing machines that don't halt, however, we're out of luck; we don't have a way to know that a given encoding represents a Turing machine that will run forever. The set of encodings of Turing machines that don't halt is not recursively enumerable.

However, the set of encodings of Turing machines that don't halt when given the empty tape as input is a co-recursively enumerable set. We can write a Turing machine which eventually prints out every encoding which fails to belong to the desired set. Indeed, this is the same Turing machine that we discuss in the previous paragraph. Indeed, if $L \in {\sf RE}$, then $L^C \in {\sf coRE}$, and vice versa.

To see how it all fits together, if we have a language that is both ${\sf RE}$ and ${\sf coRE}$, the language is also ${\sf R}$, and vice versa. Suppose the language is is both ${\sf RE}$ and ${\sf coRE}$. Then we have Turing machines $M\_{{\sf RE}}$ and $M\_{{\sf coRE}}$ which enumerate all words belonging to, and not belonging to, the language, respectively. To positively determine whether a given word is or isn't in the language, then, we can simply run both machines at the same time, and wait for one of the machines to list our query. If our language is ${\sf R}$, we can make a machine to enumerate it or its complement by checking all Turing-machine encodings, and either skipping or emitting each one depending on whether or not it's in the language (which we can definitively answer, based on the assumption that the language is recursive, meaning we have a Turing machine to decide it).

The example of "encodings of Turing machines that don't halt" is a little contrived, but there's no reason that there couldn't be more natural sounding languages that are ${\sf coRE}$ by themselves.

---
Tags: terminology, computability
---


# Question
Title: Looking for cheat sheet to J.C. Reynolds symbols
Most specifically, his use of small epsilon introduced at the end of section 1 of "Types, Abstraction and Parametric Polymorphism" is throwing me, but in general I would like references to symbols in the Type and Logical Relations literature.

# Answer
> 2 votes
You aren't going to find a list of all notations ever used. Apart from a few standard notations, each paper will define the notation that it uses.

This paper is from the dark ages of typewriter typesetting, so the typographic quality is subpar. The character `ε` stands for $\in$, which is the standard mathematical notation for set membership.

---
Tags: terminology, reference-request, type-theory, abstract-data-types
---


# Question
Title: Why is this language involving reversal regular?
For a language to be regular it needs to be recognized by DFA/NFA.

Let $L = \\{ xy^rzyx^r \mid |x| , |y|, |z| \ge 1 \\}$ over the alphabet $\\{0,1\\}$.

$x^r$ means the reverse of $x$.

A DFA has no memory, so how can it handle the reverse check?

# Answer
> 9 votes
Notice that big unconstrained $z$ in the middle. You don't need the DFA to check anything if there is a way to decompose the word that dumps almost everything into $z$.

In particular, any word of the form $a b z b a$ where $a$ and $b$ are letters and $z$ is an arbitrary non-empty word is in $L$ (with words of length 1 for $x$ and $y$).

Conversely, suppose that you have a word $w \in L$: it can be broken down as $x y^r z y x^r$ with $|x| \ge 1$ and $|y| \ge 1$. If $|x| \ge 2$ then write $x = a b x'$: we have $w = a b x' y^r z y x'^r b a = a b z' b a$ where $z' = x' y^r z y x'^r$. If $|x| = 1$ then write $y = b y'$ and do a similar decomposition.

Conclusion: another way of describing $L$ is $L = \\{a b z b a \mid a,b \in \\{0,1\\}, z \in \\{0,1\\}^{+}\\}$. This language is regular; a regular expression that matches it is `00..*11|01..*10|10..*01|11..*11`. Intuitively, an autotomaton recognizing $L$ only needs a finite amount of memory, because it only needs to memorize the first two letters.

# Answer
> 4 votes
To complete Gilles's answer, another way to find the result : notice that if you set $y' = y^r$, you obtain (since $y = y'^r$) :

$ L = \\{ xy'zxy'^rx^r : |x|,|y'|,|z| \geq 1 \\}$

Thus setting $t = xy'$, since $t^r = y'^rx^r$, we end up with :

$ L = \\{ tzt^r : |z| \geq 1, |t| \geq 2 \\} $

And, as Gilles said, you can keep only two letters in $t$ and put all the remaining stuff in $z$, to finally obtain the same result :

$ L = \\{ tzt^r : |z| \geq 1, |t| = 2 \\} $

---
Tags: formal-languages, regular-languages
---


title: What's Big O of $\log(n+7)^{\log(n)}$?

text:
# Question
Title: What's Big O of $\log(n+7)^{\log(n)}$?
As part of my continual improvement plans, I'm reviewing algorithm analysis and I've hit a roadblock. I cannot figure out how to determine the Big O complexity of $\log(n+7)^{\log(n)}$. I've spent the last few days rolling this over in my head and I still haven't made any progress in solving it. Could someone tell me what the Big O of this algorithm is, and explain how you solved it?

# Answer
If you meant what $\mathcal{O}((\log (n+7))^{\log (n)})$ is (so the power applies to the logarithm itself, not its argument), then we simplify that to $\mathcal{O}((\log (n))^{\log (n)})$; as per a suggestion by Saeed Amiri, here a proof for this equality:

Since $(\log (n))^{\log (n)}) \leq (\log (n+7))^{\log (n)})$ for all $n$, we have $\mathcal{O}((\log (n))^{\log (n)}) \subseteq \mathcal{O}((\log (n+7))^{\log (n)})$.

For the other direction, consider

$\qquad \begin{align} (\log (2n))^{\log (n)} &\leq c(\log (n))^{\log(n)} &\iff \\ \frac{\log(2n)}{\log(n)} &\leq \sqrt\[\log(n)\]{c} &\iff \\ 1+\frac{\log(2)}{\log(n)} &\leq \sqrt\[\log(n)\]{c} &\iff \\ \left(1+\frac{\log(2)}{\log(n)}\right)^{\log(n)} &\leq c \end{align} $

What we now notice is that $\log n$ is a non-integer bound, so we can't directly expand to a polynomial here. We could if we knew that

$\left(1+\frac{\log(2)}{\log(n)}\right)^{\log(n)} \leq \left(1+\frac{\log(2)}{\lceil\log(n)\rceil}\right)^{\lceil\log(n)\rceil}$

Therefore, a small proof of the monotonicity of that function:

$\frac{d}{dx}\left(1+\frac{\log(2)}{\log(x)}\right)^{\log(x)} = \frac{\left(\frac{\log (2x)}{\log (x)}\right)^{\log (x)}\left(\log (2x)\log\left(\frac{\log (2x)}{\log (x)}\right) - \log (2)\right)}{x \log (2x)} \geq \frac{\log (2x)\log\left(\frac{\log (2x)}{\log (x)}\right) - \log (2)}{x (\log (x))^{\log (x)}} \> 0$

for all $x \> x\_0$ for some $x\_0$ \[specifically, for $x\_0 = 2$; check the link to math in the comment section\].

Since we now know that the function is monotonically nondecreasing for all $n \> 2$, we can choose our $c$ slightly differently:

\begin{align} \left(1+\frac{\log(2)}{\log(n)}\right)^{\log(n)} \leq \left(1+\frac{\log(2)}{\lceil\log(n)\rceil}\right)^{\lceil\log(n)\rceil} &\leq c &\overset{\text{rewriting the polynomial}}{\iff} \\ \sum\_{i=0}^{\lceil\log(n)\rceil}\binom{\lceil\log(n)\rceil}{i}\left(\frac{\log(2)}{\lceil\log(n)\rceil}\right)^i &\leq c \end{align}

Now we use the inequality $\binom{n}{k} \leq \frac{n^k}{k!}$ and see that \begin{align} \sum\_{i=0}^{\lceil\log(n)\rceil}\binom{\lceil\log(n)\rceil}{i}\left(\frac{\log(2)}{\lceil\log(n)\rceil}\right)^i &\leq \sum\_{i=0}^{\lceil\log(n)\rceil}\frac{(\lceil\log(n)\rceil)^i}{i!}\left(\frac{\log(2)}{\lceil\log(n)\rceil}\right)^i \\ &= \sum\_{i=0}^{\lceil\log(n)\rceil}\frac{(\log(2))^i}{i!} \\ &\leq \sum\_{i=0}^{\infty}\frac{(\log(2))^i}{i!} \\ &= e^{\log(2)} \end{align}

So we know that $\mathcal{O}((\log (n+7))^{\log (n)}) \subseteq \mathcal{O}((\log (n))^{\log (n)})$ since we can choose a finite $c$ in the above inequation.

---

If we try to express $(\log (n))^{\log (n)}$ as a power of $n$ now, we get

\begin{align} n^{f(n)} &= (\log (n))^{\log(n)} &\iff \\ \log(n^{f(n)}) &= \log ((\log (n))^{\log(n)}) &\iff \\ f(n) \cdot \log(n) &= \log(n) \cdot \log (\log (n)) &\iff \\ f(n) &= \log (\log (n)) \end{align}

, and so we get $\mathcal{O}((\log (n))^{\log (n)}) = \mathcal{O}(n^{\log(\log(n))})$, if that is any improvement.

(Credit where it's due: I copied this way of expressing our function as a power of $n$ from here, so google can help with this stuff, sometimes.)

---

Now where does this place $\mathcal{O}((\log n)^{\log n})$ in terms of complexity? We know that $\forall c \in \mathbb{R}: \lim\_{n \to \infty} \frac{c}{\log \log n} = 0$, which means that $n^c \in \mathcal{o}((\log n)^{\log n}) = \mathcal{o}(n^{\log \log n})$; the small $\mathcal{o}$ is intended here, it means that $n^c$ grows strictly slower than $n^{\log \log n}$. \[A small remark about that at the end of all this; if this is not relevant to your needs or confuses you, you can - apart from those in the remark at the end itself - replace every $\mathcal{o}$ with $\mathcal{O}$, all statements will still be true.\]

On the other hand, we have for any constant base $b \> 1$:

\begin{align} n^{\log \log n} &\leq b^n &\iff \\ (\log \log n) * (\log n) &\leq n * \log b \end{align}

This tells us that instead of $n^{\log \log n}$ and $b^n$, we can equivalently compare $(\log \log n) * (\log n)$ and $n$ by just ignoring the constant (!) factor $\log b$. Using the limit rules for asymptotic notation as well as l'Hôpital's rule, we get

\begin{align} \lim\_{n \to \infty} \frac{(\log \log n) * (\log n)}{n} &\leq \lim\_{n \to \infty} \frac{(\log n) * (\log n)}{n} \\ &\overset{\text{l'Hôpital}}{=} \lim\_{n \to \infty} \frac{2\*\log n}{n} \\ &\overset{\text{l'Hôpital}}{=} \lim\_{n \to \infty} \frac{2}{n} = 0 \end{align}

Therefore we know $(\log n)^{\log n} = n^{\log \log n} \in \mathcal{o}(b^n)$ for any base $b\>1$ of the exponential, meaning it grows strictly slower than any exponential function with constant base that we would be interested in. (What I mean by this is that in the analysis of the complexity of algorithms, we don't care about exponentials with negative bases because those aren't even real functions, much less functions over the naturals, or exponentials with bases between $0$ and $1$ because those all converge to $0$.)

In summary, we now know that in terms of complexity:

\begin{align} \mathcal{O}(n^c) \subsetneq \mathcal{O}((\log n)^{\log n}) = \mathcal{O}(n^{\log \log n}) \subsetneq \mathcal{O}(b^n) \end{align}

for any constants $c \> 0$ and $b \> 1$. What you have is a function strictly between polynomial and exponential growth.

---

Now the remark about Big-Oh and small-oh: $\mathcal{o}$ is a stronger statement than $\mathcal{O}$, because if $f(n) \in \mathcal{o}(g(n))$ then we know $g(n)$ grows strictly (meaning by a non-constant factor) faster than $f(n)$, but if $f(n) \in \mathcal{O}(g(n))$ we only know that $g(n)$ grows at least as fast as $f(n)$, so there may only be a constant factor. For example, $n \in \mathcal{o}(n \log n)$ and $n \in \mathcal{O}(n)$, but $n \not \in \mathcal{o}(n)$.
> 10 votes

# Answer
*I assume that the power is applied to the argument.*

Following the lines of G.Bach's answer you can bound your expression as follows. For a sufficiently large $n$ we have $$\log(n+7)^{\log(n)}\<\log(2n)^{\log n}=\log(2^{\log n }\cdot n^{\log n }) =\log 2^{\log n }+\log n ^{\log n}\<2 \log n ^{\log n}.$$

This can be simplified as follows

$$\log n ^{\log n }=\log n \log n = \log^2n.$$

So a reasonable upper bound is $O(\log^2 n)$.
> 3 votes

---
Tags: algorithms, algorithm-analysis, asymptotics
---


title: E-R diagram and relationships

text:
# Question
Title: E-R diagram and relationships
Suppose we have two entities $A$ and $B$ and some relationship between them. If there is an $M:N$ relationship between them (i.e. an $M$ on the line connecting $A$ to the relationship and an $N$ connecting the relationship to $B$), how do we read this? Would it be the following: A single instance of $A$ is related to $N$ of $B$ and a single instance of $B$ is related to $M$ of $A$?

# Answer
> 2 votes
You got it right, I think.

* $1 : N$ means: Any $A$ may be connected with any number of $B$, but every $B$ is connected to (exactly) one $A$.

*Example:* (Biological) Mothers and children.
* $M : 1$ means the same, just reversed.
* $M : N$ means that any $A$ may be connected with any number of $B$ and vice versa.

*Example:* Teachers and students.

---
Tags: terminology, databases
---


title: Why is this language regular?

text:
# Question
Title: Why is this language regular?
If you could include your thought process in determining why it's regular it would help me a lot.

* $L\_1 = (0^\*(10)^\*11)$
* $L\_2 = \\{ \langle M \rangle \mid M \text{ is a Turing machine that halts on all inputs from }L\_1 \\}$
* $L\_3 = \\{ x \in \\{0,1\\}^\* \mid \exists y \in L\_2. xy \in L\_1 \\}$

Why is $L\_3$ regular? It's a set of strings, I need to determine if there's a DFA that can accept it. Do I even care about $L\_2$ and $L\_1$ in this case?

# Answer
**Short answer**. The language $L\_1$ is clearly regular. Further, $L\_3 = L\_1L\_2^{-1}$ is a quotient of $L\_1$ and hence it is regular since the quotient of a regular language by any language (regular or not) is regular. So you don't care about $L\_2$, but you do care about $L\_1$.

**More details**. Let $L$ and $R$ be languages. Then $LR^{-1} = \\{ u \in A^\* \mid ur \in L \text{ for some }r \in R\\}$. Therefore $LR^{-1} = \bigcup\_{r \in R} Lr^{-1}$. If $L$ is regular, there are only finitely many languages of the form $Lr^{-1}$, each of which is regular (this is the dual form of Nerode's lemma) and hence $LR^{-1}$ is a finite union of regular languages and thus it is regular.
> 5 votes

# Answer
Consider these regular languages: $$ R\_1 = \begin{cases} 0^\* & \exists\_{m,n \in \mathbb{N}} 0^m(10)^n11 \in L\_2 \\ \emptyset & \text{otherwise} \end{cases} \\ R\_2 = \begin{cases} 0^\*(10)^\* & \exists\_{n \in \mathbb{N}}(10)^n11 \in L\_2 \\ \emptyset & \text{otherwise} \end{cases} \\ R\_3 = \begin{cases} 0^\*(10)^\*1 & 011 \in L\_2 \\ \emptyset & \text{otherwise} \end{cases} \\ R\_4 = \begin{cases} 0^\*(10)^\* & 11 \in L\_2 \\ \emptyset & \text{otherwise} \end{cases} \\ R\_5 = \begin{cases} 0^\*(10)^\*1 & 1 \in L\_2 \\ \emptyset & \text{otherwise} \end{cases} $$

Well, each of $R\_i$ are regular and it is obvious that $L\_3 = R\_1 \cup R\_2 \cup R\_3 \cup R\_4 \cup R\_5$. Thus $L\_3$ is also regular.

Note that the exact value of $R\_i$ does not need to be known, and indeed will not be unless we have sufficient information about $L\_2$.
> 2 votes

# Answer
Notice that $xy \in L\_1$ implies that $x$ is prefix of a word in $L\_1$. But all $L\_1$'s prefixes are of the form $A = 0^\*(10)^\*$ or $B = 0^\*(10)^\*1$.

Then, because you don't give any constraint on the encoding of Turing Machine, I can set that $\langle M \rangle = 1, \langle M'\rangle = 11$, where $M$ and $M'$ are Turing machines that stop on every input.

Hence, $L\_3$ is exactly $A \cup B$, and is thus regular.

But again, this is true only if you can chose the encoding of Turing Machine. Otherwise, it would depend on the way Turing Machine are encoded.
> 1 votes

---
Tags: formal-languages, computability, regular-languages
---


# Question
Title: Access to publicly available project with all the artefacts (files) created during the development
Does anyone know where I could get an access to a project that contains all the artefacts (documents) that were created during the development? So I would like to get all the word, pdf, power designer, etc. files as well as all the source code. If possible, I would prefer that all this files are stored in some of the software reporitories.

# Answer
Your best bet is to go with major open source projects (Apache, Open Office, Mozilla, MySql, perhaps Linux). Since these are done by large online communities all communication occurs online through bug databases and forums or mailing lists (which are usually archived). If they do code reviews they may be archived with a tool like Review Board or will be done through the official archived mailing lists. It seems unlikely that you will find a non-open source project/company willing to provide such detailed information.

An example of an academic software engineering study which quite successfully used open source artifacts is:

> Shan Lu, Soyeon Park, Eunsoo Seo, Yuanyuan Zhou: Learning from mistakes: a comprehensive study on real world concurrency bug characteristics. (ASPLOS-XIII):329-339, 2008.

Prof. Y.Y. Zhou's research team at UCSD has done a variety of other studies mining open source bug databases to understand bug or failure characteristics. http://opera.ucsd.edu/pub\_system\_depend.html#characteristic-study
> 4 votes

---
Tags: reference-request, software-engineering, data-sets
---


# Question
Title: What learning algorithm is appropriate for predicting one time-series from another?
I have eye-tracking data on two subjects -- a teacher, and a student. It's in the form (x, y, time), so there is a series of these for each subject. What the teacher looks at influences what the student looks at. What method would I use to predict what the student is looking at, using only teacher data? Lets say I can train some learning algorithm using a gold standard set of student and teacher data.

I was thinking hidden markov model would be appropriate, given the definition in Wikipedia, but I am not sure how to put this into practice over my dataset.

More detail: I have data about how a teacher and student each look at a map and some readings. I have 40 of these datasets, which look like \[(366,234,0), (386,234,5), ...\] which means the teacher looked at point (366,234) at time 0 and then 5 seconds later moved up to look at coordinate (386, 234). I can to learn a model to understand the relationship between how a teacher looks at content, to predict how a student will look at the same content. So maybe the student looks at the content in the same order as the teacher but slower. Or perhaps the student doesn't look around as much but the teacher scans more of the content. I have both sets of data and want to see how accurate of a model I can get -- would I be able to predict the student's looking behavior within 50px of the teacher's looking behavior?

# Answer
> 3 votes
If I understand your question right, you want to model two stochastic processes, where the 'student' process is driven by the 'teacher' process.

A hidden Markov model can represent such a relationship, but is restricted to a discrete state space. This means that you can only model a finite set of points on your map rather than continuous (x/y) coordinates. A Linear Dynamical System might suit better to your problem.

You could also use recurrent neural networks to model your system.

---
Tags: machine-learning
---


# Question
Title: What would be the over all speed-up achieved?
Suppose we are using a dual core processor and we run 2 applications (1 with 80% resource requirements and the other with 20% resource requirements).
Now the first program is parallelizable for 40% and the second one not parallelizable.
My question is what would be the speed up achieved in this case.
By speed-up i mean the ratio between the execution times before and after parallelization.

# Answer
> 3 votes
Hint: Look up Amdahl's Law on your favorite search engine and plug your question into the equation you find.

---
Tags: parallel-computing
---


# Question
Title: Why is the difference of two NP-complete languages not in NP?
I found something in my notes I don't really understand, maybe you could help.

Let $A$ = Independent Set and $B$ = Clique. Then, we clearly have

* $A \in \mathsf{NPC}$ and
* $B \in \mathsf{NP}$.

Now, the claim is that $A \setminus B \notin \mathsf{NP}$ with the following explanation. If it was in $\mathsf{NP}$ then $\mathsf{NP} = \mathsf{NPC}$.

Can you explain why this argument is true?

# Answer
> 4 votes
It's a bit artificial, but if we define

$A = \\{(G,k):G \text{ has an independent set of size } k \\}$

$B = \\{(G,k):G \text{ has a clique of size } k \\}$

then $A \setminus B$ is $\mathsf{coNP}$-hard because we can reduce $\overline{B}$ to it: given a graph $G$ and a number $k$ we can form $G'$ by adding $k$ isolated vertices to $G$, then $(G',k) \in A\setminus B$ iff $(G,k) \in \overline{B}$.

I claim that

$A \setminus B \in \mathsf{NP} \Leftrightarrow \mathsf{NP}=\mathsf{coNP}$

$(\Rightarrow)$: If a $\mathsf{coNP}$-hard language is in $\mathsf{NP}$, then $\mathsf{NP}=\mathsf{coNP}$.

$(\Leftarrow)$: If $\mathsf{NP}=\mathsf{coNP}$ then $A \setminus B \in \mathsf{NP}$ follows by closure properties of $\mathsf{NP}$.

Since researchers believe that $\mathsf{NP} \neq \mathsf{coNP}$ (this is a stronger version of $\mathsf{P} \neq \mathsf{NP}$), it makes sense to bet on $A \setminus B \notin \mathsf{NP}$. Currently we have no proof though.

# Answer
> 2 votes
The difference between two $\mathsf{NP}$ languages is *not necessarily* in $\mathsf{NP}$. (It might be, but it might not be.)

Consider $A=\\{0,1\\}^\*$ and $B$ any $\mathsf{NP}$-complete language (e.g., 3SAT). Then $A \setminus B = \overline{B}$ is the complement of $B$. Since $B$ is $\mathsf{NP}$-complete, by definition $\overline{B}$ is $\mathsf{coNP}$-complete. Now if any $\mathsf{coNP}$-complete language is in $\mathsf{NP}$, it follows that $\mathsf{NP}=\mathsf{coNP}$. This would be a very surprising result.

To summarize: Most researchers believe that $\mathsf{NP}\ne \mathsf{coNP}$ (just like they believe that $\mathsf{P}\ne \mathsf{NP}$); and if we assume that $\mathsf{NP}\ne \mathsf{coNP}$, it follows that there exists languages $A,B \in \mathsf{NP}$ such that $A\setminus B\notin \mathsf{NP}$.

In other words, under plausible assumptions, the difference between two $\mathsf{NP}$ languages is not necessarily in $\mathsf{NP}$.

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


# Question
Title: Unsupervised anomaly detection: assigning the clusters to normal and anomaly
Having a unsupervised algorithm done on a dataset (e.g. K-means), how can I determine which cluster is normal and which is anomalous (for 30 clusters, for example)?

If the dataset contains normal traffic much more than anomalies (99%), then the radius of clusters associate to normal traffic is bigger. Is this true? Why?

If so, then we set the clusters with greater radius to normal according to a threshold. The smaller the threshold, the more the detection rate and the more the false alarm rate. Is this true?

Could a labeled dataset help determine the normal clusters? For example, finding the closest point to the centroid of a given cluster and checking whether it is labeled anomaly or not?

\[1\] uses Cluto software and its mountain visualization graph that I can't understand why its 3D, having feature space of dimension 41.

Reference: \[1\] Jose F. Nieves, Data Clustering for Anomaly Detection in Network Intrusion Detection

# Answer
The radius depends on the number of clusers you choose. The more clusters, the smaller the radius.

If you have labelled data, you could eliminate the outliers/anomalies for determining the threshold radii for your clusters. For example you could take the greatest distance from the cluster center to its members (smaller radius for higher detection rate as stated in your question).

This question is closely related to the question Anomaly/outlier detection using fuzzy clustering. I am reposting my answer:

As far as I know there is no unique definition for what is an outlier/anomaly. Therefore you'll have to decide by yourself what the characteristics of outlying data points in your data set are. This could be for example: distance to the cluster center (threshold), local neighbourhood (a data point that has no/few data points in its neighgbourhood might be an outlier) or statistical characteristics (an outlier doesn't 'fit' to the distribution of a cluster, e.g. Grubbs' method). You can find a survey of outlier detection methods in A Survey of Outlier Detection Methodologies by Hodge and Austin (2004).
> 1 votes

# Answer
If you have a labelled training set of normal data (or mostly normal data), then it is easy to identify which clusters are "normal" and which are "anomalies": just associate each data point in the training set to a cluster. If a cluster appears many times in the training set, it is normal.

If you do not have a labelled training set, in the absence of additional information there is no way to declare some clusters as normal and some as anomalous.
> 1 votes

---
Tags: machine-learning, pattern-recognition
---


title: Deciding if language is Context-Free

text:
# Question
Title: Deciding if language is Context-Free
I need help with deciding if $L$ is context-free.

$$L = \\{a^pb^{q+r}c^sd^{q+t}e^{p+r} \mid p, q, r, s \ge 0\ , s \> t\\}$$

Can be rewritten into:

$$L = \\{a^pb^qb^rc^sd^qd^te^pe^r \mid p, q, r, s \ge 0\ , s \> t\\}$$

When we see the first occurrence of $c$, we push the $c$:s onto the stack. But we can't make difference between $d^q$ and $d^t$, so comparing $s \< t$ is impossible when popping the $d$:s.

Hence $L$ is not Context-Free.

Is my reasoning right ?

# Answer
> 4 votes
Hint: rewrite $L$ as $L = \\{a^p b^r b^q c^s d^t d^q e^r e^p \mid p,q,r,s \ge 0, s\>t\\}$.

Does $L$ now look like something you can generate with a CFG?

# Answer
> 1 votes
You reasoning is *not* correct, and not only because you reach the wrong answer.

You argued for *one* representation of the language that it can't be faithfully checked by *one* (idea for) a push-down automaton. However, in order to show that a language is not context-free you have to show that *no* PDA can accept the language in *any* representation.

There are techniques to approach this task; see our reference question. Always try these if you think a language is not context-free. If you are not able to apply those techniques, you may figure out how to build a PDA or a grammar along the way -- or you have a really tough language at your hands.

# Answer
> 0 votes
If we rewrite L as

$$L = \\{a^pb^qb^rc^sd^td^qe^pe^r \mid p, q, r, s \ge 0\ , s \> t\\}$$

If we then look at the case where $$q = 0$$ and $$s, t \> 0$$

We take this example string $$z = abcccddee$$ which belongs to L.

This string can be accepted by a PDA and the comparison $$s \> t$$ can be done by pushing all the c:s and then popping the d:s.

L is context-free because we showed that a PDA exists for SOME representation of the language.

Is my reasoning right ?

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


# Question
Title: How can you shuffle in $O(n)$ time if you need $\Omega(n \log n)$ random bits?
A shuffling algorithm is supposed to generate a random permutation of a given finite set. So, for a set of size $n$, a shuffling algorithm should return any of the $n!$ permutations of the set uniformly at random.

Also, conceptually, a randomized algorithm can be viewed as a deterministic algorithm of the input and some random seed. Let $S$ be any shuffling algorithm. On input $X$ of size $n$, its output is a function of the randomness it has read. To produce $n!$ different outputs, $S$ must have read at least $\log(n!) = \Omega(n \log n)$ bits of randomness. Hence, any shuffling algorithm must take $\Omega(n \log n)$ time.

On the other hand, the Fisher-Yates shuffle is widely believed to run in $O(n)$ time. Is there something wrong with my argument? If not, why is this belief so widespread?

# Answer
> 12 votes
Your argument appears to be perfectly valid (Fisher-Yates does indeed require $\log (n!)$ bits of randomness), the discrepancy comes in by making different assumptions about the complexity of the random number generation.

You're assuming generating a random number between $0$ and $n$ takes $O(\log n)$.

But, when saying that the Fisher-Yates shuffle is $O(n)$, one assumes generating a random number takes $O(1)$.

An integer index (which is used in the Fisher-Yates shuffle) is generally considered $O(1)$ space (even though it's technically $O(\log n)$) because you can index way more data with a simple 64-bit integer than can currently reasonably fit into the memory of any computer most of us have access to $^{1}$. And the space complexity per number is same as the complexity for the number of random bits that must be generated for that number.

1: To go beyond the number of elements a 64-bit integer can index, we would require $2^{64}$ = $18446744073709551616$ elements, and, assuming 1 bit (which is obviously very small) per element, this requires 2 exabytes.

# Answer
> 6 votes
In the analysis of Fisher-Yates shuffle and similar algorithms we typically assume that we can draw a number from $\[1..n\]$ uniformly at random in time $O(1)$. Also, we usually assume a RAM model with uniform cost, that is we can read such numbers in time $O(1)$, too.

If you include random number generation into your runtime analysis (which you probably *should* do), make sure to be clear about whether you are talking about worst-case or expected time.

Depending on what kind of random source you have at hand, assuming constant-time random number generation may or may not be warrented. For instance, a (black-box, constant-time) source of $\mathcal{U}(0,1)$ (uniform) real numbers can be used thus, but a $\mathcal{B}(0.5)$ (Bernoulli) bit source can not. See here for details.

---
Tags: algorithms, algorithm-analysis, runtime-analysis, randomized-algorithms
---


# Question
Title: Can you do an in-place reversal of a string on a vanilla turing machine in time $o(n^2)$?
By a vanilla Turing machine, I mean a Turing machine with one tape (no special input or output tapes).

The problem is as follows: the tape is initially empty, other than a string of $n$ $1$s and $0$s terminated by an end-of-string character. The tape head starts at the beginning of the string. The goal is for the tape to contain the original string in reverse order, terminated by an end-of-string character, with the tape head returned to the beginning of the string when the Turing machine finally halts.

The Turing machine can use as large an alphabet as we like (so long as it contains $0$, $1$, and an end-of-string character), and can have as many states as we like. Is there a fixed Turing machine that can complete this task in time $o(n^2)$?

It's easy to do this in time $O(n^2)$ using just a few states and symbols. It seems intuitively clear that something prevents us from doing it more than a constant factor faster, but I've never been able to prove it, and I often worry late into the night about miraculous applications of network coding or voodoo magic that somehow get a logarithmic speedup...

# Answer
> 11 votes
The standard way to prove things like this is to show that $\Theta(n)$ bits of information must cross at least $\Theta(n)$ points.

That is, if you're reversing it "in place", the first third of the bits must cross all $n/3$ middle cells and end up in the last $n/3$ cells. Since the head moves $O(1)$ bits a distance at most $1$ cell each step, this requires $n^2/9$ steps. If the reversed copy ends up in a different set of cells, a very similar argument gives an $\Omega(n^2)$ lower bound.

It takes some work to make this intuitive idea rigorous, but it has been done, although I don't have enough time to locate the papers these results appeared in. If anybody can point to a relevant paper, please edit this answer to do so.

# Answer
> 3 votes
I don't see any way to do it, either.

It seems to take $\Theta(n^2)$ time just to make a second copy of the string (e.g., if the input is the $n$-bit string $s$, at the end of the computation we want the tape to contain the string $ss$). Maybe this could be formalized somehow using the methods of communication complexity; I don't know.

Here's some intuition for why reversal feels like it should require $\Omega(n^2)$ steps. Color bit positions $0,1,\ldots,n/2$ of the tape green; that's "the green zone". Similarly, let's treat bit positions $3n/4,\dots,n$ as "the red zone". Intuitively, we have to convey $n/2$ bits of information from the green zone to the red zone. If the finite-state automaton of the Turing machine can hold $b$ bits of information, then the Turing machine will have to visit the green zone $n/(2b)$ times, and then it'll have to travel at least $n$ positions to get to the red zone. Thus, it feels like the Turing machine is going to have to do at least $n/(2b)$ passes (where in each pass it enters the green zone, then travels from the green zone to the red zone), and each pass will take $n$ steps just for the head movement, for a total of at least $n^2/(2b)=\Omega(n^2)$ steps. This is not a complete proof, but it seems to give some sense of why I don't expect there to be a faster way to do it.

---
Tags: complexity-theory, turing-machines, time-complexity, lower-bounds
---


# Question
Title: Which machine learning algorithms can be used for time series forecasts?
Currently I am playing around with time series forecasts (specifically for Forex). I have seen some scientific papers about echo state networks which are applied to Forex forecast. Are there other good machine learning algorithms for this purpose?

It would also be interesting to extract "profitable" patterns from the time series.

# Answer
> 28 votes
Here are three survey papers that examine the use of machine learning in time series forecasting:

> "...multilayer perceptron, Bayesian neural networks, radial basis functions, generalized regression neural networks (also called kernel regression), K-nearest neighbor regression, CART regression trees, support vector regression, and Gaussian processes."

> "...that artificial neural networks (ANNs) are the dominant machine learning technique in this area."

> "...the formalization of one-step forecasting problems as supervised learning tasks, the discussion of local learning techniques as an effective tool for dealing with temporal data, and the role of the forecasting strategy when we move from one-step to multiple-step forecasting."

---
Tags: reference-request, machine-learning, artificial-intelligence
---


# Question
Title: Count the number of integers satisfying two conditions using DP
Given two integers $n$ and $m$, how many numbers exist such that all integers have all digits from $0$ to $n-1$, the difference between two adjacent digits is exactly $1$, and the number of digits in the integer is at most $m$?

The integer cannot start with a $0$. All digits from $0$ to $n-1$ must be present.

Example: for $n = 3$ and $m = 6$ there are $18$ such numbers ($210, 2101, 21012, 210121 \ldots$)

I know there is a dynamic programming method to solve this. After looking the solution, I am not able to understand it. Can anybody please give any good solution to me?

# Answer
> 0 votes
Hint: The table consists of cells $T(S,d,\ell)$, which count numbers of length $\ell$ in which the last digit is $d$ and the set of digits is $S$. Unfortunately this solution is exponential in $n$.

---
Tags: algorithms, combinatorics, dynamic-programming
---


# Question
Title: Calculate the number of elements after multiplying/adding two polynomials
Suppose I have two polynomials $f(x)$ and $g(x)$ and I somehow represent their coefficients. I have a couple of ways to hold a polynomial depending on how many significant coefficients the polynomial has. I want to determine the amount of significant coefficients in the results of $f(x) + g(x)$ ,$f(x) \cdot g(x)$ , $f(x) - g(x)$ etc. .

But I'd like to do it before I create the object that holds them, is there some efficient way of doing this without calculating the result twice?

I can assume that I know the current rank and number of elements in $f(x)$ and $g(x)$

If this is not possible knowing that the new polynomial's non-trivial coefficients will be at least half of the rank will suffice, but I'm unsure how to do it as well.

I did try to apply various heuristics but didn't come up with something consistent and fast.

# Answer
If $F$ is the number of terms in $f(x)$ and $G$ is the number of terms in $g(x)$ then the number of terms in $f(x)\pm g(x)$ is between $|F-G|$ and $F+G$, and all cases can occur. If you want to calculate the number of terms, you can first run a loop that checks how many non-zero terms the result has, allocate the needed array, and then do the actual computation. The first pass could be faster, since you are only comparing coefficients, which might be faster than actually adding or subtracting them.

For $f(x) \cdot g(x)$, the number of terms is between $F+G-1$ and $FG$, and again these extreme cases can actually occur. Again you can run a first pass which calculates how many non-zero terms there are, though you'd have to be careful if you want to implement it using constant space and the same time (if it is at all possible). It might be better to calculate the product and then reallocate the result to its actual size.
> 2 votes

---
Tags: algorithms, time-complexity, optimization, efficiency, arithmetic
---


title: Random sampling in a polygon

text:
# Question
Title: Random sampling in a polygon
I would like to sample a uniformly random point in a polygon...

If sample a large number they'd be equally likely to fall into two regions if they have the same area.

This would be quite simple if it were a square since I would take two random numbers in \[0,1\] as my coordinates.

The shape I have is a regular polygon, but I'd like it to work for any polygon.

https://stackoverflow.com/questions/3058150/how-to-find-a-random-point-in-a-quadrangle

# Answer
1. Triangulate the polygon
2. Determine in which of the triangles the point should lie (weights triangle areas)
3. Sample the point in the triangle as explained in this post
> 10 votes

# Answer
One easy way is to find the bounding box for your polygon and use rejection sampling: sample from the bounding box and accept if it falls within the polygon, which will happen with probability $1/2$ at least (I think).

Another possibility is to triangulate your polygon. First sample a triangle in a proportionate way, then sample a random point in the triangle. The latter is simple: up to affine transformations, all triangles are of the form $\\{(x,y) : x,y \geq 0, x+y \leq 1\\}$. To sample uniformly a point from that distribution, first sample $x \in \[0,1\]$ according to the density $2(1-x)$ (i.e. sample a uniform $r \in \[0,1\]$ and compute $x = 1-\sqrt{1-r}$) and then sample $y \in \[0,1-x\]$ uniformly (i.e. sample a uniform $s \in \[0,1\]$ and compute $y = (1-x)s$). An even simpler method is to sample $x,y \in \[0,1\]$, and if $x+y \> 1$ replace $(x,y)$ with $(1-x,1-y)$.
> 4 votes

# Answer
This is a little crazy, but should work well even if your polygon is very weird.

Use the Reimann mapping theorem to find a conformal map from the unit disc to your polygon, viewing it as a subset of $\mathbb{C}$. See, for example the references in:

http://siam.org/pdf/news/1297.pdf

Then use the pushforward of a uniform density on the disc as the proposal density in Metropolis-Hastings MCMC sampling.
> 4 votes

---
Tags: algorithms, randomness, sampling, random-number-generator
---