# Question
Title: Optimal coverage of arbitrary mask by strided masks
Say we have bit mask with some bits on and off:

```
1001110010101

```

We want to "deduce pattern", by covering this mask with as few strided masks as possible.

By "strided mask" I mean masks like:

```
11111111....
01010101....
00100100....

```

We can choose any length of strided masks and we need to cover initial mask completely.

Say for

```
1001110010101

```

Answer might be 3:

```
1001110010101
1001
    11
        10101

```

But I am not sure even in this case -- may be we can do better?

More tricky example:

```
11011101

```

covered by only 2 strided masks:

```
01010101
10001

```

Naive solution is 3: 11, 111 and 1

I have feeling this problem may be well-known, something like regular Post Embedding or like Set Cover, but everything I know is not exactly this problem.

How do you think can we have good algorithm here or can we prove NP or even undecidability?

# Answer
> 3 votes
Your problem is known as *(exact) cover by arithmetic progressions* (depending on whether you allow overlaps or not). Both variants were shown to be NP-complete by Heath, Covering a Set with Arithmetic Progressions is NP-Complete.

---
Tags: algorithms, np-complete, combinatorics
---


# Question
Title: How can I best represent my 2D thrust problem as a linear programming problem?
While my question stems from game dev, the problem itself isn't as much about the game, but more about correctly representing my problem as a linear programming problem that I can solve with a linear programming library (alglib.net, in this case).

### Problem description

I'm creating a prototype of a 2D space game. The spaceship has various thrusters on it. For each thruster I have a unit vector representing its orientation, a vector representing its offset from center of mass, and a unit-less value representing its maximum thrust capability.

For each thruster, I want to calculate a value from 0 to 1 that I will use to determine a force vector for each thruster, which I then sum with the game engine to determine the net effect of the forces: `thruster.orientation * max_force * scale_factor`.

### Constraints

I also have some constraints for my linear programming problem. Based on two inputs: the desired translation of the space ship (a unit vector) and a value (tau) which represents the desired angular velocity change. My first constraint, which I am having no issue with yet, is that the sum of the cross products of each thruster's offset and orientation vectors, scaled by the max\_force and the to-be-calculated scaling factor, must equal the desired tau value. The other constraint, which I am having trouble with, is how to maximize movement in the desired direction while ensuring that the resulting vector points the same direction as the desired movement vector?

### What I have so far

The expression that I'm trying to maximize currently is:

```
x * thruster1.force + y * thruster2.force + z * thruster3.force ... etc.

```

for each thruster on the ship.

My constraints are:

```
x * thruster1.force * thruster1.cross_product + y * thruster2.force * thruster2.cross_product + z * thruster3.force * thruster3.cross_product ... etc.

```

```
desired_direction.x = x * thruster1.orientation.x * thruster1.force + y * thruster2.orientation.x * thruster2.force + thruster3.orientation.x * thruster3.force ... etc.

```

```
desired_direction.y = x * thruster1.orientation.y * thruster1.force + y * thruster2.orientation.y * thruster2.force + thruster3.orientation.y * thruster3.force ... etc.

```

I know these last two are wrong, but I can't figure out how to maximize the x and y components of the resulting vector of the summed forces *while also ensuring their normalized value is the same as the desired normalized direction*. The constraints for the x component and y component are fundamentally linked, but how do I represent that with my constraints? I want my spaceship to maximize movement in the desired direction.

I suspect my current representation is fundamentally flawed and I'm not approaching this from the right angle, but I'm a little stuck at this point.

# Answer
Let $s$ be a vector denoting the summed forces from the thrusters, and $d$ the desired direction. Then you want to maximize the dot-product $s \cdot d$, subject to the constraint that $s \cdot d^\top = 0$, where $d^\top$ is a vector that is orthogonal to $d$. This ensures that $s$ will point in the same direction as $d$, and will be as large as possible in that direction.
> 1 votes

---
Tags: linear-programming, computer-games
---


# Question
Title: How are bitwise operators used in normalisation of floating-point numbers?
After having spent a significant amount of time googling this topic, I am still struggling to confidently answer the following question:

```
Identify the process using logical operators to normalise a floating-point number.

```

My first assumption was, we use the binary shift to remove the leading 0's (for positive numbers) or 1's (for negative numbers) and then use XOR to increase the exponent by the required amount.

I do not understand, however, what happens to the binary point.

Let's say we have the number 1.75 represented as 000001.11 in 8-bits. If I shift it to the right by one place, I lose the 1 at the end. If I shift it to the left by 4 places, how does the computer know to move the binary point between the first two bits from the left? I am lost. How do bitwise operations work in this case?

Thank you in advance for your time and help.

# Answer
It's helpful to think of the number in the following representation( I choose 3.75 as an example): $$2^0 * 11.11\_2 = 3.15$$ Now $2^0 = 1$ so we can just write it in front of the number. Now we want to normalize $3.75$ meaning we need to transform it to $2^e * 1.m$ where $e$ and $m$ are some bitstrings. Notice that we can shift a binary number to the left by dividing it by to e.g. $4 = 100\_2 = 2\* 010\_2 = 2\*2\* 001\_2$. I hope you can see how dividing/multiplying by 2 corresponds to shifting (in base 2!). Lets shift 3.75 in such a way that a 1 is in front of the comma: $2^0 * 11.11\_2 0 = 2^1\* 1.111\_2$; as you can see we shifted 3.75 and thereby pulled a $2$ out of it and increased the exponent to account for the $2$. The value of the number is still 3.75 it's just written down as $2\* 1.875$. This is the normalized form. Now the exponent $e$ and the places behind the comma are stored in a floating point number. Why don't we need the $1$ in front of the comma? Cause the normalized form guarantees that there is a 1 so it's redundant to store it.
> 0 votes

# Answer
Normalising floating-point numbers will most likely be done in hardware. It will use bit operations, but not visible to the programmer using it. And normalising will be done in very close conjunction with *rounding*.

