How can it be detected that a number generator is not really random? I heard that random number generation in computers isn't really random, but there is no efficient algorithm to detect it. How can it be detected at all ?

Computers Being Really Random:

True randomness is impossible for Turing Machines in a theoretical sense, and most computers can't generate truly random output.  Therefore, some modern computers include hardware that allows the computer to access an outside source which will hopefully include some randomness.   One example of how this can be accomplished is to track small fluctuations in temperature inside the computer.  Randomness can be obtained from an outside source as well.  But from the tone of your post I don't think that outside sources of randomness are what you're interested in.

Seeds:

Without an outside addition, everything a computer does is deterministic.  This leads to a big issue: if you call a random number generation program, it will give you the same result every time if you give it the same input.  Clearly, we need a program that outputs a random number to change its behavior each time it's run (otherwise we'll keep getting the same "random" number, which is not particularly helpful).  One idea is to give the program some input, which changes each time the program is run, so that a different number will be output.  We call this input a "seed."  The random number generator needs to take in a seed, perform some operations, and give us a random number.

The current system time is a classic example of a seed.  This gives a long string with high entropy, and if the time is kept track of in a sufficiently granular fashion (i.e. if your system clock uses hours then "time" is a pretty poor seed), you're unlikely to feed the pseudorandom number generator the same number twice.

Algorithms that are Random Enough:

Now we have an algorithm that at least has some way to be different each time it's run.  We give it a seed, and while the algorithm gives the same number when prompted with the same seed, we want the numbers it generates to be random otherwise.  This acts like the above--you take in some input, and it produces some (hopefully different enough from the input to be "random") output.

Now let's say you came up with your own algorithm to do this, and you claim that the numbers you come up with are pretty close to random when you gave it a bunch of different seeds.  How would we test how good it is?

Now we want some algorithm that will take in a seed, do some operations, and produce a random number.  At the simplest, the algorithm could just output the seed--it's not giving us the same number each time, and random seeds give us random outputs.  But clearly that's not what we want.  On the other hand, an algorithm can be fairly complicated, like many actual pseudorandom generators.  How can we tell which algorithms give us "random" numbers  from our not-necessarily-random seeds?  If we can't get it exactly, how can we tell which are best?

It's hard to tell which of those tests are ideal, but it's easy to come up with some minimum requirements these algorithms should meet before we say they give us "random" numbers.  Maybe we want to make sure that your algorithm gives even numbers half the time.  Maybe  we want to make sure that if I ask for a random number between $1$ and $n$, all numbers in that range will be output for some input to your function.  Clearly there are a lot of tests we can run; if your algorithm passes some suite of tests it's a pseudorandom generator.  Which tests to use is a very interesting and well used/studied area of computer science.

Random Enough to Fool an Attacker:

Now what you MAY be referring to is Cryptographially Secure Pseudorandom Generators.  I think the best way to explain this is in the context of the above--here, we're using our randomness for cryptography, so when we're designing tests what we really care about is that someone won't be able to break our security by predicting what random number we picked.   I don't know your level of familiarity with cryptography, but imagine we're doing a simple replacement cypher---each letter is replaced with some other letter.  We want to pick these replacements randomly, so they're hard for an attacker to guess.  But if he can figure out how my random number generator works, he'll be able to solve the whole cipher!  Therefore, cryptographic algorithms require random number generators that are specifically hard to guess.  Specific cryptographic algorithms may require additional tests (like for some sort of nice-enough distribution as mentioned above).

For this reason, CSPRGs are defined in terms of how well other algorithms solve them (which is where we finally come to your question).  Specifically, let's say I have a CSPRG which I'll call R.  R is a CSPRG if and only if there is NO feasible algorithm that can guess which bit it will output next.  This is true even if you know all the previous bits it output!

So let's say that the first five bits my CSPRG has output are 10100.  You don't know the input I used to the program, but you have access to the code I used to write my CSPRG.   Then the claim is that it's impossible for you to write a program to decide if the next bit output will be 101000 or 101001.

So for reasons of cryptography, sometimes how well a pseudorandom number generator does is defined in terms of how predictable it is to other programs.  Note that this still gives much of the intuition of "randomness," as (say) if you know all of the random outputs will be odd it is neither cryptographically secure nor does it pass a common-sense randomness test.

In fact everything a classical computer do is deterministic, in the sense that when you give them some tasks it follows them in a deterministic way. Therefore if you want to have one random number you can compute it accordingly to the time (based on the user's input time), but if you want to have a set of random numbers you can not use the time for the next numbers, because the numbers would no more be independent.

What people do is to use pseudo-random generators which have a seed, i.e. a number that is used to compute all the numbers of the pseudo-random number generator (in some more sophisticated cases of simulation or other tasks, more seeds may be needed, if more than one set of independently random numbers is needed). The seed is usually 0 or a specific number if you want reproducible results, or the time if you and different unreproducible results.

The fact that the pseudo-random number generators are good enough, lies in the fact that they follow "the basic characteristics of a pseudo-random numbers generation", in order to be computeded efficiently and behave like real random numbers:

the produced numbers must follow an uniform distribution (from this distribution you can achieve any other distribution);
the produced numbers must be statiscally independent;
the sequence is reproductible (this point is imposed because of that property of the hardware of a classical computer, and it's why they are called "pseudo-random numbers");
the period of the sequence must be large enough;
the numbers generation must be fast.

From each number of the sequence of pseudo-random numbers a new number is computed (usually we work with integers). However there is a period, n, in a sequence of pseudo-random number generators prepared to work in a specific base with finite number of available bits to express the numbers (eg. binary). If this n wouldn't be big enough there would be serious problems, but don't worry, the computer scientists choose the seeds and other parameters of the pseudo-random generators well, in order to have a good n.

For instance, a possible pseudo-random number generator, with the linear congruential method, which is one of the oldest and best-know pseudo-random number generators algorithmns can be defined accordingly to:

it has four values:
 - x_0 ≥ 0
 - a ≥ 0
 - c ≥ 0
 - m > x_0, where:

x0 is the initial value, a, c, and m are constants where: m > a, m > c, and it produces the sequence  with the fornula:

x_{i+1} = (a*x_i+c) MOD m

The values for these constants must be carefully chosen. One possibility is:

x_{i+1} = (1664525*x_i + 1013904223) MOD 2^32, refs.[1-2]

There are other algorithms more sophisticated to generate random numbers, which avoid some of the problems of previous algorithms, that included: [3]

  shorter than expected periods for some seed states (such seed states may be called 'weak' in this context);
  lack of uniformity of distribution for large amounts of generated numbers;
  correlation of successive values;
  poor dimensional distribution of the output sequence;
  the distances between where certain values occur are distributed differently from those in a random sequence distribution.

In the future, the classical computers may be united to quantum systems which can provide really random numbers, and deliver them. [4]

references:
[1] http://en.wikipedia.org/wiki/linear_congruential_generator
[2] William H., et al. (1992). "Numerical recipes in fortran 77: The art of scientific computing" (2nd ed.). ISBN 0-521-43064-X.
[3] http://en.wikipedia.org/wiki/pseudorandom_number_generator
[4] http://www.technologyreview.com/view/418445/first-evidence-that-quantum-processes-generate-truly-random-numbers/


Does Second chance Page replacement algorithm suffer with Belady's anomaly? In Second chance Page replacement algorithm(clock algorithm), if all the Reference bits are set to one, then the algorithm behaves just as FIFO.

Considering this case, can we conclude that Second chance algorithm also suffers from Belady's anomaly?

This is not true.  This is only a special case in once instance of 2nd chance algorithm.  All reference bits set to one does not persist for each page that tested for a page replacement.  Since LRU does not suffer from Belady's anomaly, and since 2nd chance is an approximation to LRU, then it follows that 2nd chance does not suffer from Belady's anomaly.


Flaw in my NP = CoNP Proof? I have this very simple "proof" for NP = CoNP and I think I did something wrongly somewhere, but I cannot find what is wrong. Can someone help me out?

Let A be some problem in NP, and let M be the decider for A. Let B be the complement, i.e. B is in CoNP. Since M is a decider, you can use it to decide B as well (just flip the answer). Doesn't that mean that we solve both NP and CoNP problems with the same M?

To put it more concretely.

Let A be some NP-complete problem, and let M be decider for A. Consider any problem B in CoNP. We consider its complement not-B, which is in NP, and then get a polynomial reduction to A. Then we run our decider M and flip our answer. We thus obtain a decider for B. This implies B is in NP as well.

May I know what is wrong with my reasoning?

There are two possible bugs in this proof:

When you say "decider" - you mean a deterministic TM. In this case, the best translation (to our knowledge) from an NP machine to a deterministic machine may yield a machine that runs in exponential time, so after complementing you will have a decider for the complement in exponential time, proving that $co-NP\subseteq EXP$ (or, after some optimization, $co-NP\subseteq PSPACE$).
When you say "decider" you mean a nondeterministic TM. In this case, flipping the answer will not necessarily complement the language. Indeed, the language of the flipped machine will be all the words for which there exists a rejecting run of $M$ on $w$

I actually agree that your nondeterministic machine M can decide whether a given input string is in B. However, it "decides" slightly differently than the way it decides if a given input is in A. In the latter case, it does so by (nondeterministically) finding an accepting state. In the former case, it does so by failing to find any accepting states. Why does this difference matter? Let's see:

When asking M "Is the string in the language A?"

M reaches an accept state. This, you can prove (see, for example, the Sipser book theorem 7.20) implies that there is a deterministic machine that verifies the string is in A in polynomial time

When asking M "Is the string in the language B?"

M reaches reject states on all branches of its nondeterministic computation. If you think about how the verifier proof above works, you will see that it cannot be accomplished in this situation. This is roughly because the verifier uses the path that M takes through its state space as "proof". In this case, there is no one such path.

Conclusion:

If you consider the existence of a polynomial time deterministic verifier for a language to be the definition of an  NP language (which you should), the existence of M does not prove that B is in NP.


Approximating the runtime of a practice problem I'm studying for an algorithms exam and came upon the problem :

    for (i = 0; i < n * n; i++) {
        i++;
        for (j = 0; j < (log(n) * log(n) * log(n)); j++) {
            j++;
        }
    }

I figure that line 1 costs $ c_1(n^2) $, line 2 costs $ c_2(n^2 - 1) $, line 3 costs $ \sum_{j=0}^{n^2} \log(j)^3 $, and line 4 costs $\sum_{j=0}^{n^2} \log(j)^3 - 1 $. Am I on the right track? If so, what do the summations get simplified to?

Those lines with the increments matters for the final complexity function, but do not take them in count as it will only make things messy. The function can be simplified as follow:

The outer for runs $\frac{n^2}{2}$ times, and for each of it's iterations it runs $\frac{log^3{n}}{2}$ times.

We can call the complexity function $T(n) = \frac{n^2}{2} * log^3{n}$ which leads to $O(n^2 log^3{n})$.


Sliding window protocol, calculation of sequence number bits I am preparing for my exams and was solving problems regarding Sliding Window Protocol and I came across these questions..

  A 1000km long cable operates a 1MBPS. Propagation delay is 10 microsec/km. If frame size is 1kB, then how many bits are required for sequence number?
  A) 3 B) 4 C) 5 D) 6

