How can I show that this language is context sensitive? I have this language $L=\{a^nb^nc^n,n\geq0\}$, I know this language is not context free, but I don't know how to show that it is context sensitive, do I have to use a PDA?

In the same way that DFAs are the counterparts for regular expressions and PDAs are the counterparts for context free languages , the counterpart for context sensitive languages are LBAs (linear bounded Automaton)
That is to say that a language is context sensitive iff some LBA recognises it
But what are LBAs ?
Hopefully you have an idea about what Turing Machines are , an LBA is basically a Turing machine with limited memory , unlike Turing Machines which can access the entire infinite tape , the LBAs computation is restricted to the part of the tape which contains the input , thus the head can only operate in the part of the tape containing the input (hence bounded) , an Alternative less stricter definition is that only a finite contiguous portion of the tape, whose length is a linear function of the length of the initial input, can be accessed by the read/write head (hence linear) , in this way you can imagine the LBA as having a tape of length kn , where n is size of input and k is a constant associated with the machine
Now can we use an LBA to recognise L ?
Let M be an LBA :
M on input w :

Read the first symbol make sure it is an a , else reject ( since n≥1 we can't accept the empty string)

Read the entire string and make sure it follows the right order as , then bs then cs then ds else reject

move the head to the left end of the tape then start crossing an a then a b then a c then a d

Repeat 3 till all as are crossed , when crossing symbols if M finds that w fell short of some symbol (ex: all bs are crossed but we need to cross a b) reject

after all as are crossed read the entire input if there remain any uncrossed symbols reject

else Accept

Clearly M is an LBA that recognises L , thus L is a context sensitive language
Notice how M uses only finite memory , in this example using only the portion of the tape where the input is written is enough to recognise L


How fast can we compute the size of maximum matching in an unweighted bipartite graph? Is there a way to compute the size of a maximum matching
in an unweighted bipartite graph
more efficiently (e.g. faster) than computing a maximum matching?

It is a long shot but
it is often an interesting problem to avoid throwaway computations like these.

Motivation
The problem I am trying to solve is match-2
where the two sets are of different sizes.
I need to determine whether there is a matching
that covers all the vertices from the smaller set.
Knowing the size of the maximum matching
would let me check if it is is equal to or
smaller than the size of the smaller set
(if such a thing is possible then whenever the result is
"yes, there is a matching that covers the small set"
you would effectively know what its size is but only in that case),
but that is not strictly necessary:
if there is a way to compute the answer without computing the size
it is good for me.

I believe the best algorithm known is Hopcroft and Karp, "An $n^{5/2}$ Algorithm for Maximum Matchings in Bipartite Graphs", SIAM Journal of Computing 2:4 (1973), pp 225-231.


Lower bound on size of proof that a list of integers is sorted Suppose we have a list of unbounded integers, written in binary, and we want to write a (formal) proof that the list is sorted in ascending order.

Such a proof might look (informally) like: "2 < 3, and 3 < 5, and ... and 71 < 79, so the list is sorted."

It would seem such a proof must have length $\Omega(n)$ where $n$ is the length of the list of integers, as you could use the same kind of argument that is used to show that comparison sorting is $\Omega(n \log n)$; roughly, if the proof was any shorter than $n$, it would have missed one of the integers on the list.

Is this the case, or have I missed something?  Is there a clever way to construct an asymptotically shorter proof?

Edit: As Gilles and Yuval Filmas point out below, a specific answer can only be given if we have some constraints on the language in which the formal proof is written.  For the purposes of this question, suppose that no matter what particular proof language is used, the proof must be written such that it can be verified in time at most polynomial in the length of the proof.  This excludes proofs of the form "for all elements of the list, ..."  (I realize this constraint may make the question more difficult than if a particular proof language was chosen, but it really is closest to what I was thinking when I asked the question.)

When talking about proofs, you need to explain three things: (1) formal proof system, (2) what you want to prove, (3) what you want to prove it from.

You seem to imply that item 3 should be $n$ different axioms, listing the contents of the array. In that case, you're right that you will need to invoke all axioms to prove that the list is sorted, in any consistent formal system.

Another reason why the proof will need to be of linear length is that item 2, what you want to prove, might be stated as $A[1] \leq A[2] \land A[2] \leq A[3] \land \cdots \land A[n-1] \leq A[n]$.

However, perhaps it is the case that item 3 is a description of the algorithm, and item 2 is something similar to Gilles's formulation, $\forall i \in [n-1], A[i] \leq A[i+1]$. In that case, if the proof system is strong enough (say ZFC), then you should be able to prove item 2 in $O(\log n)$ by starting with a general correctness proof for your algorithm, and then invoking it for your particular $n$. If your proof system is too weak to prove something like that, you might still be able to prove that the array is sorted in $O(\log^{O(1)})$; the relevant subject is known as bounded arithmetic.


Find all polygons from a set that overlap a given polygon (convex case) Problem:  Given a set of $N$ non-overlapping convex polygons $\{S_i | 1\leq i\leq N\}$ defined by their vertex coordinates $(x,y)$ and a convex polygon $P$, also defined by its vertex coordinates, find all polygons $S_i$ that overlap with $P$.  Assume an algorithm to test whether a pair of polygons overlap already exists.

Constraints:  We are allowed to perform operations of $O(N \log N)$ on $\{S_i\}$ without knowledge of $P$ (initialization step).  After that, given an arbitrary $P$ the algorithm should perform in approximately $O(\log N)$ time when $S$ consists of polygons of uniform size.  Hence, an algorithm that just tests $P$ against every $S_i$ will be rejected.

Solution idea:  On initialization, insert all vertices of the polygons of $\{S_i\}$ into a kd-tree $K$ and associate each vertex with its associated polygon.  Store the diameter $dS$ of the largest polygon in $\{S_i\}$.  Then given a polygon $P$, calculate the diameter $dP$ of $P$.  Find all vertices in $K$ that are no farther than $\max(dS,dP)/2$ (?) from any vertex in $P$.  Test $P$ against only faces that contain the vertices in $K$.

Since lookup in $K$ is a $\log(N)$ operation, then if $N$ is large and $dP$ is approximately equal to dS then the number of tests should be $<< N$.

Any other solution ideas?  Google is yielding nothing of value.

Similar to How to find polygons overlap reign but with additional constraints.

Suppose all the polygons $S_1,\dots,S_n,P_1,\dots,P_n$ are given in advance.  Then I can propose an algorithm that might often be efficient in practice (though it can degenerate to quadratic-time behavior if you get a sufficiently nasty configuration of polygons).

In particular, the polygon $P_i$ overlaps with some $S_j$ if and only if:

(1) some line segment of the perimeter of $P_i$ crosses some line segment of the perimeter of $S_j$; or,

(2) some vertex of $P_i$ is inside $S_j$, or some vertex of $S_j$ is inside $P_i$.

So, it suffices to check both conditions separately.

Crossings between perimeters

You can check find all crossings between the perimeters of the polygons as follows.  Decompose the perimeter of each polygon $P_i$ into a collection of line segments.  Do the same for each $S_j$.  Then, use the Bentley-Ottmann algorithm (or some other similar algorithm) to find all crossings between these line segments.  This will tell you, for each $P_i$, whether its perimeter crosses any of the $S_j$ perimeters.  If it does, then you know that $P_i$ has an overlap with some $S_j$.

The running time will be $O((n+k) \log n)$, where $k$ is the number of crossing between these line segments.  In practice, you can hope that $k$ won't be too large (it probably often will be fairly small, unless you get really unlucky with how the polygons are arranged).

Vertex inside a polygon

So we have a bunch of polygons, and a bunch of points.  I suggest using the Bentley-Ottman sweepline algorithm on the line segments corresponding to the perimeters of the polygons.  In addition to an "event" happening at each two intersection between two line segments and at each endpoint of each line segment, create another event at the location of each point.  In addition to a binary search tree storing the locations of the line segments that intersect the sweepline, also use an interval tree to store an interval for each polygon that intersects the sweepline (namely, the range of $y$-coordinate values where the sweepline intersects that polygon).  Now, when you hit an event corresponding to a point, you can check which intervals in the segment tree contain that point, i.e., which polygons contain that point, using a stabbing query.

By using self-balancing trees, you can arrange that each step of this algorithm can be done in $O(\log n)$ time.  Thus, the total running time will again be $O((n+k)\log n)$.

Online queries?

The above describes how to solve your problem in "batch mode", where all polygons are given in advance.  What if only $S_1,\dots,S_n$ are given in advance and the $P_i$'s are provided one at a time, and we have to check for overlap in an online fashion?  I don't know how to handle that.

I might be able to get you started on an idea for half of it, but I don't see how to flesh it out into a full algorithm.  For part of it, I think it might be possible to do something for that case as well, using partially persistent data structures.

Apply the sweepline algorithms above to the polygons $S_1,\dots,S_n$, and store all copies of the binary tree and interval tree at each event.  Naively, this would require $\Omega(n^2)$ space (since there are $\Omega(n)$ events and each tree is $\Theta(n)$ in size), which is horrible.  Fortunately, each tree differs from the previous tree by only $O(1)$ modifications.  Therefore, we can use a persistent data structure to store all of the trees, using standard path copying techniques, and in that way we'll be able to store all of the trees in $O((n+k) \log n)$ space.  Moreover, if we keep an array of all of the roots of these trees, then given any x-coordinate, we'll be able to look up the appropriate tree for that x-coordinate in $O(\log (n+k))$ time using binary search.

Given a polygon $P_i$, we'll first look up each vertex of $P_i$ in this data structure to see if it is contained in any of the $S_j$'s.  This can be done by taking each vertex, looking up the Bentley-Ottman trees for the x-coordinate of that vertex, and looking up the y-coordinate of that vertex in the interval tree to see if any of the $S_j$s contain it.

Next, we need to go through each line segment in the perimeter of $P_i$ and check whether it intersects any of the line segments of the $S_j$'s.  However, I don't know how to do this in a way that supports online queries for the $P_i$'s.  So, that's the part you'd need to find a way to fill in.


Change the structure from 3SAT to 1in3 3SAT There is a variable set V = {x1,x2,x3} and clause set C1={x1,x2,-x3} C2={x1,-x1,-x2} C3={-x1,-x2,x3} C4={x2,x3,-x3}. For this structure, no matter each variable is positive or negative, the clause can always be TRUE by at least one literal is TRUE within each clause, just like 3SAT.
How can I change the variable gadgets and clause gadgets to make it no matter each variable is positive or negative, the clause can always be TRUE by only one literal is TRUE within each clause, just like 1 in3 3SAT?

A 1-in-3 SAT clause (A,B,C) can be expressed with the following 5 clauses in 3SAT.

$(A ∨ B ∨ C) $

$(A ∨ \overline{B} ∨ \overline{C}) $

$(\overline{A} ∨ B ∨ \overline{C}) $

$(\overline{A} ∨ \overline{B} ∨ C) $

$(\overline{A} ∨ \overline{B} ∨ \overline{C}) $

Why? Consider the truth table over A,B,C.

| A | B | C |   | A | B | C |
| 0 | 0 | 0 |   | --------- |
| 0 | 0 | 1 |   | 0 | 0 | 1 |
| 0 | 1 | 0 |   | 0 | 1 | 0 |
| 0 | 1 | 1 |   | --------- |
| 1 | 0 | 0 |   | 1 | 0 | 0 |
| 1 | 0 | 1 |   | --------- |
| 1 | 1 | 0 |   | --------- |
| 1 | 1 | 1 |   | --------- |

There are 8 lines. Each clause eliminates 1 line. We only want to allow (0,0,1), (0,1,0), (1,0,0) and eliminate the others.


Is destructuring a heap (taking down a heap) also O(n) like building a heap? If so, can the selection problem be solved by this method in O(n) time? If we can build up a heap with time O(n), can we take down a heap also by O(n)? (by delete-max repeatedly).

Intuitively, it may feel it is, because it is like the reverse of build it up.

(Building a heap can be O(n) -- in Wikipedia).

If building a heap is O(n) in the worst case, including the numbers are all adding by ascending order, then taking the heap down is exactly the "reverse in time" operation, and it is O(n), but this may not be the "worst case" of taking it down.

If taking down a heap is really O(n), can't the selection problem be solved by building a heap, and then taking it down (k - 1) time, to find the kth max number?

Delete-max is $O(\log n)$, so you have $O(n) + k O(\log n)$ which is $O(n)$ for fixed $k$. But if $k$ is not fixed, it can be up to $\frac{n}{2}$ (if it's greater, just use a min-heap instead of a max-heap), and  $O(n) + \frac{n}{2} O(\log n) = O(n \log n)$.

In fact, if there was some tricky way to do what you want, you would solve sorting in $O(n)$, not just selection, which is known to be impossible.


Creation of skip list: Las Vegas or Monte Carlo? I have come across this video on skip lists:
https://www.youtube.com/watch?v=UGaOXaXAM5M
Clearly, the creation of skip-list from a sorted singly linked list is a randomized algorithm.
But I am confused: is it a Las Vegas algorithm or a Monte Carlo algorithm?
I feel it is a Monte Carlo algorithm since there is a possiblity of an incorrect output(degenerate case where every node is in every level), and if we don't maintain a checking condition, we won't know where the algo went wrong.
Am I correct?
P.S. My first question here.

The difference between a Las Vegas algorithm and a Monte Carlo algorithm is that a Las Vegas algorithm is always correct but its running time may be large with small probability, whereas a Monte Carlo algorithm always has the same time complexity but may give wrong results with small probability.
These definitions are more appropriate for decision problems and optimization problems, and less for data structures. That said, they still make sense for data structures. Here are two examples:

Skip-lists correctly implement the list abstract data type. They are efficient with high probability. This is like a Las Vegas algorithm.
Bloom filters are always efficient (in this case we care about space complexity), but may give wrong results to queries. This is like a Monte Carlo algorithm.

Most data structures are designed with the Las Vegas objective in mind.


If there is an algorithm $A$ that guesses the entire message, given an encryption, with probability of $0.2$, then it's not $(O(A) +O(n), 0.1)$-secure Let $(E,D)$ be a cipher with message space $M = \{0,1\}^n$ and key space $K = \{0,1\}^n$.
Assume that there is an algorithm $A\colon \{0,1\}^n \to \{0,1\}^n$ of size $T$ that given an
encryption of a message can guess the entire message with probability $0.2$. Namely, for a message $m \in M$  it satisfies $$P[A(E(k,m)) = m] = 0.2$$
I want to prove that $(E,D)$ is not $(T + O(n), 0.1)$-secure.
A cipher $(E,D)$ is called $(T + O(n), 0.1)$-secure if for every two messages $m_1, m_2 \in M$ and every algorithm $B\colon \{0,1\}^n \to \{0,1\}$ of size at most $T + O(n)$, it follows that:
$$| P[B(E(k,m_1)) = 1] - P[B(E(k,m_2)) = 1] | \le 0.1$$
My idea was to assume on the contrary that $(E,D)$ is $(T+O(n), 0.1)$-secure, and then find an algorithm $B\colon \{0,1\}^n \to \{0,1\}$ of size $T+O(n)$ that uses $A$ to break this encryption.
Namely I need to show that for any two messages $m_1, m_2 \in M$ it satisfies:
$$| P[B(E(k,m_1)) = 1] - P[B(E(k,m_2)) = 1] | > 0.1$$
Basically I need to describe such $B$ and two messages $m_1, m_2$ that satisfy this inequality.
My idea was to pick two random messages $m_1, m_2 \in M$. Then, somehow use $A$ to get the probability $P[B(E(k,m_1)) = 1] = 0.2$, and use randomness somehow to get the probability $P[B(E(k,m_2)) = 1] = 0.2 \times 0.5 = 0.1$
However, I don't really know how to do that.
Help or some hint would be very appreciated!

Let $m_1$ be an arbitrary message. We are guaranteed that $P(A(E(k,m_1)) = m_1) = 0.2$. Averaging over all other messages, there is some message $m_2$ such that $P(A(E(k,m_1)) = m_2) \leq 0.8/(2^n-1) \leq 2^{-n}$.
Consider the following algorithm $B$: on input $x$, if $A(x) = m_2$ then output $1$, else output $0$. By assumption, $P(B(E(k,m_1))=1) \leq 2^{-n}$, whereas $P(B(E(k,m_2))=1) = 0.2$. When $n \geq 4$, the difference between the two probabilities is larger than $0.1$.


Find offset and page number given paged virtual memory address I ran into this question in class:
Assume a machine that is 64-bit and has 8GB memory. They use a paged virtual memory where the page size is 4KB. You run the following program:
int main() {
   int *ptr = malloc(16);
   printf("%p\n", ptr);
   return 0;
}

and get output:
0x555555756260
We're to find the virtual page number of the address and the offset.
What I'm thinking is that I first convert that to binary, figure out how many bits and which bits represent the address/offset.
But I'm not sure how to figure out the latter. How can I determine which bits in the address correspond to which?
I'd really love some guidance

assume address printed out to be a "byte address"
guess whether the offset to find is addressable unit in page or byte in page

if addressable unit in page, figure out its size
with nothing more than 64-bit to go on a first assumption is 8 bytes

guess the representation wanted for virtual page number & offset

(Base conversions in the process depend on practice with the representations involved. For a result in hex, too, some would prefer to just double (word offset) or halve ("byte page#") "in hex". A coder might have a program print both parts before even considering if coding the task was least effort.)


If A is reducible to B and B is reducible to A, and A is NPC, is B also NPC? I was thinking about the max-clique problem and the k-independent set problem. You can show that k-independent set is reducible to max-clique easily and you can show that max-clique is reducible to k-independent set (with a simple for loop). And k-independent set is NPC, so wouldn't that mean max-clique is also NPC, but it's not because we can't create a verifier, so I'm terribly confused. What wrong assumption am I making?

First, note that there are two problems frequently called the "Maximum Clique Problem".

One of them is the Clique Decision Problem: given an undirected graph $G$ and a number $k$, does $G$ contain a clique with at least $k$ vertices? This is one of Karp's 21 Problems, the original list that made NP-completeness famous. The proof involved reducing to it from the Boolean Satisfiability Problem, the very first original NP-complete problem. And a verifier for this is easy to make: check whether the set given as a solution actually does contain $k$ or more vertices, and is actually a clique.

The other is the Maximum Clique Size Problem: given an undirected graph $G$, what is the size of the largest clique in $G$? This can be shown to be NP-hard by reduction from the Clique Decision Problem, by simply comparing the size of the largest clique with $k$. And as you mentioned, it can apparently be shown to be in NP by reduction to the Clique Decision Problem: for every integer from the number of vertices down to 1, check if there's a clique of that size, and if so return that number.

So it would seem that both versions of the problem are NP-complete. But be careful about the definition of NP. NP is defined as a class of decision problems, and the Maximum Clique Size Problem is not a decision problem.

Specifically, NP is the class of decision problems where, if the answer is yes, you can be given extra information of polynomial size that lets you verify that the answer is yes in polynomial time. (If the answer is no, you can't necessarily verify it, unless NP = co-NP.) So for problems which aren't answered with yes or no, trying to put them in NP just doesn't make sense.

So while the Maximum Clique Size Problem is indeed NP-hard, and can be reduced to an NP-complete problem in polynomial time, it is not in fact in NP. And thus it cannot be NP-complete. This is why you can't make a verifier for it (unless NP = co-NP, which is an open question).


Is there code below microcode? Which is the lowest level of code (human written instruction for computers) in computer architecture? After doing minor research, I have come to the conclusion that, as far as determining a hierarchy in terms of the level of computer code, the following is the general level of code hierarchy: High-Level->Low-level->Assembly->Machine Code->Micro Code.
Am I correct?
If I am correct, is there a level of code below Micro code?
Is hardware control (in logical gates and transistors) code?

Am I correct?

Not completely
It is wrong for 2 reasons:

Assembly code is just a human readable version of machine code. So the conversion process to assembly can be skipped if is not required. Unlike other codes, assembly directly corresponds to machine code. Assembly code is dependent on the Instruction Set Architecture of the machine. Converting to assembly is done by the assembler and it is optional. Machine code can be produced without the intermediate assembly code conversion step. As far as hierarchy is concerned, the assembly code and machine code are at the same level.
Machine code is not at a level above Micro code for 2 reasons:

Not all architectures are microcoded. So microcode is optional.
Microcode is independent of the machine code. Machine code corresponds to what the machine does. Micro code corresponds to how the machine does it. Machine code corresponds to the Instruction set. Micro code corresponds to the
micro architecture of the machine. 2 machines having different microcodes can utilize the same machine code if they share the same instruction set architecture.
In fact, Intel corporation sometimes updates the microcode of their processors to patch up vulnerabilities. This is called microcode update. Even after the microcode is updated, the processor can still utilize the same machine code, because the microcode is independent of the machine code. Machine code is not converted to micro code. Both microcode and machine code are sequences of bits. While microcode is optional, machine code is essential.

Is there a level of code below Micro code?

No.

Is hardware control (in logical gates and transistors) code?

No. Code is a sequence of instructions. Hardware is not a sequence of instructions. Hardware is fixed. Code can be modified. Hardware control cannot be reprogrammed, software control can be reprogrammed.


How can I keep track of the state of a sequence after rotating parts of it multiple times? Given a sorted array

1 2 3 4 5 6 7 8

and an operation that takes the N-th element out the array and puts it in front (or rotates the first N elements to the right by one), leaving the following for N = 3

4 1 2 3 5 6 7 8

I need to be able to figure out the state of the array, after performing an arbitrary number of these operations.

I've implemented a simple algorithm using std::rotate that simulates this behavior, but the problem is that my input data set is too large, and rotating the physical array gets really slow.

I've also tried doing this in a std::list (linked list), while keeping a separate array of pointers to every K-th element, so that I could access anywhere in the list in near constant time, while benefiting from the fast removal. This approach requires moving the pointers (or iterators in my implementation) every time I rotate, but since I have less pointers than the actual elements in the array (say 1 pointer per 1000 list elements), this isn't so expensive. All in all, this solution turns out to be about 2 times faster than the vector in some cases, in others it's less fast, but it's still too slow.

I don't need to store the actual array, I only need to be able to compute the value of any element in it. I can see how to do this easily if I only had to do one rotation, where the 0th index would be the rotated element, everything before the rotated element would be shifted one to the right by one and everything on the right side of the element would be kept in place, but I don't see how to keep this up when I do multiple rotations.

One of the possible solutions I found was using interval trees, though this seems rather complex and I'm not sure if it would be more efficient given the high number of rotations needed.

TL;DR: Given a sequence of the first N natural numbers, perform K rotations and figure out the final state of the sequence. For the sake of example, set N = 10^6 and K = 10^5.

But the problem here is that the values of the elements do not matter,
since the rotations can change the order arbitrarily (actually, I do
not understand why they are first sorted).

You want to find an element according to its index in the list, not
its value. A way to do that is to keep with each node of the tree
the number of list elements (leaves) dominated by its left daughter.
Then very simple arithmetics will tell you at each node whether the
$n^th$ element of the list is to be found under the left or the right
daughter, and you acess it in $O(\log n)$ steps if the tree is
properly balanced.

Then the element in inserted at the beginning, which can also be done
in $O(\log n)$ steps.

Then you need to rebalance the tree when it gets unbalanced. But there
are techniques to maintain balancing.

The same should be possible with skiplist, again relying on some size
information to access by index rather than by value.


Spotting the difference between two arrays using divide-and-conquer Say we have two equal-sized arrays that contain a 1 or 0 at each of their indices. These two arrays are identical, except at one unique index. We want to find and output that particular index.

For simplicity, assume we can use two subroutines that can sum any subarray in our first and second arrays, respectively.

How would we use this to find a suitable algorithm using a divide-and-conquer approach? And if so, how many times would it have to call the subroutines? I assume we can start by dividing our arrays into two and solving our problem recursively from there.

Compute sums for the first two halves of the arrays, if they agree, the difference (if any) is in the second halves. If they don't agree, check first quarters, and so on.


Impossibility condition in the Byzantine Generals problem I am unable to understand why there is a requirement of 3m+1 generals overall given m traitors. As per my understanding, the steps are as follows:

Each general decides a strategy and forwards their strategy to all the other ($3m$) generals.
Each general forwards a vector containing the strategies (of all the other generals they received) to all the generals ($m$)
Now, each general has a list of vectors corresponding to the vote made by each general and using a majority criteria (majority vote) decides each general's strategy and thus, the strategy that it itself chooses.

If there are $3m+1$ generals then, with $m$ (loyal) generals choosing to 'attack' and $m+1$ (loyal) generals choosing to 'defend' and $m$ traitors, then since every loyal general forwards the message correctly, each of the $m$ 'attacking' generals will receive $m-1 + m$ (from the other 'attacking' generals and the $m$ 'defending' generals) confirmations of attack for all the other $m-1$ 'attacking' generals, similarly $m-1 + m$ confirmations of 'defend' for the strategy adopted by each one of the defending generals. The traitors however can alter either by sending whatever they'd like (different bits) to the attackers and the defenders [send d for all the defenders and a for all the attackers, but send conflicting values — d to the defenders and a to the attackers — for all the traitors' values], thus making them follow a different plan (defenders will defend, while attackers will attack).

This can't be right, because all the papers and presentations I've gone through state that $3m+1$ with only $m$ traitors will definitely give you the correct solution (all loyal generals follow the same plan). Can anybody go through my understanding, find the flaw and re-explain it to me?

Also, I have understood the $m = 1$ example, it would be nice if someone could explain to me how it fails when $m = 2$ and there are 6 generals and how it succeeds if $m = 2$ and there are 7 generals... I've tried a lot and am stuck.

all the papers [...] state that $3m+1$ with only $m$ traitors will definitely give
  you the correct solution

They should actually state that when $3m+1$ then correct algorithms exist, but not all algorithms are correct.

Algorithms are like cooking recipes (in fact recipes are algorithms): Consider the problem of baking bread. There are books that tell you that you require flour, water and yeast (or similar). But not every recipe of the three will at the end resemble bread.
Consider this one: Mix a spoon yeast, a spoon of flour and 5 litres of water, fill in glasses and refrigerate overnight, serve cold... Definitely not bread ;-)

What your example shows is that the algorithm given in 1),2),3) is not one that solves
the Byzantine Generals problem. (Note that it is well known that a correct algorithm will (in the worst case) need at least m+1 rounds.)

