# Question
Title: Non-deterministic Büchi vs Rabin: Automaton size for LTL->automaton
Is there any general result to show that which automaton is more succinct? I have a set of LTL properties and I would like to know (show) which automaton is more efficient in term of state number and edge number.

# Answer
Consider a nondeterministic Büchi automaton $A = \langle \Sigma, Q, q\_0, \delta, \alpha\rangle$. The acceptance condition of $A$ is a subset of states $\alpha\subseteq Q$, and an infinite run $r = q\_0, q\_1, q\_2, \ldots$ over an infinite word $\sigma\_1\sigma\_2\cdots $ is accepting iff $r$ visits a state in $\alpha$ infinitely many times.

In Rabin automata, the acceptance condition is given by $\alpha = \\{\langle \alpha\_1, \beta\_1 \rangle, \langle \alpha\_2, \beta\_2 \rangle, \ldots , \langle \alpha\_k, \beta\_k \rangle \\}$, where $ \alpha\_i, \beta\_i\subseteq Q$, for all $i\in \[k\]$. An infinite run $r = q\_0, q\_1, q\_2, \ldots$ over an infinite word $\sigma\_1\sigma\_2\cdots $ is accepting iff for some $i\in \[k\]$, $r$ visits a state in $\alpha\_i$ infinitely many times, and visits the states in $\beta\_i$ finitely many times. The number $k$ is the index of the automaton, and is usually taken into account when defining the automaton's size.

Clearly, a Büchi condition $\alpha$ is equivalent to the Rabin condition $\\{ \langle \alpha, \emptyset \rangle\\}$. Thus, nondeterministic Büchi automata can be translated to nondeterministic Rabin automata with no blowup (they can be thought of as a simple fragment of Rabin automata - although they are equally expressive). So, nondeterministic Büchi automata cannot be more succinct than nondeterministic Rabin automata. However, a nondeterministic Rabin automaton with $n$ states, $m$ transitions, and index $k$, can be translated to a nondeterministic Büchi automaton with $O(n\cdot k)$ states, and $O(k\cdot m)$ transitions. The later translation is justified by a lower bound. So, nondeterministic Rabin automata are polynomially more succinct than nondeterministic Büchi automata, which is not significant.

A comprehensive overview of the translations can be found here (along with other relevant references).

Note that you can easily translate an LTL formula into a nondeterministic Büchi automaton (see section 6 here), and the translation has a tight exponential bound. However, following your comment, if you're interested in translating the LTL-formula into a deterministic automaton, then you can translate the Büchi automaton to a deterministic Rabin automaton (such determinization construction has a tight bound of $2^{\Theta(n \log n)}$). Also, the double exponential blow-up of translating LTL formulas to deterministic automata cannot be avoided (see theorem 26 here).
> 3 votes

---
Tags: automata, linear-temporal-logic
---


title: Blueprint for class and objects in Java

text:
# Question
Title: Blueprint for class and objects in Java
Good morning everybody. I would like to know if there is a blueprint I could refer to when creating classes and objects in Java? For instance, I was told for classes. You start VARIABLES DECLARATIONS then CONSTRUCTOR then SETTERS AND GETTERS. What do you guys think. Thank you kindly.

PS I have just starting Java.

# Answer
According to Oracle's Java SE Archives

> The proper order of a Java file is:
>
> 1. Beginning documentation
> 2. Package and Import Statements
> 3. Class and Interface Declarations
>
> Where a class/Interface is arranged as follows:
>
> 1. Class/Interface documentation
> 2. Class/Interface statement
> 3. Class/Interface implementation comments (if needed)
> 4. `static` variables
> 5. Instance variables
> 6. Constructors
> 7. Methods
>
> Variables within each category are organized by access level (`public`, `protected`, no modifier, and then `private`).
>
> Finally it mentions that methods should be organized by functionality.
>
> see: https://www.oracle.com/java/technologies/javase/codeconventions-fileorganization.html

While this archive is from 1999, in my experience people usually stick to this organization system. The organizational variation mostly comes in how people organize methods.
> 1 votes

---
Tags: java, object-oriented
---


# Question
Title: How can I prove that a build max heap's amortized cost is $O(n)$?
Suppose a **build** max-heap operation runs bubble down over a heap. How does its amortized cost equal $O(n)$?

# Answer
I assume that the operation **build** just turns an array into a heap by repairing the heap-property for every subtree bottom-up (let the operation for a single repair step called **heapify**).

It is not so hard to see, that **heapify** takes $O(h)$ steps, where $h$ is the height of the subtree to repair. We set $k=\lfloor \log n \rfloor $ as the height of heap. Notice that we have no more then $2^{(k-h)}$ subtrees of height $h$. So we can simply add up the costs as follows (we slightly abuse the big-O notation):

$$ \sum\_{h=1}^k O(h) 2^{k-h} = 2^k \sum\_{h=1}^k O(h)/2^{h}. $$

Since $\sum\_{h=1}^\infty O(h)/2^{h}$ converges, we can upper bound the sum $\sum\_{h=1}^k O(h)/2^{h}$ by a constant $C$. Thus we have that the running time for **built** is less than $C\cdot 2^k\le C \cdot n = O(n)$.
> 7 votes

# Answer
Note that here we don't have an arbitrary list of operations, we are talking about a single operation. So referring to it as amortized analysis can be confusing. Amortized analysis is usually used for an arbitrary list of operations, not a particular list of operations. We can use the methods for amortized analysis but AFAIK it is not common to call the result an amortized analysis.

Schulz answer is correct and uses the aggregate method. It is the usual proof of the fact and you can find it in textbooks like CLRS, chapter 6.

If you want to use the potential method for proving the bound, then remember that we want to get $O(1)$ for each heapify operation (to get $O(n)$ for the build heap operation). The real cost for each heapify is $O(h)$. We have to pay for the rest from the potential function. If we charge $c$ units for amortized cost then we can see that the analysis will work (we will determine $c$ later).

For the nodes in the bottom level (1) we will have to pay $n/2$. So we save potential $$cn/2-n/2$$

For the next level (2) we will pay $2n/4$ so we have potential $$c(n/2 + n/4) - (n/2 + 2n/4)$$

For the next level (3) we will pay $3n/8$ so we have potential $$c(n/2 + n/4 + n/8) - (n/2 + 2n/4 + 3n/8)$$

For the $k$th level we will pay $kn/2^i$ so we have potential $$cn\Sigma\_{i=1}^k \frac{1}{2^i} - n\Sigma\_{i=1}^k \frac{i}{2^i}$$

Note that $\Sigma\_{i=1}^k \frac{i}{2^i} \leq d$ for some constant $d$ independent of $n$ and $k$ and $\Sigma\_{i=1}^k \frac{1}{2^i} \geq \frac{1}{2}$. If we put these in the formula we get that the potential will always be at least $\frac{c}{2}n - dn$. So if we choose $c$ to be any constant larger than $2d$ it will always be positive.

The exact value of $c$ is not really important.

To cast this as an accounting method we need to specify which part of the data structure the potential is being assigned. In this case the potential needs to be assigned to the levels of the heap (if we want to assign the potential to nodes then it will be more complicated since it is difficult to tell which nodes will be use later when heapify is applied to nodes on higher levels).
> 2 votes

# Answer
If anyone will still come across this problem and interested in a potential analysis way of obtaining the accepted answer. I have a preprint in arxiv discussing this. We got a simpler sum and a tighter constant, but you need to have some idea about potentials.

Essentially we treat the array as a forest of heaps and define the potential to be the sum of the levels of all the heaps in the forest. Each time the build heap repairs a subtree, we treat it as merging of at most 3 heaps. So each repair decreases the number of heaps in the forest. We then show that the amortized cost of a repair is 1. Since there are n level 1 heaps at the start and there are n/2 repairs, the total cost is 1.5n.
> 0 votes

# Answer
Algorithm of Build Heap:

BUILD-HEAP(A) heapsize := size(A); for i := floor(heapsize/2) down to 1 do HEAPIFY(A, i); end for END

A quick look over the above algorithm suggests that the running time is O(nlogn), since each call to Heapify costs O(logn) and Build-Heap makes O(n) such calls. This upper bound, though correct, is not asymptotically tight.

As we know that heapify is called for all internal nodes, and heapify takes O(logn) time, but this is not exactly the case. In reality, the O(logn) time is taken by root only, as root is at the height logn, time varies for the internal nodes with different height. For example, for the internal nodes at the second last level, heapify will take O(h) time for all the nodes at that level where h=1, for the internal nodes at the third last level, heapify will take O(h) time for all the nodes at that level where h=2, therefore depending height time to heapify is changing. So considering this, we can derive a tighter upper bound than O(nLogn).

For finding the Time Complexity of building a heap, we must know the number of nodes having height h. For this we use the fact that, A heap of size n has at most ceil( n / 2^(h+1) ) Now to derive the time complexity, we express the total cost of Build-Heap as-

T(n)= ceil( n / 2^(h+1 )) * O(h) = n/2 * h / (2^h) =O( n * h /( 2^h) )

Step 3 uses the properties of the Big-Oh notation to ignore the ceiling function and the constant 2 ( since 2^(h+1) = 2.(2^h) = O(2^h) ), and the upper limit of the summation can be increased to infinity since we are using Big-Oh notation. Here we will consider that ‘h’( means the height) tends to infinity for the worst case time complexity.

Now, ∑ h / 2^h = (0 / 2^0) + (1 / 2^1) + (2 / 2^2) + (3 / 2^3) + (4 / 2^4) + ……….

= 0/1 + 1/2 + 2/4 + 3/8 + 4/16 + 5/32 + …………. ------------\> eqn 1

Now, if we divide the whole equation from 2 we get,

∑ h / 2.(2^h) = 0 / 2.(2^0) + 1 / 2.(2^1) +2 / 2.(2^2) +3 / 2.(2^3) +4 / 2.(2^4) + …….

= 0/2 + 1/4 + 2/8 + 3/16 + 4/32 + 5/64 + ………….. ------------\> eqn 2

Now, subtracting (eqn 1 – eqn 2) —-\>we get,

∑ h / (2^h) - h /( 2.(2^h)) = 1/2+ 1/4 + 1/16 + 1/32 + ……………. + 1/∞

=\> ∑ 1/2(h / 2^h) = 1/2 / (1 – 1/2) (using formula for infinite GP, sum = a / (1-r))

=\> ∑ h / 2^h = 2

Therefore, T(n) = O( n * h /( 2^h) ) = O(n * 2) = O(n),

So, time complexity of build-heap is O(n).
> -1 votes

---
Tags: data-structures, runtime-analysis, heaps
---


# Question
Title: Is there a method to generate the complement of a context-free grammar?
Given the languages $L\_0 = {w \in \\{0,1\\}^\*}$ such that $w$ is a palindrome and $L\_1 = {w \in \\{0,1\\}^\*}$ such that $w$ is *not* a palindrome, meaning $L\_1$ is the complement of $L\_0$, we want to find the grammar for both languages. $G(L\_0) = S \to \epsilon | 0S0 | 1S1 | 0 | 1$ is easy to come up with, but $G(L\_1)$ is much more complex.

In this case, we have the simple CFG $G\_0$ and want to find the CFG $G\_1$ that is its complement which can be much more complex. Is there a method to derive the complement of a CFG?

# Answer
If $L\_0$ in a context-free language, this doesn't guarantee that its complement is context free. For example, consider the language $$L\_0 = \\{a,b,c\\}^\* \setminus \\{a^nb^nc^n : n \geq 0\\}.$$ This language is context-free, but is complement (with respect to $\\{a,b,c\\}$) is not.