I got the ans as C option as follows,

propagation time is 10 microsec/km
so, for 1000 km it is 10*1000 microsec, ie 10 milisec
then RTT will be 20 milisec

in 10^3 milisec 8*10^6 bits
so, in 20 milisec X bits;

X = 20*(8*10^6)/10^3 = 160*10^3 bits

now, 1 frame is of size 1kB ie 8000 bits
so total number of frames will be 20. this will be a window size.

hence, to represent 20 frames uniquely we need 5 bits.

the ans was correct as per the answer key.. and then I came across this one..

  Frames of 1000 bits are sent over a 10^6 bps duplex link between two hosts. The propagation time is
  25ms. Frames are to be transmitted into this link to maximally pack them in transit (within the link).

  What is the minimum number of bits (l) that will be required to represent the sequence numbers distinctly?
  Assume that no time gap needs to be given between transmission of two frames.

  (A) l=2 (B) l=3 (C) l=4 (D) l=5

as per the earlier one I solved this one like follows,

propagation time is 25 ms
then RTT will be 50 ms

in 10^3 ms 10^6 bits
so, in 50 ms X bits;

X = 50*(10^6)/10^3 = 50*10^3 bits

now, 1 frame is of size 1kb ie 1000 bits
so total number of frames will be 50. this will be a window size.

hence, to represent 50 frames uniquely we need 6 bits.

and 6 is not even in the option. Answer key is using same solution but taking propagation time not RTT. and their answer is 5 bits. I am totally confused, which one is correct?

Frames of 1000 bits are sent over a 10^6 bps duplex link between two hosts.

When the data is transmitted using a duplex link, Round Trip Time (RTT) do not include the time taken by ACK frame to reach sender from the receiver. This is because the ACK frames are piggybacked with the data frames that are coming from the receiver for the sender (maybe a bit later).
Aforementioned, we must now calculate the number of frames transmitted during propagation time (rather than round trip time)

$No.\ of\ frames = \left(25*10^{-3}*10^{6}\right)/10^3 = 25$

Thus, we will need minimum of $5\ bits$ to represent sequence number distinctly.
HTH

Ignore the key...
Your answer is absolutely correct.

However, you have missed a small point in the procedure.

  While calculating the window size, you must also consider the
  Transmission time.

  Trans. time = 1000bits / 10^6 bps = 1ms.

  Cycle time = 1ms +RTT = 51ms

01sec  -> 10^6 bits

51msec -> 51*10^(-3) *10^6 bits = 51000bits = (51000/1000) frames = 51 frames

Sender window size is 51 frames.
lets assume the receiver window size is 1 frame.

then, minimum number of bits required for sequence number =log(51+1)/(log2) {base 2} = 6 bits.


Is there Any difference between dynamic programming vs branch-bound vs delayed column generation I was reading about cutting stock problem
https://en.wikipedia.org/wiki/Cutting_stock_problem , this is best solved using dynamic programming but wiki page mentions 2 other techniques names Branch-Bound and delayed column generation...
I read them but it all look same ...every case we break problem into sub problem

Can anyone shed some more light with some example.?

Dynamic programming is a strategy which avoids explicit enumeration of all possible solutions in the cutting stock problem.
Branch and bound  is a search based technique also based on pruning. However in branch and bound you might in the worst case need to search over all possible solutions.
Column generation is a variant of branch and bound where instead of creating all variables at once they are generated sequentially based on which ones are more "attractive".

In terms of implementation you can implement dynamic programming in any general purpose programming language like C or Java while for column generation  you will need to use specialised linear programming solvers as also for Linear programming based branch and bound.


How hard is finding the discrete logarithm? The discrete logarithm is the same as finding $b$ in $a^b=c \bmod N$, given $a$, $c$, and $N$.

I wonder what complexity groups (e.g. for classical and quantum computers) this is in, and what approaches (i.e. algorithms) are the best for accomplishing this task.

The wikipedia link above doesn't really give very concrete runtimes.  I'm hoping for something more like what the best known methods are for finding such.

Short answer.
If we formulate an appropriate decision problem version of the Discrete Logarithm problem, we can show that it belongs to the intersection of the complexity classes NP, coNP, and BQP.

A decision problem version of Discrete Log.
The discrete logarithm problem is most often formulated as a function problem, mapping tuples of integers to another integer. That formulation of the problem is incompatible with the complexity classes P, BPP, NP, and so forth which people prefer to consider, which concern only decision (yes/no) problems. We may consider a decision problem version of the discrete log problem which is effectively equivalent:

  Discrete Log (Decision Problem). Given a prime $N$, a generator $a \in \mathbb Z_N^\times$ of the multiplicative units modulo $N$, an integer $0 < c < N$, and an upper bound $b \in \mathbb N$, determine whether there exists $1 \leqslant L \leqslant b$ such that $a^L \equiv c \pmod{N}$.

This would allow us to actually compute loga(c) modulo N by binary search, if we could efficiently solve it. We may then ask to which complexity classes this problem belongs. Note that we've phrased it as a promise problem: we can extend it to a decision problem by suspending the requirements that $N$ be prime and $a \in \mathbb Z_N^\times$ a generator, but adding the condition that these restrictions hold for any 'YES' instance of the problem.

Discrete Log is in  BQP.
Using Shor's algorithm for computing the discrete logarithm (Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer), we may easily contain Discrete Log in BQP. (To test whether or not $a \in \mathbb Z_N^\times$ actually is a generator, we may use Shor's order-finding algorithm in the same paper, which is the basis for the discrete logarithm algorithm, to find the order of $a$ and compare it against $N-1$.)

Discrete Log is in  NP ∩ coNP.
If it is actually the case that $N$ is prime and $a \in \mathbb Z_N^\times$ is a generator, a sufficient certificate either for a 'YES' or a 'NO' instance of the decision problem is the unique integer $0 \leqslant L < N-1$ such that $a^L \equiv c \pmod{N}$. So it suffices to show that we can certify whether or not the conditions on $a$ and $N$ hold. Following Brassard's A note on the complexity of cryptography, if it is both the case that $N$ is prime and $a \in \mathbb Z_N^\times$ is a generator, then it is the case that
$$ r^{N-1} \equiv 1 \!\!\!\!\pmod{N} \qquad\text{and}\qquad r^{(N-1)/q} \not\equiv 1 \!\!\!\!\pmod{N} ~~\text{for primes $q$ dividing $N-1$} $$
by definition (using the fact that $\mathbb Z_N^\times$ has order $N-1$).

A certificate that the constraints on $N$ and $a$ both hold would be a list of the prime factors $q_1, q_2, \ldots$ dividing $N-1$, which will allow us to test the above congruence constraints. (We can test whether each $q_j$ is prime using AKS test if we wish, and test that these are all of the prime factors of $N-1$ by attempting to  find the prime-power factorization of $N-1$ with only those primes.)
A certificate that one of the constraints on $N$ or $a$ fail would be an integer $q$ which divides $N-1$, such that $a^{(N-1)/q} \equiv 1 \pmod{N}$. It isn't necessary to test $q$ for primeness in this case; it immediately implies that the order of $a$ is less than $N-1$, and so it is a generator of the multiplicative group only if $N$ fails to be prime.

since $|a|=O(N)$, then $b=O(N)$. (Meaning brute-force is in EXP.)

For a non-deterministic machine, there is a polynomial witness since we can do modular exponentiation in P. (I.e. the problem is in $NP$.)

The theory that discrete logarithms are in $NP$ but not $P$ is the basis of modern cryptography, but that's obviously unproven.

Shor's method (linked to on that wikipedia page) runs in polynomial time on a quantum computer.


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

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

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

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

There are some options (from comments):

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

Here, the number of $b$s is twice the number of $a$s, so we have to push the $a$s in stack first. Once we start encountering $b$s, we transition on the first $b$ (but put nothing on the stack, just move to next state). After reaching the second $b$, pop the top $a$ as we transition on that $b$.

$z(q_0,a,z_0)\to(q_0,az_0)$

$z(q_0,a,a)\to(q_0,aa)$

$z(q_0,b,a)\to(q_1,a)$

$z(q_1,b,a)\to(q_2,E)$

$z(q_2,b,a)\to(q_1,a)$

$z(q_2,E,z_0)\to(q_f,z0)$


How to find an algorithm's complexity from actual running times I have a certain algorithm which I can run, but I do not have access to its code. Thus, it works as a black box. I would like to now the order of complexity of this algorithm on a certain set of instances, which grow in size as a function of $n$.

Now, I have collected running times from $n = 1$ up to $n = 5000$, which is as far as my computer can go in a reasonable amount of time.

I have plotted my data using Python and I have made some simple regression (exponential, cuadratic, cubic...), but I still can't get to decide which function best fits the algorithm. Obviously, if I try regression with a polynomial of higher degree, I will get a tighter curve, so in case the running time is a polynomial in $n$, I don't know how I could decide which is the one that really fits.

