# Question
Title: Undergrad resources for identifying regular languages with Myhill-Nerode matrices
I am taking an undergraduate CS Theory course and the material on finite automata and regular languages is being taught in a non-traditional manner. Instead of using regular expressions, the closure properties of regular languages, the pumping lemma etc, to show that a language is or is not regular, all of our proofs and examples for identifying regular languages use the Myhill-Nerode theorem and boolean matrices as defined below.

Let $L = \\{w\_1, w\_2, ...\\}$ be a set of words over some alphabet $\Sigma$ and let $T\_L$ be a matrix with entries $t\_{ij}$ where

$$ t\_{ij} = \left\\{ \begin{array}{ll} 1 & \mbox{if } w\_iw\_j \in L \\ 0 & \mbox{otherwise} \end{array} \right. $$

Then by Myhill-Nerode, L is non-regular iff all rows of $T\_L$ are distinct.

**Correction:** Then by Myhill-Nerode, $L$ is non-regular iff $T\_L$ has an infinite number of distinct rows.

My question is, are there any readily available books, papers, or lecture notes that lean heavily on this technique and are appropriate for undergrads?

# Answer
I wanted to make this a comment, but it is too long.

First, your definition of the matrix is poorly written and probably wrong. There is no reason to introduce indices $i, j$. My *guess* is that the right definition is the following: $T$ is the infinite matrix $(T\_{u,v})\_{u, v \in A^\*}$ defined by $$ T\_{u,v} = \begin{cases} 1 &\text{if $uv \in L$}\\ 0 &\text{otherwise} \end{cases} $$ Next, your claim

> $L$ is non-regular if and only if all rows of $T$ are distinct

is wrong. Take $A = \\{a, b\\}$ and $L = \\{ u \in A^\* \mid |u|\_a = |u|\_b\\}^1$. Then $T\_{1,v} = T\_{ab,v}$ for all $v \in A^\*$, so the rows $T\_{1, -}$ and $T\_{ab,-}$ are equal although $L$ is not regular. What is true however is that $L$ is regular if and only if $T$ has finitely many distinct rows.
${}\_{\text{(1) $|u|\_c$ denotes the number of occurrences of the letter $c$ in $u$.}}$

**References**. The matrix $T$ is used in the larger setting of noncommutative formal power series under the name of *Hankel matrix*. Here is a good reference, but I am afraid it is not really appropriate for undergraduate students.

\[1\] J. Berstel and C. Reutenauer, Noncommutative rational series with applications. Encyclopedia of Mathematics and its Applications, 137. Cambridge University Press, Cambridge, 2011. xiv+248 pp. ISBN: 978-0-521-19022-0
> 2 votes

---
Tags: regular-languages, finite-automata, education, matrices
---


title: Which grammar is this?

text:
# Question
Title: Which grammar is this?
Having the grammar `G = (V,P,S)` with variable `V = {S,A}` over the alphabet `{a,b}` with the rules:

> S-\>aA
>
> A-\>Sbb|b

How can i recognize which kind of grammar is this? I think that's not "regular expression" because in the second rule there are 2 letters (bb) instead of one, so i think it's a "context free" grammar. Am i right?

# Answer
Technically it is a linear grammar, where every production is of the form $A\to uBv$ where $A,B$ are variables, and $u,v$ are terminal strings. The linear languages are in between the regular and context-free languages.

The power of these grammars is reduced because in every string (sentential from) derived there is (at most) one variable. They are more powerful than right-linear grammars because the terminal strings that are generated during the derivation can appear both left end right from the variable. An example of a linear language that is not regular is $\\{a^nb^n \mid n\ge 1\\}$. An example of a language that is context-free, but not linear, is $\\{ w\in\\{a,b\\}^\* \mid w \text{ contains the same number of $a$ and $b$}\\}$.
> 1 votes

---
Tags: regular-languages, context-free, regular-expressions
---


title: Definition P-Completeness

text:
# Question
Title: Definition P-Completeness
I've got this problem:

> * Write down a definition of P-completeness analogous to the definition of NP-completeness, i.e., using polynomial-time reductions.
> * Which problems are P-complete in this sense, and why?
> * Thus, what is the problem, i.e., what must be changed if the goal is to come up with a more interesting notion of P-completeness?

I have an idea about the first part, but I don't have any idea about the second and third part. The first part is like the NP-Complete, and small change for P-Complete, which is wrong I know, but I want it that way!

# Answer
You should really work this out yourself, but here are a few hints.

Define P-completeness just as you say, by taking the definition of NP-completeness and changing NP to P. Then ask yourself which problems are P-complete. For a problem to be P-complete it must be in P. What about the other condition? Can you come up with a problem in P which you'd conjecture shouldn't be P-complete under your definition?

Once you've answered part 2, you will be able to answer part 3, so don't despair if you have no idea what they want in part 3 right now.
> 5 votes

# Answer
Looking at the definition of P-completeness in Wikipedia may help you. So let me quote part of this article, which gives a solution to your third question:

> Formally, a decision problem is **P-complete** (complete for the complexity class P) if it is in P and that every problem in P can be reduced to it by using an **appropriate reduction**.
>
> The specific type of reduction used varies and may affect the exact set of problems. If we use **NC reductions**, then **all P-complete problems lie outside NC** and so cannot be effectively parallelized, under the unproven assumption that NC ≠ P. If we use the weaker **log-space reduction**, this remains true, but additionally we learn that all P-complete problems lie outside L under the weaker unproven assumption that L ≠ P. In this latter case the **set P-complete may be smaller**.

But if you use **polynomial reduction** instead, the set of P-complete problems will be P, and thus the definition would not be very exciting.
> 1 votes

---
Tags: complexity-theory, reductions
---


# Question
Title: Calculating the number of non-intersecting routes in an Euclidean graph
I have an Euclidean graph: each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices. I found a geometric proof that every optimal TSP solution contains no intersections.

How many non-intersecting routes could be there? Or in other words: what is the probability to guess an optimal solution to a TSP problem if we just enumerate or sample non-intersecting routes?

**Edit:** I want to ignore the case that D.W. mentioned. For every path that you can swap between two neighbors vertices(If we represent the path as an array of vertices so neighbors will be two vertices with consecutive indexes) without changing its non-intersecting quality, all of those paths will be considered as one.

**Edit** I found that this kind of removing crossings from the graph also know as 2-OPT

# Answer
There are exponentially many such routes.

Think of a sequence of $n$ diamonds. At each diamond, you can go either left or right, independently of what you do at all other diamonds. This leads to $2^n$ paths, each of which is non-intersecting. Now the complete graph on those vertices contains all of these paths, plus some more, so this is a lower-bound on the number of non-intersecting paths.

Therefore, you can't hope to find the optimal one in polynomial time by guessing or enumerating non-intersecting routes.

You probably could have guessed or suspected this, from the fact that Euclidean TSP is NP-complete....
> 10 votes

---
Tags: algorithms, graphs, graph-traversal, traveling-salesman, weighted-graphs
---


# Question
Title: Towers of Hanoi but with arbitrary initial and final configuration
Recently, I came across this problem, a variation of towers of hanoi.

Problem statement:

> Consider the folowing variation of the well know problem Towers of Hanoi:
>
> We are given $n$ towers and m disks of sizes $1,2,3,\dots,m$ stacked on some towers. Your objective is to transfer all the disks to the $k^{\text{th}}$ tower in as few moves as you can manage, but taking into account the following rules:
>
> * moving only one disk at a time,
> * never moving a larger disk one onto a smaller one,
> * moving only between towers at distance at most $d$.
>
> (Limits in the original problem: $3 \le n \le 1000$ and $m \le 100$. Number of test cases $\le 1000$. You can assume that all the problems can be solved in not more than $20000$ moves.)

It's an interesting one. The classic towers of hanoi problem has one source, destination and temporary tower that is used to move the disks from source to destination. The problem pitched on that site basically has an initial and final configuration.

How does one approach this problem?

# Answer
The most succesful approach to deal with the original version of the Towers of Hanoi is using Pattern Databases (PDBs). The current state of the art is described in "Recent Progress in Heuristic Search: A Case Study of the Four-Peg Towers of Hanoi Problem"

Pattern Databases are an automated means for deriving admissible heuristics which are necessary in order to find optimal solutions (as your problem requires). In the particular case of the Towers of Hanoi, some discs are preserved while others are just ignored. This results in a smaller state space which can then be fully traversed with a backward breadt-first search algorithm. It is traversed with a breadth-first search to derive optimal lengths in this *abstract* state and it is traversed from the goal node $t$ (i.e., backwards), to ensure that the optimal lengths computed are relative to the goal. Since the abstract space is smaller, these distances are admissible estimates in the original state space.

This said, I would highly recommend using PDBs again for solving this particular problem since "*moving only between towers at distance at most $d$*" is trivial since pegs are not abstracted, only the discs.

I do not see, indeed, any reason to change the typical approach just in view of this particular constraint.

Hope this helps,
> 2 votes

---
Tags: algorithms, combinatorics, recursion, towers-of-hanoi
---


# Question
Title: What is the difference between Decision Support System and Machine Learning?
I have started reading about Decision Support Systems which according to wikipedia is "a computer-based information system that supports business or organizational decision-making activities".

I have seen papers suggesting intelligent decision support systems, does that means a DSS necessarily utilizes Machine Learning ? How is a DSS different from Machine Learning or vice versa.

# Answer
Decision Support Systems (DSSs) are devoted to the management of large volumes of data. Its main goal is to simulate decision-making procedures that actually simulate (or show) some intelligence. This is why the wikipedia see DSSs well related to business processes ---as they are, indeed.

Machine Learning (ML) is used to infer or derive new knowledge from existing one usually expressed in the form of static data and optionally, as dynamic data or rules. The new knowledge is also expressed in one or both forms.

In general, DSSs and ML are different in their scope. ML is not expected to serve to take decisions though some mechanisms produce new data in such a form that a recommendation becomes apparent (e.g., when using clustering algorithms). Instead, ML can serve in the back for DSSs which I see as a more general system: it is not only in charge of taking decisions but also of managing data, the human-machine interaction (e.g., implementing Mixed-Initiative procedures), and a number of additional modules such as an explanatory module which provides additional evidence of the decisions taken.

None of these processes (necessarily) exist in ML: no need to manage data in any particular way (and indeed data is usually assumed to come either in a declarative way, e.g., PROLOG, or in a large Database conveniently designed, e.g., as in RapidMiner); no particular interface is usually required since the interesting *product* is the new knowledge which is writen usually in the same format than the input; no need to produce explanations of the learnt knowledge (though, admittedly, some mechanisms produce a trace that can be revisited to verify the learnt knowledge).

Other than these rather theoretical (but not really) considerations, let me emphasize that many (if not all) DSSs usually consist of Expert Systems (even nowadays) while ESs are not a form of ML.

Hope this helps,
> 3 votes

---
Tags: terminology, machine-learning
---


title: Memory complexity?

text:
# Question
Title: Memory complexity?
I am unclear about finding the memory complexity of an algorithm.

Some places refer memory complexity as what container would be carrying for instance:

```
for i = 1 to n-1
     if d[i] == d[i + 1]
           d[i] = (d[i] + 5) mod 13

```

Is considered as having $\theta(N)$ memory complexity.

At some other places how much data we write to a container is a complexity for instance:

```
reverse_list(n)

    Stack res
    while (n != NULL)
         res push n
         n = n->next
    while (res != null)
         a = pop res
         print a

```

Is considered as having a memory complexity of $\theta(N)$ too. Moreover:

Such thing is considered having $\theta(1)$ memory complexity

```
reverse_list(head)
    last = NULL;
    while(last != head)
        current = head
        while(current->next != last)
            current = current->next
        print current
        last = current

```

I know how these algorithms work and what they do, but I don't understand how are we meant to be analysing their memory complexity. Could someone explain that please?

# Answer
> 10 votes
Memory complexity is the size of *work memory* used by an algorithm. In the relevant Turing machine model, there is an read-only input tape, a write-only output tape, and a read-write work tape; you're interested only in the work tape. This makes sense since work memory is the additional memory that the specific algorithm uses. For example, if it is called recursively, then it is only this additional memory that is added per each recursive call.

Under this definition, the first code snippet that you provided uses $O(1)$ memory (when memory is measured in machine words rather than bits). Perhaps the algorithm enclosing it allocates the array `d`, and in that case the memory taken by the array is considered work memory; but if the array is given as an input, then it isn't considered work memory.

The second algorithm constructs a list of size $N$ (where $N$ is the length of the input), and so uses $\Theta(N)$ work memory. The third algorithm uses two local variables, and so uses $\Theta(1)$ work memory.

# Answer
> 1 votes
The memory complexity of an algorithm is the amount of memory it uses.

(Just like the fact that the time complexity of an algorithm is the amount of computing time it uses.)

If the inputs to the algorithm take more than $\Theta(1)$ space, sometimes we might use the phrase "memory complexity" to refer to the amount of extra memory the algorithm requires, over and above whatever is needed to store the inputs.

---
Tags: complexity-theory, algorithm-analysis, asymptotics, space-complexity
---


title: Computability vs Complexity?

text:
# Question
Title: Computability vs Complexity?
In Theoretical Computer Science, which one is more important? Computability of a problem or Complexity of a problem?

# Answer
> 1 votes
Both computability and complexity are theoretical abstractions. A theoretical abstraction is most useful, if the gap between theory and practice is small.

1. It is well known that there is a large gap between a problem whose solutions is computable in theory, and one whose solution is computable in practice. Complexity theory managed to shrink that gap considerably, to the point where the remaining gap is caused by factors like cache behavior, parallelization, large scale distribution and similar advanced practical issues.
2. Computability theory has been able to prove that certain problems can't be solved. One might believe that there can't be any gap between theory and practice here, but this is not the case. It seems like Gödel's incompleteness theorems from 1931 would prove that the consistency of the Peano axioms can't be decided. However, Gentzen proved the consistency of the Peano axioms in a paper published in 1936. I know that there is a nice theoretical explanation for this, but I'm (still) unable to judge the practical consequences, and I guess I'm not alone in this.
3. Complexity theory still struggles to rigorously prove lower bounds for most important practical problems, even so it slowly advances in this direction. One may question whether these theoretical lower bounds are important at all, because we have no guarantee that the practical lower bounds have to respect these theoretical bounds. However, it turns out that the practical lower bounds closely match the theoretical lower bounds, so that this objection is unfounded in practice.
4. The above comparison might suggest that computability theory is not much use in practice compared to complexity theory. However, things like the Chomsky hierarchy and a bunch of other similarly useful results should easily disprove this suspicion.

---
Tags: algorithms, complexity-theory, computability
---


title: What is a preterm parser?

text:
# Question
Title: What is a preterm parser?
I am working with HOL-Light parser and keeping seeing references to preterm parser.

What is a preterm parser?

The most informative statement I find is from the HOL-Light reference for the parse\_pretype function.

> This is mostly an internal function; pretypes and preterms are used as an intermediate representation for typechecking and overload resolution and are not normally of concern to users.

# Answer
> 0 votes
Since HOL Light is based on $\lambda$ Calculus and HOL Light is typed and as we know there is untyped $\lambda$ Calculus and typed $\lambda$ Calculus, HOL Light starts by parsing something close to untyped $\lambda$ Calculus, creating pre-terms. Then it applies a typing checking and typing phase, along with resolving overloaded operators resulting is something closer to typed $\lambda$ Calculus. Obviously HOL is much more than typed $\lambda$ Calculus, but the point here is to understand what pre-term means with regards to parsing.

The only reference I have found for this is in

Lectures on the Curry-Howard Isomorphism
Section 1.2 Pre-terms and $\lambda$-terms.

Specifically how this is done in HOL Light is in the parser module:

The pre-terms are created with

```
let ptm = (parse_pteterm << lex << explode) input

```

and the type checking, etc. is done with

```
let term = (term_of_preterm << (retypecheck [])) ptm

```

---
Tags: lambda-calculus, parsers, type-checking
---


# Question
Title: Proving Little-Oh notation by definition
I need to prove by definition (show that for every $C$ there exists a $n\_0$) that: $$5n^2+3n= o(n^3-4n)$$

By trying to simplify the expression I get to the point where I should prove that: $$ \frac{5n^2+3n}{n^3-4n} \< C$$.

Now, showing that $\lim\limits\_{x\to\infty} \frac{5n^2+3n}{n^3-4n} = 0$ isn't a tough mission, but how do I prove it by definition? How do I point out specific $n\_0$ for every $C$ that comes up? I'm asked to provide a tight answer and not let $n\_0 = C^C$ so that the $n\_0$ for sure will be large enough but to point out $n\_0$ that is reasonably small.

# Answer
Either you do what David suggested, or you do something like this:

Let $c \> 0$. Then

\begin{align} 5n^2 +3n &\le c(n^3-4n) &\iff \\ 5n+3 &\le cn^2-4c &\iff \\ 0 &\le cn^2-5n-(3+4c) \end{align}

Now solve for $n$ and let $n\_0$ be the bigger root of that term.
> 4 votes

# Answer
You don't have to prove every single step by definition. So, prove that the limit is zero and then use the definition of "the limit as $x$ goes to infinity is zero" to show that the definition of $o(-)$ is satisfied.
> 2 votes

---
Tags: asymptotics
---


# Question
Title: Which priority queue implementations are stable?
I can't answer this question. It seems simple but I really don't know how to approach it. Here it is:

> A priority queue is said to be stable if deletions of items with equal priority value occur in the order in which they were inserted. Which of the following priority queue structures are stable:
>
> * linked lists ordered in increasing priority (key)
> * balanced search trees (e.g., 2-3 trees)
> * heaps
> * leftist heaps
>
> Explain why, or give counter-examples.

I don't need a full solution just a way to approach this problem. I would prefer to solve it on my own.

# Answer
Here's how I would suggest that you approach the problem. Try running each data structure by hand on some small examples. Then, based on those examples, see if you can form any conjecture about which data structures are stable and which ones aren't. For the ones you suspect are stable, try proving it. For the ones that you suspect are not stable, try to come up with a counterexample to demonstrate that they're not stable.
> 2 votes

---
Tags: data-structures, priority-queues
---


# Question
Title: Known bounds on space complexity of multiplication decision problem
Given three numbers $m$, $n$ and $p$ in interleaved binary encoding1, it's obviously possible to check in $O(1)$ space whether $m+n=p$. It's less obvious2 that it isn't possible to check in $O(1)$ space whether $m\cdot n=p$. I wonder whether one can prove that it isn't possible to check in $O(\log N)$ space3 whether $m\cdot n=p$. On the other hand, are there any known non-trivial upper bounds on the space complexity of this problem, like $O(N/\log N)$?

The problem described above is a simplified version of the "Multiplication decision problem: Is the $k$th bit of the product of $m$ and $n$ a one?" Since this problem is more "powerful" (and also better known), I wonder whether one can show that this problem can't be decided in $O((\log N)^2)$ space.

---

 1. The interleaved binary encoding starts with the lowest significant bit, and allows "leading" zeros for the most significant bits.

 2. The proof idea I have in mind would use such an algorithm as building block for a decision procedure of Robinson arithmetic. I call this less obvious, because the fact that Robinson arithmetic is undecidable may be well known, but still remains non-trivial.

 3. Here $N$ is the length of the input $m$, $n$ and $p$ in binary encoding.

# Answer
> 1 votes
You can do it in $O(\lg N)$ space, if you're willing to accept a randomized algorithm with an exponentially small probability of error. In practice, this algorithm is practical and every bit as good as a deterministic algorithm with no possibility of error.

The idea is to choose a random $\ell$-bit prime $\alpha$, reduce $m,n,p$ modulo $\alpha$, and then check whether the congruence $m\times n \equiv p \pmod{\alpha}$ holds modulo $\alpha$. This test can be done with $O(\ell)$ bits of space (about $3\ell$ bits). Moreover, it suffices to take $\ell = O(\lg N)$. In particular, if you want the probability of error to be at most $1/2^t$, it suffices to take $\ell=O(t + \lg N)$. The constants hidden by the big-O notation are small (something like 3 or so).

Now take $t=100$, and you get a practical algorithm. The probability of error is $1/2^{100}$, which is so small as to be negligible. It's more likely that you have a cosmic ray bit flip that causes your computation to give the wrong answer than that you get a wrong answer due to bad luck. (And cosmic ray bit flips affect deterministic algorithms, too, so the notion of an algorithm with zero error is not something that can be implemented in the real world; the best we can hope for is for the probability of error to be negligible.)

---

The analysis of this relies upon the prime number theorem. I don't have time to write out the full analysis right now, but the basic idea is that the algorithm gives the wrong answer only if $\alpha$ divides $mn-p$. Since $|mn-p|$ is (at most) $2N$ bits long, there can be at most $2N/\ell$ distinct $\ell$-bit prime divisors of $mn-p$. Also, by the Prime Number Theorem, there are about $2^{\ell}/\ell$ possible $\ell$-bit primes. Therefore, the probability that the randomly chosen $\alpha$ happens to divide $mn-p$ is at most $(2N)/2^{\ell}$. Now solve for $\ell$, and you get the result I claimed above.

Importantly, the probability of error is taken only over the internal coin flips of the algorithm, *not* over the possible values of $m,n,p$. In other words, even if an adversary chooses the values of $m,n,p$, the probability of error will still be at most $1/2^t$.

---
Tags: space-complexity, binary-arithmetic
---


title: Prove language is not regular?

text:
# Question
Title: Prove language is not regular?
I know how to use the pumping lemma to do so, but I don't think that can be used for this language:

$$L = \\{x \in \\{0,1\\}^\* : \text{no prefix of $x$ has more $1$'s than $0$'s}\\}. $$

What other method can I use to prove this?

# Answer
> 1 votes
Hint: use $0^n1^n$ for large enough $n$.

Another approach is to use the Myhill-Nerode criterion, say with the words $0^n$.

---
Tags: regular-languages, proof-techniques
---


title: What can be defined as a Regular Set

text:
# Question
Title: What can be defined as a Regular Set
I'm currently studying compilers and am having some issues with understanding regular sets. For example, lets say I had a set of binary strings, (0, 1). Would all integers that are even and positive be considered part of a regular set? Lets say I have that same set, but instead of being even, they are divisible by 5, would it still be a regular set?

I've been looking at this helpful guide I found online, but I'm still confused about what can be defined as a regular set.

# Answer
> 2 votes
A regular set is the same thing as a regular language. You haven't explained how to encode integers, but suppose you encode an integer in binary notation, MSB first; so each zero is represented as $0$, and all other numbers start with $1$. The set of even positive integers is the represented by the regular expression $1(0+1)^\*0$ (why?), and so is regular. The set of non-negative integers divisible by $5$ is also regular, since there is a DFA that accepts it; the minimal DFA has $5$ states corresponding to the value of the current prefix modulo $5$, which is updated in the obvious way. I'll let you figure out the details.

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


# Question
Title: Minimal size of contracting a DAG into a new DAG
We have a DAG. We have a function on the nodes $F\colon V\to \mathbb N$ (loosely speaking, we number the nodes). We would like to create a new directed graph with these rules:

1. Only nodes with the same number can be contracted into the same new node. $F(x) \neq F(y) \Rightarrow x' \neq y'$. (However, $x' \neq y'\nRightarrow F(x) \neq F(y)$.)
2. We add all the old edges between new nodes: $(x,y) \in E \land x' \neq y' \iff (x',y')\in E'$.
3. This new graph is still a DAG.

What is the minimal $|V'|$? What is an algorithm creating a minimal new graph?

# Answer
One approach to solving this problem would be to use integer linear programming (ILP). Let's tackle the decision version of the problem: given $k$, is there a way to contract same-color vertices to get a DAG of size $\le k$?

This can be expressed as an ILP instance using standard techniques. We're given the color of each vertex in the original graph. I suggest that we label each vertex with a label in $\\{1,2,\dots,k\\}$; all vertices with the same label and same color will be contracted. So, the decision problem becomes: does there exist a labelling, such that contracting all same-color same-label vertices yields a DAG?

To express this as an integer linear program, introduce an integer variable $\ell\_v$ for each vertex $v$, to represent the label on vertex $v$. Add the inequality $1 \le \ell\_v \le k$.

The next step is to express the requirement that the contracted graph must be a DAG. Notice that if there is a labelling of the form listed above, without loss of generality there exists such a labelling where the labels induce a topological sort on the contracted graph (i.e., if $v$ precedes $w$ in the contracted graph, then $v$'s label is smaller than $w$'s label). So, for each edge $v\to w$ in the original graph, we'll add the constraint that either $v$ and $w$ have the same label and same color, or else $v$'s label is smaller than $w$'s label. Specifically, for each edge $v\to w$ in the initial graph where $v,w$ have the same color, add the inequality $\ell\_v \le \ell\_w$. For each edge $v \to w$ where $v,w$ have different colors, add the inequality $\ell\_v \< \ell\_w$.

Now see if there is any feasible solution to this integer linear program. There will be a feasible solution if and only if the labelling is of the desired form (i.e., contracting all same-color same-label vertices yields a DAG). In other words, there will be a feasible solution if and only if there is a way to contract the original graph to a DAG of size $\le k$. We can use any integer linear programming solver; if the ILP solver gives us an answer, we have an answer to the original decision problem.

Of course, this isn't guaranteed to complete in polynomial time. There are no guarantees. However, ILP solvers have gotten pretty good. I would expect that, for a reasonable-sized graph, you've got a decent chance that an ILP solver might be able to solve this problem in a reasonable amount of time.

It's also possible to encode this as a SAT instance and use a SAT solver. I don't know whether that would be more effective. The ILP version is probably easier to think about, though.

(I hope this is right. I haven't checked every detail carefully, so please double-check my reasoning! I hope I haven't gone awry somewhere.)

---

Update (10/21): It looks like ILPs of this form can be solved in linear time, by processing the DAG in topologically sorted order and keeping track of the lower bound on the label for each vertex. This has me suspicious of my solution: have I made a mistake somewhere?
> 5 votes

# Answer
**NOTE: AFAICT, D.W found a hole in this reduction and it is wrong (see comments). Keeping it here for historical reasons.**

**Intro**: first I will reduce the ***Monotone 3SAT*** problem to our problem. Though the ***Monotone 3SAT*** problem is trivially satisfiable, our problem can further solve the ***Minimum True Monotone 3SAT*** problem, which is NP-hard; thus this problem is NP-hard.

## Reduction from ***Monotone 3SAT*** to our problem

We have a monotone boolean formula expressed as a sequence of variables, and a sequence of clauses. The CNF is of the form $\Phi = (\mathcal V,\mathcal C)$ such that:

$$\forall\_{\left(c\_i \in \mathcal C\right)} ~ \left.c\_i=\left(x\_j \vee x\_k \vee x\_l\right) \vphantom{\LARGE | } \right|\_{\left(x\_j,x\_k,x\_l \in \mathcal V\right)}$$ and

$$\left.{\Large{\bigwedge}}\_{i=1}^{n}{c\_i}\right|\_{\genfrac{}{}{0}{}{c\_i\in \mathcal C,}{n=\left|\mathcal C\right|}}.$$

### Conversion

We construct a graph, $G'=V',E'$. Each vertex in $G'$ has a label; vertices with the same label are eligible for contraction.

First we construct the graph as follows: for each $x\_i \in \mathcal V$, we make two nodes, each labeled $x\_i$, and a directed edge from one to the other (click images for high resolution view).

These nodes can of course be contracted, because they have the same label. **We will consider variable/nodes that are contracted to be valued as false, and those that are uncontracted to be valued as true**:

After this step, $V'$ should contain $2\cdot \left|\mathcal V\right|$ nodes. Next, we introduce the clause constraints. For each clause, $c\_i \in \mathcal C, ~ \left.c\_i = (x\_j \vee x\_k \vee x\_l) \right|\_{x\_j,x\_k,x\_l \in \mathcal V}$, we introduce ***one*** node $c\_i$, and the following edges:

Note the duplicatation of $c\_i$ is for viewing purposes only; there is only **$1$** node labeled $c\_i$. (click image for full view)

After this step, we should have $2\cdot \left|\mathcal V\right| + |\mathcal C|$ nodes.

Now, if $x\_i$, $x\_j$ *and* $x\_k$ get contracted, $c\_i \rightarrow c\_i$ will result in a cycle.

Here is another visualization, unrolling the clause constraint:

Thus, each clause constraint requires that at least one of the variables it contains remain uncontracted; since the uncontracted nodes are valued as true, this requires that one of the variables be true; exactly what Monotone SAT requires for its clauses.

## Reduction from Minimum True Monotone 3SAT

Monotone 3SAT is trivially satisfiable; you can simply set all the variables to true.

However, since our DAG minimization problem is to find the most contractions, this translates to finding the satisfying assignment that produces the most false variables in our CNF; which is the same as finding the minimum true variables. *This* problem is sometimes called ***Minimum True Monotone 3SAT*** or here (as an optimization problem, or decision problem), or ***k-True Monotone 2SAT*** (as a weaker decision problem); both NP-hard problems. Thus our problem is NP-hard.

---

References:

Graph sources:
> 5 votes

# Answer
With each replacement (except for direct-parent-child replacements), you add new ancestor-descendant relationships that make it non-trivial to determine which one is actually worth it in the long-term. Therefore, a simple greedy algorithm will fail in the general case. However, if you do a brute-force approach, you can determine the smallest graph:

Python-ish (not tested):

```
def play((V,E),F,sequence=[]):
  """
  (V,E) -- a dag.
  V     -- a set of vertices.
  E     -- a set of directed-edge-tuples.
  F     -- a function that takes a vertex, returns an integer.
  sequence -- the sequence of moved taken so far; starts with/defaults to
              an empty list, will contain tuples of the form (x,y)
              where x is removed and replaced with y.

  Returns the best recursively found solution.
  """

  #find all the integer values in the graph, remember which
  # values correspond to what vertices. Of the form {integer => {vertices}}.
  n2v = {}
  for x in V:
    n = F(x)

    #for each integer, make sure you have a set to put the vertices in.
    if n not in n2v:
      n2v[n] = set()

    #for each integer, add the vertex to the equivalent set.
    n2v[n].add(v)

  #record the best sequence/solution. You start with the current sequence,
  # and see if you can obtain anything better.
  best_solution = list(sequence)

  #Now you will try to combine a single pair of vertices, obtain a new
  # graph and then recursively play the game again from that graph.

  #for each integer and equivalent set of vertices,
  for n,vset in n2v.iteritems():

    #pick a pair of vertices
    for x in vset:
      for y in vset:

        #no point if they are the same.
        if x == y:
          continue

        #If there is a path from x => y or y => x, then you will be
        # introducing a cycle, breaking a rule. So in that case, disregard
        # this pair.
        #However, the exception is when one is a direct child of the other;
        # in that case you can safely combine the vertices.
        if pathtest((V,E),x,y) and (x,y) not in E and (x,y) not in E:
          continue

        #combine the vertices (function is defined below), discard x,
        # replace it with y, obtain the new graph, (V',E').
        Vp,Ep = combine_vertex((V,E),x,y))

        #record the sequence for this move.
        sequencep = list(sequence) + [(x,y)]

        #recurse and play the game from this new graph.
        solution = play(Vp,Ep,F,sequencep)

        #if the returned solution is better than the current best,
        if len(solution) > len(best_solution):
          #record the new best solution
          best_solution = solution
  #return the best recorded solution
  return best_solution

def combine_vertex((V0,E0),x,y):
  """
  (V0,E0)   -- an initial digraph.
  V0        -- a set of vertices.
  E0        -- a set of directed-edge-tuples.
  x         -- vertex to discard.
  y         -- vertex to replace it with.

  returns a new digraph replacing all relationships to and from x to relate
   to y instead, and removing x from the graph entirely.
  """

  #the final vertex set will have everything except x
  V = set(V0)
  V.discard(x)

  #now you construct the edge set.
  E = set()

  #for every edge,
  for (u0,v0) in E0:
    #recreate the edge in the new graph, but replace any occurence
    # of x.
    u,v = u0,v0
    #if x is in the edge: replace it
    if u == x:
      u = y
    if v == x:
      v == y

    #sometimes u=v=y and can now be pointing to itself, don't add that
    # edge
    if u == v:
      continue

    #add the new/replaced edge into the edge-set.
    E.add( (u,v) )
  return (V,E)

```

I am not sure if it really a hard problem, but playing with some graphs manually, it seems very combinatorial. I am curious if something difficult can be reduced to this problem, or if there is an algorithm with better running time.
> 1 votes

---
Tags: algorithms, graphs, np-complete, reductions
---


# Question
Title: Complexity of deciding the satisfiability of a quasi-monotone CNF formula
A *quasi-monotone CNF formula* is a formula where each variable appears at most once as a positive literal (and any number of times as a negative literal).

What is the complexity of deciding its satisfiability?

# Answer
Obviously this can be solved with the same complexity as boolean SAT. The question is, can we do better. The answer is no: this problem is NP-complete.

You can show it is NP-complete by reducing a regular CNF formula to "quasi-monotone" CNF, as follows:

Since you cannot use positive terms in general, what you want is a new, equivalent, variable in-place of the positive terms. So let $\Phi = {\LARGE\bigwedge}C\_i$ be a general boolean sat formula. We will replace all non-negated $x\_j$ terms with new variables called $\neg n\_{x\_j}$. Then, we need to constrain $n\_{x\_j} = \neg x\_j$; so we introduce the following clauses:

$$\left(n\_{x\_j} \implies \neg x\_j\right) \wedge \left(\neg x\_j \implies n\_{x\_j}\right)$$

This essentially means that $n\_{x\_j} = \neg x\_j$. Written in CNF:

$$\left(\neg n\_{x\_j} \vee \neg x\_j\right) \wedge \left(x\_j \vee n\_{x\_j}\right)$$

These two clauses will effectively allow you to replace all your other non-negated terms, and they only leave behind a single non-negated term for each literal (within these clauses), which is allowed in "quasi-monotone" CNF as defined by the question.
> 10 votes

---
Tags: complexity-theory, np-complete, satisfiability, decision-problem
---


title: Grammar generating specific language

text:
# Question
Title: Grammar generating specific language
Construct a context-sensitive grammar that generates L:

```
L = {a^n b^m c^k|k>n, k>m}

```

I believe my productions should go along this lines:

```
S-> ABCC
A-> a|aBC|BC
B-> b|bBC
C-> c|Cc
CB->BC

```

The idea is to start with 2 c and keep always one more c, and then with C-\>c|Cc ad as much c as i want. How can my production for C remember the numbers of m and n.

# Answer
> 1 votes
**Hint.** Can you figure out a regular grammar such that for any $k, m, n$ with $k \> n$ and $k \> m$, there is a word in its language with that number of `a`, `b` and `c` (in any order)?

**Hint.** Did you know that you can sort with a context sensitive grammar? See an example for inspiration.

# Answer
> 0 votes
Maybe this?

```
// end of string marker X
S := TX

// sets up the count relationships
T := TT | AC | BC | C

// sets up the order relationships
BA := AB
CA := AC
CB := BC

// convert to terminals from back to front
Aa := aa
Ab := ab
Ac := ac
Bb := bb
Bc := bc
Cc := cc
CX := c

```

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


# Question
Title: Does a language stay regular if you re-encode the input?
$\tau$ be a transformation that, applied to a word of $\Sigma\_a^\star$, replaces each character with a word from a possibly different $\Sigma\_b^\star$ and concatenates the resulting words. For instance, given a $\tau$ with the following translation table:

```
A -> AA
B -> AB
C -> BA
D -> BB

```

$\tau(ABC)=AAABBA$ and $\tau(DACB)=BBAABAAB$. Note that the words may not all have the same length. A translation table such as

```
A -> FOO
B -> BAR
C -> BAZ
D -> QUUX

```

is also valid.

Now, is $\\{w'|w\in L\land w'=\tau(w)\\}$ regular iff $L$ is a regular language as well?

# Answer
The answer is yes. This is generally called homomorphism, and regular languages are closed under homomorphism. Moreover, regular languages are closed under inverse homomorphism also. More precisely, if $\tau$ is a homomorphism from alphabet $\Sigma$ to alphabet $\Delta$ and $L$ is a regular language over $\Delta$, then $\tau^{-1}(L)$ is also a regular language.

You can take a look here for more details, or the best is to take a look at this book, which contains proofs about basic properties of regular languages.
> 4 votes

---
Tags: regular-languages
---


# Question
Title: Confused about beta-reduction/shifting in untyped $\lambda$-calculus with de Bruijn terms
In *Types and Programming Languages*, the family of sets of terms with de Bruijn indices in the untyped $\lambda$-calculus is defined in this way:

Let $T$ be the smallest family of sets $\\{T\_0, T\_1, T\_2, ...\\}$ such that

1. $k \in T\_n$ whenever $0 \le k \lt n$;
2. if $t\_1 \in T\_n$ and $n \gt 0$, then $\lambda. t\_1 \in T\_{n-1}$;
3. if $t\_1 \in T\_n$ and $t\_2 \in T\_n$, then $(t\_1\ t\_2) \in T\_n$.

The $\beta$-reduction operation is then defined as $(\lambda. t\_{12})\ v\_2 \rightarrow\ \uparrow^{-1}(\[0 \mapsto\ \uparrow^1(v\_2)\]t\_{12})$, where $\uparrow^d(t)$ is the function to add $d$ to the indices of all free variables in $t$. By the definition of the $\uparrow$ function, if $t \in T\_n$, then $\uparrow^d(t) \in T\_{n+d}$. Substitution is defined like so:

1. $\[j \mapsto s\]k = s\ $if $k = j; k$ otherwise
2. $\[j \mapsto s\](\lambda. t\_1) = \lambda. \[j+1 \mapsto\ \uparrow^1(s)\]t\_1$
3. $\[j \mapsto s\](t\_1\ t\_2) = (\[j \mapsto s\]t\_1\ \[j \mapsto s\]t\_2)$

I can't seem to get these definitions to work properly in manually reducing the term $((\lambda. 0)\ (\lambda. 0))$ (i.e. the identity function applied to itself). Here are the steps I've gone through in attempting to apply the $\beta$-reduction rule; I'll add a subscript to each term indicating which set in $T$ I think the term is in, so e.g. $(\lambda. 0\_1)\_0$ is an abstraction of $0 \in T\_1$, and the abstraction itself is in $T\_0$. I believe that if done properly, $((\lambda. 0\_1)\_0\ (\lambda. 0\_1)\_0)$ should reduce to $(\lambda. 0\_1)\_0$.

* $(\lambda. 0\_1)\_0\ (\lambda. 0\_1)\_0$
* (by def. of $\beta$-reduction) $\rightarrow\ \uparrow^{-1}(\[0 \mapsto\ \uparrow^1((\lambda. 0\_1)\_0)\] (\lambda. 0\_1)\_0)$
* (by def. of $\uparrow$) $\rightarrow\ \uparrow^{-1}(\[0 \mapsto (\lambda. 0\_2)\_1\] (\lambda. 0\_1)\_0)$
* (by def. 2 of substitution) $\rightarrow\ \uparrow^{-1}(\lambda. \[1 \mapsto\ \uparrow^1((\lambda. 0\_2)\_1)\]0\_1)$
* (by def. of $\uparrow$) $\rightarrow\ \uparrow^{-1}(\lambda. \[1 \mapsto (\lambda. 0\_3)\_2\]0\_1)$
* (by def. 1 of substitution) $\rightarrow\ \uparrow^{-1}(\lambda. 0\_1)$

Now I've worked myself into a corner - $\uparrow^{-1}(\lambda. 0\_1)$ should reduce to $(\lambda. 0\_0)\_{-1}$, which is nonsensical. I also haven't actually performed any substitutions, which seems like it must be incorrect. Am I misapplying these definitions somehow?

# Answer
> 3 votes
I figured it out - I was messing up the $\beta$-reduction in the first step by applying the substitution to $(\lambda. 0\_1)\_0$ instead of just $0\_1$. This is the correct sequence of reduction steps:

* $(\lambda. 0\_1)\_0\ (\lambda. 0\_1)\_0$
* (by def. of $\beta$-reduction) $\rightarrow\ \uparrow^{-1}(\[0 \mapsto\ \uparrow^1((\lambda. 0\_1)\_0)\] 0\_1)$
* (by def. of $\uparrow$) $\rightarrow\ \uparrow^{-1}(\[0 \mapsto (\lambda. 0\_2)\_1\] 0\_1)$
* (by def. 1 of substitution) $\rightarrow\ \uparrow^{-1}((\lambda. 0\_2)\_1)$
* (by def. of $\uparrow$) $\rightarrow\ (\lambda. 0\_1)\_0$

---
Tags: lambda-calculus, types-and-programming-languages
---


title: How to reverse a subarray of an array

text:
# Question
Title: How to reverse a subarray of an array
How to reverse the order of elements in an array between indices $i$ and $j$.

Ex: For the array `[A,B,C,D,E,F]`, calling the function `reverse(array, 1,4)` will modify the array to be `[A,E,D,C,B,F]`.

I want to optimize the solution to work with multiple calls on the same array, so pre-computations allowed. What would be the most efficient way to do so?

# Answer
> 7 votes
Let me restate the problem. We're given an array $A\_0$ and a sequence $(\ell\_1,r\_1),\dots,(\ell\_m,r\_m)$. Set $A\_{i+1}=\text{reverse}(A\_i,\ell\_i,r\_i)$. The goal is to compute the array $A\_m$.

The naive way to solve this is to just incrementally apply the reverse operations, i.e., incrementally invoke Yuval's `reverse` algorithm $m$ times. The running time of the naive solution is $\sum\_{i=1}^m (r\_i-\ell\_i)$. The question is, can we do better?

---

The answer is, yes, in some cases. It's possible to build a data structure to optimize the sequence of reversal operations, in a way that's faster than the naive solution. With sufficient cleverness, you can get the total running time down to $O(n + m \lg n)$ -- in comparison, the naive algorithm could potentially be as large as $O(nm)$, in the worst case. I'll explain how to do it below.

We can model the desired rearrangement by a permutation $\pi$ on the array indices. Such a permutation acts on arrays: given any array $\pi$ and any permutation $\pi$ on the indices, we can obtain an array $\pi A$, namely, the array $A'$ given by $A'\[\pi(j)\]=A\[j\]$. Notice that the operation $\text{reverse}(A,\ell,r)$ should return the array $\pi A$, where $\pi(j)=\ell+r-j$ for $\ell \le j \le r$ and $\pi(j)=j$ for all other $j$. Let $\text{rev}(\ell,j)$ denote this permutation.

This gives us a new strategy for solving the problem: first, compute $\pi = \text{rev}(\ell\_m,r\_m) \circ \cdots \circ \text{rev}(\ell\_1,r\_1)$; then, compute $A\_m = \pi A\_0$. The latter step can be done in $O(n)$ time, with no additional space. So, how quickly can we compute $\pi\_m$?

Here is one way to compute $\pi\_m$. We will represent a permutation $\pi$ as an interval tree, i.e., a binary tree where each leaf has an interval on the indices. The intervals on the leaves will be pairwise disjoint, their union will be $\\{1,2,\dots,n\\}$, and they will be in sorted order (from left to right). Each internal node will hold an interval representing the union of the intervals on all of its descendants. Also, we'll annotate each leaf with an affine function of the form $f(x)=x+\alpha$ or $f(x)=\alpha-x$. The idea is that if we have a leaf with interval $\[a,b\]$ and function $f$, then $\pi(j)=f(j)$ for $j=a,a+1,\dots,b$.

In this way, we can represent a permutation as this sort of interval tree. Notice that the identity function can be represented as an interval tree with one leaf, with interval $\[1,n\]$ and function $f(x)=x$. Also, the permutation $\text{rev}(\ell\_m,r\_m)$ corresponding to a single reversal operation can be represented as an interval tree with three leaves, namely $\[1,\ell\_m-1\],f(x)=x$, $\[\ell\_m,r\_m\],f(x)=\ell\_m+r\_m-x$, and $\[r\_m+1,n\],f(x)=x$.

Now suppose we have an interval tree representing $\text{rev}(\ell\_m,r\_m) \circ \cdots \circ \text{rev}(\ell\_{i+1},r\_{i+1})$. Let me explain how to derive an interval tree representing $\text{rev}(\ell\_m,r\_m) \circ \cdots \circ \text{rev}(\ell\_i,r\_i)$. Basically, we search the interval tree to find all leaves whose interval overlaps with $\[\ell\_i,r\_i\]$, and split them in two pieces if they partially overlap (one piece that doesn't overlap, the other piece containing the rest that is contained within $\[\ell\_i,r\_i\]$). Then, for each such leaf that overlaps $\[\ell\_i,r\_i\]$, if it currently contains the function $f$, we replace it with the function $g \circ f$, where $g(x)=\ell\_i+r\_i-x$.

So, we iteratively do this. When we're done, we have an interval tree representation of $\pi$. Now we can compute $\pi A\_0$ in linear time. The running time to construct the interval tree is now dependent on the number of intervals that get treated differently. In other words, say that indices $j,j'$ are treated differently if there exists some $i$ such that $j\in \[\ell\_i,r\_i\]$ but $j'\notin \[\ell\_i,r\_i\]$ (or vice versa); otherwise, say that $j,j'$ are treated the same. Now construct the equivalence classes of the "treated the same" equivalence relation. Each equivalence class is one interval in the final interval tree, so the total running time is related to the total number of such equivalence relations. In particular, if there are $k$ intervals in the final interval tree (i.e., $k$ such equivalence classes), then the running time is $O(mk+n)$.

---

It's possible to speed this up even further by annotating each internal node with an affine function as well.

The idea is that such an interval tree represents a permutation $\pi$ as follows: if we have a leaf with interval $\[a,b\]$ and function $f\_0$, and its parent has function $f\_1$, and its grandparent function $f\_2$, and so on up to the function $f\_d$ on the root, then for every $j \in \[a,b\]$, we have $\pi(j) = (f\_d \circ \cdots \circ f\_1 \circ f\_0)(j)$. In other words, the effective function on this leaf is the composition of all of the functions on the path from the leaf to the root.

This tree representation is even better: it allows you to derive the tree for $\text{rev}(\ell\_m,r\_m) \circ \cdots \circ \text{rev}(\ell\_i,r\_i)$ from the tree for $\text{rev}(\ell\_m,r\_m) \circ \cdots \circ \text{rev}(\ell\_{i+1},r\_{i+1})$ in $O(\lg k)$ time, where $k = $ the number of intervals in the tree. Basically, we may have to split at most two intervals (one on the left side, if it partially overlaps $\[\ell\_i,r\_i\]$ on the left, and one on the right). Then, we need to compose a function $g(x)=\ell\_i+r\_i-x$ to all of the leaves whose intervals is contained within $\[\ell\_i,r\_i\]$. The latter can be done by identifying $O(\lg k)$ nodes of the tree whose (disjoint) union is $\[\ell\_i,r\_i\]$ (by construction you can always find such a set of nodes), and then composing $g$ with the function at each of those nodes: for each such node, if its function was $f$, you update it to $g \circ f$.

Consequently, the total running time of this improved solution is $O(n + m \lg k)$, where $k$ is the number of intervals in the final interval tree. A conservative upper bound is $O(n + m \lg n)$ to perform $m$ reversal operations on an array of size $n$. This is better than the naive algorithm, whose running time could be as bad as $O(nm)$.

# Answer
> 5 votes
Here is the classical algorithm used to solve the problem:

```
def reverse(array, i, j):
  if i > j: # ensure i <= j
    i, j = j, i
  while i < j:
    array[i], array[j] = array[j], array[i]
    i += 1
    j -= 1

```

For example, `reverse(array, 1, 4)` will swap array\[1\] and array\[4\], and then array\[2\] and array\[3\]. This algorithm makes the minimal amount of swaps, and is optimal op to a multiplicative constant in any reasonable machine model in which it can be implemented.

# Answer
> -3 votes
> Hope this works, the code is self explanatory and is in c#

```
     private static void ReverseSubArray(ref char[] SourceArray, int i, int j)
    {
        int len = SourceArray.Length;
        if (i > len || j > len)
        {
            Console.WriteLine("Improper Index Supplied !");
            Console.ReadLine();
            return;
        }
        else
        {
            int arrayLen = (j - i) + 1;
            char[] NewArray = new char[arrayLen];
            for (int index = i, localIndex = 0; index <= j; index++, localIndex++)
            {
                NewArray[localIndex] = SourceArray[index];
            }
            Array.Reverse(NewArray);
            for (int index = i, localIndex = 0; index <= j; index++, localIndex++)
            {
                SourceArray[index] = NewArray[localIndex];
            }
            Console.WriteLine("Task Done !");
            return;
        }
    }

```

---
Tags: algorithms, arrays
---


title: Basics of Amortised Analysis

text:
# Question
Title: Basics of Amortised Analysis
I cannot really find a source that does not use the same examples provided by CLRS. I need a simpler example than `MULTI-POP` example. Could someone provide an example and explain me:

a) What is the difference between worst-case analysis and amortised analysis?

b) What is the difference between average-case analysis and amortised analysis?

