# Question
Title: How to generate graphs with a Hamiltonian path?
I need to create a graph generator for my next project. Generally algorithms are trying to find a Hamiltonian path in a graph. So I can create a graph generator, generate a graph, and then I can decide whether the graph has a Hamiltonian path or not. If not, I can regenerate the graph but this is not a cool way.

I want my generated graphs that always have a Hamiltonian path. My graph has two additional conditions:

* Vertices can only have 2, 3, or 4 edges.
* Possible number of vertices follow the sequence 6, 10, 15, 20, 25...n-5,n where n % 5 = 0.

How should I start, and how do I achieve this easily?

# Answer
The simplest solution is the one suggested by Yuval Filmus. That is, take a simple path on $n$ vertices, and finish the construction after you have added some number of edges. Clearly, it is easy to enforce the maximum degree condition as well.

Alternatively, you could generate graphs whose structure guarantees the existence of a Hamiltonian path. For example, as shown by Tutte, every 4-connected planar graph has a Hamiltonian path (see e.g., Wikipedia for the statement). Then, a high-performance tool for generating planar graphs is plantri. My feeling is that this is unnecessarily complicated for your use case, but it gives you a possible another approach you might be interested in later on.
> 6 votes

# Answer
The solution suggested by Juho applies to any problem where you can generate an object that trivially has the property you're interested in and then modify it in a way that maintains that property:

* For the problem in the question, start with a path and randomly add edges obeying the degree conditions.
* To generate a graph with a $k$-clique, start with a $k$-clique, then add the rest of the vertices, then add edges at random.
* To generate $k$-colourable graphs, start with no edges, randomly choose the colour of each vertex and then randomly add edges between different coloured vertices.
* To generate satisfiable 3CNF formulas, start by picking a truth assignment for the variables and then add random clauses that have at least one true literal.
* To generate unsatisfiable 3CNF formulas, start with something simple and unsatisfiable and add random clauses to it.

If you don't care about the distribution of the instances you generate, these methods work fine. If you do care about the distribution, things get trickier. If you want a uniform or near-uniform distribution (i.e., each Hamiltonian graph on $5n$ vertices is generated with \[roughly\] equal probability), you should look into Fully Polynomial Almost Uniform Samplers (FPAUS). These typically use Markov chain Monte Carlo and the method for your problem would probably be to start with a path and then randomly add and remove the extra edges enough times that the process converges to the right distribution (you'd have to check this actuall works).

Another thing to be aware of is that instances generated in this way might be easy to solve if you knowsomething about how they were generated. For example, in the clique example I gave, if you just add each the non-clique edge independently with probability $p$ for some $p$, it's very likely that your clique is just the $k$ vertices of highest degree.
> 4 votes

# Answer
How about:

1. Start with a fully connected graph.
2. Choose a random permutation of the list of all nodes - this will be our guaranteed Hamiltonian cycle.
3. Delete an edge from the graph at random, as long as it is not
    * in our protected HC path
    * going to leave any vertex with too few edges.
4. Repeat step 3 until all your vertices have a degree in your required range.

To implement steps 3 and 4 above, you could shuffle the non-HC edges into a queue; then you pop edges off in turn and decide whether to drop or keep. You'd also better keep track of the number of edges for each node so that you know whether you can drop an edge and also when to stop altogether.
> 3 votes

---
Tags: graphs, hamiltonian-path
---


title: What motivates the RAM model?

text:
# Question
Title: What motivates the RAM model?
It looks like most of today's algorithm analysis is done in models with constant-time random access, such as the word RAM model. I don't know much about physics but from popular sources I've heard that there's supposed to be a limit on information storage per volume and on information travel speed, so RAMs don't seem to be physically realizable. Modern computers have all these cache levels which I'd say makes them not very RAM-like. So why should theoretical algorithms be set in RAM?

# Answer
Let me give a different take on it than vonbrand. Everything you said is true: the RAM model is not realistic for a number of reasons, and whereas it is possible to defend different aspects of it, such a defense doesn't really get to the heart of the matter.

**The heart of the matter -- and the answer to your question -- is that the RAM model is the best thing we have.** Compared to other models that are accepted, it more accurately models real-life computation. In particular, the reason we adopted the RAM model was primarily a response to Turing machines, as we found that the use of Turing machines leads to problems being artificially difficult to solve in terms of time complexity. The RAM model clearly solves this glaring issue, and thus it has been accepted, even though it remains far from perfect.

A classical example that illustrates the glaring issue with Turing machines is the problem of string equality: given input

$$ w\_1 \\# w\_2$$

where $w\_1, w\_2$ are binary sequences and $\\#$ is a separator, determining whether $w\_1 = w\_2$. It can be shown that any Turing machine for the equality problem takes $O(n^2)$ time. This is uncomfortable, because Turing machines are what everyone thinks of as the universal model of computation -- yet no software engineer or algorithms researcher believes that string equality really takes $O(n^2)$ time. So what gives? String equality should be linear, so we invent a new model where it is, and the best solution available right now is word RAM machines.

Perhaps some day in the future we will come up with a better model -- one that is simple, conceptually clear, and improves on RAM in its ability to model real-life computational complexity. For now, we can only make do with the best that we have.
> 5 votes

# Answer
As a first, rough, approximation you can take the time to access a word in memory as constant, independent of preceding accesses. I.e., the RAM model.

You are right, today's machines are quite un-RAM-like, it does pay off (even handsomely) to organize data access to be as sequential as possible or squeze the last bit of information out of a (short!) memory segment before manhandling the next. But you rarely have the leeway to do so, your memory accesses are essentially random and the model isn't that far from the truth. Plus today's machines have many more than one CPU, the model has just one. And then there is vector processing (doing the same operation on a vector of data, not one by one) as the "multimedia instructions" (and even more using graphics cards for processing) do.

A bit of discussion is given for example by Khoung's Binary search is a pathological case for caches. As you see, analyzing even simple, well-understood algorithms under more realistic memory access time models is daunting.
> 1 votes

# Answer
RAM model is motivated by asymptotic analysis of algorithms that are designed as single-threaded in-memory computations.

Optimising performance for specific instruction set, caches and whatnot is one thing. The other thing is to be prepared for growth of the problem size. To estimate how well your in-memory algorithm scales you probably want to ignore small factors and focus on big $\mathcal{O}$ notation. Big $\mathcal{O}$ isn't going to optimise everything for you, but at least it may tell you that your solution scales well (or that you should try something different).

RAM assumes small fixed instruction set, where each operation works in $\mathcal{O}(1)$. Note that this is a good model if we only care about asymptotic growth:

1. Instruction set of a modern CPU is not small, but we can pretend that it actually is. Those additional op-codes do not make difference in the big $\mathcal{O}$ notation.
2. CPUs may have instructions whose runtime depends on input. Again, we can ignore them, because we can model them using simpler instructions without affecting big $\mathcal{O}$ complexity. The same holds for cache levels: their performance is still bounded by some small constant, thus work in $\mathcal{O}(1)$ by definition.
3. Yes, you can't access memory in constant time if it keeps growing. Luckily, this is never required thanks to common sense. Nobody is indexing the entire Internet into non-persistent memory of a lonely single-threaded machine.
> 1 votes

---
Tags: computation-models
---


# Question
Title: Confused by proof of correctness of Majority
I have been studying a streaming algorithm to determine if there is a majority element in a stream. But am confused by a proof for it.

The algorithm works as follows. You keep one counter $c$ and a store for one item called $a^\*$. When a new item arrives, first you check if $c == 0$. If so you set $c=1$ and $a^\*$ stores the arriving item. Otherwise, if $c\>0$ and the arriving item is the same as $a^\*$ you increment $c$ or decrement $c$ if not.

If there is a majority element then it will be stored in $a^\*$ at the end.

In the notes from http://www.cs.toronto.edu/~bor/2420f17/L11.pdf there is a proof of this fact (called simpler proof).

I can see that if there is a majority item then $c'$ will be positive at the end of the stream. But:

* How do we know that $a^\*$ will hold the majority item at the end?
* Does $c'$ being positive imply that $c$ will be positive too?

# Answer
At each step,

* if $c == 0$, set $c=1$.
* Otherwise, if $c\>0$, either increment $c$ or decrement $c$.

Since $c$ is 0 initially, it is always true that $c\ge0$. That means, $-c\le0$ all the time.

---

Suppose, at some moment, $c'$ is positive. The definition of $c'$ says $c'=c$ when $a^\*=v$ and $c'=-c$ otherwise. Since $-c\le0$, $c'\not=-c$. So, the situation cannot be "otherwise". The situation must be other than "otherwise", i.e, $a^\*=v$ and, hence, $c'=c$.

We just proved that for any moment, if $c'$ is positive, then $a^\*=v$ and $c=c'$ is also positive.

Now just apply the above conclusion to the very last moment.
> 3 votes

---
Tags: streaming-algorithm
---


# Question
Title: Why isn't there just one "keystone" activation function in Neural Networks?
This article says the following:

> Deciding between the sigmoid or tanh will depend on your requirement of gradient strength.

I have seen (so far in my learning) 7 activation functions/curves. Each one seems to be building on the last. But then like the quote above, I have read in many places essentially that "based on your requirements, select your activation function and tune it to your specific use case".

This doesn't seem **scalable**. From an engineering perspective, a human has to come in and tinker around with each neural network to find the right or optimal activation function, which seems like it would take a lot of time and effort. I've seen papers which seem to describe people working on automatically finding the "best" activation function for a particular data set too. From an abstraction standpoint, it's like writing code to handle each user individually on a website, independently of the others, rather than just writing one user authentication system that works for everyone (as an analogy).

What all these are papers/articles are missing is an explanation of *why*. Why can't you just have *one* activation function that works in all cases optimally? This would make it so engineers don't have to tinker with each new dataset and neural network, they just create one generalized neural network and it works well for all the common tasks today's and tomorrow's neural networks are applied to. If someone finds a more optimal one, then that would be beneficial, but until the next optimal one is found, why can't you just use one neural network activation function for all situations? I am missing this key piece of information from my current readings.

What are some examples of why it's not possible to have a keystone activation function?

# Answer
Those are old articles. Tinkering with activation functions probably isn't your best use of time, in most cases. Today, the standard engineering practice is (to a first order of approximation): use ReLU and don't stress over it. ReLU is clearly superior to sigmoid and tanh for most cases, so if you read older articles they'll talk about sigmoid and tanh, but today, ReLU has replaced them. There are fancier newer activation functions that in some cases are slightly better than ReLU and in some cases are slightly worse but the short version is ReLU is good enough and don't worry about the others at this stage in your learning and knowledge; just use ReLU and call it a day.

This is a crude simplification and there are absolutely exceptions but I'm giving you a rule of thumb that will be pretty reasonable in practice.

Why? My main answer is that you will need to get used to the fact that when working with neural networks, we don't really know the answer to most "why" questions. Sometimes we have intuition and theories but at its heart this is an empirical science: we don't really understand why neural networks work well. There are papers that give some explanation of why ReLU seems to do better than sigmoid/tanh -- in particular, sigmoid/tanh suffer from vanishing gradients when their inputs are in the tails of the sigmoid/tanh (as then their output is exponentially small, so the gradient is essentially zero), and then training gets stuck or proceeds very slowly -- but don't expect great theory that is going to tell you what to do. Instead, this is largely an empirical science, and if we're lucky, we have experiments and theory that helps us understand the empirical data we see.

I don't see any reason to expect there to be a single activation function that is optimal for all tasks, so I'm not bothered if that isn't true and don't feel that we need a "reason" for it to be false.
> 3 votes

