# Question
Title: Is this special case of the subset-product problem $\mathsf{NP}$-complete?
It is a well known fact that the following 'subset-product' problem is $\mathsf{NP}$-complete when $n/\log M \in \Theta(1)$.

> Consider a size-$n$ subset of a multiplicative group $\mathbb{G}\cong\mathbb{Z}^{\*}\_M$. Then an instance of the subset-product problem consists of $(a\_1, a\_2,\dots,a\_n, t)$ with each $a\_i, t\in \mathbb{G}$ and the problem asks to find a (possibly $s(n)$-size, where $s(n)\in\Theta(n)$) subset $S\subset\[n\]$ such that $\prod\_{i\in S}a\_i = t$.

Is the special case where $t=1$ also $\mathsf{NP}$-complete? In particular, can every instance of the subset-product problem be reduced to an instance where one needs to find a subset whose product is $1\_{\mathbb{G}}$?

Since the fact is true for the related subset-sum problem (that every general subset-sum instance can be reduced to one in which the goal is to find a subset which sums to $0$) it could possibly be true. Are there any known results which deal with the above? References would be appreciated.

# Answer
> 3 votes
Yes, your problem is NP-complete, even when we restrict to the case where $t=1$.

We will focus on the case $M=2^k$. Then $\mathbb{Z}\_M^\*$ is isomorphic to $\mathbb{Z}\_2 \times \mathbb{Z}^{2^{k-2}}$, and $3$ has order $2^{k-2}$ in $\mathbb{Z}\_M^\*$, so the subgroup generated by $3$ modulo $M$ is isomorphic to $\mathbb{Z}^{2^{k-2}}$. (See https://math.stackexchange.com/q/2460124/14578.)

This lets us reduce the ordinary subset sum problem to your problem. Suppose we have an instance of (positive) subset sum, namely, $x\_1,\dots,x\_n \ge 0$ and a target $y$; the question is whether there exists a subset of the $x\_i$'s that sum to $y$. Choose $k$ large enough that $2^{k-2} \ge x\_1 + \dots + x\_n$, and set $M=2^k$. Let $a\_i = 3^{x\_i} \bmod M$, $a\_{n+1} = 3^{-y} \bmod M$, and $t=1$. Then there is a solution to your problem (with values $a\_1,\dots,a\_{n+1}$ and target $t=1$) iff there is a solution to the original subset sum instance. This shows how to reduce the (positive) subset sum problem to your problem with $t=1$, which proves that your problem is NP-complete.

My thanks to Yuval Filmus for the main ideas underlying this answer.

---

This doesn't prove that your problem is hard for all $M$. There may well be choices of $M$ where the problem is easy. In particular, for the special case where $M=3 \times 5 \times 7 \times 11 \times \cdots \times p$ is the product of the first few primes, I'm not sure whether the problem remains NP-complete or not. (Why do I have some doubts? Well, the subset sum problem is not hard over $\mathbb{Z}\_2^k$: it can be solved in polynomial time with linear algebra. When $M=3 \times \cdots \times p$, then $\mathbb{Z}\_M^\*$ is isomorphic to $\mathbb{Z}\_2 \times \mathbb{Z}\_2 \times \mathbb{Z}\_4 \times \mathbb{Z}\_6 \times \cdots \mathbb{Z}\_{p-1}$, and the isomorphism can be efficiently computed in both directions using the Chinese remainder theorem. So when $M$ has this special form, the situation feels somehow close to the case of $\mathbb{Z}\_2^k$, and I'm not sure whether there might some sophisticated generalization of linear algebra that can be used to solve the subset sum problem over $\mathbb{Z}\_M^\*$ efficiently or not.)

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


# Question
Title: What exactly is the relation between Haskell and category theory?
In articles or Quora posts about category theory, I often find mentions of the programming language Haskell. I have little knowledge of category theory and even less of programming. Could someone please explain how category theory is important in Haskell?

# Answer
> 10 votes
Category theory is an abstract branch of mathematics and you do not need to learn it before you start writing Haskell code. Similarly, you do not need to learn Haskell before you start learning category theory.

Haskell has a beautiful relationship with category theory. For example, consider polymorphic functions. When we define some reasonable restrictions, it turns out that they are simply natural transformations on which category theory applies.

Another example is Haskell's relation with Cartesian closed categories (CCCs). Haskell, at its core, is pure typed lambda calculus and lambda expressions can be considered the composition of functions that come with a Cartesian closed category. Once you start dwelling into Haskell and category theory, you will develop a concrete understanding of this relationship.

Check out free theorems, CCCs and $\lambda$ calculus, category theory from Haskell's POV and monads.

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


title: What is 0.1 converted to 8bit IEEE754?

text:
# Question
Title: What is 0.1 converted to 8bit IEEE754?
0.1 via $32\text{ bit}$ is rather easy:

Sign: $0\_2 = 0\_{10}$

Exponent: $123\_{10} = 01111011\_2$

Mantissa: $5033165\_{10} = 100110011001100110011001101\_2$

Now, how do you calculate this, if you've only $8\text{ bit}$ available?
**Sign: $1\text{ bit}$, Exponent: $2\text{ bit}$, Mantissa: $5\text{ bit}$**

My idea: $S=0; E=01; M=00001$

What do you think?

# Answer
With using analogy of IEEE 754 standard. We see the only difference is about size. Yours is 8-bit while IEEE 754 is 32-bit for single precision and 64-bit for double precision.

Let's play with your own standard format that still using IEEE 754 analogy:

```
sign (1-bit) | exponent (2-bit) | mantissa (5-bit)

```
* `Sign = 0` since `0.1` is positive.

Integer part: 0. = 0 in binary

Fraction part:

```
.1 * 2 = .2 + 0
.2 * 2 = .4 + 0
.4 * 2 = .8 + 0
.8 * 2 = .6 + 1
.6 * 2 = .2 + 1
.2 * 2 = .4 + 0 (back to the second equation)
...

```

So the fraction part is:

```
0001100110011...

```

Now combine integer part and fraction part

```
0.0001100110011...

```

Now represent it with using scientific notation

```
0.0001100110011 = 1.100110011 * 2 ^ (-4)

```

From scientific notation we got normalized mantissa that is `100110011`. Since your mantissa standard size is 5-bit we need to truncate it into 5-bit hence the mantissa is `10011`.

From scientific notation we got also `exponen = -4`. Since your exponent size is 2-bit we need to find offset of exponent bias first. `01 is considered as 0` so the offset is 1 hence `1 + (-4) = -3` . This is underflow!!! Due to your exponent size is too small, but let force it.

```
01 = 0
00 = -1
11 = -2 (back to the 11 due to underflow)
10 = -3 (we will take this)

```

With using your standard format we get:

```
sign (1-bit) | exponent (2-bit) | mantissa (5-bit)
0 | 10 | 10011
Or
01010011

```

Undeflow happened because your standard to represent 0.1 is too small. If it's me it depends on case i will face. I mean If the case care precision then I extend more mantissa size, If the case care higher range or lower range I extend the exponent size.
> 1 votes

# Answer
For $8$-bit floating point, you should look at $A$-law and $\mu$-law encoding standards:

http://en.wikipedia.org/wiki/%CE%9C-law\_algorithm

http://en.wikipedia.org/wiki/A-law\_algorithm

Depending on your input range, you may need some scaling.
> 2 votes

---
Tags: floating-point
---


# Question
Title: Is significand same as mantissa in IEEE754?
I'm trying to understand IEEE 754 floating point. when I try convert `0.3` from decimal to binary with online calculator, it said the significand value was `1.2`

Where `1.2` come from?

I did understand another bits like exponent and sign bit.

.3 if converted to binary it will be

```
.3 * 2 = .6 + 0
.6 * 2 = .2 + 1
.2 * 2 = .4 + 0
.4 * 2 = .8 + 0
.8 * 2 = .6 + 1
...

```

So 0.3 = 0.010011001... in binary

Apply the scientific notation in binary:

```
0.010011001 = 1.0011001 * 2 ^ (-2)

```

So the exponent is `-2`. And the normalized mantissa is `0011001...`

I will not talk about exponent bit and sign bit. Back to the my question, what is the difference of significand and mantissa?

# Answer
In base 2, the significand is a number of the form $1.b\_1b\_2\ldots$ where the $b\_i$'s are base 2 digits. The mantissa is the digits $b\_1b\_2\ldots$.

More generally, in base $n$, the normalized **significand** $s$ and **exponent** $e$ of a positive number $x$ are the numbers such that $x = s \cdot n^{e}$, $1 \le s \< n$ and $e$ is an integer (negative if $x \< 1$). In the case of base 2, the integer part of $s$ is always $1$ (since the definition yields $1 \le s \< 2$). So instead it's usual to write the number as $x = (1 + m) \cdot n^{e}$ with $0 \le m \< 1$. The digits of $m$ in base 2 (or the fractional part of $s$, depending on who you ask) are called the (normalized) **mantissa**.

For $x = 0.3$, we have $x = 1.2 \cdot 2^{-2}$ so for its representation in base 2, the exponent is $-2$, the significand is $1.2\_{10} = 1.001\overline{1001}\_2$ (where $x\_n$ means the digits are written in base $n$ and $\overline{1001}$ means the digits are repeated infinitely many times). The mantissa is the digits after the point: $001\overline{1001}$.
> 8 votes

# Answer
**They're used as synonyms in the context of floating point math**, but "mantissa" is less correct mathematically.

It's fewer syllables, easier to type, and starts with a different letter than Sign or Exponent, so many people including myself still prefer it, despite what Kahan and Knuth have to say. (Also including Intel, in naming the AVX512 instruction `vgetmantpd` for example, as a partner for `vgetexppd` which are convenient for exp/log implementations.)

---

Either / both get used as names for the part that isn't the sign bit or the exponent field. Or the value represented by that field, as opposed to the bits of the encoding. Wikipedia's articles on single-precision binary32 (`float`), and double, and IEEE FP formats in general, are very good.

Gilles's answer suggests that the two terms could make a distinction between the `1.x` value represented vs. the bit-pattern or encoding, but I don't think that usage is common; I've never come across it.

For example, a single-precision `binary32` FP converter (with a nice UI and display of the bits) names the field "Mantissa", and shows both the binary bit-pattern and the `1.x` or `0.x` value it represents (depending on the leading 1 or 0 implied by the exponent field for a normalized or subnormal float).

Wikipedia's Significand article describes the fact that they're used synonymously. But has a section at the end about why "mantissa" isn't quite the right mathematical meaning for FP math, since the significand is linear with only the exponent field being exponential. Unlike in earlier use of mantissa for log tables.

> The significand (also mantissa or \[other names\]) is part of a number in scientific notation or in floating-point representation, consisting of its significant digits. Depending on the interpretation of the exponent, the significand may represent an integer or a fraction.

> ### Terminology
>
> The term *significand* was introduced by George Forsythe and Cleve Moler in 1967 and is the word used in the IEEE standard. However, in 1946 Arthur Burks used the terms *mantissa* and *characteristic* to describe the two parts of a floating-point number (Burks *et al*.) and that usage remains common among computer scientists today.
>
> *Mantissa* and *characteristic* have long described the two parts of the logarithm found on tables of common logarithms. While the two meanings of *exponent* are analogous, the two meanings of *mantissa* are not equivalent. For this reason, the use of *mantissa* for *significand* is discouraged by some including the creator of the standard, William Kahan and prominent computer programmer and author of The Art of Computer Programming, Donald E. Knuth.
>
> The confusion is because scientific notation and floating-point representation are log-linear, not logarithmic. To multiply two numbers, given their logarithms, one just adds the characteristic (integer part) and the mantissa (fractional part). By contrast, to multiply two floating-point numbers, one adds the exponent (which is logarithmic) and *multiplies* the significand (which is linear).
> 10 votes

# Answer
Strictly speaking, a *mantissa* is part of a logarithm (specifically a common logarithm). For example, the common (base-10) logarithm of 1234 is 3.09132. From that number 3.09132 we can immediately see that we're dealing with a number between 103 = 1000 and 104 = 10000. And then the .09132 part essentially gives us the rest of the digits.

When working with such logarithms, .09132 is the *mantissa* and 3 is the *characteristic*. This is useful because multiplications and divisions by 10 change the characteristic but not the mantissa. For example, we immediately know that the logarithm of 123.4 is 2.09132, and that the logarithm of 1.234 is 0.09132.

In fact, back in the day when people used *log tables* to do higher-order arithmetic, those log tables didn't bother to give you the logarithm of *every* number. They just told you that 1234 had a mantissa of 09132, and it was your job to figure out the characteristic, based on whether you knew you started with 1234, or 1.234, or 1234000, or some other magnitude of number. (There was also a funny convention for numbers less than 1. Mathematically, the logarithm of 0.1234 is -0.90868, which doesn't have .09132 in it, until you realize that 0.09132 - 1 = -0.90868. Using the log tables, you said that the logarithm of 0.1234 had a mantissa of .09132 and a characteristic of -1, which was often written as 1̅.09132. If your browser didn't render that correctly, there's an overbar over the leading 1, indicating that it's negative, but the mantissa is still positive.) You can read more about this at the Wikipedia article on common logarithm.

So that's the story behind "mantissa". The significand, on the other hand, is simply one part of the representation of a number in *scientific notation* (aka *exponential notation*). If we say 1234 = 1.234 × 103, we've got a significand of 1.234 and an exponent of 3. In IEEE 754, in binary, if we have 57.375 = `42658000` = `0b1.11001011` × 25, we've got a significand of `0b1.11001011` (or `0b0.11001011` without the implicit leading 1 bit) and an exponent of 5.

So a mantissa is something you can add an integer to in order to get the logarithm of the number you're interested in; it's the fractional part of the logarithmic representation of a number. A significand is something you can multiply by a power of the base in order to get the number you're interested in; it's the normalized part of a scientific or exponential notation.

So *mantissa* and *significand* really are two pretty different things. It's unfortunate, I suppose, that Burks started using "mantissa" in the context of floating point, because that term really caught on, and it's what pretty much everyone learns.

This is also explained in the "Terminology" section of the Wikipedia article on Significand.
> 3 votes

---
Tags: floating-point
---


title: Transitive Closure of a graph

text:
# Question
Title: Transitive Closure of a graph
Assuming we have a DAG, $G = (V, E)$, and we know that we can calculate $G$'s transitive closure in time complexity of $f(|V|, |E|)$, whereas $f$ is monotonic increasing function.
Show that given a directed graph (not necessarily DAG) $G^{'}$, we can calculate it's transitive closure, $G^{+}=(V, E^{+})$, in time complexity of $O(f(|V|, |E|) + |V| + |E^{+}|)$.
We can assume all the graphs are represented in adjacency matrices.
I don't have any idea for this one. I tried to read stuff about this topic, including in cormen's book, but it didn't lead me to any solution.

# Answer
Using Kosaraju's algorithm, you can compute the strongly connected components (SCC) of $G$ in linear time.

The metagraph (or graph of the SCC) is well known to be a DAG. You can then compute the transitive closure of the metagraph.

Now to compute $G^+$:

* if $u$ and $v$ are in the same SCC, that means there is an edge from $u$ to $v$ and from $v$ to $u$;
* if $u\in C$ and $v\in C'$ where $C$ and $C'$ are two different SCC such that there is an edge from $C$ to $C'$ in the transitive closure of the metagraph, that means there is an edge from $u$ to $v$ (but not from $v$ to $u$).

All this can be done in the required complexity.
> 2 votes

---
Tags: graphs, dag
---


# Question
Title: Solve Recurrence T(n) = 4T(n/4) + n*[log(n)]^2
I am trying to solve

```
T(n) = 4*T(n/4) + n*[log(n)]^2

```

I decided to use Master Theorem so I found a,b=4 and logb(a)=1. I thought that 3rd case is the solution but I don't know actually how to solve this.

Any help appreciated. Thanks in advance !

# Answer
Following the numbering of cases as per this wikipedia article, we see that our recurrence follows the second case and hence, $$ T(n) = \Theta\left( n \log^3n \right) $$
> 0 votes

---
Tags: asymptotics, recurrence-relation, master-theorem
---


# Question
Title: Is there a TM that halts on all inputs but that property is not provable?
> Does there exist a Turing machine that halts on all inputs but that property is not provable for some reason?

I am wondering if this question has been studied. Note, "unprovable" could mean a "limited" proof system (which in the weak sense think the answer must be yes). I am of course interested in the strongest possible answer, i.e. one that is not provable to halt on all inputs in say ZFC set theory or whatever.

It occurred to me this could be true of the Ackermann function but I am hazy on the details. It doesn't seem like Wikipedia describes this aspect clearly.

# Answer
> 13 votes
Yes. The Turing machine that computes the Goodstein sequence beginning from its input and terminates when the sequence hits zero. It always terminates but this can't be proven in Peano arithmetic. I'm sure there are equivalent things for ZFC or any other system you might choose.

---

**Edit** For ZF, Hartmanis and Hopcroft show that there's a Turing machine $M$ that rejects every input but that this can't be proven in ZF. I'm not sure if ZF can prove that $M$ always halts but it certainly can't prove that the machine $M'(x)$ $=$ "If $M$ accepts $x$ then loop forever, else halt" always halts, even though it does. That still leaves ZFC open but ZF is more powerful than PA.

See Sec. 3 of Scott Aaronson's survey on independence of P=NP for an exposition of the Hartmanis–Hopcroft result and citations to their original papers.

# Answer
> 8 votes
Take a theory ${\cal T}$ that is at least as strong as "basic" arithmetic, and that is recursively enumerable (it's possible to enumerate every theorem of ${\cal T}$).

Construct the following machine $M$, which behaves as following on input $n$:

```
If there is no proof of 0 = 1 in less than n steps in T, ACCEPT
Otherwise, LOOP.

```

It's pretty easy to show using the second incompleteness theorem that ${\cal T}$ can not prove that $M$ terminates on all input (iff it is consistent).

This of course works for ${\cal T}=\mathrm{ZFC}$, ${\cal T}=\mathrm{PA}$, ${\cal T}=\mathrm{PA²}$,... as long as they are consistent.

# Answer
> 5 votes
Some unprovable in PA but true theorems can be converted to Turing machines. For example, there is a (strengthened version of) Ramsey's theorem, that is unprovable in PA, and we can construct a machine that would just search for the right $N$.

# Answer
> 1 votes
The halting of one TM can be encoded by constructing another TM and asking whether it halts. That is, given TM $T\_1$ and input $I\_0$, we can construct a TM $T\_2$ with inputs indexed by the natural numbers such that $T\_2(I\_n)$ halts if $T\_1(I\_0)$ doesn't halt after $n$ steps. Then there are inputs on which $T\_2$ doesn't halt iff $T\_1(I\_0)$ does halt, and proving that $T\_2$ halts on all inputs is equivalent to proving that $T\_1(I\_0)$ doesn't halt. Thus, once we find $T\_1, I\_0$ such that $T\_1(I\_0)$ doesn't halt, but it is not provable that it doesn't halt, there must be a $T\_2$ that halts on all inputs, but it is not provable that it halts on all inputs.

---
Tags: computability, reference-request, turing-machines, halting-problem
---


# Question
Title: Decide whether regular language contains a word $w$ for which $|w| = n^2$
**Task:**

Input: DFA $M = (Z, Σ, δ, q\_S, E)$
$T(M)$ := Language that $M$ accepts.
Question: Does $T(M)$ contain at least one word $w$ such that $|w| = n^2$ with $n \in \mathbb{N}$$ ?$

**My attempt:**

Since the language $\\{w\in Σ^\* \mid |w| = n^2 \\} $is not regular. You cannot create DFA $M'$ which accepts this language and use it somehow.

If $M$ is finite (which is decidable) you can check each word so this is not a problem.

If $M$ is not finite there has to be a cycle from a productive state. I have drawn a couple simple DFAs and I have noticed that there is DFA's with cycles that don't contain such word $w$.

Then I tried to find the property of the cycle/DFA so that there has to be a $w$ with $|w| = n^2$ and noticed that the following equation has to be true: $$n^2 = d + ck$$ with $d$ being the distance from the initial state $q\_s$ to an accepting state $q\_e \in E$ and $c$ being the length of the cycle somewhere on the path from $q\_s$ to $q\_e$.

Therefore: $$\sqrt{d+ck} \in \mathbb{N}$$ However I don't know how to continue from here. Any help would be greatly appreciated!

# Answer
> 5 votes
Convert $M$ to an NFA over $\Sigma = \\{a\\}$ by renaming all labels on edges to $a$. The language accepted by the NFA has the same word lengths as $T(M)$. Convert the NFA to a DFA. After removing unreachable states, the DFA is a path leading to a cycle. This implies that the set of length of words in $T(M)$ is eventually periodic. This means that for some there exist some $k,m$ and sets $S \subseteq \\{0,\ldots,k-1\\}$ and $T \subseteq \\{0,\ldots,m-1\\}$ such that the lengths of word in $T(M)$ are $$ S \cup \bigcup\_{i \in T} \\{ nm + k + i : n \in \mathbb{N} \\}. $$ We have reduced your problem to the following:

> Given $a \> 0$ and $b \ge 0$, decide whether $\\{na + b : n \in \mathbb{N}\\}$ contains a square.

If $na + b = r^2$ for some $r$ then $b \equiv r^2 \pmod{a}$, and so $b$ is a quadratic residue modulo $a$. Conversely, suppose that $b$ is a quadratic residue modulo $a$. Then there exists $r$ such that $b \equiv r^2 \pmod{a}$, say $r^2 = b + za$, where $z \in \mathbb{Z}$. For any $m \in \mathbb{N}$, we have $$ (ma + r)^2 = a(m^2a + 2mr) + r^2 = a(m^2 a + 2mr + z) + b. $$ Choosing $m = |z|$, this is of the form $na + b$ for some $n \in \mathbb{N}$.

We have shown that $\\{na + b : n \in \mathbb{N}\\}$ contains a square iff $b$ is a quadratic residue modulo $a$, which is a decidable property.

---
Tags: regular-languages, decision-problem
---


# Question
Title: To remove all comments in a JavaScript file, do we need just a scanner or also a parser?
I was asked how to remove comments in a JavaScript program, but once I gave the regular expression solution, I was asked what if there are comments like text inside of a string:

```
let hi = " // here ";
let foo = "   use this: /*   ";
let foo2 = "   \" and that */   ";

```

it also can get complicated with the cases with string being able to be quoted by `'` and the backtick ```:

```
let hi2 = 'here //';
let i = 123;
let hi3 = `here //  ${i  /* don't use j */}`;
let hi4 = `here //  ${i  // don't use j
                         // because j is not good
                     }`;
let hi5 = ` and use there ' " \' \" \`  /*  */`;
let hi6 = ` this is really closing, not quoted backtick \\`;
let hi7 = `here //  ${i  /* don't use j in `` */}`;

```

So I mentioned a scanner (lexical analyzer) and a parser (like yacc or bison) can be used. So we can build a tree of node representing the program, and then wherever it is a comment type of node, we can remove it. (comment nodes have no children, I think? If they do, then can just change the comment to nothing, the empty string).

But is it true that all we need is a scanner? We can tokenize all the text, and then we get each element which is a string, an operator, the left and right operands, and also the comment elements.

And then we can just remove all the comment elements and then reconstruct the program using all the tokens.

So probably we don't even need the program code to be represented as a tree, but just as a series of tokens. So if we already have a scanner and parser, all we need is a scanner, and when we supply it with the proper grammar rules, we can remove all the comments?

(is the following considered grammar or just finite state automata and do we just use it to form the tokens?)

# Answer
> 1 votes
Scanner (tokenizer) will be enough. Most programming languages do not allow comment nesting, so there is no need to use recursive parsers to strip all comments.

# Answer
> 1 votes
You should be able to achieve it with a finite state machine, hand rolled lexer or even a regular expression (rather long regular expression). But I will throw in a quick and easy overkill solution. There is a project called "jison" which is like Bison, but for JavaScript (https://github.com/zaach/jison). It is a parser generator.

Here is a grammar you can use to strip comments everywhere except in strings:

```
/* description: Scripts comments from JavaScript code. */

/* lexical grammar */
%lex
%%

\/\*                  return 'BLOCK_COMMENT_START'
\*\/                  return 'BLOCK_COMMENT_END'
\/\/                  return 'LINE_COMMENT_START'
\"                    return 'DOUBLE_QUOTE'
'                     return 'SINGLE_QUOTE'
\\"                   return 'ESCAPED_DOUBLE_QUOTE'
\\'                   return 'ESCAPED_SINGLE_QUOTE'
\\\\                  return 'ESCAPED_BACKSLASH'
\n                    return 'NEW_LINE'
<<EOF>>               return 'EOF'
.                     return 'OTHER'

/lex

%start code

%% /* language grammar */

code
    : c EOF
        { typeof console !== 'undefined' ? console.log($1) : print($1);
        return $1; }
    | c LINE_COMMENT_START c3 EOF
        { typeof console !== 'undefined' ? console.log($1) : print($1);
        return $1; }
    ;

c
    : c OTHER {$$ = $1 + $2}
    | c BLOCK_COMMENT_START c2 BLOCK_COMMENT_END
    | c LINE_COMMENT_START c3 NEW_LINE
    | c DOUBLE_QUOTE c4 DOUBLE_QUOTE { $$ = $1 + $2 + $3 + $4 }
    | c SINGLE_QUOTE c5 SINGLE_QUOTE { $$ = $1 + $2 + $3 + $4 }
    | {$$ = ""}
    ;

c2
    : c2 any_except_block_comment_end
    |
    ;

c3
    : c3 any_except_new_line
    |
    ;

c4
    : c4 any_except_double_quote { $$ = $1 + $2 }
    |
    ;

c5
    : c5 any_except_single_quote { $$ = $1 + $2 }
    |
    ;

any_except_block_comment_end
    : BLOCK_COMMENT_START
    | LINE_COMMENT_START
    | DOUBLE_QUOTE
    | SINGLE_QUOTE
    | ESCAPED_DOUBLE_QUOTE
    | ESCAPED_SINGLE_QUOTE
    | ESCAPED_BACKSLASH
    | NEW_LINE
    | EOF
    | OTHER
    ;

any_except_new_line
    : BLOCK_COMMENT_START
    | BLOCK_COMMENT_END
    | LINE_COMMENT_START
    | DOUBLE_QUOTE
    | SINGLE_QUOTE
    | ESCAPED_DOUBLE_QUOTE
    | ESCAPED_SINGLE_QUOTE
    | ESCAPED_BACKSLASH
    | EOF
    | OTHER
    ;

any_except_double_quote
    : BLOCK_COMMENT_START
    | BLOCK_COMMENT_END
    | LINE_COMMENT_START
    | SINGLE_QUOTE
    | ESCAPED_DOUBLE_QUOTE
    | ESCAPED_SINGLE_QUOTE
    | ESCAPED_BACKSLASH
    | NEW_LINE
    | EOF
    | OTHER
    ;

any_except_single_quote
    : BLOCK_COMMENT_START
    | BLOCK_COMMENT_END
    | LINE_COMMENT_START
    | DOUBLE_QUOTE
    | ESCAPED_DOUBLE_QUOTE
    | ESCAPED_SINGLE_QUOTE
    | ESCAPED_BACKSLASH
    | NEW_LINE
    | EOF
    | OTHER
    ;

```

Once again. Super overkill, but does the job. It generates an LR parser and since all recursions can be left-recursive, it will use constant stack space. And it will also run in linear time with regards to length of input.

The reason it should be achievable with just a finite state machine or regexp is that all the grammar can be rewritten to be using either just all left or just all right recursion. I do not have the regexp solution yet though.

I'll have a go at translating that LR grammar into a regular expression. But it will take a while.

Here is another solution too. Just to prove it can be done via a finite state machine. Here is a finite state machine implemented in JavaScript for stripping out comments except for inside single quote and double quote strings:

```
var StripperState = {
    OUTSIDE: 0,
    ENTERING_BLOCK_COMMENT: 1,
    INSIDE_BLOCK_COMMENT: 2,
    LEAVING_BLOCK_COMMENT: 3,
    ENTERING_LINE_COMMENT: 4,
    INSIDE_LINE_COMMENT: 5,
    LEAVING_LINE_COMMENT: 6,
    INSIDE_DOUBLE_QUOTE_STRING: 7,
    INSIDE_SINGLE_QUOTE_STRING: 8,
    ESCAPED_BACKSLASH_INSIDE_DOUBLE_QUOTE_STRING: 9,
    ESCAPED_BACKSLASH_INSIDE_SINGLE_QUOTE_STRING: 10,
    ESCAPED_SINGLE_QUOTE_INSIDE_SINGLE_QUOTE_STRING: 11,
    ESCAPED_DOUBLE_QUOTE_INSIDE_DOUBLE_QUOTE_STRING: 12,
};

function make_stripper(ahead) {
    return {
        char: undefined,
        ahead: ahead,
        state: StripperState.OUTSIDE,
    };
}

function feed_stripper(stripper, char, consumer) {
    stripper.char = stripper.ahead;
    stripper.ahead = char;
    process(stripper, consumer);
}

function process(stripper, consumer) {
    switch (stripper.state) {
        case StripperState.OUTSIDE: {
            if (stripper.char == '/' && stripper.ahead == '*') {
                stripper.state = StripperState.ENTERING_BLOCK_COMMENT;
            } else if (stripper.char == '/' && stripper.ahead == '/') {
                stripper.state = StripperState.ENTERING_LINE_COMMENT;
            } else {
                if (stripper.char == '"') {
                    stripper.state = StripperState.INSIDE_DOUBLE_QUOTE_STRING;
                } else if (stripper.char == '\'') {
                    stripper.state = StripperState.INSIDE_SINGLE_QUOTE_STRING;
                }
                consumer(stripper.char);
            }
            break;
        }
        case StripperState.ENTERING_BLOCK_COMMENT: {
            console.assert(stripper.char == '*');
            stripper.state = StripperState.INSIDE_BLOCK_COMMENT;
            break;
        }
        case StripperState.INSIDE_BLOCK_COMMENT: {
            if (stripper.char == '*' && stripper.ahead == '/') {
                stripper.state = StripperState.LEAVING_BLOCK_COMMENT;
            }
            break;
        }
        case StripperState.LEAVING_BLOCK_COMMENT: {
            console.assert(stripper.char == '/');
            stripper.state = StripperState.OUTSIDE;
            break;
        }
        case StripperState.ENTERING_LINE_COMMENT: {
            console.assert(stripper.char == '/');
            stripper.state = StripperState.INSIDE_LINE_COMMENT;
            break;
        }
        case StripperState.INSIDE_LINE_COMMENT: {
            if (stripper.char == '\r' && stripper.ahead == '\n') {
                stripper.state = StripperState.LEAVING_LINE_COMMENT;
            } else if (stripper.char == '\n') {
                stripper.state = StripperState.OUTSIDE;
            } else if (stripper.char == '\r') {
                stripper.state = StripperState.OUTSIDE;
            }
            break;
        }
        case StripperState.LEAVING_LINE_COMMENT: {
            console.assert(stripper.char == '\n');
            stripper.state = StripperState.OUTSIDE;
            break;
        }
        case StripperState.INSIDE_DOUBLE_QUOTE_STRING: {
            if (stripper.char == '"') {
                stripper.state = StripperState.OUTSIDE;
            } else if (stripper.char == '\\' && stripper.ahead == '\\') {
                stripper.state = StripperState.ESCAPED_BACKSLASH_INSIDE_DOUBLE_QUOTE_STRING;
            } else if (stripper.char == '\\' && stripper.ahead == '"') {
                stripper.state = StripperState.ESCAPED_DOUBLE_QUOTE_INSIDE_DOUBLE_QUOTE_STRING;
            }
            consumer(stripper.char);
            break;
        }
        case StripperState.INSIDE_SINGLE_QUOTE_STRING: {
            if (stripper.char == '\'') {
                stripper.state = StripperState.OUTSIDE;
            } else if (stripper.char == '\\' && stripper.ahead == '\\') {
                stripper.state = StripperState.ESCAPED_BACKSLASH_INSIDE_SINGLE_QUOTE_STRING;
            } else if (stripper.char == '\\' && stripper.ahead == '\'') {
                stripper.state = StripperState.ESCAPED_SINGLE_QUOTE_INSIDE_SINGLE_QUOTE_STRING;
            }
            consumer(stripper.char);
            break;
        }
        case StripperState.ESCAPED_BACKSLASH_INSIDE_DOUBLE_QUOTE_STRING: {
            console.assert(stripper.char == '\\');
            stripper.state = StripperState.INSIDE_DOUBLE_QUOTE_STRING;
            consumer(stripper.char);
            break;
        }
        case StripperState.ESCAPED_BACKSLASH_INSIDE_SINGLE_QUOTE_STRING: {
            console.assert(stripper.char == '\\');
            stripper.state = StripperState.INSIDE_SINGLE_QUOTE_STRING;
            consumer(stripper.char);
            break;
        }
        case StripperState.ESCAPED_DOUBLE_QUOTE_INSIDE_DOUBLE_QUOTE_STRING: {
            console.assert(stripper.char == '"');
            stripper.state = StripperState.INSIDE_DOUBLE_QUOTE_STRING;
            consumer(stripper.char);
            break;
        }
        case StripperState.ESCAPED_SINGLE_QUOTE_INSIDE_SINGLE_QUOTE_STRING: {
            console.assert(stripper.char == '\'');
            stripper.state = StripperState.INSIDE_SINGLE_QUOTE_STRING;
            consumer(stripper.char);
            break;
        }
    }
}

function strip_comments_from_code(code) {
    if (code.length == 0) {
        return code;
    }
    var stripper = make_stripper(code[0]);
    var result = '';
    var consumer = function(char) {
        result += char;
    };
    for (var i = 1; i < code.length; ++i) {
        feed_stripper(stripper, code[i], consumer);
    }
    feed_stripper(stripper, undefined, consumer);
    return result;
}

var code = "te/*st*/ // /* aaa vvv */\ncd. ' /* er */ '";
console.log(strip_comments_from_code(code));

```

The code doesn't know about backtick strings, but that can be an exercise for the reader. Also if you throw in a counter in the stripper state you can handle nested comments, but then it is no longer a finite state machine anymore.

Here is the regular expression: `/^(\/\*((?!\*)(.|\n|\r)|\*(?!\/)(.|\n|\r))*\*\/|"((?!("|\\))(.|\n|\r)|\\(.|\n|\r))*"|'((?!('|\\))(.|\n|\r)|\\(.|\n|\r))*'|\/\/.*(\r\n?|\n|$)|((?!(\/|"|'))(.|\n|\r)))*/g`

There is a couple of groups in that regular expression that will match comments outside strings. Now we just need a way to substitute only certain groups in the regex to a empty string.

Finally a regex solution:

```
var regex = /^(("((?!("|\\))(.|\n|\r)|\\(.|\n|\r))*"|'((?!('|\\))(.|\n|\r)|\\(.|\n|\r))*'|((?!(\/|"|'))(.|\n|\r)))*)(\/\*((?!\*)(.|\n|\r)|\*(?!\/)(.|\n|\r))*\*\/|\/\/.*(\r\n?|\n|$))/g;
var code = "te/*st*/ aaa // bbb \n ' /* ccc */' ";
var l = code.length;
while (true) {
    code = code.replace(regex, "$1");
    if (code.length == l) {
        break;
    }
    l = code.length;
}
console.log(code);

```

---
Tags: parsers, lexical-analysis
---


title: Is there a notation for types?

text:
# Question
Title: Is there a notation for types?
Is there a notation for statements like the following:

> If both operands are of type `int`, then the result is of type `int`. If either operand is of type `float`, then the result is of type `float`.

e.g. for the first case, can I say something like: $$int \ \text{op} \ int \rightarrow int$$

where $\text{op}$ is an operator with the above semantics.

I think I've come across this sort of notation before, but I'm not sure if it has a name or how to express the second scenario (*either* operand is a float).

# Answer
In looking at

`int op int→int`

my focus is immediately drawn to .

If you have ever studied Lambda Calculus and how it forms the foundation of many functional programming languages then you will come to understand  which should not be confused with `→ᵦ` or `→ₐ` . Since searching for  is not easy search for Currying instead.

When Alonzo Church invented Lambda Calculus it did not have types. Within a few years typed Lambda Calculus was created. Since many functional languages derive from typed Lambda Calculus you often see type definitions like `int -> int -> int`.

While I don't fully understand your question I suspect this is what you seek

Specialized type systems

If you want to spend the rest of your life on this then see

So many data types, so little time

---

> how to express the second scenario (either operand is a float).

Since you did not give a specific programming language I would expect something like

`int -> float -> float` and `float -> int -> float`
> 2 votes

# Answer
One approach is to use union/intersection types: https://stackoverflow.com/q/5653678/781723.

Haskell type classes can be used to support this, but with some significant restrictions: https://www.schoolofhaskell.com/school/starting-with-haskell/introduction-to-haskell/5-type-classes.
> 1 votes

# Answer
You can write a new union type as $$ \mathrm{type} \\; number = int \\; | \\; float $$ Then, you can write down your function $$ addition : number \rightarrow number \rightarrow number $$
> 1 votes

---
Tags: terminology, notation, types
---


# Question
Title: Cellular automata on the Eisenstein integers?
Is there any cellular automaton on the Eisenstein integers? By this I mean that the triangles formed by the Eisenstein integers are considered as cells and each triangle has three neighbours plus itself. I programmed in python such a cellular automaton and am curious what properties it has.

git: https://gist.github.com/githubuser1983/aaea24744998f3b263519048136ee49d

video: https://www.youtube.com/watch?v=R\_kcuWfGsTo

The only rule is: If a cell has exactly one alive cell in the neighbourhood then it is alive, otherwise it is dead.

Thanks for your help.

**Edit**: It seems that these triangular CA have been studied by : https://wpmedia.wolfram.com/uploads/sites/13/2018/02/08-2-4.pdf

# Answer
Yes, such cellular automata have been studied. However, you're unlikely to find much about them using terms like "Eisenstein integers", since the convention in the field is to describe cellular automata on regular lattice using the lattice symmetry (e.g. hexagonal / rectangular / triangular for 2D lattices) and the neighborhood size and shape (i.e. how many and which nearby cells on the lattice can influence the behavior of the cell we are looking at).

For example, the triangles between Eisenstein integers form — unsurprisingly — a triangular lattice in the complex plane, and the three directly adjacent neighbors of a cell in this lattice constitute what is sometimes called the triangular von Neumann neighborhood (by analogy with the four-cell von Neumann neighborhood on the 2D square lattice).

One notable issue with cellular automata on this lattice is that the small neighborhood size rather severely limits the number of possible rules. In particular, with two states per cell, there are only $2^{2^4} = 2^{16}$ possible rules, even including non-isotropic rules — some of which will be isomorphic to each other, restricting the rule space even further.

While this does mean that an exhaustive enumeration and investigation of *all* CA rules on this neighborhood may be at least somewhat practical, it does also mean that some interesting behaviors found in cellular automata one larger neighborhoods may be missing from small neighborhoods like this simply due to the limited diversity of the rule space.

The small neighborhood — and, in particular, the fact that adjacent cells have disjoint neighborhoods — also limits the behavior of the edges of localized patterns. In particular, it should fairly easy to prove the following lemma (which also holds for the classic four-cell von Neumann neighborhood on the square lattice):

> **Lemma**: If the all-dead lattice state is stable (i.e. a dead cell with zero live neighbors remains dead), then a finite pattern of one or more live cells on an unbounded lattice must either remain confined within a bounded region of the lattice, unable to escape it, or expand infinitely in all directions at the maximum possible speed.

(I may add a more detailed proof sketch later, but the basic idea is to consider the smallest axis-aligned hexagon covering all the live cells, and look at what happens to cells immediately outside each edge of this hexagon.)

In particular, this implies that totalistic CA rules on such a neighborhood cannot support spaceships, as found e.g. in Conway's Game of Life, since such a pattern must be able to expand indefinitely on one side while shrinking and *not* expanding on other sides. As interactions between spaceships (and stationary objects) are the main source of computational complexity and universality in Conway's Game of Life, any attempts to find computationally universal rules on the (triangular) von Neumann neighborhood are unlikely to succeed, at least not using the same methods.

That is, of course, unless one "cheats" by breaking some of the assumptions of the lemma above, e.g. by considering rules where the all-dead lattice state is *not* stable (but rather oscillates between all-live and all-dead), or initial states where the lattice is (mostly) covered in some non-uniform repeating pattern of cells. Then spaceships and other non-explosively propagating patterns may be possible. (At least they exist for the 4-cell von Neumann neighborhood, so I see no obvious reason why they couldn't also exist here.)

---

**Addendum:**

There are $2^{2 \times 4} = 256$ possible 2-state semitotalistic CA rules (i.e. rules where the new state of a cell depends only on its current state and the number of neighboring cells in each state) on your 3-neighbor lattice. (In fact, this is also the number of isotropic rules on your lattice, as all such rules — and indeed all rules that are invariant under a 120° rotation — on your lattice are semitotalistic.)

Since the adjacency graph of your lattice is bipartite, those rules come in exactly $128$ isomorphic pairs related either by state reversal (i.e. swapping the live and dead states) or, for the $2^4 = 16$ rules that are invariant under state reversal, "checkerboard reversal" (i.e. toggling the state of the cells in one half of the bipartition of the adjacency graph).

Let's try to classify those 256 (effectively 128) rules based on how finite patterns can propagate on the lattice. For brevity, I'll use the shorthand notation "B$n$" to indicate that a dead cell with $n$ live neighbors will become live, and "S$n$" to indicate that a live cell with $n$ live neighbors will remain live under the rule:

* As noted, rules without B0 are subject to the lemma above, and so:

+ in rules without either B0 or B1 finite patterns of live cells cannot expand outside their bounding hexagon;
    + in rules with B1 but no B0 any finite pattern of live cells surrounded by dead cells will "explode", expanding in all directions at one cell per step.
* In rules with both B0 and S3 any initial all-dead lattice state will flip to all-live and stay that way. All such rules have isomorphic state-reversed equivalents with neither B0 nor S3 (and which are thus subject to the lemma given earlier).
* In rules with B0 but not S3, an initial all-dead state will flip indefinitely between all-dead and all-live. These rules are *not* subject to the lemma above, and are thus in principle capable of having spaceships. However:

+ In rules with B0 and B1, and neither S2 nor S3, finite patterns of live cells on an all-dead background (or vice versa) are still confined to their bounding hexagon.
    + In rules with B0 and S2, and neither B1 nor S3, finite patterns still expand explosively at one cell per step.
    + Rules with B0 and neither B1, S2 or S3 are state-reversal isomorphic to rules with B0, B1, S2 but not S3. Thus, only one of these two sets of 16 rules needs to be considered further.

Thus, there are only 16 (isomorphic pairs of) rules on your lattice that are, even in principle, capable of having spaceships. Of course, not all of them actually do.

For example, the rule B0/S (i.e. where all live cells die, and dead cells become live only if they have no live neighbors) has trivial dynamics where every finite pattern eventually settles into a period-2 cycle (and so does its state-reversed dual B0123/S012, where all dead cells become live, and live cells die only if they have no dead neighbors).

I haven't investigated the remaining 15 rules to see what kind of dynamics they support. Based on my experience of investigating rules with spaceships on the 4-cell von Neumann neighborhood many years ago, however, I'd probably start by looking at rules that are "nearly linear", i.e. close to the rule B02/S13, where cells switch state if and only if the have an even number of live neighbors.

Of course this rule itself cannot support spaceships, as it has both B0 and S3. (It instead displays universal linear replication, which is a neat phenomenon but ultimately useless for complex dynamics, as patterns never interact except by trivially passing through each other.) But if you drop S3, you get B02/S1, which *is* in the space of potentially spaceship-supporting rules, and would seem like a prime candidate for exploration to me. (Of course, this is just a semi-informed guess.)
> 3 votes

---
Tags: reference-request, cellular-automata
---


# Question
Title: Looking for the English name of algorithm using a precomputed array for interval sum computation
I am looking for the English name of the following algorithm:

We are given an array `a` with numbers and we need to be able to efficiently retrieve the sum of a continuous interval `[f,t]` of numbers in that array. In order to do that we precompute an array `sums`(of size `size(a) + 1`) that stores the sums of the prefixes of the initial array. More formally `sums[i] = a[0] + a[1] + ... a[i-1]`. This array can be constructed with linear complexity and now in order to compute the sum of the numbers in the interval `[f,t]`, we simply compute `sums[t]-sums[f-1]`.

Direct translation of the name of the algorithm(or more precisely the datastructure) that I've seen used in Bulgaria is `prefix array`, but in my experience direct translation often turns out to be wrong when it comes to algorithms and data structures.

How is this algorithm(or datastructure) called in English?

# Answer
> 2 votes
I think the array `sum` is the result of the prefix computation of the original array (link).

# Answer
> 2 votes
The correct term is *Prefix Sum*. See e.g. https://en.wikipedia.org/wiki/Prefix\_sum

# Answer
> 0 votes
I don't know if your algorithm has a name, however the *maximum sum subsequence problem* is very similar:

> To solve the *maximum sum problem* one must locate the maximal sum sub-vector of an array $A$ of $n$ numbers. The maximal sub-vector of $A$ is the sub- vector $A\[i, . . . , j\]$ maximizing $\sum\_{s=i}^j s$. The problem originates from Ulf Grenander who defined the problem in the setting of pattern recognition \[1\].

1. Bentley, J.: Programming pearls: algorithm design techniques. Commun. ACM 27(9) (1984) 865–873

---
Tags: algorithms, data-structures
---


title: prove $A$ is context-free

text:
# Question
Title: prove $A$ is context-free
> Prove that the following language is context-free by giving a context-free grammar that generates the language: $A = \\{a \in \\{0,1\\}^\* : \text{ no character in an even position is a 0 or no character in an odd position is a 1}\\}$, where the first position is position 1. For instance, $01110, 01010$ are both in $A.$

If A were regular, I could convert a DFA for A into a CFG. I know I need to keep track of the parity of the positions of a character in a string. Basically, it should suffice to generate a CFG for the language $\\{a\in \\{0,1\\}^\* : \text{ no character in an even position is a 0}\\}$, which consists of all strings where every character in an even position is a 1 and where the characters in all other positions can be 0 or 1. I think constructing this language should be symmetric to constructing the language that's the "other part" of $A$, namely $\\{a\in \\{0,1\\}^\* : \text{ no character in an odd position is a 1}\\}$.

# Answer
This language is regular and this is an NFA that describes it:

Please notice that the language has nothing to do with "counting" and it doesn't need any memory so you can simply realize it's regular, CFL uses the stack for memory purposes but here it's all about determining the place of a character.
> 1 votes

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


title: What does O( n^{1+o(1)} ) mean

text:
# Question
Title: What does O( n^{1+o(1)} ) mean
The latest development in solving the max-flow problem promises a ${\displaystyle O(E^{1+o(1)}\log U)}$ solution.

What does it mean, this $O(n^{1+o(1)})$-complexity?

# Answer
A function $f(n)$ is $O(n^{1+o(1)})$ if there exist a constant $C \> 0$ and a function $g(n)$ satisfying $\lim\_{n\to\infty} g(n) = 0$ such that $$ f(n) \leq Cn^{1+g(n)}. $$
> 4 votes

# Answer
As n grows, o(1) eventually becomes less than 1, then less than 1/2, then less than 1/3 and so on.

So as n gets large, f(n) will be O(n ^ 3/2), O(n ^ 4/3) and so on. The factor between n and f(n) can become larger and larger, but the increase will become less.
> 1 votes

---
Tags: time-complexity, complexity-classes
---


# Question
Title: expression/pattern for language where product of number of 0s and 1s is even
I am trying to solve one of the sample test problems in which I have to write an expression/pattern for the following language:

$\\{w \in \\{0, 1, 2\\}^\*: {\\#}\_{0}(w) ∗ {\\#}\_{1}(w) \text{ is even}\\}$

I was thinking about the approach of getting all strings with even number of 0s and 1s first and then make a complement of that expression, but now I'm not so sure if my solution would also include all variations, that is:

* even number of 0s and odd number of 1s
* odd number of 0s and even number of 1s
* even number of 0s and even number of 1s

My solution: $\overline{2^{\*}(002^{\*}|112^{\*})^{\*} 012^{\*}}$

Mostly I'm not so sure about points 1. and 2. and would gladly accept any help in dispelling my doubts and solving this issue.

# Answer
> 1 votes
I don't know whether writing the complement of a regular expression will satisfy the requirements of your test, but anyway it's not correct. $2^∗(002^∗|112^∗)^∗012^∗$ must start with $0$, $11$, or $2$, so neither $100$ nor $101$ are included, and so both of them will show up in the complement. But they both satisfy the criterion, since the product of population counts in both cases is 2.

All the same, you're actually very close to solving this problem. You've already enumerated three of the four possible categories of inputs (the three which satisfy the criterion). It's only necessary to add the fourth possibility and show the transitions between them with each new input, in order to construct a finite automaton with four states. From that it's straight-forward (although a bit messy) to produce a regular expression, or trivial to produce a regular grammar.

---
Tags: formal-grammars
---


title: Compare solutions of counting sort

text:
# Question
Title: Compare solutions of counting sort
I was looking for implementations of counting sort and most of them are implemented with cumulative counts like this:

```
public void SortArray1(int[] nums)
    {
        var output = new int[nums.Length];

        var count = new int[nums.Max() + 1];
        foreach (var num in nums)
            count[num]++;

        for (int i = 1; i < count.Length; i++)
            count[i] += count[i - 1];

        for (int i = nums.Length - 1; i >= 0; i--)
        {
            var index = count[nums[i]] - 1;
            output[index] = nums[i];
            count[nums[i]]--;
        }

        for (int i = 0; i < nums.Length; i++)
            nums[i] = output[i];
    }

```

But actually it can be also implemented without cumulative counts:

```
public void SortArray2(int[] nums)
    {
        var count = new int[nums.Max() + 1];
        foreach (var num in nums)
            count[num]++;

        int number = 0; int index = 0;

        while (index < nums.Length)
        {
            while (count[number]-- > 0)
                nums[index++] = number;
            number++;
        }
    }

```

I am interested what is the reason behind it. Maybe first approach has some advantages and I miss them. Second approach looks better to me and I want to be confident when using it.

# Answer
> 1 votes
I think there are two important advantages of the original counting sort implementation. First, the original version can easily be modified in case the items (keys) being sorted includes additional data. Say you are sorting objects that contains an ID and name, and these objects must be sorted by their ID. The original version does not simply accumulate the count of each key but it moves the actual elements around. However, to do this the algorithm needs an extra array. Hence, it is not an in-place algorithm, which can be disadvantageous sometimes.

The second is that it is guaranteed to be stable (order of items with equal keys is retained). It is not clear to me if your implementation will also be stable since you are not keeping the original elements.

---
Tags: sorting
---


# Question
Title: Better results for minimum vertex cover algorithms
Currently I'm using the well-known ratio-2 algorithm which is nice and fast, but I'm looking for an intuitive way to improve my results.

All the articles I read so far were way too complicated for me, I'm looking for simple ideas to improve the results.

What I got so far:

```
    def approx_vc(g):
        """
        Find a vertex cover that in the worst case is twice the size of the mvc (ratio 2).
        :param g: Graph object
        :return: Set of integers as vertices.
        """
        c = Set()
        e = g.get_edges()
        while len(e):
            u, v = e.pop()
            c.update([u, v])
            for edge in list(e):
                if u in edge or v in edge:
                    e.remove(edge)
        return c

```

# Answer
A short trip to wikipedia will tell you that there is no known better approximation algorithm for vertex cover (at least when by "better" we require an improvement by a constant independent of the input).

This is what is known so far:

* The best known approximation achieves an approximation factor of $2-\Theta\left(\frac{1}{\sqrt{\log V}}\right)$ \[\].
* VC is NP-hard to approximate within a factor of $1.3606$ (meaning that if we have a polynomial approximation algorithm with this factor then $\mathsf{P}=\mathsf{NP})$ \[\].
* If the unique games conjecture holds, then VC is NP-hard to approximate within a factor of $2-\epsilon$, for all $\epsilon\>0$ \[\]. So if there exists a $2-\epsilon$ approximation for VC, then either $\mathsf{P}=\mathsf{NP}$, or the unique games conjecture fails.

Thus, any better approximations than the naive one you presented will solve open questions in complexity, so you are not likely to find them here (and they might not exist at all).

---

1. G. Karakostas, A better approximation ratio for the vertex cover problem, ACM Trans. Algorithms (TALG) 5 (4) (2009) 41.

2. Dinur, Irit; Safra, Samuel (2005). "On the hardness of approximating minimum vertex cover". Annals of Mathematics. 162 (1): 439–485.

3. Khot, Subhash; Regev, Oded (2008). "Vertex cover might be hard to approximate to within 2−ε". Journal of Computer and System Sciences. 74 (3): 335–349.
> 9 votes

# Answer
Although, as posted by Ariel, there is no known way to obtain theoretically better results, there are many ways to improve on it in practice. A typical technique is a local search algorithm, that applies some small modifications to the current solution to look for better results.

As a first improvement, I would try randomizing your algorithm and run it several times to get a better solution: u, v = random.sample(e, 1)

Then you can try using more elaborate algorithms, such as simulated annealing: you just need to define a way to find "close" solutions, such as removing a few vertices from your solution and restarting your (randomized) algorithm.

A few papers have been published on local search for this particular problem if you want even better - but more complex - algorithms. Here is an example: Shaowei Cai, Kaile Su, Abdul Sattar (2012), Two New Local Search Strategies for Minimum Vertex Cover
> 6 votes

# Answer
Ariel has covered worst-case approximation, so I'll mention two cases in which you can efficiently get an exact answer.

By this paper, that can be done whenever the size of the minimum vertex cover is not too large.  (i.e., the size of the *graph* is otherwise mostly-irrelevant.)

Like lots of graph problems, that can also be done whenever the treewidth is not too large.

This paper gives efficient way of approximating the treewidth, and section 1.2 cites ways of efficiently finding low-width tree-decompositions.
> 3 votes

# Answer
I proposed a better approximation algorithm for vertex cover problem (a 1.999999-approximation algorithm by solving a well-known SDP model and a randomized procedure). It is not published, yet. But, I am sure that it is true (I am grateful if anyone identify any potential issues).

To clarify the main topics of the idea, first of all, we prove that,

1. If the optimal VCP value is greater than $n/2+n/k$ then for all VCP feasible solutions, we have the approximation ratio $2k/(k+2)\<2$,
2. Based on a feasible VCP solution with objective value smaller than $kn/(k+1)$ , we have the approximation ratio $2k/(k+1)\<2$.

Then, to fix the value $k$ and to produce a constant factor better than $2$, we solve a well-known SDP relaxation and do as follows:

**Step 1**. Let $V\_{-1}=\\{j:v\_o^\* v\_j^\*\<0\\}$, and $V\_1=V-V\_{-1}$ which is a feasible VCP solution.

If $|V\_{-1}|\>0.000001n$ then $|V\_1 |\< 0.999999n$ and based on (2) we have an approximation ratio $(2(999999))/(999999+1)≤1.999999$. Else, let $ε=0.0004$ and $G\_ε=\\{j∈V│0≤v\_o^\* v\_j^\*≤+ε\\}$ and $A=\\{j∈V│v\_o^\* v\_j^\*\>+ε\\}$.

**Step 2**. If $|A|\>0.01n$, then, we can prove that the optimal VCP value is greater than $n/2+0.0000015n$ and then based on (1) we have an approximation ratio $(2×1/0.0000015)/(1/0.0000015+2)≤1.999999$. Else, we know that $|G\_ε |≥(1-0.000001-0.01)n=0.989999n$. Now, it is sufficient to introduce a suitable feasible VCP solution based on $G\_ε$.

**Step 3**. We prove that for any normalized vector $w$, the induced subgraph on $H\_w=\\{j∈G\_ε;|wv\_j^\*|\>0.5003\\}$ is a bipartite graph. As a result, by introducing a set $H\_w$ where $|H\_w |\>0.000001n$, we can produce a feasible VCP solution where $|V\_{-1}|≥0.000001n/2$ and $|V\_1|≤(1-0.000001/2)n= 1999999n/2000000$, with a performance ratio of $(2(1999999))/(1999999+1)= 1.999999$.

Finally, to introduce a suitable set $H\_w$, we prove that, by introducing two random vectors $u$ and $w$, one of the sets $H\_u$ or $H\_w$ has more than $0.000001n$ members. As a result we could introduce an approximation ratio of $1.999999$ on arbitrary graphs and based on the proposed $1.999999$\- approximation algorithm for VCP, the unique games conjecture is not true.
> -1 votes

---
Tags: graphs, approximation
---


# Question
Title: Identifying easy subsets/instances of NP-hard problems?
Say I want to solve a set of problems. I know that I can map my problem as a problem that is known to be hard in the general case (say, inference in Bayesian networks). But my set only contains instances which will map to easy instances - (say, having a tree-structure when cast to a BN inference problem)

I know BNs with tree-structures have linear-time inference algorithms. If I didn't, I may have given up on exact solutions in favour of loose approximations.

(2nd, looser example: I find myself needing to solve SAT, but turns out I can easily reduce all my problem instances to 2-SAT)

Is there a common approach to determine whether a given subset of a hard problem is hard or not? How does one typically approach this? Are these well studied

# Answer
This is a very broad topic. Every problem is a special case of some hard problem. For instance, most problems (both hard and easy ones) can be viewed as a special case of the halting problem, but that doesn't really help us distinguish hard from easy problems. It all depends on the details. I don't think there's any general answer at this level of abstraction.
> 3 votes

---
Tags: np-complete
---


# Question
Title: Prove a stronger version of the pumping lemma for context-free languages
Let $L$ be a context-free language. Prove that there exists integer $p\>0$ such that

$ \forall z\in L $ such that $ |z|\ge p $, there exists a partition $ z=uvwxy $ such that

1. $|vwx|\le p$
2. $|vx|\geq2$
3. $\forall i\geq 0 : uv^iwx^iy\in L$

HINT: $p$ needs to be bounded $ p\leq 2^{2k}$ which gives you more power. What is the power?

---

Please note the constraint $|xv|\geq2$ is stronger than the constraint $|xv|\>0$ in the usual pumping lemma of context-free languages. How I can prove from one to another please?

# Answer
#### Proof Idea for the usual pumping lemma

Let $z$ be a very long string in $L$. A parse tree for $z$ is so tall that it must contain some long path from the start symbol at the root of the tree to one of the terminals at a leaf. On this long path, some nonterminal $R$ must repeat because of the pigeonhole principle. This repetition of a nonterminal allows us to replace the subtree under the second occurrence of $R$ with the subtree under the first occurrence of $R$, which leads to a parse tree of a new string in $L$. We can thus find a partition $z=uvwxy$ where $vx$ is nonempty and $v...x$ can be pumped.

#### Refined Idea

To extend the length of the pumpable part to be $\ge2$, we will let $z$ be even longer so that some nonterminal $R$ must appear at least three times so that we can find a partition $z=uv\_1v\_2wx\_2x\_1y$ where both $v\_1x\_1$ and $v\_2x\_2$ are nonempty and $v\_1x\_1...x\_2v\_2$ can be pumped.

#### Proof

Here is a proof that follows basically the proof in *Introduction to the Theory of Computation* by Michael Sipser.

Let $G$ be a Chomsky normal form grammar for $L$. In any parse tree using $G$, a node can have no more than $2$ children. So, if the height of the parse tree is at most $h$, the length of the string generated is at most $2^h$.

Say $k$ is the number of non-terminals in $G$. We set $p$, the pumping length, to be $2^{2k+1}$. Now if $z$ is a string in $L$ and its length is $p$ or more, its parse tree must be at least $2k+1$ high, because $2^{2k+1}\gt2^{2k}$.

Let $\tau$ be one of its parse tree. If $z$ has several parse trees, choose $\tau$ to be a parse tree that has the smallest number of nodes. We know that $\tau$ must be at least $2k+1$ heigh, so its longest path from the root to a leaf has length at least $2k+1$. That path has at least $2k+2$ nodes; one at a terminal, the others at non-terminals. Hence that path has at least $2k+1$ non-terminals.

Consider the first $2k+1$ non-terminals on that path starting from the root. With $G$ having only $k$ non-terminals, some non-terminal $R$ appears at least $3$ times among them, thanks to the pigeon-hole principle.

We divide $z$ into $uvwxy$, where $v=v\_1v\_2$ and $x=x\_2x\_1$ according to the figure above, which depicts the parse tree of $z$ as selected above. If we ignore the middle occurrence of $R$, $R$ still repeats. We can continue the usual proof of the usual pumping lemma to obtain that $|vx|\ge1$, $|vwx|\le p$ and $uv^iwx^iy\in L$ for all $i\ge0$.

Suppose both $v\_1$ and $x\_1$ were empty. The parse tree obtained by substituting the subtree rooted at the middle occurrence of $R$ for the subtree rooted at the upper occurrence of $R$ would have fewer nodes than $\tau$ does and would still generate $z$. This result isn't possible because we had already chosen $\tau$ to be a parse tree for $z$ with the smallest number of nodes. Hence either $v\_1$ or $x\_1$ is non-empty. Similarly, either $v\_2$ or $x\_2$ is non-empty. So $vx=v\_1v\_2x\_2v\_2$ must have length at least $2$.
> 2 votes

---
Tags: formal-languages, context-free, formal-grammars, pumping-lemma
---


# Question
Title: What is meant by the term "prior" in machine learning
I am new to machine learning. I have read several papers where they have employed deep learning for various applications and have used the term "prior" in most of the model design cases, say prior in human body pose estimation. Can someone explain what does it actually means. I could only find the mathematical formulation of prior and posterior in the tutorials.

# Answer
Put simply, and without any mathematical symbols, **prior** means *initial beliefs about an event in terms of probability distribution*. You then set up an experiment and get some data, and then "update" your belief (and hence the probability distribution) according to the outcome of the experiment, (the posteriori probability distribution).

**Example:** Assume we are given two coins. But we don't know which coin is fake. Coin 1 is unbiased (HEADS and TAILS have 50% probability), and Coin 2 is biased, say, we know it gives HEADS with probability 60%. Mathematically:

Given we have HEADS, the probability that it is Coin 1 is 0.4 $$p(H | Coin\_1) = 0.4$$ and probability it is Coin 2 is 0.6 $$p(H| Coin\_2) = 0.6$$

So, that is all what we know before we set up an experiment.

Now we are going to pick a coin toss it, and based on the information what we have (H or T) we are going to guess what coin we have chosen (Coin 1 or Coin 2).

Initially we assume $p(Coin\_1) = p(Coin\_2) = 0.5$ both coins have equal chances, because we have no information yet. This is our **prior**. It is a **uniform** distribution.

Now we take randomly one coin, toss it, and have a HEADS. At this moment everything happens. We compute **posterior** probability/distribution using Bayesian formula: $$p(Coin\_1 | H) = \frac{p(H | Coin\_1)p(Coin\_1)}{p(H | Coin\_1)p(Coin\_1) + p(H | Coin\_2)p(Coin\_2)} = \frac{0.4\times0.5}{0.4\times0.5 + 0.6\times0.5} = 0.4$$

$$p(Coin\_2 | H) = \frac{p(H | Coin\_2)p(Coin\_2)}{p(H | Coin\_1)p(Coin\_1) + p(H | Coin\_2)p(Coin\_2)} = \frac{0.6\times0.5}{0.4\times0.5 + 0.6\times0.5} = 0.6$$

So, initially we had $0.5$ probability for each coin, but now after the experiment our beliefs has changed, now we believe that the coin is Coin 1 with probability 0.4 and it is Coin 2 with the probability 0.6. This is our **posterior** distribution, **Bernoulli** distribution.

This is the basic principle of Bayesian inference and statistics used in Machine learning.
> 17 votes

# Answer
**It's roughly any pre-training choices you encode into your model**

In machine learning a prior is, according to the book "Deep Learning" by Goodfellow, Bengio, and Courville, a probability distribution over the parameters of your machine learning model. So as I understand it according to this definition your priors determine how you randomly select your initial parameters before you start training. An alternative definition according to this website is more general, basically any configuration of parameters or model choices that you make *prior to starting training*.

So it looks like the term prior in machine learning is sometimes applied less rigorously than in statistics, though it is either based on, or at least inspired by the corresponding term in the field of statistics.
> 1 votes

# Answer
In Bayesian statistics, a "prior" represents the beliefs we have before observing some data. Then, after we observe some data, we update our beliefs; those updated beliefs are called the "posterior".

Statistical machine learning can be viewed through this lens. The "priors" are the beliefs we hold or we try to enforce/encourage a model to hold even before it is trained with any training data. The observed data is the training data, and the machine learning model is trained on this data. After it finishes training, the final model is the posterior. Here are some examples:

In natural language processing, one "prior" belief we might have is that if two words tend to be used in the same context, there is a decent chance they are related. For instance, even if you didn't know the meaning of "good" or "delicious", if I told you that "lip-smackingly" was often followed by either the word "good" or the word "delicious", you might suspect that "good" and "delicious" might mean something similar (or are somehow related). That's a prior belief -- it's something we might believe is true, even before we've seen any data. Starting from that prior, we might design a word embedding like GloVe, use it to encode sentences before feeding them to a machine learning model, and train the model. In this way, we have build a model that respects our "priors" (our beliefs before we saw the training data).

In image classification, one "prior" belief we might have is that if it's useful to look for a particular pattern -- e.g., straight lines -- in the upper-right of an image, it's also useful to look for them everywhere in the image. That's a "prior" because it's an assumption or belief or hypothesis we hold, even before training on any training data. We might then build a neural network architecture, such as a convolutional neural network, that behaves in a way that is motivated by or is consistent with this "prior". Then, we can train such a network on training data, to obtain a specific model. This illustrates how an architecture can embed a prior (in this case, translation-equivarance), either deliberately or inadvertently. Convolutional neural networks are biased towards performing well on types of images that are consistent with this "prior", and performing poorly on types of images that are inconsistent with this "prior".

In some applications of statistical modeling, one prior is that there are many features but only a few are relevant to the quantity we wish to predict. Lasso regression was invented to deal with this situation: it is linear regression, but starting from a prior that the coefficients for most features should be zero, and probably only a few features should have a non-zero coefficient. In contrast, linear regression doesn't start with any assumption or information about what the coefficients are likely to look like. Lasso regression will perform better than linear regression on tasks where the assumption is appropriate.

In particular, having an informative "prior" can be a good thing. It can help the model perform better, given a limited amount of training data, because the model starts with some knowledge -- it doesn't start from nothing.
> 1 votes

---
Tags: terminology, machine-learning, pattern-recognition, bayesian-statistics
---


title: Time Complexity for the given algorithm

text:
# Question
Title: Time Complexity for the given algorithm
Recently, I had to implement the following algorithm (similarly). Code in Kotlin:

```
fun solution(keyword: String, lyric: String): Boolean {
        val lyricWords = music.split(" ")
        var index = 0
        for (word in lyricWords) {
          for (c in word) {
            if (c == keyword[index]) {
              index++
              break
            }
            if (index == word.size) return true
        }
        return false
 }

```

My intuition to the runtime analysis, given `n` to be the length of lyric and `m` the length of keyword:

1. O(n) for the `split` operation, since it should scan the entire string looking for spaces.
2. Roughly O(n) for the second for-loop, since it would iterate through all the characters for every word in the worst case.
3. O(m) for the internal for-loop over all characters in keyword.
4. Overall, should that take under O(n+m)?

What would be the time complexity for the above function?

# Answer
> 1 votes
For loop inside For loop indicates multiplication of time complexity parts.

For loop following for loop indicates addition of time complexity parts.

So I'd expect: $O(mn)$

That is to say. You doing $O(m)$, $n$ number of times. Thus $O(mn)$.

---
Tags: algorithms, algorithm-analysis, runtime-analysis, strings
---


title: Optimality of DSATUR on interval graphs

text:
# Question
Title: Optimality of DSATUR on interval graphs
The DSATUR algorithm is a greedy graph coloring algorithm. It consists of applying the usual greedy coloring algorithm, considering vertices in reverse lexicographic order of *(number of different colors among neighbours, total number of neighbours)*.

Though not always optimal, this algorithm is already known to be optimal on certain families of graphs, like cycles or bipartite graphs.

An interval graph is a non-directed graph $G = (V, E)$ such that there exists a set of intervals $(I\_v)\_{v\in V}$ such that $\\{u, v\\}\in E\iff I\_u\cap I\_v\neq \emptyset$.

My question is: is DSATUR optimal for interval graphs?

I already know that there are efficient optimal coloring algorithms for interval graphs, whether you know the corresponding interval set or not, but that is not the question.

My first intuition was that DSATUR was not always optimal, and as a tentative to find a counterexample, I tested 130 millions randomly generated interval graphs, of order between 10 and 20, but none was a counterexample.

That leads me to think that maybe it **is** optimal, but I have no real idea as to how to prove it.

As suggested by Juho in the comments, I tested the property for **ALL** interval graphs of order up to 12, and DSATUR is indeed optimal on those graphs.

# Answer
Yes. DSATUR produces an optimal coloring for interval graphs. My idea is as follows (Please identify any potential issues). We know that **a)** In DSATUR, once a new vertex has been colored then we should determine which of the remaining uncolored vertices has the highest number of colors in its neighborhood to color this vertex next. **b)** For interval graphs a greedy coloring algorithm (by choosing the vertex ordering to be the reverse of a perfect elimination ordering) can be used to find an optimal coloring in polynomial time.

**Theorem.** By running the DSATUR algorithm, if we color the vertices of $G=(V,E)$ in order $v\_1,v\_2,...,v\_n$ then we have a perfect elimination scheme $v\_n,v\_{n-1},...,v\_2,v\_1$ on $G$.

**Proof.** By induction. It is true for $n=1,2,3$. Suppose that it is true for $n-1$ and we want to prove it for $n$.

By removing $v\_n$ to produce $G'$, all of vertices $v\_i$ ($i=n-1,...,1$) are simplicial on $G'$ ($v\_i$ is simplicial if all of its neighborhood $v\_j$ where $j\<i$ induce a complete subgraph) and on $G$ and we have to prove this only for $v\_n$.

If $v\_{n-1}v\_n\notin E$ then simplicial characteristic of $v\_n$ is simply proved by removing the vertex $v\_{n-1}$ to produce $G'$. Here, the order of coloring by DSATUR is unchanged and based on induction hypothesis, $v\_n$ is simplicial on $G'$ and (due to $v\_{n-1}v\_n\notin E$) on $G$.

Suppose that $v\_{n-1}v\_n\in E$. If the vertex degree of $v\_n$ is 1 then it is simplicial on $G$. Otherwise, suppose that $v\_t$ ($t\<n-1$) is the last vertex which is adjacent to $v\_n$ and during the execution of DSATUR, after coloring of $v\_t$ the DSATUR number of the vertex $v\_n$ is $k$; i.e. After coloring of $v\_t$ always there exist a vertex $v\_i$ ($t\<i\<n$) with a DSATUR number greater than or equal to $k$.

Now remove $v\_t$ to produce $G'$. By execution of DSATUR on $G'$ the order of coloring is unchanged until $v\_{t-1}$ and after coloring of $v\_{t-1}$, the DSATUR number of the vertex $v\_n$ is $k-1$ and always there exist a vertex $v\_i$ ($t\<i\<n$) with a DSATUR number greater than or equal to $k-1$; i.e. The vertex $v\_n$ is the last colored vertex and the DSATUR algorithm colors the vertices of $G'=(V-\\{v\_t\\},E')$ in order of $v\_1,...,v\_{t-1},v\_{i1},...,v\_{it},v\_n$ where $t\<i1,...,it\<n$. Therefore, based on the induction hypothesis $v\_n$ is simplicial on $G'$.

We should prove that it is impossible to have $v\_{n-1}v\_t\notin E$ (Note that, if $v\_{n-1}v\_t\in E$ then $v\_n$ is simplicial on $G$, too). Based on the above result $v\_{n-1}$ is adjacent to all of neighborhoods of $v\_n$ except to $v\_t$. Then, suppose that the vertex degree of $v\_n$ is greater than 2 and $v\_l$ ($l\<t\<n-1$) is the last vertex which is adjacent to $v\_n$ and during the execution of DSATUR, after coloring of $v\_l$ the DSATUR number of the vertex $v\_n$ is $k-1$; i.e. After coloring of $v\_l$ always there exist a vertex $v\_i$ ($l\<i\<n$) with a DSATUR number greater than or equal to $k-1$.

Now remove $v\_l$ to produce $G'$. By execution of DSATUR on $G'$ the order of coloring is unchanged until $v\_{l-1}$ and after coloring of $v\_{l-1}$, the DSATUR number of the vertex $v\_n$ is $k-2$ and always there exist a vertex $v\_i$ ($l\<i\<n$) with a DSATUR number greater than or equal to $k-2$; i.e. The vertex $v\_n$ is the last colored vertex and the DSATUR algorithm colors the vertices of $G'=(V-\\{v\_l\\},E')$ in order of $v\_1,...,v\_{l-1}, v\_{i1},...,v\_{il},v\_n$ where $l\<i1,...,il\<n$. Therefore, based on the induction hypothesis $v\_n$ is simplicial on $G'$ and we should have $v\_{n-1}v\_t\in E$.

Finally, suppose that the vertex degree of $v\_n$ is equal to 2 and we cannot select such a vertex $v\_l$ in the above proof. Hence, during the execution of the algorithm, the DSATUR number of $v\_n$ is $0$ until coloring of vertex $v\_t$ which increases the DSATUR number of $v\_n$ to $1$. Then, there exist no common neighborhood for the vertices $v\_{n-1}$ and $v\_t$, due to the construction of a cycle with no chord. Moreover, There exist no common neighborhood for the neighborhoods of vertices $v\_{n-1}$ and $v\_t$, due to the construction of a cycle with no chord and so on. Therefore, the vertices $v\_t,v\_{n-1}$ and $v\_n$ are (only) on some paths and by execution of DSATUR on these paths the vertex $v\_n$ is colored between two vertices $v\_t$ and $v\_{n-1}$. Hence, it is impossible to have a coloring order $v\_1,...,v\_t,...,v\_{n-1},v\_n$ in DSATUR algorithm which is a contradiction.
> 0 votes

---
Tags: graphs, greedy-algorithms, colorings, intervals
---


# Question
Title: Are the set of all Bitcoin addresses a context-sensitive language?
This started with me trying to make a regex to accept Bitcoin addresses. However, I couldn't do it. That led me to think: "is the set of all possible Bitcoin addresses even a regular language"?

For simplicity, consider only "legacy" P2PKH Bitcoin addresses: a valid address consists of the character "1" followed by 25 to 33 Base58 (`123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz`) symbols. There is an additional constraint that the last 32 bits of the address are a checksum which equals the first 32 bits of the result of the double SHA-256 hash of the rest of the address.

Obviously, the set of Bitcoin addresses under this definition is a regular language because it is finite, although this is probably no solace to anyone who wants to write a regex to validate it! But it's more interesting to think about Bitcoin addresses of unbounded length. I believe this is not a regular language, and the pumping lemma for regular languages can be used to prove that, nor is it a context-free language, once again because of the pumping lemma (for context-free languages), although I'm not as certain because I didn't take the actual time to think of a proof of this. It's also obvious that this new language of Bitcoin addresses of up to any length is recursively-enumerable and recursive, as it's trivial to write some C code to validate strings in it and also generate strings for it.

Now, the question that I am unable to answer is this: **is the set of Bitcoin addresses with up to any length a context-sensitive language?**

Forgive me if this is a question with an obvious answer; I only learned this stuff last term :)

