# Question
Title: Efficiency of 0-1 linear programming w.r.t. number of binary variables
I am working on a problem in which I have to solve 0-1 linear programs, that is linear programs where some of the variables are binary, i.e. either 1 or 0.

Lets say I have a fixed number of $n$ variables in my program of which $k \leq n$ are binary. The other $n-k$ variables are continuous. My question is: **What can be said about the efficiency of solving these problems with respect to $k$? I know that 0-1-programming is NP-hard, but does it make a difference whether $k$ is small or large?**

In my problem setting, I can somewhat modify the parameter $k$, i.e. the number of binary variables. Is it recommendable to lower them if possible ($k=0$ is impossible)? If so, why?

Thanks in advance

P.S.: If someone could point me to a paper discussing this, I'd happily download it.

# Answer
> 1 votes
## If the other variables are integer variables

This is still NP-hard, even when $k=0$, for the same reason that integer programming is hard.

As for whether lowering the number of binary constraints will help in practice, that depends, and usually the only way to know is to try it. It will depend on what the price of doing that is, as well as depend on the behavior of your ILP solver (which can sometimes be hard to predict).

I would expect that binary variables are harder to deal with than integer variables with a larger range. In particular, if we have an integer variable whose values are in the range $\\{0,1,2,\dots,r\\}$, then I would expect that the smaller $r$ is, the harder the problem is. Heuristically, the larger the value of the integer variable is, the better it can be approximated with a continuous variable (not restricted to integers), so the closer it comes to linear programming. A standard strategy for ILP solvers is to solve the linear program without the integer constraints, then fine-tune the solution somehow to make everything an integer (e.g., round to the nearest integer). We might hope that the larger the integers, the less error this process will introduce. So, binary variables might be a lot harder than integer variables whose value will be large and whose range of plausible values is large. This is not a hard-and-fast rule; just a rule of thumb to help you think about formulating your problem as an integer problem.

As always, the ultimate answer is to try it and see.

See also https://cstheory.stackexchange.com/q/16530/5038 and https://cstheory.stackexchange.com/q/29317/5038. The operations research community studies what properties of ILP problems tend to be solvable more efficiently with existing ILP solvers (as "rules of thumb" and heuristics).

## If the other variables are continuous variables

Then yes, the fewer binary constraints, the faster the ILP solver probably will be. With no binary constraints (or integrality constraints), this becomes linear programming, which can be solved in polynomial time and for which there are efficient algorithms. It's the binary constraints that make the problem hard. The more binary constraints you have, the harder things can get.

---
Tags: efficiency, linear-programming, integer-programming
---


title: SQl query output

text:
# Question
Title: SQl query output
Consider the table employee(empId, name, department, salary) and the two queries Q1 ,Q2 below. Assuming that department 5 has more than one employee, and we want to find the employees who get higher salary than anyone in the department 5, which one of the statements is TRUE for any arbitrary employee table?

Q1 :

Select e.empId

```
    From employee e
 Where not exists
    (Select * From employee s where s.department = “5” and
                                    s.salary >=e.salary)

```

Q2
Select e.empId

```
 From employee e
 Where e.salary > Any
(Select distinct salary From employee s Where s.department = “5”)

```

(A) Q1 is the correct query

(B) Q2 is the correct query

(C) Both Q1 and Q2 produce the same answer.

(D) Neither Q1 nor Q2 is the correct query

My work:- I am stuck at the word "**anyone**". If by anyone it means that all employees of department 5 than Q1 is correct,but if by anyone it means "any" (at least one) then Q2 is correct.We have a function is SQl named as "any" and that function says at least one should satisfy condition.So i am relating anyone to that function.Please help in understanding it correctly

# Answer
> 1 votes
In English, "higher salary than anyone in department 5" normally means "higher salary than everyone in department 5".

---
Tags: database-theory, databases
---


title: Time complexity of this while loop

text:
# Question
Title: Time complexity of this while loop
So, i would like to know the time complexity of the following codes:

```
x = (float) rand() / rand();   // T(4)

while (x >= 0.01)   // T(?)
{
    x *= 0.8;  // T(?) x T(2)
}

```

Assuming that all the basic operations are perfomed once, is the best case T(1) - constant time? Since, that might only happen when the random x generated is \<= 0.01.

What about the average case? Is it T(?) x T(1) / 2?

Thanks a lot!

# Answer
Worst case, if the second call to rand() returns 0 and the first call doesn't, you get a floating point division by zero, and if you are using standard IEEE 754 arithmetic, the result is +infinity. In that case, the loop will run forever.

If you changed your code to exclude that case, and exclude the case that rand () might return a 128 bit integer, then for any implementation the size of x is limited, so the number of multiplications by 0.8 is limited, so the runtime is O (1).
> 8 votes

# Answer
This answer refers to a version of the question in which $x$ is sampled by dividing two random numbers.

As mentioned by Rick Decker's answer, given $x$, we can approximate the running time by $O(\max(\log x,1))$. Assuming that `rand` returns a random number in $\[0,1\]$, the running time should be proportional (up to an additive constant) to $$ \int\_0^1 \int\_0^1 \max(\log \tfrac{x}{y},0) \\, dx \\, dy. $$ Let us start by computing the inner integral: $$ \int\_0^1 \max(\log \tfrac{x}{y},0) \\, dx = \int\_y^1 \log \tfrac{x}{y} \\, dx = (1-y)\log y + \int\_y^1 \log x \\, dx = \\ -(1-y)\log y + \left. x(\log x-1) \right|\_y^1 = -(1-y)\log y-1-y(\log y-1) = \\ y-\log y-1. $$ Integrating this over $y$, we get $$ \int\_0^1 (y-\log y-1) \\, dy = \left. \tfrac{1}{2} y^2 - y\log y \right|\_0^1 = \frac{1}{2}. $$ This shows that in this idealized setting, the expected running time is $O(1)$ (rather than infinity, which could also have been the case).
> 6 votes

# Answer
In general, the time taken by this snippet is mainly governed by how many times the loop iterates. In other words, how many times will you need to multiply $x$ by $0.8$ to get a result less than $0.01$?

> In other words, for a fixed $x$, what $n$ value will ensure that $(0.8)^nx\<0.01$?
> 2 votes

---
Tags: algorithm-analysis, runtime-analysis, randomness, average-case
---


# Question
Title: What is the time and space complexity of the algorithm to either prove or refute that given expression is equals to (A+B)^n for any natural number n
**Note** that this is **not** duplicate of my previous question: how to simplify algebraic expressions, though it is similar, but still this is different, this is **not** the same.

I need an algorithm that either proves or refutes that:

∀X,Y,Z,n,i,j,k,l: X∈{A,B} ∧ Y∈{A,B} ∧ Z∈{A,B} ∧ i,j,k,l≥0 ∧ n≥1 ∧ i+j+k+l≤n-3

$\Sigma$ (A+B)iX(A+B)jY(A+B)kZ(A+B)l = (A+B)n

Note that Σ here stands for sum with the operator +, which is union of set of words.

It should be noted that i,j,k and l are changing from term to term, keeping that:

i≥0 ∧ j≥0 ∧ k≥0 ∧ l≥0 ∧ i+j+k+l≤n-3

The only one that is not changing in the sum is n.

The algebraic rules are:

The operator + in this algebra is **binary idempotent** as I read about the semiring on wikipedia that someone linked me in the comments.

∀n,e1, ... , en ∈ {A,B,(A+B)}

e1...en+e1...en=e1...en

Where e1...en is concatenation of all e1 to en

In other words, sum of same expressions is equal to same expression, e.g. A+A=A, B+B=B, (A+B)+(A+B)=(A+B), AB+AB=AB, BA+BA=BA, A2+A2=A2, B2+B2=B2, (A+B)2+(A+B)2=(A+B)2 and etc, like in regular expressions.

That's because, each expression is a set of words, and the operator + is suppose to be union of the sets.

AA=A2, BB=B2, (A+B)(A+B)=(A+B)2, AAA=A3, BBB=B3, (A+B)(A+B)(A+B)=(A+B)3, ... , AAB=A2B, ABB=AB2

Note that ABA≠A2B

The power of A means how many times A appears in row, and the power of B means how many times B appears in row, and the power of (A+B) means how many (A+B) appears in row.

A(A+B) = AA+AB=A2+AB

B(A+B) = BA+BB=BA+B2

(A+B)A = AA+BA = A2+BA

(A+B)B = AB+BB = AB+B2

Thus:

A(A+B)B = (AA+AB)B = (A2+AB)B = A2B+ABB = A2B+AB2

Unlike in regular expressions, in this algebra you can do the following:

AB+BA=2AB

2AB says that in the set there are exactly 2 different words that contains 1 letter 'A' and 1 letter 'B' in the set.

Thus: 2BA=2AB, 2BA means the same thing as 2AB means.

3AB=2AB, because 3AB says that in the set there are exactly 3 different words that contains 1 letter 'A' and 1 letter 'B' in the set, but this is impossible combinatorially.

In general, the coefficient is natural number that says how many words exist in the set, when you specify how many As and Bs are contained in each word in the set.

If the coefficient is larger than the number of possible different words combinatorially, the expression is equals to the same expression, but with smaller coefficient that is equals to the number of possible different words combinatorially.

Thus 3BA=2BA, because only 2 words with 1 letter A and 1 letter B is possible, but not 3.

It should be noted that when the coefficient is smaller than the number of possible words combinatorially, the set is undefined, i.e. for example:

2A2B says that in the set there are 2 words that each contains 2 letters A and 1 letter B, but combinatorially there exists 3 different words.

So:

Does 2A2B={AAB,ABA} ? Does 2A2B={ABA,BAA} ? Does 2A2B={AAB,BAA} ?

This is unknown! It's known that it can be equals to either of these sets, but it's unknown which exactly.

But sure that 2A2B≠{AAA,BBB}!

The algorithm should be careful! Because that union is commutative operator thus the plus operator marked as +, i.e. changing the order does not change the result.

∴ A+B=B+A

AB+BA=BA+AB

Note that: AB≠BA

Because concatenation isn't commutative operator, unless the coefficient is larger than 1.

But:

1. AB+AB+BA=AB+BA+AB ∵ AB+BA=BA+AB

But:

2. AB+AB+BA = AB+BA = 2AB ∵ AB+AB=AB

and

3. AB+BA+AB = 2AB+AB = 3AB

∴ 2AB=3AB ∵ 1, 2 and 3

In this case it works, because really 3AB=2AB and this already explained above by the definition of coefficient of a word

But in the following case, it doesn't work:

4. AAB+AAB+BAA = AAB+BAA+AAB ∵ AAB+BAA = BAA+AAB
5. AAB+AAB+BAA = AAB+BAA = 2AAB ∵ AAB+AAB=AAB
6. AAB+BAA+AAB = 2AAB+AAB = 3AAB

∴ 2AAB=3AAB ∵ 4, 5 and 6

But this is **fallacy** ∵ 2AAB≠3AAB ∵ |2AAB|≠|3AAB|

∵ |2AAB|=2 ∧ |3AAB|=3 ∧ 2≠3 according to the definition of coefficient of a word.

Where || is the operator that returns the cardinality of the set, and because that all sets are **finite** in this math, it returns the number of words in the set.

Even though it cannot be determined what exactly is 2AAB, still it can be determined that |2AAB|=2, but note that |4AAB|=3, not 4, because 4AAB=3AAB and |3AAB|=3, because there is no 4 different words that contains 2 letters 'A' and 1 letter 'B'.

