# Question
Title: What are the recents topics of research that combine both systems research and theoretical computer science?
I am an undergraduate majoring in Computer Science and Mathematics. For my undergraduate research, I would like to work on something that lies in the overlap between systems research and theoretical computer science. Something that could satisfy this requirement is *cache-oblivious algorithms* because it is about the analysis and design of algorithms without completely ignoring how actual systems work (memory hierarchy and so on). But there could be many other fields in systems research which involve a lot of theory, or vice versa.

One of my seniors suggested *distributed systems* \- he seemed to indicate that things like Paxos and Raft have a lot of underlying theory, but I haven't taken the time to dig into it.

You could also suggest some field in systems research which can gain a lot from some rigorous mathematical foundations and analysis. A senior will be going to graduate school at Johns Hopkins University to do a PhD on the math behind deep learning. So maybe I could try something like "the math behind --some systems research field--".

Another example I found is "Distributed Computing using Combinatorial Topology".

**TL;DR: What fields/topics of research lie in the intersection of theoretical computer science and systems research?**

# Answer
> 2 votes
This might not be what you mean by "theoretical computer science", but there's some rich interaction between Programming Languages Theory and Distributed systems going on with Session Types. They basically are a way to use type systems to specify communication protocols, increasing safety in distributed languages.

For example, The Imperial Mobility Group has many publications in session types, this should at least get you started on finding research in the area.

---
Tags: algorithms, complexity-theory, operating-systems, distributed-systems, research
---


title: Solving recurrences by substitution

text:
# Question
Title: Solving recurrences by substitution
I'm going through Cormen et al.'s Introduction to Algorithms and I am a little thrown off by some of the subtleties of solving recurrences with the substitution method. Given the recurrence:

$$ T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + 1, $$

We guess that the solution is $T(n) = O(n)$. Thus we try to show that $T(n) \le cn$. By substituting our guess, we are left with,

$T(n) = cn + 1$, which is not $\le cn$.

Makes sense. But then in the next paragraph, he writes that if we guess for $T(n) = O(n^2)$, we can make the solution work. However, wouldn't the solution still be off by a constant of 1, since:

$$T(n) = O(n^2) = 2c(n/2)^2 + 1?$$

Or am I not substituting correctly for $O(n^2)$? Seems like I'm missing something trivial about this.

# Answer
> 2 votes
Assuming for simplicity that $n$ is even, if we guess that $T(n) \leq C^2n$ then we can prove our guess by induction (for powers of 2) for an appropriate value of $C$ since $$ T(n) = 2T(n/2) + 1 \leq C(n/2)^2 + 1 = \frac{C}{4} n^2 + 1 $$ is smaller than $Cn^2$ as long as $C \geq 4/3$ (assuming $n \ge 1$).

# Answer
> 1 votes
It's worth noting that the substitution method is a alternative name for proof by induction. So, in the end, **(1)** you need to get exactly the same hypotheses. Also, it needs to **(2)** work for all $n$.

For example, using the hypoteses $T(n) \leq cn^2$,

\begin{eqnarray\*} T(n) &=& T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + 1 \\ &\leq& c (\lfloor n/2 \rfloor)^2 + c(\lceil n/2 \rceil)^2 + 1 \\ &=& c \frac{(n-1)^2}{4} + c\frac{(n+1)^2}{4} + 1 \quad\quad\quad (\textrm{assuming $n$ odd})\\ &=& c \frac{n^2-2n+1}{4} + c\frac{n^2 +2n +1}{4} + 1 \\ &=& \frac{cn^2+c+2}{2} \\ &\leq& cn^2 \quad\quad\quad(\textrm{if } c \ge 2/(n^2-1))\\ \end{eqnarray\*}

Note that, in the last line, **(1)** you got exactly the same hypotheses. You also need that **(2)** it works for all $n$, but this proof only works for $n$ odd. So, in a similar way, you can do the rest of the proof for the even case. Only after that you have finished the induction proof.

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Do NFAs with $\varepsilon$-moves never terminate?
Suppose in an NFA we have an $\varepsilon$-move from a state $q\_0$ to $q\_1$. According to Sipser,

> Without reading any input, the machine splits into multiple copies one following each of the exiting $\varepsilon$-arrows and one staying at the current state. Then the machine proceeds nondeterministically as before.

Here is an application of this logic to our case: upon reaching the state $q\_0$ our machine splits into two copies: one in state $q\_1$, one in state $q\_0$. For the latter copy, execution continues as before, so again another copy of the machine is created in state $q\_0$. Thus, a copy of the machine always in state $q\_0$ will exist indefinitely.

Is this true? If no, why not? How should I then interpret the description given above?

# Answer
Sipser proposes an operational intuition for non-determinstic machines. As you have experienced, it's not very useful. In particular, it doesn't relate a lot to the formal definition, and there are more problems down the road¹.

I recommend sticking to the definition: an NFA accepts an input if there is a path from a starting to a final state labelled with the input. That really tells you all you need to know, and all there *is* to know.

Try to think mathematically instead of computationally.

---

1. Parallelism and non-determinism are not the same; you can not *build* non-deterministic machines in a meaningful sense; cost models (e.g. in complexity theory) for non-deterministic machines don't make sense if you have the split/fork intuition; ...
> 3 votes

# Answer
This is not true. The key to interpreting the quoted description correctly is noting that the splitting occurs **without reading any input**. So when we arrive at $q\_0$, we split into two copies with the same input string left to be read, one in the state $q\_0$, the other in the state $q\_1$.

After the splitting, however, we have to continue reading the input string. So if $q\_0$ does not have any other moves from it, the computation is simply stuck at $q\_0$ and that branch of computation dies.
> 2 votes

---
Tags: computability, finite-automata, nondeterminism
---


# Question
Title: Find the computational complexity of a concatenated system
I have a network which includes $L$ blocks ($B\_1,\cdots,B\_L$) connected one after the other. I have an algorithm having computational complexity $\mathcal{O}(N)$ which runs in each block individually.

I first run the algorithm on $B\_1$ and get the output. Based on that output, I select the second data set in $B\_2$. Then run the same algorithm on $B\_2$ and get the output, and so on till $B\_L$. The important thing is that the present data set depends on the previous block output.

Now I want to know the overall system complexity. I guess it is $\mathcal{O}(LN)$. Is that right?

# Answer
> 1 votes
To summarize what you're saying:

* You have an algorithm that runs in $O(n)$.
* You're running it on $L$ different blocks, sequentially (no parallelism).
* Every block has size $N$.

In this case, the total running time is indeed $O(LN)$.

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


# Question
Title: Using a 2nd neural network to predict 1st neural network prediction error
So for example, we are trying to predict the amount of rainfall in the afternoon base on continuous features such as humidity and temperature in the morning.

1st neural network: Regression neural network on features to give one output label which is a continuous value for predicted rainfall in the afternoon.

2nd neural network: Features will be the same as the 1st neural network. But now, the label will be the absolute difference between the 1st neural network predicted rainfall and the actual rainfall.

From this, we can train the 2nd neural network to recognise what particular set of features will result in the 1st neural network giving a 'bad' prediction and be more wary of that 'bad' prediction. In a way, this is like using another neural network to give the confidence level of the first neural network, solely based on the same features (the humidity and temperature in the morning).

I could not find much literature on this subject and am wondering if this idea makes sense in the first place? Perhaps stacking neural networks over each other is a bad idea because it compounds the error from one network to another?

I tried this with some data except my 2nd neural network is a classifier which classifies if the error is above a certain threshold (bad prediction) or below a certain threshold (good prediction).

However, from a few different model runs, it seems that my 2nd neural network usually gives a matthew's correlation coefficient of about 0. This means my 2nd neural network is as good as guessing whether the 1st neural network prediction is good or bad.

So I am not sure if the problem is the idea itself or that my model hyperparameters are bad.

More details: I used 10 fold cross-validation for the 1st model to get a predicted rainfall for all the data. Then I used another separate 10 fold cross-validation and a siamese neural network for the 2nd model to predict whether the 1st neural network prediction is good or bad.

# Answer
> 1 votes
It's not an unreasonable approach, but I suspect you'd need to define a custom loss function to make it work well.

I can also suggest two different, more sophisticated approaches: the bootstrap, or a variational neural network.

In the bootstrap, you train many classifiers (say, 100 of them); each is trained on a different random sample of the training set, and then you look at the distribution of outputs from these classifiers when you feed in the input $x$ to each of them.

In a variational network, instead of outputting a single number $y$ for the prediction in response to the input $x$, the network outputs two parameters $(\mu,\sigma)$, with the idea that the network is predicting a Gaussian distribution $\mathcal{N}(\mu,\sigma^2)$ as an approximation for $p(y|x)$. Then you can use this to get a sort of confidence interval for the prediction, e.g., $\[\mu-2\sigma,\mu+\sigma\]$. I'm not an expert on this, but I think a variational network is actually very close to what you suggested; we can think of it as two networks, one that outputs $\mu$ (your first network) and one that outputs $\sigma$ (your second network). However, variational networks are trained with a special loss function. In particular, if we have an instance $(x\_i,y\_i)$ in the training set, the loss for the network is the log likelihood $-\log p(y\_i)$ where here $p(y\_i)$ represents the probability of getting the output $y\_i$ from a Gaussian distribution with parameters $\mathcal{N}(\mu,\sigma^2)$, where $\mu,\sigma$ are the two outputs from the network. Since the Gaussian distribution has probability density function

$$p(y\_i) = c e^{-(y\_i-\mu)/2\sigma}$$

where $c$ is a constant. Therefore, the loss function is

$$-\log p(y\_i) = (y\_i-\mu)/2\sigma + c'$$

where $c'$ is a constant that can be ignored. Thus, I think you can think of the variational approach as being equivalent to your approach, but with a custom loss function chosen to be appropriate for what you're trying to achieve.

---
Tags: machine-learning
---


# Question
Title: If it's Possible to Create the If-Statement from Simpler Primitives
This question is about how to create an `if` statement (one of the control-flow statements) from scratch.

An if-statement is typically a built-in construct in languages. However, I am wondering if there is a way to construct an if-statement from some other non-control-flow primitives. I am also wondering how to do this with Boolean algebra, and there is a link there to how to represent `if/else` statements with circuits.

I started off trying like this:

```
var x = true
var run = {
    true: [],
    false: []
}
var state = []
while (true) {
    x = !x
    var arr = run[x == true]
    for (var i = 0, n = arr.length; i < n; i++) {

    }
}

```

That `x` toggle seemed like it could be used to somehow shift the evaluation path. Then in the `state` array there would be states of the application listed, and so the application would go into that state *if* the `x` was 0 vs. 1. But there pops up the `if` right there, so it's hard to make it work without resorting to `if` somewhere. The `for` loop is also a form of control-flow, so would hope to avoid that.

Was going to try to test it out to simulate a program such as this:

```
if (a == 1) {
    if (b == 1) {
        console.log('1.1')
    }

    if (b == 2) {
        console.log('1.2')
    }
}

if (a == 2) {
    if (b == 1) {
        console.log('2.1')
    }

    if (b == 2) {
        console.log('2.2')
    }
}

if (a == 3) {
    if (b == 1) {
        console.log('3.1')
    }

    if (b == 2) {
        console.log('3.2')
    }
}

```

The program would then run:

```
myiftest(1, 1) // a == 1, b == 1
myiftest(1, 2)
...

```

There are ways to sort of cheat, such as using `&&` to hack the conditional. For example:

```
a == 1 && b == 1 && console.log('1.1')

```

You could also do it with a `while` loop:

```
while (a == 1 && b == 1) {
  console.log('1.1')
  break
}

```

I would like to see if there's any way to do this using only non-control-flow statements in JavaScript (or in C, Ruby, or Python, any modern iterative language, or even Assembly which might make it easier), i.e. not cheating like the above. I don't even know if it's possible, so any form that shows it is possible (or not possible!) would be great to know.

It's okay to use the `while(true)` loop to start it out, so the program actually runs (if necessary).

---

Even in assembly the "if" statement is built into the `jmp` or jump-/branch-related statements.

# Answer
> 1 votes
This is perhaps most clear at the assembly level.

There is an instruction pointer, which normally moves to the next instruction after executing the current one.

Any instruction that interferes with that behavior is, by definition, a control flow instruction.

Conversely, if no instruction can have an effect to alter the instruction pointer, the program has to run sequentially: the first command, then the second, ..., all the way until the last.

# Answer
> 2 votes
Contrary to what you (and many people) may think, in the field of programming languages, the most primitive control-flow operation is actually **pattern matching**!

With a simple type system (say the simply-typed lambda calculus) plus unit types and sum types, you can encode the boolean type easily. Let $\mathbf{1}$ be the unit type. The boolean type is simply $\mathbf{1} + \mathbf{1}$, i.e. the sum of two unit types (because each variation has exactly one inhabitant, respectively "true" and "false").

Now, when we get a sum type, we can destruct it by pattern matching. That is, for each branch of the sum type, we return a different expression. This is the most basic control-flow operation! The expression `if b then et else ef` is simply sugar for:

```
match b with
| left -> et
| right -> ef

```

Interesting, isn't it?

Of course, this is not how machines work, but from a lambda-calculus/type theory standpoint, pattern matching is the father of all conditional execution!

---
Tags: algorithms, boolean-algebra, iteration
---


# Question
Title: What is the relation between Time Sharing operating systems and Round Robin CPU scheduler?
So i have asked this before, but i still didn't get my answer so I'll try to make my question more clear this time :

Based on my O.S book, Time sharing operating systems switch between processes very fast using a time slice and it uses interrupts when the time slice ends and switches to another process, so isn't this the definition of round robin CPU scheduling algorithm? so are they saying Time sharing O.S uses Round Robin cpu scheduling or what?

if not, then what is the relation? for example what happens if our O.S is time sharing and uses Round Robin cpu scheduling vs when it uses another algorithm like FCFS?

# Answer
No. A time-sharing computer switches between processes in some way or other. A time-sharing computer with round-robin scheduling switches between processes in a particular way. For instance, suppose there are three processes, A, B, and C. A round-robin scheduler would switch between them in the order ABCABCABCABC etc. Some other scheduler might switch between them in the order AABAABAACAABAABAAC (for instance). Both are examples of time-sharing, but the latter is not a round-robin scheduler.

I suggest reading https://en.wikipedia.org/wiki/Scheduling\_(computing).
> 1 votes

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


# Question
Title: A Turing Machine that Doesn't Move to the left
My question is if the following statement is true or false:

> Does every turing-recognized $B$ language has a turing machine $M$ that recognizes $B$ and fullfiles the following statement:
>
> For every word $w$ the belongs to $B$, $w \in B$, the writing-reading head **never moves to the left**?
>
> Notice that the condition is required only for words in the language. if $w \notin B$ then the head can move to the left as usual.

The statemet seems correct to me. I think I can simulate a regular $TM$ with this "special" $TM$, while saying that every time the head moves left, it will stay put. Couldn't prove it, though.

# Answer
### False.

A Turing machine that can't move left can never write information on the tape, then go back to read it later. In other words, it can't store any information; it has no memory apart from its state.