# Answer
Any answer I give you is likely to be unsatisfying and a little silly, both because we're squarely in theory-land here (and not the useful kind of theory, but theory that is irrelevant in practice), but also because of an oddity of the SHA256 hash: the SHA256 hash was not designed to hash messages that are longer than $2^{64}$ bits long. The SHA256 spec is not 100% clear (and I can't blame the authors, as it's ridiculous to imagine hashing such long messages), but it appears that the hash is not defined for longer messages, so Bitcoin addresses longer than that are not well-defined.

As a result of this oddity, arguably this language is finite: because it seems to suggest that Bitcoin addresses have an upper limit on their length, there are only finitely many valid addresses, so it is regular by definition. This is silly and useless in practice because the number, while finite, is so ridiculously large that you'd never want to recognize it using a DFA or regular expression.

But what if we let that bit of silliness go, and assume that SHA256 is well-defined for longer messages? Well, then we have to decide how to hash messages longer than $2^{64}$ bits, which is not something the SHA256 spec describes. The spec says that we append the length of the message, expressed in a 64-bit word. So what should we do if the length is longer than $2^{64}$? Perhaps we use the length modulo $2^{64}$ (even though there is nothing in the spec saying to do that)? In that case, the language is regular, since SHA256 can be computed in a streaming way with a finite amount of space, so you can check membership in this language with a finite-state automaton. In general, if you can check membership using $O(1)$ space, the language is regular, and that would apply here. But that would be purely theoretical, because the finite-state automaton would have a humongous number of states, so you'd never want to compute it using a regular expression.

