# Question
Title: Why is the Kleene star operator also called the Kleene 'closure' operator?
I've found that if I don't understand the etymology behind a cs/programming term, it usually means that I've missed or misunderstood some important underlying concept.

I don't understand why the Kleene star is also called the Kleene closure. Is it related to closures in programming, a function with bound non-local variables?

... on reflection, maybe it is because it allows an open ended set to be written in a closed expression form?

... well in good old rubber-duck-explaining fashion, I'm now guessing that is it, but would still welcome an authoritative answer.

# Answer
> 18 votes
A set is *closed* under some operator if the result of applying the operator to things in the set is always in the set. For example, the natural numbers are closed under addition because, whenever $n$ and $m$ are natural numbers, $n+m$ is a natural number. On the other hand, the naturals are not closed under subtraction since, for example, $3-5$ is not a natural number.

The *closure* of a set $S$ under some operator is the smallest set containing $S$ that is closed under the operator. For example, the closure of the natural numbers under subtraction is the integers; the closure of the natural numbers under addition is just the natural numbers, since the set is already closed.

So, "Kleene closure" is not an alternative name for "Kleene star". The Kleene star is the operator; the Kleene closure of a set is the closure of that set under the operator.

# Answer
> 7 votes
## In a nutshell

**The name *Kleene closure* is clearly intended to mean closure under some string operation.**

However, careful analysis (thanks to a critical comment by the OP mallardz), shows that the Kleene star cannot be closure under concatenation, which rather corresponds to the Kleene plus operator.

**The Kleene star operator actually corresponds to a closure under the power operation derived from concatenation.**

The name *Kleene star* comes from the syntactic representation of the operation with a star `*`, while *closure* is what it does.

This is further explained below.
**Recall** that closure in general, and Kleene star in particular, is an operation on sets, here on sets of strings, i.e. on languages. This will be used in the explanation.

## Closure of a subset under an operation always defined

A set $C$ is closed under some $n$-ary operation $f$ iff $f$ is always defined for any $n$-tuple of arguments in $C$ and $C=\\{f(c\_1,\ldots,c\_n)\mid \forall c\_1,\ldots,c\_n \in C\\}$.

By extending $f$ to sets of values in the usual way, i.e. $$f(S\_1,\ldots,S\_n)=\\{f(s\_1,\ldots,s\_n)\mid \forall s\_i\in S\_i. 1\leq i\leq n\\}$$
we can rewrite the condition as a set equation:
$$C=f(C,\ldots,C)$$

For a domain (or set) $D$ with an operation $f$ that is always defined on $D$, and a set $S\subset D$, The closure of $S$ under $f$ is the *smallest* set $S\_f$ containing $S$ that satisfies the equation: $S\_f=\\{f(s\_1,\ldots,s\_n)\mid \forall s\_1,\ldots,s\_n \in S\_f\\}$.

More tersely with a set equation, the closure of $S$ under $f$ may be defined by:

$$S\_f \text{ is the smallest set such that } S\subset S\_f \text{ and } S\_f=f(S\_f,\ldots,S\_f)$$

This is an example of least fixed-point definition, often used in semantics, and also used in formal languages. A context-free grammar can be seen as a system of languages equations (i.e. string set equations), where the non-terminal stand for language variables. The least fixed-point solution associate a language to each variable, and the language thus associated to the intial symbol is the one defined by the CF grammar.

## Extending the concept

The closure as defined above is only intended to extend a subset $S$ into a minimal set $S\_f$ such that the operation $f$ is always defined.

As remarked by the OP mallardz, this is not a sufficient explanation, since it will not include the empty word $\epsilon$ in $S\_f$ when it is not already in $S$. Indeed this closure corresponds to the definition of the Kleene plus `+` and not to the Kleene star `*`.

Actually, the idea of closure can be extended, or considered in different ways.

1. **Extension to other algebraic properties**

On way to extend it (though it is no longer called *closure*) considers more generally an extension to a set $S\_f$ having specific algebraic properties with respect to the operation $f$.

If you define $S\_f$ as the smallest set containing $S$ that is a Monoid for the binary function $f$, then you require both closure and a neutral element which is the empty word $\epsilon$.
2. **Extension through a derived operation**

There is a second way which is more properly a closure issue. When you define the closure of $S\subset D$, you can consider it with respect to some of the arguments, while you allow values from the whole set $D$ for the other arguments.

Considering (for simplicity) a binary function $f$ over $D$, you can define $S\_{f,1}$ as the smallest set containing $S$ that satisfies the equation: $$S\_{f,1}=\\{f(s\_1,s\_2)\mid \forall s\_1\in S\_{f,1}\wedge\forall s\_2\in D\\}$$

or with set equations:

$$S\_{f,1} \text{ is the smallest set such that } S\subset S\_{f,1} \text{ and } S\_{f,1}=f(S\_{f,1},D)$$

This also makes sense when the arguments do not belong to the same set. Then you may have closure with respect to some arguments in one set, while considering all possible values for the other arguments (many variations are possible).

Given a Monoid $(M,f,\epsilon)$ $-$ for example the monoid of strings with concatenation $-$ where $f$ is an associative binary operation on the elements of the set $M$ with an identity element $\epsilon$, you can define the powers of an element $u\in M$ as: $$\forall u\in M.\\; u^0=\epsilon\\; \text{ and }\\; \forall n\in\mathbb N\\; u^n=f(u,u^{n-1})$$

This exponentiation $u^n$ is an operation that takes as argument an element of $M$ and a non-negative integer of $\mathbb N\_0$.