As you can see the result can be wrong and incorrect due to fallacy and to avoid this, the algorithm **must first** in every iteration to scan the entire string and detect same expressions and eliminate them. Then to sum up the others.

In this case, when the following expression is given:

AAB+BAA+AAB

The algorithm should notice that AAB repeats itself and eliminate all the repeatings, until there is only 1 occurrence.

After first scan:

**AAB**+BAA+**AAB**

Now eliminate AAB so the string becomes:

AAB+BAA

Then:

2AAB

And this is the correct result.

It should be noted that in this algebra, you can also use the binomial theorem.

For instance:

(A+B)2=A2+2AB+B2

And this is correct, because (A+B)2 is the set of all words that has length of 2, where the alphabet is {A,B}.

The other side is union of 3 sets, where A2={AA}, B2={BB} and 2AB={AB,BA}, so A2+2AB+B2={AA}∪{AB,BA}∪{BB}=(A+B)2

It seems that this works with power of 2, but this should work with any other power, not only 2, thus the binomial theorem applies, because for any natural number n, (A+B)n is the set of all words of length n, where the alphabet is {A,B}. Check it out! According to the definition of coefficient of a word, the binomial theorem works!

Note that kleene star is **undefined** in this algebra, unlike in regular expressions, i.e. the operator * does not exist in this algebra.

The purpose of brackets () in this algebra is to write the union of two expressions shorter, if both expressions have identical prefixes or/and identical infixes or/and identical suffixes.

That's all the rules.

If you have any more questions, please ask in the comments.

I will answer all of your questions until everything is understood.

I don't expect for quick answers, I will wait.

I do understand that you need the time to read my question over and over again until you understand everything or you have questions to ask.

I have already said what is given to the algorithm in the beginning of this question.

The algorithm suppose to return true, if the given expression is equals to (A+B)n or false otherwise for any given natural number n.

To determine if the given expression does equal to (A+B)n, the algorithm will have to simplify the given expression, but only by applying all the rules I have talking about above.

It should be easy to write the pseudo code of this algorithm to do this task, but I want to know what would be both the time and space complexity of this algorithm.

I think it should be polynomial both in time and space, but I need a proof.

**EDIT:** Someone noted that I asked 3 questions, but I thought that I asked only 1 question.

My real question is: what is the complexity of this problem?

Although if there exists polynomial algorithm that solves this problem, then by definition of the complexity class P, this problem suppose to be in P, so giving polynomial algorithm as an answer to the question: "What is the algorithm that solves this problem?", also answers that question: "What is the complexity of this problem?", because this answer implies that this problem is in P.

If the answer also answers **in**directly the question "What is the complexity of this problem?" then it also answers **in**directly the question "What is the complexity of this algorithm?", because if I inferred from the answer that the problem is in P, then the algorithm in the answer must be polynomial in time and space.

That's the reason that for me, these 3 questions are 1 question, because 1 answer can answer all these 3 questions, 1 of them **directly**, the 2 others **in**directly.

I also admit that this question is very long, that's why I already said that I don't expect for quick answers.

Take your time.

I can wait for answer even until the next week.

I am not rushing or something.

I know that you need the time to understand this algebra.

I also apologize for my bad formatting.

Please let me know what is bad in the format of my question and I will improve my question.

In the mean time, I am going to **try** to answer my question by myself, but this will take some time.

I don't think that this question is easy.

# Answer
> 1 votes
You don't need an algorithm; you just want to prove a theorem. This isn't a question about computer science algorithms, so much as a question about mathematics. The theorem is tedious but not difficult to prove.

I suggest you start by practicing proving some simpler statements. For instance, in your algebra,

$$(A+B)^i (A+B)^{n-i} = (A+B)^n$$

is true for all $i,n$ with $0 \le i\le n$. This can be proven by simply considering all cases; you consider any term in the right-hand side, and prove that it is in the left-hand side, and vice versa. The right-hand side is a sum of terms, where each term is a sequence of $n$ letters. Each such term appears on the left-hand side, too.

Similarly, you can prove

$$\sum\_{i=0}^n (A+B)^i (A+B)^{n-i} = (A+B)^n$$

is true in your algebra for all $n$. In particular, using the above fact, we see that

$$\sum\_{i=0}^n (A+B)^i (A+B)^{n-i} = \sum\_{i=0}^n (A+B)^n = (A+B)^n.$$

It's also true that

$$\sum\_{i=0}^n \sum\_{X\in \\{A,B\\}} (A+B)^i X (A+B)^{n-1-i} = (A+B)^n.$$

A helpful step in that derivation is that

$$\begin{align\*} \sum\_{X\in \\{A,B\\}} (A+B)^i X (A+B)^{n-1-i} &= (A+B)^i \left(\sum\_{X\in \\{A,B\\}} X \right) (A+B)^{n-1-i}\\ &= (A+B)^i (A+B) (A+B)^{n-1-i}\\ &= (A+B)^i (A+B)^{n-i}. \end{align\*}$$

To help you learn how to do proofs like this, I suggest that you write a proof for each of these statements.

Once you understand those methods, you should be able to prove that your statement holds. It's just a more complicated version of these examples.

---
Tags: complexity-theory, time-complexity, space-complexity
---


title: Grid covering by rectangles

text:
# Question
Title: Grid covering by rectangles
We have a $N\_1 \times N\_2$ grid. We have a collection of rectangles on this grid, each rectangle can be represented as a $N\_1$-by-$N\_2$ binary matrix $R$. We want to cover the grid with those rectangles.

Is the decision version of this set cover problem NP-complete ?

* Input : Collection $\mathcal{C}=\\{R\_1,R\_2,\dots,R\_L\\}$ of rectangles on the grid (input size: $N\_1N\_2L$), and $K \in \mathbb{N}^+$
* Output : Subset $\mathcal{S}\subset\mathcal{C}$ with $|\mathcal{S}|\leq K$ and $\mathcal{S}$ containing for each cell at least one rectangle covering it.

I found that the 1D case ($N\_2=1$) can be solved in polynomial time by dynamic programming: any optimal cover is going to be the union of

* an optimal cover for some subproblem of covering the first $N\_1-n\_1$ cells.
* a 1D rectangle, i.e. an interval, covering the remaining $n\_1$ cells.

I don't think however DP can work for the 2D problem: for the 1D problem, you have a $N\_1$ subproblems to solve, but for 2D you have $\binom{N\_1+N\_2}{N\_2}$ subproblems (number of North-East lattice paths on the grid).

I think the problem might be NP, but I am not sure (though it seems harder than P), and I have not succeed in finding a polynomial reduction from an NP-complete problem (3-SAT, Vertex Cover,...)

Any help or hint is welcome.

# Answer
> 4 votes
Thanks to j\_random\_hacker's hint, I've found a solution to reduce Vertex Cover to the Grid Problem:

We make a $|E|$-by-$|V|$ grid of 3-by-3 blocks, i.e. a $3|E|$-by-$3|V|$ grid, with vertices ordered as columns $\\{v\_1,\dots,v\_{N\_1}\\}$ and edges ordered as rows $\\{e\_1,\dots,e\_{N\_2}\\}$. We'll construct rectangles on this grid (the drawing below will help a lot understanding the different rectangles used)

For each vertex, we create a rectangle of type 1, which covers the central column of the column of blocks corresponding to that vertex, so we have $|V|$ rectangles of type 1.

Each block correspond to a unique couple $(e\_i,v\_j)$, with $e\_i=(v\_a,v\_b)$ for each block we add a rectangle of type 2 :

* if $j\<a$ or $b\<j$, this is a 3-by-3 rectangle covering the entire block.
* if $j=a$ (resp. $j=b$), this is a 3-by-1 rectangle covering of the left (resp. right) column of the block.
* if $a\<j\<b$, this is a 1-by-3 rectangle covering the top row of the block.

So we have $|E||V|$ rectangles of type 2, those rectangles will be obligatory to choose, as each will be the only cover for the top-left (or top-right) corner of the block it's in.

