# Question
Title: Looking for a set implementation with small memory footprint
I am looking for implementation of the set data type. That is, we have to

* maintain a dynamic subset $S$ (of size $n$) from the universe $U = \\{0, 1, 2, 3, \dots , u – 1\\}$ of size $u$ with
* operations `insert(x)` (add an element `x` to $S$) and `find(x)` (checks whether element `x` is a member of $S$).

I don't care about other operations. For orientation, in applications I'm working with we have $u \approx 10^{10}$.

I know of implementations that provide both operations in time $O(1)$, so I worry mostly about the size of data structure. I expect *billions* of entries but want to avoid swapping as much as possible.

I am willing to sacrifice runtime if necessary. Amortised runtime of $O(\log n)$ is what I can admit; expected runtimes or runtimes in $\omega(\log n)$ are not admissable.

One idea I have is that if $S$ can be represented as a union of ranges `[xmin, xmax]`, then we will be able to save on storage size with the price of some performance decrease. Also, some other data patterns are possible, like `[0, 2, 4, 6]`.

Could you please point me to data structures which can do something like that?

# Answer
> 8 votes
Joe's answer is extremely good, and gives you all the important keywords.

You should be aware that succinct data structure research is still in an early stage, and many of the results are largely theoretical. Many of the proposed data structures are quite complex to implement, but most of the complexity is due to the fact that you need to maintain asymptotic complexity both over the universe size and the number of elements stored. If either one of these is relatively constant, then a lot of the complexity goes away.

If the collection is semi-static (that is, inserts are rare, or at least low-volume), then it's certainly worth considering an easy-to-implement static data structure (Sadakane's sdarray is a fine choice) in conjunction with an update cache. Basically, you record updates in a traditional data structure (e.g. B-tree, trie, hash table), and periodically bulk-update the "main" data structure. This is a very popular technique in information retrieval, since inverted indexes have many advantages for searching but are hard to update in-place. If this is the case, please let me know in a comment and I'll amend this answer to give you some pointers.

If inserts are more frequent, then I suggest succinct hashing. The basic idea is straightforward enough to explain here, so I will do so.

So the basic information theoretic result is that if you're storing $n$ elements from a universe of $u$ items, and there is no other information (e.g. no correlation between the elements) then you need $\log {u \choose n} + O(1)$ bits to store it. (All logarithms are base-2 unless otherwise specified.) You *need* this many bits. There is no way around it.

Now some terminology:

* If you have a data structure which can store the data and support your operations in $\log {u \choose n} + O(1)$ bits of space, we call this an *implicit* data structure.
* If you have a data structure which can store the data and support your operations in $\log {u \choose n} + O(\log {u \choose n}) = (1 + O(1)) \log {u \choose n}$ bits of space, we call this a *compact* data structure. Note that in practice this means that the relative overhead (relative to the theoretical minimum) is within a constant. It could be 5% overhead, or 10% overhead, or 10 times overhead.
* If you have a data structure which can store the data and support your operations in $\log {u \choose n} + o(\log {u \choose n}) = (1 + o(1)) \log {u \choose n}$ bits of space, we call this a *succinct* data structure.

The difference between succinct and compact is the difference between little-oh and big-oh. Ignoring the absolute-value thing for a moment...

* $g(n) = O(f(n))$ means that there exists a constant $c$ and a number $n\_0$ such that for all $n \> n\_0$, $g(n) \< c \cdot f(n)$.
* $g(n) = o(f(n))$ means that for all constants $c$ there exists a number $n\_0$ such that for all $n \> n\_0$, $g(n) \< c \cdot f(n)$.

Informally, big-oh and little-oh are both "within a constant factor", but with big-oh the constant is chosen for you (by the algorithm designer, the CPU manufacturer, the laws of physics or whatever), but with little-oh *you pick the constant yourself and it can be as small as you like*. To put it another way, with succinct data structures, the relative overhead gets arbitrarily small as the size of the problem increases.

Of course, the size of the problem may have to get huge to realise the relative overhead that you want, but you can't have everything.

OK, with that under our belts, let's put some numbers on the problem. Let's supposed that keys are $n$-bit integers (so the universe size is $2^n$), and we want to store $2^m$ of these integers. Let's suppose that we can magically arrange an idealised hash table with full occupancy and no wastage, so that we need exactly $2^m$ hash slots.

A lookup operation would hash the $n$-bit key, mask off $m$ bits to find the hash slots, and then check to see if the value in the table matched the key. So far, so good.

Such a hash table uses $n 2^m$ bits. Can we do better than this?

Suppose that the hash function $h$ is invertible. Then we don't have to store the whole key in each hash slot. The location of the hash slot gives you $m$ bits of the hash value, so if you only stored the $n-m$ remaining bits, you can reconstruct the key from those two pieces of information (the hash slot location and the value stored there). So you would only need $(n - m) 2^m$ bits of storage.

If $2^m$ is small compared with $2^n$, Stirling's approximation and a little arithmetic (proof is an exercise!) reveals that:

$$(n - m) 2^m = \log {2^n \choose 2^m} + o\left(\log {2^n \choose 2^m}\right)$$

So this data structure is succinct.

However, there are two catches.

The first catch is constructing "good" invertible hash functions. Fortunately, this is much easier than it looks; cryptographers make invertible functions all the time, only they call them "cyphers". You could, for example, base a hash function on a Feistel network, which is a straightforward way to construct an invertible hash functions from non-invertible hash functions.

The second catch is that real hash tables are not ideal, thanks to the Birthday paradox. So you'd want to use a more sophisticated type of hash table which gets you closer to full occupancy with no spilling. Cuckoo hashing is perfect for this, as it lets you get arbitrarily close to ideal in theory, and quite close in practice.

Cuckoo hashing does require multiple hash functions, and it requires that values in hash slots be tagged with which hash function was used. So if you use four hash functions, for example, you need to store an additional two bits in each hash slot. This is still succinct as $m$ grows, so it's not a problem in practice, and still beats storing whole keys.

Oh, you might also want to look at van Emde Boas trees.

**MORE THOUGHTS**

If $n$ is somewhere around $\frac{u}{2}$, then $\log {u \choose n }$ is approximately $u$, so (once again) assuming that there is no further correlation between the values, you basically can't do any better than a bit vector. You will note that the hashing solution above does effectively degenerate to that case (you end up storing one bit per hash slot), but it's cheaper just to use the key as the address rather than using a hash function.

If $n$ is very close to $u$, all of the succinct data structures literature advises you to to invert the sense of the dictionary. Store the values that *don't* occur in the set. However, now you effectively have to support the delete operation, and to maintain succinct behaviour you also need to be able to shrink the data structure as more elements get "added". Expanding a hash table is a well-understood operation, but contracting it is not.

# Answer
> 5 votes
It sounds like you want a *succinct* data structure for the *dynamic membership problem*.

Recall that a succinct data structure is one for which the space requirement is "close" to the information-theoretic lower bound, but unlike a compressed data structure, still allows for efficient queries.

The *membership problem* is exactly what you describe in your question:

> maintain a subset $S$ (of size $n$) from the universe $U = \\{0, 1, 2, 3, \dots , u – 1\\}$ of size $u$ with operations:

* `find(x)` (checks whether element `x` is a member of $S$).
* `insert(x)` (add an element `x` to $S$)
* `delete(x)` (remove an element `x` from $S$)

If only the `find` operation is supported, then this is the *static* membership problem. If either `insert` or `delete` are supported, but not both, it is called *semi-dynamic*, and if all three operations are supported, then it is called the *dynamic* membership problem.

Techincally, I think you only asked for a data structure for the semi-dynamic membership problem, but I don't know of any data structures which take advantage of this constraint and also meet your other requirements. However, I do have the following reference:

In Theorem 5.1 of the article *Membership in Constant Time and Almost-Minimum Space*, Brodnik and Munro give the following result:

> There exists a data structure requiring $O(B)$ bits which supports searches in constant time and insertions and deletions in constant expected amortized time.

where $B = \lceil \log {u \choose n} \rceil$ is the information theoretic minimum number of bits required.

The basic idea is that they recursively split the universe into ranges of carefully chosen sizes, so this even sounds like the techniques might be along the lines that you are thinking of.

However, if you're looking for something you can actually implement, I don't know if this is going to be your best bet. I only skimmed the paper, and trying to explain the details is way beyond the scope of this answer. They parameterize their solution, using different strategies depending on the relative sizes of $u$ and $n$. And the dynamic version of the data structure is only sketched in the paper.

---
Tags: data-structures, efficiency, space-complexity, sets, dictionaries
---


# Question
Title: How many sequences in a prefix code can be compressed by m bits?
I have a little understanding problem with Appendix A ("Universal Codes") in the paper "Shannon Information and Kolmogorov complexity" by Gründwald and Vitanyi (Link).

At the end of page 50, they say something corresponding to:

> For each Prefix-code, the fraction of sequences of length $n$ that can be compressed by more than $m$ bits is less than $2^{-m}$.

Either this is a writing mistake or I should make a break from reading.

It is easy to see, that the number of strings with length $n$ and compression length smaller than $m$ is smaller $2^{m-n}$ for a prefix-code because there are simple not enough "shorter" words.. Did they mean this information?

It is also easy to understand, that the Kraft-Inequality $\sum\_{x\in X}2^{-l(x)}\leq1$ holds for a prefix code with source word set $X$ and the compression length $l(x)$ for strings $x\in X$.

Is that only a writing mistake? Respectively can you tell me an explanation?

# Answer
There is no problem with the statement. An *encoding* $f$ of the set of strings of length $n$ is a map from $\\{0,1\\}^n$ to $\\{0,1\\}^\*$ which is injective (one-to-one). Such a mapping *compresses a string $x$ by more than $m$* if $|f(x)| \< |x| - m$. In our case, all the strings have length $n$, so a string $x \in \\{0,1\\}^n$ is compressed by more than $m$ if $|f(x)| \< n-m$. There are $\sum\_{i=0}^{n-m-1} 2^i = 2^{n-m}-1 \< 2^{n-m}$ such strings, and since $f$ is injective, the fraction of strings compressed by more than $m$ is less than $2^{n-m}/2^n = 2^{-m}$.
> 2 votes

---
Tags: coding-theory
---


title: Model for diurnal nature of data

text:
# Question
Title: Model for diurnal nature of data
I have a timeseries dataset of a quantity measured over the period of a week. I want to verify if the data is varying in a diurnal fashion with the help of some mathematical measure. Does any such measure exist?

# Answer
> 1 votes
If you want to find periodic behaviors of your data, you should use the Fourier transform, which decomposes your data into a linear combination of cyclic waveforms. If you have a guess on the actual period, as in your case, you can try something simpler. For each hour during the day, compute the mean $\mu$ and variance $\sigma^2$ of your data, and plot the intervals $\[\mu-\sigma,\mu+\sigma\]$ for each hour. That should give you an idea regarding your hunch. (More generally, you can try a sophisticated method like ANOVA.)