Answer to original question on CSTheory:

I think your miss-conception lies in the assumption

  m+1 loyal generals should vote the same way

Why should this hold?

Assuming you are talking about the problem as defined in LSP82:
For simplicity let's set $m=1$. Then with just $2m+1=3$ generals
you have one commanding general and two lieutenant generals.
When the commanding general is correct, he and the correct general
will vote the same way. So in this case your assumption holds.
But what if the commanding general himself is Byzantine? Then he can
give different instructions to the two correct (lieutenant) generals,
and they are no longer guaranteed to vote the same way.

In general, if the proposer/commanding general is faulty then
there is no way to guarantee that all correct processes will vote in the same way.


Are context free grammars the only ones that have parsing trees? As I understand, the generation process of a string in a context free language according to its context free grammar can be represented as a tree.

For a formal language which can have a formal grammar, can the generation process of a string  also be represented as a tree?

What kind of trees can identify context-free grammars then? I.e. a formal grammar is context free, if and only if the generation of each string according to the grammar can be represented as what kind of trees?

If you look at the Chomsky Hierarchy and the corresponding definitions
of grammars for each of the four types you can make the following
remarks:

there does not seem to be any natural concept of derivation
(generation) tree for type 0 grammars, the unrestricted kind, that
would apply to all.
for context-sensitive (type 1) grammars, at least in the form given
in the wikipedia article, one could associate a tree structure to
the derivation of the string, but this tree, even annotated with
the grammar rule applied at each node, would not be sufficient to
recover simply the order of application of the rules. You would
have to actually associate some partial order with the tree nodes.
I do not know whether this was ever used.
The context-free case (type 2) is well known.
The regular case (type 3) is well known too. It may be seen as a
special case of CF. But regular grammars, and associated tree
structures are not interesting since they are trivial. They do not
really provide useful generative information, nor do they impart
structure on the generated string. Note however that CF grammars
with interesting tree structures could well generate regular
languages.