c) In plain English(with using minimal notations), how can we provide a complexity(especially I am interested in potential method)

# Answer
I'll just answer a) and b) because I don't know the potential method.

**About a)** Worst case analysis only considers a single operation. If you want to know how expensive your algorithm is in its worst case, you need to find the worst case cost of every single operation and then count how often each of them is executed. For example, you may have come about a structure called "dynamic array", which is very similar to an `ArrayList` in Java. The way that structure operates is that internally it has an array, and it doubles in size once it's full, copying everything into the new array.

Now what's the worst case cost for an insert operation into that structure? The worst that can happen is that you have to double the array that contains $n$ elements, so you get a worst case cost of 1 operation (!) of $\mathcal{O}(n)$. If you insert $n$ elements, this gives you a worst case running time of $\mathcal{O}(n \cdot n) = \mathcal{O}(n^2)$.

Obviously that is far too pessimistic. We know that we only have to double every $2^k$ steps, because with every time we double the size of the array, it'll take twice as long until we need to double it again. Here is where amortized analysis comes into play: you know that there are some expensive operations, but you also know that they happen comparatively rarely, so you try to see whether the "naive" worst case analysis can be improved with a little bookkeeping. In order to do this reasonably, you don't consider a single operation anymore, you consider a sequence of operations, usually of length $n$.