This makes it into a finite state machine, which is significantly weaker than a Turing machine. (As `ratchet freak` points out in the comments, a finite state machine can't recognize the language $\\{ 0^n 1^n | n \in \mathbb{N} \\}$, while a Turing machine can.)

Note, however, that some Turing machines have multiple tapes. If you have another tape available, and can move left on that one, then there's no problem: just run once over the original tape and copy it onto your working tape, then run as normal, without ever moving the original head backward.
> 3 votes

# Answer
If you only allow moving right (and no external memory), all your TM "knows" about the input already seen is the *finite* amount of information in its state. I.e., it can't do more than a finite state automaton.
> 2 votes

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


# Question
Title: How to describe an algorithm whose input size diminishes by 1 for each iteration
To elaborate on the title: I have a recursive algorithm whose input is reduced by 1 for every iteration until the input size is 1.

1st iteration: n
2nd iteration: n-1
3rd iteration: n-2
4th iteration: n-3
.
.
.
nth iteration: n-(n-1)

How can I describe this in asymptotic notation?

# Answer
On recursive algorithms, you need **first to obtain the recurrence relation**. Then you solve the recurrence to get the total time required by the algorithm.

Let $n$ be the input size. Let $f(n)$ be the time required in each recursive call. Let $b$ be the input size for the base case. A general recurrence relation might look like this

$$ T(n) = T(n-1) + f(n) \quad \quad \textrm{if } n \> b \\ T(n) = c \quad \quad \quad \quad \quad \quad \quad \quad \\;\ \textrm{if } n = b $$ where $c$ typically is a constant (because typically the base case takes constant time).

So, you need to figure it out the function $f(n)$, which is specific for each algorithm. For example, if $f(n)=n$ (e.g. a simple pass on a array), and assuming $b=1$ and $c=1$ (it is not a problem to assume $c=1$ if you are working with assymptotic notation) then

$$ T(n) = T(n-1) + n \quad \quad \textrm{if } n \> 1 \\ T(n) = 1 \quad \quad \quad \quad \quad \quad \quad \textrm{if } n = 1 $$

Solving this recurrence, you have that $$T(n) = n + (n-1) + \ldots + 2 + 1 = \frac{n(n+1)}{2} = O(n^2)$$.
> 2 votes

---
Tags: asymptotics
---


# Question
Title: What is the constant $C$ in the definition of asymptotic notations?
For example in the definition of $\Theta$:

> $f(n) = \Theta(g(n)$ if there exist positive constants $c\_1, c\_2$ and $n\_0$ such that $$ 0 \leq c\_1 \cdot g(n) \leq f(n) \leq c\_2 \cdot g(n) \text{ for all } n \geq n\_0. $$

I was scratching my head for two weeks since we took this definition in class. Why do we need this constant anyways? Shouldn't we get rid of all constants because they aren't significant?

Why can't we just say $g(n) \leq f(n) \leq g(n)$?

# Answer
The basic idea of asymptotic notation is that "constant factors shouldn't matter". This has several different interpretations. Taking as our example big O, the simplest interpretation is:

> For all $C,D\>0$ and functions $f,g$: $$ f = O(g) \Longleftrightarrow Cf = O(Dg). $$

This means that big O should be scale-invariant, that is, it should treat the functions $f$ and $Cf$ exactly the same. Stated differently, if $f\_1,f\_2$ differ by a constant factor, then $f\_1,f\_2$ should be treated the same.

In practice, the condition "$f\_1/f\_2=\text{const}$" is too restrictive. Instead, we would like to treat two functions $f\_1,f\_2$ in the same way as long as $f\_1/f\_2$ is *bounded*, that is, as long as $C\_1 \leq f\_1/f\_2 \leq C\_2$ for some constants $C\_1,C\_2\>0$. That is, we would like that

> For all $C\_1,C\_2,D\_1,D\_2$ and functions $f\_1,f\_2,g\_1,g\_2$ satisfying $C\_1 \leq f\_1/f\_2 \leq C\_2$ and $D\_1 \leq g\_1/g\_2 \leq D\_2$: $$ f\_1 = O(g\_1) \Longleftrightarrow f\_2 = O(g\_2). $$

You can check that the definition of big O satisfies this invariance property. The constant in the definition of big O ensures that. Indeed, while $2n \leq n$ doesn't hold, $2n = O(n)$ does hold.

The integer constant – $N\_0$ – in the definition of big O isn't really necessary. It is there so we can accommodate functions which aren't positive or aren't even defined for small $n$. If your functions aren't pathological in that sense, then you can do away with $N\_0$.

For these non-pathological functions (extended to non-integer points), the various asymptotic notations have equivalent definitions in terms of limits:

* $f = O(g)$ if $\limsup\_{n\to\infty} f(n)/g(n) \< \infty$.
* $f = \Omega(g)$ if $\liminf\_{n\to\infty} f(n)/g(n) \> 0$.
* $f = \Theta(g)$ if both these conditions hold.
* $f = o(g)$ if $\lim\_{n\to\infty} f(n)/g(n) = 0$.
* $f = \omega(g)$ if $\lim\_{n\to\infty} f(n)/g(n) = \infty$.
> 2 votes

# Answer
> Why can't we just say $g(n)\leq f(n)\leq g(n)$?

Because the only way that we can have $a\leq b\leq a$ is if $a=b$.
> 2 votes

# Answer
I will strongly rely on the intuition here. Consider two excerpts of codes in C language, that does the same thing.

Excerpt 1:

```
if (a>b) {
    result = x;
} else {
    result = y;
}

```

Excerpt 2:

```
result = a > b ? x : y;

```

Suppose that both excerpts are inside a $n^2$ loop. So, Excerpt 1 runs $4n^2$ instructions, while Excerpt 2 runs $n^2$ instructions. We have a difference of constant $c=4$ between the two cases (even though both excerpts do the same thing).

But the difference between $4n^2$ and $n^2$ is realistic? To answer this, we have to know:

**(1)** both excerpts are translated into different machine instructions? we need to know all the details of the compiler used.

**(2)** what area the specific machine (processor) that we are compiling this?

**(3)** what if we change the language, for example, from C to Java? The algorithm will have the same performance? Again, we need to know the how to answer (1) and (2).

So, if algorithm analysis were to pay attention to all these **technological details**, it would be practically impossible or too tricky to come up with useful conclusions. That's the main reason to use the constant in assymptotic notation. It **hides details like programming languages, compiler, processor,** ... But it still allows to compare different ideas on designing algorithms.
> 1 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: How to efficiently get frequency of subranges and update its values altogether?
I'm trying to solve the following problem:

There are `N` notes in an array (2\<=N\<=105) labeled 0..N-1, all of them initially set to `1`. Then there follows `Q` operations to perform in the array (1\<=Q\<=105).

The task for each operation is:

* Find the most frequent value between the inclusive range `[A,B]`.
* Add that value to all elements in the same range. The new values must be in range \[0..8\], then we take it modulo `9`.

At the end, output all array values.

---

This is the first problem of *"Maratona de Programação da SBC – ACM ICPC – 2017"* here in Brazil, and I'm trying to solve it in the URI Online Judge site. Time Limit: 1 second.

---

First I tried SQRT Decomposition because it looked good, but it's not. This week I came up with a few nice ideas to solve it using Segment Tree. I was so sure my code was perfect... but it wans't. Time limit exceeded again.

I don't have Advanced Data Structures classes, I learn those things by myself. So I'm probably lacking some fancy tree structure that would solve this problem really faster. Please, give me some resource to learn such a structure.

---

Here is an Ideone link to my code. Let me describe the few nice ideas using Segment tree that I mentioned above:

* Storing the difference (delta) instead of values. With that I was able to update the ranges without going to the leaf nodes. And to find value of some node, ex: leaf node `[0,0]` for N=8, I can traverse from root to that node and sum up delta values `[0,7].delta + [0,3].delta + [0,1].delta + [0,0].delta`.
* Store in each node the count of every value \[0..8\] in its descendants and itself. Because each node represents a subrange, then the frequencies can be precalculated.
* Instead of recalculating the subrange array of frequencies, I can rotate it. Ex: If the most frequent note is `3`, the previous quantity of values 2 is now the quantity of values 5, and so on... so rotating makes sense instead of calculating the quantities of descendant nodes again.
* This is the most brilliant, *I think*. Instead of rotating, use the value (calculated using delta since root path) to find which index of the frequency subrange array should be treated as the first index 0.

I spent more than twenty hours over this week since the first version of the segment tree approach. It was not easy to think all the ideas I listed above. I know I'm not the best at it. But I think you can feel how frustrated I am, after getting Time Limit Exceeded in all of my attempts.

I also think I evolved since the Square Root Decomposition approach. The problem is that I am out of ideas to improve it further. If I didn't see that 156 people have already solved it. I would think it is impossible.

Please, share a bit of your knowledge with me. Thanks in advance.

# Answer
> 1 votes
Almost one year later... I tried to solve it today without looking my previous code and I got ACC'ed now. (ideone link)

Reading my question now, I've implemented what I called `delta` and `rotate` in a simpler way. I will try to illustrate.

This is how the segment tree for *N = 5* looks like after `build()`:

My node struct has:

```
int freq[9], i, lazy;

```

The `i` variable is the position circled in red in the picture, it will hold which position of the `freq` array contains the frequency for note `0` (which initially is zero). The `lazy` flag stores pending sums for children (both left and right), blue in the picture.

Now suppose first query for `[1, 2]`. The `query()` function will find nodes `[1, 1]` and `[2, 2]` and the resulting `int fquery[9]` array will have values `[0,2,0,0,0,0,0,0,0]`. The `greatest()` value then is `1`. Ok, this is a simple search.

Now the function `chord()` will update those ranges by setting `lazy += 1` and `i -= 1`:

Note that since those are leaf nodes, the `lazy` property does nothing. Also note that since `i` was decreased, there is no need to update `freq[]` array. This two things were done in the pre-order traversal of the recursive `chord()` function.

Now we update the `freq[]` array of the parents using the post-order traversal of the recursive `chord()` function by calling `update()`, this update function is just a merge of left and right child nodes:

These separation of pre-order and post-order traversal of the recursive call was the main point that I didn't understand last year. I was trying to update the parents out of the recursion track, and it caused me TLE.

Now suppose second query for `[0, 4]`. The `query()` function will find node `[0, 4]` and the resulting `int fquery[9]` array will have values `[0,3,2,0,0,0,0,0,0]`. The `greatest()` value then is `1`.

Now the function `chord()` will set `lazy += 1` and `i -= 1`:

Since we found the desired range in the root, this time we don't have post-order traversal.

Now suppose third query for `[0, 2]`. The `query()` function will find node `[0, 2]`. *But*, we can only reach a node if there is no pending sums. So, we need to resolve the `lazy = 1` flag of node `[0, 4]`. This is what `propagate()` function does:

Note: the `i` value of node `[0, 2]` is `8`.

And the resulting `int fquery[9]` array will have values `[0,0,1,2,0,0,0,0,0]`. The `greatest()` value then is `3`.

Now the function `chord()` will set `lazy += 3` and `i -= 3`:

As previously, we update the `freq[]` array of the parents using the post-order `update()`:

To get the output after all queries, you just need to `propagate()` every node, doing so the leaf nodes will have the final values. You can check the `show()` function.

The output for this example will be: `5 6 6 2 2`. (The first test case in the URI Online Judge).

---

Conclusion: The solution to the problem is a standard segment tree with lazy propagation with each node containing an `int freq[9]` array and an additional index starter holder.

---
Tags: data-structures
---


# Question
Title: Why is the graph inside Graham Scan always planar
One of the ways to prove that Graham Scan constructs convex hull in linear time is using planarity of the graph obtained by running the algorithm. This graph is always planar, so according to Euler's formula the number of edges can never be more than $3\*n$ (where $n$ is the number of vertices). My question is, how do we know that the edges examined by Graham Scan never intersect (hence always form a planar graph)? Here is the screenshot of this being discussed in the course "Computational Geometry" from Tsinghua University (from EdX.org). The lecturer just mentioned it being true, but did not give the proof.

# Answer
The edges examined never intersect because all points are first sorted in terms of angle from the starting point, and then traversed counterclockwise sequentially. By examining edges to each point sorted by their angle counterclockwise and never traversing clockwise (because you stop when you reach the starting node), you ensure that the edges won't interest.

See this for a good visual.
> 1 votes

---
Tags: runtime-analysis, computational-geometry, proof-techniques, planar-graphs, convex-hull
---


title: Task calendar scheduling algorithm

text:
# Question
Title: Task calendar scheduling algorithm
I want to write a scheduling algorithm for the following scenario:

There is a set of tasks to complete, each one with a due date, difficulty (easy, normal, hard) and progress on the task. The idea is that the user specifies the amount of daily hours available to work on tasks, so the algorithm can create a weekly schedule so the user can work in the tasks that require most attention, scheduled within the interval of hours (e.g. from 9:00 AM to 1:00 PM) the user decides. I have thought to require the user to specificate an approximate amount of time it needs to be used to complete each of the tasks.

The criteria would be priorizing the tasks with the nearest due date, highest difficulty and lowest progress first, then go for the tasks with nearest due date, highest difficulty and medium progress afterwards and so on.

What came to my mind was to create a function to calculate the value of a specific task, the higher the value, the more importance it has. With that in mind, sort all tasks by due date and by this calculated value using some greedy technique, but the issue here is what amount of time to dedicate on each task per day.

What kind of algorithm would this be? Is there any solution or book reference?

# Answer
> 0 votes
This issue is simply creating a weighted function modeling the importance of each assignment. The priority function should take into account the difficulty, due date, and other factors you choose with a weighted sum of these factors.

As for the difficulty, my suggestion would be to have a difficulty scale 1-10 that the user chooses, and create your weighted function based on that, so more difficult assignments will have a higher priority.

---
Tags: algorithms, scheduling
---


# Question
Title: Implementing Gauss–Legendre algorithm using arbitrary-length rationals
I am trying to re-implement SuperPI myself in Rust, but the results I get are not very accurate. SuperPI computes pi using the Gauss-Legendre algorithm.

The Gauss–Legendre algorithm is quite simple, but the problem is how to store values with full precision. I store all numbers as arbitrary sized rationals, but I am still getting weird results.

Pseudocode:

```
a0 = 1/1;
b0 = 470832/665857; // an approximation to 1/√2
t0 = 1/4;
p0 = 1;

for i in 0..n {
    a_i+1 = (a + b)/2;
    squared_b_i+1 = a * b;
    b_i+1 = sqrt(squared_b_i+1); // calculated as sqrt(numerator)/sqrt(denominator)
    t_i+1 = t - p * (a_i - a_i+1)^2;
    p_i+1 = 2 * p;
}

let result = (a_n+b_n)^2 / (4t_n);

```

(actual code may be found here)

My implementation has at least two problems:

1. It doesn't matter how good `1/√2` approximation I take (470832/665857 in this example), the algorithm doesn't converge to the correct value.
2. Calculating √(a/b) as √a/√b is not very accurate, because it does ⌊√a⌋/⌊√b⌋ which can introduce a large error.

As a result, my implementation calculates 11 true digits per 20 iterations, while SuperPI does 1M digits.

How do I implement the Gauss–Legendre algorithm efficiently, given the above challenges?

# Answer
> 1 votes
It sounds like you are using arbitrary-precision arithmetic, i.e., you represent each rational number as a ratio $a/b$ where $a,b$ are stored as arbitrary size integers (bignums). If that's the case, that's probably the source of your problem.

Don't do that. That's highly inefficient, because you'll end up with very large integers $a,b$, that may be far larger than needed for the desired precision level; and it'll be imprecise, because of the ⌊√a⌋/⌊√b⌋ problem you mention.

Instead, use fixed-precision arithmetic: each number is represented directly as a number (not a ratio) using a fixed-precision representation. That will be much more efficient and more accurate. It won't have the problem of ⌊√a⌋/⌊√b⌋, since you're not limited to a ratio of integers. You might need to find a library that implements fixed-precision arithmetic, or to implement that part yourself, and you'll probably need to estimate the appropriate precision level based on the number of iterations and the amount of precision achievable with that given precision level.

---
Tags: algorithms, arithmetic, floating-point, mathematical-programming
---


# Question
Title: Algorithm for estimating lossless compression factor
Is there any algorithm for estimating how well certain array of bytes could be compressed in lossless manner?

Usage for me is to automatically choose "best" data reorder method without knowing what compression method end user is going to use. I don't need perfect/optimal result, I just need some kind of numerical result that I can use to compare different permutation runs.

For example string *"AAAABBBBCCCCDDDD"* should compress better than *"ABDABBABCDCCDACD"* but if I use e.g. Shannon Entropy for estimation then I get identical results.

# Answer
In general the only way to know what the compression factor with a particular compression method is to compress the data using that compression method and see what the compression ratio is.

Some compression algorithms have different levels of compression (e.g., 0-9), which allow the algorithm to spend a lot more CPU time to try to get a bit better compression. You might be able to use the compression factor at a lower compression level as a predictor of the compression factor at a higher level, though this won't be perfect.
> 1 votes

---
Tags: algorithms, data-compression
---


# Question
Title: time complexity of erasing repeated entries
This problem involves the time complexity of erasing entries that occur more than once in a list. I think it might be $n \log n$.

# Problem

The input is a finite set $S$ and a finite list $T$ whose entries are in $S$. The size of the input is $n= |S|+ |T|$, where $|T|$ is the length of the list. The output is a list of the elements of $S$ that occur in the list $T$, an output list having no repeated elements of $S$. Does there exist a linear-time, $n p(\log n)$, where $p$ is a polynomial, or subquadratic-time algorithm for this problem?

I would be grateful for any ideas, direction, pseudo-code.

# Answer
The basic algorithm is to first put all the members of S into a hash table $\mathcal{S}$. Then walk down the list T, recording its elements in a hash table $\mathcal{T}$ as you go. If an element has already been recorded in hash table $\mathcal{T}$ then you delete it from T. If an element does not appear in hash table $\mathcal{S}$ then you delete it from T. When you've completed your walk down T, there will be no repeated elements left in it and every remaining element will be a member of S.

Hash table insertions and lookups have amortized O(1) runtime so the whole algorithm scales O(n).
> 1 votes

---
Tags: algorithms, time-complexity, linked-lists
---


# Question
Title: Summing two array using FFT: time complexity analysis
This is the problem :

> Given two arrays of $n$ elements A and B, let's define their sum as $$ A + B = \\{ a + b \mid a \in A \text{ and } b \in B \\}. $$ Calculate $A + A$ in optimal time given that $A\[i\] \in \[1,10n^{1.5}\]$ for all $i$.

In order to solve this problem I used FFT by representing a polynomial in the following way:

$$ p(x) = \sum\_{i=0}^n x^{A\[i\]}. $$

After multiplying this polynomial with itself using FFT in linear time, I get the desired result in $\Theta(n^{1.5} \log n)$ time.

However, basic combinatorics gives us that there are $O(n^2)$ elements in the sum of $A + A$, How can I possibly produce them and copy them to a result array all in less than $O(n^2)$ using FFT?

# Answer
Since all elements are in the range $\[1,10n^{1.5}\]$, all elements $A+A$ are in the range $\[2,20n^{1.5}\]$. So there are $O(n^{1.5})$ distinct elements in the sum. Some of them will be obtained more than once.
> 2 votes

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


# Question
Title: Data structure for a quantity to price multiplier table
Yesterday at work I came across an interesting problem that I wasn't able to figure how to structure properly. I'm relatively new to the field and was wondering if I could get some help around here. What i have here is a table like this:

```
          |1-2| 3-5 | 6+ | ($)
          ________________
          |              |
10 - 100  | x9   x6   x4 |
          |              |
100 - 2000| x5   x3   x2 |
          |______________|

```

Where the columns shows the **base price** and the row shows the **quantity**. The idea here is that the bigger quantity you buy, the better the price. Not only that but we would also reduce the multiplier to items with bigger base price, because otherwise the price could become too high too quickly.

---

The outcome I want to achieve is when given two variables - **base price** and **quantity** to find where I'm standing in the table. This means for each table entry I need two ranges.

Let me give some examples:

* Base price: 1.5$
* Quantity: 200
* Result: x5 (multiplier)

So the actual price will be 7.5$

* Base price: 10$
* Quantity: 15
* Result: x4

So the actual price will be 40$

---

How would you remember the data and how would you write something flexible and scalable so one is able to add and remove table rows easily?

I would evaluate the answers based on how clean the solution is. And by clean I mean easy to use and easy to implement. Currently in our system this table is made from 20 if statements so anything would be better I think!

# Answer
> 2 votes
It's hard to see anything beating the obvious implementation with arrays. You have an array whose columns are indexed by price bands and whose rows are indexed by quantity bands. Store that as a 2D array. Use a pair of 1D arrays to store the minimum value in each price and quantity band. To look up a value, just use linear search through the bands. Binary search would be faster if the array is huge but it's probably not necessary for small arrays (and your "20 if-statements" suggests the array is very small).

Load the data from a file so you can easily rebuild the data structure if you change your discounting schemes. I'm assuming this is a relatively rare event and, with a small table, it takes no time anyway.

# Answer
> 0 votes
Start with the simplest data structure, and use something fancier only if you can show that it will make a performance difference. A two-dimensional array would probably suffice, as would a hashmap (dict) that maps from (row number, column number) to the value in that cell. If you're really worried about adding and removing table rows, you could use a hashmap or treemap that maps from row identifier to a one-dimensional array with the items in that row.

---
Tags: data-structures
---


# Question
Title: STCON in L using matrix multipication algorithm?
I'm trying to understand why the following is **incorrect**.

Given a $STCON$ problem, specifically a graph and nodes $(G, s, t)$, we can assume we are given it's adjacency matrix, $A$. By adding self-loop (filling the main diagonal with $1$'s) we can multiple this matrix with itself n times, each time checking if the $s,t$ entry is $1$, and if so returning true.

We know multiplying binary matrices is in $L$ (need to "save" only couple of indices), and by also saving $n$ (number of total matrix multiplications) one can solve $STCON$ also in $L$.

Where am I wrong here?

# Answer
A machine runs in logarithmic space if the working space it requires (excluding the read-only input and the write-only output) is at most logarithmic in the number of bits required to represent the input.

For matrix multiplication, the input is the two matrices, and the output is their product. The only working space is, as you say, the "loop counters" for stepping through the current row and column to compute the next bit of the output.

For graph connectivity, the input is the adjacency matrix of the graph, along with the two vertices of interest, and the output is the single bit "yes" or "no". Your proposed algorithm requires remembering the matrix of paths you've discovered so far, which has size $n^2$, and that's not logarithmic.
> 3 votes

# Answer
L contains decision problems. The output of a decision problem is a single bit (not an entire matrix). Contrary to what you wrote, matrix multiplication is not a decision problem so it is not in L. I suggest you check the definition of L and the definition of STCON (which is a decision problem), then try applying your argument with this in mind. Try to write out your algorithm for STCON explicitly and see how much space it uses. You'll find yourself trying to keep a copy of an entire matrix in memory; but that takes more than logarithmic space.
> 1 votes

---
Tags: space-complexity
---


# Question
Title: Is there a universal learning rate for NeuralNetworks?
I'm currently creating a **NeuralNetwork** with **backpropagation**/gradient descent. There is this hyperparameter introduced called "**learning rate**" (**η**). Which has to be chosen to guarantee not overshooting the minimum of the cost function when doing gradient descent. But you also do not want to slow down learning unnecessarily. It's a tradeoff. I've found that **for too small or too big η the NeuralNetwork doesn't learn at all**.

I've successfully trained the NN on the sin-function with η = 0.1. But **for other functions** like any linear combination of the inputs, **a different η is required** (more like η = 0.001). For the quadratic function, I still haven't been able to make the NN converge at all, maybe I just haven't found the right hyperparameters.

My question now is: Is there any way I can **find a η that works for any function**, so I don't have to try and search for it manually.

Thanks in advance, Luis Wirth.

# Answer
> 4 votes
There is no universal learning rate. It depends on your problem space (Are you solving a problem with many local minima or just one? Does your problem’s solution vary dramatically based on a slight change to your input or does the solution gradually shift?, etc.), and it depends on your network architecture (number of layers, number of hidden layers. Do you have a feedback loop etc).

Character recognition is relatively easy for example so you could try a faster learning rate. I once tried to teach a neural network to understand a simple computer machine code, and after a month of training with a dozen computers, it always came close but never solved the problem 100% correctly. No choice of learning rate worked to get me to the solution.

Once I broke down the problem space into a few subcomponents, the entire set of neural networks were trained in under an hour. I used the same choice of training rate in both cases (see below). A good example of how the rate of convergence changes based on the problem being trained.

What I found works best is to start with a fast learning rate to quickly find local minima, but then reduce the rate with each successive training, down to some limit.

All that to say that there is no universal learning rate, and that it worked best for me to reduce it as the training proceeds.

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


# Question
Title: Why does the copycat strategy work for two parallel chess games?
I'm currently looking into computability logic. Japaridze explain that a game !P v P like !Chess v Chess is always winnable thanks to the copycat strategy (http://www.csc.villanova.edu/~japaridz/CL/3.html#copycat). However, what guarantees that the environment will play the same moves? One game could be e4 e5, but the other one e4 Nf6, and then the machine won't know what to do, right?

I'm probably not getting something, but I don't know what. Could someone help me?

Thanks.

# Answer
> 8 votes
The setting in the link you gave (where is it referred to as $chess\lor \neg chess$) is that the player is playing on two boards with different colors, and has to win in at least one.

In that case you can win by mimicking your opponent as follows. Let $b\_{\text{white}},b\_{\text{black}}$ be the boards on which you play white/black correspondingly. Whenever the opponent makes a move $x$ on $b\_{\text{black}}$, you play $x$ on $b\_{\text{white}}$, similarly when your opponent makes a move $x$ on $b\_{white}$ your play $x$ on $b\_{black}$. The result is that you are playing the same position on both boards, only with different colors.

# Answer
> 5 votes
I'm not sure this observation is worth a full answer.

The way to think about this strategy, is that you are trying to guarantee a win on one of two boards. You accomplish this, by forcing two opponents to play each other, with you acting as the intermediary. One one player moves, you duplicate the identical move on the opposite board. So the two players are playing each other, but on different boards.

If this doesn't make sense, I'd recommend setting this up with a very simple game (if you know the game of Nim, that would be a good choice) and see how this plays out.

---
Tags: computability, logic
---


title: Recursion in pi-calculus

text:
# Question
Title: Recursion in pi-calculus
In the book by Sangiorgi and Walker ("The $\pi$-calculus: A theory of Mobile Processes"), Subsection 3.2 is devoted to recursion. They state the following constraint (pages 132-133):

"The environment is *finitary*, in the sense that any process depends on only finitely many constant definitions. (Formally, the transitive closure of the relation that relates two different constants $K$ and $K'$ if an instance of $K$ occurs in the definition of $K'$, is well-founded.)"

I do not understand how the two sentences are related. Right after there is an example with the definitions of $B\_0$, $B\_1$ and $B\_2$: instances of $B\_1$ and $B\_0$ occur in the definition of $B\_0$; instances of $B\_2$ and $B\_0$ occur in the definition of $B\_1$; and an instance of $B\_1$ occurs in the definition of $B\_2$. Thus the environment is "finitary" in the sense that each one of the constants $B\_0$, $B\_1$ and $B\_2$ only depends on three constant definitions. But how is "the transitive closure of the relation that relates two different constants $K$ and $K'$ if an instance of $K$ occurs in the definition of $K'$" well-founded? This transitive closure should relate any of the three constants $B\_0$, $B\_1$ and $B\_2$ to any of these same constants and thus, if I consider the set $\\{ B\_0, B\_1, B\_2 \\}$, I cannot find a minimal element.

# Answer
I am as puzzled as you are. Indeed, that looks wrong, as far as I can see. The mentioned relation can indeed have infinite descending chains, otherwise we could not have "cycles" which are needed for (mutual) recursion.

What should be ruled out is the presence of infinite descending chains involving infinitely many constants $K$. This is however a different requirement from well-foundation.
> 2 votes

---
Tags: recurrence-relation, pi-calculus
---


# Question
Title: How to transpile generic functions into language that do not support generics?
Currently, I am developing a transpiler for my own language, however, I find difficulties to transpile generic functions. For example, how would you translate the following Java-like code in to C?

```
interface Comparable<T> {
    boolean compare(T that);
}

class Person implements Comprable<Person> {
    public string name;
    public boolean compare(Person that) {
        return this.name.compareTo(that.name);
    }
}

// The generic function
<T extends Comparable<T>> boolean isSorted(T[] xs) {
    for(int i = 1; i < xs.length(); i++)
        if(xs[i-1].compare(xs[i]) > 0)
            return false
    return true
}

```

My current solution is to use Javascript prototypes. So, the code above would be translated into the following Javascript (workable in Google Chrome):

```
class Person { }

Person.prototype.compare = function (that) {
    return this.name.localeCompare(that.name);
}

function isSorted(xs) {
    for (var i = 1; i < xs.length; i++)
        if(xs[i-1].compare(xs[i]) > 0)
            return false;

    return true;
}

```

However, Javascript prototype suffers performance issue (I tested it myself), so I am looking for other ways to translate generics without using prototypes. That is why I'm looking for example on how to translate that into pure C.

Note: You might also translate it to any language you like, as long as you did not use generics.

# Answer
> 9 votes
When compiling to a target language without generics, there are two main strategies.

1. Monomorphization: if you have a generic function, and it's instantiated with types $T\_1\ldots T\_n$ throughout your program, you make $n$ copies of the function, with the concrete type replacing the generic variable. This tends to result in fast but large code, since there's lots of duplication.
2. Boxing: you can "box" the generic variables behind some sort of reference type, and cast to and from this type when entering and exiting your generic function. The guarantees of the source language ensure that these casts are always safe. For example, in C you probably want to use `void*`.

If you're looking for resources, generics are known as "parametric polymorphism" in the Programming Languages literature, so that might help your search.

If you're compiling from a Java-like OO language, you'll also need to attach a VTable to your objects: a table of pointers to their methods, you get Java's dynamic dispatch (i.e. the method of an object depends only on its runtime type, not it's compile-time type).