However, this is not the end of the story. There are many kinds of
grammars, between the regular family and the full context sensitive
(CS) family, i.e. around the CF realm. Many can associate a derivation
tree with the generation process, and they can also associate a
derived tree with the generated string, thus giving it a structure.

These two trees are the same in the case of CF grammars, but, as I
indicated in my answer to another of your questions, they may also
differ, notably in grammars involving multi-parts constituents. such
as Tree Adjoining Grammars (sometimes called mildly context
sensitives) or more generally Linear Context-Free Rewriting Systems
(LCFRS). These grammars depart somewhat from the basic model of
Chomsky hierarchy, as do many others, such as indexed grammars.

For all these formalisms, the languages defined are usually in the context
sensitive realm, and cannot be generated by a CF grammar. The derived
trees associated with the strings are thus also beyond what can be
done with CF grammars. However, many of the formalisms considered in
the literature have sets of derivation trees that are the same as those
of Context-Free languages.

The set of parse trees (meaning here both derivation and derived
trees) for context-free language is a tree language. The family of
parse-tree languages associated with CF grammar is precisely what is
called regular sets of trees. They can be defined by Regular Tree
Grammars (that may look suspiciously like string CF grammars). They can be
recognized by finite state tree automata.

What distinguishes CF Grammars is that their derived trees are regular
sets of trees, which is not the case for the other formalisms. However,
many of these formalisms have regular sets of derivation trees, the
same as CF languages.


Could an NP-hard problem have a mechanical or physical solution method? Is there any NP-hard problem that we can find a mechanical "polynomial time" solution to? For example, suppose we construct a graph out of something physical, e.g. we have have pipes through which we can move water. If this pipe system was suitably built, could we solve say some routing problem by seeing if water flows from one node to another?

So by a mechanical solution, I mean a physical configuration and not a computer program, i.e. I am not looking for a computer algorithm. I also used "polynomial mechanical solution" to describe a solution on a physical device that runs in time polynomial in the order of the input. For example, a piping system could yield the answer in "number of nodes squared" seconds.

No.

Unless $P=NP$, it's unlikely that any mechanical process can solve an $NP$-hard problem efficiently. Given a mechanical approach to solving a problem, we could run a physics simulation on a computer to get the same result.

Of course this depends on being able to simulate what happens in the real world efficiently. In order for "mechanical polynomial time" to be stronger than "polynomial time" you'd need to find some physical process that can not be simulated efficiently. One possible candidate would be quantum mechanics but that doesn't seem to be what you're asking about (and it is speculated that even quantum computing doesn't allow one to solve $NP$-hard problems efficiently).


How does the midpoint line drawing algorithm work? I'm having trouble understanding the mechanics of the midpoint algorithm. I understand the gist of what it does; it keeps us within a half a pixel of where the actual line should be printed. It does this by updating this $d$ value for each pixel that we traverse.

However, even after drawing some samples and observing what the $d$ value does, I can't figure out the true inner workings of it, and how updating it by these $\Delta_e$ and $\Delta_{ne}$ symbols (which are also a bit of a mystery to me) keeps our pixel placement in check.

Can someone summarize it in simple terms for the good of all humanity?

The Algorithm:

Line (x1, y1, x2, y2)
    begin
    int x, y, dx, dy, d, deltaE, deltaNE;
    x <- x1;        y  <- y1;
    dx <- x2 - x1;  dy <- y2 - y1;
    d <- 2*dy - dx;
    deltaE <- 2*dy;     deltaNE <- 2*(dy - dx);

    PlotPixel(x, y);
    while ( x < x2) do
        if (d < 0) then
        begin
            d <- d + deltaE;
            x <- x + 1;
        end;
        else begin
            d <- d + deltaNE;
            x <- x + 1;
            y <- y + 1;
        end;
        PlotPixel (x, y);
    end;
end;

This is not a self-contained answer, but you can find all the details and pictures in the link below. However, I'll give a summary of the idea behind this algorithm.

Take $F(x,y) = (x-x_1)dy - (y-y_1)dx$ as the line function. Let $p=(x_p,y_p)$ be the last pixel we turned on, then $m=(x_p+1,y_p+0.5)$ is the point exactly between the right and the right-top neighbouring pixels. This is the middle point as the title suggests.

Now, if $F(x_m,y_m) > 0$ then the line is above $m$ and if $F(x_m,y_m) < 0$ then it is below $m$, otherwise the line passes through $m$. In the first case we turn on the pixel above the midpoint (i.e. top-right of $p$), and the pixel bellow $m$ (right of $p$) for the second case, and an arbitrary one for the third case.

$d$ initially is the value of $2.F(x,y)$ for the first midpoint (the reason for doubling it to get an integer and avoid floating point calculations), so $d$ is guiding us which direction (N or NE) we should go next. At each iteration instead of recalculating $d$, depending on our last choice of direction we just need to add $\Delta_{NE}$ or $\Delta_E$ to get the new value for $d$.

http://www.dgp.toronto.edu/~karan/courses/csc418/fall_2002/notes/lines.html

I hope it helps.


Data structure for equivalence classes Let $E$ be an equivalence relation defined over a set $S$. The access to $E$ is only via queries of the form $M(s_1,s_2) = 1$ if $s_1$ and $s_2$ are in the same class and $0$ otherwise. Computing $M$ is expensive (say, $O(n^2)$).

