# Question
Title: Is the power of a regular language regular? Is the root of a regular language regular?
If $A$ is a regular set, then:

$L\_1=\\{x\mid\exists n \geq0, \exists y \in A: y=x^n\\}$,

$L\_2=\\{x\mid \exists n \geq0, \exists y\in A: x=y^n\\}$.

Which one of them is regular?

My reasoning is since in $L\_2$ we can have uncountable $x$ from even one value of $y\ (y^0, y^1, y^2,...),\ L\_2$ cannot be regular. But that thinking seems wrong.

# Answer
The language $L\_2$ is not necessarily regular. Indeed, consider $A = a^\*b$. If $L\_2$ were regular, then so would the following language be: $$L\_2 \cap a^\*ba^\*b = \\{ a^nba^nb : n \geq 0 \\}.$$ However, this language is not regular (exercise).

In contrast, the language $L\_1$ is regular. We can see this by constructing a DFA for it. Let the DFA for $L\_1$ have states $Q$, initial state $q\_0$, accepting states $F$, and transition function $\delta$. The states of the new DFA are labeled by functions $Q \to Q$. The idea is that the new DFA is at state $f\colon Q \to Q$ if the original DFA moves from state $q \in Q$ to state $f(q)$ after reading $w$ (i.e., if $\delta(q,w) = f(q)$ for all $q \in Q$). The initial state is the identity function. When at state $f$ and reading $\sigma$, we move to the state $g$ given by $g(q) = \delta(f(q),\sigma)$. A state is accepting if $f^{(n)}(q\_0) \in F$ for some $n \geq 0$.
> 6 votes

# Answer
$L\_1$ is regular.

Let $M=(Q,\Sigma,\delta,q\_0,F)$ be a DFA recognizing $A$, and we denote by $M(s)$ the state $M$ reaches finally after reading the string $s$. Consider some $x\in L\_1$, and let $n$ be the smallest one such that $M$ accepts $x^n$. We have $M(x^n)\in F$, and $M(x^0),M(x^1),\ldots,M(x^{n-1})\notin F$ (otherwise we can choose a smaller $n$ instead). Moreover, $M(x^0),M(x^1),\ldots,M(x^{n-1})$ must be pairwise different otherwise $M$ will never reach $M(x^n)$, hence we have $n\le |Q|$. This means we can rewrite $L\_1$ as

$$L\_1=\bigcup\_{n=0}^{|Q|}\\{x\mid x^n\in A\\}.$$

We only need to prove $\\{x\mid x^n\in A\\}$ is regular for all $n$ because the union of finite many regular languages is still a regular language. We prove this claim by mathematical induction.

For $n=0,1$, this is trivial.

Suppose $\\{x\mid x^n\in A\\}$ is regular for some $n\ge 1$. Denote by $M\_q=(Q,\Sigma,\delta,q,F)$, i.e. the DFA by changing the start state of $M$ to $q$. We have \begin{align} \\{x\mid x^{n+1}\in A\\}&=\bigcup\_{q\in Q}\\{x\mid M(x)=q \wedge M\_q(x^{n})\in F\\}\\ &=\bigcup\_{q\in Q}\left(\\{x\mid M(x)=q \\}\cap\\{x\mid M\_q(x^{n})\in F\\}\right). \end{align} Since $\\{x\mid M(x)=q \\}$ and $\\{x\mid M\_q(x^{n})\in F\\}$ (by inductive assumption) are both regular languages for all $q\in Q$, $\\{x\mid x^{n+1}\in A\\}$ is also a regular language.

Q.E.D.

---

$L\_2$ is not regular.

Let $A$ be the language expressed by the regular expression $0^\*1$, then $L\_2$ is not regular by pumping lemma.
> 2 votes

# Answer
I used the following reasoning, but it has a flaw, see comment below:

> $L\_2$ is regular. As $A$ is regular, then there is a regular expression $e$ such that $A=L(e)$. It is easy to see that $L\_2=L(e^\*)$.
> -2 votes

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


# Question
Title: Minimum and maximum of sum of inverse degree of a graph
Suppose we have a simple undirected graph $G(V,E)$, where $V$ and $E$ are the set of vertices and edges respectively. we denote $d(v)$ as the degree of a vertex $v \in V$. I am interested to find closed form or a tight bound of the following quantity

$$ D = \sum\_{e=\\{u,v\\} \in E} \frac{1}{d(u)+d(v)} $$

For example, suppose we have a complete graph with $n$ vertices. Then $D$ becomes $$ D = \frac{n(n-1)/2}{2(n-1)} = n/4$$.

For a path graph with $n$ vertices ($(n-1)$ edges) $D$ is $ \frac{(n-3)}{4}+2/3 $. My question is

1. Is there any closed form of $D$ for general graph that involves $|V|$?
2. If not is there any tight lower bound on the sum?
3. Can we claim something like that the $D \geq |V|/k$ where k is a constant and $k\<\<|V|$?

\*Yuval conjectured that $D \geq 1−1/n$ for a connect graph with $n$ vertices.

# Answer
Nice question!

---

There is no simple closed form of $D$ for general graphs that involves $|V|$ since $D$ can take at least two different values for any connected graph with more than 2 vertices. $D=1-\frac1{|V|}$ for a start graph and $D=\frac{|V|}4 \> 1-\frac1{|V|}$ for a cycle graph. In fact, I would believe that the number of different values of $D$ for a graph of $n$ vertices grows exponentially with respect to $n$.

---

## Yuval's tight lower bound

**Claim: $D \geq 1−1/n$ for a connect graph with $n$ vertices, where the equality holds for and only for star graphs.**

**Proof**. Let $G$ be a connect graph with $m$ edges. Since $G$ is connected, $m\ge n-1$, where the equality holds for and only for tree graphs. Let $e=\\{u,v\\}$ be an edge in $G$. $$\begin{aligned} d(u)+d(v) &= \Sigma\_{s\in E,\\, s \text { contains u}} 1 + \Sigma\_{s\in E,\\, s \text { contains v}} 1 \\ &= (1 + \Sigma\_{s\in E,\\, s \text { contains u},\\, s\neq e} 1) + (1 + \Sigma\_{s\in E,\\, s \text { contains v},\\, s\neq e} 1) \\ &= 2 + (\Sigma\_{s\in E,\\, s \text { contains u},\\, s\neq e} 1 + \Sigma\_{s\in E,\\, s \text { contains v},\\, s\neq e} 1) \\ &\le 2 + \Sigma\_{s\in E,\\, s\neq e} 1\\ &= 2 + (m -1)\\ &= m +1 \end{aligned}$$ The inequality above holds since the only edge that contains both $u$ and $v$ is $e$. The equality $d(u)+d(v)=m+1$ holds when every edge besides $e$ has a common vertex with $e$.

So, $$ D = \sum\_{e=\\{u,v\\} \in E} \frac{1}{d(u)+d(v)} \ge m\\, \frac1{m+1} = 1 - \frac1{m+1} \ge 1-\frac1n $$

The equality $D=1-\frac1n$ holds when there are $n-1$ edges in total and every two edge has a common vertex, which means the graph is a star graph.

---

There is no positive constant $k$ such that $D \geq |V|/k$, since $|V|/k$ goes to infinity while $1-1/|V|$ stays below 1 when $|V|$ goes to infinity.
> 3 votes

---
Tags: graphs, lower-bounds
---


# Question
Title: Can this DFA be converted to a regular expression?
I want to make the regular expression of this language but I can't: I tried but the regular expression didn't match some strings that it should. Is it even possible?

# Answer
> 2 votes
*Every* DFA can be converted to a regular expression, so you must have made a mistake when you converted. The conversion is quite fiddly, so making a mistake with a nine-state automaton is easy to do, unfortunately.

It might help if you split the automaton in two: if the automaton accepts, it either reads an $a$ and then accepts using only states $2,4,6,\omega$ or it reads a $b$ and then accepts using only states $3,5,7,\omega$. So the regular expression must be something of the form $aR\_{\\{2,4,6,\omega\\}}+bR\_{\\{3,5,7,\omega\\}}$, where $R\_S$ is the regular expression for the automaton that just has the states in $S$. Now, you just have to convert two nearly identical four-state automata, which should be easier to do correctly.

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


# Question
Title: Proof By Contradiction - Hamiltonian Paths and Cycles
Was hoping if anyone had any way to prove the following claim using proof by contradiction

> Let $G = (V, E)$ be a simple graph with at least one vertex, and let $G'$ be the graph formed by adding a new vertex $v$ and making it adjacent to every vertex in $V$.
>
> Claim: $G$ has a Hamiltonian Path if and only if $G'$ has a Hamiltonian cycle.

I tried manipulating the definitions of each of the two (path vs. cycle), but didn't find much luck. Any thoughts?

Thanks!

# Answer
> 1 votes
Contradiction isn't the most natural way to do this, since there's a straightforward constructive proof.

Suppose $G$ has a Hamiltonian path. How can you extend that to a Hamiltonian cycle of $G'$? Conversely, suppose that $G'$ has a Hamiltonian cycle. Cover up $v$ with your finger – what do you see?

It's possible to rewrite the reasoning hinted at above as a proof by contradiction, but it's not very natural. ("Suppose $G$ has a Hamiltonian path but $G'$ has no Hamiltonian cycle. Oh, look, here's a Hamiltonian cycle in $G'$ – contradiction.")

---
Tags: graphs, reductions, proof-techniques
---


# Question
Title: Maximum number of segments with no intersection
This is an interview question.
Suppose you have an array of `n` segments, when each segment is a pair of two integers: start point and end point. For example: `(1,3)`.

Two segments `s1,s2` are intersecting if
`(s2.start<=s1.start<=s2.end) or (s1.start<=s2.start<=s1.end)`
For example: `(1,3),(2,4)` are intersecting.

Find an algorithm for finding maximum number of segments in the array (and returning those segments in some list) which don't intersect.

My attempt: I thought maybe some sorting can help, but didn't find how so tried something else. Then the interviewer gave me a hint: the run time expected is `O(nlogn)`.

So now I'm sure the solution need to involve some sorting algorithm, but I don't know how to use it.

Any suggestions?

# Answer
> 4 votes
I can show you a solution that I suspect is $O(n \log n)$, but I haven't proven the runtime. **Edit:** Following a linked solution, I amended this solution to be simpler and run in $O(n \log n)$.

So the issue is that if you take a greedy approach, you might choose a 'bad' segment that blocks a favorable choice later. That is, *choices you make at the beginning affect what choices you have available later on*. This suggests a dynamic programming approach.

First step is to sort the segments by their start times. Then, you need to define exactly what you're going to calculate. We'll define $numsegs(i)$ as the max number of segments possible when segment $i$ is included and has the earliest start time of all included segments.

Then your final answer is going to be the maximum of value of $numsegs(i)$ for all possible values of $i$. Now you need a formula for $numsegs(i)$.

Think about how to calculate $numsegs(0)$, the maximum segment count when you include the first segment. If we include the first segment, then we can only include other segments that begin after the first segment ends. So we need to find the index of the first segment that is compatible with segment 0. We can do this in $O(\log n)$ time with a simple binary search - let that index be $k$. Now, we can say that $numsegs(0)$ is 1 (for segment 0) plus the maximum of $numsegs(k), numsegs(k+1), \dots, numsegs(n)$. (There's an edge case to consider as well. If segment $i$ doesn't have any compatible segments after it, then $numsegs(i)$ is just 1.)

You can compute $numsegs(i)$ in a very similar way. Note that $numsegs(i)$ depends only on $numsegs$ values greater than $i$. Therefore we can compute $numsegs(n-1)$ first, then $numsegs(n-2)$, and so on, caching the values as we go, and we'll never have to recalculate any $numsegs$ values.