With instances up to $n = 1000$, it seems like the cubic polynomial is the best approximation. However, when I plot the instances up to $n = 5000$, things become less clear (in the second graph I compare the actual running times against the approximations obtained for up to $n =1000$, while the first one compares against the the approximations up to $n = 500$)

(in addition, I feel there is something off with float point calculations, as two of the curves below get really messy)

Any suggestions?

A bit of context: I am working on a particular class of hard Quantified Boolean Formulas (QBF) and I want to test their running times on different available QBF-solvers. These formulas verify a certain interesting property: they have linear size proofs in the QU-resolution proof system. However, QBF-solvers act as block boxes for me, and, altough I can see from data that they do not have the "predicted" linear running times, I would like to know how is the growth in complexity in these particular instances. Particularly, it would be great to give some approximate bound or even confirm that they do not seem to have an exponential growth. Thanks.

You can do regression on the whole data to get a better fit.


Is the following CFG ambiguous? I was given the following CFG :

$S \rightarrow A\ |\ B$

$A\rightarrow aAa\ |\ abAb\ |\ bAc\ |\ aca\ |\ abcb\ |\ bcc$

$B \rightarrow bBa\ |\ aBb\ |\ babBc\ |\ bca\ |\ acb\ |\ babcc$

And I have to show if it is ambiguous by giving two leftmost derivations for the same word.

I am pretty sure that there are two leftmost derivations but I can not find them.

I do not need the solution, just a tip where to start with would be enough.

Is unambiguous because there is no string of rule A which is a string or substring of B. And viceversa.


How to write a recursive function that with certain time complexity I'm now doing exam revision, and from some past year exam papers, I noticed some questions that ask to write a recursive method with signature like

public void run(int n)

that must have a time complexity of like : $O(n^2), O(n^3), O(n^7), O(n^2!), O(2^n), O(9^n)$.

Can anyone give some idea on how to solve this kind of recursion questions.

I will assume the person stating the problem actually meant $\Theta$ where you write $O$; otherwise the question is trivial as Juho points out. Realising this may very well have been the point of the problem (or an intended shortcut for the observant), though.

Here is one basic idea to create an algorithm with runtime $\Theta(f(n))$: find a set of objects $S$ with $|S| = \Theta(f(n))$ and recursively enumerate it. If done correctly, this gives you a runtime in $\Omega(f(n))$; if you don't waste time, you get $\Theta(f(n))$.

Some hints for the concrete runtimes you want to achieve:

Given a set $T$ of $n$ objects, $|T \times T| \in \Theta(n^2)$.
Given a set $T$ of $n$ (distinguishable) objects, the set $\operatorname{Perm}(T)$ of all permutations of these objects has size $n!$.
The set $\{0,1\}^n$ contains $2^n$ words.

Note that all these (simple) facts should be known from basic algorithm analysis and formal languages (and maybe combinatorics). The exam question can be solved by generalising and combining them.

When you are given a problem statement there will be an input.The given input has to be countable in some way. In order to get the answer or output you got to manipulate the input in some way are the other in programming. The question is ,how many operation are you going to do on your inputs ... it depends on problem requirement .

For example : In an sorted array of n elements .
      1)searching can be done by checking each and every element .
      2)And using the mathematical property that array is sorted you apply a very old trick
       called  binary search .which divedes our search space into half every time we check
       our trick. This reduces our search space so as reducing the operations.

please read Master theorem to know how to evaluate complexity.

In the case 1 we have complexity in big oh notation as O(n) where n is the input .
In the case 2 we have complexity in big oh notation as O(log(n)) where n is the input .

For basic please refer Big Oh

Coming to the recursion , Suppose our problem be searching, let us consider the binary search .

int binary_search(int A[], int key, int imin, int imax)
{
  // test if array is empty
  if (imax < imin):
    // set is empty, so return value showing not found
    return KEY_NOT_FOUND;
  else
    {
      // calculate midpoint to cut set in half
      int imid = midpoint(imin, imax);

      // three-way comparison
      if (A[imid] > key)
        // key is in lower subset
        return binary_search(A, key, imin, imid-1);
      else if (A[imid] < key)
        // key is in upper subset
        return binary_search(A, key, imid+1, imax);
      else
        // key has been found
        return imid;
    }
}

