title: Prove number of nodes in heap

text:
# Question
Title: Prove number of nodes in heap
Consider a variation of the normal heap which we will call the **x-heap**

The **x-heap** of height $h$ has the following properties:

* It will have $2^h$ nodes
* A height of $0$ corresponds to the single root node
* The format of the tree is a root with exactly one child, which in turn is the root of a complete binary tree

We define a **collection** of x-heaps to be sequence $X\_0, X\_1,\dots,X\_k$ with the following properties:

* $height(X\_{i-1})\leq height(X\_i)$, where $0\leq i \leq k$
* There exist at least $i + 1$ (X-heaps) of $height \leq i$, where $0\leq i \leq k$
* There exist at most $i + 2$ (X-heaps) of $height \leq i$, where $0\leq i \leq k$

We cannot have a collection with all of the same type of x-heap (can't have collection with all single nodes)

Prove that if $X\_0,X\_1,\dots,X\_k$ is a collection, then the total number of nodes is between $2^k$ and $2^{k+1}$

---

I am not sure where to start here. I feel I must use the last two bullet points, but not sure how.

Moreover, the trees in a collection can have height $1, 3, 4, 8$ as an example. It is not limited to increasing by $1$.

# Answer
Interesting proposition.

> Moreover, the trees in a collection can have height 1,3,4,8 as an example. It is not limited to increasing by 1.

How could 1,3,4,8 be an example? If you set $i=0$ in "there exist at least $i + 1$ x-heaps of $height \leq i$, where $0\leq i \leq k$", you know there exist at least 1 X-heap of height less than or equal to 0. That means $X\_0$ must be 0. In fact, the height will be increased by 0 or 1 every time.

## Reformulation

Since an x-heap is completely determined by its height, let us introduce almost-natural sequences, which comes from a collection of x-heaps in the question.

An **almost-natural sequence** is a non-decreasing sequence of integers $0=h\_0, h\_1,\dots,h\_k$, where $k\ge0$, such that, for all $0\le i\le h\_k$,

* at least $i + 1$ of them are not greater than $i$
* at most $i + 2$ of them are not greater than $i$.

**Characterization of almost-natural sequences.** An almost-natural sequence must be one of the following.

* $0, 1, \cdots, k-1, k$, i.e., the first $k+1$ natural numbers.
* $0, 1, \cdots, m-1, m, m, m+1, \cdots, k-2, k-1$, i.e., the first $k$ natural numbers with one of them, $m$ repeated once, where $0\le m\le k-1$.

**Corollary.** $2^k\le\sum\_{i=0}^k2^{h\_k}\le2^{k+1}-1$ for an almost-natural sequence $h\_0,h\_1,\dots,h\_k$.

## Exercises

Here are a few related exercises.

**Exercise 1**. Prove the characterization of almost-natural sequences.

Here is a hint. Does a given almost-natural sequence contain a repeated number? If yes, prove that number appears exactly twice and no other number is repeated.

**Exercise 2**. Prove the corollary.

**Exercise 3**. Let a **d-natural sequence** be a non-decreasing sequence of $k+1$ integers $0=h\_0, h\_1,\dots,h\_k$ such that at least $i+1$ and at most $i+1+d$ of them are not greater than $i$ for all $0\le i\le h\_k$. Determine the lower bound and upper bound of $\sum\_{i=0}^k{h\_k}$ and $\sum\_{i=0}^k2^{h\_k}\\,.$
> 0 votes

---
Tags: binary-trees, heaps
---


# Question
Title: Single Layer Perceptron vs Multi Layer Perceptron
Why the single layer perceptron has a linear activation function while the Multi Layer Perceptron has a non-linear activation function ? What is the potential of the Multi Layer Perceptron respect of the Single Layer perceptron ?

# Answer
Your premise is wrong. A single-layer neural network (perceptron) can use a (nonlinear) activation function. Nothing prevents you from doing that.

It's common that the last layer of a neural network doesn't use any activation function, and instead is input into a softmax layer. If there's only one layer, that means that no activation function is used. But this is just a standard convention. There's no ironclad law that says you have to do it this way. You could have an activation function after a single-layer neural network, if you wanted.
> 1 votes

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


# Question
Title: Can the pseudo-random-sequence generator be described as a finite state automaton?
I am thinking some real examples of FSAs in order to help me know how to use the model of the FSA. As I know, the pseudo-random-sequence generator should be a kind of DFAs or FSTs . But I cannot describe a pseudor-andom-sequence generator (e.g. LFSRs) by using $(Q, \Sigma, \delta, q\_{0}, F)$.

Specifically, the input of the pseudo-random-sequence generator is the seed which is a short string. However its output is a long (or even an infinite) string. Maybe we need construct a FSA with a clock, but I have no idea. And what is $F$ (the set of final states) here? I cannot image what is the language of a pseudo-random-sequence generator.

# Answer
> 1 votes
A finite-state automaton can output an unending sequence of outputs, so you don't need to do anything special. The regular language will contain all prefixes of possible output streams.

If you really want to consider infinite strings, you could use Büchi automata to model that. Personally, I don't see the point.

---
Tags: finite-automata, pseudo-random-generators
---


# Question
Title: Smallest circuit for square of sparse symmetric matrix
I have an $n \times n$ symmetric matrix, and I would like to compute its square in as small a circuit complexity as possible. It's sparse: there are $\sqrt{n}$ nonzero entries in each row/column, so the input will be sparse by the output will be nearly a density of $1$. A normal sparse multiplication algorithm would take $O (n^2)$ time which is clearly optimal, but the circuit depth for any sparse representation I can think of is at least $O (n^3)$. (The act of "accessing a given location in memory" is not efficient in circuits.)

Using a fast matrix multiplication method like Coppersmith-Winograd (C-W) would bring me to $O \left( n^{\sim 2.4} \right)$. I know I can use the symmetry to reduce by a constant factor, but I figure not more than that. I'm hoping that the fact that it's squaring (and not multiplying two different matrices) can reduce the exponent, but I don't know how — I know that it can cut my work down a bit because the first iteration of C-W will have some identical results. I can't find any way to use the sparsity at all.

Numerical precision isn't an issue for me; the input is a 0-1 matrix.

In terms of practical purposes, I particularly care about $n \sim 3000$, but am generally curious about asymptotically good answers too. (Just saying this to explain that very huge constant factors are a big negative for me.) Any references very much appreciated!

# Answer
If it's really depth that you care about, I think you should be able to do it with a circuit of depth $O(\log^2 n)$ using sorting networks. I'll assume we want to compute the product $AB$, and that $A$ is represented as an array of rows, where each row is a sorted list of non-zero entries; and $B$ is an array of columns, where each column is a sorted list of non-zero entries. Then the $ik$ cell of the product $AB$ (namely, $(AB)\_{ik}$) can be computed as follows: copy the entire row $A\_{i\cdot}$; copy the entire column $B\_{\cdot k}$; concatenate these two lists; sort them based on their indices, using a sorting network, to bring together entries with a common index; at each position where both matrices have an entry, multiply those entries; and sum up those products. You can build a sorting network with depth $O(\log^2 n)$, and the multiply-and-sum step can be done with depth $O(\log n)$ using an addition tree.
> 0 votes

---
Tags: complexity-theory, circuits, linear-algebra, multiplication, sparse-matrices
---


# Question
Title: Finding infeasible sets of constraints (CSP)
Given a set of constraints, I want to check whether the constraints are feasible. What I am trying now, is to feed the constraints to a solver and check if the solver returns infeasible. I am using both CSP solvers and optimzation (such as MILP) solvers (in the latter case, I set a dummy objective function, e.g., maximize a constant).

This works, so I can check if a given set of constraints is feasible. However, now I am looking for a more general problem: How many set of constraints are infeasible. One way to do this is to generate all sets of constraints separately, and then feed each of them individually to the solver. Alternately, I can ask the solver to enumerate all solutions, then check which ones do not appear in. Both becomes impractical in my case, as the search space is too big to exhaustively enumerate.

> The question is, is there any practical way to find the sets of constraints which are infeasible by using standard CSP/optimization solvers?

Since the question is too broad, let me give a more specific example. Assume, we have 4 binary variables, $x\_0$, $x\_{1}$ and $y\_0$, $y\_{3}$. There are certain constraints (say, $x\_0+x\_1 = 1$, $x\_0+y\_0=1$, $y\_1=1$) which are satisfied only for $(x\_0, x\_1, y\_0, y\_1) = (0, 1, 1, 1), (1,0,0,1)$; hence the rest 14 quadruples are infeasible (which I am interested in). In the first method, I am generating all 16 constraints and checking which ones are infeasible. In the second, I am asking the solver for all solutions and taking those 14's which are not present in the solution. In my case, the number of variables are too large (say, $x\_0, \ldots, x\_{127}$ and $y\_0, \ldots, y\_{127}$), so no method will work in practice.

Modern CSP solvers can check for feasibility for thousands of variables. What I am looking for is kind of the opposite direction: Can it look for non-feasibility?

# Answer
If your system of constraints is expressed as a SAT instance, then this is known as the MAX-SAT problem. MAX-SAT is harder than SAT, but there are standard algorithms. The case of other discrete constraints can be reduced to Weighted MAX-SAT.
> 2 votes

---
Tags: constraint-programming
---


# Question
Title: Batch sizing for convolution neural networks -- powers of 2 or powers of primes?
The conventional wisdom for convolution neural networks (CNNs) is to make the batch size a power of 2 because of hardware utilization/optimizations done in the convolution layers.

A similar logic applies to the Fast Fourier Transform (FFT). However, the FFT is actually best used when it is a size of a power of primes (e.g. $2^M3^N5^P$ where $M,N,P$ are positive integers.) I was wondering if this also applies to CNNs.

# Answer
> 0 votes
No. It doesn't apply to CNNs. CNNs are doing the same operation on each item in the batch; it's much simpler than what's happening in a FFT (which involves interaction between the elements of the array; you can't compute a FFT by just separately doing something to each element of the array in parallel).

---
Tags: algorithms, machine-learning
---


# Question
Title: Doubt over the index value used in dynamic programming
I was going through Count All Palindromic Subsequence in a given String where I've to count all the palindromic subsequence of a given string.

After seeing the brute force(recursive solution), I went through the dynamic programming technique but the index values used surprised me.

```
for (int L=2; L<=N; L++)
{
    for (int i=0; i<N; i++)
    {
        int k = L+i-1;
        if (str[i] == str[k])
            cps[i][k] = cps[i][k-1] +
                        cps[i+1][k] + 1;
        else
            cps[i][k] = cps[i][k-1] +
                        cps[i+1][k] -
                        cps[i+1][k-1];
    }
}

```

In the above code snippet,

```
if(str[i] == str[k])
    cps[i][k] = cps[i][k-1] + cps[i+1][k] + 1;

```

whereas in the code for brute force approach the same thing works using:

```
Else if (str[i] == str[j])
    return   countPS(i+1, j) + countPS(i, j-1) + 1;

```

I agree with what has been used in the brute force but Shouldn't the code following the DP approach be written as:

```
if(str[i] == str[k])
    cps[i][k] = cps[i-1][k] + cps[i][k+1] + 1;

```

because in the brute-force approach if we are computing for `CountPS(i,j)` then for `str[i]==str[j]` case, we need to compute `countPS(i+1,j)` and `countPS(i,j-1)` which in on translating to DP approach should mean that we need to compute cps\[i-1\]\[j\] and cps\[i\]\[j+1\].

But, it isn't like what I'm thinking.

Where am I going wrong in understanding the code?

# Answer
> 2 votes
The code there is not optimal in terms of space as you can reduce the space complexity to n.

In any case I would recommend thinking as follows when you are trying to convert a brute force recursive solution to dynamic programming.

First look at the recurrence.