Having "bounded polymorphism" with option 2 (i.e. the `T extends Comparable<T>`makes this a little more tricky, since you need to come up with some sort of boxed representation that lets you find your `Comparable` methods. You could do a dynamic lookup to find such methods, but this is slow. I'd search around for how to compile bounded polymorphism, you'll probably find a better answer.

---
Tags: programming-languages, compilers
---


# Question
Title: How to find information quickly in a table
I have a table and asked me to add my information to it. And then asked me to find my information in the easiest way (after adding your details to the table, assume that the table is arranged alphabetically for names How many comparisons to find your name in the table if you use binary search Give details on how you got the answer) .. How will I be able to find it ??

# Answer
> 0 votes
In each iteration, your arrays size decreasing in 2 times. For example, if you have the array with 1000 elements in the array, in 1st iteration you array length will be:

$\lfloor 1000 / 2 \rfloor = 500$

On the second iteration:

$\lfloor 500 / 2 \rfloor = 250$

And so on. So in result, the number of iterations will be appx. $\log\_2 N$ where $N$ is the array size. This is the worst case. In the best case, you will find an element in 1 iteration.

---
Tags: databases
---


# Question
Title: Complexity of a graph parity-coloring problem
Suppose I have a positively weighted (bounded-degree) graph $G$ where each vertex in $G$ is colored either black or white. I'm curious about the complexity of the following problem:

Find a subset $S$ of edges of G of maximal weight, subject to the constraint that any node colored black is incident to an odd number of edges in $S$, and any node colored white is incident to an even number of edges in $S$. The constraint is sort of a $2$-coloring up to parity.

The problem seems hard in general. I'm more interested in the simpler case that $G$ is a tree. In this case, are there any efficient algorithms to determine such a set $S$? Also, does this problem have a name?

# Answer
Note for each node $v$, there is a one-to-one mapping between the parity of incident edges in $S$ and that of incident edges in $\bar{S}$. This means we can consider the problem with minimum weight equivalently.

The minimum weight version is named min-cost T-join that is studied in this note, which is an application of min-cost matching.

The idea is, one can decompose $S$ ($\bar{S}$ in the maximum weight version) into a set of edge-disjoint paths joining black nodes (nodes requiring an odd degree), thus the solution is exactly a min-cost matching of the complete graph induced by black nodes where the cost of edge $(u,v)$ is the length of the shortest path between $u$ and $v$ in the original graph. So this problem can be solved by any algorithm solving min-cost matching.

---

If the graph is a tree, the solution is much simpler as Yuval Filmus pointed out in the comment.

> Try solving it on a tree using "dynamic programming" (i.e., recursion). For each subtree, solve the corresponding instances with both colors for the root.

Note for a tree, there is at most one feasible solution. So asking for maximum/minimum weight may be meaningless.
> 3 votes

---
Tags: algorithms, graphs, time-complexity, colorings
---


title: if P=NP, why is P a subset of NPC?

text:
# Question
Title: if P=NP, why is P a subset of NPC?
Assuming P = NP, why should P be a subset of NPC? Here is how I understand it:

1. P is a subset of NP
2. NPC is a subset of NP

if we solve an NP Complete problem on a deterministic machine in polynomial time then

3. NP is a subset of P
4. P=NP (from 1 and 3)
5. NPC is a subset of P (2 and 3)

But why is P a subset of NPC, if P = NP? This question has been asked before and the answers just pointed to the definitions of NP, P and NP-C. I have gone through the definitions but still require a detailed picture.

# Answer
To be in NPC a problem, C, has to be in NP, and every problem in NP has to be polynomial-time reducible to C.

If P=NP every problem in NP can be solved in polynomial time.

This means that if P=NP, we can for most problems in P define the following reduction to C; Solve the problem in polynomial time, if the instance you are looking at returns true then reduce it to an input to C for which we know that C returns true - Otherwise reduce it to an input for C that we know returns false.

So for an example; if we take C to the problem of determining if a number is even. And we want to reduce the hamiltonian path problem. We solve the hamiltonian path problem; which we can do in polynomial time since we assume P=NP. If we find that a hamiltonian path exists we select 2 as input to C. If we find that no hamiltonian path exists then we select 1.

This of course fails if C always returns true, or always returns false, so those two problems, as noted by Tom, while part of P, can not be part of NPC. However, all other problems in P will be in NPC if P=NP.
> 9 votes

# Answer
The premise of your question is false. If $P=NP$, then the middle drawing ("This is true...") is wrong and the third ("but why not this?") drawing is correct.

> Assuming P = NP, why should P be a subset of NPC?

$P$ is not a subset of $NPC$, and this is unconditionally true.

There are two very trivial problems in $P$ that can never be $NP$-complete: the empty problem (where the answer is always "no"), and $\Sigma^\*$ (the problem consisting of the set of all inputs, where the answer is always "yes"). These problems are not $NP$-complete because a reduction (showing $NP$-completeness) must map yes-instances to yes-instances and no-instances to no-instances, but if there do not exist any no- or yes-instances to begin with this is impossible.
> 7 votes

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


# Question
Title: Are there any algorithms that run in (2 ↑ ↑ n)?
I’m wondering whether there are any algorithms that use so much time that they must be represented using Knuth up-arrow notation.

Required: Use more than one up-arrow for time complexity.

Bonus points:

* Have the algorithm be useful.
* Have the algorithm be useful and optimized

# Answer
Yes! A simple automaton-based algorithm for answering first-order queries in Presburger arithmetic (and some extensions) has worst-case running time about $2 \uparrow\uparrow n$, where $n$ is the number of quantifier alternations in the query. Despite this formidable worst-case running time the algorithm has been implemented and gives useful results (see Hamoon Mousavi's implementation here).
> 7 votes

# Answer
For any computable function $f$, there are trivially algorithms that run in time $\Omega(f)$:

```
x := f(n);
for i = 1 to x do [nothing];

```

If, in addition, $f$ is time-constructible, the above algorithm runs in time $\Theta(f(n))$.

I forego my bonus points, since the above is neither useful nor optimized.
> 3 votes

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


# Question
Title: Turing machines and their computational power
Is Turing machine most powerful model of computation? Is it possible theoretically to build the model of computation which is more powerful than TM i.e is it theoretically possible to build the machine which could solve the problems that T.M cannot?Are quantum computers also the T.M or are they more powerful than T.M?

# Answer
Your question is closely related to the Church–Turing thesis, which says that Turing machines can compute anything that can reasonably be described as an algorithm (i.e., a sequence of discrete steps). Variants, such as the physical Church–Turing thesis state that Turing machines can compute anything that can be computed by any physical mechanism. Note that these are described as "theses", rather than theorems. They're not formal claims about mathematics so they're not possible to prove.

We don't know how to build any physical device that could compute a non-Turing-computable function. This includes quantum computers, which can be simulated (though inefficiently) to arbitrary accuracy by non-quantum devices such as Turing machines.

We can certainly consider more powerful devices, though, even though we don't know of any way to build them. A typical construction is to take something that Turing machines can't do, and then imagine that we have a subroutine that instantly solves that problem. These are known as oracle machines, and they are provably more powerful than Turing machines. Indeed, one can define a whole infinite hierarchy of successively more powerful machines using this idea, with the caveat that we have no clue how to physically build such a thing.
> 7 votes

---
Tags: turing-machines, computability, quantum-computing
---


# Question
Title: Symbolic Evaluation for Type Inference in a Dynamic Language
Say I have the following contrived example code:

```
a(1)

function a(x) {
  var n = b(x)
  var m = c(x)
  return n + m
}

function b(x) {
  var n = d(x / 2)
  var m = e(x)
  return n - m
}

function c(x) {
  var n = d(x)
  var m = e(x)
  return n * m
}

function d(x) {
  return x + 2
}

function e(x) {
  return x + 3
}

```

Then, I am analyzing the method `d(x)`. From just analyzing it by itself, we can infer that x must be some sort of number. We do this by *what seems like* simulating `x + 2`, and realizing that for that to be satisfied x must be a number. Not quite sure how to implement the type inference here, not sure if it uses symbolic evaluation too.

But then we get to the function call `a(1)`. In this case to do typechecking / type inference on `d(x)`, we have to somehow traverse down the tree of functions, simulating how `x` is transformed along the way. It finds out that it is divided by 2 somewhere in there, so it goes from integer to float. So we check based on our original assumption that `d(x)` is a number, and agree that it will be valid.

*That is just me roughly trying to figure out how to do type checking / type inference.*

I'm wondering two things:

1. If you need to do some sort of *symbolic evaluation* to do type checking / inference. If so, any suggestions on resources or places/ways to better understand that.
2. Say we have a gigantic app with millions of lines of code. Say between `a(x)` and `d(x)` there were 500 function calls, doing all sorts of things to `x`. Wondering if we have to simulate that entire process to figure out if `x` will be a valid type, or if we can somehow limit the scope and do some sort of shortcut. If we had to traverse the 100's of functions for *every variable*, that would be a ton of evaluation and would be slow. So wondering how to limit the scope of the search somehow, to do type checking / inference.

Basically I am figuring out how to do type checking / inference. The resources are mostly on the lambda calculus from what I've found, which I am not too familiar with and works differently I would imagine than an imperative program.

For example, they seem to be mentioning that here:

> (1) **3.2 Type Graph**
>
> After each method has been converted into its intermediate representation, zscript gradually builds a type graph by each method called by the program. The CPA is non-iterative. Only the methods that could potentially be called are processed, and (except for templates) they are only processed one time only. In our implementation of the algorithm, we use a work list. First, the constructor of the class containing the main method, and the main method itself is added to the work list. Then, while the work list is not empty, the methods of the work list are processed. During the processing of a method, more methods may be added to the work list. The algorithm terminates when no more methods remain to be analyzed.

# Answer
> 2 votes
I am not sure you actually understand the terms you use here.

### Symbolic execution has nothing to do with type inference

Symbolic execution is used for static analysis of programs, and is a special case of abstract interpretation. The symbolic executor provides an symbolic input value and traces the program execution given that symbolic input value.

Type inference is much simpler: it involves automatically deducing the type of programs. Nowhere is symbolic execution of the program involved.

### Type inference is usually undecidable

For a dynamic typed language, type inference is not decidable. Moreover, even we have a static type system, type inference is usually still undecidable.

The only (?) type system we know of that has decidable type inference is the **Hindley-Milner type system**, i.e. System F with only Rank-1 types (plus a few conservative extensions). It is known that H-M can type imperative programs (such as Standard ML), as long as you can give good typing rules. When I was an undergraduate, we did an exercise in which we implemented H-M type inference for a restricted, strongly-typed version of Scheme (which was imperative). It was a lot of fun, but it also proves that type inference is possible for imperative programs.

**Update**: oh, how could I have left out the canonical reference for polymorphic, inferable typing of imperative programs? The canonical reference would be Xavier Leroy's PhD thesis, *Typage polymorphe d'un langage algorithmique* (translated into English as *Polymorphic typing of an algorithmic language*).

I suggest that you start reading on Hindley-Milner and Algorithm W, as a first step (see, e.g., Chapter 22 of *Types and Programming Languages* by Benjamin C. Pierce). I also suggest that you do more basic reading and learning before asking on CS.SE, as that would make this site work much better. The theory of programming languages is not like coding and must be studied systematically if you want to have a solid grasp of it :-)

# Answer
> -1 votes
First, let us assume the `+` operator is actually a function.

Secondly, suppose there are one and only one definition for the `+` function, and its type signature is `(Number , Number) -> Number`, i.e. the `+` function will 2 `Number` as input and return a `Number` as output.

Based on all this assumption, whenever we see an invocation for `+` , let say `x + 2`, then we can properly infer that `x` is type of `Number`, since there are only one definition for `+`.

However, if we have 2 definitions for `+` , as seen in the function table below:

```
|=====|================|============================|==========================|
| No. | Representation | Type signature             | Usage                    |
|=====|================|============================|==========================|
|  1  | `+`            | (Number, Number) -> Number | For addition             |
|=====|================|============================|==========================|
|  2  | `+`            | (Number, String) -> String | For string concatenation |
|=====|================|============================|==========================|

```

In this case, it would still be possible to identify the type of `x` in the expression `x + 2`, because the first argument for every definition of `+` is always `Number`.

But, if the expression is `2 + x`, it would be impossible to accurately determine the type of `x`, as it maybe `Number` or `String`, if the language support union type, then the type of `x` can be inferred as `Number|String`.

Hope that helps :)