Firstly for searching an element say X in our input length N then we check middle element in an sorted array to see whether element to be searched(x) is greater or lesser .If it is greater we search the element from middle element(n/2) to last element N recursively .If element to be search(x) is smaller than middle we search from 1 to (n/2) ,as we know that element after middle element is bigger than middle(x


Machine Learning vs System Identification? Could anyone explain to me the differences & similarities between machine learning and system identifications? Are these just two names of the same thing? In this page, they say:

  Machine learning and system identification communities are faced with similar problems where one needs to construct a model from limited or noisy observations.

I've also read the early chapters of the famous book Pattern Recognition and Machine Learning by Christopher M. Bishop. So far, my conclusion is that the problem that system identification is trying to solve is a subset of what machine learning is trying to solve.

System identification is the science of constructing dynamical models from observed data. There are two main approaches: Prediction Error Identification (PEI) and Subspace Identification (SID). Both of them are delivering a so called parametric model, that is to say, a model of a fixed structure. Usually it is the case that the user selects the structure of the underlying system (especially in the PEI methods) or at least the order of the system (in both methods). Even though it is not necessary, a low order system is sought (that is to say, the number of the basis coefficients is relatively small) because it is often used for control purposes, so we have to keep it as simple as possible to avoid computational issues etc. This model can be used to make predictions about the future behaviour of the system given some inputs.

On the other hand, machine learning (ML) has two main branches, classification  and regression algorithms. The latter ones are also used for prediction purposes. Two of the most famous approaches in machine learning are Support Vector Machines (SVM) and Gaussian processes (GP). The main difference with the system identification techniques is that the ML techniques are delivering a non-parametric model. The latter means that the prediction for a new input is given as a function of the data points used for the "training" (learning, identification) of the model. Therefore, if we used N=1000 data points for the training, then the prediction would be expressed as a function of these data points. ML methods are more flexible since they don't require any structure selection from the user, but they face other limitations (e.g. computational effort).

Until recently the ML and the system identification techniques were developing independently. But in the latter years there is a great effort to establish a common ground (e.g. see the paper "Four encounters with system identification" from Ljung)

Machine Learning:
   modeling for static model and dynamic model
, System Identification:
   focus on dynamic model or dynamic process


What is the utility of proving P=NP if we can't find an algorithm that can solve any NP problem in polynomial time? Here we see a very interesting attempt to show that $\mathrm{P} \ne \mathrm{NP}$ by Norbert Blum.

Here we see 116 previous attempts at solving P vs. NP.

Here we see the P vs NP problem defined as:

  The informal term quickly, used above, means the existence of an algorithm solving the task that runs in polynomial time, such that the time to complete the task varies as a polynomial function on the size of the input to the algorithm (as opposed to, say, exponential time).

Here the commentator writes:

  I think it's even less useful, even if P = NP it is possible that no one finds an algorithm. Creating a (useful) algorithm is independent of proving the theorem. Also interesting is that someone could create an algorithm that solves NP complete in polynomial time without proving P=NP. They would be unable to prove the algorithm correct though.

My question is: What is the utility of proving P=NP if we can't find an algorithm that can solve any NP problem in polynomial time?

In short, if we prove $P=NP$, then we know a whole lot more about computation than we did before, even if we don't find the algorithm, and that was the objective behind research on $P=NP$ all along.

It's much worse, because most researchers believe that $P\ne NP$, meaning that even when the proof is discovered, it means that we won't be able to find a polynomial-time algorithm for SAT, not because we're looking in the wrong places, but because no such algorithm exists.

But that doesn't worry most complexity theorists, because the would-be algorithm for SAT that you describe is only a practical application, a spin-off, of the proof. And if you care about practical applications, then why are you working on $P=NP$? It's the most theoretical question in computer science!

Rather, the motivation behind research in this direction is* to better understand computation, very much akin to why mathematicians care about the Riemann hypothesis, and why physicists build giant particle colliders, even though we already have giant databases of prime numbers and even though the discovery of new particles mostly does not help us build faster rockets or better fusion reactors.

But what don't we understand about computation? We can build marvellous AI systems that recognize faces and Chinese characters, and predict the weather! Those are results of the form, this problem can be solved with so-and-so many resources, but on the flip side, one can ask, for this problem, what is the minimum amount of resources needed? The current state of affairs in the last regard is rather embaressing, because as far as we know:

SAT has a linear-time (!) algorithm**
SAT has an algorithm that uses $O(n^{1.802})$ time and $O(\sqrt{n})$ space
every language in $NP$ has a circuit with $5n$ gates.
The Succinct Circuit Satisfiability problem***, which is $NEXP$-Complete ($NEXP$ is the exponential-time version of $NP$), can be solved in polynomial time with a randomized algorithm with bounded error (i.e. it gives the wrong answer only with probability $\leq \frac{1}{n}$)
Everything that can be computed using a polynomial amount of memory can be solved using a polynomial amount of time. For example, the Quantified Boolean Formula problem, which is like SAT except instead of an $\exists$ quantifier, there are any number of $\exists x\colon\forall y\colon\exists z\colon\cdots$ quantifiers.

Until these ridiculous scenarios are ruled out, we cannot honestly say that we understand computation in any depth. And that is the utility that you ask for, of why anybody at all works on $P=NP$.

I encourage you to read this wonderful survey of Scott Aaronson where in section 1.2 he addresses all the usual objections, like, what if $P=NP$ but we can't find the algorithm, or what if we do, but it's exponent is hopeless, or...

*as far as I can tell, as someone who is not a professional complexity theorist, but who did write his Master's thesis on the topic.

** We do not know whether nondeterminism gives you an advantage for solving SAT, but we do know, since 1983 [1] that nondeterminism gives you an advantage for some language, because there is a language $L$ solvable by a non-deterministic machine in $O(n)$ time but not by any deterministic machine in $O(n)$ time. In 2001, that result was improved [2] to a language in $NTime(n)$ but not in $DTime(n\sqrt{\log(n)})$.

*** The Succinct Circuit Satisfiability problem is this: fix some encoding of Boolean circuits as binary strings. You are given a circuit on $n$ inputs. Interpret the truth table of this circuit as a binary string of length $2^n$. Interpret that string as representing a circuit. Is that circuit satisfiable?

[1] Paul, Wolfgang J., et al. "On determinism versus non-determinism and related problems." Foundations of Computer Science, 1983., 24th Annual Symposium on. IEEE, 1983.

[2] Santhanam, Rahul. "On separators, segregators and time versus space." Computational Complexity, 16th Annual IEEE Conference on, 2001.. IEEE, 2001.

Proving P=NP in the same time shows that such algorithm gives a proof to NP in polynomial time if it's true, assuming a same program appears for infinite times: (assuming $n>1$)

for k=1..inf
    x=[result running the k-th program for n^k steps]
    if x is a proof then return x


Algorithm for implementing the modulus "%" operator? How can an efficient modulus operator be implemented?

Here's a naive way of defining A % B:

  given $(a,b) \in \mathbb{Z}$ (represented as int)

  while $a > b$ : $(a,b) \mapsto (a-b,b)$

  return $a$

This could be very slow. E.g. $(a,b) = (10^7, 13)$.  I could be subtracting 13's for a long time.

One more possibility is that % is defined in terms of another infix operator / as well as the int function (here in C and verbatim in Python):

  a % b = a - (b * int(a/b))

This is probably not how Python implements it's modulus operator (as it makes a call to C or Fortran).   The % operator is need to reduce fractions or compute GCD's.

Here are some examples of truncation and division from Wikipedia:

You don’t “implement the modulus operator”. You check wit the standards for your programming language how it is defined, and that’s what you implement. For languages like C, C++, Objective-C, Swift and many others, a % b is defined as a - b * (a/ b). And that’s what you implement.

To be efficient: Most processors have built-in division and multiplication. Many support faster implementation of division if b is known. And at last if you want to know whether a % b = 0, you can do that without calculating a / b exactly which makes it a bit faster.

My own mathematical implementation of mod(float x, float y) may be useful in some cases
$$\frac{y}2 - \frac{y}{\pi} \arctan \left ( \cot \left( \frac{x}y\pi \right) \right)$$
https://www.desmos.com/calculator/2uczus4jyr


What is the formal name for an "entry" in an ontology? I am trying to wrap my head around ontologies and their related counterparts (RDF, OWL, etc.).

My understanding is that an ontology, at the end of the day, really boils down to some database storing objects/entries, where each entry has a set of known attributes as well as relationships to other entries.

If that's true, I'd imagine ontologies lend themselves as perfect candidates for NOSQL graph DBs.

Either way, after all my initial reading, I still haven't found what the formal/official name is for a single "entry" in an ontology. Any ideas? Ditto for what the official names of their attributes and other relationships are. Thanks in advance!

My understanding is that an ontology, at the end of the day, really boils down to some database storing objects/entries, where each entry has a set of known attributes as well as relationships to other entries.

The more common understanding is that one can emulate1 any ontology as a theory in single sorted first order predicate logic. Because such a theory can be seen as an ontology itself, it "really boils down to ... database(s)" if and only if predicate logic boils down to databases. And indeed, there is a close connection, but it won't help you to understand ontologies.

  What is the formal name for an “entry” in an ontology?

Even in your database analogy, you are missing the fact that you also have to specify the database scheme itself in the ontology language. There are different components of an ontology, namely individuals, types/classes, attributes, interrelationships/relations, function terms, restrictions, rules, axioms, and events1. Your "entry" seems to be intended to describe the attributes of an individual, and the relations between individuals. This task is done by the rules, but note that rules are more powerful than this.

1If the ontology contains events, then it is unclear how to emulate it in predicate logic.

Just like vzn, I now have the urge to clean up some of the confusion from the question, independent of whether it will earn me downvotes or not. (People might argue that such explanations based on mathematical logic require too much background knowledge, are too unrelated to ontology, and only lead to confusion. They may be right...) Even if there are practical reasons to prefer RDF or OWL as ontology languages over predicate logic, the simple structure of the later makes it a good tool for explaining some essential components of an ontology language.

A theory in single sorted first order predicate logic consists of axioms and a signature describing the non-logical symbols, i.e. the constants, functions, and predicates (and their arity). The axioms are well formed logical sentences over the given signature (with equality). Let's take set theory as an example. The signature just consists of $S_{rel}=\{\in\}$ and $\operatorname{ar}(\in)=2$, i.e. "$\in$" is a binary predicate. The axioms are logical sentences like $\forall A \, \forall B \, ( \forall X \, (X \in A \iff X \in B) \Rightarrow A = B)$ (Axiom of extensionality).

As an ontology, such a set theory has (at least) the following components:

a single type/class (sets),
a single interrelationship/relation (set $A$ is an element of set $B$ written as $A\in B$),
and a set of axioms/rules

Further attributes and relations can be defined based on these, for example

$\operatorname{singleton}(A) \iff \exists S \, (S \in A) \land \forall X \, \forall Y \, ((X \in A \land Y \in A)\ \Rightarrow\ X=Y)$
$A\subset B\ \iff\ \forall X \, (X \in A\ \Rightarrow X \in B)$

In single sorted first order predicate logic, you could use such attributes (as well as attributes that are part of the signature) to emulate further types/classes. One can also define constants (like the empty set $\{\}$) and functions (like union $\cup$) based on these. So individuals can be emulated as constants and function terms as functions.

Ontologies are "a representation of entities, ideas, and events, along with their properties and relations, according to a system of categories."
they are an abstraction that impose a limiting "world view" on reality that may or may not exist (reality is slippery that way). There is not a unique way to represent/ symbolize reality and an ontology will have both inherent objective and subjective aspects. In a sense they are almost like "belief systems" that impose a structure on reality. The concept of psychological framing and chunking and labelling are relevant. These are methods that humans use to make sense of the world and categorize it into objects. Hence there is also strong connection with CS oriented modelling.

Ontologies are a somewhat more general/ recent theory of the classic, decades-old, well-established version of objects in CS. The original concept of objects in CS are dynamic entities that model real world entities. ontologies are largely used as a sort of higher-level abstraction/ representation of objects in systems. Ontologies are roughly "the higher level entities/ properties etc expressed by CS objects of interest to external systems". It's similar or could be regarded as a customized machine-based language to describe objects & interrelations. Languages have verbs (representing processes)/ nouns (representing objects). There are many different language possibilities and different languages may describe the same objects. As those who know multiple languages can attest, different languages can describe different ideas, and languages can actually have a reverse-influence on thinking in this way.

From wikipedia:

  What many ontologies have in common in both computer science and in philosophy is the representation of entities, ideas, and events, along with their properties and relations, according to a system of categories. In both fields, there is considerable work on problems of ontological relativity (e.g., Quine and Kripke in philosophy, Sowa and Guarino in computer science),[4] and debates concerning whether a normative ontology is viable (e.g., debates over foundationalism in philosophy, and over the Cyc project in AI). Differences between the two are largely matters of focus. Computer scientists are more concerned with establishing fixed, controlled vocabularies, while philosophers are more concerned with first principles, such as whether there are such things as fixed essences or whether entities must be ontologically more primary than processes.


Finding the longest repeating subsequence Given a string $s$, I would like to find the longest repeating (at least twice) subsequence. That is, I would like to find a string $w$ which is a subsequence (doesn't have to be a contiguous) of $s$ such that $w=w' \cdot w' $. That is, $w$ is a string whose halves appear twice in a row. Note that $w$ is a subsequence of $s$, but not necessarily a substring.

Examples:

For 'ababccabdc' it will be 'abcabc', because 'abc'='abc' and 'abc' appears (at least) twice in 'ababccabdc'.

For 'addbacddabcd' one option is 'dddd' because 'dd' appears twice (I cannot use the same letter several times, but here i have 4 'd's so its ok), but its of lebngth 4. I can find a better one of length 8: 'abcdabcd', because 'abcd' is a substring of 'addbacddabcd' that appears twice.

I'm interested in finding the longest repeating subsequence. This is also called "finding the longest/largest square", but I've read many articles in which a square is defined for a substring and not for a subsequence.

I can easily use a brute force algorithm that will take $O(n^3)$ by iterating on all options for a breakpoint in the string, and then I will have two strings in which I'll be looking for largest/longest common subsequence, but each check will take $O(n^2)$ using a dynamic programming technique, so the entire time will be $O(n^3)$. I found a more efficient algorithm for longest common subsequence which takes $O(\frac{n^2}{\log n})$ , so the running time will be $O(\frac{n^3}{\log n})$.

I am looking for a more efficient algorithm for longest repeating subsequence problem. Perhaps my idea of iterating over all breakpoints wastes too much time, and can be reduced to less iterations. Or perhaps an algorithm with a different attitude can solve this problem.

I've searched in many journals and previous questions, and most of the results I found were about a substring and not about a subsequence.

I've also read that this can be done using suffix trees, but this too was relevant to substrings and I am not sure if such an idea can be extended for subsequence.

I'm looking for a solution that runs in time $O(n^2)$. If there exists one in time $O(n \cdot \log n)$ that will be even better (I am not sure if such exists).

Here is a dynamic programming solution.

Suppose that the input string is $x_1\ldots x_n$. Create a table $T$ whose rows and columns are indexed by $0,\ldots,n$ (where $n$ is the length of the string), populated by the rule
$$
 T[i,j] =
\begin{cases}
0 & \text{if $i = 0$ or $j = 0$}, \\
T[i-1,j-1] + 1 & \text{if $x_i = x_j$ and $i \neq j$}, \\
\max(T[i-1,j],T[i,j-1]) & \text{otherwise}.
\end{cases}
$$
The answer is $T[n,n]$.


Represent a real number without loss of precision Current floating point (ANSI C float, double) allow to represent an approximation of a real number.
Is there any way to represent real numbers without errors?
Here's an idea I had, which is anything but perfect.
For example, 1/3 is 0.33333333...(base 10) or o.01010101...(base 2), but also 0.1(base 3)
Is it a good idea to implement this "structure":

base, mantissa, exponent

so 1/3 could be 3^-1

{[11] = base 3, [1.0] mantissa, [-1] exponent}

Any other ideas?

There is no way to represent all real numbers without errors if each number is to have a finite representation. There are uncountably many real numbers but only countably many finite strings of 1's and 0's that you could use to represent them with.

You cannot represent all real numbers in a computer, but you can represent many. You could use fractions which would represent more numbers than floats. You could also do more sophisticated things like representing numbers as a root of some polynomial with an approximation that under newtons method will converge to the number.


Simplest combination of logic gates to produce a given set of outputs Given a truth table for a truth function that takes n inputs and produces a single output (true or false), what is the fastest way to find the simplest combination of logic gates that will output the given truth table?

A few rules for specificity:

Any binary truth function may be used as a logic gate. In other words, AND, OR, XOR, NOR, and NAND are all valid logic gates, but a binary truth function like AND(NOT(A), B) also counts as a single logic gate when determining the simplicity or complexity of a solution.
The "simplest" solution is the one which uses the fewest logic gates
The output of a logic gate may either be the output, or it may be an input to exactly one other logic gate.

Primary inputs themselves may go to more than one logic gate; it is only the output of a logic gate that may only be used once. I am most concerned with the minimal circuit necessary for the binary multiplication of two numbers. Do we know of a minimal circuit for multiplication? If so is there an efficient algorithm to construct the minimal circuit?

This problem is discussed in Circuit Minimization Problem, by V. Kabanets and J.-Y. Cai.

Obviously the decision version is in NP (does there exists a circuit of size $\le k$ which agrees with the given truth table), since you could provide the circuit $\mathcal{C}$ and verify that $\forall x\in\left\{0,1\right\}^n : \mathcal{C}(x)=f(x)$. This can be done in polynomial time (relative to the input's size), since the size of the truth table is $2^n$.

It's an open question how hard the problem is.  The above paper shows that any proof that this problem is in $P$, or any proof that it is $NP$-complete, would extend our current knowledge and imply a solution to long-standing open problems in complexity theory.

If the Circuit Minimization Problem is in $P$, then it is shown that $BPP=ZPP$ (so for now, showing your problem is in $P$ is open).

Since this is believed to happen anyway (under the assumption that $P=BPP$), they give more consequences which are less likely. For example, it is enough to show $2^n/n$ circuit lower bound for the class $E$ to obtain a $2^{c\cdot n}$ lower bound (If high circuit complexity functions exist in $E$, then very high circuit complexity functions exist too). They also show how to factor Blum integers efficiently on average (Which, they say, is the strongest evidence for the fact that this problem lies outside of $P$).

If the Circuit Minimization Problem is $NP$-hard (under what they call a "natural reduction", where the reduction's output size depends only on the input's size and not structure) then $BPP\subseteq SUBEXP$ and $BPP=P$ unless the exponential time hypothesis fails.

This is the (optimization version of) the problem of circuit minimization for Boolean functions ; it is known to be $\Sigma^p_2$-complete, so it resides at the second level of the polynomial-time hierarchy. In other words, this problem is hard. See http://users.cms.caltech.edu/~umans/papers/BU07.pdf for more details.


Knapsack and set cover-like problem Given $n$ sets $r_1, r_2, \cdots, r_n$ and a number $\delta$ where $0 \le \delta \le 1$. Let $T=\cup_{i=1}^{n}r_i=\{t_1,t_2,\cdots,t_m\}$. Each $t$ has a value $v(t)$, which is given to us.  The task is to find a subset $S$ of $T$ that minimize the total value $\sum_{t\in S}v(t)$ while guaranteeing $\sum_{i=1}^{n}\frac{|r_i \cap S|}{|r_i|}>\delta n$.

Is this problem NP-complete? If so, which problem should I reduce from?

I've tried reduce it from the knapsack problem. One of the steps is not in P time and the attempt failed.

Your problem is an instance of the following problem:

VECTOR-MINIMIZATION:
Input: vectors $v,w \in \mathbb{R}^m$, a threshold $\gamma \in \mathbb{R}$
Goal: minimize $v \cdot x$, subject to $w \cdot x \ge \gamma$ and $x \in \{0,1\}^m$

In your problem, $v=(v(t_1),\dots,v(t_m))$ and $w=(w_1,\dots,w_m)$ where $w_i = \sum_{t_i \in r_j} 1/|r_j|$, where the sum is over all $j$ such that the set $r_j$ contains the element $t_i$.

So, your problem is an instance of VECTOR-MINIMIZATION.  In turn, VECTOR-MINIMIZATION is basically an instance of the knapsack problem (it is at least as hard as knapsack, and thus NP-hard).

That raises the question, is your problem any easier than the general VECTOR-MINIMIZATION problem (or knapsack)?  In your problem, each $w_i$ has a special form: it is a sum of a polynomial number of reciprocals of polynomial-size integers.  I don't think there's any way to use the special structure of the $w_i$'s (and there are exponentially many possible values for the $w_i$'s), so I think your problem is NP-hard, but I don't have a proof at the moment.

That said, you can still use the standard algorithms for knapsack-like problems: e.g., integer linear programming (ILP).

Try reducing from Clique.  The $r_i$ are the vertex pairs in each edge (so $n$ will be the number of edges and $|r_i|=2$ for each $1 \le i \le n$).  Set $v_i=1$ for each $i$, and set $\delta = \frac{k(k-1)}{4n}-\epsilon$, where $k$ is the threshold parameter for the Clique problem instance and $\epsilon$ is some tiny positive amount to make the $> \delta n$ condition like $\ge \delta n$.  (If this produces $\delta > 1$, then add dummy vertices with huge costs and edges between them.)  This way we are trying to find the fewest vertices such that we get at least $\frac{k(k-1)}{2}$ edges, i.e., a $k$-clique.


Is Applicative-order and Normal-order evaluation model's definition contradictory as per sicp text book? As per this explaination, it defines applicative and normal order evaluation in one form saying:

  This alternative "fully expand and then reduce" evaluation method is known as normal-order evaluation, in contrast to the "evaluate the arguments and then apply" method that the interpreter actually uses, which is called applicative-order evaluation.

while this explanation defines the other way around

  applicative-order language, namely, that all the arguments to Scheme procedures are evaluated when the procedure is applied. In contrast, normal-order languages delay evaluation of procedure arguments until the actual argument values are needed

They seem to contradict each other. Do these definitions mean the same thing?

Those definitions are saying the same thing (at the level of precision of the English description).

An example from the book

Normal-order evaluation goes “fully expand and then reduce”, meaning that function calls are expanded before reducing the arguments, and the reduction only happens when the value is needed. Let's take one of the examples in the book: start from (sum-of-squares (+ 5 1) (* 5 2)). First, we fully expand the definition of sum-of-squares:

(sum-of-squares (+ 5 1) (* 5 2)) → (+ (square (+ 5 1)) (square (* 5 2)))

Since + is a primitive, we can't expand it. It requires integers as arguments, so here we have no choice: we must reduce the arguments. To reduce (square (+ 5 1)) in normal order, we start by expanding:

(square (+ 5 1)) → (* (+ 5 1) (+ 5 1))

Then we have the primitive *, also requiring integers as arguments, so we must reduce the arguments.

(+ 5 1) → 6
(+ 5 1) → 6

and so

(* (+ 5 1) (+ 5 1)) →→ (* 6 6) → 36

and likewise for (square (* 5 2)), so the original expression finally evaluates thus

(+ (square (+ 5 1)) (square (* 5 2))) →→ (+ 36 100) → 136

In contrast, applicative-order evaluates the arguments when the function is applied, before expanding the function call. So to evaluate (sum-of-squares (+ 5 1) (* 5 2)), we first need to evaluate the arguments:

(+ 5 1) → 6
(* 5 2) → 10

and then we can expand the function call:

(sum-of-squares (+ 5 1) (* 5 2)) →→ (sum-of-squares 6 10)
                                 → (+ (square 6 6) (square 10 10))

The next step is to evaluate the arguments of +; they're function calls, and in each case the arguments are already fully evaluated so we can perform the function call right away:

(square 6 6) → (* 6 6) → 36
(square 10 10) → (* 10 10) → 100

and finally

(+ (square 6 6) (square 10 10)) →→ (+ 36 100) → 136

An example with side effects

The order of evaluation doesn't make any difference when the expressions have no side effect. (Except with respect to termination, if you don't consider non-termination a side effect: an expression may terminate in some evaluation orders and loop forever in others.) Side effects change the deal. Let's define a function with a

(define (tracing x)
  (write x)
  x)

If we evaluate (square (tracing 2)) in applicative order then the argument is evaluated only once:

(tracing 2) → 2 [write 2]
(square (tracing 2)) → (square 2) [write 2]
                     → (* 2 2)
                     → 4

In normal order, the argument is evaluated twice, so the trace is shown twice.

(square (tracing 2)) → (* (tracing 2) (tracing 2))
(tracing 2) → 2 [write 2]
(tracing 2) → 2 [write 2]
(* (tracing 2) (tracing 2)) →→ (* 2 2) [write 2, write 2]

You can observe this in Scheme. Scheme applies applicative order to function evaluation, but also has a macro facility. Macro calls use normal order.

(define-syntax normal-order-square
  (syntax-rules () ((normal-order-square x) (* x x))))

At a Scheme prompt, you can see that (square (tracing 2)) prints 2 once whereas (normal-order-square (tracing 2)) prints 2 twice.

Towards theory

Let's present the rules of evaluation in a more formal way (with small-step semantics). I'm going to use a notation that's closer to what is commonly used in theory:

$(\lambda x y. A)$ is (lambda (x y) A), where $A$ is an expression.
$B[x\leftarrow A]$ means to take the expression $B$ and replace all occurrences of $x$ by $A$.
$[\![ \ldots ]\!]$ is an integer obtained by some mathematical computation, e.g. $[\![ 2+2 ]\!] = 4$.
$A \xrightarrow{\;t\;} B$ means that the expression $A$ evaluates to the expression $B$, and in doing so prints the trace $t$.

I'll simplify away everything that's related to variable binding: a variable is considered equivalent to its definition.

Evaluation rules come in two flavors. There are head rules, that explain how to make progress on the evaluation of an expression by looking at the topmost node in the syntax tree.

$$ \begin{align}
  ((\lambda x. B) \: A) &\longrightarrow B[x \leftarrow A] && (\beta) \\
  ((\lambda x_1 x_2. B) \: A_1 \: A_2) &\longrightarrow B[x_1 \leftarrow A_1, x_2 \leftarrow A_2] && (\beta_2) \\
  (* \: i \: j) &\longrightarrow [\![ i \times j ]\!] && (\delta_*) \\
  (\texttt{tracing} \: x) &\xrightarrow{\;x\;} x && (\delta_{\texttt{tracing}}) \\
\end{align} $$

$(\beta)$ is the rule the application of a user-defined function. I've defined a variant for two arguments (there are other, better ways to treat functions with multiple arguments but that's a topic for another day). The $(\delta)$ rules are for the evaluation of primitives (I'm treating tracing as a primitive because expressing it in terms of progn and write would unnecessarily complicate this presentation).

There are context rules, that explain how to look for things to evaluate deeper inside the evaluation syntax tree. The notation $\dfrac{P}{C}$ means “if there's a way to do the reduction $P$ according to the rules, then $C$ is also a valid reduction”. In other words, assuming that the premise above the line holds, the conclusion below the line holds.

$$
  \dfrac{A \xrightarrow{t} A'}{(F \, A \xrightarrow{t} F \, A')} (\texttt{App}^1_1)
  \qquad
  \dfrac{A_1 \xrightarrow{t} A_1'}{(F \, A_1 \, A_2 \xrightarrow{t} F \, A_1' \, A_2)} (\texttt{App}^2_1)
  \qquad
  \dfrac{A_2 \xrightarrow{t} A'_2}{(F \, A_1 \, A_2 \xrightarrow{t} F \, A_1 \, A_2')} (\texttt{App}^2_2)