Another way to formulate your question is as follows: given a context-free grammar for a language $L$, is there an algorithm that either constructs a context-free grammar for the complement of $L$, or determines that the complement of $L$ is not regular? Such an algorithm can be used to decide whether the complement of $L$ is context-free. However, this is undecidable, as we now show following Hendrik Jan's notes.

Recall that given a grammar $G$ over an alphabet $\Sigma$, it is undecidable whether $L(G) = \Sigma^\*$. Let $\\#$ be a new symbol, and construct a grammar for the language $$ L = L\_0 \\# \Sigma^\* \cup \Sigma^\* \\# L(G), $$ where $L\_0$ is a context-free language whose complement is not context-free (if $|\Sigma| \geq 3$, we can use the one above, and if $|\Sigma| = 2$, we can encode $a,b,c$ as $a,ba,bba$; if $|\Sigma| = 1$ then it is easy to check whether $L(G) = \Sigma^\*$). If $L(G) = \Sigma^\*$ then $L=\Sigma^\*\\#\Sigma^\*$, and so the complement of $L$ is context-free. Otherwise, suppose that $w \notin L(G)$. Then $$ \overline{L} \cap \Sigma^\* \\# w = (\Sigma^\* \setminus L\_0) \\# w, $$ which is not context-free, and so $\overline{L}$ itself is not context-free (since the context-free languages are closed under intersection with a regular language). This shows that $\overline{L}$ is context-free iff $L(G) = \Sigma^\*$.

The problem of deciding whether $L(G) = \Sigma^\*$ is actually not recursively enumerable. This means that there is no algorithm which, on input $G$, halts iff $L(G) = \Sigma^\*$ (however, there is a simple algorithm that halts iff $L(G) \neq \Sigma^\*$, namely go over all words in $\Sigma^\*$ in parallel, and check whether each of them belongs to $L(G)$). Therefore there is no algorithm that, given a context-free grammar for a language $L$, halts iff the complement of $L$ is context-free.

In other words, even the following solution to your problem does not exist: an algorithm that attempts to construct a context-free grammar for the complement of the given context-free language, and either halts with the grammar, or never halts (if the complement is not context-free).
> 2 votes

---
Tags: finite-automata, context-free, formal-grammars
---


# Question
Title: Should you post basic computer science homework to your github?
I am currently taking computer science coursework as part of a computer science related degree at my University. I was wondering if I should upload the solutions I make for various trivial homework assignments (ie. not more than 20-30 or so lines of code, on basic/fundamental topics) to my GitHub account, or if I should only upload larger course/personal projects to it. I have only been regularly coding for about a year, and a large portion of the code I have written was for a company where I was under an NDA, so I was wondering if this would be an appropriate way to add more breadth to future job applications.

# Answer
> 13 votes
No, solutions to homework assignments are not likely to impress potential future employers.

Many professors would prefer that you not post solutions to homework assignments to public Github repositories. Why? If they ever reuse those problems in a future semester, then by making the solutions publicly available you are creating a temptation to cheat for other students, and that can be detrimental. So it would be a kindness to avoid publicly posting solutions.

If you are a student, you can get free unlimited private repositories on Github that you could use for homework assignments. Just make sure not to let them revert to public when you graduate.

# Answer
> 4 votes
For advanced homework solutions, I'd indeed consider polishing and uploading or writing a blog post about it.

The natural way to create advanced solutions is to solve advanced exercises that are stated openly, without a clear path/coding framework in mind — typically in M.Sc.-level courses. Alternatively, you can try to go above and beyond when solving simple exercises.

For instance, we were once asked to model a toy ontology language in a programming language of our choice, and I modelled it in Coq, the proof assistant. I do think there is some value in me having published that solution on GitHub; if only for the reason that it raises my incentive to improve it when I can spare time.

Whether professors generally mind students publishing their solutions, is apparently highly culture-dependent. The other answers by D.W. and Joshua096 report on the default in their experience being *yes*, i.e., you should always ask professors before hand.

In contrast, in the German academic culture I experienced, the *default* was that you can share anything. In fact, our student council publicly collects old written/oral exam questions. And professors know this; some even recommend you to take a look at them. Rarely do they *kindly ask* you to not publish things, knowing they couldn't/wouldn't want to go down to legal path of forcing you anyway.

# Answer
> 4 votes
I'd recommend that you talk with your professors. No one here can speak for your professor (unless your professors is here).

From my experience, I'd bet that most professors would love your enthusiasm but be very reluctant to allow it because of the issues with plagiarism and academic integrity. If you discuss it with the professor you may find that they are open to extra credit projects or something to give you some opportunity to add to your repositories. Go into the discussion fully expecting it to be a long shot.

I've had quite a few syllabi state that storing class work in a public repository would be considered a breach in our academic integrity policies, but at the same time I've also been given permission from other professors to use GitHub public repositories on a number of projects. It usually came down to if the mission of the project is unique to the student/team. When every team is creating a one of a kind project, it usually becomes less of a problem to create a public repository. The best luck I've had getting public GitHub repository approval was with professors that offed independent study extra credit opportunities and when we had group projects.

In any case, never assume that you can upload any coursework to a public repository! Discuss it with your professors.

---
Tags: career
---


# Question
Title: Why we can't create a binomial heap in max-heap format?
Why we can't create a binomial heap in max-heap format instead of min-heap format?

# Answer
Why do you say that we cannot create a binomial max-heap? Given any min-heap implementation you can always create its max version (and vice-versa).

An easy "black-box" way to see that this is true is considering what happens when all operations involving a key $k$ are actually performed on the key $-k$ instead.

That is, instead of inserting $k$ we insert $-k$; instead of deleting $k$ we delete $-k$; when we need to return the minimum key $k$, we return $-k$; etc...
> 1 votes

---
Tags: heaps
---


# Question
Title: What are the differences between the set of Real Numbers and the Java datatype float?
Besides the fact that the real numbers ℝ go on forever whereas the floats only go up to a certain point (Float.MAX\_VALUE) in Java, what else could I compare between these two sets of numbers?

# Answer
The set of double precision floating point numbers in Java has the following elements:

Integers from 1 to $2^{53}-1$, multiplied by $2^e$ for integers e in some fixed range (which I am too lazy to look up right now).

+Infinity and -Infinity

+NaN and -NaN

+0 and -0.

The last six are not real numbers (+0 and -0 are both similar, but not quite the same as the real number 0).

Real numbers which are not Java floating-point numbers are 0, those numbers that are either too large or too small, requiring an integer e outside the allowable range, those that are not integer multiples of a power of two, and those that are integer multiples of a power of two with an integer \> $2^{53}$.
> 1 votes

# Answer
The most important difference is that there are infinitely many real numbers and only finitely many floats.

Indeed, between any two numbers $a\<b$, the set $\mathbb R \cap (a,b)$ is uncountably infinite (countably if you intersect with $\mathbb Q$ instead).

That is not the case with the floats.

Furthermore, the floating point numbers are *well-ordered*, i.e. any set $S$ of floating point numbers has a smallest element, whereas that's not the case with the reals.
> 0 votes

---
Tags: java, real-numbers
---


# Question
Title: Provide a polynomial time algorithm that decides whether or not the language recognized by some input DFA consists entirely of palindromes
Everything needed to know is in the question statement. I believe that the DFA has to be acyclic (meaning its language is finite), which can be checked in polynomial time. However, finding all paths from the start state to an accept state can run in exponential time in worst-case.

# Answer
> 2 votes
I will give a general algorithm going through intermediate steps that can be implemented in polynomial time, each. Yet, I will not dive into the details of how to implement each step. The solution I'm suggesting may not be optimal, yet it is easy to understand. Essentially, we're going to rely on basic properties of Pushdown automata (PDAs, for short).

Let $\mathcal{A}$ be a given DFA over the alphabet $\Sigma$, and consider the language $PAL\subseteq \Sigma^\*$ of the palindrome words. We need to decide whether $L(\mathcal{A})\subseteq PAL$ in polynomial time. Note that $L(\mathcal{A})\subseteq PAL$ iff $L(\mathcal{A})\cap \overline{PAL} = \emptyset$. So we need to decide whether the language $L(\mathcal{A})\cap \overline{PAL}$ is empty, and we do it as follows:

1- Construct a PDA $\mathcal{B}$ for $\overline{PAL}$: this is a well known exercise.

2- Construct a PDA $\mathcal{C}$ for $L(\mathcal{A})\cap \overline{PAL}$: this is also known, and can be done in polynomial time by a product construction of $\mathcal{A}$ and $\mathcal{B}$ (for example, see here).

3- Finally, check whether the language of the PDA $\mathcal{C}$ is empty. This also can be done in polynomial time (see here, or here).

# Answer
> 1 votes
The most straightforward way is the following:

Let $p(u,v)$ ("p" for palindrome) be a predicate which means "any path from $u$ to $v$ is a palindrome". We are interested in $p(S, F)$ for each starting state S and each finishing state F. To compute it, we need an auxiliary predicate $c(u,v)$ ("c" for connected): "there exists a pat from state $u$ to state $v$". $c$ can be computed in $O(n^3)$ time using transitive closure.

Let $E$ be the set of transitions. Let $\ell(u,v)$ be the label (symbol) on edge $u \to v$. Then:

$$p(u,v) = false,\ \ \text{if $\exists u', v':\ (u,u'), (v', v) \in E,\ c(u',v')=true,\ \ell(u,u') \ne \ell(v',v)$}$$ Simply put, if there is a path $u \to u' \leadsto v' \to v$ such that the first and the last symbols don't match, $p(u,v)$ is false.

If such a path doesn't exist, we can define $p(u,v)$ recursively: $$p(u,v) = \land\_{u', v':\ (u,u'), (v', v) \in E,\ c(u',v')=true} p(u', v')$$ I.e. if there is a path $u \to u' \leadsto v' \to v$ such that $u' \leadsto v'$ is not a palindrome, then $p(u,v)$ is not a palindrome.

Now, we can write a DFS-like solution. Let $G$ be a graph where vertices are pairs of states and edges are as defined by the second equation: $$ (u,v) \to (u',v') \iff (u,u'), (v', v) \in E,\ c(u',v')=true $$ Intuitively, an edge leads from a problem to a "subproblem".

Our starting vertices for DFS are $(S,F)$ for each starting state $S$ and each finishing state $F$. We need to check that none of these vertices reaches a "bad" vertex, where $(u,v)$ is bad if it fails the condition from the first equation, i.e.: $$\exists u', v':\ (u,u'), (v', v) \in E,\ c(u',v')=true,\ \ell(u,u') \ne \ell(v',v)$$ This is a standard use-case for DFS or BFS.

# Answer
> 0 votes
The following doesn't necessarily answer the question, but might be of interest.

Suppose that $L$ is a regular language consisting entirely of palindromes, and suppose that $L$ is accepted by a DFA having $n$ states. According to the pumping lemma, every word $w \in L$ of length at least $n$ can be decomposed as $xyz$ such that $|xy| \leq n$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$.

Suppose that $w$ has length at least $2n$, so that $|z|\ge |x|+|y|$. Choose $i$ so that $|x|+i|y| \geq |z|$. Since $xy^iz \in L$, we have $xy^iz = z'(y')^ix'$, where $w'$ is the reverse of $w$. In particular, we can write $y=st$ so that for some $j \geq 1$ we have $z' = xy^js$. Since $xz$ is also a palindrome, we have $$ xs'(t's')^jx' = xz = z'x' = x(st)^jsx'. $$ This shows that $s=s'$ and $t=t'$, that is, $s,t$ are palindromes, and the entire word has the form $w = x(st)^{j+1}sx'$. The proof of the pumping lemma shows that the first occurrence of $st$ corresponds to a cycle in the DFA, and this shows that in fact $x(st)^ksx' \in L$ for all $k \geq 0$.

