What is the definition of P, NP, NP-complete and NP-hard? I'm in a course about computing and complexity, and am unable to understand what these terms mean.

All I know is that NP is a subset of NP-complete, which is a subset of NP-hard, but I have no idea what they actually mean. Wikipedia isn't much help either, as the explanations are still a bit too high level.

I think the Wikipedia articles
$\mathsf{P}$, $\mathsf{NP}$, and $\mathsf{P}$ vs. $\mathsf{NP}$ are quite good.
Still here is what I would say: Part I, Part II

[I will use remarks inside brackets to discuss some technical details which
you can skip if you want.]

Part I

Decision Problems

There are various kinds of computational problems.
However in an introduction to computational complexity theory course
it is easier to focus on decision problem,
i.e. problems where the answer is either YES or NO.
There are other kinds of computational problems but
most of the time questions about them can be reduced to
similar questions about decision problems.
Moreover decision problems are very simple.
Therefore in an introduction to computational complexity theory course
we focus our attention to the study of decision problems.

We can identify a decision problem with the subset of inputs that
have answer YES.
This simplifies notation and allows us to write
$x\in Q$ in place of $Q(x)=YES$ and
$x \notin Q$ in place of $Q(x)=NO$.

Another perspective is that
we are talking about membership queries in a set.
Here is an example:

Decision Problem:

  Input: A natural number $x$,
  Question: Is $x$ an even number?

Membership Problem:

  Input: A natural number $x$,
  Question: Is $x$ in $Even = \{0,2,4,6,\cdots\}$?

We refer to the YES answer on an input as accepting the input and
to the NO answer on an input as rejecting the input.

We will look at algorithms for decision problems and
discuss how efficient those algorithms are in their usage of computable resources.
I will rely on your intuition from programming in a language like C
in place of formally defining what we mean by an algorithm and computational resources.

[Remarks:
1. If we wanted to do everything formally and precisely
we would need to fix a model of computation like the standard Turing machine model
to precisely define what we mean by an algorithm and
its usage of computational resources.
2. If we want to talk about computation over objects that
the model cannot directly handle,
we would need to encode them as objects that the machine model can handle,
e.g. if we are using Turing machines
we need to encode objects like natural numbers and graphs
as binary strings.]

$\mathsf{P}$ = Problems with Efficient Algorithms for Finding Solutions

Assume that efficient algorithms means algorithms that
use at most polynomial amount of computational resources.
The main resource we care about is
the worst-case running time of algorithms with respect to the input size,
i.e. the number of basic steps an algorithm takes on an input of size $n$.
The size of an input $x$ is $n$ if it takes $n$-bits of computer memory to store $x$,
in which case we write $|x| = n$.
So by efficient algorithms we mean algorithms that
have polynomial worst-case running time.

The assumption that polynomial-time algorithms capture
the intuitive notion of efficient algorithms is known as Cobham's thesis.
I will not discuss at this point
whether $\mathsf{P}$ is the right model for efficiently solvable problems and
whether $\mathsf{P}$ does or does not capture
what can be computed efficiently in practice and related issues.
For now there are good reasons to make this assumption
so for our purpose we assume this is the case.
If you do not accept Cobham's thesis
it does not make what I write below incorrect,
the only thing we will lose is
the intuition about efficient computation in practice.
I think it is a helpful assumption for someone
who is starting to learn about complexity theory.

  $\mathsf{P}$ is the class of decision problems that can be solved efficiently,
  i.e. decision problems which have polynomial-time algorithms.

More formally, we say a decision problem $Q$ is in $\mathsf{P}$ iff

  there is an efficient algorithm $A$ such that
  for all inputs $x$,

  if $Q(x)=YES$ then $A(x)=YES$,
  if $Q(x)=NO$ then $A(x)=NO$.

I can simply write $A(x)=Q(x)$ but
I write it this way so we can compare it to the definition of $\mathsf{NP}$.

$\mathsf{NP}$ = Problems with Efficient Algorithms for Verifying Proofs/Certificates/Witnesses

Sometimes we do not know any efficient way of finding the answer to a decision problem,
however if someone tells us the answer and gives us a proof
we can efficiently verify that the answer is correct
by checking the proof to see if it is a valid proof.
This is the idea behind the complexity class $\mathsf{NP}$.

If the proof is too long it is not really useful,
it can take too long to just read the proof
let alone check if it is valid.
We want the time required for verification to be reasonable
in the size of the original input,
not the size of the given proof!
This means what we really want is not arbitrary long proofs but short proofs.
Note that if the verifier's running time is polynomial
in the size of the original input
then it can only read a polynomial part of the proof.
So by short we mean of polynomial size.

Form this point on whenever I use the word "proof" I mean "short proof".

Here is an example of a problem which
we do not know how to solve efficiently but
we can efficiently verify proofs:

  Partition
  Input: a finite set of natural numbers $S$,
  Question: is it possible to partition $S$ into two sets $A$ and $B$
  ($A \cup B = S$ and $A \cap B = \emptyset$)
  such that the sum of the numbers in $A$ is equal to the sum of number in $B$ ($\sum_{x\in A}x=\sum_{x\in B}x$)?

If I give you $S$ and
ask you if we can partition it into two sets such that
their sums are equal,
you do not know any efficient algorithm to solve it.
You will probably try all possible ways of
partitioning the numbers into two sets
until you find a partition where the sums are equal or
until you have tried all possible partitions and none has worked.
If any of them worked you would say YES, otherwise you would say NO.

But there are exponentially many possible partitions so
it will take a lot of time.
However if I give you two sets $A$ and $B$,
you can easily check if the sums are equal and
if $A$ and $B$ is a partition of $S$.
Note that we can compute sums efficiently.

Here the pair of $A$ and $B$ that I give you is a proof for a YES answer.
You can efficiently verify my claim by looking at my proof and
checking if it is a valid proof.
If the answer is YES then there is a valid proof, and
I can give it to you and you can verify it efficiently.
If the answer is NO then there is no valid proof.
So whatever I give you you can check and see it is not a valid proof.
I cannot trick you by an invalid proof that the answer is YES.
Recall that if the proof is too big
it will take a lot of time to verify it,
we do not want this to happen,
so we only care about efficient proofs,
i.e. proofs which have polynomial size.

Sometimes people use "certificate" or "witness" in place of "proof".

Note I am giving you enough information about the answer for a given input $x$
so that you can find and verify the answer efficiently.
For example, in our partition example
I do not tell you the answer,
I just give you a partition,
and you can check if it is valid or not.
Note that you have to verify the answer yourself,
you cannot trust me about what I say.
Moreover you can only check the correctness of my proof.
If my proof is valid it means the answer is YES.
But if my proof is invalid it does not mean the answer is NO.
You have seen that one proof was invalid,
not that there are no valid proofs.
We are talking about proofs for YES.
We are not talking about proofs for NO.

Let us look at an example:
$A=\{2,4\}$ and $B=\{1,5\}$ is a proof that
$S=\{1,2,4,5\}$ can be partitioned into two sets with equal sums.
We just need to sum up the numbers in $A$ and the numbers in $B$ and
see if the results are equal, and check if $A$, $B$ is partition of $S$.

If I gave you $A=\{2,5\}$ and $B=\{1,4\}$,
you will check and see that my proof is invalid.
It does not mean the answer is NO,
it just means that this particular proof was invalid.
Your task here is not to find the answer,
but only to check if the proof you are given is valid.

It is like a student solving a question in an exam and
a professor checking if the answer is correct. :)
(unfortunately often students do not give enough information
to verify the correctness of their answer and
the professors have to guess the rest of their partial answer and
decide how much mark they should give to the students for their partial answers,
indeed a quite difficult task).

The amazing thing is that
the same situation applies to many other natural problems that we want to solve:
we can efficiently verify if a given short proof is valid,
but we do not know any efficient way of finding the answer.
This is the motivation why
the complexity class $\mathsf{NP}$ is extremely interesting
(though this was not the original motivation for defining it).
Whatever you do
(not just in CS, but also in
math, biology, physics, chemistry, economics, management, sociology, business,
 ...)
you will face computational problems that fall in this class.
To get an idea of how many problems turn out to be in $\mathsf{NP}$ check out
a compendium of NP optimization problems.
Indeed you will have hard time finding natural problems
which are not in $\mathsf{NP}$.
It is simply amazing.

  $\mathsf{NP}$ is the class of problems which have efficient verifiers,
  i.e.
  there is a polynomial time algorithm that can verify
  if a given solution is correct.

More formally, we say a decision problem $Q$ is in $\mathsf{NP}$ iff

  there is an efficient algorithm $V$ called verifier such that
  for all inputs $x$,

  if $Q(x)=YES$ then there is a proof $y$ such that $V(x,y)=YES$,
  if $Q(x)=NO$ then for all proofs $y$, $V(x,y)=NO$.

We say a verifier is sound
if it does not accept any proof when the answer is NO.
In other words, a sound verifier cannot be tricked
to accept a proof if the answer is really NO.
No false positives.

Similarly, we say a verifier is complete
if it accepts at least one proof when the answer is YES.
In other words, a complete verifier can be convinced of the answer being YES.

The terminology comes from logic and proof systems.
We cannot use a sound proof system to prove any false statements.
We can use a complete proof system to prove all true statements.

The verifier $V$ gets two inputs,

$x$ : the original input for $Q$, and
$y$ : a suggested proof for $Q(x)=YES$.

Note that we want $V$ to be efficient in the size of $x$.
If $y$ is a big proof
the verifier will be able to read only a polynomial part of $y$.
That is why we require the proofs to be short.
If $y$ is short saying that $V$ is efficient in $x$
is the same as saying that $V$ is efficient in $x$ and $y$
(because the size of $y$ is bounded by a fixed polynomial in the size of $x$).

In summary, to show that a decision problem $Q$ is in $\mathsf{NP}$
we have to give an efficient verifier algorithm
which is sound and complete.

Historical Note:
historically this is not the original definition of $\mathsf{NP}$.
The original definition uses what is called non-deterministic Turing machines.
These machines do not correspond to any actual machine model and
are difficult to get used to
(at least when you are starting to learn about complexity theory).
I have read that many experts think that
they would have used the verifier definition as the main definition and
even would have named the class $\mathsf{VP}$
(for verifiable in polynomial-time) in place of $\mathsf{NP}$
if they go back to the dawn of the computational complexity theory.
The verifier definition is more natural,
easier to understand conceptually, and
easier to use to show problems are in $\mathsf{NP}$.

$\mathsf{P}\subseteq \mathsf{NP}$

Therefore we have
$\mathsf{P}$=efficient solvable and $\mathsf{NP}$=efficiently verifiable.
So $\mathsf{P}=\mathsf{NP}$ iff
the problems that can be efficiently verified are
the same as the problems that can be efficiently solved.