This solution is actually $O(n^2)$. To compute $numsegs(i)$, you have to find the maximum among potentially $n-i$ following $numsegs$ values. How then to get the total runtime down to $O(n \log n)$?

**Edit:** As a linked solution pointed out, we can compute the maximum quickly using caching. Suppose we want to know the maximum $numsegs$ value starting from index $k$. We can just compare $numsegs(k)$ to the maximum starting from $numsegs(k+1)$, which we cached in a previous step.

---
Tags: algorithms, time-complexity, sorting, arrays, performance
---


# Question
Title: Most efficient way to check if key exist on a table
Imagine a person called Albert. Albert lives in Europe and would love to move to America. One day he got his wish come true. A person called Margareta gave him a key. The value of the key is the same as the address for a house in USA. Albert doesn't have that much money to travel to America to confirm whether the key is a hoax or not, by going to the address of the key. He certainly doesn't have the money for a house in America. If the key turns out to be a hoax, Albert would have a very hard time to make a living in America. It would cost him dearly. One day, a postman who knew all the addresses in America visited Europe. He happened to meet Albert.

Can the postman carry a certain information that is less than the information of all addresses in America to confirm whether Albert's key is valid or not? Then what is the information and what kind of operations is made to make the confirmation?

Assume all information is numeric here.

**Background:** I was looking at implementing a hash table for already known keys and I was wondering whether there exists efficient lookups where I don't have to visit a bucket in a hash table(America) to confirm whether a key exist or not.

# Answer
> 1 votes
Using Bloom filters you can store membership of $n$ elements using approximately $-1.44\cdot\log\_2(p)\cdot n$ bits, where $p$ is your probability of a false positive (it does not have false negatives).

This is assuming you have perfect independent hash functions (which is a reasonable enough assumption).

So if Albert wants an 0.1% chance of wasting his time the postman needs to carry $\approx 14.4$ bits of information per address, which is definitely less than the amount of bits to uniquely store an address.

---
Tags: hash, hash-tables
---


# Question
Title: Did Date and Darwen's "Third Manifesto" have a lasting impact?
In 1995, two DB theory researchers, C.J. Date and H. Darwen, published a text with the rather impressive-sounding name "The Third Manifesto" with their ideas regarding future DBMSes, which would better harmonize a relational model with object-oriented programming, including user-defined types.

It is my understanding that object-relational DBMSes has been mostly/entirely abandoned as a subject of research. So, has this manifesto had a significant impact on the DBMS world community over the past 23 years? If so, what are the salient aspects of this impact?

# Answer
> 3 votes
Hmm, before some moderator closes this q as being a matter of opinion, not substance ...

I think you need to consider whether the first two manifestos (to which TTM was a response) had any impact? I'd say little or no: there were a few OODB ideas that made it into the SQL standard (but were little implemented). There are a few niche commercial products that claim to be OODBMSs. But mostly the industry has stuck with SQL tables; and applications or development tools provide an ORM layer (Object-Relational Mapping).

A comparable question: have 'Codd's 12 Rules' had a significant impact on the DBMS world? I'd say not much, even though most industry practitioners would at least be aware of them.

Hugh Darwen, by the way, is not principally a "DB theory researcher". He was part of the UK development team for an early IBM relational system Business System 12 -- which arguably was more relational than SQL has ever achieved \[\**\]; and he was IBM's representative on the SQL standard committee for many years. He only lately moved into academe. His first draft of TTM was a visceral reaction against the fulminations of the SQL committee, written while he was at one of their plenaries.

Chris Date, IMO, is not much of a researcher either: he's more of an educator and writer of textbooks. I'm unconvinced he's added much to the research rigour of the TTM document.

Apart from that, your q seems to me to show many confusions.

If you read TTM (and the supporting explanations), I see no intent to "harmonise" with OOP. Note that an OODBMS is not aimed purely at OOP's: it's aiming to support notions of encapsulation of data. TTM's claim is that a Truly Relational DBMS already includes sufficient means to encapsulate data -- including under the Liskov/Wing Substitution Principle; and that SQL has bastardised the applicability of the Relational Model. Separation of concerns is principally to be achieved through schema design; we don't need perversion or subsumption of the Relational Model.

What has support for user-defined types got to do with it? Any modern language in any paradigm has those. The usual catchcry is 'types are orthogonal to the model'.

A large part of the TTM Prescriptions and Proscriptions are taken up not with opposing OODBMSs, but opposing SQL. Has TTM had a "significant impact" on SQL? I'd say no: SQL has continued to get worse and worse. Each revision of the standard has retained all the old awfulness (due to the shackle of backwards compatibility); has added new awfulness; and has multiplied up the effective awfulness in trying to support multiple 'features' that are in tension.