Perhaps you should ask your question over in stats.se.

---
Tags: algorithms, data-mining
---


# Question
Title: Why does this automation accept the empty string?
I am new to Automata Theory. I am studying the book thoroughly and understanding it well. I have got a confusion regarding NFA. Why does this automaton accept the empty string λ?

What I think is that: implicitly δ(q,λ)=q for all states q. But here also explicitly defined δ(q0,λ)=q2. As there is a walk to the final state using δ(q0,λ)=q0, so δ(q0,λ)=q2 will not be followed. Am I correct?

# Answer
An automaton accepts $\lambda$, the empty string, if and only if the starting state is a final state, or there is some final state in the empty-string-closure of the starting state (in the non-deterministic case).

You don't need to walk from the start state, since it is already final. The fact that you have the option to doesn't mean you are obligated to.
> 8 votes

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


title: 2 threads accepted at the same time

text:
# Question
Title: 2 threads accepted at the same time
Assuming we have an automaton that simultaneously accepts a string on two paths. Would this mean that the construction of the NFA might be faulty? In other words; at the end of any string over any alphabet, does the NFA have to end up accepting one single path only? Or could it accept several at the same time?

# Answer
A NFA is defined so that if there is *any* accepting path for the given input string, it will accept. It's perfectly allowable for an NFA to have two paths to acceptance. If *no* path accepts, then the NFA doesn't accept.
> 4 votes

# Answer
An NFA which has only one accepting path for any string is known as unambiguous. Any regular language can be represented as an unambiguous NFA (since DFAs are, trivially, unambiguous NFAs), but NFAs which are not defined as such are still valid.

The acceptance of an NFA very much corresponds to the $\exists$ quantifier: the string is accepted if there is at least one solution, and more than one is still acceptable.
> 3 votes

---
Tags: terminology, automata, finite-automata, nondeterminism
---


# Question
Title: Good motivation for parallel data structures and algorithms
I have a more general question for you. I'm working in *Parallel Data Structures* and *Parallel Algorithms*. That is a nice topic with a lot of interesting challenges. However, I have some problem to argue for why is necessary use parallel solutions. The most common justification is "We need to take advantage of the current architectures", "Parallel alternatives speed up sequential alternatives", but it isn't enough. Some people can think: *OK, I believe you, but I don't have any problem waiting 10 minutes for my efficient sequential algorithm instead of 2 minutes for your parallel algorithm*. That reflects a weak spot of parallel solutions: they are, in general, difficult to program and need more time to debugging.

So, now I'm trying to find a better motivation for parallel solutions. I have this motivation now: *There are **problems** that don't have efficient solutions in sequential, and parallel solutions appear like the best alternative for those kind of **problems***. My question now for you is: *How characterize this kind of problems?*. I thought in problems with a lot of computation, like some graph problems, but I would like to know other view points.

# Answer
> 1 votes
The quintessential example is large-scale physics simulations, say "electronic" wind tunnel or protein folding (i.e. "finding new medicines"). Both are hugely expensive in terms of computation cost, but yield themselves well to parallelization.