$$

For example the rule $(\texttt{App}^1_1)$ means that to evaluate a function call, we can evaluate the argument. In a full treatment, there would be a similar rule for the function part, but we don't need it here.

The arrow $\longrightarrow$ means “evaluates in a single step to”. We can derive the notion of “evaluates to” (in any number of steps):
$$
  \dfrac{}{A \xrightarrow{} A}
  \qquad
  \dfrac{A \xrightarrow{\;t\;}^* B \text{ and } B \xrightarrow{\;t'\;} C}{A \xrightarrow{\;t,t'\;}^* C}
$$
The first rule means that an expression evaluates to itself (in zero steps). The second rule allows adding one more step to a sequence of evaluations.

These rules are non-deterministic: there can be more than one applicable rule for a given expression, and thus there are multiple possibilities to evaluate an expression. This is where evaluation strategies come into play. An evaluation strategy defines a priority on the rules.

In normal order, $(\beta)$ (the application rule) is applied before context rules that would affect the arguments. This is what the first quote means by “fully expand [apply head rules] and then reduce [in context]”, and what the second quote means by “delay the evaluation of procedure arguments until the actual argument values are needed” (don't apply context rules until forced by a $\delta$ rule). (In the first quote, the use of the word “expand” is somewhat jarring — applying $(\beta)$ is a reduction too!)
In applicative order, the context rules are applied first, and $(\beta)$ is only applied if the arguments can't be evaluated anymore. This is what the first quote means by “evaluate the arguments [in context] and then apply [head rules]”, and what the second quote means by “all the arguments (…) are evaluated when the procedure is applied [before performing the actual application]”.

Let's look at (square (tracing 2)) in this model. In the notation I've presented, that's $((\lambda x. (* \: x \: x)) (\texttt{tracing} \: 2))$. In normal order:
$$ \begin{align}
  ((\lambda x. (* \: x \: x)) \: (\texttt{tracing} \: 2))
  &\longrightarrow (* \: (\texttt{tracing} \: 2) \: (\texttt{tracing} \: 2)) && \text{by \((\beta)\)} \\
  &\xrightarrow{\;2\;} (* \: 2 \: (\texttt{tracing} \: 2)) && \text{by \((\delta_{\texttt{tracing}})\) and \(\text{App}^2_1\)} \\
  &\xrightarrow{\;2\;} (* \: 2 \: 2) && \text{by \((\delta_{\texttt{tracing}})\) and \(\text{App}^2_2\)} \\
  &\longrightarrow 4 && \text{by \((\delta_*)\)}
\end{align} $$
In applicative order:
$$ \begin{align}
  ((\lambda x. (* \: x \: x))\:  (\texttt{tracing} \: 2))
  &\xrightarrow{\;2\;} ((\lambda x. (* \: x \: x)) \: 2) && \text{by \((\delta_{\texttt{tracing}})\) and \(\text{App}^1_1\)} \\
  &\longrightarrow (* \: 2 \: 2) && \text{by \((\beta)\)} \\
  &\longrightarrow 4 && \text{by \((\delta_*)\)}
\end{align} $$
(I used left-to-right evaluation for function arguments; specifying this is necessary to get a fully deterministic evaluation order.)
This shows how $((\lambda x. (* \: x \: x)) \: (\texttt{tracing} \: 2))$ evaluates to $4$ with the trace $2,2$ under normal order, but to $4$ with the trace $2$ under applicative order.

Yes, it seems to me they are in contradiction.

I think you're reading it correctly, and it's just one of those errors that make it into text books from time to time.

I searched, and found this errata page, but it seems to be more focused on code errata, and not on conceptual errors.

Hope this helps,
-john


Push down automata for $\{a^n b^n c^n | n \ge 0\}$ I am learning about context free languages.

I understand how $\{a^n b^n c^n | n \ge 0\}$ can be shown to be not context free using the pumping lemma for CFL's.

Intuitively however it seems that a pushdown automata to recognize $\{a^n b^n c^n | n \ge 0\}$ can be constructed. This PDA would initially push two $a$'s into its stack whenever it sees an $a$ in the input. It would change state when it first encounters a $b$ and pop a single $a$. It would continue to pop $a$'s for every b in the input until it encounters a $c$. It would again change state and pop single $a$'s for every c encountered. If the stack is empty at the end of the input the language is recognized as $\{a^n b^n c^n | n \ge 0\}$.

There must be something I am overlooking whilst constructing the PDA as a language is context free if its has a PDA recognizing it. Please point out my mistake.

Your PDA would also accept strings of the form $a^nb^ic^j$ where $i+j=2n$ and $i,j>0$. For example the string "aaabbbbbc" is accepted. There is no way to tell that there are exactly $n$ $a$'s still remaining on the stack once you've finished reading the $b$'s.

You are trying to say that for every a read from the tape you will push two a's on the stack then string aabccc will also be accepted by this PDA which is not part of given language


Why and how is a quantum computer faster than a regular computer? I'm currently reading a book (and a lot of wikipedia) about quantum physics and I've yet to understand how a quantum computer can be faster than the computers we have today.

How can a quantum computer solve a problem in sub-exponential time that a classic computer can only solve in exponential time?

A quantum computer by itself isn't faster. Instead, it has a different model of computation. In this model, there are algorithms for certain (not all!) problems, which are asymptotically faster than the fastest possible (or fastest known, for some problems) classical algorithms.

I recommend reading The Limits of Quantum by Scott Aaronson: it's a short popular article explaining just what we can expect from quantum computers.

A quantum system is a system that exists in a quantum state(s) at different probabilities determined by environmental constraints. Assuming that a quantum computer contains all the states of an n-bit quantum system the extraction of one of these states collapses the system to one of the states. This is akin to a hash function using O(1) to search for a bucket without iteration. Two things are needed, quantum storage of the n-bit systems and a hash-like function to collapse the state that is needed. The constrains play the role of different hashing functions for collapsing the n-bit system into the wanted state.


Why must a function with polymorphic type `forall t: Type, t->t` be the identity function? I am new to programming language theory. I was watching some online lectures in which the instructor claimed that a function with polymorphic type forall t: Type, t->t be the identity, but did not explain why. Can someone explain to me why? Maybe a proof of the claim from first principles.

The first thing to note is that this isn't necessarily true. For example, depending on the language a function with that type, besides being the identity function, could: 1) loop forever, 2) mutate some state, 3) return null, 4) throw an exception, 5) perform some I/O, 6) fork a thread to do something else, 7) do call/cc shenanigans, 8) use something like Java's Object.hashCode, 9) use reflection to determine if the type is an integer and increment it if so, 10) use reflection to analyze the call stack and do something based on the context within which it is called, 11) probably many other things and certainly arbitrary combinations of the above.