There are a few products that have attempted to implement TTM's ideas -- see "Projects" linked from the TTM website. I'd describe them as 'hobby products' developed and supported by individuals -- individuals who are rather cranky, strongly opinionated and difficult to deal with IMO. I would never recommend anybody use these products. (And for that reason, I'm not going to suggest you go ask your question at the TTM forum. You have been warned.)

\[\**\] The more I discover about BS12, the more impressed I am by how much it got right even when the Relational Model was very far from mature. How come it was killed off but SQL continued? IBM internal politics, plus commercial pressure: Larry Ellison stole some significant brainpower from the IBM System/R research team (who arguably never understood what Codd was talking about); they re-implemented at Oracle what had been only a prototype at IBM; then commercial pressure resulted in a race to get 'something' to market, and never mind the quality. Mike Stonebraker/Ingres did originally try harder to follow the model, but eventually had to cave to commercial pressure.

---
Tags: database-theory, databases, history, research
---


# Question
Title: CLRS pseudocode involving both subscripting and property access of a data structure
In Introduction to Algorithms, the stack data structure's enqueue operation has the following pseudocode

```
ENQUEUE(Q,x)
Q[Q.tail] = x
if Q.tail == Q.length
    Q.tail = 1
else Q.tail = Q.tail + 1

```

I started writing it in Swift and figured the queue should be modeled as a structure

```
struct IntQueue {
    var items = [Int]()
    var head = 0
    var tail = 0
}

func enqueue(queue: IntQueue, item: Int) {

}

```

to be able to access the `head` and `tail` properties. However, I'm not sure why the pseudocode subscripts `Q` directly. Is this shorthand for subscripting a queue's nested array property rather than the queue type itself?

# Answer
In pseudocode we can use whatever convention we want, as long as the reader understands what we mean.

That said, in languages like python and C++ you can actually define the subscript operator to access the underlying array, and for such languages the pseudocode could work literally.
> 1 votes

---
Tags: programming-languages, pseudocode
---


# Question
Title: Grid Based DP: How do we tweak the Travelling Salesman Problem to work with Grids
The question is:

> There is a n x n grid (Maze) which has either 0, 1 or 2. 0 means a path exists, 1 means the cell is blocked and 2 means there exists gold in that cell. Task is to start from 0, 0 and cover the grid such that all the gold is collected and then returned to a specific cell (x, y) in the grid. This task has to be done in the minimum number of steps.
>
> Example:
> Input: Maze = {0, 2, 0}, {0, 0, 1}, {1, 1, 1} and x = 1, y = 1 (return to this cell)
>
> Output: 1 as there is only 1 gold (in 1,1) and we are to return also in (1,1) so 1 move is what we need.

Reading the question, I can speculate that this is perhaps a variant of the traveling salesman problem but I cannot think of how I should be applying it here. Also, since in Travelling Salesman we return back to the source node and here we do not, I am having second thoughts if this has TSP like implementation. Any ideas?

# Answer
> 1 votes
Travelling Sales Man is NP-complete. This problem isn't, it has an easy polynomial time solution. Don't go there.

---
Tags: dynamic-programming, traveling-salesman, square-grid
---


# Question
Title: What if an $L$-complete problem has $NC^1$ circuits? More generally, what evidence is there against $NC^1=L$?
What if an $L$-complete problem has $NC^1$ circuits? More generally, what evidence is there against $NC^1=L$?

# Answer
> 0 votes
If an $L$-complete problem (under first-order projection, or $NC^0$-reduction) has $NC^1$ circuit, then we have $L=NC^1$.

The $NC^1$ circuit for an arbitrary language $\mathbb{L}\in L$ is obtained by first projecting (in case of first-order projection) or doing a constant-depth transformation (in case of $NC^0$-reduction) to obtain an instance of the $L$-complete problem. Then, plugin the $NC^1$ circuit for the complete problem to solve the original problem overall.

---
Tags: complexity-theory, logic, complexity-classes, space-complexity, circuits
---


# Question
Title: Is the union of 2 non context free languages always non context free?
Let $L\_1 = \\{a^nb^nc^n\\}$ and $L\_2 = \\{a^ib^jc^k \mid i\ne j\text{ or }j\ne k\\}$ (which I think is a non Context free but I am not sure)

So, $L\_1 \cup L\_2$ will give $L\_3 = \\{a^\*b^\*c^\*\\}$ which is a CFG.

Is this correct?

# Answer
As you suspected, the union of two non context-free languages may be context-free.

For example, $\\{a^nb^nc^n\mid n\ge0\\}\cup\\{a^nb^nc^m \mid m,n\ge 0,m\ne n\\,\\} = \\{a^nb^nc^m\mid m,n\ge0\\}$.

For a simpler example, $\\{a^{n^2}\mid n\ge 0\\}\cup\\{a^{m}\mid m \text { is not a square}\\} = \\{a^{n}\mid n\ge 0\\}$.

In fact, by a counting argument on countably infinity, for almost all languages $L$, both $L$ and its complement $\overline L=\Sigma^\*\setminus L$ are non context-free (and even non context-sensitive), where $\Sigma$ is the (nonempty) alphabet. Their union, $\Sigma^\*$ is context-free (and, actually, regular).

---

Your example is not correct since $L\_3\setminus L\_1 = \\{a^nb^mc^k\mid n,m,k\ge0, n\ne m\\}\cup \\{a^nb^mc^k\mid n,m,k\ge0, m\ne k\\}$ is a union of two context-free languages, hence also context-free.
> 2 votes

# Answer
Let $L$ be a non-context-free language over $\\{0,1\\}$. Then $0L \cup 1\Sigma^\*$ and $0\Sigma^\* \cup 1L$ are not context-free, but their union $\Sigma^+$ is context-free.
> 2 votes

# Answer
$\Sigma^\*$ is context free and its union with any language at all is $\Sigma^\*$, which is still context-free.

If you want to consider questions about closure properties of languages, always start with things like $\emptyset$ and $\Sigma^\*$, which are in any sane class of languages, and very often give give trivial counterexamples to false hypotheses about closure properties. For example, is the union of two non-regular languages always non-regular? No, because it's easy to come up with a language $L$ such that $L$ and $\overline{L}$ are non-regular, but we have $L\cup \overline{L}=\Sigma^\*$, which is regular. And, if you wanted intersection instead, $L\cap\overline{L}=\emptyset$ and that's regular, too.
> 0 votes

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


# Question
Title: Why is the total number of atoms in the observable universe often considered as an upper bound for computational feasibility?
There are many papers and textbooks in computer science that claim that computational problems are not feasibly computable (technically, not theoretically as with the halting problem) using a classical computer if the number of operations needed to be performed for solving them is exceeding the total number of atoms in the observable universe. \[\]

Now, it's pretty clear that in terms of space you have the total number of atoms in the observable universe as an upper bound, but how is it also an upper bound for computation time or number of instructions?

**Update**: A computer with memory of X bits can have a total of 2 to the power of X states, so in case X theoretically equals to the total number of atoms in the observable universe, the upper bound for computation time would actually be 2 to the power of the total number of atoms in the observable universe, which is a lot more than the total number of atoms in the observable universe. In fact, a computer can actually count the total number of atoms in the observable universe using only about 266 bits.

# Answer
> 3 votes
Let us assume an explicit range of the number of atoms in the universe to make sure that we are talking about the same thing. It is estimated that **there are between $10^{78}$ to $10^{82}$ atoms in the known, observable universe**. In other words, it is a number between ten quadrillion vigintillion and one-hundred thousand quadrillion vigintillion atoms.

## Is the number of atoms in the universe large enough?

The common unit of computing performance is one floating point operation per second (FLOPS, flops or flop/s).

* How much is the total computing capacity worldwide today? According to a popular estimate, "computing capacity worldwide was probably around 2 x $10^{20}$ – 1.5 x $10^{21}$ FLOPS, at around the end of 2015".
* Extrapolating that by a generous 50% yearly growth rate, the total computing capacity worldwide today, around the end of 2018 is less than 6 x $10^{21}$ FLOPS.
* Suppose you can run the total computing capacity worldwide today continuously for 100 billion years (which is much longer the life span of our universe as commonly estimated by physicists), you would have done a whopping 6 x $10^{21}$ (seconds) x 3.1536 x $10^{19}$ (Flop/s) $\approx$ 2 x $10^{41}$ FLOPs.
* Suppose everyone of about 7.6 billion people on the earth is enjoying the same computing journey and there are another 100 billion planets like earth, we would have done a total of 2 x $10^{41}$ x 7.6 x $10^9$ x $10^{14}$ $\approx$ 1.5 x $10^{65}$ FLOPs.
* However, that number is still much less than a billionth of the number of atoms in the universe! If each FLOP would count as 1, we need much more computing device and time to count the number of atoms in the universe!

Even given the impossibly optimistic yearly doubling of computing capacity worldwide, we would still need tens of years before our total computing ability to be anywhere near the number of the atoms in the universe.

## Why choosing the number of atoms in the universe?

As Rick Decker indicated in his comment, that number is about the easiest way to say a big but fathomable number just about right to convey the message of practical un-computability. The vivid image of an immensely large universe filled with one of the smallest particles brings immediate understanding of an otherwise unfathomably big number to all walks of people.

Another nice huge number, Google, $10^{100}$, is sort of void of concrete meaning.

## Further Topics

Which project is the largest computing project that has been completed or is going on?

Does FLOP capture all kinds of computing power? For example, quantum computing?

Why is the number of atoms is a really very small number compared to the number of combinations that we have to deal with routinely in many practical computations?

# Answer
> 1 votes
There are two physical bounds:

1. If you could implement a single bit of memory using one single atom (which we are nowhere near achieving), then total memory in the universe would be limited by the number of atoms in the universe, so we have a physical upper bound for the amount of state that a computation can ever have.
2. From quantum physics we know there is a minimum amount of energy required to make *any* change to any system. Take the total mass of the universe, apply $e = mc^2$, divide by the minimum amount of energy required for any state change, and you have an upper limit for the total number of state changes that a computation can ever have.

I can't think of any problem where the amount of state is a problem, but there are many especially cryptographical problems that cannot be solved due to the second restriction. And of course total mass of the universe is limited by number of atoms.

---
Tags: computability
---


# Question
Title: A data structure that makes finding close objects easy
I’m working on a project that involves a robot and a very large number of reference points. The robot moves around, while the reference points are fixed in space. I would like the robot to be able to tell which reference points are within a fixed distance of it at any point in time. This must be done in an online fashion. There are a very large number of reference points, so iterating through the list is impractical.

This is in many ways similar to a priority queue, but I don’t see any way to adopt that data structure to this context. Every move would require recalculating the distances which appears to require iterating over the entire list of reference points after every move.

Is there a data structure that works for this context? I can allow for a large amount of precomputation if necessary, though the robot’s path isn’t known in advance so I can’t precompute all the relevant distances or something like that. Iterating over the list of reference points can be done during precomputation, just not online because \[number of points\] * \[number of moves\] is too large. A solution that is linear in points and sublinear in moves may be feasible, but I would be highly surprised to learn it exists.

I would also be interested in a data structure that tracks the closest waypoint, if that is feasible but the general question is not.

# Answer
Data structures designed to organize multi-dimensional data can help, for instance quad trees or, more generally, k-d-trees.

It might also be possible to apply ideas from sweep-line algorithms, sweeping outwards radially from the current position of the robot.
> 2 votes

# Answer
You likely want to use some kind of spatial partitioning. Divide your space into, e.g., a square grid. Each grid cell stores a list of the reference points inside it. To get a list of points that are near your robot, then, you just iterate over all the points in the grid cell that contains the robot and any adjacent grid cells that are close enough to be at least partly inside the radius.
> 0 votes

---
Tags: algorithms, data-structures, nearest-neighbour
---


title: interval scheduling algorithm

text:
# Question
Title: interval scheduling algorithm
can any one explain why the greedy algorithm solution i.e sorting according to finishing time is optimal in the interval scheduling algorithm ?? I want proof in layman's language. I was watching this video and i am not able to understand the proof

# Answer
Algorithm - we will accept the request that finishes first. This is also quite a natural idea, we ensure that our resource becomes free as soon as possible.In this way we can maximize the time left to satisfy other requests.

let ***O*** is the set of optimal intervals and **A** is the set of intervals produced by our algorithm

formally: `Initially let **R** be the set of all requests, and let **A** be empty
 While R is not yet empty
 Choose a request i ∈ R that has the smallest finishing time
 Add request i to A
 Delete all requests from R that are not compatible with request i
 EndWhile
 Return the set A as the set of accepted requests`

Let **i1**,..., **ik** be the set of requests in A in the order they were added to A

similarly let **j1**,......**jm** be the set of requests in ***O*** in the order they were added to ***O***

we have to show that **k $=$ m** , that is both the set have same number of intervals

we want to show that our greedy rule “**stays ahead**” which means that each of its intervals finishes at least as soon as the corresponding interval in the set ***O***.

which means **f(ik) $\leq$ f(jK)**

here **f(ik)** denotes the finishing time of a interval **i**

this statement can easily be proved using induction. base case here is the very first interval which is **f(i1) $\leq$ f(j1)**

**Optimality** \- Now let's assume that **k \< m** which means there is a interval in ***O*** which is not selected by our algorithm

let the index of that interval is **k+1**

we know that **f(ik$+$1) $\leq$ f(jk$+$1)** **-** based on the statement we just proved

also **f(ik) $\leq$ f(ik$+$1)** and **f(jk) $\leq$ f(jk$+$1)** **-** As the intervals are ordered by their finishing time

clearly **jk$+$1** interval was available after **jk** finished but we know that **ik** finished before **jk**, so this means that an interval was available for selection after **ik** finished but our algorithm did not select it, but this can not happen as our algorithm will only stop when there are no intervals left.

so our assumption was wrong which means **k = m**

PS - I suggest reading the greedy algorithm section from the "Algorithm & Design" by Kleinberg and tardos

here is a link to a soft copy - http://www.cs.sjtu.edu.cn/~jiangli/teaching/CS222/files/materials/Algorithm%20Design.pdf
> 0 votes

---
Tags: algorithms, greedy-algorithms, intervals
---


# Question
Title: Proving a language is non-regular using the Pumping Lemma for non-binary strings
I am unsure of how to prove this language is non-regular. I do not even know where to start to develop a string that would prove the language is non-regular by contradiction. Any help would be appreciated.

I understand that the string has to have a length greater than the pumping length of L. What does that even mean in this context of such a vast alphabet?

I imagine I have to choose a string that fits the properties:

must be in the form of the expression a+b=c no leading zeros in a,b,c the expression on the left must equal the value on the right But I do not know what string would fit all these properties but also provides a contradiction in the proof.

My Attempt:

# Answer
You have demonstrated a pretty good understanding of the pumping lemma for regular languages. Your proof is clean and correct. (That mino typo, $xy^{iz}$ where $z$ should not be in the superscript, could be ignored by a human reader.)

Here is a minor suggestion. You can just use a specific string such as $1^p+2^p=3^p$, instead of a more general one $a^p+b^p=c^p$. Your proof will become easier to write and easier to understand.
> 0 votes

---
Tags: regular-languages, pumping-lemma, check-my-answer
---


# Question
Title: If a Triple Graph Grammar rule counts as a Mathematical Proof
I am intrigued by Triple Graph Grammars (TGG) as a potential for formal mathematical proof.

> Triple Graph Grammars (TGGs) are a technique for defining the correspondence between two different types of models in a declarative way.

In some systems, proofs are simply trees of rules being applied to transform one syntax tree of terms into another. *I don't really have a firm grasp of what that actually means in practice, but I think I understand the gist of it.* As such, a proof is a transformation of a into b, so a correspondence between two different models. Some sort of *isomorphism*.

The diagrams below show (roughly) that there are links between source and target objects, defining how to transform them (bijection). I'm wondering if a TGG rule has enough information in it to allow it to be considered a valid proof of a transformation of isomorphism. That is, *and I don't fully understand how to apply TGGs*, you define a TGG between two forms of an object (or more generally, between two objects), and that definition is equivalent to a formal proof of the isomorphism between the two objects. Wondering if this is true or if it is close to true. If close / along the lines of the right direction, wondering what it would require to make it into a valid proof.

To summarize, the questions are:

1. If a TGG counts as a valid proof of **transformation** (maybe of isomorphism) from $A \to B$.
2. If a TGG counts as a valid proof of transformation from $B \to A$.
3. If not, what would be required to make it into a valid proof.

---

Some more notes are:

> A triple graph $G =(G\_S \overset{s\_G}{\longleftarrow} G\_C \overset{t\_G}{\longrightarrow} G\_T)$ consists of three graphs $G\_S$, $G\_C$, and $G\_T$, called source, correspondence, and target graphs, together with two graph morphisms $s\_G : G\_C \to G\_S$ and $t\_G : G\_C \to G\_T$. A triple graph morphism $m = (m\_S, m\_C , m\_T) : G \to H$ consists of three graph morphisms $m\_S : G\_S \to H\_S$, $m\_C : G\_C \to H\_C$ and $m\_T : G\_T \to H\_T$ such that $m\_S \circ s\_G = s\_H \circ m\_C$ and $m\_T \circ t\_G = t\_H \circ m\_C$. A typed triple graph $G$ is typed over a triple graph $T\_G$ by a triple graph morphism $type\_G : G \to T\_G$. \[source\]

A function transforming A into B doesn't keep track of the actual individual steps between transformation, so the information is lost. But the TGG does. The only way to "prove" that A can be transformed to B with a function is to actually apply the function and compare the outputs. But with a mapping defined in a TGG, the "proof" would be the mapping itself, so you don't have to actually perform the transformation (or it seems). So given A and B and R (rule) in TGG context, R is the proof, we don't have to try converting A $\to$ B.

An example of this would be the transform between a parse tree and an abstract syntax tree. The parse tree let's say is the actual individual tokens organized into a tree of symbols and words, where every object in the tree is the same type of object (let's say a "parse node" object). The AST though is a tree of custom objects like "function node" and "variable node". So you convert the parse tree to the AST. How to prove that AST came from the parse tree. A function requires recomputing the output, maybe a TGG rule means it's automatically proven as a "derivation" of the parse tree.

Given I have parse tree A and AST B in memory, I would like to be able to say "A becomes B" without having to recompute it. I would like to say "B came from A" as well, which seems possible because of the bidirectional mapping of TGGs.

---

# Answer
A TGG defines (generates) a language of triples of graphs. This can be used for many things, including establishing a notion of correctness for forward and backward transformations. So if you have some transformation A -\> B, you can check if it is correct by checking if there exists some A \<-C-\>B that can be generated by the TGG.

