An algorithm to find highest lines in at least one point Suppose we have $n$ lines $L_1, L_2, \dots, L_n$, where $L_i$ has the equation $y = a_i x + b_i$. We call $L_i$ the highest line at $x_0$ if for each $j \in \{1, 2, \dots, n\}$

$$a_i x_0 + b_i \ge a_j x_0 + b_j.$$

Goal: Find an algorithm in $O(n \log n)$ time to return a set of lines that are the highest lines in at least one point.
Hint: Use the divide and conquer technique.

Since we should use divide and conquer technique, I think I should split the problem into two subproblems with size of $n/2$ and try to solve these two first. I don't know what to do next. Thanks in advance.

If the lines are unlimited (as they seem to be) then the way to go seems to divide the lines by their slope.

Preprocessing:

Sort all the lines lexicographically by their slope and constant term. This allows to remove each line which is parallel to some higher-placed line. The ordering is also used to split the lines into subroups depending on their slope later on.

Recursion:

Divide the lines into lines with positive and negative slope. For each group call recursion. From each recursion we get two lists, a list of top-lines (ordered as they appear on top from left to right) and a list of top-intersections of the top-lines (ordered by x-coordinate) corresponding to the points where one line takes over the previous one.

Now we only need to combine the two results we got from recursion. The algorithm passes through the intersection-point lists in parallel, going through positive-slope lines from right to left, and through negative-lines from left to right until the x-coordinates of the intersections meet. To do this properly, we need always make the step on the side with higher y-coordinate.