So the property that leads to this, parametricity, is a property of the language as a whole and there are stronger and weaker variations of it. For many of the formal calculi studied in type theory, none of the above behaviors can occur. For example, for System F/the pure polymorphic lambda calculus, where parametricity was first studied, none of the above behaviors above can occur. It simply doesn't have exceptions, mutable state, null, call/cc, I/O, reflection, and it's strongly normalizing so it can't loop forever. As Gilles mentioned in a comment, the paper Theorems for free! by Phil Wadler is a good introduction to this topic and its references will go further into the theory, specifically the technique of logical relations. That link also lists some other papers by Wadler on the topic of parametricity.

Since parametricity is a property of the language, to prove it requires first formally articulating the language and then a relatively complicated argument. The informal argument for this particular case assuming we're in the polymorphic lambda calculus is that since we know nothing about t we can't perform any operations on the input (e.g. we can't increment it because we don't know if it is a number) or create a value of that type (for all we know t=Void, a type with no values at all). The only way to produce a value of type t is to return the one that is given to us. No other behaviors are possible. One way to see that is to use strong normalization and show that there is only one normal form term of this type.

EDIT: A comment above has provided the missing piece. Some people are deliberately playing with less-than-turing-complete languages. I explicitly don't care about such languages. A really usuable not-turing-complete language is a crazy hard thing to design. The whole rest of this expands on what happens trying to apply these theorems to a full language.

False!

function f(a): forall t: Type, t->t
    function g(a): forall t: Type, t->t
       return (a is g) ? f : a
    return a is f ? g : a

where the is operator compares two variables for reference identity. That is, they contain the same value. Not an equivalent value, same value. Functions f and g are equivalent by some definition but they aren't the same.

