title: Coalescing by register allocation

text:
# Question
Title: Coalescing by register allocation
I have a rough idea of what coalescing in terms of memory access by threads is, but now, when learning about compilers, the term coalescing also appears when talking about register allocation.

In my book, it is just briefly mentioned, that coalescing for register allocation is just merging nodes from the graph (I assume the nodes of the graph show the variables that can be stored in a register).

Can someone explain a bit more thoroughly what coalescing in this sphere means?

# Answer
In this context, "coalescing" means eliminating variable-to-variable move operations in the register allocator by allocating those two variables to the same location, typically the same register.

It may not be obvious why you'd do this in the register allocator, as opposed to in an earlier optimisation like constant folding. The reason is that code generation might introduce loads and stores for convenience or optimisation purposes.

The way that register allocation is often presented, you generate an assignment of "variables" to "locations", where a location could be a register or spilled. That's a good mathematical model of the problem, but it's a bit more complicated than this in practice.

Look at live range splitting as one example. This is an optimisation where a variable is not held in the same place for its lifetime ("spilling" can be thought of as a special case). As a concrete example, consider the case of two nested loops with a variable that is used a lot in the inner loop:

```
x <- something();
for (outer loop) {
    some_computation();
    for (inner loop) {
        some_other_computation_involving(x);
    }
}
use(x);

```

It seems like we probably want to store `x` in a register in the inner loop, but we may not want to store it in a register in the outer loop, because that would tie up a register during `some_computation`. On the other hand, there may be enough registers to keep `x` in a register, depending on how allocation for `some_computation` works out.

One solution is to split the range of variable `x` into two:

```
x1 <- something();
for (outer loop) {
    some_computation();
    x2 <- x1;
    for (inner loop) {
        some_other_computation_involving(x2);
    }
    x1 <- x2;
}
use(x1);

```

That introduces two variable-to-variable moves. If we allocate `x1` and `x2` to different locations, we are essentially spilling `x` for some of its lifetime. But using a coalescing-aware allocator, we have the chance that the spill may never happen if the moves are coalesced.

Another interesting case is that of special-purpose registers and calling conventions. Suppose, for example, you are calling a function:

```
x <- f(p(), q());

```

We will also suppose that the calling convention for this architecture requires the first argument for the call to `f` to be in register `r1` and the second argument to be in register `r2`. One way to do this is to generate code like this:

```
t1 <- p()
r2 <- q()
r1 <- t1
call f

```

Again we have introduced a variable-to-variable move. A coalescing-aware register allocator can then decide whether to "spill" `t1` or to generate it directly in `r1`:

```
r1 <- p()
r2 <- q()
call f

```

I use the word "spill" advisedly here because it might also be appropriate it to "spill" it to another register:

```
r3 <- p()
r2 <- q()
r1 <- r3
call f

```

Since `r1` plays an important role in the calling convention, it may be needed for computing `q()`.

Callee-save/caller-save registers can also be implemented using this mechanism.
> 4 votes

---
Tags: compilers, memory-management
---


# Question
Title: Given three infinite languages L1 L2 L3 over the same Alphabet, that do not intirsect. could one be TR and the other TD and the third neither?
$\sum$ is the Alphabet of three infinite languages $L\_{1},L\_{2}$ and $L\_{3}$

where $L\_{1}\cup L\_{2} \cup L\_{3}=\sum^{\*}$

and

$L\_{1} \cap L\_{2} = \emptyset$, $L\_{2} \cap L\_{3} =\emptyset$ and $L\_{1} \cap L\_{3} = \emptyset$

is it possible that $L\_{1}$ is Decidable, $L\_{2}$ is Turing Recognizable but not Decidable

and $L\_{3}$ is not Turing Recognizable?

If so please give an example, if not why?

Now, it is most likely this is possible, I just had trouble finding an example.

# Answer
Let $L\_{1}$={Set Of All Regular Languages},

$L\_{2}\cup L\_{3}$= $\bar{L}\_{1}$

$L\_{2}$={Set Of All Non Regular Languages That Are Recognizable By Turing Machines.}

$L\_{1}$ is Decidable, $L\_{2}$ Recognizable but not decidable, and $L\_{3}$ is not recognizable. Languages do not intersect and their union is all the alphabet.
> 0 votes

---
Tags: complexity-theory
---


# Question
Title: Fastest known algorithm for $3$-$\mathrm{Partition}$ problem
$3$-$\mathrm{Partition}$ problem is $\mathsf{NP}$-Complete in a strong sense meaning there is no pseudo-polynomial time algorithm for it unless $\mathsf{P=NP}$. I am looking for the fastest known exact algorithm that solves $3$-$\mathrm{Partition}$.

Is there a fast (e.g subexponential) algorithm for $3$-$\mathrm{Partition}$? Is it possible to solve it faster than using SAT solvers?

# Answer
> -1 votes
If you find a fast (sub-exponential) exact algorithm for 3-Partition , while 3-Partition is NP-Complete, then dear sir you have just proven P=NP, which no body has done so far, and you have a 1M $ price waiting for you as well as wealth and fame, cheers.

Anyway if you do have a faster than a SAT solver, wouldn't you actually be performing SAT it's self faster? I mean if you can reduce SAT to 3-PARTITION and you can solve 3-PARTITION in sub-expo time, doesn't that mean that SAT can be solved in sub-expo time, hence all NP-COMPLETE problems also can be solved in such time? So you might as well be looking for a sub-expo time solution of any other NP-COMPLETE problem just as well, it would still be a significant breakthrough.

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


# Question
Title: Longest subsequence accepted by DFA (Dynamic Prog algorithm)
Problem: Given a string $s$ and a DFA $D$, compute the longest subsequence of $s$ such that the subsequence is accepted by $D$, or report that no such subsequence exists.

This problem has a runtime of $O(qn)$ where $q$ is the number of states of the DFA, and $n$ is the length of the string.

This problem is supposed to be solved using Dynamic Programming.

I can't figure out how to get a bound lower than $O(2^n)$.

My recurrence (it's $O(2^n)$ with memoization) --

Consider the string to be $A\[1 .. n\]$. And consider the substring $A\[1 .. i\]$ for $i \< n$. I know the length of the longest subsequence accepted by the DFA for this substring. Next, I consider the substring $A\[1 .. i+1\]$.

If this substring has a longer subsequence that is accepted by the DFA, the max value is updated. If not, the max value is kept the same. To figure out if the max value got updated, I have to search for all subsequences accepted by the DFA that have $A\[i+1\]$ included in them, as well as the entire substring $A\[1 .. i+1\]$.

This last thing can be memoized. That is, the end point of the entire substring $A\[1 .. i\]$ can be memoized. So when we need to check if $A\[1 .. i+1\]$ works, we just need to go to the next state after reading $A\[i+1\]$.

We can also memoize a lot of the earlier problems we solved. We memoize the pair (subsequence, end-state).

Here's an example: Consider the string $a\_1a\_2a\_3a\_4$.

$a\_1$:
Takes $O(1)$ to check. Then memoize.

$a\_1a\_2$:
Check $a\_2$. Takes $O(1)$. Then memoize.
Check $a\_1a\_2$. Takes $O(1)$ as checking $a\_1$ was previously memoized. Then memoize.

$a\_1a\_2a\_3$:
Check $a\_3$: Takes $O(1)$. Then memoize.
Check $a\_1a\_3$, $a\_2a\_3$: takes $O(1)$ per check, as $a\_1$, $a\_2$ were previously memoized. Then memoize. Check $a\_1a\_2a\_3$: Takes $O(1)$ as checking $a\_1a\_2$ was previous memoized.

$a\_1a\_2a\_3a\_4$:
Check $a\_4$: Takes $O(1)$. Then memoize.
Check $a\_1a\_4$, $a\_2a\_4$, $a\_3a\_4$: takes $O(1)$ per check, as $a\_1$, $a\_2$, $a\_3$ were previously memoized.
Check $a\_1a\_2a\_4$, $a\_1a\_3a\_4$, $a\_2a\_3a\_4$: takes $O(1)$ per check, as $a\_1a\_2$, $a\_1a\_3$, $a\_2a\_3$ were previously memoized.
Check $a\_1a\_2a\_3a\_4$: takes $O(1)$ as $a\_1a\_2a\_3$ was previously memoized.

# Answer
> 1 votes
You can add an extra parameter $s$, which represents a state of the DFA, for your dynamic programming.

Let $f(i,s)$ be the length of the longest subsequence of $A\[1\ldots i\]$ accepted by a DFA obtained by changing the end state of the primary DFA to $s$. Now $f(i+1,s)$ can be computed by comparing $f(i,s)$ (representing $A\[i+1\]$ is not chosen) and $f(i,t)+1$ (representing $A\[i+1\]$ is chosen) for each state $t$ that transforms to $s$ when reading $A\[i+1\]$.

But note, the time complexity this algorithm is not bounded by $O(qn)$ because we may have to check no more than constant $f(i,t)$'s for each computation. A simple improvement is to consider $A\[i\ldots n\]$ instead of $A\[1\ldots i\]$. Now $f(i,s)$ represents the length of the longest subsequence of $A\[i\ldots n\]$ accepted by a DFA obtained by changing the **start** state of the primary DFA to $s$, and $f(i,s)$ can be computed by comparing $f(i+1,s)$ and $f(i+1,t)+1$ where $s$ transforms to $t$ when reading $A\[i\]$. Now the running time is improved to $O(qn)$.

---
Tags: dynamic-programming
---


# Question
Title: Training a neural net without labels in Reinforcement Learning
I am trying to dig further into machine learning and I am making a program to play a game as a start. I have created a game that is based on the mobile game *Flappy Bird* and can be generalized to the following:

* Actions $A = \\{\text{no action}, \text{tap}\\}$
* States $S \subset \mathbb{R}^3$ such that $s \in S$,
    + $s\_1$ is the horizontal distance to the center of the nearest forward gap
    + $s\_2$ is the vertical distance to the center of the nearest forward gap
    + $s\_3$ is the vertical velocity ($\text{unit}/\text{sec}$)

As a starting point, I have implemented a naive Q-Learning algorithm with positive rewards whenever it passes through a gap successfully. Everything went well and the q-table ($f(s): S \to A$) was adjusted accordingly to the rewards.

Now I would like to train a neural net to do the same. One problem that existed with the Q-Learning approach is that the algorithm does not take locality into account. I had to also discretize the feature space into very huge chunks which is not optimal. I am hoping that a neural net can solve these issues.

I am familiar with performing basic classifications with neural nets, and so I am trying to approach this problem similarly. I would just take a *state* (a vector of three real numbers) as input and an *action* as output (one neuron per action and take the one with the highest probability). The problem is, I do not have labels for training! The only thing that I get from the game is reward.

Is a neural net a good choice for this type of problem? How should I train or design such network?

# Answer
> 2 votes
What you are looking for is DQN: Deep Q-Network.

You want to have a look at the example code, but the idea is as follows:

* **Input**: The observation
* **Output**: Reward - the action can either be in the input or better one reward-prediction per possible action, if the action is discrete.

For final states, you know the true reward. Hence your target is clear (see line 112). But if this is not the case, you need to adjust the target to the observed reward and the discounted expected reward (line 113ff).

Extremely important: **The output layers activation function**. Don't use softmax, as it is unlikely that your rewards sum up to 1. Don't use ReLU if the reward can be negtive. Simply using a linear output makes most sense in most cases.

# Answer
> 2 votes
The whole point of reinforcement learning is that it gives you a way to train a machine learning algorithm, without having labels for training. It provides a way to obtain labels; then you use some existing ML method to build a policy. You can use any ML method you like, including a neural network -- neural networks are often chosen for this purpose, because they seem to work well in many situations.

So, I suggest that the best answer to your question is going to be: use reinforcement learning with neural networks. See, e.g., https://karpathy.github.io/2016/05/31/rl/ for an overview of how you could do that.

See also Are neural networks a type of reinforcement learning or are they different? for an overview of the relationship between reinforcement learning, supervised learning, and neural networks.

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


# Question
Title: Trying to verify the solution to a lambda calculus equation
I am going through the following introduction to lambda calculus :

http://www.cse.chalmers.se/research/group/logic/TypesSS05/Extra/geuvers.pdf

At page 12 , the following has been asked to prove

$ \exists $ $ G $ $ \forall X $ such that

$GX$ = $GG$

This means to find a function which takes a function as an argument and returns the same expression irrespective of the function .

The book posits the solution to be $ G $ = $Y$ $( \lambda gx. gg) $

On trying to verify this I first evaluated the L.H.S to be

$ GX $ = $ Y ( \lambda gx.gg ) $ $X$.

Now $X$ being the argument will be picked up by the first bound variable so .

$L.H.S $ = $ Y ( \lambda x . XX) $ = $( \lambda x . XX)$ $ Y ( \lambda x . XX) $ = $ Y ( \lambda x .$ $ Y ( \lambda x . XX)$ $ Y ( \lambda x . XX)$)

Here due to the presence of the form $ YF $ , I can carry on the reduction continuously by replacinf $YF$ with $FYF$

$R.H.S$ = $Y$ $( \lambda gx. gg) $ $Y$ $( \lambda gx. gg) $ = $Y$$ \lambda x.$ $( Y( \lambda gx. gg) $ $Y( \lambda gx. gg)) $

Now similarly the reduction can be carried on further by again consuming the first $g$ that comes in the expression with $Y( \lambda gx. gg)) $ and this can on perpetually and it will look like $ Y ( \lambda x .$ $ Y ( \lambda x . XX)$ $ Y ( \lambda x . XX)$)..... So I couldn't completely ascertain that they ( L.H.S and R.H.S) will turn out to be equal but I can see that L.H.S and R.H.S are going to be infinitely long and will resemble each other more and more as the number of reductions go on since the $ g$ 's in the R.H.S will continually get replaced .