Another area in which parallelization is important is "big data", say search engines. When dealing with big data you need to divide the work among many processors. However often in these cases, most of the work is done in an "embarrassingly parallel" fashion, in which each processor does its share of work, and everything is combined in the end; you could (but don't have to) argue that this is not an interesting example for parallel algorithms.

Yet another example is computer animation, say for the movie industry. This example probably has the same shortcoming as the previous one.

What is common to all three examples is that computation is very costly, and cannot be executed sequentially within a reasonable span of time. Hence the need to distribute the work among several computers (or processors, or cores).

Another possible use case is when you want answers really fast. Here an example could be real-time cryptanalysis during a war: you want your answers in one hour rather than one day, and it makes a big difference. A similar example is real-time TV studios, which probably benefit from distributed computing as well. Chess-playing machines and the like also belong to this category. Big data also shows up in this category – when interactively exploring data, you would like queries to run in reasonable time.

# Answer
> 1 votes
There are two main reasons for parallel computing. The first, and obvious one, is time. It's our desire to minimize the time required for a solution that leads naturally to parallel computing. But, in some cases, this is not just a desire, but a necessity. Besides the examples already given by @YuvalFilmus, think about, for instance, weather forecasts. We need today a forecast for tomorrow, otherwise the forecast is useless, so we use parallel computing. In general, parallel computing, with regard to this point of view, is useful since it makes unfeasible problems feasible, and helps reduce design time, and therefore allows gaining a competitive advantage in industry. So, your example (10 versus 2 minutes) is not really the realm of parallel computing. Think about Boeing designing a new airplane using parallel computers saving years of design time instead.

The second reason is mainly scientific. For the majority of the problems, many scientists are willing to wait for the same amount of time to solve larger problems or to solve a problem of the same size but with greater accuracy (better, more complicated models) or with improved numerical precision. For instance, scientists usually don't care too much if climate change parallel simulations run for 6 months on a parallel supercomputer. If they spent 6 months last year, this year they are still willing to wait for 6 months, but they are now interested on getting better, high-quality answers, so they use a new , more complicated model (adding a lot of non-linear partial differential equations etc).

Finally, sequential problems that are difficult to parallelize are technically called $P-Complete$ problems, i.e. they are complete for the complexity class $P$. However, even though parallel computing helps, you can not expect to obtain optimal parallel solutions: these problems are thought to be $intrinsically$ sequential.

# Answer
> 0 votes
In a talk about the new Mill CPU architecture, Ivan Godard makes a great point about why normal users might want faster bigger better CPUs:

http://youtu.be/jNgIdTUmzEQ?t=10m13s

He says that the reason games are full of zombies is because the AI is too dumb to do much else, and he posits it as a hardware limitation.

Newer game engines are multi-threaded, and even heterogeneous. But there is a lot more to be done to make them use all the cores and types of core in the next generation of hardware effectively.

Parallel data structures and algorithms are applicable to 'small data' and 'home user' problems as much as the big science and industry applications. People don't know it, but people want progress on parallel data structures and algorithms for their own selfish entertainment as much as for the improvement of mankind as a whole.

So ask these people if they think that games are too linear and the AI too dumb. Gaming resonates with people in a way abstract discussion about computational biology doesn't.

---
Tags: parallel-computing
---


# Question
Title: Define a list using only the Hindley-Milner type system
I'm working on a small lambda calculus compiler that has a working Hindley-Milner type inference system and now also supports recursive let's (not in the linked code), which I understand should be enough to make it Turing complete.

The problem now is I have no idea how to make it support lists, or whether it already does support them and I just need to find a way to encode them. I'd like to be able to define them without having to add new rules to the type system.

The easiest way I can think of a list of `x` is as something that is either `null` (or the empty list), or a pair that contains both an `x` and a list of `x`. But to do this I need to be able to define pairs and or's, which I believe are the product and the sum types.

Seems that I can define pairs this way:

```
pair = λabf.fab
first = λp.p(λab.a)
second = λp.p(λab.b)

```

Since `pair` would have the type `a -> (b -> ((a -> (b -> x)) -> x))`, after passing, say, an `int` and a `string`, it'd yield something with type `(int -> (string -> x)) -> x`, which would be the representation of a pair of `int` and `string`. What bothers me here is that if that represents a pair, why is that not logically equivalent to, nor implies the proposition `int and string`?. However, is equivalent to `(((int and string) -> x) -> x)`, as if I could only have product types as parameters to functions. This answer seem to address this problem, but I have no idea what the symbols he uses mean. Also, if this does not really encode a product type, is there anything I can do with product types I couldn't do with my definition of pairs above (considering I can also define n-tuples the same way)? If not, wouldn't this contradict the fact that you cannot express (AFAIK) conjunction using only implication?

Also, how about the sum type? Can I somehow encode it using only the function type? If so, would this be enough to define lists? Or else, is there any other way to define lists without having to extend my type system? And if not, what changes would I need to make if I want to keep it as simple as possible?

Please keep in mind that I'm a computer programmer but not a computer scientist nor a mathematician and pretty bad at reading math notation.

**Edit:** I'm not sure what's the technical name of what I have implemented so far, but all I have is basically the code I've linked above, which is a constraint generation algorithm that uses the rules for applications, abstractions and variables taken from the Hinley-Milner algorithm and then a unification algorithm that gets the principal type. For instance, the expression `\a.a` will yield the type `a -> a`, and the expression `\a.(a a)` will throw an occurs check error. On top of this, there is not exactly a `let` rule but a function that seems to have the same effect that lets you define recursive global functions like this pseudo-code:

```
GetTypeOfGlobalFunction(term, globalScope, nameOfFunction)
{
    // Here 'globalScope' contains a list of name-value pair where every value is of class 'ClosedType',
    // meaning their type will be cloned before unified in the unification algorithm so that they can be used polymorphically
    tempType = new TypeVariable() // Assign a dummy type to `tempType`, say, type 'x'.
    // The next line creates an scope with everything in 'globalScope' plus the 'nameOfFunction = tempType' name-value pair
    tempScope = new Scope(globalScope, nameOfFunction, tempType)
    type = TypeOfTerm(term, tempScope) // Calculate the type of the term
    Unify(tempType, type)
    return type
    // After returning, the code outside will create a 'ClosedType' using the returned type and add it to the global scope.
}

```

The code basically gets the type of the term as usual, but before unifying, it adds the name of the function being defined with a dummy type into the type scope so that it can be used from within itself recursively.

**Edit 2:** I just realized that I'd also need recursive types, which I don't have, to define a list like I want.

# Answer
> 13 votes
## Pairs

This encoding is the Church encoding of pairs. Similar techniques can encode booleans, integers, lists, and other data structures.

Under the context `x:a; y:b`, the term `pair x y` has the type `(a -> b -> t) -> t`. The logical interpretation of this type is the following formula (I use standard mathematical notations: $\to$ is implication, $\vee$ is or, $\wedge$ is and, $\neg$ is negation; $\iff$ is equivalence of formulas): $$ \begin{align} (a \to b \to t) \to t & \quad\iff\quad \neg (\neg a \vee \neg b \vee t) \vee t \\ & \quad\iff\quad (a \wedge b \wedge \neg t) \vee t \\ & \quad\iff\quad (a \wedge b) \vee t \\ \end{align} $$ Why “`a` and `b` *or `t`*”? Intuitively, because `pair` is a function that takes a function as an argument and applies it to the pair. There are two ways this can go: the argument function can make use of the pair, or it can produce a value of type `t` without using the pair at all.

`pair` is a constructor for the pair type and `first` and `second` are destructors. (These are the same words used in object-oriented programming; here the words have a meaning that is related to the logical interpretation of the types and terms that I won't go into here.) Intuitively, the destructors let you access what is in the object and the constructors pave the way for the destructor by taking as an argument a function that they apply to the parts of the object. This principle can be applied to other types.

## Sums

The Church encoding of a discriminated union is essentially dual to the Church encoding of a pair. Where a pair has two parts that must be put together and you can choose to extract one or the other, you can choose to build the union in either of two ways and when you use it you need to allow for both ways. Thus there are two constructors, and there is a single destructor which takes two arguments.

```
let case w = λf. λg. w f g           case : ((a->t) -> (b->t) -> t) -> (a->t) -> (b->t) -> t
  (* or simply let case w = w *)
let left x = λf. λg. f x             left : a -> ((a->t) -> (b->t) -> t)
let right y = λf. λg. g x            right : b -> ((a->t) -> (b->t) -> t)

```

Let me abbreviate the type `(a->t) -> (b->t) -> t` as `SUM(a,b)(t)`. Then the types of the destructors and constructors are:

```
case : SUM(a,b)(t) -> (a->t) -> (b->t) -> t
left : a -> SUM(a,b)(t)
right : b -> SUM(a,b)(t)

```

Thus

```
case (left x) f g → f x
case (rightt y) f g → g y

```

## Lists

For a list, apply again the same principle. A list whose elements have the type `a` can be built in two ways: it can be an empty list, or it can be an element (the head) plus a list (the tail). Compared with pairs, there's a little twist when it comes to the destructors: you can't have two separate destructors `head` and `tail` because they would only work on non-empty lists. You need a single destructor, with two arguments, one of which is a 0-argument function (i.e. a value) for the nil case, and the other a 2-argument function for the cons case. Functions like `is_empty`, `head` and `tail` can be derived from that. Like in the case of sums, the list is directly its own destructor function.

```
let nil = λn. λc. n
let cons h t = λn. λc. c h t
let is_empty l = l true (λh. λt. false)
let head l default = l default (λh. λt. h)
let tail l default = l default (λh. λt. t)

```

Each of these functions is polymorphic. If you work the types of these functions, you'll note than `cons` is not uniform: the type of the result is not the same as the type of the argument. The type of the result is a variable — it is more general than the argument. If you chain `cons` calls, the successive calls to build a list instantiate `cons` at different types. This is crucial to make lists work in the absence of recursive types. You can make heterogeneous lists that way. In fact, the types that you can express are not “list of $T$”, but “list whose first elements are of types $T\_1,\ldots,T\_n$”.

As you surmise, if you want to define a type that only contains homogeneous lists, you need recursive types. Why? Let's look at the type of a list. A list is encoded as a function which takes two arguments: the value to return on empty lists, and the function to compute the value to return on a cons cell. Let `a` be the element type, `b` be the type of the list, and `c` be the type returned by the destructor. The type of a list is

```
a -> (a -> b -> c) -> c

```

Making the list homogeneous is saying that if it's a cons cell, the tail has to have the same type as the whole, i.e. it adds the constraint

```
a -> (a -> b -> c) -> c = b

```

The Hindley-Milner type system can be extended with such recursive types, and in fact practical programming languages do that. Practical programming languages tend to disallow such “naked” equations and require a data constructor, but this is not an intrinsic requirement of the underlying theory. Requiring a data constructor simplifies type inference, and in practice tends to avoids accepting functions that are actually buggy but happen to be typable with some unintended constraint that causes a difficult-to-understand type error where the function is used. This is why, for example, OCaml accepts unguarded recursive types only with the non-default `-rectypes` compiler option. Here are the definitions above in OCaml syntax, together with a type definition for homogeneous lists using the notation for aliased recursive types: `type_expression as 'a` means that the type `type_expression` is unified with the variable `'a`.

```
# let nil = fun n c -> n;;
val nil : 'a -> 'b -> 'a = <fun>
# let cons h t = fun n c -> c h t;;
val cons : 'a -> 'b -> 'c -> ('a -> 'b -> 'd) -> 'd = <fun>
# let is_empty l = l true (fun h t -> false);;
val is_empty : (bool -> ('a -> 'b -> bool) -> 'c) -> 'c = <fun>
# let head l default = l default (fun h t -> h);;
val head : ('a -> ('b -> 'c -> 'b) -> 'd) -> 'a -> 'd = <fun>
# let tail l default = l default (fun h t -> t);;
val tail : ('a -> ('b -> 'c -> 'c) -> 'd) -> 'a -> 'd = <fun>
# type ('a, 'b, 'c) ulist = 'c -> ('a -> 'b -> 'c) -> 'c;;
type ('a, 'b, 'c) ulist = 'c -> ('a -> 'b -> 'c) -> 'c
# is_empty (cons 1 nil);;
- : bool = false
# head (cons 1 nil) 0;;
- : int = 1
# head (tail (cons 1 (cons 2.0 nil)) nil) 0.;;
- : float = 2.

(* -rectypes is required for what follows *)
# type ('a, 'b, 'c) rlist = 'c -> ('a -> 'b -> 'c) -> 'c as 'b;;
type ('a, 'b, 'c) rlist = 'b constraint 'b = 'c -> ('a -> 'b -> 'c) -> 'c
# let rcons = (cons : 'a -> ('a, 'b, 'c) rlist -> ('a, 'b, 'c) rlist);;
val rcons :
  'a ->
  ('a, 'c -> ('a -> 'b -> 'c) -> 'c as 'b, 'c) rlist -> ('a, 'b, 'c) rlist =
  <fun>
# head (rcons 1 (rcons 2 nil)) 0;;
- : int = 1
# tail (rcons 1 (rcons 2 nil)) nil;;
- : 'a -> (int -> 'a -> 'a) -> 'a as 'a = <fun>
# rcons 1 (rcons 2.0 nil);;
Error: This expression has type
         (float, 'b -> (float -> 'a -> 'b) -> 'b as 'a, 'b) rlist = 'a
       but an expression was expected of type
         (int, 'b -> (int -> 'c -> 'b) -> 'b as 'c, 'b) rlist = 'c

```

## Folds

Looking at this a bit more generally, what is the function that represents the data structure?

* For a natural number: $n$ is represented as the function which iterates its argument $n$ times.
* For a pair: $(x,y)$ is represented as a function which applies its argument to $x$ and $y$.
* For a sum: $\mathrm{in}\_i(x)$ is represented as a function which applies its $i$th argument to $x$.
* For a list: $\[x\_1,\ldots,x\_n\]$ is represented as a function that takes two arguments, the value to return for the empty list and the function to apply to cons cells.

In general terms, the data structure is represented as its fold function. This is a general concept for data structures: a fold function is a higher-order function that traverses the data structure. There is a technical sense in which fold is universal: all “generic” data structure traversals can be expressed in terms of fold. That the data structure can be represented as its fold function shows this: all you need to know about a data structure is how to traverse it, the rest is an implementation detail.

# Answer
> 2 votes
You can represent sum types as product types with tags and values. In this case, we can cheat a bit and use one tag to represent null or not, having the second tag representing the head/tail pair.

We define booleans in the usual way:

```
true = λi.λe.i
false = λi.λe.e
if = λcond.λthen.λelse.(cond then else)

```

A list is then a pair with the first element as a boolean, and the second element as a head/tail pair. Some basic list functions:

```
isNull = λl.(first l)
null = pair false false     --The second element doesn't matter in this case
cons = λh.λt.(pair true (pair h t ))
head = λl.(fst (snd l))   --This is a partial function
tail = λl.(snd (snd l))   --This is a partial function

map = λf.λl.(if (isNull l)
                 null
                 (cons (f (head l)) (map f (tail l) ) )

```

---
Tags: lambda-calculus, type-theory, type-inference
---


# Question
Title: Genetic algorithm: What is the expected number of strings that are explored?
My question concerns genetic algorithm searching along bit strings.

Given:

* $N$ = population size
* $l$ = length of bit strings
* $p\_c$ = probability that a single crossover occur (double crossover never occur)
* $p\_m$ = probability for a given bit that a mutation occur

$w(x)$, the fitness function is equal to the number of 1 in the strings. Therefore, the fitness can take any integer value between 0 and $l$ (the length of the strings).

My question is (three ways of formulating the same question):

* What is the expected total number of possibilities explored in $G$ generations?

or

* What is the expected proportion of the total possibility space (which equals $2^l$) that is explored in $G$ generations?

or

* What is the expected size of the subset of strings that have ever existed in the population during a simulation that last $G$ generations?

Secondary questions:

* How does the frequency distribution - of the total number of possibilities explored in $G$ generation - looks like?
    + is it a normal (Gauss) distribution?
    + Is it skewed?
    + ...

---

I don't quite know how complex is my question. Here are two assumptions that one would like to consider in order to ease the problem.

* one might want to assume that the population at start is not randomly drawn from the possibility space. He could assume that the whole population is made of identical strings (only one instance). For example, the string `000000000` (which length equals $l$).
* one might want to assume that $p\_c = 0$

# Answer
> 3 votes
As I pointed out in the comments, the primary feature of interest for understanding how a genetic algorithm (or evolution, even) explores the fitness landscape is the fitness function. In this case, you specified an extremely simple fitness function with no epistasis. This was a standard assumption for analytical tractability when biology first started out (i.e. most analyses that have Fisher somewhere in the name probably assume no epistasis), but it is seen as less reasonable now. Hence, if your goal was to gain biological intuition, this question will not provide it. Since landscape with epistasis have qualitatively different dynamics.

Finally, you don't specify a selection function, so to give you a heuristic answer I will assume one that has strong selection.

First note, that at any given time, the number of genotypes you explore is bounded above by the trivial bound of $GN$. To start building a better bound, lets look at Wilf & Evans (2010) that analyzed a no-epistasis model under strong selection is a sexual population (i.e. with recombination). They showed, that it converges to equilibrium (the all $1$s string in your case) in $\Theta(\log l)$ (they actually showed a tighter characterization with a careful analysis of radix-sort, but I will leave that exploration upto you) generations (I think we have to assume that $N \in \omega(l)$). Thus, you will reach the peak very quickly.

On the way to the peak, you will explore $O(N \log l)$ genotypes. In fact, if the selection strength is very high, then we can assume that the population remains close-to monomorphic in terms of the phenotype specified as "number of ones in the genome" although polymorphic in terms of the genotype. This can give us a bound of about $O(l^2 \log l)$.

Once you reach the peak, strong selection will keep you there, and any mutants will go extinct after each generation. This means that from there on out, the population will just stay at the string $1^l$ with transient (single-generation) mutants of Hamming-distance one.

This gives us a pretty ridiculous bound $\min (O(GN), O(l^2 \log l))$. In other words, as long as you look at generations $G \in \Omega(\log l)$ you will only end up sampling an exponentially small fraction of the genome space $O(\frac{l^2 \log l}{2^l})$.

# Answer
> 0 votes
Unless the search space is small, the probability of hitting a genome that already has appeared can be neglected. In that case, all you need to do is to compute how many new individuals are created each generation.

---
Tags: algorithms, optimization, average-case, genetic-algorithms
---


title: Bubble sort complexity

text:
# Question
Title: Bubble sort complexity
So I have this code:

```
  done <- false                                     [1]
  n <- 0                                            [1]
  while (n < a) and (done = false)                  [(n+1)(1+1+1)]
    done <- true                                    [n]
    for m <- (a- 1) downto n                        [n(1+1+1+1)]
       if list[m] < list[m - 1] then                [n]
         tmp <- list[m]                             [n]
         list[m] <- list[m-1]                       [n]
         list[m - 1] <- tmp                         [n]
         done <- false                              [n]
       n <- n + 1                                   [1]
  return list                                       [1]

```

Am I doing this right? My conclusions are that the inne for-loop runs (n^2 + n) / 2 times and the outher while-loop runs n+1 times. I don't know how to properly argue for that the bubble sort has the complexity O(n^2)

# Answer
There is just one loop in `for`, so the number of steps here will be proportional to `n` not n^2. The outer loop is running in a `n` proportional number of steps too. So The complexity of your algorithm is `n^2`.
***N.B.*** : When speaking complexity, you don't have to state `(n^2 + n) / 2`,just say n^2 because they are the same for big `n`s.
> -2 votes

---
Tags: algorithm-analysis, asymptotics, runtime-analysis, loops
---


title: Detecting overflow in summation

text:
# Question
Title: Detecting overflow in summation
Suppose I am given an array of $n$ fixed width integers (i.e. they fit in a register of width $w$), $a\_1, a\_2, \dots a\_n$. I want to compute the sum $S = a\_1 + \ldots + a\_n$ on a machine with 2's complement arithmetic, which performs additions modulo $2^w$ with wraparound semantics. That's easy — but the sum may overflow the register size, and if it does, the result will be wrong.

If the sum doesn't overflow, I want to compute it, and to verify that there is no overflow, as fast as possible. If the sum overflows, I only want to know that it does, I don't care about any value.

Naively adding numbers in order doesn't work, because a partial sum may overflow. For example, with 8-bit registers, $(120, 120, -115)$ is valid and has a sum of $125$, even though the partial sum $120+120$ overflows the register range $\[-128,127\]$.

Obviously I could use a bigger register as an accumulator, but let's assume the interesting case where I'm already using the biggest possible register size.

There is a well-known technique to add numbers with the opposite sign as the current partial sum. This technique avoids overflows at every step, at the cost of not being cache-friendly and not taking much advantage of branch prediction and speculative execution.

Is there a faster technique that perhaps takes advantage of the permission to overflow partial sums, and is faster on a typical machine with an overflow flag, a cache, a branch predictor and speculative execution and loads?

(This is a follow-up to Overflow safe summation)

# Answer
You can add $n$ numbers of size $w$ without any overflow if you are using $\lceil \log n\rceil + w$ bits arithmetic. My suggestion is to do just that and then check if the result is in the range. Algorithms for multiprecision arithmetic are well-known (see TAOCP section 4.3 if you need a reference), there is often hardware support for addition (*carry* flag and *add with carry* instruction), even without such support you can implement it without data dependant jump (which is good for jump predictors) and you need just one pass on the data and you may visit the data in the most convenient order (which is good for cache).

If the data doesn't fit in memory, the limiting factor will be the IO and how well you succeed in overlapping the IO with the computation.

If the data fit in memory, you'll probably have $\lceil \log n\rceil \leq w$ (the only exception I can think of is 8-bits microprocessor which usually have 64K of memory) which means you are doing double precision arithmetic. The overhead over a loop doing $w$-bits arithmetic can be just two instructions (one to sign extend, the other to add with carry) and a slight increase of register pressure (but if I'm right, even the register starved x86 has enough registers that the only memory access in the inner loop can the data fetch). I think it is probable that an OO processor will be able to schedule the additional operations during the memory load latency so the inner loop will be executed at the memory speed and thus the exercise will be one of maximising the use of the available bandwidth (prefetch or interleaving techniques could help depending on the memory architecture).

Considering the latest point, it is difficult to think of other algorithms with better performance. Data dependant (and thus not predictable) jumps are out of question as are several passes on the data. Even trying to use the several cores of today's processor would be difficult as the memory bandwidth will probably be saturated, but it could be an easy way to implement interleaved access.
> 3 votes

# Answer
On a machine where integer types behave as an abstract algebraic ring \[basically meaning that they wrap\], one could compute the sums of item\[i\] and (item\[i\] \>\> 16) for up to about 32767 items. The first value would give the lower 32 bits of the correct sum. The latter value would yield bits 16-47 of something close to the correct sum, and using the former value it may be easily adjusted to yield bits 16-47 of the exact correct sum.

Pseudocode would be something like:

```
Sum1=0 : Sum2 = 0
For up to 32768 items L[i] in list
  Sum1 = Sum1 +L[i]
  Sum2 = Sum2 +(L[i] >> 16) ' Use sign-extending shift
Loop
Sum1MSB = Sum1 >> 16 ' Cannot use division of numbers can be negative--see below
Sum2Mid = Sum2 and 65535
Sum2Adj = Sum1MSB - Sum2Mid
If Sum2Adj >= 32768 then Sum2Adj = Sum2Adj - 65536
Sum2 += Sum2Adj

```

After the above code, Sum2 and Sum1 together should yield the correct sum, regardless of intervening overflows. If it's necessary to total more than 32768 numbers, they may be divided into groups of 32768, and after computing Sum2 for each group, one can add it to a two-variable "big sum" for all the groups as a whole.

In some languages, the shift right operator could be replaced by a division by 65536. That generally work when computing Sum2, but not when extracting Sum1MSB. The problem is that some languages round divisions toward zero while it's necessary here to perform a division rounding to the next lower number (toward negative infinity). Errors computing Sum2 would get corrected later on, but errors computing Sum2LSB would affect the final result.

Note that nothing in the final results would indicate whether any of the computations involving Sum1 had "overflowed", but if values are guaranteed to wrap cleanly code shouldn't need to care about whether any overflow had occurred.
> 1 votes

---
Tags: algorithms, arrays, integers, numerical-analysis
---


# Question
Title: Why does induction with big-O lead to paradoxes?
For example, say I want to analyze $T(n)=3T(\lfloor n/3 \rfloor )+2n$ for $n\>2$, and $T(n)=1$ otherwise. This is clearly $O(n\log n)$; however it seems that with induction you can prove it is $O(n)$:

Base case: $T(1)$ is $O(1)$, $T(2)$ is $O(2)$

Inductive step: $T(n) = 3\times O(n/3) + 2n \in O(n)$

Where does this go wrong? Why can I do this? Induction clearly is a valid technique, but what subtlety of $O$ causes me to be able to prove a wrong bound?

# Answer
> 2 votes
You have to carry around the big-O constant. Suppose that we are trying to prove that $T(n) \leq Cn$. In the inductive step, we have $$ T(n) \leq 3C\lfloor n/3 \rfloor + 2n \leq (C+2)n. $$ So we are not able to maintain the constant $C$. Let's have another go, with $T(n) \leq C\_nn$. The argument above shows that we can put $C\_n = C\_{\lfloor n/3 \rfloor} + 2$, and so $C\_n = O(\log n)$ works, and we get the correct asymptotics $O(n\log n)$. (To know that this is tight, we would also need a lower bound, proved in much the same way, with some minor technicalities stemming from the floor.)

---
Tags: asymptotics
---


# Question
Title: How DMA improves I/O operation efficiency?
I am reading Computer Architecture & Organization by William Stallings to understand I/O operations. Stallings pretty well explains why Programmed I/O (CPU keeps checking the I/O module register status) & Interrupt I/O (CPU still has to over look data transfer between I/O module & memory) are not efficient & introduces to DMA, where DMA itself handles everything.

But, however, he also mentions that during a DMA operation, CPU sits idle & has no control over memory bus. If CPU has to sit idle, then how it is better than other two methods ?

Page no. 415, Computer Architecture & Orgazination by Morris Mano:

> During the DMA transfer, the CPU is idle and has no control of the memory.

Only way it make sense to me is that, CPU can perform any operation which does not involve memory bus during a DMA operation. So, CPU will not be idle. Or am I missing something ?

I think author has formulated in a bad way. It can be phrased like:

> During DMA transfer, the CPU has no control of memory buses and thus cannot perform any operations involving memory. However it can perform other operations like arithmetic, logical or can operate on data in cache.

Am I right?

# Answer
> 6 votes
The DMA engine doesn't grab the bus for the duration of the whole transfer, only while specific data is being transferred. Yes, that means CPU acces to memory is hampered, but not shut off completely. The CPU can also work with data from its cache in the meantime.

# Answer
> 3 votes
Indeed, the wording of that sentence can lead to false conclusions. "The CPU is idle" actually means that it has no part in the memory transfer and (in principle) is free todo whatever the instructionstream(s) indicate.

While this can be phrased in only a couple of words the effects are tremendous! When the CPU does not do the data transfer, the CPU is not central anymore. This indicates the change in architecture performed by introducing DMA. Further, when there are two communicating entities and neither is the CPU, components will probablby end up competing for resources at some point. In this case they compete for the memory bus. Now the previously unthinkable can happen: the CPU cannot do memory I/O as it pleases and there must be coordination. There are race conditions and system states (and all hell breaking lose *gg*) to consider that couldn't happen before. That's what the second part of the quoted sentence and the following sentence are hinting at.

If a real architecture ever leaves a CPU idle can be doubted, but in principle, if your instruction stream is stored in memory only and the CPU cannot access memory it actually has nothing to do. Jumps can easily point to code that is not in the (rather small) cache and then the CPU indeed has to wait (or take action) for the memory bus to become available again. So Stallings is not wrong at all. He just ships around having to discuss a CPU's options, conditions and corner cases, when the bus is busy.

# Answer
> 1 votes
Historically, there have been a few advantages to DMA:

1. Many processors would require multiple cycles to copy each byte of data from an I/O device to memory, or vice versa. With a 6502, for example, even if one makes some *very* generous assumptions about self-modifying code and memory layout, one would be hard-pressed to manage better than 10 cycles per byte transferred per in any sort of loop. By contrast, DMA hardware would only require two cycles per byte if reads and writes had to occur on separate cycles, or one per byte if the I/O could receive a read request when memory saw a write, or vice versa. Burst DMA hardware may thus outperform optimized code by a factor of 4-10.
2. Some I/O devices require that data be transferred at a rate which is far below the memory bus bandwidth, but still pretty fast (say once every fifty bus cycles). Even if the processor took a few cycles to give up the bus for each DMA request, and such cycles ended up being idle, spending a half-dozen cycles to process each byte would be much better than requiring that the CPU service an interrupt for each byte.
3. Some processors don't need to use the bus on every cycle. If the DMA can be limited to cycles when the CPU isn't otherwise using the bus, it might be possible for it to run without slowing down the CPU at all. Even if that isn't possible, some processors will prefetch code on an as-convenient basis. If a prefetch request is delayed by DMA, but the data still gets fetched before it's actually needed, the DMA request won't end up slowing things down.

Many of today's processors wouldn't have much trouble moving data about as fast as DMA could do it, but the other advantages can still be significant.

---
Tags: computer-architecture, memory-hardware, memory-access
---


title: Computer Music Composition

text:
# Question
Title: Computer Music Composition
I've been looking into computer assisted music composition lately for my school project. While searching for literature I came across GenJam, an interactive jazz improvisation software which uses genetic algorithms to produce musical phrases.

I was wondering If anyone has done some work on computer generated music and could suggest term papers, books or other reading material I should look into.

# Answer
see also eg
> 2 votes

# Answer
Here's some resources that might help you:

The Wikipedia pages on Algorithmic Composition and Computer Generated Music give good overviews.

Wolfram Tones is an online music generation tool based on cellular automata.

David Cope's work, including the 1991 book "Computers and Musical Styles", inspired Douglas Hofstadter.

A well-cited survey paper by Papadopoulo & Wiggins describes different AI methods for algorithmic composition.

"Algorithmic Composition: Paradigms of Automated Music Generation" by Gerhard Nierhaus (2009) is a more modern textbook covering "prominent procedures and classes of algorithms for algorithmic composition."
> 1 votes

---
Tags: algorithms, reference-request, genetic-algorithms
---


# Question
Title: How to show that all 2-terminal SP-graphs are O(log n)-outer-planar
I am trying to show that every 2-terminal SP-graph is $O(\log(n))$-outer-planar for a challenge question on my assignment. In particular, I am trying to prove this by induction on the number of combinations (either a series or a parallel combination). This is what I have so far.

The base case on $0$ combinations is that we just have some edge $(s, t)$. Clearly this is outer-planar and so $O(\log(n))$-outer-planar as well (in this case, $\log(2) = 1$, so this does hold).

Now we do the inductive step. Given some 2-terminal outer-planar graph $G = (V, E)$, we will show that it is $O(\log(n))$-outer-planar, where $|V| = n$. Since $G$ is a 2-terminal outer-planar graph, it was either the result of combining two graphs $G\_1$ on $n\_1$ vertices and $G\_2$ on $n\_2$ vertices by series or by parallel. So we have two cases two consider.

The first case is when $G\_1$ and $G\_2$ were combined by series. By induction, $G\_1$ is $O(\log(n\_1))$-outer-planar and $G\_2$ is $O(\log(n\_2))$-outer-planar. Since $G$ was combined by series, it has $n = n\_1 + n\_2 - 1$ vertices, where $n\_1, n\_2 \ge 2$. Let $n\_0 = \max(n\_1, n\_2)$. Then $G$ is $O(\log(n\_0))$-outer-planar since we have not added any layers to $G\_1$ or $G\_2$ by combining them. It follows that $G$ is $O(\log(n))$-outer-planar since $n\_0 \le n$.

In the second case, $G\_1$ and $G\_2$ are combined in parallel, meaning that $G$ has $n = n\_1 + n\_2 - 2$ vertices. Again by induction, $G\_1$ is $O(\log(n\_1))$-outer-planar and $G\_2$ is $O(\log(n\_2))$-outer-planar. However, this time we cannot conclude that the number of layers around $G$ is the same.

This is where I am stuck. I understand that we are at-most doubling the amount of vertices in $G$ by combining them in parallel, but I don't know how to use that to argue that the number of layers in $G$ is $O(\log(n))$. Any help would be appreciated since I've been stuck on this for several days now.

**EDIT**: Now that the deadline has passed for my assignment, I would love to have a solution so that I can prepare for my midterm exam (solutions to bonus/challenge problems are never posted).

## Terminology

**Series-parallel graphs (SP-graphs)** are constructed in the following way. A *two-terminal* graph is a graph with two distinguished nodes $s,t$. A single edge connecting $s$ and $t$ is an SP-graph. If $(G\_1,s\_1,t\_1)$ and $(G\_2,s\_2,t\_2)$ are two SP-graphs, then their *serial* composition is an SP-graph, and their *parallel* composition is an SP-graph. The serial composition is obtained by identifying $t\_1$ with $s\_2$; the new terminals are $s\_1$ and $t\_2$. The parallel composition is obtained by identifying $s\_1$ and $s\_2$, and $t\_1$ and $t\_2$; the new terminals are $s\_1=s\_2$ and $t\_1=t\_2$. SP-graphs are the minimal class of graphs generated by these operations. See Wikipedia for more on this class.

**$k$-outerplanar graphs:** A planar embedding (i.e. an embedding without crossings) is $1$-outerplanar if all of the vertices belong to the unbounded face. For $k \gt 1$, a planar embedding is said to be $k$-outerplanar if removing the vertices on the outer face results in a $(k − 1)$-outerplanar embedding. A graph is $k$-outerplanar if it has a $k$-outerplanar embedding.

# Answer
> 1 votes
The idea of the proof is to come up with a parameter of graphs $f(G)$ satisfying the following properties:

1. The outerplanarity of $G$ is $O(f(G))$.
2. If $G$ is the (serial or parallel) composition of two graphs $G\_1,G\_2$, then $$ f(G) \leq \begin{cases} \max(f(G\_1),f(G\_2)) & \text{if } f(G\_1) \neq f(G\_2), \\ \max(f(G\_1),f(G\_2)) + O(1) & \text{if } f(G\_1) = f(G\_2). \end{cases} $$

If we are able to construct such a parameter, then your result follows (exercise). It could be that outerplanarity itself satisfies these axioms, but this is not clear. I was able to construct another parameter $f(G)$ which does satisfy these properties, and is very similar to the outerplanarity of $G$. Can you?

---

Here is my solution. For a two-terminal graph $G$, let $F(G)$ be the result of adding an extra edge connecting both terminals, and define $f(G)$ to be the outerplanarity of $F(G)$, when the extra edge is forced to be on the outer face. Clearly the outerplanarity of $G$ is at most $f(G)$.

It is easy to see that if $G$ is the serial composition of $G\_1,G\_2$ then $f(G) = \max(f(G\_1),f(G\_2))$. Now suppose that $G$ is the parallel composition of $G\_1,G\_2$. It is easy to see that $f(G) \leq \max(f(G\_1),f(G\_2)) + 1$. This is not good enough, however: we need to show that when $f(G\_1) \< f(G\_2)$, then $f(G) = f(G\_2)$ (without the $+1$). To that end, take a "good" planar embedding of $F(G\_2)$ (with outerplanarity $f(G\_2)$), and replace the extra edge with a copy of a "good" planar embedding of $F(G\_1)$ (with outerplanarity $f(G\_1)$). The result is a planar embedding of $F(G)$ with outerplanarity $f(G\_2)$.

---
Tags: graphs
---


title: Indentation based Grammars

text:
# Question
Title: Indentation based Grammars
Considering programming languages with significant whitespace for indentation, such as Python or Haskell. How does this whitespace fit into the grand schemes of programming language grammars.

I can see that a "preprocessor" can convert indent changes into tokens which are then handled in grammars, yet can one also perform the parsing based upon a single grammar without changing the intrinsic complexity of the 2nd grammer?

# Answer
> 3 votes
Any modern compiler consists of multiple phases, at least

1. lexing,
2. (context-free) parsing and
3. target code generation.

Additional phases are static analysis (names, types, ...) and optimisations. Each phase uses the result of the prior as input.

Now, the lexer processes the actual program text and transforms it into a token stream. For instance, the (sub)string `"abc"` becomes a token `StringLiteral("abc")`, `if` becomes `IF` and `myMethod` becomes `Identifier("myMethod")`. Tokens typically hold additional information, e.g. their position in the original program text. The context-free grammar used for syntax parsing is expressed in terms of these tokens, usually ignoring their parameters.

At this point, it should be clear that handling whitespace is nothing crazy: instead of dropping all whitespace (like a Java compiler would do), you could as easily lex the strings `" "` or `\t` to a token `Indentation` used in the grammar.

---
Tags: formal-grammars, compilers, parsers
---


# Question
Title: Solving the part-of-speech tagging problem with HMM
There is a famous part-of-speech tagging problem in Natural Language Processing. The popular solution is to use Hidden Markov Models.

So that, given the sentence $x\_1 \dots x\_n$ we want to find the sequence of POS tags $y\_1 \dots y\_n$ such that $y\_1 \dots y\_n = \arg\max\_{y\_1 \dots y\_n}p(Y,X)$.

By Bayes Theorem, $P(X,Y)=P(Y)P(X \mid Y)$.

Solving POS by HMM implies the assumptions: $p(y\_i \mid y\_{i-1})$ and $p(x\_i \mid y\_i)$.

The question is there are any particular reason why we prefere to solve it by generative model with a lot of assumption and not directly by estimating $P(Y \mid X)$, given the training corpus it's still possible to estimate $p(y\_i \mid x\_i)$.

The second question, even when we convinced that the generative model is preferred why to calculate is as $P(Y,X)=P(Y)P(X \mid Y)$ and not $P(X,Y)=P(X)P(Y \mid X)$. In case we have an appropriate generative story I can use $P(X,Y)=P(X)P(Y \mid X)$ as well, is it mentioned somewhere that assumed generative story is preferred.

# Answer
> 2 votes
Isn't this exactly the same question you asked previously? I'll make some additional comments and add some links here. Hopefully that will help.

> is there are any particular reason why we prefere to solve it by generative model with a lot of assumption and not directly by estimating $P(Y∣X)$, given the training corpus it's still possible to estimate $p(y\_i∣x\_i)$?

It just depends. Choosing whether to model $P(X,Y)$ or $P(Y|X)$ is simply the choice of generative versus discriminative. Both have advantages. See the paper On Discriminative vs. Generative classifiers by Ng and Jordan. One thing worth mentioning, that I didn't say last time, is unsupervised learning in a generative framework is normally straightforward. This means it is also fairly obvious how to do semi-supervised learning. Semi-supervised learning can be very helpful for NLP tasks where the amount of unlabeled data is essentially infinite and labelled data is hard to obtain. Semi-supervised learning is typically not as easy in a discriminative framework. See Co-training as an example of the later.

As for how one decomposes the joint, well that's up to you. There's no rule saying you cant decompose it as $P(X,Y) = P(X)P(Y|X)$. Doing so would be perfectly valid, just not sensible. Notice decomposing the joint this way includes the factor $P(Y|X)$ already. If you're ultimately interested in predictiong $Y$ given $X$, then you should should predict $$ \begin{align\*} \arg\max\_y P(Y=y,X=x) &= \arg\max\_y P(X=x)P(Y=y|X=x) \\ &= \arg\max\_y P(Y=y|X=x). \end{align\*} $$ So you just use $P(Y|X)$ and ignore $P(X)$ and we're back at a discriminative classifier.

---
Tags: machine-learning, natural-language-processing, hidden-markov-models
---


title: Functional Dependencies and BCNF

text:
# Question
Title: Functional Dependencies and BCNF
Consider the following schema:  `Students(Id, Name, AdvisorId, AdvisorName, FavouriteAdvisorId)`

What are the functional dependencies here? Ir seems that it would be:

`Id --> Name AdvisorId AdvisorName FavouriteAdvisorId`

If we know the student id then we know his name, his advisor, his advisor id and his favouriteadvisorid. But the correct functional dependencies given are:

`Id ---> Name FavouriteAdvisorId`

`AdvisorId ---> AdvisorName`

Why is this?

# Answer
> 1 votes
Perhaps because a student with two majors might have an advisor in each department, so the ID wouldn't uniquely determine the advisor (and hence the AdvisorID and, perhaps, the AdvisorName). Remember, the definition of $A\rightarrow B$ is that if two tuples in the relation have the same value for attribute $A$, they must have the same value for attribute $B$.

# Answer
> 0 votes
i am trying it out:

Lets make it simple-

## R(A,B,C,D,E)

```
    A-> B E
    C-> D

```

So according to the correct FD: A,C is not getting derived in RHS, so you can consider AC to be the Candidate key.So, combine them,you can derive the rest data in the relation.So, u can break the relation as :

```
   R1(A,B,E)
   R2(C,D)

```

Its BCNF as def: x-\>a , x should be a super key. So in both the FD , LHS is a super key/candidate key.

Now, your case

why not:

```
    A-> B C D E

```

you can think its in BCNF, but the basic criteria of FD is canceled. as:

```
  A    B          C    D             E

  A1  SAM WATSON  C1   PETER PARKER  C1
  A1  SAM WATSON  C2   BRUCE WAYNE   C1

```

a Student can have exactly 2 different advisers.

ATD: x-\> a = x is functionally dependent to a if the value of a can uniquely identify x.But in the above example its violated,A1 derives 2 different combination .

Now if break it in my way:

```
 A   B           E
 A1  SAM WATSON  C1

 C  D
 C1 PETER PARKER
 C2 BRUCE WAYNE

```

but the decomposition is not Loss-less(lossy), as there is no common attribute to unite the tables. if i try to add :

```
 A  C
 A1 C1
 A1 C2

```

so the FD definition is again violated.

Thats it! I've ried my best, i am still the beginner so if i've made any mistake please point it out, i would love to learn from it.

---
Tags: database-theory
---


# Question
Title: Computation tree logic and Kripke structures
Specifications in Kripke structures are verified by Computation tree logic (CTL). However, refering to this Wikipedia article the CTL-operators are relative to a *current state*. So, when we want to verify if `EF q` is satisfied in a Kripke structure

Do we only need to check if `EF q` holds starting from the starting state oder do we need to check if `EF q` holds starting from every state?

# Answer
> 3 votes
CTL formulas are always evaluated from the starting state of the Kripke structure. Indeed, CTL stands for computation *Tree* logic, and the tree in question is the unwinding of the Kripke structure, starting from the initial state.

If you want to specify that $EF q$ should hold from every (reachable) state, that can be specified as $AGEFq$, which is still a CTL formula.

---
Tags: logic, model-checking, temporal-logic, computation-tree-logic
---


# Question
Title: Until quantifier of Computation Tree Logic
It's quite a short question: Refering to this Wikipedia article `p U q` means, that *`p` has to hold at least until at some point `q` holds*.

So, does it mean:

1. On each path starting from the current state `p` has to hold in each state until a state is reached in which `q` holds.
2. On each path starting from the current state `p` has to hold in any state before a state is reached in which `q` holds.

**Example**: Suppose `p` holds in `s3` and `q` holds in `s5`. Let `s0` be the starting state and the set of edges given by `{ (s0,s1),(s1,s2),(s2,s3),(s3,s4),(s4,s5) }`. Let's assume `p` and `q` don't hold in all the other states. Is `p U q` satisfied, starting from `s0`?

# Answer
> 3 votes
$pUq$, as is, is not a well-formulated CTL (or more generally - CTL\*) formula. A CTL\* formula is a *state* formula, which starts with has a path quantifier ($A$ or $E$).

$pUq$ is a *path* formula, which means it refers to a single (linear) computation. A computation satisfies $pUq$ if $p$ holds in every state until $q$ holds (and $q$ must hold at some state).

Translating to CTL, you can talk about two different formulas: $ApUq$ and $EpUq$. The former is true in a state if every path starting from this state satisfies $pUq$. The latter is true in a state if there exists such a path starting from that state.

Does that clear things up?

---
Tags: terminology, logic, temporal-logic
---


# Question
Title: Compare asymptotic WC runtime with measured AC runtime
I have an algorithm and I determined the asymptotic worst-case runtime, represented by Landau notation. Let's say $T(n) = O(n^2)$; this is measured in number of operations.

But this is the worst case, how about in average? I tried to run my algorithm 1000 times for each $n$ from $1$ to $1000$.I get another graph which is the average running time against $n$ but measured in real seconds.

Is there any possible way to compare these figures?

# Answer
> 4 votes
You can't, not really, for three reasons:

1. Number of operations and runtime do not compare well; too many factors (typically) left out in analysis influence actual runtime.
2. Asymptotic results (which hold in the limit) and a finite sets of observations do not compare.
3. Landau classes don't compare with "exact" functions. For instance, if you have $f \in O(n^3)$ and $g(n) = 3n^2$, you have no idea which grows faster.

All hope is not lost, though. With some additional work you can get to reliable statements.

* Perform an (asymptotic) average-case analysis. That is, assume a random distribution on the input set and calculate the expected number of executed operations. That can be tough, but if you succeed you can compare the result to your worst-case asymptotic. (Note that you may need $\Theta$ to make meaningful statements.)
* If you can, improve your analysis to yield constant factors (not only $\Theta$). That way, you can separate, say, a $2n^2 + 5n$ worst-case from $1.5n^2 - 3 \log n$ average-case.
* Run the program for worst-case instances (you should know them from your WC-analysis) and compare the real measurements with the average case.

*Note:* This can only provide guesses for asymptotic behaviour.
* Alternatively, run the program average and worst-case instances but *count statements*. That gives you more reliable measurements and removes platform-dependent artifacts from consideration. Still, you get only guesses for asymptotics.

Bottom line, you have to have the same "kind" of statement for both worst- and average-case if you want to compare them.

---
Tags: algorithm-analysis, asymptotics, runtime-analysis, average-case
---


# Question
Title: Starvation in longest remaining time first CPU scheduling
I want to know if longest remaining time first (LRTF) CPU scheduling has starvation or not. Also give reason how it starve/does not starve a process.

I know longest job first (LJF) may starve a process if all other incoming processes have longer CPU burst.

# Answer
> 1 votes
**TLDR: Starvation is possible under some assumptions.**

Without loss of generality let's assume that in tie situation of longest remaining time first (LRTF) algorithm we give CPU time to process with lowest ID.

Let's also assume that incoming processes IDs are always increasing.

Now let's consider two cases.

**1) At some time there will be no new processess.**