Note that any problem in $\mathsf{P}$ is also in $\mathsf{NP}$,
i.e. if you can solve the problem
you can also verify if a given proof is correct:
the verifier will just ignore the proof!

That is because we do not need it,
the verifier can compute the answer by itself,
it can decide if the answer is YES or NO without any help.
If the answer is NO we know there should be no proofs and
our verifier will just reject every suggested proof.
If the answer is YES, there should be a proof, and
in fact we will just accept anything as a proof.

[We could have made our verifier accept only some of them,
that is also fine,
as long as our verifier accept at least one proof
the verifier works correctly for the problem.]

Here is an example:

  Sum
  Input: a list of $n+1$ natural numbers $a_1,\cdots,a_n$, and $s$,
  Question: is $\Sigma_{i=1}^n a_i = s$?

The problem is in $\mathsf{P}$ because
we can sum up the numbers and then compare it with $s$,
we return YES if they are equal, and NO if they are not.

The problem is also in $\mathsf{NP}$.
Consider a verifier $V$ that gets a proof plus the input for Sum.
It acts the same way as the algorithm in $\mathsf{P}$ that we described above.
This is an efficient verifier for Sum.

Note that there are other efficient verifiers for Sum, and
some of them might use the proof given to them.
However the one we designed does not and that is also fine.
Since we gave an efficient verifier for Sum the problem is in $\mathsf{NP}$.
The same trick works for all other problems in $\mathsf{P}$ so
$\mathsf{P} \subseteq \mathsf{NP}$.

Brute-Force/Exhaustive-Search Algorithms for $\mathsf{NP}$ and $\mathsf{NP}\subseteq \mathsf{ExpTime}$

The best algorithms we know of for solving an arbitrary problem in $\mathsf{NP}$ are
brute-force/exhaustive-search algorithms.
Pick an efficient verifier for the problem
(it has an efficient verifier by our assumption that it is in $\mathsf{NP}$) and
check all possible proofs one by one.
If the verifier accepts one of them then the answer is YES.
Otherwise the answer is NO.

In our partition example,
we try all possible partitions and
check if the sums are equal in any of them.

Note that the brute-force algorithm runs in worst-case exponential time.
The size of the proofs is polynomial in the size of input.
If the size of the proofs is $m$ then there are $2^m$ possible proofs.
Checking each of them will take polynomial time by the verifier.
So in total the brute-force algorithm takes exponential time.

This shows that any $\mathsf{NP}$ problem
can be solved in exponential time, i.e.
$\mathsf{NP}\subseteq \mathsf{ExpTime}$.
(Moreover the brute-force algorithm will use
only a polynomial amount of space, i.e.
$\mathsf{NP}\subseteq \mathsf{PSpace}$
but that is a story for another day).

A problem in $\mathsf{NP}$ can have much faster algorithms,
for example any problem in $\mathsf{P}$ has a polynomial-time algorithm.
However for an arbitrary problem in $\mathsf{NP}$
we do not know algorithms that can do much better.
In other words, if you just tell me that
your problem is in $\mathsf{NP}$
(and nothing else about the problem)
then the fastest algorithm that
we know of for solving it takes exponential time.

However it does not mean that there are not any better algorithms,
we do not know that.
As far as we know it is still possible
(though thought to be very unlikely by almost all complexity theorists) that
$\mathsf{NP}=\mathsf{P}$ and
all $\mathsf{NP}$ problems can be solved in polynomial time.

Furthermore, some experts conjecture that
we cannot do much better, i.e.
there are problems in $\mathsf{NP}$ that
cannot be solved much more efficiently than brute-force search algorithms
which take exponential amount of time.
See the Exponential Time Hypothesis
for more information.
But this is not proven, it is only a conjecture.
It just shows how far we are from
finding polynomial time algorithms for arbitrary $\mathsf{NP}$ problems.

This association with exponential time confuses some people:
they think incorrectly that
$\mathsf{NP}$ problems require exponential-time to solve
(or even worse there are no algorithm for them at all).
Stating that a problem is in $\mathsf{NP}$
does not mean a problem is difficult to solve,
it just means that it is easy to verify,
it is an upper bound on the difficulty of solving the problem, and
many $\mathsf{NP}$ problems are easy to solve since $\mathsf{P}\subseteq\mathsf{NP}$.

Nevertheless, there are $\mathsf{NP}$ problems which seem to be
hard to solve.
I will return to this in when we discuss $\mathsf{NP}$-hardness.

Lower Bounds Seem Difficult to Prove

OK, so we now know that there are
many natural problems that are in $\mathsf{NP}$ and
we do not know any efficient way of solving them and
we suspect that they really require exponential time to solve.
Can we prove this?

Unfortunately the task of proving lower bounds is very difficult.
We cannot even prove that these problems require more than linear time!
Let alone requiring exponential time.

Proving linear-time lower bounds is rather easy:
the algorithm needs to read the input after all.
Proving super-linear lower bounds is a completely different story.
We can prove super-linear lower bounds
with more restrictions about the kind of algorithms we are considering,
e.g. sorting algorithms using comparison,
but we do not know lower-bounds without those restrictions.

To prove an upper bound for a problem
we just need to design a good enough algorithm.
It often needs knowledge, creative thinking, and
even ingenuity to come up with such an algorithm.

However the task is considerably simpler compared to proving a lower bound.
We have to show that there are no good algorithms.
Not that we do not know of any good enough algorithms right now, but
that there does not exist any good algorithms,
that no one will ever come up with a good algorithm.
Think about it for a minute if you have not before,
how can we show such an impossibility result?

This is another place where people get confused.
Here "impossibility" is a mathematical impossibility, i.e.
it is not a short coming on our part that
some genius can fix in future.
When we say impossible
we mean it is absolutely impossible,
as impossible as $1=0$.
No scientific advance can make it possible.
That is what we are doing when we are proving lower bounds.

To prove a lower bound, i.e.
to show that a problem requires some amount of time to solve,
means that we have to prove that any algorithm,
even very ingenuous ones that do not know yet,
cannot solve the problem faster.
There are many intelligent ideas that we know of
(greedy, matching, dynamic programming, linear programming, semidefinite programming, sum-of-squares programming, and
many other intelligent ideas) and
there are many many more that we do not know of yet.
Ruling out one algorithm or one particular idea of designing algorithms
is not sufficient,
we need to rule out all of them,
even those we do not know about yet,
even those may not ever know about!
And one can combine all of these in an algorithm,
so we need to rule out their combinations also.
There has been some progress towards showing that
some ideas cannot solve difficult $\mathsf{NP}$ problems,
e.g. greedy and its extensions cannot work,
and there are some work related to dynamic programming algorithms,
and there are some work on particular ways of using linear programming.
But these are not even close to ruling out the intelligent ideas that
we know of
(search for lower-bounds in restricted models of computation
if you are interested).

Barriers: Lower Bounds Are Difficult to Prove

On the other hand we have mathematical results called
barriers
that say that a lower-bound proof cannot be such and such,
and such and such almost covers all techniques that
we have used to prove lower bounds!
In fact many researchers gave up working on proving lower bounds after
Alexander Razbarov and Steven Rudich's
natural proofs barrier result.
It turns out that the existence of particular kind of lower-bound proofs
would imply the insecurity of cryptographic pseudorandom number generators and
many other cryptographic tools.

I say almost because
in recent years there has been some progress mainly by Ryan Williams
that has been able to intelligently circumvent the barrier results,
still the results so far are for very weak models of computation and
quite far from ruling out general polynomial-time algorithms.

But I am diverging.
The main point I wanted to make was that
proving lower bounds is difficult and
we do not have strong lower bounds for general algorithms
solving $\mathsf{NP}$ problems.

[On the other hand,
Ryan Williams' work shows that
there are close connections between proving lower bounds and proving upper bounds.
See his talk at ICM 2014 if you are interested.]

Reductions: Solving a Problem Using Another Problem as a Subroutine/Oracle/Black Box

The idea of a reduction is very simple:
to solve a problem, use an algorithm for another problem.

Here is simple example:
assume we want to compute the sum of a list of $n$ natural numbers and
we have an algorithm $Sum$ that returns the sum of two given numbers.
Can we use $Sum$ to add up the numbers in the list?
Of course!

Problem:

  Input: a list of $n$ natural numbers $x_1,\ldots,x_n$,
  Output: return $\sum_{i=1}^{n} x_i$.

Reduction Algorithm:

  $s = 0$
  for $i$ from $1$ to $n$
  2.1.  $s = Sum(s,x_i)$
  return $s$

Here we are using $Sum$ in our algorithm as a subroutine.
Note that we do not care about how $Sum$ works,
it acts like black box for us,
we do not care what is going on inside $Sum$.
We often refer to the subroutine $Sum$ as oracle.
It is like the oracle of Delphi in Greek mythology,
we ask questions and the oracle answers them and
we use the answers.

This is essentially what a reduction is:
assume that we have algorithm for a problem and
use it as an oracle to solve another problem.
Here efficient means efficient assuming that
the oracle answers in a unit of time, i.e.
we count each execution of the oracle a single step.

If the oracle returns a large answer
we need to read it and
that can take some time,
so we should count the time it takes us to read the answer that
oracle has given to us.
Similarly for writing/asking the question from the oracle.
But oracle works instantly, i.e.
as soon as we ask the question from the oracle
the oracle writes the answer for us in a single unit of time.
All the work that oracle does is counted a single step,
but this excludes the time it takes us to
write the question and read the answer.

Because we do not care how oracle works but only about the answers it returns
we can make a simplification and consider the oracle to be
the problem itself in place of an algorithm for it.
In other words,
we do not care if the oracle is not an algorithm,
we do not care how oracles comes up with its replies.

For example,
$Sum$ in the question above is the addition function itself
(not an algorithm for computing addition).

We can ask multiple questions from an oracle, and
the questions does not need to be predetermined:
we can ask a question and
based on the answer that oracle returns
we perform some computations by ourselves and then
ask another question based on the answer we got for the previous question.

Another way of looking at this is
thinking about it as an interactive computation.
Interactive computation in itself is large topic so
I will not get into it here, but
I think mentioning this perspective of reductions can be helpful.

An algorithm $A$ that uses a oracle/black box $O$ is usually denoted as $A^O$.

The reduction we discussed above is the most general form of a reduction and
is known as black-box reduction
(a.k.a. oracle reduction, Turing reduction).

More formally:

  We say that problem $Q$ is black-box reducible to problem $O$ and
  write $Q \leq_T O$ iff
  there is an algorithm $A$ such that for all inputs $x$,
  $Q(x) = A^O(x)$.

In other words if there is an algorithm $A$ which
uses the oracle $O$ as a subroutine and solves problem $Q$.