---
Tags: neural-networks
---


# Question
Title: Why don't they use all kinds of non-linear functions in Neural Network Activation Functions?
Pardon my ignorance, but after just learning about Sigmoid and Tanh activation functions (and a few others), I am wondering why they choose functions that always go up and to the right? Why not use all kinds of crazy input functions, those that fluctuate up and down, ones that are directed down instead of up, etc.? What if used functions like those in your neurons, what is the problem, why isn't it done? Why do they stick to very primitive very simple functions?

# Answer
> I am wondering why they choose functions that always go up and to the right? Why not use \[...\] ones that are directed down instead of up, etc.?

The activation function is applied to a weighted sum of the inputs of the neuron. Replacing a function that is "directed up" with one that is "directed down" is equivalent to changing the weights. There's no particular reason to prefer an increasing function to a decreasing one, it just happens to be the convention.

> Why not use all kinds of crazy input functions, those that fluctuate up and down

In principle, you could. People are using the functions that work best. If somebody found a "crazy" activation function that yielded good results it would certainly get used. However, using a "crazy" activation function probably makes it much harder to train the network. Part of the reason why e.g. ReLU is popular is because its simplicity makes training easier.
> 1 votes

# Answer
* Why do they go up? This is called being *increasing*. It expresses that *more stimulus implies more activation*. You might ask then, why would they want to express that? No particular reason other than *imitating nature*.
* Why do they go to the right? I don't really understand this question. The $X$-axis, which in Cartesian coordinates is used to represent the inputs of functions with real variable is, by convention, drawn horizontally with the values increasing from left to right.
* Why not use all kinds of crazy input functions, those that fluctuate up and down? The more complicated the function, the harder it can be to compute. For a computation that is going to be done many times, one would like it to be as simple as possible. The feature of not being monotonic (going up and down) also doesn't really add much to how expressive is a neural network. You can model a neuron with a non-monotonic activation function as the superposition of a few neurons with monotonic activation functions.$\*$
* \[Why not use\] ones that are directed down instead of up? Increasing or decreasing doesn't matter, because this can be expressed by a change of sign of the weights that represent the influence of a neuron on another. Recall that if $f(x)$ is decreasing, then $f(-x)$ and $-f(x)$ are increasing.

---

$\*$ You can observe that this is trading a more complex anatomy of the neural network for a simpler structure of the neuron. Is it worth it? I don't know. Often, when a neural network has some knowledge (usually after being trained to learn something) it is hard to identify in its structure which aspects correspond to which aspects of the knowledge. Potentially, as more research is done techniques could be developed for, in an already trained network, replacing blocks of neurons with a simple activation by a simpler block of neurons with more complex activation. I think that I am starting to talk science fiction with this surgery of neural networks.
> 1 votes

---
Tags: neural-networks, mathematical-analysis
---


# Question
Title: What were the shortcomings of Robinson's resolution procedure?
Paulson et alii. *From LCF to Isabelle/HOL* say:

> Resolution for first-order logic, complete in principle but frequently disappointing in practice.

I think complete means they can proof any true formula in first-order logic correct. In the *Handbook of Automated Reasoning* I find:

> Resolution is a refutationally complete theorem proving method: a contradiction (i.e., the empty clause) can be deduced from any unsatisfiable set of clauses.

From Wikipedia:

> Attempting to prove a satisfiable first-order formula as unsatisfiable may result in a nonterminating computation

Why is that disappointing?

# Answer
While "disappointing in practice" is certainly not definable formally, unlike "complete" (which does indeed mean "can eventually prove every true formula"), it's pretty easy to find examples where *naive* resolution is not even remotely adequate, i.e. examples which *should* be easy to prove but which resolution is extremely slow on.

A famous example is an encoding of the pigeon hole principle for $n$ holes in propositional logic (which is the statement "$n+1$ pigeons cannot fit in $n$ holes without duplicates). There is no proof of this statement using only resolution in time sub-exponential in $n$.

Things are even worse in predicate logic, where it is very easy to find statements without any fast resolution proofs.

Note that any implementation of resolution must implement a strategy for picking the resolvents, which is already a very difficult problem, and an active area of research, since most practical algorithms for theorem proving are *enhancements* of naive resolution, e.g. hyper-resolution.
> 1 votes

---
Tags: logic, proof-assistants, automated-theorem-proving
---


# Question
Title: Binary string satisfying several constraints
I'm trying to solve this problem, but without success.

> Problem: You're given a binary string where some of the bits are replaced by `?`. You're also given several intervals \[$l\_i$, $r\_i$\] ($l\_i \< r\_i$). Find a binary string S with `?` replaced by `0` or `1`, such that in each interval \[$l$, $r$\], s\[$l..r$\] includes both `0` and `1`.
>
> Example:
>
> Given the string `00?11` and the interval \[2, 3\], the string `00111` satisfies the requirements, as S\[2..3\]=`01` include both 0 and 1.
>
> However, the string `00?11` and the intervals \[2, 3\] and \[3, 4\] cannot be solved, as the `?` would have to be both `0` and `1`.
>
> The bounds are |S|,Q\<=1e5

I tried using greedy, but it's giving *wrong answer* for this case: `0??0`, \[1, 3\], \[2, 3\] and \[3, 4\], as the greedy algorithm would try `0??0` -\> `01?0` -\> `0100` -\> fail, yet there exists a solution (`0010`).

I tried removing completely overlapping intervals (such as \[1, 3\] and \[2, 3\]), but there're other cases I found that fails. What would be a correct solution?

Thanks.

# Answer
There are 4 types of intervals:

1. Intervals containing both $0$ and $1$ (e.g. `00?11?`). Such intervals are already satisfied, and we simply ignore them.
2. Intervals which can't be satisfied: either of length 1 (e.g. `0`, `?`), or contain only 0's or 1's (e.g. `000`, `111`). If such an interval exists, report "no solutions".
3. Intervals which consist only of 0's or only of 1's and have a **single** `?` (e.g. `00?0`, `1?`). For such intervals, we know what `?` must be - so we just set `?`, satisfying the interval, and ignore the interval from now on.
4. Intervals which have **more than one** `?`. We'll talk about them later.

The first phase of the algorithm is to get rid of Types 1, 2, 3. Note that when we satisfy an interval of Type 3, other intervals can change their Type.

```
while (true) {
    Remove all intervals of Type 1
    Check that there are no intervals of Type 2
    if (there exists an interval of Type 3) {
        Satisfy and remove this interval
    } else {
        break
    }
}

```

As a result, only intervals of Type 4 remain. Each such interval has two `?`. In particular, it covers two **consecutive** remaining `?`'s. Therefore, it suffices to assign to the remaining `?`'s values `0`, `1`, `0`, `1`, `0`, `1`, ..., from left to right.

---

Now, the efficient algorithm for the first phase. We process all intervals in increasing order of their right ends. We maintain a set of intervals $T\_4$ (initially empty) of currently encountered Type 4 intervals, sorted by their left ends.

For each new interval, depending on their type, we do the following:

* Type 1: Ignore it
* Type 2: Return "no solutions"
* Type 4: Add an interval into $T\_4$.
* Type 3: Satisfy it. Now we look into the rightmost interval $I$ in $T\_4$ (i.e. with the largest left end). If it changed its type, remove it from $T\_4$ and process it again (i.e. check its type and apply the corresponding action from this list). Otherwise do nothing: since $I$ didn't change its type, other intervals in $T\_4$ also won't change their type.

Indeed, let $I'$ be another interval from $T\_4$. If $I \subseteq I'$, we are fine (if $I$ has two `?`, then $I'$, which contains $I$, also has them). Let $i$ be the position of the fixed `?`. If $i \> right(I')$, then we are fine. Otherwise, we have $i \le right(I') \< right(I)$. But note that there are no `?` between $right(I')$ and $right(I)$: otherwise, the currently processed interval wouldn't be Type 3, since it has at least two `?`'s. Therefore, $I \cap I'$ has at least two `?`'s, and therefore, $I'$ too.

While processing Type 3, we find the rightmost interval $I$ in $T\_4$ until $T\_4$ is empty or $I$ didn't change its type. Simply put, we remove intervals from $S$ while there are intervals which change their type.
> 2 votes

---
Tags: algorithms, data-structures, strings, greedy-algorithms
---


title: The intersection of 2 CFL

text:
# Question
Title: The intersection of 2 CFL
I have the following two CFL: $A =\\{a^m b^n c^n\\}$ and $B = \\{a^m b^m c^n\\}$. I don't understand why the intersection of this languages is $\\{a^n b^n c^n\\}$: can anyone explain to me why the power is to the $n$ and not to the $m$ or something else? Thank you in advance.

# Answer
> 1 votes
The set $A$ cointains all the strings on the alphabet $\\{a,b,c\\}$ starting with $a$, ending with $c$ and with the same number of $b$s and $c$s. Similarly, $B$ is made by strings on the same alphabet, starting with $a$, ending with $c$ and with the same number of $a$s and $b$s.

So the intersection $A\cap B$ simply cointains all the strings on the alphabet $\\{a,b,c\\}$ starting with $a$, ending with $c$, with the same number of $b$s and $c$s and the same number of $a$s and $b$s. By the transitivity of equality (I mean, if $x=y$ and $y=z$ then $x=z$, where $x$, $y$ and $z$ are the numbers of $b$s, $c$s and $a$s in a string), you can express these last two condition by saying that the number of $a$s, $b$s and $c$s is the same, *i.e.*, that the strings in $A\cap B$ are of the form $a^n b^n c^n$ for some natural number $n$ (of course here you can use the letter $m$, or any other letter you prefer, instead of $n$).

# Answer
> 0 votes
You have that $A=\\{a^mb^nc^n:\ m,n\in\mathbb{N}\\}$ and $B=\\{a^mb^mc^n:\ m,n\in\mathbb{N}\\}$. If $w\in A$, then there are $r,s\in\mathbb{N}$ such that $w=a^rb^sc^s$. If we also have that $w\in B$ (such that $w\in A\cap B$), then there are $t,u\in\mathbb{N}$ such that $w=a^tb^tc^u$.

Therefore, $a^rb^sc^s=w=a^tb^tc^u$.

> We need to assume that $a,b,c$ are different characters. Otherwise the conclusion wanted is not satisfied. For example, if $a=b=c$, then $A=B=\\{a^n:\ n\in\mathbb{N}\\}$, while $A\cap B= A\neq\\{a^na^na^n:\ n\in\mathbb{N}\\}$. This assumption, if it was not explicitly said, it was probably intended.

Now, if $r\<t$ (or $r\>t$), then comparing the $(r+1)$-th (or $(t+1)$-th) letters of $a^rb^sc^s$ and $a^tb^tc^u$ we would get $a=b$. This is a contradiction. Therefore, $r=t$.

So, $a^rb^sc^s=a^rb^sc^s=w=a^tb^tc^u=a^rb^rc^u$. We do the same analysis with $r$ and $s$. If $r\<s$ (or $r\>s$) we compare the $(r+1)$-th (or $(s+1)$-th) characters of $a^rb^sc^s$ and $a^rb^rc^u$. This gives that $b=c$, which is a contradiction. Therefore, $r=s$.

So, $a^rb^rc^r=w$.

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


# Question
Title: solving recurrence T(n) = T(√n) + theta((lg lg n))
My solution: let m = lg n. Then n = 2^m. T(2^m) = T(2^(m/2)) + theta(lgm). Let S(m) = T(2^m). Then S(m) = S(m/2) + theta(lgm). Applying master theorem, I get m^(lg1) = 1 which is asymptotically smaller than theta(lgm). So I think case 3 of the master theorem should apply. However, the solution given explains that case 2 of the master theorem applies here which I do not quite understand.

# Answer
Let $S(n) = T(2^n)$. Write a recurrence formula for S, solve S(n), use that to solve T(n).
> 2 votes

# Answer
T(n) = T(√n) + ϴ(log log n) …….1
Let n = 2m
Taking log2 both side, we get
log2n = m ……2
=\> (log n) /log 2 = m (using the formula logab = logmb /logma)
=\> log n = m x log2
Now, equation 1 becomes
T(2m) = T(2(m/2)) + ϴ(log (m x log2))
=\> T(2m) = T(2(m/2)) + ϴ(log (m) + loglog2))
As we know that constant can be ignored hence loglog2 can be ignored
=\> T(2m) = T(2(m/2)) + ϴ(log m) …….3
Now, let T(2m) = S(m) ……4
then T(2(m/2)) = S(m/2)
So eq. 2 becomes:
S(m) = S(m/2) + ϴ(log m)
Now it is in master’s form, i.e T(n) = aT(n/b) + ϴ(nk x logp n)
here a = 1, b= 2, k = 0 , p = 1
which follows the case a = bk, where p \> -1
Hence S(m) = ϴ(mlogba x log(p+1) m)
=\> S(m) = ϴ(mlog21 x log2 m)
=\> S(m) = ϴ(m0 x log2 m)
=\> S(m) = ϴ(log2 m)
Substituting S(m) with T(2m) from eq. 4
T(2m) = ϴ(log2 m)
Now substituting the value of m from equation 2, we get
***T(n) = ϴ(log2 log2n)***
Thus it doesn't matter what base is log the answer will be same taking log both side instead of log2 will make our job more easier.
> 1 votes