Is this logic correct ? If not , where did I err ?

P.S. : On a general and on a lighter note , how are this lambda calculus equations solved ? (They look analogous to differential equations ).

# Answer
> On trying to verify this I first evaluated the L.H.S to be
>
> $ GX $ = $ Y ( \lambda gx.gg ) $ $X$.
>
> Now $X$ being the argument will be picked up by the first bound variable so .
>
> $L.H.S $ = $ Y ( \lambda x . XX) $

This is where you went wrong, and the reason is that you've got the association the wrong way round. $Y ( \lambda gx.gg ) X$ means $(Y ( \lambda gx.gg )) X$.

Taking that into account, the only evaluation step possible is to apply $Y$, giving $$( \lambda gx.gg )(Y ( \lambda gx.gg )) X$$ which is $( \lambda gx.gg )GX$, from which the desired conclusion is immediate.
> 3 votes

---
Tags: lambda-calculus
---


# Question
Title: Regular expression for string with substring 010 and ending with 01
How can one design a regular expression for given string in title ?

Also how can we draw DFA of that regular expression?

I've tried many expressions but couldn't succeed, please help.

# Answer
The regular expression would be like $(0 + 1)^\*010(0 + 1)^\*01 + (0 + 1)^\*0101$. Transformation of a regular expression to a DFA has a well-defined algorihtms, and you can find them in the resources.
> 1 votes

# Answer
Not the best photo quality , but it will work. I think this DFA is the one but correct me if i'm wrong. :)
> 0 votes

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


# Question
Title: Algorithm to generate non-repeating random numbers of O(1) memory?
Is it possible to create $O(1)$ memory consuming algorithm, which is generating non-repeating pseudo random numbers?

I can remember numbers in the hash set and it will be $O(1)$ time, but the set will grow as numbers generated as $O(N)$. Is it possible to do $O(1)$?

**UPDATE**

Narrowing the question: we have parameter $N$. We need to generate all numbers from 1 to $N$ without repetition in (pseudo) random order.

**UPDATE 2**

May be there are reversible hash functions? I would compute just $H(i)$ then.

# Answer
First, you should precisely define what you mean by random. One way to interpret you question is as follows. Given some fixed number $N$, you wish to sample elements from the uniform distribution over the set $\\{1,...,N\\}$. Let us denote by $S$ the set of samples seen so far, then we want to support a $Gen$ command, which upon calling returns a uniformly chosen element from $\\{1,...,N\\}\setminus S$. $Gen$ has access to additional memory $q\in\\{0,1\\}^\*$ (the state), which can be altered upon invocation.

It can be easily shown that you cannot achieve the above goal while keeping $q$'s length bounded by some constant. Suppose $|q|\le c$ for some $c\in\mathbb{N}$, and choose $N$ such that $N \> 2^c$. Consider the random variable $x\_1,...,x\_N$ obtained by invoking $Gen$ $N$ times. The difference in the distributions of $x\_i,x\_j$ depends solely on $q\_i,q\_j$ (the state during the sampling). Since there are less than $N$ possible states (values of $q$), there exists $i\neq j$ such that $x\_i,x\_j$ are drawn from the same distribution, contradiction.
> 2 votes

# Answer
Take any bijective memoryless function $f$ that scrambles the bits and use the sequence $f(i)$ for $i\in\[0,N)$.

For instance, Gray codes.
> 1 votes

# Answer
Many pseudo-random number generating algorithms naturally produce a very long sequence of unique numbers, and the repeat the sequence. Of course if you have a sequence length of $2^{128}$ then the sequence is not repeating.

So the solution: If you need non-repeating numbers in the range 1 to n you use a PRNG with a cycle not longer than n. If n is small, it’s not going to be very random.
> 0 votes

# Answer
Effectively what you want to compute is some permutation of a sequence of numbers $\\{1, \ldots, n\\}$.

Let $p\_1$ and $p\_2$ be two prime numbers. It can be shown that the sequence

$$(p\_1)^1 \text{ mod } p\_2, (p\_1)^2 \text{ mod } p\_2, (p\_1)^3 \text{ mod } p\_2, \ldots, (p\_1)^{p\_2} \text{ mod } p\_2$$

does not have repetitions. So if you want to get a pseudo-random permutation of the numbers $\\{1, \ldots, n\\}$, you can set $p\_2$ to be a prime number higher than $n$ and select $p\_1$ somehow (e.g., close to 1/4 of $p\_1$). Then, when enumerating the sequence above, you just drop all elements greater than n.

Note that the resulting sequence is only *somewhat* random according to some statistical tests.
> 0 votes

# Answer
No.

Any deterministic algorithm with bounded memory has a finite number of states and every state always leads to the same next state.

So whatever you generate will be periodical, with a period not excceding $2^S$for $S$ bits of memory.
> 0 votes

---
Tags: space-complexity, pseudo-random-generators
---


# Question
Title: on "On the cruelty of really teaching computing science"
Dijkstra, in his essay *On the cruelty of really teaching computing science*, makes the following proposal for an introductory programming course:

> On the one hand, we teach what looks like the predicate calculus, but we do it very differently from the philosophers. In order to train the novice programmer in the manipulation of uninterpreted formulae, we teach it more as boolean algebra, familiarizing the student with all algebraic properties of the logical connectives. To further sever the links to intuition, we rename the values {true, false} of the boolean domain as {black, white}.
>
> On the other hand, we teach a simple, clean, imperative programming language, with a skip and a multiple assignment as basic statements, with a block structure for local variables, the semicolon as operator for statement composition, a nice alternative construct, a nice repetition and, if so desired, a procedure call. To this we add a minimum of data types, say booleans, integers, characters and strings. The essential thing is that, for whatever we introduce, the corresponding semantics is defined by the proof rules that go with it.
>
> Right from the beginning, and all through the course, we stress that the programmer's task is not just to write down a program, but that his main task is to give a formal proof that the program he proposes meets the equally formal functional specification. While designing proofs and programs hand in hand, the student gets ample opportunity to perfect his manipulative agility with the predicate calculus. Finally, in order to drive home the message that this introductory programming course is primarily a course in formal mathematics, we see to it that the programming language in question has not been implemented on campus so that students are protected from the temptation to test their programs.

He emphasises that this is a serious proposal, and outlines various possible objections, including that his idea is "utterly unrealistic" and "far too difficult."

> But that kite won't fly either for the postulate has been proven wrong: since the early 80's, such an introductory programming course has successfully been given to hundreds of college freshmen each year. \[Because, in my experience, saying this once does not suffice, the previous sentence should be repeated at least another two times.\]

**Which course is Dijkstra referring to, and is there any other literature available that discusses it?**

The essay appeared in 1988 when Dijkstra was at the University of Texas at Austin, which is probably a clue -- they host the Dijkstra archive but it is huge, and I'm particularly interested in hearing from others about this course.

I don't want to discuss whether Dijkstra's idea is good or realistic here. I considered posting this on cstheory.se or cs.se but settled on here because a) a community of educators might be more likely to have someone who can answer easily, and b) Dijkstra himself emphasises that his course is "primarily a course in formal mathematics." Feel free to flag for migration if you disagree.

# Answer
> 18 votes
This is pretty much what TU Eindhoven's Computing Science education, designed and implemented by Dijkstra and colleagues, was like from the time it started, around 1980, until Dijkstra's influence started to wane, somewhere half way through the 1990s.

I started studying CS at Nijmegen University in 1982; a classmate did the same at TU Eindhoven. Every spring, our old secondary school would have a day on which former students would introduce their chosen field of study to current students, and we were both there to introduce CS, so we compared our experiences. They were vastly different. In Nijmegen, we obtained actual experience with actual programming languages, actually running our assignment programs on an actual computer (a VM/CMS virtual machine, to be precise). Not so in Eindhoven. My former classmate told me they weren't allowed to touch a computer in the first year. Programming, in Eindhoven, meant learning to mathematically construct provably correct algorithms from mathematically stated problem definitions. On paper.

This attitude was somewhat relaxed after Dijkstra left, but even in the early 1990s, the courses called *Programmeren* (Programming), numbered 1 to 9, and spanning several years, still consisted of that same activity, and one in particular presented a major hurdle for the students. I never took any of those courses, but I doubt any use of computers was involved.

In case you're wondering: today's computer science education at TU Eindhoven is very different.

# Answer
> 2 votes
Have a look at "A Method of Programming by Edsger W. Dijkstra, W. H. J. Feijen, Joke Sterringa". It contains the material evoked in the citations. A delightful reading.

---
Tags: reference-request, programming-languages, education, didactics
---


# Question
Title: Show that the collection of Turing-recognizable languages is closed under homomorphism
I have seen this question here, Closure of Turing-recognizable languages under homomorphism But actually this question answers the question of "What is the relation between homomorphism and concatenation?", so I still have a problem of how to show that the collection of Turing-recognizable languages is closed under homomorphism. Could anyone help me in doing so please?

In my opinion closure under homomorphism is very similar to closure under Kleene Star, but I am convinced that I have to put marks on any number of tape cells because my language $f(L)$ may contain many strings, am I right?

Many thanks!

# Answer
> 1 votes
The proof is posted by Anwar Saiah on this post. I quote it here (with its formatting improved).

> Given a language $L$ that is Turing recognizable and a TM $M$ that recognizes it and a homomorphism $f$, we build a NTM $M'$ that recognizes $f(L)$.
>
> $M'$ looks like this:
>
> On input $w$ :
>
> * Non-deterministicly feed words from $\Sigma^∗$ to $f$ until you obtain $w$.
> * Run $M$ on $f^{−1}(w)$, if $M$ accepts accept, otherwise reject.

This works because $M'$ is a non-deterministic Turing machine. A NTM accepts $w$ if there is at least one branch accepting $w$, so if there is any word $x$ such that $f(x)=w$ and $M(x)$ accepts, this will find it and accept.

