# Question
Title: How can we find the number of pairs of intersecting ranges on a circular number line?
I recently thought of and managed to solve this algorithmic problem:

On a infinite 1-dimensional number line, we have `N` ranges specified by two distinct integers `A` and `B`, such that all `A` and `B` are unique. Each pair of integers then represents the starting and ending points of a range on the number line. How many distinct pairs of ranges intersect?

^^ In this example, 4 distinct pairs of segments intersect.

Obviously, there is a `O(N^2)` brute-force solution: just test all possible pairs in `O(1)` time each. However, I also thought of a `O(NlogN)` sweep-line algorithm: treat every `A` as a "segment start event" and every `B` as a "segment end event". Then, keep a variable `curr_in_range` (originally 0) that stores the current number of segments that we currently see, and then iterate through the events in sorted order of their positions on the number line. Every time we add another segment, add `curr_in_range` to the answer (because this new segment will intersect with every other segment that we can see) and increment it as well. Every time we remove a segment, decrement `curr_in_range`. In the end, this gets us the correct answer.

Happy with this algorithm, I decided to tackle a slightly modified version of this problem: What if the number line is *circular*? As in, it has a specified length `L` such that the number line contains numbers in the range `[0, L)`? In this case, each range would still be specified by two distinct integers `A` and `B`, but let's just say the range is always *counterclockwise* starting from A and ending at B. Could we still find the number of pairs of sectors that intersect in less than `O(N^2)` time in this scenario?

Here's my thought process on this problem:

We should be able to use a very similar algorithm to the one described above. Completely copying it wouldn't work, though, because the sectors can have `B < A` when it crosses over 0. My idea was to initially have `curr_in_range` equal to the number of sectors that cross over 0 (instead of just it at 0 like we did in the above algorithm). Then, we could treat every sector as a "sector start event" and a "sector end event", and do the same process that we did.

However, after extensive analysis, I found why this approach doesn't work. This approach won't work because it *overcounts* some of the intersections, as sometimes two sectors can intersect in 2 places. This is where I'm stuck.

^^ Our sweep-line algorithm will count 2 distinct pairs that intersect, when there is actually only 1.

But besides this overcounting, I found that this current algorithm **isn't doing a single other thing wrong**. I coded a `O(N^2)` brute-force algorithm and tabulated all the distinct pairs that it found, and also tabulated the distinct pairs found for the current algorithm. For every randomly-generated test case, *these two tables were the same*. In other words, our current algorithm is correctly detecting every intersection there is to be detected, but it just happens to overcount some of them.

So, sorry for a really long post, but my final question is:

**Can someone come up with an algorithm that solves this problem? Is my thought process close to a solution or completely off?**

# Answer
### Summary

Interesting question.

Please check this program in Java that runs in $O(n\log n)$ time, where $n$ is the number of given ranges. The program uses sweep-line technique, once for counting intersecting pairs of ranges, and once for counting containing pairs of ranges together with Fenwick tree. Explanations follow.

### Reduce to the hard case

Here are the notations and assumptions for the ease of explanation.

* All numbers and variables are integers.
* The numbered circle of cardinality $L\ge2$ is the set of number $0, 1, \cdots, L-1$, where $L$ is considered to wrap around to $0$.
* A range $\[s,e\]$ with respect to $L$, where $0\le s\le e\lt L$, means
    + a non-wrapping range (a.k.a. an ordinary range) if $s\le e$, i.e., numbers $s, s+1,\cdots, e-1, e$;
    + a wrapping range otherwise, i.e,. numbers $s, s+1, \cdots, L-1, 0, 1, \cdots, e-1, e$.

Note every range contains at least one number. The non-wrapping range $\[0, L-1\]$ contains all the numbers. So does every wrapping range like $\[s,s-1\]$.

Suppose there are $n$ ranges. The question is how to compute the number of all unordered pairs of two intersecting ranges efficiently.

There are three cases for an unordered pair of two ranges.

* Both ranges are wrapping.
This is the easiest case since two wrapping ranges always intersect at $0$.
* Both ranges are non-wrapping.
This is the classical case. The total number of such intersecting pairs can be computed by the sweep-line (or, as I would call it, the sweep-point or sweep-event) algorithm, which runs in $O(n)$ time, as described in the question.
* One range is non-wrapping and the other is wrapping.
This is the new and hard case. One way to understand why this case may not be easy is j\_random\_hacker's illustration. How can we deal with this case?

### Transform to the containing pairs of non-wrapping pairs

Denote the non-wrapping ranges and the wrapping ranges in the given ranges by $\mathcal N$ and $\mathcal W$, respectively. Instead of counting the intersecting pairs between $\mathcal N$ and $\mathcal W$, we will use complementary counting, i.e., we will count the non-intersecting pairs between $\mathcal N$ and $\mathcal W$.

Given any range $r$, let $\overline r$ be the numbers among $0, 1, \cdots, L-1$ that are not in $r$, i.e., the complement of $r$ with respect to $\mathcal C$. Note that two ranges do NOT intersect iff the complement of either one contains the other.

Let $\overline{\mathcal W} = \\{\overline r\mid r\in\mathcal W\\}$. Then the number of non-intersecting pairs between $\mathcal N$ and $\mathcal W$ is the number of containing pairs between $\mathcal N$ and $\overline{\mathcal W}$. Here a containing pair means, naturally, two sets $a$ and $c$ such that $c$ contains $a$. The number we wanted, i.e., the number of all intersecting pairs of ranges between $\mathcal N$ and $\mathcal W$ is $|\mathcal N|\cdot|\mathcal W|$ minus that number of containing pairs.

More formally, we have $$\\#\\{(a, b) \mid a\in{\mathcal N}, b\in{\mathcal W}, a\cap b\not=\emptyset\\} = \\#{\mathcal N}\cdot\\#{\mathcal W} - \\#\\{(a, c) \mid a\in{\mathcal N}, c\in\overline{\mathcal W}, a\subseteq c\\}. $$

Here is a simple observation, the complement of a wrapping range is a non-wrapping range, except when the wrapping range is like $\[s,s-1\]$, whose complement is empty. Containing all numbers, a wrapping range like that intersects with every other range. It is easy to count all intersecting pairs that involve a wrapping range like that.

Let us assume there is no such wrapping range; if necessary, we can replace such a range with non-wrapping range $\[0, L-1\]$. The problem is reduced to counting the number of containing pairs between two sets of non-wrapping ranges.

### An algorithm that counts the number of containing pairs

Here is an algorithm that counts the number of containing pairs between two given sets of non-wrapping ranges, $\mathcal N$ and $\overline{\mathcal W}$. It is, basically, sweep-line technique together with Fenwick tree.

1. Let `containingPairCount = 0`.
2. Initialize a Fenwick tree (a.k.a. binary indexed tree) `ft` for an (implicit) interested array of length $L$, with all values 0 initially. The `e`-th element of the interested array will be the number of all ranges in $\overline{\mathcal W}$ so far that end at `e`.
3. Sort all ranges that are in either $\overline{\mathcal W}$ or $\mathcal N$ by the starting points, breaking ties by putting ranges in $\overline{\mathcal W}$ before ranges in $\mathcal N$. Breaking the remaining ties arbitrarily.
4. One by one process the sorted ranges. Let the current range be `[s,e]`.
    * If it comes from $\overline{\mathcal W}$, updates the Fenwick tree as if the `e`-th element of the interested array is increased by 1. This operation registers the current range as a candidate containing range that has started and will end at `e`.
    * If it comes from $\mathcal N$, add the sum of elements of indexes no smaller than `e` in the interested array to `containingPairCount`, by `containingPairCount += st.getSum(e, L-1)`.
5. Return `containingPairCount`.

**Proof of the algorithm**: `st.getSum(e, L-1)` is the number of all ranges in $\overline{\mathcal W}$ that contain the current non-wrapping range, since, thanks to the careful setup, we have processed all ranges in $\overline{\mathcal W}$ that start at or before the start of the current range, and only those ranges that end at or after the end of the current edge are counted. $\quad\checkmark$

The sorting of all ranges at step 3 takes $O(n\log n)$ time. At step 4, each range is processed with $O(\log n)$ time, thanks to the power of Fenwick tree. So the running time of this algorithm is $O(n\log n) + O(n \log n) = O(n\log n)$.

### Complexity analysis

The running time for other parts of the entire algorithm is $O(n\log n)$, which is spent mostly on counting the intersecting non-wrapping pairs. So, the running time of the entire algorithm is $O(n\log n) + O(n \log n) = O(n\log n)$.

---

<sub>The sections "Reduce to the hard case" and "transform to the containing pairs of non-wrapping pairs" follow D.W's answer roughly. </sub>
> 1 votes

# Answer
This is solvable in $O(n \log n)$ time, too, by considering the complement of the intervals that wrap around and using a suitable data structure.

There are two types of intervals that can appear on a cycle:

* Intervals that do not wrap around: e.g., $\[0.3,0.5\]$ does not wrap around. In general, this includes all intervals of the form $\[a,b\]$ with $0\le a \le b \le 1$.
* Intervals that wrap around: e.g., $\[0.8,0.1\]$ wraps around; it is equivalent to $\[0.8,1.1\]$ or $\[0.8,1\] \cup \[0,0.1\]$. In general, this includes all intervals of the form $\[b,a\]$ with $0\le a \< b \le 1$; each such interval is equivalent to $\[b,1\] \cup \[0,a\]$.

Let $A$ denote the set of intervals that do not wrap around, and $B$ the set of intervals that do wrap around. Also, let $\overline{B}$ denote the complements of the intervals in $B$, i.e., $\overline{B} = \\{\overline{b} \mid b \in B\\}$. For instance, the interval $\[0.8,0.1\]$ wraps around; its complement is $(0.1,0.8)$, which does not wrap around. It is easier to think about intervals that do not wrap around, and this decomposition will help us to deal only with intervals that do not wrap around.

Now, we will separately count the number of overlaps between (1) an interval in $A$ and an interval in $A$; (2) an interval in $A$ and an interval in $B$; (3) an interval in $B$ and an interval in $A$; and (4) an interval in $B$ and an interval in $B$. (1) can be counted with your sweepline algorithm, as we don't need to deal with wraparound. (4) can also be counted in the same way, as two intervals overlap iff their complements overlap. I will show below how to count (2); case (3) will then follow by symmetry. This covers all the cases, so it suffices to count up these four cases and sum them up.

Note that intervals $a \in A, b\in B$ overlap iff $a$ is not a subset of $\overline{b}$. So, it suffices to count the number of pairs $a \in A, \overline{b}\in \overline{B}$ where $a$ is a subset of $\overline{b}$; then you can subtract that from $|A| \cdot |B|$.

To do that, you can use the data structure in Data structure for interval subset queries. Store all the intervals $\overline{B}$ in the data structure. Then, for each $a \in A$, count the number of intervals in $\overline{B}$ that $a$ is a subset of. This can be done in $O(\log n)$ time per query interval $a$, for a total time of $O(n \log n)$.