If our reduction algorithm $A$ runs in polynomial time
we call it a polynomial-time black-box reduction or
simply a Cook reduction
(in honor of
Stephen A. Cook) and
write $Q\leq^\mathsf{P}_T O$.
(The subscript $T$ stands for "Turing" in the honor of
Alan Turing).

However we may want to put some restrictions
on the way the reduction algorithm interacts with the oracle.
There are several restrictions that are studied but
the most useful restriction is the one called many-one reductions
(a.k.a. mapping reductions).

The idea here is that on a given input $x$,
we perform some polynomial-time computation and generate a $y$
that is an instance of the problem the oracle solves.
We then ask the oracle and return the answer it returns to us.
We are allowed to ask a single question from the oracle and
the oracle's answers is what will be returned.

More formally,

  We say that problem $Q$ is many-one reducible to problem $O$ and
  write $Q \leq_m O$ iff
  there is an algorithm $A$ such that for all inputs $x$,
  $Q(x) = O(A(x))$.

When the reduction algorithm is polynomial time we call it
polynomial-time many-one reduction or
simply Karp reduction (in honor of
Richard M. Karp) and
denote it by $Q \leq_m^\mathsf{P} O$.

The main reason for the interest in
this particular non-interactive reduction is that
it preserves $\mathsf{NP}$ problems:
if there is a polynomial-time many-one reduction from
a problem $A$ to an $\mathsf{NP}$ problem $B$,
then $A$ is also in $\mathsf{NP}$.

The simple notion of reduction is
one of the most fundamental notions in complexity theory
along with $\mathsf{P}$, $\mathsf{NP}$, and $\mathsf{NP}$-complete
(which we will discuss below).

The post has become too long and exceeds the limit of an answer (30000 characters).
I will continue the answer in Part II.

P, NP, NP-complete and NP-hard are complexity classes, classifying problems according to the algorithmic complexity for solving them. In short, they're based on three properties:

Solvable in polynomial time: Defines decision problems that can be solved by a deterministic Turing machine (DTM) using a polynomial amount of computation time, i.e., its running time is upper bounded by a polynomial expression in the size of the input for the algorithm. Using Big-O notation this time complexity is defined as O(n ^ k), where n is the size of the input and k a constant coefficient.

Solution verifiable in polynomial time: Defines decision problems for which a given solution can be verified by a DTM using a polynomial amount of computation time, even though obtaining the correct solution may require higher amounts of time.

Reduces any NP problem in polynomial time: Defines decision problems whose algorithms for solving them can be used to solve any NP problem after a polynomial time translation step.

I've recently written an article about this subject providing more details, including a code demonstration for reducing an NP problem into an NP-hard problem: Complexity classes of problems


Why can't we flip the answer of a NDTM efficiently? I read several times that it is not possible to flip the answer of a NDTM efficiently. However, I don’t understand why. For instance, given a NDTM $M$ that runs in $O(n)$, this text (section 3.3) states that it is unclear how another NDTM $T$ can determine in $O(n^{100})$ time how to flip $M$’s answer.

My Problem is as follows: A NDTM outputs $1$ iff there exists a sequence of non-deterministic choices that leads to the accepting state. Furthermore, there exists a universal NDTM $NU$ that can simulate every NDTM with only a small (logarithmic) overhead. So why can’t we construct T as follows: First, simulate M with the universal NDTM which should be possible in time $O(n\log n)$. Then output 1 – M’s answer. This would mean that we can flip the answer of any linear NDTM in time $O(n\log n)$.

A nondeterministic Turing machine accepts if at least one path accepts; it only rejects if all paths reject. This asymmetry makes it hard to "flip answers".

For example, suppose you have a nondeterministic Turing machine $M$ that has two paths for input $w$: one accepts, the other rejects. $M$ has at least one accepting path for $w$, so it accepts. Suppose we want to produce a machine that accepts exactly the inputs that $M$ rejects.  The obvious first attempt is to take $M$ and make its accepting states reject, and its rejecting states accept. $M$ has one accepting path for $w$ and one rejecting path; this new machine $M'$ has one rejecting path and one accepting path. So it still accepts $w$, which it was supposed to reject!

A nondeterministic machine can't look at all its paths simultaneously and take action based on what all of those paths do. If you like, you can think of it as a form of parallelism where the threads are forbidden to communicate with each other. When all of the threads have finished the program must ask itself the following question: "Did at least one of my threads accept?" If the answer is yes, it is legally obliged to accept; if the answer is no, it is legally obliged to reject. It cannot do anything else.

When you simulate a nondeterministic machine $M$ using another one, $M'$, each path of $M'$ simulates one path of $M$ and sees only that path. It can't say, "If all those other paths rejected, I'll accept" because it can't see the other paths; it can only see itself. So all it could possibly say is things like, "If the path I simulated accepted, I'll reject" or "If the path I simulated accepted, I'll accept too". Then, at the end of the computation, the machine has to say, "If any of my paths accepted, I'll accept too", leading to the problem I described above. To invert the behaviour of $M$, each path of $M'$ needs to say, "If the path I simulated accepted, I reject; else, I accept" and, at the end of the computation, the machine needs to say, "If all of my paths accepted, I accept; else, I reject."  This is because, if all of the simulator's paths accepted, that means all of $M$'s paths rejected, so $M$ rejected, so the simulator needs to accept. But the simulator isn't a valid nondeterministic Turing machine because it isn't using the legally mandated acceptance criterion. It can't do that.

The only way we know to figure out if a nondeterministic machine rejects its input is to try every possible path and verify that they all reject.  After all, if even one of them accepted, the machine would accept the input.  But trying every possible path is exponentially slower than trying just one.

actually technically you are asking the P$\stackrel{?}{=}$coNP($\stackrel{?}{=}$NP) question which is open. it is widely conjectured but not proven that they are not equal. the other answers are intuitive sketches/circumstantial evidence why they are not equal.


How to get all in constant time? We are planning to design a system where following operations are supported.

Increment("foo"): Increase the count of key 'foo'

Decrement("bar"): Decrease the count of key 'bar'

getMin():  Return the key which has minimum count

getMax():  Return the key which has maximum count

The catch is all operations should be in $O(1)$ time.

If your keys are strings, you can use a prefix tree mapping keys to values. In this way each operation can be implemented in $O(h)$ time, where $h$ is the length of the key, which means it is $O(1)$ to the size of the collection.
To get the minimum key(or maximum) you can traverse the tree, by going through the edge from the lexicographically smallest (or largest if you need max) node on each level.
 I don't think you can get better complexity than $O(h)$ for arbitrary sized keys as you need $O(h)$ time to output the key anyway.


Programming Language Hierarchy I know that Assembly is the lowest level of the stack besides machine code, but are the languages above it all considered "high level languages" or is there a hierarchy amongst these languages. For instance, are C++, Ruby, and Python all "high level languages"?

There are supposedly generations of languages. According to Wikipedia:

First generation: Machine language.

Second generation: Low-level programming languages such as assembly language.

Third generation: Structured high-level programming languages such as C, COBOL and FORTRAN.

Fourth generation: Domain-specific high-level programming languages such as SQL (for database access) and TeX (for text formatting)

The fifth generation was supposed to be developed by Japan's fifth generation project in the 1980s but didn't really go anywhere. Some people consider constraint-based languages to be fifth generation (Wikipedia).

There is also a supposed hierarchy of language power, expressed by Paul Graham as the "Blub Paradox" in his essay Beating the Averages. In this controversial approach, languages such as Basic and Cobol are low in the hierarchy, Python and Perl would be in the middle, and Lisp would be at the top.

This picture shows the hierarchy:
Machine Language is the lowest. It is the most understandable by computer.
High level language is the highest. It is the most understandable by human so far.


Effectiveness of TLB This is a book question:

  Suppose that a machine has 48-bit virtual addresses and 32-bit
  physical addresses.

  Suppose this same system has a TLB (Translation Lookaside Buffer) with
  32 entries. Furthermore, suppose that a program contains instructions
  that fit into one page and it sequentially reads long integer elements
  from an array that spans thousands of pages. How effective will the
  TLB be for this case?

Answer: I think that we cannot know the effectiveness of the TLB because we do not know the number of instructions the program has. I hope I make sense.

source:
Modern Operating Systems
Question 15, chapter 3
ISBN-13: 978-0-13-359162-0

Assuming size of long is $32$ bits, each page frame in physical memory exactly contain $1$ long number, therefore in $TLB$ at particular instance of time $31$ long integers would be present. Hence, $1$ page fault in every $32$ memory accesses. Now, I am not sure what is criteria of effectiveness here. But $1$ per $32$ memory access seems pretty good.


Quick and space-efficient way to find whether two sets intersect I hope you can help me -

Given a lot of sets containing integers,
I'd like for any two sets, to quickly (i.e. O(1)) ask whether they intersect.
Note that I don't need the exact intersection, rather just a yes/no answer.
Also, I am fine with some false-positives.
Also, the representation of the sets should be space-efficient (i.e. less than the set-size).

Ideally, I'd also like to (infrequently) update the sets.

My requirements make me think of Bloom Filters, which 1)represent sets efficiently, 2)allow O(1) containment-test and 3) have some false-positives. Unfortunately it they don't apply to two-set-intersection.

Any ideas? Thanks!

(Just FYI, the sets are subsets of ids of adjacent edges from a huge graph)

Build a $k \times k$ table $ans$ of answers, storing in each entry the smallest (according to some total order) element in that intersection or a sentinel value (e.g. -1) if the intersection is empty, and also maintain a mapping from each element to the set of all sets that contains it (e.g. using a hashtable of hashtables).

When you add an element $x$ to a set $i$, you can efficiently find all other sets $j$ for which $ans[i][j]$ might need to change, and the change itself is also simple: set $ans[i][j] = \min(ans[i][j], x)$.  Removing an element will also be efficient, except in the rare case when you remove that minimum shared element, which requires fully recomputing (just) $ans[i][j]$.

You might want to try Dynamic Partition Bloom Filters.


What are some efficient ways to find the differences between two large corpuses of text that have similar, but differently ordered content? I have two large files containing paragraphs of English text:

The first text is about 200 pages long and has about 10 paragraphs per page (each paragraph is 5 sentences long).
The second text contains almost precisely the same paragraphs and text as the first. It is also 200 pages long with 10 paragraphs per page. However, the paragraphs are randomized and in a different order when compared to the first text. Also, a large percentage of the paragraphs have small changes in wording compared to similar paragraphs. For example, a paragraph in the first text might have a sentence like Like Jimmy, I wanted to go to the palace while the corresponding sentence in the paragraph of the second text would read Like Jimmy, I really wanted to go to the castle.

I want to be able to capture the changes here like the addition of really and the deletion of palace with replacement of castle. If the paragraphs were roughly aligned, then this would be pretty trivial as there are plenty of ways to diff text. However, since the paragraphs aren't aligned, that isn't the case.