Floating-point numbers usually consist of a sign bit, an exponent field, and a mantissa field. Since floating-point numbers are supposed to be normalised, which means the highest bit of the mantissa is supposed to be 1, this is often not stored. In addition, you will have tiny numbers that are *denormalised* (they are so small that if they were normalised, you wouldn't be able to store the exponent), and you have special values like infinities and not-a-numbers.

In floating-point arithmetic, usually the first step is detecting special values and handling them. For example, +inf / NaN = NaN, +inf * any positive number = +inf, etc. etc. There are lots of special cases, but you just follow the definition what the results should be. For multiplication and division, zeroes may also be handled as a special case.

For multiplication and division, you normalise denormalised numbers. You count the leading zero bits in the mantissa, then shift the mantissa to the left to have the leading bit set, and subtract the shift count from the exponent. You add or subtract the exponents and perform the multiplication division, giving a larger mantissa than needed. Depending on the inputs, the highest bit of the result mantissa may be cleared. In that case you shift the result mantissa to the left and decrease the exponent. Now you perform rounding based on the extra mantissa bits you have. Rounding can lead to overflow, in which case the exponent is increased. Finally you check the exponent: If it is too large, the result becomes infinity, If it is too small, the result will be a denormalised number, possibly zero.

For addition and subtraction, you need to have identical exponents. So you shift the mantissa with the smaller exponent to the right. Then you perform the addition or subtraction. You may have a huge number of leading zero bits, so you shift the mantissa to the left by possibly many bit positions and change the exponent. You don't change it to something lower than the exponent for denormalised numbers. And then you perform rounding, again checking for overflows.

So the bit operations that you perform are: Extracting sign bit, exponent and mantissa, processing sign bits. Normalising denormalised numbers by counting leading bits, shifting, and adjusting exponents. Normalising results again by counting leading bits etc. Rounding is done using logical operations.
> 0 votes

# Answer
You don't really specify from what representation you want to normalize the float.

If from an integer, no problem, you shift left by as many bits as it takes to let the most significant bit overflow, and adjust the exponent to compensate.

E.g. (single precision) $10000\_d=10011100010000\_b=\color{red}100111000100000000000000\_b\times2^{-10\_d}$.

If from a fixed-point binary representation, it is easy to turn it to integer by shifting the "decimal" point.

If from a decimal representation (char string), an option is to turn the number to scientific notation, convert the mantissa to binary (fixed-point) and combine with the suitable power of $10$. Then this power can be turned to a normalized floating-point value by $10^n=2^{n\log\_2(10)}=2^{\\{n\log\_2(10)\\}}2^{\lfloor n\log\_2(10)\rfloor}$.
> 0 votes

---
Tags: floating-point, bit-manipulation
---


# Question
Title: Partially correct?Totally correct?Deterministic?Determined?Terminating? What do these adjectives mean for an algorithm?
These terms are often used to describe algorithms but I'm not really sure what they mean. I would like to see more examples of what each one is like and how they can be identified. Can anyone please provide a thorough explanation or any links/books that can help me understand these terms better? thank you!

# Answer
> 3 votes
An algorithm is correct if it returns the intended output for all possible input instances.

As far as I know *partially correct* does not have any standard accepted meaning. If I was forced to assign a meaning to it, I would take it to mean that the algorithm returns the correct output for **some** input instances, although this is a very weak requirement...

Similarly, I'm not sure why one would need to specify that an algorithm is *totally* correct... that's probably just an alias for the definition of correct I gave above.

A *deterministic* algorithm is an algorithm that does not have access to any random bits, i.e., its execution is completely determined by the input instance.

I've never heard the concept of *determined* algorithm.

Terminating simply means that, for every input, the execution of the algorithm ends after some finite number of steps. To be pedantic, some definitions require algorithms to always terminate in a finite number of steps. It is possible that the term algorithm you encountered was used in a more relaxed sense that also encompasses non-terminating procedures.

---
Tags: algorithms, algorithm-analysis, programming-languages
---


# Question
Title: Algorithm to test whether a language specified in algebraic form is context-free
Is there an algorithm/systematic procedure to test whether a language is context-free?

In other words, given a language specified in algebraic form (think of something like $L=\\{a^n b^n a^n : n \in \mathbb{N}\\}$), test whether the language is context-free or not. Imagine we are writing a web service to help students with all their homeworks; you specify the language, and the web service outputs "context-free" or "not context-free". Is there any good approach to automating this?

There are of course techniques for manual proof, such as the pumping lemma, Ogden's lemma, Parikh's lemma, the Interchange lemma, and more here. However, they each require manual insight at some point, so it's not clear how to turn any of them into something algorithmic.

I see Kaveh has written elsewhere that the set of non-context-free languages is not recursively enumerable, so it seems there is no hope for any algorithm to work on all possible languages. Therefore, I suppose the web service would need to be able to output "context-free", "not context-free", or "I can't tell". Is there any algorithm that would often be able to provide an answer other than "I can't tell", on many of the languages one is likely to see in textbooks? How would you build such a web service?

---

To make this question well-posed, we need to decide how the user will specify the language. I'm open to suggestions, but I'm thinking something like this:

$$L = \\{E : S\\}$$

where $E$ is a word-expressions and $S$ is a system of linear inequalities over the length-variables, with the following definitions:

* Each of $x,y,z,\dots$ is a word-expression. (These represent variables that can hold any word in $\Sigma^\*$.)
* Each of $a,b,c,\dots$ is a word-expression. (Implicitly, $\Sigma=\\{a,b,c,\dots\\}$, so $a,b,c,\dots$ represent a single symbol in the underlying alphabet.)
* Each of $a^\eta,b^\eta,c^\eta,\dots$ is a word-expression, if $\eta$ is a length-variable.
* The concatenation of word-expressions is a word-expression.
* Each of $m,n,p,q,\dots$ is a length-variable. (These represent variables that can hold any natural number.)
* Each of $|x|,|y|,|z|,\dots$ is a length-variable. (These represent the length of a corresponding word.)

This seems broad enough to handle many of the cases we see in textbook exercises. Of course, you can substitute any other textual method of specifying a language in algebraic form, if you like.

# Answer
> 1 votes
The way I think we could handle this problem is devising a language which is context free if and only if a given word is in a recursively enumerable language, that is, if a Turing machine halts on a given input. If we can do this, we can reduce the problem $L \in CFL$ to the halting problem and deem it undecidable.

Let $L$ be a recusively enumerable language and let $M$ be a Turing machine such that $\mathcal{L}(M) = L$. Let $$ L\_{M} = \\{a^n c^k b^n | n \> 0 \land (k = n \iff M(n)\uparrow) \land (k = 0 \iff M(n)\downarrow)\\} $$

We have that $L\_{M}$ is context free if and only if for each $n$ $k = 0$, that is $$ L\_{M} \in CFL \iff \forall n ~M(n)\downarrow $$ which is undecidable. Therefore, there can't be an algorithm which can decide, in general, if $L \in CFL$.

# Answer
> 0 votes
By Rice's theorem, to see if the language accepted by a Turing machine has any non-trivial property (here: being context free) is not decidable. So you would have to restrict the power of your recognizing machinery (or description) to make it not Turing complete to hope for an answer.

For some language descriptions the answer is trivial: If it is by regular expressions, it is regular, thus context free. If it is by context free grammars, ditto.

# Answer
> -1 votes
There are Several Methods to Solve this. Let me Discuss one by one

1. Try to make a Context-free grammar, and then check whether all the production on the left-hand side is exactly one non-terminal symbol, then language is context-free.
Ex:- like if $aA\rightarrow Bc$ is in the context-free grammar then it's not context-free language .
2. Take a stack and push element of language into stack, and pop the element from stack when newly element wants to push into stack, like in a language
$L = \\{a^n b^n c^n : n \in \mathbb{N}\\}$
then push all $a$'s into stack and pop one $a$ when one $b$ wants to push into stack. Then there is no element which can nullify the remaining $n$ $a$'s. So this language is not context free. Must remember in context-free language only *one* comparison is allowed. But here are *two* comparisons. It's context sensitive language (CSL), which allow two comparisons.
3. Next approach is not straight forward. Means you can only check when language is not Context-free language (CFL). It's called Pumping Lemma.

# Answer
> -2 votes
Yes there a concept of Pumping Lemma which is a negativity test.

# Answer
> -3 votes
Try JFLAP software if you just want to check a CFG. You can maybe even ask JFLAP developers to give you the code or algorithm for the software. you can get JFLAP from here http://www.jflap.org/jflaptmp/ it is free however it requires JDK or JRE or something. Or maybe you can try some other similar softwares and their developers.

# Answer
> -4 votes
Any language is is accepted by a Push Down Automata, is a CFL. Here is a detailed breakdown to determine whether a language is CFL or not. check if language is CFL or not

---
Tags: algorithms, formal-languages, context-free, decision-problem
---


title: Difference between CTL and CTL*

text:
# Question
Title: Difference between CTL and CTL*
I am wondering what exactly the difference between CTL and CTL\* is. I know that CTL\* is strictly more expressive than CTL, but it is not clear to me how the "restrictions" to CTL accomplish that. I.e., why do we have to alternate quantifiers and do not allow negation nor conjunction (no boolean logic)?

In the book I am reading "Principles of Model Checking" by Baier & Katoen, the abstract syntax for CTL simply enforces the aforementioned restrictions by construction.

I would appreciate some "intuition" behind this, e.g., why are the restrictions necessary and where could these restrictions be stretched.

# Answer
> 3 votes
First, let's see a formula that's in CTL$^\*$ but not in CTL: $EGFp$. That is, there exists a path with infinitely many $p$'s.

One intuition (and **this is by no means a formal argument**) is that the "closest" CTL formulas are $EGEFp$ and $EGAFp$, and neither of them capture the same notion.

The motivation behind defining this restriction of CTL$^\*$ is that it still captures interesting properties, and it allows efficient model checking. The reason behind this efficiency is that CTL can be model-checked "bottom-up", and evaluating each path formula is easy, as these are simple formulas: just one temporal operator. If you allow arbitrary LTL within each path formula, you immediately get PSPACE hardness from LTL.

---
Tags: temporal-logic, computation-tree-logic
---


# Question
Title: Irregularity of $\{a^{b+cd} : d \in \mathbb{N}\}$
I was solving some basic problems about the theory of machines and automata. The topic was about pumping lemma, but I could not solve the below question and prove that it is not regular.

$$L=\\{a^{b+cd} \mid \text{$b$ and $c$ are constant, $d \in \\{0,1,2,3,…\\}$}\\}$$

This is my incomplete solution: Assume for contradiction that $L$ is a regular language. Since $L$ is infinite, we can apply the pumping lemma. Let $p$ be the integer in the pumping lemma. Pick a string $w$ such that $w ∈ L$ and $|w| \ge p$.

Example: pick $a ^ {1 + p}$ and $b,c = 1$. But now how should I get to a contradiction?

I will be grateful for any help.

# Answer
I think that the language is regular. Aside of counting $a$'s $b$ times, instead of thinking of counting $c$ times $d$ (counting a known number of times something unknown), we can think of counting $d$ times $c$ (counting an unknown number of times something known), of course. That is, we see $L$ as $$ L = a^ba^{cd} = a^b({a^c})^d $$ for two fixed $b$ and $c$.

We can draw a simple deterministic automaton for it:

Furthermore, we can see that the language is context free, as we can show a context-free grammar for it: \begin{align\*} &S = B ~ D ~ . \\ &B = a^b. \\ &D = a^cD ~|~ \epsilon. \end{align\*}

Then, since this language is defined on the singleton alphabet $\Sigma = \\{a\\}$, we know by Parikh's theorem that this language is regular.
> 2 votes

# Answer
For $b$ and $c$ fixed, this is a regular language. A corresponding regular expression would be $a^b(a^c)^\*$.
> 2 votes

---
Tags: regular-languages, proof-techniques, pumping-lemma
---


# Question
Title: extending bellman ford to find shortest weight paths with no repeating vertices
Is it possible to extend the Bellman Ford algorithm to output all shortest simple paths without repeating vertices?

The issue is that the Bellman Ford algorithm doesn't make any checks for whether the shortest "paths" it counts have repeating vertices. Also, if one were to keep track of all of these paths, I think it would be very inefficient. Breadth first search doesn't even come close to solving the issue, as it can't be used if edge weights are not all equal to a positive number. Dijkstra's algorithm doesn't work for negative weight edges.

> Note: Unlike in the Bellman ford algorithm, negative weight cycles are allowed; since each vertex in a shortest simple path must be distinct, a shortest simple path must always exist.

# Answer
> 2 votes
There won't be repeating vertices. If there was one, then there must have been a negative cycle that it is a part of - since otherwise (the cycle's weight is positive) you can "remove" the entire cycle and by that reduce the total path's weight, hence contradicting the fact that the original path was optimal.

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


# Question
Title: Can all teams in a tournament finish with the same points? If yes, how can there also be fewest drawn matches?
n teams play pairwise matches. If the match is a draw, both teams get 1 point.
The winner gets 3 points, and the loser gets 0 points otherwise. Is it possible that all n teams
finish with the same total points, and how? Could we devise an algorithm for it that
includes the fewest drawn matches among such a possibility?

**My Thoughts**
there will be n(n-1)/2 matches. And each team will play with other n-1 teams. There must
be a draw in the tournament. Because if there is no draw, that means for each match, one team gets 3 points, and the other gets 0 points. Suppose team i wins wi matches, so the total score of the team i = 3 * wi. Since the total score for all teams is the same, they
must have won the same number of matches and lost the same number of matches.
I am not sure how to proceed with this argument and whether showing that there will be
draws

# Answer
### A simple algorithm that let all teams finish with same points

Let $n$ teams sit around a circle evenly.

* If $n$ is odd, let each team win over the next $(n-1)/2$ teams clockwise.
* Otherwise $n$ is even. Let each team win over the next $n/2-1$ teams clockwise and draw with the team sitting opposite to it.

#### Why does the algorithm above also include the fewest draws?

In the case when $n$ is odd, each team gets $3(n-1)/2$ points and no draws. So the algorithm includes the fewest draws.

In the case when $n$ is even, each team gets $3(n/2-1)+1$ points. The total number of draws is $n/2$. The following lemma shows the algorithm achieves the desired goal.

---

**Lemma**. Assume that $n$ is even and at the end, each team gets the same point. Then there are at least $\frac n2$ draws.

**Proof**. Let $d$ be the number of draws.
A match contributes $2$ points if it ends in a draw. Otherwise, it contributes $3$ points. The total number of points is, $$ d \times 2 + (n(n-1)/2 - d) \times 3 = n(\frac{3n}2-1)-(\frac n2+d),$$ which means the total number of points is smaller than $n(\frac{3n}2-1)$.
Since each team scores the same points, the total number of points must be a multiple of $n$. So it is at most the largest multiple of $n$ that is smaller than $n(\frac{3n}2-1)$, i.e., it is at most $n(\frac{3n}2-2)$. $$ n(\frac{3n}2-1)-(\frac n2+d) \le n(\frac{3n}2-2)$$ which means, $$ d \ge \frac n2. \quad\quad\checkmark$$
> 1 votes

---
Tags: algorithms, combinatorics
---


# Question
Title: Failing to calculate the gradient and y-shift for best fit line using sum-squares method. Can anyone help me to pinpoint the issue?
I'm trying to work out how to make the working implementation of fitting the straight line among the set data points. I base my function:

```

pub fn sum_squares<Q: CanBeLabel>(l1: &Line<Q>, accuracy: u32) -> Point {

    let mut dataset_size: f32 = 0.;
    let (mut y_mean, mut x_mean): (f32, f32) = (0., 0.);
    let (mut y_max, mut x_max): (f32, f32) = (0., 0.);

    for point in l1.points() {
        dataset_size += 1.;
        y_mean += point.y;
        x_mean += point.x;

        if y_max < point.y {
            y_max = point.y;
        }

        if x_max < point.x {
            x_max = point.x;
        }
    }

    y_mean /= dataset_size;
    x_mean /= dataset_size;

    let fpa = |a: f32, b: f32| -> f32 {
        2. * dataset_size * a * x_mean * x_mean + 2. * dataset_size * x_mean * b - 2. * dataset_size * y_mean * x_mean
    };

    let fpb = |a: f32, b: f32| -> f32 {
        - (a * dataset_size * y_mean) + 2. * a * k * x_mean + 2. * dataset_size * b
    };

    let fpa2 = |b: f32| -> f32 { 2. * dataset_size * x_mean  };

    let fpb2 = |a: f32| -> f32 { 2. * dataset_size  };

    let mut a: f32 = y_max;
    let mut b: f32 = y_max;

    for _ in 0..accuracy {
        a -=  ( fpa(a, b) / fpa2(b));
        b -= (fpb(a, b) / fpb2(a));

    }

    return Point::new(a, b);
}

```

I base my function on the following expansion:

$\sum^{k}\_{n = 1}\left(y\_n-\left(ax\_n+b\right)\right)^2=$

$\sum^{k}\_{n = 1}{{(y}\_n^2-2y\_n\left(ax\_n+b\right)+\left(ax\_n+b\right)^2)}=$

$\sum^{k}\_{n = 1}\left(y\_n^2\ -2y\_nax\_n-2y\_nb+a^2{x\_n}^2+2a^2x\_nb+b^2\right)=$

$k\bar{y^2}\ -2k\bar{y}ax-2k\bar{y}b+{a^2k\bar{x}}^2+2a^2k\bar{x}b+kb^2$

and then take derivatives with respect to a, and b:

a. $0\ -\ 2k\bar{y}x\ -\ 0+{\ 2ak\bar{x}}^2\ +\ 4ak\bar{x}b\ \ +\ 0\ \equiv{\ 2ak\bar{x}}^2\ +\ \ 4ak\bar{x}b\ -\ 2k\bar{y}x$