Correct forward and backward transformations do not have to be bijections, although this could be enforced by analysing the TGG appropriately.

As a proof, one could use a TGG to generate proofs of consistency. So given some A and B, I can prove that A and B are consistent (and whatever produced B from A or A from B correct), by determining a rule application sequence that takes you from some start triple graph to some A\<-C-\>B.

So for your concrete syntax tree and AST you could check for consistency without recomputing the trees. In practice, however, such a consistency checker can actually be slower than a recomputation (but is sometimes still better, e.g., if the computation was non-deterministic or required some form of decision making).
> 2 votes

---
Tags: graphs, formal-grammars, proof-techniques, software-verification
---


# Question
Title: Subset sum exponential solution - how does the sorting work?
The wiki for the subset sum problem found here it states that you take the list of N elements and split it into two lists of N/2 elements. You then generate all the subsets for each list (each having $2^{N/2}$ subsets). It then states...

"Each of these two lists is then sorted. Using a standard comparison sorting algorithm for this step would take time $O(2^{N/2}N)$. However, given a sorted list of sums for k elements, the list can be expanded to two sorted lists with the introduction of a (k + 1)st element, and these two sorted lists can be merged in time $O(2^{k})$."

Can someone illustrate/explain this part of the algorithm?

# Answer
> 2 votes
The idea is that two sorted lists of length $n$ can be merged into one sorted list of length $2n$ in time $O(n)$. This is a standard procedure used in the mergesort algorithm. Given a list of integers $x\_1,\ldots,x\_m$, you proceed as follows:

* Start with $A\_0 = 0$.
* Merge $A\_0$ and $A\_0 + x\_1$ into $A\_1$.
* Merge $A\_1$ and $A\_1 + x\_2$ into $A\_2$.
* ...
* Merge $A\_{m-1}$ and $A\_{m-1} + x\_m$ into $A\_m$.
* Output $A\_m$.

Here $A\_k + x\_{k+1}$ is formed by adding $x\_{k+1}$ to all elements of $A\_k$, preserving the order.

Since $A\_k$ has length $2^k$, the total running time is $$ O(|A\_0| + |A\_1| + \cdots + |A\_{m-1}|) = O(1 + 2 + \cdots + 2^{m-1}) = O(2^m). $$

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