(I strongly suggest to draw it, it's easier to see in a picture. Imagine bunch of lines forming a "U"-shape and the algorithm descends with equal vertical speed on both sides until it reaches the lowest point of the "U"-shape.)

In this way we found a "middle" point where one positive- and one negative-slope top-line meet in a new top-intersection. From the list of lines we know which lines meet there and we can compute the intersection point they share (the lowest point of the "U"-shape).

We can now construct the total list of intersections of top-lines (all the point we went through + the new intersection point we found in the middle) and the list of the corresponding top lines.

Note that it might happen that all the positive-slope intersection might be too much to the left (so we do not get a "U"-shape). In that case we only get one positive- and one negative-slope line as a result, intersecting in an "V"-shape.

Now, how to split the groups in the recursion? Well, simply realize that by tilting (by less than 90 degrees) what the algorithm understands us "horizontal" none of the necessary properties is violated (within the subgroup). Thus the algorithm can again split the groups into smaller groups, while the left-right orderings remain consistent. So in fact we don't want to split lines into positive and negative slope, but simply split by the median slope each time. (splitting by the horizontal direction just makes it easier to understand)

Complexity:

Each level of recursion is linear-time in respect to the number of lines (going through lists in parallel, concatenation of lists, etc.). Since the lines are already ordered by their slope (from preprocessing), we can always split by the mean slope in linear time. So the total time is O(nlogn).

Hope the description is somewhat clear. I did not go into details as that would be lengthy.

SORRY: I MIS-READ THE PROBLEM AS FIXING THE X COORDINATE FIRST:

Evaluate each line $L_i$ at $x_0$, yielding $y_i$.  Collect all ordered pairs ($L_i$,$y_i$) and sort on the $y$ values.  Top pair yields the desired line. [note: there may be more than one 'top line', in which case they will all be at the 'top' with the same $y$ value]


Writing programs with a block programming environment vs. Writing programs using high level prgramming language I'm a GCSE Computing student and I've been asked to compare writing programs in a block programming environment (I think this means using programs such as Scratch or App Inventor but I'm not entirely sure) compared to writing programs using high level programming languages such as Python, Java etc.
I'm honestly not trying to ask you to do my work for me, I just desperately need some help on the advantages and disadvantages of both ways of writing programs because we haven't really been taught it by my teacher and I haven't found much on the Internet about it.

Scratch is a Turing-complete language, so any problem that can be solved with computers can be solved using Scratch (just like Python or Java).  However, you would have to reduce the problem to one that can be solved with Scratch.

In application, Scratch can't do anything that you may be interested in as an engineer, such as hardware interfacing.

I'm doing the same course right now and I'm having the same problem but i do know that block programming languages like app inventor are easier to  use because you don't need to (effectively) learn a completley new language and the syntax that goes with it all you need to learn is what task the blocks perform and how they fit together.


Data structure for maintaining large space-efficient filtered array How does one implement a space efficient data structure that satisfies the requirements below?

You have a large array
You have a filter which tells you which elements in that large array are to be deleted
Lookup of i'th element in the array should be constant time
The space formerly occupied by deleted elements in the array should be available for further use.

I've explored approaches ranging from bloom filters to trees, but they violate one requirement or the other.

EDIT: Further clarification.

Space-efficient: Any space not used by elements of the array that have not been deleted by the filter, which we can term extra space or space for book-keeping, should be $O(1)$. We can probably relax this to allow any solution that gets close to $O(1)$ extra space. $O(n)$ extra space is undesirable.

Array in the context of this problem is an array-like collection where you can get the $i$th element in constant time. You lookup by index here.

I suspect amortized performance bounds should be fine.

The filter takes each element of collection and returns 0/1 corresponding to delete/no delete.

There is a simple and clean solution that satisfies all of your requirements.

To delete elements, you scan the set of array indices (from 1 to $n$), querying the filter on each and deleting each element that is to be deleted, compacting the array as you go (to shift everything after the deleted element forward one slot).  The deletion operation can be implemented in $\Theta(n)$ time, with a single linear scan.  This satisfies all of your requirements.  (Note that you did not specify any restriction on the running time of the deletion operation.)  In particular, it is space-efficient: it does not require any extra space (it has 0 space overhead, since after deletion, all of the space that's not in use for storing undeleted array elements is immediately available for other use).  Looking up the $i$th element of the array takes constant time, thanks to the compaction: you just index into the $i$th element of the compacted array.

If for some reason this solution is not acceptable to you, then you need to re-think the requirements more thoroughly and edit the question to pose the exact set of requirements more carefully.

Given the problem as you've stated it, I don't think it will be possible to do better than this trivial solution.  You can't do better than $\Theta(1)$ time for lookup.  You can't do better than 0 space overhead.  And I don't think you can do better than $\Theta(n)$ time for deletion, given how you specified the interface to deletion (which works by specifying a filter that is an oracle that, on input $i$, tells you whether index $i$ should be deleted or not).  Even just figuring out which elements of the collection to delete requires querying the filter on all $n$ possible indices, which takes $\Theta(n)$ time.  So, I don't think you can do any better than $\Theta(n)$ time for the deletion operation -- and in particular, I don't think you can do any better than the above scheme, at least not with this specification of how the filter is provided.

Lookup of i'th element in the array should be constant time

The only thing I could think of is a hashtable

  The space formerly occupied by deleted elements in the array should be
  available for further use.

This could be achieved easily by having an array of pointers or a queue of pointers that way whenever you decide to create a new item, you can choose to pop from the queue or array. When you delete/don't need the object in the array, you enqueue it. If the queue or array is empty, then you create a new object.


What is the $\mathcal O$ of subtraction-based GCD algorithm? Subtraction-based algorithm for finding the greatest common divisor works like this:

For two integers a and b (a > 0, b > 0),
if a > b, then gcd(a, b) = gcd(a-b, b)
else if b > a, then gcd(a, b) = gcd(a, b-a).
else if a = b gcd(a, b) = a

What is the $\mathcal O$ of this algorithm?

Suppose that $a,b$ are the two input numbers. At each step of the algorithm, the sum $a+b$ decreases, since (assuming $a > b$), the new numbers are $a'=a-b,b'=b$, and $a'+b'=a < a+b$ (since we stop when $b=0$). Thus the algorithm terminates in at most $a+b$ steps. This is almost tight: if $b = 1$, then the algorithm terminates in $a$ steps.

Summarizing, on inputs $a,b$, the number of steps (or arithmetic operations) is at most $a+b$, and could be as bad as $a$. In terms of the length $n$ of the input (number of bits needed to represent it), the number of operations is at most $O(2^n)$ (since $a,b \leq 2^n$), and could be as bad as $\Omega(2^n)$ (when $a = 2^n,b=1$). Thus the worst-case running time (as measured by number of steps) is $\Theta(2^n)$, where $n$ is the input length.

Try calculating gcd (1, 0) using that "algorithm". It doesn't seem to be an algorithm, because it never finishes. Fix your question.  Also, please think about the problem more carefully before asking.


What is a mod b if a < b? So when you are decrypting an encryption with modular arithmetic, I know the modulus operator (%) gives the remainder of a/b, but what if a is less than b?

For example, 5%2 is 1, since the answer is 2 remainder 1. But for something like 2%9, how do you find the answer?

If $a,b$ are both positive integers, then we can always write $a = kb+\ell$ where $0 \leq \ell < b$. We call $\ell$ the remainder and $k$ the quotient. In your first example, $5 = 2 \cdot 2 + 1$ so 5 % 2 == 1. In your second example, $2 = 0 \cdot 9 + 2$, so 2 % 9 == 2. More generally, if $a < b$ then a % b == a.

There is also a rule for signed integers, but unfortunately I can't remember it. Also, 0 % x == 0 whenever $x \neq 0$, and x % 0 will cause an exception ("division by zero").

The answer is 9.  2 / 9 is 0r9.  The modulus operator returns the remainder of integer division, since 9 goes into 2 0 times the operator returns 9.


Are compilers able to detect alternating accesses to arrays and interleave them in memory? Is it possible to design a compiler which optimizes a loop in which arrays are accessed in alternate fashion? For example like this:

// int[] a,b
int sum = 0;
for(int i = 0; i < n; i++)
{
  sum += a[i] + b[i];
}

With the usual sequential array storage, a[i] and b[i] may be far away from each other in memory. Therefore, I think a good compiler optimization would detect that a[i] and b[i] are always accesses at the "same" time, and store the arrays interleaved, that is a[0] b[0] a[1] b[1] ... so that one memory access may retrieve both a[i] and b[i].

Some work has been done that matches your description. For instance:

Compiler-directed array interleaving for reducing energy in multi-bank memories. by Delaluz, V.  Design Automation Conference, 2002. Proceedings of ASP-DAC 2002. 7th Asia and South Pacific and the 15th International Conference on VLSI Design. Proceedings.

describes a such an optimization.

Your example is not complete, the arrays are not declared anywhere, nor are they initialised anywhere.

I suspect in a general programming context this sort of optimisation would be "more trouble than it's worth". Most arrays are accessed from more than one place so a compiler would often have to guess which place was the most important. Also many arrays would not be able to be modified in this way because they pass over compilation unit boundries either as parameters to functions or as global variables. Finally it would make debug information more complex.


Not quite-infinitely expandable human-friendly naming system? This may be a known problem, with known approaches, but I can't find the right way to search for it.

I would like to name points along a line of unknown final length such that their name reflects their relative position to all other named points on that line.  One should be able to insert an arbitrary number of names at any point along the line including outside the existing first and last named points. A lexicographical sort of the point names would always result in a list of points in a monotonic order.

An order of magnitude estimate of the total number of points to be ultimately named can be supplied up front

Additional restrictions:

Names must be stable, no-renaming after initial assignment
Names may be constructed from a limited character set: 25 lowercase letters a-z with 'L' removed.
The naming scheme should not require an extreme fan-out of name length when adding names either outside the existing points or between two adjacent points. E.g. Imagine that I want to add something before the name 'a', that wouldn't be possible while maintaining linear order during sorting.  Starting with 'b' only delays the issue.  Same for z on the other end.

Names should be of the shortest possible length such that a human could easily glance at one and then write it out elsewhere for most names.

It is highly likely that one would want to insert names between previously adjacent names, and then later between adjacent named points in that previous insertion.

The real-life use case for this is the creation of spatial names for all features of a given kind, say genes, in a species when we don't know in advance the total set of features.  This is because different individuals only contain a subset of the total sequence space that the whole population of organisms encompass.  The problem is easy to solve with static sets of sequences, but not if you allow them to expand at any point along the line (chromosomes) with the addition of new information.  The set sizes of interest encompass 10^5 -10^7 items.

As David points out in a comment, you are asking for an impossible thing because the lexiocgraphic order does not have infinite descending chains, and so you will run out of names if you keep adding points on the far left side. So forget the lexicographic order. (You may keep it if you have an upfront upper bound on the number of points.)

You can use the naming scheme x_N_M where N and M are numbers. Think of this as indexing a point with the fraction N/M. Because fractions are dense, you will never run out of them. To insert a new point on the left of the leftmost point x_N_M, name the new point x_N_2M. To insert on the right of the rightmost point x_U_V name the new point x_2U_V. And to insert between adjacent points x_A_B and x_C_D, name the new point x_E_F where E/F is the average of A/B and C/D.

No way.

Let's say you have n possible names. I insert the first point into the list, and you name it. However you name it, either there are only $n/2$ possible names larger or only $n/2$ possible names smaller than the name you chose.

I insert the second point so that it is in the range with fewer names. You name it. Now you have at least one range with only $n/4$ possible names. I insert the third point into the range with fewer possible names, and so on. After inserting k points, there will be a range where you have only $n/2^k$ possible names, and I can make you fail when $k ≥ \log n$.

(I actually ran into an implementation of this in some widely shipping software a few years ago, and users did systematically create this situation where it failed, so I had to add some rather horrid code that would at some point rename everything).


Can we build a nondeterministic decider PDA using two PDAs accepting a language and its complement? When talking about turing machines, it can be easily shown that starting from two machines accepting $L$ and its complement $L^c$, one can build a machine which can fully decide if a word is inside $L$ or not.

But what about PDAs? starting from two different PDAs, one accepting $L$ and one accepting $L^c$ can we build another PDA, which accepts $L$, and only crashes or halts in non-final states (rejects) when $w\notin L$?

Yes, it is possible to do so. Although a given PDA may have $\varepsilon$ loops that can induce infinite computation, we can sidestep this by converting the PDA to a CFG, then back to a PDA (using the standard methods). The second PDA is guaranteed to halt on all inputs (this is not too hard to see if you know the conversion method - essentially you guarantee that either a non-terminal from the CFG is added to the stack, or a terminal is read from the input at each broad step and the nondeterminism takes care of the rest, or equivalently, CFGs can always be parsed).

So then we can take the PDA for $L$, apply this transition, and we get a machine that always halts, and only halts in an accept state if the input is in $L$.

DPDA class is close under complement.

if you have a PDA for $L$ and an other one for $L^c$ then $L \in \{ L\subset \Sigma | \quad \exists DPDA\quad  \text{ such that} L=L(DPDA)\} $ so you can make a non-deterministic decider for L.

After Edit:

@Ali.S:
It seems you are right. Although it’s difficult for me to make a PDA for $L- WW^R$.

But again I think it’s possible to have non-deterministic decider!

Let $M_1$ be a non-deterministic acceptor for $L$ and $M_2$ be a nondeterministic acceptor for $L^c$.
$\forall w \in L^c$ , $M_2$’s answer is “Yes” and it means $\forall w \notin L$ , $ M_2$ will halt.
We can construct a non-deterministic decider as follows:

Put a new initial state and add two lambda transition from it to $ M_1$ and $ M_2$ initial states.
Wherever in $M_2$ we have “Yes” we change it to “No” and if it has “No” answer we stuck in loop.
Wherever in $M_1$ we have “yes” it is what we wanted and if it has “No” answer we stuck in a loop.

By this way if $w \in L$ if PDA decide to goes $M_1$ initial state and continue it will get answer "Yes" and halts. if it chooses to start by $M_2$ initial state and continues it won't get answer "No". if $w \notin L$ and PDA choose to goes in $M_1$ if will get stuck in loop and if it goes in $M_2$ it will get answer "No" and halt.


How/when is calculus used in Computer Science? Many computer science programs require two or three calculus classes.

I'm wondering, how and when is calculus used in computer science? The CS content of a degree in computer science tends to focus on algorithms, operating systems, data structures, artificial intelligence, software engineering, etc. Are there times when Calculus is useful in these or other areas of Computer Science?

I can think of a few courses that would need Calculus, directly. I have used bold face for the usually obligatory disciplines for a Computer Science degree, and italics for the usually optional ones.

Computer Graphics/Image Processing, and here you will also need Analytic Geometry and Linear Algebra, heavily!  If you go down this path, you may also want to study some Differential Geometry (which has multivariate Calculus as a minimum prerequisite). But you'll need Calculus here even for very basic things: try searching for "Fourier Transform" or "Wavelets", for example -- these are two very fundamental tools for people working with images.
Optimization, non-linear mostly, where multivariate Calculus is the fundamental language used to develop everything.  But even linear optimization benefits from Calculus (the derivative of the objective function is absolutely important)
Probability/Statistics. These cannot be seriously studied without multivariate Calculus.
Machine Learning, which makes heavy use of Statistics (and consequently, multivariate Calculus)
Data Science and related subjects, which also use lots of Statistics;
Robotics, where you will need to model physical movements of a robot, so you will need to know partial derivatives and gradients.
Discrete Math and Combinatorics (yes!, you may need Calculus for discrete counting!) -- if you get serious enough about generating functions, you'll need to know how to integrate and derivate certain formulas. And that is useful for Analysis of Algorithms (see the book by Sedgewick and Flajolet, "Analysis of Algorithms"). Similarly, Taylor Series and calculus can be useful in solving certain kinds of recurrence relations, which are used in algorithm analysis.
Analysis of Algorithms, where you use the notion of limit right from the start (see Landau notation, "little $o$" -- it's defined using a limit)

There may be others -- this is just off the top of my head.

And, besides that, one benefits indirectly from a Calculus course by   learning how to reason and explain arguments with technical rigor. This is more valuable than students usually think.

Finally -- you will need Calculus in order to, well, interact with people from other Exact Sciences and Engineering. And it's not uncommon that a Computer Scientist needs to not only talk but also work together with a Physicist or an Engineer.

To these other excellent answers I add this point: rigor in testing.

In creating test cases for some applications I have had to make use of calculus to predict expected running times, memory sizes, and choose optimal parameters when tuning data structures. This includes understanding expected rounding error, etc.

While statistics is mentioned in other answers, I would like to specifically mention Monte-carlo algorithms, such as optimization algorithms and some frugal streaming algorithms that are based on Mathematical principles that include calculus.

Specific industries where I have worked where calculus was required include:

Finance (creating a trading platform)
Insurance (numerical integration of insurance policies in what-if scenarios to compute expected policy losses)
Logistics (optimizing the consolidation of transportation routes)
Signal processing


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.

In addition to what Yuval Filmus wrote, let me remark that the transition "function" not actually being a function but, rather, a partial function may impair the elegance of some proofs (or make them unnecessarily harder). Consider, for instance, the proof of the pumping lemma; in the usual definition, you let $p$ be the number of states and then take a word $w$ which the DFA accepts and is longer than $p$. The argument then is that, when you consider the trace of states which the automaton takes to accept $w$, there is at least one state that comes up twice (by the pidgeonhole principle). This is then used to derive a loop and, hence, pump the "middle" part of $w$.

This argument falls flat on its face when the transition function is partial. Then there is no guarantee the DFA does not stop and accept $w$ previously to running into the loop.

(Of course, here I am talking about the DFA accepting early whereas you were possibly referring to only nonaccepting states having incomplete transitions, but I am sure you get the idea.)


Language of TMs that accept some x in less than 50 steps. Is it in co-RE? L = {M | M is a TM and there exists an input that the TM M accepts in
less than 50 steps}

I need to find a minimal
class it belongs to between R/ RE/ co-RE/ not in RE∪co-RE. I managed to show that it is in RE with a TM. I think its not in co-RE, because it has to check every input to know wheter a TM M belongs to L. and there are an infinite amount of inputs. I tried to use mapping recursion with ATM, but that failed. Would appreciate any advice, thanks.

Maybe that will help ?

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-045j-automata-computability-and-complexity-spring-2011/lecture-notes/MIT6_045JS11_lec09.pdf

Page 42
Credits : Nancy Lynch MIT

Applications of Rice’s Theorem

• Example 3: Another property that isn’t a language property and is decidable

{ M |M is a TM that runs for at most 37 steps on input 01 }

– Not a language property, not a property of a machine’s structure.

– Rice doesn’t apply.

– Obviously decidable, since, given the TM description, we can just simulate it for 37 steps.

This is my solution:

reduction from ATM to L

On input M,w:
return a machine M', that on input x:
runs w on M, and if M accepts, M' accepts(in a single step)
if M decline or loops, decline

if M accepts w, L(M')=Sigma* and therefore is y in Sigma* that M' accepts in a single step(in fact it's true for all y in Sigma*)-that's less 50.
if M loops or declines, L(M')=emptyset and therefore there is no word the M' accepts in less than 50 steps, because M' rejects all words.

good luck on your hw!


Is there a way to make chess an absolutely fair game? Chess is usually considered a mostly "fair game" between White and Black because the opening position of pieces has mirror symmetry (between players). In practice it also appears to be a fair game because it is combinatorially complex, so if White has a first-move-advantage, it is hard to detect in actual play.

What are some examples of changes in the rules of chess where the game can be made exactly mathematically fair, including eliminating any possibility of White's possible first-move-advantage, and without adding any chance events (such as a coin toss as to who moves first)?

We can run a pair of games, sequentially, where player one first plays white, then black.

Let's write W for win, L for lose and D for draw, from the point of view of player one. In the cases WW,WD,DW, player one wins the match. In the cases LL,LD,DL, player one loses the match. In the cases WL,LW,DD, the match is a draw.
(If a draw match is undesired, play another match.)

Simple. Throw a coin to decide who moves first.

In a single game, white has a distinctive advantage. Usually you play tournaments where each side plays white and black equally often.


How can you prove 3^n is not O(n^2)? I can obviously tell by inspection that it is not true but I cannot figure out how to prove it with witnesses (C and k). Thanks!

Let's assume that $3^n = O(n^2)$.

This would by definition mean that there are real positive numbers $a$ and $b$ such that for any sufficiently large $n$ (or to say as $lim_{n \to +\infty}$):

$ an^2 \leq 3^n \leq bn^2 $

Dividing everything by $3^n$ we get:

$ a\frac{n^2}{3^n} \leq 1 \leq b\frac{n^2}{3^n}$

And since if we let $lim_{n \to +\infty}$ we get a contradiction:

$ 0 \leq 1 \leq 0 $

Hence inital statement is false and $ 3^n \neq O(n^2) $


Which law is this expression X+ X’.Y=X+Y Question. Name the law given and verify it using a truth table. X+ X’.Y=X+Y

My Answer.
X   Y   X’  X’.Y    X+X’.Y  X+Y
0   0   1   0       0       0
0   1   1   1       1       1
1   0   0   0       1       1
1   1   0   0       1       1

Prove algebraically that X + X’Y = X + Y.
L.H.S. = X + X’Y
           = X.1 + X’Y        (X . 1 = X property of 0 and 1)
           = X(1 + Y) + X’Y   (1 + Y = 1 property of 0 and 1)
           = X + XY +  X’Y
           = X + Y(X + X’)
           = X + Y.1          (X + X’ =1 complementarity law)
           = X + Y            (Y . 1 = Y property of 0 and 1)
           = R.H.S.      Hence proved.

My teacher marked my answer wrong. And told me to find the correct answer. Friends tell me is it a complementary law or distributive law or Absorption law? If it is absorption kindly tell me how to prove RHS and LHS algebraically.

One way of looking at this is as a consequence of distributivity, where $P+QR\equiv (P+Q)(P+R)$. Then you'll have
$$\begin{align}
X+(X'Y) &\equiv (X+X')(X+Y)&\text{distributivity}\\
&\equiv T(X+Y)&\text{inverse}\\
&\equiv X+Y&\text{domination}
\end{align}$$

X+X'Y=X+Y

taking LHS
X+X'Y=(X+X')(X+Y)      OR distributes over AND
1.(X+Y)                (X+X'=1)
X+Y=RHS                1 is identity for AND

Hence Proved


How can I calculate the maximum sum/product of sequence? I am looking for an algorithm in $O(N^2)$ that finds the maximum value that be obtained from a sequence of real numbers greater than 0 (e.g. $\{ 1, 2, 3 , 4\}$) by inserting a plus ($+$) or multiplication ($\times$) between the elements.

Really not having much luck and wondering if anyone has any insight on this?

It must follow normal order of precedence.

For example with $\{1,2,3,4\}$, the maximum is $1+2\times3\times4 = 25$
not $1\times2\times3\times4 = 24$ and not $1\times2+3+4 = 9$.

Let's say all numbers are positive (i.e. $\geq0$). Before and after $0$s you should always use $+$. This could also solved in $O(n^2)$ by first finding all zeros and then find maximum value for each group separated by zeros. Inside each group, for positive numbers, you should always use $\times$ except in $1$ cases, if ones are in the middle of a group, still you should choose $\times$. But when ones are at the very beginning or at the very end of the group, you should choose $+$.


What Do Logical Operators In a Grammar Mean? Is there a way to figure out what the following CFG accepts?

$\qquad\begin{align}
  S &\to S \vee T \mid T \\
  T &\to T \wedge F \mid F \\
  F &\to p \mid\; \thicksim p
\end{align}$

I'm confused by the boolean algebra symbols. I know the first is S or T, the second is T and F and the third is not p but I'm not sure how they affect the grammar itself.

A grammar generates a language, it doesn't accept it. Automata accept languages.

The whole point of gramars is that they are easily able to generate quite complex languages. Even regular languages (accepted by finite automata or denoted by regular expressions) can be very hard to describe in simple terms.

In this case, the grammar generates (a subset of) logical formulas, with connectives and ($\wedge$), or ($\vee$), and not ($\thicksim$).

This accepts all the expressions involving 1 variable, sum of products (minterms) expressions.

This grammar makes the priority of $\thicksim$ greater than $\wedge$ which is in turn greater than $\vee$, in this grammar, because if you generate the parse tree, $\thicksim$ will be at the leaves.


Why is the quantity of sentences not finite? I'm currently studying formal languages. My lecture states that, while the words of a language are finite, the sentences build with the underlying grammar are not. But I don't get why this should be generally true. I can imagine grammar which leaves me with a finite amount of sentences.

I agree that one could create a language with infinite amount of sentences but I can't see why it should be generally the case.

Before I can tell you why there are arbitrarily long sentences in English, I would like to point out that 1 is a number,
2 is a number,
3 is a number,
4 is a number,
5 is a number,
6 is a number,
7 is a number,
8 is a number,
9 is a number,
10 is a number,
11 is a number,
12 is a number,
13 is a number,
14 is a number,
15 is a number,
16 is a number,
17 is a number,
18 is a number,
19 is a number,
20 is a number,
21 is a number,
22 is a number,
23 is a number,
24 is a number,
25 is a number,
26 is a number,
27 is a number,
28 is a number,
29 is a number,
30 is a number,
31 is a number,
32 is a number,
33 is a number,
34 is a number,
35 is a number,
36 is a number,
37 is a number,
38 is a number,
39 is a number,
40 is a number,
41 is a number, and
42 is a number. Of course, one could also think of other thing to point out, for example, that the son of the
son of the
son of the
son of the
son of the
son of the
son of the
son of the
son of my
son is my
grand
grand
grand
grand
grand
grand
grand
grand
grand
son. I hope I did not make a mistake there, or two mistakes, or three mistakes, or four mistakes, or five mistakes, or six mistakes, or seven mistakes. Let us stop there, as 7 is a nice number.

Do you still think that there is a bound on the length of grammatically correct English sentences?

Since quotes are allowed in sentences, and quotes do not have to be grammatically correct, then there must be an infinite number of sentences:

The man said "Blah blah blah blah blah...".


Is an NP-hard problem which is in NP is NP-complete? I'm reading Combinatorial Optimization book by Bernhard Korte and Jens Vygen. There's a part that they said:

It is an open question whether each $NP$-hard decision problem $A \in NP$ is $NP$-Complete, because of the difference between polynomial reduction and polynomial transformation.

I understand that, but when I read wikipedia article about NP-complete, I see this picture
According to wikipedia, a decision problem is $NP$-complete when it is both in $NP$ and $NP$-hard, which make me confused. Can someone help me understand the difference between the book and wikipedia?

Definition 15.15. Let P1 and P2 = (X, Y) be decision problems. Let f : X → {0, 1} with f (x) = 1 for x ∈ Y and f (x) = 0 for x ∈ X \ Y . We say that P1 polynomially reduces to P2 if there exists a polynomial-time oracle algorithm for P1 using f
Definition 15.17. Let P1 = (X1, Y1) and P2 = (X2, Y2) be decision problems. We say that P1 polynomially transforms to P2 if there is a function f : X1 → X2 computable in polynomial time such that f (x1) ∈ Y2 for all x1 ∈ Y1 and f (x1) ∈ X2 \ Y2 for all x1 ∈ X1 \ Y1.

Check the definitions of NP-completeness and NP-hardness. I suspect they use Karp reductions for one and Cook reductions for the other.

Then, the quote makes sense: it is indeed unknown if Cook reductions and Karp reductions are equivalent in this sense. This is related to the question whether co-NP = NP; Cook reductions can not separate the two but Karp reductions might. See here for some details.

However, the authors use different definitions than (most of) the rest of the CS world: the widely accepted standard is to use Karp reductions. I recommend you read our reference question (and get a better book).

To be fair, the authors want to talk about optimization problems, in which case they need a notion of (NP-)hardness that is not tied to decision problems. Karp reductions won't get them there directly.

They picked a poor way out, arguably, by defining the notions differently from everybody else. There are cleaner (but more involved) ways, defining complexity classes for optimization problems rigorously, providing them with their own types of reduction, and tying them to the classic decision-problem classes using threshold languages.

NP is an abbreviation of the term "non-deterministic polynomial". Informally, it means a problem belonging to the class NP can be 'solved' (formal term is 'decided') by using a non-deterministic Turing machine (TM) in the number of steps which are polynomial in the input size. Input size is usually no. of TM cells used by the input problem encoded in certain format. Intuitively, it is an amount of memory required to write input on TM tape.

You should note that NP is a complexity class of problems and not the problem instance itself. The complexity class is a set of problems which requires similar amount of resources (time and/or memory space) to solve.

Meaning of the term 'Hard': I think you have misunderstood meaning of the term 'hard'. Hardness is the measure for comparing amount of resources needed to solve problems in various complexity classes. For a problem in NP, time  requirement is polynomial in input size. Problems in the class NP-hard need at least polynomial no. of steps, but they may actually need more. Informally speaking, all problems which have same or more resource requirement (hence at least that much hard to solve) than problems in NP are NP-hard.


Is this grammar really LL(1) while not being LR(1)? $S \rightarrow S$, $L(G) = \{\}$

LL(1) analysis:

We estabilish $FIRST(S)$ to be empty and $FOLLOW(S)$ to be $\{\$\}$.
$FIRST(S)$ doesn't contain ε, so the parse table looks like this:

+---+---+
|   | $ |
+---+---+
| S |   |
+---+---+

and correctly rejects any input including ε.

LR(1) analysis:

We start with the initial state 0:

$S' \rightarrow \bullet S [\$]$

calculate its closure:

$S' \rightarrow \bullet S [\$]$

$S \rightarrow \bullet S [\$]$

and the only transition, which leads to state 1 on S:

$S' \rightarrow S \bullet [\$]$

$S \rightarrow S \bullet [\$]$

State 1 has a reduce/reduce conflict.

Now, obviously there must be something I'm missing, since LL(k) grammars are a proper subset of LR(k) grammars. Would anyone care to point out the error?

I've just consulted a parsing book, and it indeed requires that $S \Rightarrow^+ S$ be impossible, if $S$ is the starting symbol, before a grammar is considered $LR(k)$. As you said yourself, this is not required for a grammar to be $LL(k)$.

Usually, it is implicitly assumed grammars 'behave' when we make statements about them, such as $LL(k) \subset LR(k)$. For instance, $S \Rightarrow^+ S$, absence of symbols not derivable from $S$, and absence of symbols not deriving terminal strings are all properties of 'well behaved' context free grammars.

If we assume these things, we are spared some weird oddities of context-free grammars: for example, if we have some grammar with starting symbol $S$, by adding a nonterminal $T$ and productions $T \to \epsilon$, $S \to T S$, we can force the grammar to have infinitely many parse trees for every string in the language it represents. In contrast, if we do assume 'well behaved' grammars, we are guaranteed only finitely many parse trees exist for any input.

I did not see why we should consider a useless grammar such as

S ::= S

Are there meaningful implications? The easy thing we can do is to require that we should "remove all useless symbols and production rules before generating LL and LR parsers."


Time Complexity analysis for Map-Reduce model I am trying to redesign my algorithm to run on Hadoop/MapReduce paradigm. I was wondering if there is any holistic approach for measuring time complexity for algorithms on Big Data platforms.

As a simple example, taking average of n (= 1 billion) numbers can be done on O(n) + C (assuming division to be constant time operation). If i break this massively parallelizable algorithm for Map Reduce, by dividing data over k nodes, my time complexity would simply become O(n/k) + C + C'. Here, C' can be assumed as the startup job planning time overhead. Note that there was no shuffling involved, and reducer's job was nearly trivial.

I am interested in a more complete analysis of algorithm with iterative loops over data and involve heavy shuffling and reducer operations. I want to incorporate, if possible, the I/O operations and network transfers of data.

S. Arora, B. Barak, Computational Complexity Modern Approach, Chapter 13 is a good introductory resource to this topic:

  Communication complexity concerns the following scenario. There are two players with unlimited computational power, each of whom holds an $n$ bit input, say $x$ and $y$. Neither knows the other’s input, and they wish to collaboratively compute $f(x, y)$ where the function $f : \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}$ is known to both. Furthermore, they had foreseen this situation (e.g., one of the parties could be a spacecraft and the other could be the base station on earth), so they had already — before they knew their inputs $x, y$ — agreed upon a protocol for communication. The cost of this protocol is the number of bits communicated by the players for the worst-case choice of inputs $x, y$.

See you are right but you know its quite hard to say a specific time complexity of map reducing. It depends upon the query. But in that case it should be o(nlogn/k)+c+c' because of k nodes. These all shorts of queries including a mapping phase of a map reducing texhnique follows a Btree concept.So from that place for inner computations we may say that its time complexity > o(nlogn)+c+c'.

Correct my suggestions please.


Time complexity of a compiler I am interested in the time complexity of a compiler. Clearly this is a very complicated question as there are many compilers, compiler options and variables to consider. Specifically, I am interested in LLVM but would be interested in any thoughts people had or places to start research. A quite google seems to bring little to light.

My guess would be that there are some optimisation steps which are exponential, but which have little impact on the actual time. Eg, exponential based on the number are arguments of a function.

From the top of my head, I would say that generating the AST tree would be linear. IR generation would require stepping through the tree while looking up values in ever growing tables, so $O(n^2)$ or $O(n\log n)$. Code generation and linking would be a similar type of operation. Therefore, my guess would be $O(n^2)$, if we removed exponentials of variables which do not realistically grow.

I could be completely wrong though. Does anyone have any thoughts on it?

The best book to answer your question would probably be: Cooper and Torczon, "Engineering a Compiler," 2003.  If you have access to a university library you should be able to borrow a copy.

In a production compiler like llvm or gcc the designers make every effort to keep all the algorithms below $O(n^2)$ where $n$ is the size of the input.  For some of the analysis for the "optimization" phases this means that you need to use heuristics rather than producing truly optimal code.

The lexer is a finite state machine, so $O(n)$ in the size of the input (in characters) and produces a stream of $O(n)$ tokens that is passed to the parser.

For many compilers for many languages the parser is LALR(1) and thus processes the token stream in time $O(n)$ in the number of input tokens.  During parsing you typically have to keep track of a symbol table, but, for many languages, that can be handled with a stack of hash tables ("dictionaries").  Each dictionary access is $O(1)$, but you may occasionally have to walk the stack to look up a symbol.  The depth of the stack is $O(s)$ where $s$ is the nesting depth of the scopes.  (So in C-like languages, how many layers of curly braces you are inside.)

Then the parse tree is typically "flattened" into a control flow graph.  The nodes of the control flow graph might be 3-address instructions (similar to a RISC assembly language), and the size of the control flow graph will typically be linear in the size of the parse tree.

Then a series of redundancy elimination steps are typically applied (common subexpression elimination, loop invariant code motion, constant propagation, ...).  (This is often called "optimization" although there is rarely anything optimal about the result, the real goal is to improve the code as much as is possible within the time and space constraints we have placed on the compiler.)  Each redundancy elimination step will typically require proofs of some facts about the control flow graph.  These proofs are typically done using data flow analysis.  Most data-flow analyses are designed so that they will converge in $O(d)$ passes over the flow graph where $d$ is (roughly speaking) the loop nesting depth and a pass over the flow graph takes time $O(n)$ where $n$ is the number of 3-address instructions.

For more sophisticated optimizations you might want to do more sophisticated analyses.  At this point you start running into tradeoffs.  You want your analysis algorithms to take much less than $O(n^2)$ time in the size of the whole-program's flow graph, but this means you need to do without information (and program improving transformations) that might be expensive to prove.  A classic example of this is alias analysis, where for some pair of memory writes you would like to prove that the two writes can never target the same memory location.  (You might want to do an alias analysis to see if you could move one instruction above the other.)  But to get accurate information about aliases you might need to analyze every possible control path through the program, which is exponential in the number of branches in the program (and thus exponential in the number of nodes in the control flow graph.)

Next you get into register allocation.  Register allocation can be phrased as a graph-coloring problem, and coloring a graph with a minimal number of colors is known to be NP-Hard.  So most compilers use some kind of greedy heuristic combined with register spilling with the goal of reducing the number of register spills as best as possible within reasonable time bounds.

Finally you get into code generation.  Code generation is typically done a maximal basic-block at a time where a basic block is a set of linearly connected control flow graph nodes with a single entry and single exit.  This can be reformulated as a graph covering problem where the graph you are trying to cover is the dependence graph of the set of 3-address instructions in the basic block, and you are trying to cover with a set of graphs that represent the available machine instructions.  This problem is exponential in the size of the largest basic block (which could, in principle, be the same order as the size of the entire program), so this is again typically done with heuristics where only a small subset of the possible coverings are examined.

Measure it with realistic code bases, such as a set of open source projects.  If you plot the results as (codeSize,finishTime), then you can plot those graphs.  If your data f(x)=y is O(n), then plotting g = f(x)/x should give you a straight line after the data starts to get large.

Plot f(x)/x, f(x)/lg(x), f(x)/(x*lg(x)), f(x)/(x*x), etc.  The graph will either dive off to zero, increase without bound, or flatten out.  This idea comes in handy for situations like measuring insert times starting from an empty database (ie: to look for a 'performance leak' over a long period.).


How to verify number with Bob without Eve knowing? You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number?

Note: This question is on a list of "google interview questions". As a result, there are tons of versions of this question on the web, and many of them don't have clear, or even correct answers.

Note 2: The snarky answer to this question is that Bob should write "call me". Yes, that's very clever, 'outside the box' and everything, but doesn't use any techniques that field of CS where we call our hero "Bob" and his eavesdropping adversary "Eve".

Update:
Bonus points for an algorithm that you and Bob could both reasonably complete by hand.

Update 2:
Note that Bob doesn't have to send you any arbitrary message, but only confirm that he has your correct phone number without Eve being able to decode it, which may or may not lead to simpler solutions.

First we must assume that Eve is only passive. By this, I mean that she truthfully sends the card to Bob, and whatever she brings back to Alice is indeed Bob's response. If Eve can alter the data in either or both directions (and her action remains undetected) then anything goes.

(To honour long-standing traditions, the two honest parties involved in the conversation are called Alice and Bob. In your text, you said "you". My real name is not "Alice", but I will respond just as if you wrote that Alice wants to verify Bob's phone number.)

The simple (but weak) answer is to use a hash function. Alice writes on the card: "return to me the SHA-256 hash of your phone number". SHA-256 is a cryptographic hash function which is believed to be secure, as far as hash functions go. Computing it by hand would be tedious but still doable (that's about 2500 32-bit operations, where each operation is an addition, a word shift or rotate, or a bitwise combination of bits; Bob should be able to do it in a day or so).

Now what's weak about that ? SHA-256, being a cryptographic hash function, is resistant to "preimages": this means that given a hash output, it is very hard to recover a corresponding input (that's the problem that Eve faces). However, "very hard" means "the easiest method is brute force: trying possible inputs until a match is found". Trouble is that brute force is easy here: there are not so many possible phone numbers (in North America, that's 10 digits, i.e. a mere 10 billions). Bob wants to do things by hand, but we cannot assume that Eve is so limited. A basic PC can try a few millions SHA-256 hashes per second so Eve will be done in less than one hour (less than 5 minutes if she uses a GPU).

This is a generic issue: if Bob is deterministic (i.e. for a given message from Alice, he would always return the same response), Eve can simulate him. Namely, Eve knows everything about Bob except the phone number, so she virtually runs 10 billions of Bobs, who differ only by their assumed phone number; and she waits for one of the virtual Bobs to return whatever the real Bob actually returned. The flaw affects many kinds of "smart" solutions involving random nonces and symmetric encryption and whatsnot. It is a strong flaw, and its root lies in the huge difference in computing power between Eve and Bob (now, if Bob also had a computer as big as Eve's, then he could use a slow hash function through the use of many iterations; that's more or less what password hashing is about, with the phone number in lieu of the password; see bcrypt and also this answer).

Hence, a non-weak solution must involve some randomness on Bob's part: Bob must flip a coin or throw dice repeatedly, and inject the values in his computations. Moreover, Eve must not be able to unravel what Bob did, but Alice must be able to, so some information is confidentialy conveyed from Bob to Alice. This is called asymmetric encryption or, at least, asymmetric key agreement. The simplest algorithm of that class to compute, but still reasonably secure, is then RSA with the PKCS#1 v1.5 padding. RSA can use $e = 3$ as public exponent. So the protocol goes thus:

Alice generates a big integer $n = pq$ where $p$ and $q$ are similarly-sized prime integer, such that the size of $n$ is sufficient to ensure security (i.e. at least 1024 bits, as of 2012). Also, Alice must arrange for $p-1$ and $q-1$ not to be multiples of 3.
Alice writes $n$ on the card.
Bob first pads his phone number into a byte sequence as long as $n$, as described by PKCS#1 (this means: 00 02 xx xx ... xx 00 bb bb .. bb, where 'bb' are the ten bytes which encode the phone number, and the 'xx' are random non-zero byte values, for a total length of 128 bytes if $n$ is a 1024-bit integer).
Bob interprets his byte sequence as a big integer value $m$ (big-endian encoding) and computes $m^3 \mathrm{\ mod\ } n$ (so that's a couple of multiplications with very big integers, then a division, the result being the remainder of the division). That's still doable by hand (but, there again, it will probably take the better part of a day). The result is what Bob sends back to Alice.
Alice uses her knowledge of $p$ and $q$ to recover $m$ from the $m^3 \mathrm{\ mod\ } n$ sent by Bob. The Wikipedia page on RSA has some reasonably clear explanations on that process. Once Alice has $m$, she can remove the padding (the 'xx' are non-zero, so the first 'bb' byte can be unambiguously located) and she then has the phone number, which she can compare with the one she had.

Alice's computation will require a computer (what a computer does is always elementary and doable by hand, but a computer is devilishly fast at it, so the "doable" might take too much time to do in practice; RSA decryption by hand would take many weeks).

(Actually we could have faster by-hand computation by using McEliece encryption, but then the public key -- what Alice writes on the card -- would be huge, and a card would simply not do; Eve would have to transport a full book of digits.)

Please call me (my name is 1001001). If you can't reach me, please write down the phone number that you have and ask Eve to return me.

Explanation: if Bob got my correct #, he can reach me then I know it is a correct #; if Bob didn't get my right #, Eve cannot read my (correct) phone number as well. In this way, I already checked that my friend, Bob, has my correct phone number or not.


Computing the closest match of an automaton and a string I have a problem where I'm trying to find an efficient algorithm for approximate string matching for an input to the closest string match from an automaton (the input is assumed to be not accepting for the automaton). I've looked around and found Levenshtein Automaton but had trouble finding out how it would be implemented from my automaton.

Also, are there any other methods that would be suitable/worth looking at for my problem?

You can adopt the usual dynamic program to compute the Levenshtein distance between a word $w$ and a regular language $L$ computed by some given NFA without $\epsilon$ transitions. Suppose $w$ has length $n$. For each $0 \leq \ell \leq n$ and state $s$ of the NFA, we will compute $A(\ell,s)$ which is the minimum Levenshtein distance between the $\ell$th prefix of $w$ and a word that causes the NFA to reach state $s$. This quantity is given by the following calculation, involving an auxiliary array $A'$:

$A(0,s)$ is the length of the shortest path from the initial state of the NFA to $s$ [insertion].
$A'(\ell+1,s)$ is the minimum of the following quantities:

$A(\ell,t)$ if there is a transition from $t$ to $s$ marked $w_{\ell+1}$.
$A(\ell,t)+1$ if there is some transition from $t$ to $s$ [substitution].
$A(\ell,s)+1$ [deletion].

$A(\ell+1,s)$ is the minimum of $A'(\ell+1,t)+\kappa(s,t)$ over all $t$, where $\kappa(s,t)$ is the length of the shortest path from $t$ to $s$ in the NFA [insertion].

Finally, the distance is the minimum of $A(n,s)$ taken across all accepting states $s$.

This calculation requires that you compute in preprocessing the all-pairs-shortest-path matrix for the directed graph underlying the NFA. Some of the quantities arising in the computation could be infinite.

The levenshtein distance is what you want.
It calculates the diference between two strings.
It counts the characteroperations to transform the one string into the other.

For Example:

test and taste:
replace 'e' with 'a'    -> +1
then add a trailing 'e' -> +1

-> The levenshtein distance is 2

You can find implementations in many languages here


Is a Turing Machine "by definition" the most powerful machine? I agree that a Turing Machine can do "all possible mathematical problems". But that is because it is just a machine representation of an algorithm: first do this, then do that, finally output that.

I mean anything that is solvable can be represented by an algorithm (because that is precisely the definition of 'solvable'). It is just a tautology. I said nothing new here.

And by creating a machine representation of an algorithm, that it will also solve all possible problems is also nothing new. This is also mere tautology. So basically when it is said that a Turing Machine is the most powerful machine, what it effectively means is that the most powerful machine is the most powerful machine!

  Definition of "most powerful": That which can accept any language.
  Definition of "Algorithm": Process for doing anything.
  Machine representation of "Algorithm": A machine that can do anything.

Therefore it is only logical that the machine representation of an algorithm will be the most powerful machine. What's the new thing Alan Turing gave us?

I agree that a Turing Machine can do "all the possible mathematical problems".

Well, you shouldn't, because it's not true. For example, Turing machines cannot determine if polynomials with integer coefficients have integer solutions (Hilbert's tenth problem).

Is Turing Machine “by definition” the most powerful machine?

No. We can dream up an infinite hierarchy of more powerful machines. However, the Turing machine is the most powerful machine that we know, at least in principle, how to build.  That's not a definition, though: it is just that we do not have any clue how to build anything more powerful, or if it is even possible.

What's the new thing Alan Turing gave us?

A formal definition of algorithm. Without such a definition (e.g., the Turing machine), we have only informal definitions of algorithm, along the lines of "A finitely specified procedure for solving something." OK, great. But what individual steps are these procedures allowed to take?
Are basic arithmetic operations steps? Is finding the gradient of a curve a step? Is finding roots of polynomials a step? Is finding integer roots of polynomials a step? Each of those seems about as natural. However, if you allow all of them, your "finitely specified procedures" are more powerful than Turing machines, which means that they can solve things that can't be solved by algorithms. If you allow all but the last one, you're still within the realms of Turing computation.
If we didn't have a formal definition of algorithm, we wouldn't even be able to ask these questions. We wouldn't be able to discuss what algorithms can do, because we wouldn't know what an algorithm is.

If you look at computational complexity, a Turing Machine is the most powerful machine - because it has unlimited memory, and no real machine has that. Any real machine cannot solve problems of arbitrary size; they cannot even read a problem, much less solve it.

On the other hand, if you tried to implement a real Turing Machine, let's say with the provision that it stops and sounds an alarm if it runs out of tape, you would find that it would take many more steps for doing any kind of computation than let's say the real machine in a cheap phone, and would be much much slower at solving real problems. You would also find that writing an answer on a tape is not a very good user interface. And you would find that lots of people use computers not for solving problems, but for sending nude photos to their friends and for watching cat videos, and a Turing Machine isn't any use for that at all.


Prove: possible to construct automata accepting all strings of other automata sans 1-length strings I believe that I have a procedure for doing this, but I don't know how to approach the proof (and for that matter I'm not entirely sure the procedure is correct).

Here's the exact problem statement:

  Given DFA $A = (\Sigma, Q, q_0, F, \delta)$ construct DFA $B$ from $A$ s.t. it accepts all words of the language of $A$ which have length distinct from 1.

And here's pseudocode that has to solve the problem followed by some explanation:

def ensure_word_length_ne_one(alphabet,
                              states,
                              initial,
                              final,
                              transition_function)
 loops = [i for i in alphabet if transition_function(initial, i) == initial)]
 new = make_new_accepting_state()
 # all arcs to the states directly accessible from the initial state
 # except the arcs from the initial state
 backarcs = [(arc.source, arc.destination, arc.input)
             for arc in arcs_to(set(for arc in arcs_from(initial))) -
                                set(arcs_from(initial))]
 for input in loops:
   # Remove all loops from the first state
   add_transition(initial, new, input)
   remove_transition(initial, initial, input)
   add_transition(new, new, input)
 for input in alphabet:
   # Bounce back from the new state to the first state
   add_transition(new, initial, input)
 for source, destination, input in backarcs:
   # For each state directly reachable
   # from the first state reattach
   # all inbound transitions
   # to the new state
   new = make_new_accepting_state()
   remove_transition(source, destination, input)
   add_transition(source, new, input)
   outbound = [(arc.input, arc.destination) for arc in arcs_from(new)]
   for input, destination in outbound:
     # Bounce back from the new state
     # to the states immediately
     # reachable from source state
     add_transition(new, destination, input)

The code tries to be more or less Python.  Auxiliary functions do what their name suggests.  The basic idea is as follows:

A DFA can accept words of length 1 in only these two scenarios:

It loops on some input in the first accepting state.
The state directly linked from the first state is accepting.

Below is the procedure to remove these accepting states while accepting
all other inputs.

If the first state loops on some inputs add a new state $q_1$, remove
all transitions from $q_0$ to itself and add transitions for the same
inputs from $q_0$ to $q_1$.  Add transitions on all inputs from
$q_1$ back to itself.

For any input which on which $q_0$ used to loop $B$ now necessary makes
at least two transitions before accepting it, possibly accepted string
with prefixes that did not cause the automate to loop on $q_0$ are
still accepted (nothing has changed).
For each accepting state $q_n$ directly linked from $q_0$ we do the
following:

change $q_n$ from accepting to non-accepting.
add a new accepting state $q_2$.
remove transitions from states $Q_i$ directly leading to $q_n$, unless they originate in $q_0$, for
each transition removed add a new one for the same input from $Q_i$
to $q_2$.
for each outbound transition from $q_n$ add new transition on the
same input from $q_2$.

Most proofs related to automata I've read so far use structural induction for similar tasks, but I cannot think about a way to approach the proof.  The difficulty is in ensuring that all strings accepted by $A$ are still accepted.

PS. I have the pseudocode set in LaTeX, if it is necessary, I can add it to the post.

Basically, the answer is what @Shaull says in the comments: construct a product automaton with the one that accepts all strings of length unequal 1.
What we use here is the fact that regular languages are closed under intersection. The product construction takes two automata, and simulates them in parallel. States are pairs of states of the original two automata. The combination accepts if both components accept.

But you ask for "minimal operations". So, have a look at what is in fact the automaton that accepts strings of length not 1. It simply has three states "zero", "one" and "many" with a loop for each letter at the last state. It simply counts letters up to length two (and then keeps in that state).

The product construction for this specific automaton is rather straightforward. Set aside a copy of your original automaton $A$. (You might add label "many" to each of the states, but that is extra.) Now add to these fresh copies of the original initial state and all states reachable in one step from the initial state. If the initial state has a loop, it is copied twice. (If you fancy it these get extra labels "zero" and "one"). Now remove final states from the "one"s and copy the original wiring.

Like I said, this is just a particular case of the product construction. In fact it might be even what is in your own pseudo code.

The simplest way to do this is to add a new starting state, with transitions exactly like the original starting state. If the new state isn't final, the result doesn't accept $\epsilon$, and you are done. If the starting state of the original automaton isn't accepting, none of this is needed.


Using software to calculate the complexity of an algorithm I am somewhat a beginner, and I have often seen complexity being calculated for various algorithms but they never actually gave me a very clear idea about how it is done. Can someone please point some resources where I can learn to calculate the complexity of an algorithm?

Secondly, is there some software that calculates the space and time complexity for an algorithm? I have seen that cyclomatic complexity can be calculated by software.

Depending on your background, the CLRS book is a solid introduction. I think in the very first chapter, they walk you through of how to analyze a simple algorithm in terms of both correctness (showing the algorithm really solves the problem) and complexity (how many steps the algorithm performs). There are lots of other books out there some other people might prefer more.

In general, there is no software that does this for you. Coming up with right invariants etc. is somewhat of an art requiring insight and experience. Read more about complexity theory, and you'll discover some inherit impossibilities and problems related to automating such analysis.

It is entirely possible with simple curve fitting exercises, which could be automated. Bearing in mind Juho's answer, some estimate must be better than no estimate whatsoever.  And some estimate is certainly possible for many algorithms, especially those that don't have many major decision branches and always halt such as cryptographic ones, compression, etc.

Code your algorithm.
Provide a test framework around it that can feed in different values of $n$.
Run the algorithm and time it's execution for each $n$.
There are only a few generic complexities to choose from if you are not too concerned with a perfect analysis.  A good example set is simply listed on the relevant Big $O$ Wikipedia page.  And any analysis must be better than none.
Iterate through the generic $O$ formulae, curve fitting and choose the best fit using your favourite fitting technique. Some experience and black magic may be useful in pruning the set.

This may not be academic computer science, but that's how the military, economics, engineering and politics works in this world. Monte Carlo simulation is exactly this type of analysis. The following simple example from Wikipedia is another:-

We see that the run time is approximated to $O((log(n)^2)$ which is polylogarithmic time. The specificity of the example is important. It's entirely possible that this approximation would be impossible to compute algebraically due to the overwhelmingly complex architecture of a Pentium 3 processor.

Reiterating, something is better than nothing and this example proves that automated complexity analysis is not only possible, but can be rather simple.


How to simulate a die given a fair coin Suppose that you're given a fair coin and you would like to simulate the probability distribution of repeatedly flipping a fair (six-sided) die. My initial idea is that we need to choose appropriate integers $k,m$, such that $2^k = 6m$. So after flipping the coin $k$ times, we map the number encoded by the k-length bitstring to outputs of the die by dividing the range $[0,2^k-1]$ into 6 intervals each of length $m$. However, this is not possible, since $2^k$ has two as its only prime factor but the prime factors of $6m$ include three. There should be some other simple way of doing this, right?

What you can do, is to employ a method called rejection sampling:

Flip the coin 3 times and interpret each flip as a bit (0 or 1).
Concatenate the 3 bits, giving a binary number in $[0,7]$.
If the number is in $[1,6]$, take it as a die roll.
Otherwise, i.e. if the result is $0$ or $7$, repeat the flips.

Since $\frac 68$ of the possible outcomes lead to termination in each set, the probability of needing more than $l$ sets of flips to get a die roll is $(1-\frac 68)^l = \dfrac 1{4^l}$. Hence, this method is efficient in practice.

Improvements:

@Angel's answer points out, that the number of coin flips in each set but the first can be reduced from 3 to 2, by using the distinction between a $0$ and a $7$ as the first bit for the next set.

@Emanuele Paolini explains, how you can reduce the number of rerolls, if you need multiple die rolls.

Take 6 coins. Each coin gets 1 point for tails, 2 points for heads. Dump out the coins and count up the total based on this idea.


Can a programming language be designed to use a fixed amount of memory? I have been toying around with the idea of creating a programming language as a side-project, specifically trying to get extreme performance out of a machine.

I have been thinking about the efficiency-memory tradeoff, and was wondering if it would be at all possible to design a language which always uses a fixed amount of memory.
That is, it allocates a large chunk of memory (16K, 64K, 1M, depending on the task), and instead of allocating from a heap, just gives some more memory out of the block we've already allocated.

The idea here is not to be practical, but rather to pose a challenge: design a fast algorithm that works on a fixed amount of memory.

If this sounds like a fun project, please let me know and I'll get on it.

If, however, this is a very naive thing to say (I don't know much about the inner workings of programming languages), I would very much appreciate some resources as to where I can learn more.

Yes. At least one variant of C supports this. Its call stacks are bounded in size: you can't call functions within functions indefinitely. It is used for embedded devices.

Can a programming language be designed to use a fixed amount of memory?

Yes. Brainf*ck works on an array of $30,000$ memory cells.

But, it's an esoteric language. Meaning, you're not supposed to use it for professional purposes.


Is finding a solution of a satisfiability problem harder than deciding satisfiability? Is the problem of determining whether or not a given Boolean expression is satisfiable computationally distinct from actually finding a solution to the expression?

In other words, is there another way of finding that a given expression is satisfiable without explicitly determining the 'right settings' for the Boolean variables? Or do all possible proofs reduce in polynomial time to the 'right settings'?

Forgive my ignorance, I am only an engineering student. Wikipedia seems to imply that the act of just finding SAT or UNSAT is NP-complete.

As mentioned in a comment, any method of determining satisfiability of a Boolean formula can be easily converted into a method for finding the satisfying variable assignment.  This is because all NP-complete problems are downward self-reducible.

From Wikipedia:

Self-reducibility

The SAT problem is self-reducible, that is, each algorithm which correctly answers if an instance of SAT is solvable can be used to find a satisfying assignment. First, the question is asked on the given formula $Φ$. If the answer is "no", the formula is unsatisfiable. Otherwise, the question is asked on the partly instantiated formula $Φ$$\{x_1=TRUE\}$, i.e. $Φ$ with the first variable $x_1$ replaced by $TRUE$, and simplified accordingly. If the answer is "yes", then $x_1=TRUE$, otherwise $x_1=FALSE$. Values of other variables can be found subsequently in the same way. In total, $n+1$ runs of the algorithm are required, where $n$ is the number of distinct variables in $Φ$.

The correct answer is that the determining if a solution exists and determining a solution are computationally distinct. Not all methods for determining if a solution exists can produce a solution. There exists a solution to the Hamiltonian Path problem that can determine if a path exists but cannot produce any such path. That said the question is made moot by arxiv.org/abs/cs/0205064.


Carry-free multiplication operation In long-multiplication, you shift and add, once for each $1$ bit in the lower number.

Let $r = p \otimes q$ be an operation similar to multiplication, but slightly simpler: when expressed via long-multiplication, the addition does not carry. Essentially you bitwise-xor the shifted numbers.

Like so:

$$
  \left[\begin{matrix}
    &&p_n & ... & p_i & ... & p_2 & p_1 \\
    &&q_n & ... & q_i & ... & q_2 & q_1 & \otimes\\
    \hline\\
    &&q_1 \cdot p_n & ... & q_1 \cdot p_i
      & ... & q_1 \cdot p_2 & q_1 \cdot p_1\\
    &q_2 \cdot p_n & ... & q_2 \cdot p_i
      & ... & q_2 \cdot p_2 & q_2 \cdot p_1\\
    &&&&&&&...\\
    q_i \cdot p_n & ... & q_i \cdot p_i
      & ... & q_i \cdot p_2 & q_i \cdot p_1 & \stackrel{i}{\leftarrow}
      &&{\Huge{\oplus}} \\
    \hline \\
    \\r_{2n}& ... & r_i
      & ... &r_4& r_3 & r_2 &r_1 & =
  \end{matrix}
  \right]
$$

Using the long-multiplication-style formulation, this takes $\mathcal O\left(\max\left(\left|p\right|,\left|q\right|\right)^2\right)=\mathcal O\left(\left|r\right|^2\right)$ time. Can we do better? Perhaps we can reuse some existing multiplication algorithms, or even better.

Followup: Shift-and-or multiplication operation

Your operation is multiplication of polynomials over $GF(2)$, i.e., multiplication in the polynomial ring $GF(2)[x]$.

For instance, if $p=101$ and $q=1101$, you can represent them as $p(x)=x^2+1$, $q(x)=x^3+x^2+1$, and their product as polynomials is $p(x) \times q(x) = x^5+x^4+x^3+1$, so $p \otimes q = 111001$.

If $p,q$ are $r$ bits long, this polynomial multiplication operation can be computed in $O(r \lg r)$ time using FFT techniques, but in practice this may not be a win unless your polynomial is extremely large. There is also a Karatsuba-style algorithm, whose complexity is something like $O(r^{1.6})$, as well as other options.  The situation is somewhat analogous to integer multiplication, in that many of the same fast algorithms can be applied, but not identical.

See, e.g.,

Wikipedia on Fast multiplication algorithms for large inputs.  These methods are described in terms of multiplying two integers, but they can be transposed to apply to polynomial multiplication.
Polynomial Multiplication, Karatsuba and Fast Fourier Transform
When is FFT multiplication of arbitrary-precision polynomials practical?.  Richard Fateman, March 14, 2006.
Can you save time in multiplying polynomials by encoding them as integers?.  Richard Fateman, January 15, 2005.

here is a nice/comprehensive survey of standard/best techniques in the area esp from the pov of implementation in logic gates, which shows basic optimizations including Schonhage and Strassen, but there is also an issue of practicality in the implementation.

  Schonhage and Strassen [302] have described a circuit to multiply integers represented in
  binary that is asymptotically small and shallow. Their algorithm for the multiplication of n-bit
  binary numbers uses $O(n \log n \log \log n)$ gates and depth $O(\log n)$. It illustrates the point
  that a circuit can be devised for this problem that has depth $O(\log n)$ and uses a number of
  gates considerably less than quadratic in $n$. Although the coefﬁcients on the size and depth
  bounds are so large that their circuit is not practical, their result is interesting...

Savage, models of computation, binary multiplication
powerful algorithms too complex to implement, tcs.se


Minimal DFA for $1\Sigma^*0$ What is the minimum number of states required in any DFA to accept the regular language $L$ over $\Sigma=\{0,1\}$ which accepts those strings that start with 1 and end with 0?

The following answer assumes that each state in a DFA must contain an outgoing edge for each symbol. Otherwise, you might need one state fewer.
Let us say that two words $x,y$ are equivalent modulo $L$ if for any word $z$, either both $xz$ and $yz$ are in $L$, or both of them are not in $L$.
If two words $x,y$ are not equivalent modulo $L$, and $A$ is any DFA accepting $L$, then the state of $A$ after reading $x$ must be different from the state of $B$ after reading $y$ (why?).
As a consequence, if $x_1,\ldots,x_n$ is a collection of words, any two of which are not equivalent modulo $L$, then any DFA for $L$ must contain at least $n$ states.
(Furthermore, it is known that if the minimal DFA for $L$ contains $n$ states, then we can find $n$ such words: for each state, we take some word leading to it; but we don't need this direction here.)
In your case, the following words are pairwise inequivalent: $\epsilon, 0, 1, 10$. To show this, we need to consider all six pairs:

$\epsilon,0$ are inequivalent since $10 \in L$ but $010 \notin L$.
$\epsilon,1$ are inequivalent since $0 \notin L$ but $10 \in L$.
$\epsilon,10$ are inequivalent since $\epsilon \notin L$ but $10 \in L$.
$0,1$ are inequivalent since $00 \notin L$ but $10 \in L$.
$0,10$ are inequivalent since $0 \notin L$ but $10 \in L$.
$1,10$ are inequivalent since $1 \notin L$ but $10 \in L$.

This shows that every DFA for $L$ contains at least $4$ states. Conversely, there is a DFA for $L$ containing $4$ states, which I will let you figure out.

The minimal DFA is attached.
Here, q0 is the initial state and q2 is the final state.


Finding Degree of match with Soundex or Metaphone I am working on a search where user would search names. Spelling mistakes are bound to happen. I have used edit distance, soundex and metaphone implementations in java so far. Each one separately and then different combinations too. Finally, a combination of soundex and metaphone seemed to work. There are more than 30 thousand names that would be searched for the match when ever a user enters a name. The search is sequential and would stop when ever a match is found. Now the problem is. Lets say in fol figure:-

   User Input Name = "Peeter"

----------------------------------------------------
 Serial       Name
----------------------------------------------------
   1           Tom
   2           Petay (Near match say 70%)
   3           Jack
   4           Peteh (Near Match say 75%)
   5           Peter (The closest Match say 100%)
----------------------------------------------------

The closest match for "Peeter" is "Peter" and near match is "Petay", "Peteh" etc. The search would stop at "Petay", returning "Petay" as the name which would be least expected by the user. So for me, 2 solutions comes to mind.

Search all 30 thousand names every time, get a list of all matches and ask user to choose the best match
Secondly, present 3 or say 5 top matching (by top matching i mean the closest match, let say more than 90% similar sounding) names to user.

I already have implemented option 1 but it returns some times more than 100 matches! it would not be possible for the user to go through all of them. So is there any way to implement option 2 mentioned above? i.e to find out to what degree soundex or metaphone match is made to a name.

Thanks in advance.

You can use K-nearest with the data points you have like % ,freq, or score of the edit and soundex algo.


Why is the class NP-Complete important compared to NP-hard? I'm studying computational complexity and I was wondering why the NP-Complete (NPC) problems is an important class at all. I find it obvious why we're interested in showing a given NP problem is NP-hard.

I also understand the definition of NPC, and that showing a given decision problem is NP-hard, knowing it is in NP, is exactly was NPC means.

However, what I don't understand is: why this concept is so important? Surely, if we find any NP-hard algorithm which runs in time P (whether or not that is in NP), we have shown that $NP = P$.

Why is this concept so important?

There are at least a few reasons that NPC is interesting:

The class NP contains many problems that are interesting (both practically and theoretically), moreover many of these problems turn out to be NP-hard (and hence NP-complete), but many problems outside of NP are almost certainly too hard to be of more than theoretical interest, so NPC provides a (rough) group of problems that are apparently hard, but not so hard that we can't try to do something with them.
In other words, NPC is probably the limit of what we can hope might be polynomial-time solvable, it would seem a stretch to try for PSPACE = P (for example).
The class is NP is structurally interesting. It's the basic example of "do we get any more computational 'speed' from nondeterminism". So we're interested whether P=NP or not, and NPC is (probably) an important component of working that out.
NP-hard (as a class) is really too big and varied to deal with as a single thing, it's everything that can be reduced to from an NP-complete problem, including a huge swathe of stuff outside NP, so from the point of view of trying to develop general results and techniques, there's nothing to grab on to.

"Surely, if we find any NP-hard algorithm which runs in time P (whether or not that is in NP), we have shown that NP=P. Why is this concept so important?"

Every NP problem reduces to any NPC problem, but it's not true that every NP problem reduces to any NP-hard problem, so proving an algorithm NP-hard is in P doesn't prove P=NP at all. It would be the case, however, for a NPC problem, that is precisely what "reduces" means. So, if we find an P algorithm for a NPC problem, then, we will have proven that P=NP.


Show that the tree resulting from BFS is a spanning tree? Given that $G$ is some connected and undirected graph, and I want to run BFS on it from some starting vertex. How can I show that $T = \{ \{\text{predecessor}[u], u\} \mid u \text{ is a vertex}\}$ is a spanning tree of $G$?

Observe that any spanning tree of $G$ contains every vertex of $G$, and has no cycles. Use induction to show that on every iteration, the process creates no cycles (and also visits every vertex).

I have no idea about data structure you are going to use, but you probably have all of your vertexes and for each vertex list of it's neighbours.
A general approach should be:

After each step in your traversal check the list. If new vertex is a visited vertex then there is a loop in your graph an it's not a tree. (check your graph is a tree or not)

Another condition is to check coverage of your graph. When your traversal completed the visited list should contain a complete set of graph vertexes.(check for spanning)


Optimizing estimator of composed functions when function is known I have a problem which I'm looking to see if there is literature on:

Consider three types of actors, a Director, Aggregator, and Follower. The Director talks to multiple Aggregators, the Aggregator talks to multiple Followers. The director gives simple commands to the Aggregator, who then can portion out the commands to each Follower as she sees fit.

The question then is, how can the Director know whether or not an Aggregator can complete a given request at time step T? T+1? If T is now, then this is relatively easy as the Aggregator can simply sum up the capabilities of each of the Followers and return it, saying "this is what I can do in total." The problem then is, if the Director is doing her own optimization problem in deciding how to direct two different Aggregators, given each command she must be able to predict how the Aggregator will react. I.e., what are the Aggregator's capabilities in time step T+1 given a direction D in time step T?

Due to the complexity of the Aggregator, I think it's likely best to create an estimator across the current state of the Aggregator (or all of their followers). Further, the Aggregator can give whatever knowledge it wants to the Director, though ideally this would be of constant size no matter the size of the set of Followers. This is therefor an optimization problem on the Aggregator's side for creating an optimal estimator, which is well studied.

What I want to know: Is there any literature about creating an estimator when you know the exact function you are estimating? So if I am the aggregator, how can I tell the Director, in a constant space for the amount of information I give no matter the number of followers, the information require to best predict I would react to a given direction?

Put another way: How can I create an optimal estimator in which I have full knowledge of the shape and composition of the functions I am estimating?

I can think of a number of places where this might occur, potentially in networking, data compression, etc., though I think I don't have the necessary vocabulary. I've tried searching through aggregation, optimization, estimation, forecasting, prediction, which a number of different combinations of keywords relating to these. There is a ton of generalized work on making estimators and predictors, though none which target the assumption that they already have perfect knowledge of that which they're estimating.

Is there any literature about creating an estimator when you know the exact function you are estimating?

I think streaming algorithms may be of interest to you. A streaming algorithm is an algorithm that operates on some model of a massive 'stream' of data that is simply impossible to completely store, but it is possible to traverse it and do some computations with bounded memory. Often, it is impossible to solve even simple computations with bounded memory, but answers that are correct with high probability can be found efficiently, with techniques as random sampling, aggregating medians or probabilistic data structures.


Algorithm to minimize an expression If I have a constraint like $y_1 + y_2 +\dots + y_n = k$ for positive integers $y_i$, how would I minimize
$$\quad\frac{x_1 }{ y_1} + \frac{x_2 }{ y_2} + \frac{x_3 }{ y_3} + \dots + \frac{x_n }{ y_n}$$
 if all of the $x_i$ are given?

One can assume that $n\le5\cdot10^5$ and $k\le10^{12}$.

For $n=2$ there is a solution:

Minimize $f(y) = x_1/y_1 + x_2/(k-y_1)$, it is convex for $y_1 >0$ so you can find derivative, solve it for $=0$ and get the solution in reals, then check floor and ceil.

For general $n$ rounding needs more investigation. The only thing I'll mention that the real solution is something like $y_i = k \cdot \frac{\sqrt{x_i}}{\sum\limits_i {\sqrt{x_i}}}$, from the lagrangian. Then you do the $\max (1, \lfloor y_i \rfloor)$ and use other deeper results or greedy discussed to reach the sun to be exactly $k$.

UPD: Using greedy after this step, it will take time at most $n$ steps, resulting in $O(n)$ time. Reminder: add 1 to the $y_i$ where the difference $ \frac{x_i}{y_i} - \frac{x_i}{y_i+1}$ is maximized. Store this differences using priority queue to reuse calculations.


How can I academically say that 'one computer is slower than the other'? I'm writing a research paper and I have to basically say that one microcontroller is slower than an other microprocessor.  However, I'm worried that simply saying that it's 'slower' wouldn't be appropriate in a research paper.

Am I right?  Is it OK to just say that one processor is 'slower', or do I need to say something else?  What else could I say?  The best I have come up with is that one has 'less computational power' than the other or that the microcontroller has 'low computational power'. Unfortunately, these expressions don't seem to be too popular when searching online.

So, what would be a better and academically correct way of saying this?

Let me see if I can clear up a few potential misconceptions here.

Sometimes people think that when they write a research paper they have to use fancy language: it's not enough to just say what they mean, but rather, it has to be written in academic code with more complex-sounding language.  Or, they think that using bigger words will make them sound more authoritative.  This is not the case.  If anything, it leads to papers that are overly pompous and unnecessarily hard to read.

Instead, I suggest you figure out what you mean, and then write that.  Don't worry too much about how to say it (whether the word you are using is OK in a research paper).  Do worry about being precise: figure out exactly what you mean, and then be precise in your wording.

You have a good intuition.  Your hesitation about just saying one processor is slower than another is valid.  (But not because you can't say one thing is slower than another in a research paper.)  The issue I see with that wording is that it is not very precise.  There are many things that 'slower' could mean.

What exactly do you mean by 'slower'?  Slower in what way?  And how do you know?  What evidence do you have?  Can you quantify it?  How would you measure 'slowness' in a quantitative, defensible way?

Once you can answer those questions, then you can figure out how to write something more convincing in your paper.  For instance, "processor X is 20% slower on the SpecCPU benchmark than processor Y" is more precise than "processor X is slower than processor Y", and backs up the claim with evidence.

But first you need to figure out precisely what you mean by 'slower', and why it matters to your argument, and then you can figure out how to be more precise in what you write and what evidence you can provide to back up your statement.

You won't always need to write with this level of care and precision.  Sometimes, when you are just providing intuition or background, the specifics don't matter so much, and then you can just say that X is slower than Y.  But if that statement plays a key role in your paper -- maybe it is a key part of the motivation for your paper, or it is a key part of the reasoning that underpins the design of your system -- then you should try to  be as precise as you can, and provide evidence for the statement.

"less performant" is a great way to say this, if the exact performance figures aren't affecting your results.  For example, you might write something like:

  Table X shows that this implementation runs in real-time on the Xeon processor used for benchmarking.  If a less performant processor were to be used, such as an ARM Cortex M microcontroller popular in battery-powered embedded systems, then additional optimizations should be investigated.

The term "less performant" neatly wraps up all the factors affecting you: clock speed, architectural efficiency, cache sizes, memory latency, etc.