Maybe you have read about the accounting method: you have an account where you can "save up" time, and every operation is allowed to take "time" out of the account, but no more than is in the account. The idea behind this is that the many cheap operations "help pay" for the few expensive ones, and if we distribute the cost that way, we can get a better analysis (that is still a true upper bound, i.e. the actual complexity is still below the amortized complexity in all cases).

How would that work in the case of the dynamic array? Every "cheap" insert is just one write operation to the array, so that costs us $1$ unit of time. Every "expensive" operation costs us $k$ units where $k$ is the number of elements in the array at that time. Now we would like the cheap inserts to share the cost of the expensive one that they help produce. This can be done if every cheap insert, in addition to paying its own $1$ unit of cost, contributes another $2$ units to the account, because this way, the inserted element pays for the copying of itself and a second one that will be copied when we double. This means that for every expensive insert we have, there will be at least $k$ units of time on our account, and we can pay for it using the money in the account only, so the actual cost of the expensive insert goes down to $k-k = 0$ (because it doesn't actually cause work that hasn't already been paid for, it's paid for with the time that was "saved up" by the cheap inserts using the account savings). How does this help us? Now every cheap insert costs us $1+2=3$ units, and every expensive insert costs us $k-k =0$ units, giving both an amortized cost of $\mathcal{O}(1)$. If we want to calculate the amortized cost of inserting $n$ elements now, we get $\mathcal{O}(1 \cdot n) = \mathcal{O}(n)$, and this is still an upper bound on the actual cost that any input can produce.

**About b)** While amortized analysis still gives you an upper bound on the actual cost of an algorithm, average case analysis doesn't guarantee that; there may be inputs where the actual cost is above the average case cost. But that's not a problem for average case analysis, because it just tells you what the cost of running your algorithm typically is, meaning as an average of the cost of all possible instances of size $n$.
> 4 votes

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