```
f(i,j) = 1                                   if i==j
f(i,j) = f(i+1,j) + f(i,j-1) +1              if str[i] == str[j)
f(i,j) = f(i+1,j) + f(i,j-1) - f(i+1,j-1)    otherwise

```

Here each i,j pair is a 'state' and each state depends on other states. Dynamic programming stores previously computed states into an array/hashmap/whatever hence allowing us to reuse previously computed states to make the program run faster.

If we are using a 2d array to store the states then state (i,j) is stored in dp\[i\]\[j\]. State (i-1,j) is stored in dp\[i-1\]\[j\] and so on.

In any case look at the recurrence relation of the brute force solution. You can see that:

* For any given state, i depends on the values of i+1 and i
* For any given state, j depends on the values of j and j-1

Thus we can make the following inference:

* Since i depends on i, i+1 values, i+1 must be filled before i. Hence i loops from n to 0.
* Since j depends on j, j-1 values, j-1 must be filled before j. Hence j loops from 0 to n.

So we know the direction of our loops and we can just fill in values accordingly like so:

```
private int count(String s) {
    int[][] dp = new int [s.length()+1][s.length()+1];
    for(int i=s.length()-1; i>=0; i--) {
        for(int j = i; j<s.length(); j++) {
            if(i==j)
                dp[i][j] = 1;
            else if(s.charAt(i) == s.charAt(j))
                dp[i][j] = dp[i+1][j] + dp[i][j-1] +1;
            else
                dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1];
        }
    }
    return dp[0][s.length()-1];
}

```

And this is basically what is in the link that you posted. f(i, string.length-1)'s state contains the result which is why we return dp\[0\]\[s.length()-1\].

```
Time complexity: n^2; Space complexity: n^2

```

**However this is not optimal. Optimal solution below:**

Like I mentioned earlier we can make an optimization in terms of space to give us a better solution. This is not done in the link that you posted.

* Notice that i depends on values of only i and i+1. This means states containing i+2, i+3, ... i+n is useless.
* Similarly j depends on values of only j and j-1. This means states containing j-2, j-3, ... j-j is useless.

If something like this happens for any parameter of the recurrence, it means that we can reduce the dimension of the array by 1. We can either reduce the dimension i or we can reduce the dimension j (since either i or j can be reduced). Just make sure that the dimension you are reducing is the outer loop.

Here i represents the rows and j represents the columns of the array. Below I will show you how to reduce the i dimension. You can do the same with j but just make sure that if you reduce j, j is in the outer loop.

We are reducing dimension i, we need only 2 rows: row i and row 1+1. We dont need the other rows in the matrix. So let row 1 be row1, let row i+1 be row2.

```
private int count2(String s) {
    int[] row1 = new int[s.length()+1];
    int[] row2 = new int[s.length()+1];

    for(int i=s.length()-1; i>=0; i--) {
        for(int j = i; j<s.length(); j++) {
            if(i==j)
                row1[j] = 1;
            else if(s.charAt(i) == s.charAt(j))
                row1[j] = row2[j] + row1[j-1] + 1;
            else
                row1[j] = row2[j] + row1[j-1] - row2[j-1];
        }
        // copy row1 into row2
        for(int j=0; j<row1.length; j++)
            row2[j] = row1[j];
    }
    return row1[s.length()-1];
}

```

The time/space analysis is:

```
Time complexity: n^2; Space complexity: n

```

So the general pattern to convert recursion to bottom up dp is:

1. Look at the recurrence relation
2. Figure out the order of the loops
3. Check to see if any variable x depends on x+-c where c is a constant. If that is the case, we can reduce the space complexity
4. Compute and store state i,j using previously computed states (unless it is the base case)
5. Return the result.

Hope this helps.

# Answer
> 0 votes
> In the above code snippet,
>
> ```
> if(str[i] == str[k])
>     cps[i][k] = cps[i][k-1] + cps[i+1][k] + 1;
>
> ```
>
> whereas in the code for brute force approach the same thing works using:
>
> ```
> Else if (str[i] == str[j])
>      return   countPS(i+1, j) + countPS(i, j-1) + 1;
>
> ```

Your usage of the concept "brute force approach" is dubious at best if not simply wrong. The analysis in initial section of the article is the standard integral part of dynamic programming for the current problem. Henceforth, I will use "in the initial analysis" instead of "for the brute force approach".

Note that the `countPS(i,j)` in the initial analysis is **the same as** `cps[i,j]` (or `dp[i][j]` in the Java version) for the dynamic programming. Both numbers means the number of palindromic subsequences the index of whose first element should be equal to or larger than $i$ and the index of whose last element should be equal or to less than $j$. That article is so brief that it does not even state this critical definition!

Let us start from the code in the initial analysis. Let us replace `j` with `k`. We get

```
 Else if (str[i] == str[k])
      return   countPS(i+1, k) + countPS(i, k-1) + 1;

```

Now replacing countPS by cps, we get

```
 Else if (str[i] == str[k])
      return   cps(i+1, k) + cps(i, k-1) + 1;

```

Note that the last express is none other than `cps[i][k-1] + cps[i+1][k] + 1`, as in the code for the dynamic programming.

> in the brute-force approach if we are computing for countPS(i,j) then for str\[i\]==str\[j\] case, we need to compute countPS(i+1,j) and countPS(i,j-1) which in on translating to DP approach should mean that we need to compute cps\[i-1\]\[j\] and cps\[i\]\[j+1\].

Since `countPS` is `cps`, on translating to DP approach we need to compute `cps[i+1][j]` and `cps[i][j-1]` for `cps[i][j]`. It is as simple as that.

---

> Since I'm using the bottom-up approach, I need to first find the lower array values and then find the higher ones.

Finding the lower array values might not be appropriate in some cases.

The better statement should be to first find the known or easier cases and then compute the unknown or harder one, repeatedly. Or first find the cases on the right side of the recurrence relations and then compute the cases on the left side of the recurrence, which are dependent on the former cases.

> I find it really difficult as to how to move over the dp matrix when writing code for dynamic programming. Here, we traversed in a diagonal manner whereas in other examples(the one I linked in my first comment) we traverse row-wise. How do I know whether to traverse diagonally or to traverse row-wise?

Let us check how we will compute the small subproblems and then combine them to solve bigger subproblems.

First we know as base cases, all `cps[0][0], cps[1][1], cps[2][2], ..., cps[n-1][n-1]` are 1. Note that case cps\[n-1\]\[n-1\] has largest array indices, but it is still a base case and it is considered a smaller subproblem. Their `j - i = 0`.

Next we will compute cps\[0\]\[1\], cps\[1\]\[2\], cps\[2\]\[3\],..., cps\[n-2\]\[n-1\], which are dependent on previous values. Their `j - i = 1`.

Next we will compute cps\[0\]\[2\], cps\[1\]\[3\],cps\[2\]\[3\], ..., cps\[n-3\]\[n-1\], which are dependent on previous values. Their `j - i = 2`.

And so on and on.

Finally we will compute cps\[0\]\[n-1\], which is the biggest subproblem. Its `j - i = n - 1`.

Graphically, we can fill the whole table if we proceed diagonally as shown below.

```
*            * *           * * *                * * * * *
  *            * *           * * *                * * * *
    *     ->     * *    ->    * * *   -> ... ->     * * *
      *            * *          * *                   * *
        *            *            *                     *

```

Looking at the recurrence relations, we see that we are going from cases with smaller difference of the last possible position to the first possible position to cases with larger difference. This "difference" implies "diagonal".

At this example, we are going from cases with smaller sum of indices to cases with bigger sums. This "sum" implies the other "diagonal".

Beside row-wise, column-wise, diagonal-wise, the-other-diagonal-wise, there can be tree-depth-wise or anything-wise. Which-wise depends on how the recurrence relation looks like, although row-wise or column-wise are easier to understand and implement.

---

In case you want to study how we can obtain those recurrence relations, you may take a look at this page on Stackoverflow.

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