We deduce that there is a finite language $F$ and a finite collection $R$ of words $(x,s,t)$, where $s,t$ are palindromes, such that $$ L = F \cup \bigcup\_{(x,s,t) \in R} x(st)^\*sx'. $$ Conversely, every language of this form is regular and consists of palindromes.

---
Tags: complexity-theory, turing-machines, automata
---


# Question
Title: This costs minimization problem, is it solvable in polynomial time?
I have the following problem: I have $c$ conflicts, named $(c\_1, \ldots, c\_c)$, where each conflict $c\_i$ has certain size $s\_i\in\mathbb{N}\_0$: the number of times conflict $c\_i$ has happened. Also, I have $m$ conflict resolution methods, named $(m\_1, \ldots, m\_m)$. Each method $m\_j$ cannot be used more than $u\_j\in\mathbb{N}\_0$ times, and each time you use it, you have to pay $p\_j\in\mathbb{N}\_0$ dollars, but you get that each conflict $c\_i$ connected to $m\_j$ is reduced by $\min(r\_{ji}, s\_i)$ units ($s\_i \leftarrow s\_i - \min(r\_{ji}, s\_i)$, for each $c\_i$ connected to $m\_j$).

Once some $s\_i=0$, the corresponding $c\_i$ must be removed, and once some $u\_j=0$, node $m\_j$ cannot be used anymore so it can be removed as well.

The problem is solving all conflicts (making every node $c\_i$ dissapear after making $s\_i=0$) by repeated uses of the available methods, expending a minimal amount of money.

For example, if we call $E$ our total expended money (with an initial value of $0$), and, for the sake of simplicity, assume that every $r\_{ji} = 1$, one use of $m\_2$ implies the following updates:

```
E <- E + p
u2 <- u2 - 1   # If u2 becomes 0, remove m2 from the graph.
s3 <- s3 - 1   # If s3 becomes 0, remove c3 from the graph.
s4 <- s4 - 1   # If s4 becomes 0, remove c4 from the graph.
s5 <- s5 - 1   # If s5 becomes 0, remove c5 from the graph.

```

It's guaranteed that all conflicts can be solved. In other words, each $s\_i\leq\sum\_j(\\{r\_{ji}\*u\_j : m\_j\text{ is neighbor of }c\_i\\})$.

Can this problem be solved polynomically? My guess is yes by using first the method that has the least "cost-per-conflict". In other words, at each iteration, make one use of the $m\_j$ that minimizes $p\_j/\sum\_i(\\{min(r\_{ji},s\_i) : c\_i\text{ is neighbor of }m\_j\\})$ and afterwards remove all nodes that became $0$.

But, since the removal of conflicts increases the "costs-per-conflict" of the surviving methods for the next iteration, I'm not sure if this eager algorithm will lead to an optimal solution or whether a solution algorithm requires dealing with combinatorial explosion to be optimal.

In other words; I'm not sure if such eager algorithm causes that early eager choices will force an unneccesary number of uses of more expensive methods later, avoidable by not taken so eager choices earlier, like any other NP-hard problem.

# Answer
It's a bad practice to use the same variable for two purposes, so I'll say that you have $C$ conflicts $(c\_1, c\_2, \dots, c\_C)$ and similarly $M$ conflict resolution methods. To simplify, let $r\_{ji} = 0$ if $c\_i$ and $m\_j$ are disconnected.

Suppose $t\_j$ is a variable indicating how many times method $m\_j$ was used we can phrase your problem as

\begin{align} \min \quad&\sum\_{j}p\_jt\_j\\ \text{s.t.}\quad&\forall i: \sum\_j r\_{ji}t\_j \geq s\_i\\,,\\ &\forall j:0\leq t\_j \leq u\_j\\,,\\ & \forall j:t\_j \in \mathbb{N}\_0\\,. \end{align}

What if instead we assume we always start by using every $m\_j$ as much as possible, and $n\_j$ represents the number of times we do **not** use $m\_j$ (compared to the maximum allowed). Note that $t\_j = u\_j - n\_j$. Substituting gives us

\begin{align} \min \quad&\sum\_{j}p\_j(u\_j-n\_j)\\ \text{s.t.}\quad&\forall i: \sum\_j r\_{ji}(u\_j-n\_j) \geq s\_i\\,,\\ &\forall j:0\leq(u\_j-n\_j) \leq u\_j\\,,\\ & \forall j:n\_j \in \mathbb{N}\_0\\,, \end{align} which is equivalent to \begin{align} \max \quad& \sum\_{j}p\_jn\_j\\ \text{s.t.}\quad&\forall i: \sum\_j r\_{ji}n\_j \leq -s\_i + \sum\_j r\_{ji}u\_j\\,,\\ &\forall j:0 \leq n\_j \leq u\_j\\,,\\ & \forall j:n\_j \in \mathbb{N}\_0\\,. \end{align}

But this is exactly the $M$-dimensional bounded knapsack problem. Thus your problem is NP-hard, but you also get to benefit from the existing literature that give very good practical solvers.
> 2 votes

---
Tags: optimization, combinatorics
---


# Question
Title: What is considered being proficient in a programming language?
I am a college student looking to get into industry work soon and want to understand what employers consider 'proficient' when it comes to programming languages. Right now, I understand that to mean that one can write a fully functional program without consulting any references. However, is there a tangible project or projects that demonstrate proficiency with a language and its libraries? Preferably projects that employers like to see in their candidates. My portfolio is relatively weak right now so I want to build that up before I graduate. Any recommendations are appreciated!

# Answer
I wouldn't go with your definition:

> that one can write a fully functional program without consulting any references

1. "Hello World" and Deep Neural Networks are both fully functional "programs". The complexity matters..
2. In the office nobody expects you to handle a program from beginning to end. Depending on the size of the office and their assembly line your assignments will vary a lot. For most of the time, you'll be implementing methods within a larger program.
3. It is a normal practice to use the documentation ("reference") even if you're on a senior position you're not supposed to remember everything by heart. Every developer I know spends at least 30 min on Stack Overflow every working day.

What is perhaps more valued is a solid foundation, understanding how the language works under the hood, ability to write clean readable code and be a team player.

Beyond a certain level of proficiency, it is not a criterion anymore because if you have a solid understanding of the language you can learn how to implement any complex algorithm or data structure in a reasonable amount of time.

You can never LEARN the whole language, you learn the Grammar...
> 2 votes

---
Tags: programming-languages, career
---


# Question
Title: Can you suggest a topic for a Bachelor Thesis in Mathematics that is related to Machine Learning?
## Context

I am a final year Bachelor of Mathematics student and next semester I will write my Bachelor thesis.
My interests are in Machine Learning (ML) and I will do a master in ML next year. More specific sub-fields I like are

* Deep Learning
* Computer Vision
* Natural Language Processing
* Reinforcement Learning

And my interests outside of ML and mathematics include

* Self-driving cars (*e.g.* Tesla)
* Rocket and space exploration

more vaguely, I find tech interesting as a whole.

## Question

I am looking for a thesis which would bring me as close as possible to the field of ML. **Do you have topic recommendations ?**

**BUT** my Bachelor is in Mathematics therefore I shall not write a thesis in Computer Science as it would not be accepted by my study director.

## Some thoughts

I know some people who were in my case. One of them for instance discovered and proved some convergence results in the context of Gradient Descent. Maybe this will inspire you with your answers.

Thanks in advance!

---

PS: This is a duplicate of my original question on the Math Stack Exchange but I thought that people on the Computer Science Stack Exchange could bring a different point of view.

# Answer
> 1 votes
I would like to make two points clear as a researcher:

1. Mathematics is a very broad discipline. When you're on bachelor level it is still appropriate to call it "Mathematics" but already in Masters, you'll need to specialize! Youll have to choose a branch and then you won't be "a mathematician" you'll be Statistician, a topologist, graph theorist, category theorist etc. This being said you need to ask yourself which branch you're most interested in? This leads to the next point:
2. The fact that you're interested in Machine Learning already narrows it down to Probability & Statistics, Linear Algebra, Multivariate Calculus. And here I would say that any topic that falls within these categories will help you later along the road.

Bachelor Thesis is a piece of scientific work that's why it is called "Bachelor". You are supposed to do research and produce new knowledge regardless of how small or significant it will be. This forum cant do it for you.

Pick something YOU are interested in from Probability & Statistics, Linear Algebra or Multivariate Calculus and explore the topic. Once you start you'll inevitably get questions that need addressing. If you get stuck pick a classic problem (for example Knight's tour) and systematically break it down.

---
Tags: machine-learning, artificial-intelligence, education
---


# Question
Title: Some questions regarding methods for solving pushdown automata problems
I have found some problems whose solving "patterns" appear quite recently, and I am not sure if the way I'm solving them is the most correct/efficient one:

For example, take this language:

$\\{w | w\in\\{a,b,c\\}^\* \text{ with }|w|\_a=|w|\_b \text{ or } |w|\_b=|w|\_c\\}$

The solution would be as follows, where $\\\\$$ is the bottom of the stack, and $\epsilon$ the empty string:

The top part is $|w|\_a=|w|\_b$ and the bottom is $|w|\_b=|w|\_c$

Taking the top part as an example (the other one is almost identical), what I do is to push $A$ whenever $a$ is read and $A$ is in the top of the stack, or remove $B$ if $B$ is in the top.

Whenever $b$ is read, I push $B$ if I don't find any $A$'s, or remove an $A$ if it's found.

Then, the rest of the characters without restrictions are read between those, leaving the stack alone.

The string would be accepted if input stops and the stack is empty.

I am not sure if this is the most graceful solution since I basically cram all possible cases in one state, though I think this works. This pattern is used basically whenever I find a restriction such as $|w|\_x=|w|\_y$

---

The other pattern I found that I'm unsure about is the following one, taking this language as an example:

**$\\{a^nb^m | n=3m\\}$**

In this one, I push one symbol into the pile only whenever 3 consecutive $a$'s are read, which will be then equal to $m$ and be consumed by reading $b$'s, accepting the string again if input is done and the stack is empty.

In these cases, I create a series of states where there is only one symbol pushed (when we enter into them), and the rest force to read a certain number of symbols without pushing of popping anything.

I am uncertain if this is the good way to do it. What if it were to be $n=56m$, would I need 55 sub-states?

# Answer
Your first solution is fine. I would not call this cramming into one state, it is kind of elegant to handle all this at the same place.

For your second problem, yes you can add 55 extra states. But also here you can use a single state instead, by coding that state into the topmost stack symbol. Simply have many stack symbols $A\_0$, $A\_1$ to $A\_{55}$ (or so) and replace $A\_i$ by $A\_{i+1}$ until 56 is reached.

In general *every* pushdown automaton can be replaced by one having at most two states.
> 1 votes

---
Tags: formal-languages, pushdown-automata
---