This is obvious because once new processess will stop arriving then eventually all processess will be executed, so no starvation.

**2) New processess will never stop arriving.**

Let's say that at time 0 all max time of process is $d$. In other words: $d=\max\_{p\in\mathcal{P}}(t\_p)$. Where $\mathcal{P}$ is set of processess and $t\_i$ it remaining time of $i$'th process.

So now let's consider following scenario:

Adversary knows $d$ and that at time 0 there are $n$ processess, at each time unit adversary inserts new process with time $d+1$.

At time $1$ one of processess numbered $1...n$ (the one with time $d$) will consume one time unit. Then new process will arrive with time $d+1$ it will gain one time unit from scheduler. From now no of processess $1...n$ will gain CPU time, because all adversary processess will remain $d$ time units and newly arrived process will have prority over another.

There is on problem with this analysis. It assumes that there can be infinite number of processess in the system. In real operating systems this cannot be achieved.

Now let's assume that adversary doesn't know $d$. He might choose some constant $k\>2$ and insert it's processess with that time. At some point in time which is equal to $\sum^{n}\_{i=1}{\max(0, k-t\_i)}$ adversary processess will starve all other procesess.

---
Tags: operating-systems
---


title: How do GPUs compute sines?

text:
# Question
Title: How do GPUs compute sines?
I've been wondering lately how GPUs compute sines and cosines, and Google hasn't helped me finding a precise answer.