If this function is passed itself it returns something else; otherwise it returns its input. The something else has the same type as itself therefore it can be substituted.  In other words, f is not the identity, because f(f) returns g, whereas the identity would return f.

For the theorem to hold it has to assume the ridiculous ability to reduce

function cantor(n, <z, a>) : forall t: t: Type int, <int, t> -> <int, t>
    return n > 1 ? cantor((n % 2 > 0) ? (n + 1) : n / 2, <z + 1, a>) : <z, a>
return cantor(1000, <0, a>)[1]¹

If you're willing to assume that you can assume the much easier type inference can be handled.

If we try to restrict the domain until the theorem holds we end up having to restrict it awfully far.

Pure Functional (no mutable state, no IO). OK I can live with that. A lot of time we want to run proofs over functions.
Empty standard library. meh.
No raise and no exit. Now we're starting to get constrained.
There is no bottom type.
The language has a rule that allows the compiler to collapse infinite recursion by assuming it must terminate. The compiler is allowed to reject trivial infinite recursion.
The compiler is allowed to fail if presented with something that can't be proved either way.² Now the standard library can't take functions as arguments. Boo.
There is no nil. This is starting to get problematic. We've ran out of ways to deal with 1/0.³
The language can't do branch type inferences and does not have an override for when the programmer can prove a type inference the language cant. This is pretty bad.

The existence of both of the last two constraints has crippled the language. While it is still Turing complete the only way to get general purpose work out of it is to simulate an inner platform that interprets a language with looser requirements.

¹ If you think the compiler can deduce that one, try this one

function fermat(z) : int -> int
    function pow(x, p)
        return p = 0 ? 1 : x * pow(x, p - 1)
    function f2(x, y, z) : int, int, int -> <int, int>
        left = pow(x, 5) + pow(y, 5)
        right = pow(z, 5)
        return left = right
            ? <x, y>
            : pow(x, 5) < right
                ? f2(x + 1, y, z)
                : pow(y, 5) < right
                    ? f2(2, y + 1, z)
                    : f2(2, 2, z + 1)
    return f2(2, 2, z)
function cantor(n, <z, a>) : forall t: t: Type int, <int, t> -> <int, t>
    return n > 1 ? cantor((n % 2 > 0) ? (n + 1) : n / 2, <z + 1, a>) : <z, a>
return cantor(fermat(3)[0], <0, a>)[1]

² The proof that the compiler can't do this depends on blinding. We can use multiple libraries to ensure the compiler can't see the loop at once. Also, we can always construct something where the program would work but could not be compiled because the compiler can't perform the induction in available memory.

³ Somebody thinks you can have this return nil without arbitrary generic types returning nil. This pays a nasty penalty for which I have seen no effective language that can pay it.

function f(a, b, c): t: Type: t[],int,int->t
    return a[b/c]

must not compile. The fundamental problem is runtime array indexing doesn't work anymore.


What is the relation between EXPTIME and NP HARD complexity classes? Need to know the relation between EXPTIME and NP HARD complexity classes.

There are NP-hard problems that are not in EXPTIME and vice versa. This is to be expected as NP-hard is defined by a lower bound and EXPTIME mainly by an upper bound. NP is contained in EXPTIME, however, and NP-complete is of course contained in NP.

NP hard is a subset of EXPTIME, but we have no idea if that subset is strict.
Answered by: @jmite


Understanding Decision Stump in Adaboost I am trying to understand how Adaboost works, and many of the tutorials online involve the use of a decision tree stump. For example, http://www.cc.gatech.edu/~thad/6601-gradAI-fall2013/boosting.pdf or http://www.fromdev.com/2012/04/creating-weak-learner-with-decision.html. However, I am confused on how the plot is actually generated. Say I have the following training set:

               Event 1     Event 2     Event 3
Classifier 1      -1          1          1
Classifier 2      1           -1         1
Classifier 3      1           1          -1

How should I generate a decision stump for this?

I wonder if you what decision stump is.

Decision stump is simply a decision tree with only one node. It is usually considered as the weak classifier in boosting algorithms since due to its simplicity it will not overfit.

In your question it is not clear what is even 1 .. 3. Anyhow, the classifiers can be : decision stump1, decision stump2 and decision stump3.


Why are non-deterministic Buchi automata factorially succinct when compared to deterministic Rabin Automata? I am trying to demonstrate the following idea without success.

  There are infinitely many $n \in \mathbb{N}$ such that: There is a
  non-deterministic Buchi automata of size $n$ such that a deterministic Rabin Automata
  accepting the same language has at least $n!$ states.

Any help would be appreciated

This is Theorem 1.30 in the chapter "Omega-Automata" in the book "Automata, Logics, and Infinite Games: A Guide to Current Research" edited by Erich Grädel, Wolfgang Thomas and Thomas Wilke. They have a proof as well (and a literature referene to the original publication).

Note that instead of the nondeterminstic Buchi automaton having $n$ states, it needs to have $O(n)$ states to make the proof work. The problem is then defined slightly differently to make this precise.

Note that it is a bit confusing if you write "Buchi automata" and "deterministic Rabin automata" in the same question if the former are meant to be "nondeterministic Buchi automata". There is ample work both on deterministic and non-deterministic Buchi automata, so spelling out which variant is meant is important.

Are you sure you didn't get them mixed up?

It seems like for any Buchi automaton with accepting states F, we can build the equivalent Rabin automaton with accepting conditions $\Omega = \{(\{\}, F)\}$ that accepts the same language.