# Question
Title: OOP: exampe and references on constructor anomalies
I have read the following artice that defines the term "constructor anomaly":

Cohen, Tal, and Joseph Gil. "Better Construction with Factories." journal of object technology 6.6 (2007): 103-123. http://www.jot.fm/issues/issue\_2007\_07/article3/

Where can I find examples and references on constructor anomalies? (also in the context of multiplie inheritance)

Are constructor anomalies always due to a method call in the constructor or is it possiple to construct an example without method calls in the constructor?

# Answer
> 3 votes
"Constructor anomaly" is not a bug or anything; it is simply an anomaly on the classification of constructor functions. ie. constructor functions are different from member functions in the following ways.

Anomalous classifications:

* While most member functions require an instance and work on an instance, a constructor does not require an instance, but still works on an instance:

```
  f.bar(); // instance of f, can call bar(). bar() does stuff to/with f.

  new F(); // no instance, yet called F::F(). Yet F::F() does works on an instance.

```
* Most member functions can replace or extend their base-class functions with the same name; that is, a member function can entirely override a base-function (replacement), ... *or* ... it can override, and call the base function as well (extension). However, the constructor (in these languages) *must* extend, that is, call the base-class constructor first. (This is to delegate the base-class's construction to the base-class, first, and then construct the derived class):

```
struct F{
    F(){/*stuff*/}
    virtual void bar(){/*stuff*/}
    virtual void baz(){/*stuff*/}
};
struct G : public F{
    virtual void bar()
    {
      //Do stuff
      F::bar(); // extend F::bar()
      //Do more stuff
    }
    virtual void baz()
    {
      //Do stuff
      //Do more stuff
      //No call to F::baz(), replaced it
    }
    G::G(){
      //this MUST extend F::F(); in C++ F() is called implicitly in this case.
      //However, if F() takes parameters, it must be called explicitly
    }
};

```
* Most member functions can be dynamically bounded; that is, you never know if a (virtual) function `F* f; f->bar()` is calling `F::bar()` or if `f` is a type that derived from `F`; and thus a different `bar` is being called. However, constructors are *always* static, you must know exactly which class you are creating when you create it:

```
H* h = get_h();
h->bar(); // this function can be H::bar(), or anything defined in the virtual table; hence it is dynamic; h can be any derivative of H, overriding H::bar().

F* f = new F(); // the call to F::F() MUST be (statically) linked to F(), not a derivative of F

```

---
Tags: reference-request, programming-languages, object-oriented
---


# Question
Title: Why is Iterative-deepening A* optimal, even without monotonicity?
Why is it that Iterative-deepening A\* is optimal, even without monotonicity? How can I be sure that the first goal reached is the optimal one?

# Answer
In a nutshell: IDA\* traverses all paths of lengths iteratively larger and it stops only when *expanding* (as opposed to *generating*) the goal node with a cost such that all paths of an inferior cost have been already examined. Monotonicity (or consistency) is not required but admissibility of the heuristic function is a must if optimal solutions are required.

Now, how can we achieve that? It is simple. Get rid of the condition of monotonicity and pay attention instead to the condition of admissibility, i.e., $h(n)\leq h^\*(n)$ where $h(n)$ is the heuristic estimate to reach the goal $t$ from node $n$ and $h^\*(n)$ is the optimal cost of reaching the target. In other words, all that is required is that we have a function (i.e., $h(n)$) which provides a lower bound on the cost-to-go.

In the following bear in mind that IDA$^\*$ is nothing more and nothing less than a depth-first search algorithm which prunes children that exceed a particular $f(n)$ value. As in the case of A$^\*$, $f(n)=g(n)+h(n)$ where $g(n)$ is the cost of the path from the start state $s$ to $n$. All we have to do is to decide how to handle $f(n)$ while achieving our goal ...

* **Step 1**: Since we have a lower bound to reach the goal, start IDA$^\*$ with a threshold equal to $h(s)$, the heuristic estimate of the start state. This simply amounts to traverse all paths stemming from $s$ until a node $n$ is found such that $f(n) \> h(s)$. This operation is necessarily finite in locally finite graphs (i.e., with bounded branching factor). While generating paths, note that you stop at those nodes $n$ that meet the aforementioned condition so that you can easily save the minimum excess over $h(s)$
* **Step 2**: Once the first step is over, you know: first, no path of length $h(s)$ gets to the target; second, the next cheaper paths that can be traversed from $s$ have a cost equal to the minimum excess computed in the previous iteration. This is all you need. Proceed now as in Step 1 but using the minimum excess computed in the previous iteration as the threshold. If the iteration ended withouth success apply iteratively until getting to the solution.

Notice the remark I made in the first paragraph: from the behaviour of this algorithm, admissibility is guaranteed if you stop when *expanding* the goal node. This means that all paths of an inferior cost have been already traversed. If you ever stop when *generating* the goal, then you might incurr in suboptimal solutions since those paths might have a cost that exceeds the current threshold of that iteration.

In no place, consistency is required. From Steps 1 and 2, a proof of correctness can be easily derived by induction on the number of iterations.

Hope this helps,
> 6 votes

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


# Question
Title: How is the implementation of pipes in a OS
I understand that a pipe is a form of IPC where a process creates a link to communicate with some other process (a child maybe), taking each one a end of the pipe. File descriptors are created for read and write and they can use it in half-duplex or full-duplex. My question is if the implementation of this schema is something like shared memory or message passing.

# Answer
> 0 votes
Like message passing. The kernel allocates a private buffer for storing the data that has been sent and is waiting to be delivered to the recipient.

For more details, see:

In the future, please do more research before asking. We expect you to do some serious research before asking. The links above showed up in the first few responses to my first Google search, which is a hint that you should have done more research on your own.

---
Tags: operating-systems
---


# Question
Title: techniques for finding relevant words in a huge list of strings
I have a huge list of strings. The goal is to make a database of "relevant" words.

Of course in the context of what I work with, "relevance" is something akin to the organization I work with. For e.g. if it is a automobile manufacturing industry they'd buy products like

```
Automotive assembly equipment
Radial tyres
Etc

```

If it were an aircraft manufacturing industry:

```
Fabricated Aluminium Body
Hydraulic Fluid
Skydrol
Jet Fuel
Etc...

```

Issue is that I might come across so many spelling mistakes, abbreviations, and variations.

So what is a technique I can prepare a database of words like these when I have nothing to start with, except a huge list of strings.

# Answer
> 5 votes
This is still an open problem. You can use some techniques like Stemming the words of the strings and counting them called Bag of Words Approach. Most occurring words comes most of the time are in your relevant words list.

However, you would find that non-informative words like 'the', 'is' are coming most of the time in the answer. Simplest way would be to create a dictionary of stop words of english or of the language that would include words that can be discarded. It can contain prepositions, conjunctions, pronouns, articles or may be frequent verbs, as according to your requirements. You can use a Trie for creating this fast lookup dictionary.

However, there is another approach that would find the words that are most occuring. It is called TF/IDF. This is used when you have different documents/strings to compare to each other. It gives you a value for each word that would be proportional to how much it occurs in this document but not in other documents. So words like 'the', 'is' would have comparatively less value. However, if your strings have words like Aluminium in most of them, it would also be having low value. so use it with caution.

Another thing that i would like to point out about the use of TF/IDF is that you would have to divide your data into some parts, to compare to each other. TF/IDF would give result for each of these parts. Lets say if you take each of your string as one part, then it would give you a huge set of key-words since you have a huge set of strings. It would be better to randomly partition your huge-set-of-strings into say 2 or 4 or 8 parts and then find keywords for each part and then take either intersection or union.

The trick is to use different methods and use one that gives the best results.

For spelling mistake you can create a BKTree, that would allow you to find how much two words differ in their spelling mistakes. If you add this approach, it can give you better or worse results. For e.g. if you allow words with one difference acceptable, it would treat bat and cat the same. But it would also take care of Aluminium and Allminium.

---
Tags: algorithms
---


title: Reachable state space of an 8-puzzle

text:
# Question
Title: Reachable state space of an 8-puzzle
I've just began studying Artificial Intelligence and am wondering why the reachable state space of an 8-puzzle is $9!/2$. I see that the number of permutations of the tiles is $9!$ but it is not immediately obvious why half the possible states of the puzzle are unreachable at any given state. Can anyone elaborate?

*An image of an 8-puzzle for reference with a random configuration on the left and the goal state on the right:*

# Answer
> 13 votes
This is an expansion of this presentation.

Because the state graph consists of two disconnected components of equal size. Without loss of generality we can assume that the *target state* is $1\\;2\\;3\\;...\\;15\\;\Box$.

```
 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15  *

```

Given a state $S$ a *permutation inversion* is a tile $T\_i$ that is placed after $T\_j$ but $i \< j$; this happens when (a) $T\_i$ is in the same row of $T\_j$, but on its right, or (b) $T\_i$ is in a lower row:

```
 .  .  .  .      .  .  .  .
 3  .  .  1      .  7  .  .
 .  .  .  .      .  5  .  .
 .  .  .  .      .  .  .  .
    (a)             (b)

```

We define $N\_j$ as the number of tiles $T\_i$, $i \< j$ that appears after $T\_j$. For example, in the state:

```
 1  2  3  4
 5 10  7  8
 9  6 11 12
13 14 15  *

```

we have that after $T\_{7}$ there is one tile ($T\_6$) that should be before it, so $N\_7=1$; after $T\_{10}$ there are four tiles ($T\_7, T\_8, T\_9, T\_6$) that should be before it, so $N\_{10}=4$.

Let $N$ be the sum of all $N\_i$ and the row number of the empty tile $T\_{\Box}$

$$N = \sum\_{i=1}^{15} N\_i + row(T\_{\Box})$$

In the example above we have: $N = N\_7 + N\_8 + N\_9 + N\_{10} + row(T\_{\Box}) = 1 + 1 +1 + 4 + 4=11$

We can notice that when the empty tile is moved *horizontally* $N$ doesn't change; if we move the empty tile *vertically* $N$ changes by an even quantity.

For example:

```
 .  .  .  .      .  .  .  .
 .  .  2  3      .  .  *  3
 4  5  *  .      4  5  2  .
 .  .  .  .      .  .  .  .

```

$N' = N + 3 \mbox{ (2 is placed after 3,4,5)} - 1 \mbox{ (empty tile is moved up)} = N + 2$

```
 .  .  .  .      .  .  .  .
 .  .  *  4      .  .  3  4
 2  5  3  .      2  5  *  .
 .  .  .  .      .  .  .  .

```

$N' = N + 1 \mbox{ (2 is placed after 3)} - 2 \mbox{ (4,5 are placed after 3)} + 1 \mbox{ (empty tile is moved down)} = N$

So $N \bmod 2$ is *invariant under any legal move of the empty tile*.

We can conclude that the state space is split in two *disconnected* halves, one having $N \bmod = 0$ and the other having $N \mod 2 = 1$.

For example the following two states are not connected:

```
 1  2  3  4     1  2  3  4
 5  6  7  8     5  6  7  8
 9 10 11 12     9 10 11 12
13 14 15  *    13 15 14  *
    N = 4         N = 5

```

---
Tags: artificial-intelligence
---


# Question
Title: Measuring uniformity of CRC32 by using birthday problem
I would like to measure what is the probability that given some data and it's CRC32 checksum there is some other data with the same checksum.
Running the simulation is not feasible because of the 2^32 possible values.
Running the simulation for the birthday problem is feasible (check if there is a collision among n checksums)
Is there a way to infer the probability mentioned above by simulating the birthday problem?

# Answer
> 1 votes
This question has nothing to do with the birthday paradox.

The birthday paradox says, given a collection of $n$ people, what are the chances that some pair of them have the same birthday.

Your question is analogous to the following: given a specific date (say, April 17), and given a collection of $n$ people, what are the chances that one of them has a birthday on that date (on April 17). That has a very different answer from the birthday question.

As the question was posed, David Richerby has the right answer: due to the properties of the CRC checksum, it is guaranteed that there exists another message that has the same CRC.

If you want to *find* such a message, there are standard techniques using linear algebra (see e.g. https://crypto.stackexchange.com/a/698/351).

If you want to know, given a 32-bit checksum $c$ and a collection of $n$ messages, what is the probability that at least one of those $n$ messages has checksum $c$, this can be computed too. That probability is $1-(1-2^{-32})^n \approx 1-e^{-n/2^{32}}$, due to the properties of the CRC (when the message is uniformly distributed, so too is the CRC).

# Answer
> -1 votes
I assume you are essentially asking "given that I have produced $N$ random 32-bit numbers, what is the probability that all $N$ are unique?"

There are $Q=2^{32}$ ways to choose the first number, $Q-1$ ways to choose the second number, $Q-2$ ways to choose the third number, and so on. So there are $\frac{Q!}{(Q-N)!}$ ways of choosing $N$ numbers that are unique. Yet there are a total of $Q^N$ ways of choosing $N$ random numbers from the range $1\ldots Q$, so the probability that all $N$ chosen numbers are unique is $$ \frac{Q!}{Q^N (Q-N)!}. $$

You can calculate it exactly with:

$$ \prod\_{k=0}^{N-1}\frac{Q-k}{Q}. $$

Or using Stirling's approximation, $n! \approx (\frac{n}{e})^n \sqrt{2 \pi n}$, and the truncated Taylor series, $\ln (1+x) \approx x$, I get the approximation

$$ e^{\frac{N}{Q} (\frac{1}{2} - N)}. $$

---
Tags: probability-theory
---


title: clarification in tf-idf formula

text:
# Question
Title: clarification in tf-idf formula
According to the wiki-article, http://en.wikipedia.org/wiki/Tf%E2%80%93idf the term frequency of term $t$ in document $d$ is given as follows: $$ tf(t,d) = 0.5 + \frac{0.5 \times f(t,d)}{\max{\\{f(w,d): w~\epsilon~d\\}}} $$

This is the augmented way of computation. But what does $w$ stand for?

# Answer
> 0 votes
A document is modeled as a set $d$ of words. Since we're maximizing $f(w,d)$ over all $w\in d$, this means that $w$ ranges over all possible words contained in $d$.

In the future, please check a textbook before asking. We expect you to do some research on your own before asking, and this is a standard topic that's well-covered in standard explanations of tf-idf.

---
Tags: search-algorithms
---


# Question
Title: Prove that a $k$-regular bipartite graph with $k \geq 2$ has no cut-edge
Although this seems rather obvious, I couldn't prove it rigorously. Any ideas how to prove it? The graph is assumed to be simple and connected.

Explanation of the terms:

* $k$-regular means that all vertices have degree $k$;
* bipartite means that there are 2 sets of vertices $X, Y$, where vertices from $X$ only have edges with vertices $Y$ and vertices from $Y$ only have edges with vertices from $X$;
* cut-edge is an edge which removal disconnects the graph;

This is b) part of the exercise, maybe a) part can help:

a) If all vertices $v \in G$ have an even degree, $G$ does not have cut-edge

From a) it actually follows that for even $k$, b) is true, thus only case with odd $k$ left to prove.

# Answer
Ok, here is a simple proof I came up by myself. I was apparently going the wrong way in trying to prove the exercise.

**Proof**. Suppose edge $e$ is a cut-edge. Study graph $G-e$. For any $v \in G-e$ other then $e$ endpoints $x, y$, the vertex degree $d(v) = k$, and $d(x)=d(y)=k-1$.

Now, since graph $G$ is bipartite, graph $G-e$ remains bipartite. Also, because $e$ is a cut-edge, $G-e$ is composed of 2 components $H\_1, H\_2$, which are also both bipartite, and each contains exactly one of $x, y$. Assume WLG that $H\_1$ has vertex $x$, that $H\_1$ has vertex bipartition $X\_1, Y\_1$ and that $x \in X\_1$.

Clearly, in subgraph $H\_1$, we have

$S\_1 = \sum\_{v\in X\_1 }d(v) = k(|X\_1|-1) + k-1$ and $S\_2 = \sum\_{v\in Y\_1 }d(v) = k(|Y\_1|)$, and $S\_1$ can't be equal $S\_2$ unless $k=1$. However, it must be the case that $S\_1 = S\_2$ in a bipartite graph. Thus, our initial assumption that $e$ is a cut-edge was wrong. Therefore, $G$ has no cut-edge. $\Box$
> 5 votes