However, the natural extension of this operation to subsets of $M$ is not the usual one which would be, for a given value of $n$, $U^n=\\{u^n\mid u\in U\\}$. It should rather take into account the original definition of $u^n$ from the operation $f$, wich would give: $$\left\\{ \begin{array}{l} U^0=\\{u^0\mid u\in U\\}=\\{\epsilon\\}\\ \forall n\in\mathbb N,\\; U^n=f(U,U^{n-1}) \end{array} \right.$$ so as to be consistent with the natural extension of the operation $f$ to subsets of $M$.

Now we can define the closure of $U\_{\wedge,1}$ of $U\subset M$ for the first argument of the power operation, as indicated above with the set notation, as: $$U\_{\wedge,1} \text{ is the smallest set such that } U\subset U\_{\wedge,1} \text{ and } U\_{\wedge,1}=f(U\_{\wedge,1},\mathbb N\_0)$$

And this does give us the the Kleene star operation when the construction is applied to the concatenation operation of the free Monoid of strings.

To be completely honest, I am not sure I have not been cheating. But a definition is only what you make it, and that was the only way I found to actually turn the Kleene star into a closure. I may be trying too hard.
<sub>**Comments are welcome.**</sub>

## Closing a set under an operation that is not always defined

This is a slightly different view and use of the concept of closure. This view is not really answering the question, but it seems good to keep it in mind to avoid some possible confusions.

The above implies that the function $f$ is always defined in the reference set $D$. That may not always be the case. Then closure can also be a mathematical technique to extend a set so than some operation will always be defined. The way it works in practice is as follow:

* start with the set $D$ where $f$ is not always defined;
* build another set $D'$ constructed from elements of $D$, with an operation $f'$ that is always defined, such that you can ...
* show that there is an isomorphism between $D$ and a subset of $D'$ that is such that $f$ is the image of $f'$ restricted to that subset.

Then the set $D'$ with the operation $f'$ is a closed extension of $D$ with $f$.

That is how integers are built from natural numbers, considering the set of pairs of natural numbers quotiented by an equivalence relation (two pairs are equivalent iff the two elements are in the same order and have the same difference).

This is also how rationals can be built from the integers.

And this is how classical reals can be built from the rationals, though the construction is more complex.

# Answer
> 6 votes
Another meaning of *closure*, which is more general than the meaning explained by David Richerby, is any operator $\ast\colon X \to X$ on a poset $X$ that satisfies the following axioms:

1. $x \leq x^\ast$
2. $x \leq y \longrightarrow x^\ast \leq y^\ast$
3. $(x^\ast)^\ast = x^\ast$

The classical example is topological closure, which also satisfies $\bot^\* = \bot$ and $(x \lor y)^\* = x^\* \lor y^\*$, two properties not satisfied by the Kleene star.

The poset in the case of the Kleene star is the poset of all sets of words: $X=2^{\Sigma^\*}$. If $x,y \subseteq \Sigma^\*$ then $x \leq y$ if $x \subseteq y$. The axioms of closure then state that

1. $L \subseteq L^\ast$
2. $L\_1 \subseteq L\_2 \longrightarrow L\_1^\* \subseteq L\_2^\*$
3. $(L^\*)^\* = L^\*$

The Kleene plus operator also satisfies these axioms, so is also a closure operator under this definition.

---
Tags: automata, regular-expressions
---


# Question
Title: Smallest possible integer not obtained from sumset
Given a number N, and some set $A=\\{a, 1\le a\le N\\}$, and let $B=\\{\text{every integer} \in \[1,N\]\\}$, and $C=B\setminus A$ (Set C has all values from B not in A)

What is the best way of finding the smallest number ($S$) that can't be obtained from the sum of any subset of C?

i.e.
if $A=\emptyset$, the smallest number $S= 1+\sum\_1^Nx$,
but if $A\ne \emptyset,\ S\leq 1+ \sum\_1^Nx-\sum\_{i=0}^na\_i$,
However if $N=10,A=\\{2\\}$, then $S=2$, and that is something that I'm not sure how to get efficiently.

I can obviously bruteforce the solution, but I can't find a better way, and I don't know how these kinds of problems are called so that I could Google them.

# Answer
> 2 votes
One possible way is computing the product $$ \prod\_{a \in C} (1+x^a). $$ This is a polynomial $p(x)$. The coefficient of $x^j$ will be non-zero if and only if $j$ can be represented as the sum of some subset of $C$. Therefore, given $p(x)$, you can read off the set of all numbers that are obtainable as the sum of some subset, and then find the smallest that isn't obtainable (i.e., the smallest integer $j$ such that $x^j$ has coefficient $0$ in $p(x)$).

As a bonus, you'll also get the number of possible representations of each number which is representable.

The running time is polynomial in $N$, and doubtless you can optimize the degree of the polynomial. (This is dynamic programming in disguise.)

If you're after an algorithm polynomial in the input length (the input can be either $A$ or $C$), that's a different question. The problem is that the input can be very small; though perhaps such inputs can be handled separately.

---
Tags: combinatorics, number-theory
---


# Question
Title: When should you disable all interrupts in a program?
Consider a machine that has nested interrupts (a higher priority interrupt can interrupt a lower priority one, the current instruction's address is saved and later restored). Why would a programmer want to disable all interrupts using instructions like x86's CLI when you know that even when your code gets interrupted it will always return to what you it was doing?

To me it looks like disabling interrupts is bad for performance because a very high priority and thus very important interrupt has to be dealt with as quickly as possible and you are stalling that by disabling interrupts.

# Answer
> 3 votes
To implement atomic routine like a semaphore, for example. When a thread call routine to gain some critical section acess, the routine needs to change the value of semaphore's variables and it must be atomic. This change cannot be interrupted otherwise other thread, or process, can use or change some values that are under some critical section. You can find more info on Andrew Tanenbaum or William Stallings book.

---
Tags: operating-systems, concurrency
---


# Question
Title: Why is it the lower the h(n) cost the more nodes need to be expanded in A*?
Why is it the lower the h(n) cost the more nodes need to be expanded in A\*?

As found here - http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

> If h(n) is always lower than (or equal to) the cost of moving from n to the goal, then A\* is guaranteed to find a shortest path. **The lower h(n) is, the more node A\* expands, making it slower.**

# Answer
**A\*** expands the search tree by expanding the node for which the past cost ($d(n)$; cost of path from the start point to the node) plus the heuristic value ($h(n)$) is minimum. Because the heuristic $h(n)$ is admissible, $d(n)+h(n)$ is a lower bound on the cost of the path to the goal that may be obtained by expanding the node $n$.

If we have found a path of cost $L$, we can (only) conclude that path is shortest when there are no more nodes for which $d(n)+h(n)\<L$. If there were such nodes then expanding them could possibly give a path of cost $\<L$.

Assume the shortest path has cost $L$. Consider the graph, but restricted to the nodes for which $d(n)+h(n)\<L$. Then the nodes that **A\*** expands are exactly the nodes in the connected component of the start point in this restricted graph.

If we have an alternative heuristic function $h'(n)$ such that for all nodes $n$, $h'(n)\leq h(n)$ then clearly the size of the connected component containing the start point in the graph restricted to nodes where $d(n)+h'(n)\<L$ is greater (or equal to) the size of the same connected component in the graph restricted to nodes where $d(n)+h(n)\<L$ because $d(n)+h'(n)\leq d(n)+h(n)$ for all nodes $n$.

This analysis assumes that there are no other nodes (other than the goal node) for which $d(n)+h(n)=L$, if not this is the case then how many nodes are expanded depends on the tie-breaking order (and we can not say anything useful about that).
> 3 votes

# Answer
Im not completely sure about the hints im giving but i think it makes sense.
Since $h(n)$ is the estimation of min distance (cost) from current node to the goal node so the lower it is the lower effect it has on $f(n)$ which $f(n)=g(n)+h(n)$ so $f(n)$ will rely more on $g(n)$.
As you know if $h(n)=0$ then $A^\*$ will change to Dijkstra's algorithm which checks all nodes. So if $h(n)$ is so small and close to zero it will act like Dijkstra's.
> 0 votes

---
Tags: algorithm-analysis, search-algorithms, heuristics
---


# Question
Title: Detect if a sentence is in passive voice
Given an English sentence, I am looking for a programmatic way to tell whether the sentence is written in passive voice.

Currently, I just check if there is a `was` or `were` inside the sentence. If yes, then the function will say that the sentence is in passive voice (I do no not know even if this is true). Is there a better approach?

---

I just want to make a *simple* detector for passive voice, I do not care much for accuracy and efficiency. Here what I ended up with:

```
// http://english.stackexchange.com/questions/472/how-can-i-reliably-and-accurately-identify-the-passive-voice-in-writing-or-speec

// forms of be, have and get
int auxilary_verb(char* str) {
    if(strstr(str, "be ") || strstr(str, "been ") || strstr(str, "being ") ||
            strstr(str, "have ") || strstr(str, "had ") || strstr(str, "was ") || strstr(str, "were ")
            || strstr(str, "wasn") || strstr(str, "weren") || strstr(str, "got ") || strstr(str, "get ")
            || strstr(str, "getting ")) {
        return 1;
    } else {
        return 0;
    }
}

// past participles of the verbs here http://web2.uvcs.uvic.ca/elc/sample/beginner/gs/gs_10.htm
int past_participle_transitive_verb(char* str) {
    if(strstr(str, "brought ") || strstr(str, "cost ") || strstr(str, "given ") || strstr(str, "lent ")
            || strstr(str, "offered ") || strstr(str, "passed ") || strstr(str, "played ") || strstr(str, "read ")
            || strstr(str, "sent ") || strstr(str, "sung ") || strstr(str, "sent ") || strstr(str, "taught ") || strstr(str, "written ")
            || strstr(str, "bought ") || strstr(str, "get done ") || strstr(str, "left ") || strstr(str, "made ")
            || strstr(str, "owed ") || strstr(str, "paid ") || strstr(str, "promised ") || strstr(str, "refused ") || strstr(str, "shown ")
            || strstr(str, "taken ") || strstr(str, "told ") ) {
        return 1;
    } else {
        return 0;
    }
}

// Once a week, the house is cleaned by Tom. <- passive
// By the end of the week, I'll be gone. <- not passive, but ok.
int contains_by(char* str) {
    return (strstr(str, "by ") != NULL);
}

// how to find No direct object -> I don't know.
// The subject of the verb phrase is the entity undergoing an action or having its state changed -> I don't know.

int passive_voice(char* str) {
    // relax conditions, by applying || isntead of &&
    if(auxilary_verb(str) || past_participle_transitive_verb(str) || contains_by(str)) {
        return 1;
    } else {
        return 0;
    }
}

```

# Answer
detecting passive voice is an AI application also used/ implemented in grammar checker/ correction software with proprietary algorithms. there is a complexity/ accuracy tradeoff. simpler algorithms can be useful and better accuracy requires more sophisticated algorithms. here are two papers on the subject including a masters thesis (60p). final link is an open source implementation of passive voice checking used in OpenOffice.
> 4 votes

# Answer
I recommend you look at methods in the NLP literature for parsing a sentence and identifying its structure, classifying the tense of the sentence and the words present in it, and identifying the subject and object of the sentence. That should help you build a more accurate classifier. If you extract suitable features, given the parse tree, and then apply a suitable machine learning algorithm, you might get a more effective classifier.
> 7 votes

---
Tags: natural-language-processing
---


# Question
Title: Maximum non-intersecting subset of circles
We are given a set of circles, stored by their center points in an array $A$. In particular, the center of the $i$th circle is at coordinates $(A\[i\].x, A\[i\].y)$. All the circles have radius of $k$.

I want to find a subset of circles such that no circles in this subset intersect with each other, such that this subset is as large as possible.

I'm asked to find a way to solve this using a backtracking algorithm. Rather than to do it with brute force, is there a effective way to prune some of the branches?

# Answer
The way I can figure out of is using 3 invariant, 1 stores selected cycles, 1 stores unselected cycles, 1 with unchecked cycles, once you add a disk $n$ from unchecked to selected, you also add the disks overlap with $n$ into the unselected and remove them from checked list, that is a way to do pruning.
> 2 votes

# Answer
If it were me, I would encode this as an instance of ILP (integer linear programming) and let an off-the-shelf ILP solver deal with the backtracking and pruning.

Introduce $n$ variables $x\_1,\dots,x\_n$, where $x\_i=1$ means that you include the $i$th circle in the subset and $x\_i=0$ means you don't include it. Add the following constraints:

* $0 \le x\_i \le 1$, for each $i$: this forces each $x\_i$ to be either 0 or 1.
* $x\_i + x\_j \le 1$, for each pair $i,j$ of circles that intersect each other: this enforces that you cannot choose two overlapping circles.

Now maximize the value of $x\_1+x\_2+\dots+x\_n$ (this is the objective function). Ask an ILP solver to find the optimal solution for you. Internally, the ILP solver will likely use backtracking, pruning, branch-and-bound, and other sophisticated methods.

This will be a very efficient use of your time: rather than trying to program up each of those methods and debug your implementation, you can rely upon an existing well-tested ILP solver. Also, given the amount of effort that has gone into optimizing ILP solvers, this approach might well perform better than any backtracking algorithm you're likely to come up with.
> 3 votes

---
Tags: algorithms, np-hard, backtracking
---


# Question
Title: How to generate a context sensitive grammar for www
I am trying to solve for my exam coming up and have no clue how to generate the grammar for Context sensitive languages for example how do i proceed on this kind of question.

> Give a context-sensitive (not just length-increasing) grammar for $\\{www : w ∈ \\{a, b\\}^⋆\\}$.

Ideas or approaches on how to deal with this kind of questions is much appreciated.

# Answer
Intuitively you want to generate three intermediate symbols at a time, and allow the symbols to sort themselves. Let $S$ be the start symbol. The generation rules are:

$$S \rightarrow S A\_1 A\_2 A\_3$$ $$S \rightarrow S B\_1 B\_2 B\_3$$ The sorting rules are as follows: For symbols $X\_i,Y\_i \in \\{A\_1,A\_2,A\_3,B\_1,B\_2,B\_3\\}$ such that $j \< i$ add the rule: $$X\_i Y\_j \rightarrow Y\_jX\_i$$ In the end we have to turn the intermediate symbols into terminal symbols. Turn the start symbol into another symbol $S\_1$ to end the generation phase. $$S \rightarrow S\_1$$ Push $S\_1$ through the string converting symbols to terminal symbols on the way and increment the subscript when done with one word $w$. For all $i \in \\{1,2,3\\}$ add the rules: $$S\_i A\_i \rightarrow a S\_i \\; | \\; a S\_{i+1}$$ $$S\_i B\_i \rightarrow b S\_i \\; | \\; b S\_{i+1}$$ The subscript of $S$ ensures that the symbols are converted in the proper order as the subscript can not decrease. In the end remove $S\_3$. $$ S\_3 \rightarrow \varepsilon $$
> 5 votes

# Answer
The answer for your specific example is there, but the general question remains.

In very many years, in both theoretical and applied computer science, I do not recall having to write a CS grammar as such.

Still, if I may give an advice, it should not be seen at all like producing a CF grammar, were you must contrive the rules to get everything in place and coordinated exactly right as it is produced.

CS grammars are a lot more algorithmic, and you can pretty much mimic a Turing machine (working in finite space, proportional to input size, which means Linear Bounded Automaton - LBA) in order to move things around as needed. So it is much more a programming exercise.

You can pretty much generates the first ingredients to build one of the words in the language, then move them around algorithmically. You can use special symbols (possibly in various flavors corresponding to finite state) to act as heads that you move around with appropriate rules, do as to check what is to be done. And so on.

A good reading may be to look at the proof of equivalence between CSG languages and LBA languages, i.e. the CS languages.

Remember that nearly all algorithms that we work with can be performed by a LBA, hence correspond to a CSG definable language. That should give you an idea of the available algorithmic power.

But a bit of imagination helps elegant solutions, as in the example you gave.
> 2 votes

# Answer
this is just an additional answer that can be thought of as a general solution. CSLs, context sensitive languages are modelled by LBAs, linear bounded automata. a LBA is a Turing machine that can accept or reject given a work tape that is no larger than a constant times the size of the input tape. so if you can figure out a computer program that can process the input in constant space, then its a CSL. idea: a program that would work for this problem would do something like enumerate permutations in constant space.
> 1 votes

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


# Question
Title: Computability of equality to zero for a simple language
Suppose we have a tree in which leaves are labeled with a set of numbers $L$, and internal nodes with a set of operations $O$.

In particular $L$ can be $\mathbb{N}, \mathbb{Z}$ or $\mathbb{Q}$, and can optionally contain $\pi$ and/or $e$. $O$ can be any subset of $\\{+,-,\cdot,/,\hat\ \\}$.

Is equality with zero decidable? Are sign comparisons decidable? If so, are they feasible?

"Invalid" operations ($0/0$, $0^0$, ...) produce $NaN$, $NaN \neq 0$ and $NaN$ propagates through computations as usual.

Some combinations are trivial: if we restrict ourselves to field operations, and don't include either $\pi$ or $e$ in $L$ then we can just compute the resulting fraction and be done with it. Or if we restrict to $\mathbb{Z} \cup \\{\pi\\}$ and $\\{+,-,\cdot\\}$ we can compute the polynomial and check the coefficents. On the other hand powers (and hence $n$-th roots) and $\pi$ and $e$ make things considerably harder.

The "equality with zero" problem is an instance of the constant problem.

# Answer
> 4 votes
If you use the operators $\\{+,-,\times,/\\}$ (i.e., you don't included the power operator), then all of your problems are likely decidable.

## Testing equality with zero

For instance, let's consider $L = \mathbb{Z} \cup \\{\pi\\}$. Then you can treat $\pi$ as a formal symbol, so that each leaf is a polynomial in $\mathbb{Z}\[\pi\]$ (e.g., the integer $5$ is the constant polynomial $5$; $\pi$ is the polynomial $\pi+0$ of degree 1). Now you can express the tree as a rational polynomial over $\mathbb{Z}$, with $\pi$ as the formal unknown.

Suppose this polynomial is $p(\pi)/q(\pi)$. Test whether $p(\pi)$ is the zero polynomial (degree $-\infty$). If it is not the zero polynomial, then the expression is not equal to zero. If $p(\pi)$ is the zero polynomial, and $q(\pi)$ is not the zero polynomial, then the expression is equal to zero. The correctness of this procedure follows from the fact that $\pi$ is transcendental.

What's the complexity of this procedure? The answer depends on the computational model. Let's assume that each operator as taking constant time to evaluate (regardless of the size of the operands). Then the complexity depends on the size of the resulting polynomials. The degree of the polynomial can grow exponentially with the depth of the tree, so if you build the polynomial recursively and express it explicitly (in coefficient form), the running time will be at most exponential in the depth of the tree. Fortunately, the degree grows at most linearly in the number of leaves in the tree, so the running time of a deterministic algorithm is linear in the size of the tree.

Therefore, assuming a straightforward representation of the tree and a simplistic computational model, this gives you a linear time algorithm for zero testing when the operators are $\\{+,-,\times,/\\}$.

This procedure works not just for $L=\mathbb{Z} \cup \\{\pi\\}$, but also for $\mathbb{N} \cup \\{\pi\\}$ and $\mathbb{Q} \cup \\{\pi\\}$.

The same procedure also works for $L=\mathbb{Q} \cup \\{\pi,e\\}$, if we can assume a reasonable conjecture: that $\pi$ and $e$ are algebraically independent. It is not known whether this conjecture is correct, but it seems likely. Anyway, here's the approach. We treat the polynomial as a multivariate polynomial over two unknowns $\pi,e$ instead of one unknown, but everything carries over as before, given the algebraic independence of $\pi$ and $e$. It also works for $L=\mathbb{Z} \cup \\{\pi,e\\}$ and $L=\mathbb{N} \cup \\{\pi,e\\}$, too, again, assuming the conjecture.

If you wanted to get fancy, you could use randomized algorithms for polynomial identity testing. If $L = \mathbb{Z} \cup \\{\pi\\}$, they'll amount to the following: choose a random prime $r$ and a random integer $s\_{\pi} \in \\{0,\dots,r-1\\}$; replace each instance of $\pi$ with $s\_{\pi}$; and then check whether the resulting expression evaluates to $0 \bmod r$. (If you have both $\pi$ and $e$, you'll pick two random integers $s\_{\pi}$ and $s\_e$.) You can repeat this test multiple times. If this procedure ever gives you something non-zero (modulo $r$), then the original expression is certainly non-zero. If it always gives you zero (modulo $r$), then with high probability the original expression is equal to zero. This may be more efficient in some computational models (e.g., where the time to evaluate a single operator is dependent on the size of the operands).

## Sign comparison

You can also find the sign of the expression using similar procedures (again, assuming you have excluded the ^ operator, and again, assuming that $\pi$ and $e$ are algebraically independent). Evaluate the expression as a rational polynomial $p(\pi,e)/q(\pi,e)$ over $\mathbb{Q}\[\pi,e\]$. Assume you have determined that $p(\pi,e)/q(\pi,e) \ne 0$ and $q(\pi,e) \ne 0$. You want to know whether $p(\pi,e)/q(\pi,e) \> 0$ or not.

Here is one approach. Note that $p(\pi,e)/q(\pi,e) \> 0$ iff $p(\pi,e) \cdot q(\pi,e) \> 0$. Therefore, we can form a new polynomial $r(\pi,e) = p(\pi,e) \cdot q(\pi,e)$ and reduce this to the problem of evaluating the sign of $r(\pi,e)$. Basically, we need to evaluate the sign of a rational polynomial in $\pi$ and $e$. We know this evaluates to something non-zero.

One approach is to compute $\pi$ and $e$ to $k$ bits of precision, and then evaluate $r(\pi,e)$ accordingly, gaining lower and upper bounds on $r(\pi,e)$. If 0 is included within this interval, double $k$, until the lower bound is strictly positive or the lower bound is strictly negative.

What's the complexity of this approach? If $|r(\pi,e)|$ evaluates to a value $\epsilon$, then I think the running time will be polynomial in the size of the input and in $\lg 1/\epsilon$.

There may be a better algorithm, but this is the best I can come up with right now.

## Conclusion

The takeaway is that the power operator (^) is the real source of difficulty. Without the power operator, all of your problems can be solved without too much difficulty (assuming a reasonable conjecture).

# Answer
> 4 votes
This is a rather tricky question! As you seem to understand, the real issue is the presence of $\hat{}$. It is intimately related to a well known conjecture: Schanuel's conjecture, which states that, essentially, there are no non-trivial algebraic relationships between $\pi$ and $e$.

The (expected) positive answer to this conjecture would give you a decision procedure for comparison with $0$:

* Reduce the expression using algebraic equalities (e.g. $(x^y)^z = x^{yz}$ etc.)
* Separate the terms with exponents and the terms without.
* Check that the base ($x$ in $x^y$) of the terms with exponents are all linearly independent.
* The term is 0 iff it is trivial i.e. it reduces to 0 by algebraic operations.

A related question is Tarski's exponential function problem which involves variables. However it is relatively simple to reduce concrete expressions with exponents to functions with variables given the Lindemann-Wierstrass theorem.

Edit: I don't know anything about the actual complexity of the problem, though. Note that it strongly depends on your *computational model* e.g. whether arithmetic operations constant time.

Edit 2: I made a crucial mistake: it's not the *base* $x$ in $x^y$ that needs to be taken but rather $y\ln(x)$, which is much harder to check for linear independence.

---
Tags: algorithms, turing-machines, real-numbers, equality
---


# Question
Title: Keep k+ties largest elements in a stream
I have $n$ numbers that come one by one, and when the last element comes, I want to output $k$ largest elements and those that are ties with the minimal element from this top-$k$ element.

For example, I have $\[10, 7, 7, 9, 10, 10\]$ and $k = 4$, then I want to output $\[10, 9, 10, 10\]$. However, if $\[10, 7, 7, 9, 10\]$ and $k = 4$ I want to output $\[10, 7 , 7, 9, 10\]$. Note that in the first example number of unique elements is less than $k$.

If I didn't want these ties, I'd probably use min-heap and keep track of top-$k$ elements in that heap, replacing minimum every time larger element comes from the stream. However, with ties I would have to perform searching inside the heap the element if it's already there and only then perform replacement/addition.

What is the best way to keep track of top-k + ties elements from the coming array of integers?

Note: $n\>\>k$.

# Answer
> 1 votes
Keep a binary heap, where each element in the heap is a unique key value together with a pointer to a list of all the items with that key value.

For instance, with the input list $\[10,5,7,5,7,9,10\]$, the unique key values are $5,7,9,10$, so you'd have a heap containing the following 4 elements: $5$ (with a pointer to the list $\[5\]$), $7$ (with a pointer to the list $\[7,7\]$), $9$ (with a pointer to the list $\[9\]$), and $10$ (with a pointer to the list $\[10,10\]$). Now you can find the top-$k$ elements (with ties) straightforwardly using this heap data structure.

---
Tags: data-structures, sorting, heaps, online-algorithms
---


# Question
Title: Subset-sum approximation algorithm running time
in 35.5 of CLRS i have read about algorithm to find sum as large as possible, but not larger than $t.$

Essential part of this algorithm is trimming. On every step you delete all numbers which close one to another, but one to represent them all. Good explanation of the algorithm.

At page 7 from provided link or at page 1133 of ClSR 3rd edition you can find such a statement: $z'/z\>1+\epsilon/2n.$ I think $z'$ and $z$ is numbers of elements before and after trimming. But i can't understand how they got such estimation. For example at first step trimming don't actually trim any element. We can devise example of sequence and epsilon to have no trimmed elements even at second step.

Can somebody, please, explain how they got such an estimation? Thanks.

# Answer
> 1 votes
Both $z$ and $z'$ belong to the same trimmed list, *after* trimming. The point is that after trimming, two adjacent elements are at a multiplicative distance of at least $1+\epsilon/(2n)$, by construction. This is why the trimmed lists are small, and so the running time is reasonable. If there is no trimming then there is no problem – the original list already satisfies this condition.

Here is a concrete example. Suppose we want our elements to be at multiplicative distance at least $2$, and suppose that the original list is $1,2,3,4,5,6,7,8$. After trimming we are left with $1,2,4,8$, and any two adjacent elements are at multiplicative distance at least $2$ (in this case, exactly $2$). Had we started with, say, $1,4,9,16$, no trimming would be necessary, but still adjacent elements are at multiplicative distance at least $2$.

---
Tags: algorithms, algorithm-analysis, approximation
---


# Question
Title: Different boolean degrees polynomially related-2?
Essentially similar question to here Different boolean degrees polynomially related? (change being error condition $\epsilon\in(0,1)$).

Let $p$ be the minimum degree (of degree $d\_f$) real polynomial that represents boolean function $f$ such that $f(x)=p(x)$.

Let $p\_{0,\epsilon}$ be the minimum degree (of degree $d\_{0,f,\epsilon}$) real polynomial that represents boolean function $f$ such that $$f(x)=0\implies p\_{0,\epsilon}(x)=0$$$$f(x)=1\implies|p\_{0,\epsilon}(x)-f(x)|\leq\epsilon.$$

Let $p\_{1,\epsilon}$ be the minimum degree (of degree $d\_{1,f,\epsilon}$) real polynomial that represents boolean function $f$ such that $$f(x)=1\implies p\_{1,\epsilon}(x)=1$$$$f(x)=0\implies|p\_{1,\epsilon}(x)-f(x)|\leq\epsilon.$$

Is $d\_{f}\leq d\_{0,f,\epsilon}^{c\_0}$ and $d\_{f}\leq d\_{1,f,\epsilon}^{c\_1}$ for some $c\_0$ and $c\_1$?

Above holds if $\epsilon\in(0,1)$ Relations among different boolean approximations

There solution considered $0\<\epsilon\<\frac{1}{2}\leq\delta\<1$. Solution showed relation between $d\_{0,f,\epsilon},d\_{0,f,\delta}$ is a linear function with constant multiplicative factor as long as we have fixed $\epsilon,\delta$.

This along with solution to another problem in Different boolean degrees polynomially related? shows $d\_{f}\leq d\_{0,f,\epsilon}^{c\_0}$ and $d\_{f}\leq d\_{1,f,\epsilon}^{c\_1}$ for some $c\_0$ and $c\_1$ holds if we have fixed $\epsilon,\delta$.

(1) I am most interested in case where we have not fixed $\delta$ and/or $\epsilon$. Say $\delta=1-\frac{1}{h(n)}$, $\epsilon=\frac{1}{g(n)}$ (that is either/both $\delta$ or/and $\epsilon$ changes) with some functions $g(n)$, $h(n)$ of $n$ (logarithmic/polynomial/exponential). I am interested in how fast do degrees (multiplicative factors) grow.

(2) There was a comment on sign degree. I understand sign degree is an useful parameter. However for sign degree as I understand ranges of functions involved are over $\Bbb R\backslash\\{0\\}$ (Only criteria is approximating function takes same sign as $f$). Here ranges are different.

# Answer
You're asking several questions. Here are answers for some of them.

1. The OR function has degree $n$, but it can be approximated by the function $(x\_1+\cdots+x\_n)/n$. This shows that $d\_{1,\text{OR},1-1/n} = 1$.
2. If you have a polynomial $P$ representing $f$ in the sense that $P(x) = 0$ whenever $f(x) = 0$ and $|P(x)-1|\<1$ whenever $f(x) = 1$, then for small enough $\epsilon \> 0$, the function $P-\epsilon$ sign-represents $f$.
3. The correct tradeoff between (say) $d\_{0,f,\epsilon}$ and $d\_{0,f,\delta}$ for different $\epsilon,\delta$ can be studied using approximation theory, i.e. Chebyshev polynomials and the related Markov and Bernstein theorems and their ilk. The functions converting a $\delta$-approximation to an $\epsilon$-approximation can be constructed explicitly using Chebyshev polynomials, and lower bounds on their degrees can be obtained using Markov–Bernstein theorems. This is similar to the way that the tight bound $\Theta(\sqrt{n})$ for the approximate degree of the OR function $d\_{\text{OR},\epsilon}$ is proved.
> 0 votes

---
Tags: complexity-theory
---


title: Kth largest subset for small K

text:
# Question
Title: Kth largest subset for small K
The $K$th Largest Subset problem is often given as an example of an NP-hard problem. However, the assumption is that $K$ is unconstrained, and can be as large as $2^n$. Clearly, if $K \le 3$ the solution in $O(n)$ time is trivial.

Are there any general results for time complexity of this problem for a given (and potentially small) $K$?

# Answer
There is a simple algorithm whose complexity is $O(Kn)$. The algorithm computes, for each $m \leq n$, the $K$ largest sums of the first $m$ numbers. Given the list for $m$, the list for $m+1$ is computed by adding the $(m+1)$st element to the old list, merging the two lists, and keeping only the top half. Since merging sorted lists can be done in linear time, the resulting complexity is $O(Kn)$.
> 2 votes

---
Tags: complexity-theory, np-hard
---


title: How to create a suffix tree by hand

text:
# Question
Title: How to create a suffix tree by hand
I will soon have to be able to draw a suffix tree of a word on an exam. I tried to understand the different algorithms available, but they seem rather complicated to do "by hand".

I do not see a simple way how to draw such a tree. Is there a simple step by step method for people not knowing the algorithms?

# Answer
> 4 votes
Here is how to draw the suffix tree for the example $abaab\\$$ mentioned in the lecture notes appearing in greybeard's comment.

**Root.** There are two characters appearing in the word, $a,b$, so the root has two outgoing edges, labeled $a$ and $b$.

**Root-\>a.** Following $a$, we have both characters $a,b$ appearing in the word. So this note has two outgoing edges, labeled $a$ and $b$.

**Root-\>a-\>a.** There is only one suffix $aab\\$$ starting with $aa$, so we replace this node with a leaf, and modify the edge label to $ab\\$$.

**Root-\>a-\>b.** There are two suffixes $abaab\\$$ and $ab\\$$ starting with $ab$. Correspondingly, we add two children with edges labeled $aab\\$$ and $\\$$.

**Root-\>b.** Following $b$ we have the two suffixes $baab\\$$ and $b\\$$. Correspondingly, we add two children with edges labeled $aab\\$$ and $\\$$.

The general method is similar. At each node $w$, we add children corresponding to all possible continuations of $w$ in the word. If there is only one continuation possible, we modify instead the edge label. This algorithm is easy to implement by hand, but could be hard to implement in linear time on a computer.

---
Tags: algorithms, strings, suffix-trees
---


# Question
Title: Books to get prepared before self studying Artificial Intelligence
I want to study Artificial Intelligence from *Artificial Intelligence: A Modern Approach* by *Russell* and *Norvig*, in the mid-year vacation. I want to get prepared before diving into the book so I decided to review some relevant subjects like Discrete Mathematics. I know there is a good book for Discrete Mathematics by *Kenneth. H. Rosen* and bought it. But I don't know about any other books to read before studying AI.

Can someone give me book suggestions?

# Answer
Probability theory is also extremely important for artificial intelligence. A textbook I very much recommend on this subject is Probability, Statistics, and Stochastic Processes by Olofsson and Andersson.

Many areas of artificial intelligence, particularly those concerning image processing of some sort, also make good use of linear algebra. For this, I recommend Linear Algebra by Spence, Insel, and Friedberg, or Linear Algebra Done Right by Axler if you want a more pure mathematics approach.
> 1 votes

---
Tags: artificial-intelligence, discrete-mathematics
---


# Question
Title: Some slight confusion with the UNTIL operator in CTL (e.g. a U b)
I've sketched a very small transition system in paint that I'll use as an example.

I want to see if $A(aUb)$ holds for this transition system. From my understanding, this CTL formula is asking if ALL paths satisfy $aUb$. The only path we can take in this example is S0S1S0S1S0S1S0S1...

This path produces the output (1) $aaaaaaaaaaaaaaaaa...$ or (2) $aaaaaaaaaaaaaaab...$

(2) definitely holds - however it's (1) that I'm unsure about. Am I correct in saying that $aUb$ doesn't hold for (1)? Since we can continue looping over a infinitely without eventually reaching b (and because (1) doesn't satisfy the formula, $A(aUb)$ doesn't hold for this transition system).

Have I understood this correctly? I guess the main confusion for me is that there is 1 path but more than 1 possible output.

Any help is much appreciated.

edit: This is the transition system I'm referring to in the comments below

# Answer
You have some misconception regarding transition systems: The alphabet of the system is $2^P$ for some set $P$, and paths induce words over $2^P$. In the first system, there is a single path: $(S\_0,S\_1)^\omega$, and it induces a single word: $(\\{a\\},\\{a,b\\})^\omega$.

Now, this word satisfies $aUb$, since $a$ holds until the secod letter, in which $b$ holds.

The $\forall$ quantifier here is somewhat useless, since there is a single path.

The second system is problematic, since there is nowhere to go to from $S\_2$...
> 4 votes

# Answer
A small addendum to @Shaull's anwswer, which is completely correct: for the output (1), $aaaaaaaaa\ldots$, you suggested (if it were possible in your transition system), your assumption that the formula does not hold is correct. The formula $A \[a U b\]$ does not hold on such a path; Wikipedia gives the following definition:

$\bigg( (\mathcal{M}, s) \models A\[\phi\_1 U \phi\_2\] \bigg) \Leftrightarrow \bigg( \forall \langle s\_1 \rightarrow s\_2 \rightarrow \ldots \rangle (s=s\_1) \exists i \Big( \big( (\mathcal{M}, s\_i) \models \phi\_2 \big) \land \big( \forall (j \< i) (\mathcal{M}, s\_j) \models \phi\_1 \big) \Big) \bigg)$

Note that, for all paths ($\forall \langle s\_1 \rightarrow s\_2 \rightarrow \ldots \rangle (s=s\_1)$), an $i$ has to exist wich satisfies the rest of the formula. This means that $i$, apart from the "rest" concerning $\phi\_1$, needs to satisfy $(\mathcal{M}, s\_i) \models \phi\_2$, which requires a state $s\_i$ in which $\phi\_2$ is present.

In your case, this means that there has to be a state in which the output contains $b$; if there is not, the forumula $A\[a U b\]$ cannot be satisfied.
> 2 votes

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


# Question
Title: How does the ID3 Algorithm differ from a generic Decision Tree learning algorithm
Based on the notes of my Machine Learning lecturer, I am struggling to understand how the two algorithms differ? Both seem to select the most informative feature A (based on least entropy), then create subsets of the example set for each value of A. Then create a new branch on the tree by recursively calling ID3 on each subset. Could someone please explain how they differ?

# Answer
The ID3 algorithm is an algorithm for inferring a decision tree: given a training set, it tries to find a decision tree that tends to label a large fraction of the training set accurately. See, e.g., https://en.wikipedia.org/wiki/ID3\_algorithm.

There is no such thing as "the generic decision tree learning algorithm". There is no such generic algorithm.

There are many algorithms for learning a decision tree. ID3 is probably the most well-known algorithm for decision tree learning, and the simplest, but there are other algorithms. Other algorithms include C4.5, CART, and others.
> 1 votes

---
Tags: machine-learning, decision-problem, classification
---


# Question
Title: What is the difference between a Transition System and a Program Graph? (model checking)
As the above question says.

I'm wondering if a transition system is the same as a program graph or they are two different things?

Thank you.

# Answer
> 5 votes
You did not provide any particular resources for neither transition system nor program graph. My answer below is based on the book "Principles of Model Checking" by Christel Baier and Joost-Pieter Katoen (The MIT Press).

For completeness, I first present the definitions of both transition system and program graph in this book. (*Keep the numbering of the definitions in the book.*)

Definition of transition system:

> Definition 2.1 (Transition System $TS$)
>
> A transition system $TS$ is a tuple $(S, Act, \to, I, AP, L)$ where
>
> * $S$ is a set of states,
> * $Act$ is a set of actions,
> * $\to \subseteq S \times Act \times S$ is a transition relation,
> * $I \subseteq S$ is a set of initial states,
> * $AP$ is a set of atomic propositions, and
> * $L : S \to 2^{AP}$ is a labeling function.

Definition of program graph:

> Definition 2.13. (Program Graph $PG$)
>
> A program graph $PG$ over set $Var$ of typed variables is a tuple $(Loc, Act, Effect, \hookrightarrow, Loc\_0,g\_0)$ where
>
> * $Loc$ is a set of locations and $Act$ is a set of actions,
> * $Effect : Act \times Eval(Var) \to Eval(Var)$ is the effect function,
> * $\hookrightarrow \subseteq Loc \times Cond(Var) \times Act \times Loc$ is the conditional transition relation,
> * $Loc0 \subseteq Loc$ is a set of initial locations,
> * $g\_0 \in Cond(Var)$ is the initial condition.

First of all, the program graph consisting of locations as nodes and conditional transitions as edges is **not** a transition system, since the edges are provided with conditions.

However, each program graph can be interpreted as a transition system. Particular, the underlying transition system of a program graph results from *unfolding*: a state of the transition system is composed of a location $l$ of the program graph and an evaluation $\eta$ of the variables. Formally,

> Definition 2.15. Transition System Semantics of a Program Graph
>
> The transition system $TS(PG)$ of program graph $PG = (Loc, Act, Effect, \hookrightarrow, Loc\_0, g\_0)$ over set $Var$ of variables is the tuple $(S, Act, \to, I, AP, L)$ where
>
> * $S = Loc \times Eval(Var)$
> * $\to \subseteq S \times Act \times S$ is defined by the rule $$\frac{l \hookrightarrow^{g:\alpha} l' \land \eta \models g}{\langle l, \eta \rangle \to^{\alpha} \langle l', Effect(\alpha, \eta) \rangle}$$
> * $I = \\{ \langle l, \eta \rangle \mid l \in Loc\_0, \eta \models g\_0 \\}$
> * $AP = Loc \cup Cond(Var)$
> * $L (\langle l, \eta \rangle) = \\{ l \\} \cup \\{ g \in Cond(Var) \mid \eta \models g \\}$.

---
Tags: terminology, model-checking, transition-systems
---


# Question
Title: Using Generalized Rice's Theorem to Prove Decidability
I have a Turing Machine M with a binary alphabet {1,2} that accepts a language L(M) that has infinitely many strings that start with 1 and finitely many strings that start with 2. I'm trying to determine if L(M) is decidable, semi-decidable (computably enumerable) or undecidable.

Using Rice's Theorem, I believe I can prove that L(M) is not decidable:

> P is the property of a language where the language has infinitely many strings that start with one symbol and finitely many strings that start with another symbol. P is non-trivial and is a property of languages of TMs. Therefore, according to Rice's Theorem, M = {⟨M⟩∣L(M) has has infinitely many strings that start with 1 and finitely many strings that start with 2 and Σ = {1,2}} is undecidable.

But I'm struggling to prove whether it's semi-decidable or completely undecidable. This post mentions using an Generalized Rice's Theorem to prove that a language is recursively enumerable (aka semi-decidable) but I'm having trouble understanding their approach.

Can anyone shed some light on this approach and/or if I'm heading down the right path? Many thanks in advance.

# Answer
> 1 votes
I'm going to ignore the second half of your post, and answer the question that appears at the first half. If this is not what you meant - post another question or edit as necessary.

Given a machine $M$ we define $L(M)$ to be the language recognized by that machine. In other words, $L(M)$ is the set of all the words $w\in \Sigma^\*$ such that $M$ accepts $w$.

Thus, by its definition $L(M)$ is at least semi-decidable (because $M$ is accepting it!!)

To clarify whether $L(M)$ is decidable or semi-decidable(but not fully decidable), we need more information on $M$.

For instance, it can be that $M$ is the trivial machine that immediately go to the accepting state. In that case $L(M)=\Sigma^\*$ (all the possible words), and $L(M)$ is decidable.

On the other hand it can be that $M$ does the following:

```
1. it ignores the first symbol of the input
2. it runs HP on the rest of the input

```

where HP is the machine that accepts the Halting Problem language. It is not too difficult to see that in this case $L(M)$ cannot be fully decidable (or otherwise the halting problem will be decidable), but, as said above, it is semi-decidable by definition (that is, it is in $RE\setminus R$).

Now, if you don't care about a **specific** machine $M$, but instead about *all* the machines that accept infinitely many words that begin with 1 and infinitely many words that begin with 2, the language that contain all such machines cannot be decidable due to Rice's theorem.

Just to be clear on the statement: let $S \subset RE$ be all the languages that contain infinitely many words that start with 1 as well as infinitely words that start with 2, then

$$L\_S = \\{ \langle M \rangle \mid L(M) \in S \\}$$ cannot be decidable, $L\_S\notin R$. Note that $L\_S$ contains all the (encodings of) machines that satisfy the property $S$ defined in your question.

---
Tags: computability, turing-machines, undecidability, semi-decidability, rice-theorem
---


# Question
Title: Proving that a certain graph contains a 4-cycle
> Show that if $G$ is a graph with $|E| \geq 2|V|^{3/2}$, then $G$ must contain a $4$-cycle

Can someone explain/point me in the right direction on this? Let's say we say $|V|= 4$, using the equation above we get $|E|= 16$.

I drew it out and I was unable to come up with $16$ edges. Do I completely misunderstand the graph equation?

# Answer
> 4 votes
The question says "**IF** $G$ contains a certain number of edges, then..." and, as you've demonstrated, if $G$ has only four vertices, then it can't contain that many edges, since a graph (without self-loops) can contain at most $\tfrac12|V|\\,(|V|-1)$ edges. So, for the condition to be true, we must have $$\begin{align\*} 2|V|^{3/2} &\leq \tfrac12|V|\\,(|V|-1) \\ 4|V|^{1/2} &\leq |V|-1 &\text{(dividing through by $\tfrac12|V|$)}\\ 16|V| &\leq |V|^2-2|V| + 1 &\text{(squaring both sides)}\\ |V|^2-18|V|+1&\geq 0 &\text{(collecting terms)} \end{align\*}$$

Then, by the quadratic formula, we see that $|V|\geq 9 + 4\sqrt5 \approx 17.94$ (or $|V|\leq9-4\sqrt5$ but we're only interested in positive solutions for $|V|$). It's not a problem that $17.94$ isn't an integer: the number of vertices must be greater than or equal to that number, so we actually have $|V|\geq 18$.

# Answer
> 4 votes
This is a typical question in graph theory, especially in extremal graph theory which studies extremal (maximal or minimal) graphs which satisfy a certain property.

A **dual problem** of your *prime* question is:

> What is the maximum possible number of edges in an undirected graph $G$ with $n$ vertices which does not contain $C\_4$?

The answer (wiki) is $\left(\frac{1}{2} + o(1) \right) n^{\frac{3}{2}}$.

You can find a quite simple proof (based on *double counting*) for it in the article: Theorem 2.4 for a slightly tighter result $|E| \le \frac{n}{4} (1 + \sqrt{4n-3})$.

*Edit:* As stated by @David Richerby, your proposition is "well-defined" only if $|V| \ge 18$. If $4 \le |V| \< 18$, you can regard that this proposition is vacuously valid. Note that, however, the *dual* problem above does not require $|V| \ge 18$.

---
Tags: graphs
---


# Question
Title: Lower bound on approximation degree in Nisan-Szegedy
In Nisan and Szegedy's 1994 paper "On the degree of boolean functions as real polynomials"\[1\] Lemma 3.8, how does proof work for $\widetilde{\deg(f)}\geq \sqrt{\\,\tfrac16\mathrm{bs}(f)\\,}$? It clearly works for $\deg(f)$ and only this portion is shown in Jukna's book \[2, Theorem 14.11\]. Why does the proof work for $\widetilde{deg(f)}$?

Here $f$ is boolean function, $\widetilde{\deg(f)}$ is the $\tfrac13$-approximation degree of $f$, $\deg(f)$ is real degree of $f$ and $\mathrm{bs}(f)$ is block sensitivity of $f$.

---

\[1\] Noam Nisan and Mario Szegedy, "On the degree of boolean functions as real polynomials". *Computational Complexity* 4(4):301–313, 1994 (SpringerLink)
\[2\] Stasys Jukna, *Boolean Function Complexity*. Volume 27 of *Algorithms and Combinatorics*, Springer, 2012. (Homepage)

# Answer
If you believe Lemma 3.8 for $\deg f$, you should also believe it for $\widetilde{\deg} f$. An earlier lemma states that if $f$ is a Boolean function on $n$ variables such that $f(\mathbf{0}) = 0$ and $f(\mathbf{x})=1$ for all $|\mathbf{x}|=1$ then $\deg f \geq \sqrt{n/2}$ and $\widetilde{\deg} f \geq \sqrt{n/6}$. Applying the first part of this lemma, we conclude the first part of Lemma 3.8, namely $\deg f \geq \sqrt{\operatorname{bs}(f)/2}$. Applying the second part of this lemma, we conclude the second part of Lemma 3.8, namely $\widetilde{\deg} f \geq \sqrt{\operatorname{bs}(f)/6}$.
> 1 votes

---
Tags: complexity-theory, boolean-algebra, polynomials
---


# Question
Title: Most frequently tools or programming language for implementation text processing and nlp algorithms in academic papers and journals
I want to prototype and try some idea (some algorithm) in the field of text processing and nlp and if the results was good I want to publish some paper or journal article about that.

I am familiar with Weka, RapidMiner, Matlab and Python for text processing and nlp but I don't know what is the most frequently tools for those fields in the academic area?

As you know, comparing results with others is one of the most important parts of any academic paper. For this reason, I want to choose most frequently tools or language for this work.

Sorry for my bad English.

Thanks for your attention.

# Answer
> 2 votes
My personnal opinion is that such comparisons usually make little sense because they can be too dependent on hidden specificity of tools or programming languages, or programming style and its interaction with those specificities.

In my opinion, the only proper way to compare techniques is by a precise knowledge of the interpretation machines. If you are comparing different algorithms intended to achieve the same purpose, you want to run them on some kind of unbiased abstract machine, providing some application meaningful primitives than can be used to implement on the same footing all the algorithmic variations.

Then you can actually count elementary computation costs over some chosen benchmark.

For example, I have seen this type of work done for various parsing algorithms, using a standardized PDA definition.

Making a slightly better tool than what exist for problem X in language Y is seldom worth publishing, unless there is some more abstract consideration of some theoretical work that shows that you are bringing something to the field, rather than just being a better hacker. And then the tool or language support does not matter so much, as long as you can compare with some known work, and explain credibly why your version works better.

Of course, if you actually manage to get major improvements, undisputable ones, then you have a much better chance of being published. But the the technical support you use will matter even less.

---
Tags: programming-languages, data-mining, natural-language-processing
---


# Question
Title: Given two heuristic values how do I tell which one is admissible?
I am given 2 list of admissible values for a graph, and the graph with the real cost to each of the nodes.

Am I correct in thinking the way to see which one is admissible is add up all the values of the h(n) and compare it to the total real cost of the graph?

Example:

> h1 total = 681 h2 total = 732
>
> Total cost of graph = 704

Does this mean h1 is admissible as it doesn't overestimate?

# Answer
A heuristic function $h$ is admissible, if it never overestimates the cost for any given node. Formally speaking, let $h^{\*}$ map each node to its true cost of reaching the goal. The heuristic function $h$ is admissible, if for all nodes $n$ in the search tree the following inequality holds: \begin{align} h(n) \leq h^\*(n). \tag{$\star$} \end{align}

That means for checking whether a given heuristic function $h$ is admissible, we have to verify that the inequality $(\star)$ holds by either
(a) calculating the real cost $h^{\*}$ for each node and comparing the values, or
(b) proving it by using additional information available of the heuristic.

For example, we know that the eucledian distance is admissible for searching the shortest path (in terms of actual distance, not path cost). Note also that any consistent heuristic is admissible (but not always vice-versa).

For your example, there is no additional information available regarding the two heuristics. Thus you have to calculate the real cost $h^\*$ for each node, and then check whether the inequality $(\star)$ holds (I leave this task to you).

By checking the total cost you can **neither prove** that a heuristic is **admissible nor** that a heuristic is **not admissible**. The problem with this idea is that on the one hand you sum up the costs of the edges, but on the other hand you sum up the path cost (the heuristic values). For example, consider the following search tree with start node $A$ and goal node $C$

and the following heuristic functions $h\_1$ and $h\_2$:

\begin{align} h\_1(A) = 20; &\quad h\_2(A) = 8 \\ h\_1(B) = 10; &\quad h\_2(B) = 11 \\ h\_1(C) = 0; &\quad h\_2(B) = 0 \\ \end{align}

The sum of the total cost of the search graph is $10 + 10 = 20$. The sum of the heuristic values of $h\_1$ is equal to $20 + 10 + 0 = 30$, which is larger than $20$ although $h\_1$ is admissible. The sum of the heuristic values of $h\_2$ is equal to $8 + 11 + 0 = 19$, which is smaller than $20$, but $h\_2$ is **not admissible**, since $h\_2(B) = 11 \nleq h^{\*}(B) = 10$.
> 10 votes

---
Tags: search-algorithms, heuristics
---


# Question
Title: MAX,MAJ variants of NP complete problems
We know that MAJSAT is PP-complete. Is it generally true that given an NP-complete problem, its majority variant is PP-complete? For example,

MAJ-Set-Splitting: are the majority of partitions of items going to split the sets?

MAJ-Subset-Sum: does the majority of partitions of items have a sum of exactly K?

etc...

# Answer
MAJ-Subset-Sum is easy to solve. A majority of partitions sum to $K$ iff $K = 0$ and all elements are equal to $0$. Indeed, let $S$ be the (multi)set, and suppose that there were some element $x \neq 0$ in $S$. For each subset $A$ of $S \setminus \\{x\\}$, either $\sum A \neq K$ or $\sum A + x \neq K$, and so $K$ can be the sum of at most half the subsets. We conclude that if $K$ is a sum of the majority of the subsets that $S$ consists only of zeroes, and so $K = 0$ as well.
> 2 votes

# Answer
The following is based on an answer I got from Piotr Faliszewski, thanks Piotr!

As the example by Yuval shows, things aren't as straightforward. First, one must clearly define what "a majority variant" really means. In most NP-complete decision problems the meaning is quite clear: these problems ask about the existence of some object with a given property and then you can enumerate these objects; "computation paths that return yes" refer to the objects with the property.

The following claim holds: if an NP-complete problem X was shown to be NP-C via a parsimonious many-one reduction from problem Y, for which MAJ-Y is PP-complete, then MAJ-X is PP complete.

In short, a parsimonious reductions guarantees that there is a 1-to-1 mapping between the "computation paths" of the problem we reduce from and the "computation paths" of the problem we reduce to.

Many reductions between standard NP-C problems are known to be parsimonious (and, indeed, such reductions are often easiest to derive).

What happens if you take a problem X which is not NP-C in a parsimonious sense?

Problem: Stupid-SAT

Input : formula $F$ over variables $x\_1,..., x\_n, y\_1, ..., y\_n$

Question: Is it possible to set the variables $x\_1, ..., x\_n, y\_1, ..., y\_n$ such that:

1. $F(x\_1, ..., x\_n, y\_1, ..., y\_n)$ is satisfied.
2. all $y\_1, ..., y\_n$ are set to false

Now, no matter what input formula we have, among the $2^{2n}$ "computation paths", there are at most $2^n$ ones that say yes (provided we are guessing the values for $x$'s and $y$'s, which, while a bit silly, would be a natural interpretation of the statement of the problem).

Thus, there is never a majority of computation paths that say yes and so Maj-Stupid-SAT is an empty set, which certainly is not PP-complete.

Thus, I would be quite careful about saying the if X is NP-C then Maj-X is PP-complete (or even hard; the empty set above is, of course, very easy).

An additional note about counting variants: given an NP-C problem X, define $\\#$-X as "how many satisfying paths does an instance of X have?"

Is $\\#$-X $\\#P$ complete? (e.g. $\\#$-TSP = how many routes of length less than k traverse all nodes?)

This also does not have a straightforward answer. There are at least four different (more and more general) notions of $\\#P$-completeness.

$\\#P$-parsimonious-complete (e.g., $\\#$SAT is here)

$\\#P$-many-one-complete (e.g., computing Shapley value for WVGs is here, but not above)

$\\#P$-metric-complete

$\\#P$-Turing-complete

$\\#P$-parsimonious-complete is the most restrictive class and $\\#P$-Turing-complete is the largest. Some of these classes are known to differ between each other.

When people show hardness, it is easiest to show $\\#P$-Turing-completeness and if someone was not careful to mention the exact type of $\\#P$-completeness and you do not explore the reduction carefully, the most you can assume is $\\#P$-Turing-completeness.

As before, if the problem X was shown to be NP-C in a parsimonious way from a problem Y for which $\\#$-Y was $\\#P$ complete, then you can certainly claim $\\#P$-parsimonious-completeness for $\\#$-X. Otherwise, things get complicated.

Indeed, though in a different direction, it is well known that there are poly-time problems whose counting variants are $\\#P$-complete (one way or the other).

The very least one can claim, however is the following: if a problem X is NP-C, then certainly $\\#$-X is hard in some computational way (indeed, if it were easy then solving X would be easy too).
> 2 votes

---
Tags: complexity-theory
---


title: Complexity of a knapsack variant

text:
# Question
Title: Complexity of a knapsack variant
Consider the following traditional integer knapsack problem:

$\max \sum\_{i=1}^k p\_i \cdot x\_i\\ \text{s.t.} \sum\_{i=1}^k w\_i \cdot x\_i \leq W \\ x\_i \in \\{0,\ldots,k\_i\\} \text{ for each } i$

Now consider a laminar family $\mathcal{I}$ of sets, i.e., a collection of subsets of $\\{1,\ldots,k\\}$ such that for each pair $I\_1,I\_2 \in \mathcal{I}$ it either holds that $I\_1 \subseteq I\_2$ or $I\_1 \supseteq I\_2$ or $I\_1 \cap I\_2 = \emptyset$. For each of these subsets $I\_j \in \mathcal{I}$, we insert an additional cardinality constraint of the form

$\sum\_{i \in I\_j} x\_i \leq \mu\_j$

for some number $\mu\_j$.

Clearly, this problem is weakly $NP$-complete in general since it contains the traditional (integer) knapsack problem. The question is what happens if the profits $p\_i$ are polynomially bounded. Does the problem remain $NP$-complete or is it easy to solve now? We are thinking about this problem for months now.

What we know so far:

* If we omit the cardinality constraints or restrict ourselves to only one cardinality constraint that involves each of the variables, the problem becomes easy to solve (this isn't as trivial as it sounds since the maximum amounts $k\_i$ are still not polynomially bounded).
* Accordingly, if the maximum amounts $k\_i$ are polynomially bounded, the problem becomes easy to solve as well.

The above results imply that, in order to prove $NP$-completeness, a possible reduction would need to make use of decision variables that are not polynomially bounded and must incorporate suitable laminar cardinality constraints with values $\mu\_j$ that aren't polynomially bounded as well.

So, does anyone have some clue on how to prove or disprove the $NP$-completeness of the problem?

# Answer
> -1 votes
It can be solved by a similar DP for traditional knapsack problem, and thus still weak NP-complete. In the following we assume that the subsets $I\_j$ are mutually disjoint, and the other case (some subsets are super sets of others) is similar.

In the DP algorithm for knapsack, let $T\[p,i\]$ be the minimum weight to reach profit $p$ by only using the first $i$ items. Now arrange the items such that all items in the same $I\_j$ are consecutive. Since $I\_j$ are disjoint, when dealing with $x\_i$, we only need to consider how many items in $I\_j$ can be picked. Thus, for each $p$ and $i$, let $D\[p,i,q\]$ be the minimum weight to reach profit $p$ by only using the first $i$ items and using only $q$ items in $I\_j$. The table size is bounded by $P\times n^2$, where $n$ is the number of items and $P$ is the maximum profit. Since you assume that $P$ is polynomial, it takes polynomial time.

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


# Question
Title: Anagrams solver based on transitions probability
I have an English dictionary (text file) and the frequency of 2-grams, 3-grams and 4-grams as the beginning of each word. I need to write an algorithm that, with a given word, calculates the possible anagrams (which have to be into the dictionary) based on transitions probability (my assignment requires that I use this method).

I thought to use the Viterbi Algorithm but I don't know if it is the right choise. What do you think about a simulated annealing algorithm? Can you give me any help or advice?

# Answer
There's a better way to list all anagrams.

Given a word, compute its "canonical form" by sorting the individual letters into alphabetical order. For instance, BASEBALL becomes AABBELLS. Do this for each word in the dictionary, and build a data structure that maps from a canonical form to the list of words with that canonical form (e.g., from AABBELLS to BASEBALL) -- for instance, you might use a hashtable or a sorted list.

Now, given one English word, if you want to find all anagrams of it, you can rapidly compute all anagrams by computing its canonical form and then looking that up in your data structure.

This doesn't require n-grams, transition probabilities, Viterbi algorithm, or anything fancy like that -- just sorting and simple data structures. Thus, it can be coded up quickly and elegantly; and it will be very efficient.
> 1 votes

---
Tags: algorithms, graphs, probability-theory, approximation, probabilistic-algorithms
---


# Question
Title: Precise runtime of the algorithm to find number of digits in an integer
Consider an integer ( of arbitrary length ). To find the number of digits it has, here is a known simple algorithm

```
count = 1;
while ( (value = value/10) )    count++;

```

Now, what is the time cost of this algorithm? If we assume that `k` is the number of bits ( not digits) required to represent the number, then it is `O(k)`. But this algorithm doesn't have a clean linear behavior. That is, if I double the the number of bits in the integer, the number of iterations of `while` loop doesn't necessarily double every time. An increase of 3-4 bits in the input increases the iteration count by 1.

I know that the number of digits in a number `N` is `floor(log10(N)) + 1` but then we wouldn't be expressing the runtime in terms of number of bits, which is what I need.

In such cases how to calculate the runtime precisely?

# Answer
There are two answers here:

1. $\log\_{10} n = \log\_{10} 2 \log\_2 n$, and $\log\_2 n$ is (almost) the length of $n$ in *bits*.
2. We don't care about the exact complexity. The point of big O notation is to hide multiplicative constants. A function is $O(\log\_2 n)$ iff it is $O(\log\_{10} n)$. Moreover, the exact time complexity depends on the exact computation model used (i.e. compiler, CPU, operating system and environment – presumably this code snippet runs on actual hardware and its execution time is measured in seconds), which you haven't specified anyway. Again, the point of big O notation is that these details don't matter since they only affect the complexity by a multiplicative constant.

Another point which you should consider is that in practice, either `value` has a fixed length, or it is variable length (*bignum*). If it has fixed length (say it's a 32 bit integer), then the correct parameter here is not the length (which is constant) but the value itself. If it has variable length, then the division instruction cannot be reasonably assumed to take constant time.
> 2 votes

---
Tags: algorithm-analysis, runtime-analysis
---


# Question
Title: Applying DFS algorithm to a transition system to find reachable states
Currently working on a past exam question which tells me to compute the product of two transition systems and then **use DFS to find the reachable states of the product**. I learnt how to compute the product of transition systems by looking at pages 43 and 44 in the "Principles of Model Checking" book by Christel Baier and Joost-Pieter Katoen (if anyone has a copy).

I understand that the way they found the reachable states in page 44 is by tracking the value of the variable y for each state and seeing if it holds, but in my particular question I'm not using a program graph; it's a transition system that uses only sigma and gamma (as handshake actions). My first question is how do I determine what is a reachable state and what is not in a product of transition systems?

Secondly, how would I show that I used DFS on paper? I couldn't find any useful articles online about it and our lecture notes don't cover it for some reason.

# Answer
> 0 votes
You can design an algorithm to traverse the product of two TSs. With a simple DFS algorithm, start from start state and with rules for handshaking generate next states. You need to keep the states that has been visited so far to avoid loop. There may be more efficient ways but here is a sudo-code of a solution:

```
stack = new Stack()
visited_states = new Array()
stack.push(start_state)
while ~stack.isEmpty() {
    current_state = stack.pop()
    if current_state not in visited_states {
        visited_states.add(current_state)
        next_states = generate_next_states(current_state)
        for each state in next_states {
            stack.push(state)
        }
    }
}

```

Where generate\_next\_states is a function that generates next states according to the rule in page 48, Figure 2.11. Now the set of states in visited\_states are reachable states.

---
Tags: graph-traversal, model-checking, transition-systems
---


# Question
Title: Can the end-to-end principle be formalized?
In the late 1990s, when I was in graduate school, the paper

> JH Saltzer; DP Reed; DD Clark: End-to-end arguments in system design. *ACM Trans. Comput. Syst.* 2(4):277-288, 1984. DOI=10.1145/357401.357402

was pretty much required reading in every operating systems class at every university, and it still seems to be one of the primary guiding principles underlying the design of the internet. (See for example: J Kempf, R Austein (eds), and the IAB, "The Rise of the Middle and the Future of End-to-End: Reflections on the Evolution of the Internet Architecture," RFC 3724, March 2004.)

The end-to-end principle states (Saltzer et al., 1984):

> \[If\] the function in question can completely and correctly be implemented only with the knowledge and help of the application standing at the end points of the communication system, ..., providing that questioned function as a feature of the communication system itself is not possible. \[Although\] sometimes an incomplete version of the function provided by the communication system may be useful as a performance enhancement.

Or more briefly (from the abstract):

> The end-to-end argument suggests that functions placed at low levels of a system may be redundant or of little value when compared with the cost of providing them at that low level.

But I've had little success applying the end-to-end principle in my own experience (which is in computer architecture, not internet architecture). Since the principle is stated as a "poem" (i.e., in English prose with a bunch of terms that are not mathematically defined) it is quite easy to fool oneself into thinking that "the function in question can completely and correctly be implemented only with the knowledge and help of the application." But what is "the function in question," let alone "the knowledge and help" of an application?

Example: On-chip networks (unlike the internet) aren't allowed to drop packets, but have quite limited buffering, so you need to have some way of either avoiding or recovering from deadlock. On the other hand, the application needs to make itself deadlock free as well, right? So I might reason that I should make the common case (no deadlock) fast and push deadlock avoidance off on the app. This is, in fact, what we tried on Alewife and Fugu (Mackenzie, et al., Exploiting Two-Case Delivery for Fast Protected Messaging, Int'l Symp High-Perf Comp Arch, (HPCA-4):231-242, 1998. Or John Kubiatowicz's dissertation.) It "worked," (by having the interconnect interrupt the processor when the buffers got filled and having the OS augment with software buffering) but I haven't seen anyone in academia or industry (including any of us that were authors on that HPCA paper) racing around trying to replicate the idea. So apparently deadlock avoidance in a network is not the same "function in question" as application-level deadlock avoidance, or the end-to-end principle is wrong.

Is it possible to turn the end-to-end principle from a "poem" into a theorem? Or at least, can it be stated in terms understandable to a computer architect?

# Answer
I believe there may be two shortcomings in your application of the end-to-end (e2e) principle:

Firstly, in the sense that you apply it for performance. The end-to-end is a design principle such as to ensure architecture orthogonality, composability, regularity, one or all, provide primitives etc. Such principles have been outlined in related textbooks. Performance is not one of them. In fact, Clark et al, implies that strict end-to-end may result in worse performance so it uses such, as an exception to this principle.

So, if you still want to formalize:

"The end-to-end argument appeals to application requirements, and provides a rationale for moving function upward in a layered system" so you will need formalized application requirements and formalized layered system. Here is an attempt that might help taking it one step further:

Say you have Layer(i) requirements (Layer(0) is for the set of applications you expect to support now or in the future, the application layer) and firm interfaces Interface(i,i+1) and Interface(i+1,i) (from Layer i to i+1 pre-assume no cross-layering here, easy to change and make it a requirement) and functions Function(i,j) (Layer i, Function index j, assume data part of function to have it simpler)

Input: Layer(0) requirements (as we said these need to be formalized)

Output: everything else

END-TO-END Output is an Output such that: For each L, Layer(L) accomplishes its requirements only by functions Function(L,j) (i.e. functions within the layer) and Interface(L,L+1), Interface(L+1,L)

For each Layer L and function Function(L,F) there is no set of Functions S in the output such that Function(L,F)=S (= means equivalent output and side-effects)

So, coming to the second possible shortcoming for the specific e2e principle application (and if I am reading correctly what is being attempted) one can claim that it does not follow the e2e principle at all, quite the contrary. You have your chips provide "some deadlock avoidance" and you have an Interface that is out-of-the-ordinary non-firm and specific to trigger (interrupt) more help from upper layers. This is arguably a cross-layer approach not an end-to-end approach. In other words you have a Function(1,x) not accomplishing its task completely and correctly with set Interfaces - if you want to use the draft formalization provided above (which of course is just a start useful to an extend to fully answer your question but likely not full in itself).
> 3 votes

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


# Question
Title: Partial order, total order, and version order in transaction histories
In Section 3.1.2 "Transaction Histories" of the PhD thesis by Atul Adya \[1\]:

> A *history* $H$ over a set of transactions consists of two parts: (1) a **partial order** of events $E$ that reflects the operations (e.g., read, write, abort, commit) of those transactions, and (2) a version order, $\ll$, that is a **total order** on committed object versions.

---

The author gives a comment on "the partial order of events" (Page 36):

"For convenience, we will present history events in our examples as a *total order* that is consistent with the partial order. Furthermore, wherever possible in our examples, we make this total order be consistent with the *real-time ordering* of events in a database system."

> **Question 1:** Why can we present the partial order of events as a total order of them? Because a partial order may imply multiple total orders consistent with it, which one to choose? Does the choice matter for later definitions and theorems?

---

Some comments on "the total version order" (Page 36) are as follows:

\[**Added (01-10-2015)**\] "The version order in a history $H$ can be different from the order of write or commit events in $H$. This flexibility is needed to allow certain optimistic and multi-version implementations where it is possible that a version $x\_i$ is placed before version $x\_j$ in the version order even though $x\_i$ is installed in the committed state after $x\_j$ is installed."

And,

"The system chooses the version order for each object."

> **Question 2:** What does it mean for the database system to choose the version order? And how? Is this implementation-dependent?

---

\[1\] Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions by Atul Adya, 1999

# Answer
> 2 votes
for what it concerns Question 1:

there is a theoretical result from 1930 \[1\] that states that

any partial order $S$ can be extended to a total order $S'$ which contains $S$.

This result is known as the "Order Extension Principle"; the proof of this result uses the Axiom of Choice (I am not aware whether there is an alternative proof that does not use it). The paper is written in French, but you can find a proof at https://www.proofwiki.org/wiki/Order-Extension\_Principle.

When Adya states that he chooses the real-time order of events, the best guess is that he assumes an implementation of the database; in this case, every history $H$ corresponds to an execution of the database, where events are totally ordered; such an order is the real-time order. More specifically, by requiring that the partial order $\<$ in a history $H$ is extended by the real-time (total) order, Adya imposes that whenever $e\_1 \< e\_2$ in $H$, then the instant of time $t\_1$ at which the event $e\_1$ takes place (in the execution of the database that leads to $H$) is less than the instant of time $t\_2$ at which $e\_2$ takes place. Choosing the real-time order of events to extend the partial order of a history $H$ is needed if one wants to prove the correctness of an abstract specification (i.e. set of properties that a history has to satisfy) with respect to a given specification.

Let's turn to Question 2:

in this case it seems to me that Adya wants to stress the fact that he allows the implementation of a database to access a version of an object which precedes (in the version order) the latest version installed. In practice, choosing an earlier version of an object could be either the result of the database not being able to access such a version (e.g. the lost update anomaly in causal consistency), or the user explicitly requesting to access an older version of an object (e.g. accessing an older version of a revision in a SVN repository).

Hope this helps, Andrea Cerone.

\[1\] Edward Szpilrajn - sur l'extension de l'ordre partiel

---
Tags: terminology, database-theory
---


# Question
Title: if I want only one element of the inverse matrix, does there exist a fast algorithm?
I use Mathematica to solve problems. I have a question about matrix inverse.

if I want only one element of the inverse matrix, does there exist a faster algorithm than using `Inverse` to calculate the whole inverse matrix and extract the element which I want?

# Answer
I have not seen exactly this in Mathematica but I think being able to solve an equation set for only one unknown may be supported.

The direct way would be of course to implement the inverse matrix algorithms and have them stop when the particular element is determined. It would probably be interesting to see what optimizations you can have for each algorithm if the goal is to get one element only.

But according to the first paragraph, one idea could be to express your matrix inverse as unknowns in equation system and then try solving only for the unknown you need (since solving equation set for a single unknown should be supported). If you get better memory and CPU performance then it may be safe to say that Mathematica did not actually solve the whole equation but just did its optimizations to determine only your unknown. You may get worse performance of course since you are not using inverse algorithms directly. If you decide to try let us know if it worked!
> 1 votes

---
Tags: algorithms
---


# Question
Title: How to Know Whether a Topic is Publishable in Computer Science
Forgive my ignorance, but I am very new to the publishing process in Computer Science. I have some research that I have done involving analyzing data formats used in web-based image processing applications being presented in various IEEE papers. Some are conference papers and some actual IEEE transactions. They all seem to proposing the use of XML or in very few cases JSON as the data formats of choice.

I have read a few IEEE papers done on data traversal speeds involving comparisons made between XML and JSON or one of those two with that of CSVs, but not all three. And I have not found anything that give clear direction for one's reasoning for selecting a particular data format and why. Have I simply missed something? Tis likely, but I wanted to confirm with others first.

I have developed a small proof of concept here, and found some interesting results that I wrote about it here and wanted to see if this is worth trying to publish. Is this a good place to get insights, and share ideas that could be publishable? If so, does anyone have any insight into whether the material I have here is of interest to the scientific computing community? Or is this just a clever IT solution?

I am in the process of refining the paper to include tests done in compiled as well as an interpreted languages. Not to mention the reasoning behind selecting other data formats like CSV or TSV, which appear to much faster to traverse than JSON or XML, but less flexible. JSON appears to be the best choice on average, but more testing is required.

If this is not appropriate, let me know and I will remove this posting. Please also let me know if it is indeed appropriate and if you need more information or less and more of a synopsis.

Thank you in advance.

# Answer
> 6 votes
I'm not from this field, but I believe the following advice holds in any field.

First of all, I will suggest reading related literature; always a good idea. What do people in the field say about this topic? Is there an active community working on it? If not, you may find it hard to publish this work.

In my discipline it is quite acceptable to publish workshop papers. These do not "formally" count as a publication (they don't normally publish proceedings); however, your paper will get reviewed (not very deeply) and if accepted for presentation you will get even more feedback at the workshop itself. You can of course submit it to several workshops: this is perfectly acceptable practice, and I've seen it done with papers that contain only preliminary results.

What's more, this will tell you where your paper stands. If it gets rejected from a workshop on the topic, this is probably a good indication that it's not ready for publication yet.

**Important note:** it is absolutely fine to submit a paper to more than one workshop; it generally **-not-** acceptable to make concurrent submissions. That is, submitting to one conference before the outcome of a previous submission is decided. This is highly frowned upon in most communities I'm familiar with (tantamount to self-plagiarism), and will almost certainly make you look very bad. What's more, this will help you for two reasons:

1. It'll give you a chance to review the feedback you got from the reviewers, and possibly improve your paper.
2. Communities tend to be small; if you double-submit a paper, there's a non-zero probability that it'll be reviewed by the same people repeatedly (I have had the chance to review the same paper more than once, and I'm fairly junior in my field). Not only will you piss off anyone adversarial to your work by making them read it again, it will also indicate to them that you are not serious and are just "spamming".

So, submit your paper to one workshop, wait for the outcome, then submit to another.

Of course, the tradeoff here is that it'll delay the publication of the work. That said, you may want to acquaint yourself with the field and what's going on by going to a workshop or two, even if your paper is not accepted.

Another alternative is to simply send your working paper to a number of experts in the field and ask their opinion. My experience is that even prominent researchers will seriously answer such queries if the work is comprehensive enough.

Good luck!

---
Tags: image-processing, information-retrieval
---


# Question
Title: What's the difference between studying "Software Development", "Software Engineering", "Computer Science" and "Information Technology"?
I really cannot understand the key-differences between those fields of study. Can please someone explain it in detail? If one graduates from a Master program of Computer Science, how does he differ from the one graduated from a Software Engineering program, or one from IT?

# Answer
As D.W. wrote this is somewhat subjective since there is no standard definitions for those fields of study. Regarding your last question, my experience in a couple of European universities is that "Computer Science" is a more theoretical program, often branched from a math faculty while "Software Engineering" is more practical, often part of the Engineering faculty.
> 3 votes

# Answer
Think of it as the difference between someone who is an economist verses someone who is a mathematician specializing in econometrics and or probability theory as it applies to market behavior. One has looked deeper into the math than the other, and is therefore going to be able to project and apply more meaningful solutions to problems that apply to economics.

The same can be said when comparing someone with an IT background specializing in Software Engineering versus a Computer Scientist focussing on Software Engineering. Your IT Software Engineer in going to more concerned with the production of software as it applies to a business strategy or profit, not what data structures and algorithms will yield the best performance based $\Theta(n)$ vs $\Theta(\sqrt{n})$ in a system, or how to prove the correctness of a database query using relational calculus or relational algebra.

One ventures into the depths of scientific and mathematical reasoning concerning software and the other develops solutions to business or government problems using software - a more shallow approach to the same problems if you will.
> 2 votes

---
Tags: software-engineering
---


# Question
Title: Are there some real-world optimization problems with very cheap objective functions?
Many real world optimization tasks (especially black box optimization) have objective functions, which are quite expensive to evaluate. For example to find the optimal shape of an airplane wing, a computer model of the wing needs to be constructed and then a large physical simulation needs to be executed, usually taking many hours.

Are there some real-world optimization tasks that have optimization functions which are extremely cheap (on the order of milliseconds) to evaluate? The only thing that comes to my mind are some classical functions, such as the travelling salesman problem with up to a few hundred nodes. The evaluation of a solution consists just of adding a few hundred numbers, which is easily accomplished on the desired time scale. Unfortunately, I am not convinced that the TSP is a real-world problem, since it is so simple.

# Answer
If you don't consider the Traveling Salesman Problem to be "real-world" enough, maybe take a look at its close cousin the Vehicle Routing Problem (VRP). In particular, consider all the variations of VRP, many of which clearly have their origins in real-world situations (e.g.: time windows, backhauls, etc...). This survey (pdf) by Eksioglu et al. details many of these variations. And, as far as I can tell, VRP objective functions are not much more difficult to evaluate than those of TSPs.
> 2 votes

---
Tags: optimization, applied-theory, evolutionary-computing
---


# Question
Title: Trying to understand how the first Hadamard gate in Deutsch–Jozsa algorithm works
I'm still a beginner in the quantum aspect of computer science (self-studying). So please bear with me if this may sound like a stupid question.

I know Hadamard gate transforms qubit into a superposition state with $\frac{1}{2}$ chance that the outcome would be 0 or 1 when the wave function collapses:

$$\frac{\left|0\right\rangle + \left|1\right\rangle}{\sqrt2} \text{ for }\left|0\right\rangle \\ \frac{\left|0\right\rangle - \left|1\right\rangle}{\sqrt2} \text{ for }\left|1\right\rangle$$

For already-in-a-superposition qubit, it would be just some linear transformation.

$$\alpha\left|0\right\rangle + \beta\left|1\right\rangle \rightarrow \alpha \frac{\left|0\right\rangle + \left|1\right\rangle}{\sqrt2} + \beta \frac{\left|0\right\rangle - \left|1\right\rangle}{\sqrt2} = \frac{\alpha+\beta}{\sqrt2}\left|0\right\rangle + \frac{\alpha-\beta}{\sqrt2}\left|1\right\rangle $$

But I got really confused when I see the $\Sigma \left|x\right\rangle$ in the equation on the Wikipedia article about Deutsch–Jozsa algorithm.

> A Hadamard transformation is applied to each bit to obtain the state

Why is it doing a summation with a ever-increasing value of $x$? My understanding of a qubit is that it can only be in either $\left|0\right\rangle$, $\left|1\right\rangle$ or a superposition state.

What the equation is doing above appears to indicate that if $n$ is 2, we would get

$$\frac{1}{\sqrt{2^{3}}} \left|0\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \frac{1}{\sqrt{2^{3}}}\left|1\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \\\frac{1}{\sqrt{2^{3}}} \left|2\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \frac{1}{\sqrt{2^{3}}} \left|3\right\rangle (\left|0\right\rangle - \left|1\right\rangle)$$

How do I make sense of the $\left|2\right\rangle$ and $\left|3\right\rangle$?

\[Update\]

As I was writing the question, I remembered that qubits in the state of $\left|1\right\rangle$$\left|0\right\rangle$ are often expressed as $\left|10\right\rangle$. Since we are working with two-state system here I figured out that the 2 and 3 should be converted into binary in this context. And therefore the expression should be interpreted as

$$\frac{1}{\sqrt{2^{3}}} (\left|0\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \frac{1}{\sqrt{2^{3}}}(\left|1\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \\\frac{1}{\sqrt{2^{3}}} (\left|10\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \frac{1}{\sqrt{2^{3}}} (\left|11\right\rangle (\left|0\right\rangle - \left|1\right\rangle)$$

It appears that things are making a lot more sense now. But as I take a deeper look into the expression above, two questions come to me:

1. Why do I see so many $\left|0\right\rangle - \left|1\right\rangle$ but not a single $\left|0\right\rangle + \left|1\right\rangle$ ? (Intuitively I expect to see just one $\left|0\right\rangle - \left|1\right\rangle$ since we can only get $\frac{\left|0\right\rangle - \left|1\right\rangle}{\sqrt2}$ when it is in the state of $ \left|1\right\rangle$ and there is only one qubit in $ \left|1\right\rangle$).
2. Why are there only $2^{n}$ possible states with each having the chance of $(\sqrt{2^{3}})^2$ when the input is $2^n+1$ qubits? Adding four $(\sqrt{2^{3}})^2$ together doesn't give us 1.

# Answer
> 4 votes
After studying the maths behind it, I realized that a linear algebraic expression for a quantum state may not appear to be intuitive at first sight (or prehaps it is only to the not mathematically gifted ones like myself).

Apparently, this is how the expression in the Wikipedia page is derived:

$$\begin{align} &\frac{\left|0...0\right\rangle + \left|0...1\right\rangle + \left|1...1\right\rangle}{\sqrt2 ... \sqrt2} \cdot \frac{1}{\sqrt{2}} (\left|0\right\rangle - \left|1\right\rangle)\\ =&\sum^{n}\_{x=0}\frac{1}{\sqrt{2^n}} \left|x\right\rangle \cdot \frac{1}{\sqrt{2}} (\left|0\right\rangle - \left|1\right\rangle) \\\=&\sum^{n}\_{x=0}\frac{1}{\sqrt{2^{n+1}}} \left|x\right\rangle \cdot (\left|0\right\rangle - \left|1\right\rangle) \\ =&\frac{1}{\sqrt{2^{n+1}}} \sum^{n}\_{x=0} \left|x\right\rangle (\left|0\right\rangle - \left|1\right\rangle) \end{align}$$

Now this explains why it is alright to have the four $\frac{1}{\sqrt{2^{3}}}$ probability amplitudes above, which is indeed just the product of $\frac{1}{\sqrt{2^{2}}}$ and $\frac{1}{\sqrt{2}}$.

$\frac{\left|0...0\right\rangle + \left|0...1\right\rangle + \left|1...1\right\rangle}{\sqrt2 ... \sqrt2} \cdot \frac{1}{\sqrt{2}} (\left|0\right\rangle - \left|1\right\rangle)$ sure feels like we are having a superposition state within a superposition state (I'm not sure if that is the correct way to interpret it). And this is probably what makes an entangled system so magical when it comes to computation.

---
Tags: algorithms, quantum-computing
---


# Question
Title: Getting sum of all numbers contained in substrings of S on a segment
I have a string of digits $S$ and *K* queries $l\_i, r\_I$ - get the sum of all numbers contained in segment of $S$ from $l\_i$ to $r\_i$.

For example, $S$ = 1034, $l = 1$, $r = 3$. So answer will be $1 + 10 + 103 + 3$ (note: $03$ was not counted, as it starts with $0$)

It has an obvious solution with $O(K\cdot N)$ performance, but I need the faster one. It looks like I need to use ***segment tree*** for storing these sums, but I can't figure out how to do it when $|\ S\ |\>2$. If it's possible to use segment tree I'll get an $O(K\log{N})$ solution, it'll be great.

Any ideas of how to use segment tree here?

# Answer
> 0 votes
$O(N \log K)$ running time looks achievable.

Hints:

* Suppose you know the answer to the query $l,m$ and the query $m+1,r$. Can you work out the answer to the query $l,r$ efficiently? Would precomputation help? What information do you need to know?
* Use a balanced binary tree, where each digit is at a leaf. At each internal node $\eta$, you will store the answer to the query $l\_\eta,r\_\eta$, where $l\_\eta$ is the leftmost leaf under $\eta$ and $r\_\eta$ is the rightmost leaf under $\eta$. Also, story the sum of all numbers that can be made by starting at index $i$ (for $l\_\eta \le i \le r\_\eta$) and ending at index $r\_\eta$, as well as the sum of all numbers that can be made by starting at $l\_\eta$ and ending at some index $j$ (where $l\_\eta \le j \le r\_\eta$).

Now for any particular query $l,r$, the answer can be obtained efficiently given only $O(\lg K)$ numbers in the tree.

I'll let you have the joy of working out the rest, since this sounds like a programming contest problem and you should probably make some effort on your own.

---
Tags: data-structures
---