# Question
Title: Can all optimizations be expressed in source code?
If someone compiled a program with all optimization settings enabled, would it be possible to create source code that, if it was compiled with all optimizations disabled, produced an identical binary? We'll assume that inline assembly and similar features are not used. If this is not always possible, (and I suspect it probably isn't) what language features or particular types of compiler optimizations make "fully pre-optimized" source code impossible?

# Answer
The key to remember is that, at its core, a compiler is just a translator between two languages. One is often machine code, and there may be some intermediate steps, but translation is the key.

With that in mind, an optimization is one of three things:

1. A transformation from source programs to source programs, that is (hopefully) observationally equivalent to the original program, that is (hopefully) faster
2. A transformation from source programs to target that takes advantage of some property of the source program to generate code that is equivalent to, but faster than, the "vanilla" compiled version of the code.
3. A transformation from target programs to target programs that produces equivalent but faster code.

(3) could happen after compilation, since it doesn't rely on source input at all, and (1) could happen in an interpreted language as much as a compiled one.

Naturally, (2) can encompass programs that can't necessarily be expressed in the source language. It all depends the properties of your transformation. Is it a surjection between your source and target languages?

If it's not surjective, and both languages are Turing Complete, then:

* There must be some programs in the target language which are never the result of compilation
* Each "unreached" target program is equivalent to some source program (since both languages are Turing Complete)

Some of these will likely be optimizations.

For some practical examples:

* Tail-call elimination is not expressible as a source-to-source transformation in any language with higher-order functions lacking GOTO
* Any optimization using a "special" CPU instruction can't be expressed as a source-to-source transformation, since there's no way to access that instruction from the source language.

There are likely many more. (Community: feel free to add examples as you see fit!)
> 4 votes

---
Tags: optimization, programming-languages, compilers, language-design
---


# Question
Title: Construct a DFA which accepts a string of length 5 with at least 2 0's
How to design a DFA of all strings over (0,1) such that every block of 5 consecutive symbols contains at least 2 0's?

# Answer
> 1 votes
The question asks HOW TO DESIGN, you don't have to write the whole DFA, but you can if you want to. Just describe how you would design.

There are 32 strings of length 5. Some of them do not contain at least two 0s, some do. Those that do not contain at least two 0s should lead to the DEAD state (from which there is no return). But those that do have at least two 0s should lead to a state that checks another block of 5 symbols.

Try to draw a binary tree of depth 5, with 0 as the left child and 1 as the right child for each node. Does it help design the DFA? For simplicity first try to design for blocks of 3 symbols not 5.

---
Tags: formal-languages
---


# Question
Title: How can a set of N players be split into M teams, given certain rules?
A lot of times, I’ve needed to split a given set of people into a given number of teams but with some complications, like:

* Alice and Bob CANNOT be on the same team.
* Carol and David just HAVE TO BE on the same team.

I feel like this is already a thing. There's gotta already be work in this problem. Where would I even start, in terms of an algorithm? It definitely can't be brute-forced.

# Answer
> 4 votes
Denote each person as a single vertex and connect them by an edge if they are not allowed to be in the same team. If several people have to be on the same team, use a single vertex to represent all of them. Then color the resulting graph by $k$ colors, where $k$ is the number of teams.This problem is the graph coloring problem. To complicate things you may require color certain vertices in the same color. Please follow this for other types of colorings.

---
Tags: sets
---


# Question
Title: Maximizing product of list of integers whose sum equals n
Given a positive integer **n**, find the list of positive integers whose **product is the largest** among all the list whose **sum is n**. For example, if **n** is 4 the desired list is 2, 2 because 2x2 = 4 is larger than 1x1x1x1 = 1, 2x1x1 = 2 and 3x1 = 3, if n is 5, the desired list is 2, 3.

What is the desired list if **n** = 2001?

Actually, what is an algorithm to generate this list? After tried lots of examples, I discern (hope am right) for **n** \> 5 it's a list of 3's, and a remainder **n** % 3.

So, for **n** = 2001, I got a list of 667 3's.

**Question**

If Correct, what property of 3 makes it the ideal integer in that it composes (mostly) this list?.

# Answer
> 6 votes
Intuitively the function $(n/x)^x$ is maximized at $x=\frac{n}{e}$ and 3 is closest to $e$.

# Answer
> 1 votes
The property that makes 3 special in this case is that it can only be decomposed into sums whose products are smaller than 3. That is, $3\cdot0 = 0$, and $2\cdot1=2$.

Think of it like this. Given a list of integers $\[x\_1, x\_2, ..., x\_n\]$ that sum up to the desired $y$, we have the product $x\_1 \cdot x\_2, \cdot ...\cdot x\_n$ (obviously). For each $x\_i$ if there is a a set of integers $j,k,l,...$ with $x\_i = j + k + l + ...$ such that $x\_i \< j \cdot k \cdot l \cdot ...$ then we can replace $x\_i$ in the original list with $j,k,l,...$ and increase the product. The numbers that can't be decomposed, 2 and 3, will makeup the final list. The trick for optimizing is the choice of $j,k,l,...$.

---
Tags: algorithms, optimization
---


title: Find the appropriate product

text:
# Question
Title: Find the appropriate product
I have a number $n$ and an integer $x$ which ends on $1, 3, 7 \ or\ 9$, meaning that the last digit (rightmost digit) of $x$ is one of those 4 numbers.

Now if $z = x * y$, what number do I have to choose for $y$ such that the $n$ last (rightmost) digits of $z$ are equal to $1$ (I mean the numerical value of the rightmost $n$ digits of $z$ has to be $1$) while ignoring leading zeros.

Examples:

```
// computes y
long computeY(int n, long x) {
    // ...magic...
    return y;
}

```
* computeY(1, 9) == 9 (because 9\*9 = 81, take the n rightmost digits, result is 1)
* computeY(1, 7) == 3 (because 7\*3 = 21, take the n rightmost digits, result is 1)
* computeY(2, 11) == 91 (because 11\*91 = 1001, take the n rightmost digits, result is 1, ignore leading zeros)
* computeY(3, 17) == 353 (because 353\*17 = 6001, take the n rightmost digits, result is 1, ignore leading zeros)
* computeY(5, 11327) == 23263 (because 11327\*23263 = 263500001, take the n rightmost digits, result is 1, ignore leading zeros)

I encountered this problem during a programming contest at my school and am stuck, It looks like I have to use number theory but I just don't know where to start.

# Answer
> 2 votes
Suppose that you are given the last $n$ digits of $x$, which is the same as knowing $x \bmod 10^n$. You want to find the last $n$ digits of $y$, that is, $y \bmod 10^n$, given that $xy \bmod 10^n = 1$. Since $xy \equiv 1 \pmod{10^n}$, the solution is $y \bmod 10^n = (x \bmod 10^n)^{-1}$, the inverse being taken in $\mathbb{Z}\_{10^n}$. The condition $x \bmod 10 \in \\{1,3,5,7\\}$ guarantees that $(x,10^n) = 1$, and so the inverse always exists.

In order to calculate the inverse, use the extended GCD algorithm to find $a,b$ such that $a(x \bmod 10^n) + b10^n = 1$, and take $y \bmod 10^n = a \bmod 10^n$.

For example, suppose you know that $x \bmod 10^5 = 11327$. The extended GCD algorithm gives $$ 23263 \cdot 11327 - 2635 \cdot 10^5 = 1, $$ and so $y \bmod{10^5} = 23263$.

---
Tags: algorithms, number-theory
---


# Question
Title: Is the term page replacement actually a misnomer?
My understanding is that "page replacement" entails replacing the contents of a frame to bring in a new frame in it's place corresponding to a new page. Since it is not the page, but the frame that changes, shouldn't this process be called "frame replacement"?

# Answer
> 1 votes
> Is the term page replacement actually a misnomer?

No.

* A *page* is the entity in virtual memory.
* A *page frame* is the real memory into which it is mapped.

So it is the page, not the frame, that is replaced.

The metaphor is that the (virtual) page is the picture around which the frame is placed. You move the frame to picture different pages. See here.

---
Tags: terminology, operating-systems, virtual-memory, paging
---


# Question
Title: What problems are believed to have an efficient algorithm?
Just out of curiosity, What problems are believed to have an efficient algorithm, yet haven't been found such an algorithm for them?

This question came up to my mind after reading about PRIMES problem.

I hope this question is appropriate for this forum

Thanks!

# Answer
I'll cover problems that are easy to *solve* (i.e. in $P$) and problems whose solutions are easy to *verify* (i.e. in $NP$), and some problems that are probably not, and try to explain why people think one way or the other.

Under standard complexity-theoretic assumptions, $P=BPP$, meaning that most randomized algorithms can be "derandomized" (this family of conjectures is called the *derandomization hypotheses*). You read about a specific example, PRIMES, and it is expected that that is an instance of a more general phenomenon. So for example, polynomial identity testing probably has a polynomial-time algorithm.

For similar reasons, it is conjectured that $NP=MA=AM$. See the Complexity Zoo for definitions of these classes). One language in $AM$ is graph *non*-isomorphism: the language of all pairs of graphs that are *not* isomorphic. Clearly its complement it in $NP$ (because you can check whether a purpurted permutation is in fact an isomorphism), so surprisingly the fact that two graphs are not isomorphic is something that is expected to be easy to *verify* given some proof. Yet (afaik) we do not know which $BPP$-language we have to derandomize to obtain this result. If $NP=MA$ or $P=RP$, then it is easy to verify that an arithmetic circuit is not minimal.

These sets, $BPP$ and $AM$ are (afaik) the "largest" classes of problems that are expected to collapse to $P$ and $NP$ respectively, meaning they are expected to be easy to solve, respectively, to verify.

So we do not know how to verify non-isomorphism yet, much less *decide* it (as in, solve it in $P$). Is it hard? Is it easy? Interestingly, if Graph isomorphism is so hard that it's NP Complete, then a widely believed complexity-theoretic hypothesis (that "the polynomial hierarchy is infinite") fails, so graph isomorphism is probably not NP-Complete. We do not know of any hypothesis that fails under the assumption that graph isorphism is easy, i.e. in $P$ or in $BPP$. The same goes for factoring: probably not NP-Complete, not known to be easy.\*

Problems in this Wikipedia list of NP-Intermediate problems are not expected to be in $P$.

Linear programming has a polynomial algorithm if you only count the number of arithmetic operations ($+,-,\times$ etc). However, those arithmetic operations may involve numbers that are more than polynomially long, so the algorithm is called *weakly* polynomial. It is expected that there is an algorithm that doesn't suffer from this, called a *strongly* polynomial algorithm. For example, Mihály and Vempala \[1\] recently presented a plausible-looking candidate for such an algorithm.

\*Scott Aaronson once quiped that factoring might as well be in $P$. It would collapse the world economy, sure, but it wouldn't collapse the polynomial hierarchy, so wouldn't be *that* impressive.

\[1\] Bárász, Mihály, and Santosh Vempala. "A new approach to strongly polynomial linear programming." (2010).
> 6 votes

---
Tags: algorithms, efficiency, research
---