---
Tags: type-checking, type-inference
---


# Question
Title: Parameter sharing / weight constraints in Neural Networks
I would like to train a neural network whose parameters (alternatively, weights) are subject to linear constraints such as

$w\_{i,j} = w\_{i',j'}$,

where $w\_{i,j}$ denotes the weight from input node $i$ to hidden node $j$ in the case of a network with a single layer. (In the case of several hidden layers, it is okay to assume that only weights stemming from the same layer can be related to each other).

It seems that a special case of this is known as parameter sharing in the context of convolutional neural networks where weights have to coincide, roughly speaking, across different layers.

Surprisingly, it seems that there is not much work / need for more general parameter constraints. Being not a machine learning expert, I am wondering whether I am using the wrong keywords in my literature research.

It would be great if someone could point me towards a tool / framework which allows for linear parameter constraints. Mathematically speaking, I would like to specify a linear subspace of the parameter space and project, at each step of the backwardpropagation, the update vector $\Delta w$ onto this very subspace.

Any help will be greatly appreciated.

# Answer
I'll list two approaches, either of which should work.

# Projected gradient descent

One general approach would be to use projected gradient descent, which provides a way to accommodate these kinds of constraints. For specific kinds of constraints there may be a better way.

Let's recall how we train neural networks. We have an objective function $\Psi$ that computes the total loss, as a function of the weights $w$. Training a neural network amounts to solving the optimization problem "minimize $\Psi(w)$". This is typically done using (stochastic) gradient descent to find the weights $w$ that minimize $\Psi(w)$. In each iteration, you take a single gradient step to update $w$ (backpropagation is just a way to help you compute the gradient $\nabla \Psi(w)$, to help you take this step).