# Question
Title: Proving the equivalence of two definitions of NFA acceptance
> Recall that an NFA $N = (Q,\Sigma,\delta,S,F)$ accepts $w=w\_1w\_2\ldots w\_n$, where $w\_i \in \Sigma$, if one of the following holds:
>
> (a) $\hat\delta(S,w) \cap F \neq \emptyset$, where $\hat\delta\colon P(Q) \times \Sigma^\* \to P(Q)$ is given by $$ \hat\delta(Q',w) = \begin{cases} Q' & w = \epsilon \\ \bigcup\_{q \in \hat\delta(q',w\_1\ldots w\_{n-1})} \delta(q,w\_n) & |w| = n \> 0 \end{cases} $$
>
> (b) $\exists r\_0,\ldots,r\_n$, where $r\_i \in Q$, such that:
>
> * $r\_0 = q\_0$
> * $r\_n \in F$
> * $r\_{i+1} \in \delta(r\_i,w\_{i+1})$
>
> Show that (a) $\leftrightarrow$ (b)

I think I have proven from (b) to (a) but I'm not sure, and I seem to have no idea where to start the other way around. This is part of the first exercise in the computational models course I'm taking and I would really appreciate the help.

# Answer
> 2 votes
Just a hint:

* First, generalize the problem: show that, for any $q\in Q$ and any word $w$, $q \in\hat\delta(S,w)$ if and only if $\exists r\_0,...,r\_{|w|}\in Q$ such that $r\_0\in S$, $r\_{|w|}=q$, and $r\_{i+1}\in\delta(r\_i, w\_{i+1})$.
* Second, show this statement by induction on the length $|w|$ of $w$. This is trivial for the base case, and should be easy for the inductive case, just apply the induction hypothesis and the definition of $\hat\delta$.
* Finally, show that your equivalence follows from the general statement: apply it for any $q\in F$.

---
Tags: finite-automata, computation-models
---


# Question
Title: Time complexity of a language whose alphabet has a single symbol
Consider a language $L$ such that $L \subseteq \Sigma^\*$, where the cardinality of $\Sigma$ is $1$ (i.e. the alphabet has only one symbol). E.g. $L \subseteq \\{a\\}^\*$.

Can anything be said about the time complexity of $L$? Is it the case that $L \in P$?

I can't come up with any example of a language with a single symbol that is not in $P$.

# Answer
The language $\\{a^n : \text{ the $n$th Turing machine halts on the empty string} \\}$ is undecidable.

In fact, a random unary language is undecidable almost surely, for the simple reason that there are only countably many computable languages.
> 4 votes

---
Tags: time-complexity, decision-problem
---


title: A problem on constrained combinatorics

text:
# Question
Title: A problem on constrained combinatorics
Not sure if this is a proper place, but I really don't know where else to ask. I'm craving for an algorithm generating certain sequences of numbers (the problem comes from physics).

I'm looking for all such sequences of $a\_n$ an $b\_n$ that: $$ \begin{cases} \sum \limits\_{n=1}^{K} (n a\_n) + \sum \limits\_{m=1}^{K} (m b\_m) = K\\ \sum \limits\_{n=1}^{K} a\_n - \sum \limits\_{m=1}^{K} b\_m = Q\\ \end{cases} \quad,\quad \text{where}\qquad \begin{cases} K\in\mathbb{Z}^+\\ Q\in\mathbb{Z}\\ a\_n,b\_m= \\{0,1\\} \end{cases} $$

For my application, I am interested in finding all such sequences starting from $K=Q(\operatorname{mod}2)$ and up to some large value of $K$, so, I guess, it would make sense to solve the problem iteratively. I would really appreciate if someone could up with an efficient solution.

EXAMPLE

For $Q=0$, $K=2$ the only option is $a\_1=b\_2=1$. We shall write it as $\\{\\{1\\},\\{1\\}\\}$. The first sublist corresponds to $a$'s, the second $-$ to $b$'s. The $j$th position in the sublist denotes the value of $a\_j$ or $b\_j$.

For $Q=0$, $K=4$, the possible sets are: $\\{a\_3=1;b\_1=1\\}$, $\\{a\_1=1;b\_3=1\\}$, $\\{a\_2=1;b\_2=1\\}$, with all other coefficients vanishing.

Here's an example of the output: \begin{alignat}{9} &Q=0,K=2:\quad &&\\{\\{\\{1\\},\\{1\\}\\}\\}\\ &Q=0,K=4:\quad &&\\{\\{\\{0,0,1\\},\\{1\\}\\},\\{\\{1\\},\\{0,0,1\\}\\},\\{\\{0,1\\},\\{0,1\\}\\}\\} \\\&...&& \end{alignat}

Where I omitted the vanishing elements following the last non-zero element.

P.S.

The particular form of the output is not important for me. I would be equally happy to get it, say, in the form of lists of numbers of non-vanishing elements: \begin{alignat}{9} &Q=0,K=2:\quad &&\\{\\{\\{1\\},\\{1\\}\\}\\}\\ &Q=0,K=4:\quad &&\\{\\{\\{3\\},\\{1\\}\\},\\{\\{1\\},\\{3\\}\\},\\{\\{2\\},\\{2\\}\\}\\} \\\&...&& \end{alignat}

**UPDATE**

1. By *efficient* algorithm I mean the one which does not make any useless steps (like "going though all possible sequences and throwing away the ones which do not work"). Yes, the algorithm will work in exponential time, and there's nothing we can do about it.
2. I think, a friend of mine came up with a solution.

At the first step, we generate the table having $K$ rows which contains all the partitions of $k=1..K$ into $m$ different terms:

$$ \begin{pmatrix} \\{1\\} & & \\ \\{2\\} & & \\ \\{3\\} & \\{1,2\\} &\\ \\{4\\} & \\{1,3\\} &\\ \\{5\\} & \\{1,4\\},\\{2,3\\} &\\ \\{6\\} & \\{1,5\\},\\{2,4\\},\\{3,3\\} & \\{1,2,3\\} \end{pmatrix} $$

Then, we consider all the possible ways to split $K=K\_1+K\_2$. For each pair $\\{K\_1,K\_2\\}$, we consider partitions of $K\_1$ and $K\_2$ having $n\_1$ and $n\_2$ elements, correspondingly. Of those, we are interested only in such that $n\_1-n\_2 = Q$.

I'm wondering if anyone could help with writing the pseudocode for this solution? I'm too stupid to deal with all the For's... I feel like it should look smth like this:

```
for (all partitions of K into K1 and K2)
    for (all lengths of partitions of K1)
        for (all partitions of K1 of given length)
            for (all partitions of K2 having the length (Q-current length of K1 partition) )
                take the current partitions!
            end
        end
    end
end

```

**MOTIVATION**

For the curious ones: the problem is motivated by representing the fermionic part of the system considered in this paper, see eq. (3.5).

In two dimensions, the state of the system containing fermions and neutral bosons is described by a list of numbers saying how many particles of each sort with given momentum we have: $$ |n\_1,n\_2,\ldots,n\_N; \overline{n}\_1,\overline{n}\_2,\ldots,\overline{n}\_{\overline{N}}; \widetilde{n}\_1^{\widetilde{m}\_1},\widetilde{n}\_2^{\widetilde{m}\_2},\ldots,\widetilde{n}\_{\widetilde{N}}^{\widetilde{m}\_{\widetilde{N}}}\rangle $$ Here $n\_k$ is the number of fermions with momentum $k$, $\overline{n}\_k$ is the number of anti-fermions with momentum $k$. Both can be either $0$ or $1$, due to the Pauli exclusion principle (or, better say, due to the spin-statistics theorem). As for bosons of each momentum, we can have an arbitrary number of those. The momenta are discretized due to the fact that the system is considered on a finite interval of space (much like in the case of the Fourier series). The momenta are positive because we are in the light-cone coordinates: if you are an observer is flying to the left with the speed of light, all the massive particles seem for you to be right-movers. We are interested in finding all the states with a given charge (the difference between the numbers of fermions and anti-fermions) and total momentum (the sum of momenta of all the particles in the state).

The first step is trivial, the total momentum can be separated into momenta of the bosonic and fermionic parts. Here I only asked about the latter, since the former is trivially given by all possible partitions of an integer.

# Answer
> 1 votes
In the following code I solve your problem. In the following code ba is the concatenation of binary vector b and $\alpha$ each one of them is of size K. So ba has length 2K. So vector a occupies the K least significant bits of ba and b occupies the most significant bits of b.

You can imagine the flow of the program as considering every possibility (0 or 1) for every bit starting from the least significant bit. If you are familiar with trees in cs I search the entire possible space in an preorder tree walk and I stop searching further the space under some certain conditions. These are:

1. In every level (n) down the tree I calculate maximum sum of remaining bits, if all of them are to be included, this maximum sum I call it rest. If sum+rest \< K then there are not enough a or b occurrences left so the sum will ever be K so there is no point to continue further searching.
2. Since n\_a - n\_b = Q there are must be at least Q occurrences of $\alpha$ terms in the partition. In other words a vector must have at least Q bits set. So n\_a is currently the bits set in $\alpha$ and K-n are the remaining maximum possible set bits. So if maximum remaining bits + n\_a aren't enough to reach Q (that is if K-n + n\_a
3. In a similar manner if the remaining occurrences of 'b' terms which are at most 2\*K-n (when n \> K) aren't enough to boost b\_a such that n\_a - n\_b be exactly Q there is no point to traverse the tree downwards further.
4. And of course if at some point I hit the exactly sum ==K with n\_a-n\_b ==Q there is no point to continue further, as by doing so the remaining partitions might exceed the already achieved sum and Q.

\>

```
#include <stdio.h>
#include <stdlib.h>

//Bad!! global variables
const int K = 50;
const int Q = 4;

void proc(int current_sum, int rest, int current_n_a, int current_n_b, int* ba, int n, int value);
void print_partition(int* ba);

int main(int argc, char const *argv[])
{
    int *ba;
    int rest;
    ba = calloc(2*K, sizeof(int));

    rest = 2 * (K/2 * (K+1)); //initialize to maximum possible sum if ba={1,1,1,1,1,1,1,1,...}
    proc(0, rest, 0, 0, ba, 1, 0);
    proc(0, rest, 0, 0, ba, 1, 1);
    return 0;
}

void proc(int current_sum, int rest, int current_n_a, int current_n_b, int* ba, int n, int value){
    int sum, n_a, n_b;
    ba[n-1] = value;
    n_a = current_n_a;
    n_b = current_n_b;
    if (n <= K){
        sum = current_sum + n*value;
        rest -= n;
        if (value){
            n_a = current_n_a + 1;
        }
    }else{
        sum = current_sum + (n-K)*value;
        rest -= (n-K);
        if (value){
            n_b = current_n_b + 1;
        }
    }

    if ((sum == K) && (n_a - n_b == Q)){
         print_partition(ba);   //we are done here
    }else{
        if ( (n < 2*K) && (sum < K) && (sum + rest >= K) ){ //backtracking conditions
            if ( (n <= K) && ( (K-n + n_a) >= Q ) /**/){ //ensure that there are enough occurences of a's left  so there are at least Q a's
                //recurse
                proc(sum, rest, n_a, n_b, ba, n+1, 0);
                proc(sum, rest, n_a, n_b, ba, n+1, 1);
            }
            if ( (n > K) && ((n_a - (2*K-n + n_b)) <= Q) /**/) { //ensure that there are enough possible occurences of b's left so n_b can be high enough in order n_a - n_b = Q
                //recurse
                proc(sum, rest, n_a, n_b, ba, n+1, 0);
                proc(sum, rest, n_a, n_b, ba, n+1, 1);
            }
        }
    }
    ba[n-1] = 0; //reset value for the calling function
}

void print_partition(int *ba){
    static int count = 1;
    int i;
    printf("#:%d    ", count);
    printf("{");
    printf("a:{");
    for (i = 0; i < K; i++){
        if (ba[i]){
            printf("%d,", i+1);
        }
    }
    printf("}b:{");
    for (i = 0; i < K; i++){
        if (ba[K+i]){
            printf("%d,", i+1);
        }
    }
    printf("}}\n");
    count++;

}

```

This code is what I would say a quick 'n' dirty solution. Sure there are ways to improve this code removing global variables, and improve the clarity of this code, anyone feel free to edit my answer for better code-clarity performance etc.

# Answer
> 2 votes
Rephrasing, $$A, B \subseteq \\{1, 2, \ldots, K\\} \\ \sum\_{a \in A}a + \sum\_{b \in B}b = K \\ |A| - |B| = Q$$

So as your friend suggests, this can be tackled by looking at partitions of an integer into a given number of distinct parts.

```
for K1 = 0 to K:
    for N1 = 0 to K1:
        for A in distinct_partitions(K1, N1):
            for B in distinct_partitions(K - K1, N1 - Q):
                process(A, B)

```

The easiest way to generate all partitions of an integer is a recursion with a second parameter: the largest part. Similarly, the easiest way to generate all partitions of an integer into a given number of distinct parts is a recursion with a third parameter: the largest part.

```
distinct_partitions(n, k):
    # Special case
    if n == 0 and k == 0:
        yield []

    for m = 1 to n:
        yield from distinct_partitions_inner(n, k, m)

distinct_partitions_inner(n, k, m):
    # Base case
    if k == 1:
        if n == m:
            yield [n]
        return

    # Parts are distinct, positive, and no greater than m
    if k > m:
        return

    # The smallest possible partition is 1+2+...+(k-1)+m
    if n < m + (k-1) * k / 2:
        return

    # The largest possible partition is m + (m-1) + ... + (m-k+1)
    if n > m * k - (k-1) * k / 2:
        return

    # m is the largest part, so we have n-m left to assign to smaller parts
    for i = 1 to m-1:
        for subpartition in distinct_partitions_inner(n-m, k-1, i):
            yield [m] + subpartition

```

The early aborts can be adjusted according to aesthetics to try to abort one level up the call stack.

---

Note that the table of the number of Fock states given in the Pauli and Brodsky paper you link contains a few errors. I derived their generating function and generated some data using the following Python code:

```
import math

def convolveP(a):
    ''' Convolves a generating function with the g.f. of the partition numbers '''
    for n in range(0, len(a)):
        for j in range(int((math.sqrt(1 + 24*n) + 1) / 6)):
            t = 1 + j * (3*j + 5) // 2
            a[n] += (-1)**j * a[n - t]
            if t + j < n:
                a[n] += (-1)**j * a[n - t - j - 1]
    return a

def fock(Q, n):
    triangles = [0] * n
    for j in range(int((math.sqrt(1 + 8*n) - 2*Q + 1) / 2)):
        triangles[(Q+j) * (Q+j+1) // 2] = (-1) ** j
    fermionic = convolveP(triangles)
    return convolveP(fermionic)

for Q in range(0, 5):
    print(fock(Q, 20))

```

This gave enough terms to find the sequences for the first four values of $Q$ in the Online Encyclopedia of Integer Sequences:

* $Q=0$: A006330
* $Q=1$: A001523 (correcting $a(0)$ to $0$: see comment by Michael Somos)
* $Q=2$: A288578, offset so that the first non-zero term is at $K=3$
* $Q=3$: A288579, offset so that the first non-zero term is at $K=6$

All four of those reference this paper, section 2.1, which gives some similar g.f.s (offset by a power of $q$) and a combinatorial explanation. I find that the explanation doesn't match up, but if I figure out the discrepancy and a suitable bijection to extract the partitions for fermions, antifermions, and bosons then I'll edit, because that might give a more economical generation procedure.

---
Tags: algorithms, combinatorics, integer-partitions
---


# Question
Title: Help writing a dynamic programming algorithm in English
It’s Friday night and you have $n$ parties to go to. Party $i$ has a start time $s\_i$ end time $t\_i$ and a value $v\_i \ge 0$. Think of the value as an indicator of how excited you are about that party. You want to pick a subset of the parties to attend so that you get maximum total value. The only constraint is that in order to get a value $v\_i$ from party $i$ you need to attend the party from start to finish. Hence you cannot drop in midway and leave before the party ends. This means that if two parties overlap, you can only attend one of them. For example, if party 1 has a start time of 7pm and ends at 9pm and party 2 starts at 7:30pm and ends at 10pm, you can only attend one of them. On the other hand, if party 2 starts at 9pm or later then you can attend both. Given as input start times, end times and values of each of the n parties, design an $O(n \log n)$ time algorithm to plan your night optimally. Describe in English the idea of your algorithm. If you use dynamic programming define the memo table, base case and recursive steps. You don’t need to write the pseudo code or provide a proof of correctness.

I am having difficulty beginning this problem. My initial thought was to have the base case be to choose the value with the initial start time and the greatest $v\_i$, however if party $i$ runs for your entire start to end time, you might not maximize $v\_i$. I would greatly appreciate some insight into how to do this problem.

# Answer
> 0 votes
Since this problem is a learning exercise of yours, I will just write the ordered subproblems used in dynamic programming. In general, I consider it is about more than half way through a nontrivial problem that can be solved by dynamic programming when the ordered subproblems have been specified clearly, at least in term of "difficult" thinking since the rest are more routine.

The subproblems are computing $v\[i\]$, the maximal total value you can get when you just finished party $P\_i$. To help computing these subproblems, that is, from earlier subproblems to later subproblems, you may sort the parties by their ending times so that $P\_1,P\_2,\cdots,P\_n$ end in order of time. After the sorting, $v\[i\]$ will only depend on those $v\[j\]$ where $j\<i$ or, to be more precise, those $P\_j$ whose ending time is before $P\_i$'s starting time. (This condition can be made even more restrictive, which may be unnecessary for your exercise and which may be necessary to get a better grade.) There are several more details such as the base case and the recurrence relation, which I will leave for you to fill in.

---
Tags: algorithms, dynamic-programming, knapsack-problems, pseudocode
---


# Question
Title: Is my decomposition of R into 3NF is lossless and preserving all dependencies?
I have a schema R = {A,B,C,D,E} and the set F of FDs:

F = {A --\> BCDE, CD --\> E, EC --\> B}.

Candidate key = A Non - Prime Attributes = BCDE Prime Attributes = A

According to me, there is no partial dependency because no non-prime attribute is dependent on part of CK.

E and B are transitively dependent on A so the schema Ris not in 3NF.

Decomposing R into 3NF, I have three relations and three set of FDs :

```
R1(A,B,C,D)                         F1={A --> B,A --> C,A --> D}
R2(C,D,E)                           F2={CD --> E}
R3(E,C,B)                           F3={EC --> B}

```

My question is, Is my decomposition of R into 3NF is lossless and preserving all dependencies or not? And if not how can I decompose it into 3NF losslessly while preserving all dependencies.

# Answer
So My decomposition is lossless and preserving all dependencies but there is no need for relation R3(E, C, B) because we already have A which can derive B in R1.
> 0 votes

---
Tags: database-theory, databases
---


title: What is an IELR(1)-parser?

text:
# Question
Title: What is an IELR(1)-parser?
I try to teach myself the usage of bison. The manpage bison(1) says about bison:

> Generate a deterministic LR or generalized LR (GLR) parser employing LALR(1), IELR(1), or canonical LR(1) parser tables.

What is an IELR-parser? All relevant articles I found on the world wide web are paywalled.

# Answer
> 9 votes
# The IELR(1) Parsing Algorithm

The IELR(1) parsing algorithm was developed in 2008 by Joel E. Denny as part of his Ph.D. research under the supervision of Brian A. Malloy at Clemson University. The IELR(1) algorithm is a variation of the so-called "minimal" LR(1) algorithm developed by David Pager in 1977, which itself is a variation of the LR(k) parsing algorithm invented by Donald Knuth in 1965. The IE in IELR(1) stands for inadequacy elimination (see last section).

## LR(1) Algorithms

The LR(1) part of IELR(1) stands for **L**eft to right, **R**ightmost derivation with 1 lookahead token. LR(1) parsers are also called canonical parsers. This class of parsing algorithms employs a bottom-up, shift-reduce parsing strategy with a stack and state transition table determining the next action to take during parsing.

Historically, LR(1) algorithms have been disadvantaged by large memory requirements for their transition tables. Pager's improvement was to develop a method of combining the transition states when the transition table is generated, significantly reducing the size of the table. Thus Pager's algorithm makes LR(1) parsers competitive with other parsing strategies with respect to space and time efficiency. The phrase "minimal LR(1) parser" refers to the minimal size of the transition table introduced by Pager's algorithm.

## Limitations of Pager's Algorithm

Minimal LR(1) algorithms produce the transition table based on a particular input grammar for the language to be parsed. Different grammars can produce the same language. Indeed, it is possible for a non-LR(1) grammar to produce an LR(1) parsable language. In practice, LR(1) parser generators accept non-LR(1) grammars with a specification for resolving conflicts between two possible state transitions ("shift-reduce conflicts") to accommodate this fact. Denny and Malloy found that Pager's algorithm fails to generate parsers powerful enough to parse LR(1) languages when provided certain non-LR(1) grammars even though the non-LR(1) grammar generates an LR(1) language.

Denny and Malloy show that this limitation is not merely academic by demonstrating that Gawk and Gpic, both widely used, mature software, perform incorrect parser actions.

## IELR(1)'s Improvements

Denny and Malloy studied the source of the deficiencies of Pager's algorithm by comparing the transition table generated by Pager's algorithm to the transition table of an equivalent LR(1) grammar and identified two sources of what they term *inadequacies* that appear in the transition table from Pager's algorithm but not in the LR(1) transition table. Denny and Malloy's IELR(1) (*Inadequacy Elimination* LR(1)) algorithm is an algorithm designed to *eliminate* these *inadequacies* when generating the transition table that is virtually identical in size to that of Pager's algorithm.

# Answer
> 6 votes
An article that claims to introduce it: IELR(1): Practical LR(1) Parser Tables for Non-LR(1) Grammars with Conflict Resolution (via archive.org) by Joel E. Denny and Brian A. Malloy, Clemson University, is freely available from Malloy's site.

What they are worth is something I can't answer. (Personally I don't understand the need for such crippled CFG parsing - why limit your expressive power when you can just use GLR? What does make sense to me is something like TAG or PEG (they seem natural and add expressive power) or tree grammars (for languages such as XML, in which recognizing parse trees is unproblematic by design.)

---
Tags: formal-languages, terminology, formal-grammars, parsers
---


# Question
Title: Computational complexity of maximizing sum of rational functions
I have a optimization problem:

$$\max\_z\ \sum\_{i=1}^n \frac{W\_i}{D\_i - z\_i} \quad \text{s.t.}\ \sum\_{i=1}^n z\_i \leq k, z\_i \in \[0,k\],$$ where each $W\_i$, $D\_i$ are constants and $z\_i$ are integer variables. Assume each $D\_i \>k$.

The optimal solution obviously satisfies $\sum\_{i=1}^n z\_i =k$. But it seems there is no efficient way to get the optimum other than trying out all partitions.

Also, I know the above problem can be formulated as linear integer programming.

Is there any hint of proving the hardness of the above problem?

# Answer
> 1 votes
Your problem can be solved in polynomial time.

Suppose $n-2$ variables (without loss of generality, say $z\_3,\ldots,z\_n$) are fixed, then the objective becomes maximizing $$\frac{W\_1}{D\_1-z\_1}+\frac{W\_2}{D\_2-z\_2}$$ where $z\_1+z\_2\le k-(z\_3+\cdots+z\_n):=K$. Let $$f(z)=\frac{W\_1}{D\_1-z}+\frac{W\_2}{D\_2-(K-z)}, 0\le z\le K,$$ then $$f''(z)=\frac{2W\_1}{(D\_1-z)^3}+\frac{2W\_2}{(D\_2-K+z)^3}\ge0,$$ which means $f(z)$ is convex on $\[0,K\]$, thus the maximum value is achieved at either $z=0$ or $z=K$. This suggests that we can adjust an optimal solution such that either $z\_1=0$ or $z\_2=0$.

We can repeat this adjustment until there are only one non-zero variable among $z\_1,\ldots,z\_n$. So to solve your primary problem, just try the solutions $(k,0,\ldots,0),(0,k,\ldots,0),\ldots,(0,\ldots,0,k)$ and choose the optimal one among them.

---
Tags: algorithms, complexity-theory, optimization, np-hard, integer-programming
---


title: Analog circuits for neural networks?

text:
# Question
Title: Analog circuits for neural networks?
Neural networks in machine learning are inherently a continuous model of computation. Yet we use digital logic circuits with floating point numbers to "emulate" this continuity.

I am wondering: is there a possiblity to develop an analog-based ASIC for neural networks, which might fit them well due to their inherent continuity. Neural networks are relatively robust to errors anyway, so the error-proneness of analog circuits shouldn't be a problem.

# Answer
> Is there a possibility to develop an analog-based ASIC for neural networks?

**This had been already implemented a long time ago.**

I guess, no one ever seriously supposes that this is impossible. There're many implementations in papers since 70th. They're still not of industry-standard quality, and with some limitations. However, they're real prototypes among them.

> error-proneness of analog circuits shouldn't be a problem

**Unfortunately, it's and it's just one of a bunch of issues.**

A general view of this field. Analog ASICs is one of the existed hardware bases for implementing neural networks along with digital ASICs, FPGAs, custom on-chip implementations, massive-parallel computers, general-purpose CPUs and GPUs. Moreover, it's not the most popular approach, currently, because of its limitations in precision and storing data overhead. Also, the analog computations aren't the mainstream, so, there's a lack of development and specialists. Analog computational elements are a kind of different world with specific problems for engineers. Hence, their cost-efficient parameters are far behind even common general purpose CPUs and they are in a narrow use.

However, the analog ASICs have positive sides - yes, on a hardware components level, they are immensely close to the neural networks (biological) which have deeper parallelism than mainstream implementations.

A lot of references for further reading can be found here: *Omondi, Amos R., eds. FPGA implementations of neural networks. Vol. 365., Springer, 2006.*
> 1 votes

---
Tags: neural-networks, digital-circuits, neural-computing
---


# Question
Title: How are the prime numbers encoded in Knuth's example of fitting primes into memory cache?
Could somebody please help me understand what is going on here (in plain English)? I think that $(k \mathbin{\\&} 63)$ has the effect of modular division. Is that right? How are the primes encoded / how can I know exactly where a number starts and ends by moving my finger across each 64-bit word?

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, ...

---

> \[The goal is to make\] a table of all odd prime numbers less than 1024, so that we can easily decide the primality of a small integer.

1. The ultimate package density is achieved when we have 1-bit items.
2. We can cram them into a 64-bit word.
3. Only 64-bit numbers are required.
4. To test whether $2k+1$ is prime, for $0 ≤ k \< 512$, simply compute the following in a 64-bit register, and see if the leftmost bit is 1:

$$P\_{\lfloor k/64\rfloor} \<\< (k \mathbin{\\&} 63)$$

P is in big-endian format. Q is in little-endian format.

> ```
> P0 —0111011011010011001011010010011001011001010010001011011010000001,
> P1 —0100110000110010010100100110000110110000010000010110100110000100,
> P2 -1001001100101100001000000101101000000100100001101001000100100101,
> P3 -0010001010001000011000011001010010001011010000010001010001010010,
> P4 —0000110000000010010000100100110010000100100110010010110000010000,
> P5 -1101001001100000101001000100001000100001000100100101000100101000,
> P6 —1010000001000010000011000011011000010000001011010000001011010000,
> P7 -0000010100010000100010100100100000010100100100010010000010100110.
>
> ```

For little-endian, $$Q\_{\lfloor k/64\rfloor} \>\> (k \mathbin{\\&} 63) $$

and look at the rightmost bit of the result.

> ```
> Q0 — 1000000101101101000100101001101001100100101101001100101101101110,
> Q1 - 0010000110010110100000100000110110000110010010100100110000110010,
> Q2 - 1010010010001001011000010010000001011010000001000011010011001001,
> Q3 - 0100101000101000100000101101000100101001100001100001000101000100,
> Q4 — 0000100000110100100110010010000100110010010000100100000000110000,
> Q5 — 0001010010001010010010001000010001000010001001010000011001001011,
> Q6 — 0000101101000000101101000000100001101100001100000100001000000101,
> Q7 — 0110010100000100100010010010100000010010010100010000100010100000;
>
> ```

– The Art of Computer Programming. Volume 4, Fascicle 1. Bitwise Tricks and Techniques. Binary Decision Diagrams. p.5

# Answer
> 2 votes
> P is in big-endian format.
> P0 —0111011011010011001011010010011001011001010010001011011010000001,

The first bit, 0, means 2\*0 + 1 = 1 is not a prime.
The second bit, 1, means 2\*1 + 1 = 3 is a prime.
The third bit, 1, means 2\*2 + 1 = 5 is a prime.
The fourth bit, 1, means 2\*3 + 1 = 7 is a prime.
The fifth bit, 0, means 2\*4 + 1 = 9 is not a prime.
The sixth bit, 1, means 2\*5 + 1 = 11 is a prime.
The seventh bit, 1, means 2\*6 + 1 = 13 is a prime.
The eighth bit, 0, means 2\*7 + 1 = 15 is not a prime.
The ninth bit, 1, means 2\*8 + 1 = 17 is a prime.
And so on.

> P1 —0100110000110010010100100110000110110000010000010110100110000100,

The first bit, 0, means 2\*64 + 1 = 129 is not a prime.
The second bit, 1, means 2\*65 + 1 = 131 is a prime.
The third bit, 0, means 2\*66 + 1 = 133 is not a prime.
The fourth bit, 0, means 2\*67 + 1 = 135 is not a prime.
The fifth bit, 1, means 2\*68 + 1 = 137 is a prime.
The sixth bit, 1, means 2\*69 + 1 = 139 is a prime.
The seventh bit, 0, means 2\*70 + 1 = 141 is not a prime.
The eighth bit, 0, means 2\*71 + 1 = 143 is not a prime.
The ninth bit, 0, means 2\*72 + 1 = 145 is not a prime.
And so on.

> P2 -1001001100101100001000000101101000000100100001101001000100100101,

The first bit, 1, means 2\*128 + 1 = 257 is a prime.
And so on.

> P3 -0010001010001000011000011001010010001011010000010001010001010010,

The first bit, 0, means 2\*192 + 1 = 385 is not a prime.
And so on.

And so on.

> P7 -0000010100010000100010100100100000010100100100010010000010100110.

The first bit, 0, means 2\*448 + 1 = 897 is not a prime.
And so on.
The last bit, 0, means 2\*511+1 = 1023 is not a prime.

> Could somebody please help me understand what is going on here (in plain English)? I think that (k&63) has the effect of modular division. Is that right? How are the primes encoded / how can I know exactly where a number starts and ends by moving my finger across each 64-bit word?

If you have read the above explanation for many bits in P0, P1, ..., P7, the answer to your questions should be obvious now. For a number $2k+1$, $\lfloor k/64\rfloor$, the quotient of $k$ divided by 64, is which $P$ should be used. $k \mathbin{\\&} 63$, the remainder of $k$ divided by 64 is how many bits you should move to the right to find its primeness-indicator bit.

---
Tags: packing, bit-manipulation
---


# Question
Title: How hard can identifying non-membership in a semi-decidable language be?
A language is called semi-decidable if there is an algorithm for identifying members. There are well-known examples of semi-decidable languages where identifying non-members is equivalent to $\emptyset'$, such as the Halting Problem.

My question is: how hard can identifying non-membership be?

# Answer
> 1 votes
A language $L$ is semidecidable if there exists a computable predicate $f$ such that $$ x \in L \Leftrightarrow \exists y \\, f(x,y). $$ We can construct a machine $M$ which halts on $x$ iff $\exists y \\, f(x,y)$: the machine just goes over all possible $y$, for each one checks whether $f(x,y)$, and if so, halts. This shows that we can decide $L$ using an oracle to the halting problem, i.e., using an $\emptyset'$-machine.

---
Tags: computability, undecidability
---


# Question
Title: How to decompose into BCNF while preserving all functional dependencies
I have a relation R = {A,B,C} and F={AB -\> C , C -\> B}. In order to check if R is in BCNF.

I checked if AB and C are both superkeys and since C is not a superkey I conclude R is not in BCNF.

After decomposing R into BCNF, I have two relations :

```
R1(C,B)   F1{ C -> B}
R2(A,C)   F2{ A -> C}

```

Now since A and C are both superkeys, I can conclude that now R(R1, R2) is in BCNF.

But after computing (F1 U F2)+, I can't derive AB -\> C and so I lose that FD.

My question is, how can I decompose than into BCNF while preserving FD's?

# Answer
> 0 votes
this very example is discussed in the first place I looked.

The short answer is that you cannot always achieve all of

* BCNF;
* an information-equivalent schema;
* using keys as the only declared constraint(s).

Pick any two.

In this case you must retain `R = {A, B, C}`, with key `{A, B}` -- then we can't losslessly decompose `R`. In order to represent the FD `C -> B` as a relation with a suitable key, you need `R1 = {C, B}` with key `{C}`. So far we've achieved BCNF. To retain information equivalence, you need an Inclusion Dependency (aka Foreign Key constraint) `R[C] ⊆ R1[C]`.

Strictly speaking to retain info equivalence, that Inclusion Dependency should probably be an Equality Dependency. But this is a contrived example, so nobody in practice would do that.

---
Tags: database-theory, databases
---


# Question
Title: Distribute to pairs with efficient algorithms
The task is to find a efficient algorithm to the following problem. There are n boys and n girls who need to be divided to pairs. You get a list with all possible pairs that could be made. It means that if the pair (a,b) is in the list then the boy a can be paired with the girls b.

It is known that each boy appears in exactly two pairs, and each girls appears exactly in two pairs. I need to find an algorithm which will find me a proper division to pairs.

My idea was to define a graph. The vertices will be the n boys and the n girls. The edge (a,b) Will be in the graph if the pair (a,b) is the list of possible pairings.

Because each boy and girl appear in exactly two pairs, then each vertex in the graph will be of degree 2. So every vertex in the graph will be of an even degree.

A connected graph with vertices that are only of even degree has an euler cycle. That way, each connected component in the graph I built will have such a circle.

For each component we fake the circle, with a boy being the starting vertex, and then we erase the last edge in the cycle. Then I define the pairing like this: a boy will be paired with the girl in front of him in the cycle, and the opposite for girls.

This will give me the needed division. Is it good enough?

# Answer
> 1 votes
Yes, that works, but I would skip making/faking Eulerian cycles and just execute your idea directly:

1. If the list is empty, you're done. Otherwise, choose an arbitrary $(a, b)$ from your list, output it and remove it.
2. Find the unique $(c, b)$ in your list, output it and remove it.
3. If $(c, d)$ exists in the list, output it and remove it. Otherwise go to 1.
4. Find the unique $(e, d)$, output it, remove it, let $c \leftarrow e$ and go to 3.

---
Tags: algorithms, graphs, eulerian-paths
---


# Question
Title: Does a notion of a context-free complete language exist?
Is there a notion of a context-free complete language (in the analogous sense to a $NP$-complete language)?

# Answer
> 7 votes
Yes.

Lautemann and Schwentick prove that Greibach's "hardest context-free grammar" with a neutral symbol is complete for $LOGCFL$ and hence $CFL$ also, under quantifier-free projection without BIT.

This is Corollary 4.3 in their paper

---
Tags: formal-languages, computability, context-free, reference-request
---


# Question
Title: Reduce EXACT 3-SET COVER to a Crossword Puzzle
I have an assignment where I have to prove that solving a **crossword puzzle** is an $NP$-complete problem by reducing from **EXACT 3-SET COVER**. I have more or less given up at this point. If anyone could give me a hint or know where to find the proof, it would be much appreciated.

> **Problem**: \[${\bf CrossWordPuzzleConstruction}$\]
>
> **Input**: Given are an alphabet $\Sigma$ not containing the symbols "blank" or "#", a non-empty set of strings $S=\\{s\_1,\dots,s\_m\\}$ over $\Sigma$, and an $n\times n$ matrix $A$ for a non-negative integer $n$. The entries in $A$ are either "blank" or "#".
>
> **Output**: YES if the blank entries in $A$ can be filled with letters from $\Sigma$ in such a way that the result is a crossword puzzle with strings from $S$. That is, every maximal horizontal or vertical sequence in $A$ consisting of letters from $\Sigma$ is a string from $S$ when read left-to-right respectively downwards. The same string may occur more than once.

We call the problem ${\bf CPC}$ for short.

**Example**: $\Sigma=\\{a,b,c\\}$, $S=\\{aa,bb,cac,ab,cab,ca,a,ac,bba,aab,bab\\}$,

The answer to this input is YES as the following solution shows:

> **Problem**: \[${\bf ExactThreeCover}$\]
>
> **Input**: The set $X=\\{1,2,\dots,n\\}$ where $n=3q$, $q\geq1$, and a collection $\mathcal{C}=\\{C\_1,C\_2,\dots,C\_m\\}$ of subsets of $X$ of sixe $3$. That is, for $i\in\\{1,\dots,m\\}$, we have $C\_i\subseteq X$ and $|C\_i|=3$.
>
> **Output**: YES if there exists a set $\mathcal{A}\subseteq\mathcal{C}$ such that the elements of $\mathcal{A}$ are a partition of $X$, i.e., $\cup\_{C\_i\in \mathcal{A}}=X$ and $C\_i\cap C\_j=\emptyset$ for $C\_i,C\_j\in\mathcal{A}$ and $i\neq j$.

# Answer
> 0 votes
Since you are so interested in solving this assignment to hand in and be applaused by the whole class.

I give you another answer.

Reduce from **X3C** (Exact 3-Set Cover) as required.

We will construct a table as follows:

The leftmost column will be forced to be (solely by its **maximum length**)

$\star\\ \star\\ \star\\ 1\_{row}\\ \star\\ \star\\ \star\\ \star\\ \star\\ 2\_{row}\\ \star\\ \star\\ \star\\ \star\\ \star\\ 3\_{row}\\ \dots $

The uppermost row will contain the solution (a subcollection of $3$-sets).

$\\#\\#\\#1\_{col}\star\star\star\star2\_{col}\star\star\star\star3\_{col}\\#\\#\dots\\#\\#\\#$ to denote that we choose a $3$-set that contains $1$, $2$ and $3$.

Now, all that we need is to make sure that our solution which appear in the uppermost row is feasible. It means that for each $i\_{row}$, if we "beam" from its position (in the first column) to the right, we will meet $i\_{col}$ exactly once (in fact, we only need to assure *at most once*).

To guarantee this, we create zig-zag tunnel like this:

`- ---`
`| | |`
`| | |`
`---- --- ...`

To be able to cross a different column item, we add these words $i\_{row}\<i\_{row}j\_{col}\>i\_{row}$ where $\<i\_{row}j\_{col}\>$ is a single symbol, for every $i\neq j$. And, similarly, for the column item, these words $j\_{col}\<i\_{row}j\_{col}\>j\_{col}$

To be able to meet the same column item (and never again), we add these words $i\_{row}\<i\_{row}i\_{met}\>i\_{met}$, for all $i$. Similarly, for the column item, these words $i\_{col}\<i\_{row}i\_{met}\>i\_{col}$.

Note that, $i\_{met}$ are **deemed** to **belong to the rows only**.

To be able, to continue after crossing the same column item, and never meets same column item again, we add these words $i\_{met}\<i\_{met}j\_{col}\>i\_{met}$, for every $i\neq j$. And, similarly, for the column item, $j\_{col}\<i\_{met}j\_{col}\>j\_{col}$.

Lastly, to be able to go through the tunnel, add all these word $x\star x$ for all symbol $x$ that appears so far.

# Answer
> 0 votes
A reduction from **PLANAR 3-SAT** with bounded occurrences is more viable.

The upper bound of occurrences should be $3$ for each variables $x\_i$ (two positive and one negative OR two negative and one negative).

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


# Question
Title: Loopless NFA equivalent in strength to NFA
For every nondeterministic finite state automata (NFA) that has self-loop(s), there exists an equivalent NFA that does not have any self-loop.

How do I prove this?

# Answer
> 8 votes
Make two copies of your original NFA and connect them in an appropriate way.

# Answer
> 5 votes
create a new state for each self looping state and connect all self looping edges to that state and reconnect that state back to its original state(s) with Epslon\lambda transition  while you can transform your self loops to another state like i did as follows  Images of NFA are created in JFLAP software.

# Answer
> 2 votes
Make a list of self-looping nodes. From left to right of the list, for each node contained, split it into $2$ distinct nodes, connect them (in both directions) by arcs with the same label as the self-loop (that is now deleted), connect each of the two new nodes to other nodes so as each look exactly like the deleted node before (that means all incoming and outgoing arcs are copied exactly).

Do not forget to set the starting node and final nodes appropriately.

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


# Question
Title: complexity classes defined as limits or "globally"?
As far as I understand correctly, to say that a decision problem $X$ is in **P** means that there exists a polynomial $c\cdot n^p$ such that **as $n$ goes to $\infty$**, the steps required to solve $X$ is bounded by $c\cdot n^p$.

But strictly speaking, this doesn't restrict the complexity for finite $n$ in any way. Strictly speaking if $X$ is in **P**, it could be that for all $n$ between $0$ and Ackermann function $A(300,300)$, the complexity of $X$ grows according to $e^n$, and then only from $A(300,300)$ onwards it starts being bounded by $c\cdot n^p$.

Am I right that if a problem is in the complexity class **P** this strictly speaking doesn't say anything about its complexity for finite $n$? Is there a way to talk about complexity for finite $n$?

# Answer
Complexity classes are (usually) expressed using Landau notation, which makes precise what you state. See also our reference questions.

Yes, *by definition* (usual) complexity classes don't say anything about the real world per se. That is by design; complexity is a *model* for classifying the inherent hardness problems, not a tool to design or analyse algorithms. See also here for some related thoughts.

> Is there a way to talk about complexity for finite n?

"Complexity" and "finite" are mutually exclusive. Of course you can study, say, the (relative) performance of algorithms on real(istic) data. The machinery of complexity theory and, sadly, "Big-Oh"-driven algorithm analysis will be mostly useless then.
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: How would you identify the size of a circular turing tape?
Came across this interesting problem in one of my interviews. Suppose you have a circular turing tape, i.e. simply a circular array. You do not know the size i.e. the number of cells available in that circular array.

The array consists only of binary digits. Lets say you are currently at one of the cells. You can read and write on the current cell you are on. You can rotate the array towards the left or right, and you have a counter with you which tells you how far away are you from the original cell that you started off with. So if you go right by x units, the counter will read x units and -x if you go x units to the left. However, you cannot store the value of previous cells you encountered. You may have at max only one unit of external memory at your disposal. For example, if you are at +x, you could compare the value at that +x with the one value you have stored in the external memory. Given that currently all the cells have been randomly assigned either a 0 or a 1.

How would you identify the size of this circular array?

# Answer
This answer was inspired by YuvalFilums's comment.

---

I will denote values in the cells with $t$ and $f$ and locations on the tape with $0, 1, 2, \dots$ to avoid confusion.

First, check that the length $\neq 1$. To do this, set the cell under the counter to $f$. Then, move right $1$ cell and set that cell to $t$, and return to $0$, checking if that is $t$. If so you have your answer, otherwise move to $2$ and set that to $f$, and return to $0$.

Second, check that the length $\neq 2$ similarly.

Then repeat the following procedure indefinitely:

1. Move right until encountering an $f$. Set this to $t$.
2. Move right one cell and set it to $f$.
3. Return to $0$. If it is $t$, find the first $f$ after $1$, and move left one cell. This is your answer. Otherwise, repeat.
> 1 votes

---
Tags: algorithms, arrays
---


title: decision trees and numeric attributes

text:
# Question
Title: decision trees and numeric attributes
I have been reading a book about Decision Trees and it caught my attention the following part:

> In case of numeric attributes, decision trees can be geometrically interpreted as a collection of hyperplanes, each orthogonal to one of the axes

I tried to look for information about this in Internet, but I did not find anything. To what the author refers in this point?

# Answer
Each vertex in a decision tree is associated with a question of the form "$x\_i \< c$?" (or "$x\_i \leq c$?"), where $x\_i$ is one of the input and $c$ is a constant. The decision whether to go left or right then depends on which side of the hyperplane $x\_i = c$ the input is located.

The possible hyperplanes which come up this way are not arbitrary – they are orthogonal to one of the axes; the hyperplane $x\_i = c$ is orthogonal to the $x\_i$ axis. An example of a different hyperplane, which cannot occur, is $x\_1 - x\_2 = 0$.
> 2 votes

---
Tags: decision-tree
---


# Question
Title: Convert given string to palindrome with given substring
Given strings `s1` and `s2`, consider the problem of converting `s1` to a palindrome string `p` such that `s2` is a substring of `p`, where the only operation allowed on `s1` is replacement of any character with any other character.

What is the minimum number of operations required for this task?

# Answer
Here is a description of a simple brute force approach that works in $O(n^2)$, where $n$ is the length of $S\_1$.

Let $m$ be the length of $S\_2$. If $m\>n$, return -1 immediately, indicating impossibility.

Keep a counter on how many characters will be changed. Change $S\_1$ so that its substring with length m that starts at index 0 is the same as $S\_2$. Mark the indexes where characters have been changed. Also chang $S\_1$ so that ist substring that starts at index n-1-0 and goes backwards to index n-m-0 is $S\_2$ backward. However, abort this try if we have to change the characters that has been marked. Now change the remaining characters of $S\_1$ to make it a palindrome. That is, if the character at index $i$ is not same as the character at index $n-1-i$, change the later to be the former. Once done, the counter tells us how many changes is needed to make $S\_1$ a palindrome that has $S\_2$ as its substring starting at index 0.

Repeat the above with index 0 replaced with index $1, 2, \cdots, n-m$, keeping tracking of the minimal number of changes.

The above description should be enough to set you up. You may want to improve it or look for better algorithms.
> 0 votes

---
Tags: algorithms, strings, substrings
---


# Question
Title: The most subtle NP-"intermediate" problem
What is the $NP$ problem whose status in $P$ or $NP$-complete is still unsettled, as of 2018?

This question is inspired by the following two recent breakthroughs:

1. The work of Mulzer et. al on $NP$-completeness of min-weight triangulation.
2. Recent quasi-polynomial algorithm of Babai for graph isomorphism. The link is to Helfgott's more recent (2017) paper.

# Answer
> 2 votes
In addition to Eugen's answer, the problem of determining whether an integer $N$ has a factor less or equal to $M$ is also not known to be in either P or NP-C.

# Answer
> 1 votes
One example is graph isomorphism.

# Answer
> 0 votes
IMHO, there are dozens of meaningful $NP$ problems which statuses have not been dichotomized.

In fact, each one of your rather long list of "**Karp hardness of**..." questions contains an $NP$ problem that has some such variant. As long as one delves deep enough into each of these, one would find some subtle variant for oneself.

---
Tags: complexity-theory, np-complete, reference-request, np, np-intermediate
---


title: Summation Properties of Big Omega

text:
# Question
Title: Summation Properties of Big Omega
What are the properties of summation with Big Omega? I have been looking online but cannot find any sources on summation with Big Omega, only for Big Oh. For example, my main inquiry is if this statement is true or not, If $a(x) + b(x) ∈ \Omega(c(x))$, then $a(x) ∈ \Omega(c(x))$ or $b(x) ∈ \Omega(c(x))$.

# Answer
Essentially, anything you can prove for $O(-)$ has a closely related fact that you can prove for $\Omega(-)$, in essentially the same way. By "closely related", I mean that you might have to swap $\geq$ and $\leq$ and things like that.

You can check that the following is a counterexample to your statement about $a$, $b$ and $c$. \begin{align\*} a(x) &= \begin{cases}x&\text{if $x$ is even}\\0&\text{if $x$ is odd}\end{cases}\\ b(x) &= \begin{cases}0&\text{if $x$ is even}\\x&\text{if $x$ is odd}\end{cases}\\ c(x) &= x\\,. \end{align\*}
> 1 votes

---
Tags: time-complexity, runtime-analysis
---


# Question
Title: join is the heart of the monad because it encompasses everything a monad can do that a functor cannot. Is this true?
There is a controversy about Monad implementation in S.O .

The original question is,

What's so special about Monads in Kleisli category?

> Is there any counterexample that Functors cannot do what Monads can do *except the robustness of functional composition by flattening the nested structure*?
>
> What's so special about Monads in Kleisli category? It seems like it's fairly possible to implement Monads with a little expansion to avoid the nested structure of Functor and without the monadic functions `a -> m b` that is the entity in Kleisli category.

An answer is

> "Avoiding the nested type" is not, in fact, the purpose of join, it's just a neat side-effect. The way you put it makes it sound like join just strips the outer type, but the monad's value is unchanged.
>
> You can think of a functor as basically a container. There's an arbitrary inner type, and around it an outer structure that allows some variance, some extra values to "decorate" your inner value. fmap allows you to work on the things inside the container, the way you would work on them normally. This is basically the limit of what you can do with a functor.
>
> A monad is a functor with a special power: where fmap allows you to work on an inner value, bind allows you to combine outer values in a consistent way. This is much more powerful than a simple functor.
>
> join is the heart of the monad because it encompasses everything a monad can do that a functor cannot. Since join and \>\>= are isomorphic and you can define each in terms of the other, defining \>\>= without join still provides the same degree of freedom (you could say that defining \>\>= indirectly defines join, and vice versa). You get the same thing either way, except that \>\>= is more convenient and join is more "pure". So it is really a boring question to compare the two. – DarthFennec

The objection by the questioner is,

> I believe "Avoiding the nested type" is not just a neat side-effect, but a definition of "join" of Monad in category theory,

the multiplication natural transformation μ:T∘T⇒T of the monad provides for each object X a morphism μX:T(T(X))→T(X)

> and that's exactly what my code does.
>
> I know many people implement monads in Haskell in this manner, but the fact is, there is Maybe functor in Haskell, that does not has join, or there is Free monad that join is embedded from the first place into the defined structure. They are objects that users define Functors to do things.
>
> Therefore, ... \[your\] observation does not fit the fact of the existence of Maybe functor and Free monad.

Which opinion is correct?

PS. Additional comment from DarthFennec (who answers) as below:

---

`Free` is weird, in that it's one of the few monads that *doesn't actually do anything*.

`Free` can be used to turn any functor into a monad, which allows you to use `do` notation and other conveniences. However, the conceit of `Free` is that `join` does not combine your actions the way other monads do, instead it keeps them separate, inserting them into a list-like structure; the idea being that this structure is later processed and the actions are combined by *separate code*. An equivalent approach would be to move that processing code into `join` itself, but that would turn the functor into a monad and there would be no point in using `Free`. So the only reason `Free` works is because it delegates the actual "doing things" part of the monad elsewhere; its `join` opts to defer action to code running outside the monad. This is like a `+` operator that, instead of adding the numbers, returns an abstract syntax tree; one could then process that tree later in whatever way is needed.

> These observation does not fit the fact of the existence of Maybe functor and Free monad.

You are incorrect. As explained, `Maybe` and `Free` fit perfectly into my previous observations:

* The `Maybe` functor simply does not have the same expressiveness as the `Maybe` monad.
* The `Free` monad transforms functors into monads in the only way it possibly can: by not implementing a monadic behavior, and instead simply deferring it to some assumed processing code.

---

First of all the word he uses "`Free` is weird" or "the conceit of `Free`" unduly disparaging the Free monad, and this words does not justify what he insists obviously.

> An equivalent approach would be to move that processing code into `join` itself, but that would turn the functor into a monad and there would be no point in using `Free`.

My question would be if "join is the heart of the monad", how come the " processing code" has been moved away from the heart =`join` and move-back into `join` again? That is the weird.

Free is one of the generalization to abstract the "processing code" of Monad. Monad structure including `join` that satisfies the monad laws are pre-defined without the "processing code" that would be functor/ or function if it's Operational monad.

> So the only reason `Free` works is because it delegates the actual "doing things" part of the monad elsewhere; its `join` opts to defer action to code running outside the monad.

In either way, again, "doing things" does not have to locate in `join`. If someone strongly insists "join is the heart of the monad", maybe it's ok to do so. However, as Free-monad, it's totally reasonable a user let `join` be pre-defined in a generalized structure of Monad as a functionality of flattening the structure, or other monads also does not have to move "doing things" to `join` because it's not the heart of the monad anyway.

# Answer
I'm not sure I fully understand the question, but since it's my answer you're wondering about, I'll do my best to clarify my meaning.1

> join is the heart of the monad because it encompasses everything a monad can do that a functor cannot. Is this true?

Let's find out!

We can define a functor2 like so:

```
class Functor' f where
    pure' :: a -> f a
    fmap' :: (a -> b) -> f a -> f b
    ap'   :: f (a -> b) -> f a -> f b

```

We can define a monad in the following way:

```
class Monad' m where
    pure' :: a -> m a
    fmap' :: (a -> b) -> m a -> m b
    ap'   :: m (a -> b) -> m a -> m b
    join' :: m (m a) -> m a

```

As you can see, these are the same except for the added `join'` on the `Monad'` class. Since without this `join'` the `Monad'` is indistinguishable from the `Functor'`, I think it's safe to say that `join'` embodies everything in `Monad'` that is not in `Functor'`.

This can also be seen in the way the Haskell Prelude defines `Monad`:

```
class Applicative m => Monad m where
    (>>=)  :: m a -> (a -> m b) -> m b

    (>>)   :: m a -> m b -> m b
    m >> k = m >>= (\_ -> k)

    return :: a -> m a
    return = pure

```

From this we can see the following:

* Any `Monad m` must also be an `Applicative m`, meaning that all `Monad`s are also `Functor`s.
* `>>` is simply a convenience method, and is defined in terms of `>>=`.
* `return` is just another name for the applicative `pure`.
* The only remaining method defined by `Monad` is `>>=`. Therefore, `>>=` is the one thing `Monad` has that `Applicative` doesn't have.

However, we can define `>>=` in the following way:

```
(>>=) :: m a -> (a -> m b) -> m b
m >>= f = join (fmap f m)

```

`fmap` is part of `Functor`, so `join` is the only remaining thing that's unique to `Monad`. This is why I described `join` as "the heart of the monad".

> In either way, again, "doing things" does not have to locate in `join`. If someone strongly insists "join is the heart of the monad", maybe it's ok to do so. However, as Free-monad, it's totally reasonable a user let `join` be pre-defined in a generalized structure of Monad as a functionality of flattening the structure, or other monads also does not have to move "doing things" to `join` because it's not the heart of the monad anyway.

I'm not sure I understand what you mean. `join` is the place in a `Monad` where the actual "doing" is defined; this is where the *purpose* of the `Monad` is encoded. The *purpose* of `Free` is to displace the "actual" processing logic for the user to deal with somewhere else. I suppose you could say that `Free` is a way to transform a `Monad` problem into a data processing problem, in that `join` creates a data structure that can later be processed. This is unusual because most `Monad`s encode destructive processing into `join`, but this doesn't have to be the case. But the fact that the "heart" of `Free` is the displacement of the business logic does not mean `join` doesn't represent the "heart" of a `Monad`.

---

1Note that I don't have a category theory background, so I'm going to be working in the context of Haskell. I assume that's okay, since this question is tagged as `[functional-programming]`.

2This is actually an "applicative functor", which defines a couple of extra methods. I believe this is appropriate, as the questioner's original question defined a functor with `fmap` and `unit`, the latter being another name for the applicative `pure`.
> 3 votes

---
Tags: functional-programming, category-theory
---