# Question
Title: Where/how did a $\log(n)$ factor disappear from well-known algorithms?
Consider the binary search problem on a sorted array containing $n$ integers on 16 bits. Everybody agrees that the binary search needs $O(\log(n))$ time, because it makes at worst $O(\log(n))$ steps. **But**: at each step it needs to calculate a midpoint. The first midpoint is $\[n/2\]$. The next midpoint could be $\[n/2\]+\[n/4\]$. If the searched number is placed in the second half of the array, the midpoint at each step is no less than $\[n/2\]$. Each calculation of a new midpoint involves at least a number with $O(\log(n))$ bits, hence each midpoint calculation requires $O(\log(n))$. I obtain a more precise complexity of $O(\log(n)^2)$. Where is the error?

The same problem could appear on countless algorithms that use arrays or matrices. Take the most well-known dynamic programming algorithm for the knapsack problem. Everybody agrees it takes $O(nW)$ time (e.g., the wikipedia article on the knapsack problem), where $n$ is the number of items and $W$ is the capacity. But at each step, it needs to compute a difference of weights/capacities, which should account for an additional factor of $O(\log(W))$. Where is the error?

Where/how does this $O(\log(n))$ complexity factor disappear? If we had needed it, it would have appeared in many algorithms.

ps. A very similar problem arises in the questions asked here and here, thanks *Ariel*, *Raphael* and *ryan* for pointing this out.

# Answer
> 9 votes
You're not wrong, you're just using a different cost model.

Typically there are two:

> * ***Uniform* cost model** \- assigns a constant cost to every machine operation regardless of size of numbers.
> * ***Logarithmic* cost model** \- assigns a cost proportional to the number of bits involved for each machine operation.

Under *uniform* cost, a binary search takes constant operations to find the next index to search at, we get a recurrence relations like so: $$\begin{align} T(1) & = O(1)\\\\[0.5em\] T(n) & = T\left( \left\lfloor \frac{n}{2} \right\rfloor \right) + O(1)\\\\[0.5em\] & = \Theta(\log n) \end{align}$$

Under *logarithmic* cost, we can assume it takes $f(n)$ operations to find the next midpoint and we get a recurrence like so: $$\begin{align} T(1) & = O(1)\\\\[0.5em\] T(n) & = T\left( \left\lfloor \frac{n}{2} \right\rfloor \right) + f(n)\\\\[0.5em\] \end{align}$$ For binary search, typically $f(n)$ will be no more than computing $\lfloor \frac{l + r}{2} \rfloor$ which would take $\log\_2 n$ operations for the addition, and to divide by $2$ we could do a bit shift taking $\log\_2 n$ operations (see here). Which brings us to: $$\begin{align} T(n) & = T\left( \left\lfloor \frac{n}{2} \right\rfloor \right) + \Theta(\log n)\\\\[0.5em\] & = \Theta(\log^2 n) \end{align}$$ These logarithmic costs are just for addition and shifting though. If you were to do other $n$-bit operations then $f(n)$ could change. For example, $n$-bit multiplication and exponentiation could be larger than $\Omega(n)$ and you would have to adjust you complexity accordingly under *logarithmic* cost.

# Answer
> 1 votes
Usually people neglect time it takes to perform simple math operations on numbers and assume them to be $O(1)$. In practice, computers work with words, so we assuming bounded number. And it uses summator to add , which is extremely fast, comparing to other $O(log(n))$ operations.

Indeed, if you go really deep, and you have unbounded numbers $n,m$, Turing machine needs $O(log(n)+log(n))$ to add they assuming they are not in unary. With your array problem, I'd suggest looking carefully what is your input size and write complexity very carefully even for math operations, I expect them to be neglecting small. Like size of your array versus bound on numbers in the array and so on.

---
Tags: complexity-theory, polynomial-time
---


# Question
Title: What is the complexity of determining whether or not conjunction of positive CNF and negative CNF is satisfiable?
Definitions:

positive CNF is a conjunctive normal form formula, where all literals are positive, i.e. the unary connective ¬ does not exist in the formula.

negative CNF is a conjunctive normal form formula, where all literals are negative, i.e. the unary connective ¬ appears next to each literal.

My question is:

Given a CNF, which is a conjunction of positive CNF and negative CNF, what is the complexity of the problem to determine that this special case of CNF is satisfiable?

Does exist polynomial time and space algorithm to solve this problem?

EDIT: Another name for "positive CNF" is "fact CNF", where all clauses are fact and another name for "negative CNF" is "goal CNF", where all clauses are goal.

> ... clause with no negative literals is sometimes called a fact

> ... clause without a positive literal is sometimes called a goal clause

Quoted from: this wikipedia documentation

# Answer
> Given a CNF, which is a conjunction of positive CNF and negative CNF, what is the complexity of the problem to determine that this special case of CNF is satisfiable?

The problem is provably NP-complete by reduction from CNF satisfiability.

Each negative literal $\lnot{x}$ in a CNF SAT instance can be converted to a positive literal by replacing all occurrences of it with a new variable $z$ plus the following two CNF clauses: $x \lor z$ and $\lnot{x} \lor \lnot{z}$. The clauses force $z$ to act as the same constraint as $\lnot{x}$. Once all the original negated literals have been replaced, you are left with clauses that contain either all positive or all negative literals. Since any CNF SAT instance can be reduced to this form and since CNF SAT is NP-complete and since your problem is trivially in NP, your problem must be NP-complete.
> 4 votes

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


# Question
Title: Consensus number of memory-to-memory swap
I think that consensus number of mem-to-mem-swap(a,b) operation which atomically swaps the values between shared locations a and b (shared R/W memory) is **infinite** , but I'm having trouble proving it.
I thought about implementing **CAS** with mem-to-mem-swap but comparing atomically is problematic, I think there is straightforward consensus protocol but I can't think about one.

# Answer
See Theorem 10 (Figure 13) of the paper "Wait-Free Synchronization " by Herlihy, 1991.

> Theorem 10: An array of registers with memory-to-meory swap has infinite consensus number.
>
> Proof: The protocol is shown in Figure 13. The processes share an array of registers $a\[1 \ldots n\]$ whose elements are initialized to $0$ and a single register $r$, initialized to $1$. The first process to swap $1$ into $a$ wins.

Footnote 4 of this paper remarks that:

> The memory-to-memory swap should not be confused with the read-modify-write swap; the former exchanges the values of two public registers, while the latter exchanges the value of a public register with a processor’s private register.
> 1 votes

---
Tags: concurrency, consensus
---


# Question
Title: "Smallest set" term in the trees set definition
I often meet such kind of the definition of the set of *trees*, as:

*The set of unranked $\Sigma$-trees, denoted by $T$, is the smallest set of strings over $\Sigma$ and the parenthesis symbols ‘)’ and ‘(’ such that for each $a\in\Sigma$ and $w\in T^\*$, $a(w)$ is in $T$.* (http://dl.acm.org/citation.cfm?id=2101368)

One question that I can not generally understand is: how does this definition prevent from the string, say "$a)($", appear in the set $T$?

Would somebody be so kind explain me this point?

And please, if you are going to downvote this question, be so kind explain **why** are you doing that.

# Answer
I think that is trivial according to the rule of how the strings are formed: $a(w)$. But if you need a formal proof then you could prove it as following using induction on the length of strings in $T$.

Assume $t \in T$ and lets call such strings "well-structured", those which do not look like "$a)($".

Base case: $t = a()$ where $a \in \Sigma$. Clearly it is well-structured.

Induction: assume that all strings in $T$ of length $n$ is well structured. Then we form a new string by taking a string $w$, a symbol $a$ from $\Sigma$ and concatenate them using parenthesis as $a(w)$ which is well-structured since $w$ is well-structured too.
> 2 votes

# Answer
> The set of unranked $Σ$-trees, denoted by $T$, is the smallest set of strings over $Σ$ and the parenthesis symbols ‘)’ and ‘(’ such that for each $a∈Σ$ and $w∈T^∗$, $a(w)$ is in $T$.

What we have here is an *inductive definition*. The base case is implicit because $\epsilon \in T^\*$ even if $T = \emptyset$; making is explicit, the definition is (reading $a$ as free variable):

$\qquad\begin{align\*} &\ \phantom{\implies}\ a() \in T \\ w \in T^+ &\implies a(w) \in T \end{align\*}$

The term "smallest set" is established, but somewhat silly, since all these sets are infinite; we mean the *minimal* set. Formally speaking, it's the *smallest fixed point* of this inductive definition; see here and here for some more on that.

As for you question, imagine this definition unfolding in an infinite process:

* $a \in T \implies a(a) \in T$.
* $a(a) \in T \implies a(a(a)) \in T$.
* ... and so on...

All you can ever do is wrap things in parentheses; thus you can never creates mismatching pairs like you propose.

A formal proof would be an induction along the inductive definition, of course!

1. Base case: all alphabet symbols have matching parentheses.
2. Inductive step: taking elements of $T$ with matching parentheses, those that are "one step larger" have matching parentheses as well.
> 4 votes

# Answer
You have to prove that $a)($ doesn't belong to $T$. You can start with constructing $T$, as follows. Let $T\_0 = \emptyset$, and for $n \in \mathbb{N}$, define $$ T\_{n+1} = \bigcup\_{a \in \Sigma} \bigcup\_{m \in \mathbb{N}} \\{ a(t\_1 \ldots t\_m) : t\_1,\ldots,t\_m \in T\_n \\}. $$ I claim that $$ T = \bigcup\_{n \in \mathbb{N}} T\_n. $$ Indeed, you can prove by induction on $n$ that $T\_n \subseteq T$. Conversely, suppose that $t\_1,\ldots,t\_m \in \bigcup\_{n \in \mathbb{N}} T\_n$. Then there exists $N$ such that $t\_1,\ldots,t\_m \in T\_N$, and so $a(t\_1\ldots t\_m) \in T\_{N+1} \in \bigcup\_{n \in \mathbb{N}} T\_n$ for all $a \in \Sigma$. This shows that $T \subseteq \bigcup\_{n \in \mathbb{N}} T\_n$, since the latter satisfies the conditions in the definition of $T$.

Now you can prove that $a)( \notin T$ by proving inductively that $a)( \notin T\_n$ for any $n \in \mathbb{N}$. The proof is quite simple: $a)( \notin T\_0$ since $T\_0$ is empty, and $a)( \notin T\_{n+1}$ for any $n \in \mathbb{N}$ since all strings in $T\_{n+1}$ start with $b($ for some $b \in \Sigma$.
> 2 votes

# Answer
This use of the phrase "smallest set", or "smallest set with respect to inclusion" is generally taken to be synonymous with "the intersection of all sets satisfying this criterion" (as long as intersection preserves satisfaction of the criterion). So "smallest" here means "is a subset of every set satisfying this criterion". Consequently, no proper subset of this set can satisfy the given criterion. I.e., this set is minimal with respect to the partial ordering $\subseteq$ of sets.

Example: Let $G$ be a group and let $S$ be a subset of $G$. The *normal closure* of $S$ is the smallest normal subgroup of $G$ which contains $S$. Equivalently, (since we have an elementary lemma that the intersection of normal subgroups is a normal subgroup), the normal closure is the intersection of all the normal subgroups of $G$ which contain $S$. This immediately shows that any proper subgroup, normal in $G$, of the normal closure of $S$ cannot contain all of $S$, so the normal closure is smallest with respect to (set) inclusion.
> 2 votes

# Answer
There *are* sets $T$ that satisfy the condition given (for each $a \in \Sigma$ and $w \in T^\*$, $a(w) \in T$) which *do* contain badly-structured trees like $a)($; however, there is also a set that doesn't contain any of these badly-structured trees. All of the sets that contain badly-structured trees also contain all the well-structured trees, so the set that contains *only* the well-structured trees is the smallest such set.
> 1 votes

---
Tags: trees, notation, inductive-datatypes
---


# Question
Title: Theory of Complexity - Relation between a class and its complement
i'm in trouble trying to prove the following proposition:

**Proposition** *If $\ C$ is a class closed under reductions and a $\ C$-Complete problem belongs to $\ coC$, then $C=coC$*.

Note: $C$ can be any class.

To prove that proposition i thought to split the proof in two ways:

**(\*)**: $C \subseteq coC$

I suppose it exists such an $L \in coC$ that is $C$-Complete. For all $L' \in C$ there is a reduction $R : L \rightarrow L'$. Thus $L \in coC$ and $coC$ is closed under reductions (because $C$ is), $L' \in coC$ also, so $C \subseteq coC$.

**(\*)**: $coC \subseteq C$

That's the part i'm not able to prove.

Thank you so much.

# Answer
The first part is easy since there is a $C$-complete problem that belongs to $coC$ and since all problems in $C$ are reduced to that complete problem, $C \subseteq coC$

As for the second part let $L\_C$ be a $C$-complete problem that belongs to $coC$. Then by definition of $coC$, $\overline{L}\_C \in C$. So, **$\overline{L}\_C$ are in $C$** (decidable in $C$). Also since $L\_C$ is $C$-complete, for any language $L \in C$ there is a reduction $f$ such as $x \in L \Leftrightarrow f(x) \in L\_C$.

Now, if a problem $L \in coC$ then $\overline{L} \in C$ and $x \in \overline{L} \Leftrightarrow f(x) \in L\_C$ meaning that $x \in L \Leftrightarrow f(x) \in \overline{L}\_C$. So $L$ is reduced to $\overline{L}\_C$ which is in $C$. Thus $coC \subseteq C$.
> 1 votes

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


# Question
Title: Trying to Classify MNIST where pixels are shuffled with a seed.Why is it not working?
I transformed the MNIST dataset as follows:(**X (70000 x 784)** is the **training** matrix)

```
np.random.seed(42)
def transform_X():
    for i in range(len(X[:,1])):
        np.random.shuffle(X[i,:])

```

I had thought that **shuffling the pixels in an image** would make the digits unrecognizable by humans,but the machine learning algorithms would still be able to learn from the images with shuffled pixels correctly.

I cannot understand the **mathematical reason** behind not learning. Do you think this should work and I should recheck my code for any mistakes? I trained on **SVC** and **SGDClassifier** of sklearn.Results from both are just randomness.

# Answer
You are essentially setting each image to a (more or less) random image. And now you wonder why it is not learning? There is (almost) no data to learn from left.

Let me give you a similar example. Here is some (unshuffled) training data:

```
0 0 0 -> 0
0 0 1 -> 0
0 1 0 -> 0
0 1 1 -> 0
1 0 0 -> 1
1 0 1 -> 1
1 1 0 -> 1
1 1 1 -> 1

```

The pattern is pretty obvious: The first column is equal to the label. The next two columns are irrelevant. Now let me give you some shuffeled training data:

```
0 0 0 -> 0
0 1 0 -> 0
1 0 0 -> 0
0 1 1 -> 0
1 0 0 -> 1
1 1 0 -> 1
1 0 1 -> 1
1 1 1 -> 1

```

Good luck with finding the correct pattern there. And this is only 3 dimensional; things get much worse with more dimensions.

One thing that could work if you stored a random permutation and applied the same permutation to each image.
> 1 votes

# Answer
A good indication, although quite rough, if an algorithm is capable of solving a task (especially pattern recognition tasks) is to check if humans can. We evolved to be quite good at it.

Obviously, that might not always be true. But in your case, by shuffling you loose all the structure of the data. The only possible feature your ML algorithm can use is the number of pixels set vs unset (or the pixel values, for grayscale images), thus basically losing all the structure. The problem is that this is a bad feature since there is little correlation between the number of pixels set and the digit. There is no pattern left, and any attempt to learn a pattern is doomed to fail. Thus, your algorithm may:

* try to learn a pattern where there is none
* not have enough features to do the classification

or a combination of the 2.
> 1 votes

---
Tags: machine-learning, neural-networks, statistics
---


# Question
Title: Polynomial time reductions between two problems
I have two sets $A$ and $B$, I want to reduce $A$ to $B$ and $B$ to $A$.

Formulas consist of a finite set of variables $\mathcal{V}$. An assignment $\sigma$ assigns truth values to each variable in $F$. When writing $F(\sigma)$ for an assignment $\sigma : \mathcal{V} \rightarrow \\{0, 1\\}$ I refer to the application of the assignment to formula $F$ (truth values are assigned to variables in $F$ according to $\sigma$).

Set A contains all unsatisfiable propositional formulas $F$:

$A := \\{F \in \mathcal{F}\ | \ \forall \sigma: \mathcal{V} \rightarrow \\{0,1\\}. \sigma(F) = 0 \\}$

Set B contains all propositional formulas which evaluate to the same truth value for an assignment $\sigma$ and its opposite $\overline \sigma$ (this condition must hold for all assignments):

$B := \\{F \in \mathcal{F}\ | \ \forall \sigma: \mathcal{V} \rightarrow \\{0,1\\}. \sigma(F) = \overline\sigma(F) \\}$

Let $A \subseteq \Sigma ^\*$, $B \subseteq \Gamma ^\*$ and $f: \Sigma ^\* \rightarrow \Gamma ^\*$. By reduction I mean finding a total and computable (in polynomial time) function $f$ such that $\forall w \in \Sigma ^\*.w \in A \iff f(w) \in B$ which can be abbreviated by $A \leq B$.

How to do the reductions $A \leq B$ and $B \leq A$? After the reductions are done, does that imply that problems $A$ and $B$ are equally difficult?

# Answer
You can reduce from $B$ to $A$ by setting $f(F) = (F \neq F^{'})$ where $F^{'}$ is $F$ with every variable replaced with its negation. Equally, you can reduce from $A$ to $B$ by setting $f(F) = F$, because every variable assignment, and its negation, will be false.
> 1 votes

---
Tags: np-complete, reductions
---


title: Binarization of Constraints

text:
# Question
Title: Binarization of Constraints
I am trying to solve a Constraint Satisfaction Problem that involves lots of n-ary constraints. But the solver I have implemented only works with algorithms for binary constraints.

I've been reading into the topic of the biniraztion of constraints (http://ktiml.mff.cuni.cz/~bartak/constraints/binary.html) but I am still not entirely sure how that would work. I thought if someone could help me convert one of the real-world constraints I am dealing with, this could help my understanding.

More specifically:

I have a set of variables: {C1, C2, C3, P}.

Each variable has a domain {0, 1}.

And a constraint: (C1 → (¬C2 ∧ ¬C3 ∧ P)) ∨ (C2 → (¬C1 ∧ ¬C3 ∧ P)) ∨ (C3 → (¬C1 ∧ ¬C2 ∧ P))

How can I convert this constraint into multiple binary constraints?

# Answer
Introduce a new variable $Q$, whose domain is $\\{0000,0001,0010,\dots,1111\\}$. It represents the value of $C1,C2,C3,P$. For instance, if $Q=0001$, that means that $C1=0$, $C2=0$, $C3=1$, $P=0$. Then, you add a constraint that the first bit of $Q$ is equal to $C1$ (that's a binary constraint), a constraint that the second bit of $Q$ is equal to $C2$ (another binary constraint), and so on.
> 4 votes

---
Tags: algorithms, satisfiability, constraint-satisfaction, constraint-programming, backtracking
---


# Question
Title: What is the complexity of the problem of computing the cardinality of the union of many (finite) and small sets?
What is the complexity of the problem of computing the cardinality of the union of many (finite) and small sets?

What is both the time and space complexity of the naive algorithm that does this computation?

An inefficient recursive algorithm to do this task is:

Where

This results in Θ(2n) exponential blow up time complexity and this is incredibly bad!

Another iterative algorithm to compute the cardinality is:

This formula was taken from this proof wiki webpage, although it doesn't show any proof, but only the formula itself.

But I don't know how to analysis it's both time and space complexity.

**EDIT:** It appears that the iterative algorithm, unlike the recursive algorithm, iterates over all the different subsets of {S1, ... , Sn} in order to compute the cardinality of the union of all sets from S1 to Sn, but the number of subsets of {S1, ... , Sn} is 2n, so the time complexity of the iterative algorithm is same as the time complexity of the recursive algorithm, i.e. the time complexity of the iterative algorithm is also Θ(2n) exponential time blow up as the time complexity of the recursive algorithm.

Does exist polynomial both time and space algorithm to compute this?

I tried to google an answer to this question for hours, but I didn't find it anywhere.

# Answer
Yes, there is a polynomial time algorithm. You simply iterate over all of the elements of each set and add each one to some data structure (e.g., a hashtable, a balanced binary tree) if it's not already present. Then, you count the number of items in that data structure.

If there are $n$ input sets $S\_1,\dots,S\_n$, each of size $k$, then the running time of this is $O(nk \log(nk))$ if you use a self-balancing binary tree data structure. The expected running time is $O(nk)$ if you use a hash table. The size of the input is $\Theta(nk)$, so this yields an algorithm whose running time is polynomial in the size of the input.
> 2 votes

---
Tags: algorithms, complexity-theory, algorithm-analysis, time-complexity, space-complexity
---


# Question
Title: What is Temperature in LSTM (and neural networks generally)?
One of the hyperparameters for LSTM networks is temperature. What is it?

# Answer
> 42 votes
**Temperature** is a hyperparameter of LSTMs (and neural networks generally) used to control the randomness of predictions by scaling the logits before applying softmax. For example, in TensorFlow’s Magenta implementation of LSTMs, temperature represents how much to divide the logits by before computing the softmax.

When the temperature is 1, we compute the softmax directly on the logits (the unscaled output of earlier layers), and using a temperature of 0.6 the model computes the softmax on $\frac{logits}{0.6}$, resulting in a larger value. Performing softmax on larger values makes the LSTM **more confident** (less input is needed to activate the output layer) but also **more conservative** in its samples (it is less likely to sample from unlikely candidates). Using a higher temperature produces a softer probability distribution over the classes, and makes the RNN more “easily excited” by samples, resulting in **more diversity** and also **more mistakes**.

Neural networks produce class probabilities with logit vector $\mathbf{z}$ where $\mathbf{z} =$$(z\_1,\ldots,z\_n)$ by performing the softmax function to produce probability vector $\mathbf{q} = (q\_1,\ldots,q\_n)$ by comparing $z\_i$ with with the other logits.

$q\_i = \frac{\exp{(z\_i/T)}}{\sum\_j\exp{(z\_j/T)}}\tag{1}$

where $T$ is the temperature parameter, normally set to 1.

The softmax function normalizes the candidates at each iteration of the network based on their exponential values by ensuring the network outputs are all between zero and one at every timestep.

Temperature therefore increases the sensitivity to low probability candidates. In LSTMs, the candidate, or sample, can be a letter, a word, or musical note, for example:

> For high temperatures (${\displaystyle \tau \to \infty }$), all \[samples\] have nearly the same probability and the lower the temperature, the more expected rewards affect the probability. For a low temperature (${\displaystyle \tau \to 0^{+}}$), the probability of the \[sample\] with the highest expected reward tends to 1.

\- from Wikipedia article on softmax function

# Reference

Hinton, Geoffrey, Oriol Vinyals, and Jeff Dean. "Distilling the knowledge in a neural network." arXiv preprint arXiv:1503.02531 (2015). arXiv

---
Tags: machine-learning, neural-networks
---


# Question
Title: How is the time complexity of an algorithm with successive-nested loops measured?
Does the time complexity of the following pseudo-algorithm simplify as $O(n^2 log(n)) = O(n^2)$?

SOME ALGORITHM

```
GET n
FOR (i=1; i<=n; i++)
    {
        calculationOfN[i] // some polylogarithmic time calculation

        FOR (j=1; j<=n; j++)
            {
                // some linear calculation
            }
        FOR (k=0; k<=n; k++)
            {
                // some linear calculation
            }
    // some statement
    }
// some statement

```

# Answer
> 3 votes
Assuming your linear calculations are actually constant-time calculations, then yes, the final time complexity of the algorithm will be $O(n^2)$ (but not for the reason you seem to be indicating).

Your polylogarithmic time calculation (running in time $O(\log^{k}n)$) is run $n$ times (one for each $i$); each of your secondary $O(1)$ time computations is run $O(n^2)$ times (one for each $(i,j)$ pair and $(i,k)$ pair respectively). Altogether, this leads to a time complexity of $O(n\log^{k}n + n^2)$ (notably, *not* $O(n^2\log^{k}n)$). Since $n^2$ dominates $O(n\log^{k}n)$, this is $O(n^2)$.

---
Tags: algorithm-analysis, runtime-analysis
---


# Question
Title: Determine if a string is a permutation of another string efficiently
Given two strings of the same length, determine if they are permutations of each other.

I can come up with two solutions, one in O(n log n) time with O(1) extra space, and one in O(n) time with O(n) extra space, but I'm wondering if there are more efficient algorithms.

If we sort the strings in-place and compare them, we get O(n log n) time with O(1) extra space.

If we use a hashtable from character to count, we can keep track of how many of each character we have in the first string, and subtract accordingly when reading characters from the second string. That's O(n) time and O(n) extra space.

Can we do better?

# Answer
You can establish a trivial lower bound of $\Omega(n)$, because you must *at least* observe all characters of each string (in worst case) to determine if they are permutations of each other. So $O(n)$ time complexity is the best you could do.

Perhaps you could improve the space complexity though. Raphael describes a unique approach here to achieve constant space and linear time using properties of prime numbers.
> 2 votes

---
Tags: algorithms, strings, permutations
---


# Question
Title: Is computing the cardinality of sum of regular expressions without kleene star closure EXPTIME problem?
Is computing the cardinality of sum of regular expressions without kleene star closure is EXPTIME problem?

Note that sum of regular expressions is union of regular expressions. The alphabet of each regular expression is Σ={0,1}, and each regular expression in the sum is concatenation of 0, 1 and (0+1).

There is no kleene star closure, so the regular language of the sum of regular expressions is finite, and so the cardinality of this regular language is finite natural number, as defined in discrete mathematics, which is the number of words in this regular language.

There are two known naive algorithms to compute this, but their running time are both Θ(2n) exponential blow up.

One naive algorithm is recursion that computes:

Where:

Computing the intersection regular language of two regular languages should be easy, because the fact that each regular expression in the sum is just concatenation of 0, 1 and (0+1), so in parallel 0∩0=0, 1∩1=1, (0+1)∩(0+1)=(0+1), 0∩(0+1)=0, 1∩(0+1)=1 and if 0 is found in regexp A and 1 in regexp B at the same offset or 1 is found in regexp A and 0 in regexp B at the same offset then L(A)∩L(B)=∅, i.e. both the languages are disjoint.

But the naive recursive algorithm runs over complete binary tree, whose height is n and it has 2n nodes, thus the running time complexity of the naive recursive algorithm is Θ(2n).

Another naive algorithm is iteration that computes:

The general formula was taken from this proof wiki webpage that doesn't show any proof for this formula.

But it seems that the algorithm iterates over all the different subsets of {R1, ... , Rn} and from the power set lemma it's known that {R1, ... , Rn} has 2n different subsets.

Thus the running time complexity of the naive iterative algorithm is also Θ(2n) exponential blow up as well as the naive recursive algorithm.

All known algorithms for this problem, for me, are exponential run time and thus it seems that this problem is EXPTIME, according to the definition of EXPTIME in computational complexity theory.

**Maybe** all **best** algorithms for this problem are Ω(2n) exponential run time, and there is no polynomial run time algorithm to compute this, but this requires a proof.

Just finding 2 exponential run time algorithms is not a proof.

But I don't know if this question is open or not in computer science.

I tried to google the answer for hours, but I didn't find it yet.

Is this open question in computer science?

If not, then what is the proof that this problem is in **P** or not in **P**, i.e. does exist polynomial algorithm to solve this problem?

EDIT:

Algorithm's input is sum of regular expressions, where each regular expression is concatenation of 0, 1 and (0+1).

The number of concatenations per regular expression in the sum is fixed.

All words in the regular language of the sum of regular expressions are in the same length.

The only operators in the regular expression are sum and concatenation.

**EDIT:**

"The number of concatenations per regular expresion in the sum is fixed."

infers the length of each word in the regular language.

If there is 1 concatenation, then the length of each word is 2, if there are 2 concatenations then the length of each word 3, if there are k concatenations then the length of each word is k+1.

For example in the regular expression: 0(0+1)1, there are 2 concatenations:

first concatenation is between 0 and (0+1) and second concatenation is between (0+1) and 1, so in total there are 2 concatenations and thus the length of each word in the regular language is 3, because all the other regular expressions in the sum have the same number of concatenations, in this example they all have 2 concatenations.

There are 2 words in the example regular expression above: 001 and 011, and their length is 3, and you can see that number of concatenations between each two nearby characters is 2.

Either number of concatenations per regular expression or the length of each word in the regular language is given in the algorithm's input. This is not necessary that both are given, because if one of them is given, then this is possible to infer the other due to their relationship.

# Answer
Assume that each of your regular expressions has only parentheses, + as union, and a concatenation operator. For example $$01(01 + 1)$$ $$(01 + 1)011+01$$ are possible inputs. Since each regular expression represents a finite set of strings over $0$ and $1$, first you could rewrite them as a finite sets of strings. For example $01(01 + 1)$ is equivalent to $0101 + 011$, simply multiply by getting rid of parentheses. If the number of concatenations is fixed, say $K$, then the upper bound for transformation (or expansion) is $2^K$ corresponding to the following input $$(0+1)(0+1)\dots (0+1) \ \ \ \ \ (K \text{ times})$$ This string generates $2^K$ different words. Thus if the number of regular expressions $N$ which constitutes the input size and $K$ is fixed then $2^K$ may be considered as constant w.r.t $N$. So the transformation of all regular expressions into the set of words takes $N2^K$ time which is $O(N)$.

Now, in fact each word is the binary representation of an integer, so you could treat them as **sets of integers**. And since each word is bound as well, say at most of the length $M$ (**also fixed**!), then you have at most $2^M$ integers which can be stored in the array of size $2^M$ (if not too large) or as bitmap and accessed in $O(1)$ time.

Thus to compute the cardinality of union of these sets you simply count the number of different elements in all sets/arrays - D.W. has already answered here. That shouldn't take more that $O(N)$ either.
> 2 votes

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


# Question
Title: Is this a Fruitful Primality Testing scheme?
Today I had an insight into an alternative deterministic algorithm for testing the primality of a number. I want to know if this algorithm is useful, and worth pursuing. I'll describe the idea behind the algorithm below:

Let the fastest gcd algorithm we know be $g^\*(a, b)$. $g^\*$ takes in two numbers and finds their greatest common divisor. To find out if any number $n$ is prime it is sufficient to test if any of the prime numbers from $2$ to $\sqrt{n}$ inclusive is a factor of $n$.

Consider a set of numbers $S$. Let $V\_c$ be any subset of $S$ such that $g^\*(V\_c) = 1$, that is, all $x\_i$ in $S$ are mutually prime. Let the set of prime numbers be $P$. Let $h\_i$ be the set of all factors of $x\_i$.
$$P = \bigcup\_{i = 1}^{{\\#}S} h\_i.$$ So $S$ is a partitioning of $P$ such that all the elements of $S$ are formed from the product of unique elements in $P$, and no element in $P$ is used to form more than one element in $S$. There are several possible configurations of $S$. Let's denote them $S^j$.
Let $P\_k$ be the set of all prime numbers from $2$ to $k$. Let $S\_k^j$ be an $S$ partitioning of $P$.

Now, my primality test is this:

> 1. Given any number $n$, pick $k: k \ge \sqrt n$ (the closer $k$ is to $\sqrt n$, the better).
> 2. Generate an optimum $S\_k^j$.
> 3. for $x\_i$ in $S\_k^j$
> 4. if $g^\*(n, x\_i) != 1$
> return **false**
> end for
> 5. return check

For implementation purposes, I'm thinking of creating a set of $S^j$ with consecutive $x\_i$ (consecutive in the sense that the largest prime number used to make $x\_i$ is consecutive with the smallest prime number used to make $x\_{i+1}$, such that we can easily cut off a portion of $S^j$ to get our $S\_k^j$. Depending on circumstances though, we may generate the optimum $S\_k^j$ on the spot, though this should only be pursued if the cost of generating it is negligible or guarantees a significant speed up over the alternative of the consecutive table. I think creating a pre-generated $S\_k^j$ is useful for this purpose, though I'm not sure if it would slow down the overall algorithm. Alternative tables apart from the consecutive table may also be considered.

# An English Explanation

My idea in English is basically this:

> To test if a number $n$ is prime, we only need to check if any of the prime numbers from $2$ to $\sqrt{n}$ is a factor of $n$. Using this foundation, I tried to devise a method that is faster at testing primality, than computing $n \mod i$ for all primes between $2$ and $\sqrt{n}$.
> If two numbers are mutually prime, then their gcd is $1$. A prime number is mutually prime with every other prime number that is not itself. Imagine I had a number $y\_n$. $y\_n$ is a product of all the prime numbers from $2$ to $\sqrt{n}$. I can test if $y\_n$ is prime, by running $g^\*(n, y\_n)$, where $g^\*()$ is our fastest gcd algorithm.
> However, what if instead of just $1$ number, I had a set $S$ of numbers which satisfied the following properties:
> 1. All the elements of the set are mutually prime with every other element.
> 1. Each element of the set is a product of some primes between $2 and \sqrt{n}$ (both inclusive). 2. The product of the elements of the set is equal to the product of all the prime numbers from $2$ to $\sqrt{n}$.
> It becomes apparent, that I can test if $n$ is prime, by computing $g^\*(n, x\_i)$ until I get a value that is not equal to $1$ (if all values are equal to $1$, then the number is prime). where $x\_i$ is some element in $S$.
> It is possible, that my $S$ contains only $y\_n$. The idea is to choose $S$ such that we minimise the runtime of the algorithm, and the runtime of generating $S$. (I suggest a table storing $S$, such that a desired subset of $S$ can easily be cut out from it to use to test any prime number. If we keep a lookup table for $S$ (as opposed to generating it), then we can minimise the cost the algorithm incurs when generating $S$. There are other ideas that can be pursued to minimise the cost of generating $S$).

# Answer
No, this won't work -- it's too slow. Let $B$ be the product of all the prime numbers up to $\sqrt{n}$. Then $B$ is roughly $\sqrt{n}^{\sqrt{n}/\log n}$, i.e., exponential in $n$. Consequently, no matter how you form the set $S$, you're going to be working with a set of exponential size. As a result the algorithm will have exponential running time, which is no good.
> 3 votes

---
Tags: algorithms, algorithm-analysis, primes
---


title: Type Inference and Generalization

text:
# Question
Title: Type Inference and Generalization
I've been trying to understand type inference for Hindley-Milner-based languages, and I'm struggling to understand how generalization works. Let's say I have the following program in Haskell:

```
x :: Int
x = id 1

y :: Char
y = id 'a'

id :: a -> a
id x = x

```

If the type-checker traverses the program from top to bottom, then from `x` we can infer that the type of `id` must generalize `Int -> Int`, and from `y` we can infer that `id` must generalize `Char -> Char`, but I'm unclear how we can use these constraints without inferring a too-specific type for `id`.

If we check `id` first, then we can just instantiate its type in `x` and `y`, and use unification. However, if we have recursive or mutually recursive bindings, ensuring that all mentioned top-level bindings are typechecked before the binding itself would lead the type-checker into an infinite loop.

How are these issues resolved?

# Answer
> 4 votes
There are a few things to realize:

First, top level declarations are implicitly let-bound, so your code is equivalent to the following:

```
let
  x :: Int
  x = id 1

  y :: Char
  y = id 'a'

  id :: a -> a
  id x = x

```

Secondly, as was mentioned in the comments, Haskell will sort the let statements topologically, nesting them when it can, and any recursive uses are monotyped unless annotated.

Finally, the types of let-variables are generalized at their definition, but specialized at their use. So now we have (something close to):

```
let
  id :: a -> a
  id x = x
in let
  x :: Int
  x = id 1

  y :: Char
  y = id 'a'

```

Finally, we need to see that while variable types are generalized at their definition, they are specialized at their use.

So, this is roughly what inference does:

* The checker infers the type $id : \alpha \to \alpha$, then generalizes this to $\forall a \ldotp a \to a$.
* The checker puts $id : \forall a \ldotp a \to a$ into the environment for checking $x$ and $y$
* While checking the definitions of $x$, at the use of $id$, the type $\forall a \ldotp a \to a$ is instantiated to $\beta \to \beta$, where $\beta$ is a fresh unification variable.
* While checking the definitions of $y$, at the use of $id$, the type $\forall a \ldotp a \to a$ is instantiated to $\gamma \to \gamma$, where $\gamma$ is a *different* fresh unification variable.

Because the polymorphic type scheme is instantiated with unique variables at each use, the inference is able proceed without error.

---
Tags: programming-languages, functional-programming, type-inference
---


# Question
Title: Finding the half with greatest elements in a set
Given an array with $2n$ elements, we want to select the greatest $n$ elements, i.e. obtain new array with these elements, no matter of the ordering (it's not necessary to be sorted). Can we do this in $O(n)$ time?

# Answer
> 2 votes
Proceed in two phases.

1. Determine the *median* of the input.
2. *Partition* the input with the median as the pivot (cf. Quicksort).

Both steps take worst-case linear time. Note, though, that in practice you'd not use a linear-time selection algorithm but rather Quickselect, which is faster in expectation.

# Answer
> 0 votes
Let $L$ be a list of $n$ elements and $k \in \mathbb{N}, k \< n$.

**First Problem:** Given $e \in L$, how to find the index of $e$ as if $L$ were sorted?

**Solution:** Just walk $L$ and count how many elements are smaller than $e$

Using this idea define a partition function, that takes the list $L$ and an element $e$ and returns all elements smaller than $e$ and greater than $e$.

```
def partition(L, e):
    # Partitions L into 3 lists
    # [_ < e], [e], [e < _]
    smaller = []
    bigger = []
    for elm in L:
        if elm < e:
            smaller.append(elm)
        if elm > e:
            bigger.append(elm)
    return smaller, [e], bigger

```

The selection algorithm described here outputs the $k$ smallest elements of $L$, you can easily modify the Python code to do what want. It works like this:

Pick $e \in L$ at random.

```
+--------------------+---+----------------------------+
|                    | e |                            |
+--------------------+---+----------------------------+

```

Now make a partition in $L$.

```
+--------------------+---+----------------------------+
|      LEFT          | e |        RIGHT               |
+--------------------+---+----------------------------+

```

Now check one of the following cases:

If $length(LEFT) \< k$, then you already have some $length(LEFT) + 1$ smaller elements, that is $LEFT + \\{e\\}$, and need to find the other $k - length(LEFT) - 1$ in a smaller subset of $L$.

```
+--------------------+---+----------------------------+
|       LEFT         | e |        RIGHT               |
+--------------------+---+----------------------------+

                         +----------------------------+
                         |         New L              |
                         +----------------------------+

```

If $length(LEFT) = k$. Then it's over, you're really lucky.

If $length(LEFT) \> k$. Then it's the same problem, in a smaller array.

```
+--------------------------------+---+----------------+
|       LEFT                     | e |    RIGHT       |
+--------------------------------+---+----------------+

+--------------------------------+
|         New L                  |
+--------------------------------+

```

The python code:

```
def selectK(L, k):
    from random import choice
    e = choice(L)
    left, mid, right = partition(L, e)

    if len(left) < k:
        return left + [e] + selectK(right, k - (len(left) + 1))
    if len(left) == k:
        return left
    if len(left) + 1 == k:
        return left + [e]
    if len(left) > k:
        return selectK(left, k)

```

Test case:

```
L = [56, 24, 68, 36, 16, 4, 44, 40, 32, 8, 28, 20, 72, 64, 60, 52, 76, 0, 48, 12]
Output for k=6: [0, 4, 16, 8, 12, 20]

```

---
Tags: algorithms, arrays, selection-problem
---


# Question
Title: Is it decidable if a TM takes at least 2016 steps on all inputs?
$$L\_1= \\{\langle M \rangle \mid \text{\\(M\\) takes at least 2016 steps on all inputs} \\}$$

Is this language decidable?

---

I will write my way of understanding it. Please answer it in the way I understand & tell if my understanding is wrong.

It means L1 is a language, which includes all such Turing machines, which takes at least 2016 steps on all inputs. So we need to say it is decidable or not...

We are talking about which machine? We are talking about that machine whose language is L1. Other TMs are input to the new turing machine as encoding of 0 &1. We need to say for all inputs (for all Turing machine encodings) the new turing machine halts or not. When it will halt? When the new turing machine can either say..."Yes, the turing machine I am considering took at least 2016 steps but still it is on progress"...it also can say "No, the turing machine you gave me went to final state before 2016 steps" If it will say either of this, then the new turing machine, language L1 is decidable.

When it will be undecidable? When the new turing machine is still on progress unable to say yes or no. So solution is run new Turing machine for 2016 steps only. If it is saying "yes, the other turing machine halted...or the other turing machine did not halt."... then for both answer our new turing machine will halt... It is simple to understand that the new turing machine will always halt... bcz it's task is just to check the other turing machine halted or not within 2016 steps.

# Answer
A Turing machine only sees (at most) the first 2015 symbols of the input in its first 2015 steps. Hence whether it stops within 2015 steps depends only on the first 2015 symbols of the input. This gives an algorithm for deciding $L\_1$: run the input machine $M$ on all inputs of length at most 2015, and check whether any of them stops within 2015 steps. If so, reject. Otherwise, accept.
> 10 votes

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


# Question
Title: Is it always possible to have one part of the reduction?
So I have been asked this question during my comprehensive and I have a few answers to it, I just wanted to check with the community whether I'm on track with them.

Is the following statement true?

$\forall A,B \subseteq \Sigma^{\*}, \exists\ f : \Sigma^{\*} \rightarrow \Sigma^{\*}, s.t. \forall x \in A \implies f(x) \in B $

The function $f$ had to be decidable in polynomial time, as in the notion of reductions. So, the question in english stands as, is it always possible to find a polytime computable function of the like written above, for any two languages, s.t. one direction of the notion of reduction holds.

So, at that moment I couldn't argue for polytime computability, but , the obvious idea of having a map from $\Sigma^{\*}$ to an element in B, was all I could come up with. Later, on subsequent thinking I realised that it basically becomes a membership checking question for arbitrary B. Another idea, also struck and that being when B $\ =\ \phi$, then $(A,\phi)$ serve as the counterexample sought, where A is any language.

So, in case we do not allow for B being the empty language, any instance of B which is undecidable or rather, takes more than polynomial time for membership checking \[Not sure about the second one as its unknown whether P!=NP\] holds, right?

Other questions associated to this, are:

(1) if A=3SAT and B $\in \mathbb{P}$ , then does the existence of such a $\ f$, prove P=NP or do you need the reverse direction of reduction to hold as well, to conclude that?

(2) What about when $\ f$ is allowed to be decidable, or semidecidable, what changes?

(3)And, what if the reverse direction of reduction was the condition to be satisfied by $\ f$, ie, $\forall x \in \Sigma^{\*},\ f(x) \in B \implies x \in A$ then what changes? \[ I worked this out, taking the contrapositive , ie, $\forall x \not\in A \implies f(x) \not\in B$ it basically boils down to membership checking for the complement language, ie, $\overline{B}$ \]

EDIT : Sorry (1) was trivial. As pointed out by the answer below, $\mathbb{P} \subseteq \mathbb{NP}\ $ means I can just use the same f trivially for the reverse direction.

# Answer
If you define "reduction" using a single implication as in $x\in A \implies f(x) \in B$, then $A$ indeed always "reduces" to any nonempty $B$. Take any $b\in B$, and define $f(x)=b$ the be a constant function. This is computable in O(1), hence in polytime.

It does not matter if $B$ is decidable, or in P, or anything else -- as long as it is not empty, that's enough.

1) No, it does not prove anything. If you have that $A$ reduces to a PTIME $B$ with your proposed reduction, you can't conclude $A$ is PTIME. $HALT$ would reduce to checking if a number is $12$ (which is PTIME), but $HALT$ is surely not PTIME.

2) $f$ above is constant, hence always decidable. (There is no such a thing as a semicomputable function)

3) Similarly, the converse implication is satisfied, for any $A$ and non-full $B$, if we take the constant function $f(x)=b \notin B$.

---

Below, I consider the more standard definition of reduction with the double implication.

The halting problem is not reducible (polytime or not) to its complement, nor its complement is reducible to the halting problem.

This is because $A\leq B$ holds iff $\bar A \leq \bar B$, hence in either case the complement of $HALT$ would reduce to $HALT$, but the first is not recursively enumerable, and the second is, so we get a contradiction.

For the others:

1) Yes. The reverse direction is trivial, since if $B\in P$ then $B\in NP$ hence it reduces to 3SAT.

2) The $HALT$ counterexample above holds for any computable $f$. There is no such a thing as a semicomputable function -- semidecidability only applies to problems.
> 1 votes

---
Tags: complexity-theory, reductions, decision-problem
---


title: What is the Name of This Problem?

text:
# Question
Title: What is the Name of This Problem?
> Given two integers $a$ and $b$, determine if $a$ and $b$ are equivalent modulo any $k \\, (k: 1 \lt k \lt |a - b|)$.

If $\exists$ an integer $ (k: 1 \lt k \lt |a - b|) \text{ and }a \equiv b \mod k$, then the algorithm would return **true**, otherwise it would return **false**.

I thought of this problem today.

Before attempting to solve it, I want to know if there is existing literature on the problem. However, I would need to know the problem to do research on it.

# Answer
> 0 votes
You just need to check if $|a-b|$ is divisible by a some integer $k$. You can reduce it to the integer factorization problem if you are not interested in the trivial divisors 1 and $|a-b|$.

---
Tags: reference-request, number-theory
---


# Question
Title: Polynomial time approximation of NPC problem
I have found a polynomial time solution of an NPC problem. My algorithm give exact result in most cases. For example if I run my algorithm for 20000 problem instances, then it fails 10 times to give correct result. But, I am unable to prove the approximation ratio mathematically. Is it feasible to show it with the experimental results? I am waiting to hear the possible solutions for it.

# Answer
> Is it feasible to show it with the experimental results?

No, you can not. There is no shortcut around formal proofs here.
> 2 votes

# Answer
First of all, any more information to give about the problem? Your algorithm? These sorts of things would make a question such as this far more approachable.

In what sense are you unable to prove it? I think a theoretical result is far stronger than any experimental results you may be able to gather, since it demonstrates that, without fail, your algorithm will return a solution with a value within some constant factor of the optimal for any given instance of the problem. The instances of the problem that your algorithm fails to give a answer for, do you notice any trends in terms of how 'off' the results are?
> 1 votes

---
Tags: algorithms, approximation
---


# Question
Title: Is there an algorithm that can solve any two-player game?
**Note:** this is basically a more precise restatement of this question, which didn't get proper answers because it was vague.

Most two-player perfect information games can be represented as a finite directed graph, because although the games could theoretically go on forever, there are only finitely many possible states for the game. Chess fits into this category, for instance. Here we'll consider states to be distinct even if the only difference between them is whose turn it is, thus our directed graph is always two-colorable with the colors "White's turn" and "Black's turn".

Given a directed graph $G$ with such a two-coloring, with one priveleged node called the "initial node", a *strategy* for a player $P$ is a partial function $s:N(G)\to N(G)$ such that:

1. $s$ is defined only on nodes at which it is $P$'s turn.
2. If $s$ is defined at a node $A$, then $s(A)$ is a child of $A$.
3. If $s$ is defined at a node $A$, it is defined at all children of $s(A)$.
4. $s$ is defined on the initial node, or on all children of the initial node if $P$ goes second.

Now, I'll call a *complete path* through $G$ a path through $G$ starting at the initial node which either goes on forever or ends at a node with $0$ out-degree, such nodes are called *endstates*. If $S$ is some set of complete paths, we will say that player $P$ can force $S$ iff there exists a strategy for $P$ such that any complete path which obeys that strategy (I think it's obvious what this means) is in $S$.

Some endstates are marked as victories for White, some are marked as victories for Black, some are marked as draws. Let $W$ be the set of all complete paths ending in a victory for White, $B$ be the set of all complete paths ending in a victory for Black, and $D$ the set of complete paths ending in a draw. Let $I$ be the set of all infinite complete paths, which we will also conceptually think of as draws.

It is then a theorem that either White has a strategy that forces $W\cup D \cup I$, or Black has a strategy that forces $B\cup D \cup I$, or both.

**Is there an algorithm which, given such a description of a game, outputs which players have such a strategy, along with the strategy itself?**

I don't mind if no such algorithm is actually *known*, but is there an existence or impossibility proof?

# Answer
(Note that you're excluding games with randomness, such as backgammon.)

Yes. In particular, endgame tablebases use most of such an algorithm.

```
Wbool,Wfull,Bbool,Bfull = set(),set(),set(),set()
keep_going = False
for v in nondraw_endstates:
 keep_going = True
 if is_a_victory_for_white_(v):
  Wbool.insert(v)
  Wfull.insert([v,0])
 else:
  Bbool.insert(v)
  Bfull.insert([v,0])
n = 1
while keep_going:
 keep_going = False
 for v in Wbool:
  for u in nodes_with_an_edge_to_(v):
   if u in Wbool:
    continue
   if white's_turn_(u):
    Wbool.insert(u)
    Wfull.insert([u,n,v])
    keep_going = True
    continue
   avoidable = False
   for x in nodes_with_an_edge_from_(u):
    if x not in Wbool:
     avoidable = True
     break
   if not avoidable:
    Wbool.insert(u)
    Wfull.insert([u,n,v])
    keep_going = True
 for v in Bbool:
  for u in nodes_with_an_edge_to_(v):
   if u in Bbool:
    continue
   if not white's_turn(u):
    Bbool.insert(u)
    Bfull.insert([u,n,v])
    keep_going = True
    continue
   avoidable = False
   for x in nodes_with_an_edge_from_(u):
    if x not in Bbool:
     avoidable = True
     break
    if not avoidable:
     Bbool.insert(u)
     Bfull.insert([u,n,v])
     keep_going = True
     continue
 if (initial_node in Wbool) or (inital_node in Bbool):
  keep_going = False
 else:
  n = n+1

```

Suppose the game is locally finite. If white has a winning strategy then the while loop will terminate and every extension of the result of removing the middle entries from Wfull's triples to all non-endstate white nodes is a winning strategy for white.  If black has a winning strategy then the while loop will terminate and every extension of the result of removing the middle entries from Bfull's triples to all non-endstate black nodes is a winning strategy for black. If only finitely many nodes can reach the non-draw endstates and neither side has a winning strategy then the while loop will terminate and white can always stay out of Bbool and white doing so guarantees that white won't lose. Bblack can always stay out of Wbool and black doing so guarantees that black won't lose.

If the while loop terminates, then it does so in an amount of time that's bounded above by a polynomial in (the number of nodes that can reach the non-draw endstates). Furthermore, by reduction from the circuit value problem, deciding who has a winning strategy is P-complete even when $G$ is (finite and) acyclic and there are no draw states.
> 2 votes

# Answer
As for chess - people use Negascout with heuristics, heavy prunning and results are poor. This comes from fact that branching factor is high.

If you have high end computation power this game is still far from being solved (which means that for every configuration you have winning strategy or draw at least).

More sophisticated games like Hex are very hard to solve - but this comes from complexity.

There are no algorithms to show strategy for player. You have to keep in mind that even gor chess people are using heuristics and change strategy addapting to oponent moves (this statement comes from my own experiments, tracking emotions and behaviour during game). So people are not repeatable players. This goes on to misleading strategy description.
Another one is number of gamed played - to get some indicator of strategy or ELO rating the more games played the better, but I do not know any human that would play for example 20000 games to define strategy, and this will change from mere fact of playing.

If nobody will give working algorithm I think it is good to treat this as too heavy computing power requirement. If you are not bothered by this good old Minimax will give you moves, but will not return patern of moves per player.

If you are able to provide solution to game - there is no indication that strategy tracking or creating good player is not possible - but still for human players there is a bit randomness in moves.
> 1 votes

# Answer
No. I believe that if we consider games that include draws (such as chess), and if we use a board that it is arbitrarily large (i.e. "infinite"), and if we use some huygens chess pieces (a huygens is a chess piece which jumps prime numbers of squares), then no algorithm can solve such a game. This is because the set of prime numbers itself is not completely known.
> -1 votes

---
Tags: board-games
---


title: Is $(a^nb^m)^r$ regular?

text:
# Question
Title: Is $(a^nb^m)^r$ regular?
I took my theory of computation exams a few weeks ago, and this was one of the questions:

> Assume language $L=\\{(a^nb^m)^r \mid n,m,r\ge 0\\}$
>
> Is L regular? If yes provide a regular expression or an automaton for it.

After I briefly asked him the answer after the exam, it appears it really is regular (I believe he said the expression is the simple $(a^\*b^\*)^\*$). However I cannot seem to understand why that is. The way I see it, its concatenating $a^nb^m$ **r** times, like this:

> $a^nb^ma^nb^ma^nb^m...a^nb^ma^nb^m$,

which isn't regular since there is no way for an automaton to recall **n** and **m** every time. Where am I at fault here?

EDIT: I talked to the professor again, he admitted it was a mistake. The language is indeed not regular.

# Answer
> 10 votes
The language $L$ is not regular, as can be proved using Nerode's method. Consider the following words $w\_n = a^n b$ for $n \in \mathbb{N}$. Then $w\_n^2 \in L$, but for $n \neq m$, $w\_n w\_m \notin L$. Hence any automaton for $L$ must be in a different state after reading each $w\_n$, which contradicts its finiteness.

# Answer
> 4 votes
In your comment you hint that you (quote) "gave a pumping lemma disproval for $r=2$, saying the same applied for bigger $r$".

This can indeed be formalized by applying a closure property. The regular languages are closed under intersection. So if $L$ is regular, then so would be $L\cap a^\*ba^\*b = \\{ a^n b a^n b \mid n\ge 0\\} $, effectively setting $r=2$ and $m=1$.

# Answer
> 0 votes
The language: **{(anbm)r | n,m,r≥0}** is **not** regular, because while the automaton/machine reads the first sequence of letters 'a' and then letters 'b', it needs to count the number of times it read the letter 'a' and the number of times it read the letter 'b' in the first sequence to know the value of **n** and **m**.

If **r\>1** then another **same** sequence of letters 'a' and letters 'b' is expected.

If the automaton/machine does**n't** know how many letters 'a' and letters 'b' it read in the first sequence then it also does**n't** know the value of **n** and **m** and thus it ca**n't** tell if the other sequences from second to last are words that equal to the first sequence.

But it's known that only Turing machine can count and know the values of **n** and **m** and recognize the language above, so **not** just that the language above is**n't** regular, but even it also is**n't** context free, i.e. also does**n't** exist pushdown automaton to recognize this language and does**n't** exist context free grammar that each word derived from that context free grammar is in the above language.

Because the fact that both deterministic finite automaton and pushdown finite automaton ca**n't** count and know the values of **n** and **m**, unlike Turing machine, they ca**n't** recognize the above language and thus the above language is**n't** context free and is**n't** regular.

Counterexample to the assumption that the language above is regular:

For **n=3 ∧ m=5 ∧ r=2**, the following word is in the above language:

aaabbbbbaaabbbbb

But the following word is**n't** in the language:

aaabbbbbaaaaabbb, because does **not** exist **n,m** and **r** so:

(anbm)r=aaabbbbbaaaaabbb, because to satisfy the first sequence of letters 'a' and then letters 'b', must be true that **n=3 ∧ m=5**, and because that we see 2 sequences of letters 'a' and then letters 'b', then **r=2**, but if **n=3 ∧ m=5 ∧ r=2** then (anbm)r = (a3b5)2 = (aaabbbbb)2 = aaabbbbbaaabbbbb ≠ aaabbbbbaaaaabbb, because their suffixes are different, i.e. aaabbbbb ≠ aaaaabbb, although their prefixes are equal to aaabbbbb for r=1.

The "best" deterministic finite automaton that can be built for this language is the deterministic finite automaton that recognizes the regular expression (a\*b\*)\*, but it does**n't** recognize the above language, because it tells that both the words aaabbbbbaaabbbbb and aaabbbbbaaaaabbb are in the language and this is not true, because aaabbbbbaaabbbbb is in the language, but aaabbbbbaaaaabbb is**n't** in the language.

Even pushdown finite automaton can't tell if both words are in the language or not, so only Turing machine can.

In the second sequence, the Turing machine found that **n=5 ∧ m=3** and this **contradicts** that in the first sequence it found that **n=3 ∧ m=5**, so it tells that the second word is**n't** in the language, but no contradiction is found in the first word.

Both sequences satisfy that **n=3 ∧ m=5**, so the Turing machine says that the first word is in the language.

Only Turing machine can, if it counts and remembers the values of **n** and **m** by writing their value on it's tape and later read them.

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


# Question
Title: Basic mapping reductions without using Turing machines
I have problems with the basics of mapping reductions.

I can understand how to do reductions using a Turing machine, but without it, I get a little bit confused.

For example:

1. How do I do a mapping reduction from $a$ to $b$, where $a$ is $\\{0,1\\}$ and $b$ is $\\{0\\}$ over the alphabet of $\\{0,1\\}$?
2. Does every language have a reduction to itself?

# Answer
> 0 votes
The identity function is a reduction from a language to itself. One reduction from $\\{0,1\\}$ to $\\{0,1\\}$ is given by $\lfloor x/2 \rfloor$, which maps $0,1$ to $0$, and all other integers to non-zero values.

---
Tags: reductions, computation-models
---


# Question
Title: Count arrays with size n, sum k and largest element m
I'm trying to solve pretty complex problem with combinatorics.

Namely, we have given three numbers N, K, M. Now we want to count how many different arrays of integers are there with length N, sum K and all the elements in the range \[1, M\]

Constraints:

* 1 \<= N \<= 100
* 1 \<= K \<= 100
* 1 \<= M \<= 100

**Example**

Let's say N = 2, K = 5, M = 3. This means that we want to count arrays of integers of size 2 with sum of all elements equal to 5 and elements in range \[1, 3\]. There are total of 2 arrays: {2, 3} and {3, 2}. Please note that the order of the elements also matters, {2, 3} is not equal to {3, 2}

Second example: N = 4, K = 7, M = 3. We want to count arrays of length 4, sum of 7 and elements in range \[1, 3\].

There are total of 16 possible way of arrays: (1,1,2,3), (1,1,3,2), (2,1,1,3), (3,1,1,2), (2,3,1,1), (3,2,1,1), (1,2,3,1), (1,3,2,1), (1,2,1,3), (1,3,1,2), (1,2,2,2), (2,1,2,2), (2,2,1,2), (2,2,2,1)

**What I have tried**

I know that one solution is to generate all possible arrays, but such algorithm in best case will work in complexity O(N!) which is far too big for N = 100. I started thinking about solving this with three-dimensional dynamical programming, but I cannot find the relations between the states.

I'm thinking about this way: Let f(i, j, l) be the number of arrays of length i, sum j, and largest element l. We can see that for i = 0 f(i,j,l) = 0, so this is I think the base case. Also f(1, 1, 1) = 1 is another base case.

Now I cannot find the relations between the states. Can you give me some hints how to find the relations between the states. Thanks in advance.

# Answer
> 3 votes
You can use dynamic programming. For each $0 \leq i \leq N$ and $0 \leq s \leq K$, count the number of arrays of length $i$, consisting of numbers in the range $\\{1,\ldots,M\\}$, which sum to exactly $s$. The running time is $O(NK)$.

Explicitly, denoting the array by $a$, we have $a(0,0) = 1$, $a(0,s) = 0$ otherwise, and $$ a(i,s) = \sum\_{t=1}^M a(i-1,s-t), $$ where $a(i-1,r) = 0$ if $r \< 0$.

As Hendrik Jan mentions in the comments, we can improve on this $O(NKM)$ algorithm by using the recursion $$ a(i,s) = a(i,s-1) - a(i-1,s-1-M) + a(i-1,s-1), $$ with suitable base cases.

Alternatively, we can obtain an explicit expression: the answer is the coefficient of $x^K$ in the generating function $$ (x + \cdots + x^M)^N = x^N \left(\frac{1-x^M}{1-x}\right)^N. $$ In other words, we are looking for the coefficient of $x^{K-N}$ in $$ \left( \sum\_{i=0}^N (-1)^i \binom{N}{i} x^{iM} \right) \left( \sum\_{j=0}^\infty \binom{j+N-1}{N-1} x^j \right), $$ which has the closed form $$ \sum\_{i=0}^{\min(N,\lfloor (K-N)/M\rfloor)} (-1)^i \binom{N}{i} \binom{K-iM-1}{N-1}. $$

# Answer
> 3 votes
You actually don't need the largest element `l` in your recursive function. It doesn't make such sense to use it, since the largest number in an array has no influence on the other numbers.

---

In most (all?) dynamic programming problems you have to think about the last step / the last part. For `f(i, j)` you have an array with `i` numbers. You can imagine, that in the last step you added the last number to the array. So before you added the last number, the array only consists of `i-1` numbers.

Now, if the added number was `1`, then there are `f(i-1, j-1)` many arrays. If the added number was `2`, then there are `f(i-1, j-2)` many arrays. And so on...

Add all those possibilities up, and you end up with `f(i, j)`.

# Answer
> 0 votes
I don't pretend this is the most efficient solution. Neither it has a strong theoretical merit, but you can still find it useful to verify your results. Here's a small program in Prolog, (using SWI Prolog for constraint satisfaction part), which can calculate or verify your guess:

```
% -*- mode: prolog; prolog-system: "swi" -*-
:- use_module(library(clpfd)).

sums(K, [], K).
sums(A, [X | Xs], K) :-
    indomain(A),
    indomain(X),
    B is A + X,
    sums(B, Xs, K).
sums([X | Xs], K) :- sums(X, Xs, K).

nmk_problem_helper(N, K, M, List) :-
    indomain(N),
    indomain(M),
    indomain(K),
    length(List, N),
    List ins 1..M,
    sums(List, K).

nmk_problem(N, K, M, Arrays) :-
    findall(X, nmk_problem_helper(N, K, M, X), Arrays).

nmk_problem_all_helper(List) :-
    [N, M, K] ins 1..100,
    indomain(N),
    indomain(M),
    indomain(K),
    length(List, N),
    List ins 1..M,
    sums(List, K).

nmk_problem_all(Arrays) :-
    findall(X, nmk_problem_all_helper(X), Arrays).

```

Example usage:

```
?- nmk_problem(4, 7, 3, X).
X = [[1, 1, 2, 3], [1, 1, 3, 2], [1, 2, 1, 3], [1, 2, 2, 2], [1, 2, 3, 1], [1, 3, 1|...], [1, 3|...], [2|...], [...|...]|...].

```

---
Tags: algorithms, counting
---


title: Finite State Automata Within A Compiler

text:
# Question
Title: Finite State Automata Within A Compiler
I've read up on Finite State Automata in a lot of different books on compiler construction (two of which are actually called Compiler Construction) and I'm kind of at a loss. I understand the idea of moving from state to state and having a state that is accepted. What I don't understand is why in the world this theory is regurgitated in such an obscenely convoluted way?

If you were to tell me that the point of FSA within a compiler is for Lexical Analysis and that its purpose therein is just to go character by character and determine whether or not a word is an identifier, keyword, or other token, I would be completely confident in my understanding. Problem is that in every chapter of finite state automata I have to go over 50 pages of rigorous notation, differences between non-deterministic and deterministic finite state automata (including separate notation where Epsilon is three different things based on its styling) and a dozen or more of these graphs:

My question is this: Do I need to understand more than this to write a Compiler? Is there something unique about FSA that I'm just completely missing? Or is this just an over complication of a simple concept in regards to creating a compiler?

# Answer
> 13 votes
What you have asked: "*Do I need to understand more than this to write a compiler?*" then answer is basically, No - but it does depend on the compiler!

You need to know a lot of theory about a lot of other things, and you could eventually ask about them too. For example, when you get to parsing you might ask "Do I need to know about top-down **and** bottom-up parsing". Do I need to know the difference between LL, LR, LALR parsing? Do I need to know about Chomsky Level 1 Grammars? Does it matter who Noam Chomsky actually is? Do I need to be able to know how to parse ambiguous languages? Do I need to know about data-flow in optimisation, do I need to know about flow-graphs? Do I need to know about machine architecture? Do I need to know about **both** register based machine code and stack based machine code?

Just so many things that one could question the need for!

You can write some kind of compiler without knowing any of this, but you wouldn't be fully equipped with all the background knowledge to be able to write **any** compiler!

If your task was to write a very straightforward compiler for a straight forward language then you can get away without knowing a lot of the background theory. There are some class exercises like that. If your jobs was as a compiler writer then you might be expected to be able to do a bit more.

The next part of your question to address are the textbooks you have used. Most of the textbooks are written for use on undergraduate Computer Science courses. In many/most those courses the background theory behind the practice of writing compilers is included because that is what most course curricula need. This then permits the students to use their wider knowledge to implement compilers for the as-yet-to-be-specified languages to solve the problems of the future. If you could only tackle the simple subset problems from introductory classes that did not require thinking outside the box you knowledge would be rather useless; or rather only useful for class credit, but not much beyond.

I hope that gives the view of a compiler writer and computer scientist. My students sometimes ask the same questions.

# Answer
> 8 votes
You don't need to know FSAs for writing a compiler, provided you use a lexer generator that writes the lexer for you.

In parts the emphasis on FSAs in compiler books is historical: fast lexing used to be a big problem in early computer science and the theory of FSAs is some of the earliest and most developed of computer science. Most textbooks (and lectures) are small variants of earlier textbooks. In the case of compilers the dominant textbook has been the Dragon Book. It is almost half a century old and has quite a lot to say about lexing and FSAs.

Another reason might be that lexing and FSAs are the easiest part of a compiler, and teachers might feel they should explain at least something about compilers with full rigour. BTW, even writing a lexer by hand for a toy language is not simple, because the resulting FSA is quite large (\> 1k states). If you 'cheat' and use a regular expression library you'll probably get it wrong -- I know because I teach compilers and writing a lexer / parser for a toy language is one of the assessed exercises they'll have to do. Moreover, regular expression parsers are also implemented 'under the hood' using FSAs.

Finally, FSAs are incredibly useful in computer science, and you do yourself a favour to understand them well. See this answer for some of the uses of FSAs.

In practise understanding lexing / parsing is probably the most important part of a compilers course: almost no student will ever write a type inferencer or code generator in their commercial work, but just about any non-trivial programming task involves reading small (and not so small) formal languages. Almost nothing is as useful as mastery of lexer and parser generators to get this done quickly.

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


# Question
Title: Why is it that the flow value can increased along an augmenting path $p$ in a residual network?
I was learning about Max Flow and Residual Graphs and was wondering if there was a formal proof for the statement:

> the flow value can increased along an augmenting path $p$ in a residual network

I was reading the slides linked at the end of question and they seem to omit the most important part of the algorithm which is proving the above claim!

Recall how a residual network is built (which can be referenced on chapter 26 of CLRS):

$$c\_f(u,v) = \begin{cases} c(u,v) - f(u,v) & if (u,v) \in E, \\ f(v,u) & if (v,u) \in E \\ 0 & otherwise. \end{cases} $$ also recall that because we don't allow self loops of length 1 or 2 (i.e. if $(u,v) \in E \implies (v,u) \not \in E$, exactly one case in the above definition of residual capacity applies.

I understand that intuitively, the first case encompasses the idea of the additional flow that we can increase in the original graph (since it encompasses the amount of extra flow we can increase) and the second case is suppose to be included for allowing our algorithms to decrease the flow.i.e. sometimes it may be necessary to actually decrease the flow in some edge(s) (or increase the flow in the opposite direction) so that the overall flow increases.

Even though this ideas are clear to me, its not clear how its guaranteed that we can actually increase the overall flow in the original graph $G$ if we choose say, the minimum residual capacity in an augmenting path. In particular, its clear to me if the path only contains edges of case 1 (since increasing the flow along such a path just means increasing the flow such that we are still bellow the capacity, so its trivial to increase the flow), but the second type of edge make it confusing for me. How is it that those edges guarantee the following:

1. The flow increases overall
2. No conservation law is broken (flow in = flow out is still obeyed)
3. No capacity constraint in the original graph is obeyed.

Not sure if there are other properties to check but those are the ones I was able to think of.

---

This is what I have so far:

Let the smallest residual capacity be $c\_f(p) = \min\_{(u,v) \in p} \\{ c\_f(u,v) \\}$. If we increase the flow according to it then its clear no capacity constraint is violated. Why? There are only two type of possibilities the edge could have come from:

1) The difference between a capacity and a flow 2) The opposite direction of a flow already on the network.

Consider case 1 first. If we increase the flow, then it means that we decrease difference of the capacity and a flow (i.e. the residual capacity). If this is the case, since we choose the smallest residual capacity as the amount to make the decrease, we don't risk increasing the flow to much because an increase will correspond to a increase in flow such that the flow is less that the capacity on the real network.

If on the other hand, if the edge came because it corresponded to the opposite direction of flow of an edge, then its even easier, because that means that the flow on the original graph will correspond to a decrease not an increase. Since we are decreasing we cannot violate a capacity constraint. Furthermore, since we are choosing the smallest decrease to be made, there is not risk of the flow randomly becoming negative in the original graph (which would correspond to non-sense). Hence, this can't happen either.

Therefore, the capacity constraints are not violated by this choice of change of flow on the network.

The other two conditions, seem a little harder to check. I am sort of stuck on the other two but will keep trying and if I make progress (or not) update the question.

---

I am learning flow form the following slides based on CLRS:

https://stellar.mit.edu/S/course/6/sp15/6.046J/courseMaterial/topics/topic2/lectureNotes/Network-Flow-Spring15-trunc/Network-Flow-Spring15-trunc.pdf

https://stellar.mit.edu/S/course/6/sp15/6.046J/courseMaterial/topics/topic2/lectureNotes/Network-Flow-II-Spring15/Network-Flow-II-Spring15.pdf

# Answer
Instead of giving a formal proof I will present some intuition on why augmenting paths increase the flow. Look at the picture below. Let's go through some augmenting path, for example the one painted in black. It increases the flow by some $x$. Then go through another one (that has $c\_f(p) = y$) that contains an edge which pulls back some flow (edge $(u, v)$ is present only in residual network). When the red path enters $u$, it increases the flow that comes into $u$ by $y$, but then pulls $y$ units of flow back to $v$, so $v$ can use edge from red path to push those $y$ units somewhere else. So you see that $y$ units came to $u$, $y$ units was withdrawn from $u$, $y$ units came back to $v$ and then $y$ units went through the red path. The property that income flow equals the one that goes out is preserved. Capacity constraints (flow through an edge is not greater than capacity of this edge) are also preserved, because $y$ is the smallest edge weight on the red path. As you can see, going through the red path increases overall flow by exactly $y$, because augmenting path doesn't decrease the flow anywhere, it rather redirects it in the manner described above. It's like vertex $u$ saying to vertex $v$ "Oh hey, the red path gave me some flow, maybe you ($v$) would take back some of the one you gave me and send it to someone else?". I'd say that adding "redirecting" word somehow to "augmenting path" would clear some misunderstanding about this concepct.

Having this intuition, I think that making a formal proof from it should be fairly easy.
> 1 votes

---
Tags: algorithms, algorithm-analysis, network-flow, max-flow
---


# Question
Title: Show that problem is PSPACE-complete - path in directed graph
I have a following problem:
**Given** $n$ and graph of size $2^n$, and circuit with $2n$ input gates. Directed edge between $k$ and $l$ exists iff only and only we encode $k$ and $l$ as bits and launch circuit on this input and get result $0$.

**Problem**: Is there exists path from vertex $k$ to vertex $l$ ?

I can reduce arbitrary problem from $PSPACE$ to above problem. The only thing that I can't do is showing that problem given in exercies belongs to *PSPACE*.

Tell me please, if my reasoning is correct (it seems to be too simple):
We know that $PSPACE = NPSPACE$. So we can give non-determinitic algorithm. Algorithm can guess sequentially verticles and check (using circuit) if there exists path).
I can say more, let algorithm guess ansewr (0 or 1).