Now you want to add some constraints on $w$. Let $\mathcal{R}$ denote the region (linear subspace) of $w$'s that satisfy all your constraints. Now we want to solve the optimization problem "minimize $\Psi(w)$ subject to $w \in \mathcal{R}$". One standard way to solve such an optimization problem is to use projected gradient descent: in each iteration, you take a single gradient step to update $w$, then project $w$ to the nearest point in $\mathcal{R}$; and repeat. So this amounts to doing the standard backprop training procedure for a neural network, but after each weight update, projecting the weights to the nearest valid value that satisfies all the constraints. You can read more about projected gradient descent in standard resources. In your situation, it is easy to project onto a linear subspace; this is a simple matter of linear algebra. So projected gradient descent should be straightforward to apply. It also shouldn't be too hard to add the projection step, in a framework like Tensorflow. This also has the nice benefit of generalizing beyond linear constraints.

# Reparameterization

The other plausible approach would be a reparameterization trick. If you have $m$ weights, your region $\mathcal{R}$ has the form $\\{w : Aw=c\\}$, where $A$ is a $m \times n$ matrix and $c$ a constant $m$-vector. This can be reparametrized into the form $\\{Bv\\}$ where $B$ is a $n\times n-m$ matrix and $v$ ranges over all possible $n-m$-vectors. In other words, we can find a matrix $B$ such that every valid weight value $w$ can be expressed as $w=Bv$ for some $v$. (I think you can compute $B$ as the pseudoinverse of $A$.) Then, instead of solving the optimization problem "minimize $\Psi(w)$ subject to $w \in \mathcal{R}$", you can solve the optimization problem "minimize $\Psi(Bv)$", where now there are no constraints on $v$. This in turn can be done using gradient descent.

Once you've found the matrix $B$, you'll probably find the latter approach very easy to implement in frameworks like Tensorflow; you just let $v$ be the variables you are trying to solve for, compute $w$ from $v$ using $w=Bv$, and then the neural network uses these derived weights $w$, and you can ask Tensorflow to minimize the loss as usual.
> 2 votes

---
Tags: optimization, machine-learning, neural-networks, constraint-satisfaction
---


title: Master Theorem on oscillating function

text:
# Question
Title: Master Theorem on oscillating function
Consider a recurrence of the form

$T(n) = a T(n/b) + f(n)$

Master theorem's regularity condition excludes some cases (for example, when $f(n)$ is oscillating).

Suppose, however, that $f(n)$ is always less than or equal to a function $g(n)$ that does not violate the regularity condition, so that the master theorem is applicable if $g(n)$ is used instead of $f(n)$. Consider then the following recurrence:

$T'(n) = a T'(n/b) + g(n)$

and assume that the master theorem gives the solution $T'(n)=\Theta(g(n))$.

My doubt is this: can I then safely conclude that $T(n)=O(g(n))$?

In other words, can I be sure that the solution of a recurrence with a term replaced by its upper bound is an upper bound of the solution of the original occurrence? After all, the recurrence establishes a relationship between $T(n)$ and $T(n/b)$ but says nothing about what happens between $n/b$ and $n$ (and $f(n)$ here is oscillating...).

# Answer
Yes, you can. You are defining the recurrence $T'$, so define $T'(1) = T(1)$. Then, since $g(n)$ satisfies the regularity conditions, the Master theorem tells you that $T'(n) = \Theta(g(n))$. Note that the Master theorem doesn't depend on the choice of $T'(1)$; it is a constant, and you get the same asymptotic bound for $T'(n)$ regardless of which constant you choose.

Now, you can prove by induction that $T(n) \le T'(n)$ holds for all $n$. This is a simple induction. The base case holds because you defined $T'$ that way. The inductive step holds because $f(n) \le g(n)$ for all $n$.