If the files were small (handful of paragraphs), Levenshtein Distance probably would work fine, but because the files are huge, it would be inefficient to compare each paragraph of text 1 to each paragraph of text 2 to find out which paragraphs match.

What would be some other approaches to this problem to handle it efficiently?

Comparing 2000 paragraphs to 2000 paragraphs is only four million comparisons.

The key to the problem is not to use a function that computes the Levenshtein distance but to use one that computes the Levenshtein distance if the distance is less than a certain threshold, and fails (or, rather, returns +∞) if the distance is greater than the threshold.

This is because you are only interested in closely similar paragraphs. You have no interest at all in the precise distance between paragraphs that are different enough to be unrelated. So as soon as a distance has got high enough to be uninteresting, the function can exit at once; and this will mostly happen very early on indeed during the execution of the function.

The higher the threshold, the longer the running time but the smaller the proportion of false negatives.

If you know something more about the documents (such as that each paragraph matches at most one paragraph in the other document) then you could make one pass with a low threshold, exclude the matched paragraphs from further consideration, make one pass over your now reduced corpus with a higher threshold, exclude those reduced paragraphs, and so on.

Implementation detail: Presumably you would be calculating a Levenshtein distance on words rather than on characters. If that is the case, you should first assign a number to each word - for example, by sorting the entire corpus, calling the first word '1', the second word '2', and so on. That way your paragraph comparisons would be done by comparing numbers rather than words, which is faster.

It might be possible to use a compound approach. Perhaps someone can build on this...

Hash the contents of the paragraph in such a way that paragraphs with only slight differences have similar hashes, then order the hashes to determine which paragraphs to compare via a more exact method (diff or something similar).

For example, as a rudimentary hash algorithm, what if you added up the ascii values of the characters and then modulo the sum by a large number like 2,000,000,000? This would cause 2 paragraphs with only a few added or subtracted words to have hash values that are likely closer together than paragraphs with very different words, and thus, they will be much closer together on the list than the very different paragraphs (you might say nearby hashes in this case are necessary but not sufficient for similar paragraphs). Obviously you have to account for the wrap-around caused by modulo and consider a paragraph with the hash value 1,999,999,999 as only being a distance of 1 from one with a has value of 0, etc.

As a result, could reduce the number of comparisons between paragraphs that you need to perform by a substantial amount (you wouldn't have to compare each paragraph in one text to every paragraph in the other text) -- you could compare a paragraph to paragraphs in text 2 in order of how close their hashes are (do the closest hash-valued ones first) and invoke a more expensive algorithm here to determine if they're "similar enough" to be considered the same.


What is the best solution to find whether the sum of an array is even or odd I was asked this question in an interview. I was not able to find a better solution than $O(n)$ which is just going over the array and finding the sum. Can it be done any better? I am not really interested in the actual sum, I just want to know whether it's even or odd.

Or how do I prove that it cannot be done better than $O(n)$?

By a simple "adversary argument", you have to check each element (in some way): Suppose you have missed some element $x$ and get an answer "The sum is even": the adversary can modify $x$ (if it's odd, make it even; if it's even, make it odd), which will change the correct result but not your computation.

The adversary argument tells that in theory you have to check each element. By the way, it does not mean you have to sum them up. You can simply count the numbers of even numbers and odd numbers (or go through the array by +1 for even and -1 for odd).

If you have a usual computer using two's complement arithmetic, just add all the numbers.  While you are only interested in the lowest significant bit of the result, the effort of masking out anything else is not going to be worth the trouble.

In theory, you can save time by just fetching and adding (or xoring, which is equivalent for the lowest significant bit) the lowest significant byte of each number.  In practice, the memory interface and cache lines will deliver all of them anyway.

Any input number can change the result or not, so you don't get around accessing any element anyway.

In short: this is one task where the simplest brute-force solution cannot be beat.  At least while we are talking about a single CPU.


How does RAID-5 algorithm locate the right device? Please consider the following diagram of a RAID-5 array (Ignore the gray background):

Now, given a logical address, how can one return the device number (0-3)?

For example, DeviceByLogicalSector(50) = 0, DeviceByLogicalSector(31)=2.

I've need to implement DeviceByLogicalSector method. I can use space if that's required.

Now, I've noticed the following:
Let's observe only the first $4$ rows; If we have a sector which is above the $P$-diagonal then the formula is: $\frac{(\text{logical_addr} \mod 12)}{4}$. And if the sector is below the diagonal then we need to add $1$.

Thanks

Extracted from: HERE

// Assume all indexes are zero-based.
// Algorithm = Left-Asym

ChunkIndex = LogicalSector / SectorsPerChunk
StripeIndex = ChunkIndex / (DiskCount - 1)

ParityDisk = (DiskCount - 1) - ((StripeIndex / ParityDelay) % DiskCount)

DataDisk = (LogicalSector % (SectorsPerChunk * (DiskCount - 1))) / SectorsPerChunk
If ParityDisk <= DataDisk:
    DataDisk = DataDisk + 1

PhysicalSector = (LogicalSector / SectorsPerChunk) * (DiskCount - 1)
PhysicalSector = PhysicalSector * SectorsPerChunk
PhysicalSector = PhysicalSector + (LogicalSector % SectorsPerChunk)


Why DCFL is not closed under kleene star? I have read somewhere that DCFL is not closed under kleene star. but I haven't found any example

The language $\{a^nb^nc^k \mid n,k \ge 1\} \cup \{a^nb^kc^n \mid n,k \ge 1\}$ I believe is a standard example of a non-deterministic context-free language. At least intuitively it is clear that we can push the $a$'s, but we do not know when to pop (compare with $b$'s or with $c$'s?)

The language $L = \{ a^nb^nc^k \mid n,k \ge 1\} \cup \{d\;a^nb^kc^n \mid n,k \ge 1\}$ however, is deterministic. The $d$ prefix gives away which part we are in.

Now consider $(\{d\} \cup L)^*$.

proving kleene closure of DCFL is not DCFL


Compute square root using (bit) additions and shifts as primitives Question: Given an $n$-bit natural number $N$, how to compute $\lceil \sqrt{N} \rceil$ using only $O(n)$ (bit) additions and shifts?

The tip is to use binary search. However, I could not achieve the required complexity (I got $O(n^2)$).

What does it mean by using only $O(n)$ (bit) additions and shifts:

This is an exercise in an algorithm book.
In my opinion, it means that adding two, say $n$-bit, natural numbers costs $O(1)$ and shifting a, say $n$-bit, natural number also costs $O(1)$. Then we are only allowed to use such $O(1)$ operations $O(n)$ times.
It does not mention the cost of comparison. I guess we can ignore it or assume that comparing two, say $n$-bit, natural numbers costs $O(1)$ as well.

My $O(n^2)$ algorithm:

Determine the range of the number of bits $t$ of $\lceil \sqrt{N} \rceil$:
      $$2^{\frac{n-1}{2}} \le \sqrt{N} \le 2^{\frac{n}{2}} \Rightarrow 2^{\lfloor \frac{n-1}{2} \rfloor} \le \lceil \sqrt{N} \rceil \le 2^{\lceil \frac{n}{2} \rceil}$$
Therefore,
$$t_1 \triangleq \lfloor \frac{n-1}{2} \rfloor + 1 \le t \le \lceil \frac{n}{2} \rceil + 1 \triangleq t_2.$$
Binary search:
Find $\lceil \sqrt{N} \rceil$ between $2^{t_1}$ and $2^{t_2}$ using binary search. For each number $x$, to compute $x^2$ using additions and shifts as primitives and compare it with $N$.

The complexity is thus $O(n \times n) = O(n^2)$ for $O(n)$ times of binary search and computing $x^2$, each of which in turn takes $O(n)$ additions and shifts.

An iterative algorithm seems like it should work.

Let $M=\lfloor N/4 \rfloor$.  Suppose we know that $x$ is the integer approximation to $\sqrt{M}$, i.e., $x=\lceil \sqrt{M} \rceil$, and suppose we know the value of $x^2$ (obtained previously).

Now we want to find $y=\lceil \sqrt{N} \rceil$.  What are the possible values of $y$?  I'm pretty sure the only possible values are $y=2x$ or $y=2x+1$.   And, it's easy to try both of them and see which is correct.  In particular, for $y=2x$, we have $y^2=4x^2$, which can be obtained from $x^2$ by two left-shifts ($O(1)$ time); for $y=2x+1$, we have $y^2=4x^2+4x+1$, which can be obtained from $x^2$ and $x$ with four left-shifts and two additions ($O(1)$ time).  Now just compare those two values to $N$ to see which one is correct.

In this way, we get an iterative algorithm where we do $n/2$ iterations, and where each iteration takes $O(1)$ time.  The total running time is $O(n)$, as required.

I realize this didn't use binary search.  Oh well.

I like Alan Campbell's answer: with careful tracking of previous guesses, the new subtraction is easy each time, and the binary shift-and-add square root is about as fast as a binary shift-and-add divide.

But it may be possible to go faster, by instead of making your next guess a single binary digit, instead using an "A-b" x "A-b" algorithm, and making your next guess the average of your previous guess, and the original number divided by the previous guess.  That sounds like it would take longer, not shorter.  However, the division doesn't have to be exact.  So if the division only runs to the square root of the number of digits remaining to find, then you might actually save time.  Moreover, if for your division you use the french method, of shorthand division, then you might actually break some speed in your calculation for really big divides.

Now, if we add in calculations in parallel that yield preliminary correctable results before the answer is found...  then we might be onto something.


How can it be decidable whether $\pi$ has some sequence of digits? We were given the following exercise.

  Let

  $\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}$

  Prove that $f$ is computable.

How is this possible? As far as I know, we do not know wether $\pi$ contains every sequence of digits (or which) and an algorithm can certainly not decide that some sequence is not occurring. Therefore I think $f$ is not computable, because the underlying problem is only semi-decidable.

There are only two possibilities to consider.

For every positive integer $n$, the string $0^n$ appears in the decimal representation of $\pi$.  In this case, the algorithm that always returns 1 is always correct.
There is a largest integer $N$ such that $0^N$ appears in the decimal representation of $\pi$.  In this case the following algorithm (with the value $N$ hard-coded) is always correct:

Zeros-in-pi(n):
 if (n > N) then return 0 else return 1

We have no idea which of these possibilities is correct, or what value of $N$ is the right one in the second case.  Nevertheless, one of these algorithms is guaranteed to be correct.  Thus, there is an algorithm to decide whether a string of $n$ zeros appears in $\pi$; the problem is decidable.

Note the subtle difference with the following proof sketch proposed by gallais:

  Take a random Turing machine and a random input.
  Either the computation will go on for ever or it will stop at some point and there is a (constant) computable function describing each one of these behaviors.
  ???
  Profit!

