# Question
Title: Counting involving equivalence classes and languages
Let $\Sigma$ be the alphabet $\\{a, b, c, d\\}$ and let $R$ be the following relation on $\Sigma^\*$: $R(x, y)$ is true if every letter in string $x$ also occurs in $y$, and every letter in string $y$ also occurs in $x$. (For example, $R(abba, babbb)$ is true and $R(abcb, cbbcb)$ is false.) How many (non-empty) sets are in the partition of $\Sigma^\*$ corresponding to $R$? (That is, how many equivalence classes does R have?)

Any help will help.

# Answer
> 1 votes
If you look at two strings in your example $abba$ and $babbb$, they are composed of *exactly* the symbols from the set $\\{a,b\\}$, where each symbol appears at least once. So you can reduce the counting problem in your question to counting the number of subsets of $\\{a,b,c,d\\}$. Note that one equivalence class would be $\\{\lambda\\}$ where $\lambda$ denotes the empty string. How many subsets does $\\{a,b,c,d\\}$ have?

---
Tags: logic, combinatorics, counting
---


# Question
Title: NFA with exponential number of states when determinized
How can I build an example of a regular language where the minimal DFA has $2^n$ states and the minimal NFA has $n$ states? Obviously the DFA's state-set should contain all subsets of the the NFA's state-set, but I don't know how to start. Any suggestions to put me on the right track?

# Answer
The standard example is the language $L$ of all words over an alphabet $A$ of size $n$ that *don't* contain all the different letters. There is an NFA accepting $L$ with $n+1$ states (or $n$ states if you allow multiple starting states): first guess a letter $a$ which is missing, then go (with an $\epsilon$-move) to an accepting state with self-loops for all letters other than $A$.

Any DFA for $L$ requires at least $2^n$ states. This can be seen using the Myhill-Nerode theorem. Let $S\_1,S\_2$ be two different subsets of $A$, and $w(S\_1),w(S\_2)$ words which contain all and only the letters in $S\_1,S\_2$, respectively. Without loss of generality, suppose $a \in S\_1 \setminus S\_2$, and let $w = w(A-a)$. Then $w(S\_1)w \notin L$ while $w(S\_2)w \in L$.
> 21 votes

# Answer
This is a late answer, but apparently nobody gave the optimal solution. Take $A = \\{a, b\\}$, $Q\_n = \\{0, 1, \ldots, n-1\\}$ et ${\cal A}\_n = (Q\_n, A, E\_n, \\{0\\}, \\{0\\})$, with $$ E\_n = \\{(i, a, i+1) \mid 0 \leqslant i \leqslant n-2\\} \cup \\{(n-1, a, 0)\\} \cup \\{(i, b, i) \mid 1 \leqslant i \leqslant n-1\\} \cup \\{(i, b, 0) \mid 1 \leqslant i \leqslant n-1\\} $$ This NFA on a two-letter alphabet has $n$ states, only one initial and one final states and its equivalent minimal DFA has $2^n$ states.
> 13 votes

# Answer
this is an exercise in the book "Finite Automata" by Mark V. Lawson Heriot-Watt University, Edinburgh, page 68:

Let $n \geq 1$. Show that the language $(0+1)^\ast 1(0+1)^{n−1}$ can be recognised by a non-deterministic automaton with $n+1$ states. Show that any deterministic automaton that recognises this language must have at least $2^n$ states. This example shows that an exponential increase in the number of states in passing from a non-deterministic automaton to a corresponding determin- istic automaton is sometimes unavoidable.
> 11 votes

# Answer
I'm going to guess that you mean that the *optimal* DFA has $2^n$ states. Maybe this doesn't get you $2^n$ states, but it's $\Omega(2^n)$.

From "Communication Complexity" by Kushilevitz and Nisan in exercise 12.6:

"For some constant \[non-negative integer\] $c$, consider the (finite) language $L\_c = \\{ww\mid w \in \\{0,1\\}^c\\}$."

and the book continues on asking you to prove that you can find a co-NFA recognizing $L\_c$ that uses $O(c)$ states and also that you cannot do better than $\Omega(2^c)$ states for a DFA.
> 10 votes

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


# Question
Title: Using a proof-of-work system to discourage piracy or encourage donations
**Background**

A proof-of-work system allows one peer to prove to another peer that a certain amount of computational effort was performed. In a network setting this can be used to throttle peer requests without needing to keep a precise track on the identity of the peers or prior events. The most well known use of proof-of-work is to throttle spam throughput in an email network\*.

Some proof-of-work systems allow certain roles on the network (say, a mailing list) to calculate the proof of work much faster by using a secret *"short-cut"* \- typically a pre-calculated trapdoor or a private key depending on the proof-of-work system.

**Hypothesis**

1. Any algorithm or a certain class of algorithms can be converted into a proof-of-work version of that algorithm. That is: A deliberately inefficient and incompressible algorithm.
2. Such converted proof-of-work algorithms can support proof-of-work shortcuts.
3. Such converted proof-of-work algorithms can not be converted back to the original algorithm without considerable computational power; if at all.

**Extrapolation**

If the hypothesis holds, then selected business logic of an application - specifically that which is unique or value-added by that application vs existing applications - could be converted to proof-of-work equivalents.

End-users could then be provided such an application; which will run slowly either generally or for certain premium features. The development team however, possesses a secret PoW shortcut and set up a subscription, donation or advertising()-based service - an SaaS \- for solving the proof-of-work bottleneck for the end-user. The end-user can now choose to run the application slower without the SaaS or faster with the SaaS.

This SaaS needs to process considerably less client-side business logic than a general cloud solution (e.g. Diablo 3 style SaaS); as the goal is the speed of execution rather than no execution - and the SaaS proof-of-work speed ratio is tailored accordingly.

This is especially relevant for software projects supported by charity as the developers *do* want the software available to anyone but can encourage donations without needing a separate fairly easy to pirate Freemium edition. The Tragedy of the Commons (freeloading) could be discouraged to a fair extent without guilt-tripping or rat poisoning, by adjusting the proof-of-work cost relative the value of the application or service.

> *Example 1:* A commercial stock market estimation tool licensed per month. If the user forgoes paying for a subscription, the estimation occurs at 1% the normal rate.
>
> *Example 2:* A free Triple A co-op video game runs twice fast if the user donates some money once a year.

In either example the user must decide between accepting the default speed; spending money on a faster computer/cloud services; or contributing to the upkeep of the product.

**Question**

*Does the hypothesis hold and has anyone attempted to explore or implement this hypothesis?*

Any example of an open source library or application that attempts to implement the hypothesis qualifies as a sufficient answer (from my perspective); as I could dissect the code.

<sub> * Which has a variety of issues for the Digital Divide, but that's another story</sub>

# Answer
> Hypothesis
>
> 1. Any algorithm or a certain class of algorithms can be converted into a proof-of-work version of that algorithm. That is: A deliberately inefficient and incompressible algorithm.
> 2. Such converted proof-of-work algorithms can support proof-of-work shortcuts.
> 3. Such converted proof-of-work algorithms can not be converted back to the original algorithm without considerable computational power; if at all.

Surprisingly, this is possible.

Essentially the idea is: you can convert any program into a proof. Add some probabilistic complicated mathematical voodoo, and you can get succinct proof that someone ran a program on his machine, the *full* program, no cheating. This means you can essentially turn any busy-work algorithm into a POW, or even use useful algorithms as POW, and not have to worry about a shortcut (for example, you can use protein folding as POW, and not have to worry that average-case might not be hard). The proof guarantees that the entire program ran until termination.

For deliberate shortcuts you can simply build in early termination into the program for your deliberate shortcuts. For example:

```
def P(user_input,hard_coded_n):
  if user_input is not None:
    p,q = user_input
    if p*q = hard_coded_n:
      return True
  protein_fold()
  return True

```

In this program, you generate and hard-code a semi-prime, $n$, into the program. If you want to provide the user with a shortcut, you give him the p,q that he can use as input for early termination. Then you check his proof that he ran the program, and the proof will guarantee that the output he provides was the output of his program; therefore his POW is to provide "True" as output, and the proof.

This type of system is insanely powerful IMO; you can think of all sorts of things you can do with this; your cheap "DRM" ideas are the least of it :P

Further terminology/keywords:

* Succint Non-interactive Argument of Knowledge (SNARKs) are basically succinct proofs that someone ran some computation.
* SCIP: Succinct Computational Integrity and Privacy, is a practical system being built upon many years of research/complicated mathematics.

There is a large body of research into this, attempting to make it practical. For an actual project (SCIP) (you asked this question at the right time in history) see this talk: Universal and affordable computational integrity - Bitcoin 2013 Conference by Eli Ben-Sasson (another talk if you found that one interesting); though he applies it to bitcoin (it is a talk given at a bitcoin conference), he generally explains the power of the system, it is a good watch, even if you don't care about bitcoin.

However, the application to bitcoin, distributed trust systems, and systems that rely on proof-of-work are very numerous and abstract. Suffice to say, though the practical applications are hard to come by at first, the intuitive power of such a system suggests that they will be numerous.

Wrt. bitcoin, this system magnifies the potential of a distributed currency by orders of magnitude; read through bitcoin forums/mailing lists/proposals on the wiki, and you can find countless applications of being able to guaranteeing secure computation on someone else's machine.

* For example, instead of verifying the entire bitcoin blockchain on your machine, you can have someone else do it, and then **simply verify that he ran the verifier!**
* Of course arbitrary POW is a big possible win for future bitcoin; perhaps one day we'll see a blockchain doing *useful* work (now doubly useful, not just guaranteeing the integrity of bitcoin, but also **computing something useful**), or even a **secure distributed computing marketplace**, where the lottery of minting the next block is won by one of the participants.

For further reading see SNARKs for C : Verifying Program Executions Succinctly and in Zero Knowledge (extended version) (PDF): yes, they are making a C compiler. They designed a virtual architecture, called TinyRam from which they generate the proof and the program to be run. They are also considering an LLVM backend. They have created a website for the SCIP project.
> 3 votes

# Answer
Another idea, similar to SCIP, is ***secure multi-party computation***, which can provide a similar ability via ***secure function evaluation***. This is essentially a function that you can run on an untrusted machine, without revealing the input-values. The function can provide an "easy-out" shortcut function via some one-way/trapdoor answer, same as above in my previous answer. Wikipedia lists some implementations.

A related and more powerful idea is ***fully homomorphic encryption***. ***HElib*** was released by IBM. ***hcrypt*** is an effort to create a project for fully homomorphic encryption called ***Scarab*** and a project called ***Secure Function Evaluation*** which does what its name suggests.
> 3 votes

# Answer
I'm skeptical of the hypothesis. I suspect you'll find it is difficult to make this work, in most applications.