Once you've proven that $T(n) \le T'(n)$ for all $n$, you are entitled to conclude that $T(n) = O(T'(n))$ and thus $T(n) = O(g(n))$.
> 2 votes

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


# Question
Title: How does the TLB identify a particular process?
I have read that the translation lookaside buffer (TLB) is implemented in hardware and stores the page numbers and the corresponding frame numbers for faster lookups. Now suppose there are two processes, A and B. Page 2 is mapped to a particular frame number. Now if we are searching for page 2 in the TLB, it can belong to either process A or Process B. So how will the TLB determine which process the page belongs to? Or it is flushed each time a new process is brought into running state? Also, what mechanism is used in TLB lookup?

# Answer
> 10 votes
In the most basic setup, the TLB doesn't determine that. Instead, the TLB only maintains mappings for the pages that are accessible to the current process. If process A is currently running, the TLB only contains mappings for the pages that are accessible to process A; so if page 2 belongs to process B, it won't be in the TLB.

Also, you should be aware that the TLB is a cache. The definitive authoritative mappings are in the page table, and the page table contains mappings only for the process that is currently running. The TLB is a cache of mappings found in the page table. It gets filled in as you go.

When you change which process is running, you change the page table (since now you need a different set of mappings), and you clear the TLB (so you don't have any old mappings that are only relevant to the previous process). Clearing the TLB is also called flushing the TLB.

I suggest reading a good OS textbook. This information can be found in many places, so do a bit of research. Also https://en.wikipedia.org/wiki/Translation\_lookaside\_buffer may be helpful.

---

That describes the basic setup. The disadvantage of the basic setup is that clearing the TLB is slow, which adds a lot of overhead every time you switch processes. That slows things down. Many modern processors have optimizations that reduce this overhead.

For instance, modern Intel TLBs have a process context ID (PCID); each TLB entry is tagged with the PCID of the process that the page mapping is for, and the processor will only use that TLB entry if its PCID matches the ID of the currently running process. The processor fills the PCID when it creates the TLB entry from a register which the operating system must set to a unique value for each process. You can read about that more by searching for PCID.

Arm processors have a somewhat similar feature called domains. Each page table entry contains a domain field, which must be set by the operating system if it wants to use this feature. The processor saves this value in the TLB entry. On a context switch, the operating system updates a register containing the set of currently accessible domains. A TLB entry is valid only if the corresponding domain is accessible.

---
Tags: operating-systems, memory-management
---


title: GraphSlam Doubt

text:
# Question
Title: GraphSlam Doubt
I am trying to implement Graph slam. I have some doubts regrading implementation. I attached a picture to clarify my doubt.

\[

I have a doubt in line number 2. It show omega have a scalar value 0. But at line 3 it show omega is a Matrix.

Next doubt at line 7. In this line omega which is a 3\*3 matrix is add with a 6\*6 matrix. As per my knowledge it is impossible.

I share the link of the paper where page no: 411-412 define this algorithm. Link of the paper is http://robots.stanford.edu/papers/thrun.graphslam.pdf.

If any one working on it please share your knowledge.

# Answer
Often we use $0$ to represent the all-zeros matrix, so the instruction to set $\Omega = 0$ might mean to set it to the all-zeros matrix (with a zero in every entry). You'll have to figure out from context whether that seems correct.
> 1 votes

---
Tags: algorithms, graphs, sparse-matrices
---


# Question
Title: “Fuzzy” Chinese Remainder Theorem NP-hard?
I have some "fuzzy" congruences like these: \begin{align} \\ x&\equiv a\_1 \mod 3 \text{ with } a\_1 \in \\{0,1\\},\\ x&\equiv a\_2\mod 5 \text{ with } a\_2 \in \\{0,3\\},\\x&\equiv a\_3 \mod 7 \text{ with } a\_3 \in \\{1,2,6\\}\\ \end{align} These example moduli would provide a unique solution for $x \bmod lcm(3,5,7)$, if the $a\_i$ were fixed. Because the $a\_i$ are not fixed, these "fuzzy" congruences lead to $2\*3\*2=12$ possible solutions for $x \bmod lcm(3,5,7)$.

To reduce the number of possible solutions for $x$, I'm also given an additional constraint $x \< B$, which provides an upper bound for $x$.

We can assume that all moduli $m\_i$ are primes, so $lcm(m\_1,m\_2,...,m\_n) = \prod\_i m\_i$. Furthermore each $a\_i$ has at most $t$ possible values ($t=3$ in the upper example).

So the general problem is that we are given a constant $t$, primes $m\_1,\dots,m\_n$, an upper bound $B$, and sets $U\_1,\dots,U\_m$ (each of size at most $t$), and the goal is to find an integer $x$ such that $x \bmod m\_i \in U\_i$ for all $i$ and $0 \le x \< B$.

Is this problem NP-hard and how can I prove this?

This question is related to another one: "Fuzzy" Chinese Remainder Theorem, but the difference is that here the sets $U\_i$ can be arbitrary and need not contain consecutive integers.

My initial approach was to use the k-Vertex-Cover problem for the reduction. I used the Wikipedia Integer programming NP-hardness proof as a template (https://en.wikipedia.org/wiki/Integer\_programming#Proof\_of\_NP-hardness).

Let $G=(V,E)$ be an undirected graph. Define a linear program as follows: \begin{align} \sum\_{v \in V} y\_v \leq k& \\ y\_v+y\_u \geq 1 && \forall uv \in E \\ y\_v \geq 0 && \forall v \in V \end{align}

I tried to define the Vertices as $a\_i$.

But I am unable to transform the $y\_v+y\_u \geq 1 \text{ , } \forall uv \in E$ (set contains at least one vertex of each edge) inequalities into "fuzzy" congruences.

# Answer
> 3 votes
If you allow arbitrary modulus (so $m\_i$ is not required to be prime), your problem is NP-hard. In particular, it is NP-hard to determine whether there exists any valid solution, even without the upper bound $B$.

To prove this, we can reduce 3SAT to the problem. Suppose we have a 3SAT formula $\varphi$ over variables $v\_1,\dots,v\_n$. Let $p\_1,\dots,p\_n$ be the first $n$ primes. Then we will associate one congruence per clause of $\varphi$. In particular, the clause $v\_i \lor v\_j \lor v\_k$ corresponds to the congruence

$$x \equiv a \pmod{p\_i p\_j p\_k} \text{ where } a \in U$$

and $U=\\{c\_{001},c\_{010},c\_{011},\dots,c\_{111}\\}$ contains seven values, where $c\_{def}$ is the unique constant such that $c\_{def} \equiv d \pmod{p\_i}$, $c\_{def} \equiv e \pmod{p\_j}$, and $c\_{def} \equiv f \pmod{p\_k}$. Do the same for each other clause; e.g., for $v\_i \lor v\_j \lor \neg v\_k$, the set $U$ has the seven values $U=\\{c\_{000}, c\_{010}, c\_{011}, c\_{100}, c\_{101}, c\_{110}, c\_{111}\\}$, and so on.

In this way, we obtain a system of congruences with one congruence per clause of $\varphi$. We don't need an upper bound on $x$ (you can use the trivial upper bound $x \< p\_1 p\_2 \cdots p\_n$ if you like). Then there exists a solution to this system of congruences iff the formula $\varphi$ is satisfiable. In particular, a satisfying assignment $(v\_1,\dots,v\_n)$ for $\varphi$ corresponds to a unique value for $x$ that satisfies all the congruences, namely, the value such that $x \equiv v\_i \pmod{p\_i}$ for all $i$.

This reduction does require the ability to choose moduluses that are not prime. I don't know if the problem becomes any easier when every modulus is prime.

---
Tags: complexity-theory, time-complexity, np-complete, reductions, np-hard
---


# Question
Title: Existence of Optimal Policy for infinite-state MDPs
It is well-know from Puterman's book (1994) that in any finite-state MDP, if there exists an optimal policy, then that policy is stationary and deterministic. How about MDPs with continuous state spaces with finite-action space? Assume that the rewards are bounded.

# Answer
If the state set is Polish (e.g the set of all real numbers), finiteness of action spaces suffices to conclude that the MDP always has an optimal stationary policy - refer to "Markov Decision Processes" by Puterman for the details.
> 1 votes

---
Tags: machine-learning, reinforcement-learning
---


# Question
Title: Algorithm to distribute elements evenly among a population
Algorithm to distribute elements evenly among a population

In the software I am doing I have three different categories:

```
Maize:
    1- Variety A
    2- Variety B
    3- Variety C
    4- Variety D
    5- Variety E
    6- Variety F
    7- Variety G
Fertilizer:
    1- Type A
    2- Type B
    3- Type C
    4- Type D
Management
    1- Form A
    2- Form B
    3- Form C
    4- Form D
    5- Form E

```

With this categories I need to produce combinations of Maize+Fertilizer+Management. So I get 140 combinations. I need to distribute the 140 combinations into 200 recipients randomly (some will repeat of course) but balanced (to avoid to many of one type of combination)

I saw this post but I might have a different case.

Is there an algorithm to do this?

# Answer
> 2 votes
Traditionally, this kind of problem is described as a fractional factorial design problem. However, your problem also can be elegantly solved via a probabilistic / statistical method that exploits the power of low discrepancy sequences.

For additional context, this method can be applied to very similar questions as yours, such as:

**Low Discrepancy Sequences**

Low discrepancy sequences, (often described as quasirandom sequences) are numbers that generally appear random, but have an underlying structure to them that makes them more evenly distributed and so have less 'gaps' and 'clumping'.

There are many ways to construct low discrepancy sequences, and they can be generalised to arbitrarily high dimensions, too. For example, below is a picture of the first 100 terms of five different low discrepancy sequences in two dimensional and how they compare to simple random sampling. Note that all of them are substantially more evenly distributed than the conventional uniform random sampling.

Further details can be found at the Wikipedia article: "Halton Sequence".

**Equidistributed Allocation**

A post I wrote, "The unreasonable effectiveness of quasirandom sequences", describes how to easily create an efficient extensible $d$-dimensional low discrepancy sequences. (For this particular case, we need a $d=3$ dimensional sequence.)

Define an $n$ x $3$ dimensional array, where each of the $n=200$ rows represents a different trial, and each of the components of each 3-vector defines which type of variety to use for each of the $d=3$ categories.

For $d=3$, there is one magical number involved which is $ \phi\_3 = 1.2207440846... $ (see the article if you are interested in what is so special about this number).

Now simply define for all integer $n$, a 3-dimensional vector $\pmb{t}\_n$ such that: $$ \mathbf{t}\_n = \pmb{s} + n \pmb{\alpha} \\; (\textrm{mod} \\; 1), \quad n=1,2,3,... $$ $$ \textrm{where} \quad \pmb{\alpha} =(\frac{1}{\phi\_3}, \frac{1}{\phi\_3^2},\frac{1}{\phi\_3^3}).$$

In nearly all instances, the choice of initial seed $\pmb{s} $ does not change the key characteristics, and so for reasons of obvious simplicity, $\pmb{s} =\pmb{0}$ is the usual choice. (I have included it in this definition, because if you wish to create another sampling distribution, all you need to do is re-run the code but with a different starting seed!)

Specifically for $d=3$; with $\phi\_3 = 1.2207440846$ and $\pmb{s}= (0.5,0.5,0.5) $, the first 5 terms of this sequence are:

1. (0.319173, 0.171044, 0.0497005)
2. (0.138345, 0.842087, 0.599401)
3. (0.957518, 0.513131, 0.149101)
4. (0.77669, 0.184174, 0.698802)
5. (0.595863, 0.855218, 0.248502) ...

Now consider the first component $x\_n$ of each vector $t\_n$, to represent the first category ("Maize"). (ie $x\_1 = 0.319173$). If

* $ 0 \leq x \< 1/7$, then select Maize, option A
* $ 1/7 \leq x \< 2/7$, then select Maize, option B
* $ 2/7 \leq x \< 3/7$, then select Maize, option C
* ...
* $ 6/7 \leq x \< 1$, then select Maize, option G

Similarly, consider the second component $y\_n$ of each vector $t\_n$, to represent the second category ("Fertilizer"). If

* $ 0 \leq x \< 1/4$, then select Fertilizer, option A
* $ 1/4 \leq x \< 2/4$, then select Fertilizer, option B
* $ 2/4 \leq x \< 3/4$, then select Fertilizer, option C
* $ 3/4 \leq x \< 1$, then select Fertilizer, option G

**Summary**

**The beautiful result of this low discrepancy method is that, for any $n$, the number of varieties allocated in each category will not differ by more than 1.**

Said another way, the number of samples for every variety and every category, will never be more than 1 away to the ideal equal allocation method.

**Code**

Python code to create the low discrepancy sequences is

```
# Use Newton-Rhapson-Method
def gamma(d):
    x=1.0000
    for i in range(20):
        x = x-(pow(x,d+1)-x-1)/((d+1)*pow(x,d)-1)
    return x

d=3
n=200

g = gamma(d)
alpha = np.zeros(d)
s=0.5  # initial seed.

for j in range(d):
    alpha[j] = pow(1/g,j+1) %1
z = np.zeros((n, d))
for i in range(n):
    z = (s + alpha*(i+1)) %1

print(s)
print(z)

```

Hope that helps!

---
Tags: algorithms, randomized-algorithms
---


# Question
Title: What are the concequences of the unit type and the unit value being the same?
What are the practical and theoretical implications of the unit *type* and the unit *value* being the same or different entities?

For example, in Haskell the unit type and unit value are both spelled `()`. In ML, the unit type is spelled `unit` and it's value is `()`.

Are there any problems that arise from either option? Are there any significant benefits perhaps to the soundness of the type-system or the ability to reason about programs?

# Answer
> 6 votes
You have been confused by Haskell's notation. The unit type and unit value are of course different, and it just happens that Haskell uses the same notation for both.

As for the consequences: there are none. Notation is irrelevant here. You can call the unit type `Dog` or `BauwnNuYwvb` (i.e., nonsense), and it won't change the type system.

# Answer
> 2 votes
If you reason in terms of sets, what you call the "unit type" is really a one element set, and its single element is what you call the "unit value". So they are obviously not the same thing.

# Answer
> 2 votes
There is no *theoretic* consequence. Even when they are spelled the same, they are different objects.

Instead, from a purely implementation point of view, there might be some cases where one needs to disambiguate them. In Haskell, a `()` at the left of `::` is the unit value, while a `()` at the right of `::` is a unit type. In rare circumstances, using the `DataKinds` extension, one needs a unit value on the right as well, and this needs to be escaped to disambiguate.

```
data T (a :: *) (b :: ()) where
    ...

foo :: T () '()

```

Above, `T` is applied to the unit type (1st arg) and to the unit value (2nd arg), the second being quoted to disambiguate.

This is, however, only a notation incident, which is an insignificant matter from a scientific point of view. One could always choose a different notation and avoid the ambiguities completely.

---
Tags: type-theory
---


# Question
Title: Optimal way to find maximal sum (with constraints) of array elements
**Problem:** Find the **maximum sum** of the elements in an array, with the following constraints:

* all the elements of the array are non-negative integers
* each element can either be left out completely from the sum (`skip`ped), can be added, or can be subtracted from the sum
* when reading the array left to right (i.e. from index `0` to index `size - 1`), the sequence of operations must be `subtract`, `add`, `subtract`, `add`, ... etc, with optional `skip`s in between (e.g. `subtract`, `skip`, `skip`, `add`, `subtract`, `skip`, `add`)
* in other words: the first element included in the sum must be subtracted, the next element included into the sum must be added, the next subtracted, etc... (i.e. we always start with subtraction).

**Example**: Suppose we have the following array: `[1, 2, 3, 4, 5]`.

Then the sums following is valid:

`-1 + 2 -3 +4 -5`

`-1 + 0 + 3 -4 +5`

`-1 + 0 + 0 + 0 + 0`

`0 -2 + 0 + 0 + 5`

`0 + 0 + 0 + 0 -5`

`0 + 0 + 0 + 0 + 0`

Some invalid sums:

`+1 -2 +3 -4 +5 // We did not start with subtraction (+1)`

`-1 -2 +3 -4 +5 // Two consecutive subtractions (-1 -2)`

`-1 +2 +0 +4 -5 // Two consecutive additions (+2 +4)`.

**My solution**: There are `2^N` possible valid sums (where `N` is the size of the array), since if we read the array left to right, each element can either be included into the sum or not. For each of these cases, let's calculate the sum that we get, and choose the minimum of those sums.

**Pseudo code of my solution**:

```
func findMax(a []) {
    max := 0;
    for (i := 0; i < 2 ^ a.size; ++i) {
        code := i;       // binary representation of the next possibility
                        // 0: we do nothing
                        // 1: we add or remove the next element
        sum := 0;
        sign := -1;
        for (j := 0; j < a.size; ++j) {
            if (code[j] == 1) {    // jth digit of code
                sum := sum + sign * a[j];
                // if (sum < 0) { goto end } // (1) would this help?
                sign := -sign;
            }
        }
        if (sum > max) {
            max = sum;
        }
end:
    }
    return max;
}

```

**Optimization** This solution has exponential run-time complexity in the size of the array, therefore I was asking myself how to optimize it. The only idea I have is to backtrack (i.e., don't continue the calculation for a given case), whenever the partial sum becomes negative (see commented out line `(1)` in the pseudo code). However, I'm not sure that a.) this could not weed out in some way the maximum we are looking for (although I can't think of any counter examples) and b.) that there other, even more efficient ways to backtrack.

**Questions**

1.) Is there an example, where back-tracking upon encountering a negative partial sum (i.e. the solution suggested at line `(1)`) would prevent us from finding the real maximum sum?

2.) Is there some even better way to back-track?

3.) What other approaches exist for this problem?

# Answer
This is a classic Dynamic Programming problem. Basically, dynamic programming is a way of turning a recursive algorithm into an iterative one with better runtime, by saving previous results that we might need again.

In this case, we can write the problem as two recursive functions:

```
maxSumSubtractFirst(startIndex):
    if startIndex is past the end of the array:
        return 0
    return max( # Two options: take whichever is better
        -A[startIndex] + maxSumAddFirst(startIndex+1), # Use this one
        maxSumSubtractFirst(startIndex+1) # Skip this one
    )

maxSumAddFirst(startIndex):
    if startIndex is past the end of the array:
        return 0
    return max( # Same as above
        A[startIndex] + maxSumSubtractFirst(startIndex+1),
        maxSumAddFirst(startIndex+1)
    )

```

In other words, we have two choices for each element: either include it (and flip the sign for the next one), or skip it (and keep the sign the same).

Now, we could run `maxSumSubtractFirst(0)` and get the answer that way, but this could take $O(2^n)$ in the worst case. We can do better.

Since each function will always return the same output given the same input, we can make two arrays the same length as our input, then store the results of `maxSumSubtractFirst` in one, and `maxSumAddFirst` in the other. If we start from the end (the largest index) and work backward, we'll never have to recurse at all: just look up the results in the array, which takes $O(1)$.

Now we can take the first element in the `maxSumSubtractFirst` array, and that's our answer. We've only had to call each function $n$ times, and each call takes $O(1)$, so this version of the algorithm runs in $O(n)$—a significant improvement over $O(2^n)$!

(Note that, as written, this only gets you the value of the sum, not the sequence of choices that led to it. But that's easy to change: make additional arrays to hold the choices, and fill them in with each call to `maxSum*First`.)
> 3 votes

---
Tags: optimization, backtracking
---


# Question
Title: Question on word probability for hierarchical softmax used in natural language processing
I am reading the following paper: https://papers.nips.cc/paper/5021-distributed-representations-of-words-and-phrases-and-their-compositionality.pdf

On page 4 of the paper they describe the hierarchical softmax which is intended to reduce the computational complexity (I believe only during training time) of training a neural network to learn word vectors. The hierarchical softmax output layer is a balanced binary tree.

Here is the description given in the paper for computing $p(w\vert w\_I)$ (where $w\_I$ is the input word or set of words, and $w$ is the missing word we are trying to predict):

More precisely, each word $w$ can be reached by an appropriate path from the root of the tree. Let $n(w,j)$ be the $j$-th node on the path from the root to $w$, and let $L(w)$ be the length of this path, so $n(w,1)=root$ and $n(w,L(w))=w$. In addition, for any inner node $n$, let $ch(n)$ be an arbitrary fixed child of $n$ and let $\lbrack x \rbrack$ (can't figure out how to generate brackets used in paper) be $1$ if $x$ is true and $-1$ otherwise. Then the hierarchical softmax defines $p(w\_O \vert w\_I)$ as follows:

$$p(w\vert w\_I) =\prod\_{j=1}^{L(w)-1}\sigma(\lbrack n(w,j+1)=ch(n(w,j))\rbrack \cdot v\_{n(w,j)}'^T v\_{w\_I})$$

where $\sigma(x) = 1/(1+\exp(-x))$.

Now, I understand that we are using the sigmoid function to essentially "squish" the dot products of our two vector arguments in values between $0$ and $1$ (i.e. probabilities). But, I don't understand the user of the indicator function in this equation. Going down the tree I feel like we should be multiplying probabilities at each branch, and somehow I know the indicator function must be "steering" us down the tree, but I cannot tell how. Intuitively, I feel like it would be more appropriate to have an indicator function that outputted $\sigma(x)$ or $(1-\sigma(x))$ based on left or right turns.

# Answer
> 2 votes
I have figured out my confusion.

The indicator function is $\lbrack x \rbrack$ is set to output a $-1$ or a $1$ based on the argument being false or true, respectively.

When the authors say "let $ch(n)$ be an arbitrary fixed child of node $n$", they mean arbitrary in the sense of left child or right child. But in order for our function to work, we must decide on this arbitrary decision. So, let us assume $ch(n)$ ouputs the left child of unit $n$.

Then as we go down our tree, if $\lbrack n(w,j+1) = ch(n(w,j))\rbrack = 1 $ it means the next node on our path is to the left of the parent node $n(w,j)$ and if $\lbrack n(w,j+1) = ch(n(w,j))\rbrack = -1$ it means that the next node is to the right of $n(w,j)$.

As a result, since we defined $ch(n)$ to indicate the left child, all left probabilities are calculated as $\sigma(v\_{n(w,j)}'^T\cdot v\_{w\_I})$ since $\lbrack n(w,j+1) = ch(n(w,j))\rbrack = 1 $. Now we know that the probability on the right must then be $1 -\sigma(v\_{n(w,j)}'^T\cdot v\_{w\_I})$. This is where I was confused since the function outputs $\sigma(-v\_{n(w,j)}'^T\cdot v\_{w\_I})$. But let $a=v\_{n(w,j)}'^T\cdot v\_{w\_I}$ and we can verify that $\sigma(-a)=1-\sigma(a)$.

We have $\sigma(a) = \frac{1}{1+e^{-a}}$, now observe that

$\begin{align\*} 1 - \sigma(a) &= \frac{1+e^{-a}}{1+e^{-a}}-\frac{1}{1+e^{-a}}\\ &=\frac{e^{-a}}{1+e^{-a}}\\ &=\frac{1}{e^a}\times \frac{1}{1+e^{-a}}\\ &=\frac{1}{1+e^a}\\ &=\frac{1}{1+e^{-(-a)}}\\ &=\sigma(-a). \end{align\*}$

Hence the function $$p(w\vert w\_I) =\prod\_{j=1}^{L(w)-1}\sigma(\lbrack n(w,j+1)=ch(n(w,j))\rbrack \cdot v\_{n(w,j)}'^T v\_{w\_I})$$

simply multiplies probabilities along the branches corresponding to the path from the root node to the proper leaf node $w$.

---
Tags: machine-learning, binary-trees, probability-theory, natural-language-processing
---