---
Tags: algorithms, algorithm-analysis, master-theorem
---


# Question
Title: Overhead cost of spawning child processes
I am curious as to the overhead cost of spawning child processes using `fork` in a Linux environment. Suppose I have a C program such as

```
void run_computation(int x);

int main() {
    for (int k=0; k<10; k++) {
        if ( fork() == 0 ) {
            run_computation(k);
            break;
        }
    }

    return 0;
}

```

Assuming that no global state is modified by `run_computation`, how efficient in terms of overhead is the setting up of the child processes?

To help understand where I'm coming from, I'd like to write my own regex engine (for self-learning) and am imagining using `fork` to implement the NFA. So, am I incurring an unreasonable cost in such an implementation compared to other methods?

# Answer
The (non-negligible) cost is the set up of the in-kernel structures to keep track of the new process (setting up page tables and so on).

You can easily measure it: Write a small program just like the one you have:

```
#include <unistd.h>

/* Define FORK for forking version */

#ifdef FORK
#define ROUNDS 10000
#else
#define ROUNDS 10000000
#endif

int main(void)
{
        for(int i = 0; i < ROUNDS; i++) {
#ifdef FORK
                if(fork() == 0) /* Child */
                        return 0;
#endif
        }
}

```

and run it under `time(1)`. Here I get (Intel(R) Core(TM) m5-6Y57 CPU @ 1.10GHz, Fedora 32, kernel 5.7.15-200.fc32.x86\_64, gcc-10.2.1-1.fc32, no optimization; just checked that the non-forking code does it's rounds) for non-forking:

```
real    0m0.027s
user    0m0.024s
sys     0m0.004s

```

For forking:

```
real    0m0.436s
user    0m0.016s
sys     0m0.414s

```

Very definitely not advisable.
> 2 votes

---
Tags: efficiency, multi-tasking
---


title: Dynamic Programming - Tiling Question

text:
# Question
Title: Dynamic Programming - Tiling Question
I came across the following question while practising for my final algorithms exam, but I am unsure how to get a linear time complexity for this problem. I assumed it would require checking which tiling patterns are compatible with each other, but get a bit stuck on how to proceed.

Thanks!

# Answer
> 1 votes
Well, the state should be dp\[n\], the optimal answer for some prefix of size n. Considering the different tiles, the transitions should be intuitive:

dp\[n\] = max(dp\[n-2\] + max(a\[n\], a\[n-1\]), dp\[n-3\] + max(a\[n-1\], a\[n-2\] + a\[n\]))

Of course, if any of the indices n-2, n-1, or n-3 are less than 0, then the involving terms should be omitted from the calculation. This is just a general representation of what the transition should be.

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


# Question
Title: Algorithm to find out if a set contains two number with sum in the same set using a blackbox function
I need help with the following question - There is a set S of n integers. Given a black box which returns three integers a,b,c in S such that a+b+c = 0 if they exist. One needs to devise an algorithm that makes only one call to the black box to find out if S contains three integers such that a+b=c

The question also had a hint - Construct a set S' such that there exists a',b',c' in S' such that a'+b'+c'=0 if and only if there exists a,b,c in S such that a+b=c

Thanks

# Answer
> 3 votes
Your question is essentially answered on the Wikipedia page on the 3SUM problem, specifically the part on 3 different arrays.

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


# Question
Title: how did they get this answer for the words that don't have bba and abb?
I am looking at the answer in solution manual which asked , all the words that don't have both substring bba and abb.

and the answer was `a*(baa*)*b+b*(a*ab)*a*`

and I'm like wait a minute is that right ? but that can't make abb, which is in the language. So it's gotta wrong.

so I came up with my own , would this be all the words that don't have both substring bba and abb ?

```
(b+^)(ab+a)*+b*

```

^ is an empty string by the way

# Answer
The textbook's answer does appear to be incorrect, as you note it does not generate $abb$ (and just to rule out an alternative interpretation of the exercise - "all strings that include neither $abb$ nor $bba$ - it does generate $bba$).

However your answer is also incorrect unfortunately - it doesn't generate $bba$.

There are a couple of reasonably sensible ways to get a correct answer (of course there's always many many techniques, and different people prefer different ones).

The first is the "intuition" approach, break the problem into the two parts, "the strings that don't have $bba$" and "the strings that don't have $abb$", then combine. With this method you have to then think about how such strings would look, and convince yourself that you haven't missed any cases.

The very formal method is to construct the expression from smaller, verifiable building blocks. In this case, we can easily construct a DFA for the strings that *do* contain $abb$ and one for the strings that contain $bba$, then we can use the intersection construction to get a DFA for the intersection of the two languages, take the complement DFA, then convert this to a regular expression.

What they seem to have done, and messed up or made a typo in one part, is the formal-but-not-quite-as-silly-as-option-2 method, where we make the two small DFAs, take their complements separately, convert each to a regular expression, then combine. I'll do the half that they seem to have gotten wrong (the bit that allows $abb$ but not $bba$, which is the first half of their expression).

The initial DFA is:

Taking the complement we get:

This second DFA recognises all the strings that don't contain $bba$. Now we convert this to a regular expression using the normal state elimination algorithm. If you haven't seen this yet, it will appear shortly in whatever course you're studying, or you can look over this explanation, but for the moment (and for the sake of keeping this answer on track!) hopefully it's acceptable that there is an algorithm for doing this conversion. In principle this algorithm can result in slightly different regular expressions depending on the order you eliminate the states, so if you have a go at it, you may not end up with quite the same regular expression (if you try one particular order, you get a real mess).

After all that we get the regular expression: $$ (a+ba)^{\ast}b^{\ast} $$

If we then proceed and do the DFA for strings containing $abb$, take its complement and derive the regular expression, we get (picking the right elimination ordering) the same as their second half, $b^{\ast}(a^{\ast}ab)^{\ast}a^{\ast}$, and combine them and get the final answer: $$ (a+ba)^{\ast}b^{\ast}+b^{\ast}(a^{\ast}ab)^{\ast}a^{\ast} $$
> 6 votes

# Answer
Do not have substrings bba and abb:

Regular Expression= ^+b+ bbb\*+(a+ba)(a+ba)\*(^+b)

L={^, a, b, aa, ab, ba, bb, aaa, aab, aba, baa, bab, bbb, aaaa, aaab, abaa, baaa, baab, baba, bbbb,...}
> 0 votes

# Answer
These are incorrect R.E we generate bba from the 2nd part

I think b\*+a\*(ab)*a*+a\*(ba)*a*+a\*ba(a+ab)*a*+a\*ab(a+ab)*a* may be correct R.E.
> -2 votes

# Answer
It is a very simple RE. {a\*(ba+a)\*(b+^) + (b \*) } Where ^ is null. JazakAllah :)
> -3 votes

---
Tags: regular-expressions
---


# Question
Title: Minimum cardinality graph partition that removes specific edges
I have a computational problem that I want to solve. I'm not sure if it has already been studied in literature, or if so under what name. I'd appreciate any pointers to literature or suggestions for an algorithm.

Input: A connected, undirected graph G = (V, E) in which certain edges are labelled "bad".

Output: The minimum cardinality partition of V such that 1) all of the induced subgraphs of the partition are connected, and 2) none of the induced subgraphs contains a bad edge.

Thanks!

# Answer
Try to look at what happens when all the edges are *bad edges*.

What would the question be if I asked:

> Can you partition the graph into *three* partitions, e.g. *red, green, blue*, such that for every edge, the "color" of the endpoints of each edge is "chromatic".