b. $0\ -\ 0\ -\ 2k\bar{y}b\ +\ 0\ +\ 2a^2k\bar{x}b\ +\ kb^2\ \equiv2a^2k\bar{x}\ +\ 2kb\ -\ 2k\bar{y}b$

and then approximating the zeroes of the derivative via Newton-Raphson (so I also use second derivatives, where $2k\bar{x}^2 + 4k\bar{x}b$ is with respect to a and $2k - 2k\bar{y}$ with respect to b).

However when I plot my graph for a dataset consisting of 4 points where $x \in \[1,4\] \land x \in \mathbb{Z}$ and $y = x + 666$,

```
fn make_dataset() -> Line<String> {
    let mut ret: Line<String> = Line::new("Cats".to_owned());

    for i in 0..5 {
        ret.add_point(Point::new(i as f32, i as f32 + 7_f32));
    }

    ret
}

```

and for checking:

```
def make_line(a: float, b: float, xs: range):
    x, y = [], []
    for i in xs:
        x.append(i), y.append(a + 666)

    return x, y

```

for every pair of consequetive x values graph looks like so:

for odd x's:

for even x's:

# Answer
> 1 votes
Just like @gnasher729, I did not check your code nor your equations, which seem overly complicated. An explicit solution is

$$a=\frac{\sum\_k (y\_k-\overline y)(x\_k-\overline x)}{\sum\_k (x-\overline x)^2}$$

and

$$b=\overline y-a\overline x.$$

---

**Explanation:**

Note that by linearity (or by differentiating the global error on $b$),

$$\overline y=a\overline x+b$$ allows to eliminate $b$ and reduce the problem to the minimization of

$$\sum\_k(\hat y\_k-a\hat x\_k)^2$$ where the hat denotes centered variables. After differentiation on $a$,

$$\sum\_k\hat y\_k\hat x\_k-a\sum\_k\hat x\_k^2=0.$$

# Answer
> 0 votes
I really don't want to go and debug your code. But if you want a linear approximation by arbitrary functions $f\_i$ minimising the squares of errors, you create a system of linear equations, with the coefficients on the left side being the sums of $f\_i \cdot f\_j$, and on the right side you write the sums of $f\_i \cdot y$. You solve the system and that's it.

Accordingly, for approximation by two functions $f\_1(x) = x$ and $f\_2(x) = 1$ you create a system of two linear equations in two variables, with the four coefficients on the left side being the sums of x^2, x, x and 1, and the numbers on the right side being the sums of $x \cdot y$ and $1 \cdot y$.

This is all just linear algebra and linear equations, so using Newton-Raphson seems quite bizarre.

---
Tags: algorithms, approximation
---


# Question
Title: If all words have the same frequency, is the generated Huffman tree a balanced binary tree?
If all words have the same frequency, is the generated Huffman tree a balanced binary tree? At the same time, is the generated Huffman tree a complete binary tree?

# Answer
> 1 votes
Here are two ways to analyze what happens when the distribution is uniform over $n = 2^m$ many codewords. The situation for other values of $n$ is more complicated, but similar techniques might work.

**Minimum redundancy codes**

Suppose that $w\_1,\ldots,w\_n$ is a prefix code. According to Kraft's inequality, $$ \sum\_{i=1}^n 2^{-|w\_i|} \leq 1. $$ Since $x \mapsto 2^{-x}$ is strictly convex, $$ \frac{1}{n} \geq \frac{1}{n} \sum\_{i=1}^n 2^{-|w\_i|} \geq 2^{-\frac{1}{n} \sum\_{i=1}^n |w\_i|}, $$ with equality only if all $|w\_i|$ are equal. Taking the base 2 logarithm, this shows that $$ \log\_2 n \leq \frac{1}{n} \sum\_{i=1}^n |w\_i|, $$ with equality only if all $|w\_i|$ are equal to $\log\_2 n$. In particular, in any minimum redundancy code, all codewords have length $\log\_2 n$, and so the coding tree is a complete binary tree.

**Analyzing Huffman's algorithm**

Huffman's algorithm starts with the $n$ original codewords, each of weight $1/n$. In the first $n/2$ steps, the original codewords are paired up to $n/2$ many codewords of weight $2/n$. In the following $n/4$ steps, the new codewords are paired up to $n/4$ many codewords of weight $4/n$, and so on. Eventually, we get a coding tree which is a complete binary tree.

---
Tags: machine-learning, information-theory, huffman-coding
---


# Question
Title: Describe statement "Exactly k out of n variables should be true" in 2-SAT in time polynomial to n and k?
I have a list of $n$ variables, exactly $k$ of which should be true. Is it possible to encode this as a 2-SAT problem in time polynomial to $n$ and $k$?

# Answer
> 2 votes
If $x,y,z$ are three satisfying assignments of a 2SAT formula $\phi$, then the bitwise majority of $x,y,z$ is also a satisfying assignment $\phi$. To verify this, it suffices to check that this works for every clause of width 2.

If $n \geq k+2$, we can consider the following three assignments:

* $x\_i = y\_i = z\_i = 1$ for $i = 1,\ldots,k-1$.
* $x\_k = 1$, and all unspecified indices are $0$.
* $y\_{k+1} = 1$, and all unspecified indices are $0$.
* $z\_{k+2} = 1$, and all unspecified indices are $0$.

The majority of $x,y,z$ has only $k-1$ many $1$'s, and so when $n \geq k+2$, you cannot express your predicate in 2SAT at all. This still holds even if you allow extension variables, that is, if you allow formulas of the form $\phi(x,t)$ such that $\phi(x,t)$ holds for some $t$ iff at least $k$ of the $n$ variables in $x$ are true.

If $n = k+1$ and $k \geq 2$, we can consider the following three assignments:

* $x\_i = y\_i = z\_i = 1$ for $i = 1,\ldots,k-2$.
* $x\_{k-1} = x\_k = 1$ and $x\_{k+1} = 0$.
* $y\_{k-1} = y\_{k+1} = 1$ and $y\_k = 0$.
* $z\_{k-1} = 0$ and $z\_k = z\_{k+1} = 0$.

The majority of $x,y,z$ has $k+1$ many $1$'s, and so again the predicate is inexpressible.

If $n = k$ then you can use $x\_1 \land \cdots \land x\_n$, or $(x\_1 \lor t) \land (x\_1 \lor \lnot t) \land \cdots$ if you want the width to be exactly $2$.

If $(n,k) = (1,0)$ then you can use $\lnot x\_1$ (or $(\lnot x\_1 \lor t) \land (\lnot x\_1 \lor \lnot t)$ if you want the width to be strictly $2$), and if $(n,k) = (2,1)$ then you can use $(x\_1 \lor x\_2) \land (\lnot x\_1 \lor \lnot x\_2)$.

---
Tags: 2-sat
---


# Question
Title: Finding all combinations of length k that has at least one of the pairs of T is in it
Let there be a list of $n$ elements $S$. Let $T$ be a set with $m$ elements ($m \leq nC2$), with each element in $T$ being a pair of distinct elements of $S$. For $k\geq2$, is there a polynomial-time algorithm to find the number of combinations of length $k$ of the elements of $S$ that at least one of the elements of $T$ is a subset of it?

This is the same as asking: For all combinations of $S$ of length $k$, how many have any of its subsets of length $2$ in $T$.

# Answer
> 2 votes
Consider a monotone 2SAT formula — that is, each clause is a disjunction of two *positive* literals. You can think of the variables as your set $S$ and of the clauses as your set $T$. A falsifying assignment corresponds to a choice of elements from $S$ (the elements assigned false) that contains one of the subsets in $T$.

If you could solve your problem, then by going over all values of $k$, you could count the number of falsifying assignments, and so the number of satisfying assignment. Yet #Monotone-2SAT is #P-complete. See for example Fournier and Malod, Universal relations and #P-completeness.

---
Tags: sets, polynomial-time
---


title: How to work out the odd case?

text:
# Question
Title: How to work out the odd case?
I am trying to solve this by using Substitution method. My solution must work both for even n-s and odd n-s. For evens case I have solved it. But for the odd's case I am stuck at this point. Hot to continue?

# Answer
If you have a solution for *all* even numbers, it might be sufficient to realize $T(k+1) \ge T(k)$.

But generally this is proved by induction where the even numbers use the odd ones. There, you have two leads :

* Take good care of your bounds during your induction
* More simple (but with less efficient approximation) : prove it for powers of two with a given constant ; and then use those to prove the general case for another constant
> 1 votes

# Answer
If $n$ is even then

$$T(n)=2T\left(\left\lfloor\frac n2\right\rfloor\right)+n$$ and

$$T(n+1)=2T\left(\left\lfloor\frac{n+1}2\right\rfloor\right)+n+1=2T\left(\left\lfloor\frac n2\right\rfloor\right)+n+1=T(n)+1\>T(n).$$
> 1 votes

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


# Question
Title: Prove that there is no $DFA$ with less than $2^n$ states that accepts $L_n =\{w\in\Sigma^*_n\ |\ \exists\sigma\in\Sigma_n\ :\ ⋕_\sigma(w)=0\}$
I've faced this question in my homework and I couldn't provide elegant proof for it.

We're given $\Sigma\_n=\\{1,\dots,n\\}$ and a language: $$L\_n =\\{w\in\Sigma^\*\_n\ |\ \exists\sigma\in\Sigma\_n\ :\ ⋕\_\sigma(w)=0\\}$$ That is a language that consists of letters from $\Sigma\_n$ but doesn't contain all the letters.

***Question:*** We're asked to prove that there is no $DFA$ with less than $2^n$ states that accepts $L\_n$.

***Note:*** It's given that there is $NFA$ with $(n+1)$ states that accepts $L\_n$.

# Answer
> 3 votes
You can use the Myhill-Nerode theorem for the given task. You must provide at least $2^n$ prefixes $p\_i\in \Sigma\_n^\*$ belonging to the different equivalence classes, e.g. s.t. for every two prefixes $p\_i$, $p\_j$ there exists a suffix $s\_{i,j}$ s.t. $p\_i s\_{i,j}\in L\_n$ and $p\_j s\_{i,j}\notin L\_n$ or vice versa.

Given your task, such prefixes correspond to all possible subsets of the alphabet $\Sigma\_n$. There are $2^n$ such subsets, and the strings containing all the letters from the chosen subset $S\_i$ and no other letters definitely satisfy the Myhill-Nerode equivalence class criterion. Given two words $p\_i$, $p\_j$ corresponding to the subsets $S\_i$ and $S\_j$, s.t. $S\_i\not\subseteq S\_j$, the suffix $p\_k$ corresponding to the set $S\_k=\Sigma\_n\setminus S\_i$ discerns $p\_i$ and $p\_j$, since $p\_i p\_k\not\in L\_n$ and $p\_j p\_k\in L\_n$.

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


# Question
Title: Condition for detection of collision in an algorithmic problem
While solving This algorithm problem I was unable to come up with condition for the collision to occur ( other than the naive O(n^2) algorithm ) on reading the explanation they say

> Let’s deepen the observation. For a set of people with the same y coordinate, let’s consider “in what condition does a collision occurs?” Then we can see that a collision occurs if and only if the following two people collides: the leftmost person facing right, and the rightmost person facing left. In other words, among the people with the same y coordinate, all the people except for the two mentioned above is unimportant.

I am unable to understand how the two people who are at extremes of some `y=k` satisfy the condition it is quite possible that the two at extremes of this `y=k` face the same direction and there could exist some pair in between these extremes that satisfy the condition, can you help me understand if I'm wrong in understanding the solution?

# Answer
> 2 votes
Your concern is legitimate.

However,

* "the leftmost person facing right" means the leftmost person among all persons who face right.
* "the rightmost person facing left" means the rightmost person among all persons who face left.

---
Tags: algorithms, decision-problem, search-problem, square-grid
---


# Question
Title: Distance bound for convex combination of inputs
Let $f$ be a function of 2 variables. Consider $f\colon X \times Y \rightarrow Z$. Let $P\_i$ (for $i=1,\ldots,n$) be $n$ probability distributions on $X$, and let $Q$ be a distribution on $Z$.