Therefore, you can count each of the four cases in $O(n \log n)$ time, and thus compute the overall sum in $O(n \log n)$ time as well. I think. I encourage you to check my reasoning to make sure I haven't made any mistakes.
> 4 votes

# Answer
Not a solution, just an illustration of what I see as the core difficulty:

The instance on the left has 3 intersections, the one on the right only 2, but there is no way to distinguish the instances just by counting numbers of "begin segment" and "end segment" events within a given interval. (Inside the gap left by the red interval, the event sequence is "begin", "end" in both cases.)

This implies that a sweep-line approach needs to track more information about each active segment -- probably their identities, which suggests to me that no fast algorithm will be possible, though that's just a feeling.
> 2 votes

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


# Question
Title: Number of inversions in an array of pairs of integers
I have a problem like this:

we have an array of elements like this :

```
(a0,b0)
(a1,b1)
.
.
.
(an,bn)

```

and I wanna find the number of elements which have one of this two condition:

`1) if ai>aj and bi<bj then:count:=count+1`

or

`2) if ai<aj and bi>bj then:count:=count+1`

I've already found an algorithm that is $O(n^2)$, but I need the faster algorithm.

**Example:** suppose we have this:

```
(1,5)
(4,7)
(8,2)

```

I wanna find the number of time that condition satisfied, so 1\<8 and 2\<5 so condition is satisfied but 1\<4 and 5\<7 so condition is not satisfied.

# Answer
You can visualize the problem like so (using `a = [1,4,8], b = [5,7,2]`):

As you can see, I have sorted `a`, with each element pointing to a position in `b` sorted in reverse. All we need to do now is iterate over `a`, counting how many previous indices were lower than us. We can can compute that with a Fenwick tree, all in $O(nlog(n))$. Here is a python implementation:

```
import bisect

def query(bit, i):
    ret = 0
    while i > 0:
        ret += bit[i]
        i -= i & -i
    return ret

def update(bit, i, delta):
    while i < len(bit):
        bit[i] += delta
        i += i & -i

def csFindInversions2(a, b):
    assert len(a) == len(b)

    def solve(a, b):
        tmp = sorted(b)
        lut = [
            len(b) - bisect.bisect(tmp, b[i])
            for i in sorted(range(len(a)), key=lambda i: a[i])
        ]
        bit = [0]*(len(a) + 1)
        ret = 0
        for i in lut:
            ret += query(bit, i)
            update(bit, i+1, 1)
        return ret
    return solve(a, b) + solve(b, a)

```

Note that this solution does not account for duplicates.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Listing integers as the sum of three squares $m = x^2 + y^2 + z^2$
I would like to write an algorithm that lists all the ways a natural number $m \in \mathbb{N}$ can be written as the sum of three squares $m = x^2 + y^2 + z^2$ with integers $x,y,z \in \mathbb{Z}$.

Legendre's theorem says $m$ has such a representation if $m \neq 4^a(8b+7)$ with $a,b \in \mathbb{N}$. See on MathOverflow:

If I just wanted to *count* the number of representations as the sum of squares, we could find formulas in the Online Encyclopedia of Integer Sequences:

* A005875 \- Theta series of simple cubic lattice; also number of ways of writing a nonnegative integer n as a sum of 3 squares (zero being allowed).
* A074590 \- Number of primitive solutions to $n = x^2 + y^2 + z^2$ (i.e. with $\gcd(x,y,z) = 1$).

How do I **list** the sum of squares representations for each $m$? I would take a slower algorithm if it were easy to implement.

I considered just writing: $\boxed{m -x^2 -y^2 = z^2 }$ and looping over $0 \< x \< y \< \sqrt{m} $ and checking it is perfect square.

Another possibility is keeping an array `square` writing `square[x*x+y*y*z*z] += [[x,y,z]]` storing triples in the appropriate place as I find them. That is something like $m^3$ time since I loop over $0 \< x,y,z \< m$.

Do any solutions jump out at you?

---

**10/12/17** Here I take a naive approach:

```
N = int(M**0.5)

z = [ (a,b,c) for a in range(N) for b in range(N) for c in range(N)
      if a**2 + b**2 + c**2 == M]

```

This rather slow, but I could get solutions in the range `N=10000` in about 20 seconds. Here I run it 100 times within a half-hour.

Sometimes, there is no solution. How can I improve this to work quickly at $N \approx 10^6$ ?

# Answer
> 4 votes
Your first approach is probably the simplest to implement. Its running time will be $O(m)$.

Another approach: you could loop over all $x$ such that $0 \< x \< \sqrt{m}$, and for each $x$ enumerate all ways to express $m-x^2$ as a sum of two squares. There's a lot of theory about how to express an integer as a sum of two squares (e.g., Lagrange's algorithm). However, this will be more complex to implement.