Can you help me ?

# Answer
Given $k$ and $l$ you can check if there is a path between these nodes using DFS. DFS requires polynomial space and time. So, that problem is in PSPACE.

**Update: I'd be glad to take into account the downvoter's opinion and improve the answer.**
> -3 votes

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


# Question
Title: Compute lebesgue measure of set of intervals
Let $S = \\{ \[x\_1, y\_1\], \[x\_2, y\_2\], \dots, \[x\_n, y\_n\] \\}$ be a set of not necessarily disjoint intervals on $\mathbb{R}$. Is there an efficient way to compute the lebesgue measure of the union $\displaystyle \bigcup\_{i = 1}^n \[x\_i, y\_i\]$ ?

I present my ideas and approaches as following.

If all intervals of $S$ are disjoint (special case), the problem is trivial and may be solved in time $\mathcal{O}(n)$. The solution is obviously $\sum\_{i = 1}^n y\_i - x\_i$ .

In the general case, we can remove intersections as long as possible. After this procedure, we apply the special case described above. There raise up two questions:

* How to find and remove intersections?
* How efficient is this solution in terms of runtime complexity?

Another approach is to sort the intervals of $S$ by $x\_i$ or $y\_i$. It seems to be a good way to simplify the problem, but does it really help and how? There are several cases we must consider: disjoint intervals, overlappings, intervals completely contained in another, ...