We know that if we choose $X$ according to any of the $P\_i$ (the distribution on $Y$ is fixed throughout), $f\_{x \leftarrow P\_i}(X,Y)$ is at most $\epsilon$-away from $Q$ (say in $L\_1$ norm). Does the statement hold when $X$ is chosen according to some convex combination of $P\_i$?

My guess is it should, with an argument similar to max should be greater than the average (convex combination), but I am unable to prove it formally.

Note that $f$ need not be linear in $X$.

# Answer
Let $R\_i$ be the distribution of $f(X,Y)$ when $X \sim P\_i$, and let $R$ be the distribution when $X$ is chosen to some mixture of the $P\_i$, say $X \sim P\_i$ with probability $\alpha\_i$. Then $R$ is a mixture of the $R\_i$, with the same coefficients $\alpha\_i$.

We are given that for each $i$, $\\|R\_i - Z\\|\_1 \leq \epsilon$. Therefore $$ \\|R-Z\\|\_1 = \left\\|\sum\_i \alpha\_i (R\_i - Z)\right\\|\_1 \stackrel{(\ast)}\leq \sum\_i \alpha\_i \\|R\_i - Z\\|\_1 \leq \epsilon, $$ using the triangle inequality and linearity at the highlighted step.
> 2 votes

---
Tags: probability-theory
---


title: Sorting segments from high to low

text:
# Question
Title: Sorting segments from high to low
I have a set of segments. None of them intersect or touch each other, and none of them have slope $0$ or infinity (i.e. the endpoints have different $x$ and $y$). All segments have length $\> 0$.

What I want to achieve is, a sorting order similar to what would happen if they were ceilings in a house and rain falls on them. If rain falls on a segment $i$ which covers completely or partially $j$, then segment $i$ goes before $j$ in the order desired.

In the figure above, the order would be (using the black letters, not the blue ones):

```
h → f → g → i → k → j

```

Note that some other orderings are also possible, like for example:

```
h → f → g → i → j → k

```

What I have tried so far:

* Sweep line algorithm. I tried a vertical and horizontal approach, but got nowhere.
* Sorting the segments with C++'s `sort` procedure. I tried several comparators, for example using the cross product to check the orientation of one segment's endpoints against the compared segment, etc. I tried several ways, but none worked. Corner cases kept appearing.

I've also been thinking about somehow turning it into a graph and running some algorithm similar to topological sort. This idea is still in development and have no progress as of yet.

I think sweep line might work, but I don't exactly what and how to implement.

Any ideas appreciated.

# Answer
> 2 votes
For a point $A$, its coordinates are $(A\_x, A\_y)$.

#### When does a line segment cover another line segment?

Suppose we have line segments $\overline{AB}$ and $\overline{CD}$. Assume $A\_x\le B\_x$ and $C\_x\le D\_x$.

Let $k\_{\ell}$ be the slope of line segment $\ell$. Let $m=\max(A\_x,C\_x)$.