I am looking for an efficient data structure $D$ that supports queries of the form "given $s$, does $D$ contain an element $s'$ in the same equivalence class as $s$"?
A naive approach is to search element by element in $D$ and test, but is there other solution?

The best you can do is keep track of all currently known equivalences using a Union-Find data structure.  Initially, each element is in own group.  Whenever you find that two elements are equivalent, you merge their groups (via a Union operation).

Then, the best you can do to answer the query you list is to enumerate over all the groups (other than the one containing $s$), find a representative $x$ for each such group, and test whether $s$ is equivalent to $x$.


Algorithm to partially sort list into equal-sized buckets Suppose I have a large list of numbers that I want to divide into equal-sized buckets so that every bucket contains only larger numbers than buckets to its left. Numbers within each bucket don't need to be sorted.

For example, for the input

[64, 72, 57, 47, 5, 4, 64, 21, 64, 65, 36, 43, 81, 44, 19, 87, 17, 86,
 73, 21, 19, 64, 94, 91, 34, 49, 8, 52, 18, 37]

that I want to divide into 5 buckets, some valid outputs would be

[[4, 5, 8, 17, 18], [19, 19, 21, 21, 34], [36, 37, 43, 44, 47],
 [49, 52, 57, 64, 64], [64, 64, 65, 72, 73]]

[[8, 17, 18, 5, 4], [21, 19, 21, 34, 19], [43, 37, 44, 36, 47],
 [52, 57, 49, 64, 64], [64, 64, 72, 73, 65]]

[[8, 18, 5, 4, 17], [19, 19, 21, 21, 34], [47, 36, 44, 43, 37],
 [52, 64, 49, 64, 57], [64, 72, 64, 65, 73]]

[[18, 8, 17, 5, 4], [21, 19, 21, 19, 34], [36, 44, 43, 37, 47],
 [57, 64, 64, 49, 52], [64, 72, 64, 65, 73]]

One approach to do this would be to sort the list, and then divide it at equal intervals. Can this be done faster?

I would also be happy with a result where the buckets are of only roughly equal size, but note that I can't assume a uniform distribution for the numbers, so bucket sort doesn't help.

Assuming you want to create $k$ buckets, to the following.

Obtain elements of rank $\lceil n/k \rceil, 2 \cdot \lceil n/k \rceil \dots, (k-1) \cdot \lceil n/k \rceil$.
Perform multi-way partitioning (cf. Quicksort) with these elements as pivot.

Both steps take time $\Theta(kn)$. All buckets are within $\pm 1$ of the same size.

In the case of duplicate elements, you can "uniquify" them in a $\Theta(n)$ preprocessing run; otherwise bucket sizes might differ more.

Essentially, this is performing only the top-level call of a $k$-way Quicksort with perfect pivots. All variants regarding pivot selection and partitioning apply and will lead to different runtime and bucket size characteristics.


Algorithm: ordering non-overlapping intervals Assume we have a (multi)set of nontrivial intervals $\mathcal{I} = \{I_1,...,I_n\}$ and for any two $I_i, I_j \in \mathcal{I}$, we have that $I_i \cap I_j$ is trivial (that is: contains at most one point), or one of them contains the other. Just to clarify, an example would be $\mathcal{I} = \{[0,10], [2,6],[6,8], [2,4],[2,3],[5,6],[6,7]\}$. For the sake of simplicity, assume there is a longest interval that contains all other intervals, call that the root.

We can arrange such (multi)sets as a tree where $I_i$ is a descendant of $I_j$ iff $I_i \subseteq I_j$ (if an interval has multiplicity $> 1$, then its multiple occurrences can form a path in the tree). What I want to do is find such a tree. It's clearly possible in $\mathcal{O}(n^2)$ time: sort the intervals by length in descending order and process them in that order. Whenever we insert the next interval $I_i$ into the tree, find the shortest interval already in the tree $I_j$ such that $I_i \subseteq I_j$; such an $I_j$ must exist since the root contains all other intervals.

I would like to do this in $\mathcal{O}(n \log n)$ time and it seems to me that should be possible. Rough ideas include using interval trees and trying to construct the tree from the bottom up starting from its leaves, or figuring out how to annotate search trees to do something like this for me, but nothing successful so far.

You can solve it in $O(n \lg n)$ time using a divide-and-conquer algorithm.

Explaining the main idea: a cleaner variant

To help me explain the main idea, I'm going to change the problem slightly.  I'll assume we're given a set of intervals, with no interval appearing more than once in the set, and where for any pair of overlapping intervals $I,I'$, one of them contains the other (i.e., either $I \subset I'$ or $I' \subset I$).  The goal is to output a forest (a collection of trees).

This variant of the problem is slightly more general, in that we're not assuming we have a single root interval that all others are contained in.  It's also slightly more specific in that I'm assuming we don't have the case of a trivial overlap containing a single point.

I'll show later in my answer how to remove these extra assumptions, but for now, let's go with this variant of the problem, as it makes explaining the main ideas easier.

Main idea: an algorithm for the cleaner variant

We'll use divide-and-conquer.  Let $x$ denote the median of the $2n$ endpoints of the intervals.  This can be computed in $O(n)$ time.

Use $x$ to partition the intervals into three collections:

The intervals that are wholly to the left of $x$ (i.e., their right endpoint is strictly less than $x$).
The intervals that are wholly to the right of $x$ (i.e., their left endpoint is strictly greater than $x$).
The intervals that contain $x$.

We'll first compute three forests, one forest for each of these three collections.  Call these forests $\mathcal{L}$ (the forest of the intervals on the left), $\mathcal{R}$ (for the intervals on the right), and $\mathcal{M}$ (for the intervals that contain $x$).  You can compute $\mathcal{L}$ and $\mathcal{R}$ by invoking the algorithm recursively.  You can compute $\mathcal{M}$ directly by sorting the intervals that contain $x$ by decreasing width and building a path of the intervals by descending size (each node in $\mathcal{M}$ has exactly one child; it is the next-smallest interval).

Now we need to join together the forests $\mathcal{L},\mathcal{R},\mathcal{M}$.  Since $\mathcal{M}$ is a path, given an interval $I$, you can find the smallest interval $I' \in \mathcal{M}$ such that $I \subset I'$ by using binary search.  Therefore, to join the forests, take the roots of $\mathcal{L}$ and $\mathcal{R}$ and use binary search in $\mathcal{M}$ to find the smallest interval containing it, and add a corresponding child relationship.  This is all you need to do to join them into a single forest, as there can be no other child relationships between $\mathcal{L},\mathcal{R},\mathcal{M}$.  Output the resulting forest.

What's the running time of this procedure?  Well, it takes $O(n)$ time to partition the intervals into these three collections.  You can compute $\mathcal{M}$ in $O(n)$ time (if you've done a single up-front precomputation to sort the intervals by decreasing width).  It will take at most $O(n \lg n)$ time to join $\mathcal{L}, \mathcal{R}, \mathcal{M}$ into a single forest, since each binary search operation can be done in $O(\lg n)$ time.  With a little more cleverness, you can speed up the merging to run in $O(n)$ time (pre-sort the intervals by their left endpoint once, and by the right endpoint; now you can join $\mathcal{L}$ and $\mathcal{M}$ by doing a merge on the sorted list of intervals of $\mathcal{L}$ and the sorted list of intervals of $\mathcal{M}$, both sorted by their left endpoint; join $\mathcal{R}$ and $\mathcal{M}$ similarly).  Therefore, the running time is $O(n)$ plus the time for the two recursive calls.  Finally, note that each recursive call is on at most $n/2$ intervals, due to the way we chose $x$ (there can be at most $n/2$ intervals wholly to the left of $x$, as each such interval contributes 2 endpoints to the $2n$ endpoints, and at most $n/2$ intervals wholly to the right of $x$).

Therefore, we get the recurrence relation

$$T(n) = 2 T(n/2) + O(n),$$

whose solution is $T(n) = O(n \lg n)$.

Solving your original problem

Your original problem allows a pair of intervals to overlap in a single point, without either one containing the other.  This doesn't fundamentally change the problem.  You need to generalize the method for computing $\mathcal{M}$ slightly, as it is no longer guaranteed to be a simple path, but this is not hard to do.  Also, now $\mathcal{M}$ might have two leaves.  If so, for each root of $\mathcal{L},\mathcal{R}$, you need to compare it to both leaves to see whether it is contained in either one.  This doesn't change the overall running time.

Also, your original problem allows some intervals to appear in the input twice.  This is easy to accommodate: remove duplicates, count how many times each interval appears in the input, run the algorithm above, and then adjust the tree to account for multiplicities (e.g., by duplicating nodes, or however you would like them to appear in the final output).


Building Suffix Array from Suffix Tree. Inorder visit when node has more than two children From the notes:

It is not difficult to observe that the suffix array $\texttt{SA}$ of
the text $\texttt{T}$ can be obtained from its suffix tree
$\texttt{ST}$ by performing an in-order visit: each time a leaf is
encountered, the suffix-index stored in this leaf is written into the
suffix array $\texttt{SA}$; each time an internal node u is
encountered, its associated value is written into the array
$\texttt{lcp}$.

How do you do the inorder visit when a node has more than two children?
Let's say you visit the leftmost child, then the node, then the other leftmost child. Then do you visit again the node?
SA in an array of pointer to suffixes, ordered lexicographically.
lcp contains the longest common prefix between two consecutive suffixes $\text{suff}_{SA[i]} \text{ and } \text{suff}_{SA[i+1]}$.
The \$ represents a char that's smaller than every other char.
The value associated to each node is the length of the prefix spelled so far.
The leaves represents indices of suffixes. If T = banana\$, the leaf 3 represents nana\$ (T[3,7])
In the image there's what is supposed to be a suffix tree, but I think there's an error since the edges should be sorted according to their label and the leaf 7 with the edge labeled "\$" should be the leftmost leaf and edge.

When simulating the algorithm, first you visit the node 7 ( using the fixed version of the tree ), then the root, so you have
SA = [7, ...]
lcp = [0, ...]

Then let's say you keep going on with an inorder visit of u. When you go back to the root, do you insert the value 0 again in the lcp? Or do you do it just the first time you visited the root?

If a node has $l$ children, with $l \geq 2$ during the inorder visit you have to treat the first $l-1$ children as left nodes, and you have to visit the parent multiple ($l-1$) times, writing multiple times the length of the prefix spelled inside the lcp array.
This, applied to the tree in the image, would yield the correct:
SA = [7, 6, 4, 2, 1, 5, 3]
lcp = [0, 1, 3, 0, 0, 2]

keeping in mind that the edge labeled "$" with the leaf 7 should be the leftmost.


The equivalence relations cover problem (in graph theory) An equivalence relation on a finite vertex set can be represented by an undirected graph that is a disjoint union of cliques. The vertex set represents the elements and an edge represents that two elements are equivalent.

If I have a graph $G$ and graphs $G_1,\dots,G_k$, we say that $G$ is covered by $G_1,\dots,G_k$ if the set of edges of $G$ is equal to the union of the sets of edges of $G_1,\dots,G_k$.  The edge sets of $G_1,\dots,G_k$ do not need to be disjoint.  Note that any undirected graph $G$ can be covered by a finite number of equivalence relations (i.e., disjoint union of cliques graphs).