Alex ten Brink explains:

  watch out what the Halting theorem states: it says that there exists no single program that can decide whether a given program halts. You can easily make two programs such that either one computes whether a given program halts: the first always says 'it halts', the second 'it doesn't halt' - one program is always right, we just can't compute which one of them is!

sepp2k adds:

  In the case of Alex's example neither of the algorithms will return the right result for all inputs. In the case of this question one of them will. You can claim that the problem is decidable because you know that there is an algorithm that produces the right result for all inputs. It doesn't matter whether you know which one that algorithm is.
  10

Step 5 of the following proof attempt is unjustified, and in fact wrong - a counterexample can be found here. (thanks, Yuval; it did feel like the sketchiest part of the sketch). I've left the answer here as I think the mistake is instructive.

First off: JeffE's pair of answers is sufficient; f is computable either way.

A brief detour, though, into an attempt at a sketch of a proof by induction:
Premise R: $\pi$ does not repeat.
1. Look at $\pi$ in base 2. This is mostly to cut down on the number of cases.
2. No matter how far down the line you go, you will always find another 1 somewhere: the alternative is all zeros, which would mean $\pi$ starts repeating, which goes against R.
3. Same goes for going down the line and finding 0.
4. Expand to two-digit sequences: you can't stop finding either 01 or 10 (that is, places where it switches), because otherwise $\pi$ would start repeating on 1's or on 0's. Similarly, you can't stop finding 11 or 00, because otherwise it starts repeating on 1010101...
5. The inductive step: each finite sequence has to appear an infinite number of times, because the alternative is that $\pi$ starts repeating on one of the shorter sequences, which contradicts R.


How to cluster similar objects into fixed size groups? I have $n$ people each of which can meet on certain days of the week. I want to group them into $\frac{n}{k}$ groups of size $k$ such that all people in a group can meet on a day.

eg - Suppose there are 3 people who are free on (M,T,W,Th,F), (M,W) and (W,Th,F) respectively. They can all be placed in the same group since all of them can meet on Wednesday.

Just model your problem with graph and use any of the widely known search algorithm to help traverse your graph. After doing that, if you have any problem, let us know.


Converting context-free grammar to chomsky normal form I'm trying to prove that the following CFG can be converted to a CNF:

S -> aAB
A -> aAa
A -> bb
B -> a

Here below is how I've managed so far:

Step 1: add a new start state

S0 -> S
S -> aAB
A -> aAa
A -> bb
B -> a

Step 2: remove epsilon rules

There are no such rules in this CFG.

Step 3: remove non-terminal to non-terminal rules

S0 -> aAB
S -> aAB
A -> aAa
A -> bb
B -> a

Step 4: make right-hand-side not contain more than $2$ non-terminals or $1$ terminal:

S0 -> BC
S -> BC
A -> BF | EE (A -> aAa and A -> bb in one line)
B -> a
C -> AB
E -> b
F -> AB

So this is where I got confused. I have now both C and F that go to AB. If I've done this correctly that would mean that either C or F can simply be removed. Or, of course, I've done something wrong in this procedure.

You're right to be cautious, but there is nothing wrong.

A context-free grammar is in Chomsky Normal Form if and only if every rule is of the form:

A → BC,  or
A → a,   or
S → ε,   where S is the start symbol.

Consider the grammar

S → TU
S → UT
T → a
U → a

Is this a valid context-free grammar in Chomsky Normal Form?

Yes, it is.  Each rule is of one of the allowed forms.

But - you say - T and U have the exact same rules; one can be replaced with the other!

Congratulations: you have invented a normal form!  A grammar is in Byfjunarn Normal Form if and only if it has no two different nonterminals for which the rules have the exact same right hand sides.

This is clearly a normal form: in fact, normalizing grammars into this form is so easy that we do it routinely, without even thinking about it.

But the algorithm you're using to bring arbitrary grammars into Chomsky Normal Form doesn't. Why should it? Grammars can be in Chomsky Normal Form without being in Byfjunarn Normal Form; the example proves it.  Yes, it would be easy to modify the algorithm to bring grammars not only into Chomsky Normal Form, but also into Byfjunarn Normal Form.  But nobody asked it to.  Except you.

Just let the poor algorithm go about its ways.  You know what to do once it's finished :-)

Rules for conversion of CFG to CNF
https://www.geeksforgeeks.org/converting-context-free-grammar-chomsky-normal-form/

Here is the solution of question:


Why is A(A+B) = A [Absorption Law]? Could you proof it to me that A(A+B) = A?

AA + BA [AA = A]

A + AB

Then what?

I presume you are looking for a way to prove the identity using a calculus. So far you have used distributivity an idempotency.

Recall that A = A1 so you get A1+AB and you can use distributivity again, this time in the other direction. Then two obvious steps.

A(A+B)         as The AND operation distributes
                     over the OR operation
                  for all x, y, z ∈ B
                   x • (y + z) = (x • y) + (x • z) so
A(A+B) = AA+AB      Idempotent x • x = x
= A+AB
= A(1+B)      as 1+B=1 so
= A(1)            as A.1=A so
= A


Binary Indexed Trees: Why does i & -i work? I already read this related question on the intuition behind binary indexed trees, and while the answer explains how the tree structure works, it does not really explain how this correlates back to the array representation where the next node is accessed based on the current nodes index according to $i \mathrel{\&} -i$.

I know physically that $i \mathrel{\&} -i$ gives you the highest power of 2 that divides $i$, essentially the least significant set of bits, but I don't see why adding or subtracting this to/from the current index allows you to jump around to get to the wanted node.

Linking this back to the tree representation,

      4
   /     \
  2       6
 / \     / \
1   3   5   7

I see how the left parent of a node with index N is $(N - 2^h)$ and the right parent is $(N + 2^h)$ where h is the height of the subtree from N down (including N), and this seems to be related to why the $i \mathrel{\&} -i$ works.

However, what about the cases like finding the previous node of 5, which according to $5 - 5\mathrel{\&}-5$ is 4? The formula $N - 2^h$ also seems to work except there is no direct link between 4 and 5. How do you prove that it works in these cases too?

Assuming that your tree is storing cumulative sums, one query you would like to make is "what is the cumulative sum to index n".  Suppose the tree is as shown in the OP, and n is 5.  The answer to the question would be found by adding the sum in node 4 and the sum in node 5.  This is because each node is storing the cumulative sum of itself plus its left subtree (if any).  Thus, node 4 has the cumulative sum of indices 1-4 and node 5 has the cumulative sum of index 5 (just itself).  Because of the way the tree is built, you basically need to visit one node for each 1 bit in the binary representation of your index.

So the algorithm to compute the cumulative sum is to start at the given index, in this case 5.  Note that 5 is 101 in binary.  Add its sum to the total.  Then, to get to the next node needed, we want to remove the least significant bit (we want to get from 101 to 100).  The least significant bit of i is i & -i.  To remove the least significant bit, i -= (i & -i).  That gets us to node 4.  We add node 4's sum to the total.  Then we remove the next significant bit, leaving 0 which means we are at the end.

If the tree were bigger, and the starting index were 50 (which is 110010 in binary), we'd have to visit node 50 (110010), node 48 (110000), and node 32 (100000).  In this example, node 32 contains the sums of 1-32, node 48 has the sums of 33-48, and node 50 has the sums of 49-50.

I have recently written a detailed post about Binary Indexed Tree.

You can have a look at it here.

I hope it will help.


How to avoid cascading resizes when resizing hash tables? With conventional collision resolution methods like separate chaining and linear/quadratic probing, the probe sequence for a key can be arbitrarily long - it is simply kept short with high probability by keeping the load factor of the table low. Collisions during rehashing thus aren't a problem as they don't affect the load factor.

However, with cuckoo hashing (and other methods offering worst-case O(1) lookup time?), a resize must happen when the probe sequence for a key gets too long. But when the keys get shuffled around during the rehash, it may be that they create a too-long probe sequence for one key, necessitating another resize - possibly several, if this happens multiple times in a row. The probability is small, especially with a good hash function, but I've seen it happen.

Is there a way - short of explicitly generating a perfect hash function during the rehash - to ensure that resizes can't cascade in this manner? Possibly specific to a given collision resolution scheme? The literature I've encountered thus far seems to gloss over the matter entirely. Bear in mind that I'm also interested in shrinking hash tables, not just growing them.

You ask how to avoid cascading rehashes but you already gave the answer in your post. You keep the probability that bad events occur small.

Since you mention cuckoo hashing. The probability that you get a long probing sequence is $O(1/n^2)$. So if you rehash, you are inserting $n$ elements from scratch. The probability that the rehash is not successful is then $O(1/n)$, so with very high probability you are successful. In expectation you need only a constant number of tries. If you observe that you have problems with rehashing, then you should increase your table size and modify your load factor. Alternatively you can select a better family of hash functions.

I believe I have one solution, inspired by linear hashing:

If the hash function(s) is held constant (that is, not changed when resizing) and the table is always grown by doubling the slots, then after the table is grown, it holds that

$H \mod 2L = \begin{cases} H \mod L + L & \text{or} \\ H \mod L \end{cases}$

where $H$ is the hash of a key and $L$ is the old number of slots. This means that a key either stays where it is or moves to a unique slot in the newly allocated area, which is guaranteed to be empty.

To apply this to (d-ary) cuckoo hashing, simply resize each of the subtables individually and don't move keys between subtables.

To shrink the table, you need to confirm that one of $\lbrace H \mod \frac{L}{2} + \frac{L}{2}, ~ H \mod \frac{L}{2} \rbrace$ is vacant for every key in the table, and if so, move them all to their $H \mod \frac{L}{2}$ slots. Of course, this is $O(n)$... I'm not sure if there's a better way to do this than running the check for every deletion once the load factor drops below half.


Equivalence of two lambda expressions for NOT I've seen two different lambda expressions for the logical NOT function.
One of them just applies its parameter to constants true and false internally in a reverse order:

$NOT \;\;=\;\; \lambda x.\; x \; \mbox{false}\; \mbox{true} \;\;=\;\; \lambda x. \; x \; (\lambda t.\lambda f.f) \; (\lambda t. \lambda f. t ) $

and the other one which captures two more parameters instead of passing them to the returned function externally, and applies $x$ to them in reverse order too:

$NOT \;\;=\;\; \lambda x. \; \lambda t.\lambda f.xft$

of which the other one seems a bit simpler (and it is also simpler when encoded in binary).

So my question is this:
Is there any transformation which could get me from one of these representations to the other?

I see they are equivalent "extensionally", that is, both produce the same results. But I'd like to "prove" it somehow by algebraic transformations, such as those for alpha, beta and eta conversions. Unfortunately, none of these can help me in this case: Alpha is just for renaming. Beta works only for function calls, but we don't have any function call here which could be reduced, since $x$ is free in the function body (not the whole expression, though) in all these expressions until we actually call NOT on something. The most close one seems to be the eta, which is related to extensional equivalence and forwarding parameters, but when the parameters are being reversed, it's not a simple forwarding anymore and eta doesn't seem to apply here.