---
Tags: graphs
---


title: XOR-like behavior in flow networks

text:
# Question
Title: XOR-like behavior in flow networks
*XOR is not the correct name, but I am looking for some kind of exclusive behavior.*

I am currently solving a set of different (assignment) problems by modeling flow networks and running a min-cost-max-flow algorithm. Flow networks are quite handy because a lot of problems can be reduced to them in an easy and understandable way. In my case these are matchings with some additional constraints. As these constraints are getting more complex I've been wondering if there are some existing constructions to model specific behaviors.

In this case I want to restrict the outgoing flow of a node to a single edge.

Given a graph $G=(V, E)$, integral capacities $c(u,v)$ and costs $k(u,v)$. An arbitrary node is called $A$. It's direct neighbors are called $B\_1, ..B\_n$. Can we replace the edges $AB\_1,...AB\_n$ (red) with some construction so that **only one edge can receive flow**? Which means that if $AB\_1$ gets some flow (e.g. $5/10$) no other (red) edge can receive flow.

We could add intermediate nodes/edges and play with costs and capacities. The total capacity of our new construction has to stay the same and the cost of the different alternatives have to stay somehow proportional.

So my questions are:

1. Are there constructions like this in general? (Any keywords, links, papers)
2. Can you suggest a solution to my specific problem?