* $P:=A$ if $k\_{\overline{AB}}$ is infinity. Otherwise, $P:=(m,A\_x+k\_{\overline{AB}}(m-A\_x))$.
* $Q:=C$ if $k\_{\overline{CD}}$ is infinity. Otherwise, $Q:=(m,C\_x + k\_{\overline{CD}}(m-C\_x)$.

So, $P$ and $Q$ are points on $\overline{AB}$ and $\overline{CD}$ respectively that share the same $x$-coordinate.

Then $$\begin{aligned} \overline{AB}\text{ covers }\overline{CD}\ &\iff \ m\le \min(B\_x,D\_x) \text{ and } P\_y\gt Q\_y \\ \overline{CD}\text{ covers }\overline{AB}\ &\iff \ m\le \min(B\_x,D\_x) \text{ and } P\_y\lt Q\_y \\ \end{aligned}$$

#### The algorithm, which uses topological sort

1. For each line segment $g$, collect all line segments covered by it into a list, which will be denoted by $\mathcal C\[g\]$.
2. Let $stack$ be an empty stack and $visited$ be an empty set.

Define recursive function "$\mathsf{topo\\\_sort}$", mimicking Python syntax.
$\quad\quad$function $\mathsf{topo\\\_sort}$(line segment $high$):
$\quad\quad\quad\quad$if $high$ is not in $visited$:
$\quad\quad\quad\quad\quad\quad$Add $high$ to $visited$
$\quad\quad\quad\quad\quad\quad$for each line segment $low$ in $\mathcal C\[high\]$:
$\quad\quad\quad\quad\quad\quad\quad\quad$$\mathsf{topo\\\_sort}$(line segment $low$)
$\quad\quad\quad\quad\quad\quad$append $high$ to $stack$

3. For each line segment $h$, call $\mathsf{topo\\\_sort}$($h$).
4. Return all elements in $stack$ in the natural order of a stack.

The algorithm above runs in $O(n^2)$-time, where $n$ is the number of line segments, because of step 1.

#### A vertical sweep line

Let us use a vertical sweep line to implement the step 1 above, which will boost performance especially when there are not many pairs of covering line segments.

1. Initialize an empty map $\mathcal C$ and an empty set $S$.
2. Sort all endpoints of all line segments by $x$-coordinate.
3. For each endpoint $e$, do the following.
    * If $e$ is the left endpoint of line segment $r$.
        + For each line segment $\ell$ in $S$,
            - If $r$ covers $\ell$, add $\ell$ to $\mathcal C\[r\]$.
            - Else $\ell$ must cover $r$. Add $r$ to $\mathcal C\[\ell\]$.
        + Add $r$ to $S$.
    * Otherwise, $e$ is the right endpoint of some line segment $r$. Remove $r$ from $S$.

With this sweep line technique, the time-complexity of the algorithm is $O(\max(n\log n, c))$ where $c$ is the number of covering pairs.

# Answer
> 0 votes
I found an algorithm similar to the one posted by John, but with lower complexity.

First start by creating a comparator for the segment. This comparator is only used for the sweep line and doesn't work elsewhere, i.e. doesn't give you an actual topological order, but does give you a "partial" (?) order during the sweep line. This exploits the fact that during the sweep line, the segment events enter in order from left to right.

```
struct Segment {
  Point p, q; // endpoints

  // "to_vec()" transforms the segment to a vector
  // "^" is the operator for cross product.
  // "to" creates a vector from A to B

  bool operator<(const Segment& s) const {
    if (p.x < s.p.x) {
      // "this" enters first (in the sweep line)
      return (to_vec() ^ p.to(s.p)) < 0;
    } else {
      // "this" enters after the one being compared
      return (s.to_vec() ^ s.p.to(p)) > 0;
    }
  }
}

```

Then the sweep line.

Before starting, sort the segments by ascending X coordinate (only left endpoint). Then, assign an `idx` (index) starting from 0 to each segment. This must be done after sorting for the following code to work properly.

I explain the sweep line in the comments:

```
typedef pair<int, int> pii;

// ....

// Sort segments by left endpoint X
sort(segments.begin(), segments.end(),
       [](const Segment& a, const Segment& b) { return a.p.x < b.p.x; });

// Create a graph with the same amount of segments +1.
// The last node will be used for a imaginary node that's the
// starting point (i.e. imagine it coming from Y=infinite above)
vector<vector<int>> graph(N + 1);

// Assign an ID to each segment
for (int i = 0; i < N; i++) segments[i].idx = i;

// Create a Segment set. Starts empty.
// Note that this is a set with order (tree set)
set<Segment> s;

// Create a priority queue containing integer pairs.
// Order of the queue is ascending.
priority_queue<pii, vector<pii>, greater<pii>> events;

// For every segment
for (int i = 0; i < N; i++) {
  // Iterate through all the events in the priority queue until
  // the X value in the queue becomes higher than the current left endpoint
  // X value. In other words consume all values that are to the left of the
  // current segment. Delete them from the set as well as from the queue.
  while (!events.empty() && events.top().first < segments[i].p.x) {
    s.erase(segments.at(events.top().second));
    events.pop();
  }

  // Insert the segment in the set. This order won't be topological,
  // but it's enough for the current sweep line state.
  auto it = s.insert(segments[i]).first;

  // If the segment inserted is the first one in the set, then add it
  // to the imaginary node. Else add it to the previous one.
  // This is the step that gets faster than the algorithm of the accepted
  // answer, since we can find where to insert it in just one O(log N) step,
  // without caring how many covered segments there are.
  if (it == s.begin())
    graph[N].push_back(i);
  else
    graph.at((--it)->idx).push_back(i);

  // Insert the right endpoint X to the priority queue along with the current
  // segment index.
  events.push({segments[i].q.x, i});
}

```

Also it seems that `idx` must be set to each segment *after* sorting. By doing this, when doing the toposort it will deal with some corner cases such as:

Segment 1 enters the vertical sweep line. It's not covered, so it's parent in the DAG is the extra imaginary node. Segment 2 enters the vertical sweep line and it covers 1. It's not covered, so it's parent is the extra imaginary node.

But we didn't set segment 2 to be parent of segment 1. However, there's no problem, because when doing the toposort, and if we do it in the correct order, the post order traversal will be 1 2 0 (zero being the extra node), so we invert the array and remove the first element, becoming 2 1, which means that the segment 2 does cover 1 (although it may not necessarily cover it in some situations).

In other words, with this approach the resulting graph will have some edges "missing", but when you do the toposort, the segments which left endpoint X coordinate is higher will appear first in the toposort result anyway, so the missing edges don't matter.

**UPDATE:** My code is here:

https://github.com/ChrisVilches/Algorithms/blob/main/spoj/RAIN1-november\_rain.cpp

I refactored it a bit, so it's slightly different from annotated code I wrote above (for example instead of assigning a `idx` property, I just use the actual index in the array, and pass it to the set grouped as a `pair<Segment, int>`). Take a look at the `vector<Segment> sort_segments(vector<Segment>& segments)` method (also the `struct`s and `toposort` are of interest, maybe).

This program solves the *November Rain* problem (https://www.spoj.com/problems/RAIN1/) which only has 40,000 segments and at most 25 segments being covered at each X coordinate, so a slower algorithm works. But there's a more complicated problem called *Directing Rainfall* (https://open.kattis.com/problems/directingrainfall \- I haven't solved it yet) which requires a similar algorithm, but does not have any limit for how many segments are covered. I learnt this algorithm by checking some existing solutions to that last problem.

**Alternative implementation:**

A different implementation done by adding two events per each segment (enter and exit). The only problem is that there's a corner case for when there are two segments with endpoints with equal X coordinate, so I added +1 to the exiting coordinate. The previous implementation using a priority queue is safer, since it doesn't need to deal with this corner case.

```
  set<pair<Segment, int>> s;
  vector<tuple<ll, bool, int>> events;

  for (int i = 0; i < N; i++) {
    events.push_back({segments[i].p.x, true, i});
    events.push_back({segments[i].q.x + 1, false, i});
  }

  sort(events.begin(), events.end());

  for (const auto& [_, enter, idx] : events) {
    if (enter) {
      const auto it = s.insert({segments[idx], idx}).first;
      graph[it == s.begin() ? N : prev(it)->second].push_back(idx);
    } else {
      s.erase({segments[idx], idx});
    }
  }

```

---
Tags: algorithms, graphs, sorting, computational-geometry
---


title: Greedy filling unit intervals

text:
# Question
Title: Greedy filling unit intervals
I have unit intervals given such as $I = \\{\\{s\_1, s\_1 + 1\\}, ..., \\{s\_k, s\_k+1\\}\\}$ ($\forall s\_i \in \mathbb{R}$). I am given a list of $X$ reals, such that each of the reals belongs to at least one interval.

I am asked to suggest a greedy algorithm to minimize the number of intervals required to capture all reals from $X$.

My attempt: Sort intervals by starting (or equivalently finishing) time. Sort numbers in $X$. Then, for the first entry in (sorted) $X$, place it in the latest intervals that can catch it. Then check if the next element of $X$ fits in this interval, if not, place in the latest interval that can catch it.

Questions that arised: how can I prove the correctness of my algorithm?

# Answer
#### The greedy algorithm

1. Let $result$ be an empty set and let $last\\\_interval$ be none.
2. For each $num$ in sorted $X$:
    * If $num$ is not covered by the last interval:
        1. let $last\\\_interval$ be the interval with the latest starting time among all intervals that cover $num$.
        2. Add $last\\\_interval$ to $result$.
3. Return $result$.

#### How can we prove the greedy algorithm is correct?

Let us prove the greedy algorithm "stays ahead", since it is clear visually that each interval selected by the greedy algorithm always pushes the latest covered number (time) to the future as far as possible while covering all numbers earlier than that latest covered number.

We can capture that intuition by the formal claim below.

**Claim.** Suppose the greedy algorithm returns intervals $g\_1, g\_2, \cdots, g\_{n\_g}$. Suppose another algorithm returns intervals $a\_1, a\_2, \cdots, a\_{n\_a}$, which are, WLOG, also in increasing order of starting time. Then the finishing time of $g\_i$ is not earlier than that of $a\_i$ for all $i\le n\_g$ and $n\_g\le n\_a$.
**Proof.** It is easy to prove by induction on $i=1,2,\cdots$. Readers can fill the details.
> 4 votes

---
Tags: algorithms, sorting, greedy-algorithms, intervals
---


# Question
Title: Constructing a DFA with $\Sigma=\{0,1\}$ that accepts $L= (0\vert10)^*$
I am trying to construct a DFA with $\Sigma = \\{0,1\\}$ that accepts $L = (0\mid10)^\*$, below is my attempt, but I'm a bit stuck.

The quiz marked it wrong since there's no transition from $q\_1$ under $1$, but if I add a loop on $q\_1$ for $1$ onto itself then I'm not actually accepting $10$, it would be $110$?

# Answer
> 1 votes
I don't know how your teachers introduced you to the construction of deterministic finite automata. The brief introduction is that we have a way of converting regular expressions into ε-NFA, then into NFA and, finally, DFA, as shown here, (adapted from Hopcroft and Ullman's 1979 *Introduction to automata theory, languages and computation*):

In your case, you have a language described by a regex: $$ L = (0 | 10)^\* $$ To be as pedantic as possible, you may use the McNaughton–Yamada–Thompson algorithm to build an ε-NFA, then use the ε-closure method to build an NFA and the powerset construction to conclude with a DFA.

In this case, the regex is fairly simple and we can proceed by intuition. We want our automaton to accept the empty string ε, and we already know that our initial state will also be one of the final states:

Then, we know we may read a $0$ or a $1$, therefore we want two transitions out of the initial state for these two symbols:

of these two new states, we can read $0$ and accept the string, therefore $q\_1$ is final as well. When we read a $1$ we must read a $0$ after it, so we need to add a transition from $q\_2$ to $q\_1$:

Now, we considered what we can do when reading a symbol from the starting state $q\_0$. If we read a $1$ from state $q\_1$ we need it to be followed by a $0$ to be in a valid state, which is the same situation as state $q\_2$; if we read a $0$ in state $q\_1$ we can stay in the same state:

As @Nathaniel pointed out, technically there should be a sink state when reading a $1$ from state $q\_2$, which is something we won't accept. In my experience, this state is often left implicit and not drawn; however, to be precise, we can insert it:

Note that this DFA is not minimal. You can minimize it using one of Hopcroft's, Moore's or Brzozowski's algorithms.

# Answer
> 2 votes
The language of this automaton is $\mathcal{L}(((0|10)(0|1))^\*(0|10))$. It accepts $0110$ which is not in the language $\mathcal{L}((0|10)^\*)$.

There is a complete DFA with 3 states recognizing $\mathcal{L}((0|10)^\*)$, but you'd need to note the following:

* the start state must be a final state because $\varepsilon \in \mathcal{L}((0|10)^\*)$ ;
* you need a non-final sink state that you reach after reading $11$.

I will add more details if necessary.

---
Tags: finite-automata
---


# Question
Title: Trivial vertex cover in regular graph is 2-approximation Proof
I need to show that in any regular graph, taking all nodes gives a 2-approximation vertex cover.

My attempt: I am proving that every $k$-regular graph can be reduced to a 2-regular fully connected graph (ring). And then the ring case is trivial.

However, I am unable to show that in the actual graph, there was no smaller vertex cover than the one of size $|V|/2$. I tried by induction, but I am unsure if I should fix the number of nodes or the factor of regularness.

# Answer
> 2 votes
A $k$-regular graph with $n$ nodes has $nk/2$ edges. Since all vertices have degree $k$, no vertex cover can contain less than $\frac{nk/2}{k} = n/2$ vertices.

---
Tags: graphs, combinatorics, discrete-mathematics, set-cover, vertex-cover
---


# Question
Title: Construct a DFA with $\Sigma=\{0,1\}$ that accepts the language $\{ x \in \Sigma^* \mid x \notin L(0^*1^*) \}$
I am trying to construct a DFA with $\Sigma=\\{0,1\\}$ that accepts the language $\\{ x \in \Sigma^\* \mid x \notin \mathcal{L}(0^\*1^\*) \\}$. To do this I first tried constructing a DFA that accepts $x \in \mathcal{L}(0^\*1^\*)$ and then found the complement of that DFA by switching the accept states and non accept states. But the quiz marked this incorrect saying that the string '' should not be accepted?

This is my first DFA:

and this is the complement:

thanks

# Answer
The language $$ L = (0^\*1^\*) $$ is such that the empty string $\epsilon \in L$. We can see $L$ as the language composed of strings of any number of $0$ followed by any number of $1$. One DFA recognizing this language is composed of an initial and accepting state $q\_0$ with a self loop for the symbol $0$ and a transition to a new state $q\_1$ for the symbol $1$; the state $q\_1$ is accepting as well and also has a self loop for the symbol $1$.

What we know about $L^c$ is that:

1. it does not contain $\epsilon$, and
2. it does not contain strings composed **only** of any number of $0$ followed by any number of $1$.

That is, we want to read at least one symbol. So, first of all, if we start reading a sequence of $1$, we want to see at least one $0$, and at that point we can see any sequence of $0$ and $1$ and we will accept the string. If the string to recognize begins with a sequence of $0$, we need to see at least one $1$, then at least one $0$, then we'll accept any sequence of symbols.

This may be enough to solve the problem, but to do it with the "DFA-inversion" construction, try to think about your transition function $\delta$: is it total? That is, we have transitions defined from every state for every symbol? Or some are left implicit?

I think this "hints" are enough to think about your exercise in a different way, but if you have doubts comment for more details.
> 1 votes

---
Tags: finite-automata
---


# Question
Title: What is the language of this simple DFA with 4 states?
I wanted to say that the language is the set of strings that end with "101" but unfortunately it does not work. Take for example "110101", which is not accept by the dfa.

# Answer
#### Description in plain English

A binary string is accepted by the DFA iff its longest suffix that looks like $1010\cdots1$ has an odd number of $0$s.

In other words, A binary string is accepted by the DFA iff its longest suffix that starts and ends with 1 and alternates between 0 and 1 has an odd number of $0$s.

In other words, a binary string is accepted by the DFA iff it ends with $101$ and we will see an odd number of consecutive $01$s when we scan the string backwards from the last $0$.

More formally, a binary string is accepted by the DFA iff it ends with $101$ and the length of its longest suffix of the form $(10)^+1$ is $3 \pmod 4$.

#### Another description in plain English

A binary string is accepted by the DFA iff "it can be decomposed into a series of substrings each of which ends $101$ without containing any other instance of $101$".

This description is given in a comment by rici.

#### Two descriptions in regular expression

$$(0^\*1^\*(00^+1^\*)^\*101)^+$$ The above expression is also given by rici.

$$(\epsilon+0+(0+1)^\*(1+00))(1010)^\*101$$
> 4 votes

---
Tags: regular-expressions
---


# Question
Title: Prove there is a matching of size n/2 on a graph with 2n vertices each of degree n
Given underirected $n$-regular graph with $2n$ nodes, I am asked to show it has a matching of size $n/2$.

My attempt:

At each step I will also remove the edge from the graph that I am adding to the matching $M$ edges.

I start at random edge $(u,v)$ and add it to $M$. The degree of nodes $u$ and $v$ is now decreased. I am going to keep removing random edges $(u,v)$ such that before removing them both $u$ and $v$ have a degree $n$.

I will prove that I will never fail. Assume that after some step $i\<n/2$ there are no 2 nodes which both have degree $n$. However, this implies that there are only at most $2i+1$ nodes of degree $n$ in the initial graph, which is a contradiction.

My question is, whether suggesting a procedure is a valid proof to solve such problems?

# Answer
> 1 votes
Giving an algorithm is not enough, you must prove its correctness. Here your proof of correctness is not correct: you would need to assume that there are no two *adjacent* nodes, both with degree $n$.

---
Tags: graphs, combinatorics, discrete-mathematics, matching
---


# Question
Title: Why do we round from 1/2 when converting the LP to ILP for the weighted vertex cover problem?
I understand that to approximate a solution to the weighted vertex cover, we need to relax the integer linear program to a linear program which can be solved in polynomial time, but why do we round from 1/2 when converting it back to an ILP? Why aren't the bounds say, round down to 0 from 1/3 if a given vertex has value \<= 1/3 and round up to 1 if said vertex has value \> 1/3?

# Answer
> 1 votes
The constraints are $x\_u + x\_v \geq 1$ for all $uv \in E$. To get an integral solution, if you round up only values strictly more that $1/2$, then when your LP solution has $x^\*\_u = x^\*\_v = 1/2$, the rounding gives $x\_u = x\_v = 0$ which is not valid. So we must round from some threshold value $\alpha \leq 1/2$.

Can we choose $\alpha \< 1/2$? Yes, but the approximation ratio is $1/\alpha$ (because if $x^\*\_u = \alpha$, then $x\_u = 1$ and the associated cost goes from $w\_u x^\*\_u$ to $w\_u x\_u$, hence is multiplied by $1 / \alpha$). So rounding from $1/3$ is worse that rounding from $1/2$, but is nevertheless a valid approximation algorithm.

---
Tags: np-hard, linear-programming, weighted-graphs, integer-programming
---


# Question
Title: Context-free grammar for $\{1^i0^j1^k \mid i+2j=k\}$
Suppose $$L=\\{1^i0^j1^k\mid i+2j=k\\}$$

How can I construct a context-free grammar for $L$?

This is homework. Here is my attempt for the case when $L$ is defined with $i+2j=3k$ instead.

\begin{align\*} S&\to aaaSc| bbbBcc| abBc| aabBc|\lambda\\ B&\to bbbBcc| \lambda \end{align\*}

But it's not true because it accepts the string $s=a^2b^4c^3 \notin L$. How can I correct the above grammar?

# Answer
> 4 votes
The simplest solution to problems of this form is usually to just rearrange the terms.

We know that $k = i + 2j$, which is the same as $2j + i$. So the language's sentences are of the form $1^i0^j1^{2j+i}$. We can regroup that as $1^i(0^j1^{2j})1^i$. (Parentheses used only for grouping.)

You should be able to just read the grammar off of that.

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


# Question
Title: How to bound the size of Boolean circuits?
Every function $f\colon \\{ 0, 1 \\}^n \to \\{ 0, 1 \\}$ can be computed by a circuit over the standard unbounded fan-in basis $\mathcal{B}\_1 = \\{ \neg, (\vee^n)\_{n \in \mathbb{N}}, (\wedge^n)\_{n \in \mathbb{N}} \\}$ of depth $3$ and size $\mathcal{O}(2^n)$ *via* the disjunctive or conjunctive normal form. Now, we can transform each circuit over $\mathcal{B}\_1$ into a circuit over the standard bounded fan-in basis $\mathcal{B}\_0 = \\{ \neg, \vee, \wedge \\}$ by substituting a gate of fan-in $k$ by a circuit of depth $\mathcal{O}(\log k)$ and size $\mathcal{O}(k)$ and, since each gate of the original circuit has a fan-in smaller than $\mathcal{O}(2^n)$, we get a circuit of depth $\mathcal{O}(n)$ and size $\mathcal{O}(2^{2n})$. How does http://www.cs.umd.edu/~jkatz/complexity/f05/lecture4.pdf obtain a size bounded by $\mathcal{O}(n \cdot 2^n)$?

# Answer
Every function can be computed by a CNF (or a DNF). A CNF is the conjunction of up to $2^n$ clauses. Each clause involves up to $n$ variables. You can express each clause using a circuit of size $O(n)$, and the entire CNF using a circuit of size $O(n 2^n)$. In fact, this constructs a *formula* of size $O(n2^n)$.

The conversion from $\mathcal{B}\_1$ to $\mathcal{B}\_0$ doesn't increase the number of leaves in the circuit, and only increases the number of wires by a constant factor. It could increase the number of gates by an unbounded amount: for example, a fan-in $k$ AND gates translates to $k-1$ fan-in $2$ AND gates.

Lupanov improved the above bound to $O(2^n/n)$, which is tight due to a counting argument; see for example lecture notes of Jayalal Sarma. In the case of formulas, the tight bound is $O(2^n/\log n)$.
> 1 votes

---
Tags: circuits
---


# Question
Title: is duality principle in boolean algebra is true for every expression
Let say A = 1 and B = 1 and then A+B = 1 now by using duality(replacing or gate by and gate and 1 by 0) we can say that, A.B = 0 but this is not 0, because 1.1 = 1, so please anyone clear my misunderstanding here, Thank in advance

# Answer
$$\overline{A+B}=\overline A\cdot\overline B$$

and

$$\overline{A\cdot B}=\overline A+\overline B$$
> 1 votes

# Answer
Negation gives you $\overline{A}=0,\overline{B}=0$, so everything is ok in "and".
> 0 votes

---
Tags: logic, boolean-algebra, binary, digital-circuits
---


title: Matching superimposed image

text:
# Question
Title: Matching superimposed image
We are given two grayscale images, one of which contains a large, mostly contiguous patch from the other one. The patch can be altered with noise, its levels may be stretched, etc.

Here's an example

We would like to determine the region of the image which was copied onto the other image.

My first instinct was to look at the local correlation. I first apply a little bit of blur to eliminate some of the noise. Then, around each point, I can subtract a gaussian average, then look at the covariance weighted by that same Gaussian kernel. I normalize by the variances, measured in the same way, to get a correlation. If $G$ is the Gaussian blur operator, this is:

$$ \frac{G(A \times B) - G(A)G(B)}{\sqrt{(G(A^2)-G(A)^2)(G(B^2)-G(B)^2)}}$$

The result is... not too bad, not great:

Playing with the width of the kernel can help a bit. I've also try correlating Laplacians instead of the images themselves, but it seems to hurt more than it helps. I've also tried using the watershed algorithm on the correlation, and it just didn't give very good results.

I'm thinking part of my problem is not having a strong enough prior for what the patch should be like, perhaps a MRF would help here? **Besides MRF, are there some other techniques, perhaps more lightweight that would apply?** The other part is that correlation doesn't seem to be all that great at measuring the distance. There are places where the correlation is very high despite the images being very visually distinct. W**hat other metrics could be of use?**

# Answer
> 1 votes
Normalized correlation works very well to compensate contrast stretching. In fact, it works too well for your taste. When you match two pretty uniform, featureless areas, the correlation will be good even if their average levels mismatch completely. Simply because uniform areas are alike.

You can't have your cake and eat it too. If you want to drop the contrast invariance, use an unnormalized correlation. Otherwise, you can disregard regions of high correlation where the variance is low, or revert to comparison of the means.

# Answer
> 0 votes
I will assume the patch is the same position and is unchanged. Given this, you could try a two-step procedure with basic image processing methods:

Step 0 (optional): Align/register the two images.

Step 1: Compute local image similarity, on a pixel-wise basis.

Step 2: Find a large connected region in that similarity map where there is high similarity.

---

For Step 1, one approach is local correlation, as you used. You could also try normalized cross correlation if you think one image might be shifted slightly (e.g., by a subpixel amount). Another is to compute the square of the pixelwise difference of the two images. Yet another possibility: at coordinate $(x,y)$, extract a patch 7x7 patch from each image centered at $(x,y)$, compute some measure of image similarity (e.g., L2 distance, local correlation, you name it; possibly preceded by some image registration step) between those two patches, and use that as the similarity measure at $(x,y)$; do this for every coordinate.

For Step 2, you are looking for a large connected region with a high similarity score. One approach is to threshold followed by connected components. Another approach is a watershed transform. Another approach is to use image morphological operators (e.g., opening) followed by one of these methods. More generally, you could look at methods for blob detection.

With image processing tasks like this, you may need to experiment with a bunch of different methods and see which ones work well. When you experiment, I recommend that you implement, measure its effectiveness, also look at a random sample of 5-10 images and the results of the analysis on those images, and look at a random sample of 5-10 images that got handled incorrectly. This visualization can be helpful in understanding in what situations a method fails, which can sometimes suggest improvements to address those particular situations.

---
Tags: computer-vision, digital-image-processing
---


# Question
Title: How to build a deterministic finite automaton from a given one with a new definition for automaton language?
I was given a new definition for a language of an automaton.

> A word is part of the automaton language if and only if the automaton finished on an accepting state and it was in an accepting state at least once before
>
> Note: it doesn't have to be the same accepting state.

Now given a deterministic finite automaton $A$ that has a language according to the new definition, I need to find an algorithm to build a new deterministic finite automaton $B$ that has the same language but according to the default definition of a language, i.e. a word is part of the language if and only if the automaton has finished in an accepting state.

The algorithm I came up with is this:

1. keep the base of automaton $A$, the path to each accepting state remains the same
2. for each of $A$'s accepting state, remove it from the accepting states, and attach another $A$ automaton to it where it will be the initial state.

so if $A$ has $n$ accepting states I need $n + 1$ $A$ automata to build automaton $B$ which will have $n ^ 2$ accepting states. while this algorithm seems to be working I'm having a problem to formally describe it and show that it is indeed the same language. Moreover this seems unnecessarily complex and wasteful with so many accepting states, I don't think there should be more then $n$ accepting states in $B$ as well.

Therefore I came up with a new algorithm:

1. for each state in $A$ have another copy of it in $B$
2. for each of the states in the first copy of $A$ define the transition function the same way as $A$
3. for each of the accepting states in the first copy of $A$, first remove them from the accepting states set, then update the transition function so that using the second copy of all the states of $A$ there is a path from each formerly accepting state to the new accepting states as if it was the initial state.

The second algorithm seems to me to be a much better candidate as it uses only $2n$ states and thus a much simpler transition function is needed, but yet again I've hit the brick wall which is describing this algorithm formally and showing the equality between the language of the new $B$ automaton and $A$'s language.

How can I show this equality? and how should I describe the algorithm so it will be formally acceptable?

# Answer
Your second construction seems to work well.

This can be formalized by starting with the formal definion of an automaton and specifying the components of the new one. So for $\mathcal A=(Q,\Sigma,\delta,q\_{in},F)$ construct a new automaton $\mathcal A'=(Q',\Sigma,\delta',q'\_{in},F')$.

The state set $Q'$ consists of two copies of the original one, this can be implemented by a cartesian product $Q' = Q\times \\{1,2\\}$. States $(q,1)$ and $(q,2)$ are the new copies of original $q\in Q$. To start with, the new initial state equals $q'\_{in} = (q\_{in},1)$. Final states are in $F'= F\times\\{2\\}$. The transition relation consists of two types of transitions: either following the original relation in one of the copies, or moving to the second copy.

If intuition is not sufficent to convince the construction works, you can find a matching between computations of the two automata. They are essentiallly equal, except for the component-index.
> 4 votes

# Answer
You have described your "new algorithm" pretty clearly.

#### A formal description

The formal way to describe it would be something like the following. We will use the formal definition of deterministic finite automaton (DFA)

Input: a DFA $A=(Q,\Sigma, \delta, q0, F)$
Output: another DFA
Procedure:

1. Let $Q'=Q\times\\{\text{false},\text{true}\\} $ .
2. Define $\delta'$ such that for all $q\in Q$ and all $\sigma\in\Sigma$,
    * $\delta'((q,\text{false}), \sigma)= \begin{cases} (\delta(q, \sigma),\text{true})\ \text{ if }q\in F\\ (\delta(q, \sigma),\text{false})\ \text{ if }q\not\in F \end{cases}$
    * $\delta'((q,\text{true}), \sigma)=(\delta(q, \sigma),\text{true})$
3. Let $F'=\\{(f,\text{true})\mid f\in F\\}$
4. Return DFA $A'=(Q',\Sigma, \delta', (q0,\text{false}), F')$.