I have several questions:

What can be said about the minimal number of equivalence relations required to cover a graph $G$?
How can we compute this minimal number?
How can we compute an explicit minimum cover of $G$, i.e., a set of equivalence relations whose size is minimal and which cover $G$?
Does this problem has any applications apart from partition logic (the dual of the logic of subsets)?
Does this problem has a well established name?

Given the various misunderstandings indicated by the comments, here are some pictures to illustrate these concepts. If you have an idea for an easier to understand terminology (instead of "cover", "equivalence relation", "disjoint union of cliques" and "not necessarily disjoint" union of edge sets), feel free to let me know.

Here is a picture of a graph and one equivalence relation covering it:

Here is a picture of a graph and two equivalence relations covering it:

It should be pretty obvious that at least two equivalence relations are required.

Here is a picture of a graph and three equivalence relations covering it:

It's less obvious that at least three equivalence relations are required. Lemma 1.9 from Dual of the Logic of Subsets can be used to show that this is true. The generalization of this lemma to nand operations with more than two inputs was the motivation for this question.

Although I don't know the name for such problem, I can show this problem is NP-hard.

For a triangle free graph, all equivalence classes must be a matching. The minimum number of equivalence classes that covers the graph equals the chromatic index of the graph.

According to this article, finding the chromatic index for a triangle free graph is NP-complete.


What is complexity class $\oplus P^{\oplus P}$ What does the complexity class $\oplus P^{\oplus P}$ mean? I know that $\oplus P$ is the complexity class which contains languages $A$ for which there is a polynomial time nondeterministic Turing machine $M$ such that $x \in A$ iff the number of accepting states of the machine $M$ on the input $x$ is odd.

But what does $\oplus P^{\oplus P}$ mean? I just can't follow what it actually does :)

What are practical consequences of such complexity class and how it is possible to show that $\oplus P^{\oplus P} = \oplus P$?

$\oplus P^{\oplus P}$ denotes the class $\oplus P$ equipped with what's known as an oracle for $\oplus P$ — we say that it has been given the ability to determine whether or not a string $s$ is a member of a language $L$ contained in the class $\oplus P$ in a single operation.

I see that another commenter (sdcwc) has linked to the proof of $\oplus P^{\oplus P} = \oplus P$ (see these notes on a lecture from CS 538 at Rutgers). A complexity class $C$ that is an oracle to a class $B$ such that $B^C= B$, is said to be low for the class $B$. In this case, we say that $\oplus P$ is low for itself.


NP-hardness of covering with rectangular pieces (Google Hash Code 2015 Test Round) The Google Hash Code 2015 Test Round (problem statement) asked about the following problem:

input: a grid $M$ with some marked squares, a threshold $T \in \mathbb{N}$, a maximal area $A \in \mathbb{N}$
output: the largest possible total area of a set of disjoint rectangles with integer coordinates in $M$ such that each rectangle includes at least $T$ marked squares and each rectangle has area at most $A$.

In Google's terminology, the grid is a pizza, the marked squares are ham, and the disjoint rectangles are slices.

We can clearly rephrase this problem to a decision problem by adding an additional input $n \in \mathbb{N}$ and let the answer be "is there a set of disjoint rectangles satisfying the conditions whose total area is at least $n$ squares".

My question: while the Google problem asked candidates to find a solution which is "as good as possible" for the computation problem on a specific instance, I think it is likely that the general problem (in its decision phrasing) is NP-complete. However, I cannot find a reduction to show NP-hardness. (NP-membership is immediate.) How to prove that this problem is NP-hard?

A few examples follow, to help visualize the problem. Consider the $4$ by $4$ grid $\{0, 1, 2, 3\} \times \{0, 1, 2, 3\}$, with marked squares $(1, 1)$, $(0, 2)$ and $(2, 2)$, represented graphically with X to indicate marked squares:

..X.
.X..
..X.
....

Set $A = 6$ (rectangles of at most $6$ squares) and $T = 1$ (at least one marked square per rectangle), an optimal solution (that covers the entire grid) is to take the following rectangles:

aaAa
bBcc
bbCc
bbcc

On the following grid, with $A = 3$ and $T = 2$:

XXX
.X.
...

One cannot do better than covering only three squares:

AAA
.X.
...

or

XBX
.B.
.b.

(remember that rectangles in the partition cannot overlap).

With other people looking at this question, we tried reductions from bin packing, covering problems, 3-SAT, and Hamiltonian cycles, and we didn't manage to get one to work.

This is a sketch of a reduction from MONOTONE CUBIC PLANAR 1-3 SAT :

Definition [1-3 SAT problem]:
Input: A 3-CNF formula $\varphi = C_1 \land C_2 \land ... \land C_m$, in which every clause $C_j$ contains exactly three literals: $C_j = (\ell_{j,1} \lor \ell_{j,2} \lor \ell_{j,3})$.
Question: Does there exist a satisfying assignment for $\varphi$ such that each clause $C_j$ contains exactly one true literal.

The problem remains NP-complete even if all literals in the clauses are positive (MONOTONE),  if the graph built connecting clauses with variables is planar (PLANAR) and every variable is contained in exactly 3 clauses (CUBIC) (C. Moore and J. M. Robson, Hard tiling problems with simple tiles, Discrete Comput. Geom. 26 (2001), 573-590.).

We use $T=3, A=6$, and in the figures  ham is represented with blue boxes (transgenic ham?), pizza with orange boxes.

The idea is to use tracks of ham that carry positive or negative signals; the track is made with an alternation of 1 and 2 pieces of hams placed far enough so that they can be covered exactly by one slice of pizza of area $A$; the segments of the track are marked alternately with $+$ or $-$, the track will carry a positive signal if slices are cut on the positive segments:

Each variable $x_i$, which is connected to exactly 3 SAT clauses, is represented by three adjacent endpoints of three ham tracks (positive segment), in such a way that there are 2 distinct ways to cut it, one will "generate" a positive signal on all 3 tracks (it reppresent the $x_i = TRUE$ assignment) the other a negative signal ($x_i = FALSE$). Notice that we can also generate mixed positive and negative signals, but in that case at least one ham remains uncovered.

Each clause $C_j$ of the 1-3 SAT formula with 3 literals $L_{i,1}, L_{i,2}, L_{i,3}$ is simply represented by a single ham with three incoming positive segments of three distinct ham tracks; by construction only one of the three tracks carrying a positive signal can "cover" the ham-clause.

Finally we can build shift and turn gadgets to carry the signals according to the underlying planar graph and adjust the endpoints:

Suppose that the resulting graph contains $H$ hams. By construction every slice of pizza must contain exactly 3 hams, and in all cases every slice can be enlarged up to area $A$.

If the original 1-3 SAT formula is satisfiable then by construction we can cut $H /3$ pieces of pizza (with total area of $A H / 3$) and no ham remains uncovered.

On the oppposite direction, if we can cut $H /3$ pieces of pizza (with total area $A H / 3$) then no ham remains uncovered, and the signals on the variables gadgets and on the clauses are consistent: the ham on the clause is covered by exactly one positive slice coming from a positive variable, and every variable generates 3 positive signals or 3 negative signals (no mixed signals); so the cuts induce a valid 1-3 SAT assignment.


When did $LR(k)$ acquire the meaning "left-to-right scan, rightmost derivation?" According to the Wikipedia article, the L in $LR(k)$ means "left-to-right scan", and the "R" means "rightmost derivation."  However, in Knuth's original paper on $LR(k)$ grammars, he defines $LR(k)$ (on page 610) as a language that is "translatable from left to right with bound $k$."

I am guessing that this new terminology was chosen to complement $LL(k)$ parsing's "left-to-right scan, leftmost derivation."  That said, I don't know when the terminology changed meaning.

Does anyone know where the newer acronym for $LR(k)$ comes from?

I went and asked Don Knuth about this. He mentioned that he first used the new terminology in his 1972 paper Top-Down Syntax Analysis (link here) to provide a consistency between the terminology in $LL(k)$ and $LR(k)$ parsing.

Hope this helps!


Array contains elements that differ by K correctness proof I have been puzzling over an algorithm that decides whether a sorted array of numbers contains two numbers that differ by k. I do not intuitively understand why this algorithm works, or what thought process might have led me to think of this algorithm on my own, although I believe that I can prove it's correctness.

CONTAINS_DIFFK(arr, k)
    n = size(arr)
    if n == 1 return false
    i = 1
    j = 2
    while i <= n and j <= n
        if i != j and arr[j] - arr[i] == k
            return true
        if arr[j] - arr[i] < k
            j++
        else
            i++
    return false

My questions are:

Is the following proof sound
Is there a more concise way to prove correctness?
What thought process might have lead me to derive this algorithm on my own? (I had to look up the solution)

Proof by Induction

Let arr be an arbitrary sorted array of integers of length n. Assume for the sake of induction that CONTAINS_DIFFK return true if arr contains two numbers which differ by k and false otherwise. Let arr' be an arbitrary sorted array formed by adding a single arbitrary integer to the end of arr. We prove that CONTAINS_DIFFK return true if arr' contains two numbers which differ by k and false otherwise.

Assume that it is the case that arr contains two elements that differ by k. By our inductive assumption, CONTAINS_DIFFK will return true for arr. Because CONTAINS_DIFFK immediately returns after finding two elements that differ by k without considering further elements, and the first n elements of arr and arr' are identical, the n+1'th element of arr' will not be considered and will not affect the output of the algorithm. Thus CONTAINS_DIFFK returns true for input arr'.

Therefore we need only consider the case, which is now assumed, in which arr did not already contain two elements which differ by k. We must consider the cases in which the n+1'th element of arr' does not differ from any of the first n elements by k and the case in which it does.

First, consider the case in which the n+1'th element of arr' does not differ from any of the first n elements of arr'. We show that the algorithm returns false. Let i' be the value of i when j is incremented to be equal to n+1. Note that i' <= n. Now simply note that the last element of arr' will be compared to some subset of the elements after and including the i'th element. Since we assumed that the last element of arr' does not differ from any element by k, the condition for returning true will never be met and false will be returned.

Finally, we consider the case in which there exists some element e in arr which differs by k from the n+1'th element of arr', and show that the algorithm returns true. Again, let i' be the value of i when j is incremented to n+1 while processing arr. Now, critically, note that j was incremented to n+1 because arr[n] - arr[i'] < k. If we note also that arr'[n+1] >= arr'[n] (because it is sorted) and arr'[n+1] - e = k, then we  may derive e > arr[i']. Thus, we note that i will be increased from i' up to the index of e at which point CONTAINS_DIFFK will return true as desired.

Base case

Let arr be an arbitrary sorted array of two integers. We may trace through the execution of this algorithm and note that if arr[2] - arr[1] then it will return true and it will return false otherwise. Thus, the induction is complete.

My line of thought for deriving this algo:

there is well-known Merge algo (part of Merge Sort) combining two sorted arrays
we can modify it to output only equal elements of arrays (i.e. producing intersection instead of union)
we can further modify it to return true on the first match, and false at the end
and finally, we can modify it to compare elements with given offset k

I suggest you to practice developing algos at leetcode or similar site, it will allow you to come up with similar solutions in a few minutes.