# Answer
> 6 votes
In general, the answer is no. If we put XOR-like restrictions on the out-going edges of a vertex, we can prove that finding a min-cut-max-flow is NP-Hard. The technique is to reduce 3-SAT to it.

Let's assume there are $n$ variables $x\_1, x\_2, ..., x\_n$ in the 3-SAT and $m$ clauses $c\_1, c\_2, ..., c\_m$. We create a graph $G(V,E)$ encoding the instance of the 3-SAT problem. For each variable $x\_i$, we create a vertex $v\_i$ connected to the source $s$ with an edge of $\infty$ capacity. Two more vertices $u\_i, w\_i$, which are connected to $v\_i$, are created to represent $x\_i$ taking the value 0 or 1 also with edges of capacity $\infty$.

For each of the clauses $c\_i$, we create a vertex $o\_i \in G$ corresponding to it and $o\_i$ is connected to the variables or their negations in the clause with edges of capacity $1$. For example, if $c\_i = (x\_3 \lor x\_4 \lor \neg x\_5)$, we connect it to $u\_3, u\_4, w\_5$ with edges of capacity. All $o\_i$ are connected to the sink with edges of capacity 1.

Since $x\_i$ and $\neg x\_i$ cannot take the same value, we put the XOR restriction on edges $(v\_i, u\_i)$, $(v\_i, w\_i)$, $\forall i = 1,2,3,...,n$. It can be proved that there is a maximum flow of size $m$ if and only if the 3-SAT instance is satisfiable. Since the problem is trivially in $NP$ and the reduction is polynomial, we conclude the decision version of XOR restriction network flow is NP-Complete.

# Answer
> 3 votes
For your first question, I do not know any general techniques or rules of thumb that you can use to model arbitrary restrictions in flow networks. Most examples I have seen are generally based on some intuition about the nature of restrictions, and often at first seem arbitrary.

For your particular case, I have yet to come up with a good mapping to max-flow. However, I can suggest a simple alternative solution (you might have already figured that out): Depth First Search from source $s$.

As the flow is restricted to only one outgoing edge for every vertex, what you have is a *path* from the source to the target. This path satisfies the two properties that it can carry the maximum flow among any other paths from source $s$ to target $t$, and that it has the lowest cost among all such paths that could carry the same flow from $s$ to $t$.

* Start a DFS from the $s$
* As you go down the DFS, keep track of the current minimum capacity of all edges encountered thus far.
* Also keep track of the current total cost (path length) encountered so far.
* If $t$ is reached during the DFS, compare these two values with global values, and update the global values if necessary.
* Backtrack from $t$ and continue with the DFS.

Basically, you enumerate all paths from $s$ to $t$ using the DFS, and choose the one that satisfies your criteria of min-cost and max-flow. The DFS itself takes $O(|E|)$ time, which is more efficient than a max flow algorithm.

# Answer
> 2 votes
To build on Paresh's answer, if all the max capacities are one (and everything else is integer), you could also split each node into two so that node (n-) has all the in edges, node (n+) has all the out edges, and (n-) and (n+) are connected with an edge of max capacity 1. Solve this new min-cost network and you are done.

If the max capacities are not all one, then the problem is harder. You can formulate the problem as a MIP (Mixed Integer Program). The only integer constraints are the XOR constraints.