(Let's also make the graph into a complete graph by adding "good" edges between every non-adjacent vertices.)
> 1 votes

---
Tags: graphs, partitions
---


# Question
Title: Intro to Algorithms: asymptotic function analysis
I'm reading "Introduction to Algorithms" 3rd edition by Cormen, Leiserson, Rivest, Stein Page 46. The authors place formal upper and lower bounds on a function which is quadratic. Can anyone explain where the values for $c\_1$, $c\_2$ and $n\_0$ are taken? I'm also confused why the $max$ function is used and it's parameters.

# Answer
The values of $c\_1$ and $c\_2$ are pulled out of thin air. Their actual values don't matter except for the property that $$0\<c\_1\leq a\leq c\_2$$

The value of $n\_0$ also doesn't matter except for the property that $$n\>n\_0\implies c\_1n^2\leq an^2+bn+c\leq c\_2n^2$$

This implication is equivalent to saying that the interval $n\geq n\_0$ is inside the set of solutions of the system of inequalities $$\begin{cases}(a-c\_1)n^2+bn+c&\geq0\\\(c\_2-a)n^2-bn-c&\geq0\end{cases}$$

So, they solved the system of inequalities $$\begin{cases}\frac{3a}{4}n^2+bn+c&\geq0\\\frac{3a}{4}n^2-bn-c&\geq0\end{cases}$$

You can see now that the concrete values of $c\_1$ and $c\_2$ were chosen such that the two inequalities in the system are nearly the same, except for the sign of the coefficients. The two are quadratic polynomials with positive leading term. They are going to be non-negative outside the interval formed by their roots. So, for the interval $n\>n\_0$ to be inside, we just need to take $n\_0$ to be a bound from above of the absolute value of the roots.

There are many known bounds of the roots in terms of the coefficients. It looks like they took this bound by Lagranges. Although $2\max\left(\frac{|b|}{a},\sqrt{\frac{|c|}{a}}\right)$ would be the bound for the roots of the polynomial $an^2+bn+c$ and we have instead $\frac{3}{4}an^2+bn+c$. The bound would be instead $2\max\left(\frac{4|b|}{3a},\sqrt{\frac{4|c|}{3a}}\right)$, which is somewhat larger.
> 1 votes

---
Tags: algorithms, runtime-analysis, big-o-notation
---


# Question
Title: minimum travel from point to point with incremental steps
It's my first time to make a question here. I have a curious problem about algorithm, in the center of Cartesian plane (0,0) I need to go to another point (x,y) -x and y are belong to Z numbers - but I only can use horizontaly and verticaly steps and this steps increases one by one units, a unit is a distance from (0,0) to (0,1), (1,0), (-1,0) or (0,-1).

For example, I need to go to (1,1) point and steps are:

* Go to (1,0), a step of 1 unit.
* Go to (1,-2) a step of 2 units.
* Finally, go to (1,1) a step of 3 units.

And for this example the answer is I need 3 steps with 6 units of distance.

Obviously, there are several ways to go to a point from center but the problem needs the minimal.

Are there a formula or an algorithm to find the minimum count of steps and the distance of this way?

Well, if you find one of them (steps or distance), the other one is easy to find because the distance is a sum of N (count of steps) first natural numbers.

Thanks for read this and for your answers and suggestions.

# Answer
Interesting question. It is surprising that the answer depends only on $|x|+|y|$. For example, the same number of the steps is needed to reach $(1,1)$ or $(0,2)$.

---

The minimum step is the least non-negative integer $n$ such that $n(n+1)/2-(|x|+|y|)$ is even and nonnegative.

Here is an $O(1)$-time algorithm that returns the value described above, where `least_n`, i.e., $\left\lceil\frac{-1+\sqrt{8(|x|+|y|)+1}}2\right\rceil$, is the least nonnegative integer $n$ such that $n(n+1)/2-(|x|+|y|)\ge0$.

```
def minimum_steps(x,y):
    distance_to_origin := absolute_value(x) + absolute_value(y)
    least_n := ceiling((-1 + square_root(8 * distance_to_origin + 1)) / 2)
    gap := n * (n + 1) / 2 - distance_to_origin
    # 0 <= gap <= n - 1

    if gap is even:
        return least_n
    else if n is even:
        return least_n + 1
    else:
        return least_n + 2

```

Given the number of steps $s$, the distance travelled is $1+2+\cdots+s=s(s+1)/2$.

---

The correctness of the formula and algorithm above comes from the following characterization.

**Proposition.** The minimum count of steps from $(0,0)$ to $(x,y)$ is the least non-negative integer $n$ such that $n(n+1)/2-(|x|+|y|)$ is nonnegative and even.

**Proof**. If we can go to $(x,y)$ in $n$ steps, the sum of some numbers between 1 and $n$ or their negations must be $x$ and the sum of the remaining numbers or their negations must be $y$, i.e., $$\pm1\pm2\pm\cdots\pm n = |x| + |y|$$ for some choice of all $\pm$'s. That means, $$1+2+\cdots+ n - (|x| + |y|)$$ is nonnegative and even.

Now it is enough to prove that $(x,y)$ is reachable in $n$ steps if $n(n+1)/2-(|x|+|y|)$ is nonnegative and even. Let us prove it by induction on $n$.

The base cases, $n=0$ or $1$ means $(x,y)=(0,0), (0,1), (1,0)$. These cases are immediate to verify.

Suppose, as induction hypothesis, it is correct for smaller $n$'s. Now consider the case of $n\ge2$ with $n(n+1)/2-(|x|+|y|)$ nonnegative and even. We can assume $x$ and $y$ are non-negative; otherwise, for example, if $x$ is negative, we can change $x$ to its absolute value and reverse the direction of all steps that are parallel to $X$-axis.

There are three cases.

* $x \ge n$. Let $x'= x-n$. Then $$(n-1)n/2-(|x'|+|y|)=n(n+1)/2-(|x|+|y|)$$ is nonnegative and even. By induction hypothesis, we can go to $(x',y)$ in $n-1$ steps. To reach $(x,y)$ in $n$ steps, we continue $n$ units in X-direction.
* $y\ge n$. This is symmetric to the case above.
* $0\le x\lt n$ and $0\le y\lt n$. There are two subcases.
    + $x\ge 2$ and $y\ge 2$. Let $x'=(n-1)-x$ and $y'=n-y$. Then $|x'|\le n-3$ and $|y'|\le n-2$. $$(n-2)(n-1)/2-(|x'|+|y'|)\ge(n-3)(n-4)/2\ge0.$$ The parity of $(n-1)(n-1)/2-(|x'|+|y'|)$ is the same as $n(n+1)/2-(|x|+|y|)$, i.e, even. By induction hypothesis, we can go to $(x',y')$ in $n-2$ steps . Reversing all the steps, we can go to $(-x', -y')$ in $n-2$ steps as well. To reach $(x,y)$ in $n$ steps, we can continue with two more steps, $n$ units in X-direction and $n+1$ units in Y-direction.
    + One of $x$ and $y$ is $0$ or $1$. Let $g(k)=k(k+1)/2-(|x|+|y|)$. The smallest nonnegative integer such that $g(k)\ge0$ is $m=\left\lceil\frac{-1+\sqrt{8(|x|+|y|)+1}}2\right\rceil$. Since both $x$ and $y$ are $\lt n$ and one of them is $0$ or $1$, $$m\le \frac{1+\sqrt{8n+1}}2.$$ When $g(m)$ is even, $n=m$ by definition. When $g$ is odd, since either $g(m+1)=g(m)+(m+1)$ or $g(m+2)=g(m)+(m+1)+(m+2)$ must be even, either $m+1$ or $m+2$ must be $n$. So, whether $g(m)$ is even or odd, we have $$n\le m+2.$$ Combing the two inequalities above, we have $$n\le \frac{5+\sqrt{8n+1}}2,$$ which implies $n\le 6$. Since X-direction and Y-direction are symmetric, let us assume $y=0,1$. Since $x\lt n$, $x\lt 6$. So it is enough to verify the cases where $(x,y)$ $\in $ $\\{(0,0),(0,1),$ $(1,0),(1,1),$ $(2,0), (2,1),$ $(3,0), (3,1),$ $(4,0), (4,1),$ $(5,0), (5,1)\\}.$ It is easy to verify each of them.

$\ \checkmark$
> 2 votes

---
Tags: algorithms, computational-geometry
---


# Question
Title: Using a rotation matrix to transform/shift a pinhole camera
I have a pinhole camera model with the following extrinsic (in Earth Centered, Earth Fixed Coordinate, (ECEF) system) and intrinsic parameters.

focal length (x,y) = 55000 px, optical center = (2400,540)

camera center (x,y,z), (ground coordinates) = -2322996.2171387854 -3875494.0767072071 5183320.6008059494 (ECEF)

Rotation matrix (3x3, camera to ground frame) = \[\[0.88982706839551795,-0.45517069374030594 ,0.032053516353234932\], \[-0.44472722029994571, -0.84940151315102252, 0.28413864394171567\], \[-0.10210527838913171, -0.26708932778514777, -0.95824725572701552\]\]

I need to shift the camera so that it points to the correct position on the ground based on a ECEF transformation matrix (4 X 4), which looks like this:

\[\[0.99999922456661872, 0.00043965959331068635, -0.0011651461883787318, 7033.5303197340108\], \[-0.00044011741039666426, 0.99999982604190574, -0.00039269946235032278 ,814.02427618065849\], \[0.0011649733316053631, 0.00039321195895935108, 0.99999924411047925 ,4139.9400998316705\], \[0, 0, 0, 1\]\]

The 3 x 3 matrix portion formed by the first three rows and columns are the rotation component, the first three values in the last column is the translation component. My general understanding is that I need to add the translation component to the camera center coordinates, while multiply the camera to ground rotation matrix with the rotation component. Is this sufficient, or would I need to do something extra ?

# Answer
> 1 votes
It looks like you got it, but what's actually going on here is that you are working in homogeneous coordinates.

In this system, a *point* in space is represented as a 4-tuple, $(x,y,z,1)$. You can multiply this 4-tuple by any non-zero constant and it represents the same point, so this is equivalent to $(wx,wy,wz,w)$ for any $w \ne 0$.

A *vector* is the difference between two points, and this is represented as a 4-tuple with a zero in the fourth component, $(x,y,z,0)$.

Right-multiplying that 4x4 matrix by a point has the effect of adding the translation component, and right-multiplying by a vector has the effect of not adding the translation component.

# Answer
> 0 votes
I think I got it. For transforming the camera-center, I use = rotation\_component of transform\*initial\_camera\_center + translation\_component of transform.

For transforming the rotation-matrix, I use = rotation\_component of transform\*camera\_rotation\_matrix.

The camera is now in the correct place, looking in the right direction.

---
Tags: computer-vision
---


title: Regular expressions

text:
# Question
Title: Regular expressions
I am new to theoretical cs and am working through it slowly. I have completed a simple question and was wondering if my answer is correct or not. Thank you kindly for any feedback.

**The question is:** Given the alphabet $\\{a, b\\}$ Construct a regular expression that defines the language $M$ containing all words beginning with exactly one $a$ or exactly one $b$. Words in $M$ are at least of length $1$. Words in $M$ can begin and end with the same letter substring or begin and end with different letter substrings.

**My answer is:** $( a( b( a + b)^\*)^\*) + (b ( a (a + b)^\*)^\*)$

Thank you.

# Answer
> 1 votes
Setting $A = a + b$, you could write $M$ as $A + abA^\* + baA^\*$ or as $A + (ab +ba)A^\*$. This avoids the nested star of your answer.

---
Tags: regular-expressions
---


# Question
Title: Does the set ALL_TM contain all Turing Machines?
ALL\_TM = { TM | A valid TM }

This was a question on my exam.

As my choice of answer I went with yes, since the set of all Turing Machines is countable, ( you can produce a binary string for each and every new Turing Machine ) my take on the answer that yes it does contain all Turing machines. But apparently my answer was wrong so I am curious

why ?

Thanks in advance for anyone's answer !

# Answer
It turned out that the set of ALL\_TM = { | M accepts all strings }, the set wasn't specified on the exam and I have seen it within notes but it was in the formulation that I have stated above so that was a bit confusing !

Anyway the set of ALL\_TM does not contain all TM's since it only contains TM's that accept all strings.
> -1 votes

---
Tags: turing-machines
---


# Question
Title: How can one measure the time dependency of an RNN?
Most of the discussion about RNN and LSTM alludes to the varying ability of different RNNs to capture "long term dependency". However, most demonstrations use generated text to show the absence of long term dependency for vanilla RNN.

Is there any way to explicitly measure the time dependency of a given trained RNN, much like ACF and PACF of a given ARMA time series?

I am currently trying to look at the (Frobenius norm of) gradients of memories $s\_k$ against input $x\_l$, where $l\le k$, summed over training examples $\\{x^i\\}\_{i=1}^N$ \- $$\text{Dep}(k,l):=\sum\_{i=1}^N \big\\|\frac{\partial s\_k}{\partial x\_l}(x^i)\big\\|\_F$$ I would like to know if there are more refined or widely-used alternatives to this prototype.

I am working with time series so I treat the inputs $\\{x\_t\\}$ as realization of a random process $\\{X\_t\\}$, thus by "current" I mean $x\_i,s\_i$ for some fixed $i$, "the past" I mean $\\{x\_j\\}\_{j=1}^{i-1},\\{s\_j\\}\_{j=1}^{i-1}$ and "time" I mean the index $t$.

I guess that the "long-term dependency" in literature refers to the sensitivity of the current memory $s\_k$ w.r.t. past inputs $\\{x\_j\\}\_{j=1}^{k-1}$, hence the prototype I formulated.

# Answer
> 0 votes
I am not aware of any standard or widely-used metric for this. I think what metric would be appropriate would depend on what you want to use it for.

The issues with RNN is "forgetting". If you feed a long sequence of inputs $x=(x\_1,\dots,x\_n)$ into a RNN, where $n$ is too large, the problem is that often the final decision is determined by the last few values ($\ldots,x\_{n-1},x\_n$) and the earliest values ($x\_1,x\_2,\ldots$) have been "forgotten" and do not affect the final decision. This is undesirable in many settings.

Your metric would be one reasonable way to get a feeling for this. Another reasonable way might be to to feed in an input $x=(x\_1,x\_2,\dots,x\_n)$, then change just $x\_1$ to get a new input $x'=(x'\_1,x\_2,\dots,x\_n)$, feed in $x'$, and compare the outputs of the RNN on $x$ vs $x'$; and repeat for many training samples or test samples $x$.

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