Initially, I was thinking that in order to make the computations as fast as possible, the GPU would use some kind of lookup table. But then I realized, storing all sin values in a table of the range of doubles between \[0, 2 * pi\] would be a massive one, and thus not be a valid option.

The table could possible be shrunk down in resolution, and the missing values for a lookup can then be lerped. This however, introduces a possible error which can propagate to bigger and unacceptable errors when performing the computation multiple times.

My last idea is then that they could be using a Taylor approximation, but that would involve quite some arithmetic, which may be too slow for a GPU. So the question is, what do GPUs use to calculate the sines? Are it lookup tables, approximations, or a hybrid of both? And possible, do they use the same method for other computations like sqrt()?

# Answer
> 12 votes
I believe that NVidia GPUs they use a table lookup, followed by a quadratic interpolation. I think they are using an algorithm similar to the one described in: Oberman, Stuart F; Siu, Michael Y: "A High-Performance Area-Efficienct Mutlifunction Interpolator," \_IEEE Int'l Symp Comp Arithmetic, (ARITH-17):272-279, 2005.

The table lookup is indexed with the $m$ most-significant bits from the input, $x$, and returns three coefficients, $c\_0$, $c\_1$, $c\_2$. The final result is produced by evaluating $c\_0 + c\_1 x + c\_2 x^2$. The coefficients for each range of $x$ are chosen to minimize the maximum error from the target function over that range.