Memory Invalidation and Misses Assume this particular architecture of a machine. Say we have 4 processors and each processor has its private L1 cache and shared L2 cache. Now if we write to an address in one of the private cache's of the L1 cache then we Invalidate the blocks in the other private cache which contains the same address. Say P0(processor 0) reads an address 100 and so the block containing it say B0 gets stored in the private cache of P0 and as well as in the shared L2 cache. Now say P2  writes to the location 100. So we need to invalidate the block B0 from the private cache of P0. Now if P0 wants to read from address 100 again it will suffer a miss in its private cache, but will it get HIT or MISS in the L2 cache?
I think it will get HIT. Can anyone confirm.

It will be HIT in the L2 cache as you have guessed it because L2 cache maintains a directory or a bit vector which tells in which of the private caches the modified state of the block is in. So when L1 of P0 requests it for the second time, L2 will supply the latest modified block.


What is a compact model? I am a domain scientist and I study biophysical systems. When I asked a colleague in CS for suggestions about how to design a multi-scale simulator, he mentioned the term "compact model".

Now, I can't find a very good definition of this term. I can find the book "Compact Modeling" edited by Gildenblat but this is a collection of domain specific applications, similar to what I found on google scholar.

I haven't found a first-principles treatment of what a compact model is or the advantages of using one. It would be great to know where I could find this topic in a textbook or annual reviews type paper.

Q: What is a compact model, and when is it useful?

This paper uses the phrases "compact model" and "multiscale simulation". Perhaps it is relevant. Indeed, Googling "multiscale simulation compact model" yielded lots of results.

The back cover of the book you refer to states:

  Compact Models of circuit elements are models that are sufficiently simple to be incorporated in circuit simulators and are sufficiently accurate to make the outcome of the simulators useful to circuit designers. The conflicting objectives of model simplicity and accuracy make the compact modeling field an exciting and challenging research area for device physicists, modeling engineers and circuit designers.

My understanding is that a compact model is a parametric equation with certain parameters determined that models the phenomenon of interest to some degree of precision.


How to efficiently specify a MILP constraint with nested AND and ORs Let's say I want to set  x1=1 if (x2=1 AND x3=1 AND x4=1) or (x5=1 and x6=1) or (x7=1) else x1=0

All of the xs are binary variables.

My first thought is I have to add 3 additional variables, let's say y1, y2, y3 and 12 constraints like this

3*y1-x2-x3-x4<=0
y1-x2>=0
y1-x3>=0
y1-x4>=0
2*y2-x5-x6<=0
y2-x5>=0
y2-x6>=0
y3-x7=0
3*x1-y1-y2-y3>=0
x1-y1<=0
x1-y2<=0
x1-y3<=0

Is there a more efficient way to tackle this?

It can be done with two auxiliary variables, y1,y2:

x1 >= y1
x1 >= y2
x1 <= y1 + y2

x2 + x3 + x4 >= 3*(y2 - y1)
x2 + x3 + x4 <= 2 + y1 + y2

x5 + x6 >= 2*(y1 - y2)
x5 + x6 <= 1 + y1 + y2

x7 >= y1 + y2 - 1
x7 <= y1 + y2

The idea here is that if (y1,y2) = (0,1), then the first and-clause is forced to be true; if (y1,y2) = (1,0), then the second and-clause is forced to be true; if (y1,y2) = (1,1), then the third and-clause is forced to be true; and if (y1,y2) = 0, then all three and-clauses are forced to be false.

In other words, (y1,y2) represents the index (in binary) of which of the three and-clauses is true; or (0,0) if none of them are true.

I would be surprised if it is possible to encode your constraint using only a single auxiliary variable.

This trick can be generalized: if you have an OR of $2^k-1$ AND-clauses, then you can find an encoding that uses $k$ auxiliary variables.


What does it mean for a random number generator's sequence to be only 1-dimensionally equidistributed? Whilst reading up on Xorshift I came across the following (emphases added):

The following xorshift+ generator, instead, has 128 bits of state, a maximal period of 2^128 − 1 and passes BigCrush:
[snip code]
This generator is one of the fastest generator passing BigCrush; however, it is only 1-dimensionally equidistributed.

Earlier in the article there's the following:

[snip code]
Both generators, as all xorshift* generators of maximal period, emit a sequence of 64-bit values that is equidistributed in the maximum possible dimension.

What does it mean for a sequence to be equidistributed in one dimension vs. multiple dimensions vs. not at all?

This website provides the answer:

  A xorshift* generator with an n-bit state space is $n/64$-dimensionally equidistributed: every $n/64$-tuple of consecutive 64-bit values appears exactly once in the output, except for the zero tuple (and this is the best possible for 64-bit values). A xorshift+ generator is however only $(n/64 − 1)$-dimensionally equidistributed: every $(n/64 − 1)$-tuple of consecutive 64-bit values appears exactly $2^{64}$ times in the output, except for a missing zero tuple.

In the case of a xorshift+ which uses 128 bits of state, n/64 - 1 = 128/64 - 1 = 2 - 1 = 1, so the Wikipedia article was correct in stating that that particular generator is only 1-dimensionally equidistributed.


Shift Organization algorithms (Constraint Programming + Marriage problem) I want to assign people to cover shifts considering a set of constraints and preferences. Here's the problem definition:

Daily shifts must be covered by workers, who are divided in three groups:

Trainees (Nt = 2)
Regulars (Nr = 3)
Experts (Ne = 7)

The organization constraints are:

All shifts must be covered
A Trainee must always cover a shift with an Expert
Workers covering Friday must also cover Sunday
Nobody can cover two shifts in a row
Nobody works more than M shifts every D days

The process should maximize the following output:

Workers get shifts assigned based on their preference
Experts work as less as possible, only covering unassigned gaps
Number of shifts are evenly distributed

My initial idea is to write a branch and bound algorithm to generate all possible combinations allowed by the constraints. I would then score each solution for each worker based on their preferences, and run a marriage algorithm to get the best combination.

The main problem is that the number of combinations is too (damn) high. Without constraints, there would be 6**30 (~1e24) possible arrangements. I know most of these will be bound, but currently I'm generating at a pace of ~1e8/minute.

I'm wondering if there are any heuristics I could apply to improve the process. Any ideas here? How does this whole thing sound?

Thanks!

Sample code to generate combinations:

def get_combinations(population, base, spots):
    if len(base) == spots:
        yield base
        return

    for candidate in population:
        combo = base + (candidate, )

        if is_viable(combo, population, spots):
            yield from get_combinations(population, combo, spots)

population = {'t1', 't2', 'n1', 'n2', 'n3'}
get_combinations(population, tuple(), 30)

Turns out this problem is pretty hard to solve and is still under active research. This paper (2004) describes the state of the art.


A text-classifier that explains its decisions I am building a text categorizer for short sentences. In addition to telling the  user "the category of the text you entered is C", I want to be able to explain why I made this decision, in a short and understandable way. For example, I don't want to tell the user "I put your sentence into a complex 3-layered neural network and that's the answer that scored the best"; I want explanations such as "Your sentence contains the words U, V and W, that are characteristic of this category, because of sentences such as X, Y and Z that appeared in the training data".

My question is: what classification algorithms are best suited for such application?

k-nearest-neighbours seems like a good candidate, because I can tell the user "Your sentence has category C because it is similar to sentences X, Y and Z that have the same category. But its performance on text categorization problems is known to be poor. I am looking for a classifie that balances performance with explanation ability.

EDIT: After spending a lot of time looking for such a classifier, I started to build a machine-learning library called limdu, that allows the classifiers to explain their decisions. It is still under development, but, it has already helped me explain to myself and my colleagues why our classifiers fail so often...

Although it performs poorly on text classification tasks, if you want a clear explanation of the classification reasoning, a decision tree would be your best option as it provides clear rules for how an instance is classified.  A trace of the tree would provide the determining values and by analyzing the instances close to the root node, you might even be able to determine which attributes where more significant in the classification.

Another option would be to use a Naive Bayes classifier, which performs better for text mining tasks and would give you a comprehensible evaluation scheme based on probabilities that you could use to generate the "why" you're looking for, even providing an indication of which attribute values were more important than others in making the determination.

Support Vector Machines, specifically Sequential Minimum Optimization (SMO), seem to work well with these tasks and likewise provide indication of the values used to make the classification in the form of attribute weights and support vectors, but I think you may have a harder time making explicit how these weights and vectors influenced the overall classification decision.

Good luck with your project! Sounds very interesting.


Conv Net dimensions misunderstanding? I was asked this question:
Given an image with shape [1,28,28], what will be the shape of the output of a convolution layer with 10 5x5 kernels (filters) without padding?
Now, are the shape dimensions [row, column, depth]?
I really don't understand how you apply a 5x5 kernel on such image, because its 1x28...
What am I missing here?

The order of dimensions usually depends on the library you are using
Tensorflow : (Height,Width,Channel) : HWC
PyTorch: (Channel,Height,Width) : CHW
In your case the image seems to go with CHW , since you cant apply 5x5 filters on a 1x128 image
As for the final shape , we follow the rule :
for input length N, and k-size filter , output-length = N-k+1
so each of the 10 filters produces output length = 28-5+1 = 24
so output length = (10,24,24) in the CHW format
Here is a simple Tensorflow code to test it if you want :
from tensorflow.keras.layers import Input,Conv2D
x = Input(shape=(28,28,1))
x = Conv2D(filters = 10, kernel_size = 5, padding='valid')(x)
print(x.shape)


How to solve recurrences involving log? For example,

$T(n) = \log {n} \cdot T(\frac{n}{\log{n}}) + \Theta(n)$

I tried using the substitution method with $ n = 2^m $, but that got me nowhere, since it still ends up with a $m$ and $2^m$. The recurrence tree method also becomes rather complicated. Is there a general approach to follow to solve such recurrences?

Define a sequence $n_0 = n$, $n_{t+1} = n_t/\log n_t$. Assuming that the underlying constant in $\Theta(n)$ is $1$, we get
$$
\begin{align*}
T(n) &= \log n_0 T(\tfrac{n_0}{\log n_0}) + n_0 \\ &=
\log n_0 \log n_1 T(\tfrac{n_1}{\log n_1}) + n_0 + n_1 \log n_0 \\ &=
\log n_0 \log n_1 \log n_2 T(\tfrac{n_2}{\log n_2}) + n_0 + n_1 \log n_0 + n_2 \log n_1 \log n_0 \\ &= \cdots
\end{align*}
$$
Now $n_{t+1} \log n_t = n_t$, and so $n_1\log n_0 = n_0$, $n_2\log n_1\log n_0 = n_1\log n_0 = n_0$, and so on.

Suppose now that the starting condition of your recurrence is $T(x) = 1$ for $x \leq 1$, and let $\ell+1$ be the minimal index such that $n_{\ell+1} \leq 1$. Then
$$ T(n) = \log n_0 \log n_1 \cdots \log n_\ell + (\ell + 1) n. $$
In fact, $\log n_0\cdots n_\ell n_{\ell+1} = n$, and clearly $n_{\ell+1} = \Omega(1)$, showing that $T(n) = (\ell + O(1))n$.