# Answer
> 2 votes
You are looking for solutions of $x^2 + y^2 + z^2 = m$ with no conditions for x, y, z, especially on the order. Instead solve for x \< y \< z and multiply the count by six (since x, y, z could be ordered in six ways), then solve $x^2 + 2y^2 = m$ for x ≠ y and multiply the count by three (you have solutions (x, y, y), (y, x, y) and (y, y, x), and then solve $3x^2 = m$ (solution x, x, x). I assume you allow x = 0, otherwise a slight change is needed. To find the count for all m, 0 ≤ m ≤ M = $10^6$:

```
Initialise an array with indices 0 to M to zeroes.
Loop for x = 0, 1, 2, ... as long as 3x^2 ≤ M
    Loop for y = x + 1, x + 2, ... as long as x^2 + 2y^2 ≤ M
        Loop for z = y + 1, y + 2, ... as long as x^2 + y^2 + z^2 ≤ M
            Increase the count for x^2 + y^2 + z^2 by 6.
Loop for x = 0, 1, 2, ... as long as x^2 ≤ M
    Loop for y = 0, 1, 2, ... as long as x^2 + 2y^2 ≤ M
        Increase the count for x^2 + 2y^2 by 3 if x ≠ y, by 1 if x = y.

```

This is of course no help if you want the count for one single m (although it is faster than your original method by some constant factor, but it won't be anywhere as fast as something more clever), but I think it will be hard to beat if you want to find the count for many m. Quite similar to the sieve of Eratosthenes, which is very good at finding *all* primes in a large range.

Runtime will be $\Theta (M^{1.5})$ to find the count for all 0 ≤ m ≤ M. You can adapt this to find the counts for M - N ≤ m ≤ M, and that should work in $\Theta (M · max (1, N / M^{1/2}))$ which degenerates to $\Theta(M)$ for N = 0, which finds just one count.

It also finds the solutions for $M - M^{1/2} ≤ m ≤ M$ in about the same as for a single m.

PS. To find the count for a single solution, it is better to look for solutions with x \> y \> z: Choose $m^{1/2} ≥ x ≥ (m/3)^{1/2}$ (a smaller x cannot be the largest number in a solution). Then we need 0 ≤ y \< x, and 0 ≤ z \< y, so $x^2 + y^2 + 0^2 ≤ m ≤ x^2 + y^2 + (y-1)^2$. Let $m' = m - x^2$, then $y^2 ≤ m'$ and $y^2 + (y-1)^2 ≥ m'$, so $(m' / 2)^{1/2} ≤ y ≤ min (x, m'^{1/2})$. This minimises the number of pairs (x, y) to examine to about M / 18.

PS. The algorithm runs at full speed if for every pair (x, y) there are many values z. If you look for solutions in \[a, b\] then this is efficient as long as (b - a) is large compared to $b^{1/2}$, so you can divide the interval \[a, b\] in as many subintervals as you have processors, as long as the width of each subinterval is still much larger than $b^{1/2}$. If you modify the algorithm so that x \> y \> z, then you will have fewer pairs (x, y) and therefore more z values for each pair (x, y), so the overhead will be less.

PS. You loop over x, and for each x you want to count the pairs (y, z) such that $y^2+z^2=m-x^2$. Consider that a^2 modulo 16 is always one of 0, 1, 4 or 9. So $y^2+z^2$ modulo 16 is one of 0, 1, 2, 4, 5, 8, 9, 10, 13. For seven possible values of $m-x%2$ modulo 16 we don’t need to do anything. For the others we can significantly reduce the number of values y to examine. And we can consider other modulo values, significantly reducing the amount of work needed.

# Answer
> 1 votes
Code :

```
N=int(M**0.5)
z=[]
for a in range(int(N/3**0.5),N+1):
    for b in range(int(((M-a**2)/2)**0.5),min(a+1,int((M-a**2)**0.5)+1)):
        if int((M-a**2-b**2)**0.5) == (M-a**2-b**2)**0.5:
            z.append((a,b,(M-a**2-b**2)**0.5))

```

We assume that a\>=b\>=c =\> a\>=(M/3)\**0.5,

Since b\>=c : b²+c²=M-a² =\> 2\*b²\>= (M-a²) =\> sqrt(b\>= ((M-a²)/2)).

You fix a and b and then you test if c = (M-a²-b²)\**0.5) is integer. You loop twice : First for a 2/3\*sqrt(M) elements and secondly for b sqrt(M)\*(sqrt(2)-1)=\> your complexity is O(M)

# Answer
> 0 votes
I came across this question while considering this Mathematics SE question, for which one solution is numbers that are the sum of $k$ squares in multiple ways, with the added criteria of a common sum of square roots and at least one distinct $k$-tuplet. Since three squares was the simplest option, I wrote a Python program to investigate these; for large limits it is far quicker to use a sieve approach, if you can stand the large storage requirement.

This is the portion of code that generate the various sums of squares; note that they are in non-decreasing order, so a general case of $a\<b\<c$ would imply different coordinates by re-ordering.

```
lim = int(input('Search limit: '))
rlim = int(lim**0.5)
sqval = {i:i*i for i in range(rlim+1)}

# sieve
allz = []
for a in range(1,rlim+1):
    for b in range(a,rlim+1):
        ab = sqval[a]+sqval[b]
        if ab > lim:
            break
        for c in range(b, rlim+1):
            abc = ab+sqval[c]
            if abc > lim:
                break
            allz.append( (abc, a+b+c, a,b,c) )
# print(len(allz))
allz.sort()

```

The process simply iterates over the possible square root values until the sum of squares goes out of range, and stores all results (i.e. all ways to generate all sums in the range).

List creation time for a sum-of-squares limit of 100,000 was about 5 seconds, most of which was the final sort. It would not be hard to modify this to generate values in a range, rather than starting at zero; you would just need to find/update the right start value for $c$ in the generating loop.

---
Tags: algorithms, number-theory
---


# Question
Title: How does the MMU map multi-channel setups
Given that the MMU does all the memory translations and etcetera, how does it maps a system consisted of multiple RAM chips?

Are their spaces concatenated (e.g Chip 1 + Chip 2)? If so, how does that works given ASLR?

# Answer
> 2 votes
ASLR has nothing to do with this. ASLR is a software technique to secure the applications where all executables are relocatable in that they keep information in the executable to relocate it to any address.

I would guess that the MMU doesn't see if there are several RAM DIMMs. It is the motherboard's job to make sure that if the memory controller of the CPU sets certain lines of the address bus, they are directed towards the right DIMM for decoding.

In hardware it could look like switches (transistors) activated by higher order bits of the address bus that will redirect all address lines to another DIMM. For example, if you have 2 DIMMs of 8GB each then the first DIMM needs 33 address lines for decoding because 2^33 bytes = 8GB. The second DIMM brings the computer to 16GB so, if you set any line of the address bus above 33, then the motherboard knows it needs to use the second DIMM.

---
Tags: memory-management
---


# Question
Title: Maximum-weight set of cliques of size 3 with no common vertices in undirected graph
I'm looking for an algorithm/insight into a problem that's an extension of the Maximum Weight Matching problem. The maximum weight matching problem looks for the max-weight set of edges that contain 0 common vertices. The problem can be thought of as grouping the vertices into sets of 2 such that no vertex belongs to more than 1 group.

I'm looking to extend the problem such that the vertices can be split into groups of 3. For an undirected graph, this translates into looking for cliques/cycles of size 3 that do not contain common vertices. Any guidance on how to approach this problem either deterministically or with an approximation/heuristic algorithm?

Note: the graphs I'm working with are typically dense

# Answer
This problem is NP-complete even when all edge weights are 1, since that restriction is equivalent to the problem Partition Into Triangles, which "Computers and Intractability" (Garey and Johnson, 1979) lists as NP-complete on p. 192, attributing the result to a personal communication from T. J. Schaefer in 1974, apparently based on a reduction from 3-Dimensional Matching.

So, no efficient algorithm can be expected. For an exponential-time exact algorithm, I would probably try branch and bound intertwined with maximum bipartite (2-)matching, as follows: At each stage, we have a vertex $v\_i$, which we will take to be the lowest-numbered vertex of a triangle, and the decision is which of its neighbour vertices $v\_j$ should become the highest-numbered vertex in the triangle. For each possible $v\_j$, to test feasibility of the choice, create a new, bipartite graph with a vertex for each low+high vertex pair decided so far, as well as a vertex for each as-yet unprocessed vertex, and an edge between two vertices whenever the low+high pair represented by one would form a triangle in the original graph with the other *and* the latter vertex is numbered between the low and high vertices represented by the former. Run maximum bipartite matching on this new graph, and check that every low+high pair decided so far is saturated (adjacent to a matched edge) -- if this fails, then the current assignment of low+high vertices cannot be extended to a full triangle partition and the branch can be pruned. I think this algorithm, which chooses just 2 vertices within each triangle, will result in B&B tree depths of around 2/3rds the fully naive approach in which all 3 vertices of each triangle are chosen.
> 3 votes

---
Tags: algorithms, graphs, weighted-graphs, clique
---


# Question
Title: algorithm for connectivity by path of given length
Given an unweighted, undirected graph $G=(V,E)$ without loops or multiedges, and vertices $v,w$, one can use breadth-first search to check if $v$, $w$ are connected, and in particular the algorithm will return a shortest path between them. BFS has time complexity $O(|V|+|E|)=O(|V|^2)$.

Now let $k$ be some fixed integer (not part of the input). Is there an algorithm that takes $G$, $v,$ $w$, and checks whether there is a path between $v$ and $w$ of length $k$? What would be its time complexity?

# Answer
> 3 votes
The problem is NP-complete and referred to as Longest Path. It is FPT, though, so you can solve it in time polynomial in $n$ for *fixed* $k$.

If you want to solve it in FPT time, the easiest solution is to do *color coding*. The trick is two-fold.

1. Suppose that vertices are colored with $k$ colors, and you are looking for a rainbow-path of length $k$, i.e. a path where every vertex has different color. This problem can be solved by dynamic programming!
2. Repeat the following step: Randomly color the vertices of the graph with $k$ colors, and run the rainbow algorithm.

With probability depending only on $k$, *if* there exists a $k$-path, then you will output a rainbow path.

# Answer
> 2 votes
If the required path doesn't need to be **simple**, then there's a dynamic programming solution. Assume that the given graph is specified by an adjacency matrix $G$. Let $F\_k(v, w)$ be the answer for input $k$, $v$ and $w$. So we have a formula:

$$ F\_k(v, w) = \bigvee\_u F\_{k - 1}(v, u) \wedge G(u, w) $$

This kind of formula can be calculated using matrix multiplication: we use the **AND** operator instead of multiplication, and take the **OR** of them instead of the sum. Time complexity is $O(|V|^3 \log k)$.

---
Tags: algorithms, graphs, graph-traversal
---


# Question
Title: Quickly determine if insertion sort or quick sort is better
I'm in a scenario where ~30% of the time, my array is almost completely sorted, and the other 70% of the time, it is basically completely random. I want to quickly determine if my list is almost sorted, use insertion sort if it is, or quicksort otherwise. I've been searching this up all day but no luck.

The alternative solution is to shuffle the array and use quicksort every time, but this passes up on the opportunity to do 30% of the sorts faster.

The way I thought of is to compare consecutive terms, find the number of consecutive pairs out of order, and use that to estimate the entire array, but its not very reliable.

This seems like a common problem, so I was wondering what the "official" solution(s) is.

# Answer
> 1 votes
Quicksort is better unless the number of items in the wrong place is O(log n) only. There is a simple sorting algorithm that runs in O (n) if the number of items in the wrong place is a bit less than O (n / log n): Scan the array, and whenever two items are out of order put them into a separate array. Sort the separate array with Quicksort, then merge both arrays.

This will be not O(n), but faster than Quicksort, if the number of items in the wrong place is much lower than n, say O (n / sqrt(log(n)). The scanning + merging is obviously O(n). If t items are in the wrong order, then sorting them using Quicksort takes O (t log t), so it's O(n) in total if (t log t) = O(n), and asymptotically faster than Quicksort if t = o(n).

---
Tags: algorithms, sorting, arrays, quicksort
---


# Question
Title: How to prove NP-hardness of a longest-path problem?
I have this question:

```
Input:
G(V, E) = an undirected graph, V={v1, v2, ..., vn} (V = set of nodes, E = set of edges)
where there is a path connecting from v1 to vn.

Question:
What is the maximum number of nodes you can visit when starting from v1 and ending at vn.
(including v1 and vn)
Each node can only be visited at most once.

```

I want to prove that this is NP-hard by reducing it from a known NP-complete problem, such as undirected Hamiltonian path or subset-sum.

However I don't know exactly how to do this and this is where I need help.

Can anyone help please?

# Answer
Assuming I understand your definition, your problem is related to the optimisation version of LONGEST PATH:

> **LONGEST PATH**
> *Input*: A graph $G=(V,E)$, an integer $k$.
> *Question*: Is there a path with at least $k$ vertices in $G$

This problem is NP-complete, there's a fairly obvious reduction from HAMILTONIAN PATH - just set $k = n$, and clearly if we are given an (ordered) set of vertices, we can easily check that it is a path over at least $k$ vertices.

Note that we can assume that $G$ is connected, and we will do so from now on.

The optimization version *max*-LONGEST PATH where we ask for the path of maximum length is then NP-hard (the polynomial-time equivalence of these two problems is a straightforward exercise).

Then the difference between *max*-LONGEST PATH and your problem is that you have two specified vertices that are the start and the end of the path. Now we need a reduction from some NP-hard problem to your problem, but we already have one that's really close.

Given an instance $G$ of *max*-LONGEST PATH you should now be able to construct an instance $G'$ of your problem such that if $p$ is the longest path in $G$, then this is almost the longest path in $G'$.

A further hint if you are still beating your head against a wall in about, say, 2 hours:

> Try taking $G$ and adding two new vertices $s$ and $t$ and connecting them so that they can start and end such a path $p$ - remember though that you don't know what $p$ is.
> 7 votes

# Answer
Suppose we have a solution to the longest path problem, *longest-path*, in which given a graph G, and an integer k, we need to decide if G has any (simple) path of k edges. Then to solve the Hamiltonian-path problem, HAM-PATH, we could use *longest-path* with k=|G|-1. This means, HAM-PATH is polynomial time reducible to longest-path. $$\begin{aligned} i.e., HAMPATH \le\_{p} longest \text{ - } path \\ equivalently,\hspace{15px} longest \text{ - } path \in P \Longrightarrow HAMPATH \in P \\ taking \hspace{5px} contrapositive, \hspace{15px} HAMPATH \not\in P \Longrightarrow longest \text{ - } path \not\in P \\ \end{aligned}$$

Since HAM-PATH is NP-Hard, so is longest path problem. However, it should be noted that for certain types of graphs, polynomial time solutions exist.
> 3 votes

---
Tags: complexity-theory, reductions, proof-techniques, np-hard
---


# Question
Title: Is $\{\varepsilon\}$ a conventional way to mark the empty language?
I am grading an exercise in Automata and Formal Languages and see many of the students use $\\{\varepsilon\\}$ as the empty language. At first I thought this was an error, and I have asked the lecturer who confirmed. But I keep seeing this and I'm losing my confidence. Is this kind of thing used by anyone? Meaning, does anyone use $\\{\varepsilon\\}$ as the empty language (even though it would "override" the obvious meaning of the singleton of $\varepsilon$)?

# Answer
> 9 votes
No, that's the language containing one string: the empty string, which is very much distinct from the empty language. The finite state machine on the left accepts language $\\{\\}$, the finite state machine on the right accepts language $\\{\varepsilon\\}$. They are not the same.

If a lot of students are confused maybe explicitly show the difference in an exercise/during a lecture.

---

As an example, we could use the language as a password check. Anyone submitting an accepted word would be let through. Then $\\{\\}$ means "let no one in" and $\\{\varepsilon\\}$ means "let anyone that submits a blank password in". Those are quite different indeed!

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


# Question
Title: Data structure for interval subset queries
I have a set $S$ of intervals. I'd like to store them in a data structure, so that I can handle the following query efficiently: given a query interval $q$, count the number of intervals $s \in S$ that contain $q$, i.e., count the number of intervals $s \in S$ such that $q \subseteq s$.

(This is like a stabbing query, but now the query is an interval, not a single point.)

Is there an efficient data structure for this? Ideally, one that can be constructed in $O(n \log n)$ time and where each query can be answered in $O(\log n)$ time, where $n$ denotes the number of intervals in $S$?

# Answer
> 2 votes
### Summary

Yes, a persistent segment tree for the sums of ranges over an array of counters can do it.

Please run the example program in Java here.

### Intuition

There are at most $|S|$ ending values for all intervals in $|S|$. We can build a persistent segment tree: we process intervals in order of increasing starting point, incrementing a counter corresponding to that interval's ending point, and use a persistent segment tree to enable us to compute suffix sums on the array of counters at any point in time. For each query, choose the appropriate version of the segment tree to get the desired count.

### A specialized persistent segment tree

Given an array $S$ of intervals, let us build a persistent segment tree with $|S| + 1$ versions. In other words, we will build $|S|+1$ segment trees. An array of that length will store the root nodes of those trees.

All arrays are 0-indexed.

0. Since only comparison matters while the actual magnitude of values is not, we can replace each endpoint of all intervals in $S$ by its standard competition rank among all endpoints of all intervals in $S$. This is the usual compression/ranking step on problems about comparisons.
Let $B$ be the array of the starting points of all intervals in $S$ and $M$ be the unranking mapping, which maps each element of $B$ to the original starting point of a given interval.
1. Create an array $E$ of $|S|$ zeros. This array is only used to help explain the data structure and the algorithm. It does not show up explicitly in the data structure nor the algorithm.
2. Initialize an array $J$ of $|S|+1$ nodes. $J\[i\]$ will be the root node of the segment tree of version $i$.
3. Created the segment tree of version 0, all nodes of which have value 0. This corresponds to the initial state of $E$.
4. Sort $S$ by the starting point of each interval, breaking ties arbitrarily.
5. One by one process the sorted $S$. Suppose the current interval is the $i$-th interval, $\[l, r\]$. Construct the segment tree of version $i+1$ by updating the segment tree of version $i$ as if we have added 1 to $E\[r\]$. Check this article or this article to get an idea how this updating is done. Read my program in Java for the exact details.

The data structure we wanted is the combination of the array of $|S|+1$ segment trees, a.k.a a persistent segment tree, the array $B$ and the unranking mapping $M$.

### Handle the queries

Suppose $q=\[l\_q, r\_q\]$ is a query interval. Here is how we find the number of all intervals in $S$ that contain $q$.

1. Find the index of the last interval in sorted $S$ whose starting point, when mapped to its original starting point before ranking (i.e., unranking by $M$), is not bigger than $l\_q$, using binary search. If there is no such index, return 0 and stop.
2. Let the index found at step 1 be $i$. Return $J\[i+1\].\text{sum}(r\_q, |S|)$, which is the sum of elements with indexes no less than $r\_q$ in array $E$ at the time right after the $i$-th interval had been processed during step 5 of the construction above, and, hence, which is the number of all intervals in $S$ that contain $\[s\_q, e\_q\]$.

### Time Complexity analysis

The standard construction of a persistent segment tree of $v$ versions for the range sums of an array of length $m$ runs with $O(m + v\log m)$ time-complexity. Here we have $v=|S|+1$ and $m=|S|$. The ranking of all endpoints takes $O(|S|\log |S|)$ time. Including other immaterial running cost, we find the construction of the data structure takes $O(|S|+ (|S|+1)\log |S|)=O(|S|\log|S|)$ time.

For a given query interval, find the right version of the segment tree takes $O(\log |S|)$ time. It takes another $O(\log |S|)$ time to get the number of containing intervals as the range sum. So, each query takes $O(\log |S|)$ time.

### Space Complexity

It requires $O(|S|\log |S|)$ space to store the persistent segment tree.

# Answer
> 1 votes
Let $F(I) = |\\{s \in S : s \subseteq I\\}|$ where $I$ is an interval.

If $\[a, b\]$ is our query interval, we can make the following partition where $R$ is our desired result:

$$R =n -F((-\infty, b)) - F((a, \infty)) + F((a, b))$$

The first two queries can be answered simply using a sorted data structure of respectively endpoints and startpoints.

The last query is the *dual* of this problem, which has an answer here on this site.

---
Tags: data-structures, search-trees, intervals
---


# Question
Title: Find a MST such that it's mostly red (original graph's edges are colored red and blue)
Consider the following problem: Given a simple, strongly-connected, weighted graph G=(V,E), of which every edge is colored either red or blue (in addition to having a numeric weight). Find an efficient algorithm to find an MST which is mostly red (meaning, has the most red edges possible).

I think this can be done in linear time, in O(n+m) complexity using either Kruskal or Prim's algorithms, but I can't find an algorithm to do that.

I thought about diving the edges into two groups - red and blue, and then running Kruskal's algorithm on the red edges first, and then if we still don't have |V|-1 edges in the MST we have so far, run Kruskal again on the blue edges. However, this algorithm doesn't solve the given problem since we might not end up with a tree, but rather with a forest (made up of two trees).

Please advise.

# Answer
> 2 votes
Hint: Add $\epsilon\>0$ to the weight of all blue edges. (This is equivalent to the suggestion Raphael made in his comment.)

# Answer
> 2 votes
Your problem is ambiguous. What is the first to be optimized? the number of red edges or the tree cost? If the tree cost must be the same as an MST of the uncolored graph, Yuval's solution is correct (equivalently when sorting the edges in Kruskal algorithm, break tie by their color). If you want to find the minimized tree cost among all spanning trees with the most possible red edges, your algorithm is correct. For your question, if the algorithm cannot find a tree, there is no MST, i.e., the graph is not connected. BTW, the time complexity is not linear.

# Answer
> 1 votes
If all of the weights are integers, then given n nodes, we know the spanning tree will have a maximum of n-1 edges. Therefore multiply all edges so the new edge weight is w\_i'=n\*w\_i+(1 if blue else 0). If non-integer data, then it can always be ordered, discretized and preserved to its original value with a dictionary. This means that the gap between weights will be a multiple of n and we know the spanning tree cannot at more than n-1 preserving the minimum spanning tree property while minimizing the blue edges.

Otherwise the suggestion to use Kruskal and selecting red edges before blue edges on tie's seems reasonable however, it will be correct by the cut property and cycle properties of MSTs. The whole reason why the greedy algorithm works in the first place is why we can simply further weight the edges in case of ties and still get a proper minimum.

If all else fails, you can check the MST of only the R red edges in E. If you find one you are done, otherwise if it is disconnected, then add all combinations of 1 edge, 2 edges, ..., |R| edges and compute MSTs until it finds an MST and at that point you for sure know the minimum. Of course this is a very expensive O(2^n) algorithm and should only be used as a tool with small cases where n \< 20 or so for example so you can verify that any algorithm you think you made right is correct. Coming up with good test cases or even exhaustive ones is also quite difficult.

# Answer
> -1 votes
**Approach 1:** Use a disjoint set structure, every vertex will be a set, then connect all the vertices with the red edges first, and then add the blue edges. Linear time.

**Approach 2:** Second approach, weight of red is 0 and weight of blue is 1. Run Prim algorithm. it is linear because you don't have to sort the edges.

---
Tags: algorithms, graphs, optimization, spanning-trees
---


# Question
Title: What are string matching algorithms used in text editors like Atom and sublime
I know there are many algorithms for finding a pattern in a text like Boyer Moore, KMP, RabinKarp and so on.

I want to know what is the one that is mostly prefered by text editors and IDEs, as I find them efficient.

# Answer
Since Emacs is the superior editor, you can take a look in the source code yourself: search.c

Emacs uses the Boyer–Moore string-search algorithm, so that's probably what you should prefer too.
> 2 votes

---
Tags: algorithms, time-complexity, string-matching
---


title: Dominating set with vertex cover

text:
# Question
Title: Dominating set with vertex cover
if we have a Graph (V, E) and for all nodes v\_i, v\_j exists a path from v\_i to v\_j can you give me an example of such graph with dominating set size 2 and doesn't have a vertex cover of size 3?

# Answer
> 0 votes
Hint: a cycle of the right size with one more edge. A complete graph of the right size can also work.

---
Tags: vertex-cover
---


# Question
Title: Is it possible fo find a vertex-cover of size $\lceil \log |V| \rceil$ in polynomial time?
If we have a graph $G=(V,E)$, can we find a vertex cover with size $\lceil \log |V| \rceil$ in polynomial time?

# Answer
> 2 votes
Let the input graph be $G=(V,E)$ and let $k$ be the (maximum) size of the vertex cover of $G$ we are searching for. Proceed as follows:

* If $E=\emptyset$ return the trivial empty solution.
* Otherwise, if $k\>0$:
    + Pick an arbitrary edge $(u,v) \in E$.
    + Recursively search for a vertex cover $S$ of size (at most) $k-1$ on the graph $G - u$. If $S$ exists return $S \cup \\{u \\}$.
    + Recursively search for a vertex cover $S$ of size (at most) $k-1$ on the graph $G-v$. If $S$ exists return $S \cup \\{v \\}$.
* Return "no solution exists".

The time complexity of the above algorithm can be described by the following recurrence relation, where $n$ is the number of vertices of the input graph for your problem.

$$ T(k) \le 2T(k-1) + O(\mbox{poly}\\, n) \quad \mbox{and} \quad T(0)=O(1). $$

Therefore $T(k) = O( 2^k \cdot \mbox{poly}\\, n )$. In your case $k=\lceil \log n \rceil$, therefore the overall time needed is $O( \mbox{poly}\\, n )$.

---
Tags: polynomial-time, vertex-cover
---


# Question
Title: How large is the seed in an encryption algorithm such as stream cipher?
The stream cipher is an encryption algorithm that was designed to approximate an idealized cipher, known as the One-Time Pad. It's crucial for a stream cipher to remain secure is to have a pseudorandom generator that hard to predictable and a seed that was never used. For this to be achieved, I assume we need to have a really large seed that the most powerful computer can't predict, but I can't approximate how large the number is.

# Answer
The seed of a pseudorandom generator that is used as a stream cipher is called a **key**.

The most common key sizes are 128 bits and 256 bits. (That's symmetric keys, where there's no cheaper way to break than brute force. Asymmetric cryptography typically relies on keys having certain mathematical properties that make the algorithm work, but also enable better attacks than brute force.)

To understand how hard it is to break a 128-bit key, meaning that you have to try $p \cdot 2^{128}$ possibilities for a chance of success $p$, consider these orders of magnitude:

* A fast processor might be able to try about one billion keys per second (1GHz).
* A powerful attacker might be able to afford one billion processors.
* The universe is about 1 billion billion seconds old (a little over 30 billion years).
* 1 billion is slightly less than $2^{30}$ ($2^{30} = (2^{10})^3 = 1024^3 \gtrsim (10^3)^3 = 10^9$).

So if you're extremely rich and willing to wait until the universe is twice as old, you can enumerate about $2^{120}$ keys. If you're only willing to wait 30 years, you can only enumerate about $2^{90}$ keys, giving you a chance of breaking any particular key of less than one in 250 billion. Conclusion: a 128-bit key is sufficient for security against brute force.

A 256-bit key provides a security margin that can cover:

* Hypothetical advances in cryptanalysis that make the algorithm slightly easier to break.
* Hypothetical advances in computation, such as quantum computers, which effectively halve the key size.
* A very powerful adversary who tries to break basically every encrypted communication, and is interested in even succeeding for a tiny fraction.
* A very powerful adversary who records basically every encrypted communication, and would detect if the same key is used twice, which could then let them discover the key by non-cryptographic means (exploiting a bug, demanding it at gunpoint, a subpoena, …). Due to the “birthday paradox”, there's a macroscopic chance that two instances will generate the same random key if the number of instances is at least about the square root of the number of possible keys, so 8 billion people using a billion different keys each (about $2^{63}$ keys in total) would be around the threshold for 128-bit keys.

---

In practice, key size just isn't an issue except in legacy software and protocols that are at least 2 decades out of date (keys shorter than 128 bits became obsolete when AES became the de facto standard in the early 2000s). Cryptography gets broken by non-cryptographic means or due to implementation weaknesses such as side channels, or gets circumvented altogether due to non-cryptography-related security vulnerabilities (binary exploits, escaping exploits, misconfigured controls, phishing, …). Cryptographic algorithms are usually the strongest part of information security.
> 4 votes

# Answer
The seed is called the key and to be secure it really depends on the usage and known computing powers. The most powerful collective power (known) is currently the bitcoin miners that they have reached $\approx 2^{93}$ SHA256 calculations per year in this year.

Therefore, the effective key size must be larger than $2^{93}$ and the NIST requires **a minimum of 112 bits**. The miners need $2^{19}$ years to achieve $2^{112}$. This may true for the single target. The attackers, however, may use batch attack (multi-target attack) so that even the key size is 128-bit they can find the first target key with $2^{70}$ work with billion targets (See in Has AES-128 been fully broken?).

Therefore we prefer the golden standard as the 256-bit key sizes. The ChaCha20 can use a 256-bit key size or one can use AES-256 in CTR mode to achieve a stream cipher.

In addition to the key, the modern stream ciphers also using **IV/nonce** to use the key more than one encryption and this is also a countermeasure to batch attack. One must be careful about the (key,nonce) re-use issue that can at least remove the confidentiality. To mitigate this one can use XChaCha20 that uses 192-bit nonces or can use a non-misuse resistant scheme that is going to be the next standard in the future.

Of course, we don't use the stream cipher alone, we prefer Authenticated Encryption modes like ChaCha20-Poly1305 to achieve confidentiality, integrity, and authentication.
> 3 votes

# Answer
## It depends on the exact encryption method you are using.

128-bit is theoretically sufficient against normal computers and 256-bit against quantum computers, as per previous answers, but you should always follow the best practice standard of the exact type of encryption you are using. This is because no encryption algorithms has perfect entropy, or in layman's terms, no encryption algorithm is perfectly random.

Because no key is perfectly random, it means that methods exist for predicting keys that do not require you to check every single possible key combination. So, while symmetric encryption like AES has very close to perfect randomness making 256-bit sufficient for all known use cases, many common asymmetric algorithms such as RSA suggest key lengths up to 4096-bit due to known methods existing against them that are more efficient than brute force.

That said, it is not really your key-length that is most important. The most important part of a symmetric encryption is the padding. This is a randomized string that is appended to the front of your plain-text string and then dropped. RC4 with a max length (2048 bit) key is actually quite easy to break, but RC4-drop512 with only a 512-bit key is much harder to break despite the shorter key because it does more to obscure the deterministic part of of the stream cipher making cracking it require something much closer to a brute force attack.
> 1 votes

---
Tags: pseudo-random-generators, security, encryption
---


title: Memory addressing rapidity

text:
# Question
Title: Memory addressing rapidity
I've got a few questions related to the different types of memory that we can find:

To my understanding, since there are registers that are close physically to the CPU, these are much faster to access, same goes for the cache that is further to the CPU but still relatively closed, and the RAM which is further than everyone else and which is the slowest to gain access too. My question is: Why can't we simply put all of the RAM memory close physically to the CPU since apparently this is what is required in order to be fast. Is there another criteria to being fast apart from being close ? As I've seen, apparently since the RAM has a bigger memory size, the address in bits to access a register is longest and therefore require more time to gain access to the latter register. What if we had let's say 1000 units of cache memory each one size 8mb, in order to have a fast access to each one of them and still store 8GB of memory ? I think this would fail because since we have 1000 cache units, we'd still have to precise which one of the units we would want to have access to and therefore we'd still have the problem of having more bits in the address (at least I think so), if not, why would this logic fail ? Thank you for your help

# Answer
> Why can't we simply put all of the RAM memory close physically to the CPU

Because that is not how geometry works. You cannot have everything close to the CPU, because the stuff that is close to the CPU is blocking the space close to the CPU, and thus other stuff has to be farther away.

Geometry works the same on the CPU as it does everywhere else: why don't all your neighbors live directly next door to you? Well, because your neighbors are taking up that space, so you simply can only have two direct neighbors. Everybody else has to live further away.

There are actually already 3-dimensional designs where the memory is stacked on top of the CPU, in order to be able to bring more memory closer to the CPU. But that only pushed the problem out, it does not solve it.

There is, however, a whole slew of other reasons, not just geometrical ones, why we have a *memory hierarchy* and not just a single flat memory. The main problems are that, in general, faster memory is also

* more expensive,
* more power hungry,
* more complex, and
* physically bigger (less dense).

That latter problem actually leads to an interesting optimization problem: as we said above, we can't have all the fast memory close to the CPU, because the space close to the CPU is limited. However, since slower memory is more dense, and thus takes up less physical space for the same memory capacity, you can actually put more slower memory close to the CPU than you can faster memory!

And even if you were to use only the fastest memory technology for all your memory, you quickly run into problems with the fundamental speed limit of the universe: the speed of light. As a general rule, our systems are designed in such a way that a single clock pulse must be able to propagate through the entire clock domain within a single clock cycle.

This means that no matter how close and how dense we pack our memory to the CPU, there comes a point where we cannot clock the memory with a high clock rate anymore. The further away we get, the lower the clock rate. But then it doesn't make sense to use the super-expensive, super-fast memory anymore, if we have to make it slower anyway. It makes more sense to use the cheaper, more dense, more energy-efficient memory.

And that is why the *memory hierarchy* exists: because the difference is not just speed, it is also cost, space, and energy. Here is an example of one possible memory hierarchy:

1. Registers (discrete flip-flops)
2. Level 0 Cache / µOP Cache (typically SRAM; per thread)
3. Level 1 Cache (typically SRAM; per core)
4. Level 2 Cache (typically SRAM; per core)
5. Level 3 Cache (typically SRAM; per die)
6. Level 4 Cache (typically SRAM; per module)
7. Local Main Memory (typically DRAM; per module)
8. Remote Main Memory (typically DRAM; "not this module")
9. SSDs (Flash; per node)
10. HDDs (magnetic; per node)
11. SAN (mix of SSDs and HDDs; per system)
12. Tape Library (per system)
13. Offsite Cloud Storage

Obviously, not all of these levels exist in all systems. This is an extreme example of a multi-core, multi-CPU, multi-node NUMA cluster with a separate storage network – my laptop doesn't have #6, #8, #10, #11, and #12, for example.

#8 only exists in so-called "NUMA" systems (Non-Uniform Memory Architecture), i.e. systems where not all RAM is "created equal". Typically, these are systems with a large number of CPUs, where it is not feasible to give all CPUs the same access to all of the RAM. Instead, the RAM is split into parts and typically one block of CPUs has direct access to one block of memory, and if it wants to access the rest of the memory, it typically has to talk to the CPU(s) that "own(s)" that block.

As a closing remark, I want to say that while the answers here have shown why your idea doesn't work, that does not mean that your idea is stupid! In fact, your idea is pretty much the Holy Grail of storage technology, and every couple of decades, a new technology comes along that tries to be fast, cheap, dense, energy-efficient, and ideally even non-volatile, at the same time, so that it can replace a large portion of that memory hierarchy.

However, as of today, none of those technologies have been able to live up to the hype, so to say: MRAM, FeRAM, T-RAM, Z-RAM, and many others. The latest entry being Intel's / Micron's 3D XPoint (better known under Intel's marketing brand *Optane*).
> 4 votes

# Answer
You can find a picture of an M1 chip where memory and CPUs are on the same physical chip. You’ll see that memory is bloody big, and you can’t move all of it close to the CPU.

The real reason is cost. L1 Cache can move data from/to several registers simultaneously and very fast. That makes it very expensive per byte. Nobody would be able to pay for even 1MB of L1 cache, and RAM is thousand times bigger. L2 cache uses a technology that is slower and cheaper but allows more storage, cheap enough that you can afford a few megabytes.

You will always have different technologies at different costs, and in that case you get the best results by mixing a tiny bit of super fast, super expensive, and a bit of slower, less expensive, and a lot of cheap and slow memory.
> 2 votes

---
Tags: operating-systems, cpu
---


# Question
Title: Can x86 Instruction Set be changed with microcode update?
How I understand microcode translate an instruction to microinstructions. And CPU has a unit that stores all possible of microinstructions. These microinstructions can be changed, because it load every time after boot from motherboard. Can instruction set be changed?

I am sorry if i ask strange question, if I misunderstood , please correct , thanks and again I am sorry if my English grammar is bad. (google translate)

# Answer
That depends completely on the CPU. Some CPUs don't use microcode at all. Some CPUs use a mixture of hardcoded instructions and microcoded instructions. This mixture can be anywhere between almost all hardcoded and only a few microcoded instructions to almost all microcoded and only a few hardcoded instructions.

For CPUs that have microcode, the microcode could be either modifiable or not modifiable.

If all instructions are microcoded (there are no hardcoded instructions) and the microcode is stored and loaded in such a way that you can load a different one at will, then it would *theoretically* be possible to load microcode that implements a completely different instruction set.

However, the feasibility of that still depends on the internal design of the CPU. An extreme example would be the Transmeta Crusoe and Efficeon CPUs. These were 128 bit VLIW designs internally, and in order to execute x86 code, they had a software layer called *Code Morphing Software*, which was essentially an interpreter and JIT compiler from x86 to the internal VLIW code. The Code Morphing Software was running entirely in the standard RAM. This makes it sound like it should have been *very* easy to just load a different version of the Code Morphing Software and turn the CPU into an ARM or PowerPC or SPARC or MIPS CPU, right?

Well, not according to Linus Torvalds, who worked for Transmeta at the time. He was asked this exact question, and his answer was that the internals of the CPU are so specifically optimized for interpreting x86 code that writing a CMS implementation for, say, MIPS would be no different (and no more performant) than simply writing a MIPS emulator for x86 … which already exist anyway.

On the other hand, the CPUs of the Xerox Alto, Dandelion, Dolphin, and Dorado workstations were *explicitly* designed to be microcoded for different use cases. They would run completely different microcode depending on whether they were running Interlisp, Smalltalk, or the Star system. For example, the Smalltalk system implemented the most important instructions of their VM in microcode, so that in some sense, the CPU could directly execute (parts of) Smalltalk byte code. You could say that when running the Smalltalk system, Smalltalk byte code was the ISA!
> 5 votes

# Answer
x86 CPUs (Intel, AMD) use a large amount of microcode, a part of this microcode can be downloaded in RAM and can be updated, principally for fixing bugs (and maybe for more hidden purposes such as disabling some parts of the CPU depending on the part number).

I doubt using different microcode would be enough to completely change the instruction set, because of the highly optimised nature of modern CPUs with very complex instruction decode.

There are a few other examples of CPUs with a complex internal microcode, for example the nVidia Denver with has an internal processor which dynamically translates the ARM instruction set, some rumors pretended that this project was initially targeting x86 before being redesigned as an ARM CPU, and I doubt supporting both x86 and ARM compatibility would be reasonably achievable.

There are a few historical examples of CPUs in the 60's and 70's which had all their microcode in RAM (for example IIRC DataGeneral Eclipse).
> 3 votes

# Answer
I very much doubt that any modern CPU will use microinstructions nowadays, and the ability to change this would be an incredible security risk. Absolutely totally unacceptable.

Being able to change the microcode would mean you cannot trust *any* code in your computer at all.
> -1 votes

---
Tags: computer-architecture, cpu
---


# Question
Title: Greedy approach suggestions for assigning objects
Suppose there are three categories of people. Type X, Type Y, Type Z. In each type, there are two objects of subtype Type 'a' and type 'b'.

For example.

X: a1 , a2 , b1 , b2

Y: a3 , a4 , b3 , b4

Z: a5 , a6 , b5 , b6

Each object of type 'a' should be assigned with an object of type 'b'. But it is ****desirable** not necessary** to assign a type 'a' with type 'b' from different classes (X, Y, Z).

In this example, the optimal solution would be: a1 with b5 , a2 with b6 , a3 with b1 , a4 with b2 , a5 with b3 , a6 with b4 .

Non -optimal solution would be :

a1 with b5 , a2 with b6 , a5 with b1 , a6 with b2 , a3 with b3 , a4 with b4 .

(Non -optimal because a3 and a4 are assigned with b's of same type Y)

If we generalize, there can be n- number of Types (X,Y,Z, .....and so on) with different number of a's and b's in each (but total number of a's = total number of b's).

How to find an optimal solution?

# Answer
> 1 votes
This problem reduces to finding a maximum matching in a bipartite graph, which can be done easily by e.g. the Ford-Fulkerson algorithm. You construct the graph as follows:

Take all elements of type $a$ on one side and all elements of type $b$ on the other. Then, for any two elements $a\_i,b\_j$, draw an edge between them if they do not belong to the same category.

If there is a matching in the set with only, say, $k$ pairs belonging to the same category, then we can find a matching in our graph on $m-k$ edges, where $m$ is the number of a's (or b's).

---
Tags: algorithms, np-complete, greedy-algorithms
---


title: Maximum Stacking Height Problem

text:
# Question
Title: Maximum Stacking Height Problem
Has the following problem been studied before? If yes, what approaches/algorithms were developed to solve it?

> **Problem ("Maximum Stacking Height Problem")**
>
> Given $n$ polygons, find their stable, non-overlapping arrangement that **maximizes their stacking height** on a fixed floor under the influence of gravity.

## Example

Three polygons:

and three of their infinitely many stable, non-overlapping arrangements, with different stacking heights:

## Clarifications

* All polygons have uniform mass and equal density
* Friction is zero
* Gravity is acting on every point into the downwards direction (i.e. the force vectors are all parallel)
* A configuration is not considered stable if it rests on an unstable equilibrium point (for example, the green triangle in the pictures can not balance on any of its vertices, even if the mass to the left and the right of the balance point is equal)
* To further clarify the above point: A polygon is considered unstable ("toppling") *unless* it rests on at least one point *strictly to the left* **and** at least one point *strictly to the right* of its center of gravity (this definition greatly simplifies simulation and in particular makes position integration etc. unnecessary for the purpose of evaluating whether or not an arrangement is stable.
* The problem in its "physical" form is a continuous problem that can only be solved approximately for most cases. **To obtain a discrete problem that can be tackled algorithmically, constrain both the polygon vertices and their placement in the arrangement to suitable lattices.**

## Notes

* Brute force approaches of any kind are clearly infeasible. Even with strict constraints on the placement of polygons inside the lattice (such as providing a limited region "lattice space") the complexity simply explodes for more than a few polygons.
* Iterative algorithms must bring some very clever heuristics since it is easy to construct arrangements where removing any single polygon results in the configuration becoming unstable and such arrangements are unreachable by algorithms relying on every intermediate step being stable.
* Since the problem smells at least NP- but more likely EXPTIME-complete in the total number of vertices, even heuristics would be of considerable interest. **One thing that gives hope is the fact that most humans will recognize that the third arrangement in the example is optimal.**

# Answer
While I don't know of any specific algorithms for this problem, you could approach this in a pretty efficient method by breaking it down into separate parts.

I would start by finding the rotation for each individual shape that provides a maximum height while maintaining a valid balancing orientation (is: not on a point like with the triangle). If a shape has multiple equal heights, i would go with the configuration that gives the greatest surface area on top of it. Once you have this, you can then figure out how to best stack each object in a manor that is able to be balanced.
> 1 votes

# Answer
The following algorithm may not be optimal, but should give a good approximation. We will use Simulated Annealing. Each configuration can be represented by the following parameters:

1. Order of shapes from ground to top
2. Rotation of each shape
3. Horizontal displacement of each shape

To evaluate a configuration, we place shapes one at a time in the order given in 1 with the rotation from 2 and horizontal displacement from 3. Wait until the configuration settles into a stable position and then measure its height. A configuration can be "mutated" by changing one of the 3 attributes. Run standard Simulated Annealing procedure to find good configurations. To make this more efficient, we can limit the number of rotations in 2 to $k$ bins. Similarly we can limit the number of possible horizontal displacements. With the right parameters, each of the configurations in the original post can be achieved. For me the hardest part in implementing this is finding a good physics simulator that would allow realistic placement of these shapes.
> 1 votes

---
Tags: algorithms, time-complexity, optimization, computational-geometry, heuristics
---


# Question
Title: Grammar for all words other than $wq,qw$
I want to generate a grammar that can't generate the words $qw$ and $wq$ but can generate the word $qwwq$. In other words, $L(G)=\\{m ∈ \\{q,w\\}^\* \mid m \neq wq,qw \\}$.

My grammar:

\begin{align} &S \to qSw \mid wSq \mid qXq \mid wXw\\ &S \to qYw \mid wYq \mid q \mid w\\ &X \to qX \mid wX \mid qXw \mid wXq \mid ε \\ &Y \to qw \mid wq \\ \end{align}

# Answer
> 1 votes
How about \begin{align\*} S&\to q\mid w\mid qqB \mid wwB \mid qwA\mid wqA\mid \varepsilon \\ A&\to qB\mid wB \\ B&\to qB\mid wB\mid \varepsilon \end{align\*}

We can just explicitly include strings of length 0, 1 or 2 that are allowed, but add another non-terminal after the length two strings which are not allowed to force us to add at least one more terminal, then make sure after that we can add any letters we want in any order.

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


# Question
Title: How to find i largest numbers in unsorted array in O(n) where i <= n^(1/2)
If we have length $n$ unsorted array such that each element is integer and different, how to find $i$ largest numbers in linear time O(n)? but $i \leq n^{\frac{1}{2}}$.

For example, if we have $A = \[11, 6, 8, 1, 9, 100, 88\]$ and input $i = 2$, then output is $\[100, 88\]$ (sorted).

# Answer
Use a selection algorithm to find the $i$th largest number. This can be done in linear time. Then, do a second scan over the array to find all numbers larger than the $i$th largest number. (With many selection algorithms, this last step is unnecessary, as they partition the array into elements smaller than the $i$th largest and larger than the $i$th largest.)
> 2 votes

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


# Question
Title: How is the Longest Path Problem NP complete?
From the following link:

https://www.csie.ntu.edu.tw/~lyuu/complexity/2016/20161129s.pdf

So basically, in our iff proof, we have to show two directions:

Forward: If Hamiltonian Path has a yes-instance, so does longest path. This makes sense because we can just let "k" = |V| - 1 if hamiltonian path is yes. Then clearly there is a longest simple path with |V| - 1 edges.

I'm having trouble with the backward part

Backward: If Longest Path has a yes instance, so does longest path. Let's assume that there is a longest path from s to t of length k (this can be a different k than the one we defined above?). **How does that guarantee that there is a hamiltonian path from s-t?** If it is the same k, where k = |V| - 1, then I agree there is a hamiltonian path, but what if this k is something different?

# Answer
> 2 votes
> How does that guarantee that there is a hamiltonian path from s-t?

It doesn't, but the Longest Path problem doesn't require a path between particular vertices, it only requires that some simple path of length $K$ exist in the graph. To reduce Hamiltonian Path to Longest Path you just require that path to have $|V| - 1$ edges, which in a simple path *must* involve all the vertices in the graph, making it a Hamiltonian Path.

# Answer
> 0 votes
Remember that we want to reduce Hamilton path problem to the longest path problem. Hence we have to show that an instance I of Hamilton path problem has a Hamilton path if and only if its transformed instance f(I) has a longest path of length n-1 where f is the reduction. We don't have to care about longest path problem instances where k is something different.

To make the point clearer, you could show the correctness of the reduction in a slightly different way: Show that if G has a Hamilton path, then G has a path of length n - 1. And if G has *no* Hamilton path, then G has no path of length n - 1.

# Answer
> 0 votes
I agree with @Kyle Jones; and the *'iff'* part in the proof looks little fishy to me. For the NP-Hard part, you may refer to my answer here https://cs.stackexchange.com/a/137129/62634 \- I've tried to prove it from the basics.

For the 1st part, to prove that the longest path is NP, I was thinking to start off with guessing a path of size K=|V| -1 and then check in polynomial time whether it exists/simple-path. If not, then I guess again a path of size K-1, and do the test, and this goes on until k=1. This way I have to guess only |V|-1 time. By contrast, the proof that you've cited, could also mean that there are exponential number of paths of size between size K and |V|-1.

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


title: Longest sequence of dominoes

text:
# Question
Title: Longest sequence of dominoes
Given $k$, a $k$-domino is a non-ordered pair of integer values of $\[\\!\[0, k-1\]\\!\]$, for example $\langle 0, 3\rangle$ or $\langle 1, 1\rangle$ are dominoes, the domino $\langle 3, 0\rangle$ being the same as $\langle 0, 3\rangle$.

A sequence of length $n$ of dominoes is a sequence $(d\_0, d\_1, …, d\_{n-1})$ where $d\_i = \langle a\_i, b\_i\rangle$ is a domino, and $\forall i \in \[\\!\[0, n-2\]\\!\], b\_i = a\_{i+1}$. For example, $\langle 2,3\rangle\langle 3,5\rangle\langle 5,2\rangle\langle 2,1\rangle$ is a sequence of length 4.

Given $k$ and $N$, and a set $S$ of $N$ distincts $k$-dominoes, I want to find the longest sequence of dominoes constructible using each domino in the set $S$ at most once.

My ideas so far are to use some kind of backtracking algorithm: I try to complete a sequence of dominoes with a new domino – among those not used, or not eliminated – and if it is valid, I continue; if there is no valid domino, I delete and elimininate the last domino to try again. I am using hash table to keep track of the remaining dominoes.

I wondered if there is a more efficient/elegant way to do it, maybe by pre-sorting the set $S$ before trying to construct sequences of dominoes, or using dynamic programming in a way I haven't found yet.

I also thought of constructing a graph with each domino as a vertex, but I don't really know how to put edges because of the two faces of the domino: if I add an edge between two dominoes that have a common value, then I risk to find $\langle 1,2\rangle\langle 2,3\rangle\langle 2,0\rangle$ as a valid sequence…

One of the ideas proposed in the comments is to construct a graph where vertices are integers of $\[\\!\[0,k-1\]\\!\]$ and edges are dominoes of $S$ (domino $\langle a , b\rangle$ is an edge between $a$ and $b$, possibly a loop if $a = b$). The question is now equivalent to finding a longest path in this graph. The problem is that it is not similar to longest path problem because the path are not necessarily simples (meaning a path can cross the same vertex multiple times). One would need to keep track of used edges to find the longest path, so it does not really simplify the problem.

The problem is difficult and seems even $NP$-hard, but I still want to find an efficient algorithm solving it. My current backtracking solution find the answer for $k = 20$ and $N = 30$ in 10 sec (for a randomly generated set of distinct dominoes), but it increases quickly if I lower the value of $k$ or increase the value of $N$ (even $k = 15$ and $N = 30$ is taking ~30 minutes).

# Answer
> 3 votes
Your problem is NP-hard. Consider an instance of Hamiltonian path graph $G=(V,E)$ in which the degree of each vertex is at most $3$ and we are given a starting vertex $s$ and ending vertex $t$ both of degree at most $2$ (the problem remains hard in this case). W.l.o.g., let $V=\\{3,\dots,k-4\\}$, $s=3$, and $t=k-4$.

Create the dominoes $(0,1)$, $(1,2)$, $(2,3)$, $(k-4, k-3)$, $(k-3, k-2)$, and $(k-2, k-1)$. Create one "edge" domino $(a,b)$ for each edge $(a,b) \in E$.

There exists an Hamiltonian path in $G$ if and only if there is a sequence of $k-1$ dominoes. Indeed, notice that any sequence of dominoes that only uses the dominoes from $E$ traces a (not-necessarily simple) path $P$ in $G$. But then, all vertices except the endpoints of $P$ must be traversed at most once (since their degree is at most $3$). The two endpoints can extend the path by at most $2$. Then the number of edges of $P$ can be at most $|V|+1 = k-6+1 = k-5$. This implies that a sequence of $k-1$ dominoes must use all "non-edge" dominoes, i.e., the sequence of dominoes must start with $(0,1), \dots, (2,3)$ and end with $(k-4, k-4), \dots, (k-2, k-1)$. Then, the path induced by the sub-sequence obtained by dropping the "non-edge" dominoes must be simple and traverses $k-1-6 = k-7 = |V|-1$ edges of $G$, i.e., it is an Hamiltonian path in $G$.

Conversely, we can create a sequence of $\ell+6$ dominoes from any simple path of length $\ell$ from $s$ to $t$ in $G$ (simply prepend $(0,1), \dots, (2,3)$ and append $(k-4, k-4), \dots, (k-2, k-1)$). For an Hamiltoniam path we have $\ell=|V|-1=k-7$, therefore the sequence has length $k-1$.

# Answer
> 2 votes
Regarding each given domino as an edge in a graph connecting the vertices labelled from $\[\\!\[0, k-1\]\\!\]$, with "doubles" $\langle j,j\rangle$ handled separately, we need to answer:

* is the graph connected? In general this will be an easy question because most cases will have a much smaller number of vertices than edges. If the answer is "no", the problem sub-divides into the connected components of the graph.
* how many vertices of odd degree are there? This determines the existence of a Eulerian path and so whether all dominoes in the current problem can be included, or otherwise gives initial information to assess which dominoes may need to be excluded. If there are zero or two odd-degree vertices, a Eulerian path is possible and all dominoes can be used.
* for the case where a Eulerian path is not possible, we need to find short paths that link together odd-degree nodes *whose removal will not disconnect the graph* (but see extra note). These would constitute the dominoes that are not going to be used; the shortest paths that connect pairs of odd-degree nodes (allowing two such to remain) give the dominoes to set aside.
Example adjustment, showing odd-degree nodes in gold and removed edges in red:

Either as given or as adjusted by removal, a Eulerian path can found using e.g. Hierholzer's algorithm

Handling doubles: These can be kept as a separate list; they are included if there is any other connection to that value (vertex). If consideration is made of which dominoes to ignore, if a double is attached to a node that otherwise has only degree one, this could change the optimum set of dominoes to exclude since the double would also then be unused.

---

Extra note: finding the paths that connect the odd-degree nodes may not permit keeping the graph connected in some cases, even limiting that to a substantial disconnection (more than just leaving an isolated node), especially if the edges (dominoes) are relatively few and the vertices (values) many. Finding bridges in the graph would allow detection of this case; these can be found in linear time. Example graph:

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


# Question
Title: Are regular grammar languages defined from "accepting" states?
In a transition diagram, the language L(D) where D is the diagram is defined as all the words that are formed from following an "accepting" walk. Does the same apply for languages of regular grammars too? They are defined by using 4 sets (terminal, non-terminal, initial non-terminal, rules) so there is no such thing as "accepting states" at the definition. The language of a regular grammar are the words that can be produced from that grammar, but do they always end in an "accepting" state?

# Answer
> 1 votes
Your question confuses automata and grammars.

Grammars do not have states.

Grammars generate words by substituting substrings in words to form other words according to the grammar's rules. So instead of ending up in a state you end up with a word.

The all-terminal words (i.e. containing no nonterminals) among those are defined to be the words the grammar generates.

So a word being all-terminal is equivalent to a state being accepting. Another notion of acceptance for grammars would be superfluous.

# Answer
> 0 votes
There is a one-to-one correspondence between NFAs and right regular grammars without productions of the form $A \to a$.

Given a right regular grammar with productions of the form $A \to aB$ and $A \to \epsilon$ and starting symbol $S$, create an NFA in which:

* The states are all nonterminals.
* The initial state is $S$.
* A state $A$ is final if there is a production $A \to \epsilon$.
* There is an edge labeled $a$ from $A$ to $B$ if there is a production $A \to aB$.

This NFA accepts the same language as the grammar.

You can also easily carry out the transformation in the other direction.

This shows that in the absence of rule of the form $A \to a$, the analogs of accepting states are nonterminals with productions of the form $A \to \epsilon$.

We can replace a production $A \to a$ by a pair $A \to aX$, $X \to \epsilon$, where $X$ is a nonterminal which is common to all such productions, but doesn't appear anywhere else. We can think of $X$ as the accepting sink. A production $A \to a$ signifies a possible transition to the accepting sink.

---
Tags: complexity-theory, regular-languages
---


# Question
Title: Why LL(1) grammar generate all regular languages?
I came across following:

> Every regular language has right linear grammar and this is LL(1). Thus, LL(1) grammar generates all regular languages.

I tried to get that.

**Definition: Right linear grammar (RLG)**
In right linear grammar, all productions are of one of the following forms: $A\rightarrow t^\*V$ or $A\rightarrow t^\*$, where $A$ and $V$ are non terminals and $t$ is terminal.

**Definition: LL(1) grammar**

A grammar $G$ is $LL(1)$ grammar if and only if whenever $A→α|β$ are two distinct productions of $G$, the following conditions hold:

1. For no terminal $a$ do both $α$ and $β$ derive strings beginning with $a$.
2. At most one of $α$ and $β$ can derive the empty string.
3. If $β⇒^\*ϵ$, then $α$ does not derive any string beginning with a terminal FOLLOW(A). Likewise, if $α⇒^\*ϵ$, then $β$ does not derive any string beginning with a terminal in FOLLOW(A). ($β⇒^\*ϵ$ means $B$ derives $\epsilon$)

**(Q1.)** How definition of RLG ensures condition 1 in the definition of LL(1) grammar.

This answer says:

> All regular languages have LL(1) grammars. To obtain such a grammar, take any DFA for the regular language (perhaps by doing the subset construction on the NFA obtained from the regular expression), then convert it to a **right-recursive** regular grammar. This grammar is then LL(1), because any pair of productions for the same nonterminal either start with different symbols, or **one produces ε and has $ as a lookahead token**.

**(Q2.)** I read somewhere "eliminating left recursion from given grammar does not necessarily make it LL(1)". Then how turning grammar to right recursive will ensure its LL(1) (as stated in above quoted answer)?

**(Q3).** I didnt get the significance of "one produces ε and has $ as a lookahead token" in above quoted answer.

**(Q4.)** First quote in this question says right linear grammar is LL(1). How is it so?

**(Q5.)** This answer says "all regular languages have a LR(0) grammar", I guess its incorrect as LR(0) are DCFLs with prefix property which are not superset of regular languages. Am I right with this?

# Answer
> 5 votes
The quoted answer does not claim that every right regular grammar is LL(1). That statement would not be true.

What the answer claims is that the grammars produced by the indicated algorithm are LL(1). That statement is correct.

So, no-one is saying "every right-linear grammar" satisfies condition 1 (of the LL(1) definition) (your Q1). They don't all do so.

Alos, no-one is saying that just removing left-recursion is sufficient to guarantee LL(1) (your Q2). It isn't.

Finally, no-one is saying that every RLG is LL(1) (your Q4), not even the unattributed quote which starts your question. That quote says that every regular *language* has at least one RLG which is LL(1). Regular languages have many RLGs, and often not all of them are LL(1). These other RLGs are not relevant to the claim that all regular languages are LL(1).

That leaves your Q3, which is really about how to demonstrate the RLG produced by the algorithm satisfies conditions 2 and 3.

It's clear why that particular RLG passes condition 1. The algorithm starts with a DFA, and the DFA has only one out-transition on each symbol, by definition. One production is generated for each out-transition, whose first symbol is the out-transition's symbol. So it's not possible for two productions starting with the same symbol to be generated for the same state (= non-terminal).

Now, under what circumstances does the algorithm produce productions which derive $\epsilon$? Answer: these productions are generated for final states. @templatetypedef wrote the quoted answer thinking about the augmented grammar/language, in which every sentence ends with an end-marker `$` which does not appear elsewhere. \[Note 1\]

Instead of augmenting the grammar or writing the LRG as implied by the cited answer, we could invent a new state `F` with no out-transitions on any symbol. We then add the production $A\to F$ to every final state $A$. And we add the production $F\to\epsilon$.

Now condition 2 is met becaus the only unit productions in the grammar are $A\to F$, so no non-terminal derives $\epsilon$ in any way other than directly through $F$. And condition 3 is met rather trivially because $FOLLOW$ of every non-terminal is empty, so no terminal is in any $FOLLOW$ set.

Since conditions 1, 2 and 3 are verified, we know that the grammar produced by converting a DFA is necessarily LL(1).

---

### Notes

1. This augmented language is prefix-free, since all sentences end with the endmarker. Also, as we'll see, the augmented grammar produced by the algorithm is LL(1) and therefore deterministic. A deterministic prefix-free language is LR(0), which might explain the error you refer to in your Q5. The original unaugmented grammar is not necessarily prefix-free, and therefore might not be LR(0) although it is still LL(1). This is an illustration of why augmented grammars are useful.

# Answer
> 0 votes
Let's consider a restricted type of right-regular grammar: all rules must be of the form

* $X \rightarrow yZ$
* $X \rightarrow \epsilon$

Such a grammar directly corresponds to a nondeterministic automaton:

* the nonterminals correspond to states
* the start symbol corresponds to the initial state
* the $\epsilon$-rules corresponds to the state being accepting
* the other rules corresponds to transitions
* the grammar generating a word corresponds to the automaton accepting that word

It is a special kind of nondeterministic automaton: one in which all transitions are on single symbols; no $\epsilon$ transitions.

It is a 1 to 1 mapping: every such automaton corresponds to such a grammar.

Such a grammar is LL(1) if and only if its corresponding automaton is deterministic. Once again, the correspondence is 1 to 1: every deterministic automaton corresponds to such a grammar.

We know deterministic automata can accept all regular languages. Hence, LL(1) right-linear grammars (of this restricted type) can generate all regular languages.

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


# Question
Title: Any problem in P can be reduced to the language of odd integers
Given $A=\left\\{n\in \mathbb{N} \mid \text{$n$ is odd}\right\\}$, we want to prove that if $S \in P$ then there is a Karp reduction from $S$ to $A$.

My attempt: If $S \in P$ we can solve $S$ with a reduction that converts in polynomial time an input from $S$ to $A$, but I don't know how to prove formally the function and to show that the function is a reduction.

# Answer
Let $S$ be any language in $\mathsf{P}$. You are looking for a function $f$ with the following properties:

* $f$ can be computed in polynomial time.
* If $x \in S$ then $f(x) \in A$.
* If $x \notin S$ then $f(x) \notin A$.

Since $S$ is in $\mathsf{P}$, we can determine whether $x \in S$ in polynomial time. Therefore, the reduction $f$ can work as follows:

1. Determine whether $x \in S$.
2. If $x \in S$ then output something in $A$.
3. If $x \notin S$ then output something not in $A$.

You take it from here.
> 2 votes

---
Tags: complexity-theory, reductions, np, polynomial-time-reductions
---


# Question
Title: Regular expression for words longer than 2 containing at most two x-s
I want to make a regular expression for the language consisting of words whose length is at least 3 and which contain at most two $x$'s, that is,
$$\\{w\in \\{x,y\\}^\* \mid |w|\geq3\text{ and the number of }x\text{'s in }w \text{ is at most } 2\\}$$

I wrote: $$ x^+(x+y)^+y^+ $$

# Answer
Your regular expression accepts the word $xxxy$, which contains too many $x$s.

We can break down words in your language into three different kinds:

* No $x$s, and so at least three many $y$s.
* One $x$. In that case, the word is of the form $y^ixy^j$, with $i+j \geq 2$. This means that either $i = 0$ and $j \geq 2$, or $i = 1$ and $j \geq 1$, or $i \geq 2$. 0 Two $x$s. In that case, the word is of the form $y^ixy^jxy^k$, with $i+j+k \geq 1$. This means that either $i=j=0$ and $k \geq 1$, or $i=0$ and $j \geq 1$, or $i \geq 1$.

Putting everything together, we reach $$ yyy^+ + xyy^+ + yxy^+ + yy^+xy^\* + xxy^+ + xy^+xy^\* + y^+xy^\*xy^\*. $$ As a bonus, this regular expression is "unambiguous", in the sense that each word belongs to exactly one summand.

We can shorten this expression in many ways. For example, notice that if we consider only words with exactly two $x$s, we can obtain all words in the language by optionally replacing an $x$ with a $y$. This gives us the simpler expression $$ (x+y)^2y^+ + (x+y)y^+(x+y)y^\* + y^+(x+y)y^\*(x+y)y^\*. $$ If we want something more symmetric, we can take $$ y^+(x+y)y^\*(x+y)y^\* + y^\*(x+y)y^+(x+y)y^\* + y^\*(x+y)y^\*(x+y)y^+. $$
> 0 votes

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


# Question
Title: Does NP-hard problems have to be decision problems? (What the fact please) (contradicting answers)
Let me explain my trouble by another example.

The wiki page says that

> Lattice problems are an example of NP-hard problems

However, by clicking NP-hard, i find this definition

> A decision problem H is NP-hard when for every problem L in NP, there is a polynomial-time many-one reduction from L to H.

What the fact? Lattice problems are not decision problems.

**Edit after two answers:** I think the two answers below have contradicting definitions:

> 1-)An optimization problem is NP-hard if it is as hard as NP-hard decision problems.

> 2-) An optimization problem is NP-hard if its decision version is NP-hard.

Which one is the real definition.

# Answer
In complexity theory, we often concentrate on decision problems. "Officially," NP-hardness is a category of decision problems — only a decision problem can be (or not be) NP-hard.

However, it is also common to use NP-hardness when referring to *optimization* problems. An optimization problem is NP-hard if its decision version is NP-hard.

In more advanced complexity theory, NP-hardness is used in a less precise way. For example, this paper "give\[s\] a new proof showing that it is NP-hard to color a 3-colorable graph using just four colors". They also prove that it is NP-hard to distinguish graphs of type A from graphs of type B (see their Theorem 3). What they really mean, in the former case, is that for any problem $L$ in NP there exists a polynomial time reduction $f$, outputting a graph, such that if $x \in L$ then $f(x)$ is 3-colorable, and if $x \notin L$ then $f(x)$ is not 4-colorable.
> 3 votes

# Answer
Now that you have edited your post, your question is more clear ('cause let's be honest, it was very confusing before the modifications…)

By definition, problems in $NP$ are decision problems. However, $NP$-hard problems are not necessarily in $NP$ and even not necessarily decision problems.

Let's make an example of this. Consider the following decision problem:

Clique – Input: a graph $G$ and an integer $k$; Question: is there a subgraph of $G$ that is a clique of size $k$?

It is well known that Clique is a decision problem in $NP$ (and even $NP$-complete). Consider now the following optimization problem:

max-Clique – Input: a graphe $G$; Maximize: the size a subgraph $H$ of $G$; Conditions: $H$ is a clique.

Now we will prove that max-Clique is $NP$-hard, despite not being a decision problem. Indeed, if you know how to solve max-Clique, then given a graph $G$ and an integer $k$, you can solve Clique$(G, k)$ by running max-Clique$(G)$ and verifying if the result is greater than $k$ or not. This is done in an additionnal polynomial time. That proves that Clique $\leq\_m^p$ max-Clique. Since Clique is $NP$-complete, we conclude that max-Clique is $NP$-hard.
> 1 votes

---
Tags: np-complete, np-hard, np, decision-problem, p-vs-np
---


# Question
Title: Plain-language example of how a functional style makes parallel programming easier
I read a few "function \>\> imperative/OOP" articles because I heard there was a move in imperative OOP languages toward a functional style of coding, especially encouraging pure functions when possible. One recurring argument is that by not mutating state, you don't have to worry about race conditions and locking.

I do get the logic behind that: no two processes would mutate the same data, so locking and race conditions are irrelevant. Problem is I hadn't done any parallel programming or know any functional languages, so it's hard for me to really understand. I got as far as reading about persistent data structures as replacements for large mutable structures, but I hit a wall. I'm looking for an example, in plain language, of a parallel algorithm in an imperative style and a functional style that illustrates this recurring argument.

If it helps to provide a programming problem, let's say I have an array of integers (`A`). People submit commands (`A[i] += 1`) in real time to increment an element of that array by 1 (at a valid index `i`). Different elements are intended to be incremented in parallel. I can imagine the imperative solution does this but it locks an index during an increment. What would a functional solution look like? I will accept answers as simple as naming a functional data structure, if I could understand it by looking it up.

# Answer
Functional programming is great for parallel programming that is *not concurrent*. The example problem you gave is inherently concurrent, but we can make it non-concurrent by "batching" the work that needs to be performed.

The batch form of the problem you suggested is like this. **Input**: length of desired array, and collection of indices to increment. **Output**: array where at each index we've summed up the number of times that index appears in the input. For example, for an array of size 4 and indices `[1,0,1,1,0,0,0,3,0,1]`, the output should be `[5,4,0,1]` because 0 appears 5 times, 1 appears 4 times, etc.

An imperative solution is exactly like you suggest (I'm using Python code just for pseudocode):

```
# n is size of resulting array
def ImperativeCountIndices(n, indices):
  A = [0 for i in range(n)]
  for i in indices:   # do this step in parallel
    A[i] += 1         # this has to be atomic!!
  return A

```

In contrast, a functional approach is as follows. The high level idea is to work with dictionaries mapping indices to values. Then we sum the values of each index by merging dictionaries.

```
from functools import reduce

def mergeDicts(d1, d2):
  allkeys = set(d1.keys()).union(d2.keys())
  return {k: d1.get(k, 0) + d2.get(k, 0) for k in allkeys}

def FunctionalCountIndices(n, indices):
  d = reduce(mergeDicts, map(lambda i: {i: 1}, indices))
  return [d.get(i, 0) for i in range(n)]

```

The `mergeDicts` function might look expensive, but actually if you use binary search trees you can make this function extremely efficient and highly parallel (see e.g. https://arxiv.org/abs/1602.02120). The `reduce` and `map` functions are great examples of a fundamental "functional programming primitives" which are highly parallel.

The great thing about the functional approach is that we don't have to worry about potential data races. The behavior of the functional code is exactly the same every time you execute it.
> 3 votes

# Answer
I'm not sure functional programming does make parallel programming any easier, when taken in the round.

If you program in a "functional style" (including all so-called good practices), then converting certain steps of a serial program to parallel execution (and getting results that are equivalent to the serial execution) may not usually involve much further difficulty, but that is primarily because all the difficulty has already been imposed in drafting the program in a form where it doesn't matter whether many steps are executed serially or in parallel.

Moreover, functional programming does not claim to guarantee that a serialised execution of a program actually produces "correct" (i.e. intended) results for all inputs, only that parallelised execution will involve *no additional error*.

In general, business systems have an irreducible need to mutate state and shared data, so any benefit or guarantee that depends in theory on not mutating state at all, can be dismissed out of hand as almost worthless to real-world development.

If the point at which state is mutated is seen as a boundary across which the guarantees of functional programming cease to apply, then the vast majority of programs can get almost nothing done before having to cross a boundary and step outside such guarantees.

Many people seem to over-estimate how much error actually occurs in systems due to race conditions etc. involving unnecessary mutations, rather than errors which involve the necessary mutations of shared data that must occur equally in functional programs as in non-functional ones.

Arguably, a real benefit of functional programming is that it allows certain kinds of functionality (especially complex calculations) to be implemented more quickly or to a more complex extent, at the price of a higher initial learning curve.

In other words, it will allow the best programmers to work a little faster once experienced, or get a little further than before with the most complex systems, at the expense of requiring far more training and experience to begin with, and excluding third-rate programmers from getting anywhere at all.

This, however, is not the typical understanding people have of the word "easier", or of a tool that "makes things easy". I contend that functional programming may improve productivity in some cases, but it does so by *increasing* the threshold of difficulty in many respects.
> 2 votes

---
Tags: functional-programming, parallel-computing, imperative-programming
---