So that the unit can be fully pipelined to produce one result per cycle the unit contains a special squaring unit and two booth-encoded wallace-tree multipliers. For each special function they choose the number of table entries ($2^m$) so that the polynomial evaluation will give them a single-precision IEEE FP answer correct to within a couple of units in the last place.

---
Tags: approximation, arithmetic
---


# Question
Title: When does the IEEE-754 64-bit float break as a counter
As a matter of curiosity I've been trying to determine at what point a 64-bit float no longer reflects the addition of 1 as expected; that is, at what point the digits as printed do not correspond to the digits of a 64-bit integer that is incremented in sync.

Around 1e15 I can continually add 1 or subtract 1 and the result seems right. At 1e16 the addition or subtraction of 1 has no effect on the value as printed. However, 1e16 - 2 gives 9.999999999999998e+15 (at least, as printed by go's fmt package).

I wonder whether there are discontinuities in the sequence of sums of n+=1 while n \< 1e15. At what point does n+=1 no longer produce a result corresponding to the expected integer?

# Answer
IEEE floating point format has a sign bit, an 11 bit exponent (ranging from -1022 to 1023) and a 52-bit mantissa with an implicit "1" in the 53rd bit.

Thus, the largest integer that can be represented without rounding is the binary number with 53 "1"s, $2^{53}-1$ = 9,007,199,254,740,991 ~ 9e15 \< 1e16. After that you start having to round off low order bits. So it looks like your experiment produced the right order of magnitude.
> 5 votes

---
Tags: floating-point, counting
---


# Question
Title: Mapping reduction to show NeverHalt is undecidable
I need help with showing that $$NeverHalt\_{TM} = \\{\langle M\rangle \mid \text{$M$ is a TM which runs forever on every input $w$}\\}$$ is undecidable by giving an explicit mapping reduction.

To show that a language reduces to any other language we must show that yes-instances are mapped to yes-instances and no-instances are mapped to no instances. We need to find a TM whose language will "help" us solve $NeverHalt\_{TM}$, given $\langle M\rangle$.

I am not really sure where to go from here or in general how to proceed with undecidability problems.

# Answer
> 2 votes
You will not prove that $NeverHalt\_{TM}$ is undecidable by "finding a TM whose language will "help" us solve" it. This would actually prove the opposite, if $M$ is a TM deciding some language.

You have to suppose $NeverHalt\_{TM}$ to be decidable by a turing machine $D$, and show that with its help you can decide other non-recursive language. In other words, you have to pick a suitable undecidable language and reduce it to $NeverHalt\_{TM}$. There is a reduction from the emptiness problem for turing machines : $E\_{TM} = \\{\left \< M \right \>\ :\ \mathcal L(M) = \varnothing \\}$.

# Answer
> 1 votes
You can reduce the $MP= \\{\langle M,w \rangle : w \in L(M)\\}$ to $NeverHalt$

For a given string $\langle M,w \rangle $ you construct the following machine $F$:

```
For input x:
  Simulate M for input w
    if it accepts, loop
    if it rejects accept x

```

Now you can see that $\langle M,w \rangle \in MP \iff \langle F \rangle \in NeverHalt$

---
Tags: computability, reductions, undecidability
---


title: Is this grammar LR(1)

text:
# Question
Title: Is this grammar LR(1)
I am reading parser chapter from dragon book and I found a grammar over there -

$ S \rightarrow L=R $

$ S \rightarrow R $

$L \rightarrow \*R $

$L \rightarrow id $

$R \rightarrow L $

Now I have created some of its items, not sure if they are correct -

$ I\_{0} $

$S' \rightarrow .S ; \\$ $

$S \rightarrow .L=R ; \\$ $

$S \rightarrow .R ; \\$ $

$ L \rightarrow .\*R; \\$/= $

$ L \rightarrow .id; \\$/= $

$ R \rightarrow .L; \\$ $

$ I\_{1} $

$ S' \rightarrow S.; \\$ $

$ I\_{2} $

$S \rightarrow L.=R ; \\$ $

$ R \rightarrow L.; \\$ $

Now I2 contains Shift reduce conflict but the lookahead symbol that is appearing is creating doubt I mean how $ can be lookahead symbol to shift `=` sign?

# Answer
> 4 votes
The grammar is LR(1) and LALR(1). It is not, however, SLR(1). The purpose of this example in the Dragon Book is to show a grammar which is LR(1) but not SLR(1).

The items that you've got so far are completely correct. To understand why state $I\_2$ is deterministic, you have to understand what the parser has to do.

The parser has to choose between the following two items:

$S \rightarrow L \cdot = R; \\{ \\$ \\} $

$R \rightarrow L \cdot ; \\{ \\$ \\} $

The first one is a shift of a $=$ symbol which will transfer you to a state with the kernel item $S \rightarrow L = \cdot R; \\{ \\$ \\}$. The second one is a reduce which reduces by the production $R \rightarrow L$.

The lookahead set is what the parser expects to see *after it has read the whole production*, but the dot indicates what the parser expects to see right now. In the case of the first item, it expects to see $=$, then $R$, then $\\$$. When constructing the parser actions, the symbol that you're looking for to do the shift is $=$, because that is the symbol which is shifted.

If the second item's lookahead set contained the symbol $=$, then the shift-reduce conflict would not be resolvable and the grammar would not be LR(1), because it would not be clear which direction to take if the next symbol were $=$.

As it is, the state is deterministic. If the next symbol is $=$, shift it and take the first item. If the next symbol is $\\$$, reduce.

(Warning: The rest of of this is a slight digression.)

As well as deriving the machine by hand, I fed the grammar into a parser generator (I used yacc, you could use Bison, ANTLR etc) just to be certain. If you do this, then you should be aware that production-quality parser generators sometimes take a shortcut by not consulting the lookahead symbol on reduction if they don't have to.

In this case, if you found yourself in state $I\_2$ and the next symbol was $id$, then you may as well reduce, even though you could have detected a syntax error at this point.

There are three main reasons for this.

First, you don't have to check, since the error will eventually be detected when you try to shift the $id$ symbol. Remember, even the LR(0) machine is *correct* for this grammar, it's just *nondeterministic*; what we call a "conflict" in LR-speak we would call "nondeterminism" in other kinds of automata. If the decision is already deterministic, using lookahead information doesn't make it more deterministic.

Second, it's expensive to store and check the lookahead set. Even though computers are big these days, smaller is still better. Saving space is good.

Third, and perhaps most importantly these days, in real parsers, you need to report the syntax error to the user in a way that helps them understand what went wrong. The "bigger" the concept that you can use in the report (e.g. "expression" rather than "lvalue"), the more understandable it is. Reducing before reporting helps with this.

So if you feed this grammar into a production parser generator like ANTLR, Bison, or YACC, you will find that the actions for this state basically say "if you see $=$ then shift and go to state X, otherwise reduce". If you were wondering why they don't consult the lookahead set, that's why.

(Digression ends.)

---
Tags: formal-grammars, compilers, parsers
---


title: Difference between 1* + 0* and (1 + 0)*

text:
# Question
Title: Difference between 1* + 0* and (1 + 0)*
I know that `(1 + 0)*` is the set of all bit strings; but isn't `1* + 0*` the same thing?

# Answer
> 11 votes
The set $1^\*+0^\*$ is composed of two parts: $1^\*$ and $0^\*$. The first part, $1^\*$, is all strings composed entirely of $1$s. The second part, $0^\*$, is all strings composed entirely of $0$s. In contrast, $(1+0)^\*$ is all strings composed of $0$s and $1$s. Can you now think of a string in $(1+0)^\*$ but not in $1^\*+0^\*$?

# Answer
> 0 votes
```
  (1*+0*)= 11.. or 00... but cannot produce 101010101
  (1+0)*= anything with 1 and 0

```

yeah: (1\*+0\*)\* would be a different story.

---
Tags: formal-languages, terminology, regular-languages, regular-expressions
---


title: iterative lengthening search example

text:
# Question
Title: iterative lengthening search example
I am looking for an example of the "iterative lengthening search". I have searched and I was only able to find definitions like

> iterative lengthening search an iterative analog to uniform cost search. The idea is to use increasing limits on path cost. If a node is generated whose path cost exceeds the current limit, it is immediately discarded. For each new iteration, the limit is set to the lowest path cost of any node discarded in the previous iteration

I'd be deeply grateful for an example, that enables me to understand.

# Answer
> 4 votes
Iterative deepening is not actually the same as iterative lengthening, but they're very similar concepts.

In an iterative deepening search (using depth-first), you use the depth (a measure of distance between nodes) as a limiting factor. So, if you're performing an *iterative deepening depth-first search* starting at point *a*, and you set a depth limit of 2, you're asking the algorithm to perform a depth-first search from point *a*, but to **not continue** the depth-first search after you get two points away from your starting point *a*.

e.g.

```
                       a             In our example, the algorithm would never
                      / \            visit point e. It is more than 2 points
                     b   c           away from a (its depth is greater than 2)
                   /
                  d
                 /
                e

```

The algorithm will therefore explore all paths from a that are equal to a length of 2 (do not go deeper than depth 2).

In an iterative deepening search, you slowly increase (*iterate*) the depth at which you limit the search. It tries all paths of length 1 **and then** all paths of length 2 and so on. This means if there's a path of length 1 to a goal that you're trying to find, this algorithm would find it before trying any paths of length 2, 3, 4, et cetera.

Similarly, an iterative *lengthening* search uses the **cost** (or "length") of a path to limit the search rather than the *depth*. This is useful in situations where connections are weighted. The algorithm would explore all possiblities with a cost of 1 or less, then all possibilities of a cost of 2 or less, and so on. For a real-life example, the *cheapest* (cost) way to get somewhere is not always the same as the *simplest* (depth) way to get there. You might have to catch seven buses and a helicopter, but it's cheaper than renting out the Concorde for a single flight. You could consider an iterative deepening search to be a specific case of an iterative lengthening search where you define the "length" that you're iterating as the depth.

# Answer
> 2 votes
Perhaps the simplest example would be to consider DFS as a search algorithm on graphs, but to use iterative lengthening as follows: the cost of each edge is 1, and the cost of a path is the sum over the edges. So we essentially use DFS while limiting the search depth.

If you start from the limit 1 and increase, then you essentially get (sort of) BFS. Indeed, while you do not open nodes layer-by-layer, in iteration $d$ of the DFS you will open all the edges up to distance $d$.

Do you consider this an example, or are you looking for a more concrete/more involved example?

EDIT: Here is a lecture of iterative depth DFS, which includes an example.

---
Tags: artificial-intelligence, search-algorithms
---


# Question
Title: Simple path in a graph, within a given range of lengths
Given an undirected graph $G(V,E)$ and two nodes $s$ and $t$, $s,t\in V$, find a path whose length $L$ is bounded by a lower bound $N$ and an upper bound $M$, $N\leq L\leq M$.

So, for example, $N=4, M=7$, I want to confirm that there is at least one simple path of 4,5,6 and 7 between two nodes in a graph? Nodes of the graph may appear in more than one path.

Typical problem size:

* 10,000 nodes
* Mean of 20 edges per node
* Cycles in graph
* Unweighted edges

# Answer
> 0 votes
A special case of your problem is to determine whether there is a path of length between $n-1$ and $n-1$ (sic) in an $n$-vertex graph. This is the Hamiltonian path problem, which is well known to be **NP**-complete, so your problem is also **NP**-complete. More generally, it's also **NP**-complete to determine if a graph has a path of length at least $k$ (i.e., between $k$ and $n-1$) between two given vertices.

# Answer
> 0 votes
I see this problem pretty close to the target-value search problem:

*Given a graph $G(V,E)$ and a natural number $T$ find the path between the vertices $s, t\in V$ whose cost (or length in case of unary costs) is as close as possible to the given target value $T$*

The latest reference on the question is, as far as I can tell Target-Value Search Revisited which was recently published at the International Joint Conference on Artificial Intelligence ---admittedly, this is a paper of my own, sorry for self-referencing my own work but I do see your question closely related to this other one.

Just invoke the target-value search algorithm with a target value equal to the average $T=\lfloor\frac{N+M}{2}\rfloor$ and there you go, it will find the path with the cost closer to it thus solving your problem. There is only a caveat and it is that if $N+M$ is an odd number the algorithm might prefer a solution with a cost equal to $\lfloor\frac{N+M}{2}\rfloor-\lceil\frac{M-N}{2}\rceil$ instead of $M$ (note that the first term is strictly less than $N$ iff $N+M$ is an odd number), but there are various ways to solve this problem efficiently.

Finally, the algorithm pursues paths with a **cost** as close as possible to the given target value $T$. In case you are interested in the **length** instead, then just provide graphs with unary costs.

In case you are interested I can provide you with source code (in C++) that implements target-value search. I made experiments with graphs as those you mention (but shorter branching factors) and it effectively finds optimal solutions pretty fast (in less than a second). Moreover, if you do not mind, I would be happy to make experiments with your domains in case you have any at hand that you could send me.

Hope this helps,

---
Tags: graphs, graph-traversal
---


title: detect closed shapes formed by points

text:
# Question
Title: detect closed shapes formed by points
I plot several arrays containing xy-coordinates of points (using plot(x,y)) and obtain a plot with some curves. The curves form some very distinctive closed shapes (that is, the points describing the curves lie close to each other).

Now I need to find the (possibly approximate) centers of the closed shapes. Alternatively, it's good to "recognize" the closed shapes and to fill them. I don't know what is easier given the coordinates of points forming the shapes.

A possible example with 3 closed shapes to detect is given below.

Points can be also added along the image's borders, thus, closing all open shapes. Then all "regions" in the figure will be closed, but the question persists.

# Answer
* find all intersections by checking all pairs of segments, belonging to different curves. Of course, filter them before real check for intersection.
* Number all curves 1..n. Set some order of segments in them.
* For every point create a sequence of intersections SOI, so: if it starts from the border end, SOI\[1\] is null. If not, SOI\[1\]= (number of the first curve it is intersecting with, the sign of the left movement on the intersecting curve). Go on, writing down into SOI every intersection - number of curve if there is some, or 0 if it is the intersection with the border.
* Obviously, you are looking only for simple bordered areas, that have no curves inside.
* Pieces of curves between two adjacent non-null intersection points we'll call segments.
* Having SOI for each curve:
    + for segment of the curve 1, starting from the first point of the segment, make 2 attempts to draw a polygon of segments. It is 2 because you can go to 2 sides along the first intersecting curve.
    + For the right attempt, make only left turns, for the left attempt, make only the right turns.
    + If you arrive at point with no segment in the correct direction, the attempt fails. If you return to the curve 1, it success. You have a closed area.
    + Remember all successful attempts
    + Repeat this for all segments of curve 1
    + Repeat this for all other curves, checking all found areas against the already found ones. Two same adjacent segments is enough to consider areas equal.

***Edit: How to find the orientation of the intersection.***

When segment p(p1,p2) crosses segment q(q1,q2), we can count the vector multiplication of vectors pXq. We are interested in only sign of its Z coordinate - that is out of our plane. If it is +, q crosses p from left to right. If it is -, the q crosses p from right to left.

The Z coordinate of the vector multiplication is counted here as a determinant of matrix:

```
0         0          1
p2x-p1x   p2y-p1y    0
q2x-q1x   q2y-q1y    0

```

(of course, it could be written more simply, but it is a good memorization trick)

Of course, if you'll change all rights for lefts, nothing really changes in the algorithm as a whole.
> 1 votes

# Answer
Here you go:

1) Do not draw the axis