What if we invent a different variant of SHA256 that appends the length, but not limiting it to a 64-bit word? In that scenario the language would be almost certainly not regular, as counting the length is something you can't do with a finite-state automaton. Yes, it would be certainly context-sensitive: you can check membership using $O(n)$ space, where $n$ is the length of the address (in fact $O(\log n)$ space suffices, as all we need is to keep track of the length), which means it can be recognized by a linear bounded automaton (LBA), hence it is context-sensitive.

At risk of stating the obvious: In practice, all of this is irrelevant (as I suspect you are already aware). Language theory is not the right tool to recognize Bitcoin addresses. Instead, parse them, and then check whether the SHA256 hash is correct.
> 4 votes

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


# Question
Title: Alternate proof of the Caro-Wei theorem for lower bounding the independence number
Let $G$ be a graph on $n$ vertices whose degree sequence is $d\_1,d\_2,...,d\_n$. Let $\alpha(G)$ denote the size of maximum independent set of $G$, i.e., the size of a maximum subset of vertices of $G$ that are pairwise non-adjacent. So Caro-Wei says that $\alpha(G) \geq \sum\_{d\_i \in V(G)}{\frac{1}{1+d\_i}}$. The standard probabilistic proof goes as follow, here we let $V(G)=\\{1,2,...,n\\}$:

Consider the set $S\_n$ of permutations of the vertices in $G$ and $\sigma \in S\_n$ be a permutation in $S\_n$. Let $A\_i$ be the event that $\sigma(i)\<\sigma(j), \forall j \in N(i)$ namely all neighbours $j$ of the vertex $i$ gets maps to by $\sigma$ to some number greater than $\sigma(i)$. There are $\binom{n}{1+d\_i}$ places that $\sigma$ can map the vertex $i$ and its neighbors to. Futhermore, $\sigma(i)$ is the smallest, so there are $d\_i!$ ways for the neighbours of $i$ to be map to and $(n-d\_i-1)!$ ways for the remaining number to be permuted. So $P(A\_i)=\frac{\binom{n}{d\_i+1} d\_i!(n-d\_i-1)!}{n!}=\frac{1}{1+d\_i}$. Now consider the subset of the vertex set of $G$, $U=\\{i \mid A\_i = \text{true}\\}$. Notice that two vertices in $U$ does not share an edge. The expected value $E\[|U|\]=\sum\_{i\in \\{1,...,n\\}}{\frac{1}{1+d\_i}}$. So done.

But I'm wondering if there is a proof not involving probabilistic method.

# Answer
> 2 votes
An algorithmic proof is given by Murphy \[1, Section 1\], where he attributes the algorithm to Erdös \[2\].