# Question
Title: Find the minimum subset of a set of numbers with product divisible by a given integer
The following problem was part of a local programming contest I attended..(I solved it via the obvious Brute Force solution)
I was wondering whether there was a cleaner Dynamic Programming solution.
**Problem Statement:**
You have an array $a$ of $n$ integers and an integer $k$. Your task is to find a subset $m$ of a where the following 2 conditions hold:
**1)** $\prod\limits\_{x\in m}x \equiv 0\mod k$.
**2)** Size of $m$ is minimal possible (size of $m \gt 0$).

**Constraints:**
$1 \le n \le 10^4$
$1 \le a\_i \le 10^9$
$2 \le k \le 10^9$
**Time Limit** = 3 seconds
**Memory Limit** = 256 MegaBytes

(I am a beginner in the concept of DP, so I am looking for a detailed explanation and if possible. some code. Thanks in advance :D)

# Answer
1. Compute all the prime factors of $k$. It would take $O(\sqrt{k})$ time $\approx$ $10^5$ time. Note that, there could be at most $10$ different prime factors of $k$ since considering the $10$ smallest prime numbers gives the product: $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 23 \cdot 29$ which exceeds $10^9$. Let us call the prime factors of $k$ as: $f\_{1}, \dotsc,f\_{10}$ with multiplicities $m\_{1}, \dotsc,m\_{10}$, respectively. The sum of multiplicities (or total number of prime factors) $\sum\_{i = 1}^{10}m\_{i}$ could be at most $30$ since $2^{30}$ exceeds $10^{9}$.
2. Now, you also need to factorize the numbers given in array $a$. However, you do not need to obtain all its factors. You just need to obtain the factors which are among $f\_{1},\dotsc,f\_{10}$ since other prime factors are irrelevant for $\prod\limits\_{x\in m}x \equiv 0\mod k$. Therefore, just check that if an array entry $a\[j\]$ is divisible by some factors $f\_{i}$ (obtained in step 2) and obtain its multiplicity in $a\[j\]$. Let $m\_{i}^{j}$ denote the multiplicity of factor $f\_{i}$ for an array entry $a\[j\]$. Computing all $m\_{i}^{j}$ would take at most $\sum\_{i = 1}^{10}m\_{i} \cdot n = 30 \cdot n$ time $\approx 10^{6}$ time.
3. Now, you just need a *Dynamic Programming* approch to obtain the minimum value on size of $m$. Let $A$ denote a matrix of dimension $(m\_{1}+1)$x $(m\_{2}+1)$ x $\dotsc$x $(m\_{10}+1)$ x $n$ such that an entry $A\[j\_{1}\]\[j\_{2}\] \dotsc\[j\_{10}\]\[t\]$ denote the minimum size value of $m$ such that $\prod\limits\_{x\in m}x \equiv 0\mod k'$ for $m \subseteq \\{a\_{1},\dotsc,a\_{t}\\}$ and $k' = \prod\_{i = 1}^{10} j\_{i} \cdot f\_{i}$. In otherwords, $k'$ is composed of all possible combinations of the factors $f\_{1}, \dotsc,f\_{10}$. Therefore $k'$ can take at most $(m\_{1}+1) \cdot (m\_{2}+1) \dotsc (m\_{10}+1) \approx 2^{10} \approx 10^{3}$ different values. This bound is based on the assumption that all $10$ factors are distinct. If all the factors are the same the we have $k' \leq 30$ since $2^{30}$ exceeds $10^9$. So I believe $k'$ would take at most $\approx 2 \cdot 2^{10} \approx 2 \cdot 10^3$ different values.

Now, assuming 1 based indexing for the matrix $A$, we define the DP steps as follows.

**The Main DP step:**

$$ A\[j\_{1}\]\[j\_{2}\]\dotsc\[j\_{10}\]\[t+1\] = \min \left\\{\begin{array}{lr} A\[j\_{1}\]\[j\_{2}\]\dotsc\[j\_{10}\]\[t\], & \textrm{do not pick $a\[t+1\]$}\\ 1 + A\[j\_{1}-m\_{1}^{t}\]\[j\_{2}-m\_{2}^{t}\]\dotsc\[j\_{10}-m\_{10}^{t}\]\[t\], & \textrm{pick $a\[t+1\]$}\\ \end{array}\right. $$

**The Base Step:**

$A\[j\_{1}\]\[j\_{2}\]\dotsc\[j\_{10}\]\[1\] = 1$ if $j\_{i} \leq m\_{i}^{1}$ for all $1 \leq i \leq 10$. And $A\[j\_{1}\]\[j\_{2}\]\dotsc\[j\_{10}\]\[1\] = \infty$ otherwise. Here $\infty$ means that it is not possible to satisfy the constraint $\prod\limits\_{x\in m}x \equiv 0\mod k'$ given $m \subseteq \\{a\_{1} \\}$ and $k' = \prod\_{i = 1}^{10} j\_{i} \cdot f\_{i}$.

**The Required Ouput:**

The output of the DP procedure would be the solution: $A\[m\_{1}\]\[m\_{2}\]\dotsc\[m\_{10}\]\[n\]$ which naturally denote the minimum size value of $m$ such that $\prod\limits\_{x\in m}x \equiv 0\mod k'$ for $m \subseteq \\{a\_{1},\dotsc,a\_{n}\\}$ and $k' = k = \prod\_{i = 1}^{10} m\_{i} \cdot f\_{i}$.

**Running Time Analysis of DP:**

The size of the matrix $A$ is $(\textrm{number of possible value of $k'$}) \cdot n \approx 2 \cdot 10^3 \cdot 10^4 \approx 2 \cdot 10^{7}$. Computing each entry takes 2 or 3 operations. Therefore total running time would be $\approx 6 \cdot 10^7$.

---

Thus the overall running time is $\approx 10^5 + 10^6 + 6 \cdot 10^ 7 \approx 10^8$. I have done the loose analysis, so it should be doable in 3 sec.

Total Space Complexity $\approx $ size of the matrix $A$ $\approx 2 \cdot 10^7$
> 1 votes

# Answer
I am the author of this problem and it was problem B in my contest. I have written an editorial here with the normal DP solution to get the 50 points and the coordinate compression DP which would get the 100 points.
> 1 votes

---
Tags: dynamic-programming, number-theory, programming-contest
---


# Question
Title: Which closure properties are always valid between regular, context-free and non context-free languages?
I am making a scheme that respresents some closure properties (union, intersection, complement and concatenation) for regular languages, context-free languages, decidable languages and RE languages. Below you can see my scheme.

I am trying to find all possible internal closure properties of these different languages that will always be valid. E.g., I know that $$\text{Regular language } \cup \text{ CFL } = \text{ CFL } $$

$$\text{Regular language } \cap \text{ CFL } = \text{ CFL } $$ $$\text{Regular language } ^\* \text{ CFL } = \text{ CFL } $$

What other internal properties are there between these languages?

# Answer
> 2 votes
I am afraid that there is no better general result than the obvious one.

Assume that $\mathcal K$ and $\mathcal L$ are two families of languages with $\mathcal K\subset \mathcal L$ such that $\mathcal L$ is closed under the operation $\circ$. Then for $K\in\mathcal K$ and $L\in \mathcal L$ we have $K\circ L\in \mathcal L$.

This is obvious, as both $K,L\in \mathcal L$. Usually we can choose simple examples that we can't do better. For instance, choose a "difficult" language in $\mathcal L$, so $L\in \mathcal L \setminus \mathcal K$. Then $L=\varnothing \cup L$, $L=\Sigma^\*\cap L$, and $L=\\{\lambda\\}\cdot L$ show that we cannot do better than $\mathcal L$.

---
Tags: regular-languages, context-free, closure-properties
---


# Question
Title: Solving the recursive equation $T(n)=T(k)+T(n-k-1)+O(n)$
The question is clear in the title. I am trying to solve this recursion as a part of showing that the worst case of quicksort algorithm occurs when $k=0$, but can't do it. I could do the following specific cases (by repeatedly using the same recursion):

1)$T(n)=T(n-1)+O(n)$
2)$T(n)=2T(\frac n2)+O(n)$

Can anybody please help me to solve this general case (or at least suggest some other way to prove that the worst case is $k=0$)?

**P.S.** I don't know Master's theorem, so I would appreciate a solution without using that (In case that is applicable here).

# Answer
> 2 votes
Consider the recurrence $$ T(n+1) = \max\_{0 \leq k \leq n} T(k) + T(n-k) + n+1, \qquad T(0) = 0, $$ which is one formalization of the worst-case running time of quicksort. Let us show by induction that the maximum is attained at $k = 0$ (or $k = n$). We will show this while at the same time showing that $T(n) = \frac{n(n+1)}{2}$.

The base case, $n=0$, is clear. Now suppose that $T(m) = \frac{m(m+1)}{2}$ for all $m \leq n$, and consider $T(n+1)$. The function $T(k)$ is convex on the interval $\[0,n\]$ (we extend it to real values using the same formula), and so the maximum of $T(k) + T(n-k)$ is attained at $k=0$ (or $k=n$). Therefore $$ T(n+1) = T(0) + T(n) + n+1 = \frac{n(n+1)}{2} + n+1 = \frac{(n+1)(n+2)}{2}. $$

Instead of arguing using convexity, we can also argue directly: $$ T(k) + T(n-k) = \frac{k(k+1) + (n-k)(n-k+1)}{2} = \frac{n(n+1)}{2}-k(n-k), $$ which is clearly maximized (uniquely) when $k = 0$ or $k = n$.

---
Tags: algorithms, sorting, recurrence-relation, recursion, quicksort
---


# Question
Title: Can one build a "mechanical" universal Turing machine?
This question connects different disciplines so it's awkward to choose a SE site for it, but I'll go with this one because here (I hope) the shared culture will make information transfer easier.

So computers as we know them use electricity and I don't know what other invisible things that I don't understand. I was wondering, is this a matter of efficiency, or of necessity? Can one achieve universal computation with just "moving parts"? Perhaps "Newtonian physics" is some term for this, although I guess it includes gravity which isn't really what I mean. You know, just good old solid pieces of matter moving around.

To get some picture of what I mean, here is a "LEGO Turing machine". I'm afraid that the big gray block on top uses electricity, but could one replace it with a "mechanical" thing, powered perhaps by rotating a piece? I have no idea how such things be designed, and the state transitions for a universal TM have to be fairly complicated, so I have no intuition for whether this is possible or not.

# Answer
> 40 votes
Sure. Electricity is unrelated to the model of computation. The only thing you can't actually build is the infinite tape, for obvious reasons. In this sense, anything that can be built is essentially equivalent to a deterministic finite automaton.

Here's a Turing Machine made of wood: https://www.youtube.com/watch?v=vo8izCKHiF0&ab\_channel=RichardRidel

# Answer
> 24 votes
Sure. Not only is it possible, the first design for a Turing-complete computer was purely mechanical. This was Charles Babbage's Analytical Engine. Babbage published its design in 1837, long before electricity was considered a practical source of energy, and even longer before electronics was even imagined.

The Analytical Engine was inspired by looms. Already in the 18th century there were looms that could be controlled by a punched tape which described the pattern to weave. Babbage had first designed a mechanical calculator, the Difference Engine, where a tape described mathematical operations. The Difference Engine could only perform prearranged calculations: it didn't have the ability to run arbitrary loops. The Analytical Engine could control the direction in which it processed its control tape, and since it also had conditional execution capabilities, it could perform arbitrary loops. The Engine had an internal memory where it could store data, which made it practically Turing-complete in the sense that an arbitrary program can be run on an engine given enough memory (which is the sense in which modern computers are Turing-complete). Everything was based on moving parts (wheels, pistons, etc.), and a complete description of the state of the engine would be a description of the position and orientation of these moving parts.

The Analytical Engine was never built. It was too complex and would have been too expensive and too slow to be worth the while. It didn't even have any direct influence on the design of the first electromechanical computers in the 1930s and 1940s, because their designers were not aware of the Analytical Engine. But it had indirect influence, partly through the work of Ada Lovelace. If Babbage was the first computer hardware designer, Lovelace was the first computer programmer. She realised that the Analytical Engine could not only make numerical calculations, but more generally could process data. Lovelace's contribution also fell into obscurity, but Babbage and Lovelace's work fostered an interest into the mathematics of computation.

Beyond looms, which translated instructions into cloth patterns, there were other mechanical engines existed with no or limited power to make numerical calculations before the first electronic computers. In particular, Herman Hollerith's mechanical tabulating machine could sort data and count records matching certain conditions; it was first used to process census data.

The progress of electronics, was what made general-purpose computers practical by the 1930s to 1940s. But the fundamental ideas of machine computation had been around for about a century. Electronics aren't the only way to design a computer, they're just (so far) the only economically viable way.

# Answer
> 3 votes
See: YouTube Matt Parker has made some small scale logic gates out of dominoes. Highly impractical, but theoretically, with enough time and space, one could build a functional computer that way. Apparently

# Answer
> 0 votes
All computers can be though of as "mechanical", broadly speaking, be they electronic, digital or analog, even "fluid" computers. What's interesting about **universal** Turing machines is that they allow us to consider machines as *encodings* in a systematic and general way. Not unlike the numbers they're supposed to compute.

That allows us to *virtualize* computers, which is arguably what makes them so interesting, both theoretically and in practice.

---
Tags: turing-machines, physics
---


title: Area preserving distance optimization

text:
# Question
Title: Area preserving distance optimization
I stumbled across the optimization problem described below and I am looking for how to approach it efficiently. I have the feeling that the problem at hand might be known, but I was not able to find its name or further information on it. So any help to find an efficient algorithm for its solution or a pointer to the name of the problem at hand would be very helpful.

Given $ n \times m $ matrix $ M $ of integers from $ \[0, w) $ and a set $ P $ of $ w $ points (i.e. tuples of indices in the matrix),
find a permutation $ M' $ of the values of $ M $, such that the global distance function $ f(M') = $ $ \sum\_{i=0}^{n-1}{ \sum\_{j=0}^{m-1} } { \left(i - x\left(P\[M'\[i, j\]\]\right)\right)^2 + \left(j - y\left(P\[M'\[i, j\]\]\right)\right)^2 } $ is minimal.