Is there any more conversion rule I'm missing?
(Well, I guess they won't just skip two Greek letters from no particular reason, wouldn't they?)

P.S.: This question is actually a model one, since there are many other definitions for other functions which have several different forms which seem to be extensionally equivalent, but completely different with regard to the known reduction rules. I've chosen the simplest example of this problem.

Edit:
To better clarify what I'd like to know, here's a diagram showing the reduction steps for both versions of the not function:
http://sasq.comyr.com/Stuff/Lambda/Not.png

As you can see, they really both reduce to the same results (contrary to what @Jonathan Gallagher was saying below). This is what I already know: that they are confluent, and so they're Church-Rosser equivalent. What I don't know however is if there is any conversion rule (similar to alpha, beta & eta) which could allow me to transform one form of not to the other. This would allow me to at least make sure if some other functions (more complicated than these two here), are also equivalent, which could be hard when they can reduce to more than just two possible answers. I'd like to know if there's some conversion rule which could allow me to convert one intensional definition into another when two functions are already extensionally equivalent (i.e. they give the same results for the same parameters). Or (which would be better) if some function can be converted somehow to the other even if I don't know whether they're extensionally equivalent.

In order to prove the two NOT forms are not generally equivalent, all you have to do is find a term that when each is applied, returns a different result such as:

$NOT1 \; \lambda x.\; x \; \;\;=\;\; (\lambda x. \; x \; (\lambda t.\lambda f.f) \; (\lambda t. \lambda f. t )) \; \lambda x.\; x \;\; =\;\; \lambda x. \; x \; $

$NOT2  \; \lambda x.\; x \; \;\;=\;\; (\lambda x.\lambda t.\lambda f.xft)  \; \lambda x.\; x\;\; =\;\; \lambda t.\lambda f. ft \; $

Let the first not be called not1 and the second not2.  Then you have the following:

$$\mathsf{not1} \, M \to_\beta M \, \mathsf{false} \, \mathsf{true}$$
and
$$\mathsf{not2} \, M \to_\beta \lambda t \, f . M \, f \, t \to_\eta \lambda t . M \, t \to_\eta M$$

Now, if we suppose that $$M = \mathsf{true}$$ then the top reduction would give us false while the bottom reduction would give us true -- so that making the identification would seem to give a strange result.


Find the minimum count of elements summing to a pre-defined sum We have the following problem: Given an array of integers $\{a_1, a_2,...,a_n\}$ and a number $s$, find a contiguous sub-array of elements that sum exactly to $s$. If multiple solutions exist, find a solution that is smallest in terms of length (length of sub-array). If there is no such contiguous sub-array, output "-1".

I have thought of an $O(n^2)$ algorithm, using two pointers and prefix sums, but I cannot find an $O(n)$ algorithm. What would an $O(n)$ algorithm be like?

This can be solved in $O(n \lg n)$ time by computing prefix sums and then using divide-and-conquer.

Step 1. Compute the prefix sums $p_0,p_1,\dots,p_n$, where we define $p_i = a_1 + a_2 + \dots + a_i$.  Throw away the $a_i$'s.  Now the problem becomes: count how many index-pairs $i,j$ there are where $0 \le i \le j \le n$ and $p_j = p_i + s$.

Step 2. Solve this problem using divide-and-conquer.  First, count the number of solutions where $0 \le i \le j \le n/2$ (recursively).  Second, count the number of solutions where $n/2 < i \le j \le n$ (recursively).  Third, count the number of solutions where $0 \le i \le n/2$ and $n/2 < j \le n$.  This third step can be done in $O(n)$ time (expected running time).  Since this is your exercise, I'll let you work out how: it's not too hard.

The total running time satisfies the recurrence $T(n) = 2 T(n/2) + O(n)$, so this yields a $O(n \lg n)$ time solution.

This algorithm is $O(n)$ only for non-negative integers, $O(n~log~n)$ otherwise. I think there is no $O(n)$ solution for mixed positive/negative numbers, though I cannot formally prove it.

First, calculate the cumulative sum over the array. This yields an array of length $n+1$

$$\{b_1,b_2,...,b_{n+1}\} = \{0, a_1,a_1+a_2,...\}$$

and allows the calculation of any sum over a range $i..j$ in constant time as $b_{j+1}-b_i$.

If all $a_i$ are non-negative, $\{b_1,b_2,...\}$ is already monotonic. If this is not the case, sort it. Also store the array of indices.

Now you can start with two pointers, called $p_1$ and $p_2$, both initialized to $b_1$. Perform the following algorithm:

If the sum over the range is too large, move $p_1$ one step forward.
If the sum over the range is too small, move $p_2$ one step forward.
If the sum over the range is exactly $s$, you found a solution.

Store it (if the element count is smaller than that of the currently best solution).
If the element in front of the trailing pointer is equal to the current one, move the trailing pointer one step forward. Otherwise move the leading pointer.
You can get range over which you calculated the sum by subtracting the indices. This range can be either ascending or descending, dependent on whether the element were swapped during sort.

Both the cumulative sum and the search require exactly one pass over the array, so the algorithm is of time complexity $O(n)$ for non-negative numbers. In the general case, a sort is required which results in a complexity of $O(n~log~n)$.

Example

s=1
a=[1, -1, 1, -1]

Calculate the prefix sums:
b=[0, 1, 0, 1, 0]

Sort b, keep track of the original indices.
b=[0, 0, 0, 1, 1]
i=[1, 3, 5, 2, 4]

Use the two-pointer method
b=[0, 0, 0, 1, 1]
p1 ^
p2 ^
p2 - p1 = 0 < 1     => rule 2

b=[0, 0, 0, 1, 1]
p1 ^
p2    ^
p2 - p1 = 0 < 1     => rule 2

b=[0, 0, 0, 1, 1]
p1 ^
p2       ^
p2 - p1 = 0 < 1     => rule 2

b=[0, 0, 0, 1, 1]
p1 ^
p2          ^
p2 - p1 = 1 == 1    => rule 3
Look up indices
i=[1, 3, 5, 2, 4]
p1 ^
p2          ^
=> solution: sum from 1 inclusive to 2 exclusive is 1
=> length of solution is 2 - 1 = 1 (accept)

b=[0, 0, 0, 1, 1]
p1    ^
p2          ^
p2 - p1 = 1 == 1    => rule 3
Look up indices
i=[1, 3, 5, 2, 4]
p1    ^
p2          ^
=> solution: sum from 3 exclusive down to 2 inclusive is 1
=> length of solution is 2 - 3 = -1 (we already have a solution of length 1 => reject)

b=[0, 0, 0, 1, 1]
p1       ^
p2          ^
p2 - p1 = 1 == 1    => rule 3
Look up indices
i=[1, 3, 5, 2, 4]
p1       ^
p2          ^
=> solution: sum from 5 exclusive down to 2 inclusive is 1
=> length of solution is 2 - 5 = -3 (we already have a solution of length 1 => reject)

b=[0, 0, 0, 1, 1]
p1       ^
p2             ^
p2 - p1 = 1 == 1    => rule 3
Look up indices
i=[1, 3, 5, 2, 4]
p1       ^
p2             ^
=> solution: sum from 5 exclusive down to 4 inclusive is 1
=> length of solution is 4 - 5 = -1 (we already have a solution of length 1 => reject)

b=[0, 0, 0, 1, 1]
p1          ^
p2             ^
p2 - p1 = 0 < 1     => rule 2

rule 2 not applicable: pointer reached end, terminate.

The final solution is: sum from 1 inclusive to 2 exclusive, length 1


Context free grammar where number of a's is larger than number of b's in any prefix of the string The prefixes of the string aabab are a, aa, aab, aaba, aabab.
If the number of a's should be greater or equal to the number of b's, the grammar would be

S -> aS | aSbS | e,

but I need it with strictly more a's than b's in any prefix.
I thought of this grammar, but I'm not sure it is correct.

S -> aS | aSAbA | a
 A -> aA | aAbA | e

In short, take your grammar for  the language having a greater or equal number of $a$'s in every prefix, but rename the startsymbol to $P$, i.e.
$$
 P \to aP \mid aPbP \mid \varepsilon.
$$
Then simply note that your condition requires a word to start with an $a$, hence the following will do the job:
$$
 S \to aP.
$$
For if $S \to w$ then $w = auv$ with $|u|_a \le |u|_b$, where $|u|_a$ denotes the number of $a$'s in $u$ (and analog for $|u|_b$), hence for the prefixes of $w$ the assertion follows. And conversely it works the same.

For your given grammar, this is correct (but I leave my answer as it seems to be simpler). For a proof note that if the produced word contains at least one $b$, then it must have at least two $a$'s before it, and this is what your production $aSAbA$ takes care of, where from $A$ we can just derive words having at most as many $a$'s as $b$'s in every prefix.

Let me give another approach to think about this. Might be a little bit to much theory, but just for education and reasoning. Note that the famous Dyck language is defined as
$$
 D := \{ w \in \{a,b\}^{\ast} :  |u|_a \le |u|_b \mbox{for each prefix $u$ of $w$ and } |w|_a = |w|_b \}.
$$
It is quite simple to give a grammar for this language, for example
$$
 S \to \varepsilon \mid SS \mid aSb.
$$
Now if we denote by $\mbox{pref}(L)$ the set of prefixes of some language $L$ then your initial language of words having at most as many $a$'s as $b$'s in any prefix is $\mbox{pref}(D)$. And it is quite easy to derive a grammar from it, just make sure every production could be finished any time on the right (for a general argument see this post), hence we could give the grammar
$$
 S \to \varepsilon \mid SS \mid aSb \mid aS \mid a
$$
where the production $S \to aS$ could also be leaved out. Now simply note that words fulfilling your restriction have to start with an $a$ and proceed as above.

One of the  possible CFG's:

S->aPbPaP/aPaPbP/bPaPaP/PaP
P->aPbPaP/aPaPbP/bPaPaP/PaP/ε

Even though S and P might look similar, P is required as S shouldn't produce ε by itself.
This is because an ε string will be invalid, as number of a's should be greater than number of b's.

This grammar takes care of even those strings that begin with b.

examples of accepted strings:
a, baaaaaa, aab,aba, aa, etc.


What are the general applications of Computer Science in the field of Psychology? I am keenly interested to do a project in Computer Science that can aid to address the problems in the field of Psychology. Now I want to know what are the most general and research-oriented issues or problems areas in Psychology that can be solved through computation or at least aid to be solved via Computer Science.
Looking for authentic answers. Thank you

Here are some of the areas that intuitively come into my mind where Computer Science and Psychology can go along together. As a student of Computer Science, one has to study the following core subjects at the undergrad level that are either directly or indirectly related to Psychology:

1. Data Structures and Algorithms: All the data structures do exist in the real world and the human mind perceives them to store, arrange, sort and search the required data as per their strength and limitation. Now the question arises, could there be a data structure or algorithm that is beyond the perception and capacity of human mind? Perhaps certainly or maybe.

2. Design and Analysis of Algorithms: Could there be a general algorithm for curing a mental disease, achieving happiness, finding love or the best match, finding career, overcome stress or depression, defeating a rival, rehabilitating a heroine addict or leading a "perfect life"? All of such aspects of human life can be addressed computationally. And yes the answers to these questions are indeed subjective and debatable as well.

3. Artificial Intelligence: Can we ever have machines more intelligent than humans? Oh yes, we certainly have such intelligent machines. But do such machines recognize vision and pattern as we humans do? That is an area of continuous research in Computer Science.

4. Human Computer Interaction: In the modern world, humans do interact with computers almost on a daily basis. Commercial hardware, software applications and games, all of them are designed with the "interface" keeping in view the human user's perception, expectation and limitation in consideration. Now the question arises: Can we have Computers as our personal psychiatrists? Can we treat mental or psychological patients with Computer-Aided Psychotherapy? I really want to explore!!!!

5. Professional/Ethical Issues in Computing: Can we ever be able to fully secure personal or professional data via Computers? Can we get rid of pornography from the internet? Can we develop a game that counters games leading to suicide like "Blue Whale"? Can we rid the world from religious fanaticism, terrorism, racism and hate crimes via Computer Science?  All of such questions and problem areas are pending to be addressed.


Minimum frame size in ethernet Suppose the round trip propagation delay for a 10 Mbps Ethernet having 48-bit jamming signal is 46.4 μs. The minimum frame size is:

a) 94

b) 416

c) 464

d) 512

My approach:- I have read in the book that minimum frame transmission time is atleast twice the round trip time.So by that logic i can say that the answer will be 464.As soon as the first bit of jamming signal reaches the sender,it know about the collision. But I need to know whether time to transmit jamming signal over the link should also be included in this case?I mean whether the first bit of the jamming signal is sufficient to for the sender to detect the collision or the complete jamming signal needs to be received at sender side,which will make the answer as 512.

I dont have the answer as this question was in some exam in 2005 and there was no answers available to this.

This might not be the correct answer to your question(as I am not sure about jamming signal), but it might resolve the query.

As Ethernet uses CSMA/CD for error detection, the time taken to transmit the data must be greater than or equal to twice the time taken to propagate the data. Only then the station will come to know if there had been a collision.

Tt >= 2*Tp


Is it 100% OK to say "All software doesn't need to know the system lower than the architecture level"? Most of you know this diagram. If this diagram is true, all software is free to not know the levels lower than ISA. But it's not true. Softwares like performance-critical programs or system softwares like OS and compilers, are often forced to understand not only ISA but also microarchitecture.

If so, what about the levels lower than microarchitecture? Is it 100% sure to say the levels lower than uArch aren't require to be understand by softwares or programmers?

Nothing is 100% sure in life.

Abstractions are rarely perfect; they can be leaky.  Nonetheless, just because developers at higher levels sometimes need to know about lower layers doesn't mean they always do, or usually do; and it doesn't mean the abstraction is useless.

Yes, there are cases where it is helpful to know about even lower levels of the architecture.  For instance, cold boot attacks and the row hammer attack are made possible by a property of the physics of DRAM cells, so if you want to analyze the security of a system against that specific threat model, you might need to know about things at the level of devices and physics.  These cases are the exception rather than the norm, but they do exist and are occasionally relevant.

I develop high-optimized (mostly compression) algorithms and use micro-architecture knowledge every day. It allows to make algorithms 10-100x faster compared to naive variants. Here is how you can learn to this level of knowledge:

What are the best resources (book, thesis, and academia papers) for one to become better at low-level computing using the C++ language?


Is there any difference between Time Complexity and Running time? Is time complexity and running time of the program/algorithm one and the same thing?
Also, running time sounds like 'computer complexity'. As, it utilizes all the resources and give tangible time that program took to run. So, can we say that running time is same as computer complexity?

The terms, as they are used in computational complexity theory are different.

Running time is a property of an algorithm. It is the maximum number of steps the algorithm can run for, as a function of the length of the input.

Time complexity is a property of a computational problem. It is, essentially, the running time of the fastest possible algorithm for that problem.

Thus, we might talk about the time complexity of the sorting problem, and the running time of heapsort.  Informally, people often refer to the "time complexity" of an algorithm. Strictly speaking, this is incorrect, but there's only really one thing it could mean.

Note that we usually only quote the asymptotic behaviour of running times and time complexities, since we're usually not interested in the exact function, and it's usually too hard to figure out, anyway.

Note also that, in applied computing, "running time" may refer to the time taken for some program to run, as you might measure with a stopwatch.

No. The difference is well explained by Steve Jessop:
"Running time is how long it takes a program to run. Time complexity is a description of the asymptotic behavior of running time as input size tends to infinity.

You can say that the running time "is" O(n^2) or whatever, because that's the idiomatic way to describe complexity classes and big-O notation. In fact the running time is not a complexity class, it's either a duration, or a function which gives you the duration. "Being O(n^2)" is a mathematical property of that function, not a full characterisation of it. The exact running time might be 2036*n^2 + 17453*n + 18464 CPU cycles, or whatever. Not that you very often need to know it in that much detail, and anyway it might well depend on the actual input as well as the size of the input."

Soure: https://stackoverflow.com/questions/4915842/difference-between-time-complexity-and-running-time

EDIT:
Here is the video that might be helpful for your edited question:
https://www.youtube.com/watch?v=8syQKTdgdzc


Can all decision problems reduce to undecidable? If one could build a machine that for any input will never accept, but always loop forever, then will all problems reduce to this?

Or did I just misunderstood the idea of reduction?

a machine that for any input will never accept, but always loop forever

isn't a decision problem, and so it doesn't make sense to say it's undecidable.

However, given an undecidable problem $A$, there are always "more undecidable" problems $B$, i.e. those which would be undecidable even given an oracle for $A$. For example, the halting problem for Turing machines extended with an oracle for $A$.

The idea of reduction for a decision problem, is to prove that a NP-Complete problem is  at least solvable in terms of another NP problem. As in, we break down (reduce) a problem to show that it may be solved.

Not all problems can be reduced to to be undecidable, only those that are not solvable in polynomial time such as NP-Hard problems.


Directed graph where DFS returns on a node before all its child nodes are visited? Give an example of a directed graph in which a depth-ﬁrst search backs
  up from a vertex $v$ before all the vertices that can be reached from
  $v$ via one or more edges are discovered.

My professor recently asked this question as a warm up to lecture, but never answered it. I still have not figure how that is possible. Why would it return if it's not complete?

I just can't see a scenario where this would happen.

It would never return, since DFS is (essentially) recursive and it can't return without having hit all base cases.

Consider the following graph. If DFS will first go to the second node, it will back up even though the third node is reachable from the second.

I am not sure what does he mean by 'back up from a vertex $v$'. If he just means an encounter of parent node then the case is shown in the pic. $s$ is the starting node in the algorithm. Flow might return to $s$ before going to leaves of $v$ making the edge $(v,s)$ back edge.


Why can't DFS be used to find shortest paths in unweighted graphs? I understand that using DFS "as is" will not find a shortest path in an unweighted graph.

But why is tweaking DFS to allow it to find shortest paths in unweighted graphs such a hopeless prospect? All texts on the subject simply state that it cannot be done. I'm unconvinced (without having tried it myself).

Do you know any modifications that will allow DFS to find the shortest paths in  unweighted graphs? If not, what is it about the algorithm that makes it so difficult?

The only element of depth-first search you tweak is the order in which children are investigated. The normal version proceeds in arbitrary order, i.e. in the order the children are stored.

The only feasible alternative (towards shortest paths) I can come up with is a greedy approach, that is looking at children in order of their distance from the current node (from small to large). It is easy to construct a counterexample for this rule:

[source]

Now, that is no proof that there does not exist a strategy of choosing the next child to be investigated which will make DFS find shortest paths.

However, no matter the rule¹ you can construct graphs that have DFS commit to a long detour at the very first node, just as I did for the greedy rule. Assign edges $(s,t)$ and $(s,a)$ weights such that the rule chooses to visit $a$ first, and assign $(a,b)$ a weight greater than the one of $(s,t)$. Therefore, it is plausible that DFS can never find shortest paths (in general graphs).

Note that since you can express every (positive-integer-)weighted graph as unweighted graph -- simply replace edges with cost $c$ with a chain with $c-1$ nodes -- the same examples deal with DFS on unweighted graphs. Here, the situation is actually even more bleak: without weights, what can DFS use to determine the next child to visit?

As long as the rule is deterministic. If it is not, it can clearly not always find shortest paths.

IT is possible to find the path between two vertices with
the minimum number of edges using DFS. we can apply level approach


Do functions with slower growth than inverse Ackermann appear in runtime bounds? Some complicated algorithms (union-find) have the nearly-constant inverse Ackermann function that appears in the asymptotic time complexity, and are worst-case time optimal if the nearly constant inverse Ackermann term is ignored.

Are there any examples of known algorithms with running times that involve functions that grow fundamentally slower than inverse Ackermann (e.g. inverses of functions that are not equivalent to Ackermann under polynomial or exponential etc. transformations), that give the best-known worst-case time complexity for solving the underlying problem?