---
Tags: formal-languages, turing-machines, closure-properties
---


# Question
Title: Is the class of Turing-recognizable languages closed under Homomorphism?
Would this proof work?

Given a language $L$ that is Turing recognizable and a TM M that recognizes it and a homomorphism $f$, we build a NTM M' that recognizes $f(L)$,

M' looks like this:

On input $w$ :

-Non-deterministicly feed words from $\Sigma^{\*}$ to $f$ until you obtain w.

-run M on $f^{-1}(w)$, if M accepts accept, otherwise reject.

# Answer
> 3 votes
Your proof has a flaw.

Assume $L=\\{b\\}$, and $f(a)=f(b)=w$ for some word $w$. We have $f(L)=\\{w\\}$.

TM $M'$ on $w$ finds the preimage $a$, then checks $a\not\in L$, and rejects. This is wrong, since $w$ should be accepted.

The point is, we should not reject $w$ just because we found a preimage of $w$ which is not in $L$. We should continue checking all such preimages.

Above, doing that we would consider $b$ as well, and cause $w$ to be accepted.

# Answer
> 2 votes
The problem with your proof is where you say "until you obtain $w$". That makes it sound to me like you stop the search as soon as you find a single $x$ such that $f(x)=w$. If that is what your machine $M'$ does, then your proof is faulty, for the reasons chi explains.

Also, there is an additional step that is worth explaining: it's worth mentioning that any language that's recognizable by a NTM is also recognizable by a standard deterministic TM. This is a standard fact that probably doesn't need to be proven here.

Fortunately, there is a simple fix. Here is an improved proof:

> Given a language $L$ that is Turing recognizable and a TM $M$ that recognizes it and a homomorphism $f$, we build a NTM $M'$ that recognizes $f(L)$.
>
> $M'$ looks like this:
>
> On input $w$ :
>
> * Non-deterministicly guess a word $x \in \Sigma^\*$.
> * If $f(x)=w$ and $M$ accepts on input $x$, accept, otherwise reject.
>
> This works because $M'$ is a non-deterministic Turing machine. A NTM accepts $w$ if there is at least one branch accepting $w$, so if there is any word $x$ such that $f(x)=w$ and $M(x)$ accepts, this will find it and accept.
>
> Moreover, any language that can be recognized by a nondeterministic TM, can be recognized by a deterministic TM. It follows that $f(L)$ is Turing recognizable.

Credit: thanks to xskxzr for explaining the idea of the proof and for the improved formatting.

---
Tags: complexity-theory, computability
---


title: Fast computation of k-fibonacci numbers

text:
# Question
Title: Fast computation of k-fibonacci numbers
Let's define the sequence of $k$-Fibonacci numbers as $$ F\_i = 2^i, ~~ 0 \leq i \leq k-1 $$ $$ F\_i = F\_{i-1} + \dots + F\_{i-k}, ~~ i \geq k $$

I have a problem which requires to compute $n$-th $k$-Fibonacci number modulo $10^9 + 7$ efficiently. $n$ can be as large as $10^6$, $k$ can have any value between $1$ and $n$, time limit is $1$ second.

When $k$ is small enough i can use matrix-power approach for computing $n$-th members of linear recurrent sequences. This requires $O(k^3 \log(n)$ operations which is not feasible when $k \> 250$ since takes more than one second.

When $k$ is large but $n$ is small i can compute this exactly by definition with $O(nk)$ operations. This approach is also not feasible when $k,n \approx 10^5$ or larger.

So how can i compute them faster? I neither derived nor found on the web any useful formulas which allow to represent this recurrence with smaller depth. Thus i believe that it's more an algorithmic than combinatorial question.

# Answer
It's trivial to do in O (n), using the obvious formula $F\_{i+1} = 2F\_i - F\_{i-k}$. Just write down the definition of $F\_{i+1}$ and note that it is mostly (but not quite) the same as the definition of $F\_i$.
> 2 votes

---
Tags: time-complexity, combinatorics, recurrence-relation, efficiency
---


# Question
Title: Flaw with Cross Entropy Error in Neural Networks
I've recently been working on creating a neural network to classify handwritten digits. I implemented 1-of-N encoding such that there are the same number of output nodes as possible digits (The expected output is 0 for all digits' nodes except for the digit that was inputted, which would be 1).

Because this is a classification problem, I opted for Cross Entropy Error. I followed this model shown here: https://visualstudiomagazine.com/articles/2014/04/01/neural-network-cross-entropy-error.aspx and also shown here: http://www.mathworks.com/help/nnet/ref/crossentropy.html

The error function is:

$$-\frac1n\sum y\ln(\hat y)$$

Where $y$ is the expected output and $\hat y$ is the predicted output.

However, after I implemented my network I noticed a problem. Because this formula for cross entropy error does not account at all for the error of the predicted output for the nodes that have an expected output 0 (since the CE function multiplies all of those costs by the expected 0), the network tunes the weights/biases to always output nodes close to 1. Therefore, I end up getting a list of 1s. According to the CE cost function this is good because one of the outputs is spot on, but it doesn't even look at the other nodes' error (which is huge), so it is impossible to decide on one output.

Maybe I'm missing something? I see the alternate CE function is

$$-\frac1n\sum y\ln(\hat y) + (1-y)\ln(1-\hat y)$$

but according to the MathWorks link above, it shouldn't be used for 1-of-N encoding where there are more than $N=1$ output nodes (Not sure why this is the case).

So my question would be: Why is the first Cross Entropy Error equation viable for classification if it does not account for the error of the nodes where 0 is expected, as it always tends all the nodes to 1?

# Answer
> 2 votes
Make sure you use softmax as your final layer. This will ensure that the outputs sum to 1. You need this for cross-entropy loss to be meaningful.

Note that the correct cross-entropy loss is

$$-\frac{1}{n} \sum\_{i=0}^9 y\_i \log \hat{y}\_i,$$

where $i$ ranges over all of the classes. You omitted the dependence on the classes.

Once you change the outputs to use softmax, the anomaly you saw can't happen. The network can't cause all nodes to output 1, because softmax renormalizes the outputs so they sum to 1. This then works cleanly with cross-entropy loss, which only makes sense if the outputs are guaranteed to sum to 1 (i.e., cross-entropy loss only makes sense if we have $\sum\_i y\_i = 1$ and $\sum\_i \hat{y}\_i = 1$).

---
Tags: artificial-intelligence, neural-networks
---


# Question
Title: Is subset sum problem with multiplicities NP-complete?
To be specific, the problem is formalized as follows.

Given a set of integers $\\{a\_1,\ldots,a\_n\\}$, determine whether there exist non-negative integers $x\_1,\ldots,x\_n$ such that $a\_1x\_1+\cdots+a\_nx\_n=0$ and at least one of $x\_1,\ldots,x\_n$ is positive.

Note this is not a duplicate of this problem. In that problem, the target sum is given as input, while in our problem, the target sum is fixed to be $0$.

I tried to follow the idea of the answer to that question to come up with a new reduction, but since a basic idea of that answer is to use big elements as well as big target to prevent an element from being chosen multiple times, while in our problem the target sum is $0$, I failed.

Related question: Is the following Subset Sum variant NP-complete?

# Answer
The problem can be solved in polynomial time.

If any of the $a\_i$ are zero, then the answer is "yes" (you can set the corresponding $x\_i$ to 1, and all other $x\_j$ to 0). So let's assume all of the $a\_i$ are non-zero.

