New answers tagged

2

If RAM is a Random Access Machine (i.e., a rudimentary computer with registers, memory and assorted instructions), the answer is just "build a DFA that recognizes the same language, simulate that DFA in code". I.e., have a transition table that tells you the next state for each combination of state and input symbol; start in the start state, check ...


2

Erdős and Gallai showed in their paper Solution of a problem of Dirac then the chromatic number of a non-complete regular graph is at most $\frac{3}{5}n$. Caccetta and Pullman constructed in their paper Regular graphs with prescribed chromatic number connected $k$-chromatic regular graphs on $n$ vertices for all $k > 1$ and $n \geq \frac{5}{3}k$. You can ...


0

Your representation is fine. Store the pieces in sorted order, sorted by their $x$-coordinate. The first two operations are straightforward to implement. Computing the maximum takes a little more work but can be implemented in linear time. Basically, we are merging two sorted lists. Let $P_1,\dots,P_m$ be the interval of $x$-coordinates of the pieces of $...


1

A similar question has been asked before, that may answer your question, here. Quoting the answer: This is basically an instance of the line segment intersection problem. One standard approach is to use a sweep line algorithm. For instance, the Bentley-Ottman algorithm would be a reasonable choice, and is not too difficult to implement. At each iteration ...


Top 50 recent answers are included