It should be noticed that I am interested in an efficient solution. Can we do in time $\mathcal{O}(n)$ and why or why not?

I appreciate hints and references for further reading as well as solutions.

# Answer
> 3 votes
You can solve this in $O(n \log n)$ time. Here is an algorithm. Sort the intervals by their left endpoint ($x$-value), in increasing value. At each stage, if the first interval is disjoint from the second interval, remove the first interval and add its width to the running total so far. If they're not disjoint, replace the first two intervals by their union.

---
Tags: algorithms, numerical-algorithms, intervals
---


# Question
Title: Algorithm to generate self-avoiding random walk on a lattice
Where can I find some code to generate random self-avoiding walks on 2 and 3-dimensional lattices whose side-lengths are powers of two? The walk should pass through every point on the lattice More specifically, how can I find a random hamiltonian path on a large $2^n \times 2^n$ or $2^n \times 2^n \times 2^n$ grid graph?

The distribution doesn't have to be completely uniform, however in general the lattice should look wrinkled. The method used to generate the path should have low probability of producing extremely long stretches of straight line.

# Answer
> 6 votes
A procedure is described in A combinatorial algorithm for effective generation of long maximally compact lattice chains.

# Answer
> 4 votes
Here are two javascript implementations of an algorithm to sample Hamiltonian paths on 2-dimensional grid graphs: http://clisby.net/projects/hamiltonian\_path/ and http://clisby.net/projects/hamiltonian\_path/hamiltonian\_path\_v1.html (This is my code. The implementation at the first link has more features, while the second allows you to download the sequence of sites visited by the path.)