Seth Pettie came up with an algorithm for computing the sensitivity of a minimum spanning tree in time $O(m\log \alpha(m,n))$, improving on an algorithm of Tarjan which computes the same in time $O(m\alpha(m,n))$. (Compare this to Chazelle's $O(m\alpha(m,n))$ algorithm for computing the minimum spanning tree itself.) The sensitivity problem asks to compute, for a given graph and a given minimum spanning tree, by how much each edge weight can change without changing the minimum spanning tree.

(Thanks to Tsvi Kopelowitz for this reference.)

When Alan Turing discovered the computer, there used to be several models for the computer proposed. Turing proved that some (3) of these models could simulate each other AND compute the Ackermann function, whereas the other models could simulate each other but not the Ackermann function (so they could not simulate the 3). Therefore, these 3 models (Turing Machine, von Neumann and one I don't know), were chosen as the architecture for a computer. This does not mean the Ackermann function is the limit of the computer, but I suppose it's hard science. I'm not aware of any computable functions that grow faster than the Ackermann function.

Now, I don't think there's a practical problem that matches your question, but perhaps we can construct one. We need to put constraints on the input though. Since we can't use O(n), we cannot check the whole input. In fact, we cannot even check the length of the input as that would be O(log n). So, we need as first parameter a representation of the length of the rest of the input, for example c such that Ackermann(c) is the length of the input. Since this is also not suitable, we demand as first value in our input the parameter c, such that bb(c) is about the length of the input, where bb is the busy beaver function. This function is incomputable but bb(c) certainly exists. Then, the algorithm goes like:

for (int i=0; i<c; i++) {
    if (input[i] == null) {
        return false;
    }
}
return true;

The purpose of the algorithm is to check that if c is the inverse of bb, if then
the input length is greater than bb(c).

If there's a computable function that grows faster than the Ackermann function, I think we can use it's inverse to create an algorithm that answers your question on any input.


Why is $\{1^n \mid n > 1\}$ regular? Given the definition of a regular language is one that can be expressed with finite memory, how is $\{1^n \mid n \geq 1\}$  regular? The $n$ is unbounded. I know a DFA can be drawn, which means the language is regular. But I thought another condition is that $n$ must be bounded, so it's as if the 2 tests contradict each other?

If I understand you correctly, the following comment seems to get to the heart of what you're really asking:

  A regular language is one where you can make an automata for it, or a regular expression for it. But this seems like a poor definition to me because how do you know if none exist or you just haven't been able to think it up yet?

That's a fair question.  I'm afraid the answer is -- the definition is what it is.  Whether you consider it poor or not, this is the standard definition of a regular language.  For now, I recommend that you simply accept it and work within it.  I agree that the implications are a bit.. uncomfortable.  Unfortunately, that's life.

Many definitions are like this.  For instance, consider the definition of what it means for a number to be prime: a number $n$ is prime if there it does not have any divisor $d$ such that $1<d<n$.  Of course you can ask: how do you know if such a divisor exists?  Maybe you just haven't been able to find one yet?  The answer is that you might not know... but that's still the definition, and there are good reasons to use this definition, rather than some other.

Ultimately, there are reasons why the standard definition of regular languages is useful.  Those reasons might not be obvious when you are first starting to study the material.  From a computer scientist's perspective, one reason why the notion of a regular language is useful is that it corresponds to what can be accepted by an automaton with finite state, and this has many applications through computer science (parsing by compilers, model checking, and more).  From a mathematician's perspective, the notion of a regular language is interesting because it has many useful properties.

But for now... accept that the definition is what it is, and there are reasons for it to be that way, and go with it.

The set of regular languages over an alphabet  is defined recursively as below. Any language belonging to this set is a regular language over  .

Definition of Set of Regular Languages :

Basis Clause: , {} and {a} for any symbol a   are regular languages.
Inductive Clause: If Lr and Ls are regular languages, then Lr  Ls , LrLs and Lr* are regular languages.

Extremal Clause: Nothing is a regular language unless it is obtained from the above two clauses.


Constructing a PDA for the language $\{a^m b^n : m < 2n < 3m \}$ I'm having a lot of trouble constructing a PDA for the language: \begin{equation*}
\{a^m b^n : m < 2n < 3m \}
\end{equation*}

I know if I push a symbol for each $a$ I see, then pop 2 symbols for each $b$ I see, then I should run out to satisfy the $m < 2n$ part of the inequality. But I really don't understand how to include the requirement $2n < 3m$. I'm assuming it has something to do with clever branching based on non-determinism, but I can't wrap my head around it. Any help would really appreciated.

To handle the inequality $m \lt 2n$, you arrange to push a marker for each $a$, and pop two markers for each following $b$. This way the number of markers on the stack indicates the number of $a$'s. When the stack is empty, the equality is reached.

To handle the inequality $2n \lt 3m$, you could to arrange to push three markers for each $a$ and pop two markers for each following $b$. However, a stack won't let you push different numbers of markers.

There is no general way of “merging” two automata in this way. If the two automata use the stack at different rates, it may not be possible to merge them without having two stacks. This is reflected in the properties of languages recognized by pushdown automata: the intersection of two context-free languages is not always context-free.

To get an idea of what to do here, I think it helps to write a context-free grammar for this language. A grammar needs to break down the language into some recursive structure, which leads us to expressing elements of the language as expansions of shorter elements. I'll look at what happens when $b$s are added; you could obtain a different grammar by similar means by looking at what happens when $a$s are added.

If you add $1$ to $n$, what happens to the possible values of $m$? For the maximum value, it's easy: it increases by $2$, because $m \lt 2n \iff m+2 \lt 2(n+1)$. For the minimum value, it's more difficult: we need to find the threshold for $\frac{2}{3}n$, so it depends on whether $n$ is a multiple of $3$, which we cannot express in a grammar rule. However, if we add three $b$s at a time, it's easy: the minimum number of $a$s increases by $2$, because $2n \lt 3m \iff 2(n+3) \lt 3(m+2)$.

Let $L$ be the desired language. The rule above tells us how words in $L$ can be constructed from shorter words; we still need to check the base cases.
$$ \begin{align}
  L \cap a^* &= \varnothing \\
  L \cap a^* b &= \{ab\} \\
  L \cap a^* b^2 &= \{a^2b^2, a^3b^2\} \\
  L \cap a^* b^3 &= \{a^3b^3, a^4b^3, a^5b^3\} \\
\end{align} $$
We have all the information needed to construct a grammar for $L$.
$$
\begin{array}{rl}
  S &\to a b \\
  S &\to a^2 b^2 \\
  S &\to a^3 b^2 \\
  S &\to a^3 b^3 \\
  S &\to a^4 b^3 \\
  S &\to a^5 b^3 \\
\end{array}
\qquad
\begin{array}{rl}
  S &\to a^2 S b^3 \\
  S &\to a^3 S b^3 \\
  S &\to a^4 S b^3 \\
  S &\to a^5 S b^3 \\
  S &\to a^6 S b^3 \\
\end{array}
$$
If you're unsure about the correction of this construction, prove that all words in $L$ are recognized by this grammar (construct a derivation) and prove that all the words recognized by this grammar are in $L$ (by induction over the rules).

Now you can apply a systematic method for constructing a non-deterministic pushdown automaton from a grammar. Since the right-hand part of every rule is the same, it is enough to have a single element in the stack alphabet. Push this symbol for each batch of 2 to 6 $a$'s (this is non-deterministic); pop it for 3 $b$'s.

yes, we can create PDA for the given language.

first i find the relation between n & m.

given that
m < 2n < 3m

i break this in two equation

2n > m
i.e [ n > m/2 ] -----------eqn-1
2n < 3m
i.e [ n < 1.5m ] -------------eqn-2

from eqn 1 & 2
i found that [ m >= n+1 ]for n,m >= 2
i.e if n=2 then m=3
       n=3 then m=4 etc

now it is simple to construct PDA for the above language
a^m b^n where m>=n+1 & m,n>=2

push all a into stack and when see 1st b leave it and when see 2nd b then start popping a from stack.


Meaning of topological distance between 2 pixels I came across the notion of topology and topological distance in the context of image processing several times (especially when it came to mathematical morphology). I looked for a not too abstract explanation of "topological distance" but haven't found one yet. Can you please explain (in layaman's terms) the notion of topological distance between 2 pixels? And what's the difference between a euclidean distance and a topological distance in image-processing?

Nonlinear Signal and Image Processing: Theory, Methods, and Applications defines topological distance as follows. First, you have to define when two pixels are neighbors. The book offers two possibilities:

The neighbors of a pixel are the 4 "cardinal" pixels around it.
The neighbors of a pixel are the 8 pixels surrounding it.

This defines a graph (two pixels are connected by an edge if they are neighbors). The topological distance between two pixels $p,q$ is then the graph distance between $p$ and $q$.

The first choice above corresponds to $L^1$ ("Manhattan") distance, and the second choice to $L^\infty$ distance. This contrasts with the usual $L^2$ (Euclidean) distance.

If you really think about it, imagine two pixels which can take on only two values: 0 or 1. How do you characterize the difference between the two?  Suppose you have no notion of position of all, just that a pixel can either take on the value 0 or 1. Preferably, there should only be two absolute values for change in this system: 0 denoting no difference, and 1 meaning existence of a difference between the two values.

Now, suppose there exist two pixels on a one-dimensional axis that can only take on the color value of 1. Now, the difference between the positions on that axis could be taken to represent the "distance" between the two points.

The notion of "distance" is really defined in terms of some fundamental change defined in terms of some units of observation of measurement. Usual Euclidean distance is described in reference to the origin as a difference between the observed or perceived numeric difference between a number and another that are attached to an N-dimensional coordinate system.

Topological distance is most likely a generic form of describing a system of points and relationships between points; topology is about defining what a space really means and relationships between subspaces or points in space, defined using mathematical structures. It's really abstract in the sense that it's really up to you or whoever else to define what a point is, how to define and measure the attributes of the point, and how to define terms to represent changes in between points, and one of those terms can be what we traditionally think as "distance."

In this case, topological distance can be computed against a model that tries to model a certain shape of an object that an image represents. The projection of a specific pixel onto a model of a higher-dimensional object can be considered a part of shape analysis.

Computing a "topological distance," here, then, will be decided by more than what is apparent from the image data itself. It may also take into account certain assumptions of a model (e.g. a pixel on the same coordinates of a 2D image will be mapped to different topologies if one is looking at a sphere versus if one is looking at a dog).

Here might be some helpful reading:

https://en.wikipedia.org/wiki/Topological_skeleton

https://en.wikipedia.org/wiki/Metric_(mathematics)


How does MIPS ( or any other multi-byte word arch ) fetch a word? I've recently been studying MIPS as part of a CS course, but something bugs me.
We've seen so far that MIPS increments the PC by 4 each cycle because each word is in fact comprised of 4 bytes (32 bits), each with their own address.
I've also seen that a theoretical RISC machine has instructions that should only take a single cycle to execute.

Ignoring memory latency, how does it manage to generate an address for each 4 bytes?
It can't have four adders for memory address calculation right? That'd be too expensive! Or am I incorrect in this assumption?
I've also seen other architectures that manage to pull multiple bytes from memory (even multiple words) in a single step/cycle/instruction, but how is this achieved if each byte needs an address?

MIPS can load a 32-bit (4-byte) word in a single instruction (load word, LW). The fact that each byte of the word is individually addressable doesn't affect this.  Effectively, the instruction says "Read the four bytes beginning at this address", not "Read the byte at this address.  Increment the address by one.  Read the byte at that address.  Increment the address by one.  Read the byte at that address.  Increment the address by one.  Read the byte at that address."

By way of an analogy, you can photocopy any two facing pages of a book simultaneously, even though each has its own number.

the cpu might have used an integrated circuit to clone one single instruction command to a number that the same number of instruction set executive commands,how for it will always be executed by transistors logic gate.Your question is unclear,i assume the command is a 8 bits so this 8 bits will be parsed and the output will have to be 11111111 and if not,it will be:example: 10110010 so if the command is available,it will switch circuit to address 8th to send to a i/o another processing circuit to send the next commands to ram or peripheral devices.if not,it will switch to address 4th.