As we have said, each edge correspond to a row, with two blocks (let's call them endblocks) corresponding to the endpoints of the vertices $(e\_i,v\_a)$ and $(e\_i,v\_b)$, now we have rectangles of type 3:

* for endblock $(e\_i,v\_a)$ (resp. $(e\_i,v\_b)$), we have a 1-by-2 rectangle covering the top-right (resp. top-left) corner of the endblock.

We have $2|E|$ rectangles of type 3, and again, they're obligatory as each will be the only cover for the top-right corner (if it's the first endblock) or the top-left corner (if it's the second endblock) it's in.

Now, for each edge we construct rectangles of type 4, between the endblocks, we have two rectangles for the second row :

* One going from the central square of the first block to the central-left square of the second block.
* One going from the central-right square of the first block to the central square of the second block.
* And the same two rectangles for the third row.

We have $4|E|$ rectangles of type 4, those are not all obligatory however.

So now, to cover the grid:

* $|E|(|V|+2)$ rectangles (type 2 and 3) are obligatory and $|V|+4|E|$ (type 1 and 4) are optionnal.

To cover, for a given edge, the part between the edge endblocks not yet covered (second and third rows of the row of blocks), we can either use:

* the four rectangle of type 4.
* one rectangle of type 1 and two rectangles of type 4.

Note that in any case, we need at least two rectangles of type 4.

So here the cost function will be : $|E|(|V|+4) + k$

* If their is a valid vertex cover with less than k vertex: we use the $|E|(|V|+2)$ obligatory rectangles, then for the optionnal rectangles, we can use the rectangles of type 1 corresponding of the vertex cover, and for every row, we need only 2 rectangles of type 4 (we already have a rectangle of type 1). So if the graph has a valid vertex cover, the grid has a valid set cover.
* If we have a valid set cover for the grid (with less than $|E|(|V|+4) + k$) rectangles, then for each edge, either we already have a rectangle of type 1 (and the edge is "covered") or four rectangle of type 4, in which case, we can replace two of them by one rectangle of type 1, and we still have a valid cover with $|E|(|V|+4) + k$ rectangles. By iterating this process, we reach a valid solution with no row using four rectangle of type 4, from which we can obtain a valid vertex cover.

So the vertex cover can be reduced to the grid cover. And the grid problem instance can be encoded by $|E|(|V|+6) + |V|$ covers on a grid with $9|V||E|$ elements, so the reduction is polynomial and the grid problem is NPC.

PS : I noticed after writing this answer that a lot of rectangles are actually useless and much simpler reduction can be made using a $|E|$-by-$3|V|$ grid with $|V|+4|E|$ covers, using cost function $3|E|+k$

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


# Question
Title: Reason for finding partial order of a graph
In a recent algorithms course we had to form a condensation graph and compute its reflexive-transitive closure to get a partial order. But it was never really explained why we would want to do that in a graph. I understand the gist of a condensation graph in that it highlights the strongly connected components, but what does the partial order give us that the original graph did not?

The algorithm implemented went like this:

1. Find strongly connected components (I used Tarjan)
2. Create condensation graph for the SCCs
3. Form reflexive-transitive closure of adjacency matrix (I used Warshall)

Doing that forms the partial order, but.... what advantage does finding the partial order give us?

# Answer
One possible use: It lets you answer the question "is vertex $y$ reachable from vertex $x$?" in $O(1)$ time.
> 4 votes

---
Tags: algorithms, graphs
---


# Question
Title: Convolutional Neural Network Example in Tensorflow
I want to ask the dimension change in different convolution and max-pooling layer. I am referring to the example in TensorFlow tutorial:

http://tensorflow.org/tutorials/mnist/pros/index.html#deep-mnist-for-experts

The original image is a 28x28x1

The first convolutional layer:

1. apply convolution to a 5x5 patch with 32 features -\> 24x24x32
2. apply max-pooling 2x2 -\> 12x12x32

Second convolutional layer:

1. apply convolution to a 5x5 patch with 64 features -\> 8x8x64
2. apply max-pooling 2x2 -\> 4x4x64

But it said "Now that the image size has been reduced to 7x7" but my calculation seems to claim that it is a 4x4

Did I miss some concept? I am new to CNN so it may be a beginner question.

Thanks

# Answer
> 4 votes
Your calculation would be correct if the example were following the "usual" approach of having convolution chop off the edges.

Instead the example you pointed to says:

> How do we handle the boundaries? What is our stride size? In this example, we're always going to choose the vanilla version. Our convolutions uses a stride of one and **are zero padded so that the output is the same size as the input**.

So they are:

1. zero-padding the 28x28x1 image to 32x32x1
2. applying 5x5x32 convolution to get 28x28x32
3. max-pooling down to 14x14x32
4. zero-padding the 14x14x32 to 18x18x32
5. applying 5x5x32x64 convolution to get 14x14x64
6. max-pooling down to 7x7x64.

They probably have an option to turn the zero padding off. In other infrastructures I've used zero padding is not the default. (In several of the infrastructures I've used zero-padding isn't even possible.)

# Answer
> 3 votes
For CNN basic knowledge, apply the first convolutional layer (5x5x32) to original image, the size of image become from `28x28x1` to `28x28x32` and to `24x24x32`, both is right.

The different between `28x28x32` and `24x24x32` is the first result had **padding** and the second had **not padding**.

Why the tutorial select **padding**?
Because if we select **NO padding**, the result of features will become small, as you see from tutorial, after only one convolutional layer, the size become to `24x24x32`. And if we have multiple convolutional layer, the size of feature map will become smaller and smaller, and the same time, the features will not useful anymore.

Detail from tensorflow tutorial: https://www.tensorflow.org/tutorials/layers

> If filter width and height have the same value, you can instead specify a single integer for kernel\_size—e.g., kernel\_size=5.
>
> The `padding` argument specifies one of two enumerated values (case-insensitive): valid (default value) or same. To specify that the output tensor should have the same width and height values as the input tensor, we set `padding=same` here, which instructs TensorFlow to add 0 values to the edges of the output tensor to preserve width and height of 28. (`Without padding`, a 5x5 convolution over a 28x28 tensor will produce a 24x24 tensor, as there are 24x24 locations to extract a 5x5 tile from a 28x28 grid.)

The step explain for example could see:

---
Tags: neural-networks
---


# Question
Title: Which is better, Flood Fill or Scanline Fill algorithm ?
Which is better, Flood Fill or Scanline Fill algorithm in computer graphics? My thoughts says that both of them has the same efficiency in term of time and space complexity. Maybe you guys have another thinking? Thanks

# Answer
> 1 votes
They have different purposes.

Flood fill implies that you have a graph with neighbours and a starting node. You need a data structure to hold the frontier of nodes you still have to fill (and possible one for all the nodes you have visited). But each node is visited exactly once.

Whereas the scanline implies that you have points in a coordinate system. Each point you visit may add new points of interest further along. You need a data structure to hold the sorted points.

---
Tags: algorithms
---


# Question
Title: Is Equality problem decidable in DCFL and CFL?
Equality problem is checking if 2 DCFL's or CFL's are producing same language.

I read that it is decidable for DCFL and undecidable for CFL.

If we consider a DCFL like a^n b^2n / n\>=1, here we can draw a PDA for this in two ways. So how can we check if 2 DCFL's produce the same language by just looking at the PDA as they are not unique?

# Answer
> 2 votes
We can't. Infinitely many different PDAs for the same DCFL exist.

In 1997, Géraud Sénizergues proved that equivalence of DCFLs is decidable, and he was awarded the Gödel Prize for it.

For general context-free languages, it is undecidable. As a matter of fact, it is already undecidable for linear context-free languages.

---
Tags: computability, context-free, undecidability
---


# Question
Title: How to generate regular expression for language of regular expressions?
Alphabets = $\\{0, 1, \epsilon, \emptyset, \[, \], \cup, \circ, \star\\}$ where $\circ$ stands for concatenation, $\star$ is kleene star, $\epsilon$ is empty string, $\[$ and $\]$ are brackets to be used for language to be generated. Only those Regular Expressions to be considered which don't have nested brackets $\[\[\]\]$.

How to handle $\[ \ \]$ in this problem ? An expression can be - $\[1\star\star \cup 0\] \cup \[\epsilon \cup 1 \circ 0\] \cup 1\star$

What would be a regular expression that describes the language of such regular expressions?

Edit -

I want to come up with Regular Expression for the **Language of Regular Expressions** as show in example above. One thing though is that the regular expression should not generate such expressions which contains nested bracket ( we don't want to consider that ) so $\[1 \cup \[0 \cup \epsilon\]\]$ is not valid and should not be generated by the Regular Expression. What I have done and my understanding so far - For single character Regular Expression would be $(0 \cup 1 \cup \epsilon \cup \phi)$. Be reminded that we are creating regular expression for Language of Regular Expressions. So $(0 \cup 1 \cup \epsilon \cup \phi)$ accepts these regular expressions - $0$ , $1$ , $\epsilon$ , $\phi$.

For $0\star\star$ kind of expressions - $(0 \cup 1 \cup \epsilon \cup \phi)\star^{\star}$ should work.

For $0\star\star \cup 1\star$ types we can have $(0 \cup 1 \cup \epsilon \cup \phi)\star^{\star} \bigcup\ (0 \cup 1 \cup \epsilon \cup \phi)\star^{\star}$

I am getting feeling that somewhere I need to use recursion. So I how to handle bracket $\[ \]$ in this case ? How to accept those expressions which have brackets and they are not nested ? If anyone can give me logic or direction to solve this problem competely that will also be ok.

# Answer
Let us consider first a simpler situation, in which you have only one "atom" $a$, only one binary operator $\circ$, and no unary operator. The expressions you are captured by $$ X (\circ X)^\*, \quad X = a+\[a(\circ a)^\*\]. $$ In order to get an actual regular expression, substitute $X$ (surrounded by parentheses) in the left expression.

Adding a postfix operation $\star$ isn't too difficult: $$ Y (\circ Y)^\*, \quad Y = A+\[A(\circ A)^\*\]\star^\*, \quad A= a\star^\*. $$

In order to get an actual regular expression, first substitute $A$ into $Y$, then $Y$ into the leftmost expression.

Finally, the expression you are looking for only differs in that there are several "atoms" and several binary operations: $$ Z (\circ Z)^\*, \quad Z = B+\[B((\cup + \circ) B)^\*\]\star^\*, \quad B= (0+1+\underline{\epsilon}+\underline{\emptyset})\star^\*. $$ Here $\underline{\epsilon},\underline{\emptyset}$ are the versions in your alphabet.
> 2 votes

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


# Question
Title: What is the optimal way to find unique combinations of N sets of integers
This is a simplification of a real world problem and only a small piece at that.

Example sets are

```
----------------------       ------------------------------------
| Set1 | Set2 | Set3 |  OR   | Set1 | Set2 | Set3 | Set4 | Set5 |
|--------------------|       |--------------------|--------------
| 1    | 10   | 40   |       | 1    | 1    | 1    | 1    | 1    |
| 2    | 12   | 45   |       | 2    | 2    | 2    | 2    | 2    |
| 3    | 13   | 51   |       | 3    | 3    | 3    | 3    | 3    |
| 4    | 20   | 61   |       | 4    | 4    | 4    | 4    | 4    |
| 5    | 25   | 76   |       | 5    | 5    | 5    | 5    | 5    |
|      | 31   | 78   |       ------------------------------------
|      |      | 81   |
----------------------

```

Real world constraints are

* Up to 12 sets
* N numbers in each set
* Only care about distinct combinations - (112), (211) and (121) are considered the same.

Example with desired result

```
----------------------
| Set1 | Set2 | Set3 |
|---------------------
| 1    | 1    | 1    |
| 2    | 2    | 2    |
| 3    | 3    | 3    |
----------------------
Results: [1,1,1],[1,1,2],[1,1,3],[1,2,2],[1,2,3],[1,3,3],[2,2,2],[2,2,3],[2,3,3],[3,3,3]

```

Generally real world examples tend to either be like the first example where there are a variable number in each set and they are different in each set, or like the second where there are the same items in each set. However there are no hard and fast rules.

A real world example of the latter is 10 sets with 40 values in each. To naively iterate that example would be $1x10^{16}$ iterations.

Are there any optimal algorithms I can implement to find distinct combinations? I am hoping that there is something clever that can be done when there are the same items in different sets, somehow excluding them once certain conditions are met, but i have failed to think of or find one.

# Answer
> -1 votes
This may be wrong
I don't follow the multiple set of the set input part of question

Have a loop for each N

Assume N = 3
L is length of array A

```
for(i = 0; i < L-2; i++)
    for(j = i + 1; j < L-1; j++)
        for(k = j + 1; k < L; k++)
            A[i], A[j], A[k]

```

I write poker software and this matches the number of combinations

---
Tags: algorithms, combinatorics
---


# Question
Title: What does it mean when its said that most Turing Machines are not programmable?
I was reading this article. In its third paragraph of the third section, named The Classical computational theory of mind, it said that **Most Turing Machines are not programmable**. I got the literal meaning out of the statement.
I have only done Automata Theory 101 and the way I know Turing Machine, not much is making sense. A Turing Machine has a set of rules for deciding whether to write or move (LEFT or RIGHT) given current state and symbol on current cell.
Doesn't this make Turing Machine programmable as rules are decided in advance? Correct me if I am wrong. What does the writer mean when he said, "Most Turing Machines are not programmable"?

# Answer
I think the point being made is that, as you say, the transition rules of any Turing machine are fixed in advance, so every Turing machine computes a fixed function of its input. Since the machine computes a fixed function of its input ("Count the number of 1s", "Determine if the graph represented has a perfect matching", etc.), it can't really be called programmable.

However, for some Turing machines (e.g., universal Turing machines), we treat one part of the input as being a program that should be executed using the rest of the input as input. These machines would be described as programmable in the context of the article you link.

---

I hereby declare actors to be programmable human beings.
> 3 votes

---
Tags: turing-machines, automata
---


title: Is a circle inside a polygon?

text:
# Question
Title: Is a circle inside a polygon?
How do I test if a **circle** (x,y,radius) is inside a **polygon** (\[x,y\],\[x,y\],\[x,y\],\[x,y\]...) without touching the edges?

*Update* I decided to do a point in polygon followed by a circle line collision on each edge, this let me know first if the circle was within the polygon and then told me if it was colliding with any of the edges.

# Answer
> 3 votes
Call the center point $(c\_x, c\_y)$. The function $d(p\_x,p\_y) = \sqrt{(p\_x-c\_x)^2+(p\_y-c\_y)^2}$ computes the distance from the point $(p\_x,p\_y)$ to the center of the circle.

For each edge of the polygon create its line equation from its two endpoints. If the two endpoints are $(a,b)$ and $(c,d)$ then this line is $y = (\frac{d-b}{c-a})\cdot(x-a) + b$. Solve for, $x$ and $y$ and plug this into the distance equation above, $d(x,y)$. Find the critical points by setting the partial derivatives equal to zero. Check that the critical points are further than the radius of the circle from the center of the circle.

If all critical points for all edges are more than the radius away from the center then the circle fits.

---
Tags: algorithms, computational-geometry, decision-problem, polygons
---


title: $O(n+nm) = O(nm) = O(m+nm)$?

text:
# Question
Title: $O(n+nm) = O(nm) = O(m+nm)$?
I am thinking about the worst-case space complexity of an algorithm.

Obviously, if $f \in O(nm)$ then $f \in O(n+nm)$. But is the converse true?

$O(m)+O(nm) = O(m+nm) = O(m(1+n)) = O(m)O(1+n) = O(m)O(n) = O(nm)$

If that were true then $O(n+nm) = O(m+nm)$

# Answer
As mentioned in the question, obviously $O(nm) \subseteq O(n + nm)$ as $n,m \rightarrow \infty $.

The reverse is also true when $n, m$ grow ever larger:

For all $n,m \geq 1 : m +nm \leq nm+nm = 2nm$ and so: $O(m+nm) \subseteq O(nm+nm) = O(2nm) = O(nm)$ as $n,m \rightarrow \infty$.

$O(2nm) = O(nm)$ as $n,m \rightarrow \infty$ is a property of big-O that follows directly from the definition.

With respect to the penultimate line in the question (the long sequence of equalities), there is some unusual notation. To make sense there, the product of two sets must be an element-wise product such as $O(n) \cdot O(m) =\\{fg ∣ f∈O(n), g∈O(m)\\}$. The ‘$+$’ sign before the first equal sign probably means the Minkowski sum A+B={a+b ∣ a∈A and b∈B} instead of A∪B, but in both cases the first equality would hold.
> 1 votes

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


title: Example of Random Binary Tree?

text:
# Question
Title: Example of Random Binary Tree?
I'm trying to understand what a random binary tree is. According to Wikipedia:

> Two different distributions are commonly used: binary trees formed by inserting nodes one at a time according to a random permutation, and binary trees chosen from a uniform discrete distribution...

If I start with a root and then append nodes randomly with no consideration to depth. Would that be considered a random binary tree? Or am I missing something?

# Answer
A random binary tree is any tree that is generated by any random process. So, yes. You have described a random process that generates a binary tree; you can describe the result as a random binary tree.

At a technical level, if you have any random variable whose values are binary trees, it would be reasonable to call that a "random binary tree".

Wikipedia is saying that there are two random processes that are particularly commonly considered. But those aren't the only possibilities. You've described a third possibility, and that's also valid.
> 2 votes

---
Tags: trees
---


# Question
Title: How to prove the outcome of both segment of code are equal
Is it possible to prove using induction? If possible what would be the steps to proof A=B?

Main thing i want to proof is outcome of two segments of code are same.

Below is the code:

Segment A:

```
int A (int x, int y) {
  if (y==0) return x;
  return A(y, x % y);
}

```

Segment B:

```
int B (int x, int y) {
   while (y!=0) {
      int t = y;
      y = x % y;
      x = t;
   }
   return x;
}

```

# Answer
*Proof idea*: first of all note that the version A is a recursive version of B. Both A and B halts when $y$ is 0, so in both cases computation lasts until $y$ reaches zero. In both versions the return value is $x$. Also note that each recursive call corresponds to a single step in the while loop. So you can prove that after each recursive call and after each step of the while-loop values of $x$ and $y$ are equals. Induction on the number of steps where we assume $x, y \> 0$.

*Base step: step 1*. In the recursive call (version A) $y$ value is passed as an argument and assigned to $x$ (stored in $x$), but new $y$ takes $x\\%y$. In other words, ($x\_{new} \leftarrow y\_{prev}$ and $y\_{new} \leftarrow x\_{prev} \\% y\_{prev}$). Similarly, in the version B the following assignments

```
int t = y;
y = x % y;
x = t;

```

implies that $x\_{new} \leftarrow y\_{prev}$ and $y\_{new} \leftarrow x\_{prev} \\% y\_{prev}$. So after the first step in both segments new $x$ and new $y$ values are equal.

*Induction*: assume that after $n$ steps of recursive call and while-loop $x$ and $y$ values are equal. Then by the same argument as in the Base step for step $n+1$ $x\_{new}$ and $y\_{new}$ in both codes are equal. Thus, when we $y = 0$ both segments return $x$s which are equal.

Alternatively, you could separately prove that both functions compute gcd of two integers $x$ and $y$ and deduce that they must give the same output for same inputs $x$ and $y$. You can do it yourself. Please look here.
> 1 votes

---
Tags: algorithms, correctness-proof
---


# Question
Title: Where to start on SJF Cpu schedualing homework problem?
So the question is;

For the following three jobs: P1: 10 (3,2,5); P2: 4 (2,2); P3: 16 (2,3,5,6) Execute the three jobs using Exp Ave Alpha =0.6, default=2

I know the formula to get the exponential average for a process is

Pn+1 = (alpha) * Tn + (1-alpha * Pn)

I am basically confused at where to start. Obviously, the value .6 gets plugged in for the alpha, but where does the 2 go in the formula? And with each iteration is N increased? Where do the first time quantum for each process (3, 2, 2) go into the equation?

I have searched all over the web for an explanation, but every video I see on SJF has a gant chart and is given arrival time and looks nothing like this problem.

# Answer
> 0 votes
Alright, so after reviewing with the professor, this is how this actually works.

The default of 2 means they all have an equal priority and just get run in order; process P1, P2, and P3.

Now, once we see P1 run for 3 quantums after the first burst, then we calculate its new prediction.

(0.6) * 2 \[original default\] + (0.4) * 3 \[last run\] = 1.2 + 1.2 = Prediction of 2.4

Same thing with P2 & P3 (both have a first burst of 2 quantums.)

(0.6) * 2 \[original default\] + (0.4)\* 2 \[last run\] = 1.2 + 0.8 = Prediction of 2.0

So for the next quantums' order, it would be P2, P3, THEN P1.

Then after that run you would just do;

(0.6) * \[2nd to last burst\] + (0.4) * \[last burst\] = new prediction to figure out which proces would run next.

So the actual order would be;

Quantum: Process

Q3: P1:3

Q5: P2:2

Q7: P3:2

Q8: P2:2 (FINISHES)

Q12: P3:3

Q14: P1:2

Q19: P3:5

Q24: P1:5 (FINISHES)

Q30: P3:6 (FINISHES)

---
Tags: process-scheduling
---


# Question
Title: How to use a logistic regression classifier to estimate the confidence of a rule?
The following is an excerpt from the Estimating LAT Confidence section of this paper:

> ... Since some LAT detection rules are more reliable than others, we would like to have a confidence value in each LAT that can be used to weight each LAT appropriately during answer scoring. To accomplish this, we trained a logistic regression classifier using a manually annotated gold standard. The classifier uses the focus and LAT rules that have fired as features, along with other features from the parse, NER, and the prior probability of a particular word being a LAT...

It's not clear to me what is the target variable of the logistic regression classifier. It sounds to me that it is binary variable indicating whether the fired rule was correct (1) or incorrect (0). Therefore, the prediction of the logistic regression classifier is the probability that the word is an LAT given that a certain rule has been hired (and some other features). Does this application of the logistic regression classifier make sense?

The details of the paper are as follows:

A. Lally et al., "Question analysis: How Watson reads a clue," in IBM Journal of Research and Development, vol. 56, no. 3.4, pp. 2:1-2:14, May-June 2012. doi: 10.1147/JRD.2012.2184637

# Answer
> 0 votes
From context, I'd guess that the logistic regression classifier is used to predict the probability that a particular word is a LAT. This looks equivalent to predicting the probability that the fired rule was correct to flag that word as a LAT. This seems to make sense given the context.

---
Tags: machine-learning, natural-language-processing
---


# Question
Title: Why is the halting problem semi-decidable?
This is what is known about the halting problem and semi-decidability :-

The halting problem says that for a given input x and a machine H, we can't say whether the machine H halts or not on input x.

A language is said to be Semi-decidable if there exists a Turing machine which halts if a word belongs to the language (YES cases) and may reject or go into infinite loop if the word doesn't belong to the language (NO case).

Now, in the halting problem we can't say whether the machine will halt even if the input belongs to the language (YES cases). Then how is it Semi-decidable? I think it should be non-recursively enumerable or undecidable.

# Answer
> 16 votes
Tl;dr: "(say) whether or not it halts" and "(say) if it halts" are not the same thing. Use mathematics to avoid confusion induced by language ambiguity.

> Halting problem says that for a given input x and a machine H, we can't say whether the machine H halts or not on input x.

No, that's not what it says. The *halting problem* is the computational problem of deciding whether $H$ halts on $x$, given $x$ and $H$ as input. It is important to note that "decide" here means "say yes if it is so, and say no if it is not".

The *undecidability* of the halting problem states that there is no *single* algorithm (Turing machine) that solves the halting problem *for all* $H$ and $x$.

> Now, in halting problem we can't say whether the machine will halt even if the input belongs to the language (YES cases). Then how is it Semi-decidable?

After the above clarification, your confusion here should be clear. It doesn't matter what "we can say". The "semi halting problem" is relaxed: the algorithm still has to say "yes" if $H$ halts on $x$, but it can do whatever it please if it does not (except answer "yes").

This is trivial to implement: just run $H$ on $x$. If it halts, answer "yes". If not, it doesn't matter since we're allowed to loop.

---
Tags: computability, turing-machines, halting-problem, semi-decidability
---


# Question
Title: What advantage do quadratic basis functions have over gaussian basis functions in RBF implementations?
I've been reading up recently on radial basis functions, and I've recently moved from Gaussian basis functions of the form $\phi(x)=\exp(-\alpha||x-x\_i||)$ to multiquadratic basis functions. My source is this paper, which is referenced in an algorithm that I'm looking at.

The basis function for the multiquadratic RBF is given as $\phi(x)=\sqrt{||x-x\_i||^2+R^2}$, where $R$ is a shape parameter. While it's certainly possible to solve the set of linear equations in a basis function and get a valid result for any equation, this choice of basis functions seems odd. Compared to a Gaussian basis function, where the effect of a basis function with a large value of $||x-x\_i||$ approaches zero, multiquadratics grow increasingly rapidly as the radius increases.

Intuitively, this seems like a strange choice for a basis function, since distant points in a training data set would seemingly influence the results of a local solution more than nearby points. Why is this function used as a basis function, and what advantages does it have over something like a Gaussian basis function?

# Answer
> 3 votes
> ...a strange choice for a basis function, since distant points in a training data set would seemingly influence the results of a local solution more than nearby points. Why is this function used as a basis function?

The *sum* of their influences quickly fades away. It's well illustrated in 1d, where we can represent a spline either piece-wise, locally controlled, or as one, 'global' RBF sum with $|x|$ kernel (see here for example). This might seem strange as each $c\_i|x-x\_i|$ term is unbounded. Yet, together they cancel out automagically at a distance. You can see it by following the derivation at the link. Another example is a system of electric charges overall neutral.

> what advantages does it have over something like a Gaussian basis function?

Multiquadric and other globally supported RBF have a good *hole-filling* property: if you have holes that are irregular with unknown scales, they're going to be smoothly interpolated over according to surrounding trends from neighborhoods of *corresponding* scales. If your dataset has a regular sparsity of one radius you can estimate, you can use instead compactly supported RBF, or Gaussian RBF which is practically local.

---
Tags: algorithms, approximation
---


# Question
Title: Consensus anomaly about read-write registers and test&set
I read this answer below and got into another question.

Why is the consensus number for test-and-set, 2?

I also read that read/write registers have consensus number 1.

But I see that in test&set (also in compare&swap) by using read write registers alone, we still arrive at consensus.

I think I am missing something very fundamental here. Need help.

The protocol in the accepted answer of the link is as mentioned below

> Suppose that we have two threads 0 and 1 that need to reach consensus. We could do this by letting each thread follow the consensus protocol below:
>
> 1. Write your proposed value to A\[t\], where t is the thread id and A is an array of size 2
> 2. Perform the test-and-set instruction on some register R, with R initialised to 0.
> 3. If the return value is 0, you were first: return A\[t\]. Otherwise, you were second: return A\[|t−1|\].

# Answer
> 2 votes
Consensus number and consensus hierarchy are defined in the classic paper "Wait-Free Synchronization" by Maurice Herlihy, 1991.

Note the keyword: ***wait-free***.

Since you did not give the algorithms for test&set using read/write registers only, I guess that they are *not* wait-free. (They may be lock-free instead.)

---

***Added:***

After the discussions with the OP in the comments, I realize that the OP has not fully understood the difference between atomic test&set registers and atomic read/write registers. He/she thought that the protocol given in the post uses read/write registers only. In fact, it uses test&set registers/operations/instructions in the second step.

A test&set register supports the test&set operation, which is a combination of test and set that cannot be interrupted. See this wiki for more details.

---
Tags: distributed-systems, consensus
---


title: Solving a system of recurrences

text:
# Question
Title: Solving a system of recurrences
If the time complexity $T(n)$ of two functions $x(n)$ and $y(n)$ are mutually recursive, as in Time complexity of mutually recursive functions, this gives $T(n)=O(2^n)$. But how do you measure an algorithm with two or more (4 in the example below) recursive functions that are not necessarily mutually recursive?

**Example: Recursive Step Function**

$$ \begin{align\*} w(n)&= \begin{cases} w(n-1)+1 & \text{if } x(n-1)=y(n-1), \\ w(n-1) & \text{otherwise.} \end{cases} \\ x(n)&=8w(n). \\ y(n)&= \begin{cases} 1 & \text{if } w(n) \> w(n-1), \\ y(n-1)+1 & \text{otherwise.} \end{cases} \\ z(n) &= \begin{cases} z(n-1)+1 & \text{if } z(n-1) \< y(n-1) \text{ and } z(n-1)=1, \\ z(n-1)-1 & \text{if } z(n-1) \< y(n-1) \text{ and } z(n-1)\neq 1, \\ z(n-1) & \text{otherwise.} \end{cases} \end{align\*} $$

These functions loop until $w(n)=I$ and then output the value of $z(n)$, where $I$ is the user input value. This input value could be rather large. I get the worse case scenario is dependent on $w(n)$, as it increases slowly.

I have calculated that the function specifically $$w(n)=O\left(\frac{\sqrt{16n+16}}{8}+\frac12\right),$$ but I am new to time complexity. Could anyone help me to understand?

Here is the example in pseudocode:

```
SET w to 0
SET x to 1
SET y to 1
SET z to 0
GET i
REPEAT
    IF z<y and z=1 THEN
        z=z+1
    ELSEIF z<y and z != 1 THEN
        z=z-1
    ELSE do nothing
    IF x=y THEN
        w=w+1 and x=8*w and y=1
    ELSE
        x=8*w and y=y+1
UNTIL w=i
PRINT z

```

# Answer
You can prove by induction that it always holds that $z \leq 0$, and so $z \neq 1$ and $z \< y$. This allows the following simplification:

* Input: $i$
* $x,y,z,w \gets 1,1,0,0$
* Repeat:
* + $z \gets z-1$
* + If $x = y$ then $w \gets w+1$ and $y \gets 1$; Else $y \gets y+1$
* + $x \gets 8w$
* Until $w = i$
* Return $z$

The running time is proportional to the number of iterations of the loop (which also happens to be the negation of the output).

In the first iteration we have $x=y$ and so set $w\gets 1$, $x\gets 8$, $y\gets 1$. Eight iterations later, we have $x=y=8$ (at the beginning of the iteration), and so we set $w\gets 2$, $x\gets 16$, $y\gets 1$. Sixteen iterations later, we have $x=y=16$, and so we set $w\gets 3$, $x\gets 24$, $y\gets 1$.

In total, we see that the number of iterations is $$ 1 + 8(1 + \cdots + (i-1)) = 1 + 8\frac{i(i-1)}{2} = 4i(i-1)+1 = (2i-1)^2. $$ This shows that the output is $-(2i-1)^2$, and that the running time is $\Theta(i^2)$.
> 2 votes

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


title: Dyna-Q in non-deterministic domains

text:
# Question
Title: Dyna-Q in non-deterministic domains
I've implemented the Dyna-Q reinforcement learning algorithm and it works perfectly on a discrete deterministic environment, the cliff. However, when applying it to a continuous environment (mountain car) with discretized states (which introduces non-determinism), it fails everytime (using function approximation is not in question here).

My question is: Sutton's description of Dyna-Q explicitly mentions its applicability to deterministic domains. Are there necessary tweaks for it to work in non-deterministic domains?

# Answer
One approach is outlined in Tucker Balch's Machine Learning for Trading course on Udacity:

In a nutshell: create a $T\_c$ table ("T count") that counts the number of times each subsequent state is reached after taking an action in a given state. Initialize all values to 0.00001 to avoid division by 0 errors. While executing QLearning, observe $s,a,s^\prime$ and increment $T\_c\[s,a,s^\prime\]$.

Formula for calculating the probability of each s' from \[s,a\]

$$ \frac{T\_c\[s,a,s^\prime\]}{\sum\_i T\_c\[s,a,i\]}$$

* The numerator is the count of times s,a lead to each s'.
* The denominator is the sum of $T\_c\[s,a,:\]$ (normalizes each s' to its probability)

Dyna-Q then updates a state's expected reward as the weighted sum of the reward in each s' weighted by their relative probability.
> 2 votes

---
Tags: artificial-intelligence, reinforcement-learning
---


# Question
Title: Is there a name for this traversal-optimized representation of a binary tree data structure?
I have used a purely functional binary tree structure in which there is a single node that is "marked". It allows for $O(1)$ access and modification of the marked node's value, as well as $O(1)$ traversal upwards and downwards.

It is represented as a pair $(M, P)$, where $M$ is the marked sub-tree and $P$ is a list of parent segments. For example, in the following tree

, the blue subtree is "marked". Groups of nodes joined by solid lines are parent segments, and parent segments are separated by dotted lines.

The marked subtree could be represented as follows (where `Terminal` represents the absence of such a node in the diagram):

```
(Tree 17
    (Tree 19 Terminal Terminal)
    (Tree 23 Terminal Terminal))

```

The parents could be represented as:

```
[ (Right 13
      (Tree 29 Terminal Terminal))
, (Right 11
      (Tree 31 Terminal
          (Tree 37
              (Tree 41 Terminal Terminal)
              Terminal)))
, (Left 2
      (Tree 3
          (Tree 5
              (Tree 7 Terminal Terminal)
              Terminal)
          Terminal))
]

```
* The marked node's value can be accessed and modified in $O(1)$ because it is at the top of the marked subtree.
* Traversal downwards can be done by choosing one subtree and turning the previous node into a Left- or Right-valued tree that stores the other child, which is added to the list of parents.
* Traversal upwards can be done by converting the most direct parent from a Left- or Right-valued tree to a full tree by filling in the other side, and then using the result as the new marked subtree.

I used the term `AccessTree` for this representation of the tree, but I decided the name was unclear.

Has this representation of a tree ever been given a name? If so, what is it?

# Answer
> 3 votes
This representation is known as a "zipper" and is described by Gérard Huet in his paper "The Zipper":

> The basic idea is simple: the tree is turned inside-out like a returned glove, pointers from the root to the current position being reversed in a path structure. The current location holds both the downward current subtree and the upward path. All navigation and modification primitives operate on the location structure. Going up and down in the structure is analogous to closing and opening a zipper in a piece of clothing, whence the name.

---
Tags: data-structures, terminology, binary-trees
---


# Question
Title: 3-SAT and Systems of Nonlinear Modular Equations
**How is the 3-SAT problem reduced to solving for a system of nonlinear modular equations?**

I have read https://stackoverflow.com/questions/4294270/how-to-prove-that-a-problem-is-np-complete in how to prove that a problem is NP complete?. But how is this done for systems of nonlinear modular equations specifically?

In that question above, Albert S. lays out nice steps:

"In order to prove that a problem $L$ is NP-complete, we need to do the following steps:

* Prove your problem $L$ belongs to NP (that is that given a solution you can verify it in polynomial time)
* Select a known NP-complete problem $L'$
* Describe an algorithm $f$ that transforms $L'$ into $L$
* Prove that your algorithm is correct (formally: $x ∈ L'$ if and only if $f(x) ∈ L$ )
* Prove that also $f$ runs in polynomial time"

**In other words**

1) Where can one find (in the literature or elsewhere) the algorithm $f$ that reduced SAT to the problem of solving a system of nonlinear modular equations originally, so that he or she can better learn about the time complexity of nonlinear modular equations or 2) Could anyone answer below how it is reduced?

***Does SAT reduce to solving a system of problem q?***

***Problem q***

Given the coefficients $a$, are there any integer solutions for $x$? List them:$$a\_n x^n + \dots + a\_1 x + a\_0 = 0 \pmod m$$

# Answer
> 4 votes
The answer depends on whether we're talking about a single equation, or a system of equations; and whether the modulus $m$ is prime or composite.

## A single equation

When the modulus $m$ is prime, then you can find a solution to a single equation

$$a\_n x^n + \dots + a\_1 x + a\_0 = 0 \pmod m$$

in polynomial time (if one exists) by factoring the polynomial $a\_n x^n + \dots + a\_0$ over the finite field $\mathbb{F}\_m$. When $m$ is composite, finding a solution is (in general) at least as hard as factoring $m$. See e.g.,Is deciding if there's a solution to a single multivariate quadratic equation NP-hard?.

## System of equations

That's the situation for a *single* equation. In contrast, finding a solution to a *system* of (multiple of) these equations (in multiple unknowns) is NP-hard, regardless of whether $m$ is prime or composite. There's a simple reduction, if $m$ is prime. Each clause is translated to a nonlinear equation, e.g., $(x\_i \lor x\_j \lor x\_k)$ translates to the equation

$$(1-x\_i)(1-x\_j)(1-x\_k)=0 \pmod m.$$

As another example, $(\overline{x\_i} \lor x\_j \lor x\_k)$ translates to

$$x\_i (1-x\_j)(1-x\_k)=0 \pmod m.$$

Finally, for each variable $x\_i$ we add the equation

$$x\_i (1-x\_i) = 0 \pmod m$$

to force $x\_i$ to be 0 or 1 (this is unnecessary when $m=2$).

An extension of this idea works when $m$ is composite, too; if $m=pr$ where $p$ is prime, then multiply the left-hand-side of each equation above by the constant $r$. This yields a system of nonlinear equations of degree 3. If you want a system of nonlinear equations of degree 2, that is achievable too; translate the clause $(x\_i \lor x\_j \lor x\_k)$ to the two equations

$$(1-x\_i) (1-x\_j) = 1-y\_{i,j} \pmod m \qquad \qquad (1-y\_{i,j})(1-x\_k)=0 \pmod m$$

where $y\_{i,j}$ is a new fresh variable (different for each clause).

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


# Question
Title: Build max heap in which all the nodes at certain level are less than all the nodes at the level before them
Max-heap is called a "**strong**" max-heap if **all the nodes at certain level are less than all the nodes at the level before them**. What is the most efficient way to build such a heap from a given array?

I was thinking about something similar to the regular build heap algorithm: scanning the array from right to left, compare every node to all of the nodes at the level below her, replace her with the max node and continuing until it reaches to the right position. However, I'm not sure How to make it more efficient. Thanks

# Answer
Here's a simple way to approach it. Let's assume the array has $n = 2^k - 1$ distinct elements for convenience.

1. Find the median in $O(n)$ using quickselect.
2. Partition into two halves (greater and lesser-equal).
3. Insert the lesser-equal half all as leaf nodes (deepest empty nodes).
4. Repeat 1-3 on the greater half until you only have 1 value left which will be the max value.

Time complexity is: $$T(n) = T\left(\frac{n}{2}\right) + \Theta(n)$$ Which overall is linear $O(n)$ time complexity.
> 2 votes

---
Tags: data-structures, heaps
---


# Question
Title: What is best case and worst case for this algorithm?
I am supposed to create an algorithm for this statement: “Two input lists of size n have at least one element in common”

This is my algorithm:

```
bool func(L1, L2){
    val1, val2 = 0;
    for(int i=0; i<n; i++){
        val1=L1[i];
        for(int j=0; j<n; j++){
            val2 = L2[j];
            if(val2 = val1){
                return true;
            }
        }
    }
    return false;
}

```

I know that you use big-theta notation to solve it, but my problem is on how to get the equation T(n).

This is what I did: first statement executes n times, 2nd → n times, 3rd → n 3 times etc, and got 3n^3 + 2n + 3, which I am sure is wrong...

Once you find the equation, how do you find the best and worst case from it? And how do you even find the equation?

BTW, don't tell me to read this site or book or smth cause I am asking only after doing all that. I need direct help. Not hints. Thanks!

# Answer
> 1 votes
The best case is when L1\[0\] = L2\[0\]. The worst case is when both loops are executed "as much as possibile", so when the state with i=n and j=n is reached (L1\[n\] = L2\[n\] or L1 and L2 have no elements in common).

What about complexity? We are talking about the worst case, so instructions belonging to the first loop are executed n times, while statements in the second loop are executed n\*n = n2 times. All other statements are executed only once. So we have: n + n2 \+ 1. Your algorithm's time complexity is O(n2).

Hint: Sort algotithm perform O(nlogn), and then you can compare L1 and L2 in O(n).

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


# Question
Title: The read tape in the definition of L and NL (logarithmic space) (DLOGSPACE, NLOGSPACE) (sublinear space)
By the definition of **L=DLOGSPACE** or of **NL=NLOGSPACE** (or any sublinear space class) there is an extra tape (for the Turing machine): the input tape, which is only for reading - but for *arbitrary* reading. The machine can read the first 10 cells and then maybe go back to read the 1st und 2nd cell.

My question is: If we restrict the way of reading that every cell is read only one time (in one direction: the 1st, 2nd, 3rd,... to the last cell of the input - and then nothing can be read of the input tape!), will we get same classes **L** and **NL** or will we lose some languages?

# Answer
> 3 votes
For a complexity class $\mathcal{C}$, we can define read-$k$-times $\mathcal{C}$ to be the set of problems $S \in \mathcal{C}$ for which there exists a $k$ such that an accepting computation for $S$ on input $w$ reads each bit at most $k$.

A consequence of a result from *On lower bounds for read-$k$-times branching programs* (1991) by Borodin, Razborov and Smolensky gives a separation between deterministic log space with unbounded reads and non-deterministic log space with bounded reads:

**Proposition:** There is a problem $S$ for which $S \in L$ but $S \not\in \text{read-}k\text{-times } NL$.

This means, to answer your question, we lose some languages since $L \not\subseteq \text{read-}k\text{-times }NL$ but $L \subseteq NL$.

My source of this proposition is from *DynFO: A Parallel, Dynamic Complexity Class* due to Patnaik & Immerman, who cite the BRS paper.

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


# Question
Title: How to find a pair of array elements whose difference is smaller than the average difference?
How to find a pair of indices $1\le i \le n$,$1\le j \le n$, $i\neq j$ in array $A\[1..n\]$ such that $0\le A\[i\]-A\[j\]\le\frac{max(A)-min(A)}{n-1}$ in $\Theta(n)$ time? `max(A)` is the max number in the array while `min(A)` is the min number.

Let $avg=\frac{max(A)-min(A)}{n-1}$. If we sort the array $A$ and calculate the differences of adjacent members then $avg$ is the average difference.

I feel like the question has to do with order statistics (select algorithm) but I don't quite know how exactly.

# Answer
> 0 votes
Hint: to build intuition, suppose I told you that you want to find a pair of elements that differ by at most $1000$. Can you think of any way to find such a pair of elements? Would looking at the decimal representation of the numbers help? Could you characterize what their decimal representation would have to look like?

---
Tags: algorithms, arrays, searching
---


# Question
Title: Suggest structure for query $sumRange(low,high)$ which returns sum of elements whose key $k$ satisfies $low \le k \le high$ in $\Theta(\log n)$ time
> Suggest a data structure to perform a query $sumRange(low,high)$ which will return the sum of the elements whose key $k$ satisfies $low \le k \le high$ in $\Theta(\log n)$ time.

I found the original problem here (although it's for counting) but it runs in $\Theta(n)$ time. However, I think with additional data structures and/or improvements this can be done in $\Theta(\log n)$.

I think we need a balanced binary search tree, for example, red-black tree.

Then I thought of the following algorithm:

```
sumRange(low, high)
sum <- 0
temp
closestToLow <- findClosest(low)

if(low=closestToLow)
    sum += closestToLow.key

temp <- successor(closestToLow)
sum += temp.key

```

It will only find the `low` point and its successor. I guess we need a similar piece of code to find the `high` point. Not sure how to traverse in between though.

# Answer
Prefix sums or a 1-D summed area table suffice to answer those queries in $O(1)$ time. (Alternatively, you can augment a balanced binary search tree -- I will let you discover how.)
> 3 votes

---
Tags: data-structures
---


# Question
Title: Finite subsets of the Halting problem are decidable. Can I prove the correctness of Turing machines computing these subsets?
I am trying to wrap my hand around the undecidability proof of the Halting problem, and to me it really seems to be more of a proof about representation than decidability. Namely, the proof that some languages are undecidable by Turing machines seems to simply state that I cannot find finite representations for arbitrary countably infinite sets. So far so good. However, I do not see how this might ever be a problem in practice.

If I fix some machine $M$ and consider the language $L\_M = \\{M \mid \textrm{$M$ halts on empty input}\\}$. Clearly, $L\_M$ is decidable, because it either denotes the singleton set $\\{ M \\}$ or the empty set, but:

(1.) Can I always prove the correctness of some machine that decides $L\_M$?

(2.) Suppose I cannot always find a proof. Can I find some specific machine $M$, for which I can find a proof that I cannot prove or disprove whether it halts on a specific input?

My first question can also be seen from another viewpoint: If I was to formulate the Halting problem in natural language, it would state

"Does there exist a fixed strategy, so I can decide for every TM whether it halts or not."

But I am interested in the problem:

"Given some TM, can I come up with a strategy to decide whether it halts or not."

I guess that that this question is more about provability than decidability, but unfortunately I know very little about the former.

# Answer
> 4 votes
You cannot always prove the correctness of the true value of $L\_M$ (unless your proof system is inconsistent). Indeed, if you could, then given $M$, you could search for proofs that $L\_M = \emptyset$ and for proofs that $L\_M = \\{M\\}$, and eventually you'll find one, thus solving the halting problem.

Gödel's incompleteness theorem gives you a specific such machine. Suppose that your proof system is $P$ (for example, ZFC), and consider the machine $M$ that goes over all possible proofs in $P$, searching for a proof of contradiction, and halting if it finds one. Assuming that $P$ is consistent, we have $L\_M = \emptyset$, but if $P$ could prove that, then it follows that $P$ proves its own consistency, which is ruled out by Gödel's second incompleteness theorem (assuming $P$ is not too weak).

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


# Question
Title: What are the reasons for and against using normalized floating point?
Floating point number formats can be normalized or not, meaning that ‘normal’ floating point numbers have an implicit (hidden) leading bit 1 in the significand. For example, the binary IEEE 754 formats are normalized, but the decimal IEEE 754 formats are not, i.e., they have an explicit leading bit (or number).

The advantage I see is the larger range or precision possible. (Larger range if compared to a format with one less exponent bit; greater precision if compared to a format with one less significand bit.)

However, the downsides I see are:

1. Dealing with a more complex format during computations, e.g., normalization steps, the existence of subnormals.
2. The loss of significance information. With, e.g., decimal IEEE 754 formats, the number of significand digits can be expressed. This would be a very useful feature, e.g., when encoding measurements. I would think that such information could also be exploited during computations.

On the whole, I feel that the larger range or greater precision that can be got with one extra bit does not justify the loss of a qualitative aspect, significance information. So my question is:

*What are (other) reasons for or against using a normalized floating point format?*

Perhaps the reason is historical and now the choice would be different; also this information is of interest to me. Perhaps the arguments I gave are not valid; it would then be interesting to know why.

# Answer
> 3 votes
Your terminology is non-standard. There are floating-point formats with an implicit leading mantissa bit, and floating-point formats with an explicit leading mantissa bit. I'm not aware that this property has a name, but if you say that the leading mantissa bit is implicit or explicit, then everyone knows what you are talking about.

Denormalized numbers, in standard use of the word, are floating-point numbers where the leading mantissa bit is not set, and the exponent has the smallest possible value. Floating-point numbers with explicit leading mantissa bit can have the leading mantissa bit set to zero even though the exponent does not have the smallest possible value; such numbers are called unnormalized (not denormalised).

Your question isn't about denormalized numbers in the standard use of the word, but numbers with implicit leading mantissa bit.

The extra bit made available by having an implicit leading mantissa bit is very valuable. It turns into an additional 0.3 digits of precision, which is useful for double precision, and very useful for single precision. You would need a very, very good reason to throw that away.

Implicit mantissa bit is not more difficult to handle. All that is needed is adding the mantissa bit if the exponent is not the smallest possible biased value, which is 0. That's simple. An explicit leading mantissa bit requires handling of unnormalized numbers, which is a pain.

Storing significance information: You could do that with unnormalized numbers. This has two problems: One, nobody cares about significance information. Two, try defining what the result of common operations should be. Especially considering that most people will just want the maximum possible precision. Enjoy.

It is reasonably simple to keep track of and estimating rounding errors, if that's what you're after. This will be much simpler than using unnormalized numbers for that purpose.

# Answer
> 1 votes
Binary IEEE format include both normal and denormal ('subnormal') numbers. The purpose of subnormals is to avoid a gap between the smallest normal numbers and zero larger than the smallest difference between consecutive normal numbers.

This gap make generate instability in some calculations dealing with small numbers,... Denormal have a performance and/or complexity cost in software and hardware. Sometimes denormals are not handled or a fast mode is provided where all denormals are considered as zero.

(Here is an historical perspective from William Kahan, one of the original creators of the P754 format: https://people.eecs.berkeley.edu/~wkahan/ieee754status/754story.html)

---
Tags: floating-point, numeral-representations
---


# Question
Title: Algorithm to determine which vertices/edges would disconnect undirected graph if removed
Is anyone aware of an algorithm to determine which vertices/edges would disconnect an undirected graph if removed? For all vertices/edges.

Of course I could run a BFS for each vertex and for each edge to test if the remaining graph would be connected. But is there anything more efficient?

In the end I would like to uniformly draw a vertex/edge out of those that would not disconnect the graph, to make simulations for fail-over routing in a computer network.

# Answer
For vertices you could use articulation point algorithm that uses DFS and runs in $O(|V| + |E|)$ time. Similarly you could find bridges. Look here and here. But if there is no bridge and you are interested in cut-set (of edges) I guess you could use maximum flow minimum cut algorithm by assigning weight equal to 1 to each edge if they are not weighted. And finally if you are interested in subgraphs whose vertices are connected with each other (there is a path between each pair of vertices) then use an algorithm for computing strongly connected components.
> 5 votes

---
Tags: algorithms, graphs, connected
---


# Question
Title: Finding maximum rectangular frame in array of zeros and ones
I've recently come across a following problem. In a rectangular array of ones and zeros one has to find maximum non-degenerate rectangle whose sides are filled with ones. By "maximum" i mean any rectangle with maximum possible perimeter. By "non-degenerate" i mean that all sides consist of at least two cells. We do not care about the points inside the rectangle. The only requirement is that its sides consist of cells filled with ones.

I know how to solve a similar problem where one needs to find maximum rectangle totally filled with ones (i.e. not only its border, but its interior too). But with this problem i got stuck so any ideas will be highly appreciated. I believe that there is some smart $O(max(m,n)^3)$ solution but can't see it yet.

Thanks in advance.

**P.S.** This is not a problem from an ongoing competition, hometask problem or an interview question. The problem originates from KPI-OPEN 2017 competition. You can find original statement here (problem F): http://kpi-open.kpi.ua/problemset/kpi\_open\_2017\_2/eng.pdf

According to bounds on rectangle's size and time limitations there has to be at most cubic (or perhaps cubic-logarithmic) solution. As far as i know there were cubic solutions during the contest.

**P.P.S.** There is an algorithm which precomputes for each cell how many cells there are to the left and above it which are filled with ones. Using such precomputation we can easily solve the problem in $O(max(m,n)^4)$ considering all possible rectangles. We just iterate through all possible cells for upper left corner of rectangle and through all possible cells for lower right corner. With the precomputation we might check in $O(1)$ that our rectangle is appropriate and if it is we just update the answer. Unfortunately such approach is to slow.

# Answer
Yes, it is solvable in $O(\max(m,n)^3)$ time. In fact, it should be solvable in $O(\min(m,n)^2 \max(m,n))$ time -- e.g., if $m\<n$, it should be solvable in $O(m^2 n)$ time.

Let $N\_\text{down}(i,j)$ denote the number of cells that you can go down, starting from $(i,j)$, without encountering a zero. Similarly, let $N\_\text{right}(i,j)$ denote the number you can go right. You can precompute all of these values in $O(mn)$ time. Do you see how?

Now, I'm going to give you some hints, to help you solve this on your own. Hint #1:

> Suppose I told you that the left side of the rectangle is at column $j\_0$ and the right side is at column $j\_1$. Could you find the top and bottom sides of the rectangle with maximum perimeter? How efficiently could you find it?

Hint #2:

> Continuing from Hint #1 -- can you identify some necessary and sufficient conditions to recognize the upper-left corner of the rectangle, $(i\_0,j\_0)$? What would have to be true about the $N\_\text{down}$ and $N\_\text{right}$ values? Similarly for the lower-left corner.

Hint #3:

> Try a linear scan downwards in those two columns. In fact, all you need are the $N\_\text{right}$ values.
> 1 votes

---
Tags: algorithms, optimization, matrices
---


title: 2 means clustering

text:
# Question
Title: 2 means clustering
I had an exam in algorithms. The question stated:

> Given $n$ points in the plane, find an algorithm that finds two centers (which can be any centers in the plane) such that the sum of the squares of the distances from the points is minimized. Prove your algorithm and analyse its complexity.

As I understood this question it is just a $2$-means problem in $\mathbb{R}^2$.

So I proposed the following algorithm:

1. Fix some partition of the points into two sets (clusters).
2. compute the centers of mass in each set (cluster), this are the new centers.
3. Assign each point to the correct center.
4. Go to 2 if some point changed its center.

In the proof section I proposed that if we look at the optimal solution it must be that each center is assigned to one of my centers so it must be also the center of mass in the cluster, thus my centers are the same as the optimal.

My teacher said it is false and reduced all the points, where is my mistake?

# Answer
> 3 votes
Your proof makes no sense to me. I don't know what you mean by "each center is assigned to one of my centers". When writing a proof, you need to define all terms before first use, and use rigorous logic, where each step is logically implied by the prior step. You can't just write down some intuition that feels right; that's not a proof.

The claim is wrong. You are using Lloyd's k-means algorithm, but that is a heuristic not guaranteed to find the optimal answer.

If you are skeptical, try implementing your algorithm, implementing a brute-force algorithm to find the optimal answer (by trying all pairs of candidate centers), and test it on a million randomly generated testcases. I think you'll quickly discover that your algorithm doesn't always give the right answer.

---
Tags: algorithms, clustering
---


# Question
Title: Curry Howard correspondence to Predicate Logic?
So I'm trying to get my head round Curry-Howard. (I've tried at it several times, it's just not gelling/seems too abstract). To tackle something concrete, I'm working through the couple of Haskell tutorials linked from wikipedia, esp Tim Newsham's. There's also a useful discussion when Newsham posted the tutorial.

(But I'm going to ignore Newsham's and Piponi's `data` wrappers, and talk about the underlying types.) We have Hilbert's axiom scheme (expressed as **S**, **K** combinators); we have propositions as types; implication as function-arrow; and Modus Ponens as function application:

```
axK :: p -> q -> p
axK  = const
axS :: (p -> q -> r) -> (p -> q) -> p -> r
axS     f                g          x  = f x (g x)

modPons = ($);   infixl 0 `modPons`          -- infix Left, cp ($) is Right

```

Then I can derive the identity law:

```
ident     = axS `modPons` axK `modPons` axK  -- (S K K)
-- ident :: p -> p                           -- inferred

```

Having these types as bare typevars merely corresponding to propositions seems rather unimaginative. Can I use more of the type system to actually construct the propositions? I'm thinking:

```
data      IsNat n  = IsNat !n                -- [Note **]

data      Z        = Z
axNatZ ::            IsNat Z
axNatZ             = IsNat Z

data      S n      = S !n
axNatS :: IsNat n -> IsNat (S n)
axNatS   (IsNat n) = IsNat (S n)

twoIsNat = axNatS `modPons` (axNatS `modPons` axNatZ)
-- ===> IsNat (S (S Z))

```

**\[Note \**\]** I'm using strict constructors, as per the discussion thread, to avoid introducing **\_|\_**.

Where:

* `IsNat` is a predicate: making a proposition from a term.
* `n` is a variable.
* `S` is a function, making a term from a variable.
* `Z` is a constant (niladic function).

So I seem to have embedded (First-Order) Predicate Logic(?)

I appreciate my types are not very hygienic; I could easily mix up a typevar-as-proposition with a typevar-as-term. Perhaps I should use the `Kind` system to segregate them. OTOH my axioms would have to be spectacularly wrong to get to any conclusion.

I haven't expressed:

* universal quantifier: it's implicit for the free vars;
* existential quant: in effect constants could act as skolemised existentials;
* equality of terms: I've used repeated typevars in implications;
* relations: this seems to work, or is it fuddlement? ...

```
    data          PlusNat n m l  = PlusNat !n !m !l

    axPlusNatZ :: IsNat m       -> PlusNat Z m m
    axPlusNatZ   (IsNat m)       = PlusNat Z m m

    axPlusNatS :: PlusNat n m l -> PlusNat (S n) m (S l)
    axPlusNatS   (PlusNat n m l) = PlusNat (S n) m (S l)

    plus123 = axPlusNatS `modPons`
              (axPlusNatZ `modPons`
               (axNatS `modPons` (axNatS `modPons` axNatZ)) )
    -- ===> PlusNat (S Z) (S (S Z)) (S (S (S Z)))

```

Writing the axioms is easy, courtesy of Wadler's *Theorems for Free!*. Writing the proofs is hard work. (I shall drop the `modPons` and just use function application.)

Is this actually achieving a logic. Or is it crazy stuff? Should I stop before I do any more harm to my brain?

You're supposed to need Dependent Types to express FOPL in Curry-Howard. But I don't seem to be doing that(?)

# Answer
> 3 votes
To explain why I'm uncomfortable with Newsham's and (especially) Piponi's `data` wrappers ... (This is going to be more question than answer, but perhaps it'll work towards explaining what's wrong with my `IsNat` even though it seems very similar to Newsham.)

Piponi page 17 on has:

```
data Proposition = Proposition :-> Proposition
                  | Symbol String
                  | False deriving Eq

data Proof = MP Proof Proof
     | Axiom String Proposition deriving Eq

```

I see no types here. Spelling a data constructor `:->` does not make it function arrow; and spelling a data constructor `MP` (for Modus Ponens) does not make it function application. There's a 'smart constructor' operator `(@@)` for `MP`, but that doesn't apply no function: it merely does pattern matching on the `:->` constructor.

Newsham has (I'll start with the Implication section/Modus Ponens):

```
data Prop p = Prop p

data p :=> q = Imp (Prop p -> Prop q)

impInj :: (Prop p -> Prop q) -> Prop (p :=> q)
impInj p2q = Prop (Imp p2q)

impElim :: Prop p -> Prop (p :=> q) -> Prop q
impElim p (Prop (Imp p2q)) = p2q p

```

This looks more like it: we have types, function arrows, function application in `impElim`. The type constructor `Imp` with its injection and elimination rules mirror the proof tree structures in the *Lectures on Curry-Howard isomorphism*. But I'm nervous: why does `Imp` need a type constructor and data constructor? Again, spelling as `:=>` doesn't make that a function arrow. Why all this wrapping and unwrapping `Prop` constructors? Why not plain `Prop (p -> q)`?

So when I look at the 'Conjunction' section (which actually comes first):

```
data p :/\ q = And (Prop p) (Prop q)

andInj :: Prop p -> Prop q -> Prop (p :/\ q)
andInj p q = Prop (And p q)

andElimL :: Prop (p :/\ q) -> Prop p
andElimL (Prop (And p q)) = p

andElimR :: Prop (p :/\ q) -> Prop q
andElimR (Prop (And p q)) = q

```

Those `Elim` functions **don't** use function application. They merely pattern match on the constructors. There's no implicational structure for conjunction: we rely entirely that the 'programmer' has used only the `andInj` rule to build a type `(p :/\ q)`.

So when Newsham gets to the commutativity of conjunction:

```
commuteAnd :: Prop (p :/\ q) -> Prop (q :/\ p)
commuteAnd pq = andInj (andElimR pq) (andElimL pq)

```

And claims

> Notice that our Haskell proof did not contain any reference to the internal structure of the (:/\\) data type. Having defined and proven our rules "andInj", "andElimR" and "andElimL" we shouldn't ever have to peek into the implementation of the (:/\\) data type again.

I plain disagree:

* The signature for `commuteAnd` **does** rely on the internal structure of the `:/\` type constructor.
* Although the function definition looks like merely function application, in fact the `andElim`s **do** "peek" into the structure.

I'd expect we could prove the commutativity of conjunction from its definition, without needing an axiom to say so(?)

OK if I'm being so purist, what do I expect? This for conjunction is based on the Church encoding for pair:

```
type Conj p q r = Prop ((p -> q -> r) -> r)     -- not right, see later

andInj :: Prop p -> Prop q -> Conj p q r
andInj (Prop p) (Prop q) = Prop (\elim -> elim p q)

andElimL :: Conj p q p -> Prop p
andElimL (Prop conj) = Prop (conj axK)    -- axK is `const`

```

Now I can write `commuteAnd` using 'proper' function application:

```
--  commuteAnd :: (Conj p q r) -> (Conj q p r)
commuteAnd pq = andInj (andElimR pq) (andElimL pq)

```

That function definition is the same as Newsham's. But I've commented out the signature because GHC's inferred type is not general enough. It wants `Prop ((p -> p -> p) -> p) -> ((p -> p -> p) -> p)`. Which is only a fancy variation on the Identity law.

**Edit:** (After @DerekElkins first comment here.) Scrap all this:

> I've ended up in deep (and murky) water. I think my type for `Conj` needs to be more polymorphic, possiby Impredicative. I've mucked about trying to give a higher rank type:
>
> ```
> type Conj p q = Prop (forall r.((p -> q -> r) -> r))
>
> ```
>
> But GHC isn't playing. (And support for Impredicative polymorphism is "flaky".) And a `forall`-quantified thing like that looks suspiciously like the definition for False/uninhabited that I was expecting to use.

I do need a higher-rank type, but not Impredicative. And not on the type for `Conj` but for `commuteAnd`

```
commuteAnd :: (forall r. Conj p q r) -> (Conj q p r')
-- (same function for `commuteAnd` as above)

```

OK. I can happily swap arguments ad infinitum.

**\[End of Edit\]**

So my question: if it's legit what Newsham is doing with nesting constructors and pattern matching everywhere, then what's not legit about my `IsNat` and pattern matching?

---
Tags: type-theory, curry-howard, haskell
---


title: Matrix Sum, factorial(K) times

text:
# Question
Title: Matrix Sum, factorial(K) times
Given an N x M matrix. The task is to repeat the following steps K! times.

1. Add all the elements of the matrix and get a matrix sum (S) % mod 10^9 + 7
2. Add S to all the elements. % mod 10^9 + 7
3. Repeat.

What I can think of regarding the complexity it will O(K! x N x M).

But K ranges from 1 to 10^5 and this is a huge number of iterations for a computer to process.

Is there a way to optimize these operations so that these can be performed using less computational resources.

Thank You.

# Answer
Suppose that the original elements are $a\_{ij}^{(1)}$. Their sum is $S^{(1)} = \sum\_{ij} a\_{ij}^{(1)}$, and the new elements are $a\_{ij}^{(2)} = a\_{ij}^{(1)} + S^{(1)}$. The new sum is $S^{(2)} = \sum\_{ij} a\_{ij}^{(1)} + nmS^{(1)} = (1+nm)S^{(1)}$, and the new elements are $a\_{ij}^{(3)} = a\_{ij}^{(1)} + (2+nm)S^{(1)}$. The new sum is $S^{(3)} = S^{(1)} + nm(2+nm)S^{(1)} = (1+nm)^2S^{(1)}$, and so on.

More generally, you can prove by induction that $S^{(t)} = (1+nm)^{t-1} S^{(1)}$ and $a\_{ij}^{(t)} = a\_{ij}^{(1)} + \frac{(1+nm)^{t-1}-1}{nm} S^{(1)}$. It remains to find a fast way to calculate expressions such as $S^{(k!)} = (1+nm)^{k!-1} S^{(1)}$ modulo the given prime $p = 10^9 + 7$. You do the rest.
> 1 votes

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


# Question
Title: Prove that following graph problem is in $L$
I have some interesting problem:

> Prove that following problem is in $L$ (decidable in logarythmic time). *Decide if given undirected graph $G=(\\{1,\ldots,n\\}, E)$ such that $\forall\_{i,j\in \\{1,\ldots,n\\}} i\le j \to \operatorname{dist}(1, i) \le \operatorname{dist}(1,j)$.* Graph is represented as adjacent matrix.

This is exercise that I can't deal with it. I know USTCON problem and I suppose that it may be useful (crucial) here. However, I can't solve it. Can anyone try to help me defeat it ?

# Answer
> 2 votes
Let $N\_k$ be the set of vertices at distance $k$ from 1. A graph satisfies the property if the sets $N\_k$ are intervals, and $N\_{k-1} \< N\_k$ (every member of $N\_{k-1}$ is smaller than every member of $N\_k$). We will check this property inductively: assuming $N\_{k-1}$ is known (starting with $N\_0 = \\{1\\}$), we will show how to calculate $N\_k$ and verify that it has the correct properties.

Suppose that $N\_{k-1} = \\{a,\ldots,b\\}$. If $b = n$, we can stop. Otherwise, go over all neighbors of the vertices in $N\_{k-1}$, and record the minimal and maximal indices $c,d$ encountered among those larger than $b$. Verify that $c = b+1$. Now go over all $e \in \\{c,\ldots,d\\}$, and verify that it is a neighbor of some vertex in $N\_{k-1}$. If so, we have verified that $N\_k = \\{c,\ldots,d\\}$, and can continue with $N\_{k+1}$.

You can check that this algorithm can be implemented in logspace.

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


# Question
Title: How to write program to list all the function values without repeating?
Suppose I have a (recursive) function $f:\Bbb N\rightarrow\Bbb N$ whose range is infinite, and I want to list all the function values without repeating.

That is, if $f(0)=1,f(1)=1,f(2)=5,f(3)=6,f(4)=6,f(5)=2$, I need a program with outputs $1,5,6,2$ I need it to firstly list $1$, then $5$, then $6$ and then $2$.

My idea is: Start from $0$, firstly output $f(0)$, and then increase $0$ by $1$ to get $1$, look at what is $f(1)$, if it is equal to $f(0)$, then we do not output it, otherwise we output $f(1)$. And then look at $f(2)$, if it is equal to at least one of $f(0),f(1)$, then we do not write it out, otherwise we output $f(2)$. But so far I found my knowledge too poor to write a program in psudocode...

My attempt:

```
x := 0;

while (n < x)

{ if (f(n)=f(x));

 n := n+1;

else

return f(x)}

```

I think maybe this code is problematic. Could someone please tell me some way to write it? This is such a minor part of my math course that we are not taught how to write psudocodes and now I feel a bit frustrated...

Other simple ways to do it would also be appreciate. Thanks in advance to you all who may help!

To sum up, I wish to see a psudocode to out put all the values of the function:

$f':\text{n↦the nth value in the enumeration that isn't a repeat of a previous value}$ where $f$ is a recursive function. Apologize for my poor knowlege of computing. I have no backgroud of computing and even not know what is "memory", only psudocode is readable for me... And actually I just need the psudocode program to prove that this function is recursive.

Thank a lot to you all who leave answers and comments!

# Answer
You can implement your task by keeping track of the values that have appeared so far. You maintain an array $S$ that starts empty. You compute the values $f(0),f(1),f(2),\ldots$, and for each value, you check whether it is already in $S$; if so, you don't do anything; otherwise, you print it, and add it to $S$.
> 1 votes

---
Tags: algorithms, enumeration
---


# Question
Title: How do we know INVERSIONS-COUNT algorithm implemented in balanced tree really works?
How do we know INVERSIONS-COUNT algorithm (exercise 14.1-7 from here), implemented in balanced tree really works?

We assume that the tree data structure we're using is an order statistic tree which means that a) it's a balanced binary tree, b) each node $x$ is augmented with $size$ field which tells us the size of the node's subtree (its inner nodes, including $x$).

We also have an array $L\[1..n\]$ which contains the values of the keys of the tree (not necessarily sorted).

The algorithm uses two helper functions:

`RANK(Tree, node_x)` \- returns the rank of the key of `node_x` in array $L$.

`SEARCH(Tree, L[i])` \- returns the node with the same key as the element $L\[i\]$ in the given array.

This is the code:

```
Construct an order statistic tree T for all the elements in L
   t = −|L|
   for i from 0 to |L| − 1 do
      t = t + RANK(T, SEARCH(T, L[i]))
      remove the node corresponding to L[i] from T end for
   return t

```

If the array is sorted then there're no inversions. Therefore `t` is incremented each time by $1$ because in sorted array each new element is the minimal one and has rank $1$ (because we delete the last node).

If the array is not sorted then why are we guaranteed that the ranks will at some point "overtake" `t` and produce the correct amount of inversions?

# Answer
At step $i$, the rank of $L\[i\]$ in $T$ is the number of elements in $L\[i\],\ldots,L\[|L|-1\]$ which are at most $L\[i\]$. Taking into account the $-|L|$ in the beginning, we see that the algorithm counts the number of pairs $i\<j$ such that $L\[j\] \leq L\[i\]$, which is exactly the number of inversions (assuming all elements are distinct).
> 3 votes

---
Tags: algorithms, algorithm-analysis, correctness-proof
---


# Question
Title: Theory of message complexity analysis of distributed systems
Inspired by this post, I thought it would be a good idea to ask an analogous question in the context of distributed systems -

While most of us are familiar with the notion of *Time Complexity* as a measure of efficiency of algorithms, In the world of distributed systems, another important measure of efficiency plays a preeminent role namely that of *Message Complexity*.

Specifically, when working in terms of the graph network model(i.e., algorithm instances executing on each node of a network pursuant of a network-level goal), it is the total number of bits of information that are cumulatively sent through each edge/connection of the system over the course of execution of the distributed system. My question is as follows:

* What are the usual techniques applied to calculating/bounding the message complexity cost of distributed algorithms?
* What is the generalised structure/theory behind these techniques?

# Answer
> 2 votes
S. Arora, B. Barak, Computational Complexity Modern Approach, Chapter 13 is a good introductory resource to this topic:

> Communication complexity concerns the following scenario. There are two players with unlimited computational power, each of whom holds an $n$ bit input, say $x$ and $y$. Neither knows the other’s input, and they wish to collaboratively compute $f(x, y)$ where the function $f : \\{0, 1\\}^n \times \\{0, 1\\}^n \rightarrow \\{0, 1\\}$ is known to both. Furthermore, they had foreseen this situation (e.g., one of the parties could be a spacecraft and the other could be the base station on earth), so they had already — before they knew their inputs $x, y$ — agreed upon a protocol for communication. The cost of this protocol is the number of bits communicated by the players for the worst-case choice of inputs $x, y$.

This chapter also covers lower bound methods: the fooling set method, the tiling method, the rank method, the discrepancy method. It gives also a brief overview of other communication models: randomized protocols, nondeterministic protocols, average case protocols, and asymmetric communication. At the end of the chapter it provides detailed reference to papers relating this topic.

---
Tags: algorithm-analysis, reference-request, distributed-systems, communication-complexity
---


# Question
Title: Can a KD tree be used as a decision tree through nearest neighbor queries?
If I were to construct a KD tree representing a sufficiently dense space, could it be used as a decision tree by querying it for the nearest neighbor to the point to classify?

# Answer
> 2 votes
Yes, you can. The scheme you are thinking of is called the nearest-neighbors classifier. Read the link for more details. In many settings it turns out to be a quite effective classification algorithm.

---
Tags: machine-learning, classification
---