# Question
Title: Finding which value I will be on after a certain number of steps
I have a fixed array: `[a,b,c]`, I wanna loop through this 3-items-sized array for 7 times in order to find what I would get at that exact step.

The "value stack" for `7` would look like `a b c a b c a`.

Question is, how can I find what value would be at step `10`, for example?

---

Input: `getValueForStep( [a,b,c], 7 )`

Output: `a`

# Answer
A simple observation is that, with 0-based indices:

```
final_index = (elements_traversed - 1) mod array_length

```

For example, for `array_length = 3` and `elements_traversed = 7`, `final_index = (7 - 1) mod 3 = 0` (corresponding to the first element).
> 1 votes

---
Tags: arrays
---


title: understanding loop invariants

text:
# Question
Title: understanding loop invariants
I have a bit of experience with loop invariants but I'm not really clear on them. I'm trying to learn them through an Algorithm I have.

```
Reverse(X,Y)
   n = X.length
   for(i = 1 to n)
      Y[n - i + 1] = X[i]
   return Y

```

This copies values in array X into array Y in reverse order, and returns array Y. If X and Y both have length n (i.e., n = X.length = Y.length) and both arrays are indexed from 1 to the length of the array, what would be some loop invariants for the for loop which would prove its correctness?

# Answer
> 1 votes
The reverse of `X[:i]`, the prefix of `X` up to the $i$-th position is equal to `Y[n-i+1:]`, the suffix of `Y` from the $(n-i+1)$-th position onward.

Before the loop starts, which we could consider as $i=0$, we have that the reverse of the prefix of `X` of length zero is equal to suffix of `Y` of length zero.

Each step of the loop preserves the property for the previous value of `i` and makes the property true for the current value of `i`.

At the end of the loop the property is satisfied for `i=n`, which implies that the reverse of `X` is equal to `Y`.

---
Tags: loops, loop-invariants
---


# Question
Title: Convention of a += operator in pseudocode
I have to write some algorithm in pseudocode for a paper. For this I have the "$\leftarrow$" to assign a value.

$x \leftarrow y^2$

now I want to write a method which adds to the variable. In normal Python code I would write `x += 1` for this. Is there a style convention how to layout this in pseudo-code in a paper? I dont really like the redundance of $x \leftarrow x+1$.

# Answer
> 3 votes
The `+=`et al are C shortcuts, adopted by many languages. Most anyone should understand them.

Then again, this is (pseudo)code, you certainly can make up you own variant. Just make sure to define clearly what any not-so-standard constructions mean (I'd go for `+=` and so on, but then again, I'm a C fan...). But make sure to be consistent, i.e., use `=` for assignment and `+=` for your operation, don't mix it with e.g. $\leftarrow$, and state that you'll use C notation for assignments.

Whatever you do, always keep in sight that the objective is *understanding* by your gentle reader, not extreme rigour or algorithmic details.

---
Tags: notation, pseudocode
---


# Question
Title: Does an insecure router bypass the privacy guarantee of a VPN connection?
If I have a router that has a vulnerability that allows an attacker to gain full control it, does using a VPN on the network with the said router prevent an attacker from being able to snoop on the connection?

In other words, does using a VPN secure the connection from a device to a router? And would a VPS make a difference in this scenario?

# Answer
> 1 votes
If you're talking about a VPN that extends to your PC/device, and similarly on the other side of the communications, and the insecure router somewhere in the path in between, then yes, an attacker should not be able to eavesdrop/snoop on the connection. The traffic would be encrypted and the attacker would not be able to understand it. This is one of the points of using the VPN in the first place. It creates a "virtual" private network over infrastructure (including routers) that may be insecure. If it doesn't even offer you this protection, then what is the point of using the VPN in the first place?

If you're talking about a *site-to-site VPN*, where traffic to/from your PC/device needs to get to/from the entry point of the VPN through, say, your office infrastructure, and if your office infrastructure is not otherwise secured, and this insecure router is part of that office infrastructure, then yes, an attacker may be able to eavesdrop/snoop, but even then it is not bypassing the privacy guarantee of the VPN, because the eavesdropping/snooping would be happening outside of the path that is protected by the VPN.

---
Tags: computer-networks, security
---


title: Operating system , synchronization

text:
# Question
Title: Operating system , synchronization
Consider the methods used by processes P1 and P2 for accessing their critical sections whenever needed, as given below. The initial values of shared boolean variables S1 and S2 are randomly assigned. Method used by P1

```
while (S1 == S2); Critical Section  S1 = S2;

```

Method used by P2

```
while (S1 != S2); Critical Section  S2 = not(S1);

```

Which one of the following statements describes the properties achieved?

* Mutual exclusion but not progress
* Progress but not mutual exclusion
* Neither mutual exclusion nor progress
* Both mutual exclusion and progress

EDIT
why in such codes we cannot preempt during executing `while`? is `while` an atomic expression here?

# Answer
> 0 votes
> why in such codes we cannot preempt during executing `while`? is `while` an atomic expression here?

No. `while` is not an atomic operation, and it can be preempted.