For this to be useful, you need to have a small unit of difficult computation that's needed by the server, and can be safely and efficiently outsourced to a client. Suppose you identify some computation in the server, say computing $y=f(x)$, where $f$ is some function (some computation to be run) on some inputs $x$. You are hoping that you will be able to outsource this computation to clients, by giving a client a value $x$ and having them compute $f(x)$ for you. But let's look at all the requirements that must hold, for this to be a net win for your application:

1. It has to be cheaper for the server to send $x$ to a client and receive $y$ in response than for the server to just compute $f(x)$ himself. In other words, the computation-to-communication ratio has to be very high (where the computation cost is the cost of computing $f$, and the communication cost is the cost of sending $x$ and $y$ over the network).
2. The server has to have some way to verify that $y$ was computed correctly. For instance, it has to be easier to verify that $y$ is the right answer than to compute it from scratch -- this is true for some functions $f$, but only in special cases. Alternatively, the server could give the same $x$ to many clients and check that it gets the same answer from all of them (but then it becomes vulnerable to Sybil attacks). Alternatively, the computational process must be chosen so that it doesn't matter if the value $y$ is incorrect (but why would you be doing the computation if that was OK?).
3. The value $x$ has to be something that isn't confidential and is OK to hand to arbitrary clients.
4. The computational process has to be a pure mathematical function, with no side effects. $x$ has to include all of the data that the computation might read.

I think what you'll find is that, in most applications, it is difficult to identify computational tasks that satisfy all of these requirements.

For instance, many server operations are data-intensive: they have a large working set of state that could possibly be read in response to any given event, so the size of $x$ would be very large. Those kinds of computations won't be a good fit. That's just one example of a challenge. There are many others.

So, I certainly don't rule out the possibility that in some specific applications you might find an opportunity to outsource work to clients. But, as a general rule, it's harder than it might seem to find opportunities to do so.
> 1 votes

---
Tags: time-complexity, one-way-functions, proof-of-work
---


# Question
Title: What is the advantage of Greibach Normal Form over Chomsky Normal Form?
I wanted to know the pros and cons of Chomsky normal form and Greibach normal form.

# Answer
There are actually several variants for these normal forms, so it might be useful to first recall the definitions. A context-free grammar is in *Chomsky normal form* if all of its production rules are of the form:

> 1. $X \to YZ$
> 2. $X \to a$
> 3. $S \to 1$

where $X, Y$ and $Z$ are nonterminal symbols, $S$ is the start symbol, $a$ is a letter and $1$ is the empty word. A grammar is in *Chomsky reduced form* if its productions are of the form 1 or 2, but with $X$ and $Y$ being possibly equal to the start symbol. The Chomsky Normal Form has been used to give a **polynomial-time parsing algorithm** (the CYK algorithm).

A grammar is in *Greibach normal form* if its productions are of the form

> 1. $X \to aX\_1 \dotsm X\_k$
> 2. $X \to b$

where $X, X\_1, \dots, X\_k$ are nonterminal symbols and $a$, $b$ are letters. It is in *Greibach quadratic normal form* if $k \leqslant 2$ in all rules. It is in *Greibach two sided normal form* if its productions are of the form

> 1. $X \to aX\_1 \dotsm X\_kb$
> 2. $X \to c$

where $X, X\_1, \dots, X\_k$ are nonterminal symbols and $a$, $b$, $c$ are letters. It is in *Greibach quadratic two sided normal form* (or *Hotz normal form*) if $k \leqslant 2$ in all rules. These normal forms have important **applications in formal language theory**. See for instance the article Towards an algebraic theory of context-free languages.
> 1 votes

---
Tags: formal-grammars
---


title: Approaches to Solve PDA

text:
# Question
Title: Approaches to Solve PDA
There is a saying by Computer Science Professor's everywhere :

```
PDA Checks the intelligence of Students, as certainly there is no approach except power and imagination
of mind to solve problems and design PDA...

```

While thinking today i thought How can we design automata of a^2n b^(2n-1)

I tried my best : For example let q0 is initial state and top of the empty stack has Z.

```
So, Let say Transition of (q0, a , Z) = (q1,Z)

            Transition of (q1, a , a) = (q1,a)

            Transition of (q1, b , a) = (q2,-)

            Transition of (q2, $ , Z) = (qf,Z)

```

I was able to solve this problem all of a sudden...

**My doubt is still the same, How to be the best in solving PDA problems and Is there any way to define a strategy to solve problems ?**

P.S. Your comments are welcome if i did something wrong in above stated question

# Answer
One technique is to start out with a context-free grammar, and apply an algorithm to get a corresponding PDA. Often, writing a grammar might be a bit easier than writing the PDA directly. In this case, it seems (to me) to be fairly easy to arrive at the grammar $S \rightarrow aaSbb \mid aab$, from which a PDA follows by construction (see this, for example, for some info on how to do such a conversion, if this is new to you)

If you want to build the PDA directly, another way to think about it is to start from the end of strings, and ask yourself what needs to be on the stack to make it easy to tell you need to accept the string. In your case, if you're looking at the last part of the string - say, you've started seeing $b$'s, what would it be really helpful to have on the stack? Well, the easiest thing would be to have $2n-1$ symbols on the stack. If we can arrange that, then when we get to $b$'s we can simply pop one symbol off the stack for every $b$ we read, and accept if the stack is empty when we're done with the input. How can we leave $2n-1$ symbols on the stack after reading $2n$ of the $a$ symbol? Well, we could put a symbol on the stack each time we read an $a$, and then, before we start reading $b$'s, remove one symbol from the stack. We get three phases to the computation: (1) read an even number of $a$'s and push a symbol onto the stack for each $a$ you read; (2) remove one symbol from the stack; (3) read $b$'s until the stack is empty and/or you run out of input. We'd get a PDA like this:

```
q    s    e    q'    s'
--   --   --   --    --
q0   Z    a    q1    aZ
q0   a    a    q1    aa
q0   a    -    q2    -
q1   a    a    q0    aa
q2   a    b    q2    -
q2   Z    -    q3    Z

```

We have start state `q0` and accepting state `q3`. Entries of `-` in the `e` column indicate $\lambda$-transitions, whereas entries of `-` in `s'` indicate popping a symbol off the stack.
> 2 votes

---
Tags: automata, pushdown-automata
---


# Question
Title: Drawing an implication graph for 2-SAT clauses
I am trying to convert the following 2-sat clauses to implications and then draw the implication graph.

The clauses are: `{¬xvy}, {¬yvz}, {¬zvw} ,{¬wvu},{¬uv¬x},{xvw},{¬wvx}`

I converted the boolean literals into implications so I could construct the implication graph:

`{¬xvy}`: I have `x-->y` and `¬x -->¬y`

`{¬yvz}` : I have `y-->z` and `¬y-->¬z`

`{¬zvw}` : I have `z-->w` and `¬z-->¬w`

`{¬wvu}` : I have `w-->u` and `¬w--->¬u`

`{¬uv¬x}` : I have `u-->¬x` and `¬x-->¬u`

`{xvw}` : I have `¬x-->w` and `¬w-->x`

`{¬wvx}` : I have `w-->x` and `¬w-->¬x`

Am I doing this right? If so, I have constructed this implication graph to prove it is not satisfiable.

I would argue that these literals are not satisfiable because of the infinite loops you can have from ¬w ¬x ¬y ¬z ¬w and w x y z w. Is this a sufficient enough explanation?

Thanks in advance!

# Answer
> 4 votes
> {¬uv¬x} : I have u--\>¬x and ¬x--\>¬u

LMFTFY:

$$(\neg u \vee \neg x) = \left\[(u \implies \neg x) \wedge (x\implies \neg u)\right\]$$

> {¬wvx} : I have w--\>x and ¬w--\>¬x

LMFTFY:

$$(\neg w \vee x) = \left\[(w \implies x) \wedge (\neg x\implies \neg w)\right\]$$

From this you get the following graph:

graphviz source

And the strongly connected components (there is only one):

graphviz source

And we get $\left\\{u,\neg u,w,\neg w, x,\neg x,y,z,\neg z\right\\}$, obviously a contradiction (the elements of this set implies each-other).

> I would argue that these literals are not satisfiable because of the infinite loops you can have from ¬w ¬x ¬y ¬z ¬w and w x y z w. Is this a sufficient enough explanation?

It isn't the "infinite" loops that make it unsatisfiable. "infinite loops" or cycles, make strongly connected components; and a 2sat formula is satisfiable **iff** (if and only if) there are no contradicting terms in any of its strongly connected components. In this graph there are clearly contradicting terms in the one large strongly connected component, as I demonstrated above, therefore it is unsatisfiable.

---
Tags: complexity-theory, logic, satisfiability
---


# Question
Title: Proving Equivalence of 1-dimensional Cellular Automaton and Turing Machines
I'm considering an automaton $A$ over a alphabet $\Sigma$, with a set of states $Q$, such that $\Sigma \subset Q$, which includes special "accept" and "blank" states not in $\Sigma$. It also has an infinite list of cells, which begins with the input string, the rest being blank. It has a transition function $\delta: Q \times Q \times Q \to Q$. The automaton computes by updating the value of the middle cell, $a$, using $\delta(x,a,y)$. The automaton accepts if any cell is in the accept state. From what I understand, this automaton is very similar to a 1-dimensional cellular automaton, with the addition of the accept state.

I'm trying to prove that a language is recognizable by a Turing machine if and only if it can be recognized by the automaton described.

I've been trying to do a proof by construction, but I'm really lost. I did some research on cellular automata, but the material I've been finding is way over my level. I know somehow I'm going to have to construct a TM from CA, and vica versa, but I'm not even sure how to get started. I would really appreciate any help.

# Answer
Here are some hints. The easy direction is simulating cellular automata with Turing machines. Turing machines can simulate C programs, and you can simulate cellular automata in C. (Replace C with your favorite programming language.)

Given a Turing machine, we want to construct a cellular automaton simulating it. We need to upgrade the alphabet by allowing, besides regular symbols $\sigma$, also symbols $\langle q,\sigma \rangle$ which signify that the head is currently at that point, the state is $q$, and the tape symbol is $\sigma$. The initial tape would contain $\langle q\_0,\sigma\_0 \rangle$ as the first symbol, where $q\_0$ is the initial state and $\sigma\_0$ is the first symbol on the input tape of the Turing machine.

It remains to show how to simulate the Turing machine by an appropriate choice of the propagation rules $\delta$. The basic idea is to maintain the invariant that the contents of the cells constitute of the tape of Turing machine, with the exception of the location of the head, which is of the form $\langle q,\sigma \rangle$. I'll let you work out the details.
> 2 votes

---
Tags: turing-machines, cellular-automata
---


# Question
Title: Shortest non intersecting path for a graph embedded in a euclidean plane (2D)
What algorithm would you use to find the shortest path of a graph, which is embedded in an euclidean plane, such that the path should not contain any self-intersections (in the embedding)?

For example, in the graph below, you want to go from $(0,0) \rightarrow (-3,2)$. Normally, an algorithm like Dijkstra's algorithm would produce a sequence like:

$$\left\[ (0,0) \stackrel {3}{\rightarrow} (0,3) \stackrel{\sqrt{2}}{\rightarrow} (1,2) \stackrel{4}{\rightarrow} (-3,2) \right\] = 7+\sqrt{2}.$$

Full graph:

Shortest path:

Shortest non-intersecting path:

However, this path intersects itself on the euclidean plane, therefore I *want* an algorithm that would give me the shortest non-intersecting sequence, in this case:

$$\left\[(0,0) \stackrel{3}{\rightarrow} (0,3) \stackrel{3}{\rightarrow} (0,6) \stackrel{5}{\rightarrow} (-3,2) \right\] = 11.$$

This path is longer than the shortest path, but it is the shortest non-intersecting path.

**Is there an (efficient) algorithm that can do this?**

## TikZ sources

# Answer
> 11 votes
It is NP-complete to even decide whether *any* path exists.

It is clearly possible to verify any given path is a valid path in the given graph. Thus the bounded-length problem is in NP, and so is its subset, the any-path problem.

Now, to prove NP-hardness of the any-path problem (and thus of the bounded-length problem), let's reduce SAT-CNF to this problem:

---

**The global structure** is a grid of wire pieces adjoined by a column of clause pieces. Logic formula is satisfiable iff there exists a non-intersecting path through the graph.

It is impossible to cross two pieces of the path, but it is neccessary to cross two logic wires. Rather, the path flow is strictly given: a wire point is given by two nodes. The sequence of the wire points through which the path passes is forced by the reduction. Logic is represented by which node is chosen. Any path can be chosen as long as it passes through all wire points.

In this diagram, the path is represented by the red curve and the logic flow is represented by the black wires:

Now let's build each component.

---

Wiring uses three tiles: the crossing, the branch point, and the vertical wire. Let's start with the hardest one:

The basic idea behind **the crossing** is to prepare a path for each pair of wire points and bend the possible paths enough so that all pairs except those that encode the same logic (compatible paths) cross each other. Of course we can't just say two parallel edges intersect, but we can introduce extra order-2 nodes to make two paths intersect.

Supposing the paths come from north to west and from south to east, we can: collect each path from north with its compatible path from east on a line (some incompatible paths will cross each other); cross each pair with each other by reversing the order of pairs; distribute the paths to their south and west endpoints. This is best explained by a diagram. Here, each pair of nodes represents a wire point. Paths with the same color code (carrying the same logic) don't intersect, paths a different color code do:

**The branch point** and **the vertical wire** work the same, but there are fewer paths to correlate:

**The clause box** follows the same logic: each literal exposes one of its paths to the reading wire, then converging to the south (if it's the northernmost term or the term to the north converges to the north) or to the north (if the term to the north converges to the south). The reading wire (one node at the endpoints) branches to become one path per literal. Each reading path then crosses the literal's true-path if the literal is negated, the false-path if it is not. Note that the converged path may or may not cross a clause boundary. For consistency, here's a diagram for $\neg A \vee \neg B$:

It is possible to generalise this reduction to encode an arbitrary tree of AND and OR gates by branching the reading wire in different way. In particular, SAT-CNF and SAT-DNF are both possible to reduce to the non-intersecting path problem in the way described as above.

# Answer
> -1 votes
the problem seems to date to Turan 1944. this looks like a good survey of theory and algorithms, the Crossing Number of Graphs: Theory and Computation by Mutzel. wikipedia has some info under crossing number of graphs

---
Tags: algorithms, graphs, shortest-path, graph-traversal, weighted-graphs
---


# Question
Title: How to discuss coefficients in big-O notation
What notation is used to discuss the coefficients of functions in big-O notation?

I have two functions:

* $f(x) = 7x^2 + 4x +2$
* $g(x) = 3x^2 + 5x +4$

Obviously, both functions are $O(x^2)$, indeed $\Theta(x^2)$, but that doesn't allow a comparison further than that. How do I discuss the the coefficients 7 and 3. Reducing the coefficient to 3 doesn't change the asymptotic complexity but it still makes a significant difference to runtime/memory usage.

Is it **wrong** to say that $f$ is $O(7x^2)$ and $g$ is $O(3x^2)$ ? Is there other notation that does take coefficients into consideration? Or what would be the best way to discuss this?

# Answer
Big-$O$ and big-$\Theta$ notations hide coefficients of the leading term, so if you have two functions that are both $\Theta(n^2)$ you cannot compare their absolute values without looking at the functions themselves. It's not wrong per se to say that $7x^2 + 4x + 2 = \Theta(7x^2)$, but it's not informative because $7x^2 + 4x + 2 = \Theta(3x^2)$ is also true (and, in fact, it's $\Theta(kx^2)$ for any positive constant $k$).

There are other notations you might want to use instead. For example, $\sim$ notation is a much stronger claim than big-$\Theta$:

$\qquad \displaystyle f(x) \sim g(x) \iff \lim\_{x \to \infty} \frac{f(x)}{g(x)} = 1$

For example, $7x^2 + 4x + 2 \sim 7x^2$, but the claim $7x^2 + 4x + 2 \sim 3x^2$ would be false. You can think of tilde notation as $\Theta$ notation that preserves the leading coefficients, which seems to be what you're looking for if you do care about the leading coefficient of the dominant growth term.
> 9 votes

# Answer
The tilde is one approach. If you want to stick with $O$, you could say

$\qquad f(x) = 7x^2 + O(x)$ and

$\qquad g(x) = 3x^2 + O(x)$.
> 6 votes

---
Tags: terminology, asymptotics, landau-notation
---


title: Sorting in O(n) time in a finite domain

text:
# Question
Title: Sorting in O(n) time in a finite domain
I've been stuck with this problem for 2 weeks. Any idea of how to aproach it?.

> Let $L$ be a list of $n$ different integer numbers, assume that the elements of $L$ are in the range $\[1,750\]$. Design a linear ordering algorithm to order the elements of $L$.

I already tried with insertion sort. But I'm not sure if my approach is right:

* Construct an array of bits. Initialize them to zero.
* Read the input, for each value you see set the respective bit in the array to 1.
* Scan the array, for each bit set, output the respective value.

Complexity: $O(2n) = O(n)$

I also wanted to use radix sort but I can't understand how to apply it, any idea?

# Answer
> 4 votes
Bitvector approach is correct solution.

Problem statement tells that you are given $n$ **different** integers so there is no need to count multiple occurrence of number in sequence. This also allows you to cut down needed storage to $\lceil{\frac{750}{8}}\rceil = 94$ bytes.

Now the algorithm:

Input: $A$ - array of unique integers, 1 based

Output: None - we update given array

```
B[750] = 0; bitvector of len 750 initially set to 0
for each i in A
    B[i] = 1
k = 1
for j = 1 to 750
    if B[j]
        A[k] = j
        k = k+1

```

This obviously runs in $O(n)$ and uses $O(1)$ memory.

This can run in linear time because it isn't compare based sorting. As you correctly pointed out every compare based sorting must take at least $O(n \log n)$ steps.

This approach is special case of bucket sorting but we used information about problem statement (namely: unique integers and range of those integers)

# Answer
> 0 votes
How about this:

```
Read numbers into array L
Initialize array of numbers D with with size of 750 and set all its values to 0

for each value in L do
  increase value of D at index value by 1
end loop

Initialize array of numbers ResultltArray

iterate over i from 1 to 750
  from 0 to value of D at index i do
    push i to ResultltArray
  end loop
end loop

return ResultltArray

```

---
Tags: algorithms, algorithm-analysis, time-complexity, sorting, radix-sort
---


# Question
Title: Undecidability of the PCP problem with bounded width
Given two ordered sets of words $a\_1, a\_2, ..., a\_k$, $b\_1, b\_2, ..., b\_k$ taking values in some discrete alphabet $A$, a solution to the PCP problem is a sequence $i\_1, ..., i\_n$ taking values in $1, 2,..., k$ such that $a\_{i\_1}|a\_{i\_2}|...|a\_{i\_n}=b\_{i\_1}|b\_{i\_2}|...|b\_{i\_n}$ where $|$ means concatenation. $k$ can be called the length of the problem, $n$ the length of the solution and if we let $w$ be the length of the largest word in $a\_1, a\_2, ..., a\_k, b\_1, b\_2, ..., b\_k$, $w$ is called the width of the problem.

I know that the PCP problem becomes decidable in several scenarios, for instance: for bounded $n$, or if $A$ is unary, etc. On the other hand for $k\geq7$ PCP is still undecidable. My question is, is there any result known for bounded values of $w$?

# Answer
If $w$ is bounded, and the alphabet size is bounded, then the number of possible words is bounded. Thus, there is only a finite number of possible instances, so the problem becomes a finite languages, and hence decidable.

If you don't bound the alphabet, then you can encode any width of $w$ by adding more letters, so the problem is the same as standard PCP, and hence undecidable.
> 3 votes

---
Tags: computability, reference-request, undecidability, decision-problem
---


# Question
Title: Concatenation of the intersection of two languages
I'm enrolled to a Formal Language And Automata course, and we have to prove this equation on sets of strings: $$(L\_1\cap L\_2)\cdot L\_3 ≠ (L\_1\cdot L\_3) \cap (L\_2\cdot L\_3)$$

I've tried a lot of sets for e.g. $L1 = \\{a,b,c,d\\}$, $L2 = \\{a,f,g\\}$, $L3 = \\{s,d,h\\}$. but always the LHS comes out equal to the RHS instead of unequal. Any idea how to prove this?

# Answer
> 7 votes
First, you may notice that there is a one-sided containment here. It always holds that $(L\_1\cap L\_2)L\_3\subseteq L\_1L\_3\cap L\_2L\_3$ (prove it!)

From this, you see that in order for the equality to fail, you need to get a strict containment. Intuitively, this means that you need the concatenation with $L\_3$ to add words to both $L\_1$ and $L\_2$.

One way to achieve this is, for example, to first let $L\_1\cap L\_2=\emptyset$, and then "tailor" $L\_3$ to fix this emptiness.

A concrete example is below (hidden as spoiler, hover mouse to see it):

> $L\_1=\\{a\\}$, $L\_2=\\{aa\\}$, $L\_3=\\{a,\epsilon\\}$.

# Answer
> 2 votes
If all the words in $L\_3$ have the same length $n$, then you can unambiguously decompose a word $w \in \mathscr{A}^\* \cdot L\_3$ (where $\mathscr{A}$ is the alphabet) into $u \in L$ and $v \in L\_3$ such that $uv = w$: take the last $n$ letters of $w$, call that $v$, and let $u$ be $w$ without its last $n$ letters. Therefore, under this condition, a word is in $(L\_1\cap L\_2)\cdot L\_3$ iff its last $n$ letters are in $L\_3$ and the corresponding prefix is in both $L\_1$ and $L\_2$, which is equivalent to the word being in $(L\_1\cdot L\_3) \cap (L\_2\cdot L\_3)$.

The same goes if all the words in $L\_1 \cup L\_2$ have the same length.

So to find a counterexample, you need to find a case where the words of the concatenation can potentially be decomposed in an ambiguous way. In particular, $L\_3$ needs to contain at least two words of different lengths, as does $L\_1 \cup L\_2$.

Take $L\_3 = \\{\epsilon, a\\}$, which is the simplest example of a language with words of different lengths. And let's take $L\_1 = \\{\epsilon\\}$ and $L\_2 = \\{a\\}$, again the simplest way of having words of different lengths in $L\_1 \cup L\_2$. Then $$ \begin{align} (L\_1\cap L\_2)\cdot L\_3 &= \varnothing \cdot L\_3 = \varnothing \\ (L\_1\cdot L\_3) \cap (L\_2\cdot L\_3) &= \\{\epsilon,a\\} \cap \\{a,aa\\} = \\{a\\} \\ \end{align} $$ There are two ways to decompose $a$ in $(L\_1\cdot L\_3) \cap (L\_2\cdot L\_3)$: one that makes it an element of $L\_1 \cdot L\_3$ and one that makes it an element of $L\_2 \cdot L\_3$. Thus the word is in the intersection of the concatenations even though it is not in the concatenation of the intersections (which is empty).

---
Tags: formal-languages, sets
---


title: NFA's number of states

text:
# Question
Title: NFA's number of states
I have read that the NFA size (i.e., the number of states) is linear in the number of characters in the regular expression. This holds even in the presence of character repetitions.

I would like to know why is it so?

If I have a pattern like this , \[b-d\]at then the number of states will be just 4 incase of NFA ? Size of DFA for this regular expression will also be 4?

# Answer
> 2 votes
What is meant by *NFA size is linear in the number of characters in the patternset* is that there exists constants $A,B$ such that every pattern of length $n$ is accepted by some NFA of size at most $An+B$. This is proved by structural induction on the patternset, and is a rather straightforward exercise.

Without knowing the constants $A,B$, you can't predict what the general claim gives you for any particular pattern. If you work out the proof, you will get values for $A,B$, and then you will be able to obtain a bound on the NFA size for your sample pattern; that bound probably would be worse than $4$. DFA size could be much bigger. For example, for an alphabet of size $n$, the set of all words *not* containing all characters has a description of size $O(n^2)$, but has DFA size $2^n$ (NFA size is $n$ or $n+1$, depending on the definition).

# Answer
> 0 votes
There is indeed an algorithm to convert a regular expression to a NFA of size linear in the size of the regexp, but this result holds for regular expressions defined in formal language theory. I am not so sure about the corresponding result for regexps used in programming languages, even if one considers only regexps representing regular languages. In particular, if you allow expressions of the form

```
     a\{n\}     (Matches 'a' repeated exactly n times.)

```

like in the POSIX Basic Regular Expressions, the result you mention does not hold anymore, since the size of a NFA accepting $\\{a^n\\}$ will be at least $n$, while the length of the expression a\\{n\\} will be $5 + log\_{10} n$.

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


title: Converting graphs to sets of paths

text:
# Question
Title: Converting graphs to sets of paths
I have an Euclidean, undirected graph: each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices.

* The number of vertices with no edges is small in comparison to the total number of vertices.
* No vertex has more than two edges connected to it.

How can I convert this graph to a closed shape, so each vertex will have exactly two edges connected to it and there will be a path between any two vertices? I want to do it with minimum change in the total weight of all the edges.

# Answer
> 2 votes
This should be NP-hard, here's a way you could try to do a reduction:

Take any graph $G$ embedded in the $\mathbb{R}^2$ plane. Let $c\_{min} = \min\_{e \in E}\\{c(e)\\}$ be the minimum edge weight in the graph ($c$ is the weight function of the edges of $G$, i.e. the euclidean distance). To build $G'$, split every vertex $v = (x,y)$ into $v\_1 = v$ and $v\_2 = (x+\epsilon,y)$ where $\epsilon = \frac{c\_{min}}{2^n}$, connect $v\_1$ and $v\_2$ with an edge weighted by their euclidean distance. Obviously, no vertex in $G'$ is incident with more than two edges, and there are no vertices that are incident with no edges.

What you now would have to prove is something like "there's a TSP route of weight $\le w$ in $G$ iff there's a TSP route of weight $\le w + n \cdot \epsilon$ in $G'$. I don't know how to prove that, but some geometry and use of the triangle inequality might help. I expect the choice of $\epsilon$ as vanishingly small will be enough to give the reduction.

EDIT: The reduction will remain valid after your edit.

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


# Question
Title: Why we can't have FPTAS for strong NP complete problems
I understood that we can apply FPTAS to the weak NP problems like 0-1 knapsack.

But why we cant apply the same principle to the strong NP problems like bin packing? I also checked wiki page about the same but understood very less.

# Answer
If there were an FPTAS for some strongly NP-complete problems then you could use the FPTAS to solve them in polytime. Consider for example bin packing. If the solution is of order $V$, then the input size is of order $V$. Therefore a $1-1/V$-approximation can be achieved in polytime, and since the answer is an integer, such an approximation actually gives the optimal answer. I'll let you work out the details.
> 10 votes

# Answer
Strongly NP-Hard problems are problems for whom it had been proved that obtaining an approximation for these problems will allow us solve other NP-Complete problems.

Here's a well-known example:

Assume an algorithm $A$ yields an approximation $\rho$ to the TSP in polynomial time.

Let $G$ be some graph for whom we want to determine if an Hamiltonian Circle exists (a known NP-Complete problem).

Let $G'$ be a complete graph with the same vertices as in $G$ ($V(G) = V(G')$). Connect each two vertices in $G'$ with an edge $e=(u,v)$ with weight 0 if $e$ belong to $E(G)$, otherwise $e$ has a weight of $\rho+1$.