If all of the $a\_i$ are strictly positive, then the answer is "no" (if $x\_i$ is the one that's set to something non-zero, then $x\_i\>0$ and $a\_i\>0$, so $a\_1 x\_1 + \dots + a\_n x\_n \ge a\_i x\_i \> 0$). So we can assume at least one of the $a\_i$ is strictly negative.

If all of the $a\_i$ are strictly negative, then the answer is "no" (if $x\_i$ is the one that's set to something non-zero, then $x\_i\>0$ and $a\_i\<0$, so $a\_1 x\_1 + \dots + a\_n x\_n \le a\_i x\_i \< 0$). So we can assume at least one of the $a\_i$ is strictly negative.

If at least one of the $a\_i$ is strictly positive and at least one is strictly negative, say $a\_i\>0$ and $a\_j\<0$, then the answer is "yes" (you can take $x\_i=-a\_j$, $x\_j=a\_i$, and set all other $x$'s to zero; then $a\_1 x\_1 + \dots + a\_n x\_n = a\_i x\_i + a\_j x\_j = -a\_i a\_j + a\_i a\_j = 0$).

These cases cover all the possibilities: at least one of the above cases must hold. So, we obtain a polynomial-time algorithm for the original problem.

Credit: I got the key idea from Discrete lizard.
> 4 votes

# Answer
This problem lies in P.

To see this, formulate this problem it as an integer linear program (ILP):

For $x\in \mathbb{Z}^n$, maximize $\sum\_{i=1}^n x\_i$ under the constraint $\sum\_{i=1}^n a\_ix\_i = 0$ and $x\_i\geq 0$ for all $i\in \\{1,\ldots,n\\}$.

Let's have a look at the relaxed version of this ILP:

For $x\in \mathbb{R}^n$, maximize $\sum\_{i=1}^n x\_i$ under the constraint $\sum\_{i=1}^n a\_ix\_i = 0$ and $x\_i\geq 0$ for all $i\in \\{1,\ldots,n\\}$.

Observe that if $x$ is a solution of the relaxed LP, then $x\in \mathbb{Q}^n$, as $\sum\_{i=1}^n a\_ix\_i = 0$ and all $a\_i$'s are integral. Furthermore, if $x\in \mathbb{Q}^n$ is a solution, then $x'$ such that $x'\_i = c\cdot x\_i$ is also a solution for any $c\in \mathbb{Z}$. Therefore, if the relaxed LP has a (non-zero) solution, there also exists a non-zero solution to the LP in $\mathbb{Z}^n$ (take $c$ as the least common multiple of all denominators).

So, if there is a non-zero solution to the relaxed LP, our ILP has a non-zero solution and therefore there exists a solution to your input. Since we can solve LP's over $\mathbb{R}^n$ in polynomial time, we have a polynomial algorithm for this problem.

Note that, as @D.W. mentioned, solving LP's in polynomial time can be a tricky business. Fortunately, (existence of a non-zero solution for) this LP can be solved by hand, as shown in this answer. In particular, there exists such a solution if and only if at least one of the $a\_i$'s is positive and at least one is negative.
> 2 votes

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


# Question
Title: Saving information from reaching definition
I am learning about compilers at the moment and in my textbook it is briefly mentioned that UD/DU (Use-Def, Def-Use Chains) a way of saving information from the reaching definition is. It is just said that, *when a variable is used, it has a list of the reaching definitions*.

The problem that I am having is, that I am not clearly understanding the way this information is being used. How can this help the compiler optimize the code? Are there any other ways of saving (using) this information?

# Answer
> 1 votes
Here are just a few examples:

* dead-code elimination,
* instruction reordering, and
* (implementation of) scoping/shadowing.

---
Tags: compilers, data-flow-analysis
---


title: Myhill-Nerode Theorem DFA Minimization

text:
# Question
Title: Myhill-Nerode Theorem DFA Minimization
I am learning how to minimize a DFA. One helpful approach is the Myhill-Nerode Theorem, which explains:

1. Draw a table for all pairs of states (P,Q)
2. Mark all pairs where P is a final state and Q is not a final state.
3. If there are any unmarked pairs such that \[delta(P,x), delta(Q,x)\] is marked, then mark (P,Q)
4. Combine all the unmarked pairs and make them a single state in the minimized DFA.

I'm a little lost on the details of the third step.

In the example here, the unmarked pairs in the resulting table are (a,b), (c,d), (c,e), (d,e). The tutorial combines the latter three into a single state such that there are now two states (a,b) (c,d,e).

**What are the rules for combining unmarked pairs? Can you combine two pairs as long as each pair shares a letter with the other? And does the new, merged state take the union of transitions of previous state?**

For instance, if state C went to state F on 0 and state D went to state F on 1 and state E never went to state F, then the new, merged state would go to F on 0 or 1, yes?

# Answer
It's much better to understand what this *marking* means. Rather than just follow an algorithm blindly, it's preferable to understand what's going on.

Let us say that two states $q\_1,q\_2$ are *equivalent* if $\delta(q\_1,w) \in F$ iff $\delta(q\_2,w) \in F$ for any word $w$. The simplest case in which two states are *inequivalent* is when $q\_1 \in F$ but $q\_2 \notin F$ (or vice versa). When this happens, we can mark this pair of states as an inequivalent pair of states. This is what happens in Step 2.

In Step 3, we make the following observation. Suppose that $q\_1,q\_2$ are inequivalent, and that $\delta(r\_1,\sigma) = q\_1$, $\delta(r\_2,\sigma) = q\_2$. Then $r\_1,r\_2$ are also inequivalent (why?). Accordingly, if $r\_1,r\_2$ is an unmarked pair (not known to be inequivalent) and $\delta(r\_1,\sigma),\delta(r\_2,\sigma)$ (known to be inequivalent) then we can mark $r\_1,r\_2$ as inequivalent as well.

You can show inductively that at the end of Step 3, a pair of states is marked if and only if the two states are inequivalent. Therefore we can merge any pair of unmarked states, obtaining in Step 4 a minimal DFA (again, there is something to prove here).
> 3 votes

---
Tags: finite-automata
---


# Question
Title: Show that a language is decidable iff some enumerator enumerates the language in lexicographic order
The proof is given in the below:

> If $A$ is decidable, the enumerator operates by generating the strings in lexicographic order and testing each in turn for membership in $A$ using the decider. Those strings which are found to be in $A$ are printed.
>
> If $A$ is enumerable in lexicographic order, we consider two cases. If $A$ is finite, it is decidable because all finite languages are decidable. If $A$ is infinite, a decider for $A$ operates as follows. On receiving input $w$, the decider enumerates all strings in $A$ in order until some string lexicographically after $w$ appears. That must occur eventually because $A$ is infinite. If $w$ has appeared in the enumeration already then *accept*, but if it hasn't appeared yet, it never will, so *reject*.
>
> Note: Breaking into two cases is necessary to handle the possibility that the enumerator may loop without producing additional output when it is enumerating a finite language. As a result, we end up showing that the language is decidable but we do not (and cannot) algorithmically construct the decider for the language from the enumerator for the language. This subtle point is the reason for the star on the problem.

1. I could not understand the rejection case in the last line in the second paragraph. The author said "if it has not appeared yet, it never will". Why, could anyone explain it for me in a simpler way?
2. Also I could not understand the last paragraph at all, could anyone explain it to me in a simpler way?

# Answer
> 11 votes
It's easier to think of $A$ as a list of natural numbers. If $A$ is decidable, then we can list all numbers in $A$ in increasing order by just testing all of them in order – Is $0 \in A$? Is $1 \in A$? And so on.

Now let us show that if $A$ can be enumerated in increasing order, then we can decide $A$. Let us try to use the following algorithm:

> On input $n$, enumerate all integers in $A$ in increasing order until a number $m \geq n$ appears. If $n$ has appeared, then clearly $n \in A$. If $n$ has not appeared, then $n \notin A$.

To see why the last point holds, suppose that $n=5$, and the enumeration starts $2,3,6$. At the point when we see 6, we know that 5 is never going to appear.

There is one problem with this algorithm – if $A$ is a finite language, then a number $m \geq n$ might never appear. Indeed, suppose for example that $A = \\{2,3,5\\}$ and that $n=6$. We see $2,3,5$, and then wait forever for a larger number to appear. We fix this problem in the following way:

* If $A$ is finite, it is clearly decidable.
* If $A$ is infinite, then the algorithm described above always terminates (why?).

Unfortunately, given just an enumerator for $A$, we (provably) cannot know whether $A$ is infinite or not, and so we don't know which of the two cases to use. Fortunately, this does not matter for the proof. All we need to do is show that if $A$ has an enumerator, then it has a decider. There is no requirement to turn an enumerator for $A$ into a decider for $A$ in a uniform fashion.

---
Tags: computability, undecidability
---


# Question
Title: Show that the regular language is contained in another
Let L1 and L2 be two non empty regular language. How can I show that the following expression is correct with an example ? $\bigotimes$ denote the transducer cross product.

$L\_1^+ \bigotimes L\_2^+$ contains $(L\_1 \bigotimes L\_2)^+$

============================================================================

Thanks PHPNick. Would my version (rewritten from yours) be correct ? I am just trying to make it more explicit to verify my doubts. If my understanding of the cross product and the + operator is correct.

Let $L\_1$ and $L\_2$ be the following

$L\_1 = \\{u\_1,u\_2,u\_3\\} $ $L\_2 = \\{v\_1,v\_2,v\_3\\} $

Then $L\_1^+$ and $L\_2^+$ would be the set of all strings that can be made by concatenating finitely many (and at least one) strings (corrected by David Richerby)

$L\_1^+ = \\{u\_1,u\_1u\_1,u\_1u\_1u\_1,...,u\_2,...,u\_3,..., u\_1u\_2,u\_1u\_2u\_1,\dots\\} $

$L\_2^+ = \\{v\_1,v\_1v\_1,v\_1v\_1v\_1,...,v\_2,...,v\_3,..., v\_1v\_2,v\_1v\_2v\_1,\dots\\} $

The two sets defined in the question are thus

$L\_1^+ \bigotimes L\_2^+ = \\{ (u\_1,v\_1), (u\_1,v\_1v\_1), \dots, (u\_1u\_1,v\_1), \dots, (u\_1u\_1,v\_1v\_1), \dots \\}$ $(L\_1 \bigotimes L\_2)^+ = \\{ (u\_1,v\_1), (u\_1,v\_2), (u\_1,v\_3), \dots, (u\_2,v\_1), \dots \\}$

The set $L\_1^+ \bigotimes L\_2^+$ thus contains $(L\_1 \bigotimes L\_2)^+$ because we can see that $(u\_1,v\_1), (u\_1,v\_2)$ etc are present in $L\_1^+ \bigotimes L\_2^+$

# Answer
It is just a simple subset proof:

Let $(u, v) \in (L\_1 \otimes L\_2)^+$. Thus, there is a decomposition of $(u, v)$ into $(u\_1 \ldots u\_k, v\_1 \ldots v\_k)$ with $u\_i \in L\_1$ and $v\_i \in L\_2$ and $k \> 0$. Hence, we have $u \in L\_1^+, v \in L\_2^+$. So overall we have $(u, v) \in L\_1^+ \otimes L\_2^+$.
> 2 votes

---
Tags: regular-languages, regular-expressions, transducers
---


# Question
Title: Is the following Subset Sum variant NP-complete?
Is the following problem NP-hard:

**Input:** $A\subset\mathbb Z, k\in\mathbb N$
**Question:** is there a *multiset of indices* $I$, such that $|I|=k$ and $\sum\_{i\in I} a\_i=0$?

For example, on the input $A=\\{-1,2\\}, k=3$ we can take $I=\\{1,1,2\\}$ and thus we get $|I|=3$ and $a\_1+a\_1+a\_2=(-1)+(-1)+2=0$, as desired.

# Answer
It is NP-hard.

Consider the following two variants:

**Variant 1:**

**Input:** $A\subset\mathbb N$, $s\in\mathbb N$.
**Question:** is there a **set** of indices $I$, $\sum\_{i\in I} a\_i=s$?

**Variant 2:**

**Input:** $A\subset\mathbb N$, $k\in\mathbb N$, $s\in\mathbb N$.
**Question:** is there a **multiset** of indices $I$, such that $|I|=k$ and $\sum\_{i\in I} a\_i=s$?

It is easy to see variant 1 is NP-hard. It is also easy to reduce variant 2 to your variant in polynomial time by transforming each element $e$ in an instance of variant 2 to $ke-s$. So if we can prove there is a polynomial-time reduction from variant 1 to variant 2, the proof is completed.

The reduction from variant 1 to variant 2 is exactly the same as the one posted by Kristoffer Arnsfelt Hansen in this answer. I rewrite it here for consistency of symbols.

Given an instance of variant 1, assume that $a\_i \< B$ for all $i$. We will have two new elements for each old element, simulating whether the element is used 0 or 1 times. For element $a\_i$ we get two new elements $a^1\_i = (2^{n+1} + 2^i)nB + a\_i$ and $a^0\_i = (2^{n+1} + 2^i)nB$. The new target sum is defined as $s' = (n2^{n+1} + 2^n + \dots + 2^1)nB + s$. The number of elements required in a solution is set to be $n$.

Note in a valid solution of the new instance, for each $i$, the number of $a\_i^1$ and that of $a\_i^0$ must be exactly $1$ in total, so there is exactly $n$ elements in a valid solution. This is indeed a polynomial-time reduction from variant 1 to variant 2.
> 2 votes

# Answer
Assuming that the algorithm for your problem returns the yes/no answer together with the actual multi-set $I$ itself, then we can build a reduction from sub-set sum to your problem by sending your algorithm several $k$'s starting with $k=N,(|A|=N)$ down to $k=2$, where each time we check for repetitiveness to make sure we have a valid minimum sub-set sum. That would be running your algorithm $N-1$ times each time checking validity which sums up to $N(N-1)$ times your algorithm's running time. Conclusion, your problem is NP-Hard.

Note: Even if your algorithm does not return the actual sub multi-set it can be obtained by repeatedly removing one of the set's elements and checking that the sub multi-set still exists.
> 0 votes

---
Tags: complexity-theory, time-complexity, np-complete, np-hard, decision-problem
---


# Question
Title: shortest cycle passing through vertices a and b with changeable edge weights
given a weighted undirected graph with $N$ vertices $(N \leqslant 500)$ we start from vertex $S$ and wo go to $M$ and then we go to $T$ and then we return to $S$.

each edge in graph has weight $a\_i$ at the beginning but after the first time we pass any edge that edge weight will become $b\_i$. ($b\_i \leqslant a\_i$)

the task is to find the minimum sum of edges for this traverse.

time limit : 2 sec.

This is from Iran's IO, a contest that is finished. Source: https://quera.ir/course/assignments/4573/problems

# Answer
> 1 votes
This solution assumes all weights are non-negative.

> *Lemma.* There exists an optimal traverse with the following shape ($A, B,C$ may be the same vertex and may coincide with $S,M,T$), where each arrow represents a simple path, and paths represented by different arrows are edge-disjoint.

The strict proof of this lemma is somewhat tedious, so I omit it here (the idea is shown in another answer). If I have time in the future, I'll add it into this answer.

Let $d\_a(x,y), d\_{a+b}(x,y)$ respectively denote the shortest distance between vertexes $x$ and $y$ when edges have weights $a\_i$'s and when edges have weights $(a\_i+b\_i)$'s. Let $\mathrm{opt}$ denote the value of optimal solution, then by this lemma we have

$$ \begin{align\*} \mathrm{opt}\ge\ & d\_a(A, B)+d\_a(B,C)+d\_a(C,A)\\ &+d\_{a+b}(B,M)+d\_{a+b}(C,T)+d\_{a+b}(A,S). \end{align\*} $$

On the other hand, following the shortest path (with weights $a\_i$'s or $(a\_i+b\_i)$'s accordingly) from $S$ to $A$, then from $A$ to $B$, and so on, constitutes a valid traverse. Easy to see the cost of this traverse is no more than

$$ \begin{align\*} d\_a(A, B)+d\_a(B,C)+d\_a(C,A)+d\_{a+b}(B,M)+d\_{a+b}(C,T)+d\_{a+b}(A,S), \end{align\*} $$

so

$$ \begin{align\*} \mathrm{opt}\le\ & d\_a(A, B)+d\_a(B,C)+d\_a(C,A)\\ &+d\_{a+b}(B,M)+d\_{a+b}(C,T)+d\_{a+b}(A,S). \end{align\*} $$

As a result,

$$ \begin{align\*} \mathrm{opt}=\ & d\_a(A, B)+d\_a(B,C)+d\_a(C,A)\\ &+d\_{a+b}(B,M)+d\_{a+b}(C,T)+d\_{a+b}(A,S). \end{align\*} $$

So one can pre-compute the all-pair shortest paths using Floyd–Warshall algorithm, then exhaust all posible $(A,B,C)$'s to find $\mathrm{opt}$. This algorithm costs $O(N^3)$.

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: Does SAT always have short analytic proofs?
By *analytic* proof, I mean mainly resolution and also other valid syntactical manipulations of the set of clauses, old and new. So this is a search over problem space rather than solution space. The question is:

**Is there a family of instances of SAT that doesn't have polynomial-size analytic proofs of their satisfiabilities?**

If all families have short analytic proofs, then if we can find them in short time, that means P = NP. But even if there aren't always, there still may be other means to solve SAT in polynomial-time. So this is only one way to attack P vs. NP. But it's curious to know on its own.

# Answer
> 2 votes
It is known that proofs of the unsatisfiability of pigeonhole problems must be at least length $2^{n^\epsilon}$ when the resolution proof system is used. $\epsilon$ depends on the difference between the number of pigeons and the number of holes, but $\epsilon \> 0$ always.

---
Tags: satisfiability
---


# Question
Title: How to prove that $n^d$ is $O(b^n)$ from $n$ is $O(2^n)$, given that $d>0, b>1$?
I'm reading Rosen's *Discrete Mathematics and Its Application*, at Page 212, it's about the "Big-O" notation using in computer science.

This is the description in the book:

And here is my reasoning:

Since there wasn't a program with "negative" steps, I only consider the case $n\>0$.

With $n$ is $O(2^n)$, there exist two constants $C$ and $k$ such that $$n \le C \cdot 2^n, \text{when } n\>k.$$

Now take logarithms on both side we have $$\log{n} \le \log{C} + n$$

Multiply both side with $d$, we get $$d \cdot \log{n} \le d\cdot \log{C} + d \cdot n,$$

Then I stuck.

Please give me some hints about how to do next... Thanks a lot!

# Answer
> 1 votes
You cannot directly prove $f(n)^d$ is $O(b^n)$ from the fact that $f(n)$ is $O(2^n)$. For example, $2^n$ is $O(2^n)$, but $(2^n)^d$ is not necessarily $O(b^n)$.

So forget the fact that $n$ is $O(2^n)$. You should prove $n^d$ is $O(b^n)$ directly.

You may find a correct proof here.

---
Tags: asymptotics, polynomial-time
---


# Question
Title: What machine learning algorithm to use and how to implement it?
I have a virtual world with a grid filled with squares (x by y). There are entities that can do:
1. move 1 step in the four cardinal directions
2. eat food
3. fight another entity of a different type
4. mate with the same type of entity to reproduce (create one more of that type of entity)

The objective is to obtain the highest score possible. The score is calculated by:
+1 per food eaten
+1 per enemy killed
+1 per entity of that type

The inputs (neurons) are as follows:
1. position (x, y) on board
2. board size
3. types of entities in adjacent squares (including food, and null if empty)

I would like to create a program that will create hidden neurons that give rise to a sophisticated moving and attacking pattern that will allow it to obtain the highest score.

Which algorithm should I use?

# Answer
I would suggest that you try to apply reinforcement learning, maybe deep Q-learning or some other form of RL.

I don't know if those are going to be the best set of features (the best way to represent the input).
> 2 votes

---
Tags: machine-learning
---


# Question
Title: Prove: if $\delta_D(q0, w) = p$ then $\delta_N(q0, w) = {p}$
In my textbook, it presents the theorem, "A language L is accepted by some DFA if and only if l is accepted by some NFA". My textbook explains that the "if" portion of the proof is given by the subset construction and theorem if $D=(Q\_D, \sigma, \delta\_D, {q0}, F\_D)$ is the DFA constructed from NFA $N=(Q\_N, \sigma, \delta\_N, {q0}, F\_N)$ by the subset construction, then L(N) = L(D).

However, it leaves it up to the reader to prove the "only if" portion - essentitally, if $\hat\delta\_D(q,a) = p$ then $\hat\delta\_N(q,a) = {p}$. It suggests that we mu prove this by induction on $|w|$.

I understand how to complete the basis part of this inductive proof, I think.

If w is the empty string, then $$\delta\_D(q,\epsilon) = q$$ and $$\delta\_N(q,\epsilon) = {q}$$ by definition of the extended transition function.

However, I'm lost as to how to finish the proof. I've come up the starts of something, but I don't know if I'm even in the right direction:

Assume the statement is true for strings shorter than y and break y into $xa$ where $a$ is last symbol of $y$ and x is the string of symbols before a.

$\delta\_N(q\_0, y) = \bigcup\limits\_{i=1}\delta\_n(p\_i, a)$

$\delta\_D(q\_0, y) = \delta(\hat\delta(q\_), x), a)$

# Answer
For the full proof we should give the definition of the automata: $N = (Q, \Sigma, \delta\_N, q\_0, F)$ is the original NFA. We yield a DFA via subset or powerset construction: $D = (2^Q, \Sigma, \delta\_D, \\{q\_0\\}, \\{P \subseteq Q \mid F \cap P \neq \varnothing\\})$, with $\delta\_D(P, a) = \\{q \in Q \mid \exists p \in P. q \in \delta\_N(p, a)\\}$.

Now for the induction:
Base case: $\hat{\delta}\_D(\\{q\_0\\}, \varepsilon) = \\{q\_0\\}$ by definition and $\hat{\delta}\_N(\\{q\_0\\}, \varepsilon) = \\{q\_0\\}$.
Induction step: Let the statement be true for all $w \in \Sigma^n$, i.e. we land in some set $P \subseteq Q$ (which is a state in $D$). Consider some word $wa \in \Sigma^{n+1}$: $\hat{\delta}\_D(\\{q\_0\\}, wa) = \delta\_D(\hat{\delta}\_D(\\{q\_0\\}, w), a) = \delta\_D(P, a) = P^\prime$ with $P^\prime$ as given in powerset construction. By induction hypothesis we have that $\hat{\delta}\_N(\\{q\_0\\}, w) = P$ and $\hat{\delta}\_N(\\{q\_0\\}, wa) = \\{q \in Q \mid \exists p \in P. q \in \delta\_N(p, a)\\} = P^\prime$.

---

**Original answer for the other direction of the proof**

I think you are overcomplicating things here. What you want to show is that if there is a language $L$ recognized by some DFA $\mathcal{A} = (Q, \Sigma, \delta, q\_0, F)$, then there is an equivalent NFA. From your post I assume, your textbook defines NFAs with transition functions $\delta^\prime\colon Q \times \Sigma \to 2^Q$ (an other possible way would be transitions relations $\Delta \subseteq Q \times \Sigma \times Q$).

So, given DFA $\mathcal{A}$, you can just define the NFA $\mathcal{A}^\prime = (Q, \Sigma, \delta^\prime, q\_0, F)$ with $\delta^\prime(p, a) = \\{\delta(p, a)\\}$ for all $p \in Q, a \in \Sigma$, i.e. always map to the singleton with the only possible state that the DFA would reach (i.e. the transition graph is the same). It is obvious that $\mathcal{A}^\prime$ recognizes the same language as $\mathcal{A}$.

In summary, you may say that DFAs are just NFAs where the transition function maps each state and symbol to a singleton (or rephrasing for transition relations: DFAs are just NFAs where the transition relation ist total and functional).
> 1 votes

---
Tags: finite-automata, nondeterminism, check-my-answer
---


# Question
Title: Is $k$-CLIQUE W[1]-hard for parameter $n - k$?
It is well-known that the problem of deciding if a graph contains a clique of size $k$ is W\[1\]-hard with respect to parameter $k$.

Is it also known to W\[1\]-hard (or perhaps FPT) in parameter $n - k$, where $n$ is the number of vertices of the graph?

# Answer
> 4 votes
I believe this is FPT.

FInding a $(n - k)$-clique is equivalent to finding an independent set of size $n - k$ on the complement. This is equivalent to finding a vertex cover of size $k$. And the latter is FPT.

# Answer
> 0 votes
Following solution works, just replace $k$ with $n-k$, and reverse the graph so that instead of clique we need to search for an independent set.

> If the input graph $G$ contains a set $W$ of size at most $k$ for which $V(G)\setminus W$ is independent set, then it can be found in $f(k)\cdot n^{O(1)}$ time as follows:
>
> 1. Since vertices of independent set have degree at most $k$, we first remove from $G$ all vertices whose degree is more than $k$.
> 2. There are now only $k^2$ edges in the current graph.
> 3. Let $A$ be set of all vertices on which at least one edge is incident, then $V(G)\setminus A$ is an independent set of size at least $(n-2k^2)$.
> 4. So $W$ must be contained in set $A$ whose size is at most $2k^2$. We can scan over all ${2k^2}\choose{k}$ subsets of A to check removal of which set makes the graph an independent set.

---
Tags: clique, parameterized-complexity
---


# Question
Title: Applying a Chernoff bound with Only an Upper Bound of the Expectation
First, I am aware at least one or two similar questions have already been asked on stack exchange, but I've gone through the answers they got and didn't find one that was satisfactory for my case. The question itself is as follows. Suppose I have a sum $X=\sum\_{i=1}^{n}{X\_i}$ of mutually independent indicator random variables. Suppose also that I have an upper bound $\mu$ on the expected value $E\[X\]$ of $X$, but that I don't know the exact value of $E\[X\]$. Now, for some value $0 \lt \delta \le 1$, I wish to apply a chernoff bound in such a way, that I will receive the inequality $Pr\[X \ge (1+\delta)E\[X\]\] \le e^{-c \cdot \mu \cdot \delta^2}$, for some appropriate constant $c$.
In short, I want to be able to derive a useful upper bound on the probability that the value of $X$ is at least $(1+\delta)E\[X\]$, that uses the fact that $E\[X\] \le \mu$. If it held that $E\[X\] = \mu$, this would be straightforward, however in this case, there seems to be some difficulty showing this using the regular multiplicative error Chernoff bounds and standard algebraic operations. It does seem to make sense though, that this also holds in this case as well. That is, that the probability of the event $X \ge (1 + \delta)E\[X\]$ is no "worse" (no higher) than in the case where $E\[X\] = \mu$.

# Answer
> 0 votes
There's no useful bound. You need a *lower* bound on $E\[X\]$, not an upper bound.

If $E\[X\]=0$, then $\Pr\[X \ge (1+\delta) E\[X\]\] = 1$, so there is no useful upper bound on $\Pr\[X \ge (1+\delta) E\[X\]\]$ if all you know is an upper bound on $E\[X\]$. (That probability could be as large as 1, so all you can say is $\Pr\[X \ge (1+\delta) E\[X\]\] \le 1$.)

Perhaps you mean that you have a lower bound on $E\[X\]$. A standard Chernoff bound says that

$$\Pr\[X \ge (1+\delta) E\[X\]\] \le e^{-\delta^2 E\[X\]/3}.$$

Suppose now you have a lower bound $\ell$ on $E\[X\]$, i.e., $E\[X\] \ge \ell$. Then it follows that

$$\Pr\[X \ge (1+\delta) E\[X\]\] \le e^{-\delta^2 E\[X\]/3} \le e^{-\delta^2 \ell/3}.$$

This gives you an upper bound on that probability, if you know a lower bound on $E\[X\]$.

---
Tags: probability-theory, randomized-algorithms, chernoff-bounds
---


# Question
Title: How approximate sine using Taylor series
I need to approximate the sine function without internal libraries. I used Taylor series in 0 to solve this, but my program works for some values, but for others awful results. The program gets x value, unit (degrees or radians) and how many words we want use for the approximation. For values like

1 rad, 5 words results are ok: sin(1 pi) = 0.833333 Difference: 0.00813765;

sin(0.5 pi) = 0.479167 Difference: 0.000258872

But for values like 125.6 rad it returns 2.60145e+008 and C++ sin() function gives -0.0636631, so the result is completely unreal.

Also it doesn't work for values in degrees although I convert degrees on radians. E.g. sin(4.71239 pi) = 6.63667 and real result should be -1. I completely don't have any idea why it doesn't work properly, could anyone tell me what could cause these problems?

```
#include <iostream>
#include <math.h>

#ifndef M_PI
#define M_PI 3.14159265358979323846
#endif

using namespace std;

double degConverter(double);
void approximate(double, int, int);
int derivative(int);
double compareWithNorm(double, double);
double inline reductionFormula(double);

double inline degConverter(double x)
{
    return x / 180.0; //x * M_PI / 180.0    <-- the expression in comment gives wrong results in all situations?
}

void approximate(double x, int unit, int words)
{
    double result = 0;
    double xVal = 0;
    int factorial = 1;

    if (unit == 1)
    {
        xVal = x;
    }
    else if (unit == 0)
    {
        xVal = degConverter(x);
        x = xVal;
    }

    if (words > 1)
    {
        for (int i = 1; i < words; i++)
        {
            switch (i % 4)
            {
                case 1:
                    result += xVal / (double)factorial;
                break;

                case 3:
                    result -= xVal / (double)factorial;
                break;

            }
            xVal *= x;
            silnia *= i + 1;
        }
    }

    //Comparing with sin() function from math.h lib
    cout << "Difference between sin C++ and Taylor: " << compareWithNorm(x, result) << endl;
}

double compareWithNorm(double x, double result)
{
    double diff = 0;
    double pattern = sin(x);
    diff = pattern - result;
    if (diff < 0)
        diff *= -1;

    return diff;

}

double inline reductionFormula(double x)
{

    if (x > 2)
    {
        x = fmod(x, 2.0);
    }
    return x;
}

int main()
{
    double x;
    int unit = 1;
    int words = 1;

    cout << "Type x [degrees / rad]: ";
    cin >> x;
    cout << "\nType unit [deg = 0 / rad = 1]: ";
    cin >> unit;
    cout << "\nHow many words?: ";
    cin >> words;
    cout << endl;

    approximate(x, unit, words);

    return 0;
}

```

# Answer
Others have talked about argument reduction, but just as a little addendum, designing good argument reduction algorithms is an art in itself. General-purpose library functions have to be "correct" (in the sense that the answer should be within 0.5ulp of the arbitrary-precision correct answer) on the entire range of floating-point numbers, and so will use a lot of special cases for efficiency and accuracy.

For example, one common technique is to let the floating point addition operation round for you. In C:

```
/* 1/2pi */

const double one_over_period = 1.591549430918953456e-1;

/* This is n = round(x / 2pi). */

const double round_to_integer = 1.5 / DBL_EPSILON;
double n = (x * one_over_period + round_to_integer) - round_to_integer;

/* This is x = x - n * 2*pi, using Cody-Waite reduction.
   Don't worry, this will be explained in a moment. The
   important part for now is that period_1 + period_2 is
   an approximation to 2pi. */

const double period1 = 6.28318524360656738280e+0;
const double period2 = 6.35730190941127867664e-8;
x = x - n * period1 - n * period2;

```

The argument reduction algorithm works for quite large `abs(x)`; calculating `sin(1e8)` is no problem. That may be good enough for you, but not for your programming language's standard library, which has to give a 0.5ulp-correct answer for `sin(1e22)`. So in a general-purpose implementation, you'd check the range of the argument and use different argument-reduction code as appropriate.

Now let's talk about that Cody-Waite method.

You want to compute $x - nK$ where $n = \left\lfloor \frac{x}{K}\right \rfloor$. We'll ignore how you get $n$; that's the code above. What we're interested in is computing $x - nK$.

The constant $K$ is known to arbitrary precision, but of course you want to compute this using only floating-point arithmetic, and you want the result to be accurate (within 0.5ulp of the true answer).

The problem with doing this the obvious way is that when $x$ is close to a multiple of $K$, doing the obvious subtraction can cause catastrophic cancellation, since you are subtracting two almost-equal numbers.

The solution is to find two constants, $C\_1$ and $C\_2$, with the following properties:

1. $C\_1$ is very close to $K$.
2. $C\_1$ is representable using only a few significant digits.
3. $C\_1 + C\_2 \approx K$, to far enough beyond the working precision of the floating point representation.

Then calculate $(x - n C\_1) - n C\_2$.

Property 2 means that $n C\_1$ is exactly representable for a large range of integers $n$. In the case above, the first number `period_1` is $\mathrm{1.921FB50000000\_{16}\times 2^{2}}$. All those zeroes at the end of the mantissa mean that you can multiply this by a very large integer indeed and still get a number that is represented exactly in floating point.

(You will note that the terms "a few significant digits" in property 2 and "far enough" in property 3 are vague. We can make these precise, but this is just to give you the idea. Using roughly half the mantissa bits to represent $C\_1$ is a good rule of thumb, but it's not a formal proof.)

The way that argument reduction is typically done for larger ranges (e.g. `sin(1e22)`) is essentially the same as this, only splitting $K$ into more constants. A *lot* more constants.
> 4 votes

# Answer
You use *argument reduction*. You know that sin (2kπ + x) = sin (x), so given an argument y, you calculate k = round (y / 2π), y' = y - 2kπ, and sin (y) = sin (y'), with y between -π and π.

You can also use sin (π + x) = - sin (x), sin (π/2 + x) = cos (x) to reduce the argument to sin (y') or cos (y') with -π/4 ≤ x ≤ π/4.

The reason why your Taylor series gives absurd results for large x is that you are adding and subtracting huge terms. Mathematically the series converges just fine, but if you have terms \> $10^{20}$, these terms will have rounding errors so large that you cannot expect a good result. Reducing the argument to -π/4 ≤ x ≤ π/4 means you have much smaller terms. (Also see Pseudonym's answer how to get the argument reduction as precise as possible).

You are adding the terms of the Taylor series from the largest. Each addition has a rounding error, proportional in size to the result of the addition. So adding in this order each addition gives a large error. It is better to start with the smallest term. The two smallest terms are tiny, adding them gives a tiny rounding error.

And usually we don't actually use the Taylor series. The Taylor series has its largest error at the end of the range. You would use Chebyshev polynomials, which minimise the largest error over the whole interval. And since you don't want any errors at x = 0, you can write sin(x) = x - x * g(x) and minimise the relative error of g(x).
> 3 votes

# Answer
The Maclaurin series for $\sin x$ (i.e., the Taylor series centred at $x=0$) does converge for all $x$. However, the speed at which it converges depends on the value of $x$ you use. Looking at it from the other side, the Maclaurin series for $\sin x$ truncated at the term in $x^k$ is a polynomial, so it goes to $+\infty$ or $-\infty$ as $x\to\infty$, whereas $\sin x$ remains in the interval $\[-1,1\]$. So, if you use a fixed truncation of the series as your approximation, the error will grow without bound as $x$ becomes large.

In more detail, because $\sin x$ is infinitely differentiable and the $k$th derivative is bounded between $+1$ and $-1$, the absolute error from truncating the series at the $x^k$ term is at most $x^{k+1}/(k+1)!$. So, if you want to approximate $\sin x$ for large $x$ you need to either take $k$ large enough for the error to be small or, more sensibly, use the fact that the sine function is periodic, so you only need to consider $-\pi\<x\leq \pi$. In that case, you're guaranteed that the absolute error is at most $\pi^{16}/16!\approx4\times10^{-6}$ after the $x^{15}$ term (actually, $\pi^{17}/17!$, since the series to $x^{16}$ is the same). And, using the trigonometric identies pointed out by gnasher729, you can use even smaller ranges of $x$ and get even better error bounds from fewer terms.
> 3 votes

---
Tags: algorithms, approximation, numerical-algorithms
---


title: Face recognition on on tilted images

text:
# Question
Title: Face recognition on on tilted images
From what I learned, viola jones needs images with faces upfront. Tilting the head a few degrees to each side can botch the algorithm. Is it possible to take an image, take a several rotated copies of it and run the algorithm on each one?

This limitation sounds like only a minor neusense to me. Is there a stronger reason for the limitation?

# Answer
Tilting your head a few degrees to the side doesn't cause Viola-Jones face detectors to fail. They are more robust than that. I suggest trying some experiments to see for yourself.

---

As an aside: It's not always possible to rotate an image to the extent one might like. You have a 2D representation of a 3D object. As an extreme case, imagine trying to take a photograph and simulate rotating the face by 180 degrees around the vertical axis. You can't, because that would require knowing what the back of their head looks like. Even tilting around a horizontal axis has limits; imagine trying to tilt by 180 degrees -- which would require simulating the effect of your hair pointing in a different direction. So while it may be possible to simulate rotation to a limited extent, but there are limits to what kind of synthetic rotation is possible.
> 1 votes

---
Tags: image-processing, facial-recognition
---


# Question
Title: Dijkstra's algorithm: why are distances initialized to infinity and not some negative number?
I'm a high schooler who has been self-learning graph algorithms for a month or two now.

I was wondering why the distance array in Dijkstra's algorithm is initialized to infinity (INT\_MAX in C++) when it could just be set to a negative number? Since Dijkstra's isn't even used for negative numbers, why isn't the distance array set to some arbitrary negative number (say, -1) and instead a very large number which takes up far more space? It's possible that I'm overestimating the space occupied in memory by a very large INT value.

I'd appreciate any constructive feedback.

# Answer
If you read the algorithm closely, you'll not that edge weight relaxation is triggered if `new_weight < old_weight`. This comparison is naturally true if all undiscovered edges are initialized with infinity (or, in programming, the largest representable value), and the algorithm correctly picks up the first "real" value it finds.

If you used a negative value, you'd have to treat it as a special case which is a lot less nice.

Note that in classic algorithms, we often disregard the size of the stored numbers (RAM model, uniform cost model). If that is not a good model for your application you have to describe more closely how you represent numbers, and in particular infinity. In practice, you can represent infinity either by a special value that is larger than any number (that's the C++ constant you mention), or you just use the maximum weight you see in the input graph plus one.
> 4 votes

---
Tags: algorithms, graphs
---


# Question
Title: Inference rules for deriving invariants in Hoare logic
The following algorithm is supposed to compare two strings $S\_1$ and $S\_2$ ("/\\" for empty string):

```
X = S1
Y = S2

E = true
// (1) S1 = S2 <=> X = Y and E = true
while X != /\ and Y != /\ and E == true
  if head(X) == head(Y)
    X = tail(X)
    Y = tail(Y)
  else
    E = false
// (2) S1 = S2 <=> X = /\ and Y = /\ and E = true
if !(X == /\ and Y == /\)
  E = false
  // (3) S1 != S2 and E = false
else // an empty else; just for inserting an assertion (i.e., 3' below) here
  // (3') S1 = S2 <=> E = true
// (4) S1 = S2 <=> E = true
return E

```

There are five invariants:

(1). $S\_1 = S\_2 \iff X = Y \land E = true$

(2). $S\_1 = S\_2 \iff X = \Lambda \land Y = \Lambda \land E = true$

(3). $S\_1 \neq S\_2 \land E = false$

(3'). $S\_1 = S\_2 \iff E = true$

(4). $S\_1 = S\_2 \iff E = true$

I can understand these invariants and how they are derived from the previous ones in an intuitive and thus informal way. For example, we can derive (3') from (2) as follows:

> At point (2), we know that $S\_1$ equals $S\_2$ iff $X = \Lambda \land Y = \Lambda \land E = true$. At point (3'), we further know that $X = \Lambda \land Y = \Lambda$. Thus, at this point, we only need to check whether $E = true$ to decide whether $S\_1 = S\_2$ holds.

However, the reasoning above cannot be justified by the conventional inference rules of propositional logic by which we would have

$$S\_1 = S\_2 \iff (X = \Lambda \land Y = \Lambda \land E = true) \land (X = \Lambda \land Y = \Lambda),$$ which is $S\_1 = S\_2 \iff X = \Lambda \land Y = \Lambda \land E = true.$

---

**Problem:** What are the inference rules for the derivation from (2) to (3')?

Related Post: Developing invariants for comparing two strings

---

**Edit:** As pointed out by @chi in the comment, it should be $$\big(S\_1 = S\_2 \iff (X = \Lambda \land Y = \Lambda \land E = true)\big) \land (X = \Lambda \land Y = \Lambda),$$ which implies (3') $S\_1 = S\_2 \iff E = true$ as the answer given by @kne shows.

# Answer
There are two ways to answer the question.

The first is on the level of propositional logic. You have three statements, $S\_1=S\_2$, $(X=\Lambda\wedge Y=\Lambda)$, and $E=true$. Let's call them $A$, $B$, and $C$ for short. (2) is $A\Leftrightarrow(B\wedge C)$ and (3') is $A\Leftrightarrow C$. At point (3') we know $B$. Every assignment of the propositional variables that satisfies $B$ and (2) also satisfies (3'). In other words, at the position (3') we know

$(A\Leftrightarrow(B\wedge C))\wedge B$

from which

$(A\Leftrightarrow C)$

follows semantically. If the propositional proof system of your choice is complete, the above can also be derived using its rules.

The second answer addresses Hoare logic instead of propositional logic. Hoare logic has its own derivations. The neat thing is that most of them can be automated. And they work backwards. In the case at hand, (3') is derived from (4) by copy. After all, at the end of the `else` clause, the same invariant must hold as after the `if-then-else`. The `then` clause does not follow that rule, so let us fix the code

```
// (2) S1 = S2 <=> X = /\ and Y = /\ and E = true
// (2') (!(X == /\ and Y == /\) and (S1 = S2 <=> false = true)) or
//    ((X == /\ and Y == /\) and (S1 = S2 <=> E = true))
if !(X == /\ and Y == /\)
  // (3'') S1 = S2 <=> false = true
  E = false
  // (3) S1 = S2 <=> E = true
else // an empty else
  // (3') S1 = S2 <=> E = true
// (4) S1 = S2 <=> E = true

```

Now (3) is derived from (4) by copy, (3'') is derived from (3) by substitution (that is the Hoare logic rule for assignment) and (2') is derived from (3''), (3') and the `if` condition. It remains to see how (2') follows from (2). That is propositional logic plus $false\not=true$.
> 2 votes

---
Tags: logic, propositional-logic, loop-invariants, hoare-logic
---


# Question
Title: What is the best algorithm for multiple matches?
What is an algorithm that can find the best possible matches given a set of data. I have read up on stable roommates problem and or stable marriage problems. However, from my understanding, these type of algorithms only output a specific match (pairings) and not a set of possible matches. For example, say we have a group of users each with a desire to trade one particular fruit for another.

\[\] - Has/Have
() - Wants

```
User 1:
[Apples, Bananas]
(Grapes)

User 2:
[Bananas, Grapes, Peaches]
(Apples)

User 3:
[Grapes, Oranges]
(Bananas)

User 4:
[Mango, Pineapple]
(Strawberry)

User 5:
[Raspberry]
(Pineapple)

User 6:
[Pineapple]
(Raspberry)

```

In this scenario, matches should be (-\>)

```
     User 1 -> (User 2 and User 3)
     User 2 -> (User 1)
     User 3 -> (User 1)
     User 4 -> None
     User 5 -> (User 6)
     User 6 -> (User 5)

```

Irving's algorithm requires that a solution have a unique pairing. What is an algorithm that could give me a solution set like above?

# Answer
Use an algorithm for bipartite matching.

Build a graph with one left-vertex per (user, fruit that user has) pair. For instance, in the example above, we'd have one vertex for (User 1, Apples) and another vertex for (User 1, Bananas). Add one-right vertex per user. Draw an edge from (user $i$, $f$) to user $j$ if user $i$ has fruit $f$ and user $j$ wants fruit $f$.

Now find a maximum matching in this bipartite graph. The set of edges in that matching will be exactly what you want.

This does allow one user to be matched to multiple other users: for instance, the vertex (User 1, Apples) might be matched to the vertex User 2, and the vertex (User 1, Bananas) might be matched to the vertex User 3.
> 1 votes

---
Tags: algorithms
---


# Question
Title: What is the big-$\Omega$ complexity of Fermat's Little Theorem?
Fermat's Little Theorem states that if an integer $n$ is prime them $$ a^n \equiv a \pmod n \hspace{10mm} (\*) $$ for any $a \in \mathbb{N}$

My question is, is it correct to say that testing $(\*)$ for some given $a$ has complexity $\Omega (n)$, since we would have to calculate $a^n$ which would require $n$ (multiplication) operations?

Additionally, what is the big-O complexity of testing this congruence?

# Answer
Modular exponents can be computed efficiently using *repeated squaring*. This is a recursive method (which can also be implemented iteratively) that relies on the following two identities: $$ a^{2k} = (a^k)^2, \qquad a^{2k+1} = a(a^k)^2. $$ This allows us to give a recurrence for $f(a,b,n) = a^b \bmod n$: $$ f(a,b,n) = \begin{cases} 1 & \text{if } b = 0, \\ f(a,b/2,n)^2 \bmod n & \text{if $b$ is even}, \\ af(a,(b-1)/2,n)^2 \bmod n & \text{if $b$ is odd}. \end{cases} $$ This shows that $a^b \bmod n$ can be computed using $O(\log b)$ many multiplications. Since we keep reducing modulo $n$ in each step, each of these multiplications takes time polynomial in $O(\log n)$ (naively, $O(\log^2 n)$, but this can be significantly improved using fast integer multiplication methods). In total, we obtain an algorithm running in polynomial time.
> 2 votes

# Answer
Here is a list on wikipedia on the computational complexity of different operations, one of which happens to be modular exponentiation which you are asking about. https://en.wikipedia.org/wiki/Computational\_complexity\_of\_mathematical\_operations

The complexity with exponentation by squaring is

```
#n = number of digits of n (= O(log(n)))
M(#n) = complexity of multiplication of two #n-digit numbers

=> O(M(#n)#n)

```

And `M(#n) ~ O(#n^2)` (for more information see wikipedia)

So putting together we get

```
O(M(#n)#n) = O(#n^3) = O(log^3(n))

```

However this is only true using that specific algorithm "exponentation by squaring".
> 1 votes

# Answer
> \[I\]s it correct to say that testing $(\*)$ for some given $a$ has complexity $\Omega (n)$, since we would have to calculate $a^n$ which would require $n$ (multiplication) operations?

No. An algorithm provides an *upper* bound on the complexity of a problem. By exhibiting an algorithm that runs in time $f$, you're saying that the complexity of the problem can't possibly be worse than the running time of $f$. But there might be a better algorithm, so the complexity might be better than the running time of $f$. In other words, by demonstrating an algorithm with running time $f$, you've proven that the complexity of the problem is $O(f)$. To prove that the complexity is $\Omega(f)$, you would need to prove that no possible algorithm has running time $o(f)$.

Always be wary of the argument "This obvious algorithm has running time $f$, so the complexity can't be any better than that, right?" The whole point of studying algorithms is to come up smart techniques to solve problems faster than the obvious way.
> 1 votes

# Answer
Who says calculating $a^n$ takes n multiplications? It is easily done in 2 log n multiplications or less. Each multiplication modulo n can be done in O (log n)^2 easily, and faster with some hard work.
> 0 votes

---
Tags: complexity-theory, primes, modular-arithmetic
---


title: Worst case time complexity of heap sort

text:
# Question
Title: Worst case time complexity of heap sort
I was learning about heaps, and came to know that the worst case time complexity of heap sort is Ω(n lg n). I am having a hard time grasping this. My reasoning is as follows:

```
1. Build a max-heap out of the unsorted array, say A. (O(n))
2. Exchange root of the heap (max element in the heap) with the last
   element of the heap.
3. Decrement the heap size by 1.
4. Run MAX-HEAPIFY on A(1).
5. Keep repeating steps 2-4 until all elements have been sorted.

```

The step 3 takes time O(lg m), where m is the current size of the shrinking heap being max-heapified (m ranges from (A.length - 1) to 2). So the total time taken max-heapifying would be Σlg(n - j) where the summation runs from j = 1 to j = n-2. So the total time taken would be lg((n-1)!). We know that lg((n-1)!) \< nlgn. So how can nlgn be the lower bound? (It should be lg((n-1)!) as per the above). Its ok if we are talking about the upper bound since nlgn is greater always, and we can say that heap sort in worst case takes O(n lg n).

I understand that the algorithm can have worst-case running time that is both O(nlgn) and Ω(nlgn); the former specifying an upper bound, and the latter the lower bound. What I understand is that the if runtime is Ω(nlgn), it means that the algorithm will take time of the order of nlgn lower bound. My question is different. The time taken in case of heap sort should Σlg(n - j), summing all the run times of max-heapify instances, which comes out to be lg((n-1)!. So heapsort in the worst case should have a run time of Ω(lg((n-1)!) instead of Ω(nlgn) ; also lg((n-1)!) \< nlgn (since nlgn = lg (n raised to n)) Please correct me if wrong.

# Answer
> 3 votes
An algorithm can have worst-case running time that is both $O(n \lg n)$ and $\Omega(n \lg n)$; those don't contradict each other. See How does one know which notation of time complexity analysis to use? and https://cs.stackexchange.com/a/201/755 for some background that might help understand why that is so.

# Answer
> 2 votes
Note

$$\log (n-1)!\ge \log \frac{n-1}{2}+\cdots+\log (n-1)\ge\frac{n-1}{2}\log \frac{n-1}{2}=\Theta(n\log n).$$

---
Tags: data-structures, heaps, heap-sort
---


# Question
Title: data structure admitting top items with prefix
A trie can answer a query for all items with a certain prefix in $O(m + \log n)$ time, where $m$ is the number of matches and $n$ is the number of items. A trie also supports $O(\log n)$ insertion and deletion and takes $O(n)$ space.

Now suppose each item has a score. I am looking for a data structure that can answer a related query: give me the top $m$ items by score with a certain prefix. Ideally search, insertion, and deletion would have the same time as a trie, up to a constant factor, and space would be $O(n)$ as well. To this end we may assume items are short (of length $O(\log n)$).

This problem can be solved with $O(\log^2 n)$ insertion and deletion and $O(n \log n)$ space by forming a trie where every node contains a sorted set of items with that prefix sorted by score. But this approach uses excess time and space compared to a trie. Can we do better?

# Answer
> 1 votes
You can achieve $O(\log n)$ time insert, $O(\log n)$ time delete, $O(n)$ space, and $O(m \log m + \log n)$ time search by augmenting the trie.

Store in each leaf the weight of the corresponding item. Also, at each internal node, add a field with a pointer to the leaf of maximum weight that's reachable from that node.

It's easy to see how to perform insertion in $O(\log n)$ time, and it's easy to see why this still uses only $O(n)$ space.

Search for the top $m$ items with a certain prefix can be done in $O(m \log m + \log n)$ time. First, find the node $x$ corresponding to that prefix. Use that node to identify the first item of the output (the highest-weight item with that prefix). Next, look at the children $y\_1,\dots,y\_k$ of node $x$, and for each, look at the highest-weight item with that prefix. Add these $k$ nodes to a priority queue, keyed on the weight of the corresponding item. Extract the highest-weight item from the queue; that's the second item of the output. Look at the children of the node you just extracted, and add them to the queue. Repeat until you have output $m$ items; in each iteration, you extract the node of highest weight from the priority queue, output the corresponding item, and add the children of that node to the priority queue. Remove duplicates as you go. Stop once you've output $m$ items. You do $O(\log n)$ time to find the first node corresponding to the prefix, and then each subsequent iteration takes $O(\log m)$ time (since operations on a priority queue of size $O(m)$ can be done in $O(\log m)$ time), and you do $m$ iterations, for a total running time of $O(\log n + m \log m)$.

Deletion can be done in $O(\log n)$ time. To delete an item, traverse the trie to find that item. Then, update each node that you visited during that traversal. To update a node $x$, if the maximum-weight leaf under $x$ is the the item you're deleting, check the children of $x$ to find the next-highest-weight leaf under $x$, and update $x$. This does $O(1)$ work per node you traverse, and the traversal visits $O(\log n)$ nodes, so the total time for deletion is $O(\log n)$ time.

---
Tags: data-structures, search-algorithms, search-trees
---


# Question
Title: Is there a way to find a simple regular expression for this language?
Let $\Sigma$ be 0,1,2. I am interested in the language of all strings $w$ such that the sum of $w$ characters (where the char 0 is treated as the number 0, the char 1 as the number 1 etc) is divideable by 5. Obviously this is a regular language, and I can also find a simple linear grammer.

My idea for a regular expression was to check all the combinations where I can receive sum zero (in modulo 5) with the digits 1 and 2 and put 0\* in between. But is there no better way? Something more elegant?

Edit: My expression is $0^\* 1 0^\* 1 0^\* 1 0^\* 1 0^\* 1 0^\* \cup 0^\* 1 0^\* 1 0^\* 1 0^\* 2 0^\* \cup 0^\* 1 0^\* 1 0^\* 2 0^\* 1 0^\* \cup 0^\* 1 0^\* 2 0^\* 1 0^\* 1 0^\* \cup \ldots $ and so it goes on for all the possible combination. My question is if there is a way to simplify this - Or maybe a different approach?

# Answer
> 1 votes
Forget about the $0$, they are boring. Like you said, you can add $0^\*$ basically everywhere and you are done.

Now for the $1,2$. Just try to order them in batches that total 5. Then you realised that this might be problematic in case at the count of 4 we read $2$ and overshoot by one. No problem, we remember this, and continue until we reach a proper multiple of five. Note however, that the overshoot just might repeat when we have $212$, or similar.

So here is how the regular expression is constructed: any multiple of five, or when we reach an overshoot, wait until we are back. Repeat.

First some abbreviations:

$E\_5= \\{11111,1112,1121,1211,2111,221,212,122\\}$.

$E\_4 = \\{1111,112,121,211,22 \\}$.

$E\_{\mathrm{shoot}}= \\{1112,212,122\\}$.

Finally here is your expression:

$\Big ( E\_5 \cup E\_4\cdot 2 \cdot (E\_{\mathrm{shoot}})^\*\cdot E\_4\Big )^\* $.

Ah. Add $0^\*$, lots of them.

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


# Question
Title: How can I determine an algorithm from a table of numbers?
I need help with figuring out an algorithm from a generated numbers in a table. I was half way solving this question and I have already got the sequence for N=6, but I'm still stuck at writing the actual algorithm

# Answer
> 1 votes
On input $n$, output $$ 0^2 - n^2, 1^2 - n^2, 2^2 - n^2, \ldots, (3n-1)^2 - n^2. $$ In pseudocode:

> For integer $k$ from $0$ to $3n-1$, print $k^2-n^2$.

---
Tags: algorithms
---


# Question
Title: Time complexity of computing binomial coefficients (with binary representation of integers)
Given two integers $n$ and $k$, I want to compute the exact value of the binomial coefficient ${n \choose k}$.

Here $n$ and $k$ are given in their binary representation, meaning that the size of the input is about $\log n + \log k$.

How fast, in big-O notation, can we compute ${n \choose k}$?

One can compute this in time $O(k)$ using, say, the multiplicative formula (see here). But in the worst case, this is exponential in the size of the input.

Can ${n \choose k}$ be computed faster?

# Answer
> 4 votes
There is no sub-exponential algorithm. For example, $\binom{2n}{n}$ has $\log\binom{2n}{n}$ bits, and according to Stirling's approximation,

$$ \binom{2n}{n}=\Theta\left(\frac{2\sqrt{\pi n}\left(\frac{2n}{\mathrm{e}}\right)^{2n}}{\left(\sqrt{2\pi n}\left(\frac{n}{\mathrm{e}}\right)^{n}\right)^2}\right)=\Theta\left(\frac{4^n}{\sqrt{n}}\right), $$

we have

$$ \begin{align\*} \log\binom{2n}{n}=\Omega(n). \end{align\*} $$

So we need at least $\Omega(n)$ time to output the result of $\binom{2n}{n}$.

---
Tags: algorithms, time-complexity
---


# Question
Title: What's the directory structure on disk that keeps the information of all files?
I'm reading Operating System Concepts by Avi Silberschatz(9thE), in chapter 11 *File-System Interface*, when the author explains the concepts of file, he states that

> The information about all files is kept in the directory structure, which also resides on secondary storage. Typically, a directory entry consists of the file’s name and its unique identifier.

I think the directory structure that holds the information of all files is of critical importance， which the author does not extend in depth though. I don't even know the terminology for this concept of directory structure. It should be somewhere on the disk and well maintained. Could anyone clarify it for me? Any literature and links will be appreciated.

Thanks in advance!

# Answer
Your intuition is mostly correct. I believe the description is not really sufficient. Directory entry should at least be able to allow the OS to be able to locate some parts the file on disk for I/O operations. File System is divided into some fixed size partitions of available space ranging from 1-16KB. For efficient implementations a file is not necessarily written in contiguous blocks therefore the challenge is mostly having an efficient way of determining which blocks belong to which file without giving up on too much space and being efficient at the same time. Similarly other meta information should also be kept such as user permissions, hard links and so forth.

Currently Unix inode system is an efficient implementation. An other example would be maintaining a FAT (File Allocation Table) which is less efficient. I believe reading about Inodes would be great place to start.
> 3 votes

---
Tags: operating-systems, filesystems
---


# Question
Title: What's the error-correcting capacity (randomly errors, or burst errors) of polar code?
Polar codes, invented by Arikan, with low encoding and decoding complexity. But the minimum distance of polar codes is not great. The normalized minimum distance goes to 0 with the block size. Yet, the existing decoding algorithms for polar codes can asymptotically achieve channel capacity.

Generally, a code with minimum distance $d$ can correct $\frac{d-1}{2}$ errors (random errors). And Polar code is also error-correcting code, I was wondering how many errors can it correct( e.g. A $\[2048, 614\]$ with $BEC(0.19)$ polar code.)? Much appreciated.

# Answer
> 1 votes
I am not an expert but I think you may be asking the wrong question. Polar codes don't have a meaningful "error correction capability" obtainable as in algebraic codes by (d-1)/2. Alternatively, this is not the meaningful parameter of significance.

For finite lengths their performance is usually analyzed in BEC (Binary Erasure Channel) and AWGN channels (Additive White Gaussian Noise). The well-cited paper *On Finite-Length Performance of Polar Codes: Stopping Sets, Error Floor, and Concatenated Design* by A. Eslami and H. Pishro-Niki on arxiv here as well as some more recent papers confirm this.

---
Tags: coding-theory, error-correcting-codes
---


# Question
Title: Count points on same distance from set of points
Let's consider finite grid of points with size of $N$ by $M$ and set of $x$ points ($x$ is small number, up to 10, $N$ and $M$ are big numbers, up to 30000 )). Each of the $x$ points is described with 2 values $(x\_i, y\_i)$. We want to count the size of set $y$ such that $y$ includes all the points in the grid that are on equal distance from all of the $x$ points.

By distance I mean Manhattan distance.

# Answer
Hint: First solve the problem for the case where x=2. Try working through a few examples: draw a picture of the grid, work out the solution (plot the points that are at equal distance from both input points), see what pattern you can spot, and use that to find a solution for the case where x=2. I think you'll discover something fascinating.

Once you can solve it for x=2, you are almost done! Think about how you might expand that to x=3.
> 0 votes

---
Tags: search-algorithms, sets, counting
---


# Question
Title: Formalism for unambiguous context-sensitive languages?
I know that there are some languages that are unambiguous but not context-free (this is a good fact). Is there any kind of formalism for describing unambiguous context-sensitive languages? Even better yet, is there a parsing algorithm for unambiguous context-sensitive languages?

# Answer
> 2 votes
Actually, I found something close enough to what I want. They're unambiguous boolean grammars and they're both unambiguous and strictly more powerful than context-free grammars. Other people may find this useful, so I decided to share it.

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


# Question
Title: Soft question: program result verification
Let's say there's a cloud computing service that allows people to run arbitrary programs and get the results. The idea being that your machine is too slow, and you don't want to overwhelm it. If your program is something like "factorize 15672965357291016", then it's a perfect candidate for this service, because you can very quickly verify that a result handed back to you is correct. But if your program is long and complicated, and you can't think of a quick way to verify that a given input/output pair is correct, then you're stuck with running the program on your own machine to verify the results, which defeats the purpose.

One solution would be to use the blockchain and have a lot of people verify that some given input/output pair is correct--then you only accept the result as true when whatever block it's on has enough confirmations. The problem with this is that it could really slow down the network if your program is resource-intensive.

What would be nice to have is a programming language where a given program `P`, an input to it `I`, and a supposed output `O`, can be verified quickly (i.e. `P(I) == O`). That way, making confirmations would be fast, and the whole network would speed up.

I don't think this can be done in general because you could use it to solve the halting problem. If you have some function `V(P, I, O)`, which verifies that `P(I) == O`, then running `V(P, I, halts)` would check that `P` halts on input `I`.

However, the fact that `V` does exist for every problem in `NP` makes me think that there has got to be some middleground, where you could make a really restricted language for which `V` always exists, and it can easily be determined from the structure of `P` (a trivial implementation is just `V(P, I, O) = P(I) == O`). I'm not really sure what my question is, but is this an existing problem? What search terms should I use to learn more about this?

# Answer
> 1 votes
I found out that this is called Verifiable computing:

> Verifiable computing (or verified computation or verified computing) is enabling a computer to offload the computation of some function, to other perhaps untrusted clients, while maintaining verifiable results.

---
Tags: distributed-systems
---


# Question
Title: Logistic model and Linear regression model
I am reading the book "An introduction to statistical learning with applications in R". I am reading Logistic Regression and I don't understand why when it's compared to linear regression model, the author said that "the problem with this approach: for balances close to zero we predict a negative probability of default; if we were to predict for very large balances, we would get values bigger than 1." as in the highlight. Could anyone please explain me how the probability can be smaller than 0 or larger than 1?

Your help is really appreciated!

Thank you

# Answer
> 1 votes
You should just keep reading:

> These predictions are not sensible, since of course the true probability of default, regardless of credit card balance, must fall between 0 and 1.

A probability cannot be smaller than 0 or larger than 1. The problem is that the model might predict such a "probability".

---
Tags: algorithms
---