#### A proof that is good enough

It is easy to check that

* if the second component of each state in $A'$ is ignored, the transitions of $A'$ is exactly the same as that of $A$.
* the second component of each state in $A'$ tracks whether the first component has been to an accept state of $A$ during the previous transitions.

Since

* the second component of the initial state of $A'$ assumes no previous transitions to an accept state of $A$ by the first component,
* a state of $A'$ is an accept state iff
    + its first component is an accept state of $A$ and
    + its second component means the first component has been to an accept state of $A$ during the previous transitions,

the language accepted by $A'$ is exactly the language accepted by $A$ by the "new definition".

#### More formal proofs

To make the proof more formal, we should prove each of following separately, using detailed analysis of the transitions made by $A$ and $A'$ on an arbitrary input string $s$.

* if $s$ is accepted by $A$ by the "new definition", $s$ will be accepted by $A'$
* if $s$ is accepted by $A'$, $s$ will be accepted by $A$ by the "new definition".

To make the proof even more formal, we could use some formal proof system such as HOL Light, Isabelle, Coq, etc. However, that is way beyond the usual course of learning DFA.
> 3 votes

---
Tags: algorithms, formal-languages, automata, finite-automata
---


# Question
Title: Efficient sorting an array generated from random distribution
I need to sort an array of *n* real numbers that was randomly generated in this way:

I have a given set of *k* closed intervals: ***\[a1,b1\],\[a2,b2\],...,\[ak,bk\]*** whose beginning and end are natural numbers. These intervals may overlap. Each *i*-th interval is assigned a number *ci*, specifying the probability of drawing it. After drawing a certain interval ***\[ai,bi\]***, we draw a number from the interval ***\[ai,bi\]*** according to a uniform distribution and place it in the array.

For example, I have a given array **T = \[6.1, 1.2, 1.5, 3.5, 4.5, 2.5, 3.9, 7.8\]**, and an additional array with interval information in which there are triples *(ai,bi,ci)*: **P = \[(1, 5, 0.75) , (4, 8, 0.25)\]**

The answer is obviously **T = \[1.2, 1. 5, 2.5, 3.5, 3.9, 4.5, 6.1, 7.8\]**

My question is, knowing how these numbers in the array were drawn, can we sort this array more efficiently? For example, in linear time? I was thinking that perhaps some modified version of bucket sort could be used here, but I have no idea what that would look like.

If I described something unclear, please tell me, my English is far from perfect.

# Answer
I'm going to assume that $k$ is small compared to $n$, because otherwise there isn't a lot of point in trying to optimise this; the cost of preprocessing the $k$ intervals into some kind of order would overwhelm the cost of just sorting $n$ elements at the end.

One possible solution is to maintain $k$ arrays, one for each interval, sort them independently, and then perform a $k$-way merge. Using a min-heap, this final step will take $O(n \log k)$ time in the worst case, and more like $O(n + k \log k)$ time if the intervals do not overlap.
> 1 votes

---
Tags: algorithms, sorting, python
---


# Question
Title: Let L be a CFL. Is $\{1\} ^∗ ⊆ L$ a decidable problem? Is $\{1\}^∗ = L$ a decidable problem?
I am working on some automata questions and I have encountered this problem:

Let L be a CFL.

Is $\\{1\\}^∗ ⊆ L$ a decidable problem?

Is $\\{1\\}^∗ = L$ a decidable problem?

I literally have no idea how to solve this, any ideas/hints? Thanks in advance!

# Answer
Here are some reasonably well-known properties:

1. The intersection of a regular grammar and a context-free grammar is context free.
2. The complement of a regular grammar is regular.
3. A context-free language over a one-letter alphabet ("a unary language") is regular.
4. It is decidable whether the language of a context-free grammar is empty.
5. It is decidable (in polynomial time) whether a particular sentence is in the language of a context-free grammar.

From (1), (2) and (4), it's easy to test whether $L(C) \subseteq L(R)$, given that $A \subseteq B$ iff $A \cap \overline{B} = \emptyset$. However, this cannot tell us whether $L(R) \subseteq L(C)$, since there is no guarantee that $\overline{C}$ is context-free. And in general, $L(R) \subseteq L(C)$ is not decidable. (In particular, there is no algorithm which could tell us whether $\Sigma^\* \subseteq L(C)$).

But that's not the whole story. The subset relationship can be determined for certain regular languages. It's decidable if $L(R)$ is finite, for example, by simply checking each sentence in $L(R)$ for inclusion in $L(C)$, as per fact (5).

And, thanks to fact (3), it's decidable in the case that $R$ is unary. The intersection of $C$ with a unary regular language, such as ${1}^\*$, is regular; the complement of a regular language is regular; and set inclusion between regular languages is decidable.

Finally, note that $A\subseteq B \land B \subseteq A \equiv A = B$.
> 5 votes

---
Tags: automata
---


# Question
Title: How do SQL databases query non-indexed columns?
I'm looking for some resources on what happens on the low-level with databases.

I've found that indexed data is looked up using b+ trees, but could not find anything on non-indexed columns.

Is there any algorithm better than fetching values of every row?

# Answer
You do in principle have to fetch every row, yes, often called a *(linear) scan*. In analytics focused database systems there are a couple more common optimizations though:

* Most analytical systems nowadays are *columnar*, instead of storing rows contiguously they store each column contiguously. This helps for scans because you only have to fetch the data for the columns your query is interested in from disk (or out-of-cache RAM).
* Queries are optimized to minimize how often a linear scan needs to happen. For example when joining two tables on non-indexed columns instead of scanning over the second table for each element in the first, it builds a temporary hash table on one table before scanning the second in one go. Essentially building the optimal index on-the-fly.
* Predicate push-down allows one to reduce the amount of data being passed around by 'pushing down' predicates such as (`WHERE age > 12`) into the scan, where the scan operator will only return the relevant values.
* It is common to store columns in groups/chunks of data, where each group can be *compressed* and read individually. Compression reduces the amount of very expensive disk I/O in exchange for some cheap CPU time.
* In addition, it's common to store cheap *statistics* for each group, such as average, sum, median, min, max, etc. Then for example if you're checking `WHERE age > 12`, and you see that the maximum for a group is `11`, you can skip the whole group, or if you're aggregating a sum you can simply take the `sum` attribute for the whole group.

There's many more, but these are some from the top of my head.
> 2 votes

# Answer
Theoretically speaking, I am not aware of any such algorithm. A linear search or Full Table Scan is performed when the rdbms doesn't find an index. This is what MySQL documentation says

> Without an index, MySQL must begin with the first row and then read through the entire table to find the relevant rows. The larger the table, the more this costs.

However, there are steps taken to try optimizing this issue. MySQL uses InnoDB storage engine by default, which requires a table to have a primary key. If you don't specify one, it will automatically create one for you as a part of extended index(indexes managed by MySQL).

Another scenario arises when a query uses ORDER BY. When an index is available and can satisfy the order, it is used. In other cases, MySQL performs a **filesort**, which is a version of quicksort, as an extra step to satisfy the order by clause.

I have taken MySQL for reference but it should be similar in case of other databases.
> 0 votes

---
Tags: algorithms, database-theory
---


# Question
Title: Is $a^nb^mc^k$, $n\neq m$ and $m\neq k$ context-free?
Is the language, $a^nb^mc^k$, where $n\not=m$ and $m\not=k $ in CFL or not? When the condition is changed to $n\not=m ~\\|~ m\not=k $, it can be shown that the language is the union of 2 CFLs. However when $n\not=m$ and $m\not=k $ that approach seems to not work.

# Answer
> 7 votes
No, $L=\\{a^nb^mc^k\mid n\neq m,m\neq k\\}$ is not context-free.

#### A proof by Ogden's lemma

Assume $L$ is context-free.

Let $p$ be the constant given by Ogden's lemma. Let $s=a^{p+p!}b^pc^{p+p!}\in L$. Let us mark all $b$s in $s$. Ogden's lemma tells that $s=uvwxy$ for some strings $u$, $v$, $w$, $x$, and $y$, such that

* $vx$ has at least one marked position,
* $vwx$ has at most $p$ marked positions, and
* $uv^{i}wx^{i}y\in L$ for all $i\geq0$.

There are several cases.

* If $v$ or $x$ contains different symbols, then $uv^2wx^2y\notin L$, since it contains symbols in the wrong order.
* Otherwise, all symbols in $v$ are the same and all symbols in $x$ are the same.
Since only $b$s are marked, either $v$ or $x$ must contain $b$.
    + Suppose $v$ contains $b$. Then $v$ only contains $b$s. So $vx$ does not contain $a$. Let $q= \\#\_b(vx)\le p$. Let $i=\frac{p!}q+1$. Consider $s'=uv^iwx^iy$.

    - $\\#\_a(s')=\\#\_a(s)=p+p!$
        - $\\#\_b(s')=\\#\_b(s) + \\#\_b(vx)^{i-1}=p + q(i-1) = p + p!$

    Hence $s'\notin L$..
    + Otherwise, $x$ contains $b$. This case is symmetric to the case above.

So, in all cases, $uv^iwx^iy\not\in L$ for some $i$. This contradicts Ogden's lemma.

Hence, $L$ is not context-free.

#### Two exercises.

**Exercises 1**. Show that $L$ satisfies the common version of the pumping lemma for regular languages. Hence, $L$ also satisfies the common version of pumping lemma for context-free languages. However, $L$ does not satisfy the stronger version of pumping lemma for regular languages.

**Exercises 2**. Show that $\\{a^nb^mc^k\mid n\neq k,m\neq k\\}$ is not context-free.

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


# Question
Title: Is the weighted sum of subset prefix product problem NP-hard?
I have this strange problem where we have a set of positive numbers $M$, a fixed number $n$, and a function $f\colon M \rightarrow R^+$ mapping each number in $M$ to another positive number. We want to know if we can select non-repetitive numbers $a\_1, \dots, a\_n \in M$, such that the sum over the weighted prefix product $\sum\_{i=1}^n f(a\_i) \cdot \prod\_{j=1}^{i} a\_j$ is maximized. Does anyone know if this is NP-hard?

In particular, I'm interested in the case $f(a\_i) = (1 - a\_i)^2$.

# Answer
This answer assumes that the numbers in $M$ are integers (it actually suffices for them to be at least $1$).

Suppose that $f$ is monotone increasing. This is the case of your example $f(a) = (a-1)^2$. In this case, your objective value is increasing in each coordinate, implying that $\\{a\_1,\ldots,a\_n\\}$ should be the $n$ largest numbers in $M$.

Now suppose that $a\_1,\ldots,a\_n$ is a solution. What happens when we switch $a\_i$ and $a\_{i+1}$? Denoting by $O$ the original value and by $S$ the new value, we have \begin{align} O - S &= \prod\_{j\<i} a\_j \cdot \bigl(a\_i f(a\_i) + a\_i a\_{i+1} f(a\_{i+1}) - a\_{i+1} f(a\_{i+1}) - a\_i a\_{i+1} f(a\_i) \bigr) \\ &= \prod\_{j\<i} a\_j \cdot \bigl( (a\_i - 1) a\_{i+1} f(a\_{i+1}) - (a\_{i+1} - 1) a\_i f(a\_i) \bigr). \end{align} Hence it is not worthwhile to do the switch if $$ (a\_i - 1) a\_{i+1} f(a\_{i+1}) \geq (a\_{i+1} - 1) a\_i f(a\_i) \stackrel\*\Longleftrightarrow \frac{a\_{i+1} f(a\_{i+1})}{a\_{i+1} - 1} \geq \frac{a\_i f(a\_i)}{a\_i - 1}. $$ The asterisk is there since we cannot divide by zero. If $a\_{i+1} = 1$ then the inequality always holds, and if $a\_i = 1$ it is always OK to make the switch. This suggests that we interpret $\frac{af(a)}{a-1}$ as $\infty$ when $a = 1$.

The conclusion is that you should arrange the $a\_i$ in non-decreasing order of $\frac{a\_i f(a\_i)}{a\_i - 1}$: $$ \frac{a\_1 f(a\_1)}{a\_1 - 1} \leq \cdots \leq \frac{a\_n f(a\_n)}{a\_n - 1}. $$

For your particular choice of $f$, we have $$ \frac{a f(a)}{a-1} \stackrel\*= a(a-1), $$ which is increasing in $a$. When $a = 1$, this conflicts with our interpretation of the fraction as infinity, but since $f(1) = 0$, it doesn't really matter where you put elements equal to $1$: their location doesn't effect the objective value. Therefore for this $f$, you should just arrange the $a\_i$ in non-decreasing order. That is, $a\_n,\ldots,a\_1$ should be the $n$ largest elements of $M$.
> 3 votes

---
Tags: np-complete, np-hard, subset-product
---


# Question
Title: How to get the optimized quicksort algorithm's time complexity
I learned in my data structures class that QuickSort can be optimized by calling the InsertionSort method when the length of the subarray is less than a certain threshold. However, when it comes to the actual time complexity calculation of the optimized version of QuickSort, I'm having trouble finding the result. The problem is as follows.

An optimized-QuickSort function calls the InsertionSort method instead of itself when the size of the sublist is less than k. Assuming that the time complexity of QuickSort and InsertionSort is $c\_1n\log n$, $c\_2n^2$ respectively, what is the time complexity of optimized-QuickSort? (Calculate for the average case)

I assumed that the sublist is split into 1:1 by each step. As a result, I got $c\_1nlog$($n\over k$) + $c\_2nk$, but I am definitely not sure of my answer since I don't know if my assumption is correct. In the textbook, the average case of a non-optimized QuickSort was supposed to be calculated by assuming the partition could be the first element, second element, third element, ... , last element and then dividing the whole sum by n.

I would appreciate some help! Thanks.

# Answer
> 2 votes
The height of tree is not $log(\frac{k}{n})$ which is negative because $k\<n$. We stop expanding the tree when we reach $k$, therefore we reduce the height of the original tree by $log(k)$. So the height is $log(n)-log(k)=log(\frac{n}{k})$ and the average running time will be: $$c\_1nlog(\frac{n}{k})+c\_2nk=c\_1nlogn-c\_1nlogk+c\_2nk$$ As noted in comments, since $k$ is constant, that is equivalent to $\theta(nlogn)$.

EDIT: I just noted that the problem was about average case complexity and you assumed the partition to have 1:1 ratio, which is the assumption for best case scenario. For average case analysis, we shouldn't consider any fixed partition ratio.

You can use the average case analysis in section 7.4.2 of CLRS book; except that here the probability of comparing the ith and jth element would be at most $\frac{1}{j-i+1}$, so the $c\_1nlogn$ would be an upper bound on the Quicksort part of the average case. As for Insertion sort part, there would be at most $n/k$ leaves with size $k$, with total cost of $\frac{n}{k}c\_2k^2=c\_2nk$.

# Answer
> 0 votes
For fixed k, and n ≤ k, O(n) is meaningless. O(n) requires *arbitrary large* values n. With a fixed k, sorting n ≤ k items with InsertionSort takes O(1) - but with a large constant if k is large. Here's what you do to find the best k:

Iterate for k = 2, 3, 4, 5 ... (hoping that your algorithm is clever enough not to sort arrays of size 1). Create a million or a billion arrays of size k filled with random array elements. Measure how long it takes to sort these arrays using InsertionSort, or another method that you like, and how long it takes to sort these arrays doing *one* partition step, then sorting both halves with InsertionSort.

Make sure that you don't switch between both methods for each array, because looking at the same data repeatedly will cache the data, and the second operation will tend to be faster.

If your array doesn't contain primitive data but objects with constructors and destructors, you can save a lot more time by reducing the number of assignments. Selection sort will tend to be faster in that case than InsertionSort because it does fewer expensive assignments.

---
Tags: algorithms, algorithm-analysis, optimization, time-complexity, quicksort
---


# Question
Title: Time complexity of quicksort for arrays in increasing or descreasing order
Two $n$-size arays are given: $n\_1$ is in decreasing order and $n\_2$ is in increasing order.

Let $c\_1$ be the time complexity for $n\_1$ using quicksort, and $c\_2$ the time complexity for $n\_2$ using quicksort.

I think $c\_1 = c\_2$ and $c\_1=O(n^2)$? Is this correct ?

I am using the last element as a pivot for each partition.

# Answer
It is true that the complexity is $O(n^2)$ in both cases, because the size of the largest partition decreases by a single unit every time, and a partition takes time linear in the number of elements it processes.

Regarding the asymptotic constant, we can say that the number of comparisons is the same, by symmetry. But the number of swaps differs. For an increasing order, there are no swaps at all, while for a decreasing one, there is exactly one swap every time, hence $O(n)$ in total. This is not enough to impact $c$.
> 1 votes

# Answer
Quicksort is just an idea. There are algorithms and implementations.

Only stupid implementations will run in O(n^2) for sorted or reversed sorted arrays. Good sorting implementations actually check for elements in ascending or descending order at the beginning and end of the array and will handle either case in O(n), because wanting an array sorted without checking that it is sorted before is such a common case. Such implementations will fall back on Quicksort for handling the more difficult parts.

(It’s not just sorted arrays. You can have a general algorithm that sorts the concatenation of two sorted arrays in O(n), or a sorted array with fewer than O(n / log n) random elements added, or a sorted element with one random element changed).

Quicksort was invented around 1960. You'd think that people wanting to sort fast would have improved it since.
> -1 votes

---
Tags: algorithms, time-complexity, sorting, quicksort
---


# Question
Title: NFA: How does it function with empty-string moves?
How does the NFA function on $\epsilon$ input if there is only a single $\epsilon$ string in the language?

I understand that $L^\* = \bigcup\_{i=0}^\infty L^i$ where $L^0 = \\{()\\} = \\{\epsilon\\}$ and $L$ is the language. The *empty string* $\epsilon$ is an input to a NFA with $\epsilon$ moves.

I suspect an infinite number of strings could be defined with $\epsilon$ anywhere in the order, then the NFA with $\epsilon$ moves would function. However I do not see this definition.

# Answer
> 5 votes
There is only one empty string, which you denoted by $\epsilon$. If you concatenate two empty strings, then you just get the empty string back: $\epsilon\epsilon = \epsilon$. This is the same as $0+0=0$. There is only one zero, and no matter how many times you add zero to itself, you only get the one zero.

I suspect that the real problem is with the semantics of $\epsilon$-NFAs (which are NFAs with $\epsilon$-transitions; an NFA is a nondeterministic finite state automaton). Let me give a definition which is similar to what you might have in mind. Suppose that $\Sigma$ is an alphabet which does not contain the symbol $\epsilon$, and define $\Sigma\_\epsilon = \Sigma \cup \\{\epsilon\\}$. Here $\epsilon$ *does not* stand for the empty string. Rather, it is a letter of the alphabet. An $\epsilon$-NFA over the alphabet $\Sigma$ is the same as an NFA over the alphabet $\Sigma\_\epsilon$.

Suppose that $A$ is an $\epsilon$-NFA over the alphabet $\Sigma$. Denote by $L\_\epsilon(A)$ the language that it accepts as an NFA over the alphabet $\Sigma\_\epsilon$. We define the language $L(A)$ over $\Sigma$, which is the language that $A$ accepts as an $\epsilon$-NFA over the alphabet $\Sigma$, as the language obtained from $L\_\epsilon(A)$ by removing all $\epsilon$'s from all words.

For example, consider the following $\epsilon$-NFA $A$ over the alphabet $\Sigma = \\{a,b\\}$:

The languages of this automaton are: $$ L\_\epsilon(A) = \epsilon^\*(\epsilon a)^+ + \epsilon^\*(\epsilon b)^+ \\ L(A) = a^+ + b^+ $$

# Answer
> 4 votes
$\epsilon$ is a typographical convention, not a part of the underlying mathematical object. It's written where writing nothing would leave a confusing or ambiguous empty space.

Transitions labeled $\epsilon$ are really unlabeled transitions, and can be taken ad lib, without consuming any characters from the string. They don't consume an $\epsilon$ from the string. The string doesn't contain any $\epsilon$s, even if it's empty.

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


# Question
Title: Which is larger: $n^{3/2}$ or $n^{\log n}$?
We know that $f(n)$ is $\mathcal O(g(n))$ if $\exists c\ge0$ s.t. $$\lim\_{n\to\infty}\dfrac{f(n)}{g(n)} = c.$$

Let $f(n)=n^{3/2}$ and $g(n)=n^{\log n}.$ When I am applying L'Hôpital's rule for $$\lim\_{n\to\infty}\dfrac{f(n)}{g(n)}=\lim\_{n\to\infty}\dfrac{1}{n^{{\log n}-3/2}} =0.$$

If I apply L'Hôpital's rule for
$$\lim\_{n\to\infty}\dfrac{g(n)}{f(n)}=\lim\_{n\to\infty}\dfrac{1}{n^{3/2-{\log n}}} $$ then it seems to be $0$. Because $$\frac{\text{something}}\infty=0?$$

My question is how to prove $$ \lim\_{n\to\infty}\dfrac{n^{3/2}}{n^{{\log n}}}=0$$ and $$ \lim\_{n\to\infty}\dfrac{n^{{\log n}}}{n^{3/2}}=\infty$$ by L'Hôpital's rule?

# Answer
> 4 votes
Which is larger, $\frac32$ or $\log n$?

Is $x\mapsto n^x$ an increasing function or a decreasing function?

# Answer
> 0 votes
**Short answer:** $\log5\>\dfrac32$.

---
Tags: asymptotics, big-o-notation
---


title: Integer decomposition algorithm

text:
# Question
Title: Integer decomposition algorithm
Suppose I have a 32-bit integer $x$, I want to find $\\{ x\_i \\}\_{i \in 1\dots\ell}$ such that $x = e + \sum\_{i=1}^\ell x\_i \cdot 2^{32 - B\cdot i}$ where the error $e$ is as small as possible. The parameter $\ell$ is the level of the decomposition and $B$ is the base of the decomposition. Increasing $\ell$ and decreasing $B$ will result in a more accurate decomposition.

Is there an algorithm that solves this kind of problem?

# Answer
> 0 votes
Assuming that $B$ and the $x\_i$ are integers, you can recast the question as

$$\frac x{2^{32}}\approx\sum\_{i=1}^l x\_iP^i$$ where $P:=2^{-B}$, and you look for the best approximation of $\dfrac x{2^{32}}\<1$ in base $2^B$ using $l$ digits.

Just write the binary representation of that number and get the digits in $l$ slices of $B$ bits.

E.g. $\frac{123456789\_d}{2^{32}}=0.00000111010110111100110100010101\_b=0.01655715052\_o$ ($o$ for octal) gives all solutions for $B=3$.

---
Tags: algorithms, integers, integer-partitions, decomposition
---


# Question
Title: Deciding whether an integer polynomial has an integer root
This is a question written by my instructor Z. Loria .

> Consider the following problem: Given a polynomial $p(x) = \sum\_{i=0}^n a\_ix^i$, where $a\_i$ are integers, is there a natural number $n \in \mathbb{N}$ such that $p(n) = 0$?
>
> Show that this problem is decidable by presenting an algorithm in pseudocode that always either outputs such an $n$, or stops in finite time and declares that no such $n$ exists.

I've to present the above algorithm.

The naïve approach will be to iterate through all the possibilities, but the problem is that it never terminates when the polynomial has no integer roots.

I was thinking about finding some upper bound on the value of $x$ and only then iterate through all the possibilities (accept if found, decline if not).

I vaguely remember that for polynomials in that form we can find some $x$ such that $|p(x)|$ only grows, but I'm not sure how to do it.

# Answer
> 5 votes
(Let's call the root $\xi$, because $n$ here means the degree of the polynomial. That's seriously bugging me about the question.)

The secret is in noticing that it's easy to test if $\xi$ is a root, since you just evaluate the polynomial, but you only need to test a finite number of candidates.

As a first observation, if $\xi$ is an integer root of the polynomial, then $\left| \xi \right| \le \left| a\_0 \right|$, so you only need to test $2\left| a\_0 \right|+1$ candidates. In fact, you can do better than this because $\left| \xi \right|$ must be a factor of $\left| a\_0 \right|$ by the rational root theorem. So you need only test the factors (both positive and negative) of $a\_0$. Either way, a finite number of candidates.

As a second observation, if

$$\sum\_{i=0}^{n} a\_i\\,\xi^i = 0$$

Then for any positive integer $m$

$$\sum\_{i=0}^{n} a\_i\\,\xi^i \cong 0\mod m$$

So, for example, if

$$\sum\_{i=0}^{n} a\_i\\,2^i \not\cong 0\mod 3$$

then there cannot be a root of the polynomial $\xi$ such that $\xi \cong 2 \mod 3$.

Conversely, suppose that for two different coprime moduli $m\_1$ and $m\_2$, you find all integers $0 \le \xi\_j \< m\_1$ and $0 \le \upsilon\_k \< m\_2$ such that

$$\sum\_{i=0}^{n} a\_i\\,\xi\_j^i \cong 0\mod m\_1$$

and

$$\sum\_{i=0}^{n} a\_i\\,\upsilon\_k^i \cong 0\mod m\_2$$

then you can use the Chinese remainder theorem to find all $0 \le \psi\_l \< m\_1 m\_2$ such that

$$\sum\_{i=0}^{n} a\_i\\,\psi\_l^i \cong 0\mod m\_1 m\_2$$

This is an important optimisation in practice (i.e. in real computer algebra systems) because evaluating the polynomial might require large integer arithmetic since intermediate values may be larger than a machine word. Using this technique, you can use word-sized integer operations to eliminate a lot of candidates.

# Answer
> 2 votes
$$|ax^3+bx^2+cx+d|\>0$$ is equivalent to

$$\left|1+\frac bax^{-1}+\frac cax^{-2}+\frac dax^{-3}\right|\>0.$$

Clearly, the limit of the LHS is $1$, and by continuity, there will be a *finite* $X$ such that $x\>X$ implies the above inequality. This generalizes to any degree.

---

You can take

$$X\>\max\left(\left|\frac{3b}a\right|,\sqrt{\left|\frac{3c}a\right|},\sqrt\[3\]{\left|\frac{3d}a\right|}\right).$$

# Answer
> 1 votes
If $a\_n = 1$, then all integer roots are divisors of $a\_0$, either positive or negative, and all other roots are irrational or complex. The integer roots can often be found quite quickly.

It's only slightly more difficult if $a\_n ≠ ± 1$: Multiply each coefficient by $a\_n^{n-1}$, then let $y = x \cdot a\_n$ or $x = y / a\_n$. You get an equation for y with the highest coefficient $a\_n = 1$. You find all the integer solutions for y. The rational solutions for x are $y / a\_n$, and you pick those that are integers.

---
Tags: decision-problem, polynomials
---