2) Do not draw the plots with * but plot it with - .

3) Also plot $y=-0.02$, $x=-0.02$, $x=0.08$ plots. Plot the upper boundary as well.

4) Now take a screen capture. The bigger the plot, the more accurate the result will be.

5) Normalize the image to $0-1$. (Make it logical as in $logical(I)$)

6) Apply connected component labeling (supposedly in matlab using bwlabel etc.) - If you are not familiar with this part, I could elaborate.

Now you have closed shapes as connected binary regions. You can compute the region properties with : http://www.mathworks.com/help/images/ref/regionprops.html

Center and area are just 2 properties of these regions.

7) If you want to paint those regions on the image you could as well do so, since you have every point in the region.

If you don't have the image processing toolbox, then let me put it this way (exactly the same operation):

Sufficiently discretize your grid (adjust grid resolution so that the accuracy is sufficient for you). Each discrete point (a.k.a pixel) will be a node in your grid. Then for all grid locations other than the actual data points, form a connectivity graph (adjacency graph). This will connect the neighboring nodes (Use 4 or 8 connectivity) Then apply Tarjan's strongly connected components analysis to it: http://en.wikipedia.org/wiki/Tarjan's\_strongly\_connected\_components\_algorithm .

At this point, you will end up a component label per each node. This is the same as obtaining the connected components from the image. After that, you could retrieve each discretized point on the grid separately to compute the centroid, area or you can visualize these by label coloring.

