greedy algorithm for Maximum directed cut Maximum directed cut: Given a directed graph $G = (V, E)$ with nonnegative edge costs, find a subset $S \subseteq V$ to maximize the total cost of edges out of $S$: $\mathrm{cost}( \{  (u \to v) \mid u \in S \text{ and } v \in \bar{S} \})$.

I am trying to come up with a greedy algorithm for Maximum directed cut with factor 1/4.

The starting point is the trivial random algorithm that chooses $S$ completely at random. Each directed edge is cut with probability $1/4$ (why?), and so in expectation, this random algorithm gives a $1/4$ approximation.

We can derandomize this algorithm using the method of conditional expectations. Arrange the points in order: $1,\ldots,n$. At step $i$, we know which of $1,\ldots,i-1$ are in $S$ and which are in $\bar{S}$. If we put $i \in S$, then we can compute the expected cost of the output given that all further choices are made randomly; and we can do the same if we put $i \in \bar{S}$. One of these choices cuts at least $1/4$ of the edges (in terms of weight), and this is the one we choose.

We can further optimize this algorithm. Consider the following two expressions:
$$
A = \sum_{\substack{j<i\\j\in\bar{S}}} w_{ij} + \frac{1}{2} \sum_{j>i} w_{ij}, \\
B = \sum_{\substack{j<i\\j\in S}} w_{ji} + \frac{1}{2} \sum_{j>i} w_{ji}.
$$
(Here $w_{ij}$ is the cost of the edge from $i$ to $j$.)
If $A>B$ then the derandomized algorithm puts $i$ in $S$, whereas if $A<B$ it puts $i$ in $\bar{S}$ (if $A=B$ it doesn't matter). We can perhaps think of this algorithm as a greedy algorithm.

As an aside, the so-called double greedy algorithm gives a $1/2$ approximation algorithm. The greedy algorithm you suggest in the comments is good in combination with the random algorithm: if you run both and choose the better solution, you get a $2/5$ approximation (see Feige's paper). The semidefinite relaxation gives the (probably) optimal approximation ratio, which is roughly 0.874.


Relationship between formal system and formal languages In a course of computer science it is common to study the hierarchy of formal languages, grammars, automata and Turing machines. I wonder what is the relationship of these objects with formal systems.

For example, lambda calculus is said to be a formal system.  Would its grammar also be considered a formal system?

Generally speaking, a formal system is comprised of

a language distinguishing its well-formed formulas from those strings over that are not well-formed
some kind of semantics that says which formulas are true and which are not
axioms and inference rules which attempt to generate, computationally, exactly those formulas which are true given the semantics.

We can specify the language of well-formed formulas using a grammar, but a grammar is not itself a formal system.


If A many-one reduces to B, does the complement of A many-one reduce to the complement of B? If A many-one reduces to B, does the complement of A many-one reduce to the complement of B? My gut says no but I am having a hard time finding a counterexample.

Let's try an example. Here is a reduction from the set of even numbers to the set of squares: $x \mapsto 2^x$ (check it!). It is also a reduction from the set of odd numbers to the set of non-squares. Is that just by chance?

We can make the following twist: the mapping $x \mapsto 2^{x+1}$ maps the set of even numbers to the set of non-squares. Is it always the case that we can modify a reduction from $A$ to $B$ to a reduction from $A$ to $\overline{B}$?


The importance of normal forms like Chomsky normal form for CFGs I understand that context-free grammars can be used to represent context-free languages.It might have ambiguities. We also have normal forms like Chomsky and Greibach normal form. I couldn't understand the need of that.

Why they are important in the theory of languages? All the textbooks I referred to tell about these normal forms but not telling anything about their importance.

There are at least two relevant uses.

Simplicity of proofs
There are plenty of proofs around context-free grammars, including reducability and equivalence to automata. Those are the simpler the more restricted the set of grammars you have to deal with is. Therefore, normal forms can be helpful there.

As a concrete example, Greibach normal form is used to show (constructively) that there is an $\varepsilon$-transition-free PDA for every CFL (that does not contain $\varepsilon$).
Enables parsing
While PDAs can be used to parse words with any grammar, this is often inconvenient. Normal forms can give us more structure to work with, resulting in easier parsing algorithms.

As a concrete example, the CYK algorithm uses Chomsky normal form. Greibach normal form, on the other hand, enables recursive-descent parsing; even though backtracking may be necessary, space complexity is linear.


Complexity class for NP with access to a DP oracle Consider the following decision problem:

Given: Two (3CNF-)formulas $\varphi_1$, $\varphi_2$ on a shared set $X\cup Y$ of variables ($X$ and $Y$ disjoint).
Question: $\exists$ assignment $\tau_X$ on $X$ such that $\varphi_1$ is satisfiable and $\varphi_2$ is unsatisfiable?

(The "satisfiable" and "unsatisfiable" conditions are relative to the fixed assignment $\tau_X$ from the outer quantifier and can only "choose" the assignment to variables in $Y$.)
This problem is a generalization of the well-known 3-SAT/3-UNSAT problem, which is DP-complete:

Given: Two (3CNF-)formulas $\varphi_1$, $\varphi_2$ on a set $Y$ of variables.
Question: Is $\varphi_1$ satisfiable and $\varphi_2$ unsatisfiable?

The generalization works in the same way in which the NP-complete problem 3-SAT is generalized for higher levels of the polynomial hierarchy. In fact, if the formula $\varphi_1$ and the corresponding condition is removed, this problem coincides with the $\Sigma_2^p$-complete variant of 3-SAT:

Given: A (3CNF-)formula $\varphi_2$ on a set $X\cup Y$ of variables ($X$ and $Y$ disjoint).
Question: $\exists$ assignment $\tau_X$ on $X$ such that $\varphi_2$ is unsatisfiable?

Now I wonder how to call the complexity class that this problem is a member of (and probably complete for). It seems to be $\textit{NP}^{\textit{DP}}$, i.e., $\textit{NP}$ with access to a $\textit{DP}$ oracle, in the same way that  $\Sigma_2^p=\textit{NP}^{\textit{coNP}}$ is $\textit{NP}$ with access to a $\textit{coNP}$ oracle.
However, I have not found such a class in the literature. Is the problem simply too unnatural to receive any attention? Or can it be simplified such that it falls into another, more common class?

You have not found explicit mention of it because it is the same class as $\Sigma_2 = \textbf{NP}^\textbf{NP}$. $\Sigma_2 \subseteq \textbf{NP}^\text{DP}$ holds because any $\textbf{NP}$ query can be poly-time (many-one) reduced to a SAT query, which, in turn, can be cast as a DP query (by setting $\varphi_2$ to a trivially unsatisfiable formula). Conversely, $\Sigma_2 \supseteq \textbf{NP}^\text{DP}$ because any DP query can be answered by two (adaptive) SAT queries.


How to use Hoare Logic to Prove this Assertion Given this assertion in Hoare Logic:

\begin{align}
&\mathbf{\{p >= 0\}}\\
&s = 0 ; n = 1 ;\\
&\mathtt{while}\ (n <= p)\ \{\\
&\quad s = s + n ;\\
&\quad n = n + 1\\
&\}\\
&\mathbf{\{s == p * (p + 1) / 2\}}
\end{align}

How to prove this using the rules of Hoare Logic. I am not sure where to really begin, I only currently understand (most) of the meaning of the axioms, but not what is required for a proof.

Its a question of chaining/glueing the axioms between them.

Let's start from the end:

$$\mathbf{\{s == p * (p + 1) / 2\}}$$

Use the strengthening rule to change the postcondition to

$$\mathbf{\{s == p * (p + 1) / 2 \wedge p == n \wedge p >= 0\}} $$

which is equivalent to

$$\mathbf{\{s == n * (n + 1) / 2 \wedge p == n \wedge p >= 0\}}$$

By the Loop rule in order for the triple:

$$ \mathbf{\{s == n * (n + 1) / 2 \}} \mathtt{while}\ (n <= p)\ \{s = s + n ;
 n = n + 1\} \mathbf{\{s == n * (n + 1) / 2 \wedge p == n \}}
$$

we need to prove that the triple

$$\mathbf{\{s == n * (n + 1) / 2 \}} \{s = s + n ;
 n = n + 1\} \mathbf{\{s == n * (n + 1) / 2\}}$$

is valid.

Let then use the composition to reduce this to proving that the two following triples are valid:

$$\mathbf{\{s == n * (n + 1) / 2 \}}
\{s = s + n\}
 \mathbf{\{s == (n+1) * (n + 2) / 2\}}$$

and

$$\mathbf{\{s == (n+1) * (n + 2) / 2 \}}
\{ n = n + 1\}
 \mathbf{\{s == n * (n + 1) / 2\}}$$

The latter one is just an application of the Assignment rule (just replace the occurrences of $n$ by $n+1$ in the postcond to get the precondition).

To prove the first one, we need to apply Strengthening to reduce it to the triple
$$\mathbf{\{s == n * (n + 1) / 2 \}}
\{s = s + n\}
 \mathbf{\{s == (n) * (n +1) / 2 + n\}}$$
and then use the Assignment rule trivially.

Okay so now we only need (by Sequence rule) to prove that the triple

$$\mathbf{\{p>=0 \}} s:=0; n:= 1 \mathbf{\{s == n * (n + 1) / 2 \wedge p >= 0\}}$$
which can be done in the same way by splitting with sequence.


An algorithm to maximize the number of parallel tasks I have a set of compute tasks I want to schedule, these tasks have dependencies and a task may not be executed until all its dependencies are executed.

The problem can be represented as a directed acyclic graph:

The current scheduler ensures correctness, and capable of culling unneeded tasks such as k in the previous graph (assuming the end goal is i).

I am struggling to find another equivalent algorithm to maximize number of tasks running in parallel (tasks on the same line may be executed in any order):

a, b, j
c
d
e, f, h, g
i

Flatten form, what is between () may be in any order and represent parallel tasks:

  (a, b, j), (c), (d), (e, f, h, g), (i)

The idea here I want to fill the compute engine with as much work as possible.

From your initial DAG $G(E, V)$ You start reversing all edges to build a new DAG $G'(E, V')$. Then do a BFS from $i$ in $G'$ to remove any unneeded tasks (unreached nodes in the BFS). This step is $O(N)$ with $N = |V'|$, the number of edges.

From $G$, build the number of requirements of each task ($R(V)$) and at the same time the list $L$ of the tasks with no requirements. this takes $O(N)$.

Then you iterate on this pseudo-algorithm:

while(root is not executed)
    L' = empty list
    for v in L
        for each node v' with an edge in G' from v to v'
             R(v') -= 1
             if R(v') == O then add v' to L'
    execute all L in a parrallel step
    L = L'

this is $O(N)$.


Prove the equality of two concatenations of words Let $x$, $u$, $v$, $w$, $y$, $x'$, $u'$, $v'$, $w'$, $y'$ be words. If

$y'x' = xy$
$y'u'x' = xuy$
$y'v'x' = xvy$
$y'w'x' = xwy$
$y'v'u'x' = xuvy$
$y'w'v'x' = xvwy$

all hold, then I need to prove that $y'w'v'u'x' = xuvwy$.

I'm a little confused how to prove this, How can I form $y'w'v'u'x'$ from the equations above?

Suppose without loss of generality that $|y'| \geq |x|$. If we write $y' = xa$ then $ax' = y$. The equalities then become

$xau'x' = xuax'$.
$xav'x' = xvax'$.
$xaw'x' = xwax'$.
$xav'u'x' = xuvax'$.
$xaw'v'x' = xvwax'$.

Cancelling $x,x'$, we get

$au' = ua$.
$av' = va$.
$aw' = wa$.
$av'u' = uva$.
$aw'v' = vwa$.

Using $y' = xa$, (5), (1), and $y = ax'$, we get
$$ y'w'v'u'x' = xaw'v'u'x' = xvwau'x' = xvwuax' = xvwuy. $$
This is close to what we want, only we got $vwu$ instead of $uvw$.

Plugging (2) into (4) gives $uva = av'u = vau' = vua$, and so $u$ and $v$ commute. Similarly, plugging (2) into (5) gives $vwa = aw'v' = wav'=wva$, and so $v$ and $w$ commute. The set of words commuting with $v$ forms a commutative monoid (since all are powers of some primitive word), and so $u$ and $w$ also commute. Therefore $vwu = uvw$, completing the proof.


What fragment of Martin-Löf dependent type theory can be expressed using generic types in Java? I have recently come to realize that a number of problems I had a few years ago trying to implement various mathematical theories in Java came down to the fact that the typing system in Java is not sufficiently strong to model all of Martin-Löf dependent type theory.

Prior to Java 5 and generics, the only type theory you could do was through classes and interfaces, which give you arbitrary types built out of the ground types int,double,char and so on using product and function types.  You can also build recursive types such as Lists, though not in a uniform way.

Using generics, you can do a bit more.  You can now define List<T> as a function
$$
\DeclareMathOperator{\Type}{Type}\Type\to\Type
$$
and so we get higher order types.

This is not the end of the story, though.  Using a generics trick, we can model some dependent product types.  For example, we can define types of the form
$$
\prod_{T\colon\Type}f(T)
$$
using the syntax

public interface f<T extends f<T>>
{
  // We can now refer to T as much as we like
  // inside the class.  T has type f<T>.
}

As an example, we can model the basic underlying structure of a monoid (but not the associativity and unitality conditions) using a term of type
$$
\prod_{T\colon\Type}T\times (T\to T\to T)
$$
(i.e., a set $T$ with a designated unit element and a binary operation on $T$).  Using Java generics, we can model this type:

public interface MonoidElement<T extends MonoidElement<T>>
{
  public T unit();

  public T mul(T op1, T op2);
}

However, when we try to model more complicated concepts, the type theory breaks down.

Is there a simple description of the fragment of MLTT corresponding to the types that can be built in the Java typing system?

There are a lot of misconceptions here. To begin, MLTT doesn't have subtypes, so Java is not going to simply be a fragment of it. It does not require dependent types to make either of the types you gave. A dependent type system doesn't need to have a "type" of types (a universe) in general  (MLTT does have universes though), nor do you need dependent types to express those types. In a system like the polymorphic lambda calculus/System F, you can say $\forall T.T\times(T\to T\to T)$.  Java doesn't have any equivalent to Type. A dependent type without an analog as a polymorphic type would be something like e.g. $\prod_{n:\mathsf{Nat}}\mathsf{Matrix}(n,n+1)$ or $\prod_{b:\mathsf{Bool}}\mathsf{if}\ b\ \mathsf{then}\ \mathsf{Nat}\ \mathsf{else}\ \mathsf{Bool}$.

It makes more sense to consider Java a fragment of System $\text{F}_{<:}$ which is not a dependent type system at all. Even then it is a rather weak fragment of it. There's a variant of System F called System F$\omega$ which supports full type level functions, essentially lambda at the type level (not to be confused with type-lambdas which relate the value and type levels and System F already has). Neither Java nor Haskell can do this.  The only type level "functions" either (standard) Haskell or Java can make are compositions of uninterpreted functions. There is no computational behavior at the type level. Java is further restricted because it doesn't have (nor need) a kind system because it lacks higher-kinded types.  That is, you can't have a type level "function" with "type" (i.e kind) $(\mathsf{Type}\to\mathsf{Type})\to\mathsf{Type}$ for example. This is why you can't make methods that operate over arbitrary monads in Java. Returning to just System F, System F has arbitrary rank types. This means you can nest $\forall$ as deeply as you like — you can use it freely. Neither Java nor Haskell (without extensions) supports this. I believe both of them can indirectly capture some higher rank types, but neither can express the type of Haskell's $\mathsf{runST}$ which requires extensions and is $\forall a.(\forall s.\mathsf{ST}\ s\ a) \to a$.

So Java is more expressive than the rank-1 types as captured by the Hindley-Milner type system but far less expressive than System $\text{F}_{<:}$. It doesn't support any form of dependent typing. Featherweight Java as introduced in Featherweight Java: A Minimal Core Calculus for Java and GJ by Igarashi, Pierce, and Wadler provides a simplified, idealized calculus specifically geared toward Java.  There is almost certainly a paper that directly compares/reduces Featherweight Java to System $\text{F}_{<:}$. The upshot is Java's type system is not even remotely close to the power of MLTT. In terms of the lambda cube, ignoring subtyping, Java would be somewhere on the edge between $\lambda\!\!\to$, the simply typed lambda calculus, and $\lambda2$, System F. MLTT (or specifically the Calculus of Constructions) is $\lambda\text{P}\omega$, the corner opposite of $\lambda\!\!\to$. So describing Java in terms of MLTT would first require ignoring everything that made MLTT different from System F$\omega$ and then ignoring nearly everything that made System F$\omega$ different from System F.


Free and bound variables I am familiar with free and bound variables theory , but while learning I somewhere saw
this lambda expression

  ((lambda var ((fn1 var) & (fn2 var))) argument)

From what I have learned it seems to me as var is bounded in both fn1 and fn2. But the reference from where the expression is taken says that both var are free and hence  can be substituted by argument while doing β-reduction .

Someone please clear my doubt.

In the usual mathematical notation: $(\lambda \color{blue}{x}. (\& (f_1 \color{green}{x}) (f_2 \color{green}{x}))) A$

The two green occurrences of $\color{green}{x}$ in the subterms $f_1 \color{green}{x}$ and $f_2 \color{green}{x}$ are bound in the term $\lambda \color{blue}{x}. (\& (f_1 \color{green}{x}) (f_2 \color{green}{x}))$. The binding occurrence is the blue $\color{blue}{x}$.

When evaluation $(\lambda \color{blue}{x}. (\& (f_1 \color{green}{x}) (f_2 \color{green}{x}))) A$ by beta-reduction of the top redex, the result is the substitution of $A$ for the free occurrences of $x$ in the body of the lambda abstraction. If $\&$, $f_1$ and $f_2$ are variables, then the result is simply
$$ (\lambda \color{blue}{x}. (\& (f_1 \color{green}{x}) (f_2 \color{green}{x}))) A  \to_{\beta} (\& (f_1 A) (f_2 A)) $$
If $\&$, $f_1$ and $f_2$ are lambda-terms, then they may contain free occurrences of $x$, which need to be substituted.
$$ (\lambda \color{blue}{x}. (\& (f_1 \color{green}{x}) (f_2 \color{green}{x}))) A  \to_{\beta} (\&[x\leftarrow A] (f_1[x\leftarrow A] A) (f_2[x\leftarrow A] A)) $$

Note that the notion of free or bound variable is really a free or bound occurrence of a variable, in a given term. A variable is often said to be free in a term if it has a free occurrence. For example, in the term $(\lambda \color{blue}{x}. (\& (f_1 \color{green}{x}) (f_2 \color{green}{x}))) (g \, \color{magenta}{x})$, the green occurrences of $\color{green}{x}$ are bound, and the magenta occurrence of $\color{magenta}{x}$ is free. In the term $\& (f_1 \color{green}{x}) (f_2 \color{green}{x}))$, the two occurrences of $\color{green}{x}$ are free.


Algorithm for finding maximum mutually coprime subset of a multiset of integers For a certain problem I am trying to solve given a list of integers, it is advantageous to me to first identify as many of the integers that are mutually coprime as possible. I'm having trouble thinking of a good general algorithm for this, and everything I've found online seems to relate to problems that are slightly different to what I'm going for. For example, given the multiset of integers A = {12, 15, 15, 16}, I would like the algorithm to return {15, 16}.

The first naive solution I could think of was to order the numbers in increasing order, take the first number into my set, then take any number after that which is coprime with all of the numbers in the set. This works for things such as {2, 3, 4, 5, 6, 7, 8, 9, 10, 11}, but it would erroneously give {12} in my example above.

Besides that, the best idea I have is to create a list of sets of the factors of each number, at which point this problem can be reduced to the exact cover problem. However, I feel like this would have a relatively large amount of overhead, especially given the fact that the data sets I'm operating on won't be very large (~1000 elements somewhere in between 1 and 500).

Is there any algorithm I could apply here that would be more simple to implement (even if it is slightly slower) and would guarantee an optimal solution?

Your problem is equivalent in complexity to the maximum set packing problem.  Unfortunately, maximum set packing is NP-hard.  Therefore, you'll need to use one of the methods in Dealing with intractability: NP-complete problems.

Here's the gist of the equivalence.  Each integer in your set A corresponds to a set of its prime factors; now you're looking for a maximum-size collection of those sets that are pairwise disjoint.  That's exactly maximum set packing.  This is only the gist of the idea; this reduction doesn't quite work, because as you noticed, factoring each element of A can take quite a bit of time (there's no known polynomial-time algorithm for factoring).

It's possible to fix up the reduction as follows.  Given an instance of your problem, factor A into a coprime base.  A coprime base is a list of integers that are pairwise co-prime (no two elements in the coprime base any common factor), and where every number in A can be factored into a product of elements of the coprime base.  For instance, a coprime base for A = {30, 105, 126} would be {5, 6, 21}.  Note that the elements of the coprime base do not need to be prime.  There are efficient algorithms for finding a coprime base for A.  Now, associate to each number x in A the set of elements of the coprime base that are divisors of x.  Then you have an instance of the maximum set packing problem.

(Conversely, given an instance of the maximum set packing problem, you can convert it into an instance of your problem, by simply treating the universe for the set packing instance to be the prime numbers.)

So given that you basically have an instance of maximum set packing, what should you do?  Well, maximum set packing has been well-studied, so you can use the literature on that problem.  Here are some candidate approaches:

ILP: It's easy to formulate the maximum set packing problem as an instance of integer linear programming.  You have a zero-or-one variable $x_i$ for each integer $i$ in A, with the idea that $x_i=1$ means that $i$ is included in the output list.  You add a constraint $x_i+x_j \le 1$ for every pair of numbers $i,j$ that have a common factor.  Then, you try to maximize the objective function $\sum_{i \in A} x_i$.  Feed this to an off-the-shelf integer linear programming solver, and it will give you the best solution it could find.

If you want something simple to implement and optimal, I suspect the ILP-based algorithm is your best bet.  It'll be easy to implement.  There's no guarantee that it'll be efficient -- it's an NP-hard problem, after all -- but it might work well enough in practice if the problems sizes are small enough.

Heuristics: You can use any of the known heuristics for set packing.  See, e.g., https://en.wikipedia.org/wiki/Set_packing#Heuristics, or search the research literature.

Approximation algorithms: Wikipedia says that it is known how to approximate maximum set packing to within a factor $k/2$, if $k$ is the size of the largest set.  (In other words, $k$ is the maximum number of elements of the coprime base that can divide any single element of A.)  If the numbers in A aren't too large, then $k$ will be relatively small, so this approximation algorithm might be reasonably effective.  Wikipedia doesn't say what the algorithm is, so you'll have to do some research in the literature.


Confusion in understanding a DFA question I am new to DFA and I am trying to understand the following question.
The alphabet is Σ = {0, 1}
Construct DFA for L = {0^n: n is either a multiple of 3 or a multiple of 5 }
Question
The above language does not say anything about the 1s.
When we write strings in this Language, we get
L = {є, 000, 00000, 000000, 000000000, ...}
There are no ones in this language.
According to the language description, 0010 would not be a valid string. Right?
So, in the DFA that we construct do we need to show 1s? Can I just leave them out?

Either you can make a 1 transition from every state to a non-final sink state. Or make a note that any character that doesn't match an available transition goes to a non-final sink state.
Depends on what format is usual for the course.
I assume the reason that 1 is also in the alphabet is to trip up people who forget about this sink state.


Maximum flow with edge demands: can't understand the example of transition to transformed graph in the lecture notes TL;DR:
There're lecture notes about a very simple reduction from "maximum flow with edge demands problem to the maximum flow problem. But I can't get the new capacities at the picture:

E.g., look at the diagonal: 15 - 0 = 14 (?). From my point of view there're a lot of off-by-one errors.

Those are just typos, as you can confirm by reading the general construction on the previous page ("Intuitively, we construct $G'$ by ...") and applying it to the flow network on the left.  Yes, there are multiple off-by-one errors.  It happens. Pobody's nerfect.

Incidentally, you might want to read the latest version of his notes, available from http://web.engr.illinois.edu/~jeffe/teaching/algorithms/, rather than the 2009 version you're reading right now (though this particular typo is still present).


Numerical issues in solving linear systems There was an exam in the class. The course is "High Performance Scientific Computing". One of the question in the exam is as follows:

Consider the linear system
$$ \begin{bmatrix} a & b \\ b & a \end{bmatrix} \times \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$$
with $a,b>0$.
a) If $a$ is very similar to $b$, what is the numerical difficulty in solving this linear system?
b) Suggest a numerically stable formula for computing $z = x + y$ given $a$ and $b$.

This is a Computer Engineering course, however I am not able to answer these questions. What is the keyword to find a solution on the issue?
Thanks in advance.

The $2\times 2$ matrix has determinant close to zero, and so its condition number is very large, causing numerical instability.

The explicit solution of your system is
$$
x=\frac{a}{a^2-b^2}, y=-\frac{b}{a^2-b^2}.
$$
Therefore
$$
x+y = \frac{a-b}{a^2-b^2} = \frac{1}{a+b},
$$
thus avoiding the numerical issues.


$\tilde \Omega$ for division by logarithmic factor Is $\Omega \left(\frac{n}{\log{n}} \right)\subset \tilde\Omega(n)$?

The notation $\tilde\Omega$ isn't completely standard, and should be explained whenever used. Usually it hides logarithmic factors, and in that case, what you wrote holds.


Algorithm to convert decimal number to binary I am reading this material to understand the basics of number system.
I am stuck at a point in that material where it writes the algorithm to convert a decimal number to binary number.
The heading of that part where I am stuck is Decimal to Base
The algorithm (may be presented less than faithfully, please refer the link) it mentions there is:

  Let $p = \lfloor \sqrt{V} \rfloor$
  Let $v = \lfloor \dfrac V {B^p} \rfloor$
  (v is the next digit to the right)
  Make $V = V − v * B^p$
  Repeat steps 1 through 3 until $p = 0$

It is explaining by taking an example of converting decimal number 236 to binary.

I am not getting how it is calculating the 1st step, i.e. to get the value of p.

It writes that p = int(square root of V)

Now, square root of 236 = 15.36229149573721635154

As per point number 1, p = integer part of 15.36229149573721635154
So, I remove the decimal part and p then becomes 15. But the material there says it is 7.

I can't get what is happening here. I am stuck.

Just converting the comment into a short answer:

$7 = \text{int}(\log_{2} 236)$. Generally, $p = \text{int}(\log_{B}V)$.

As other people pointed out, this algorithm is needlessly complicated and not practical; it is not easy to calculate $\log_B V$ for large $V$ by pencil and paper. Instead, use the other algorithm which is also mentioned in the article you are reading:

From decimal to binary

Step 1: Check if your number is odd or even.
Step 2: If it's even, write 0 (proceeding backwards, adding binary digits to the left of the result).
Step 3: Otherwise, if it's odd, write 1 (in the same way).
Step 4: Divide your number by 2 (dropping any fraction) and go back to step 1. Repeat until your original number is 0.


Push two symbols to stack at once in a push down automata I am pretty new to PDAs and I was solving a problem which asked to design a PDA for the following: $a^n b^{2n}$.

The transitions on the PDAs I've encountered so far have pushed only one symbol onto the stack at any time. Can we push two symbols?
Eg: for every $a$ I encounter I push two symbols.  Thus, the transition will be:

$\Delta(q_0, a,0;000) \to \Delta(q_0)$

where "$a,0;000$" indicates pushing two zeroes onto stack for every $a$ that it encounters.

There are some options (from comments):

By some definition of PDA, you can push a string $w \in \Gamma^\ast$, where $\Gamma$ is the stack alphabet. (from abc's comment)
Even if you could push only one symbol per transition, you could modify your PDA to push the first -> move to a new state -> push the second -> continue as usual. (from chi's comment)
The third option is to use multiple stack symbols encoding different things. (from Raphael's comment)


Selecting Columns with Minimum Overlaps Given a matrix $A=[a_{ij}]$ of positive number $0\leq a_{ij}\leq1$ that has $m$ rows and $n$ columns. I would like to select, for each row $i$, a set of columns $S_i$ such that $$\sum_{j\in S_i} a_{ij}\geq1,$$ and the number of overlaps $\Delta$ is minimum. The number of overlaps $\Delta$ is calculated as follows: $$\Delta=\sum_{1\leq p<q\leq m}\Delta(S_p,S_q),$$ where, for any pair of columns $(S_p,S_q)$, we have $S_p\cap S_q\ne\emptyset\iff\Delta(S_p,S_q)=1$.

I would like to find an algorithm that minimizes the number of overlaps.

I tried to sort $a_{ij}$ for each $i$ such that $a_{i1}\geq a_{i2}\geq \cdots\geq a_{in}$, then make $S_i=\{1\}$ and verify the sum to be larger than $1$, if not make $S_i=\{1,2\}$, and so on. But, I found a counter-example for this to be non-optimal.

I don't know if there is a polynomial-time algorithm, but if your matrix is not too large, you could try approaching this with integer linear programming.  Define zero-or-one variables $x_{ij}$, with the intended meaning that $x_{ij}=1$ means $j \in S_i$.  Then you have the constraints

$$\sum_{j} a_{ij} x_{ij} \ge 1.$$

Also, introduce zero-or-one variables $o_{pq}$, with the intended meaning that $o_{pq}=\Delta(S_p,S_q)$, and enforce that

$$o_{pq} = (x_{p1} \land x_{q1}) \lor \dots \lor (x_{pn} \land x_{qn})$$

using the techniques in Express boolean logic operations in zero-one integer linear programming (ILP).  (In other words, you introduce fresh temporary zero-or-one variables $o'_{pqj}$ and add the constraints $o'_{pqj} \ge x_{pj} + x_{qj}-1$, $o'_{pqj} \le x_{pj}$, $o'_{pqj} \le x_{qj}$, $o_{pq} \le o'_{pq1} + \dots + o'_{pqn}$, $o_{pq} \ge o'_{pqj}$.)

Finally, minimize $\sum_{p<q} o_{pq}$, subject to the constraints above.  This is a set of linear inequalities over integer variables, so you can feed it to an off-the-shelf ILP solver and hope it finds you a good solution.  This algorithm will have exponential running time in the worst case, but ILP solvers incorporate many heuristics, so if the matrix is not too large, it's possible this might give you good results in a reasonable amount of time.


Qualifications for a problem to be solved as a single source shortest path problem What are the pre-conditions for any problem X to be qualified for being solved in a single source shortest path problem (SSSP) setting?

Lets, say we have a problem X. What should be the pre-conditions that we check in problem X definition that would allow us to formulate it as a SSSP.

Initial Idea for solution: I believe if it satisfies the property of optimal substructure. One can formulate the problem as SSSP as well.

Wonderful question!

In spite of the question been very general, this is indeed a research topic by itself. I will rephrase slightly the question as follows: "what are the conditions that enable the applicability of Dijkstra and/or A$^*$ to solve a problem?" Obviously, for those cases that could be identified, the translation you mention to a single-source shortest path comes from the fact that either Dijkstra or A$^*$ (if a heuristic function is available) can solve the problem.

As a matter of fact, your initial guess, optimal substructure is not far from the real answer. As others might not know this concept, let me please introduce a related concept to that:

Definition (Prefix Optimality) A solution path $\pi=\langle s, v_1, v_2, \ldots v_k\rangle$ is prefix-optimal if each of its prefixes is an optimal solution to the corresponding partial problem.

This definition is a specialized version of optimal substructure for the path-finding problem.

This said, the answer to your problem are Cost Algebras. Cost algebras propose a general notion of costs under which various
search algorithms can be reformulated. More recently, an
abstract formalism based on cost algebras has been introduced for
costs suited for heuristic search algorithms such as A$^*$. See Stefan Edelkamp, Shahid Jabbar and Alberto Lluch Lafuente. Cost-Algebraic Heuristic Search. American Association for Artificial Intelligence, 2005, 1362-1367.

Definition (Monoid) Let $A$ be a set and $\times : A\times A\rightarrow A$ be a binary operator. A monoid is a tuple $(A, \times, \mathbf{1})$, if
$\mathbf{1}\in A$ and for all $a,b,c\in A$: (1) $a\times b\in A$; (2) $a\times (b\times c)= (a\times b)\times c$; (3) $a\times\mathbf{1}=\mathbf{1}\times a=a$.

We have a set, and an operation defined over the elements of our set. Let us now define a total order over them:

Definition (Total order) Let $A$ be a set. A relation $\preceq\in A\times A$ is a total order whenever for all $a,b,c\in A$: (1) $a\preceq a$; (2) $a\preceq b \wedge b\preceq a\Rightarrow a=b$; (3) $a\preceq b\wedge b\preceq c\Rightarrow a\preceq c$; (4) $a\preceq b\vee b\preceq a$.

Additionally, the least and greatest operations, denoted as
$\sqcup$ and $\sqcap$ respectively, are defined as follows: $\sqcup
A=c$ such that $c\preceq a, \forall a\in A$ and $\sqcap A=c$ such that
$a\preceq c, \forall a\in A$. A set $A$ is isotone if $a\preceq b$
implies both $a\times c\preceq b\times c$ and $c\times a\preceq
c\times b$, $\forall a, b, c\in A$.

With all these elements we can finally introduce Cost Algebras:

Definition (Cost Algebra) A cost algebra $\mathcal{A}$ is defined as a 6-tuple $\langle A, \sqcup, \times, \preceq, \mathbf{0}, \mathbf{1} \rangle$, such that:

$\langle A, \times, \mathbf{1} \rangle$ is a monoid
$\preceq$ is a total order induced by $\sqcup$
$\mathbf{0}=\sqcap A$
$\mathbf{1}=\sqcup A$
$A$ is isotone

Now, any problem whose formulation satisfies the defintion of a Cost Algebra, can be solved with Dijkstra and/or A$^*$. The following are instances of cost algebras given by the authors:

$\langle \{\top, \bot\}, \vee, \wedge, \Rightarrow, \bot, \top \rangle$ (boolean): Network service availability
$\langle \mathbb{R}^+\cup \{+\infty\}, \min, +, \leq, +\infty, 0\rangle$ (optimization): Price, propagation delay
$\langle \mathbb{R}^+\cup \{+\infty\}, \max, \min, \geq, 0, +\infty\rangle$ (max/min): Bandwidth
$\langle [0,1], \min, \cdot, \geq, 0, 1\rangle$ (probabilistic): Performance and rates
$\langle [0,1], \max, \min, \geq, 0, 1\rangle$ (fuzzy): Performance and rates

Just a minute! What about your initial guess? Well, the authors proved that Cost Algebras actually imply prefix optimality (and hence, optimal substructure) so that their answer is more general than just saying that the problem has to verify the latter. As a matter of fact, Cost Algebras are verifiable whereas optimal substructure can not be immediately decided.

Hope this helps,


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.


In what sense a type of parser is less power than the other? I am learning LR(0), SLR(1), CLR(1) and LALR(1) parsers.
I know how parsing tables of each of them is formed. If x < y means parser x is less "powerful" that parser y, then, I read, the relationship between these parsers can be shown as:

  LR(0) < SLR(1) < CLR(1) < LALR(1)

However, I am not very clear about exactly what being "powerful" means. I can guess following possibilities for being less powerful:

a. Cannot accept valid string
b. Accept valid string very late
c. Cannot reject invalid string
d. Reject invalid string very late
f. Involves SR, RR conflict for some grammars

Doubts

I know point 5 holds for sure. However what exact effect a conflict have on parsing? Do we say that parser is non deterministic and/or requires backtracking to steps involving conflict or we simply say parser of certain type cannot be simply prepared for given grammar?
Which of first four (a,b,c,d) holds? I tried solving one example, for which I prepared both SLR(1) and CLR(1) parsing table. I SLR(1) parsing table had reduce move for state 2 and terminal ), whereas CLR(1) did not. I took an invalid string for which SLR(1) was able to incorrectly reduce when stack top was state 2 and next input symbol was ). But eventually it failed to shift ). So, in the end rejecting the string. However, CLR(1) rejected the string right away without incorrectly reducing. Is this what all can happen? Or there can be an invalid string which SLR(1) may incorrectly accept (point c)? Or points (a) and (b) do also hold?
I feel only point (d) holds. Also SLR(1) and CLR(1) can accept valid string in same number of steps (that is, point b does not hold). Am I right with what I feel?

 Edit

I concluded following for above points (a) through (d). Need someone to confirm:

(a) SLR(1) always accept valid strings as it will be able to correctly do shift reduce moves for such strings. So, point (a) is incorrect.

(b) Accepting valid strings late can only happen when valid string causes traversing through incorrect reduce moves of SLR(1) parsing table. However, this never happens. Valid strings can never be accepted by going through incorrect reduce move cells of parsing table. Those are only hit by invalid strings. Hence, point (b) is also wrong.

(c) SLR(1) can never fail to reject invalid string as it will always fail to shift some terminal in such string. So, point c is also not correct.

(d) SLR may reject some invalid strings late since it may do incorrectly do some reductions. So only point d is correct.

Another (possibly last) doubt

Though in (c) above, I said SLR(1) can never fail to reject invalid string, I doubt its correctness. If a parser accepts invalid string, we simply say that the parser does not implement that grammar, right? But my doubt is whether such parser always involve SR / RR and such "conflict is the only reason to fail to reject invalid string"? We know that SLR can do some incorrect reductions. So, "can't such incorrect reduction be reason for acceptance of invalid string"? Or in other words, for some invalid string, can't SLR shift all of it (so that no terminal will remain un-shifted in the end), and finally do incorrect reduction of whole invalid input string to starting symbol S, thus accepting invalid string? After all we know SLR parser may do some incorrect reductions. Then, why it cant do incorrect reduction of whole invalid input string to the start symbol?

Assuming that by "CLR" you mean "canonical LR", then you have the order wrong; the correct containment order is

$LR(0) < SLR(1) < LALR(1) < CLR(1)$

A possibly more meaningful way of saying that is that if we define $G_X$ to be the set of context-free grammars which can be parsed with algorithm $X$, then

$G_{LR(0)} \subset G_{SLR(1)} \subset G_{LALR(1)} \subset G_{CLR(1)}$

That containment sequence does not apply to languages. If we say that $L_X$ is the set of languages for which there is a grammar in $G_X$, then we will find that

$L_{LR(0)} \subset L_{SLR(1)} \subseteq L_{LALR(1)} \subseteq L_{CLR(1)}$

For all of these parsing algorithms, the fact that the algorithm cannot produce a conflict-free parsing table for a particular grammar means that that grammar cannot be parsed with that algorithm. The word "accept" is quite confusing here: an algorithm produces a parser from a grammar (or fails to do so); the parser then accepts those sentences which are in the grammar's language. If an algorithm produces a parser for a grammar, then that parser will be 100% precise: it will accept all sentences in that grammar's language and reject all other sentences.

Furthermore, all these LR parsers have linear time and space complexity (in the size of the sentence to be recognised), and all of them reject invalid inputs at the earliest possible point, which is as soon as the prefix of the input cannot be the prefix of any sentence in the language. It is true that some of the parsers may perform extra reduce actions before reporting failure, but that is not considered in the definition of a grammar's "power".


What is the difference between transmission delay, queuing delay, and processing delay? My book defines queuing delay as the time the packet waits to be transmitted onto the link. It defines transmission delay as the amount of time required to push all of the packet's bits onto the link. It defines processing delay as "the time required to examine the packet’s header and determine where to direct the packet". I do not completely understand the difference. The first two sound very similar and processing delay sounds like it is part of one of the other two. Can anyone explain me the difference?

There's some similarity.  In the end, they all get bundled up into one big "delay" factor, but the size of the delays depends on different factors so it makes sense to break them apart.

Transmission delay is a delay based on how long it takes to send the signal down the transmission line.  This includes costs like the time it takes for an EM signal (or other signal) to propagate from one side to the other.  It also includes costs like training signals that are often put on the front of a packet to help the receiver synchronize clocks.  The important factor to transmission delays is that the packet is in motion.  Once the transmission period starts, bits have to keep appearing on the wire one after another, without unexpected delays.
Queuing delay is a delay based on how long the packet has to sit around in the router.  Quite often the wire is busy, so we can't transmit a packet immediately.  In these cases, the packet sits, ready to go, in a queue.  These delays are almost entirely defined by the amount of traffic on the network (often queuing delay is the only traffic dependent part of the puzzle!).  The more traffic there is, the more likely a packet finds itself stuck behind another packet in the queue, just sitting in memory, waiting.
Processing delay is the delay based on how long it takes the router to figure out where to send the packet.  Once it figures it out, it will queue the packet for transmission.  These costs are predominantly based on the complexity of the protocol.  The router must decode enough of the packet to figure out which queue to put the packet in.  Sometimes that's easy, sometimes it's not.  Typically the lower level layers of the stack have simpler protocols.  If a switch doesn't already know which physical port to send a packet to, it will typically send it to all ports, queuing the packet in many queues immediately.  On the other hand, at a higher level such as those which come into play in IP protocols, the processing may include making an ARP request to find out the physical address of the destination before queuing the packet for transmission.  One may choose to call that a processing delay.


P=NP when number of inputs that give 1 is bounded by polynomial Suppose there exists some NP-complete problem such that the number of inputs that gives 1 as an output is bounded by a polynomial; that is, if the problem is $f \colon \{0, 1 \}^* \to \{0, 1\}$, then, for every $n$, $|\{ x \in \{0, 1 \}^n : f(x) = 1\}| \leq p(n)$ for some polynomial $p$. Then, I want to show that the existence of this problem implies $\mathsf{P} = \mathsf{NP}$. Is it somehow related to LEXSAT?

The result you are trying to prove is known as Mahaney's theorem. It is covered by textbooks on complexity theory, and in many online lecture notes.

The proof in Jonathan Katz' lecture notes indeed uses LEXSAT.


Find most valuable subset of a node weighed tree Suppose you got a directed acyclic graph of positvely and negatively weighed nodes $T\hspace{-0.02 in}$.

Now I have to find the the subset  $M\subseteq T$  such that the sum of

the weights of the nodes in $M$ is maximised, but if  $v \in M$  then all

children of $v$ as well as their children, and so on have to be in $M$ too.

For now my algorithm is as follows:

calculate the depth of each node (how many nodes you have to
traverse at maximum to reach one which doesn't have any children)
for all nodes $v$ of depth $n$ do the following:

add up the weight of $v$ and the weights of all children and
grandchildren,
... (you get the idea) of $v$
if the last step added up to a positive value then mark $v$ and
all children of $v$ as in $M$ and don't consider them any further
if the last step marked any node with the current depth then repeat
for this depth (since the sums changed) otherwise increment n.

This works fine for some DAGs:    (Note:  the edges are directed downwards)

As expected all nodes except the top node are in $M$

But for othes the algorithm falls short:

The algorithm outputs that  $M = \emptyset$ ,  whereas  $M=T$  should be the case.

Is there an algorithm which solves a similar problem?

If no, how can I correct my solution?  Any help is highly appreciated.

PS:    I apollogize for the use of MS Paint.  Sorry for that.

I forget the name but it's a classic minimum-cut problem. You can always consider min-cut approach when you want to choose an optimal subset.

(Edit: It's called "project selection problem".)

Think about cutting nodes into two partitions $S$, $T$ and $S$ is what we choose. Ideally we want $S$ to contain all the positive nodes and avoid any negative node. However, it's not always possible. If there exists an edge $(u,v)$, $u\in S\to v\in S$. In the min-cut model, it means we can't cut this edge, so we set $capacity(u,v)=\inf$. Next consider what we should pay if we can't assign them ideally.

Create a source $s$ and a target $t$. For each node $u$, if $w_u$ is positive, add an edge $(s,u)$ and set $capacity(s,u)=w_u$. It means we lose $w_u$ if $u\notin S$. If $w_u$ is negative, add $(u,t)$ and set $capacity(u,t)=-w_u$. It means we lose $-w_u$ if $u \in S$.

The answer is $\sum_{w_u>0} w_u-min cut(s,t)$, and $M$ is the source partition.


How to convert improper CFG to weakly equivalent one? In wikipedia there's the definition for "Proper CFG".

  A context-free grammar is said to be proper, if it has

  $$\text{no unreachable symbols}: \forall N \in V: \exists \alpha,\beta
> \in (V\cup\Sigma)^*: S \stackrel{*}{\Rightarrow} \alpha{N}\beta$$
  $$\text{no unproductive symbols}: \forall N \in V: \exists w \in
> \Sigma^*: N \stackrel{*}{\Rightarrow} w$$ $$\text{no ε-productions}:
> \neg\exists N \in V: (N, \varepsilon) \in R$$ $$\text{no cycles}:
> \neg\exists N \in V: N \stackrel{+}{\Rightarrow} N$$

https://en.wikipedia.org/wiki/Context-free_grammar#Proper_CFGs

It's also stated that non-proper CFGs can be transformed into "weakly equivalent" CFGs:

  In formal language theory, weak equivalence of two grammars means they generate the same set of strings, i.e. that the formal language they generate is the same.

https://en.wikipedia.org/wiki/Equivalence_(formal_languages)

but I cannot find the algorithm for doing this.

How is it done?

First of all, Wikipedia does supply a reference to a standard textbook. Second, since a proper grammar is one without unproductive symbols, to make a grammar proper all you have to do is erase all unproductive symbols and all productions involving them.


Why not space out memory allocations? In ext4 file system, the files are spaced out as far apart as reasonably possible to allow for efficient reallocation. Why do we not do this in memory?

Why not allocate one memory as page 20, and the next large allocation as page 100 to allow for excess expansion before and after the current allocation? I feel that makes sense for large frequently changing-in-size buffers. For smaller buffers, doing so would probably be a drain on memory because we have to allocate each page for a small amount of bytes(but perhaps do it within a block too in the malloc impl). This would also provide greater memory corruption prevention, allowing segfaults(or windows equivalent) to happen quicker(specifically for larger buffers).

Why don't we do this? I get it on modern 32-bit systems because of limited address space, but why not on 64-bit?

Why is memory different from a hard disk?

Because hard disks have different performance characteristics than RAM.

With hard disks, seeking is extremely slow.  Sequential reads are much faster than random-access reads.  In other words, it's much faster to read data that is stored consecutively than to store data that's scattered all around the disk.  Therefore, there are benefits to making sure your files are contiguous, as much as possible.

RAM doesn't have the same property.  With RAM, there is no penalty for "seeking".  You can pick any page and read from it, and the cost will be the same, no matter where the page is located.  For instance, reading page X and then page Y will have the same cost regardless of whether X and Y are adjacent or not.

So, you end up with different algorithms that are optimized for hardware with different performance characteristics.

Why do hard disks have this strange property?  Because they are based on a rotating piece of iron.  If you read block X on the hard disk, and next want to read block Y, but Y is on the other side of the platter, then you'll have to wait for the platter to finish rotating far enough for Y to be under the read head.  That takes time.  RAM doesn't have this property.

Interestingly, the differences are becoming less these days.  Today, SSD (solid state storage devices, based on Flash storage) are becoming a popular replacement for hard disks.  SSD's have their own performance characteristics, but they're more like RAM than like magnetic hard disks.  This means that the filesystem optimizations you'd do for a SSD-oriented filesystem are different from the ones you'd do for a hard-drive-oriented filesystem.  Many of today's filesystems were designed decades ago when magnetic hard disks were dominant, and optimize for the performance characteristics of magnetic hard disks.

Why not harden software by deliberately leaving space between buffers?

You are implicitly proposing a scheme for making software more robust against out-of-bounds errors and buffer overruns: leave plenty of unallocated space between each pair of buffers allocated on the heap.

That's not a bad idea.  It's been proposed before and studied in considerable depth.  It does add some robustness against bugs.  It can also make buffer overrun attacks harder, especially if you randomize the location of all heap buffers.  It's also relatively easy to deploy in a way that is compatible with legacy software.  So it does have some quite attractive advantages.

However, it also has some disadvantages.  It imposes some performance overhead -- not a huge amount, but enough to be a bit painful.  Why does it impose performance overhead?  Largely because it reduces spatial locality.  Consider two 16-byte allocations.  Current allocators try to pack them together into a single page.  In your scheme, we'd have to put each allocation onto its own page.  That means we have a lot more pages, which means that we get a lower TLB hit rate.

There are different variants on this scheme, with different performance implications, but they all run up against the challenge: in exchange for the robustness and security benefits, there is some non-zero performance overhead.  So that's one reason why people might not adopt it.

The other big reason is: we're using platforms and allocators that were designed decades ago.  At the time, security wasn't as critical as it is today, so this sounded like a pretty unattractive proposal: I get to implement something more complicated and fiddly, and it'll make my entire system slower?  No thanks.

Today given the magnitude of security problems we're facing, there's gradually increasing interest in these alternatives.  But they still face an uphill battle, because of the non-zero performance implications.

To learn more about academic research on this subject, read research papers on the Diehard, Dieharder, and Archipelago systems.  They discuss the design in a very accessible way and measure the performance and other costs of such a scheme.  If you're still intrigued, you can explore the literature where other researchers have explored other points in the design space to understand their implications.

Bottom line: you're not the first to think of this, and it is a pretty attractive idea, but it also comes with some significant costs.


In cycle stealing mode, Does CPU gets blocked for 1 cycle or blocked till DMA transfer completion? In cycle stealing mode, is CPU idle during data transfer between peripheral devices or idle only for 1 cycle ( during shifting of bus controls ) ?
Because I'm unable to understand these lines.

  The DMA module is transferring characters at the rate of 1200 characters per second. or one every 833 microsecond. The DMA therefore steals every 833rd cycle.

Now, I think these lines make sense only if we assume CPU is blocked for 1 cycle not during 833microsecond(during DMA transfer).
Please anyone help me where I'm wrong or am I missing something.

The CPU doesn't stay idle at all. It just gives the control of the data Bus to the DMA for 1 memory cycle . DMA transfers the data in this cycle which is consistent with it's transfer rate. Meanwhile the CPU can perform operations which do not involve the memory bus (by the means of cache memory and registers). In the scenario which you have presented assuming each instruction takes 1 cycle to complete , every 833rd instruction will have to wait for the DMA to complete its operation.


Reductions between LIS and LCS Given an oracle that returns both the length and the subsequence for the Longest Increasing Subsequence of a given input $A$ of $n$ elements $\text{LIS}(A,n)$, can one use a polynomial number of calls to it to find the length of the Longest Common Subsequence of two sequences $A$ and $B$ ($\text{LCS}(A,B)$)? If so, how few calls can we query the LIS oracle in order to find the length of $\text{LCS(A,B)}$?

Alternatively, given an oracle for finding both the subsequence and length of the Longest Common Subsequence between two sequences, it's easy to find $\text{LIS}(A)$: Given a sequence $A$, sort $A$ into $A'$, and calculate $\text{LCS}(A,A')$.

This question is prompted by the fact that there are $O(n\log n)$ algorithms for LIS but not LCS. On a separate note, are there any results comparing the hardness of the two problems or giving a superlinear/quadratic lower bound to LCS?

Given an oracle that returns both the length and the subsequence for the Longest Increasing Subsequence of a given input $A$ of $n$ elements $\text{LIS}(A,n)$, can one use a polynomial number of calls to it to find the length of the Longest Common Subsequence of two sequences $A$ and $B$ ($\text{LCS}(A,B)$)? If so, how few calls can we query the LIS oracle in order to find the length of $\text{LCS(A,B)}$?

Well, we can find $\text{LCS}(A,B)$ without any call to the oracle since we can just run any algorithm that finds $\text{LCS}(A,B)$ such as brutal force or a solution by dynamic programming.

What you intended to ask was how much we can reduce the time-complexity of algorithms that find $\text{LCS}(A,B)$ if the oracle is available. The time-complexity will consist of two parts. One part comes from ordinary operations, and the other part comes from the calls to the oracle. There are two questions here.

Question one. Can we use less ordinary operations (asymptotically) with the availability of the oracle?

Question two.  If we can, how few calls to the oracle are needed to lower the complexity of the ordinary operations?

When one of $A$ and $B$ consists of distinct elements

Suppose the elements in $A$ are distinct. Here is an algorithm that employs the oracle. The idea of the algorithm is that if we regard the natural order of elements in $A$ according to the indices as defining a strictly increasing order, a common subsequence of $A$ and $B$ is exactly an increasing subsequence of $B$.

Keeping $A$ intact, sort $A$ into a new sequence $\alpha$.
Initialize a new sequence $I$.
For $i$ from 0 to size($B$) exclusive, try finding the index $j$ such that $A[j]$ is $B[i]$. If found, append $\alpha[j]$ to $I$.
Return the length that is returned by the oracle given sequence $I$.

There are two ways to implement step 2.

If the elements in $A$ and $B$ can be totally ordered, we can sorted the elements in $A$, keeping track of each element's index in $A$. Then a binary search can find that index $j$.
Construct a hash set whose elements are $(A[i],i)$ for all $i$, where the hash depends only on $A[i]$. Then we can use the hash set to find that index $j$.

So an answer to question one and two is that we can use a single call to the oracle to lower the complexity of the ordinary operations from $O(nm)$ to

$O(n\log n + m \log n)$ when $m\gg\log n$ or
$O(m)$ if the operation of finding an element in a hashset is considered $O(1)$.

Here $n$ is the number of distinct elements in one array and $m$ is the number of the elements in the other array.

When both $A$ and $B$ contain duplicate elements

It is not clear how we can take advantage of the oracle in order to reach a positive answer to question one. Instead, here is a conditional hardness result.

It is not possible to find $LCS(A,B)$ in time $O(n^{2 - \epsilon})$ for any positive constant $\epsilon$ where $n$ is the length of $A$ and $B$, if we can assume the strong exponential time hypothesis. This is shown in Tight Hardness Results for LCS and Other Sequence Similarity Measures by Amir Abboud, Arturs Backurs and Virginia Vassilevska Williams, 2015.


Memoization without array In Cormen et al.'s Introduction to algorithms, section 15.3 Elements of dynamic programming explains memoization as follow:

  A memoized recursive algorithm maintains an entry in a table for the solution to each subproblem. Each table entry initially contains a special value to indicate that the entry has yet to be filled in. When the subproblem is first encountered as the recursive algorithm unfolds, its solution is computed and then stored in the table. Each subsequent time that we encounter this subproblem, we simply look up the value stored in the table and return it.

And it adds, as a footnote:

  This approach presupposes that we know the set of all possible subproblem parameters and that we have established the relationship between table positions and subproblems. Another, more general, approach is to memoize by using hashing with the subproblem parameters as keys.

Is there any well-know DP problems that requires (or makes it easier) to store memoized values in a dictionary rather than in a (multi dimensional)array?

Background: if this is of any use, the reason for this question is that I'm trying to motivate the notion of (self-balanced) binary search trees to people that has just seen dynamic programming.

There are probably better examples, but here is one, off the top of my head:

Let's say you want to check whether the edit distance between two strings $S,T$ is $\le d$, and if it is, compute the edit distance.  You can use the standard dynamic programming algorithm to compute the edit distance, but "prune" the computation (stop the recursion) at any place where the edit distance is known to be $>d$.  This means you probably won't need to fill in the entire table; you'll only need to fill in some of the entries.  Thus, using a dictionary can give a performance boost.


(Formal) Proofs of Node Centrality Properties Despite there being relatively frequent discourse regarding the usage and effectiveness of various node centralities when analysing the influential spreaders of a graph, I have thus far struggled to find any formal treatments of such discussions. For example, betweeness centrality is theoretically well-defined and is popular in practice for finding influential spreading members, but is there any proof of its effectiveness in this capacity (e.g. compared to any other centrality)? All the arguments I have witnessed thus far have been largely simulation/virtual-experiment based. My question is: is there anywhere I can more formal treatments of this subject matter?

Whilst I am generally curious to see if possible formal discussions around graph analysis efficacy could exist, I have my suspicions as to why this is not already the case given that formal comparisons of this nature could be infeasible... but perhaps this is not true?

Example papers/articles:
https://www.nature.com/articles/nphys1746.pdf
https://www.nature.com/articles/srep19307.pdf
https://cambridge-intelligence.com/keylines-faqs-social-network-analysis/

There are many papers dealing with the algorithmic aspects of these measures, with formal proofs, complexity analysis, and so on. However, I understand that this is not really what you are looking for.
There are only few formal works on their actual relevance for describing features of interest in practice.
Pagerank is a notable exception, though. Its connections to random walks, Markov chains, and matrices, as well as its wide use and mere features, make it a great metric for formal analysis. I particularly recommend the book Google's PageRank and Beyond: The Science of Search Engine Rankings, by
Amy N. Langville and Carl D. Meyer. It deals with many aspects, putting together practical concerns as well as theoretical analysis.
Node degree distribution is another important exception, although one may consider it too basic to be a valid answer here. Still, there are many formal works showing the importance of high degree nodes in random graphs that model real-world complex networks. See for instance our survey entitled Impact of random failures and attacks on Poisson and power-law random networks.


More details about the Baillie–PSW test It's clear that Mathematica uses the Baillie–PSW test for its PrimeQ function (which tests primality), and as I read in the Mathematica documentation, it starts with trial division, then base 2 and 3 Miller–Rabin, and then Lucas pseudoprime test. My question is:

  Can we remove base 2 and 3 and use only a random base?

Also, can any one suggest a good reference about this primality test other than Wikipedia?

The advantage in using base 2 is that we know all of the psp's base 2 up to $2^{64}$. It has been verified that none of these psp(2)'s passes a Lucas test when the parameters $P, Q$ are chosen in accord with any of the methods in the Baillie/Wagstaff paper.

If you choose a random base, there might be some composite $n$ that passes both the Fermat and Lucas tests. For example, $n = 5777$ is a strong psp base 76, and is also a Lucas pseudoprime.

By the way, if you implement a Lucas test, I would also recommend adding the following check, which is virtually free once you reach the end of the Lucas calculation. If $n$ is an odd prime and $(n, QD) = 1$ where $D = P^2 - 4Q$, (and, as usual, $\left(\frac{D}{n}\right) = -1$ (a Jacobi symbol), then $V_{n+1} \equiv 2Q \pmod n$. If $D, P$, and $Q$ are chosen by method $A^*$ (see Baillie/Wagstaff), then 913 is the only odd composite number up to 25 billion for which this congruence holds. (The B/W paper gives a limit of $10^8$, but I've recently carried the calculation farther). So, in addition to the sprp(2) and slprp(P,Q) tests, this congruence adds additional strength to the primality test.


What is exponent of denormalized real in IEEE 754 floating point format? I was reading this link.

Here I noticed that, in table titles "Float Values (b = bias)", in exponent column, entry for denormalized reals is $00..00$, but in value column, the entry is $-b+1$. Why is there $+1$? If we consider bias of $127$ for single precision format, shouldnt it be $0-127$ only? If its $-126$, then shouldnt the entry in the exponent column be $00..01$?

(The article seems to have taken from Stallings book specified in the references. Stallings book also says the same as above.)

Both an exponent field of 00000000 and 00000001 encode an exponent of -126, but with 00000000 there is no implicit leading 1 and with 00000001 there is. Consider going from 0x00800000 (smallest normal) to 0x007fffff (biggest denormal). For 0x00800000 the significand (including leading 1) is still 0x00800000 (a nice coincidence), for 0x007fffff is significand is just 0x007fffff. Since the exponent remains the same, these are just as adjacent as they seem (the distance between them is the lowest non-zero denormal).

If the exponent for denormals was -127, the denormals would only fill up to halfway between zero and the lowest normal, leaving a large gap between the highest denormal and the lowest normal.

Normally the number line including denormals looks like this (if you had 2 bits of significand, so 4 numbers per binade): (source)

You can see the denormals and the numbers in the first normalized binade are equally spaced, meaning they have the same exponent. What happens if the denormals had the exponent which their encoding seems to imply?

A gap appears.


Find number of triples that sum up to zero in query-intervals My problem is that we have an array of $N$ integers $(N <=5000)$ on the interval $[-10^6,10^6]$. We also have $Q$ queries $(Q <= 10^5)$ giving us some range in the array.

For each query, we want to find the number of triplets of indices in the range such that the sum of those array values equal to zero. More formally we want to find the number of ways we can choose unordered distinct triples $i, j$ and $k$(within the given query range) such that $a[i]+a[j]+a[k] = 0$.

I'm thinking of doing an $O(N^2)$ pre-computation and $O(\log N)$ time for each query but I am unable to come up with a concrete working idea. Any help would be appreciated.

Edit: queries can be processed offline, as the array does not need to be updated.

Let us call the input array $A$. We build the solution in three steps:

First, for each value $v$ between $-10^6$ and $10^6$, build a list with all the indices in $i \in \{1, \dots N\}$, where $A_i = v$ and keep all these lists sorted. One way to achieve this is to iterate over $A$ and append the index of each element to its corresponding list. Let $L_v$ be the list corresponding to a value $v \in \{-10^6, \dots 10^6\}$.

In the second step, we will build a two-dimensional array $C[N][N]$, where
\begin{equation}
C[i][j] = \begin{cases}
|\{k: i+j+k = 0, k \in \{i, \dots j\}\}| &;i\leq j,\\
0 &;\text{Otherwise}.
\end{cases}
\end{equation}
We can compute $C$ by iterating over all pairs $i, j \in \{1, \dots N\}$, $j\geq i$, and for each such pair, let $u = A_i$ and $v = A_j$. Let $w = -(u + v)$. Note that $u + v + w = 0$, Using binary-search twice, find in $L_w$ the lowest index not less than $i$ and the highest index not greater than $j$. The difference of the indices of these two values plus 1 is the number of elements $w$ between $A_i$ and $A_j$, such that $A_i + A_j + w = 0$, which is exactly $C[i][j]$.

Now as a last pre-processing step, Let us compute the two-dimensional array $S$, the prefix-sums over $C$, that means:
$$
S[i][j] = C[i][j] - C[i-1][j] - C[i][j-1] + C[i-1][j-1],
$$
where we consider $C[i][j] = 0$ for $i = 0$ or $j = 0$ (since we considered 1-indexed arrays).

Now for each query $i, j$, output
$$S[j][j] - S[i-1][j] - S[j][i-1] + S[i-1][i-1],$$
where again, we consider $S[i][j] = 0$ for $i = 0$ or $j=0$.

Based on the previous definitions, try to see why this yields the answer you are looking for.

The running time is $O(N^2\log N)$ pre-processing and $O(1)$ per query. The space complexity is $O(N^2 + M)$, where $M$ is the largest value (equal to $10^6$ in your case), which is needed to keep track of the start of each list $L_i$ for each $i \in [-M, M]$.


Does the Bondy-Chvátal theorem have algorithmic applications beyond Ore's theorem? I'm toying around with graph properties and I want to make some effort to check whether a given graph is Hamiltonian. I understand that the general problem is NP-complete, but I'm looking for simple checks that are easy to implement and computationally inexpensive to get some indication.

So I've implemented Dirac's and Ore's theorems to check the sufficient conditions for whether a graph is Hamiltonian (in my implementation Dirac's is a cheap check before I run Ore's). Digging around I found that the Bondy-Chvátal theorem generalizes both and is thus more powerful, but it seems to be less useful for algorithmic purposes.

If I understand it correctly, the theorem states that a graph is Hamiltonian if and only if its closure is Hamiltonian. The only constructive application of this however seems to me to verify that the closure of a graph is a complete graph, which is the case if (and only if?) the graph meets Ore's condition anyway, which is easier to implement efficiently.

I'm wondering though, might there be some other algorithmic application I may have missed, or is Bondy-Chvátal indeed impractical in my scenario (and more of theoretical use in general)?

Other way than Bondy-Chvátal theorem is brute force search. However brute force search isn't an efficient way of solving this problem - there can be an exponential number of possibilities to test.

You won't have to test so many possibilities, if you will try following algorithm:

http://arxiv.org/pdf/1405.6347.pdf

The main principle of algorithm is "to think over" which paths(possibilities) should be checked than check many wrong paths.

Algorithm can remove unnecessary edges from graph and test when Hamiltonian cycle can't exist in graph.

Algorithms implementation:

http://findinghamiltoniancycle.codeplex.com/


Priority Queue Using Stack Can one build a priority queue using stacks, such that the priority queue has the same complexity for each operation.
Could it be done? If so how? If not what is the best solution that can be done?

Each operation of a stack using an array is $O(1)$ whereas almost all operation of priority queue is $O(logn)$.
an implementation can be done using $2D$ stacks, each elements of the stack is again a stack.
When the first element of the main stack is the first element of the other stacks.
The dequeue operation will take $O(n)$ as it is LIFO and the priority queue is FIFO.

Think about it. You can sort an array by adding all the items to a priority queue, then removing the items in sorted order.

If you could run a priority queue in constant time, you could sort in linear time. But you can't.


Polynomial by the size of the output and the input I wounder why the complexity of algorithms always depend on the size of the input, but not on the size of the output.

For example, in a problem that I have solve, the size of the input is exponentially smaller than the size of output. In addition, the complexity of the algorithm is polynomial by the size of the output, and pseudo-polynomial by the size of the input.

I think that in such case, the complexity of  algorithm  is said to be "polynomial", but I am not sure about it.

What are your opinion?

I wonder why the complexity of algorithms [does not] depend on the size of  [...] the output.

But it does!

The size of the input is often used as a trivial lower bound on the running time ("you need to write the output"). So trivial, indeed, that it's rarely talked about in introductory courses. There, the output is usally not the dominating factor so it's not interesting to discuss is further.

Think about what that would mean on the intuitive: an algorithm that writes more bits than it takes time to compute them. That doesn't seem very efficient in itself; maybe your output encoding is bad.

That said, you do on occasion encounter runtime analyses where characteristics of the output appear in the determined bounds. Search and enumeration algorithms, for instance, can admit non-trivial bounds the separate them from brute force ("I don't have to check all candidates, but only at most three times the number of those I want to find").


Does preparing min DFA by combining equivalent states always result in min DFA I know the following fact:

  If $Ma_N=\{w:n_a (w)=Nk,k≥0\}$, then
  Number of states in
  $$Ma_{N1}×Ma_{N2}
=Ma_{N1}∪Ma_{N2}
=Ma_{N1}∩Ma_{N2}
=Ma_{N1}-Ma_{N2}
=LCM(N1,N2)$$
  where $n_a (w)$ is the number of occurrences of $a$ in $w$

I recalled the example I solved: the DFA for the language $(111+11111)^*$. It was given as follows:

It was backed by the fact that Any number greater than 8 can be factored into sum of 3s and 5s.

Q.1 Can we interpret this language as union of two: $(111)^*\cup (11111)^*$?

Q.2 If yes, then should forming union DFA by forming product DFA (and making desired states final as required by union operation) of above two languages $(111)^*$ and $(11111)^*$ and then applying DFA minimization by finding equivalent states result in 9 states? I tried it as below using JFLAP (product DFA on left and auto generated min DFA on right). But I didnt get 9 states. Instead I got number of states $=LCM(3,5)=15$ states.

Q.3 So can we conclude we cannot always get minimum DFA by the approach of combining equivalent states (may be especially when the DFA can be simplified using some mathematical insights)? Or did I made some mistake?

The answer to Q1 is no.

$1^{11}$ is in $(1^3 + 1^5)^*$, but not in $(1^3)^* + (1^5)^*$

I think that leads to the remaining confusions.


Efficiently check if any vertex has a path to its partner vertex So I have a directed graph that looks something like:

I'm trying to make an algorithm that can go through all the vertices and tell me whether we have any path from an upper case letter to its lowercase version, or a path from a lowercase letter to its upper case version. In the above example, we have a path from C to c.  We also have a path from B to b, from a to A, from E to e, and from G to g.  I'd like the algorithm to find at least one of these paths.

The algorithm can stop looking if it just finds one such case where this happens. Each vertex points to at most one different vertex, so the out-degree of every vertex is either zero or one. I'm trying to get this done efficiently (linear time) and can put whatever extra information in the vertices to do it. I've been attempting to use the DFS algorithm to do it because you can work with ancestry but I'm not sure if it works for specific vertex relationships efficiently.

I'm aware that DFS can use discovery time and finish time to find if a vertex is the ancestor of another, and that this is used for cycle detection. I'm basically wondering if there is an efficient way to check if a specific node (that isn't necessarily part of a cycle) is the ancestor of another specific node. Unless, of course, this is unnecessary and there is a better way to go about it.

Observation: Each weakly connected component can contain at most 1 cycle, and every vertex in such a cycle is reachable from every vertex in the weakly connected component.  That's because every vertex that participates in a cycle exhausts its single out-edge by connecting to the next vertex in the cycle, so the only other edges that can be incident on any vertex in this cycle must be in-edges from other vertices.

In more detail: Suppose to the contrary that a single component contains 2 cycles: Then either they are vertex-disjoint or not.  In the former case, there must be an undirected path of edges (i.e., a path in the graph where edge orientation has been forgotten) connecting the two cycles.  But the first and last edges in this undirected path must be "outwards" (i.e., the first must be an in-edge to the first cycle, and the last must be an in-edge to the second cycle), implying that some vertex on the path must have 2 out-edges, so this case cannot happen.  In the latter case, let the two cycles be $C_1$ and $C_2$, and w.l.o.g. suppose $|C_1| \geq |C_2|$.  Let $uv$ be an edge in $C_1$ such that $u \in C_1 \cap C_2$ but $v \notin C_2$.  (Such an edge must exist if $C_1 \neq C_2$.)  Then $u$ must have a successor $w \neq v$ in $C_2$; but this immediately implies that $u$ has outdegree at least 2, so this cannot happen either.

Algorithm phase 1: Detecting a cycle

So, starting at any vertex and successively traversing the single out-edge can only give one of two possible outcomes:

We reach a vertex with no out-edge.  In this case, the component has no cycle.
We reach a vertex we have seen before.  In this case, the component has a single cycle consisting of all vertices visited since the last time the final vertex was visited.  In a $k$-vertex component, the cycle vertices can be identified in $O(k)$ time by numbering the vertices in visitation order and gathering them together in a subsequent pass.

To simplify notation I'll label the vertices with positive and negative integers, instead of upper- and lower-case letters.  We will maintain a counter $c_i$ for each pair of vertices $i, -i$: at the end of the algorithm, $c_i = 2$ if and only if at least one of the vertices $i$ and $-i$ can reach the other by some path.

If a cycle was detected, we can start at any vertex in the cycle and continue following out-edges until we hit the first vertex again, incrementing $c_{|i|}$ for each vertex $i$ encountered.  Also, we (at least conceptually) create a new vertex $x$ to represent "the cycle", and as we proceed through each vertex $v$ in the cycle, we change every non-cycle edge $uv$ to $ux$.  (Conceptually) delete the cycle vertices, and set $z = x$.

If no cycle was detected, set $z$ to the last vertex we found, say $i$, which by construction has no out-edge.  Increment $c_i$.

Observe that since any cycle has been deleted, the component is now a tree with all edges directed toward $z$.

Algorithm phase 2: Reverse DFS

We now perform a DFS starting at $z$ and proceeding "against" the direction of each edge.  During this traversal:

Upon entering a vertex $i$: If $c_{|i|} < 2$, then increment it.
Upon leaving a vertex $i$: If $c_{|i|} = 1$, then decrement it.

This asymmetric increment/decrement scheme ensures that, whenever we discover a path from the root $z$ that contains both vertices in a pair, the discovery (which is recorded as a count of 2) "sticks", while OTOH whenever we discover that no path from the root $z$ through some vertex $i$ also contains $-i$, the discovery of $i$ is "forgotten" -- this has the important effect of not recording as matched any pair $i, -i$ that occur in the same component but such that neither is the ancestor of the other.

The above can all be implemented to take linear time in the number of edges within a component, so the overall time to process the graph is $O(|V|+|E|)$.


What does being Turing complete mean? I see that most definitions of what it is to be Turing-complete are tautological to a degree. For example if you Google "what does being Turing complete mean", you get:

  A computer is Turing complete if it can solve any problem that a Turing machine can...

While it is very well defined whether different systems are Turing complete or not, I haven't seen an explanation of what the implications/consequences of being Turing complete are.

What can a Turing machine do that where no non-Turing machine exists that can also perform the same task? For example a computer can perform simple calculations like (1+5)/3=?, but an ordinary calculator can also do them, which is non-Turing complete if I am correct.

Is there a way to define the capabilities of Turing Machine without just saying "being able to simulate another Turing Machine"?

It's not tautological at all.

A model of computation is Turing-complete if it can simulate all Turing machines, i.e., it is at least as powerful as Turing machines.

One thing that Turing machines can do is simulate other Turing machines (via the universal Turing machine). That means that, if your model of computation can't simulate Turing machines, it can't do at least one thing that Turing machines can do, so it doesn't satisfy the definition, so it isn't Turing complete.  There's no circularity because we didn't define Turing-completeness in terms of itself: we said that Turing-completeness is the property of being able to do everything that Turing machines can.

But there are plenty of other things that models of computation might fail to do. For example, no deterministic finite automaton (DFA) can recognize the class of strings consisting of some number of $a$s followed by the same number of $b$s. Turing machines, on the other hand, can recognize that class of strings. Hence, DFAs are not Turing-complete.

  Is there a way to define the capabilities of Turing Machine without just saying "being able to simulate another Turing Machine"?

I'm not sure what you mean by "define the capabilities of Turing machines". The capabilities are defined in terms of the finite state automaton operating on the infinite tape. (I'll not repeat the full definition but you can find it, e.g., on Wikipedia.)


Number of integers in a certain range with certain properties How would one (quickly) find the number of integers in the range [1, x] for some x, more than half of its digits being one digit, given that $x$ has at most, say, 19 digits.

Brute force would obviously not work in a reasonable amount of time (where "reasonable" means roughly $10^9$ seconds)

Hint: Decompose the range $[1,x]$ into more manageable ranges of the form $[N\cdot 10^{k+1},N\cdot 10^{k+1} + d \cdot 10^k)$, where $d < 10$. Enumerate over the "popular" digit, and use inclusion-exclusion.


MSD vs LSD Radix sort I read the following in CRLS:

I don't understand the text in yellow. Why would radix sort not work so well if we sort by their most significant digit? What extra "piles of cards" is it referring to?

Perhaps I'm not able to follow the example with cards, and an example with actual numbers would be best.

In case it helps, sorting naively by MSD doe not seem to work, even if all values are d-digit numbers:

Input   (1)   (2)   (3)
        *      *      *
 321    132   321   321
 522    321   426   522
 132    426   522   132
 426    522   132   426

where (i) is the result of sorting the previous column by the ith-highest digit.

It would work, the only problem is that it will generate a lot of extra piles for the intermediate results that are difficult to track.
if the sorting algorithm sorts the $d$-digit numbers starting from their most significant digit it would create 10 piles at first (one pile for the numbers starting with 0, another one for those starting with 1 and so on) and then sort each pile recursively as explained in the book.
The problem is that to sort the pile of numbers starting with 0 the algorithm needs to create ten more piles (one for the numbers starting with 00, the second for the numbers starting with 01 and so on, the last pile is for the numbers starting with 09).
Thus we have created 19 piles until now. To sort the pile of the numbers starting with 00 we need to create 10 more piles. If this process continues until the $d$ digit are sorted you can imagine that a huge number of piles are created (how many?).
This are the extra piles that the book was referring to.
If you use LSD radix sort you don't have to split the numbers in piles at all. You can just sort the input pile by last digit, then the same pile by the penultimate digit and so on, after $d$ steps you will end up with the expected result.
The intuition is the following: let $d$ be $2$ and let $83$, $19$ and $17$ be the input.
The first step on MSD radix sort will place $17$ and $19$ before $83$. Then if you sort the same whole pile by the second digit you will end up with $83$ before $17$ which is wrong. You need to split the pile because you have to "remember" the previous sorting made by the algorithm, which is more "important".
Conversely, the first step of LSD radix sort will place $83$ before $17$, then $19$. If you take the whole pile and sort it by the first digit you get $17$, $19$, $83$ which is correct. You don't need to split the pile because the current step of the algorithm is more "important" of the previous ones and it is allowed to "mess up" the previous ordering in any way (for example by placing $83$ after $17$ and $19$). This would work as long as the sorting algorithm used for each digit is stable.


Maximum number of segments with no intersection This is an interview question.
Suppose you have an array of n segments, when each segment is a pair of two integers: start point and end point. For example: (1,3).

Two segments s1,s2 are intersecting if
 (s2.start<=s1.start<=s2.end) or (s1.start<=s2.start<=s1.end)
For example: (1,3),(2,4) are intersecting.

Find an algorithm for finding maximum number of segments in the array (and returning those segments in some list) which don't intersect.

My attempt: I thought maybe some sorting can help, but didn't find how so tried something else. Then the interviewer gave me a hint: the run time expected is O(nlogn).

So now I'm sure the solution need to involve some sorting algorithm, but I don't know how to use it.

Any suggestions?

I can show you a solution that I suspect is $O(n \log n)$, but I haven't proven the runtime.  Edit: Following a linked solution, I amended this solution to be simpler and run in $O(n \log n)$.

So the issue is that if you take a greedy approach, you might choose a 'bad' segment that blocks a favorable choice later.  That is, choices you make at the beginning affect what choices you have available later on.  This suggests a dynamic programming approach.

First step is to sort the segments by their start times.  Then, you need to define exactly what you're going to calculate.  We'll define $numsegs(i)$ as the max number of segments possible when segment $i$ is included and has the earliest start time of all included segments.

Then your final answer is going to be the maximum of value of $numsegs(i)$ for all possible values of $i$.  Now you need a formula for $numsegs(i)$.

Think about how to calculate $numsegs(0)$, the maximum segment count when you include the first segment.  If we include the first segment, then we can only include other segments that begin after the first segment ends.  So we need to find the index of the first segment that is compatible with segment 0.  We can do this in $O(\log n)$ time with a simple binary search - let that index be $k$.  Now, we can say that $numsegs(0)$ is 1 (for segment 0) plus the maximum of $numsegs(k), numsegs(k+1), \dots, numsegs(n)$.  (There's an edge case to consider as well.  If segment $i$ doesn't have any compatible segments after it, then $numsegs(i)$ is just 1.)

You can compute $numsegs(i)$ in a very similar way.  Note that $numsegs(i)$ depends only on $numsegs$ values greater than $i$.  Therefore we can compute $numsegs(n-1)$ first, then $numsegs(n-2)$, and so on, caching the values as we go, and we'll never have to recalculate any $numsegs$ values.

This solution is actually $O(n^2)$.  To compute $numsegs(i)$, you have to find the maximum among potentially $n-i$ following $numsegs$ values.  How then to get the total runtime down to $O(n \log n)$?

Edit: As a linked solution pointed out, we can compute the maximum quickly using caching.  Suppose we want to know the maximum $numsegs$ value starting from index $k$.  We can just compare $numsegs(k)$ to the maximum starting from $numsegs(k+1)$, which we cached in a previous step.


Source entropy and other questions related to information theory Kolmogorov-Sinai entropy (KS) explains the mathematical concept behind KS entropy.

$$h ( T ) =\sup\limits_{\xi} \, h ( T , \xi )$$

defines the formula for KS where the left-hand side is nothing but the Shannon's entropy. In many papers I have seen that KS is defined as the supremum over source entropy. These conflicting views raises the following questions

What is the difference between Shannon's entropy and source entropy (source entropy given by $\lim \frac{1}{n}\cdot h(T)$ where $n$ is the length of the word or sequence,unsure though).
Would source entropy be the entropy of the raw signal before it has been quantized or should it be that of the quantized?
Is 'n' the length of the data series or the number of quantization levels>
Topological entropy (TS) explains topological entropy whose formula looks exactly as KS. So, what is the difference since KS is also known as metric entropy and not known as Topological entropy?

If you look at wikipedia you see that topological entropy is modeled after Kolmogorov-Sinai (KS) entropy, but it is defined without reference to a probability measure $\mu$ on the space.

For KS entropy, you need to use Shannon entropy: $-\sum_i\mu(X_i) \log \mu(X_i)$ for some partition of the space $\{X_i\}$, which can only be defined if you have some probability measure $\mu$ on your space, while topological entropy is defined without reference to a probability measure.

Since putting different probability measures on the space will give different KS entropies, while not affecting the topological entropy, these entropies are different. However, they are related by the theorem that the topological entropy is the supremum of the Kolmogorov-Sinai entropy over all probability measures $\mu$.


Is there a described algorithm converting _from_ Continuation Passing Style? Continuation Passing Style (CPS) is a form of code where the control is passed explicitly, by passing the continuation of the code at each call point, unlike direct style.

There are many descriptions in the literature for how to convert from direct style to CPS. The following pseudo-JavaScript:

function direct() {
    var a = foo(1);
    return bar(a);
}

becomes:

function cps(cont) {
    foo(1, function(a) {
        bar(a, cont);
    }
}

But are there any descriptions of the reverse transformation, where the CPS representation is taken back to a direct style?

I did some additional research to answer this question but find nothing better suited.

To do reverse of CPS to direct programming you have to assign functions to variables, this makes direct structural code.

Automated and well described technique comes from compilers - SSA (Single Static Assignment).
This has additional bonus like compacting code and constant propagating to some extend.

This is not per se technique to reverse CPS, but structure of assignments creates direct code, so it is usable in your situation.


Proving the (in)tractability of this Nth prime recurrence As follows from my previous question, I've been playing with the Riemann hypothesis as a matter of recreational mathematics. In the process, I've come to a rather interesting recurrence, and I'm curious as to its name, its reductions, and its tractability towards the solvability of the gap between prime numbers.

Tersely speaking, we can define the gap between each prime number as a recurrence of preceding candidate primes. For example, for our base of $p_0 = 2$, the next prime would be:

$\qquad \displaystyle p_1 = \min \{ x > p_0 \mid -\cos(2\pi(x+1)/p_0) + 1 = 0)  \}$

Or, as we see by plotting this out: $p_1 = 3$.

We can repeat the process for $n$ primes by evaluating each candidate prime recurring forward. Suppose we want to get the next prime, $p_2$. Our candidate function becomes:

$\qquad \displaystyle \begin{align}
p_2 = \min\{ x > p_1 \mid f_{p_1}(x) + (&(-\cos(2\pi(x+1)/p_1) + 1) \\
                                   \cdot &(-\cos(2\pi(x+2)/p_1) + 1)) = 0\}
\end{align}$

Where:

$\qquad \displaystyle f_{p_1}(x) = -\cos(2\pi(x+1)/p_0) + 1$, as above.

It's easy to see that each component function only becomes zero on integer values, and it's equally easy to show how this captures our AND- and XOR-shaped relationships cleverly, by exploiting the properties of addition and multiplication in the context of a system of trigonometric equations.

The recurrence becomes:

$\qquad f_{p_0} = 0\\
\qquad p_0 = 2\\
\qquad \displaystyle
  f_{p_n}(x) = f_{p_{n-1}}(x) + \prod_{k=2}^{p_{n-1}} (-\cos(2\pi(x+k-1)/p_{n-1}) + 1)\\
 \qquad \displaystyle
 p_n = \min\left\{ x > p_{n-1} \mid f_{p_n}(x) = 0\right\}$

... where the entire problem hinges on whether we can evaluate the $\min$ operator over this function in polynomial time. This is, in effect, a generalization of the Sieve of Eratosthenes.

Working Python code to demonstrate the recurrence:

from math import cos,pi

def cosProduct(x,p):
    """ Handles the cosine product in a handy single function """
    ret = 1.0
    for k in xrange(2,p+1):
        ret *= -cos(2*pi*(x+k-1)/p)+1.0
    return ret

def nthPrime(n):
    """ Generates the nth prime, where n is a zero-based integer """

    # Preconditions: n must be an integer greater than -1
    if not isinstance(n,int) or n < 0:
        raise ValueError("n must be an integer greater than -1")

    # Base case: the 0th prime is 2, 0th function vacuous
    if n == 0:
        return 2,lambda x: 0

    # Get the preceding evaluation
    p_nMinusOne,fn_nMinusOne = nthPrime(n-1)

    # Define the function for the Nth prime
    fn_n = lambda x: fn_nMinusOne(x) + cosProduct(x,p_nMinusOne)

    # Evaluate it (I need a solver here if it's tractable!)
    for k in xrange(p_nMinusOne+1,int(p_nMinusOne**2.718281828)):
        if fn_n(k) == 0:
            p_n = k
            break

    # Return the Nth prime and its function
    return p_n,fn_n

A quick example:

>>> [nthPrime(i)[0] for i in range(20)]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]

The trouble is, I'm now in way over my head, both mathematically and as a computer scientist. Specifically, I am not competent with Fourier analysis, with defining uniform covers, or with the complex plane in general, and I'm worried that this approach is either flat-out wrong or hides a lurking horror of a 3SAT problem that elevates it to NP-completeness.

Thus, I have three questions here:

  Given my terse recurrence above, is it possible to deterministically compute or estimate the location of the zeroes in polynomial time and space?
  If so or if not, is it hiding any other subproblems that would make a polytime or polyspace solution intractable?
  And if by some miracle (1) and (2) hold up, what dynamic programming improvements would you make in satisfying this recurrence, from a high level? Clearly, iteration over the same integers through multiple functions is inelegant and quite wasteful.

The following paper shows that PRIMES is in P (it also won a Gödel award in 2006):

http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf

By setting the solution of the Nth prime minimization procedure to the AKS PRIMES algorithm (modulo a subtraction), we may effectively get a tractable solution to the recurrence relation (if you can prove that the prime gap is given by the recurrence relation).

Source codes can be found on the internet. I am not pointing to them here because I did not check them personally.

As is however, we may still have the upper bound of $\sqrt{n}$ for checking all numbers...