Explained in a different way, consider an image with $ n \times m $ pixels, where each pixel is of one of $ w $ distinct colors. We then want to rearrange the pixels such that all pixels of the same colors from a group around the seed point of the same color. We are allowed the swap the colors of pixels as long as the total number of pixels for each colors stays constant. Below you find an example of the resulting image from a random initial image with a hundred equally likely color as starting point located around randomly pixed seed points. The result was obtained by iteratively picking two points at random and swapping them if the global distance function after swapping is reduced. Doing this for millions of times approaches (at least a local) optimum depicted in the images. However this approach is rather slow for larger values of $ n $ and $ m $. So I am looking for a faster solution to obtain the result. Also a non-discrete solution where polygons would describe the final areas would be appreciated. I was also considering Voronoi tesselations (which can be computed much faster), however they do not work in my case due to the fixed area constraint (i.e. the colored sections should be of equal size in this example).

# Answer
This appears to be an instance of the assignment problem, where you are trying to match up the $nm$ cells of $M$ with the $nm$ cells of $M'$. For each place where $M\[i,j\]$ may get permuted to, you can compute the cost of that: namely, if it is permuted to $M'\[i',j'\]$, then its cost is $(i'-x P\[M\[i,j\]\])^2 + (j' - y P\[M\[i,j\]\])^2$. Then you can use standard algorithms for the assignment problem, such as the Hungarian algorithm. Whether this is practical or not may depend on how large $nm$ is. If it's not practical, you could instead try a heuristic, such as local search algorithm based on making swaps.
> 0 votes

---
Tags: algorithms, optimization
---


# Question
Title: Number of sentences and sentential forms generated by a grammar
In this question, I'm considering only "finite grammars". A finite grammar can only produce a finite number of distinct sentences. The following grammar is **finite** in my definition:

```
S         → AB
A         → B | a
B         → a | b

```

It can only generate the following finite number of sentences: `aa`, `ab`, `ba`, `bb`

On the other hand, the following grammar is **not finite**:

```
S         → AB
A         → AA | B | a
B         → a | b

```

Because it can create an infinite number of sentences: `aa`, `aaa`, `aaaa`, `aaaaa`, ...

Now to the actual question. Suppose the following finite grammar:

```
S         → variable = math_expr
variable  → a | b | c
math_expr → INT | function
function  → func_1() | func_2(INT, INT, INT, INT)
INT       → 1 | 2 | 3 | 4 | 5

```

I want to know if there is some kind of formula that calculate the number of **sentences** and **sentential forms** that can be generated by a finite grammar.

Example of sentences: `b = func_2(2,4,3,3)`, `a = func_1()`

Example of sentential forms: `b = func_2(2,2,INT,INT)`, `c = math_expr`, `S`

At the moment, I am able to know the number of sentences and sentential forms by applying a Breadth-First Search (BFS) starting from the `S` node.

However, because I'm working with search in program synthesis, it would be great to know the size of the domain without the need of applying an exhaustive search on it.

**Question: How can I find the number of sentences and sentential forms given only an arbitrary finite grammar?**

For the first finite grammar I showed here, the answer is easy to calculate by hand:

Sentences: `aa`, `ab`, `ba`, `bb`
Sentential forms: `S`, `AB`, `BB`, `aB`, `bB`, `Aa`, `Ab`

So the final answer would be 4 + 7 = `11`

However, for the second finite grammar I showed, it is not that easy to calculate it.

**PS.**: In my original problem, I am working with program synthesis with a Domain Specific Language (DSL). I tagged CFG with the hope that the same applies, granted I'm not 100% sure.

# Answer
> 2 votes
If the context-free grammar is unambiguous, you can count the number of sentences it generates in a linear scan with a carefully chosen order.

I'll assume we have removed all useless symbols and cycles from the grammar. If it is finite and free of useless symbols and cycles, then it should not contain any recursion.

Let $N(A)$ denote the number of sentences that can be constructed starting from nonterminal $A$, i.e., $N(A) = |L(A)|$. If the grammar is unambiguous and has no recursion, you can compute $N(A)$ for each nonterminal as follows. Construct a dependency graph with one vertex per nonterminal, and an edge $A \to B$ whenever the grammar contains a rule $B ::= \cdots A \cdots$, i.e., a rule with $B$ on the left-hand side and $A$ on the right-hand side. If the grammar has no recursion, then this is a dag. Visit the vertices of this graph in topologically sorted order. Then it is easy to compute the number of sentences: for example, if we have the rule $A ::= BaC | DE$, then we have

$$N(A) = N(BaC) + N(DE) = N(B) N(a) N(C) + N(D) N(E).$$

That's an example, but you can do the same for any number of alternatives on the right-hand side and any string of symbols in each alternative. Note that we have the base case $N(a) = 1$, for any terminal $a$.

I expect this can be adjusted to count the number of sentential forms as well, but I haven't tried to work out the details.

This relies crucially on the grammar to be unambiguous. If the grammar is ambiguous, I'm not sure whether there is any efficient algorithm -- I just don't know.

For unambiguous grammars, see also https://en.wikipedia.org/wiki/Chomsky%E2%80%93Sch%C3%BCtzenberger\_enumeration\_theorem, which shows how to count the number of sentences of a particular length, even if the grammar is not finite.

---
Tags: formal-languages, context-free, search-problem, breadth-first-search, program-synthesis
---


# Question
Title: Algorithm favours CPU bound or I/O bound processes
Some scheduling algorithms favour CPU bound processes while others favour I/O bound processes.
Which algorithm favours which type of process?
My answers:

1. **SJF** favours I/O bound processes.
*Explanation*: Short CPU burst processes(I/O bound processes) are given higher priority.
2. **SRTF** favours I/O bound processes.
*Explanation*: Same as SJF
3. **Round Robin**? *Not able to decide categorically*
4. **LRTF** favours CPU bound processes.
*Explanation*: Large CPU burst processes(CPU bound) are given higher priority.
5. **HRRN**? *Not able to decide categorically*
6. **Multilevel feedback Queue** favours I/O bound processes.
*Explanation*: Short CPU burst processes(I/O bound processes) are given higher priority. While processes that have large CPU bursts(CPU bound) will slowly have decrement in priority. A process in lower priority queue can only execute when higher priority queues are empty. A process running in a lower priority queue is interrupted by a process arriving in a higher priority queue.
7. **Multilevel Queue** favours I/O bound processes.
*Explanation*: Similar to multilevel feedback.
8. **Priority Scheduling**? *Not able to decide categorically*
9. **FCFS**? *Not able to decide categorically*

Please verify above answers and explanations.
Correct me if I'm wrong somewhere and provide answers with explanation for the omitted ones.

# Answer
First of all, let me clarify that the CPU Burst Time of a process has no relation with being a CPU or I/O bound process. A CPU-bound process is one that spends most of its execution time at CPU and an I/O-bound process is one that spends most of its execution time at an I/O device. Therefore, a process having a small CPU burst time can also be a CPU-bound process. Similarly, a process having a very large CPU burst time can still be I/O bound.

For example, consider a process A having CPU burst time of 1ms and I/O burst time of 5 ms. It is clearly an I/O-bound process. And a process B having a CPU burst time of 10ms and I/O burst time of 5 ms is clearly a CPU-bound process. But if we consider SJF or SRTF algorithms, they will definitely prefer process A over B inspite of A being I/O bound and B being CPU bound because A has a lower CPU burst time than that of B. Thus, it is incorrect to think that SJF favors I/O bound processes.

But, as I/O bound processes spend more time doing I/O than CPU, they will be sent to the waiting state more often. (It has nothing to do with CPU scheduling as CPU scheduling is handled by Short Term Scheduler and waiting state is handle by Medium Term Scheduler). Once a process in waiting finishes its I/O, it now depends on the CPU Scheduler. Now, if any preemptive algorithm is being used, there are chances that this process will get execution (depending on the criteria). But if any non-preemptive algorithm is being used, this process won't get execution until the currently executing process is finished. So, we can say that non-preemptive algorithms (kind of) favor CPU-bound processes (as they spend more time at the CPU, so they have to face lower chances of waiting).
> 1 votes

---
Tags: operating-systems, scheduling, process-scheduling
---