It remains to estimate $\ell$. Clearly $n_t \geq n/\log^t n$, and so $\ell \geq \log n/\log\log n$. For the other direction, notice that when $t \leq \log n/2\log\log n$, we have $n_t \geq \sqrt{n}$, and so $n_t \leq n/(\log n/2)^t$. This shows that $n_{\log n/2\log\log n} \leq \sqrt{n} 2^{\log n/2\log\log n} \leq n^{0.51}$ for $n$ larger than some constant $C$. Repeating the same argument, $n_{\log n/2\log\log n + \log n^{0.51}/2\log\log n^{0.51}} \leq n^{0.51^2}$ for $n^{0.51} \geq C$. Notice that $\log n^{0.51}/2\log\log n^{0.51} \leq 0.52\log n/2\log\log n$, for $n$ larger than some constant $C'$. Repeating this argument $k = O(\log\log n)$ times, we get that for $t = \log n/(2\log\log n) (1 + 0.52 + 0.52^2 + \dots) = O(\log n/\log\log n)$ we have $n_t = n^{0.51^k} = O(1)$. This shows that $\ell = \Theta(\log n/\log \log n)$, and so
$$ T(n) = \Theta(n\tfrac{\log n}{\log\log n}). $$


Data structure for counting bits set on a table I have a table that contains only bits. I would like to be able to do the following two queries:

SET any bit to 0 or 1;
GET the number of bits that are set to 1 from the beginning of the table up to a specifique index i.

Is there a data structure that is more efficient than a binary indexed tree, i.e. a Fenwick tree? A binary indexed tree performs both operations in $O(\log n)$ time, where $n$ is the number of elements.

For practical info, my tables are really large, containing up to millions of elements.

If one of the operations is much more common, you could use an array of bits resp. of counts, so the common operation can be done in $O(1)$ at the cost of the other operation taking $O(n)$.

If you can't make such an assumption, then I don't think there is anything better than the $O(\log n)$ of the BIT.


Simplify the asymptotic expressions $O(n^2 + n) + \Omega (n^2 + n \log n)$ How can it be shown that the expression $O(n^2 + n) + \Omega (n^2 + n \log n)$ simplifies to $\Omega (n^2)$? Why is it not $\Theta(n^2)$?

The expression that you write means what can we say about $f(n) + g(n)$ such that $f(n) \in O(n^2 + n)$ and $g(n) \in \Omega(n^2 + n \log n)$. First, we can rewrite the inputs to $f(n) \in O(n^2)$ and $g(n) \in \Omega(n^2)$. Hence, the we can say $f(n) + g(n) \in \Omega(n^2)$.

However, we cannot say $f(n) + g(n) \in \Theta(n^2)$. As a counterexample, $f(n) = n$ and $g(n)  = n^3$.

Anyhow, if you want to say there is a function $f(n)$ such that it is in $O(n^2 + n)$ and also in $\Omega(n^2 + n \log n)$, you're right. Although if $f(n) \in \Theta(n^2)$, it is in $\Omega(n^2)$ as well.


How can the class of tail recursive functions be compared to the classes of PR and R? How can the class of tail recursive functions (TR) be compared to the classes of primitive recursive functions (PR) and recursive functions (R)?

The computation of a PR function always halts. This does not apply to TR functions.
Given a tail recursive function $f$:
   $$f(x) = f(x)$$
The function $f$ obviously will result in an endless recursion and therefore $TR \not\subseteq PR $.
Also a PR function has a finite time and space complexity, where a TR function can have a finite space and infinite time complexity.
For this reason I assume:
 $$PR \subset TR \subset R $$

 Is this assumption correct?
 Is the Ackermann function $\in TR$?
 Is there a well known function which is in $R$, but not in $TR$?

Every computable function can be expressed in continuation-passing-style, in which all calls are tail-calls.

The trick is to add a "continuation" parameter to every function. Instead of making a non-tail-call to a function, you make a tail call to that function with a modified continuation, describing what to do with the result. All instances where a value is directly returned (such as recursion base cases) are replaced by calling the continuation in tail-position with the result as an argument.

Transformation from the lambda calculus into CPS can be done mechanically. So, $TR=R$.

EDIT: addressing the comments about higher-order functions:

Tail-calls are almost always discussed in the context of higher order functions and the lambda calculus. So the problem is, what precisely is our definition of $TR$?

You can certainly add a wrapper around a CPS function to give it the type $\mathbb{N}^n \to \mathbb{N}$, by giving it an initial continuation of $\lambda k \ldotp k$. If higher-order functions are allowed internally, then the result that $TR=R$ still holds.

If higher order functions aren't allowed internally, what is our definition of $TR$? If we define it in the same way as $PR$, then it is going to only contain primitive recursive problems by definition (since it's just the restruction of $PR$ to tail-recursion). If we add $\mu$ for infinite search, I think we're just going to get $R$, since we can encode higher-order functions using integers. So, I'm not sure there's a meaningful question to be asked in the non-higher-order case.

EDIT 2:

As for the class of first-order functions that only allow tail recursion, with Constant, Successor, Projection and Composition functions, and extension by tail recursion:

h(x1 ... xn) =
  if c(x1 ... xn) = 0 then
    h(g1(x1), ..., gn(xn))
  else
    f(x1, ..., xn)

where $c$, $g_i$ and $f$ are all tail-recursive functions, I think we can prove that it's Turing Complete, by solving Post's Correspondence Problem, which is undecidable but semi-decidable:

Assume that we've got nice functions for dealing with strings encoded as integers, with concatenation, etc.

Let $pcpInst(k, n)$ be a function which takes an integer $k$ and returns the $k$th string over the alphabet $\{1, \ldots, n \}$.

Let $c(k, x_1, \ldots, x_n) = $ be a function, where $k$ is an integer, and each $x_i$ is a pair containing two strings over a binary alphabet. Thus function does the following:

Computes $k_1 \cdots k_p = pcpInst(k,n)$, the $k$th possible PCP solution indices.
Constructs $s_1=\pi_1(x_{k_1}) \cdots \pi_1(x_{k_p}))$. This is the string we get by concatenating the first string of the arguments indexed by our $k_i$ sequence. We define $s_2$ with $pi_2$ similarly.
Return $0$ if $s_1 \neq s_2$, return $1$ otherwise.

Now, we'll define our function to solve the a PCP instance with $n$ strings:

$h(k, x_1, \ldots, x_n) = h(S(k), x_1, \ldots, x_n)$ if $c(k, x_1, \ldots, x_n) = 0 $
$h(k, x_1, \ldots, x_n) = 0$ otherwise

Now we define $h'(x_1, \ldots, x_n) = h(0, x_1, \ldots, x_n)$.

It is clear to see that $h'(x_1, \ldots, x_n)$ returns 0 if and only if there is a solution to the correspondence problem defined by pairs of strings $x_1, \ldots, x_n$. If there is a solution, we eventually iterate to it by increasing $k$, and return $0$ when our $c$ function returns 1. If there is no solution, we never return.

The trick here is ensuring that $c$ is itself tail-recursive. I am fairly confident that it is, but that proving so would be tedious. But since it is performing simple string manipulations and equality checks, I would be very surprised if it is not tail recursive.


Prove a language is not recursive enumerable I need to prove
$: L=\left\{<M>| M \text { is a } T M \text { and } L(M)=L\left((01)^{*}\right)\right\} \notin R e$

at first observation it looks like it's immediate from Rice's extended Thm, but is it really?
Rice's extended Thm requires that the set won't include sigma star and won't be empty, as I believe $L\left((01)^{*}\right)$ meets the conditions? or do I have to make some manipulation in order to meet the requirements of the Thm.

Yes it's okay to use Rice's extended theorem.

To clarify, the theorem states: "if $C$ is some set of languages, and $C\neq\emptyset\wedge\Sigma^*\notin C$, then $\{<M>|L(M)\in C\}\notin RE$."

So, let us define $C=\{L((01)^*)\}$. Notice that our $L$ in the question is exaclty $\{<M>|L(M)\in C\}$, and then since $C\neq\emptyset$ and $\Sigma^*\notin C$ $[$as the only language in $C$ is $L((01)^*)\space]$, we have by the extended theorem that $L\notin RE$.


Hard connected instances for Weisfeiler-Lehman test of isomorphism There are instances when WL algorithm fails. For example graphs G1 and G2 below have the same coloring after WL-1 algorithm.

However, one of these graphs is disconnected. So what are the instances of undirected connected graphs for which WL algorithm fails?

Yes, there are non-isomorphic connected graphs that cannot be distinguished by Weisfeiler–Lehman.  The following construction is due to Cai, Fürer and Immerman (An Optimal Lower Bound on the Number of Variables for Graph Identification, Combinatorica 12(4):389–410, 1992; PDF).

Take any connected, $3$-regular graph $G=(V,E)$. We will produce non-isomorphic graphs $G_\parallel$ and $G_\times$ from $G$, that are indistinguishable by Weisfeiler–Lehman.  These will be made by producing a gadget for each vertex of $G$ and, for each edge $xy\in E$, connecting the gadgets for $x$ and $y$ by a pair of parallel edges.

The vertices of $G_\parallel$ are is defined as follows.

For each $xy\in E$, we create four (distinct) vertices, $a_{x,y}$, $a_{y,x}$, $b_{x,y}$ and $b_{y,x}$.
For each $x\in V$, we create a vertex $c_{x,S}$ for each odd-cardinality subset of $\Gamma(x)$ (the neighbours of $x$ in $G$).  So, if $x$'s neighbours are $u$, $v$ and $w$, we create vertices $c_{x,\{u\}}$, $c_{x,\{v\}}$, $c_{x,\{w\}}$ and $c_{x,\{u,v,w\}}$.

The edges of $G_\parallel$ are defined as follows.  For each edge $xy\in E$, we add:

the two edges $a_{x,y}a_{y,x}$ and $b_{x,y}b_{y,x}$;
the edges $a_{x,y}c_{x,S}$ for each $S$ such that $y\in S$;
the edges $b_{x,y}c_{x,S}$ for each $S$ such that $y\notin S$.

Note that $G$ is undirected so if $xy\in E$, then $yx\in E$ also, and we follow the above rules twice for each edge of $G$.

Now, let $xy$ be any edge in $G$ and let $G_{xy}$ be the graph made from $G_\parallel$ by deleting the edges $a_{x,y}a_{y,x}$ and $b_{x,y}b_{y,x}$ and replacing them with the "cross" edges $a_{x,y}b_{y,x}$ and $b_{x,y}a_{y,x}$.  The following lemma is the key point of the construction.

Lemma 1. For any edges $uv,xy\in E$, the graphs $G_{uv}$ and $G_{xy}$ are isomorphic.

Proof sketch. You can move the cross edge around the graph in the following sense.  For any pair of edges $ij,jk\in E$, there's an isomorphism of $G_{ij}$ that exchanges $a_{j,i}$ and $b_{j,i}$ and exchanges $a_{j,k}$ and $b_{j,k}$. This isomorphism is a permutation of the vertices $c_{j,S}$, and it fixes every other vertex in $G_{ij}$.  If you draw the fragment of the graph corresponding to vertex $j$ and its incident edges, the isomorphism should be pretty obvious.

This means that $G_{ij}\simeq G_{jk}$, because the isomorphism "uncrosses" the edge $ij$ and "crosses" the edge $jk$.  Since $G$ is connected, it contains a path whose first edge is $uv$ and whose last edge is $xy$, and we can use the isomorphisms corresponding to each adjacent pair of edges in this path to move the cross in $G_{uv}$ to $xy$. $\Box$