The javascript programs generate Hamiltonian paths on an n × n grid using the backbite move described in the paper “Secondary structures in long compact polymers” by Richard Oberdorf, Allison Ferguson, Jesper L. Jacobsen and Jané Kondev, Phys. Rev. E 74, 051801 (2006). Paper available via the APS (subscription required) or as a pre-print on the arXiv at https://arxiv.org/abs/cond-mat/0508094

The code includes an adjustable parameter that determines how close to the uniform distribution your sample will be, and you could adapt the method (Markov chain Monte Carlo with backbite moves) to 3d grid graphs with a little work.

---
Tags: random-walks, lattices
---


title: Programming question for a new approach

text:
# Question
Title: Programming question for a new approach
There is a matrix of size (M x N) in which the cells are marked by one of the three letters (either 'a','b' or 'c'). Now given that there is only one cell that is marked with value 'a' but more than one cells can be marked with value 'b' or 'c'.

There is 8 ways in which one can move form one cell to another, considering rowwise, columnwise, diagonal and anti-diagonal movements to the next cell. taking the cell marked by 'a' as starting cell and cells marked by 'c' as destination cells. The length of a route is defined as the total number of steps taken while moving from starting to a destination cell without going through the cells marked by value 'b'.

What is the minimum length of the route for a given matrix with all the cells properly marked with values either 'a','b' or 'c'? I tried using the recursive implementation which basically is taking long time (as it checks all the 8 directions and then it gives the best of them). Can I get a better solution approach may be through DP? Any help is greatly appreciated.

# Answer
Construct a graph in which the vertices are all cells not marked 'b', and in which two vertices are connected if they are adjacent in the matrix. Use BFS from the 'a' vertex to go over all vertices in order of distance from 'a', until you find the first 'c' vertex. The overall complexity is $O(MN)$.
> 2 votes

---
Tags: algorithms, dynamic-programming
---