Now find an approximation to the TSP on $G'$ by using $A$, if $A$ produced a solution that is $\< \rho+1$, we can determine that there's an Hamiltonian Path in $G$, otherwise, there isn't.

We proved that any approximation algorithm for the TSP will allow us to solve the Hamiltionian Circle problem and thus it is strongly NP-Hard.
> 1 votes

---
Tags: algorithms, np-complete
---


# Question
Title: Algorithm playing modification of "Hey, That's My Fish!" game
Ok, I must admit this a task from my studies but I'm stuck.

Rules of the game are on Wikipedia. However, we have a modified version: on input we have a board with x fields, there are y penguins on some fields, there may be gaps between fields. All penguins are the same, they can move only to the farthest possible location (in a straight line, can't jump over gaps and other penguins). There is one player and he needs to move the penguins in such manner so as to get the maximal number of fish. I have to come up with an algorithm that finds the sequence of moves that leads to the best possible result.

I tried something like guessing the final arrengment of the fields (f.e. all the penguins left on fields with just one fish each) and then reverse-engineer the steps but I didn't go any further with my idea.

I also thought it would be probably good to represent this as a graph, possibly with weighted edges and then do some graph search but again, I don't know what next.

Finally, there was a thought about using Monte Carlo method. However, this just seems too hardcore for a class project like this and that would be too diffult for me.

Any ideas where should I start?

# Answer
> 3 votes
You are probably supposed to use exhaustive search, that is, recursively try all possible moves. They made it easier by restricting the number of possible moves. One optimization which might be needed is storing board positions and the number of fish obtained from them, so that you don't analyze twice the same sub-position; there might be too many of them to store, and in that case you should only store "large" positions. Alpha-beta pruning could also be useful perhaps, but if you haven't learned about that, there is probably no need to use it.

---
Tags: algorithms, board-games
---


# Question
Title: Abstract machine that can recognize repetition
Let $C$ be an infinite set of characters. I'd like an abstract machine which can recognize sequences consisting of $k$ (constant) of repetitions of a char from $C$.

For example, if ${x,y,z} \subset C$, and $k = 3$, it should recognize $xxx$ but not $ddd$ or $xyz$. (The same char must be repeated.)

Since $C$ is infinite, a finite state machine *cannot* recognize this. A Turing machine trivially can. But we don't anything like the power of a Turing machine; simply extending the FSM with a single register that points to a member of $C$ is enough.

My question is: What's the simplest formal abstract machine that is powerful enough to recognize this? Is there a standard extension to FSM's that enables them to recognize this? If I have more complicated versions of this machine (e.g. *Move from state 2 to state 3 if you encounter a $k$ repetition of a $C$ char*), what's the best way to express them?

# Answer
There is a generalization of NFAs in which the transitions are labeled with regular expressions. (They are equivalent to NFAs and DFAs.) You can represent "twice the same letter" by $\sum\_{\sigma \in \Sigma} \sigma^2$. Of course, such expressions are not standard, but if you want a succinct representation, this is one.
> 2 votes

---
Tags: formal-languages, computability, turing-machines, automata, finite-automata
---


# Question
Title: Does coNP-completeness imply NP-hardness?
Does coNP-completeness imply NP-hardness? In particular, I have a problem that I have shown to be coNP-complete. Can I claim that it is NP-hard? I realize that I can claim coNP-hardness, but I am not sure if that terminology is standard.

I am comfortable with the claim that if an NP-complete problem belonged to coNP, then NP=coNP. However, these lecture notes state that if an NP-hard problem belongs to coNP, then NP=coNP. This would then suggest that I cannot claim that my problem is NP-hard (or that I have proven coNP=NP, which I highly doubt).

Perhaps, there is something wrong with my thinking. My thought is that a coNP-complete problem is NP-hard because:

1. every problem in NP can be reduced to its complement, which will belong to coNP.
2. the complement problem in coNP reduces to my coNP-complete problem.
3. thus we have a reduction from every problem in NP to my coNP-complete, so my problem is NP-hard.

# Answer
> 10 votes
You claim that *every problem in NP can be reduced to its complement*, and this is true for Turing reductions, but (probably) not for many-one reductions. A many-one reduction from $L\_1$ to $L\_2$ is a polytime function $f$ such that for all $x$, $x \in L\_1$ iff $f(x) \in L\_2$.

If some problem $L$ in coNP were NP-hard, then for any language $M \in NP$ there would be a polytime function $f$ such that for all $x$, $x \in M$ iff $f(x) \in L$. Since $L$ is in coNP, this gives a coNP algorithm for $M$, showing that NP$\subseteq$coNP, and so NP$=$coNP. Most researchers don't expect this to be the case, and so problems in coNP are probably not NP-hard.

The reason we use Karp reductions rather than Turing reductions is so that we can distinguish between NP-hard and coNP-hard problems. See this answer for more details (Turing reductions are called Cook reductions in that answer).

Finally, coNP-hard and coNP-complete are both standard terminology, and you are free to use them.

# Answer
> 6 votes
The problem with that line of reasoning is the first step. In the deterministic case, you can decide $x \in L$ with a TM $\text{M}$ iff you can decide $x \notin \overline{L}$ with it, because the way to do it is just flip the output bit of $\text{M}$ since its output only depends on $x$ (if we compare with the verifier definition of $NP$).

In the nondeterministic case using the verifier definition, it's not known whether you can build an $\text{NP}$-verifier from a $\text{coNP}$-verifier or vice versa, and the problem is that they have different quantifiers in the definitions that the verifier machines must fulfill. Let $L \in \text{coNP}$, then we have a verifier DTM $\text{M}$ such that:

$$x \in L \iff \forall z \in \\{0,1\\}^{p(|x|)}:\text{M}(x,z) = 1$$

For $\overline{L}$, the verifier $\text{M'}$ will have to fulfill

$$x \in \overline{L} \iff \exists z \in \\{0,1\\}^{q(|x|)}:\text{M'}(x,z) = 1$$

Why can't we then just use the $\text{NP}$-verifier $\text{M'}$ of the language $\text{K}$ to build a $\text{coNP}$-verifier $\text{M}$ for $\text{K}$? The problem is the $\forall$-quantifier required to have a $\text{coNP}$-verifier. The $\text{NP}$-verifier $\text{M'}$ may give you $0$ for **some** (wrong) certificate even for $x \in \text{K}$, so you can't go from $\exists$ to $\forall$.

Maybe more abstractly: it's not clear how to build (in polynomial time) a machine that recognizes exactly the elements of a language, regardless of what certificate come with them, from a machine that recognizes exactly the elements of a language that have some certificate for it, but for which also some certificates don't work.

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


title: Computer theory/ automata example help

text:
# Question
Title: Computer theory/ automata example help
Computer Language/Logic Examples? These are some of the questions i am having within a few chapters of my automata class and would like some help if you could :) Class is online and can be hard to self teach at times, you dont have to answer all or any for that matter, just thought id ask i got a midterm coming up and would like to know how to do these. ¯*(ツ)*/

Λ is not a word but it’s still used in its language? How do I show that there are other CFGs for these languages that do not use Λ-productions.

(ex i) S → aX | bX X → a | b | Λ

(ex ii) S → aX | bS | a | b X → aX | a | Λ

(ex iii) S → aS | bX X → aX | Λ

(ex iv) S → XaX | bX X → XaX | XbX | Λ

How would I convert these CFGs to CNF? (ex i) S → SS | a

(ex ii) S → aSa | SSa | a

(ex iii) S → aXX X → aS | bS | a

(ex iv) E → E + E E → E * E E → (E) E → 7 The terminals are + * ( ) 7

How would I make a PDA that accepts the same language (given that a CFG makes L then a PDA makes L) S → XaaX X → aX | bX | Λ

# Answer
There are online lecture notes which give *algorithms* for getting rid of $\epsilon$ productions ($\epsilon$ is another name for $\Lambda$) and for converting arbitrary grammars into Chomsky normal form. Both are reasonably simple. There is also an algorithm for converting a context-free grammar to a non-deterministic PDA, but if I remember correctly you first have to convert your grammar to Greibach normal form, so it might be better to understand what the language is and come up with a PDA for it directly.

Since you're taking this course online, I think it will be advantageous for you to find useful lecture notes online yourself, as part of your general education. Finding stuff over the internet is extremely useful, and if that's the only thing you get out of this course, you've already benefitted a lot.

I can illustrate the algorithms by solving some of your examples. In order to eliminate $\epsilon$-productions from your (i), the idea is that for every production that has $X$ in it, we create another one in which $X$ is missing. So we add productions $S \to a | b$. This works in general, but has to be applied iteratively.

In order to convert your (i) to Chomsky normal form, we only need to "rename" $S$: replace $S \to SS$ with $S \to TT$, and add $T \to TT|a$. Other cases require other operations; for example, if you had $A \to BCD$ then you would replace it with $A \to ED$ and $E \to BC$; and if you had $A \to Bc$ then you would replace it with $A \to BC$ and $C \to c$. This should be enough for you to work out the other parts of this question.
> 0 votes

---
Tags: automata
---


# Question
Title: Prove that any directed cycle in the graph of a partial order must only involve one node
So I have the question:

Prove that any directed cycle in the graph of a partial order must only involve one node.

So I know that a partial order must be transitive, antisymmetric, and reflective, but from there I am pretty lost. I also know that any path of one or more edges from a node to itself is a directed cycle, but from there I am having trouble connecting everything.

I kind of need help as to where to start thinking, and the first step as to how to answer this question.

# Answer
I'm assuming your partial orders are of the type "$a \leq b$" rather than of the type "$a \< b$", though the proof is very similar to both cases. Each edge $a \to b$ in the graph corresponds to an inequality $a \leq b$. Now suppose you had a triangle $a \to b \to c \to a$. Such a triangle would imply $$a \leq b \leq c \leq a, $$ which has some implications since $\leq$ is a partial order. The case of longer (or shorter) cycles is similar.
> 2 votes

# Answer
* A cycle is a strongly connected component (there is a path from every node to every other node).
* In a partial order, all nodes in a strongly connected component are all equally related; because there is a path from every node to every node: due to the transitive property, this means that $a \le b \wedge b \le a$ for all $a,b$ in the strongly connected component.

---

**Spoiler (mouseover):**

> This can contradict the antisymmetric property. "More formally, R is antisymmetric precisely if for all a and b in X: `if R(a,b) and R(b,a), then a = b`, or, equivalently, `if R(a,b) with a ≠ b, then R(b,a) must not hold.`" - wikipedia. It requires that: **iif two nodes are equally related to eachother, that they are the same node**. Thus, if a cycle contains more than one node, there are two nodes that are equally related ($a\le b, b\le a$), yet not the same ($a \ne b$). If the cycle is one node, then it is equal to itself and the same and thus the antisymmetric property holds.
> 2 votes

---
Tags: graphs, graph-traversal, partial-order, order-theory
---


# Question
Title: Are algorithms (and efficiency in general) getting less important?
Since buying computation power is much affordable than in the past, are the knowledge of algorithms and being efficient getting less important? It's clear that you would want to avoid an infinite loop, so, not everything goes. But if you have better hardware, could you have somehow worse software?

# Answer
> 31 votes
I really like the example from Introduction to Algorithms book, which illustrates significance of algorithm efficiency:

Let's compare two sorting algorithms: insertion sort and merge sort. Their complexity is $O(n^2) = c\_1n^2$ and $O(n\log n) = c\_2n \lg n$ respectively. Typically merge sort has a bigger constant factor, so let's assume $c\_1 \< c\_2$.

To answer your question, we evaluate execution time of a faster computer (A) running insertion sort algorithm against slower computer (B) running merge sort algorithm.

We assume:

* the size of input problem is 10 million numbers: $n=10^7$;
* computer A executes $10^{10}$ instructions per second (~ 10GHz);
* computer B executes only $10^7$ instructions per second (~ 10MHz);
* the constant factors are $c\_1=2$ (what is slightly overestimated) and $c\_2=50$ (in reality is smaller).

So with these assumptions it takes

$$ \frac{2 \cdot (10^7)^2 \text{ instructions}} {10^{10} \text{ instructions}/\text{second}} = 2 \cdot 10^4 \text{ seconds} $$ for the computer A to sort $10^7$ numbers and

$$ \frac{50 \cdot 10^7 \lg 10^7 \text{ instructions}} {10^{7} \text{ instructions}/\text{second}} \approx 1163 \text{ seconds}$$

for the computer B.

So the computer, which is 1000 times slower, can solve the problem 17 times faster. In reality the advantage of merge sort will be even more significant and increasing with the size of the problem. I hope this example helps to answer your question.

However, this is not all about algorithm complexity. Today it is almost impossible to get a significant speedup just by the use of the machine with higher CPU frequency. People need to design algorithms for multi-core systems that scale well. This is also a tricky task, because with the increase of cores, an overhead (for managing memory accesses, for instance) increases as well. So it's nearly impossible to get a linear speedup.

So to sum up, the design of efficient algorithms today is equally important as before, because neither frequency increase nor extra cores will give you the speedup compared to the one brought by the efficient algorithm.

# Answer
> 36 votes
On the contrary. At the same time that hardware is getting cheaper, several other developments take place.

First, the amount of data to be processed is growing exponentially. This has led to the study of *quasilinear* time algorithms, and the area of *big data*. Think for example about search engines - they have to handle large volumes of queries, process large amounts of data, and do it quickly. Algorithms are more important than ever.

Second, the area of *machine learning* is growing strong, and full of algorithms (albeit of a different kind than what you learn in your BA). The area is thriving, and every so often a truly new algorithm is invented, and improves performance significantly.

Third, *distributed algorithms* have become more important, since we are hitting a roadblock in increasing CPU processing *speed*. Nowadays computing power is being increased by *parallelizing*, and that involves dedicated algorithms.

Fourth, to counterbalance the increasing power of CPUs, modern programming paradigms employ virtual machine methods to combat security loopholes. That slows these programs down by an appreciable factor. Adding to the conundrum, your operating system is investing more CPU time on bells and whistles, leaving less CPU time for your actual programs, which could include CPU-intensive algorithms such as video compression and decompression. So while hardware is faster, it's not used as efficiently.

Summarizing, efficient algorithms are necessary to handle large amounts of data; new kinds of algorithms are popping up in the area of *artificial intelligence*; distributed algorithms are coming into focus; and CPU power is harnessed less efficiently for various reasons (but mainly, because computers are getting more powerful). Algorithms are not dead yet.

# Answer
> 12 votes
The knowledge of algorithms is much more than how to write fast algorithms.

It also gives you problem solving methods (e.g. divide and conquer, dynamic programming, greedy, reduction, linear programming, etc) that you can then apply when approaching a new and challenging problem. Having a suitable approach usually leads to codes which are simpler and much faster to write. So I have to disagree with Kevin's answer since codes that are not carefully put together are often not only slow but also complicated. I like this quote by David Parnas:

> I often hear developers described as "someone who knows how to build a large system quickly." There is no trick in building large systems quickly; the quicker you build them, the larger they get!

(Of course, we also need to combine algorithms with software design methods to write good codes.)

The knowledge of algorithms also tells us how to organize your data so that you can process them more *easily* and efficiently through the use of data structures.

Furthermore, it gives us a way to *estimate* the efficiency of your approach, and to understand the trade-offs between several different approaches in term of time complexity, space complexity, and the complexity of the codes. Knowing these trade-offs is the key to make the right decision within your resource constraints.

On the importance of software efficiency, I will quote Wirth's Law:

> Software is getting slower more rapidly than hardware becomes faster.

Larry Page recently restated that software gets twice as slow every 18 months, and thus outpaces Moore’s law.

# Answer
> 7 votes
**Yes**, they are **'relatively'** less important in wide industry. Text editor may be 'fast enough' and it might not need much improvements. Large part of IT effort goes to making sure component A written in Java works with component B written with C communicates correctly via message queue written in Cobol (or something), or to get the product to the market etc.

Furthermore the architecture got complicated. When you had plain old simple processors where you had 1 instruction per cycle and you wrote in assembly the optimizations were 'easy' (you just needed to count number of instructions). Currently you don't have a simple processor but a fully-pipelined, superscalar, out-of-order processor with register renaming and multiple level cache. And you don't write in assembly but in C/Java/etc. where code's compiled/JITed (usually to better code then you or I would wrote in assembly), or in Python/Ruby/... where code is interpreted and you are separated by several level of abstraction from machine. Microoptimalizations are hard and most programmers would achieve opposite effect.

**No**, they are as ever as important in research and in **'absolute'** terms. There are areas where speed is important as they operate on large amount of data. On this scale the complexities matter as shown by Pavel example.

However there are further cases - going 'down' from algorithms is still an option chosen when speed matters (HPC, embedded devices etc.). You will find on many universities groups specializing in compilers and/or software optimization. For example a simple swap of loop ordering can get a thousand time speedup just because it utilizes cache efficiently - while it might be a borderline example the CPU-Memory gap grow 1000 times over past 30 years. Also Computer Architecture is part of CS. Therefore many of the improvements in speed of computation are in fact a part of general CS field.

On the industrial side - when you have a HPC cluster speed matters because single program can run for days, months or years. Not only you need to pay the electricity bill but waiting also can cost money. You can throw twice as much hardware but 700M$ can be hardly considered a pocket change for all but biggest companies - in such cases the programmers are the cheaper option and if rewriting the program into new language mean just a 'small' speedup - they might consider it.

Also speed might mean better UX. Many reviews of mobile phones OS states which one is 'snappier' and while it can be done by 'tricks' it is certainly an area of study. Also you want to access your data faster and quickly do what you need. Sometimes it means you can do more - in games you have 0.017s to do everything and the faster you are the more candies you can put.

# Answer
> 2 votes
It is an interesting discussion. And we have a few things to look at here.

1. The theoretical computer science - This is an evolving science which means as time goes on we will find new and better ways to solve problems, which means improved algorithms for searching and sorting for instance.
2. Larger communities / larger libraries - Because a lot of work has been done by other people we can just build on their work and use the algorithms they have already created and even coded. And these libraries will be updated with time allowing us automatic access to more efficient programs/algorithms.
3. Development - Now here we have a problem I think. A lot of programmers are not computer scientists so they write code to solve business problems not technical / theoretical problems and would be as happy using a bubble sort as a quick sort for instance. And here the speed of hardware is allowing bad programmers to get away with using bad algorithms and bad coding practices. Memory, CPU speed, storage space these things are no longer major concerns and every few months things are getting larger, faster and cheaper. I mean look at the new Cellphones. They are now more advanced than the mainframe computers / servers from the 1970's / 80's . More storage, more processing power, faster memory.
4. UI & DATA - User Interface/ User Experience and DATA are now considered more important than super efficient code in most areas of development. So speed only becomes and issue when a user has to wait long. If we give the user a good look and feel and he gets good response from the application he is happy. And if business knows all data is stored safely and securely and they can retrieve it and manipulate it at anytime they do not care how much space it needs.

So I would have to say it is not that efficient programmers are no longer important or needed, it is just that very few companies/users reward people for being super efficient programmers, and because of the hardware being better we are getting away with being less efficient. But there are at least still people out there focusing on efficiency and because of the community spirit everyone in time gains benefit from this.

# Answer
> 1 votes
Some other angles on this interesting and deep question that emphasize the interdisciplinary and crosscutting aspects of the phenomenon. Dai quotes Wirth's law in his answer:

> Software is getting slower more rapidly than hardware becomes faster.

There are interesting parallels of this idea to phenomena observed in economics. Note that economics has many deep connections with computer science e.g. in say scheduling where scarce resources (say threads etc.) are allocated on request, by "load-balancing" algorithms. Another example is what is called a producer-consumer queue. Also, auctions.

Also e.g., List of eponymous laws, Wikipedia:

> Parkinson's law – "Work expands so as to fill the time available for its completion." Coined by C. Northcote Parkinson (1909–1993), who also coined its corollary, "Expenditure rises to meet income." In computers: Programs expand to fill all available memory.

There is some strong similarity also to Jevon's paradox which was observed in the increase in energy use after the more efficient Watt steam engines began to replace the Newcomen design, but use or proliferation of the engines increased:

> In economics, the Jevons paradox (/ˈdʒɛvənz/; sometimes Jevons effect) is the proposition that technological progress that increases the efficiency with which a resource is used tends to increase (rather than decrease) the rate of consumption of that resource.

The analogy is that hardware is the resource and software is like the consumption of the resource (aka, supply vs demand). So software and hardware (and advances in each) exist somewhat in a tightly-coupled symbiotic feedback loop with each other, in a sense, *coevolving*. There are many complex and interrelating factors influencing this interplay, e.g.:

# Answer
> -3 votes
No, mostly while considering space complexity! Storage capacity of a normal computer is growing exponentially.

---
Tags: efficiency
---


# Question
Title: Maximum number of inversions that can be removed by swapping two elements?
I have come across a question that is a bit hard to understand due to its wording, I may havecome up with a possible solution, but I don't know if it's correct. Can you please help me? Thanks in advance!

**Question**

Suppose we exchange elements $a\[i\]$ and $a\[j\]$, where $j \> i$, which are originally out of order.

For example, $a = \[2,8,3,7,1,5,6\]$ and we exchange the second and sixth elements, we have $\[2,5,3,7,1,8,6\]$.

The array has now fewer inversions. What is the maximum number of inversions that can be removed if we exchange $a\[i\]$ and $a\[j\]$?

**My proposed answer**

Take an array and sort it in reverse order. The first element would have the most inversions. We switch it with the last element and the number of inversions decrease drastically.

The maximum number of inversions would be $j-i+n-2$.

**My concern**

Since the question doesn't say anything about me being allowed to change the order of the array, I don't know if my proposed answer is the one they were aiming for.

# Answer
> 5 votes
The question is indeed not completely clear, but they definitely wanted you to search the "worst possible" array $a$ (the one leading to the largest number of removed inversions). Otherwise there is nothing to do - just look at the array and calculate the number of inversions resulting from the swap.

What is somewhat less clear is whether they also wanted you to optimize over $i$ and $j$. Your answer, which doesn't assume that, is on the safe side.

One thing you haven't shown is that your example leads to the maximal number of inversions being removed. The argument is very simple, but it's still needed for completeness.

---
Tags: sorting, arrays
---


title: String matching for all suffixes

text:
# Question
Title: String matching for all suffixes
Given a string $(a\_0,a\_1,\ldots a\_n)$. I want to find the length of the longest common prefix of the substrings $(a\_0,a\_1,\ldots a\_{n-1})$ and $(a\_1,a\_2,\ldots a\_n)$. I know this has atleast $O(n)$ complexity. Lets call this operation as *prefix-suffix match*.

I want to calculate *prefix-suffix match* length for all suffixes of a string. Now the naive algorithm which doesn't take into account that all the strings for which I am doing this operation are related has $O(n^2)$ complexity. Now my question is can we do this in better complexity.

Note that what I want is similar to LCP array of a slightly modified suffix array. Where the suffixes are sorted based on length instead of lexicographic ordering.

# Answer
> 1 votes
Expanding on reinierpost's comment, here is how to do it in linear time. Every word $w$ can be decomposed as $w = a\_1^{k\_1} a\_2^{k\_2} \cdots a\_l^{k\_l}$, where $a\_i \neq a\_{i+1}$ and $k\_i \geq 0$. This is just decomposition into runs. The LCP of $w$ and its shift is simply $a\_1^{k\_1-1}$.

In view of this, here is how to compute the answer for all suffixes of a word $w$ in linear time. We go over the array backwards, populating an array $K$ using the following algorithm:

1. $K\_n = 1$.
2. For $i = n-1,\ldots,0$:
    1. If $w\_i = w\_{i+1}$, $K\_i = K\_{i+1} + 1$, otherwise $K\_i = 1$.

The answer for the suffix starting at $w\_i$ is $w\_i^{K\_i-1}$.

---
Tags: algorithms, strings, suffix-array
---


# Question
Title: What would be a not arithmetically definable language that is not Turing reducible to another given not arithmetically definable language?
I have this question I'm struggling with.

Let $A=\\{\<i,n\>|\\;n \in \phi ^{(i)}\\}$. In other words, $A$ is the language defined by the set of all pairs $\<i,n\>$ such that $n$ is $\leq\_m$ to the $i$th Turing jump. A is definitely not an arithmetically definable language, and you can prove this by contradiction.

I have to find a language, let's say $B$, that is more complex than $A$ $i.e.$ $B\nleq\_T A$. I thought about $B=\\{\<i,n\>|\\;n \not\in \phi ^{(i)}\\}$, but I'm not sure about my reasoning, I think an oracle turing machine with an oracle $A$ couldn't reduce to $B$..

And one last thing, do you think there exists a language that is more complex than any other (it doesn't reduce to anything)?

If you have any hints that could help me solve those two questions I would be really grateful!

# Answer
Reiterating my comment, for each $A$ we can construct a language $A'$ (read: $A$ jump) which cannot be reduced to $A$ by taking all halting TMs with oracle access to $A$. The classical proof of the undecidability of the halting problem applies, showing that $A'$ cannot be (Turing-)reduced to $A$.
> 1 votes

---
Tags: complexity-theory, computability, reductions, arithmetic
---


# Question
Title: Recognizing finite state machines with repetition
I'm interested in finite state automata which have the capacity to require repetition. That is, the machine may be in a state in which the next character may be any character from set $S$, but, whatever character there is, it must be repeated 3 times. Or it may be in a different state, which requires a character from set $T$ repeated twice.

I could in theory make a different state for each character in set S, and for each character in set T. But that overcomplicates things and obscures the pattern - it can be any character in set S, but the same character must be repeated.

Is there any standard approach to this? I'm interested both in terminology and in practical code.

---

Motivation: I do not know the full makeup of the set $S$ or $T$. I'd like to be able to communicate effectively about the FSM, draw state diagrams, and do implementation, without having to define $S$ or $T$. In fact, $S$ and $T$ change based on the scenario. (Now, given a character, it's trivial to tell if it's part of $S$ or $T$ — but, a priori, it's impossible to enumerate them.)

At the least, I'd like a good way to draw a state diagram for these types of machines. Perhaps I should use a standard FSM with some type of annotation? Could state charts help with this?

# Answer
> 2 votes
Finite automata in which the transitions are regular expressions might be the model you are looking at. Indeed you could have transitions of the form $p \xrightarrow{aa + bbb} q$ to indicate that in order to go from $p$ to $q$, you need either 3 $a$'s or 2 $b$'s. This model has the same expressive power as NFAs and DFAs.

# Answer
> 1 votes
(Previously a comment, made into an answer instead)

In finite automata, using additional states is the pattern to what you're asking. Adding scratch, or working, memory may give you something that is formally no more powerful than the FA model, but which is nonetheless different. What you want is like a pizza without any dough: lacking memory, or rather, encoding memory entirely within state information, is the defining characteristic of a DFA. Of course, you could define your own machine model with finite scratch memory and prove it's the same as a DFA, but that's not exactly what you asked.

---
Tags: algorithms, regular-languages, formal-grammars, finite-automata
---


# Question
Title: Is there a name for this infinite language?
Is there a name for this infinite language?

$$L = \\{ 0(,1)^\*(,2)^\*(,3)^\*....(,n)^\* \\;\mid n \geq 1\\}$$

A string $w \in L$ is simply an ordered list of increasing integers in which every integer $\geq 1$ can be repeated 0 or more times, for example "0", "0,1", "0,1,2,2", "0,1,2,3", "0,1,1,4,4,4,21,21".

Or perhaps a name for its unary variant: $L\_U = \\{ 1^{x\_1}(,1^{x\_1})^\*,1^{x\_2}(,1^{x\_2})^\*,...,1^{x\_n}(,1^{x\_n})^\* \mid x\_1\<x\_2\<...\<x\_n\\}$

# Answer
Non-decreasing sequences of natural numbers.
> 6 votes

# Answer
I don't know of any standard name, but I think calling it the language of sorted lists (or: sorted lists of integers) would be reasonable.
> 1 votes

---
Tags: terminology
---


# Question
Title: $k$-way merge but without an absolute order
I have $k$ lists that I would like to combine to a single list. Each list's elements are unique and are sorted in a particular order, but there is no notion of an absolute order, and different items across lists can only be compared if they are equal. To give a specific example (here I use $\<$ to indicate the sorting inside each list):

```
l1 = a < b < c
l2 = b < d

```

`l1 + l2` should result in one of the following (and I don't care which one it results in):

```
a < b < c < d
a < b < d < c

```

If the lists are incompatible, e.g. `a < b` and `b < a` then I want to get an error. The resulting list (if it exists) should respect all of the orderings of the sublists. Also all the items should be unique in the result.

I thought about modifying k-way merge somehow but it's not clear to me how to do that without a global order. By the way, I'll probably be happy with a $O(nk)$ solution.

---

Perhaps a better way to phrase the problem is this. I'd like to construct an order vector given $k$ pieces of that order vector (or get an error if that's impossible).

Here's an algorithm that I think works for $k=2$. Find and mark all the duplicates - I think this is $O(n)$ - then start writing down elements from first list until you hit a duplicate, once you do add all elements from second list until you hit that same duplicate, then write down the duplicate and continue. The part where it's a bit more tricky with $k\>2$ is that the duplicate may not be in every list to do the above (and this process cannot be done sequentially, i.e. `l1+l2+l3` is generally not the same as `(l1+l2)+l3`, where `+` denotes this operation of finding the superset order list).

It should be easy to extend the above to any $k$. Use a hash to find which lists each unique element belongs to. Then traverse along the first list using the above logic - writing down all elements until you hit first duplicate, in which case write down all elements (that haven't been written down yet) in all other lists before that duplicate and keep doing that until you reach the end of first list. If haven't reached the end of second list, continue same algorithm there and so on. Each list will be traversed twice - once to get the duplicates, and second time to do the above, making it $O(n)$. A compatibility error will be discovered if you iterate along a list but can't find the duplicate (because it was already written down in an earlier pass).

# Answer
> 5 votes
Edit: You recently revised the question to clarify that you are allowed to hash items. That changes the question: it lets us build much more efficient algorithms.

With this change, your question becomes: given $k$ partial orders, find a total order that is consistent with all of the $k$ partial orders. This problem can be solved in linear time, i.e., in $O(n)$ time, where $n$ is the total number of items across all of the sublists.

Here's how to solve it. We'll build a directed graph, where each item (in any sublist) is a vertex is the graph. Traverse the sublists to extract all consecutive pairs of items that appear in any sublist. If you have `a < b` in a sublist (i.e., item `a` immediately precedes `b` in some sublist), add an edge $a \to b$ to the graph. (Notice that you can have a hashtable that maps the item `a` to the corresponding vertex $a$ in the graph, so this operation involves two lookups in the hashtable and then adding an edge: $O(1)$ time.)

Once you've built the entire graph, topologically sort it, and output the vertices in topologically sorted order. That will be a valid output list that solves your problem. If the topological sort fails and reports that the graph has a cycle, then your sublists are inconsistent and you should output an error.

This solves your problem in linear time, i.e., $O(n)$ time.

---

My original answer to your original question: You don't list any requirements on what order the combined list elements must appear in. Therefore, concatenating/interleaving all of the list items in an arbitrary order appears to meet all of the explicitly stated requirements. If that's not an acceptable solution, you'll need to think through your requirements more carefully and then edit your question to state the requirements explicitly.

I *suspect* you meant to require that the elements in the combined list must appear in an order that is consistent with the order in each sublist, and any item should appear only once in the combined list. If that's what you meant, then you can't do better than $O(n^2)$ time, where $n$ is the total number of items across all of the sublists: there's no way to avoid comparing each item of each sublist with each other. (If there is any pair of items which you have not compared explicitly, you have no way of knowing whether they are equal or not: both are possible.)

It's easy to achieve an $O(n^2)$-time algorithm. You simply compare each item to all other items, to first find all duplicated items (items that appear in more than one sublist). Then, you do a straightforward $k$-way merge. At each step of the $k$-way merge, you look at the head of each of the $k$ sublists and classify each of those $k$ items as duplicated or not. If any of them are non-duplicated, you can remove it from the head of its sublist and append it to the combined list. If one of them is duplicated, and all of its duplicates appear among these $k$ items, then you remove each of them from their corresponding sublists and append it to the combined list. Repeat this until done. If no items appears twice in any sublist, and if all of the sublists are sorted in a compatible way (e.g., you don't have `a` before `b` in one sublist but `b` before `a` in another sublist), then this process will never get stuck and will yield the desired output.

The running time of this algorithm is $O(n^2)$, and it's not possible to do better than that (assuming the only operation available on items is to test two items for equality), so this algorithm is optimal up to a constant factor.

---
Tags: algorithms
---


# Question
Title: How to analyze the lower bound of the horse racing problem using adversary argument?
Consider the following problem:

> Give an algorithm to find the $1^{st}, 2^{nd}, 3^{th}$ fastest horses from 25 horses. In each round, at most 5 horses can race and you can get the exact position of these horses. Analyze the lower bound of this problem using *adversary argument*. One race is considered as one critical operation.

I can figure out a solution using 7 races:

> 1. Divide 25 horses into 5 groups with 5 horses for each: $A: a\_1, a\_2, a\_3, a\_4, a\_5$; $B: b\_1, b\_2, b\_3, b\_4, b\_5$; $C: c\_1, c\_2, c\_3, c\_4, c\_5$; $D: d\_1, d\_2, d\_3, d\_4, d\_5$; and $E: e\_1, e\_2, e\_3, e\_4, e\_5$.
> 2. One race within each group. Suppose that the position of each horse in each group is consistent with its index: e.g., $A: a\_1 \> a\_2 \> a\_3 \> a\_4 \> a\_5$.
> 3. One race for $a\_1, b\_1, c\_1, d\_1, e\_1$ and get $a\_1 \> b\_1 \> c\_1 \> d\_1 \> e\_1$. Thus, $a\_1$ is the fastest horse.
> 4. The second and third ones are among $a\_2, a\_3, b\_1, b\_2, c\_1$. So one more race is enough.

However I have difficulty in analyzing its lower bound using adversary argument. So my problem is:

> How to analyze its lower bound using *adversary argument*? What is the adversary strategy?

# Answer
Intuitively, the reason you need $7$ comparisons is that (1) you need $5$ comparisons just to see all the horses, (2) you need to compare all the first ranked horses to see which one is the fastest, (3) at this point you can't tell which is the second ranked horse.

Of course, this is not quite an adversary argument, and some work will be needed, though it is easy to use an adversary argument to show that (1) is correct: suppose that the strategy involves less than $5$ comparisons; then you don't see all the horses; so you can't tell whether the fastest horse is one of those you've seen or not. (Formally, if the algorithm states that a horse it's seen is the fastest, then you arrange for one of the one it didn't see to be the fastest; and vice versa in the other case.)

The same argument can be extended to show that $5$ comparisons are not enough: the only way that $5$ comparisons could be enough is by executing step 2 of your algorithm, and then you cannot tell which horse is the fastest. (I'll let you formalize that.)

I'll let you complete the argument and show that $6$ comparisons are also not enough.
> 4 votes

---
Tags: algorithms, algorithm-analysis, lower-bounds
---


title: Efficient way to find intersections

text:
# Question
Title: Efficient way to find intersections
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 am randomly creating a path thru all the vertices and I want to know if there is any efficient way to find all the intersections on my path.

# Answer
A path of length $n$ consists of $n$ line segments in the plane. You want to find all intersections between these line segments. This is a standard problem that has been studied in depth in the computer graphics literature.

A simple algorithm is the following: for each pair of line segments, check whether they intersect (using a standard geometric algorithm). The running time of this algorithm is $O(n^2)$. In terms of worst-case complexity, this is the best we can hope for, as in the worst case, there can be $\Theta(n^2)$ intersections, so obviously it'll take at least $\Theta(n^2)$ time to output them all.

However, in many cases, we have an arrangement of line segments where there are only a few intersections, say at most $O(n)$ intersections. In this case, there are algorithms whose running time is $O(n \lg n)$. See, e.g., the sweep line technique; there are others as well. In general, if there are $k$ intersections, the total running time for the sweep line algorithm to find all $k$ intersections is $O((n+k) \lg n)$ time.
> 14 votes

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


# Question
Title: A technical clarification on subgraph isomorhism
Let $G$ be a graph on $|\mathcal{V}(G)|$ vertices. If $H$ is another graph that contains a clique of size $|\mathcal{V}(G)|$, then does it mean $G$ is subgraph isomorphic to $H$? Does this mean that all graphs with vertices less than $|\mathcal{V}(G)|$ are subgraph isomorphic to $H$?

If the above is not the case, is there another term for the exact presence of $G$ in $H$ as a structure preserved subgraph (when I say structure preserved, that means, edges are mapped to edges and non-edges are mapped to non-edges in the subgraph of $H$)?

# Answer
> 4 votes
The subgraph isomorphism problem is "Is $G$ isomorphic to some subgraph of $H$?" so, yes, if $H$ contains a $k$-clique, that clique on its own has subgraphs isomorphic to any graph on $k$ or fewer vertices. Your "exact presence" version is the induced subgraph isomorphism problem: is $G$ isomorphic to some induced subgraph of $H$? Both versions are NP-complete.

You could have found this trivially by Googling for "subgraph isomorphism problem".

---
Tags: graphs
---


# Question
Title: difference between propagation speed and bandwidth in digital communication
I want to know difference between propagation speed and bandwidth in digital communication.I know bandwidth is no of bits in one second and propagation speed of signal is distance traveled by signal is one second.Is there any relation between them or they are totally different.Can anyone tell me exact definition to differentiate these twos.

# Answer
> 3 votes
They are unrelated.

The bandwidth is, as you correctly said, the number of bits per second. The propagation speed is the time until the first bit arrives (this is also called the latency).

Imagine you have an army of snails that can carry SD cards along a straight line. Their propagation speed is very slow, so it takes a long time until a snail arrives after you send it. However, you can send a snail every second, so that after the initial delay your snails deliver one SD card of data every second. That's high bandwidth.

---
Tags: computer-networks
---


# Question
Title: What does this context-free grammar generate?
The grammar is

$$ S\to aSb\ |\ bSa\ |\ SS\ |\ \epsilon. $$

I think this generates the set of strings with equal numbers of $a$'s and $b$'s based on examples I've done. Is this correct?

# Answer
This doesn't seem particularly rigorous as far as arguments go, but it's early here. Besides, this might help with intuition.

To see that the grammar generates words in the language, consider that every rule which adds either $a$ or $b$ adds an equal number of the two. Therefore, any string the grammar generates must have equal numbers of the two symbols.

To see that any word in the language can be generated by the grammar, consider any word $w$. We can definitely write $w$ as one of the following:

1. $w = axa$
2. $w = axb$
3. $w = bxa$
4. $w = bxb$

In cases 2 and 3, we can have applied the productions $S \rightarrow aSb \mid bSa$; we have that $w$ can be generated by our grammar if $x$ can. We also have that $|x| \< |w|$. In cases 1 and 4, we must have used the rule $S \rightarrow SS$ to get $w$; let us now write $w = xy$ where $x$ and $y$ are also strings in the language (exercise: show this is always possible in the cases considered). We have $|x|, |y| \< |w|$.

Both strings of length 2 in the language can be generated by the grammar (we could choose the empty string as the base case instead, might make more sense). By recursively applying the analysis in the preceding paragraph, we can find a way to generate any string in the language (since all words are even length, child words are shorter than parent words, and length 2 is the base case).
> 2 votes

# Answer
You conjecture that your grammar generates the language $L$ of words having as many $a$s as $b$s. In order to prove your conjecture, you should do two things:

1. Prove that every word generated by the grammar belongs to $L$.
2. Prove that every word in $L$ can be generated by the grammar.

In this case, the first part is easy to prove by structural induction. The second part is more difficult, so here is a hint. Given any non-empty $w \in L$, show that it can be decomposed as either $w = xayb$ or $w = xbya$ for some $x,y \in L$. Given this lemma, you can use induction on $|w|$.

Here is a hint for the lemma. Let $d\_k(w) = |\\{i \in \[k\] : w\_i = a\\}| - |\\{i \in \[k\] : w\_i = b\\}|$, and let $d(w) = d\_0(w),d\_1(w),\ldots,d\_{|w|}(w)$. For example, $d(aabb) = 0,1,2,1,0$ and $d(baba) = 0,-1,0,-1,0$. A prefix $w\_1\ldots w\_k \in L$ corresponds to a position $k$ such that $d\_k(w) = 0$.
> 3 votes

---
Tags: context-free
---


# Question
Title: Is the Syntax of C Language completely defined by CFGs?
I think the Question is self sufficient. Is the syntax of C Language completely defined through Context Free Grammars or do we have Language Constructs which may require non-Context Free definitions in the course of parsing?

An example of non CFL construct i thought was the declaration of variables before their use. But in Compilers(Aho Ullman Sethi), it is stated that the C Language does not distinguish between identifiers on the basis of their names. All the identifiers are tokenized as 'id' by the Lexical Analyzer. If C is not completely defined by CFGs, please can anyone give an example of Non CFL construct in C?

# Answer
The C language has typing rules. For example, you can't divide two pointers, and when you call a procedure accepting a pointer, you can't use a double. A C compiler analyzes its source in several phases: first there is lexical analysis, then the source is parsed, and so on. These phases are abstraction, and in fact additional information is passed from phase to phase. For example, even though the grammar of C doesn't care about names of variables, this information is passed, and that's how the attributed grammar can verify the typing rules. So there are additional mechanisms working on top of the grammar.

For an even simpler example, take the one given by Aho and Ullman. At the parsing phase, all variable names look "the same", yet you cannot use a variable unless it had been declared. This information is hidden from the context-free parser, but is retained as an attribute for the lexical phase, and is checked during parsing. The context-free grammar of C represents only some aspects of what legal C code is, which are useful for implementing a fast parser. On top of that parser, the other rules are checked, semantics are given to the C code, and machine code is generated.
> 13 votes

---
Tags: context-free, programming-languages, compilers, parsing, c
---


title: Software for testing graph homomorphism

text:
# Question
Title: Software for testing graph homomorphism
I have graphs $G\_k$ and $H\_k$ with $|\mathcal{V}(G\_k)|=|\mathcal{V}(H\_k)|^{2k}=n^{2k}$ with $k\in\Bbb N$ that pass sanity checks such as no-homomorphism lemma. Are there free and easy to use tools to test graph homomorphism from $G$ to $H$?

# Answer
> 8 votes
The best way (in terms of laziness) is to use the freely available tool Sage which has the best support for graph theory.

Example

```
sage: G = graphs.PetersenGraph()
sage: G.has_homomorphism_to(graphs.CycleGraph(5))
False
sage: G.has_homomorphism_to(graphs.CompleteGraph(5))
{0: 0, 1: 1, 2: 0, 3: 1, 4: 2, 5: 1, 6: 0, 7: 2, 8: 2, 9: 1}

```

# Answer
> 6 votes
One approach would be to use a SAT solver.

Introduce a boolean variable $x\_{t,v}$ for each vertex $t$ from $G$ and each vertex $v$ from $H$. The intuition is that $x\_{t,v}$ will be true if the homomorphism maps $t \mapsto v$. (Of course, if you have a smaller candidate set of vertices that $t$ could map to -- maybe narrowed down using degree considerations or other local criteria -- then you can reduce the number of boolean variables accordingly. This kind of preprocessing might improve the efficiency of this approach significantly.)

Next, add two kinds of clauses/constraints:

* Add some clauses to require that this mapping forms a graph homomorphism. In particular, for each edge $(t,u) \in E(G)$, add the constraint

$$\bigvee\_{(v,w) \in E(H)} (x\_{t,v} \land x\_{u,w}).$$

(You can convert this to 3CNF using the standard Tseitin transform.)
* Add some clauses to require that each vertex $t$ from $G$ maps to exactly one vertex $v$ from $H$. There are a number of standard methods for encoding this constraint. One simple way is, for each vertex $t \in V(G)$, add the clause

$$\bigvee\_{v \in V(H)} x\_{t,v}$$

and the clause

$$\bigwedge\_{v,w \in V(H)} (\neg x\_{t,v} \lor \neg x\_{t,w}).$$

Then, you can use any standard SAT solver. I don't know how well it will work in practice, but you could give it a try and see how it works out.

---

In the research literature, the graph homomorphism problem has been studied extensively for graphs with special properties (e.g., where $H$ is a clique, whre $H$ has bounded treewidth, and so on). If you know something special about the structure of your graphs, it may be possible to find better algorithms for your problem. For general graphs, this problem is known to be NP-hard.

---
Tags: complexity-theory, graphs
---


# Question
Title: Estimating the time until we obtain five-in-a-row?
Consider the following random process. We have a $10\times 10$ grid. At each time step, we pick a random empty grid cell (selected uniformly at random from among all empty cells) and place a marker in that grid cell. As soon as we have five contiguous markers in a line (in a row, column, or diagonal), we stop.

I'm given a grid containing some markers in some positions, and I'd like to estimate how long until the process stops if we start from that configuration (i.e., the number of additional time steps until five-in-a-line occurs). I would be happy with any reasonable metric for that: e.g., the expected time until it stops, or the value $t$ such that there's a probability $0.5$ that the process will stop in $\le t$ time steps. I'd be happy with an estimate of any such metric.

Is there any efficient algorithm to estimate this metric, given a configuration where some markers have already been placed? I'm hoping for something faster than random simulation (repeatedly simulating the process and computing an estimate based upon the resulting empirical distribution).

# Answer
Just for fun, I coded this up in Mathematica. I started with a $10 \times 10$ matrix initialized to all zeros. I then considered two processes throwing darts in the cells: **(1)** a cell is chosen uniformly and independently at random from the set of all cells, and **(2)** a cell is chosen uniformly and independently at random from the set of all empty cells. When a dart hits a cell, the value of that cell is set to $1$. A five-in-a-row can appear on a row, column, the diagonal, or on the antidiagonal.

For both processes, I ran $N = 20000$ simulations. Rounded up to the nearest integer, for process **(1)** we need $65$ dart throws on average to obtain a five-in-a-row. For process **(2)**, the same number was $47$.

This is not exactly what you were asking for, but maybe you can at least compare the numbers you get with mine.
> 2 votes

---
Tags: algorithms, combinatorics, probability-theory, approximation
---


title: Unranking paths in a graph/lattice

text:
# Question
Title: Unranking paths in a graph/lattice
> A ranking algorithm determines the position (or rank) of a combinatorial object among all the objects (with respect to a given order); an unranking algorithm finds the object having a specified rank. Thus, ranking and unranking can be considered as inverse operations.

The following lattice has 9 unique max length paths from {} to {1,2,3,4,5}, which can be obtained by a depth first search.

(The graph is directed, with arrows pointing down)

Is it possible to write a function that generates the N'th path without enumerating paths 1..N-1.

see: https://math.stackexchange.com/questions/510911/computing-all-simple-paths-in-a-distributive-lattice-in-parallel for more problem details.

# Answer
> 2 votes
Suppose without loss of generality that there is one source $\emptyset$ and one sink $S$. For each node $v$ in your digraph, you can compute recursively the number $N\_v$ of unique maximum length paths from $\emptyset$ to $v$: at $\emptyset$ we have $N\_\emptyset = 1$, and at other points, $N\_v = \sum\_u N\_u$, where the sum goes over all immediate predecessors of $u$.

This suggests the following encoding for maximal paths at a node $v$. Suppose the immediate predecessors of $v$ are $u\_1,\ldots,u\_k$, in some arbitrary but fixed order. We will encode all paths as numbers in the range $\[0,N\_v)$ ($=\\{0,\ldots,N\_v-1\\}$) in the following way: all paths through $u\_1$ will be encoded in $\[0,N\_{u\_1})$, all paths through $u\_2$ will be encoded in $\[N\_{u\_1},N\_{u\_1}+N\_{u\_2})$, and so on. Inside each interval, we apply the same encoding scheme recursively. By applying this scheme for $v = S$ (the sink), we get an efficient encoding system for all maximal paths.

---
Tags: graphs, combinatorics, lattices
---