Fortunately, these can be modeled as Special Ordered Sets - type SOS1 (see http://en.wikipedia.org/wiki/Special\_ordered\_set). Most MIP solvers specifically represent SOS1 constraints and will handle them much more efficiently (sometimes you need to tell it, sometimes it will figure it out - check your solver docs).

Although the MIP will *eventually* converge to the optimum answer, for really large models, you may not have the time to wait for it to finish. Getting large MIPs to converge is often more art than engineering.

The next suggestion is a lot more work. You could use a min-cost-network solver as a subroutine and do you own branching on the XOR edges using SOS1 techniques. For example, on each branch, turn off the least-used 1/2 of the out edges, resolve the min-cost network (very fast), repeat until all the XOR constraints are satisfied.

You could prioritize the branching sequence by your own criteria (flow volume, volume X cost, reserved capacity, number of possible edges, etc.). By guiding the search yourself, you can hone in on the parts of the solution that are most important to you.

You don't indicate whether you always know whether your problem is feasible or not. If it is always feasible, you might be able to get away with a branching strategy that is "backtrack free", that is, you follow it like a heuristic.

If the problem is not guaranteed to be feasible, a MIP could go away forever. A heuristic based on the above may still be valuable to find a solution quickly with a relatively low number of violations.

# Answer
> -2 votes
In general, the answer is unknown, not impossible!

we conclude the decision version of XOR restriction network flow is NP-Complete. therefore (it's possible, we can do that) if and only if P=NP.

---
Tags: algorithms, graphs, network-flow, assignment-problem
---


# Question
Title: Generalized operators for programming languages
After asking this question on stackoverflow, it has changed slightly. Is there a way to represent a grammar as a basis for a vector space and represent a program as an object that lives in that vector space?

I'm interested in the parallels between mathematical operators (like the Hamiltonian, ladder operators, momentum operators, etc) and programming languages. The operators that I'm talking about can be thought of as transformation matrices that act on (potentially) infinite vectors. It seems like a good place to start might be a tree algebra?

An alternative would be to force the program into some sort of allowed bitwise representation, and then perform transforms on it. Is such a thing possible?

# Answer
You might be interested in the citations provided in the following post on CSTheory.StackExchange: https://cstheory.stackexchange.com/q/19091/5038 They get at something roughly similar to what you are asking for.

See also the algebraic theory of parsing, e.g., https://cstheory.stackexchange.com/q/9000/5038 It seems like it too might be in the space that you are interested in.
> 1 votes

---
Tags: formal-grammars, linear-algebra, category-theory
---


# Question
Title: Is there an adjustment for Adler32 algorithm so it works well on short messages?
The Adler32 algorithm has a shortcoming as noted on Wikipedia:

> Jonathan Stone discovered in 2001 that Adler-32 has a weakness for very short messages. He wrote "Briefly, the problem is that, for very short packets, Adler-32 is guaranteed to give poor coverage of the available bits. Don't take my word for it, ask Mark Adler. :-)"

If I am only computing a checksum on packets that are around 1,500 bytes long, is there an adjustment to Adler32 to make it work well in this case? Alternatively, is there another algorithm that is as fast as Adler32 but does not have such weaknesses? What about the Fletcher algorithm - does it suffer the same weakness?

# Answer
> 3 votes
In \[1\], the authors show that for 1500 bytes, the chance of an undetected collision with Adler32 is less than one in 100 billion.

In that paper, see Figure 13 which states:

> Comparison of 8-, 16-, and 32-bit Fletcher and Adler checksums using random data at a BER of
> 10-5. The data point values are the mean of 10 trials.

And shows probability of undetected error using Adler32 to below 10-11 for a 1500 byte message.

Therefore, as D.W. suggested above, no adjustment is needed.

---

\[1\] Maxino, Theresa C., and Philip J. Koopman. "The effectiveness of checksums for embedded control networks." Dependable and Secure Computing, IEEE Transactions on 6.1 (2009): 59-72.

---
Tags: algorithms, hash
---


# Question
Title: Object recognition - given an image, does it contain a particular 3D object of interest?
I have in mind a particular 3D object. Given an image taken by a camera, I want to check whether that image contains an instance of my object.

For instance, let's say that the object is a bathroom sink. There are many kinds of bathroom sinks, but they tend to share some common elements (e.g., shape, size, color, function). There can also be significant variation in lighting and pose. Given an image, I want to know whether the image contains a bathroom sink.

How do I do that? What technique/algorithm would be appropriate? Is there research on this topic?

Of course, it is easy to use Google Images to obtain many example images that are known to contain a bathroom sink (or whatever the object I'm looking for might be), which could be used for training some sort of machine learning algorithm. This suggests to me that maybe some combination of computer vision plus machine learning might be a promising approach, but I'm not sure exactly what the specifics might look like.

# Answer
> 4 votes
If you have one or several images of a particular "sink" or object, then you can possibly use SIFT or SURF or other feature extraction/matching algorithms to match the objects up. You can investigate the OpenCV project (wikipedia, project); it includes many of these (possibly patented) algorithms. You can get an idea of how they work and what they can do by searching youtube for "opencv". If you specialize in matching previously known instances of a particular object, this might be appropriate. Additionally, there is much research specializing in facial recognition, so you can possibly find work on that.

Another project of interest: Sketch2Photo: Internet Image Montage. I don't know how they do it though, or if it can reliably identify anything; it seems to rely on some sort of recognition, and semantics search as well (you must name the objects in the sketch). You can read their paper (PDF)

If you want to recognize a generic "sink" concept or many multiple generic concepts, then it is bordering on strong(er) AI. There are lots of machine learning projects, and I am not sure which are useful for this or practical, but to demonstrate how cutting edge this is (and possibly not practical unless you spend a lot of time and research), Google (paper (PDF)) has made a giant GPU neural network that it successfully trained to recognize cats, presumably learning some sort of ability to conceptualize a more abstract "idea" of what a cat looks like. Related work by Yoshua Bengio; wired article; open source project.

This is "cutting edge", so again not practical, but just pointing out that you are trying to recognize generic things, and Google is working so hard just to recognize generic cats, you are in for a lot of work, or a restriction/trick/shortcut.

# Answer
> 4 votes
There are multiple approaches which can be taken into account. Some of them are mentioned above.

From what you want I think you should apply a combination of techniques to get good results.

In my opinion you should start with blob matching (affine invariant) -\> followed by keypoint feature matching inside the blob to verify the result.

I think this approach should give reasonable results. Once you have some preliminary results then you can definitely move onto more complicated algorithms using machine learning etc.

---
Tags: machine-learning, image-processing, computer-vision, pattern-recognition
---


title: NP-hardness and FPTAS

text:
# Question
Title: NP-hardness and FPTAS
I have a problem in understanding how to prove the following question.

Let $Q = \langle\max,f,L\rangle$ be an NPO-Problem, where $f$ only supports integers. Define $$L\_Q^\* =\\{(x\_0,1^k) : \exists x . L(x\_0,x) \land f(x\_0,x) \geq k\\}.$$ The instance of $x\_0$ is binary coded, while the numerical parameter $k$ is unary coded. Show that if $L\_Q^\*$ is NP-complete, then there is no FPTAS for $Q$. It can be assumed that $P \neq NP$.

Normally I have some ideas, but this time I am really stumped. My only idea was to use the fact that if $L\_Q^\*$ has an approximation scheme, then $f$ must run in time polynomial in $|x\_0|+|x|$.

# Answer
> 4 votes
Hint: Show that an FPTAS for $Q$ implies a polytime algorithm for $L\_Q^\*$. This contradicts the assumption $P \neq NP$, which is missing from your question but seems to be tacitly assumed.

# Answer
> 1 votes
Short on the Question: The most important step was to use that f supports only integers.

I have to say my idea was not nearly as neat as the one the author suggested. First we remind us of the concept of FPTAS for Q: $$f(x,x\_0) \geq (1-\epsilon) \cdot f(x\_0,x^\*)$$ for some optimal solution $x^\*$
Idea: If there is an FPTAS for Q, then $P = NP$ (Proof by Contradiction).

Show that: $$f(x\_0,x) \geq (1-\epsilon) \cdot f(x\_0,x^\*) \geq k-\frac{1}{2}$$. If we solve $f(x\_0,x^\*)$ we get $(1-\epsilon)\cdot k$: $$f(x\_0,x) \geq (1-\epsilon) \cdot k$$ We know that f will give us an integer, so we take $\epsilon = \frac{1}{2k}$.Now we can decide $L\_Q^\*$ in time $$poly(|x\_0|,\frac{1}{\epsilon}) = poly(|x\_0|,2k) = poly|(x\_0,1^k)|$$. This contradicts our assumption that $P \neq NP$

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


# Question
Title: Sum number of times statement is executed in triple nested loop
I have this code fragment:

```
for( i=0; i<n; i++ )
    for( j=0; j<i; j++ )
        for( k=0; k<j; k++ )
            S;

```

I need to find the number of times that S is executed in that code block. I plugged it into Wolfram Alpha but I am not sure if that is the right answer.

I want to be able to do the math in order to figure the answer out so can someone point me in the right direction?

# Answer
The Wolfram Alpha answer isn't quite correct - you're off by one in each sum - the loop will iterate over $\\{1,...,n-1\\}$, not $\\{1,...,n\\}$, though other than that your reasoning is sound. What you should be asking W/A for is:

$$ \sum^{n-1}\_{i=0}\sum^{i-1}\_{j=0}\sum^{j-1}\_{k=0} 1 $$

If you break the sums down bit by bit it gets a little easier to swallow, just start at the innermost sum and work outwards. It's probably fairly obvious that $\sum^{j-1}\_{k=0}1 = j$, which breaks the triple-sum down into $\sum^{n-1}\_{i=0}\sum^{i-1}\_{j=0}j$.

We have that $\sum^{i-1}\_{j=0}j = \frac{1}{2}(i^2-i)$, so what was a double sum is now the difference of two sums, $\frac{1}{2}(\sum^{n-1}\_{i=0}i^2 - \sum^{n-1}\_{i=0}i)$.

The second term has already been worked out, and we have that $\sum^{n-1}\_{i=0}i^2 = \frac{n(n-1)(2n-1)}{6}$. From there, you should be able to work out your answer;

\begin{align\*} \frac{1}{2}\left(\sum^{n-1}\_{i=0}i^2 - \sum^{n-1}\_{i=0}i\right) &= \frac{1}{2}\left(\frac{n(n-1)(2n-1)}{6} - \frac{3n(n-1)}{6} \right)\\ &= \frac{1}{2}\left((2n-1)\frac{n(n-1)}{6} - 3\frac{n(n-1)}{6} \right)\\ &= \frac{n(n-1)(2n-4)}{12}\\ &= \frac{n(n-1)(n-2)}{6} \end{align\*}

The results about the sum of the first $n-1$ numbers and the sum of the first $n-1$ square numbers are fairly standard ones - if you want some proofs of them then this page gives some nice arguments, though note that their sums end at $n$ and not $n-1$.
> 2 votes

---
Tags: runtime-analysis, loops
---


title: A* optimality of the expanded node

text:
# Question
Title: A* optimality of the expanded node
Suppose I have a admissible and consistent heuristic.

Is it true, that when I expand a node, I have guaranteed that the path I found to this node is optimal?

Look at this pseudocode from wikipedia:

```
function A*(start,goal)
 closedset := the empty set    // The set of nodes already evaluated.
 openset := {start}    // The set of tentative nodes to be evaluated, initially containing the start node
 came_from := the empty map    // The map of navigated nodes.

 g_score[start] := 0    // Cost from start along best known path.
 // Estimated total cost from start to goal through y.
 f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)

 while openset is not empty
     current := the node in openset having the lowest f_score[] value
     if current = goal
         return reconstruct_path(came_from, goal)

     remove current from openset
     add current to closedset
     for each neighbor in neighbor_nodes(current)
         tentative_g_score := g_score[current] + dist_between(current,neighbor)
         if neighbor in closedset
             if tentative_g_score >= g_score[neighbor]
                 continue

         if neighbor not in openset or tentative_g_score < g_score[neighbor]
             came_from[neighbor] := current
             g_score[neighbor] := tentative_g_score
             f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
             if neighbor not in openset
                 add neighbor to openset

 return failure

```

I suppose it should be true. Because of this:

```
if current = goal
     return reconstruct_path(came_from, goal)

```

If it wasn't true then this test would not guarantee me that the solution is optimal right?

What I don't get and the reason I am asking this question is this:

```
if neighbor in closedset
         if tentative_g_score >= g_score[neighbor]
             continue

```

If the neighbor is in closed list, it means that it has already been expanded. Why are they testing the scores then? Why would not the next condition work?

```
if neighbor in closedset
         continue

```

# Answer
Please, let me contribute to this question with some observations. Most of them refer to the reply by Shaull.

First, and foremost, I found that the answer provided to the question pointed to by Shaull is a little bit strange. The property of monotonicity is defined there in a strange way and indeed, I posted a question ---note I am not saying that's wrong but just strange to me and not very common and frankly speaking, I am a little bit suspicious that it might be wrong.

In the original question I see various questions so let's go by steps.

First, *consistency* is usually defined as follows \[Pearl, 1984\]: a heuristic $h(n)$ is consistent if and only if $h(n) \leq c(n,n') + h(n')$ for every pair of nodes $n$ and $n'$ in the state space, where $c(n,n')$ stands for the cost of the shortest path joining $n$ and $n'$. I think it is clear that admissibility (i.e., $h(n) \< h^\*(n)$ where $h^\*(n)$ is the true optimal cost of node $n$) is immediately implied from consistency if $h(t)=0$ where $t$ is the goal node. For this and other definitions see "Common Misconceptions Concerning Heuristic Search".

So far, no need to say "*Suppose I have a admissible and consistent heuristic*". It just suffices saying "Suppose I have a consistent heuristic".

Now, regarding your first question. If you have a consistent heuristic, there is no need to reopen nodes or, equivalently, everytime a node $n$ is expanded by A$^\*$, the path discovered to it is necessarily optimal.

**Proof**: Let us assume this is not true and after expanding node $n$ through a path $\pi\langle s, n\_1, n\_2, \ldots, n\_k, n\rangle$ there was another path $\pi'\langle s, n'\_1, n'\_2, \ldots, n'\_l, n\rangle$ such that $g\_{\pi}(n) \> g\_{\pi'}(n)$. Note that $f(n)=g(n)+h(n)$ so that from our assumption $f\_{\pi}(n) \> f\_{\pi'}(n)$ since $h(n)$ takes the same value in spite of the path followed to node $n$. But this is impossible, since $n$ was expanded as a successor or the path $\pi$ so that $f\_{\pi}(n) \leq f\_{\pi'}(n)$. Of course, you might say that the error was committed somewhere along the path $\pi'$ because a node $n'\_i$ had such a large value of $h(n'\_i)$ that it was delayed in the OPEN list, but this is impossible by definition of consistency.

From here it should be obvious that the condition:

`if current = goal return reconstruct_path(came_from, goal)`

works smoothly since once the goal is about to be expanded it is guaranteed that the path discovered to it is optimal.

Regarding your second question, the reason of your post, Shaull already answered in the footnotes of his reply: if the heuristic function is consistent then nodes are never reopened and your condition:

`if neighbor in closedset continue`

is enough. However, in practice, it is just simply substituted by a different condition: when expanding a node, their children are only added to OPEN if it was never expanded (not in closedset) and also, it is not already in OPEN (not in openset). With the appropriate structures for managing the open and closed list this can be done very fastly. This trick make it unnecessary to use that statement.

But again, bear in mind what Shaull says, the pseudocode you show in your post is intended to work also with inconsistent heuristic functions. What you are asking for are, indeed, simplifications that result from the assumption of consistency.

Hope this helps,

\[Pearl, 1984\] Judea Pearl. Heuristics. Addison-Wesley. 1984
> 5 votes

# Answer
The A\* algorithm is a non exhaustive search algorithm, it does not check all the possibilities, but rests on the hypothesis that the heuristic will consistently provide accurate estimates of the cost of reaching the goal node from a given node in the graph. The algorithm will skip certain possibilities because of their costs, yet if the estimate is wrong, there might be a better path going through that list of skipped nodes. The garantee is therefore dependent of the heursitic garantee.

Regarding the algorithm presented, indeed the test is wrong. Any node in the closed list is there because it has been fully explored and cannot yeld any new path.
> 1 votes

# Answer
This would depend on the heuristic. Consider a graph where $start\to a\to d\to end$ and also $start\to b\to c\to d\to end$. Now assume you have a bad heuristic that prefers that gives $b,c,d$ much higher scores than $a$, then you would reach $end$ in a non-optimal path. In particular, when you open $d$, you are in a non-optimal path.
> 0 votes

---
Tags: algorithms, algorithm-analysis, search-algorithms, correctness-proof
---


# Question
Title: Term for array of identical type and different types
What is proper terminology to distinguish between an array (ordered list) data structure in which each element is of identical type/class, and an array in which each element can be different?

# Answer
A structure containing only the same type is homogeneous, and a structure containing different types is heterogeneous.
> 2 votes

---
Tags: terminology, arrays
---


# Question
Title: Term for size of maximum independent set
An *independent set* is a set of vertices in a graph, no two of which are adjacent.

A maximum independent set is a largest independent set for a given graph G.

Is there a standard term for the size of the largest independent set in a given graph?

If not, what short term can you suggest for this size? Maybe "independence number"?

# Answer
Yes, it's called the **independence number** and it's usually denoted $\alpha(G)$.
> 3 votes

---
Tags: graphs, terminology
---