By Lemma 1, we're entitled to use the name $G_\times$ for an arbitrary graph $G_{xy}$.  We now have the graphs $G_\parallel$ and $G_\times$; it remains to show that they're non-isomorphic and that they're indistinguishable to Weisfeiler–Lehman.

Lemma 2. For any connected, 3-regular graph $G$, we have $G_\parallel \not\simeq G_\times$.

Proof sketch. It turns out that the only isomorphisms of $G_\parallel$ and $G_\times$ are isomorphisms induced by isomorphisms of $G$, and isomorphisms of the form used in the proof of Lemma 1.  But no such isomorphism can transform $G_\times$ into $G_\parallel$ because $G_\times$ has a cross edge and $G_\parallel$ does not. $\Box$

Now, indistinguishability.  Weisfeiler–Lehman is definable in so-called "fixed-point logic with counting."  This is first-order logic plus:

counting quantifiers: for each natural number $n$, you can write $\exists^{\geq n}x\,\varphi(x)$, meaning "There exist at least $n$ values of $x$ that satisfy $\varphi$." This can already be expressed in ordinary first-order logic, just by saying that there exist distinct $x_1, \dots, x_n$ that all satisfy $\varphi$, but the (rather subtle) point here is that the counting quantifier only uses just one variable, whereas the "pure" first-order expression uses $n$ distinct variables.
inductive definitions. These let you build up a relation $R$ as follows.  You start with $R=\emptyset$. Then, you add to $R$ all the tuples that satisfy a formula $\varphi$, and keep doing that until you run out of tuples to add.  $\varphi$ itself can depend on $R$, so you can build up some interesting things.

In particular, you can build up an equivalence relation corresponding to the colour-classes of Weisfeiler–Lehman. The counting quantifiers let you talk about the numbe of neighbours of each colour, and the inductive definitions let you recursively refine the colouring based on the number of neighbours of each colour in the previous step.

A separator of a graph $G=(V,E)$ is a set $S\subseteq V$ such that no component of $G-S$ has more than $|V|/2$ vertices. In the following, I say "less than about $2k$" because I'm silently translating from fixed-point logic with counting to so-called "infinitary logic with counting", which roughly doubles the number of variables. I don't remember the exact details, and it's not important enough to hunt them down.

Theorem 3. Let $\varphi$ be a formula of fixed-point logic with counting, using $k$ distinct variables.  If $G$ is a graph with no separator of size less than about $2k$, then $\varphi$ cannot distinguish $G_\parallel$ from $G_\times$.

Proof sketch. Very roughly speaking, while you're evaluating the formula $\varphi$ on $G_\parallel$ or $G_\times$, you might need to consider $k$ vertices as being the value of some variables at the current iteration of an inductive construction and $k$ more variables as being the value of the variables at the previous iteration. The fact that $G$ has no small separators means that, even if we fix those vertices, we can still move the cross around in a large component of the rest of the graph, without the formula "knowing" that we've done that, so the formula can never "see" the cross, so it can never tell the difference between the graph with the cross and the graph without it. $\Box$

For any fixed $d$, $d$-dimensional Weisfeiler–Lehman can be expressed as a formula of fixed-point logic with counting, using some number $k$ of variables ($k\approx 2d$ is enough, as I recall). Since that formula can't tell the difference between the non-isomorphic graphs $G_\parallel$ and $G_\times$ as long as $G$ has no small separators, nor can Weisfeiler–Lehman.

Guess who got a PhD doing this kind of stuff...


Why can't DFA's have 0 exiting arrows for some input symbols? Suppose you are in a middle of computation on a non accepting state and at this point, an input of 0 is rejected by the DFA. But, according to Sipser's formal definition, you must still draw an exiting arrow for input 0 from this nonaccepting state, which is just redundant. Why not draw no arrows at all for 0?

This is part of the (usual) definition of DFAs. It's hard to argue with a definition.

While it's hard to argue with a definition, one can ask why the object was defined in a certain way. Here one answer is that we want our automaton to always be at a particular state, whatever happens. In other words, we want the transition function to be a function rather than just a partial function. It is a matter of taste.

Some people allow the transition function to be partial, and still call the resulting model DFA, though this is probably less common than Sipser's definition. The two definitions are almost equivalent – accommodating a partial transition function takes at most one additional "sink" state.


foresightful acceleration and decelerations I am programming a CNC machine (using matlab). In order to generate a surface with a "high" shape accuracy (order of $1\mu m$) and "small" micro roughness (order of few nm) I need to make sure that no large acceleration/decelerations takes place, because this would induce vibrations. If the amplitude of these vibrations exceeds approx. $50nm$ they would generate unwanted structures on the machined surface.
Since most people are not familiar with the CNC context, I like to transfer the problem to a car, which is driving down a street in 2D. As input to the program I have a 2D point cloud $(x,y)$, which represent the ideal path. The goal is to move along this ideal path as quickly as possible. However, not only should the change in position $(x, y)$ be smooth, but also the change of the accelerations $(a_x, a_y)$ -- we have to avoid vibrations.
The main problem I am currently facing is the deceleration. Since I like to move along the path as fast as possible, I accelerate the car till I reach it's maximal velocity. However, my code does not work well, if I reach a sharp edge. In order to stay within the given path the car has to "look ahead" and decelerate way before reaching the edge.  Hence, I need to implement a foresightful driver. Are there simple methods available for this task? How would you implement this?
Inputs: The input is a dense point-cloud $(x,y)$ with a step side of $\Delta x = 1\mu m = \Delta y$. This raster is only used to define the surface.
Outputs: In order to achieve the high accuracy I have to use an external reference, which define a fixed time interval $\Delta t$. The path is defined as point-cloud $(x,y)$ in such a way, that the machine (car) gets one point per time interval:

$$x_1 y_1$$
$$x_2 y_2$$
$$x_3 y_3$$

Hence, the velocity and the accelerations are defined by the point-cloud itself. Each point must be accurate to the $1nm$ level.
===
There are robotic communities, which did these kind of calculations. Here is one example: Link.

I think an approach that will work is to "work backwards" through the path, keeping track of the maximum velocity that can be used at that point (subject to the restrictions on acceleration), then "work forwards" along the path, assigning a velocity at each point (subject to the restrictions on acceleration).
Represent the path as a sequence of evenly spaced points $P_1,\dots,P_n$, i.e., $P_1$ is the start of the path, $P_n$ is the end of the path, and $\|P_{i+1}-P_i\|_2$ is the same for all $i$.  At each point $P_i$, you know the direction $D_i$ the car will be heading: $D_i$ is a unit-length vector that is tangent to the path at that point, so we can approximate $D_i = (P_{i+1}-P_{i-1})/\|P_{i+1}-P_{i-1}\|_2$, using vector arithmetic.  I'll describe an algorithm to compute speeds $s_1,\dots,s_n$ so that $s_i$ represents the speed of the car at point $P_i$, and so that the acceleration constraints are satisfied.  Then the car's velocity vector at point $V_i$ will be $V_i = s_i D_i$.
What constraints do the acceleration constraints impose on the $s_i$?  Well, I'll assume your goal is to impose an upper bound on the maximum acceleration allowed: in particular, I'll assume we have a constant threshold $c$ and we require that the acceleration vector $A_i$ satisfies $\|A_i\|_2 \le c$ at every point.  Notice $$A_i = {V_{i+1} - V_i \over \|V_i\|_2/\|P_{i+1}-P_i\|},$$ so the constraint $\|A_i\|_2 \le c$ becomes
$$\|s_{i+1} D_{i+1} - s_i D_i\|_2 \le c s_i / \|P_{i+1}-P_i\|.$$
Given $s_{i+1},D_i,D_{i+1}$, we can obtain an upper bound on the maximum allowable $s_i$ that is consistent with this constraint, as the constraint is equivalent to
$$\|s_{i+1} D_{i+1} - s_i D_i\|_2^2 - c' s_i^2 \le 0,$$
where $c' = c \|P_{i+1}-P_i\|$ is a known constant. The left-hand side of that is a quadratic function in $s_i$, so you can efficiently compute an upper bound on $s_i$ by solving a quadratic equation.  Moreover, given an upper bound on $s_{i+1}$, we can obtain an upper bound on $s_i$ by replacing $s_{i+1}$ in the equation above with the upper bound and solving for the upper bound on $s_i$.
So, our strategy during the backwards pass will be: at each point $P_i$, we will compute an upper bound $u_i$ on the maximum speed $_i$ that the car can be permitted to have at that point.  In particular, we'll choose $u_i$ so we're assured that if the car has speed $u_i$ or less at $P_i$, then there is a way to complete the path so that from $P_i \ldots P_n$ the car satisfies all the constraints.  We've already described how to do this: given $u_{i+1}$ (an upper bound on $s_{i+1}$), we described above how to compute $u_i$ (the upper bound on $s_i$).  Thus, during the backwards pass, we will iterate through $i:=n,n-1,\dots,1$, setting at each step $u_i$ based on $u_{i+1}$.  At the end of the backwards pass, we have computed all of the $u_1,\dots,u_n$.
Next, we will do the forwards pass, to assign a speed at each point.  Iterate through the points in the order $i:=1,2,\dots,n$.  At each step, we'll compute $s_i$ based on $s_{i-1}$ and $u_i$.  In particular, the acceleration constraints impose a constraint on $s_i$: $\|s_{i} D_{i} - s_{i-1} D_{i-1}\|_2^2 \le c' s_i$.  We also have the constraint $s_i \le u_i$.  You can solve this to find the maximum possible value of $s_i$ (it involves solving a quadratic equation), and assigning $s_i$ this value.  Continue forward along the path, until you have assigned speeds $s_1,\dots,s_n$ for the entire path.
The result will be a valid plan for how to traverse the path.  In particular, at point $P_i$, the car will be travelling at speed $s_i$.  While at point $P_i$, you will accelerate or decelerate the car so that by point $P_{i+1}$ it is travelling at speed $s_{i+1}$.  This can be done by using the gas pedal or brake pedal to accelerate by $A_i \cdot D_i$, where $A_i = s_{i+1} D_{i+1} - s_i D_i$ (this will ensure acceleration in the $D_i$ direction of the acceleration vector $A_i$), using the steering to stay on the road (this will ensure acceleration in the direction perpendicular to $D_i$ to stay on the road).
This solution assigns the maximum possible speed at each point, and thereby traverses through the path in the fastest way possible, while respecting the limits on acceleration at every point along the path.


How do you get a regex from this DFA? I've been trying for hours. I'm teaching myself automata theory right now and I have this DFA:

And I'm trying to create a regex from it by removing q1 first and then q2. I already managed to remove q1 by doing it like this:

But now I'm not sure how to continue. The next step I'm trying to do is remove q2 and then read the regex from it. Even after trying to wrap my head around it for a long time I didn't really get it. Hopefully someone here can help me :)

By reading a 0, your DFA switches its state from right to left,
By reading a 1, it switches state from up to down.
So to reach your final state $q_3$ your DFA has to read an odd number of 1's and an even number of 0's.
Therefore your language is $L=\{w \in \{0,1\}^*|  |w|_1 mod  2 = 1, |w|_0 mod 2 = 0  \}$