Hope this helps. Cheers,
> -2 votes

---
Tags: algorithms, computational-geometry
---


title: Precedence in regular expressions

text:
# Question
Title: Precedence in regular expressions
I'm having trouble finding the language represented by the following:

(AA|BB)\*

Should the expression be read as... ( A (A|B) B ) * or... ( (AA) | (BB) )\*

If that isn't clear, should this produce something like... ABABAB or should it produce AABBAABBBBAA

My guess is that AABBAA is part of the represented language, while AB is not.

# Answer
> -1 votes
This Regular expression $(AA|BB)\*$ can accept any string having two consecutive A's or B's i.e. even number of consecutive A's and even number of consecutive B's. so `AABBAA` is in it but `AB` is not in it.

# Answer
> 6 votes
This depends entirely on convention; with respect to a (proper) formal definition, the expression is invalid as it not properly parenthesised. I'd say that typically, the order is (from stronger to weaker binding)

* Kleene Star/Plus (also finite versions),
* concatenation,
* alternative.

Note that this corresponds (visually) to exponentiation over multiplication over addition in basic arithmetics, so it's probably the natural way.

That is,

* $10^\*1$ is read as $1(0)^\*1$ and
* $10|01|11$ as $(10)|(01)|(11)$.

Note that I still drop parentheses due to associativity of concatenation and alternative.

# Answer
> 0 votes
I think it is :

```
  (AA+BB)* =AABBAABBBBAA

```

if it has to be like starting with A and ending with B concept then probably they would have provided the parenthesis like:

```
   (A(A+B)B)*  =ABABABABB

```

---
Tags: formal-languages, terminology, regular-expressions
---


title: Glue-concatenation v.s concatenation

text:
# Question
Title: Glue-concatenation v.s concatenation
I wanted to give the following as a homework question, but my first few attempts to solve it failed, so now I'm just curios for a solution:

For two words $x,y\in \Sigma^\*$ and for a letter $\sigma\in \Sigma$ we define the *glue-concatenation* of $x\sigma$ and $\sigma y$ to be $g(x\sigma,\sigma y)=x\sigma y$, and for words $w,z$ such that the last letter in $w$ differs from the first letter in $z$, the glue concatenation is undefined.

For languages $A,B\subseteq \Sigma^\*$, we lift the glue operator such that $g(A,B)=\\{g(w\sigma,\sigma z):w\sigma \in A, \sigma z\in B\\}$ (note that we only consider words for which $g$ is defined).

> The question: is it always true that $|g(A,B)|\le |A\cdot B|$?

Observe that trying to prove that if $g(x,y)\neq g(w,z)$ then $xy\neq wz$ will fail, since for example, $g(a,abb)\neq g(aab,b)$, but $a\cdot abb=aab\cdot b$.

# Answer
The statement does not hold.

For $A = \\{a, aaba\\}$ and $B = \\{a, abaa\\}$ we find

$|g(A,B) = \\{a, abaa, aaba, aababaa\\}| = 4 \> 3 = |\\{aa, aabaa, aabaabaa\\}| = |A\cdot B|$.

As a sidenote, I'd say this could actually be a worthwile exercise task, once students are reasonably experienced with standard proof techniques. After all, you only really learn how to attack such problems from practising.
> 3 votes

---
Tags: formal-languages
---


title: Is $a^{n+m}b^{n}c^{m}$ context free?

text:
# Question
Title: Is $a^{n+m}b^{n}c^{m}$ context free?
Language:

$ L = a^{n+m}b^{n}c^{m} $

As per a recent test I gave, this language is not context free.

However, I think it is.

**Corresponding Grammar:**

$ X \rightarrow aXY \space |\space \epsilon $

$ Y \rightarrow b \space | \space c $

**Pushdown Automata:**

Keeping pushing all $a$ to the stack, until a $b$ is scanned. Keeping popping $a$ from stack for each character scanned, until end of input.

If, after the end of input the stack is empty accept the string. Else, go to non-accepting state.

Please let me know if I'm thinking along the right lines or if I've missed something..

# Answer
the corresponding grammar you gave would accept aaaabcbc. A better grammar for this problem would be

$X \rightarrow aXc$

$X \rightarrow aYb$

$X \rightarrow \lambda$

$Y \rightarrow aYb$

$Y \rightarrow \lambda$

where $\lambda$ is empty string.
> 4 votes

# Answer
Hint for constructing a grammar: $a^{n+m} b^n c^m = a^m (a^n b^n) c^m$.

Hint for constructing a PDA: start with a PDA for $a^{n+m} b^{n+m}$.

As a bonus, you can try to solve both parts for the language $\\{ a^{n+m+k} b^n c^m d^k : n,m,k \geq 0 \\}$.
> 3 votes

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