# Question
Title: Trying to remove ϵ rules from a formal grammar resulted in L(G) ≠ L(G')
I am trying to remove ϵ rules from the following grammar (after applying the remove redundant symbols algorithm): $G = (\\{S,A,B,C\\},\\{0,1\\},P,S)$, where the productions are

\begin{align} &S \to AB \mid C \\ & A \to 0A1 \mid \epsilon \\ &B \to 0B \mid 0 \\ &C \to 0C0 \mid B \end{align}

The result of applying the remove ϵ rules algorithm is:

\begin{align} &S \to B \mid C \mid AB \\ &A \to 0A1 \\ &B \to 0B \mid 0 \\ &C \to 0C0 \mid B \end{align}

but then, when I re-apply the remove redundant symbols algorithm (as I should do) I get:

\begin{align} &S\to B \mid C \\ &B \to 0B \mid 0 \\ &C \to 0C0 \mid B \end{align}

(as $A \Rightarrow^\*$ will never result in a terminal word)

The problem is, that $010$ is generated by the original grammar but not by the latter grammar.

in fact, not a single word that contains 1 in it belongs to the latter grammar, as 1 could only have been achieved via $A$!

What have I done wrong? Why are the two grammars producing different languages? They are supposed to be the same.

# Answer
This question shows the pitfalls of applying algorithms without understanding how they work. There is absolutely no problem with applying an algorithm mechanically, but in that case, you should make sure that the algorithm you are applying is 100% correct, and that you are following it 100% accurately.

How does the $\epsilon$-removal work? Suppose that we want to remove the production $A \to \epsilon$. How can this production be used in a derivation? Whenever $A$ appears on the right-hand side of a production, we can remove it by applying $A\to\epsilon$. Hence, in order to get rid of the production $A\to\epsilon$, we simply replace each production $X \to \alpha$ by all possible productions obtained by removing occurrences of $A$ in $\alpha$. (This may result in productions of the form $X \to \epsilon$, which we need to handle separately.)

In your case, this means that we need to augment the production $A \to 0A1$ with the production $A \to 01$ obtained by erasing $A$ on the right-hand side.

What is a good way of finding such bugs? You describe three grammars: the original one, the one obtained after removing $\epsilon$ productions, and the final one obtained by removing redundant symbols. The first one generates $010$, the last one doesn't. The first step is to check which of the two transformations introduced the mistake, and you can do that by checking whether the second grammar generates $010$.

It turns out that the second grammar doesn't generate $010$. In order to understand what went wrong, you can take a derivation of $010$ in the first grammar, and see why it cannot be reproduced in the second grammar. One such derivation is $S \to AB \to 0A1B \to 0A10 \to 010$. In the second grammar, all but the last steps are still available, so the problem lies with the production $A \to \epsilon$, which the second grammar isn't able to simulate.
> 4 votes

# Answer
You already lost the $010$ word when you've removed the $A\to \epsilon$ rule. In $G'$, which is the grammar you got by removing $\epsilon$-rules, you also need to add the $A \to 01$ rule.
> 2 votes

---
Tags: algorithms, context-free, formal-grammars, normal-forms
---


title: Longest path on a full tree

text:
# Question
Title: Longest path on a full tree
Given a full tree $\ T = (V, E, w) $ I need to find the path with maximum length from root $\\ s $ to any of the leaves.

I was thinking I could use some sort of BFS. Because I'm looking for maximum length path, I must go through all of the edges of the tree and I will start at the vertex $\ s $. So I'll use a dictionary $\ lengths = \\{\\} $ where each vertex in the $\ lengths $ dictionary is a key and its value is the total length from $\ s $ to that vertex. Then I'll just choose a the leaf with the highest value. From what I've seen online the solution to the problem is actually using Shortest path for DAG and multiply lengths by $\ -1 $ and the multiply back once algorithm finish. So not sure if my solution is ok?

Thanks,

EDIT: added proposed solution

```
 weights = {}

 def max_path(root, w):
     if root in weights:
        return weights[root]
     else:
        weights[root] = w + max(max_path(root.leftchild, root.weight), root.rightchild, root.weight))

```

# Answer
> 2 votes
Your solution will work and, if implemented properly, will require $O(n)$ time where $n$ is the number of vertices of $T$ (to achieve this complexity you cannot just use a BST or a hashmap as a dictionary though). Notice that you're using the fact that there is a **unique** path from the root of $T$ to each of the leaves.

Also running any shortest-path algorithm for DAGs on the weighted version of $T$ in which each edge $e$ weighs $-w(e)$ will work in $O(n)$ time. However this is overcomplicated as it requires finding a topological order of $T$ (which requires a DFS). In other words you are not taking advantege of the fact that $T$ is a tree and not just a generic DAG.

A quick way to solve this problem in $O(n)$ time is performing a depth first search starting from the root of $T$ while keeping track of the weighted depth $d$ of the current vertex. Whenever you traverse an edge $e$ "forward" (i.e., from a vertex to one of its children) you increase $d$ by $w(e)$, whenever you traverse an edge $e$ "backwards" (from a vertex to its parent) you decrease $d$ by $w(e)$. It is very easy to implement this recursively.

---
Tags: dynamic-programming
---


# Question
Title: Solving $T(n)=3T\bigl(\bigl\lfloor \frac{n}{3}\bigr\rfloor\bigr) +2n\log n$ without the Master Theorem
I want to solve $$T(n)=3T\bigl(\bigl\lfloor \frac{n}{3}\bigr\rfloor\bigr) +2n\log n,$$ with base case $T(n) = 1$ if $n \leq 1$.

I know that the solution is(with the help of the Master Theorem) $$\Theta(n\*log^2(n))$$ I tried without the Master theorem and witht the help of the substuition method I got the following expression $$T(n)=n+2\*n\*\sum\_{k=0}^{log\_{3}(n)-1}log(\frac{n}{3^k})$$

How can I convert this expression into a valid $\Theta(n\*log^2(n))$ expression ?

# Answer
> 1 votes
Let's suppose $n=3^k$. Then we have: $$T(n)=3^kT(1)+2n\log \frac{n^k}{3^{k-1}\cdots3^0}=n+2n\log 3^{k^2-\frac{k(k-1)}{2}} =\\ =n+2n\log n \cdot \frac{\log\_3 n+1}{2} $$ Hope it helps.

# Answer
> 1 votes
T(n)=3T(⌊n3⌋)+2nlogn By substitution method

---
Tags: time-complexity, recursion, master-theorem
---


# Question
Title: Is it possible to generate a better random number generator algorithm from an algorithm that use N computers with one that uses N+1 computers?
Is it possible to generate a better random number generator algorithm from an algorithm that use N number of computers with an algorithm that uses N+1 number of computers? I use the word computer here, but I believe you can use the word processor instead as not all computers are single-processor computers although I am not sure if it makes any difference as the answer would be similar I think. The algorithm can be any algorithm, but for the sake of simplicity let's say the fastest one we know, and if you can't generalize for N, let's say N = 1.

# Answer
The fastest random number algorithm that we know is

```
0

```

It is not very random, but it is very fast and therefore the best according to your definition. Maybe you need to rethink your definition. Maybe you should rethink the idea that there might be a “best” algorithm.
> 1 votes

---
Tags: algorithms, complexity-theory, performance, high-performance-computing
---


# Question
Title: Question regarding the proof that quadratic probing always finds an empty slot if the table is less than half full
to prove this statement I assume the probing function as: $$h(i,x)=h'(x)+i^2 \text{ mod t} $$ And for $0\leq i,j \< \frac{t}{2}$; $i\neq j; t \text{ prime}$: $$h(i,x) = h(j,x)$$ This results into $$(i+j)(i-j) \text{ mod t} = 0$$ Which is a contradiction as either $i+j=0$, $i-j =0$ or $(i+j)(i-j)=t$, and because i and j are chosen to be different and positive the first two can not be. Further t is prime and thus can not be written as a factor.

That is what I got so far. Judging by the Wikipedia entry this should suffice to prove the statement, but I fail to see why this actually shows that it always finds an empty slot. In particular because the fact that i and j are smaller than t/2 is not used at all.

Thank your for your input!

# Answer
> 1 votes
Suppose that $t=11$, $i=5$, $j=6$. Then $i+j \bmod t = 0$, and there is no contradiction. However, in this example $i \< t/2$ while $j \> t/2$. This sort of example cannot happen if $i,j \< t/2$, since then $i+j \< t$.

# Answer
> 0 votes
Probing doesn’t find an empty slot if all probed slots are full. If less than half the slots are full, and half the slots or more are probed, then you are probing more than the full slots, so the probed slots cannot all be full.

---
Tags: hash, hashing
---


title: Is vmlinux a virtual machine?

text:
# Question
Title: Is vmlinux a virtual machine?
From Wikipedia,

> On Linux systems, vmlinux is a statically linked executable file that contains the Linux kernel

Does that mean vmlinux is a virtual machine that runs Linux? I am really confused.

# Answer
`vmlinux` is the executable file that is generated when building the Linux kernel. This isn't a normal executable file that would be generated as a result of compiling a program using, say, gcc.

As Wikipedia suggests, this executable needs to be further processed to be made bootable, but this is the essentially the executable image of the kernel.

> Does that mean vmlinux is a virtual machine that runs Linux?

No, the 'vm' here stands for 'virtual memory'. From Wikipedia,

> With the development of virtual memory, kernels that supported this feature were given the vm- prefix to differentiate them. The name vmlinux is a mutation of vmunix.

What is this `vmlinux` executable good for? Well, for starters, it can be made bootable and then booted on a physical computer.

You can also use this executable to run a virtual machine using qemu. Then, you can debug the kernel that is running in the virtual machine using gdb.
> 1 votes

---
Tags: operating-systems, os-kernel
---


# Question
Title: What is the theoretical minimum number of "switches" requried to implement a Turing-complete CPU?
Where "switches" are the basic abstract building blocks for logic gates: vacuum tubes, transistors, magnetic relays, or whatever. We're not counting any switches in the RAM or tape drive because that's a separate component.

I'm not sure if the exact number is known or provable, but an upper bound could be proven by implementing one or pointing to a known implementation.

I am assuming a binary computer with empty memory. You can, of course, load a program to make it work, but said program must be finite in length. Something like Wolfram's (2, 3) UTM, which requires the whole unbounded tape to be initialized, is out.

The first commercial microprocessor was the Intel 4004, with a transistor count of 2,250 (not sure if that's exact), so that's an upper bound.

But that already had a 4-bit data width and multiple opcodes, probably much more than is required for the theoretical minimum CPU. I have heard of 1- and 2-bit CPUs and one-instruction set architectures like Subleq, so I think we can do a lot better than the 4004. I suspect the true answer is \< 1000 switches, but I'm not sure.

---

Update: I discovered "Cedric", the first working carbon-nanotube CPU, which used just 178 transistors. It used a variant of Subneg, another Turing-complete instruction similar to Subleq.

178 is my new upper bound.

# Answer
The Rule 110 cellular automaton is apparently Turing-complete. If you're not counting the cost of memory, I imagine a circuit that applies the Rule 110 evolution rules could be implemented with very few switches.

See also https://softwareengineering.stackexchange.com/q/230538/34181.
> 1 votes

---
Tags: automata, computer-architecture, cpu, turing-completeness
---


# Question
Title: Quickly identify changes in connectivity
Given an undirected graph with at least one path connecting $u, v$, and a sequence of edges to be removed: $e\_1, e\_2, \dots$, I would like to quickly identify the point at which $u$ will be separated from $v$. Clearly this could be done by doing a full path search after each removed edge, but this is very expensive.

Is there a faster algorithm? (This is this question which asks about a related but more general and difficult situation, but it has gone unanswered.)

# Answer
You can work your way backwards. Suppose the edges being removed are $e\_1,\ldots,e\_\ell$, and the rest of the edges form a set $E$. Start by determining the connected components induced by $E$, using a disjoint sets data structure. Now add the edges $e\_\ell,\ldots,e\_1$ in that order, updating the disjoint sets data structure, until $u$ and $v$ belong to the same connected component. The last edge encountered in this way is the one you seek.
> 4 votes

---
Tags: graphs
---


title: Cyclic tour minimizing total weight

text:
# Question
Title: Cyclic tour minimizing total weight
I asked the following question on math.se but it wasn't really answered so moved it over here as I feel it's more relevant.

I saw the question below on an old stack exchange question when looking to understand NP-completeness. At first, I thought I understood it so I gave it a go but ended up more confused than before (I'm a maths student and computational complexity is my first foray into CS and I'm struggling to get to grips with it).

Question is as below:

> Given as inputs integers $a, b$ and $c(i,j)$ for each $i,j \leq a$, decide if there is a permutation $\tau$ of $\\{1,2,\dots,a\\}$ such that
>
> $$ c(\tau(a),\tau(1))+\sum\_{i=1}^{a-1}c((\tau(i),\tau(i+1))\leq b $$
>
> Prove this problem is NP-complete. Hint: find a reduction from the Hamiltonian circuit decision problem (given a graph, decide whether it contains a Hamiltonian circuit).

It seems very similar to the decision version of TSP (where given a set of cities with the distances between each pair of cities, and a length $k$, does there exist a circuit connecting all cities of length less than $k$). I've read the proof for NP-completeness of TSP and I feel like I understand the reduction from Hamiltonian circuit decision problem to TSP, but I can't get it to translate into a reduction from HC to this problem.

My understanding to compare this to TSP, is that $a$ is the number of cities, each $c(i,j)$ represents the distance between city $i$ and $j$.

My (fairly poor) attempt at this reduction is as follows;

The problem is clearly in NP as we can non-deterministically "guess" a permutation and calculate the given sum and verify that it's at most $b$ in polynomial time.

Then, given a graph $G=\langle V,E\rangle$ where there are $a$ vertices, say $1,2,\ldots,a$, and $b$ edges of length $c(i,j)$, where $i \neq j$ and $i,j\leq a$, construct the completion of $G'$ of $G$ and a weight function that assigns any edge of $G'$ a 1 if the edge is present in $G$ and 2 if not. This can be computed in polynomial time.

Then if $G$ contains a Hamiltonian circuit (consisting of $b$ edges), this path has weight at most $b$ in $G'$ and so the sum of the lengths of this path is at most $b$ and so the permutation corresponding to the order of this path satisfies the original decision problem for these numbers $a,b$ and $c(i,j)$.

Conversely, if given the numbers $a,b$ and $c(i,j)$ and a permutation $\tau$ that satisfy the problem the associated graph G contains a path starting at $\tau(a)$ and finishing at $\tau(b)$. Thus G has a Hamiltonian circuit.

Thus HC reduces to this problem and hence it is NP-hard and so NP-complete.

I can tell it's wrong but I'm not sure how to properly describe a function relating to Hamiltonian circuits and lengths into weights in $G'$.

Any advice and or pointers would be much appreciated.

# Answer
The problem you describe is exactly asymmetric TSP. As your reduction shows, asymmetric TSP generalizes the Hamiltonian circuit problem, which is known to be NP-hard.

Usually we consider metric versions of TSP, in which the triangle inequality $c(i,k) \leq c(i,j) + c(j,k)$ holds, and often the TSP instance is symmetric, $c(i,j) = c(j,i)$. Your reduction shows that (symmetric) metric TSP is also NP-complete, since the cost function you construct is symmetric and satisfies the triangle inequality.
> 1 votes

---
Tags: np-complete, np-hard, decision-problem, traveling-salesman, hamiltonian-circuit
---


# Question
Title: Partitioning a graph into subgraphs with overlapping nodes
I'd like to partition a graph into subgraphs with overlapping nodes.

To do a simple partition into two, I could use `kernighan_lin_bisection` algorithm available in networkx package.

```
import networkx as nx
from networkx.algorithms.community.kernighan_lin import kernighan_lin_bisection

if __name__ == '__main__':
     G = nx.gnm_random_graph(n=30, m=55, seed=1)
     A, B = kernighan_lin_bisection(G)

```

For creating more than two partitions, it is mentioned here, https://stackoverflow.com/questions/63357626/networkx-kernighan-lin-multipartition, that `metis` can be used. However, I came across an old post that mentions partitioning with overlapping nodes is not supported in metis. I would like to ask for suggestions on references to algorithms/packages that support partitioning with overlaps.

EDIT: I'd like to partition into subgraphs with \>= 4 overlapping vertices. e.g. in the subgraphs presented here . i.e.

> for any cluster C1 there must be a cluster C2 such that |C1∩C2|≥4

The number of overlap nodes (overlap size) is 3 and 1. But I want the overlap size to be \>=4 overlap nodes.

EDIT 2:

> For example, why not simply pick another pure-yellow vertex randomly and add that to the green set, so that yellow and green overlap by exactly 4? And why not pick the remaining 3 pure-yellow vertices and add them to the blue set, so that yellow and blue overlap by exactly 4?

Yes, I could do this. I'm trying the óverlapping communities algorithms available in CDLIB to do the same.

```
 import networkx as nx
 from cdlib import algorithms

if __name__ == '__main__':

    g = nx.karate_club_graph()

    coms = algorithms.angel(g, threshold=4, min_community_size=10)
    print(coms.method_name)
    print(coms.method_parameters)  # Clustering parameters)
    print(coms.communities)
    print(coms.overlap)
    print(coms.node_coverage)

```

Output:

```
ANGEL
{'threshold': 4, 'min_community_size': 10}
[[14, 15, 18, 20, 22, 23, 27, 29, 30, 31, 32, 8], [1, 12, 13, 17, 19, 2, 21, 3, 7, 8], [14, 15, 18, 2, 20, 22, 30, 31, 33, 8]]
True
0.6470588235294118

```

From the communities returned, I understand 1 and 3 have an overlap of 4 nodes but 2 and 3 or 1 and 3 don't have an overlap size of 4 nodes. It is not clear to me how the overlap threshold (4 overlaps) has to be specified here `algorithms. angel(g, threshold=4, min_community_size=10)`. Since it is mentioned in the comment below that the "overlap is upper bounded" , I tried setting threshold=4 here. However, from the documentation available for `angel`

> :param threshold: merging threshold in \[0,1\].

I am not sure how to translate the 4 overlaps to the value that has to be set between the bounds \[0, 1\]. Could someone please clarify? If there are suggestions on the other overlapping communities algorithms that I could try from CDLIB, I'd be happy to try. I also had a look at the percolation methods implemented in the kclique algorithm of CDLIB. Unfortunately, I am not sure how to specify the overlap threshold here.

I'm really sorry for not being clear, I'm new to this field and I am learning from here.

# Answer
> 4 votes
I never heard of any algorithm with the constraint of having an overlap *between communities* larger than a given threshold (4 here).

But I suggest the following: **turn your graph into its line graph, use a classical node partitioning method that gives a hierarchy of communities, and then choose a partition that fits your requirements.**

More details:

* the line graph is the graph in which the nodes are the links of your original graph, and these nodes are linked together if corresponding links have an extremity in common, see wikipedia on line graph.
* classical community detection algorithms partition nodes into disjoint sets; doing so on the line graph will produce a partition of the edge set, with some nodes in several communities (overlap).
* many classical community detection algorithms actually produce a hierarchical decomposition, often encoded as a dendrogram, *i.e.* a tree of communities, sub-communities, sub-sub-communities, and so on, see wikipedia on dedrograms.
* a partition into communities then is a choice of a place to *cut* this tree, wherever it fits your needs; for instance, one may maximize a quality function and a scale parameter, see *e.g.* Post-Processing Hierarchical Community Structures: Quality Improvements and Multi-scale View
* therefore you may choose a cut maximizing a quality function while satisfying your requirement; you may for instance start with the optimal partition regarding the quality function, and then move the cut to fit your overlap requirement.

Good luck, please keep us informed of any progress :)

# Answer
> 2 votes
Depends what you want to do with the "partition with overlapping nodes".

---
Tags: algorithms, graphs, optimization, partitions, network-analysis
---


# Question
Title: I'm trying to understand why every language has an infinite number of TMs that accept it
I found the following answer:

> $L\_{17} = \\{ \langle M \rangle \mid \text{$M$ is a TM, and $M$ is the only TM that accepts $L(M)$} \\}$.
>
> * **R.** This is the empty set, since every language has an infinite number of TMs that accept it.

As I know number of TMs is $\aleph\_0$ and number of languages is $2^{\aleph\_0}$, so how can it be possible that "every language has an infinite number of TMs that accept it"?

source of the solution here

# Answer
The correct version of the claim states that every *computable* language is accepted by infinitely many Turing machines.

Indeed, if $L$ is computable, then there is a Turing machine $T$ that accepts it. Let $T\_n$ be $T$ together with $n$ unreachable states. Then $T\_n$ also accepts $L$, and the machines $T\_n$ are all different from one another.
> 30 votes

# Answer
Intuitively?

Do you know programming? Can you think of a way of making infinitely many versions of the same program?

Say, adding a function `foo` that you never call creates a different program, but it still does the same thing.
> 19 votes

# Answer
Note that the quoted sentence should be "R. This is the empty set, since every $\text{L(M)}$ has an infinite number of TMs that accept it."

The other answers are correct, and there are other ways to prove that every language that is accepted by some TM, is actually accepted by $\aleph\_0$ distinct TMs. However, following the last sentence in the question, I believe what may be counterintuitive to you is that there are also $\aleph\_0$ distinct languages that are accepted by means of TMs. So the question is how come there are $\aleph\_0$ TMs in total?

Maybe what you're missing is the following claim: the union of countably many countable sets is countable. See here.
> 6 votes

# Answer
Just put a *for* loop in there. It goes around n times before doing the calculation. There is no limit to the size of n.
> 5 votes

# Answer
The quoted claim is very unfortunate. First because it is written in a clumsy way which makes it wrong as Yuval wrote. Two because it is a huge hammer to smash a tiny nut - all you need is to show that any TM can be modified slightly (usually by making it a tiny bit less efficient) while recognising the same language.
> 2 votes

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


# Question
Title: (Formal) Proofs of Node Centrality Properties
Despite there being relatively frequent discourse regarding the usage and effectiveness of various node centralities when analysing the influential spreaders of a graph, I have thus far struggled to find any formal treatments of such discussions. For example, betweeness centrality is theoretically well-defined and is popular in practice for finding influential spreading members, but is there any proof of its effectiveness in this capacity (e.g. compared to any other centrality)? All the arguments I have witnessed thus far have been largely simulation/virtual-experiment based. My question is: is there anywhere I can more formal treatments of this subject matter?

Whilst I am generally curious to see if possible formal discussions around graph analysis efficacy could exist, I have my suspicions as to why this is not already the case given that formal comparisons of this nature could be infeasible... but perhaps this is not true?

Example papers/articles: https://www.nature.com/articles/nphys1746.pdf https://www.nature.com/articles/srep19307.pdf https://cambridge-intelligence.com/keylines-faqs-social-network-analysis/

# Answer
> 2 votes
There are many papers dealing with the algorithmic aspects of these measures, with formal proofs, complexity analysis, and so on. However, I understand that this is not really what you are looking for.

There are **only few *formal* works on their actual relevance** for describing features of interest in practice.

**Pagerank is a notable exception**, though. Its connections to random walks, Markov chains, and matrices, as well as its wide use and mere features, make it a great metric for formal analysis. I particularly recommend the book *Google's PageRank and Beyond: The Science of Search Engine Rankings*, by Amy N. Langville and Carl D. Meyer. It deals with many aspects, putting together practical concerns as well as theoretical analysis.

**Node degree distribution is another important exception**, although one may consider it too basic to be a valid answer here. Still, there are many formal works showing the importance of high degree nodes in random graphs that model real-world complex networks. See for instance our survey entitled *Impact of random failures and attacks on Poisson and power-law random networks*.

---
Tags: graphs, social-networks, network-analysis
---


# Question
Title: Sample a scale free subnet from random network
I already have a network which is like random complex network. Is there any way I can delete some of nodes and reduce the network into a scale-free network?

I notice there are some methods that can sample a scale-free subnet from a scale-free network. But I have not found anyone sampled a scale-free subnet from a random network.

# Answer
> 1 votes
In order to do this, **you *need* high degree nodes in your initial network**: since you do not add anything, degree may only decrease, and you want high degree nodes in the end.

Now, assume your initial random network indeed has high degree nodes. Since it is random, **choosing random links in it will often lead to high-degree extremities**. Indeed, the probability to pick a degree $k$ extremity when you choose a link at random is proportional to $k$.

This property underlies the works conducted to estimate bias in internet measurements. Several works show that **power-law networks may indeed be obtained from initially random networks**, for instance by taking a BFS tree.

See *e.g.* On the Bias of Traceroute Sampling; or, Power-law Degree Distributions in Regular Graphs for a formal analysis published in STOC and Journal of the ACM, as well as Relevance of Massively Distributed Explorations of the Internet Topology: Qualitative Results for an experimental work published in INFOCOM and Journal of Computer Networks.

---
Tags: network-topology, network-analysis
---


# Question
Title: Is there a human-friendly version of the Pumping-Lemma?
I found this on Wikipedia and I'm confused by the parenthesis in the notation not that it doesn't make sense to me but is there a more natural human version? And im generally confused about all the different notations surrounding logic and quantifier.

$(\forall L \subseteq \Sigma^\*)(regular(l)\Rightarrow((\exists p\geq1)((\forall w\in L)$ $((|w|\geq p)\Rightarrow((\exists x,y,z\in \Sigma^\ast )(w = xyz \land(|y|\geq 1\land|xy|\leq p \land(\forall n\geq 0)(xy^nz\in L))))))))$

# Answer
> 2 votes
I agree that the way the lemma is written is confusing, a more *friendly way* to write the lemma is as follows (I have added an intuitive explanation for the conditions appearing in the lemma, hoping that it is more *human readable* now):

**The Pumping Lemma:** for every regular language $L\subseteq \Sigma^\*$, there is a positive pumping constant $p$ such that for every word $w\in L$ with $|w|\geq p$ (that is, for every *long enough* word in the language $L$ ), the following holds. There exists a partition of $w$ into three words over $\Sigma$, $w = xyz$, such that:

1. $|xy|\leq p$ (that is, $y$ lies in the prefix of length $p$ of $w$).
2. $|y| \> 0$ (that is, $y$ is nonempty).
3. $xy^iz\in L$, for every $i\geq 0$ (that is, if you take the word $w$ and pump the infix $y$ in $w$, $i$ times, the word $w$ remains in the language $L$).

---
Tags: pumping-lemma
---


title: Find language and regular expression

text:
# Question
Title: Find language and regular expression
I don't know how to find the Language and the regular expression for each one. there are any special method for those kind of question?

# Answer
> 2 votes
Here are the first few words accepted by the DFA on the right: $$ 0 \\ 00 \\ 000,010 \\ 0000,0010,0100,0110 \\ 00000,00010,00100,00110,01000,01010,01100,01110 $$ The DFA on the left accepts a subset of these words. Here are the words it does *not* accept: $$ 010 \\ 0010,0100 \\ 00010,00100,01000,01110 $$ Perhaps you can use these lists to obtain a guess on the languages accepted by the DFAs. You can then try to see how the structure of the DFA corresponds to the language it accepts. For example, what do the states $D$ and $q\_3$ signify? How do you reach them? How do you get to the accepting states $B$ and $q\_1$?

# Answer
> 0 votes
You almost got it Right in the comments, so I will give you the last push along with one way to think about it.

* In the right automaton: the language of the automaton is simply $0\cdot L(q\_1)$, where $L(q\_1)$ is the set of words that can be accepted from $q\_1$. Its not hard to see that a word $w$ is accepted from $q\_1$ iff it $w$ is the empty word $\epsilon$, or $w$ ends with 0 (indeed, consider the component of the states $\\{q\_1, q\_2\\}$, reading 0 always leads to $q\_1$, and reading $1$ always leads to $q\_2$). Thus, $L(q\_1) = \\{ w: \text{ $w= \epsilon$ or $w$ ends with 0}\\}$, and therefore the language of the automaton is given by the regex $0\cdot \[\epsilon + (0+1)^\* \cdot 0\]$. The regex that you suggested is almost correct: it does not care about whether the word has to end with 0
* In the left automaton: the language is simply $0\cdot L(B)$, where $L(B)$ is the set of words that can be accepted from $B$. Since $B$ is the only accepting state, a word is accepted from $B$ if its run from $B$ ends also in $B$. To get from $B$ to $B$, you have to read a word that contains only 0s, or to read a word of the form $( u\cdot u \cdot 0^\*)^\*$, where $u$ is a word that has exactly one letter that equals 1 and $u$ ends with 1. Indeed, you get to $C$ upon reading $u$ from $B$. Also you get to $A$ upon reading $u$ from $C$, and once you're in $A$, you have to read 0s to move back to $B$ and stay there. So $L(B)$ is given by the regex $r = 0^\* + ( 0^\*1\cdot 0^\*1\cdot 0^\*)^\*$. Hence, the regex of the automaton is given by $0\cdot r = 0 \cdot \[0^\* + ( 0^\*1\cdot 0^\*1\cdot 0^\*)^\*\]$. Note that maybe one can suggest a simpler regex (I leave that to you), yet this one goes well with the above explanation. Also, your regex assumes that when we move to $B$ for the first time, we have to see immediately 1. Finally, note that $L(B)$ is actually the set of words $w$ such that $\\#\_1(w)$ is a multiple of two, and 0 appears immediately after every 2nd 1.

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


title: Double hashing constraints

text:
# Question
Title: Double hashing constraints
For double hashing, we have some constraints on $h'(k)$

(1) It should never evaluate to 0

(2) It should be relatively prime to m

How to show that all slots in an open addressing table will be included in a probe sequence.

# Answer
In double hashing, we have (for a specific $k$) the series $h(k) + nh'(k) \mod m$

Since we have that $gcd(h'(k), m) = 1$ (they are relatively prime), then from Bézout's identity there exists two integers a,b such that $ah'(k) + bm = 1$. since $h'(k)$ is not 0, we can conclude that b is not 0 and thus also a is not 0. We have $ah'(k) = 1 \mod m$, which means that a is the inverse of h'(k) in modulo m.

Now, let $0 \leq i \leq m$ be an integer. by choosing $n = ia$, we have $( h(k) + nh'(k) ) \mod m = ( h(k) + iah'(k) ) \mod m = ( h(k) + i ) \mod m$.

This concludes the proof (think why).

I hope i managed to help!
> 3 votes

# Answer
*Answer to 2nd part*

In double hashing, let the hash function be h(k, i) where k is the key and i is the probe sequence.

Let h(k, i) = h(k, j) for some i and j where j \> i. This means that starting at ith step, after (j-i) more steps, the hash function points to the same slot. Let m be the size of the table. Also, h1(k) and h2(k) are ordinary hash functions.

```
h(k,i) = h(k, j)
(h1(k) + i * h2(k)) mod m = (h1(k) + j * h2(k)) mod m
(i * h2(k)) mod m = (j * h2(k)) mod m
((j - i) * h2(k)) mod m = 0

```

Since, h2(k) and m are relatively prime, therefore (j - i) must be a multiple or at least m. Therefore, for the hashing function to repeat the slot, the steps must be at least m.

This proves that keeping h2(k) and m relatively prime, the double hashing hits all slot in a table of size m producing all permutations of m.
> 1 votes

---
Tags: proof-techniques, hash-tables
---


# Question
Title: Is it decidable when a TM M gets another as inputs and checks if it fullfiills certain property?
I was asking myself if it is not possible to decide the language where a TM M gets the Godel number of a TM M' as input and the checks if, let us say, the TM M' has a certain amount of transitions.

My idea was that it is decidable because we have an countably infinite amount of Godel numbers and the number of TMs which fulfill a certain property is also countably infinite. Therefor, we could make a reduction with the Halting-problem and show via this way that it is undecidable.

# Answer
> 0 votes
That definitely isn't enough. The set of Turing machines that always halt is countable (being a subset of the countable set of all Turing machines), but very not decidable.

Don't overcomplicate: If you are given a Turing machine, any property of the machine as such (number of states, number of transitions, is it deterministic, ...) that can be checked by a deterministic algorithm is obviously decidable.

# Answer
> 0 votes
I wanted to simply comment this, but given my current reputation, I can't.

I am not sure how broad your definition of properties. But certain properties of a TM may not be decidable. A simple one is to check if an accept state is useful. That is, if the accept state will ever be entered.

To see, we can construct a TM M that when executed ignores its input and simulate the TM M' for the halting problem using a predefined input w'. TM M accepts if M' accepts. So if we can test if the accept state of M is useful then we can solve the halting problem.

---
Tags: turing-machines, undecidability
---


# Question
Title: Question about the conditions to find articulation points in a graph
I have been reading a book called The Algorithm Design Manual by Steven Skiena and one of the topics discussed there is an algorithm to find all the articulation points in a graph.

In it, we first construct a DFS tree and store the following information for each vertex in the DFS tree:

* The traversal order at which we visited the vertex
* The highest reachable ancestor from the tree for each vertex

After constructing the tree, the author says one of the following conditions need to be satisfied for a vertex to be an articulation vertex:

* If the root has more than 1 child, it is an articulation point
* If we have an edge `A -> B` which is a bridge, then A is an articulation point
* If we have an edge `A -> B` (A is parent of B) and the highest reachable node from B is A, then A is an articulation point.

I wrote a program to test this and it works on the graphs I tested it against:

```
// lo[] contains highest index
// pre[] contains traversal order
private void dfsFindArticulationPoints(int node, int parent) {
    if(pre[node] != 0) {
        lo[parent] = Math.min(lo[parent], pre[node]);
        return;
    }

    pre[node] = index;
    lo[node] = index;
    index++;

    int childCount = 0;
    for(int child: graph[node]) {
        if(pre[child] != 0)
            childCount++;
        if(child == parent)
            continue;
        dfsFindArticulationPoints(child, node);
        lo[node] = Math.min(lo[child], lo[node]);

        // Check case 2 and 3
        if(node != 0 && pre[node] <= lo[child])
            articulationPoints.add(node);
    }

    // Check case 1
    if(node == 0 && childCount > 1)
        articulationPoints.add(0);
}

```

---

**My Question:** I understand why those three conditions work. However how can I convince myself that those are the only three conditions to check?

Can somebody please prove to me that those are the only three conditions and there are no other conditions to check for?

# Answer
> 1 votes
Here is the proof:

Given we have `A -> B` as an edge where A is not the root, let's assume A is an articulation point thats not the root. Removing it results in 2 subsets - the first containing the root and the second containing B.

For the subset containing B to be disjoint from the root if A is removed, B should not have a link to any node from `root ... A` that is it should not be able to reach a vertex higher than itself. This is possible only if:

* `A -> B` is a bridge meaning the highest node reachable from B is itself
* A is the only node B is connected to that is above it. This way if we remove A the highest node reachable from B is itself.

---
Tags: graphs, graph-traversal, depth-first-search
---