# Question
Title: Complexity of recursive function using Master theorem
this code aims to determine whether there exists a contiguous subarray starting from index 0 in the given array A whose elements sum up to the target value S. can we apply Master theorem to find out its complexity

```
 public static boolean subsumFun(int[] A, int S, int i, int j) {
    if (i >= j)
        return S == 0;
    if (i + 1 == j)
        return A[i] == S || S == 0;

    int mid = (i + j) / 2;
    if (subsumFun(A, S, i, mid))
        return true;

    int s1 = 0;
    for (int k = i; k < mid; k++) {
        s1 += A[k];
    }

    return subsumFun(A, S - s1, mid, j);
}

```

# Answer
Assume that the runtime $n$ is measured in the number of elements between `i` and `j`. In your method there are two recursive calls

```
    ...
    int mid = (i + j) / 2;
    if (subsumFun(A, S, i, mid))
        return true;
    ...

```

and

```
    ...
    return subsumFun(A, S - s1, mid, j);
}

```

which both halve the search space, so we have $a = 2$ recursive calls on a problem size of $\frac{n}{b} = \frac{n}{2}$. The work done in

```
    ...
    if (i >= j)
        return S == 0;
    if (i + 1 == j)
        return A[i] == S || S == 0;
    ...

```

can assumed to be constant, and the work done in

```
    ...
    int s1 = 0;
    for (int k = i; k < mid; k++) {
        s1 += A[k];
    }
    ...

```

is proportional to $\frac{n}{2}$. So the work outside of the recursive calls can be written as $$f(n) = c\_1 \frac{n}{2} + c\_2$$ for positive constants $c\_1, c\_2$.

The total runtime of your method can be expressed as the recurrence relation $T$ with

$$T(n) = aT(\frac{n}{b}) + f(n) = 2T(\frac{n}{2}) + c\_1 \frac{n}{2} + c\_2$$

therefore the Master theorem can be applied:

> We have $f \in \Theta(n^{\log\_2{2}}) = \Theta(n)$, so using the Master theorem we get $$T \in \Theta(n^{\log\_2{2}} \cdot \log{n}) = \Theta(n \cdot \log{n}).$$
> 1 votes

---
Tags: algorithms, complexity-theory, recursion, master-theorem
---


# Question
Title: How does numpy.linalg.inv calculate the inverse of a matrix?
What is the algorithm behind this routine and is there documentation available for it?

# Answer
> 3 votes
The source code of this function is here, which is a wrapper for a C++ function here, which is calling some BLAS/LAPACK library functions. Specifically, in order to compute the inverse of a matrix $A$, it calls the "SGESV" routine to solve the equation $AX = I$ for the matrix $X$. (note that SGESV can solve arbitrary systems $AX = B$; $B$ does not have to be the identity matrix)

The SGESV routine first computes an LU-decomposition of $A$: it finds a lower triangular matrix $L$ and upper triangular matrix $U$ such that $L U = A$. Solving a system with a triangular matrix is easy, as we can go row by row; we only need to solve an equation with one unknown variable for each row. So, we can solve $AX=B$ as follows: let $X':=UX$, then we have $LX' = A$ and $UX= X'$. These are both systems with a triangular matrix, and solving them gives $X$.

---
Tags: algorithms, matrices, linear-algebra, python
---


# Question
Title: Two Generals Problems - What's wrong with my approach?
Some time ago, I've come across the *Two Generals Problem* and that it cannot be resolved. Now, recently, I've had an idea how to approach it. IMHO, it is a very obvious way to handle it but I haven't found this way to handle it anywhere and therefore assume my idea is flawed but I can't find the error.

The approach I've found online (from Wikipedia):

> A pragmatic approach to dealing with the Two Generals' Problem is to use schemes that accept the uncertainty of the communications channel and not attempt to eliminate it, but rather mitigate it to an acceptable degree. For example, the first general could send 100 messengers, anticipating that the probability of all being captured is low. With this approach the first general will attack no matter what, and the second general will attack if any message is received.

This seems very crude and the chance of a non-delivery stays at $(1-p)^c$.

## My Approach

> General A sends a message to General B when to attack. The message contains the following information:
>
> * Attack at time $T$.
> * Send confirmation of receival.
> * I will not confirm your confirmation.
> * I will resend the time of attack after time $t$ if I did not get a confirmation.

That way, General A can be sure General B got the message when he gets the confirmation. General B can be $(1 - p)^{m \cdot c}$ sure that it passed after not getting the time of attack again, where