# Question
Title: For a given k-DNF formula, what is the size of the formula for the purpose of complexity?
I am currently in the process of proving some complexity bounds about k-DNF. However I am confused what the $n$ in the time complexity would refer to in this case (that is that I don't know how the "size" of a k-DNF is defined, nor was it defined in the assignment). Is it the number of clauses, the number of literals (distinct or nondistinct?) or something else? I think they should all be equivalent for the purpose of complexity, but I would rather adopt the standard convention.

# Answer
> 0 votes
The two standard conventions are number of clauses and number of literals (counted with repetition!). The two measures are within a factor of $n$ of each other.

---
Tags: satisfiability
---


# Question
Title: Shortest path from source to all vertices, but with some wildcards
Here is problem in Sprinklr Interview Experience | Set 5 (On campus – FTE for Product Engineer).

> You are given a graph of $n$ nodes with $m$ bidirectional edges. Each edge has some value associated with it. Vertex $1$ is source vertex. You have $K$ wildcards. In the path from vertex $1$ to vertex $i$ ($2 \leq i \leq n$), you can use at most $K$ wildcards while traversing. When you use a wildcard on an edge, you can pass that edge in summing the cost of path (i.e., value of that edge will be $0$ if you use a wildcard on an edge). Note: You can use at most $K$ wildcards from vertex $1$ to vertex $2$. Now you can again use at most $K$ wildcards from vertex $1$ to vertex $3$ and so on to vertex $n$. In other words, you can use at most $K$ wildcards in each path from source to destination. You have to find minimum distances from node $1$ to all other nodes in graph.
>
> Constraints: $1 \leq n, m \leq 500000, 1 \leq K \leq 15$
>
> Expected Approach: DP with shortest path algorithms on graph.

What I am doing is that, we can choose $k$ edges from $m$ edges in $\binom{m}{k}$ ways. And for each case find shortest path, but that will be too much time complexity.

# Answer
> 4 votes
Take $K+1$ copies of your graph. For each edge $(x,y)$ and for each $i \in \\{1,\ldots,K\\}$, connect the $i$'th copy of $x$ to the $(i+1)$'th copy of $y$ with a zero weight edge. Also connect the $i$'th and $(i+1)$'th copies of each vertex with a zero weight edge. Now calculate the minimum distance between vertex 1 on the first copy to all vertices in the last copy.

I'll let you figure out why this works.

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


# Question
Title: Is there an algorithm for selecting best matching data in a data set given a set of parameters?
What I am trying to do is for a diet app that I am planning to build. The goal is the users will input their desired macros (carbs, fat, protein) and the system should find all recipes that match the provided macros. It does not have to match it exactly, just the best match. Another idea is users provide their daily calorie intake and the system will find the best match, regardless of the macros.

Links and study materials are much appreciated.

# Answer
> 0 votes
Assuming you don't have that many recipes, you could just go over all of them and choose the best $k$ (use a heap of size $k$). You should test the naive approach before looking for fancier approaches.

Otherwise, you could use a data structure supporting nearest neighbor search. These are hard to implement, but good implementations should be available in computational geometry libraries.

---
Tags: algorithms
---


title: How does a computer "wait" time?

text:
# Question
Title: How does a computer "wait" time?
Me and a friend were discussing how programming languages can perform asynchronous tasks, like waiting 15 seconds before performing another task, and we started a debate.

I know that computers have an internal clock that uses the CMOS battery that can keep track of time, but how does it know it has been 15 seconds since right now and since when I told it to wait 15 seconds without looping infinitely and performing conditional operations, or does it do that?

# Answer
If you are using an x86 based computer, see this article: https://en.wikipedia.org/wiki/High\_Precision\_Event\_Timer Other current architectures will use similar methods.

Part of your CPU is a *programmable timer*. The timer increases a counter at fixed intervals, maybe every 100 nanoseconds, with very high precision. It can be programmed to raise an interrupt when certain pre-programmed points in time happen.

If you want your program to execute some code exactly 15 seconds from now, you call some operating system function which will program the programmable timer to raise an interrupt after the counter increases by exactly 1.5 billion counts = 15 seconds. 15 seconds later the interrupt happens, and the operating system will cause your code to run.

If the operating system is clever it will figure out how long it will take from the time the interrupt happens to the time your code will start running (things don't just happen instantly). If this is estimated to take 300 nanoseconds, then a clever operating system will program the timer so that the interrupt happens 300 nanoseconds earlier, so your code starts running after exactly 15 seconds.
> 2 votes

# Answer
In their most basic form, computers use electrical signals that are represented as 1's or 0's. A 1 meaning that there is an electrical signal and a zero meaning that there isn't an electrical signal.

A computer keeps track of time using a vibrating crystal oscillator. This crystal oscillator gives off a constant and precise frequency. The oscillator is powered by a small and weak CMOS battery on your motherboard that provides a constant electrical signal for up to three years.

So how can a computer use this oscillator along with binary (1s and 0s) to keep track of timers?

When an interval is set, a value of zero is given to the computer along with a threshold based on the length of the interval and the frequency of the oscillator.

```
threshold = length of interval in ms / 1000 * frequency of crystal in MHz

```

When the oscillator vibrates, it puts off an electrical signal (1) and triggers a binary calculation that adds 1 to to the initial binary number (the one that started at 0). Once the initial value passes the threshold, the binary function puts off a 1 indicating that the interval has been fulfilled. Depending on the operations that are done after the threshold is met, the interval may be reset, saved, altered, or deleted.

Helpful links:

https://www.youtube.com/watch?v=1gyCZIBk\_88

https://www.computerhope.com/jargon/q/quartz.htm
> 2 votes

# Answer
It depends on the specific architecture. But I think typically there is a timer interrupt that occurs every so often, so the computer can enter a low-power state and "go to sleep" and be woken up by the next timer interrupt; and if it's not time yet, it can go back to sleep.

At any time, the processor can query the clock hardware to observe what the current time is. How does that work? I think there's a simple hardware circuit that has a counter that increments each time the crystal "ticks". Thus, if you know the date and time at which this was reset to zero, by querying this counter you can learn the current time. So, the computer can query this whenever useful (including in response to an interrupt), and check whether it's time to do the scheduled task yet.

See https://superuser.com/q/253471/93541 and https://superuser.com/q/907902/93541 for lots of details on how this works.
> 1 votes

---
Tags: computer-architecture, programming-languages
---


# Question
Title: What does it mean to take a union of a transition function with a starting state?
$$ \delta(q,a) = \begin{cases} \delta\_1(q,a) & q \notin F\_1 \text{ or } a \neq \lambda \\ \delta\_1(q,a) \cup \\{q\_1\\} & q \in F\_1 \text{ and } a = \lambda. \end{cases} $$

Look at the second line of the function definition. It's a transition function. $q\_1$ is the starting state. What does that union mean here? Union of the function range with $\\{q\_1\\}$?

# Answer
The function $\delta\_1$ is the transition function of an NFA. It outputs a set of states. So $\delta\_1(q,a) \cup \\{q\_1\\}$ is just the union of two sets of states.
> 2 votes

---
Tags: automata, finite-automata
---


# Question
Title: Master Method: $T(n) = 10T\Big(\frac{n}{2}\Big) + \frac{n^4}{\log(n)}$
I'm having a hard time trying to understand how to solve this recurrence relation using the Master Method:

$$T(n) = 10T\Big(\frac{n}{2}\Big) + \frac{n^4}{\log(n)}$$

First, we have:

$a = 10,\ b = 2$ so we have $n^{\log\_2^{10}} = n^{\lg10}$

Now we need to find how $f(n)$ compares to $n^{\lg10}$.

And here I'm stuck. What do I have to pay attention to in order to know whether I'm dealing with Case 1 (and look for $O(n^{{\lg10} - \varepsilon}))$ or Case 3 (and look for $\Omega(n^{{\lg10} + \varepsilon})) $ of the method?

My attempt:

From what I know $\log(n) \< n^\varepsilon\quad \forall \varepsilon \> 0$. So

$$\frac{1}{\log(n)} \> \frac{1}{n^\varepsilon}$$ $$\frac{n^4}{\log(n)} \> \frac{n^4}{n^\varepsilon}$$

$$\implies \frac{n^4}{\log(n)} = \Omega( n^{4-\varepsilon})$$

but I have no idea how to relate this (assuming no mistakes) with one of the two cases. In Case 1 we deal with $O(\cdot)$ and not $\Omega(\cdot)$ while in the 3rd Case the form of the exponents doesn't seem to match.

# Answer
In order to apply Case 3, you have to show that $\frac{n^4}{\log n} = \Omega(n^c)$ for some $c \> \log\_2 10$, as well as the regularity condition (which holds for functions of the form $n^\alpha \log^\beta n$).

You take it from here. Hint: $4 \> \log\_2 10$.
> 1 votes

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


# Question
Title: $O(n\log n)$ algorithm for minimizing number of inversions in leaves of complete binary tree
I'm having trouble making an algorithm to fit these specs:

* Given a complete binary tree ($n = 2^d$ leaves) with integers in leaves.
* Reading the leaves from left to right makes a sequence of integers (we can assume we have an array)

**Goal**: How can we minimize the number of inversions in that array only by choosing non-leaf nodes and swapping the the subtrees under the given nodes. For example, if the sequence is (4,2,1,3), then choosing the root (swapping its direct children) followed by choosing the right child of the root (and swapping its direct children) turns the sequence into (1,3,2,4), which has only one inversion. This would be the minimum number of inversions.

**My approach**: My idea was to use something like merge sort but modified. First i would recursively split the array and then when I merge back together I'd need to change the strategy. For the first level of merges (say I have the integers \[2\] and \[1\]) I can simply put those in the correct order because our swapping operation doesn't prevent this.

However, once I have to merge something like \[1,2\] and \[3,4\] (and larger groups which are powers of 2), I have to move those groups as single units (because of the operation we have to use). I can't put it in exact order like I want but I was thinking maybe it would be best to merge the larger groups by summing up all the numbers inside the groups and moving the groups with the smallest sums to the left to minimize inversions. That seems inefficient though. All the while I have to somehow count inversions. I'm really kind of lost on what to do besides what I've thought of so far. Would anyone be able to help?

# Answer
> 0 votes
Let us denote by $L(x)$ the set of leaves in the subtree rooted at $x$. The idea is that the decision whether to switch the two children $x\_1,x\_2$ of $x$ depends only on $L(x\_1),L(x\_2)$, and depends on how many of the pairs $(a,b) \in L(x\_1) \times L(x\_2)$ satisfy $a \< b$ and how many satisfy $b \< a$.

If the sets $L(x\_1),L(x\_2)$ were available to you in their sorted forms, then you could count the number of pairs of each type by merging these sets and doing some accounting. This suggests a recursive algorithm which sorts the leaves using the merge sort strategy.

Details left to you.

---
Tags: algorithms, sorting, binary-trees, divide-and-conquer
---


# Question
Title: Advances in recent time in Von-neumann self replication idea
I have read about Von-neumann self replication from Theory of Self-reproducing automata, which are lecture notes reconstructed from lectures in book of the same name. Theory of Self-reproducing automata

> Its looks really interesting that neumann has formalize this even far before the discovery of DNA. I'm looking the work now from biological perspective and the work by Jeremy England his paper on Statistical Physics of Self-Replication and other similar work in irreversible biological process.

The work that Von-neumann did was around 50's. Is there any recent relevant work in this field based on the neumann's work. One that i could see is Enhancing the Robustness of Self-Replication Processes

Thank You.

# Answer
For those who don't know, I am the world's only producer of a von Neumann 29-state self-replicating cellular automaton.
Indeed, respecting vNCA, I am the world's expert. Ask Sayama (U Binghamton), Reggia(U of Maryland), or Adamatzky (U of South of England). While DW may be a moderator, he does not know anything about von Neumann's cellular automata, I dare say he has not designed such self-replicators, and he certainly had not designed a machine zygote. For my design of a machine zygote, see here: https://www.researchgate.net/publication/235432119\_Computational\_Ontogeny One more thing, it is 29 states, not 28.
> -1 votes

---
Tags: turing-machines, computation-models
---


# Question
Title: $ L = \{xyyz\in\{0,1,2\}^{*} : y \neq \epsilon \wedge \exists_{a \in \{0,1,2\}} |y|_a \equiv 0 \}$
$ L = \\{xyyz\in\\{0,1,2\\}^{\*} : y \neq \epsilon \wedge \exists\_{a \in \\{0,1,2\\}} |y|\_a \equiv 0 \\}$

I think this languages is regular. I write regular expression: $(1 + 2 + 0) ^ {\*} (11 + 22 + 1212 + 2121) (1 + 2 + 0) ^ {\*} \cup (1 + 2 + 0) ^ {\*} (11 + 00+ 1010 + 0101) (1 + 2 + 0) ^ {\*} \cup (1 + 2 + 0) ^ {\*} (00 + 22 + 0202 + 2020) (1 + 2 + 0) ^ {\*}$

Can someone check out my answer?

# Answer
> 1 votes
Slight more formally, we have $$ L = \\{xyyz : x,y,z\in\\{0,1,2\\}^{\*} \wedge y \neq \epsilon \wedge \exists\_{a \in \\{0,1,2\\}}\\,|y|\_a = 0 \\}$$

Yes, your regular expression is correct. It can be made simpler.

$(0+ 1 + 2) ^ {\*} (00 + 11 + 22 + 0101 + 1010 + 0202 + 2020 + 1212 + 2121)(0 + 1 + 2) ^ {\*}$

---
Tags: regular-languages, regular-expressions, check-my-answer
---


# Question
Title: Why are regular expression used in lexical analysis instead of grammars?
Even though grammars can do what regular expressions do, why are regular expression employed instead of grammars in lexical analysis?

# Answer
> 2 votes
Regular languages are faster to recognize, and so they are preferred whenever possible. Fortunately, regular expressions are usually good enough for describing the lexemes of a language.

Indeed, in some sense the separation between lexical analysis and parsing is exactly due to this fact, that lexical analysis can be done more efficiently than parsing.

---
Tags: compilers, lexical-analysis
---


# Question
Title: Fast multiplication with a full binary $n \times 2^n$ matrix
Let $A$ a $n\times n$ matrix, and X the full matrix of $n\times 2^n$ binary vectors (you can choose the order of the columns of X).

What is the fastest way to compute the product AX?

# Answer
> 0 votes
Suppose that $A$ were a $1 \times n$ matrix, let $X\_n$ denote your matrix for a given value of $n$, and let $A\_{\<n}$ consist of all but the last entry $A\_n$ of $A$. Then up to rearrangement, $$ AX\_n = \begin{bmatrix} A\_{\<n} X\_{n-1} & A\_{\<n} X\_{n-1} + A\_n \end{bmatrix}, $$ where $+A\_n$ means adding $A\_n$ to *all* entries. The running time of this procedure satisfies the recurrence $$ T(n) = T(n-1) + O(2^{n-1}), $$ whose solution is $T(n) = O(2^n)$, which is linear in the size of the output. This should be compared to the trivial $O(n2^n)$ solution.

You can save a factor of $n$ in your case in the same way. The resulting algorithm is asymptotically optimal.

---
Tags: algorithms
---


# Question
Title: How to find how many times an object's path crosses another?
I have several hundred objects that will move in a fixed area throughout the day. Frequently the objects will cross over another object's path, either at the same time (eg. a collision) or within a few seconds or minutes, the time window tolerance. How can I determine how many times that happens throughout a fixed period of time, let's say in a day?

For example, to visualize it on a simple level, let's say I have 2 points, A & B, arranged in a north-south and east-west configuration:

```
         (A) - Loc 1

              |
              |

```

Loc 3---------------------- (B) Loc 4

```
              |
              |
            Loc 2

```

Object A moves only from Loc 1 to Loc 2 throughout a given period of time. Likewise Object B only moves from Loc 3 to Loc 4 during that same period of time. They cross paths at the center. One could just calculate the speed of A and figure out when it hits the location of the path cross, and also do that with B. Then simply determine when those cross point time windows are close. However that logic breaks down when I have hundreds of objects, variable indirect paths, and changing speeds.

What I am given at the end of the day is the path of each object, timestamps along the path, stops and times. Is there a straightforward way or algorithm to determine how many times one path crossed another during a time window tolerance?

# Answer
> 1 votes
This can be done by what I'd call "accelerated replay" (I'm making up this term).

Let's suppose the movement of each object is piecewise linear: each object moves in a straight line at a constant speed for a while, then changes direction and moves in a different direction at a different speed, etc. So, object $i$'s path can be specified a sequence of times $t\_{i,0},t\_{i,1},\dots,t\_{i,n}$ at which the object changes direction; between times $t\_{i,j}$ to $t\_{i,j+1}$, the object is moving in a straight line (with known endpoints) at a constant speed. The algorithm can be generalized to allow each individual piece of the path to be curved or other shapes as well, but it's easiest to describe in this setting.

So, let's take the union of all of the times $t\_{i,j}$ and sort them. In this way, we get a set of "events", where each "event" corresponds to an object changing direction/speed. Now, we're going to replay all of the object movements. However, we're going to "fast forward" through all of the times that fall between two adjacent events. In other words, we're going to iterate through the events in time order.

At a single step of the algorithm, we're going to be processing a particular event, say the event at time $t\_{i,j}$ where object $i$ changes direction. We know the line segment that each of the other objects are currently on; and we know the line segment that object $i$ will travel on after time $t\_{i,j}$. So, for each other object $i'$, compute the location where the lines for objects $i$ and $i'$ intersect, check the time when that will happen, and check whether that time is before the end time for both line segments; if so, you've found a cross-over. Notice that finding the intersection point of two line segments can be done in constant time ($O(1)$ time). Once you've done that, you've taken into account all cross-overs that can occur until the next event. So, no need to continue simulating what happens in any future time, until the next event. So, fast-forward to the next event, and then do the same thing for the next event.

The total running time will be $O(nm)$, where $n$ is the number of objects and $m$ is the total number of events. Or, if you expect $q$ events per object (i.e., $q$ changes of direction), then the total running time will be $O(n^2q)$. Since you have only a few hundred objects, that should be quite reasonable.

It's plausible to me that it might be possible to reduce this to something more like $O(nq \log n)$, using techniques from computational geometry (e.g., Shamos-Hoey etc.), if that were really necessary -- but I haven't tried to think about whether that's possible, as given the numbers you listed in your question, the algorithm above should be fine.

If you want to find "points of closest approach" instead of "crossovers", it's easy to adjust the above algorithm to do that. Given two line segments, it is easy to find their point of closest approach in $O(1)$ time, so then you just apply the same ideas as before. If you want to deal with curved trajectories, that is also possible; if you have two curved lines that are parts of a circle, it is also possible to find whether they intersect in $O(1)$ time using some trigonometry, so again you can generalize the above algorithm to handle that as well.

There are probably many pragmatic ways one could speed this up, e.g., by using quadtrees to separate the plane into multiple regions and map each part of the path to the region(s) it visits, and then only look for crossovers within each region.

---
Tags: algorithms, graphs
---


title: What does all uppercase letters mean?

text:
# Question
Title: What does all uppercase letters mean?
I am reading https://www.irif.fr/~mellies/mpri/mpri-ens/biblio/Selinger-Lambda-Calculus-Notes.pdf and would like to know, what the following statement means:

```
Lambda terms: M,N ::= x | (M N) | (λx.M).

```

It is from page 11.

What does for example mean? Is `x` a type of `M` and `N`?

# Answer
> 5 votes
As it's explained in the comments, $M$ and $N$ are know as **metavariables**. More importantly, this kind of definition is known as an **inductive definition**, that is, you start with very basic elements (symbols belonging to the set $\mathcal{V}$) and build up more complex things from there.

For instance, let $\mathcal{V} = \\{v\_0, v\_1, \ldots, v\_{1001}, \ldots\\}$. In the BNF definition:

$$ M,N ::= x \mid (M N) \mid (\lambda x.M) $$

* $x$ can be any of the $\\{v\_0, v\_1, v\_2, \ldots \\}$. That means any symbol from $\mathcal{V}$ can be considered a $\lambda$-term, a most basic of rules.
* $M$, $N$ are structures already known to be $\lambda$-terms, so from the previous example we can build expressions like $(v\_0 ~ v\_1)$, $(v\_{100} ~ (v\_{0} ~ v\_{1}))$, $((v\_{100} ~ (v\_{0} ~ v\_{1})) ~ v\_2) $ and so on.
* With the previous two rules you can now build more complex expressions like $(\lambda v\_{100}. (v\_0 ~ v\_1))$, since all previous terms made by combining the two previous rules are known to be $\lambda$-terms.
* Now you can mix all three rules, like in $(v\_0 ~ (\lambda v\_9.(v\_9 ~ v\_{999})))$

---
Tags: lambda-calculus
---


title: Identity types and universes

text:
# Question
Title: Identity types and universes
Let us consider Martin-Löf type theory with a cumulative hierarchy of universes $$ \mathcal{U}\_0\colon\mathcal{U}\_1\colon\ldots $$ If $A, B\colon \mathcal{U}\_i$, we can form an identity type $A=\_{\mathcal{U}\_i} B:\mathcal{U}\_i$. Using the axiom of cumulative hierarchy, we can derive $A, B:\mathcal{U}\_{i+1}$, so we have also an identity type $A=\_{\mathcal{U}\_{i+1}}B$. Assuming the Univalence axiom (for all the universes), they are both equivalent to a type of equivalences $(A\simeq B)$, which has nothing to do with universe issues. What can we say about the relationship between types $A=\_{\mathcal{U}\_i} B$ and $A=\_{\mathcal{U}\_{i+1}} B$ without the Univalence axiom?

# Answer
> 3 votes
In general cummulative universes are a bit nasty. To see what is really going on, at the very least it makes sense to have explicit *lifting* maps $\mathsf{lift}\_{i,j} : \mathcal{U}\_i \to \mathcal{U}\_j$ for $i \leq j$. With these in place, your question is: how do the types $$\mathsf{lift}\_{i,i+1}(A =\_{\mathcal{U}\_i} B)$$ and $$(\mathsf{lift}\_{i,i+1} A) =\_{\mathcal{U}\_{i+1}}(\mathsf{lift}\_{i,i+1} B)$$ relate? The answer is: unless we make further assumptions, we cannot show them to be equivalent. In fact, when type theory is given with explicit $\mathsf{lift}\_{i,j}$ maps, we include judgemental equalities which say "lifting maps commute with type constructions", such as, for $i \< j$, $$\mathsf{lift}\_{i,j}(A =\_{\mathcal{U}\_i} B) \equiv (\mathsf{lift}\_{i,j} A =\_{\mathcal{U}\_{j}} \mathsf{lift}\_{i,j} B).$$ These sorts of details are usually skipped in informal presentations of type theory. In particular the HoTT book is a bit sloppy on this point. (But the formalizations of HoTT in Coq, Agda and Lean are not.)

# Answer
> 2 votes
The induction principle for $=\_{U\_{i+1}}$ gives you a map $(A=\_{U\_{i+1}}B)\rightarrow (A=\_{U\_i}B)$.

In HoTT without univalence, there is no map $(A=\_{U\_i}B)\rightarrow (A=\_{U\_{i+1}}B)$: indeed, you could assume the univalence axiom only for universe $U\_i$. In that case, $A\simeq B$ gives you by univalence an inhabitant of $A=\_{U\_i}B$, but not of $A=\_{U\_{i+1}}B$: with the rules of the theory, the inhabitants of the identity types $=\_{U\_{i+1}}$ can only take the form $refl\_A$.

---
Tags: type-theory, dependent-types, homotopy-type-theory
---


# Question
Title: If there is any sense of an optimal set of instructions in an ISA
So there are One Instruction Set Computers, having only one (complicated) instruction like `addleq`, "add and branch if less than or equal to zero". And then there are extremely complicated Instruction Set Architectures (ISAs) with 100's of instructions like x86.

Most computers today I think use the x86 architecture, though ARM architectures seem like they are gaining some attention. I think x86 is popular (for one reason or another) because they have created these many instructions to handle specific use-cases, and so can be performance-optimized for specific common instruction scenarios.

However, I am interested in the fact that all logic can be boiled down to AND + NOT or OR + NOT. I'm not sure if this means you can implement a computer with just these two instructions, or if it's not possible to model things like ALUs using them. But it's interesting.

What I'm wondering though is if there is any notion of "optimal" in the architecture of an ISA. For example, it's a lot easier to *represent* things you can do in a computer with the let's say 20 or 30 or so regular operators like `+` and `>=` and `=`, etc. LLVM also shows you can have a pretty small instruction set, not taking into account the instructions with multiple different variations based on the datatype (int32 vs. int64, etc.). But either way, from a practical perspective I suspect most people don't use the 100's of x86 instructions, and instead use a standard small subset. Compiler architects probably do because they have the time and resources to do all the micro optimizations perhaps.

But then there are the optimizations in terms of processor speed. Implementing custom instructions like x86 does probably allows you to take advantage of hardware accelerations. So there is a balance.

My question is if there are any resources/papers/topics on "optimal" and "minimal" ISAs. Maybe they have like 10 or 20 instructions or something like that. Some minimal but not too minimal as in OISCs.

# Answer
> 3 votes
The paper you are asking for is:

> Patterson, David A; Ditzel; David R: The case for the Reduced Instruction Set Computer, *Computer Architecture News*, 8(6):25-33, Oct 1980. (non-paywalled copy).

Beware that it may be the paper you are asking for, but may not be the paper you *want*. Almost everything it says is false, or has been debunked. It is more of a humanities paper than a computer science paper.

There are ways of reducing the number of instruction bits that are fetched from DRAM (using more-or-less traditional compression techniques like Huffman encoding). (And these kinds of concerns about minimizing instruction bits are evident in most "CISC" designs, as I described in a different question.) There are ways of minimizing the decode logic of a state machine (see for example the work of Villa, Kam, Brayton and Sangiovanni-Vincentelli, especially their 1997 book). There are ways of minimizing the amount of power consumed by an instruction (for example, by *increasing* the number of different things that the instruction does, thereby better amortizing the power costs of fetching and decoding the instruction).

Finally, when there are ways of better representing instructions internally (for example to reduce decode power) it is trivial to do the translation from the "bad" instruction set to the "good" instruction set and cache the result. (Something x86 processors and many others have been doing since the late '80's (I can't find the academic references for this idea right now)).

What is rarely the case is that minimizing the number of instruction *opcodes*, or minimizing the number of addressing modes, is correlated with optimizing anything else about a computer design.

---
Tags: reference-request, computer-architecture
---


# Question
Title: Asymptotic relation between n! and (n+1)!
I am having difficulty writing this formally. I know that by L'Hospital's rule we can reduce it to $\lim\_{n \to \infty} \frac{n+1}{n}$ which is a constant and hence $n = \theta (n+1)!$. But I am not sure how to write this formally.

# Answer
> 2 votes
I am afraid that you could have been more careful.

> I know that by L'Hospital's rule we can reduce it to $\lim\_{n \to \infty} \frac{n+1}{n}$ which is a constant and hence $n = \theta (n+1)!$.

By L'Hospital's rule we have $$\lim\_{n \to \infty} \frac{(n+1)!}{n!}=\lim\_{n \to \infty} (n+1)=\infty\\,, $$ which means $(n+1)! = \omega(n!)$, or what is equivalent, $n! = o(n+1)!$. Note that both $(n+1)! = \Omega(n!)$ and, what is equivalent, $n! = O(n+1)!$ are correct, which are, however, less precise.

---
Tags: complexity-theory, time-complexity, asymptotics, landau-notation
---


# Question
Title: Algorithm / data structure to filter documents by number of missing words
Is there a data structure or an algorithm or a combination of both to allow me to filter a set of documents based on the number of missing words (compared to another list)?

## Problem Definition

We have a list of documents $D = \\{d\_1, d\_2, \dots, d\_n\\}$. Each document $d\_i$ consists of a subset of words from a word pool $W = \\{w\_1, w\_2, \dots, w\_k\\}$. For example, $\text{words}(d\_1) = \\{w\_1, w\_5, w\_{7}\\}$.

Each person $p\_j$ also has a set of words $\text{words}(p\_j)$.

The goal is to find all documents where the length of the set difference between both is smaller than a threshold $t$:

$$ |\text{words}(d\_i) \setminus \text{words}(p\_j)| \< t $$

$\text{words}(p\_j)$ will in most of the cases be much larger than $\text{words}(d\_i)$ (i.e. there will be a lot of words in the person's set that are not in the document's set).

## Complexity

The sizes will probably be around these numbers:

* documents: millions or tens of millions of documents
* words: around 100k different words (per independent set)
* person: between 1 and 1000 people

## Use Cases

My actual use case for this is to retrieve foreign language texts where I do not know all the vocabulary, yet. I have a list of words that I know for each language and I want to find documents from a collection of texts that contain between 1 and 10 words that I do not know, yet. That way, I expect to be able to find texts that I can understand while also improving my vocabulary skills.

Another use case might be finding recipes that match a user's stock at home. In this case, you might want to find documents (recipes) that contain between 0 and 2 missing items, so that the user either has to buy nothing or can replace the few missing items with something similar.

## My current approach

While it is easy to find documents that have an overlap of at least $t$ words, I found the opposite (find documents that have a difference of at most $t$ words) quite complex. At the moment I fell back to a two stage approach:

1. I first filter documents by the length of the text and the length of the sentences and compare them to an average value I store for myself
2. In the filtered list I then loop in my code and calculate the set difference for each document and delete all that have more than $t$ unknown words.

# Answer
Use a locality sensitive hash, like MinHash or SimHash.

You could also sort the set of words, extract shingles, and hash them using MinHash or something similar.
> 1 votes

---
Tags: data-structures, sets
---


# Question
Title: Difference between sequential and parallel divide and conquer
In the textbook *Introduction to Algorithm*, third edition, by Coremen et al. (CLRS), the following introduction has been given about divide and conquer algorithm strategy

> In divide and conquer, we solve a problem recursively, applying three steps at each level of recursion:
>
> **Divide** the problem into a number of subproblems that are smaller instances of the same problem
>
> **Conquer** the subproblems by solving them recursively. If the subproblems sizes are small enough, however, just solve the problems in a straight forward manner.
>
> **Combine** the solutions into the solution of the original problem.

This algorithmic strategy is assumed on sequential machines and is a non-parallel divide and conquer strategy.

How is parallel divide and conquer different from the above? Which step among divide, conquer, combine will be different?

My assumption is that the dividing step will not change and combine step will not change, but only the conquer step changes and the change will be that each subproblem will be solved in parallel. Is it true?

# Answer
Just like you wrote, you can solve independent subproblems in parallel. Here are two examples:

* In merge sort, you can sort the two halves of the input in parallel, and then merge them together sequentially.
* In quicksort, you split the input into two halves sequentially, and can then sort both of them in parallel.

In the first case there is no *divide* step, and in the second case there is no *conquer* step. In other cases probably all three steps will be present.

Some divide-and-conquer approaches have a single subproblem. This is the case in binary search. Such algorithms do not benefit from parallelization.
> 3 votes

---
Tags: algorithms, parallel-computing, divide-and-conquer
---


# Question
Title: Algorithm to solve $L_1$ optimization of $\sum_i ||\mathbf{A_i x} - \mathbf{b_i}||_1$
Is there is an efficient algorithm to solve the following optimization:

$\mathbf{x}^\* = \arg\min\_\mathbf{x}\sum\_i ||\mathbf{A\_i x} - \mathbf{b\_i}||\_1$

for given $\mathbf{b\_i}, \mathbf{A\_i}\ \forall i$, where $|| \mathbf{y} ||\_1$ is the $L\_1$ norm (i.e. $\sum\_j |y\_j|$) and $\mathbf{A\_i}$ are big matrices which we don't have their explicit representations, only access to operations $\mathbf{A\_i y}$ and $\mathbf{A\_i^T z}$?

I can solve the problem for small matrices $\mathbf{A\_i}$ using linear programming using the same trick from here, but if the matrices are large, there is no obvious way (at least for me) to solve it using linear programming.

Any ideas and suggestions are welcome.

# Answer
> 2 votes
I have found the answer for this problem. One way is, as suggested in the comment, to stack the matrix $\mathbf{A\_i}$ and $\mathbf{b\_i}$ together and apply first-order convex optimization algorithm, such as Primal-Dual Hybrid Gradient (PDHG), inexact ADMM, or their variants.

For PDHG, the problem to solve is

\begin{align} \mathrm{min}\_{\mathbf{x},\mathbf{y}} &~ F(\mathbf{y}) + G(\mathbf{x}) \\ \mathrm{s.t.} & ~ \mathbf{Ax} = \mathbf{y} \end{align}

where

\begin{align} F(\mathbf{y}) &= ||\mathbf{y} - \mathbf{b}||\_1 \\ G(\mathbf{x}) &= 0 \\ \mathbf{A} &= \[\mathbf{A\_1}^T, \mathbf{A\_2}^T, ..., \mathbf{A\_n}^T\]^T \\ \mathbf{b} &= \[\mathbf{b\_1}^T, \mathbf{b\_2}^T, ..., \mathbf{b\_n}^T\]^T. \\ \end{align}

Thus, the convex conjugate of $F(\mathbf{y})$ is

\begin{align} F^\*(\mathbf{y}^\*) &= \mathrm{sup}\_{\mathbf{y}} \left\[\left\<\mathbf{y},\mathbf{y}^\*\right\> - F(\mathbf{y})\right\] \\ F^\*(\mathbf{y}^\*) &= \left\<\mathbf{b},\mathbf{y^\*}\right\> + \mathcal{I}\_{\mathbf{y^\*}\<\mathbf{b}} \end{align} where $\mathcal{I}\_\mathcal{C}$ is an indicator function with value $0$ if the condition $\mathcal{C}$ fulfilled, otherwise $\infty$.

As the algorithm uses proximal operator, we need to get the proximal operator for $F$ and $G$,

\begin{align} \mathrm{prox}\_{F^\*\sigma}(\mathbf{y}^\*) &= \arg\min\_{\mathbf{y}'}\left\\{\frac{||\mathbf{y}'-\mathbf{y}^\*||^2}{2\sigma} + F^\*(\mathbf{y}^\*)\right\\} \\ \mathrm{prox}\_{F^\*\sigma}(\mathbf{y}^\*) &= \max(\mathbf{y}^\* + \sigma \mathbf{b}, \mathbf{b}) \\ \mathrm{prox}\_{G\tau}(\mathbf{x}) &= \mathbf{x} \\ \end{align}

Thus, the algorithm in this case reads

\begin{align} \mathbf{y}^{n+1} &= \max(\mathbf{y}^n + \sigma \mathbf{A} \mathbf{w}^n + \sigma \mathbf{b}, \mathbf{b}) \\ \mathbf{x}^{n+1} &= \mathbf{x}^n - \tau \mathbf{A}^T \mathbf{y}^{n+1} \\ \mathbf{w}^{n+1} &= \mathbf{x}^{n+1} + \theta (\mathbf{x}^{n+1} - \mathbf{x}^n), \end{align}

with $\theta = 1$, and $\sigma \tau ||A||^2 \< 1$.

All the operations do not need the direct access to the element of the matrix $\mathbf{A}$ and only require the operation of $\mathbf{A} \cdot$ and $\mathbf{A}^T \cdot$.

# Answer
> 0 votes
One possible approach would be to use stochastic gradient descent. This will be memory-efficient, as you desired. In particular, in each iteration we randomly pick an index $i$, then update $x$ based on the gradient of the function $f\_i(x) = \\| A\_i x - b\_i \\|\_1$, and repeat many times. Each iteration only requires access to a single matrix $A\_i$ at a time.

---
Tags: optimization, linear-algebra
---


# Question
Title: Is the language of words that contain a square regular or context-free?
$ L = \\{w \in\\{a,b\\}^{\*} : \exists\_{x,y,z} , w=xyyz \wedge y \neq \epsilon \\}$

I have a problem with this exercise. I need to determine if this language is regular, context-free or not both and prove. The word itself $ww$ above the alphabet $a, b$ is not context-free, but here we have $(a + b) ^ {\*}$ before and after, and it changes a lot, I think.

Is it possible to describe this language with a regular expression? For example $$(a + b) ^ {\*} (aa + bb + abab + baba) (a + b) ^ {\*}$$ So is the language regular?

# Answer
> 3 votes
A word is *square-free* if it contains no non-empty sub word of the form $y^2$. Your language consists of all words over $\\{a,b\\}$ which are *not* square-free. It is not difficult to enumerate (using exhaustive search) *all* square-free words over $\\{a,b\\}$: $$ \epsilon, a, b, ab, ba, aba, bab. $$ Since this list is finite, the language of square-free words over $\\{a,b\\}$ is trivially regular, and so is its complement.

In contrast, the language of square-free words over $\\{a,b,c\\}$ is *not* regular. This follows from the existence of an infinite square-free word $w$, which can be obtained from the Thue–Morse sequence.

Indeed, I claim that the set of prefixes of $w$ is pairwise inequivalent modulo your language. To see this, let $x,y$ be two such prefixes, say $x$ is a prefix of $y$. Then $y = xz$, and so $xz$ is square-free while $yz = xz^2$ isn’t.

Alternatively, we can apply the pumping lemma to the language of all square-free words over $\\{a,b,c\\}$. If the pumping length is $n$, take the prefix of $w$ of length $n$, and pump it up so that it contains a square. Similarly, since the Thue–Morse sequence is an infinite binary cube-free sequence, the language of cube-free words over $\\{a,b\\}$ is not regular.

The latter argument shows that the language of square-free words over $\\{a,b,c\\}$ and the language of cube-free words over $\\{a,b\\}$ are not context-free. This leaves the following questions open:

> 1. Is the language of non-square-free words over $\\{a,b,c\\}$ context-free?
> 2. Is the language of non-cube-free words over $\\{a,b\\}$ context-free?

# Answer
> 1 votes
The language is regular for the reason you stated, and the regex you gave is also correct.

Since the language allows any prefix and any postfix, the only requirement is to have a duplicate substring inside the language.

For this reason, any word containing "aa" or "bb" is in the language. Any word with neither aa nor bb is either of the form "abab..." or "baba...". For words of length \>= 4 the substring "ab" or "ba" occurs twice consecutively in the word, so the word is in the language.

---
Tags: regular-languages, context-free, formal-grammars, regular-expressions, pumping-lemma
---


# Question
Title: Why databases make the distinction between basic logical operations and functions
It just occurred to me that things like "greater than or equal to" and other "logical operators" are also just simple functions, such as `gte(a, b) == a >= b`. This makes me wonder why these are treated as "special" in databases and why they are not just functions like SQL functions. Wondering if there is some advantage to treating them differently like they do.

# Answer
Is this q specific to ~~databases~~ DBMS's/query languages, or to SQL? (I think you don't mean "databases": they're artefacts that hold data.) In all programming languages, operators are just functions written infix, aren't they? In programming languages that allow user-defined operators (like Haskell) that's explicitly syntactic sugar: you can define some operator as equivalent to a function; then you can use the operator infix.

The SQL aggregate functions like `SUM( ), COUNT( )` are not really functions in the same way as say `SIN( )`, because aggregate functions need all sorts of syntax around them such as `GROUP BY`.

Re "logical operators" in SQL like `AND`, `OR`, `NOT`, `[NOT] EXISTS` (that is a good question): their appearing in `WHERE` clauses is more syntactic, like aggregate functions, than merely being sugar for a function.

Let's start by washing away SQL thinking, and look at Codd's original Relational Algebra.

The RA relational operators are "closed over relations". That is, they take relations as arguments and return relations as results. That means those operators are orthogonal to the types of the values in attributes. (They do require we can test values for equality, as needed for Natural Join, for example.)

An operation like greater-than is 'domain specific'. That is, we can test numbers or strings or dates for greater-than; but we can't test images or sounds or other exotica we might want to hold in the database.

Similarly arithmetic is domain specific: you can't multiply two strings.

Coming back to "logical operators", we need to distinguish: if your attributes are holding Boolean values (or integer 1 vs 0, treated as Booleans), then operations on them that return Booleans are also domain specific: you can't `AND` strings.

OTOH the Relational Operators do correspond to logical operators (see Codd's 1972 paper on 'relational completeness' of the RA operators: 'complete' means can express all logical operations over relations considered as sets of axioms).

But RA operators do not operate on Booleans, returning Booleans. They operate on relations (sets of axioms) returning relations (sets of consequences).

There is a crossover (I'll do this in SQL, for fear you won't follow the RA):

```
SELECT DISTINCT * FROM S
WHERE City = 'London' AND Status = 10 ;

```

The `AND` in there can be equivalently expressed:

```
( SELECT DISTINCT * FROM S WHERE City = 'London')
INTERSECT
( SELECT DISTINCT * FROM S WHERE Status = 10) ;

```

Similarly `OR` in a `WHERE` can be expressed using `UNION`; `AND NOT` can be expressed using `EXCEPT` (if your SQL supports it).

The execution engine/query plan may well take advantage of those equivalences: if the database has indexes over `City` and `Status`, it's going to be more efficient to stream rows from the database using those indexes separately, then intersect the two streams, as opposed to a full table scan looking for rows matching both tests.

BTW `INTERSECT` is just a special case of Natural Join.

The equivalences go deeper. Imagine I have a way in SQL to write a table literal, then that above query could be

```
SELECT DISTINCT *
FROM S
NATURAL JOIN (TABLE (ROW( City 'London')))
NATURAL JOIN (TABLE (ROW( Status 10)))

```

`NATURAL JOIN` corresponds to logical `AND` over the sets of axioms (facts) represented by rows held in a table. Natural Join is more flexible than `INTERSECT`: the tables aren't required to have the same set of columns. It's an accident of history that SQL `INTERSECT` must appear as an operator between `SELECT` clauses; whereas `NATURAL JOIN` must appear within a `FROM` phrase as an operator between tables (which might be sub-`SELECT`s).
> 1 votes

# Answer
Database indices are typically binary search trees, meaning you can do range queries on them very efficiently. If you handed the database the \>= relation as a black box, on the other hand, it would have to iterate over every single record in the table performing the check.
> 2 votes

---
Tags: database-theory
---


# Question
Title: When to use Context-(in)Sensitive Inter-procedural Data Flow Analysis
I've been exploring the differences between `Context Sensitive Analysis` (CSA) and `Context Insensitive Analysis` (CIA), members of inter-procedural static analysis. The problem I'm coming up against is when to use one over the other.

Namely, suppose the following context:

The input program is in *Static Single Assignment* form. We have a machine that has no memory hierarchy. All it can do is store things in registers. We want host languages to support functions, including non-tail recursion. Which is to imply, when we call a function, we need to save all variables live across the function into registers and then calculate space requirements to see if we have enough registers to execution the function.

To do so, we need to use both CIA and CSA. Though I'm not entirely sure *why* that is the case. I've speculated a few ideas:

1. reaching definitions require a tighter bound,
2. invalid paths through recursion could ruin analysis,
3. there is some dark magic here that I'm unaware of.

But ultimately, given the context, I'm not sure why we need both CSA and CIA to compute space requirements across function calls.

# Answer
It's a tradeoff between accuracy vs running time. CSA often provides more accurate (more precise) results than CIA; but it takes longer. There's no hard-and-fast rule about when you must use one or the other; rather, you can use either, and you choose where you want to live on that tradeoff.
> 2 votes

# Answer
Registers are different from memory in that you only have an absolute addressing mode, no indirect or relative addressing modes. They are also a finite resource in a way that can't be avoided (memory is also a finite resource, but compilers can often pretend that it is infinite and rely on the O.S. to kill the program if we run out of memory).

If you didn't have recursion (or only had tail recursion). You could do a CIA of every function to determine the maximum number of registers it required (other than for function calls) and then assign each function a different non-overlapping range of registers for every one of its internal variables.

But (a) that would be incredibly suboptimal because there will be many functions that are never live simultaneously (thus could be assigned overlapping ranges), and (b) you do have recursion.
> 2 votes

---
Tags: compilers, data-flow-analysis, static-analysis
---


# Question
Title: "Functional dependencies" with cardinality constraints
Let us write $\\{ A\_1, \ldots, A\_k\\} \rightrightarrows^n \\{B\_1, \ldots, B\_m\\}$ for a relation $R$ if for all $\langle a\_1, \ldots, a\_k\rangle$ we have $\left\lvert \pi\_{B\_1, \ldots, B\_m} \sigma\_{\bigwedge\_{i = 1}^k A\_i = a\_i} R\right\rvert \le n$ (and $A\_i$, $B\_j$ are attributes from the schema of $R$), i.e, for any choice of values for the attributes $A\_i$ at most $n$ corresponding tuples of values for $B\_j$ can be found in $R$. Then $\\{A\_1, \ldots, A\_k\\} \rightrightarrows^1 \\{B\_1, \ldots, B\_m\\}$ is just the functional dependency $\\{A\_1, \ldots, A\_k\\} \rightarrow \\{B\_1, \ldots, B\_m\\}$, and $\emptyset \rightrightarrows^n \\{B\_1, \ldots, B\_m\\}$ is an upper bound on the number of possible $B\_j$-tuples occurring in $R$ (regardless of any selection).

One may come up with a bunch of possible inference rules similar to Armstrong's axioms, for example

* reflexivity: $\mathcal{A}' \subseteq \mathcal{A} \implies \mathcal{A} \rightrightarrows^1 \mathcal{A}'$,
* augmentation: $\mathcal{A} \rightrightarrows^{n} \mathcal{B} \implies \mathcal{A} \cup \mathcal{C} \rightrightarrows^{n} \mathcal{B} \cup \mathcal{C}$,
* transitivity: $\mathcal{A} \rightrightarrows^{n\_1} \mathcal{B}$, $\mathcal{B} \rightrightarrows^{n\_2} \mathcal{C} \implies \mathcal{A} \rightrightarrows^{n\_1 n\_2} \mathcal{C}$,
* decomposition: $\mathcal{A} \rightrightarrows^{n} \mathcal{B} \cup \mathcal{C} \implies \mathcal{A} \rightrightarrows^{n} \mathcal{B}$, $\mathcal{A} \rightrightarrows^{n} \mathcal{C}$,
* composition: $\mathcal{A}\_1 \rightrightarrows^{n\_1} \mathcal{B}\_1$, $\mathcal{A}\_2 \rightrightarrows^{n\_2} \mathcal{B}\_2 \implies \mathcal{A}\_1 \cup \mathcal{A}\_2 \rightrightarrows^{n\_1 n\_2} \mathcal{B}\_1 \cup \mathcal{B}\_2$.

Indeed, by setting $n = n\_1 = n\_2 = 1$, we obtain Armstrong's axioms.

Let $\Sigma = \\{\mathcal{A}\_i \rightrightarrows^{n\_i} \mathcal{B}\_i\\}\_{i = 1}^N$ be a set of such "cardinality constraints". Again following the conventions from functional dependencies, let us write $\Sigma \vDash \mathcal{A} \rightrightarrows^n \mathcal{B}$ if $\mathcal{A} \rightrightarrows^n \mathcal{B}$ holds in every relation $R$ where all constraints in $\Sigma$ hold. Let $\min\_\Sigma(\mathcal{A}, \mathcal{B})$ be the smallest $n$ such that we have $\Sigma \vDash \mathcal{A} \rightrightarrows^n \mathcal{B}$. How can we compute (or bound) $\min\_\Sigma(\mathcal{A}, \mathcal{B})$? Is there a way to minimize $\Sigma$ and obtain (the smallest) $\Gamma$ such that $\min\_\Gamma(\mathcal{A}, \mathcal{B}) = \min\_\Sigma(\mathcal{A}, \mathcal{B})$ for all sets of attributes $\mathcal{A}$, $\mathcal{B}$?

I'd be interested in references or algorithms regarding the constraints defined above. Have they been studied? What is the standard terminology or notation?

# Answer
After searching around for paper some more (unfortunately, I found nothing in Ling Liu, M. Tamer Özsu eds. Encyclopedia of Database Systems), I managed to find out that these dependencies are called *numerical dependencies*. In particular, standard notation for my $\mathcal{A} \rightrightarrows^k \mathcal{B}$ is $\mathcal{A} \xrightarrow{k} \mathcal{B}$, which is also referred to as a $k$-dependency.

Unfortunately, they are not finitely axiomatizable:

John Grant and Jack Minker (1985). *Normalization and axiomatization for numerical dependencies*. In: Inf. Control **65**(1), pp. 1-17. https://doi.org/10.1016/S0019-9958(85)80017-6

The entailment problem is in EXPSPACE. However, there is a sound branch-and-bound algorithm that may be used:

Paolo Ciaccia, Matteo Golfarelli and Stefano Rizzi (2013). *Efficient derivation of numerical dependencies*. In: Inf. Syst. **38**(3) pp. 410-429. https://doi.org/10.1016/j.is.2012.07.007

A general survey of the generalization of functional dependencies is

Loredana Caruccio, Vincenzo Deufemia and Giuseppe Polese (2016). *Relaxed Functional Dependencies—A Survey of Approaches*. In: IEEE Tran. Knowl. Data Eng. **28**(1) pp. 147-165. https://doi.org/10.1109/TKDE.2015.2472010

An extension of numerical dependencies is $\mathit{CFD}^c$, conditional functional dependencies with cardinality constraints. This paper defines them, and gives some algorithms for satisfiability and entailment:

Wenguang Chen, Wenfei Fan and Shuai Ma (2009). *Incorporating cardinality constraints and synonym rules into conditional functional dependencies*. In: Inf. Process. Lett. **109**(14) pp. 783-789. https://doi.org/10.1016/j.ipl.2009.03.021
> 2 votes

---
Tags: reference-request, relational-algebra, functional-dependencies
---


title: Pumping Lemma vs Myhill-Nerode

text:
# Question
Title: Pumping Lemma vs Myhill-Nerode
I was searching for a difference on both ways of proving that a language is not regular but I didn't came up with much.

Let us take the following as an example:

$$ L = \\{ a^n b^n \mid n \ge 0\\} $$

Could someone tell me the differences between both theories and how to prove the language I brought is not regular according to each approach.

I know this is a basic example – that is the reason I chose it, make it simple rather than make it harder.

Thank you in advance!

# Answer
The main difference between the pumping lemma and Myhill–Nerode theory is that the non-regularity criterion of Myhill–Nerode theory *always* holds for non-regular languages, whereas the same isn't true for the pumping lemma.

In other words, both the pumping lemma and Myhill–Nerode theory give you conditions which imply that a given language is not regular. If a language is not regular, then it is guaranteed that the Myhill–Nerode criterion will hold, but it is not guaranteed that the pumping lemma condition will hold. You can see an example in this question.

There are extensions of the pumping lemma which are guaranteed to work:

1. Jaffe's pumping lemma: a language $L$ is regular iff all long enough words $w \in L$ can be decomposed as $w = xyz$, with $y \neq \epsilon$, such that for all $i \geq 0$ and all words $v$, $$xyzv \in L \text{ iff } xy^izv \in L.$$
2. Block pumping lemma: a language $L$ is regular iff there exists a constant $k$ such that for all words $u,v,w\_1,\ldots,w\_k$ there are $1 \leq i \< j \leq k$ such that for all $\ell \geq 0$, $$ uw\_1\ldots w\_k v \in L \text{ iff } u w\_1 \ldots w\_i (w\_{i+1} \ldots w\_j)^\ell w\_{j+1} \ldots w\_k v \in L. $$

In both cases, it in fact suffices to allow only $i = 0$.

(This material is from *Handbook of Formal Languages, Volume 1: Word, Language, Grammar*, Chapter 4 by Sheng Yu, Section 4.1.)
> 0 votes

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


# Question
Title: Why can't exhaustive search parsing stop after |w| + 1 derivations?
If my grammar does not have productions of the form $A\rightarrow\lambda$ and $A\rightarrow B$ for some variables $A$ and $B$ then I know that each step in the derivation must involve an increase in the sentential length. Therefore if I do an exhaustive search for some word $w$ then I know I can stop searching after $|w|$ derivations.

My question is why then do textbooks assert that we can stop after $2|w|$ derivations instead? Yes, I agree that this is true, but wouldn't it be easier just to stop at $|w|+1$ and above? What am I missing for this condition?

# Answer
> 2 votes
You increase the length of the *sequential* form with each derivation, but you also need to convert non-terminals to terminals.

Think of a grammar in Chomsky normal form. For each word symbol, you need to create a non-terminal first (and you create *only* one per derivation!) and then convert it into a terminal. That's $2|w| \pm 1$ derivations right there.

Yes, CNF is a little wasteful this way, but finding short derivations isn't its purpose, isn't it?

# Answer
> 1 votes
Each derivation step replaces applies a production to one non-terminal. After $|w|-1$ derivation steps you have a sentential form of length $|w|$. You need one derivation to replace each non-terminal with its corresponding terminal. So the total number of steps is $2|w|-1$.

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


# Question
Title: Path of maximum value with bounded cost in DAG
Consider a Directed Acyclic Graph in which every node has a value and a cost and edges do not have any weight. I need to find a path containing nodes such that sum of values of these nodes is maximized, but sum of cost over all these nodes must be at most C.

I am thinking of some modification of Dijkstra's algorithm. Any ideas? Is there any standard algorithm for this?

# Answer
Consider a SUBSET SUM instance with weights $w\_1,\ldots,w\_n$ and target $C$. We create an instance of your problem, with the same value of $C$. There are $n+1$ nodes $v\_1,\ldots,v\_n$, where node $v\_i$ has cost and weight $w\_i$. There is an edge from $v\_i$ to $v\_j$ iff $i \< j$.

Any directed path in this DAG corresponds to a subset of the weights $w\_1,\ldots,w\_n$. You are thus looking for a subset of the weights with maximal sum under the constraint that the sum is at most $C$. Thus the solution to your problem is $C$ iff the SUBSET SUM instance is a Yes instance.
> 3 votes

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


title: Replace queries on string

text:
# Question
Title: Replace queries on string
Let's define a replace query on some string $s$.

Consider a string $s$ of length $n$ over alphabet $C = \\{ c\_{0}, c\_{1}, c\_{2}, \dots, c\_{k}\\}$. Also consider $l, r \in \\{0, 1, 2, \dots, n - 1\\}, l \geq r; \quad c\_{i}, c\_{j} \in C$. The replace query $\left(l, r, c\_{i}, c\_{j}\right)$ replaces all occurrences of $c\_{i}$ with $c\_{j}$ on $\[l; r\]$ segment of $s$.

There is a problem. Given string $s$ and $m$ replace queries $\left(l, r, c\_{i}, c\_{j}\right)$, perform them on $s$ and print the result.

Originally, the problem has low bounds on string length and queries count: $1 \leq n, m \leq 100$. The bruteforce solution seems to have $O(nm)$ complexity. But what if we increase the upper bound on $n$ and $m$ to, for example, $10^{10}$ or even $10^{100}$? Is there solution with better complexity?

# Answer
> 2 votes
The following approach will solve the problem in $O(km^2\log m + n)$ time, which is only better than $O(mn)$ if $n$ is extremely large compared to $m$ and $k$ is relatively small. **My hope is that someone can come up with a refinement of my "caching mechanism" that decreases the dependence on $m$.**

## The view from one position in the string

From the point of view of a particular position in the string, replace queries appear as a sequence of instructions of the form "If you are an `x`, change to a `y`", each of which occurs at a particular *time*. The only instructions that are "visible" to a particular position in the string are those whose $\[l, r\]$ range includes that position. The timestamp of an instruction is simply its position within the list of all replace queries: timestamps are therefore unique.

The idea is to build a directed graph that represents these time-stamped instructions as seen by the "current" string position (initially, position 1). The vertices in this graph are the characters $c\_1, \dots, c\_k$; each directed edge $uv$ represents the instruction "If you are a $u$, change to a $v$", and is labelled with a timestamp, which is the position where it occurs within the list of all replace queries (starting from 1). *Note that an edge can be present multiple times, with different timestamps.* To find the "final" character at the current position, we start at time 0 at the vertex corresponding to the initial character at this position, and repeat the following steps as long as we can:

* Choose the outgoing edge from the current vertex with the smallest timestamp that is greater than the current time
* Move to the endpoint of this edge
* Update the current time to the timestamp on this edge

The first step, choosing the "next" instruction, can be performed in $O(\log m)$ time if we use an adjacency-list graph representation that uses a self-balancing binary tree keyed by the timestamp to hold the set of outgoing edges for each vertex. In the worst case, all $m$ instructions are visible to the current string position, so a single traversal therefore takes at most $O(m\log m)$ time.

## Maintaining the instruction graph

Initially, we build this graph for position 1. After determining the final character at that position, we update the graph as we move left-to-right through the string, processing each position in turn.

The $t$-th replace query $(l, r, c\_i, c\_j)$ requires 2 changes to the graph: An edge $c\_ic\_j$ with timestamp $t$ needs to be inserted when we reach position $l$, and that same edge needs to be removed when we reach position $r+1$. Each of these changes takes $O(\log m)$ time using the graph representation described earlier.

## Caching

The algorithm described so far performs the graph traversal at each of the $n$ string positions, so it takes $O(nm\log m)$ time -- worse than the original! But all is not in vain.

Notice that for $m$ queries, there are only $2m$ times at which the graph changes -- so if we cache the final destination character for each distinct initial character $c\_1, \dots, c\_k$ whenever the graph changes, we can simply look up the answer in $O(1)$ time for each position until we hit the next query boundary. This way, the full traversal need be performed at most once per distinct character after each change to the graph, for $O(km^2\log m + n)$ time. (This approach -- "flush the entire cache as soon as the graph changes" -- is a very simple caching mechanism. It may be that more sophisticated caching techniques can drop the time complexity further, by avoiding the recomputation of some cached final destination characters that do not change.)

---
Tags: data-structures, strings
---


# Question
Title: DFA for $L = \{y \in (a+b)^* \mid ||y|_a - |y|_b| \leq 10 \}$
$L = \\{y \in (a+b)^\* \mid ||y|\_a - |y|\_b| \leq 10 \\}$

Any idea? I have problem with this kind of task.

# Answer
I am afraid that you cannot construct a DFA for $L$ since it is not regular.

Intuitively, a finite automaton cannot even make sure the number of $a$'s and the number of $b$'s are the same since its finite memory cannot keep track of the number of the $a$'s in the initial part of $a^nb^n$ when $n$ become sufficient large.

How to prove that language is not regular?

* Use the pumping lemma. For example, what about a word that barely satisfies the condition such as $a^pb^{p+10}$?
* Use Myhill–Nerode theorem. How about elements $a^n$ for all $n$? Does any of two of them belong to the same Myhill–Nerode class?

---

**Exercise 1.** Let $\lfloor x\rfloor\_a$ be the minimum number of consecutive $a$'s in $x$ and $\lceil x\rceil\_a$ be the maximum number of consecutive $a$'s in $x$, where $x\in\\{a,b\\}^\*$ contains $a$. $\lfloor x\rfloor\_a=\lceil x\rceil\_a=0$ if $x$ does not contain $a$. Is the following language regular? $$L = \\{x \in \\{a, b\\}^\* \mid \lceil x\rceil\_a - \lfloor x\rfloor\_a \le 10 \\}$$ **Exercise 2.** Is the following language regular? $$L = \\{xy \mid x,y\in \\{a,b\\}^\* \wedge ||x|\_a - |y|\_a| \leq 10 \\}$$
> 3 votes

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


# Question
Title: Understanding arguments in Haskell type classes and instances
I am trying to understand a Haskell class declaration and instance from a paper. I am trying to understand the class declaration:

```
class (Surfaces v o, Paths a b (v o)) => Vehicles v o a b

```

My current understanding is that the first occurance of types "v o" in the `Vehicles` context seems to refer to two distinct data types. I assume that it is the same for the "v o" on the right of `=>`.

Question 1

Is my understanding correct? Does the bracketed "(v o)" in the `Vehicles` context refer a type constructor and its argument, rather than two independent types?

Question 2:

Is the instance OK? Why do I need `FlexibleInstances`

```
 instance Vehicles Boat Person Route (Water Source)

```

I apologize for the level of detail, but I believe that the context is important to my question. Regards, Pat

```
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
data Person = Person deriving Show
data House a = House a  deriving Show
data Boat a  = Boat a deriving Show
data Route a b = Route a b deriving Show
data Source = Source deriving Show
data Destination = Destination deriving Show
data Water a = Water a deriving Show
data Land = Land deriving Show

-- The three top level classes are constructor classes, indicated by the signatures of the methods (not the class header).
-- The kinds in the class headers have kinds * and *->*
-- "Containers a b" stands for all container types "a" holding things of type "b".
class Containers a b where
 insert :: b -> a b -> a b
 remove :: b -> a b -> a b
 whatsIn :: a b -> [b]

-- Type "a" is the type of  surface
-- Type "b" is the type object on the surface e.g. boat is on water.
class Surfaces a b where
 put :: b -> a b -> a b
 takeOff :: b -> a b -> a b
 whatsOn :: a b -> [b]

-- The path class represents motion
-- Type "c" represents the moving object e.g Boat.
-- Type "a" route
-- Type "b" origin and destination place
class Paths a b c where
 move :: c -> a b c -> a b c
 origin, destination :: a b c -> b
 whereIs :: a b c -> c -> b

class People p
class HeavyLoads l
class Surfaces w o => WaterBodies w o
class Containers h o => Houses h o

-- The types "v o" in the Vehicles the context seems to refer to two distinct data types.
-- I assume that it is the same for the "v o" on the right of =>
-- But "(v o)" in the Vehicles the context seems to refer a type constructor and its argument??.
-- Vehicles are derived from surfaces (affording to ride on the vehicle) and paths (affording motion).
-- Vehicles type class has  parameters for
--  the type "o" of the transported object
--  the type "a" of the path,
--  the type "b" of the origin and destination places.
--  "o" has kind *, "a" has kind *->*->*,  "v" has kind *->*
class (Surfaces v o, Paths a b (v o)) => Vehicles v o a b

instance Surfaces Boat Person
instance WaterBodies Boat Person  -- Boats carrying people on water
instance Paths Route (Water Source) (Boat Person) -- boat moving on water carrying people
instance Vehicles Boat Person Route (Water Source)  -- Boat as a vehicle

```

# Answer
> Question 1
>
> Does the bracketed "(v o)" in the Vehicles context refer a type constructor and its argument, rather than two independent types?

In the constraint `Surfaces v o`, `v` and `o` are two separate type arguments to class `Surfaces`. Constraint `Paths a b (v o)` has three arguments: `a`, `b`, `(v o)`. The third is `v` applied to `o`, so we can infer parameter `v` to class `Vehicles` is a type constructor, kind `* -> *`.

I'm not sure what you're trying to say by "independent types": `v`, `o`, are distinct parameters to `Vehicles`. The constraints are telling us we can't freely choose just any types for `a`, `b`, `v`, `o`, so they're all inter-dependent.

> Question 2:
>
> Is the instance OK? Why do I need `FlexibleInstances`
>
> ```
>    instance Vehicles Boat Person Route (Water Source)
>
> ```

Firstly, class `Vehicles` needs `FlexibleContexts`. That's because not all of the constraints are of the form class name followed by bare type variables. Argument `(v o)` is the culprit.

Similarly for that instance, not all the type arguments are plain type constructors or constructors followed by bare type vars. Argument `(Water Source)` is the culprit. If it were `(Water b)`, that wouldn't need `FlexibleInstances`.
> 1 votes

---
Tags: haskell
---


# Question
Title: Is the reverse of a closed under operation maintainable?
I'm looking at the following question from this handout:

> The class of decidable languages is closed under union

My question is, does this hold in reverse? Is there a phrase for this? Basically, if $L\_1 ∪ L\_2$ is decidable would $L\_1$ and $L\_2$ be decidable as well?

I believe it does, by making one machine $M$ to emulate both on any given input string and have the following:

```
Save a copy of input somewhere (multitape)
Run M1
    If it accepts, accept
Reset the tape using copy
Run M2
    If it accepts, accept
Both machines have rejected, so reject

```

Does this work? If so, would this also apply in the case of intersection as well?

# Answer
No, if $L\_1\cup L\_2$ is decidable $L\_1$ and $L\_2$ are not necessarily decidable.

Here's an example.

$$\begin{align} L\_1 &= \text{any language that is not decidable.}\\ L\_2 &= \Sigma^\*\setminus L\_1. \end{align}$$ $L\_1\cup L\_2$ is $\Sigma^\*$, which is decidable. However, $L\_1$ is not decidable. In fact, $L\_2$ is not decidable, either.

---

The proof given in the preformatted block of the question is a proof for the original proposition, "if $L\_1$ and $L\_2$ are decidable, then $L\_1\cup L\_2$ is decidable". It is not a proof for its converse proposition.

To prove its converse proposition, all you can assume is a Turing machines that decides $L\_1\cup L\_2$. There is no way that you can construct a Turing machine that can decide $L\_1$ from that machine.

---

Intuitively, one condition cannot imply two other conditions. That is, "$L\_1 \cup L\_2$ is decidable" cannot imply both "$L\_1$ is decidable" and "$L\_2$ is decidable"

Here are a few related exercises.

**Exercise 1.** Does $L\_1 \cup L\_2$ is regular imply $L\_1$ is regular and $L\_2$ is regular?

**Exercise 2.** Does $L\_1 \cup L\_2$ is context-free imply $L\_1$ is context-free and $L\_2$ is context-free?

**Exercise 3.** Does $L\_1 \cup L\_2$ is recursively enumerable imply $L\_1$ is recursively enumerable and $L\_2$ is recursively enumerable?

**Exercise 4.** Raise a question similar to the above question.

**Exercise 5.** If you know that $L\_1\cup L\_2$ and $L\_1$ are both decidable, does that imply $L\_2$ is decidable?

---

The case with intersection is the same. Please check question if $L\_1$ and $L\_2$ are languages over the same alphabet and $L\_1\cup L\_2$ is context free, at least one of them must be context free, its answer and its exercises.
> 4 votes

# Answer
No. $\Sigma^\*\cup L$ and $\emptyset\cap L$ are both decidable for every language $L$, whether $L$ is decidable or not.

Your proof shows that, if $L\_1$ and $L\_2$ are decidable, then so $L\_1\cup L\_2$. You started by assuming that $L\_1$ and $L\_2$ are decided by machines $M\_1$ and $M\_2$, and then you built a machine that decides $L\_1\cup L\_2$. But you were supposed to be proving the converse! (Which you can't, because it's not true.)
> 2 votes

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


title: Sorting on non-linear topology

text:
# Question
Title: Sorting on non-linear topology
**Disclaimer.** What I'm going to ask about below may seem to be "Topological sorting". To my understanding, it is not. The latter runs in linear time, while I'm looking for a modification of the regular sort, which is at $N\log N$.

**Remark.** I'm doing the sort in the reverse order, to use the analogy with heights and masses.

Let us reformulate the sorting problem in the following way. Let us introduce two sets:

1. A set of sites (positions) $s\_a,\\,a=1..N$. Those are assigned certain 'heights' $h\[s\_a\]$, which in the case of usual sorting can be simply $h\[s\_a\]=a$.
2. A set of objects (numbers) $x\_i,\\,i=1..N$ which are assigned numerical values $m\[x\_i\]$ (according to which the sorting will be performed). In the case of usual sorting, $m\[x\_i\]$ are the numbers to be sorted.

The problem of sorting can be viewed as assigning to each object $x\_i$ a site $s\_a$ in such a way that for all assignments $\\{x\_i\to s\_a; x\_j\to s\_b\\}$: $$ h\[s\_a\] \> h\[s\_b\] \Longrightarrow m\[x\_i\]\leq m\[x\_j\] $$

The physical visualization of this problem is a vertical stack of massive balls. Sorting them is equivalent to arranging them in such a way that heavier ones have lower height.

I first wanted to generalize the problem to "higher dimensions", i.e. to assume that the balls can stay in a $2$-dimensional grid, in a bucket, etc. However, I realized that from the computational point of view these settings are equivalent. In other words, whether we have a $2d$ grid with $nm$ balls in each row or a box with $n\times m$ balls in each layer makes no difference.

So, I decided to generalize the problem to an arbitrary topology (which can be reduced to the $2$-dimensional problem actually).

1. A set of sites (positions) $s\_a,\\,a=1..N$. Those are assigned certain 'heights' $h\[s\_a\]$. Repetitions are allowed: $h\[s\_a\]=h\[s\_b\]$ for $a\neq b$ is OK.
2. A set of objects (numbers) $x\_i,\\,i=1..N$ which are assigned numerical values $m\[x\_i\]$.

Again, we want to assign to each object a site in accordance with the same requirement as above.

Clearly, the brute-force solution for the most general set of 'heights' and 'masses' runs in $N \log N$. One simply sorts the objects according to their 'mass', and then fills the sites, starting from the 'highest' or the 'lowest' one.

**Question.** Has there been done any research for some particular cases? Clearly, if all the 'heights' are equal, the problem is trivial (which, I guess, means that it is solved in linear time). The first thing coming to my mind would be considering the case of "levels of same lengths", $$ h\[s\_a\]=\lceil a/r\rceil,\\,r\in\mathbb{N} $$ I would actually expect that this can be done faster than $N\log N$ (I'd assume that $r$ should enter the answer).

# Answer
If there are $k$ distinct heights, you can sort in $O(n \log k)$ time using a heap or balanced binary tree. Even better, you can sort with expected time $O(n + k \log k)$, if you use a hashtable.

This leads to a solution to your problem with the corresponding complexity.
> 2 votes

---
Tags: graphs, sorting, search-algorithms
---


# Question
Title: Lexicographically smallest down-right path in matrix
Here is the problem which I thought was simple dynamic programming, which is however not the case.

Given an $N \times M$ matrix of numbers from 1 to $NM$ (each number occurs only once), find a path from top left to right bottom while moving right or down only. If we sort all values visited in this path it should be lexicographically smallest.

I thought smallest sum path will be the answer, but it need not be true.

# Answer
> 3 votes
Every path must hit the top left and bottom right corners. Let $x$ be the minimal element among the remaining $NM-2$ elements. The lexicographically smallest path must go through $x$. If $x$ is at address $(i,j)$, this decomposes the original problem to two problems of the same form: one on an $i \times j$ matrix, and the other on an $(N-i+1) \times (M-j+1)$ matrix. (This requires a proof, but intuitively seems correct.)

To implement this algorithm efficiently, we need an efficient data structure for the two-dimensional range minimum query problem. Brodal, Davoodi and Rao give, in their paper On Space Efficient Two Dimensional Range Minimum Data Structures, a data structure that answers queries in $O(1)$ time, after $O(NM)$ preprocessing.

Actually, we need to find the minimum of a rectangle without two of its corners, but this domain can be written as the union of three rectangles, so such a query can also be answered in constant time.

Using such a data structure, we obtain an algorithm running in linear time $O(NM)$.

In fact, it suffices to use a much simpler data structure supporting *one-dimensional* range minimum queries; see Fischer, Optimal Succinctness for Range Minimum Queries for appropriate references. Suppose that $N \leq M$. Using a range minimum query data structure on each row, we can answer a two-dimensional range minimum query in time $O(N)$. Since the algorithm above makes only $O(N+M) = O(M)$ such queries, the overall complexity is still $O(NM)$.

---
Tags: algorithms, dynamic-programming, lexical-analysis, matrix
---


# Question
Title: Regular expression for binary words with 1 in the middle
> Given the alphabet $\\{0,1\\}$, generate a regular expression with the following language: $$ \\{w\in \Sigma^\* \mid w \text{ has odd length and its middle symbol is }1\\}. $$

I'm having trouble finding a solution for this regular expression. I think it's impossible because you need to have an even amount of 1's and 0's on both sides of the middle 1. You also would need to have the same amount of 1's and 0's on both sides. Since a regular expression has limited memory, would that make this regular expression impossible?

# Answer
> 3 votes
The intersection of your language with $0^\*10^\*$ is $\\{ 0^n 1 0^n : n \geq 0 \\}$, which can be shown to be non-regular by reduction to the more well-known $\\{ a^n b^n : n \geq 0 \\}$. This shows that your language indeed isn't regular.

# Answer
> 3 votes
Yes, you are right that there is no regular expression for this language.

For the sake of contradiction, assume $L$ is regular with pumping length $p$. Consider the word $w=0^p1^{n+1}$. There must be $x,y,z \in \\{0,1\\}^\*$ such that $|xy|\<p$, $|y| \> 0$, $w=xyz$ and for all nonnegative integer $i$, $xy^iz \in L$.

Since $w$ starts with $p$ 0's and $xy$ is shorter than $p$, $y$ consist of $0$ only. Thus $xy^2z = 0^{n+|y|}1^{n+1} \not\in L$. This contradicts the assumption, which means $L$ is not regular.

The general intuition or heuristic here is that any particular regular expression cannot remember count that is arbitrarily large, although it can count to any finite constant.

---

Here is a couple of related exercises, where $\Sigma=\\{0,1\\}$.

**Exercise 1.** Is the following language regular? $$ \\{w\in \Sigma^\* \mid w \text{ has even length and its middle two symbols are 11 or 00}\\}. $$

**Exercise 2.** Is the following language regular? $$ \\{w\in \Sigma^\* \mid w \text{ has odd length and both of its endpoints are 1} \\}. $$

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