As a side remark, I don't know what the original proof of Caro or Wei is, but I believe the proof you mention is due to Alon and Spencer \[3\].

---

\[1\] Murphy, Owen. "Lower bounds on the stability number of graphs computed in terms of degrees." Discrete Mathematics 90.2 (1991): 207-211.

\[2\] Erdös, Paul. "On the graph theorem of Turán." Mat. Lapok 21. (1970): 249-251.

\[3\] Alon, Noga, and Joel H. Spencer. The Probabilistic Method. John Wiley & Sons, 2004.

# Answer
> 1 votes
There are several non-probabilisitc proofs : 1/ using greedy algorithm deleting minimum degree : See : https://www.sciencedirect.com/science/article/pii/S0166218X13001339 https://onlinelibrary.wiley.com/doi/10.1002/jgt.3190150110

2/ deleting vertices of maximum degree : see :https://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i1p33

There are everal more variations.

My original 1999 proof was via induction and deleting vertex of maximum degree.

# Answer
> 1 votes
Induction on the order of G . True for |G| = 1. Assume for |G| = n let prove it for |G| = n +1. Choose a vertex v of minimum degree . Consider H = G - N\[v\]. Clearly a(G)\> = 1 + a(H) \> = 1 + sum { 1/( deg\_H(u) +1) :u in V(H)} \> = \** sum { 1/(deg\_G(w)) +1 ) :w in N\[{v\] } + sum { 1/( deg\_H(u) +1) : u in V(H)} = sum { 1/(deg\_G(w)) +1 ) : w in N\[{v\] } + sum { 1/( deg\_G(u) +1 : u in V(G)\N\[v\]}= sum { 1/(deg(w)+1 ) w in V(G) }. deg\_G(w) the degree of w in G , deg\_H(u) the degree of u in H. \** observe 1=sum {1/(deg(v)+1 ):w in N\[v\] } \> = sum{ 1/(deg\_G(w) +1) : w in N\[v\] } as v has minimum degree . Best - Yair Caro .

---
Tags: graphs, proof-techniques, combinatorics, discrete-mathematics
---


# Question
Title: How to analyze the amortized running time of indexed linked list operations using potential method?
I have implemented an indexed linked list that runs (under mild assumptions) all single-element operations in $\mathcal{O}(\sqrt{n})$ time. The description is here and Java implementation is here.

It’s clear to me that the running time is linear in $n$ in the worst case, but I would love to see something smarter than that.

The idea is to maintain a list of *fingers*. Each finger $f$ has two fields: (1) $f.node$ pointing to a linked list node, and (2) $f.index$ being the actual index of the node pointed by $f.node$.

Now, the finger list has size $\lceil \sqrt{n} \rceil$, and it’s sorted by finger indices. Given an element index $i$, we can access it as follows:

Apply C++ lower\_bound to find the closest to $i$ finger $f$, and ”rewind” $f.node$ to point to the $i$th node. (Set $f.index \leftarrow i$ also.) This applies to the get operation and runs in logarithmic time. Assuming that the fingers are distributed more or less evenly, rewinding will run in $\mathcal{O}(n / \sqrt{n} = \sqrt{n})$ time.

For the insert/removeAt operations, both do (1) finger list lookup in logarithmic time, (2) finger node rewind in $\mathcal{O}(\sqrt{n})$, and (3) also update the finger indices that runs in, too, $\mathcal{O}(\sqrt{n})$.

# Answer
> 0 votes
Suppose we are appending elements to the tail of the list. Suppose also that the rightmost finger has index $f$. Now, the distance between $f$ and the second rightmost finger $f - 1$ (which should be the largest since we are comparing two rightmost fingers (the distance between adjacent fingers grows as we scan the fingers from left to right)), is given by $$ \begin{aligned} f^2 - (f-1)^2 &= f^2 - (f^2 - 2f + 1) \\ &= 2f - 1 \\ &\overset{1}{=} 2\Big\lceil \sqrt{n} \Big\rceil -1\\ &= \Theta(\sqrt{n}). \end{aligned} $$ We conclude that appending all the elements one by one keeps the finger indices (in asymptotic sense) evenly distributed.

(Above, we have (1) by the data structure invariant.)

---
Tags: heuristics, linked-lists, succinct-data-structures
---


# Question
Title: Prove or disprove that the language $L = \{xcy\, | \, x,y\in \{a,b,c\}^\star, |x|_a = |y|_b \}$ is context free
Let me cross post my question from math.stackexchange, since I feel this community is more related to the field.

Title is self explanatory. I want to know is the language $L = \\{xcy \\,| \\,x,y\in \\{a,b,c\\}^\star, |x|\_a = |y|\_b \\}$ is context-free.

I tried to prove that is not context-free using a proof by contradiction. Assuming that it is context-free we may apply the pumping lemma on the word $$a^pcb^p\\,,$$ where $p$ is the pumping length of $L$.

Letting $a^pcb^p = z\_1u\_1vu\_2z\_2$, where $$\begin{gather} z\_1u^k\_1vu^k\_2z\_2\\,,\quad \text{for } k=0,1,2,\ldots \\ |u\_1u\_2| \> 0 \quad \text{and} \quad |u\_1vu\_2| \leq p \end{gather}\\,.$$ I took cases on the consistency of $u\_1u\_2$; i.e. if it consists only of $a$'s or if it has a $c$. Every case, except the follwing

* $u\_1u\_2$ consists of $a$ and $b$ but no $c$

wields a contradiction. The above case seems to produce no contradiction. Hence my method failed.

Do you know if the language $L$ is context-free? Could you explain how to obtain the answer?

# Answer
> 2 votes
Start with *the* context-free language for beginners $\\{ a^nb^n \mid n\ge 0\\}$.

> $S\to aSb\mid \varepsilon$

Instead end with the symbol $c$ in the middle.

> $S\to aSb\mid c$

Now sprinkle the left and right parts with free $b,c$ and free $a,c$ respectively.

> $S\to aSb\mid c \mid bS\mid cS\mid Sa\mid Sc $

And I think we are actually ready to go!

# Answer
> 5 votes
Well this is a basic context-free language and you should easily realize it's context-free, I guess what confused you is that $x,y\in\\{a,b,c\\}^\*$ and the word is $xcy$ so you didn't know how to deal with the $c$, I recommend for questions like this you try to solve it in the form $x\\#y$ where $\\#\notin\Sigma^\*$ and then solve the original problem.

---

Think about your problem like this: for each $a$ you read in $x$ insert $0$ to the stack, non-deterministically guess when the $x$ ends (by seeing the letter $c$), and from now on for each $b$ you read in $y$ remove $0$ from the stack, at the end if the stack is empty then the word is in the language. As a tip, try to prove this language $L=\\{x\\#y:x,y\in\\{a,b,c\\}^\*,|x|\_a=|y|\_b\\}$ is context-free.

---

This is a PDA that describes your language:

---
Tags: context-free
---


# Question
Title: How to prove non-regularity with Myhill-Nerode theorem?
I have a problem in proving of nonregularity of EQ\_n = {u = v2v : |v| = n}. I just dont know how to start. Can you help me?

# Answer
> 0 votes
If the alphabet is only $\\{2\\}$, then the language is regular.

Otherwise, there's at least one other letter, let's say $a$. Then the infinitely many words $a^i2$ are all pairwise non-equivalent.

# Answer
> 0 votes
Notice that it's preferable in that case (and in general too) to use the conclusion of myhill-nerode theorem which is: if there are infinite strings such that every two strings $w,s$ satisfies $w\not\equiv\_Ls$ then the language $L$ isn't regular.

So in your case, you can take the strings $w\_i=a^i2$ and the string $z=a^i$. For each $i,j\in\mathbb{N}$ and $i\neq j$: $$w\_i\circ z=a^i2\circ a^i\in L$$ $$w\_j\circ z=a^j2\circ a^i\notin L$$

The first string is $a^i2a^i$ then it's in the language since $|a^i|=|a^i|$. However, the second string is $a^j2a^i$ and since $i\neq j$ then $|a^i|\neq|a^j|$ and therefore the string isn't in the language.

We have found infinite strings such that for every two strings $w,s$, $w\not\equiv\_Ls$ and therefore $L$ isn't regular. QED.

---
Tags: regular-languages
---


# Question
Title: $(Q\to R)\wedge (R\to Q)$ converting to sentence
Well, I am following this video lecture (MOOC) and I came across this quiz where I have to convert $(Q\to R)\wedge (R\to Q)$ to sentence.

$Q$: "I will go to town"

$R$: "I have time"

My answer to $(Q\to R)\wedge (R\to Q)$ is

"I will go to town ONLY IF I have time AND I have time ONLY IF I will go to town".

Whereas, the professor teaching in video gave following answer:

"I will go to town ONLY IF I have time AND IF I have time I will go to town".

I don't get the answer given by professor because it changes the meaning of sentence after 'AND'.

NOTE: Further professor explain that this can be converted to equivalent "If and Only If", but my concern is not on equivalence. I understand that part.

Thank you in Advance!

# Answer
Your answer and the professor's answer are both correct. Other ways to say $p$ implies $q$ are: "if $p$ then $q$" and "$p$ only if $q$". You can replace "only if" by "implies".

Thus, "I have time ONLY IF I will go to town" and "IF I have time I will go to town" both say the same thing - "I have time implies I will go to town".
> 1 votes

# Answer
## There are multiple ways of understanding **IMPLICATIONS** statements. In brief,

**x**$\implies$ **y** can be written as

* **if** x **then** y
* y **if** x
* x **only if** y
* x **is sufficient for** y
* y **is necessary for** x
* x **implies** y
* y **is implied by** x
* ~y **implies** ~x
* y **provided** x
* y **follows from** x
* y **whenever** x
* y **without** x **is possible**
* x **without** y **is not possible**

Now, many of these might sound *confusing* in one go, but with *examples* and *repetition of thought process*, they become clear. One more thing, that while practicing question, we should often ignore our understanding of nature and the thought process if it is possible or not. Moreover, this might sound confusing because of our understanding of *English Language* and more specifically *Tenses*. Translating these in mother tongue often helps!

## Now, **the question**.

$Q :$ "I will go to town"
$R :$ "I have time"

Now, $Q \implies R$ using **only if** will give :

> I will go to town **ONLY IF** I have time.

Now, $R \implies Q$ using **if-then** will give :

> **IF** I have time **THEN** I will go to town.

Thus, if your professor has used word **"THEN"** then his solution is correct. Otherwise, not being so strict on language, if we even miss **THEN**, and had a pause (comma) instead of **THEN**, *\[then\]* the meaning doesn't change. Although, correct solution among multiple correct solutions is :

> *I will go to town **ONLY IF** I have time* **AND** ***IF** I have time **THEN** I will go to town.*

## REFERENCES

Page 335-336 of this Textbook *(Page 15-16 of PDF)* **and** Page 251-252 of this Textbook *(Page 6-7 of PDF)*.
> 0 votes

# Answer
IMO both you and the teacher read in a contrived way. I would say "I go to town implies that I have time and I have time implies that I go to town".

Note that as this is formal logics, no causation should be considered. (I am not going to town *because* I have time nor conversely; it is just two events that will simultaneously occur or not occur.)
> 0 votes

# Answer
Note that

$$Q\iff R\equiv(Q\to R)\wedge (R\to Q).$$ Hence your professor and you say same thing.
> -1 votes

---
Tags: discrete-mathematics
---


# Question
Title: Variant of the Knapsack Problem 0-1 - One item from each set and zero-weighted items
I understand the basics of the 0-1 problem and its solution.

I have a variant of it that I'm trying to solve in a decent way and I'm struggling on it, mostly because of the 0-weighted items. These are the rules:

* I have k finite sets of items. Each item has a weight and a value.
* I must take exactly one item from each set.
* Zero-weighted items are allowed. But since you are not allowed to take more than one item from each set, it's not always convenient to take them.
* Weights in each set are the first natural numbers {0, 1, 2, 3...i}.
* In each set, values are non-decreasing when the weight increases.
* I want to determine which items maximize the total value for a certain total weigth.

example:

| Set | Weight 0 | Weight 1 | Weight 2 | Weight 3 | Weight 4 | Weight 5 |
| --- | --- | --- | --- | --- | --- | --- |
| **A** | 3 | 6 | 6 | 9 | 15 | 26 |
| **B** | 0 | 6 | 8 | - | - | - |
| **C** | 1 | 1 | 10 | 15 | 16 | - |

The notation "B3" means "Select the object from set B that weights 3".

The solutions for a maximum total weight = n are:

* n=0 -\> \[A0; B0; C0\] =\> Total Value = 4
* n=1 -\> \[A0; B1; C0\] =\> Total Value = 10
* n=2 -\> \[A0; B0; C2\] OR \[A1;B1;C0\] =\> Total Value = 13
* n=3 -\> \[A0; B1; C2\] =\> Total Value = 19
* n=4 -\> \[A0; B1; C3\] =\> Total Value = 24
* n=5 -\> \[A1; B1; C3\] OR \[A5;B0;C0\] =\> Total Value = 27
* n=6 -\> \[A5; B1; C0\] =\> Total Value = 33
* n=7 -\> \[A5; B0; C2\] =\> Total Value = 36
* n=8 -\> \[A5; B1; C2\] =\> Total Value = 42
* n=9 -\> \[A5; B1; C3\] =\> Total Value = 47
* n=10-\> \[A5; B2; C3\] =\> Total Value = 49
* n=11-\> \[A5; B2; C4\] =\> Total Value = 50
* n\>=12 it's the same as n=11.

Do you have some clue for implementing a decent algorithm to find the best combination of items to solve this problem with a generic collection of such set? Thanks!

# Answer
> 0 votes
If weights aren't too large, use the standard pseudo-polynomial-time algorithm (using dynamic programming) for the knapsack problem. It is easy to adjust to this setting. See https://en.wikipedia.org/wiki/Knapsack\_problem#0-1\_knapsack\_problem.

If weights can be large, use integer linear programming, and apply an off-the-shelf ILP solver.

# Answer
> 0 votes
If I have realized the problem, I think this problem is more similar to matching problem than knapsack problem.

In other words, you can introduce a bipartite graph with two sets $S$ of objects (A, B, C, ...) and $T$ of weights ($0, 1, 2 ,...$) and a weighted arc between each object i to each weight j; e.g. weight of the edge $v\_{A5}$ is equal to $26$ in your example.

Then, to produce a solution with maximum weight, you can not select more than one item from each weight (Otherwise, we don't need to solve any problem and the solution is to select the largest weights from each object). Therefore, you can solve the maximum matching on the proposed graph (if you want to select at most one item from each object and at most one item from each weight).

But, if you can select more than one item from each weight then you should add another constraint to the problem; e.g. Weighted sum of the selected objects is less than $k$. In this case, introduce decision variables $x\_{ij}:=\\{1: $ if we select object from set i that weights j , $0:$ Otherwise $\\}$ and solve the following ILP model:

$min\ \sum\_{i,j}w\_{ij}x\_{ij}\ $

1. $\sum\_{j}x\_{ij} = 1 \ \ i\in S$
2. $\sum\_{i,j}w\_{ij}x\_{ij} \le k$
3. $x\_{ij} \in \\{0,1\\}$

---
Tags: algorithms, knapsack-problems, optimal-strategy
---