(I.e., any infinite sequence $\rho$ has to intersect some state in $F$ infinitely often and has no restrictions on what states it can't hit infinitely often.)

I'm using the acceptance condition here https://en.wikipedia.org/wiki/Ω-automaton#Acceptance_conditions. Was there a different formulation you had in mind?


An $O(n^2)$ is faster than an $O(n\log n)$ algorithm for small $n$ If $n<100$ then $O(n^2)$ is more efficient, but if $n\ge 100$ then $O(n\log n)$ is more efficient.

I am sure that this statement is valid, but I don't know how to prove it or justify it. Can someone please help me?

Your statement is meaningless, since $O(n^2)$ and $O(n\log n)$ are just upper bounds on the time complexity. If you know that $A \leq 100$ and $B \leq 10$, you have absolutely no idea which is larger, $A$ or $B$.
Let us correct your statement to

If $n<100$ then $\Theta(n^2)$ is more efficient, but if $n \geq 100$ then $\Theta(n\log n)$ is more efficient.

This statement still has no truth value, since we don't know which functions are represented by $\Theta(n^2)$ and by $\Theta(n\log n)$. What we do know is that for large enough $n$, the $\Theta(n\log n)$ algorithm would be more efficient.
Suppose you instantiate your statement with specific functions $f(n) = \Theta(n^2)$ and $g(n) = \Theta(n\log n)$. There is no reason to expect that there is a single crossover point. For example, take the following functions:
$$
f(n) =
\begin{cases}
100 & \text{if } n < 20, \\
n^2 & \text{if } n \ge 20
\end{cases} \\
g(n) =
\begin{cases}
50 & \text{if } n < 10, \\
200 & \text{if } 10 \le n < 20, \\
10^{300} n\log n & \text{if } n \ge 20
\end{cases}
$$
As you can see, $g(n)$ is faster for $n < 10$, and then for (astronomically) large enough $n$.
While such definitions are artificial, in practice we could have (say) $f(n) = 3n^2 + n\log n + 9n + 17$ and $g(n) = 10n\log n + 4\sqrt{n} + 50$, which might have several crossover points (I haven't checked).
Finally, even if there is a single crossover point, there is no reason to expect it to be exactly $n = 100$. The exact crossover point(s) depend on the functions $f(n),g(n)$. The only way to determine it is by running the two algorithms and comparing the running times.

$O(n\log n)$ is always faster.  On some occasions, a faster algorithm may require some amount of setup which adds some constant time, making it slower for a small $n$.
So in reality, $O(n^2 + i)$ may be faster than $O(n\log n + j)$ if $j$ is sufficiently larger than $i$ for small enough $n$.  There is certainly no number $n$ for which you can say there is definitely a crossover.
Note that we always ignore $i$ and $j$ in practice because big O notation is for when $n$ is large, so constants become increasingly meaningless and we only care about the fastest growing term.


Possible solutions how to find all points (given by lat, long) that are within a radius from main point let's say that I have:

M - Main point - given by coordinates (lat, long)
C - Collection of points - also given by coordinates (lat, long)
R - Radius - maximum search distance

I'm trying to find all points that are within a radius from main point (neighbors).

algorithm(main_point, collection_of_points, radius) --> neighbors

Obvious solution is to calculate distances and select those points, where distance is equal or smaller than R, but I believe there are better options with better performance.

Do you know any possible solutions? I'm open for every idea (not only the best one).

EDIT:

I should add that I'm looking for solution where points are strongly dynamic (every point is mobile phone or car). I'd like to update point when it's neccessary (it has been moved) so frequency of updates depends on amount of connected devices (so as queries). Let's say that server will get update request every 5 second and query request every 20 second.

Visualisation

You can speed up your search by using a datastructure like a kd-tree or an r-tree. The basic idea is to divide your space into boxes and store the mapping from points to boxes (and back) in a way that allows for quick lookup times. Then you don't have to calculate the distances to all points to see which are too far away, you can restrict your search to points in the same (or adjacent) boxes.

But note that the naive approach is actually pretty good in this case, even if it's asymptotically not optimal. CPUs are really good at summing squares and it's trivial to throw more cores at the problem if you need more speed. So unless you're dealing with many points, it will be hard to beat.

https://en.wikipedia.org/wiki/Spatial_database#Spatial_index

This link describes most popular ways to index spacial data.


Can this algorithm still be considered a Binary Search algorithm? While doing the second code kata (which asks you to implement a binary search algorithm five times, each time with a different method), I've come up with a slightly different solution which works as follows:

If i have a sorted array of lenght 100 and I see its starting field contains the number 200 and its ending field contains the number 400, me, as a maths studying human, would be likely to start searching around field 35 if I was searching the number 270, and not the field 50 like in a normal binary search algorithm.

Then, if the number on field 35 of the array is 270, 35 is the index I was searching for.

If that isn't the case I can compare the number I got (say 280) and repeat the operation taking the lower part of the array (so I have 35 fields with the starting field containing 200 and the ending field containing 280) if the number I found is greater than what I'm searching for, or the upper part of the array (say I got 260: now I have 65 indexes, the first one containing 260 and the final one containing 400. Orientatively, I would head torward index 4 of this sub array, which is index 39 of the entire array) if the number I got is smaller than the number I'm searching for.

The question is: can this algorithm be considered a binary search algorithm? If not, has it got its own name?

I would not call this a binary search.

It is clearly similar to binary search and it's natural to see it as a refinement of binary search.  However it has significantly different algorithm complexity characteristics, Interpolation Search has expected run time of O(log(log(n)) assuming the data is uniformly distributed, however it pays for this by having O(n) worst case run time.

I prefer to say "The worst case run time of binary search is O(log(n))" rather than "Depending on the choice of bounding elements the worst case run time of binary  search is O(log(n))".  This means that I can not classify Interpolation search as a binary search algorithm.

I think the correct terminology would be dychotomial pondered search.

You search in a flat array with subsequent pondered seeking based on the supposed flat distribution of the numbers in it.

This corresponds to how a person would search a word in a dictionary. But it can be very inefficient if the distribution of data is irregular.


Huffman encoding: why is there no need for a separator? Char        Code
====        ====
E           0000
i           0001
y           0010
l           0011
k           0100
.           0101
space       011
e           10
r           1100
s           1101
n           1110
a           1111

Original text:

  Eerie eyes seen near lake

Encoded:
0000101100000110011100010101101101001111101011111100011001111110100100101

Why is there no need for a separator in the Huffman encoding?

You don't need a separator because Huffman codes are prefix-free codes (also, unhelpfully, known as "prefix codes"). This means that no codeword is a prefix of any other codeword.  For example, the codeword for "e" in your example is 10, and you can see that no other codewords begin with the digits 10.

This means that you can decode greedily by reading the encoded string from left to right and outputting a character as soon as you've seen a codeword.  For example, 0, 00 and 000 don't code anything so you keep reading bits.  When you read 0000, that encodes "E" and, because the code is prefix-free, you know there's no other codeword 0000x, so you can now output "E" and start to read the next codeword. Again, 1 doesn't encode anything but 10 encodes "e".  No other codewords begins with "10", so you can output "e".  And so on.

We cant use separator in Huffman encoding because every letter's binary equivalent doesn't matches the prefixed code of any letter, so we can do without even using separator.


why are deterministic PDAs not closed under concatenation? I can understand that they are not closed under concatenation because without non determinism, PDA cannot decide whether to loop in the first PDA or jump to the next one.
But can someone prove this with an example. Also prove that the resulting language cannot be accepted by DPDA

Pick the languages:

$L_1 = \{a^ib^jc^k | i \neq j \}$ and $L_2 = \{a^ib^jc^k | j \neq k\}$; both are DCFL and $L_3 = 0L_1 \cup L_2$ is DCFL, too.

$L_0 = 0^*$ is DCFL (regular)

But $L_{conc} = L_0 \cdot L_3 = 0^* L_3$ is not DCFL.

Proof: Suppose that $L_{conc}$ (which is the concatenation of two DCFLs) is DCFL.

If we intersect $L_{conc}$ with the regular language $0a^*b^*c^*$, we should get a DCFL language:

$L_{conc} \cap \{0a^*b^*c^*\}$ = $0L_1 \cup 0L_2$. suppose $0L_1 \cup 0L_2$ is a DCFL, so $L_1 \cup L_2$ should be a DCFL, too but:

$L_1 \cup L_2 = \overline{\overline{L_1} \cap \overline{L_2}} = \overline{\{a^ib^ic^i\}}$ which is not DCFL $\Rightarrow$ contradiction.

Explain how,    given   a   PDA for a   L1  and a   PDA for L2, you
can construct   a   PDA for the concatenation   L1L2.?
Answer: The basic   answer  is  to  take    the accept  state   for L1, and make    it
the start   state   for L2. However – if    L1  leaves  symbols on  the stack
(other  than    delta), we  might   have    to  pop them.   It  is  not required    the
stack   be  empty   at  accept. So  we  need    a   non-deterministic   pop to  clear
out the stack. Solution on  right


Cover the maximum of elements I have a collection of subsets $\{S_1,\ldots,S_m\}$ where each $S_i\subset \{1,\ldots,n\}$. I would like to cover the maximum number of elements from $\{1,\ldots,n\}$ by choosing a single element from each $S_i$. What is the optimal way to do this?

For example, say I have $S_1=\{1\}$ and $S_2=\{2,3\}$ and $S_3=\{3\}$ and $n=3$. If my algorithm picks randomly (or the maximum number say) a number from each $S_i$, then I could obtain a solution that covers only $\{1,3\}$ but there is a solution that covers all elements.

This problem is the same as the problem of finding the maximum matching in bipartite graphs, which can be solved by the Ford-Fulkerson algorithm in $O((n+m)s)$ time or the Hopcroft-Karp algorithm in $O(\sqrt{n+m}s)$ time, where $s$ is the number of elements in all $S_i$ combined.

Given a collection of subsets $\{S_1,\ldots,S_m\}$ where each $S_i\subset \{1,\ldots,n\}$, let $G$ be the graph with nodes $\{1, 2, \cdots, n, S_1,S_2,\cdots,S_m\}$. Whenever $j\in S_i$, there is an edge $e_{j,S_i}$ in $G$ that connects node $j$ and node $S_i$. $G$ is a bipartite graph with vertex sets $X=\{1, 2, \cdots, n\}$ and $Y=\{S_1,S_2,\cdots,S_m\}$

Suppose we have selected $k_i$ from $S_i$ for all $i$. Having removed duplicate numbers among ${k_1}, {k_2}, \cdots, {k_m}$, we can assume $\{k_i\mid i\in I\}$ for some $I\subseteq
\{1,2,\cdots,m\}$ is the set of distinct numbers among them. Then $\{e_{k_i, S_i}\mid i\in I\}$ is a matching in $G$.

Conversely, if we have a matching $\{e_{k_i, S_i}\mid i\in I\}$ in $G$ for some $I\subseteq \{1,2,\cdots,m\}$, we can select $k_i$ from $S_i$ when $i\in I$ while selecting any element from $S_i$ when $i\not\in I$.

The above two conversions show that the problem in the question, finding the maximal number of selected elements is the same as the problem of find the cardinality of the maximum matching in a bipartite graph. Note that the conversion takes linear time or polynomial time depending on which parameters are used.

Here is a variation for which I do not know if there exists a polynomial algorithm.

Problem. What if we select two elements from each set, assuming each set has at least two elements?

This is the hitting set problem, you can find greedy algorithm for solving it.


If $f$ reduces $L_1$ to $L$ and also $L_2$ to $L$ is $L_1=L_2$ If the same $f$ reduces $L_1$ to $L$ and also $L_2$ to $L$ does it imply that $L_1=L_2$?
My intuition says no, but I couldn't find a counterexample.

Using the definition of reduction,
$x\in L_1\iff f(x)\in L \iff x\in L_2$
And thus $L_1=L_2$.

When a reduction takes place that means that the problem $L_i$ is just a different "point of view" of problem $L$. Given that you have two problems $L_1$ and $L_2$ reducible to the same $L$ then you could say that by solving $L$ you would be able to solve both. This in turn implies that they could be treated as the same problem.


Complexity of finding factors of a number I have come up with two simple methods for finding all the factors of a number $n$. The first is trial division:

For every integer up to $\sqrt{n}$, try to divide by $d$, and if the remainder is $0$ then add $d$ and $n/d$ to the factor list. Assuming division and appending to a list are $O(1)$ operations for a CPU, this seems to be $O(\sqrt n)$.

The second is to use trial division with prime factors:

Sieve all primes up to $\sqrt n$. The time complexity of the Sieve of Eratosthenes is $O(n \log \log n)$, so this is $O(\sqrt n \log \log \sqrt n)$?
From that list of primes, repeatedly try to divide by $p$ and move on to the next prime if the current prime will not divide evenly anymore. If it does divide, add $p$ and $n/p$ to the factor list. The density of primes is $n / \ln n$, and since primes go up to $\sqrt n$ the supposed time complexity is $O(\sqrt n / \ln \sqrt n)$. However, this does not take into account dividing by primes more than once.

I would like to know if my analysis is correct. It seems counter-intuitive that trial division only takes $O(\sqrt n)$ time, but $n$ is integer size, not input length. I don't think the time complexity of the second method is correct, but I am sure it must be faster than the first (trying primes instead of all numbers within a range).

The exact running time depends on your computation model. When analyzing arithmetic with large numbers, we usually count either bit operations, or arithmetic operations on words of size $O(\log n)$ (where $n$ is the input size, which in your case is the logarithm of the number you want to factor). This means that in a constant amount of time the first model only allows you to perform an operation involving a constant number of bits; and the second model allows you to perform a constant number of arithmetic operations (addition, subtraction, multiplication, division) on registers of length $C\log n$, where $C$ is some constant which you can use but must depend only on the algorithm.

In both models, the division operation itself won't take $O(1)$; indeed, the CPU cannot divide a large number $N$ by a prime $p$ in $O(1)$. So the running time is really $O(\sqrt{N}(\log N)^{O(1)})$ (where $N$ is the number you're trying to factor). We usually don't care about these logarithmic factors, so we use the notation $\tilde{O}(\sqrt{N})$, and we explain that it hides logarithmic factors.

this does not take into account dividing by primes more than once.

But that is exactly why the problem of integer factorization is hard.  It can not be decided efficiently (I.e. in polynomial time) how many times each prime occurs in the factorization. Both your analysis' assume each prime occurs either once or not.

In other words.
The hardness doesn't lie in the fact of finding out which primes are part of the factorization (i.e. at least once or not) , but how many times each prime occurs (not, once, twice, ...?).

In even other words. You can, using your algorithms, decide which primes will be part of the factorization but now how many times they will occur.

The wikipedia article on this problem is pretty extensive