* $p$ := probability the confirmation passed
* $m$ := multiple of time $t$ that has passed.
* $c$ := count of messages sent per time unit (one of the solutions I've come across is to send a lot of messages at the same time).

It does not solve the problem that General B can't be 100% sure that General A received the confirmation but after some time, he can be very certain.

## Special Case

Now, if we were to change the scenario slightly, we can reach a 100% certainty for both:

> Assume both Generals do not only communicate in order to synchronize the attack but also for other purposes. In that case, General A can send the message:
>
> * Attack at time $T$.
> * Send confirmation of receival.
> * I will not confirm your confirmation.
> * I will resend the time of attack after time $t$ if I did not get a confirmation.
> * I will not send any other communication until I've received your confirmation.
>
> That way, General A can be sure that General B received the plan, when he gets the confirmation and General B can be sure General A received the confirmation when General A sending messages about something else.

So, what is wrong with my approach?

# Answer
> 3 votes
# New answer

After thinking some more and searching around for a bit I believe both of your approaches are already implemented in TCP, as can be seen here:

> \[...\] Acknowledgements (ACKs) are sent with a sequence number by the receiver of data to tell the sender that data has been received to the specified byte. \[...\] Reliability is achieved by the sender detecting lost data and retransmitting it. TCP uses two primary techniques to identify loss. Retransmission timeout (abbreviated as RTO) and duplicate cumulative acknowledgements (DupAcks).
>
> **Timeout-based retransmission**
>
> Whenever a packet is sent, the sender sets a timer that is a conservative estimate of when that packet will be ack'ed. If the sender does not receive an ACK by then, it transmits that packet again. \[...\]
>
> **Dupack-based retransmission**
>
> If a single packet (say packet 100) in a stream is lost, then \[...\] the receiver acknowledges packet 99 again on the receipt of another data packet. \[...\] if the sender receives three duplicate acknowledgements, it retransmits the last unacknowledged packet. \[...\]

## Retransmission timeout

Retransmission timeout is similar to your first approach: if general A did not receive the confirmation, he will send the same message again.

## Duplicate cumulative acknowledgements

First we need to understand the steps taken in each algorithm.

**TCP**

1. The sender did not receive an acknowledgement so it sends the same message again.
2. The receiver notices that the same message is being sent again so it sends the same acknowledgement it sent previously for this message.
3. Only when the sender receives this acknowledgement it will send the next message. Only when the sender sends a new message will the receiver know that the confirmation has been received.

**Your special case**

1. General A did not receive an acknowledgement so he sends the same message again.
2. General B notices that the same message is being sent again so he sends the same confirmation he sent previously for this message.
3. Only when general A receives this acknowledgement he will send the next message. Only when general A sends a new message will general B know that the confirmation has been received.

We can see that both algorithms are the same, except for their terminology. So there isn't any problem with your approaches.

---

# Old, wrong answer

The problem with your *Special Case* approach is that B cannot do anything until new communication is sent. Because this can happen after the attack time has passed, this is not a functional approach.

Translated to real life networking, this means that the message has to sit in the buffer until the next message is received. This is not a usable strategy in most applications.

# Answer
> 1 votes
Whenever you think you have solved the *two generals* problem, there is only one thing you need to do to find why your solution is wrong.

Take every step s\_1...s\_n of your algorithm and treat it as the final step before a permanent network failure.
Does a general end up dead if any step s\_i is the final step before total network failure?
Then you haven't solved it.

You say once A receives confirmation he will begin sending some new type of messages instead of the old attack time. Okay so he gets the confirmation. Then a permanent network failure happens. He begins sending that new type of message out but none of them will ever reach B, so B will never be certain enough to attack. Now under your scheme general A rides out to his death alone.

# Answer
> 1 votes
### Here is where you misunderstand the Two Generals Problem:

> I will resend the time of attack after time `t` if I did not get a confirmation.

The Two Generals problem does not allow for retries. That isn't specified as being part of how the system works.

You even said it yourself:

> It does not solve the problem that General B can't be 100% sure that General A received the confirmation but after some time, he can be very certain.

Well, that is the definition of the Two Generals Problem. Both of them have to be certain about all messages being sent and received without any message being lost. (Including the final one.)

You have redefined an alternative message exchange system, essentially the same as to that of TCP, where retries are permitted and used to attempt to transfer information from one place to another.

---

Here is some more detailed information:

#### The Two Generals Problem (and the more general case of the Byzantine Generals Problem) is not about answering the question:

* Can you send a piece of information from one entity to another

Clearly this is possible, and is how TCP works. You keep sending the data or an ack to the data until the sender sees the ack. That way the sender knows the receiver knows the information the sender has. (RETRIES are permitted.)

#### Instead it is about answering the question:

* Can two entities exchange a fixed, finite number of messages between each other to agree on a concensus, WITHOUT retrys.

This question is clearly mathematically impossible on an unreliable network because the number of messages exchanged is irrelevant. The problem is both intuitive and obvious: With each message which is exchanged, there is a finite probability of it being lost. The more messages which are exchanged, the higher probability that the sequence will be broken at some point by a message being lost.

I suspect, in terms of information theory, the more messages are successfully exchanged, the higher degree of confidence one has about both systems being "in concensus" however there is also a higher probability of a message being lost at some point in the sequence.

I'm not totally sure on that.

* In the "TCP case" one system starts with the message x=4. It wants to send that message to another system. All it has to do is repeatedly send x=4 until the other system replies with x=4. Then the sender knows the receiver has the data it sent. The reciever however NEVER knows the sender knows the receiver has the information x=4. It may be able to infer this by the fact that the sender stops sending x=4 for some period of time - but how long should it wait? It might not be that the sender has stopped sending but that all messages are now being lost.
* In the "Two Generals case" one system starts with the message x=4. It wants to send that message to the receiver, but critically the receiver also wants to know that the sender knows that it knows that x=4. This is different from the above case. If the receiver replies to the sender saying x=4 (ie: I know that x=4 as well) the reply may be lost. This is a mirror image of the original problem, just one step further along a chain of messages. There is a symmetry to the problem, a recursive nature to it, if you will.

Hopefully it is obvious how the two problems differ?

# Answer
> 1 votes
The enemy puts a few dozen highly trained snipers around the generals camp. Anyone leaving looking like a messenger or entering looking like a messenger will be instantly shot.

Sorry, your general will be in the dark.

---
Tags: computer-networks
---


# Question
Title: Prove that it is impossible to construct the toffoli gate using only CNOT gates
> Show that it is not possible to construct the toffoli gate using only CNOT gates, given we are allowed to choose any number of ancilla bits.

**My Attempt**

The action of a toffoli gate can be defined as,

\begin{align} f\_{toffoli}:(x,y,z)= &(x,y,z\oplus xy)\\ =&(x,y,z\overline{xy}\vee\bar{z}xy)\\ =&(x,y,z(\bar{x}\vee\bar{y})\vee\bar{z}xy)\\ =&(x,y,z\bar{x}\vee z\bar{y}\vee\bar{z}xy) \end{align}

Therefore, the simulation of the toffoli gate requires the CNOT gate to carry out AND, OR, and NOT operations.

The action of a CNOT gate produces, $f\_{cnot}:(x,y)\to (x,x\oplus y)$. Hence, the possible operations achievable by CNOT gate along with ancilla bits are

\begin{align} f\_{cnot}(x,y)&=(x,x\oplus y)=(x\bar{y}\vee \bar{x}y)\\ f\_{cnot}(x,0)&=(x,x)\\ f\_{cnot}(x,1)&=(x,\bar{x}) \end{align}

A NOT gate can be created using CNOT gate, whilist AND gate cannot be created using CNOT gate alone. Since OR gate can be decomposed of AND and NOT gates, the inability to construct AND gate with CNOT gate alone proves that toffoli gate cannot be constructd using CNOT gates even with ancilla bits.

Is it a complete and concrete proof? or is there a better way to prove it?

# Answer
Study the gates as functions over the field GF(2), where XOR is addition and AND is multiplication.

All of the bits of the CNOT gate are linear functions of the input.

The Toffoli gate has an output bit with the non-linear term $xy$.

Since all combinations of linear functions are themselves linear, you can conclude you can not construct the Toffoli gate from the CNOT gate.
> 0 votes

---
Tags: boolean-algebra, xor, reversible-computing
---


# Question
Title: Why does a lock ordering prevent deadlocks?
I am reading *C++ Concurrency in Action* and it says that always locking mutexes in a certain order prevents deadlocks. However, this is not a computer science book and no proof is given for this claim. I would like to develop some (more) intuition for why this is, with ideally a proof to convince me.

# Answer
> 3 votes
The four necessity conditions for deadlock are:

1. Mutual exclusion
2. Hold and Wait
3. No preemption
4. Circular Wait

Let there be two processes/threads - P1 and P2 and two resources - R1 and R2. Now assume that both resouces must be acquired to perform a certain task T. Assume that requirements 1 to 3 are guaranteed. If you allow the processes to run concurrently to perform T such that P1 tries to acquire R1 first, followed by R2 while P2 acquires the resources in reverse order, then it can happen that P1 is holding R1 while P2 is holding R2. At this point the processes are waiting for the other to release the other resource. You now have circular wait and a deadlock occurs.

Now, if the processes follow the same order of acquisition, only one of then will be able to hold the first resource and the other cannot proceed, hence preventing circular wait and the deadlock.

# Answer
> 2 votes
How you get a deadlock: Thread 1 waits for lock A and grabs it. Thread 2 waits for lock B and grabs it. Then thread 1 waits for lock B which is already locked and thread 2 waits for lock A which is already locked. Now both threads are waiting and will not ever release the lock they are already holding, so both threads wait forever.

This is easily solved if both threads take their locks in the same order. Thread 1 and thread 2 both wait for lock A. One is quicker and grabs the lock. The other has to wait until the first thread has completely done its job and eventually releases lock A, but that *will* happen eventually and both threads finish eventually.

So the deadlock can be prevented by taking locks in the same order. A simple ordering: Assign a level 0, 1, 2 etc. to every lock. Then a thread must not wait for a lock at some level L if it is already holding a lock at the same or a higher level.

---
Tags: deadlocks
---


# Question
Title: How is $|xy^{2}z| < 2^{p+1}$ (Pumping Lemma application)
In the Question here it is said that

> $|xy^2z|\<2^{p+1}$

Considering that $|x| = 0$ and $|z| = 0$, y consists of $2^{p}$. It's probably trivial, but how do I see, that $|xy^2z| \< 2^{p+1}$?

# Answer
> 1 votes
In the question you've linked, we have $|xy| = |x| + |y| \leq p$ (property b) so $|y| \leq p$ since $|x| \geq 0$. Therefore $$|xy^2z| = |xyz| + |y| = 2^p + |y| \leq 2^p + p \< 2^{p + 1}.$$

---
Tags: regular-languages, regular-expressions, pumping-lemma
---


# Question
Title: Pumping Lemma Contrapositive, why is this proof wrong?
I have this proof trying to show L={0}^\* {1}^\* is not a regular language, I know that L is regular but I don't know what in this proof is wrong. If y contains a 0 and 1 and is pumped wouldn't that make the any word not be in the proper form like going from 000111 to 0000101111?

Let p≥0 . We construct w=0⌈p/2⌉1⌈p/2⌉ ; w is in L and |w|≥p . Let w=xyz with |xy|\<p and |y|\>0 . Assume the middle word y contains both 0 and 1 . This implies that xy2z is not a sequence of 0’s followed by a sequence of 1’s, so that xy2z∉L . Hence L is not regular

# Answer
> 1 votes
You're not allowed to assume that $y$ contains both 0s and 1s. Take for example $x = \varepsilon$, $y = 0$ and $z = 0^{\lceil \frac{p}{2} \rceil - 1}1^{\lceil \frac{p}{2} \rceil}$ with $w = xyz$, then for $p \geq 1$

1. $|y| = 1 \> 0$
2. $|xy| = 1 \leq p$
3. $xy^nz = 0^{\lceil \frac{p}{2} \rceil + n - 1}1^{\lceil \frac{p}{2} \rceil} \in L$ for all $n \in \mathbb{N}\_0$

The Pumping lemma only requires that at least *one* such factorization of $w$ exists that satisfies 1.-3., not that *all* factorizations of $w$ do.

---
Tags: automata, pumping-lemma
---


# Question
Title: Reduction mechanism of PSPACE problems to SPACE-TMSAT
To show $\text{PSPACE-completeness}$ of $\text{SPACE-TMSAT}$, we perform a polynomial-time reduction of $\forall L \in \text{PSPACE}$ to $\text{SPACE-TMSAT}$. The language $L$ can be decided by a TM $M$ that takes at most $O(n^k)$ space for some constant $k \> 0$. Does the reduction require the value of this constant $k$?

I feel the reduction makes an inherent assumption of the value $k$, I am not sure if this value is required. If the value is required then how do we calculate this?

Edit: This solution hints towards the above reduction, but this minute detail is not clear to me.

Edit(2): Made the question more clear based on comment

# Answer
When we write $A\leq\_p B$, we mean that there exists a polynomial-time reduction from $A$ to $B$, and we don't care whether you have a description of such reduction in hand. So we're trying to prove the **existence** of a reduction. If $k$ is a constant, then there exists machine that encodes this constant, and therefore one can use that machine to conclude the existence of a machine that computes the reduction.
> 0 votes

---
Tags: complexity-theory, reductions
---


title: Can we say $|xy^iz| = a^{p+i|y|}b^p$?

text:
# Question
Title: Can we say $|xy^iz| = a^{p+i|y|}b^p$?
Using the Pumping-Lemma for $ \\{L = a^nb^n | n \in \mathbb{N}\\} $.

We define $p \in \mathbb{N}$
It exists a word $w = a^pb^p$
For every $|w| \ge p$: $w=xyz$, $y \> 0$, $|xy| \le p$
Because of $|xy| \le p$, we can say that y only consists of a's or b's.
For the language to be regular $|xy^iz| \in L$
Which means $|xy^iz| = a^{p+i|y|}b^p$ or $|xy^iz| = a^pb^{p+i|y|}$

My question is, is the expression $|xy^iz| = a^{p+i|y|}b^p$ correct? \

Lets fill $i=3$ would mean $|xy^3z| = a^{p+|y|+|y|+|y|}b^p$

# Answer
What you suggested does not work. As a sanity check, consider pumping down with $i = 0$ -- this should result in a word with a fewer number of a's.

If you consider the word $w = a^p b^p$, where $p \> 0$ is a pumping constant, then since $w\in L$ and $|w| \geq p$, we can parition $w = xyz$ where:

1- $|xy| \leq p$

2- $y\neq \epsilon$

3- $\forall i\in \mathbb{N} \cup \\{ 0\\}$, it holds that $xy^iz\in L$

Now by items 1 and 2, we can write $x = a^l, y = a^m, $ and $z = a^n\cdot b^p$, where $l+m \leq p, m\neq 0, l+m+n = p$, and $l, m, n \geq 0$. Using item 3, we get that for all $i\geq 0$, $$xy^iz = a^l a^{im} a^{n}b^p = a^{l+m+n + (i-1)m}b^p = a^{p + (i-1)m} b^p = a^{p + (i-1)|y|} b^p \in L$$

So by pumping $i$ times the word $y$, we get the word $a^{p + (i-1)|y|} b^p$, and not $a^{p + i|y|} b^p$.
> 0 votes

---
Tags: regular-languages, regular-expressions, pumping-lemma
---


# Question
Title: Iterative minimization algorithm to find a target among a set of points
I would like to find a target point in a 3-dimensional space. I do not know the exact location of the target, but I can measure to it from some of the points in the space with a metric that roughly approximates distance to the target (smaller metric values are closer to the target). The metric is noisy and it's safe to assume variance is normally distributed. Measuring to the target is expensive and can only be done serially/iteratively.

This feels like a minimization problem, but I'm struggling to see how I can best choose my source points. Intuitively, if I measure to the target and I appear to be far away, I would want to select another source that's far away from where I just measured. Likewise, if I measure to the target and appear to be very close, I should next attempt to measure from a source that's close by to see if it's closer. What is a good approach to this problem?

Inputs to the algorithm are a set of point, P where the locations of the points are know and the target to measure to, T. The objective is to perform as few measurements as possible (iteratively) to find the closest point in the set of P to the target T. Bonus points if it's possible to establish some sort of error bounds that would presumably improve as more points are tested ultimately resulting in the finding the closest point (lowest measurement) if all points in P where tested.

# Answer
I can see many possible approaches. I don't think there's enough information to tell which will be best, so you might have to try them out and see.

Notation: Let $d(A)$ denote the true distance from $A$ to $T$ (which is not observable), and $\tilde{d}(A)$ for the measured distance from $A$ to $T$.

Method 1: One simple approach might be to apply repeated trilateration. Pick 3 points $A\_1,A\_2,A\_3$ randomly, measure the distances $\tilde{d}(A\_i)$, and use trilateration to infer an approximate position $\hat{T}$ of $T$. Repeat multiple times, each time picking points from within some sphere centered around $\hat{T}$ from the previous iteration. Perhaps you halve the radius of the sphere in each iteration, or perhaps you use $2\tilde{d}(\hat{T})$ as the radius of the sphere. Eventually, once the number of points in the sphere is small enough, you can try all of them, and hopefully this finds the point nearest to $T$.

Method 2: You might be able to further reduce the number of measurements by using more sophisticated statistical methods, specifically, maximum likelihood estimation. Let's suppose you have some mathematical error model for $\tilde{d}(A)$, say,

$$\tilde{d}(A) = d(A) + E$$

where $E \sim \mathcal{N}(0,\sigma^2)$ has a Gaussian distribution with known variance $\sigma^2$ (which does not depend on $A$). Then for any point $A$ with observed measurement $\tilde{d}(A)$ you can derive a likelihood function for the location of $T$, namely,

$$p(x) = {1 \over \sigma \sqrt{2\pi}} e^{-((|x-A|\_2-\tilde{d}(A))/\sigma)^2/2}$$

gives the likelihood that $T$ is at position $x \in \mathbb{R}^3$. Taking logs of both sides, and ignoring additive constants (which won't matter), the log likelihood given a single measurement is

$$\log p(x) = -\frac{1}{2} ((\\|x-A\\|\_2-\tilde{d}(A))/\sigma)^2 + \text{a constant}.$$

Now if we have multiple measurements, say $\tilde{d}(A\_i)$ for $k$ points $A\_1,\dots,A\_k$, then the log likelihood of $T$ is the sum of the log likelihoods for each $A\_i$, and thus

$$\log p(x) = -{1 \over 2 \sigma^2} \sum\_{i=1}^k (\\|x-A\_i\\|\_2-\tilde{d}(A\_i))^2 + \text{a constant}.$$

Our goal will be to find the location $x$. Now the maximum likelihood estimation technique suggests that we find the location $x$ that maximizes $p(x)$, and use that as our best guess at the position of $T$. Equivalently, since the logarithm is a monotonic function, we can maximize $\log p(x)$. Additive or multiplicative constants don't change the location of the maximum. Therefore, we can define

$$\Phi(x) = \sum\_{i=1}^k (\\|x-A\_i\\|\_2-\tilde{d}(A\_i))^2,$$

and then minimizing $\Phi(x)$ will be equivalent to maximizing $\log p(x)$.

So the approach becomes as follows. Pick a few points $A\_1,\dots,A\_k$ (say, 5 of them or so). Measure $\tilde{d}(A\_i)$. Then, use an optimization algorithm to find $x \in \mathbb{R}^3$ that minimizes $\Phi(x)$. This is your estimate $\hat{T}$ of the location of $T$. Basically, this gives you a way to do trilateration that is tolerant of noise and errors in the measurements, and can make use of measurements from $k\ge 3$ points.

Finally, repeat this iteratively. At each stage, given $\hat{T}$, pick a few more points (perhaps as in Method 1), measure the distance to those points, add them to your collection of points (incrementing $k$ for each, so that $A\_1,\dots,A\_k$ contains all points you have ever done a measurement for), and then use maximum likelihood estimation to estimate $\hat{T}$ given all of those measurements.

To do the optimization, you'll need to minimize a complicated nonlinear function of $x$. One approach is to use Newton's method with some appropriate initialization, e.g., the prior value of $\hat{T}$, or a value obtained by trilateration with the 3 last measurements.

This statistical treatment assumes that the error model for $\tilde{d}(\cdot)$ has a particular mathematical form. If it has some other mathematical form, then you'll need to adjust the above derivation to write down the appropriate expression for the log likelihood and then define $\Phi$ accordingly.
> 1 votes

# Answer
Your problem seems like a Nearest Neighbor Search but with an approximate distance. There are many indexing methods to solve it approximately.

* IVF Index: divides space into regions and assigns a centroid point to each region. Then it searches first the centroids and then it focus only on the regions assigned to the closest centroids. It's a heuristic, no guarantees, but it works well in practice and you can manage the accuracy/speed trade-off by adjusting the parameter of the number of centroids to expand.
* Hashing-based methods: use some Locality-Sensitive hashing function to find the right group of points and then look at them. (see Locality Sensitive Hashing (LSH) ). These approaches can offer guarantees thanks to the collision properties of hash functions.
* Graph-Based method: Build a proximity graph by connecting your points trough edges. Then navigate this graph in a greedy manner to reach the target point in few steps. Ideal graph structures offers guarantee on finding the right answer (up to noise), however you often opt for approximate solutions which are way faster to build
* Tree-based approaches: kd-trees, vp-trees, k-means trees, spatial-aprroximation tree, etc. They all build trees you can navigate to find the right point, discarding useless points.

These are the main approaches to solve the so-called Approximate Nearest Neighbors Search. The best option depends on many factors (dimensionality of vectors, memory, search speed, construction time, etc).
> 1 votes

---
Tags: optimization
---


# Question
Title: Disconnection of a directed and weighted graph
Let $G = (V, E)$ be a directed weighted graph such that all the weights on the edges are positive.

In $G$, we have two nodes, $v$ and $u$, that have a path from $v$ to $u$.

The question asks to find a set of edges $ E' \subseteq E $ with the minimum weight such that $G' = (V, E') $ has no path from $v$ to $u$.

I tried the following:

We will run Dijkstra's algorithm $|E|$ times, and in each iteration, we will remove the edge with the minimum weight on the path from $v$ to $u$.

The time complexity of the method is:

$$\sum\_{i=1}^{|E|} O(i \cdot \log |V|) = O(\log |V| \cdot \sum\_{i=1}^{|E|} i) \underbrace{=}\_{\text{complete graph}} O(|V|^4 \cdot \log |V|)$$

I wanted to ask:

1. Is this method correct?
2. Is there any better solution?

I got answered that this solution in wrong with a counter example.

I tried to convert this problem to a flow network problem like suggested.

Suppose that $G$ is the following graph:

$G$ is a valid flow network graph.

The node $s$ is the source and $t$ is the sink.

At the end of $EK$ we will get the following flow:

And the residual graph $G'$ look like:

The nodes that are in blue and orange represent the minimum cut.

Following the Max-flow min-cut theorem, we get that the maximum flow is 9.

One way to disconnect $s$ and $t$ will be by removing the following edges:

These are all the edges that crossing the minimum cut.

Another way:

Here is what I don't understand and don't know how to prove:

1. I think that this example loses generality. I assume that $s$ has no edges entering it, and $t$ has no edges going from it. I think this is too big of an assumption.
2. The weight of the set of edges $E'$ in my example was 9, which I think is indeed the minimum weight of the edges that will disconnect $s$ and $t$. This is also the maximum flow of the network. Is this a coincidence?
3. I noticed that in

You can do the following :

a. Run a BFS scan from $s$ on $G$.

b. If you use an edge that flows it's maximum capacity, mark the edge and don't continue to the node at it end.

It will give the set of edges in the last picture.

I don't how to explain why it disconnects $s$ from $t$ in the particular graph $G$, and why this method will disconnect $s$ and $t$ in general.

# Answer
The algorithm is not correct. Imagine the following graph:

```

   2     1     2
v --- o --- o --- u
      |     |
     2|     |2
      |  1  |
      o --- o
      |     |
     2|     |2
      |  1  |
      o --- o
      |     |
     2|     |2
      |  1  |
      o --- o

```

Your algorithm will output all the edges labelled 1 instead of a single edge labelled 2.

The problem you want to solve is called the Minimum Cut problem, which is solved by the Maximum Flow algorithm. Its running time is also ever-so-slightly better then your $n^4 \log n$ algorithm, but not extremely much, with Edmonds-Karp running in time $O(mn)$, i.e., $O(n^3)$.
> 2 votes

---
Tags: algorithms, graphs, correctness-proof, network-flow, dijkstras-algorithm
---


title: Trouble proving this is regular

text:
# Question
Title: Trouble proving this is regular
I'm taking an automata class and one of the examples is showing this is regular. My initial thought was to make a DFA to show it is but i'm a bit confused on what a DFA with a standard 5 tuple would look like for this. I know my alphabet is all the combinations of 0,1,2 for the columns and that my final state would be when ternary number on the top would be larger. But i'm confused on my set of states, transition function, and how to write this all in a 5 tuple form. Any hints?

Let Σ3 be the alphabet that contains all columns of 0,1,2 of height two:

Σ2={\[00\],\[01\],\[10\],\[11\],\[02\],\[20\],\[12\],\[21\],\[22\]}. A string of symbols in Σ3 gives two rows of digits, we see each row as a ternary number. For instance \[20\]\[11\]\[01\] has a top row of 210 in ternary, which is 21 in decimal, and a bottom row of 011 in ternary, which is 4 in decimal.

Show that the following language is regular:

D={w∈Σ∗3∣the top row of w is a larger number than is the bottom row}. For instance, \[00\]\[20\]\[02\]\[00\]∈D but \[00\]\[01\]\[11\]\[00\]∉D .

Hint: Each element of Σ3 you read corresponds to the same position in the top and bottom numbers.

# Answer
Note that for two ternary numbers $x = x\_1x\_2...x\_n$ and $y = y\_1y\_2...y\_n$ with digits $x\_i$ and $y\_i$ holds that $$x \< y \iff x\_1x\_2...x\_n \prec y\_1y\_2...y\_n$$ where $\prec$ is supposed to be the lexicographic order (dictionary order) of strings. In general

* $x\_1x\_2...x\_n \prec y\_1y\_2...y\_n$ if $x\_1 \< y\_1$ or
* $x\_1x\_2...x\_n \prec y\_1y\_2...y\_n$ if $x\_1 = y\_1$ and $x\_2...x\_n \prec y\_2...y\_n$.

So the language can be decided by reading pairs of digits $\begin{bmatrix} x\_i \\ y\_i \end{bmatrix}$ from left to right, and either going into an accepting state if $x\_i \> y\_i$, going into a dead state if $x\_i \< y\_i$ or simply continuing to read if $x\_i = y\_i$.

The corresponding DFA recognising $D$ can be defined as follows:

> Define the DFA $A = (Q = \\{q\_=, q\_\>, q\_\<\\}, \Sigma\_3, \delta, q\_=, F = \\{q\_\>\\})$ such that $$\delta(q\_=, \begin{bmatrix} x \\ y \end{bmatrix}) = \begin{cases} q\_\> & \text{if } x \> y \\ q\_= & \text{if } x = y \\ q\_\< & \text{if } x \< y \end{cases}$$ and $\delta(q\_\>, \begin{bmatrix} x \\ y \end{bmatrix}) = q\_\>$ as well as $\delta(q\_\<, \begin{bmatrix} x \\ y \end{bmatrix}) = q\_\<$ for all $\begin{bmatrix} x \\ y \end{bmatrix} \in \Sigma\_3$.

A proof that $L(A) = D$ is best left to the reader ;)
> 1 votes

---
Tags: finite-automata, formal-grammars
---


# Question
Title: Why does Coq include let-expressions in its core language
Coq includes let-expressions in its core language. We can translate let-expressions to applications like this: `let x : t = v in b ~> (\(x:t). b) v` I understand that this does not always work because the value `v` would not be available when typechecking `b`. However this can be easily fixed by special casing the typechecking of applications of the form `(\(x:t). b) v`. This allows us to remove let-expressions at the cost of a special case while typechecking. Why does Coq include still include let-expressions? Do they have other advantages (besides not needing the special case)?

# Answer
> 27 votes
It is a common misconception that we can translate `let`-expresions to applications. The difference between `let x : t := b in v` and `(fun x : t => v) b` is that in the `let`-expression, during type-checking of `v` we know that `x` is equal to `b`, but in the application we do not (the subexpression `fun x : t => v` has to make sense on its own).

Here is an example:

```
(* Dependent type of vectors. *)
Inductive Vector {A : Type} : nat -> Type :=
  | nil : Vector 0
  | cons : forall n, A -> Vector n -> Vector (S n).

(* This works. *)
Check (let n := 0 in cons n 42 nil).

(* This fails. *)
Check ((fun (n : nat) => cons n 42 nil) 0).

```

Your suggestion to make application `(fun x : t => v) b` a special case does not really work. Let us think about it more carefully.

For example, how would you deal with this, continuing the above example?

```
Definition a := (fun (n : nat) => cons n 42 nil).
Check a 0.

```

Presumably this will not work because `a` cannot be typed, but if we unfold its definition, we get a well-typed expression. Do you think the users will love us, or hate us for our design decision?

You need to think carefully what it means to have the "special case". If I have an application `e₁ e₂`, should I normalize `e₁` before I decide whether it is a $\lambda$-abstraction? If yes, this means I will be normalizing ill-typed expressions, and those might cycle. If no, the usability of your proposal seems questionable.

You would also break the fundamental theorem which says that every sub-expression of a well-typed expression is well-typed. That's as sensible as introducing `null` into Java.

# Answer
> 0 votes
For anyone whose first reaction to Andrej Bauer's response was to wonder, like me, whether this is caused by inductive types or also present in the baseline calculus of constructions without inductive types, here is another example that doesn't make use of inductive types at all:

```
Definition T := forall P : Prop, P -> P.
Definition x : T := fun P x => x.

Check (let P := T in x P x) : T.
Fail Check ((fun P => x P x) T).

```

---
Tags: type-theory, dependent-types, type-checking, coq
---


# Question
Title: Minimizing total distance traveled by points in points cloud transformation
I have a point cloud of size n (in the example on picture n = 5). The starting coordinates are in green, destination coordinates are in red. What I need is to move the points from the starting coordinates to the destination ones so that the total distance, traveled by all points is minimal.

There is one important restriction - **points' trajectories should not intersect** (so, trajectories could be curvy). To handle this, we may introduce some `ε` to denote the minimum distance between two trajectories, after which they will be considered intersecting.

Non-intersecting trajectories can be changed in favor of non-colliding points (the distance between several points can't be smaller than `ε` at the same moment of time) if that makes the task easier to solve (if not - let's stick to the original conditions). In such a case maximum point speed, `V`, should be introduced.

More than 2 points may lay on a line (e.g. 2 starting points and 2 destination ones may be collinear).

For the particular case described at the picture, the minimal path will look like `A -> F` \+ `B -> G` \+ `C -> H` \+ `D -> I` \+ `J -> E`.

Solutions that came to my mind:

* The greedy approach will not work, because if we start from point `A` and choose the nearest destination point, we'll end up with `E` moving to `F`, which is far from being optimal.
* Brute dynamic programming solution will result in something like `O(n!)` complexity, which is not really acceptable.

None of those solutions save me from intersecting trajectories.

My gut tells me, that some kind of gradient descent may be useful for this task, but I can't figure out how to apply it to this task.

What I need **is not** a working code, but advises or directions to related topics/articles/papers which will help me to understand how to solve this task.

P.S. I saw Assign m agents to N points by minimizing the total distance and Given 2 sets of n points: minimize sum of traveled distances but wondered how this task can be handled after the introduction of the aforementioned trajectory-related restriction.

# Answer
> 4 votes
If the trajectories must be lines and $\epsilon$ is small enough, the problem can be solved with min-cost matching. If all coordinates are integers with absolute value bounded by $H$, then two disjoint intervals with integer endpoints have distance at least $\frac{1}{4H}$ from each other. Hence if $\epsilon$ is less than this value, it might as well be 0.

Take any four points $A, B, C, D$ and assume that there exists a line segment connecting $A$ and $B$, one connecting $C$ and $D$, and that these line segments intersect at point $X$. Then $|A - B| + |C - D| = |A - X| + |B - X| + |C - X| + |D - X|$. Triangle inequality is strict when the three points do not lie on the same line, so if not all of $A,B,C,D$ are colinear, we can exchange the startpoints of the segments to decrease their total length. Thus, if no four points lie on a line, the minimum total length solution doesn't have intersecting line segments.

To find the minimum total length solution, we use min-cost matching, with cost $|A - B|$ to match points $A$ and $B$ (assuming one of $A$ and $B$ is a starting point, and the other is an endpoint).

To handle the case where some four points lie on a line, we just disallow matching $A$ and $B$ if some other point lies between them. Matching in this case is not always possible, for example if we have two startpoints, then two endpoints on a line.

# Answer
> 0 votes
Just a visual idea: Get all the segments possible, and remove all the crossing ones. Their number should be greatly reduced. Then apply brute-force algorithm, or smarter ones.

---
Tags: algorithms, optimization, assignment-problem
---


# Question
Title: How does knowing the input size make the time complexity of a function constant?
After reading the question and answers on Time complexity of min() and max()? I would like to clear up some confusion on the relation between time complexity and size of input.

First, I've noticed most of the time people omit what exactly `n` represents in big O notation. Usually it's related to the input, but it may be the value or length in bits or something else. Am I right that it's usually inferred from context?

When is a function O(1) vs O(n)? I had thought that only functions that do not depend on the input would be O(1) for example

```
foo()
{
  return "bar"
}

```

Or accessing certain data structures like an array `arr[0]` or a map would have operations of O(1). But in the linked question some answers stated this is only true if the size is known. What difference does this make? Even if the size is known, some operations may take O(n). For example given in an array of 100 elements you know the value 50 appears and would like to find its index. That would be O(n) because the array would have to be traversed. So why do some people say knowing the size makes it constant time?

# Answer
> First, I've noticed most of the time people omit what exactly `n` represents in big O notation.

Yes, that is indeed a bad habit. In general, when you analyze complexity, you must specify:

* Are you talking about space complexity, step complexity, time complexity?
* Are you talking about best-case, worst-case, amortized worst-case, average case, expected case?
* What is your machine model? (I.e. what operations exist?)
* What is your cost model? (How long do those operations take?)
* What are you actually counting? (Comparisons, stores, loads, arithmetic operations, bit operations, etc.)
* How do you define "length of the input"? (Number of elements, number of bits, etc.)
* What is the distribution of your inputs? (In case of average or expected complexity.)

> Usually it's related to the input, but it may be the value or length in bits or something else.

For data structures, it is usually the number of elements. For strings, it already gets trickier: is it the number of bytes, number of octets, number of \`chars, number of code points, number of characters, number of graphemes, number of grapheme clusters?

One thing that catches many people out is that for numbers, it is usually *not* the magnitude, it is the *length* (i.e. the number of "digits" or bits), which is the logarithm of the magnitude.

> Am I right that it's usually inferred from context?

Indeed. However, as mentioned above, for numbers, it is often inferred wrong.

The reason why we usually use the *length* of numbers is that arithmetic operations depend on the number of digits, not on the magnitude of the number: adding 1+1 take the same time as adding 4+4, but adding 10+10 takes twice as long. Adding 4999+5000 doesn't take 5000 times as long as adding 1+1, it only takes 4 times as long.

> For example given in an array of 100 elements you know the value 50 appears and would like to find its index. That would be O(n) because the array would have to be traversed.

No, it would not. O(1) means the number of comparisons (which is what we are usually counting when talking about "searching") is bounded by a constant. In your example, you will never need more than 100 comparisons, therefore the number of comparisons is bounded by 100, which is a constant.

Therefore, the time complexity is O(100), which is the same as O(1).
> 4 votes

# Answer
This can be summed up in one sentence that you should memorise:

> In complexity theory, what we call a "problem" is never *one* question, but instead *an infinite family of questions that depend on an input*.

For each input, there is a question.

An algorithm is said to solve the problem if for any input, the algorithm is able to find the answer to the question. Upper bounds and lower bounds on the complexity of an algorithm that solves a problem are expressed as a function of the size of the input.

With these definitions in mind, a problem that doesn't depend on an input can be solved in O(1) by definition, and a problem whose input is artificially limited in size can be solved in O(1) by definition. Only problems whose input can grow arbitrarily large are "interesting" from the point of view of complexity theory.

#### Constant Connect-Four vs. unbounded Connect-Four

For instance, the problem "Given a position of 7x6 Connect-Four, does the first player have a winning strategy?" is a boring O(1) problem from the theoretical point of view of complexity theory. You can imagine many algorithms to solve this problem, and all of them will have O(1) complexity by definition, which tells us nothing. For instance, one possible algorithm is to hardcode all $3^{42}$ possible positions and their answers in a lookup table. Technically this algorithm only uses O(1) space, even though $3^{42}$ is a huge number (about two hundred million million millions). Another possible naive algorithm is to explore the whole tree of possible plays from the given position, running a minmax algorithm to determine each player's best moves; this would have time complexity $7^{42}$, which again is a gargantuan number, but technically O(1).

This is of course a disappointing answer, and certainly we want to say that some algorithms are more efficient than others. Our intuition tells us that 6x7 shouldn't be treated as a constant. But complexity theory only studies the growth of complexity as input size grows, so if you don't allow input size to grow, then by definition the theory cannot do anything.

So instead of studying "classic 7x6 Connect-Four", you can study the more general problem "cxr Connect-Four", a generalisation of classic Connect-Four played on a board with c columns and r rows. Now you can't hardcode all the answers in a lookup table, because the problem is an infinite family of questions, for arbitrarily-large board sizes. And now you can express upper bounds and lower bounds on the complexity of an algorithm as a function of c and r, or as a function of n=cr to simplify. Now it can be said that a time complexity of $c^{cr}$ is terrible, and the theory is able to distinguish between an efficient algorithm and a terribly-slow algorithm.

#### Searching for a substring of size k in a string of size n

Sometimes instead of just one number n, there can be several numbers that depend on the input and that are relevant to algorithms' complexity. For instance, the problem "Find the index of a substring in a string" can be solved by a naive algorithm in time $O(nk)$, where $n$ is the length of the big string ("the haystack") and $k$ is the length of the substring ("the needle").

If the input is just the haystack and the needle, and there is no constraint on $k$ and $n$, then the size of the input is $N = k + n$ and if we want to express the complexity of the naive algorithm with respect to $N$, all we can say is that this algorithm has quadratic complexity, ie in the worst case it grows proportionally to $N^2$. This worst-case is realised for instance whenever $k = \frac{1}{2}n = \frac{1}{3}N$, because in those cases $nk = \frac{2}{9}N^2 = Θ(N^2)$.

However, a variant of this problem is the similar problem, but with $k$ bounded by a constant. In this case, the naive algorithm has linear complexity, because $kn = k(N-k) = Θ(N)$.

Studying this "k is bounded" variant makes sense; it's a subproblem where we limit ourselves to searching small needles in arbitrarily large haystacks, so we don't want to be pessimistic and calculate worst-case complexities that allow $k$ to grow proportionally with $N$. We want to favour algorithms whose complexity grows lowly with $n$, even if the tradeoff is that the complexity grows highly with $k$; and we do that by declaring that $k$ is guaranteed not to grow.
> 2 votes

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


# Question
Title: Does a language dictate the order of the word?
Lets take the Language $$L = \\{ (ab)^na^k | n \ge k \\}$$

Does it dictate, that the $(ab)^n$ comes before the $a^k$ ? Or is the order irrelevant as long as it matches the $n \ge k$ criterium?

In simple terms: is the word $aaaababab \in L$ ?

And if so, does this apply for every language?

# Answer
> 1 votes
Yes, order matters. The fundamental operation used in the definition of language $L$ is "string concatenation", for which order is important.

One question: if you were happy about transposing $(ab)^n$ and $a^k$, why wouldn't you also be happy about transposing the $a$ and $b$ inside $(ab)^n$ to get a string like $aaabbabb$?

Of course it's possible to construct languages which are stable under "anagraming", but you'll need to make that explicit in the notation, for instance:

$$L\_2 = \left\\{ w \in \\{a,b\\}^\* \\, \middle| \\, \\#\_a(w) \geq \\#\_b(w) \right\\}$$

now $L\_2$ is the language of all words that contain more $a$ than $b$, regardless of order.

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


title: How to handle odd word

text:
# Question
Title: How to handle odd word
Given the language $L = \\{ a^n | \text{n is odd} \\}$

I'm looking for a word $w$ using $p \in \mathbb(N)$. For example, if it would be even, instead of odd I'd choose $w = a^{2p}$.

But with odd, I'm really struggling to find a word. What do I do? Define a variable $j$ and say $\text{j is odd}$ so $a^j \in L$

I know the language is regular but I still want to know how to handle the $odd$.

# Answer
I have no idea what exactly you're asking, but if you consider $w = a^{2p}$ to be a valid answer for even-sized words, I assume $w = a^{2p+1}$ would be fine for odd words.
> 4 votes

---
Tags: formal-languages, regular-languages, pumping-lemma
---


# Question
Title: Provide a 2-state DFA for L={a}∗{b}∗ , the set of words of the form aa⋯abb⋯b
I'm kinda confused on how to construct this DFA. I'm trying but keep running into the problem of reading an a after the b's or what to do if starting with a 'b'.

# Answer
There are two types of people, those who allow missing transitions when defining a DFA, and those who do not. It does not make a notable difference, see my answer here. Stick to the definition you've seen in class/book/whatever.
> 2 votes

---
Tags: finite-automata
---


# Question
Title: Improving a ranking system with "best rank"
I've implemented a ranking system (based on a score), using a Map\<Player,Score\> and an improved BST\<Score, Set\<Player\>\>. So now I can compute "rank of a player" in O(log(n)) time, "top xxx players", insert/update/remove in O(log(n)) time.

Now I want to improve my data structure to remember the "best rank" of each player. So when a player's score is updated, it will affect this player's rank, but other players' ranks as well as this player's ranking will go up/down. I want, for each player, to always keep the best rank they ever had.

An easy way to do so would be to keep a new hashmap\<Player,BetScore\> and, when an update is done, to check all the affected players and potentially update their best rank. The issue with this is the O(n) running time per operation. I'm trying to figure out if there is a way to do this in O(log(n)) time per operation. Is it possible?

# Answer
Each query can be implemented to run in $O(\log n)$ time by lazily propagating appropriate operators on the binary search tree. The lazy propagation technique \*1, is that it is possible to perform *range update* on a BST as long as such update operations can be composed in $O(1)$ time (forms a monoid).

Let $x\_i$ and $m\_i$ be the current and the best ranks of the player $i$. Then, let $y\_i := x\_i - m\_i$ be the difference between current and best ranks. We implicitly maintain $x\_i$ and $y\_i$ on a binary search tree ordered by the score (ties broken arbitrary). A score change can be represented by first removing a player from the BST and then re-inserting the player. Ranks change when:

* When inserting a player, we must down-rank all players $j$ with score less than the inserted player: $x\_j \leftarrow x\_j + 1$ and $y\_j \leftarrow y\_j + 1$.
* When removing a player, we must up-rank all players $j$ with score less than the removed player: $x\_j \leftarrow x\_j - 1$ and $y\_j \leftarrow \max(y\_j - 1, 0)$.

The operators on $y$ can be represented as a function of the form represented by two numbers $(a, b) \in \mathbb{Z} \times \mathbb{Z} \cup \\{-\infty\\}$:

$$ f(X) = \max(X + a, b) $$

and two such functions $f, g$ can be composed:

$$ \begin{align} (f \circ g)(X) &= \max(\max(X + a\_1, b\_1) + a\_2, b\_2) \\ &= \max(\max(X + a\_1 + a\_2, b\_1 + a\_2), b\_2) \\ &= \max(X + (a\_1 + a\_2), \max(b\_1 + a\_2, b\_2)) \end{align} $$

while still being represented by two numbers. That is, the composition is closed and forms a monoid with the identity $(0, -\infty)$. Independently, update on $x$ (range addition) can be represented by just one number.

To summarize, we can implement the required range update operations by storing three additional numbers on each node of the BST. Therefore, it takes $O(\log n)$ time to insert/delete/query a player.

* \*1 I don't know a proper reference, but there are many tutorials on the web as a popular competitive programming technique. It is usually written for *segment trees* (statically allocated full BST) but can adopted to any BST. Rotation/other tree change should trigger a "push" of update operator.
> 6 votes

---
Tags: data-structures, binary-trees, search-trees, rank
---


# Question
Title: How to handle multiple exponents (Pumping-Lemma)
Example $L = {(ab)^na^k|n\ge k}$

When searching for a word $w$, using $p \in \mathbb{N}$, for instance $(ab)^pa^p$, but wanting to pump $a$ (which is not possible because $|xy| \le p$ holds), how do I deal with that? I would need a variable $j \lt p$ for $(ab)^ja^j$ to have the possibility that $a \in y$, so I can pump $a$ and argue that $(ab)^ja^{j+(i-1)|y|} \notin L$ → The condition is no longer satisfied: $\forall i\ge 0: xy^iz \in L$.

My question: How is the best way to handle multiple exponents? Not just in this but in general.

# Answer
> 3 votes
There is actually a more generalized version of the pumping lemma, where you can pump a substring anywhere in the word. The proof is almost the same: in a computation of a word $w$ in a DFA, if there is a substring long enough, it contains a cycle.

The lemma can be stated as such:

> Let $L$ be a regular language over alphabet $\Sigma$. Then there exists a pumping length $p$ such that if $uvw\in L$ with $|v| \geqslant p$, then there exists a decomposition $v = xyz$ such that:
>
> * $|xy|\leqslant p$
> * $y \neq \varepsilon$
> * for any $k\in \mathbb{N}$, $uxy^kzw\in L$.

For your language, you want to apply this lemma with $uvw = (ab)^pa^p$ with $u = (ab)^p$, $v = a^p$ and $w = \varepsilon$.

There is another way to handle this language without the need of changing the lemma, but you need a bit of a trick: you can show that $L$ is the mirror language of $L' = \\{a^k(ba)^n\mid n\geqslant k\\}$. You can use the classic version of the pumping lemma to show that $L'$ is not regular, and since the mirror operation must preserve regularity, $L$ is not regular either.

# Answer
> 3 votes
There is a solution to your pumping problem using the classical formulation of the Pumping Lemma, writing $w=xyz$ and considering $|xy| \le p$ and $xy^iz$ for $i\ge 0$. The trick is *pumping down*...

For clarity, instead consider $L = \\{b^na^k \mid n\ge k\\}$. Assume pumping length $p$. Consider the string $w = b^pa^p$. Setting $w = xyz$ with $|xy|\le p$ implies that $y$ consists of $a$'s only. Deleting $y$, i.e. setting $i=0$, gives us the string $xy^0 z = a^{p-|y|} a^p$ which is not in $L$ as $p-|y| \< p$.

In general there might not be a common solution for handling "multiple exponents". An infamous example is the language $\\{ a^n b^m \mid n\neq m \\}$ where the usual Pumping Lemma can be applied, but one needs factorials. See https://cs.stackexchange.com/a/64074/4287. Other approaches are available too, see the other answers to that problem.

---
Tags: formal-languages, regular-languages, pumping-lemma
---


# Question
Title: How to optimize algorithm to solve the following time series problem?
I am working on a project and came across the following problem I have to solve.

Imagine we have a time series data `Ts` which is an array of pair, say each element is `(Xi, Yi)`. The length of this array is constant `N` but is updated regularly. Each update consists of two steps,

1. We remove `Ts[0]`
2. Add a new pair `(X, Y)` to the end of `Ts`

Essentially like an online update to a sliding window of size `N`.

Now here comes the problem. At any given times (could be after an update or before), we are given a nonzero input integer `A` and `B`. The goal is to find such `i` between `0` and `N-1` inclusive where the term `(A-Xi)/(B-Yi)` is maximized.

Another constraints I would like to mention here,

1. `(X0, X1, X2, ... X(N-1))` is non-decreasing, `Xi` is non-zero non-negative integer for all `i`.
2. `(Y0, Y1, Y2, ... Y(N-1))` is non-decreasing, `Yi` is non-zero non-negative integer for all `i`.
3. `A` and `B` are both non-zero non-negative integer.
4. For any query, we can safely assume `B > Yi` for every possible `i`. Technically for the original problem, `B` could be equal to the last `Y(N-1)`. But this is a boundary condition and we would just eliminate `N-1` in this case.
5. We can also safely assume `A > Xi` for every possible `i`. Unlike constraint (4). It is not possible for `A - Xi` to be 0 in any case.

A naive approach would be to iterate through all `N` possibilities and easily find the solution (This is what I am doing). But I am thinking of a way to optimize this in the case of very large `N`. A query could come at any time for however many number of times, for example,

1. Query, Update, Query (1000 times), Update. Or could also be,
2. Query, Update, Query, Update, ...

Is there any room for optimization here? I am interested to see a proof from more mathematical standpoint if there is none as well.

# Answer
> 1 votes
First, apply the standard reduction: to solve a ratio maximization problem (sometimes called "fractional programming"), binary search on the solution $t$:

$$ \max\_x \frac{f(x)}{g(x)} \geq t \iff \max\_x f(x) - t g(x) \geq 0 \\ \text{assuming } g(x) \> 0 \\; \forall x. $$

Applying that to this problem,

$$ \begin{align} \max\_i (A - X\_i) - t (B - Y\_i) &= \max\_i A - X\_i - t B + t Y\_i \\ &= \max\_i (-X\_i + t Y\_i ) + (A - t B) \end{align} $$

so it is sufficient to maintain a data structure on $X, Y$ to answer queries of form $Q\_{X,Y}(t) := \max\_i (-X\_i + t Y\_i)$.

When data is considered as 2-D points $\\{(X\_i,Y\_i)\\}$, a query is a linear function maximization. It is possible to maintain a convex hull of dynamic points to support such query in $O(\log N)$ time using $O(N)$ space \[1\].

Let $M$ be the maximum integer value of input then we only need $O(\log M)$ iterations of the binary search. Therefore, the final runtime is $O(\log N \log M)$ per query, and $O(\log N)$ time per update.

(Time complexity doesn't change but it is possible to use a simpler incremental convex hull data structure by utilizing the sliding window update. It may also be possible to use the non-decreasing constraint (thinking of Convex hull trick) but I'm not sure.)

* \[1\] Brodal, Gerth Stølting, and Riko Jacob. "Dynamic planar convex hull." *The 43rd Annual IEEE Symposium on Foundations of Computer Science* (2002).

---
Tags: algorithms, data-structures, optimization, discrete-mathematics, time-series-analysis
---


# Question
Title: How to construct context-free language $L$ to prove $L′=\{x|xx∈L\}$ is not context-free?
Can someone please explain me how to solve this?

In this post here was one user sketching the solution but I still don't understand how to construct a context-free language $L$ in such a way that the words in $L$ of the form $ww$ are $a^mb^mc^ma^mb^mc^m(m≥0)$. How does the grammar for L looks like? What equalities have the grammar to ensure and why?

Thanks!

# Answer
Take a look at $$L = \\{a^nb^nc^ma^mb^kc^l : n, m, k, l \geq 0\\}.$$

Now take some $x \in L$ with $x = ww$, then $x = a^nb^nc^ma^mb^kc^l$ for some $n, m, k, l \geq 0$. There's only *one* possible way to split $x$ into two equal parts $w$:

$$w = a^nb^nc^m = a^mb^kc^l.$$

Note that for distinct symbols $c\_i$, $c\_1^{n\_1}c\_2^{n\_2}...c\_k^{n\_k} = c\_1^{m\_1}c\_2^{m\_2}...c\_k^{m\_k}$ implies $n\_i = m\_i$ for all $i$. From this we know that

1. $n = m$,
2. $n = k$, and
3. $m = l$.

So from 1. it follows that $A(L) = \\{a^nb^nc^n : n \geq 0\\}$ which is known to be not context-free. To prove that $L$ is context free, note that $L$ can be generated by the following context-free grammar with start variable $S$:

$$S \to ABCD$$ $$A \to aAb | \varepsilon$$ $$B \to cBa | \varepsilon$$ $$C \to bC | \varepsilon$$ $$D \to cD | \varepsilon$$
> 2 votes

# Answer
Context-free languages are not closed under intersection. We start there. The relevant example is here that $\\{ a^p b^p c^q \mid p,q\ge 0 \\} \cap \\{ a^p b^q c^q \mid p,q\ge 0 \\} = K$, where $K = \\{ a^m b^m c^m \mid m\ge 0 \\}$ is not context-free.

The two languages each force a pair of letters to have the same number.

For your question we set $L = \\{ a^p b^p c^q \mid p,q\ge 0 \\} \cdot \\{ a^p b^q c^q \mid p,q\ge 0 \\}$. Or, written differently $L = \\{ a^p b^p c^q a^r b^s c^s \mid p,q,r,s\ge 0 \\}$. If a string in $L$ is of the form $xx$ the two $abc$-halves must be equal. Thus of the form $x= a^m b^m c^m$.
> 1 votes

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


# Question
Title: What is the Time Complexity of this Slow Sorting Algorithm?
```
    public static void sort(int[] A, int i, int j) {
        if (i >= j) return;

        int m = (i + j) / 2;
        sort(A, i, m);
        sort(A, m + 1, j);

        if (A[m] > A[j]) {
            // swap A[j] and A[m]
            int temp = A[j];
            A[j] = A[m];
            A[m] = temp;
        }

        sort(A, i, j - 1);
    }

```

I tried the master theorem to find out the complexity of this function, but I guess it can't be used in this case. The algorithm seems to split the array in half, then it compares the element at index m with the element at index j and swaps them. However, the recursive call `sort(A, i, j - 1)` is confusing me. Can $T(n)=T(n/2)+T(n/2)+T(n-1)+O(1)$ be a possible solution?

# Answer
> 4 votes
Firstly, this is clearly a joke algorithm, AKA selection sort with extra steps -- you find the maximal element by splitting the array into halves, sorting them, and taking the maximum of the biggest element in each half.

Your recurrence relation is correct. Since only constant work is done at each branch, the time spent is proportional to the number of branches, which AFAICS is given by integer sequence A022905 in the OEIS.

You can easily see that this is a function that grows faster than any polynomial, by noting that $\lim\_{n\rightarrow\infty}\frac{(n/2)^c + (n-1)^c}{n^c}$ is a constant larger than 1 for any $c$.

On the other hand, the function given by your recurrence relation grows by $O(n^{\log n})$ (try and see if you can figure out why), in other words it is a quasi-polynomial algorithm. I don't think this is the best analysis possible, though, as it looks like it grows even slower.

# Answer
> 1 votes
Too long for a comment: If we call the number of calls for sorting an array with n items T(n), then T(1) = 1, and T(n) = T(n div 2) + T((n+1) div 2) + T(n-1) for n \>= 2.

Assume that $T(n) = n^{c\_n \cdot \log\_2 n}$. Calculating $c\_n$ by computer shows that $c\_n$ gets smaller until $c\_n = 0.432840$ when n = 716,727; then it becomes larger slowly; at $n = 18 \cdot 10^{9}$ we have about $c\_n = 0.4394$. At this point $T(n)$ is just below $n^8$.

---
Tags: algorithms, recursion, big-o-notation
---


# Question
Title: Algorithm for 3-coloring a graph, given a search algorithm that finds a k-colored graph for $k \ge 4$ if one exists, and otherwise returns false
The problem statement is:

> Given a search algorithm that finds and returns a k-colored graph for $k \ge 4$ if one exists, and otherwise returns false, show that there exists a search algorithm for 3-coloring.

My idea is to connect each vertex $v \in V$ to another colored vertex(all new vertices are colored in the same color), and to use the given algorithm to find if there exists a 4-coloring for the new graph. If so, then the 3-coloring algorithm will return the colored graph that was returned from the 4-coloring algorithm, minus all the added vertices. If the 4-coloring algorithm fails, then the 3-coloring algorithm returns false.

I think the alogrithm works, as each node $v \in V$ can be colored only in one of three colors, since it is connected to a node which is already colored in a pre-defined color.

I've tried to build counter-examples to the algorithm, but I couldn't find any.

I will appreciate to read your thoughts.

# Answer
> 0 votes
Your idea works only if you are allowed to *pre-color* vertices. That's not given in the problem statement, so a much simpler idea is to add *a single universal vertex*, i.e. a vertex $u$ that is neighbors with every vertex in the graph. Let this graph be $G'$, and the original graph $G = G' - u$.

Now, if $G'$ is 4-colorable, then it assigns a color to $u$, $\chi(u)$ that no other vertex gets, hence $G$ is 3-colored. This holds both directions. Hence $G$ is 3-colorable if and only if $G'$ is 4-colorable. Indeed, something even stronger holds: $G$ is $c$-colorable if and only if $G'$ is $c+1$-colorable.

---
Tags: reductions, colorings
---


title: Pumping Lemma Applied to 3 Variables

text:
# Question
Title: Pumping Lemma Applied to 3 Variables
Prove That the Language

$L\_1 = \\{0^i1^j0^k | i \< j\ or\ i \> k\\}$

is not regular using the pumping lemma.

I am not sure how to begin with this I ended up using the string:

$0^p1^{p+1}0^{p+1}$

S = 00001111100000

It holds for the conditions because the first set of 0s is less than the set of 1s, and the last set of zeros doesn't matter because I only have to meet one condition

I Divided the string as follows, {000,0,1111100000}

in the case: $xy^2z$ = 000001111100000 is not part of the language because i = j = k so neither condition is met. Please tell me if I did this right and give me some pointers because I have not found a single source that shows how to deal with 3 variables with an or statement.

# Answer
> 4 votes
You seem to misunderstand a bit how the Pumping lemma works. You're not free to choose the value of $p$ or how to divide the string, but need to show that there's *no* factorization for some $w \in L$ with $|w| \geq p$ and $p$ arbitrary that would satisfy the pumping lemma.

The trick here is to find values of $i, j, k$ such that after pumping $j \leq i \leq k$. We know that the pumped substring $y$ must have length $1 \leq |y| \leq p$ for the pumping length $p$, and can use this to clamp the value of $i$ between sufficient $j, k$.

Assume $w = 0^p1^{p + 1}0^{2p} \in L$ such that $|w| \geq p$ for the pumping length $p \geq 1$. Then, if $L$ was regular, there must be $w = xyz$ with

1. $|y| \geq 1$,
2. $|xy| \leq p$, and
3. $xy^iz \in L$ for all $i \in \mathbb{N}\_0$.

Now we must use *only* 1.-3. to derive a contradiction. Notice that from 2. it follows that $y \in 0^+$, and

$$xy^2z = 0^{p + |y|}1^{p + 1}0^{2p}.$$

But then by 1. it follows that $p + |y| \geq p + 1$ and by 2. that $p + |y| \leq p + |xy| \leq 2p$. Therefore $xy^2z \notin L$ contradicting 3. ⭍

---
Tags: finite-automata, pumping-lemma
---


title: Named outputs of a function

text:
# Question
Title: Named outputs of a function
Is there a programming language with named return values?

I imagine something like in the following (syntax to be workshopped):

```
def f(a, b):
    export c = a * b
    d = 3*c
    export e = c + d

```

and then

```
from f(4, b=5) import *
print(c, e)

```

This would obviate the need to repeat variable names (now done by defining output dataclasses/structs/namedtuples, or by unpacking: `return c,e; c,e=f()`).

This is a related question, but it only discusses anonymous tuples.

Functions have automatically bound named inputs; why not outputs.

# Answer
Golang has this feature (named return values):

```
package main

import "fmt"

func f(a, b int) (c, e int) {
    c = a * b
    d = 3*c
    e = c + d
    return
}

func main() {
    fmt.Println(f(4, 5))
}

```

`c` and `e` are named return values of `f` function.
> 3 votes

---
Tags: programming-languages
---


# Question
Title: Are there some additions that a Turing machine cannot perform
The total number of Turing machines is the cardinality of the set of natural numbers. Now consider the following functions

* f1(x) = x + 1
* f2(x) = x + 2
* f3(x) = x + 3
* and so on

Since the total number of these functions is also the same as the cardinality of the set of natural numbers, each of these functions can be assigned to one Turing machine.

Therefore either there must be no Turing machines left to do other computations or they can do other computations at the expense of not being able to do some of these.

What am I missing here. Thank you.

# Answer
The cardinality of even natural numbers is the same as the cardinality of natural numbers.

That does not mean that odd natural numbers do not exist.
> 3 votes

---
Tags: turing-machines, computability
---


# Question
Title: Are languages generated from a statically typed language statically typed?
Are languages generated from a statically typed language statically typed?

So say, generating Python from C++.

*to generate a language from another language:*

You write a *transpiler* in a static language $L\_s$ so that it can produce the equivalent program in language $L\_{sORd}$.

---

Issues:

* The statically typed language must be well-typed so it should not necessarily contain ways to express dynamic types.
* One may be able to emulate dynamic types by using some switches. However, are programs written for such dynamically or statically typed?

# Answer
No, they are not.

A C compiler typically compiles to machine code, which is not statically typed. While machine code is not really a programming language, this should be enough to convince you that the language the compiler compiles to doesn't need to be statically typed, or typed at all.

Examples:

* C compilers often compile to assembly language, which is then assembled into machine code. The types that C can statically check (such as integers and characters) do not exist in assembly language or machine code. Assembly language is not statically typed.
* TypeScript is a statically typed variant of JavaScript (which isn't statically typed). TypeScript is typically executed by compiling it to JavaScript and then executing the resulting JavaScript code (either by interpreting it or by compiling it and executing the result).
* C can be compiled to JavaScript; see e.g. this Reddit thread.
> 2 votes

---
Tags: type-theory, type-checking
---


# Question
Title: Notation in NFA, DFA diagrams and language
I've only recently started learning about deterministic/nondeterministic finite automata and languages and I'd like some clarification on common notation used to describe languages. A 0 or 1 raised to an nth power just means that 0 or 1 occurs n times, correct?

For example: the language $L = \\{ 0^n \mid n ≥ 1 \\} \cup \\{ 1^m 0^k \mid m,k ≥ 0 \\}$.

My interpretation of this represents strings with at least one zero *or* any number of ones followed by any number of zeroes. Strings like `001111000` and `0000110` would not be accepted. What confuses me here is that anything raised to the 0th power is `1`, so I'm not sure if a string accepted by this language must have at least 1 one and 1 zero. I've included images of my state diagrams if that helps:

Another language I am having trouble understanding is $L = \\{ w ∈ \\{0,1\\}^\* \mid w = 0x0, ∀x ∈ \\{0,1\\}^\* \\}$.

My interpretation is as follows: the * star means zero or more, and the ∀ means 'for all, for every', so this language accepts any string that starts and ends with 1 zero, with any number of ones and zeroes in between. I originally thought this was the set of strings that was just a single one or zero between 2 zeroes, so either `010` or `000`. I'm still not entirely sure which one is right. I'd be so grateful for any advice. Thank you!

# Answer
> 8 votes
You need to distinguish between three kinds of operations:

* Operations on numbers such as 0 and 1. $0^3 = 0$ when $0$ is taken to be a number. Here, $0^3 = 0 ⋅ 0 ⋅ 0$, where $⋅$ is integer multiplication.
* Operations on strings of characters. $0^3 = 000$ when $0$ is a string of characters of length 1. Here, $0^3 = 0 ⋅ 0 ⋅ 0$, where $⋅$ is string concatenation. (Usually, concatenation is written without any symbol at all, so the $⋅$ does not appear, but that is just a notational shorthand. You need to think of it as an operation anyway.)
* Operations on languages (sets of strings). Operations on strings can be "lifted" to work on sets of strings. For instance, $⋅$ when applied to sets of strings is pairwise application of $⋅$ on the individual elements. Hence, $\\{0\\}^3 = \\{0\\} ⋅ \\{0\\} ⋅ \\{0\\} = \\{xyz \mid x,y,z \in \\{0\\}\\} = \\{000\\}$.

# Answer
> 6 votes
Consider a finite nonempty alphabet $\Sigma$. The set $\Sigma^\* = \bigcup\limits\_{n\geq 0 } \Sigma^n$ is the set of finite words over $\Sigma$, indeed, for all $n\geq 0$, we define $\Sigma^n$ as the set of finite words of length $n$ over $\Sigma$. For every two words $w,v\in \Sigma^\*$, we define the concatenation $w\cdot v$ as the word $w v$. Then, once we have concatenation, we can define $w^n$, for every natural $n\geq 0$, as the word that is obtained by concatenating $w$ to itself $n$ times, in particular, the empty-word $\epsilon$ is obtained as a concatenation of length 0; that is $w^0 = \epsilon$.

So as you've seen by defining concatenation, we have defined powers of words, and this can be lifted also to languages: given two languages $L\_1, L\_2 \subseteq \Sigma^\*$, the concatenation $L\_1\cdot L\_2$ is defined as the language $\\{ u\cdot v: u\in L\_1, v\in L\_2\\}$ which is the langauge of words that can be partitioned to two words, the first one is in $L\_1$ and the second is in $L\_2$. Now we can generalize that and for a natural $n\geq 0$ and a language $L\subseteq \Sigma^\*$ define $L^n = \underbrace{L\cdot L \cdot L \cdots L}\_{n \text{ times}}$; Note that we define $L^0 = \\{ \epsilon\\}$ as epsilon is obtained as a concatenation of length 0. We can also proceed and define $L^\* = \bigcup\limits\_{n\geq 0} L^n$. Note that $\Sigma^\*$ is defined before the star of a language, yet it reads the same. You can think of $L^\*$ as a generalization of $\Sigma^\*$ for all languages $L\subseteq \Sigma^\*$.

The point here is that we have powers of words, and powers of languages. Any word to the power of $0$ equals epsilon, and any language to the power of $0$ (even the empty language) equals the the language containing only the empty word. Everything boils down to the concatenation which is simply "putting two words next to each other".

There are also regular expressions that have the kleene-star operation, union, and dots in their syntax, etc. For example, $r = (0\cdot 1)^\*\cdot (1\cup 2)$ is a regular expression. Not to confuse with operations on words or languages, regular expressions is another way to generate regular languages. The 1 and 0, and $\*$ in the regular expression $r$ are symbols in its syntax, not words or $\*$ of a language.

# Answer
> 5 votes
For a (usually finite) set $A$ the star denotes the free monoid on $A$ where

$$A^\* = \\{a\_1a\_2...a\_k : k \geq 0 \land \forall i. a\_i \in A\\}$$

is the set of all finite sequences or strings of elements in $A$. So

$$\\{0, 1\\}^\* = \\{\varepsilon, 0, 1, 00, 01, 10, 11, 000, 001, ...\\}.$$

A string raised to the $0$th powers isn't $1$, it's $\varepsilon$. The reason for this ist that $A^\*$ forms a monoid under concatination, meaning that

* conatenation is associative: $(uv)w = u(vw)$ for $u, v, w \in A^\*$
* there's an identity element: $\varepsilon u = u \varepsilon = u$ for $u \in A^\*$

Exponentiation for monoids is defined as follows, $x^0$ is the identity element and $x^{n + 1} = x(x^n)$.

$\mathbb{R}$ also forms a monoid under multiplication, and that's why for all $x \in \mathbb{R}$ holds that that $x^0 = 1$ since $1$ is the identity of $\mathbb{R}$. But the identity of the free monoid $A^\*$ is $\varepsilon$, so $u^0 = \varepsilon$ for all $u \in A^\*$.

---
Tags: formal-languages, regular-languages, nondeterminism
---


# Question
Title: How are conflicts between free and bound de Bruijn indices resolved?
On page 77 (section 6.1) of *Types and Programming Languages* by Benjamin C. Pierce (1st and only edition thus far), there is the following quote regarding naming contexts and de Bruijn indices:

> Γ = x ↦ 4, y ↦ 3, z ↦ 2, a ↦ 1, b ↦ 0
>
> Then x (y z) would be represented as 4 (3 2), while λw. y w would be represented as λ. 4 0 and λw.λa.x as λ.λ.6.

In the second example how do we distinguish between the free variables 0 and the bound variable zero if there were a free variable `b` in the same term? For instance, it seems like `λw. b w` would have the name less term `λ. 0 0`, but this appears ambiguous to me. Maybe I missed something or haven't read far enough ahead.

**Update**

Another point of confusion I had was my misunderstanding that the context Γ was global, but in 6.2 it is stated:

> ... the context in which the substitution is taking place becomes one variable longer than the original; we need to increment the indices of the free variables \[in the substituted term\] so that they keep referring to the same names in the new context as they did before.

So, it appears Γ is local to each abstraction.

# Answer
> 1 votes
The best way to view this, in my opinion, is by looking at the abstract syntax tree. For `λw. b w`, this would be something like:

```
  λw
   |
   @
  / \
 b   w

```

Here, we're going to assign `w` the de Bruijn index 0, because you do not pass any binders in order to get to its definition. However, for `b` we will assign it de Bruijn index 1, since you pass one binder, and it then has index 0 in the context. In general, you add 1 to the index in the context for every binder you pass along the way to reach a use of a variable to compute its de Bruijn index at that point. Thus, `λw. b w` would be represented as `λ. 1 0`.

# Answer
> 0 votes
Working on exercise 6.1.5 part 1 provided some clarity on the issue (at least I believe so). However, the solution provided in the appendix doesn't seem to get into the weeds (implementation details) enough to address this question.

It seems that we can get around this by starting the de Bruijn indices for bound variables after those for free variables; since we are given the context Γ as part of the function, we know all the free variables. Instead of starting an innermost λ-abstraction's de Bruijn index at 0, it would start at max(range(Γ)) + 1, ensuring no conflict.

**Update** The wording in 6.1.5 part 2 seems to confirm this approach: “choose the first variable name that is not already in dom(Γ)”.

---
Tags: programming-languages, types-and-programming-languages, types
---


# Question
Title: Complexity of a naive algorithm for finding the longest Fibonacci substring
Given two symbols $\text{a}$ and $\text{b}$, let's define the $k$-th Fibonacci string as follows:

$$ F(k) = \begin{cases} \text{b} &\mbox{if } k = 0 \\ \text{a} &\mbox{if } k = 1 \\ F(k-1) \star F(k-2) &\mbox{else} \end{cases} $$

with $\star$ denoting string concatenation.

Thus we'll have:

* $F(0) = \text{b}$
* $F(1) = \text{a}$
* $F(2) = F(1) \star F(0) = \text{ab}$
* $F(3) = F(2) \star F(1) = \text{aba}$
* $F(4) = F(3) \star F(2) = \text{abaab}$
* ...

Given a string $S$ formed by $n$ symbols, we define a Fibonacci substring as any substring of $S$ which is also a Fibonacci string for a suitable choice of $\text{a}$ and $\text{b}$.

## The problem

Given $S$, we want to find its longest Fibonacci substring.

### A trivial algorithm

For each position $i$ of the string $S$, suppose that $F(2)$ starts there (it's enough to check that the $i$-th and $(i+1)$-th symbols are distinct). If that's the case, check if it can be extended to $F(3)$, then $F(4)$, and so on. After that, start again from the position $i+1$. Repeat until you reach the position $n$.

We must look at each symbol at least once, so it's $\Omega(n)$. There are only two for loops involved, so we can furthermore say that it's $O(n^2)$.

However (somewhat unsurprisingly) this naive algorithm performs much better than usual quadratic algorithms (if it does a lot of work on the $i$-th position, it won't do a lot of work in the next positions).

How can I use Fibonacci properties to find tighter bounds for the execution time of this algorithm?

# Answer
Say that $F(n)$ *occurs* at some position if the substring starting at that position is compatible with either $F(n)$ or its complementation. How close can occurrences of $F(n)$ be? Take as an example $F(4) = abaab$. If $F(4)$ occurs at position $p$ then it cannot occur at position $p+1$ or $p+2$, but it can appear at position $p+3$. We let $\ell(n)$ be the smallest number such that two occurrences of $F(\ell)$ can occur at distance of $\ell$. You can prove by induction that for $n \geq 4$ we have $\ell(n) = |F(n-1)|$ (for example, $\ell(4) = 3$).

Given a string of length $N$, for each $n$ let $P(n)$ be the set of positions at which $F(n)$ occurs. We can upper bound the running time of your procedure roughly by $\sum\_n |P(n)| |F(n)|$, where the sum runs over all $n$ such that $|F(n-1)| \leq N$ (say). Since occurrences of $F(n)$ are separated by at least $|F(n-1)|$, we see that the running time is bounded by order of $$ \sum\_n |F(n)| \left(\frac{N}{|F(n-1)|} + 1\right). $$ Since the lengths of the Fibonacci words increase exponentially, $\sum\_n |F(n)| = O(N)$. The remaining term is $\sum\_n O(N) = O(N\log N)$, since the sum contains $\log N$ many terms. We conclude that the running time is $O(N\log N)$.

Conversely, the running time on $F\_n$ is $\Omega(|F\_n|\log|F\_n|)$, as can be proved by induction. We conclude that the worst case running time on strings of length $N$ is $\Theta(N\log N)$.
> 5 votes

# Answer
Well, if you will use Fibonacci properties with Aho-Corasick automaton, you can easily figure out that the running time is linear.
> 0 votes

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


# Question
Title: SAT solvers for counting the number of solutions
Are there existing SAT solver libraries that can count the number of solutions of a boolean formula? Can you give examples?

I mean implementations more efficient than the naive approach, i.e. each time a solution is found, a new clause is added to prevent it to be found again.

# Answer
Yes, they are known as #SAT solvers. Some of them are exact, some of them are approximate.

Some of them are based on a version of DPLL that exhaustively find every solution in a factorized way. Some of them, known as bottom up, are based on transforming the input CNF to Boolean circuits for which we know how to find the number of satisfying assignment and which can be inductively built from the clauses (with an exponential worst case obviously). Some of them are approximate and roughly work by trying to halve the space of satisfying assignments by cutting it with a hyperplane until they are no more than $k$ solutions and return $2^\ell k$ where $\ell$ is the number of times the space was divided.

Here is a non exhaustive list. See also the model counting competition of the SAT conference.

DPLL based:

Bottom up:

Approximate:
> 3 votes

---
Tags: algorithms, satisfiability, counting, sat-solvers
---


# Question
Title: Undecidability of the exactly-1-in-k halting problem
The problem:

> Given $k\>1$ Turing machines decide if for every possible input exactly one of them halts.

Is this variant of halting problem undecidable?

Intuitively, it seems that it must be not only as hard as the standard halting problem, it actually is harder. Because even if you have a refutation input string, you'd still need to run the machines, and if none of them halt, it could take forever to verify that this is a correct refutation.

But is there a proof of its undecidability?

# Answer
Consider a Turing Machine $M\_1$. Create $k - 1$ looping machines $M\_2, …, M\_k$ that never halts.

Then $M\_1$ halts on all inputs if and only if for any input, exactly one among $M\_1, …, M\_k$ halts.

There, you have a many-one reduction from $H\_{\textsf{ALL}} = \\{\langle M\rangle \mid M \text{ halts on every inputs}\\}$ which is known to be neither decidable, nor semi-decidable.
> 2 votes

---
Tags: complexity-theory, turing-machines, undecidability, halting-problem
---


# Question
Title: Find all the induced paths with a start vertex
Let $G$ be a graph and let $v$ be a vertex. Is there a polynomial algorithm for the following operation?

**Operation.** Find all the **induced paths** in $G$ with first vertex $v$.

---

**Background**

This problem is the confusion I encountered while reading the article *Induced paths in graphs without anticomplete cycles*. The authors asserted that there is a polynomial algorithm to check whether a graph contains no two non-adjacent cycles (and more generally no k non-adjacent cycles). Their algorithm is as follows:

* For each vertex $v$, find all the induced paths with first vertex $v$.
* For each induced path $P$, find all induced cycles that consist of $P$ and one extra vertex.
* Check whether any two of these cycles are disjoint and have no edges between them.

I am puzzled by the first step. If that's the case, then I think that finding the longest induced path in a graph would be possible with a polynomial algorithm. But as far as I know, it is NP-hard. See https://en.wikipedia.org/wiki/Induced\_path

# Answer
Consider the following graph $G = (V, E)$ where:

* $V = \\{v\_0\\}\cup \\{u\_1,…, u\_n\\}\cup \\{v\_1, …, v\_n\\}$;
* $E = \\{\\{v\_0,u\_1\\}, \\{v\_0, v\_1\\}\\}\cup \bigcup\limits\_{k=1}^{n-1}\\{\\{u\_k, u\_{k+1}\\}, \\{u\_k, v\_{k+1}\\}, \\{v\_k, u\_{k+1}\\}, \\{v\_k, v\_{k+1}\\}\\}$.

Then the graph has more than $2^n$ induced paths from $v\_0$. So there is no way to find all of them in polynomial time.

I think the paper states that there is a polynomial-time algorithm to find them if you make additionnal hypotheses on the graph (though I agree that many details are missing).
> 2 votes

---
Tags: algorithms, graphs, algorithm-analysis
---


# Question
Title: Lightest Paths Tree that is 10 times heavier than an MST of the same graph
Something I was asked to solve and tried to come up with a formula or some method to solve it after I did and couldn't.

* Given is a graph G=(V,E) that is undirected and weighted. Say we want to find the lightest paths tree (assume using Dijkstra's algorithm), we will call it K, and the Minimal Spanning Tree (assume using Kruskal's or Prim's algorithm) that we will call T. How can we ensure that the total weight of K is **10 times** that of T if we run the algorithm on the same source node 's'? Important note: we cannot use negative weights on the edges.

The only way I managed to do this is by drawing and testing a bunch of graphs until I found something that works. It seems if we build a "ferris wheel" graph, and make the inside edges heavy and the outer edges light, we can manage getting a 10 times heavier lightest paths tree.

This definition of a "ferris wheel" graph is **not** formal - a node that is surrounded by more nodes and each node has an edge to the 'middle' node, and each surrounding node has an edge to the node next to it, forming something that resembles a ferris wheel)

# Answer
> 0 votes
Consider a graph $G = (V, E, w)$ such that:

* $V = \\{s\\}\cup \\{v\_1, …, v\_n\\}$;
* $E = E\_1 \cup E\_2$, with:
    + $E\_1 = \\{\\{s, v\_i\\}\mid i\in \\{1, …, n\\}\\}$, $f(s, v\_i) = n + 1$
    + $E\_2 = \\{\\{v\_i, v\_{i+1}\\}\mid i \in \\{1, …, n\\}\\}$, $f(v\_i, v\_{i+1}) = 1$ (with the convention that $v\_{n+1} = v\_1$).

Then the shortest path tree from $s$ will be $(V, E\_1)$, of weight $n(n+1)$, and a MST will be all edges from $E\_2$ but one, and one edge from $E\_1$, of weight $(n-1) + n + 1 = 2n$. That means that there is a factor $\frac{n+1}2$ between the weight of the SPT and the MST. If you choose $n = 19$, you will get what you want.

You can repeat the process by adding other "layers" to the graph, with heavy radial edges and light transversal edges.

I don't know if that was what you described as a ferris wheel, but hey, at least I added a formal definition. (Then again, what you are asking is unclear)

---
Tags: graphs, dijkstras-algorithm, prims-algorithm
---


title: Memory Question

text:
# Question
Title: Memory Question
Say we're back in the 1950s and our clunky computer has a $1$ kilobyte memory. $1$ kilobyte is $1024$ bytes, which is $8192$ bits. When we consider the entire available storage space, there are $2^{8192}$ states we can harness (each bit can be on or off), but in actuality we only utilize $1024$ size-$8$-bit states. In short, we store only $1024$ items, each item being allotted a byte ($8$ bits) of memory when it seems possible to use a $8192$ bit system to store $2^{8192}$ items.

I have very little knowledge of computers. Gracias, muchas.

My question is, for a $1$ kilobyte memory, wouldn't it be better to use an $8192$-bit system (each *word* or unit of memory being $8192$ bits long) rather than a $8$-bit system (the unit of memory being $1$ byte or $8$ bits). There are more *combinations* in the former than the latter, which in my book would mean I could store *more* information. What's all the Sturm und Drang about $32$-bit and $64$-bit "systems"?

# Answer
You are thinking about it wrong. 8192 bits can only store 8192 single bit items. Now, the number of **combinations** that the entire collection of 8192 bits can store is indeed 2 to the 8192.
> 3 votes

# Answer
It does not matter whether 8192 bits are subdivided into 1024 items of 8 bits, 512 items of 16 bits, 256 items of 32 bits, or not subdivided at all - the amount of information one can store in that memory stays always the same. To express this fact in simple math counting the combinations:

$2^{8192} = (2^8)^{1024} = (2^{16})^{512} = (2^{32})^{256}$

which shows your idea of

> There are more combinations in the former than the latter,

must have a calculation error.
> 3 votes

---
Tags: memory-management
---


# Question
Title: how to generate regular expression for the language where symbols have to maintain certain length?
I am having hard time creating regex for languages where symbols must be in certain length. I hope I am not ignorant about rules. we have to generate regex using $^\*,|,+ \text{ and }\cdot$ right?

I am expected to generate a regex for the language $\\{ L = \\{ w ∈ \\{0,1\\}^∗ : |w|\_0 and |w|\_1 \text{ is odd } \\}$. both 0s and 1s have must have odd length.

I was able to generate it for the same language but with even length, but can't find a pattern for this.

# Answer
> 2 votes
I created a DFA recognizing the language and used the Brzozowski and McCluskey's algorithm (state elimination method) to obtain:

$$(00\mid 11)^\*(01\mid 10)\left(00\mid 11 \mid (01\mid 10)(00\mid 11)^\*(01\mid 10)\right)^\* $$

# Answer
> 2 votes
The odd-odd language can be accepted by a four state finite state automaton. It stores for each of the symbols whether it has seen an even or odd number of that symbol. Thus we need two bits, one for each of $0,1$. Reading and $0$ or a $1$ will flip the corresponding bit.

The fun part is that we can reduce this elegantly into a *two* state automaton, holding a single bit (representing *both* parities at the same time), when reading two symbols at a time.

This is seen as follows. Reading $00$ or $11$ will stay in the same state: the parity of both symbols does not change. Reading $01$ or $10$ will move to the other state, both parities change.

Both numbers have to be odd, so we need the strings that have $01+10$ an odd number of times, and any number of $00+11$. This is a much simpler exercise, but equivalent to the original question.

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


# Question
Title: Time complexity of specific variant of Turing Machine
Assume a variant of a one-tape deterministic Turing Machine that reads and writes on the portion of the tape that the input $w$ appears (like linear bounded automata). My question is, how we could bound the time complexity for membership in this type of Turing machine?

I think the time complexity could be the worst as exponential, the reason is if we consider $|w|=n$ and $|\Sigma |=k$ we might have $k^n$ configurations. Consequently, the worst case could be exponential according to $w$. Is this argument correct?

# Answer
> 3 votes
* If the machine is a decider, meaning halts on its input $w$, then it does not repeat a configuration in its run on $w$. Hence, the number of configurations that the machine can be in bounds its running time from above. The number of configurations is at most $|Q| \cdot |\Sigma|^n \cdot n = 2^{log(|Q|\cdot |\Sigma|^n \cdot n )} = 2^{log(|Q|) + n\cdot log(|\Sigma|) + log(n)}$, which is exponential in $|w| = n$ as $|Q|$ and $|\Sigma|$ are constants. Note that the number of configurations takes into account in which state we're in, and at which tape-cell the head of the machine points.
* If the machine is not a decider, we cannot bound its runtime as it may not halt even when it uses bounded space. Note that in this case we can decide for sure if the machine does not halt as it must repeat a configuration given that it uses at most $n$ space.

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


title: A floating-point rounding problem

text:
# Question
Title: A floating-point rounding problem
I run the Python code below. `x` and `y` differ in their 4th and 5th number, and `x` has larger values. The program correctly shows that there is a difference between the two sums, and the difference is not that small. I therefore expect that the sum for `y` is smaller than the sum for 'x'. However, it shows that `x` has the same value as `y`. The floating-point rounding could obviously contribute to this problem. But I am very puzzled by why the two sums are **identical**. If I change `range(5)` to `range(3,5)` (i.e., including only the two different values), the results do show different sums.

I obtained these results from two approaches to solving a problem. One approach is expected to be more accurate than the other, because only one division is performed, while the other approach performs many divisions.

x = [0.333333333333333314829616256247, \
0.133333333333333331482961625625, \
0.057142857142857141072855853281, \
0.025396825396825396803368590781, \
0.011544011544011544001531177628]

y = [0.333333333333333314829616256247, \
0.133333333333333331482961625625, \
0.057142857142857141072855853281, \
0.025396825396825393333921638828, \
0.011544011544011542266807701651]

diff = 0
sum_x = 0
sum_y = 0
for i in range(5):
    diff += x[i]-y[i]
    sum_x += x[i]
    sum_y += y[i]

print(f'{diff:.60f}')
print(f'{sum_x:.60f}')
print(f'{sum_y:.60f}')
```
</code></pre>

# Answer
Python `float` corresponds to C++ `double`. According to Institute of Electrical and Electronics Engineers Standard for Floating-Point Arithmetic (IEEE 754), `double` or `binary64` is specified with:

* Sign bit: $1$ bit
* Exponent: $11$ bits
* Significand precision: $53$ bits ($52$ explicitly stored)

The 53-bit significand precision gives from $15$ to $17$ significant decimal digits precision ($2^{−53}$$1.11 × 10^{−16}$).

Notice $x\[3\]$ and $y\[3\]$ share identical $16$ significant decimal digits precision `2539682539682539`, and $x\[4\]$ and $y\[4\]$ share identical $16$ significant decimal digits precision `1154401154401154`.

They only differ in the $17$th significant decimal digits precision. This is nearing its limit, and only works because the first digit is smaller. This is lost with the larger $x\[0\], x\[1\], x\[2\], y\[0\], y\[1\], y\[2\]$.

We can see that this is no longer erroneous when we change the largest decimal places of $x\[0\], x\[1\], x\[2\], y\[0\], y\[1\], y\[2\]$ to $0.01$ as follows:

```
x = [0.013333333333333314829616256247, \
0.013333333333333331482961625625, \
0.017142857142857141072855853281, \
0.025396825396825396803368590781, \
0.011544011544011544001531177628]

y = [0.013333333333333314829616256247, \
0.013333333333333331482961625625, \
0.017142857142857141072855853281, \
0.025396825396825393333921638828, \
0.011544011544011542266807701651]

```
> 0 votes

---
Tags: floating-point, python
---


# Question
Title: Is it possible to sort numbers in linear time and constant extra space?
The programming language is C++, and the elements of the input `vector` are of type `int` and able to take all valid `int` values. So it’s not possible to store extra information in the input `vector`. Now, is it possible to sort the `vector` in linear time and constant extra space? Simple solutions are preferred.

And to avoid ridiculous constant factors, the constant factor in linear time is at most 100.

# Answer
If you require a comparison-based sorting algorithm akin to quicksort and merge sort, the answer is "No." Simply put, it can be proven that sorting an array of $n$ elements using a comparison-based method in that respect would require, at least, a complexity of $O(n\times log(n))$. Alternatively, Kelly Bundy's solution works fine and does run in linear time, as requested. However, I would not wager too much in terms of efficiency.
> 2 votes

# Answer
(Note: This was posted before their edit.)

Yes. Move all elements with value $-2^{31}$ to the front, order of the remaining elements doesn't matter. Easy in linear time. Then move all remaining elements with value $-2^{31}+1$ to the front (but after the $-2^{31}$ elements). Then do the same with $-2^{31}+2$, ..., $2^{31}-1$. Total time for $n$ elements is $O(2^{32}n) = O(n)$.
> 0 votes

---
Tags: sorting, space-complexity, linear-complexity
---