For example, while P1 is executing `while (S1 == S2);`, P2 can change the value of `S2`. (Otherwise the program wouldn't be very interesting, since `while (S1 == S2);` would either do nothing or loop forever.)

`while (S1 == S2);` means:

* Read the value of `S1` from shared memory into local memory. (Local memory is memory that none of the other threads access.)
* Read the value of `S2` from shared memory into local memory.
* Compare the local copies of `S1` and `S2`. If they're equal, start again. If they're different, execute the code after the loop.

And `S1 = S2;` means:

* Read the value of `S1` from shared memory into local memory.
* Write the local copy of the value to `S2` in shared memory.

The only thing that's atomic is reading or writing a single variable from/to memory. Other processes can do things, including changing the values of `S1` and `S2`, between each line in the decompositions above.

To determine whether progress is achieved, check whether P1 might get stuck in `while (S1 == S2);` forever, assuming that P2 is running and will pass through its own attempt to reach the critical section. And likewise, check whether P2 might get stuck in `while (S1 != S2);` forever.

> If P1 is stuck in `while (S1 == S2);`, given that P1 is the only one that changes `S1`, it means that `S2` keeps having the same value which is equal to `S1`. But eventually P2 will come along, and since `S1 == S2` it will enter its critical section, set `S2 = not(S1)`, and unblock P1. So P1 can progress.

I leave the progress of P2 as an exercise for the reader.

To determine whether mutual exclusion is achieved, check if there is a way to interleave the execution of the two processes such that P1 and P2 both enter their critical section at the same time. If the processes are never interrupted during their `while` loops, this is obviously true, since either `S1 == S2` or `S1 != S2`. But what might happen if the other process changes `S1` or `S2` at the wrong time?

> Suppose that initially `S1` and `S2` are both true. P1 is stuck until P2 changes `S2`. (`S1` won't change since P1 is the only one that would change it.) If P2 changes `S2`, that's to set it to false, and after that it will be stuck in its own while loop until the value of `S1` or `S2` changes. But the only thing that can change `S1` or `S2` is after one of the processes enters its critical section. So P2 can't enter its critical section again until P1 has entered and finished its critical section.

I leave the generalization to the other initial states as an exercise to the reader.

---
Tags: synchronization
---


# Question
Title: While number can be checked for primality in O(n^0.5) then why was it considered to be not in P until AKS test?
While a basic algorithm to check for primality of a number 'n' \[checking if a divides n for all a less than n\] would take O(n), AKS test was the breakthrough after which it was placed in P complexity class.

# Answer
The bit length of $n$ is $\log(n)$, if we forget about the most significant digits, which is always $1$ except for $n=0$. As a function of $t=\log(n)$ you have $n^{1/2}=2^{t/2}$. It is in terms of the bit length of $n$ that AKS runs in polynomial time, while the naive test doesn't.
> 4 votes

---
Tags: algorithms, time-complexity, p-vs-np, primes
---


# Question
Title: Show $L = $ { w $\in (a,b) ^* $| for every u substring of w, $-5\le|u|_a−|u|_b\le5\}$ is regular
I try to show that this language is regular:

$L = $ { w $\in \ (a,b) ^ * $| for every u substring of w, $-5\le|u|\_a−|u|\_b\le5\\}$

If I build a NFA and run on it every substring of w (skip other letters every time) - and only if they are all accepted (follows the condition) then accept w. Is it possible in NFA? Is there other way to show the regularity of the language?

# Answer
> 7 votes
Nice question! This is a very nontrivial problem involving regular languages.

First of all: no, you cannot run an automaton on every substring of a string skipping other letters, you are supposed to run the automaton only once on the target string.

In this case it is simpler to reason on the *complementary* of the given language, namely on

$$L^C = \\{ w \in (a,b) ^ * \mid \text{ there is a substring } u \text{ of } w \text{ such that } |u|\_a−|u|\_b\>5 \text{ or } |u|\_a−|u|\_b\<-5\\}$$

The language $L^C$ is regular, as it is recognized by the following NFA:

(each state name is the difference $|u|\_a−|u|\_b$, the first letter of the substring $u$ is "found" nondeterministically by the NFA).

So, as $L^C$ is regular, also $L=(L^C)^C$ is.

---

Following Hendrick's suggestion, I tried to determinize the NFA and to draw its complement, and I get this nice DFA that recognize $L$:

Each name of an accepting state name is an interval: when, running the automaton, we are in state $\[x\_1,x\_2\]$ and we have read the string $z$ this means that for all $x\in \[x\_1,x\_2\]$ there is a suffix $u$ of $z$ such that $|u|\_a−|u|\_b=x$. Otherwise said, following Dmitry's suggestion, the automaton calculate the residual set of $z$.

In a sense, as Hendrick says, it is like we are running the automaton on each substring, but this do not mean that we can directly use a DFA that recognize strings such that the difference between the $a$s and the $b$s is in $\[-5,5\]$ (which would be easy to realize) and run this automaton on each substring of a given one, and in this way prove that the language is regular.

---

Lastly, I would write a trivial generalization of the result (I think that this is folklore, but I couldn't find a reference).

Let $T$ be a regular language on an alphabet $\Sigma$ and let $L$ be the language defined as follows:

$$L= \\{ w \in \Sigma^\* \mid \text{ for every substring } u \text{ of } w,\ u\in T\\}$$

then also $L$ is regular.

Indeed, as above, consider $L^C$, the complement of $L$, namely

$$L^C = \\{ w \in \Sigma^\* \mid \text{ there is a substring } u \text{ of } w \text{ such that } u\not\in T\\}$$

Then $L^C=\Sigma^\*T^C\Sigma^\*$, and therefore $L=(\Sigma^\*T^C\Sigma^\*)^C$ is regular, as the family of regular languages is closed under concatenation and complementation.

Cleary the result is still true for every family of languages closed under concatenation and complementation, but this is not a necessary condition. Indeed, the family of finite languages it is not closed under complementation, but clearly if $T$ is finite, then also $L$ is (as it is always the case that $L\subseteq T$). On the other hand, this is not true for all classes of languages. Consider the family NR of non-regular languages, then $T=\\{1^p\mid p\text{ is prime}\\}\in\ $NR, but in this case we have $L=\varnothing$, which is regular.

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


# Question
Title: Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs
I am studying "An Introduction to the Theory of Computation" by Sipser -- there is a problem \*3.17 (p.161) which I can not solve. Any *hints* (not *answers*) from which side to attack it?

> Let $B=\\{M\_1, M\_2, ...\\}$ be a Turing-recognizable language consisting of TM descriptions. Show that there is a *decidable* language C consisting of TM descriptions s.t. every machine in B has an equivalent machine in C and vice versa.

# Answer
Technical hint: assume that every string is a legal encoding of a TM. Can you solve this now?

Intuitive hint: the language $C$ can contain many other encodings as well as those that are equivalent to the machines in $B$. Perhaps so many that $C$ becomes decidable.
> 1 votes

# Answer
Let $M$ be the Turing machine recognizing $B$.

# Hint

For a Turing machine, try to encode the running time required for $M$ to accept it into itself, so that one can simulate $M$ on it without going into infinite loop.

# Complete Answer

> Let $f$ be a computable bijection from $\mathbb{N}\_0^2$ to $\mathbb{N}\_0$, where $\mathbb{N}\_0$ is the set of non-negative integers.
> Define a state of a Turing machine to be *isolated* if no state can be transitioned to it and it cannot be transitioned to any state. Obviously adding or deleting isolated states does not affect the function of a Turing machine.
> Define $M\_d$ to be a decidable Turing machine, which works as follows on input \<$M\_w$\> where $M\_w$ is a Turing machine.
>
> 1. Compute the number $n$ of isolated states in $M\_w$.
> 2. Let $(n\_1,n\_2)=f^{-1}(n)$.
> 3. Let $M\_w'$ be the Turing machine that is almost the same as $M\_w$ except it has $n\_1$ isolated states.
> 4. Simulate $M$ on \<$M\_w'$\> with at most $n\_2$ steps.
> 5. If $M$ accepts, accept; otherwise, reject.
>
> Consider $M\_i$ (recall $M$ accepts \<$M\_i$\>). Suppose $M$ runs in total $n\_2$ steps on \<$M\_i$\> and $M\_i$ has $n\_1$ isolated states. Let $M\_i'$ be the Turing machine that is almost the same as $M\_i$ except it has $f(n\_1, n\_2)$ isolated states. Now $M\_i'$ and $M\_i$ are functionally equivalent, and easy to see \<$M\_i'$\> is accepted by $M\_d$.
> On the other hand, suppose \<$M\_w$\> is accepted by $M\_d$ and $M\_w$ has $n=f(n\_1,n\_2)$ isolated states. Let $M\_w'$ be the Turing machine that is almost the same as $M\_w$ except it has $n\_1$ isolated states. Now $M\_w'$ and $M\_w$ are functionally equivalent, and easy to see \<$M\_w'$\> is accepted by $M$.
> So the language deciding by $M\_d$ is what we want.
> 4 votes

# Answer
Here's a much simpler answer that uses the same idea as @xskxzr's answer. I found the bijection used in that answer not really necessary: it's much simpler to just directly store the number of steps itself in the description.

# Hint

For each description accepted by the original recognizer, construct a modified equivalent description that also stores the number of steps required by the recognizer to accept. A decider can then read this number and then simulate the original recognizer for this many steps.

# Solution

As in the answer by @xskxzr, define an *isolated state* to be a state with no transitions to and from it. Hence, for any description, we are free to choose the number of isolated states to be any arbitrary integer, without changing the functionality of the description. Hence, this becomes a mechanism to store an arbitrary non-negative integer in a description.

Now suppose we have a machine that recognizes $\\{X\_1, X\_2, X\_3, \ldots\\}$, where each description $X\_i$ is accepted by the recognizer in $n\_i$ steps.

Now define descriptions $Y\_i$ which are functionally equivalent to $X\_i$ except with $n\_i$ isolated states. We can now easily construct a decider that decides $\\{Y\_1, Y\_2, Y\_3, \ldots\\}$ by first counting the number $n$ of isolated states in the input string $Y$, and then simulating the original recognizer with $n$ steps. Clearly, there's a one-to-one correspondence between $X\_i$ and $Y\_i$, and the decider will always terminate.
> 0 votes

---
Tags: turing-machines, computability, decision-problem
---


# Question
Title: Repeating functions in functional programming?
Functional programming is said to be superior in many ways to imperitive programming. But I am struggling to find a simple functional way of writing:

```
x = f(y);
g(x,x)

```

Since in functional language this would be g(f(y),f(y)) thereby calling the function f twice. Whereas in imperitive language this seems more efficient. Equally one could write this as:

```
(x=>g(x,x)) f(y)

```

But then this to be exactly the same as imperitive way just rearranged slightly differently.

What is the "functional" way to repeating things in expression?

# Answer
> 4 votes
In the pure functional language Haskell, you could write this as

```
result =
  let x = f y
  in g x x

```

or

```
result = g x x
  where x = f y

```

or, indeed, as

```
result = (\x -> g x x) (f y)

```

...if you really wanted to for some reason.

An imperative language is one where the program is organized as a series of instructions (verbs)—that is the literal meaning of the word *imperative*. For the most part, this is equivalent to saying an imperative language is one that allows repeated mutation of a variable.

By contrast, the above notations bind the variable `x` once; it cannot be updated in-place. `x` is a name for a shared subexpression, not a mutable memory location.

Imperative vs. functional is a matter of language semantics, not language syntax. If you take an imperative language and disallow reassignment of all variables (i.e. require programs to be written in static single assignment form) and mutation of data structures, you no longer have an imperative language; you have a first-order functional language with a somewhat inconvenient syntax.

To write a very imperative version of this using Haskell monads—that explicitly creates a mutable memory location, assigns it the value of `f y`, reads it twice, and calls `g` with these values—you'd have to write something like

```
result = runST $ do
  x <- newSTRef (f y)
  liftM2 g (readSTRef x) (readSTRef x)

```

It is worth mentioning that the history of the past 40 years or so of programming language design is dominated by designers trying new ways of hybridizing features of imperative and functional programming languages. That is why JavaScript has const-bindings and anonymous functions, Haskell has monads, etc.

---
Tags: functional-programming
---


# Question
Title: Creating a large tuple from smaller tuples via a monad or applicative
Suppose I have a term $a :\alpha$ of the Simply-Typed Lambda Calculus (in the following, $\alpha, \beta, \gamma$ stand for arbitrary types) and I want to **lift** it to a term

$\lambda x\_{\beta}. \\;(x, \\, a)$

I could use a function $\lambda z\_{\alpha}, x. \\;(x,\\, z)$.

Suppose we then form $(b, a) : \beta \times \alpha$, by applying $\lambda x\_{\beta}. \\;(x, \\, a)$ to $\\,b\_{\beta}$.

We might want to add $c$ to the beginning of this to form $(c, b, a) : \gamma \times \beta \times \alpha$. We could do this (here $\pi\_1$ and $\pi\_2$ are projections)) by having a function $\lambda z'\_{\beta \times \alpha}, z. \\,(z,\\, \pi\_1 z',\\, \pi\_2 z')$. And again, we could cook up a function to form $(d,\\, c,\\, b,\\, a)$ and $(e,\\,d,\\, c,\\, b,\\, a)$ (so on and so forth).

I could do things in the way above; however, I wondered whether there was a way of doing this kind of operation via an applicative or a monad. Then I could (ideally) use the operations of the monad or applicative, to lift term $a$ (perhaps into $\lambda x.\\,(x, \\, a)$, and then form these tuples $(b, a), (c, b, a), (d, c, b, a)$, etc, by the operations of the monad or applicative.

If you know a way of doing this I would be very interested.

# Answer
(Note, this requires a more sophisticated type theory such as System Fω to encode)

This idea is captured by the concept of an *indexed* monad (and in turn indexed applicative/functor).

Using Haskell as lingua franca, we talk about a typeclass:

```
class IxMonad (m :: n -> n -> * -> *) where
  ireturn :: a -> m i i a
  ibind :: m i j a -> (a -> m j k b) -> m i k b
  {- alternatively, if it's an IxFunctor, the categorical version:
  ireturn :: a -> m i i a
  ijoin :: m i j (m j k a) -> m i k a
  -}

```

An action `m i j a` makes a connection "from" an index `i` "to" an index `j`, and wraps some type `a`. Actions can be composed only if the respective indices "line up". Sort of like how horizontal oidification turns a monoid into a category: morphisms can be composed only if their endpoint objects "line up".

Analogous definitions of an indexed functor and an indexed applicative can be made:

```
class IxFunctor (m :: n -> n -> * -> *) where
  ifmap :: (a -> b) -> m i j a -> m i j b

class IxApplicative (m :: n -> n -> * -> *) where
  ipure :: a -> m i i a
  iap :: m i j (a -> b) -> m j k a -> m i k b
  {- alternatively, if it's an IxFunctor, the categorical version:
  iunit :: () -> m i i ()
  iprod :: (m i j a, m j k b) -> m i k (a, b)
  -}

```

Say we wanted to "output" entries of some type, while keeping a type-theoretic witness of how many entries there are, we could define an indexed writer monad.

Here's definitions of natural numbers used to track length, and a length-indexed "log" datatype:

```
data N = Z | S N

data Vec (n :: N) (a :: *) where
  Nil :: Vec 'Z a
  Cons :: a -> Vec n a -> Vec ('S n) a

```

In an indexed monad, the usual intuition is that the indices `i`/`j` describe the "state" of the system: an action brings the system from "state `i`" to "state `j`". Here we'll be using the index to track how many entries we've written to the "log", and for completely technical reasons (to do with making the typechecker happy in an easy way), the left index will be the output log length, and the right index will be the input log length:

```
type family Add (n :: N) (m :: N) :: N where
  Add 'Z m = m
  Add ('S n) m = 'S (Add n m)

data IxWriter w i j a where
  IxWriter :: Vec k w -> a -> IxWriter w (Add k i) i a

instance IxMonad (IxWriter w) where
  ireturn x = IxWriter Nil x
  ibind (IxWriter xs x) f = case f x of
    IxWriter fs y -> iwappend xs fs y
    where
      iwcons :: w -> IxWriter w i j a -> IxWriter w ('S i) j a
      iwcons p (IxWriter qs z) = IxWriter (Cons p qs) z

      iwappend :: Vec k1 w -> Vec k2 w -> a -> IxWriter w (Add k1 (Add k2 i)) i a
      iwappend (Cons p ps) qs z = iwcons p $ iwappend ps qs z
      iwappend Nil qs z = IxWriter qs z

```

Then we can define the "logging" action, and an interpreter for our effect:

```
itell :: Vec k w -> IxWriter w (Add k i) i ()
itell ps = IxWriter ps ()

runIxWriter :: IxWriter w i 'Z a -> (Vec i w, a)
runIxWriter (IxWriter Nil x) = (Nil, x)
runIxWriter (IxWriter (Cons p ps) x) = case runIxWriter (IxWriter ps x) of
  (qs, r) -> (Cons p qs, r)

```

With this we can keep track of exactly how many entries we've logged:

```
case runIxWriter $
  itell (Cons 1 Nil) `ibind` \_ -> itell (Cons 2 Nil) `ibind` \_ -> itell (Cons 3 Nil)
of (Cons a (Cons b (Cons c Nil)), x) -> (a, b, c, x)
{- pattern match is valid and complete because we
   statically know it's a Vec ('S ('S ('S 'Z))) Integer -}

```

Here we used the graded monoid of finite sequences (and thus all our logs are of the same type). In theory we could have used any monoid graded by any other monoid, (for example the monoid of heterogeneous lists, graded by the monoid of lists of types -- if we wanted to be able to talk about heterogeneous tuples)
> 1 votes

---
Tags: type-theory, lambda-calculus, functional-programming, category-theory
---


# Question
Title: Implementing regular expression matching using Brzozowski derivatives
I have been taking a language theory class, and we learned about Brzozowski derivatives recently. At class it occurred to me that they could be used to implement a simple regular expression matcher. If you take the derivative of a regular expression with respect to a given string and the resulting expression matches the empty string ($\varepsilon$), then the original expression matches the string used in the derivative:

$$ w \text{ matches } e \Leftrightarrow \varepsilon \text{ matches } D\_w(e) $$

I did a web search and, as expected, other people had the same idea before. There is an implementation here and another one here. They are short and simple.

Is this used in practice anywhere? I'm not sure, but I believe that most regular expression matchers are implemented using either finite automata or backtracking algorithms (like Perl regular expressions). Why is this the case? Is the technique I mentioned too slow? Is it missing functionalities? Does anybody know what the complexity of regular expression matching using derivatives is?

# Answer
> 4 votes
Yes. This approach has been used before. I've seen it used in a research project, where the goal was to build a regexp matcher that could be formally verified to be correct (with as little effort as possible). This algorithm was implemented in Coq and then proven correct. The nice thing is that it is relatively easy to prove correct. In contrast, a table-driven lexer would be harder to prove correct, because one would have to prove that the table was constructed correctly.

I *think* that table-driven lexers are often faster in practice. Your scheme essentially computes the transition table on the fly. Table-driven lexers involve pre-computing the transition table, and now you only need to do a few instructions per character read from the input (read one character, do a table lookup based on the current state and just-read character, update the current state). Therefore, their constant factor can be lower.

To be clear, by table-driven lexer, I mean something that converts the regexp to a DFA and then precomputes a table that represents the transition table. This is useful in cases where the regexp is fixed and known at compile time. For many regexps seen in practice, the size of the DFA is not too large and so this leads to a fairly efficient matcher algorithm.

# Answer
> 4 votes
The principal reason is the performance. Such a direct use of derivatives would be slower than any DFA-based matchers because constructing a DFA already corresponds to a pre-computation of derivatives. Besides the original paper of Ken Thompson (Regular expression search algorithm, 1968) states that the algorithm is an fast parallel implementation of Brzozowski derivatives. So the concept of derivatives was there from the very beginning.

In short, by analogy, if DFA construction is the compilation of a regular expression, then matching with derivatives is the interpretation.

For complexity results one can check the paper "Testing Extended Regular Language Membership Incrementally by Rewriting" by Grigore Rosu and Mahesh Viswanathan (2003).

# Answer
> 1 votes
Derivatives do have some important advantages in practice over competing approaches.

Firstly, while *matching time per element* is typically slower with derivatives than with a DFA, *compile time* can be completely avoided. This is because derivatives work on regexes syntactically, so they don't need to be converted to any other representation. For example, in cases where NFA to DFA conversion blows up, derivatives avoid the blowup. They dynamically and lazily update the regex as the input string is read in, which may result in finding the match without actually compiling the entire (exponentially large) state space.

This advantage particularly shows up on *regexes with complex features*, such as counting loops (e.g. `.{200}` to match a sequence of 200 characters), which are typically allowed in practical regex libraries. Compiling regexes with such features to DFAs is typically very inefficient and can hang on bad examples. Using derivatives, the derivative expressions that result typically remain simple even though the full state space might be exponentially large or worse.

Finally, compared with many implementations of regexes based on backtracking, derivatives do not backtrack and so enjoy linear-time matching. They share this advantage with DFA-based approaches. The desire to avoid expensive backtracking (and hence, potentially hanging on bad regex examples) was the motivation behind Google's RE2 matcher, which is based on DFAs.

Due to these advantages and others, there is interest in using derivatives for practical regex matching, though it may not be mainstream. For an example of a real implementation based on derivatives, see the Symbolic Regex Matcher from Microsoft (Veanes, Saarikivi, Wan, and Xu).

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


# Question
Title: How to prove that this problem is NP-complete (or NP-Hard)
I have the following data:

* A set $V$ of tasks, the starting time $s\_j$ of each task and the duration $p\_j$ of each task.
* A set $K$ of resource, each resource has an availability function $R\_{k}$ that is piecewise constant.That is, for each $t = 0, .., T-1$, we precise $R\_{k}(t)$ the number of units available at $t$. $R\_k$ is an array of length $T$.
* Each task $j$ needs $r\_{j,k}$ resources to be processed (it could be zero). This quantity needs to be available during all the processing time starting from $s\_j$.

For example consider :

* Task$A$ has processing time $3$ and starts at time period $t=2$ and needs 2 units of some resource $k$
* Task $B$ has processing time $4$ starts at time $t=3$ and needs 3 units of the same resource $k$.

Then if $R\_{k}(t) = \[\*,\*,2,6,6,3,\*,\*\]$ then we are ok since at time $t=2$ only task $A$ is active and it requires $2$ units, at time $t=3$, both tasks are active and the sum of their utilization is $2+3 = 5 \leq 6$; same at time $t=4$. At time $t=4$, only task $B$ is active and it requires $3$ units.

However, if $R\_{k}(t) = \[\*,\*,2,4,6,3,\*,\*\]$, is not ok since at time $t=3$, both tasks $A$ and $B$ are active and their total use is equal to $5$ wheras only $4$ units are available.

Here is my attempt to verify that the resource utilization at each $t$ is no larger than the availability function. So the answer is yes or no (we can say that this is a decision problem).

```
For each time t in [0,T-1]
  For each resource k in K
    total_use = 0, active_set = A
    for each task j in V
      if s_j<=t and s_j+p_j > t and r_{j,k}>0 \\if the task is active at time t and it requires positive amount of resource k in order to be processed)
        total_use += r_{j,k}
        active_set := active_set U {j}
      if total_use > R_{k}(t)
        print(at time t the usage of resource k exceeds its capacity, active_set)
        return False
return True

```

The algorithm here is pseud-polynomial. Unfortunately, I need to find a polynomial one in order to say that the problem is in $\mathcal{NP}$.

# Answer
You may think that your algo is pseudo-polynomial because the outer loop repeats $T$ times and the possible size of $T$ grows exponentially with a bit string describing $T$. But notice that $R\_k(t)$ is given for $t\in\[0,T-1\]$ (in your input) meaning that your input grows $\Omega(kT+|V|)$ and the runtime of the algo is $O(Tk|V|)$ (disregarding log factors from the set operations etc.). Hence, the runtime grows polynomial with respect to the input size.

As a result your decision problem lies in $\mathcal{P}$.
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: Why doesn't diagonalization require taking a limit?
When we quantify infinite sums, we do so by taking the limit as $i$ goes to infinity. For example, we look at $\lim\_{n\rightarrow \infty}\sum\_{n\in \mathbb{N}}n$, and then we say that this diverges and does not have a sum.

When we do diagonalization, we iterate over an infinite list while indexing each list item by a natural number, and then talk about the result. Why can we do this instead of having to invoke limits?

In the same way, would it be fine to assign a value to $\sum\_{n\in \mathbb{N}}n$ with the value being an infinite sequence?

# Answer
> 2 votes
Some diagonalization arguments might require limits to be able to nail down *all* the details (e.g. if they involve an infinite sum, or an infinite decimal expansion, which is formally just an infinite convergent sum of a certain kind), but they do not require limits in general.

The most popular diagonalization argument proves that $|\mathbb{N}| \neq |\mathbb{R}|$. Depending on how you've seen this, resolving some of the details *might* end up requiring limits because of the nature of $\mathbb{R}$. So let's look at a decidely discrete example of diagonalization instead:

### Theorem $|\mathbb{N}| \neq |\\{0, 1\\}^\mathbb{N}|$

We take $\\{0, 1\\}^\mathbb{N}$ to be the set of all infinite sequences of ones and zeros (you can also think of it as the function space $\mathbb{N} \to \\{0,1\\}$). So for example, we could have the sequences $a = (0, 1, 0, 1, 0, 1, 0, 1, \cdots)$ such that $a\_{2i} = 0$ and $a\_{2i+1} = 1$.

Since this is a diagonalization argument, we proceed via contradiction. We first assume that it's possible to enumerate all elements of $\\{0, 1\\}^\mathbb N$ via some function $f$, so that for all $i \geq 0$, $f(i)$ is an infinite sequence of 0s and 1s.

We will construct an explicit infinite sequence which doesn't show up in the image of $f$, which proves that no such $f$ can enumerate all infinite sequences of 0s and 1s, which means that $|\mathbb N| \neq |\\{0,1\\}^\mathbb N|$ as desired:

$$ a\_i \triangleq 1 - f(i)\_i $$

And now we can immediately see by construction that for each $i \geq 0$, $a \neq f(i)$, since if $a = f(i)$ then for all $k$, $a\_k = f(i)\_k$, but in particular for $k = i$ we have $a\_i = 1 - f(i)\_i \neq f(i)\_i$. $\blacksquare$

---

This construction clearly doesn't involve any limits - all of the objects are discrete. The equivalent complete proof specifically for $\mathbb R$ might involve a limit or an (easy and automatic) proof of convergence for the construction of the real number $a$, but there's nothing particularly insightful about that step.

---
Tags: proof-techniques, mathematical-analysis
---


title: Sampling from the uniform distribution

text:
# Question
Title: Sampling from the uniform distribution
Is there an efficient classical algorithm that generates samples from the uniform distribution (or a distribution that is close to the uniform distribution in total variation distance), over the set $\\{0, 1\\}^{n}$, for a fixed $n$?

We can easily express the uniform distribution in terms of a formula:

$Pr(X = x) = \frac{1}{N}$, for each $x \in \\{0, 1\\}^{n}$ and $N = 2^{n}$.

My guess is that any distribution that can be expressed in terms of an explicit formula can be efficiently sampled from, but I can't find a concrete proof.

# Answer
> 1 votes
Sure, just sample $n$ bits, concatenate them, and output the result.

---
Tags: probability-theory
---


# Question
Title: What is the "continuity" as a term in computable analysis?
# Background

I once implemented a datatype representing arbitrary real numbers in Haskell. It labels every real numbers by having a Cauchy sequence converging to it. That will let $\mathbb{R}$ be in the usual topology. I also implemented addition, subtraction, multiplication, and division.

But my teacher said, "This doesn't seem to be a good idea. Since comparison is undecidable here, this doesn't look very practical. In particular, letting division by 0 to fall in an infinite loop doesn't look good."

So I wanted my datatype to extend $\mathbb{Q}$. Since equality comparison of $\mathbb{Q}$ is decidable, $\mathbb{Q}$ is in discrete topology. That means a topology on $\mathbb{R}$ must be finer than the discrete topology on $\mathbb{Q}$.

But, I think I found that, even if I could implement such datatype, it will be impractical.

# Proof, step 1

Let $\mathbb{R}$ be finer than $\mathbb{Q}$ in discrete topology. Then $\\{0\\}$ is open in $\mathbb{R}$. Assume $+ : \mathbb{R}^2 → \mathbb{R}$ is continuous. Then $\\{(x,-x): x \in \mathbb{R}\\}$ is open in $\mathbb{R}^2$. Since $\mathbb{R}^2$ is in product topology, $\\{(x,-x)\\}$ is a basis element of $\mathbb{R}^2$ for every $x \in \mathbb{R}$. It follows that $\\{x\\}$ is a basis element of $\mathbb{R}$ for every $x \in \mathbb{R}$. That is, $\mathbb{R}$ is in discrete topology.

# Proof, step 2

Since $\mathbb{R}$ is in discrete topology, $\mathbb{R}$ is computably equality comparable. This is a contradiction, so $+$ is not continuous, **and thus not computable**.

# Question

What is bugging me is the bolded text. It is well-known that every computable function is continuous (Weihrauch 2000, p. 6). Though the analytic definition and the topological definition of continuity coincide in functions from and to Euclidean spaces, $\mathbb{R}$ above is not a Euclidean space. So I'm unsure whether my proof is correct. What is the definition of "continuity" in computable analysis?

# Answer
> 8 votes
Different people have different views on what the definition of continuity should be, but the way I see it, we should define continuity to be computability relative to some oracle. For example:

**Definition**: A function $f : \mathbf{X} \to \mathbf{Y}$ is continuous, if there is a computable partial function $F :\subseteq \mathbf{X} \times \mathbb{N}^\mathbb{N} \to \mathbf{Y}$ and some $p \in \mathbb{N}^\mathbb{N}$ such that $f(x) = F(x,p)$.

So the most primitive concept in handling a space is what representation we are using for it, which then yields the notion of computability, and from that we get the notion of continuity.

So far, the definition of continuity seems rather unrelated to continuity from topology, and one may wonder why that term has been chosen. One reason is that we usually use *admissible representations*, which have the characterization that the functions between them which are continuous in the computable analysis definition are exactly the functions which are continuous in the topological sense.

If we have an admissible representation $\delta : \subseteq \Sigma^\mathbb{N} \to \mathbf{X}$, we get the topology on $\mathbf{X}$ as the final topology along $\delta$, i.e. a set $U \subseteq \mathbf{X}$ is open iff there is a set $W$ of finite words such that $\delta^{-1}(U) = \operatorname{dom}(\delta) \cap \bigcup\_{w \in W} w\Sigma^\mathbb{N}$. Matthias Schröder has shown that the topological spaces which have admissible representations are exactly the $T\_0$ quotients of countably-based spaces.

Now to slowly come back to the starting point of your question, what prevents us from using the discrete topology on the reals? The reason we cannot do that is that every countably-based space is separable, ie has a (countable) dense sequence. Taking quotients preserves being separable, so every topology associated to a representation is necessarily separable. A discrete space is separable iff it is countable, so we cannot get the discrete topology on the reals.

There is a way to get an admissible representation of $\mathbb{R}$ that makes $\mathbb{Q}$ a discrete subspace (essentially, treat $\mathbb{R}$ as $\mathbb{N}^{\*} \cup \mathbb{N}^\mathbb{N}$), but as you have argued in the question, that makes addition uncomputable (and overall, has very little resemblance to the reals as we would want them).

On a side note, that we cannot avoid getting stuck without even recognising it when accidentally trying to divide by $0$ is a significant obstacle if we are trying to do linear algebra with real numbers.

**References**:

Pieter Collins: Computable analysis with applications to dynamic systems. Math. Struct. Comput. Sci. 30(2): 173-233 (2020)

Martín Hötzel Escardó: Synthetic Topology: of Data Types and Classical Spaces. Electron. Notes Theor. Comput. Sci. 87: 21-156 (2004)

Takayuki Kihara, Arno Pauly: Dividing by Zero - How Bad Is It, Really?. MFCS 2016: 58:1-58:14

Arno Pauly: On the topological aspects of the theory of represented spaces. Computability 5(2): 159-180 (2016) arXiv

Matthias Schröder: Extended admissibility. Theor. Comput. Sci. 284(2): 519-538 (2002)

# Answer
> 8 votes
Arno's answer provides some very useful background reading material, I would just like to address your specific question about $\mathbb{R}$.

Let us first recall a result by Peter Hertling, see Theorem 4.1 in A Real Number Structure that is Effectively Categorical (PDF here), about computable structure of the real numbers. Suppose we have a representation of $\mathbb{R}$, i.e., a data structure representing the reals, such that:

* $0$ and $1$ are computable elements of $\mathbb{R}$,
* the field operations $+$, $-$, $\times$ and $/$ are computable (where division by zero is of course undefined)
* the limit operator, taking a rapid Cauchy sequence to its limit, is computable (a sequence $(x\_n)\_n$ is rapid when $|x\_n - x\_m| \leq 2^{-\min(m,n)}$).
* the strict order $\<$ is semidecidable

The above conditions simply state that the reals should be a computable Cauchy ordered field, which is pretty much the computable version of the usual chracterization of reals (the Archimedean axiom holds as well, as it turns out).

Then it follows that:

1. The topology of $\mathbb{R}$ is the standard Euclidean topology
2. Equality is undecidable, or equivalently, testng for zero is undecidable.
3. Any two such structures are computably isomorphic.

These are unavoidable facts. Your teacher may think that not having decidable equality is unfortunate, or that division by zero should report an error, but *that is impossible to arrange* if one wants to keep the computable structure of the reals.

Regarding your implementation: it is vital that you represent a real with a Cauchy sequence *together with* information on how fast it converges. I hope you did that.

---
Tags: computability, mathematical-analysis, topology, computable-analysis
---


title: How does f(n) < cg(n) specify time?

text:
# Question
Title: How does f(n) < cg(n) specify time?
I have been reading this tutorial on time complexity, and I am a bit puzzled on its explanation of big $O$ notation. It writes:

> $O(g(n)) = $ { $f(n)$ : there exist positive constants $c$ and $n\_0$ such that $0 \leq f(n) \leq c\*g(n)$ for all $n \> n\_0$.

The way I understand it, $c\*g(n)$ denotes $c$ multiplied by $g(n)$. If this is the case, then how does the above expression specify time, and not just that $c\*g(n)$ is greater than $f(n)$? Or am I incorrect, and this is some notation I don't understand? My understanding of time complexity is very rudimentary, so forgive me if this is just a stupid mistake on my part.

# Answer
> How does f(n) \< cg(n) specify time?

It doesn't. Bachmann-Landau notation is simply a handy way to compare the growth-rate of functions. It doesn't say anything about *what those functions mean*, and we can be pretty sure that Bachmann wasn't thinking about computers when he came up with it in 1894.

*What meaning* you assign to those functions is up to you. For example, when analyzing comparison-based sorting algorithms, we typically take $n$ to be the number of elements in the collection and $f(n)$ to be the number of comparisons, or the number of swaps, or the number of comparisons and swaps.

Note also that all of this is always relative to a machine model or a cost model.

As a very simple example, if I were to ask you what is the algorithmic worst-case step complexity for copying a list, you would say $O(n)$. But actually, the *correct answer* would be "I can't tell you that because you haven't specified the machine model". Because, for example, in a Turing machine, copying a list is $O(n^2)$, because for each element being copied, the head of the TM has to drive further and further and further to reach the end of the list to write the next element.
> 2 votes

# Answer
Saying that the running time of an algorithm is in $O(g(n))$ gives, as you noted, only an upper bound. Moreover, the upper bound is given with the constants $c$ and $n\_0$ unknown. So yes, it is a rather weak information about the running time.

The unspecified constant $c$ can contain the information about the real cost of the basic operations of the algorithm, which can be unknown and/or variable between runs, but still known to cost an amount of time that is bounded. The unspecified constant $n\_0$ reflects that the bound given refers to large sizes of the input (or whatever parameter $n$ is representing).

Other symbols are used to give other types or more precise information about the running time.
> 1 votes

---
Tags: time-complexity, big-o-notation
---


# Question
Title: Difficulty understanding the use of arbitrary function for the worst case running time of an algorithm
In CLRS the author said

"Technically, it is an abuse to say that the running time of insertion sort is $O(n^2)$, since for a given $n$, the actual running time varies, depending on the particular input of size $n$. When we say “the running time is $O(n^2)$,” we mean that there is a function $f(n)$ that is $O(n^2)$ such that for any value of $n$, no matter what particular input of size $n$ is chosen, the running time on that input is bounded from above by the value $f(n)$. Equivalently, we mean that the worst-case running time is $O(n^2)$. "

What I have difficulties understanding is why did the author talked about an arbitrary function $f(n)$ instead of directly $n^2$.

I mean why didn't the author wrote

"When we say “the running time is $O(n^2)$,” we mean that for any value of $n$, no matter what particular input of size $n$ is chosen, the running time on that input is bounded from above by the value $cn^2$ for some +ve $c$ and sufficiently large n. Equivalently, we mean that the worst-case running time is $O(n^2)$".

I have very limited understanding of this subject so please forgive me if my question is too basic.

# Answer
I think that the point that the authors are trying to make is the following:

> The exact running time depends on the input.

When we say that the running time of insertion sort is $O(n^2)$, what we really mean is:

> The worst-case running time of insertion sort is $O(n^2)$.

Actually, we could be even more verbose, and mention that by *worst-case* we mean worst case with respect to the length of the array:

> The worst-case running time of insertion sort, in terms of the length $n$ of the input, is some function $f(n)$ which belongs to the class $O(n^2)$.

This is *equivalent* to the following claim:

> There exists $C$ such that insertion sort takes time at most $Cn^2$ when running on an input of length $n$.

Note that there is no need to specify a lower bound on $n$ – if the running time is bounded by $C\_1n^2$ for all $n \geq N$, then it is bounded by $C\_2n^2$ for all $n \geq 1$. You can take $C\_2$ to be the maximum between $C\_1$ and the worst-case running times on inputs of length at most $N$.
> 2 votes

---
Tags: time-complexity
---


title: On the proof techniques of Udi Manber

text:
# Question
Title: On the proof techniques of Udi Manber
I was familiar with the approach of first coming up with an algorithm, and then proving the loop invariant to come up with an algorithm as elucidated in CLRS (Introduction to algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein). Lately, on reading Udi Manber's introduction 'A creative approach' I have come across the idea of positing and algorithm and then proving it using induction and also getting the algorithm itself. It's like having your cake and eating it too.

There is one question which remains inexplicable to me. When I am proving an algorithm using Udi Manber's approach, am I arguing in the object language or in the meta language? In either of these cases, how am I just generating a proof? From the meta language it seems sensible to generate a proof in the object language, but arguing the soundness/completeness of these class of arguments appears difficult. But how do I guarantee that the proof is correct in the object language if it is generated by the object language itself? It is unclear to me if it is the metalanguage or the object language that is involved in here.

This question might seem poorly phrased, but I cannot find a better way to express it. Udi Manber's approach seems to generate an algorithm despite not knowing a priori what the algorithm itself is. This is something counter intuitive to me. Please kindly explain.

# Answer
> 1 votes
It is not a rigorous answer, but if we are to posit in the way of Udi Manber using induction, we are tacitly positing a recursively enumerable algorithm that can terminate. Udi Manber's algorithmic approach though does not necessarily posit a primitive recursive algorithm. If the problem in our class is not recursively enumerable, then we cannot use Udi Manber's approach, and it may as well be uncomputable. A primitive recursive algorithm is likely to be more efficient than a recursively enumerable one.

---
Tags: algorithms, proof-techniques
---