Is the calculation of infinite sums solvable by a computer? The question is: I give the computer a sum, such as $\sum_{n=1}^\infty\frac{1}{n^3}$, the computer is expected to return an elegant closed-form solution, because the answer may be irrational. Has this problem been solved using a computer? Or, has it been proved to be undecidable? Or is it open?

It's complicated. Some very broad classes have been solved completely, but that's still one way of saying that it's only been done for special cases. The book A=B by Wilf, Zeilberger and Petrovšek would probably interest you: it describes algorithms for some of these broad classes.

Given a general infinite series, the most a computer can do is calculate the partial sums (the sum of the first thousand terms or the first million terms, for example). And even then it can only calculate the approximate values of those partial sums, to some finite degree of precision.

Showing that an infinite series converges to some closed-form expression (such as

$\displaystyle \lim_{k \rightarrow \infty} \sum_{n=1}^k \frac{1}{n^2}= \frac{\pi^2}{6}$

for example) can only proved by mathematical reasoning. We do not know how to create a computer algorithm that will originate that reasoning (although a proof-checking algorithm could possibly validate the proof once it was found).

At best, a program can compare the partial sums of the series to values of combinations and functions of mathematical constants such as $\pi$, $e$ or $\sqrt{2}$ and suggest a closed-form solution if it finds a close match. This field of research is called experimental mathematics.


Are Context Sensitive Languages Turing Complete? Related questions:

Can regular languages be Turing complete?
Why are Linearly Bounded Turing Machines more powerful than Finite State Automata?
https://stackoverflow.com/questions/14589346/is-c-context-free-or-context-sensitive
https://softwareengineering.stackexchange.com/questions/132385/what-makes-a-language-turing-complete

Context-sensitivity has nothing to do with the semantics of a language. A language could have an arbitrarily complicated grammar, and still not be able to do anything useful, perhaps because it has no looping construct.

To make the above possibly clearer, here's a simple example. We know that it is possible to list all Turing machines in some order. (The proof is not difficult and comes from Alan Turing himself). That means that we can associate every positive integer with some Turing machine, in such a way that every machine has a unique index.

Now, take the language $L_1 = \{a^i \mid i > 0\}$ (where $a^i$ means a string consisting precisely of $i$ $a$s). Since any string of $a$s is in $L_1$, the language is equivalent to the regular expression $a^+$.

The semantics of a program in  $L_1$ is simple: it does whatever Turing machine number $i$ would do, where $i$ is the length of the program. That's clearly a Turing complete regular language.

Then we define $L_2 = \{a^ib^i\mid i>0\}$ and $L_3 = \{a^ib^ic^i\mid i>0\}$, with the same semantics: in each case, program $i$ executes Turing machine number $i$. So these languages are also Turing complete, but $L_2$ is context-free and $L_3$ is context-sensitive.

Now, let's redefine the semantics. We'll define three languages with exactly the same syntaxes, but instead of executing Turing machine $i$, they print out $i$ in binary and then halt. These three new languages are still regular, context-free and context-sensitive, respectively, since the syntaxes have not changes. But none of them is Turing complete.

Bottom line: What a language means and how it is expressed are completely different concepts.

Any context-sensitive language is decidable and can be recognised by a Turing machine in NLINSPACE. Recognising a string from an arbitrary deterministic context-sensitive grammar is PSPACE-complete.

Moreover, just as context-free languages are equivalent to NPDAs, context-sensitive languages are equivalent to linear-bounded automata. Every CSL can be recognised by an LBA, and the language recognised by any LBA is a CSL.

All of the above is fairly standard (since it's type-1 on the Chomsky hierarchy) and covered in any decent textbook on languages and automata.


Algorithm for finding best combination of elements Say I have a very large, arbitrary number of variables, each of which I can assign to be type A, B, or C.

The types come with expenses: Type A's are the least expensive, and C's are the most expensive, but their expense varies from variable to variable.
For example {A, C, C} may actually be more expensive than {C, A, A} if that first variable happens to be worth more, but we won't know how much the total cost is until we assign the types and run the program.

Also we don't want to go below a certain given total expense (can't make all A's), but get as close as possible to it.

I am trying to minimize the total expense while staying above the threshold. The search space (permutations of variable types) is too large to try all combinations.

Someone recommended sampling via Monte Carlo method earlier.
How can the Monte Carlo method, or Markov-Chain Monte Carlo, be applied to such a problem to find the optimal combination of parameters?
Could a genetic algorithm be used effectively?

You normally need to know what heuristic function you have.

Usually, when you use simulated annealing, you don't find a maximum score (or combination that gives the maximum score). What you do is trying to get a score that is better than the current score that you have.

Note that, I find it very strange when you say you want to use simulated annealing for discrete optimization problem like the one you mention. When your problem is discreet, how do you do differential? Thus, how do you know which direction you should proceed with gradient ascent/descent?

There are cases in which a seemingly discreet optimization problem is actually a continuous one in which you can use a customized and modified gradient ascent/descent with an optional simulated annealing. I will refrain from comment further in this particular case.


Finding a Hamiltonian path in this graph family Given a directed graph $G = (V, E)$, you have been told that a Hamiltonian path $p_0p_1\ldots p_V$ exists with the property that for each edge $p_ip_j$ that is not part of the Hamiltonian path, $i > j$.

Find any Hamiltonian path.

It is not too hard to find an $O(|V||E|)$ solution to this problem: for every vertex with out-degree one, try starting a BFS from this vertex. If ever there is more than one vertex that could be expanded next in the BFS, give up and try another vertex.

I am not necessarily looking for a more efficient solution than this (though that would be nice), but I'm having trouble finding literature on this type of graph (in general, it seems very hard to look up literature on a family of graphs you do not know the name of).

Do you know where I can find out more about this graph family, or other graph families that involve guaranteeing the existence of a Hamiltonian path/cycle with interesting properties?

The class of graphs that contain a Hamiltonian cycle is known as Hamiltonian graphs. Being Hamiltonian doesn't really imply much: a wide range of well-known graph parameters (diameter, treewidth, chromatic number, ...) can still be unbounded. At least partly, this is the reason there aren't many non-trivial subclasses of Hamiltonian graphs known.

As an example, every 2-connected $(P_6,K_{1,3})$-free graph is Hamiltonian (see e.g., [1]). Further, [1] also cites some conjectures which claim that every 2-tough graph is Hamiltonian, or that every 4-connected $K_{1,3}$-free graph is Hamiltonian.

On the algorithmic side, even recognizing Hamiltonian graphs is of course well-known to be NP-complete. That is, recognition means the problem of deciding whether a given graph is Hamiltonian or not. Also, because many structural parameters remain unbounded, many classical problems also remain hard for Hamiltonian graphs (as there is no clear algorithmic foothold to exploit).

You might also enjoy Hypohamiltonian graphs, which are "almost Hamiltonian".

[1] R. Faudree, E. Flandrin, Z. Ryjacek. Claw-free graphs - a survey. Discrete Math. 164 87-147 (1997)

"I'm having trouble finding literature on this type of graph"

A good book recommended by universities is Discrete Mathematics and It's Applications by Kenneth H. Rosen. You can find the chapter on graphs (Euler and Hamilton paths) on page 666.


Mathmatical way to represent an image kernel? How to represent the calculation in this image mathematically?

For example: With the discrete convolution
$(f * g)[n]\ \stackrel{\mathrm{}}{=}\ \sum_{m=-\infty}^\infty f[m]\, g[n - m]$
and Fourier transform.

Applying the filter corresponds to two-dimensional convolution:
$$
(f \ast g)(x,y) = \sum_{i=-\infty}^\infty \sum_{j=-\infty}^\infty f(i,j) g(x-i,y-j).
$$
In our case, $f$ is the filter, $g$ is the image, and $f \ast g$ is the filtered image. Since the support of $f$ (the number of non-zero entries) is finite, the sums in question are finite, and the convolution is well-defined. More explicitly, we have $f(0,0) = 5$, $f(-1,0) = f(1,0) = f(0,-1) = f(0,1) = -1$, and $f(i,j) = 0$ otherwise.

Edit 1: Here is another way of viewing it. This time, $f$ is the image and $g$ is the filter, defined by $g(0,0) = 5$, $g(-1,0) = g(1,0) = g(0,-1) = g(0,1) = -1$, and $g(i,j) = 0$. The same formula for filtering, $f \ast g$, works before, since $f \ast g = g \ast f$. In other words, the filtered image $h$ is given by the formula
$$ h(x,y) = \sum_{i=-\infty}^\infty \sum_{j=-\infty}^\infty g(i,j) f(x-i,y-j). $$

Edit 2: We can rewrite the convolution as a product of generating functions. Suppose the original image is given by
$$ F = \sum_x \sum_y f(x,y) X^x Y^y. $$
The filter $G$ in your case is given by
$$ G = 5 - X - X^{-1} - Y - Y^{-1}. $$
Filtering the image corresponds to the multiplication $H = FG$, and the filtered image $h$ can be extracted as
$$ H = \sum_x \sum_y h(x,y) X^x Y^y. $$

Edit 3: Going back to the notation of Edit 1, in terms of the two-dimensional Fourier transform, we have
$$ \hat{h} = \hat{f} \hat{g}, $$
where the multiplication on the right is pointwise. So filtering corresponds to multiplying each Fourier coefficient by some fixed amount, which depends on the filter.

Edit 4: In this particular case, the relation between the original image $f$ and the filtered image $h$ is
$$ h(x,y) = 5f(x,y) - f(x-1,y) - f(x+1,y) - f(x,y-1) - f(x,y+1). $$

Edit 5: The image you posted handles the boundary issue by extending the first and last rows and columns past the boundary. For example, $f(x,-1) = f(x,0)$, $f(-1,y) = f(0,y)$ and $f(-1,-1) = f(0,0)$.

it seems a classical image filtering technique, should be in textbooks, try fundamentals of digital image processing by Anil K Jain

the depicted filter seems like a discrete laplacian (altough the central number is 5 instead 4), have a look at
http://en.wikipedia.org/wiki/Discrete_Laplace_operator


Are there automatic transformation of grammar algorithms? From time to time you can write a grammar that creates shift/reduce conflict (for example) but after reading the grammar you notice that if you rewrite the productions the conflict will go away, despite the fact that the rewritten grammar is obviously equivalent and accepts exactly the same language.

Are there some automatic transformations of the grammar to avoid conflict? Something (just an analogy) as left recursion elimination in LL parsers?

For example, here is a trivial example of two grammars:

...
deco_symbol -> anon_symbol | named_symbol;
...

and

...
symbol -> anon_symbol | named_symbol;
deco_symbol -> symbol;
...

For LR(1) parser such indirection can be crucial and second form can introduce conflicts (it did in real life).

Since I asked this question I wrote automatic removal of identity production and it helped, so this would be the first type of transformation I know it is helpful. Now I am testing wrapper production removal and empty productions as well.

If you are willing to implement an lr(k) algorithm then yes, there are transformations that you should do in order to obtain a correct parser:
first of all, you have to build an augmented grammar adding production S'->S, making S' the new axiom. This is actually not always necessary, but it allows you have a standardized procedure for all the productions so let's pretend it is for now. After that, you should also eliminate useless symbols from the grammar with the apposite algorithm.

If you execute lr(k) parsing under these hypothesis for the grammar, you should not have conflicts.

----- EDIT ----- I hope this will be of some help :)

An lr(k) parser builds a parsing table over a given grammar G. These parsers are able to recognize words generated from grammars which are deterministic context free and in lr(k) form. If a conflict occurs, then the language generated by the given grammar cannot be parsed using that table and the grammar is not a lr(k) grammar.

However, one can show that a language L is deterministic context free iff there exists k >= 1 such that L is generated by an lr(k) grammar.

I might be wrong but what I concluded from these notions is that if the grammar is lr(k) no conflicts should occur, and one of the definitions of a lr(k) grammar is:

The definition of lr(k) grammars states that the axiom must not occurr on the right hand side of any production, and should this is not be respected one needs contruct the augmented grammar first, using S' as new axiom and adding the only production S'->S. For further definitions of lr(k) grammars or a clarification of what I wrote, I advise to read The Theory of Parsing, Translation and Compiling (around page 370), since I fear I don't have the preparation to answer all questions.


Is there a canonical definition of “pure” function? StackOverflow pointed me here, so the question might be a bit in a layman's terms.

Wikipedia defines pure functions as

  In computer programming, a function may be described as a pure
  function if both these statements about the function hold:

  The function always evaluates the same result value given the same
  argument value(s). The function result value cannot depend on any
  hidden information or state that may change as program execution
  proceeds or between different executions of the program, nor can it
  depend on any external input from I/O devices.
  Evaluation of the result does not cause any semantically observable side effect or
  output, such as mutation of mutable objects or output to I/O devices.

However it does not seem to cite any sources -- so it is hard to say whether this is an accepted definition, or who defined it this way.

When I look at what the languages do when they include a syntax/annotation for "pure" functions, there are quite a few different approaches:

In D the only limitation is non-mutation of global state. "Pure" functions can mutate its arguments.
In GCC there are two types of "pure": pure (no side-effects, but can read global state) and const (stricly pure as per wikipedia definition).
In C#, it is defined as "does not make any visible state changes" (whatever that is).
Haskell follows the Wikipedia definition.

So my question is: is there a canonical definition of pure function?
And if there is, what is its source?

As noted in this paper Imperative Functional Programming, (1993) by Peyton-Jones and Wadler (among the group of researchers that created Haskell):

  We focus on purely-functional solutions, which rule out side effects,
  for two reasons. Firstly, the absence of side effects permits
  unrestricted use of equational reasoning and program transformation...

the focus is on absence of side-effects to enable program transformations (i.e compiler optimisations).

What are side-effects? This paper in turn points to Integrating functional and imperative programming (1986) by Gifford and Lucassen, which mentions four types of effect classes: Pure, Function, Observer and Procedure. So, the term "pure function" derives from this paper.

  a PURE is referentially transparent: it does not cause side-effects,
  its value is not affected by side-effects, and it returns the same
  value each time it is evaluated.

Note, however, that Peyton-Jones and Wadler mentioned shortcomings in this approach. Worth noticing, they say, is the programming language Clean that uses linear types to introduce side-effects in a safe manner (i.e. safe for the compiler). Basically, it threads the World as a variable in all I/O related functions, including the main entry point.

With that, it is possible to have a pure functional language interacting with the world and having side-effects (I/O, the OS, the Windowing system, etc), contradicting partially your wikipedia definition. One can in fact say that Haskell has Clean as one of its influencers; although it departs from linear types and uses another type-level construct (monads) to guarantee linearity, i.e. a single-reference at all times.

Wikipedia's definition is canonical.  The crucial two requirements are:

The return value and behavior of the function is a deterministic function of the arguments that were explicitly passed to the function.
An invocation of the function has no observable side effects.

Strictly speaking, D and gcc shouldn't be using the word "pure" the way they do; it's an abuse of standard terminology.


What are the characteristics of a $\Theta(n \log n)$ time complexity algorithm? Sometimes it's easy to identify the time complexity of an algorithm my examining it carefully. Algorithms with two nested loops of $N$ are obviously $N^2$. Algorithms that explore all the possible combinations of $N$ groups of two values are obviously $2^N$.

However I don't know how to "spot" an algorithm with $\Theta(N \log N)$ complexity. A recursive mergesort implementation, for example, is one. What are the common characteristics of mergesort or other $\Theta(N \log N)$ algorithms that would give me a clue if I was analyzing one?

I'm sure there is more than one way an algorithm can be of $\Theta(N \log N)$ complexity, so any and all answers are appreciated. BTW I'm seeking general characteristics and tips, not rigorous proofs.

Your archetypical $\Theta(n \log n)$ is a divide-and-conquer algorithm, which divides (and recombines) the work in linear time and recurses over the pieces. Merge sort works that way: spend $O(n)$ time splitting the input into two roughly equal pieces, recursively sort each piece, and spend $\Theta(n)$ time combining the two sorted halves.

Intuitively, continuing the divide-and-conquer idea, each division stage takes linear time in total, because the increase in the number of pieces to divide exactly matches the decrease in the size of the pieces, since the time taken by division is linear. The total running time is the product of the total cost of a division stage multiplied by the number of division stages. Since the size of the pieces is halved at each time, there are $\log_2(n)$ division stages, so the total running time is $n \cdot \log(n)$. (Up to a multiplicative constant, the base of the logarithm is irrelevant.)

Putting it in equations (), one way to estimate the running time $T(n)$ of such an algorithm is to express it recursively: $T(n) = 2 T(n/2) + \Theta(n)$. It's clear that this algorithm takes more than linear time, and we can see how much more by dividing by $n$:
$$ \frac{T(n)}{n} = \frac{T(n/2)}{n/2} + \Theta(1) $$
When $n$ doubles, $T(n)/n$ increases by a constant amount: $T(n)/n$ increases logarithmically, or in other words, $T(n) = \Theta(n \log n)$.

This is an instance of a more general pattern: the master theorem. For any recursive algorithm that divides its input of size $n$ into $a$ pieces of size $n/b$ and takes a time $f(n)$ to perform the division and recombination, the running time satisfies $T(n) = a \cdot T(n/b) + f(n)$. This leads to a closed form that depends on the values of $a$ and $b$ and the shape of $f$. If $a = b$ and $f(n) = \Theta(n)$, the master theorem states that $T(n) = \Theta(n \log n)$.

A generic example of a loop (not an algorithm per se) that runs in $O(n \log n)$ is the following:

for (i = 0; i < constant; i++){
    for(j = 0; j < n; j++){
        // Do some O(1) stuff on the input
    }
}

// Alternative Variant:
for (i = 0; i < constant; i++){
    for(j = n; j < constant; j++){
        // Do some O(1) stuff on the input
    }
}

(note that this nested loops are not $O(n^2)$. Also note that it isn't divide-and-conquer nor recursive.)

I can't give a concrete example of an algorithm that uses this loop, but it comes up often when coding custom algorithms.


Question concerning subset sum problem: split into 3 equal subsets Task: Given an array $arr[a_1, a_2, \dots, a_n]$ of integers, let $A = \sum\limits _{i\in \{1, 2, \dots, n\}}a_i$.  Determine whether it is possible to spit $arr[]$ into 3 subsequences of equal sum, i.e. if $s_1 =s_2 = s_3 =\dfrac{A}{3}$ where $s_1 ,s_2 , s_3$ denoted the splitted arrays.
My thoughts: I will first examine whether there exists some sequence of numbers that sums up to $\dfrac{A}{3}$ via dp, then I will backtrack those numbers, "throw them out" (meaning I won't consider them anymore), and proceed with the remaining numbers of the array. After doing this a second time I examine whether the numbers left sum up to $\dfrac{A}{3}$ and return true if this is the case. Even though this sounds valid to me I somehow doubt the correctness of this.
Recurrence of DP: $dp[i][j] = dp[i-1][j-a_j] \text{ OR } dp[i-1][j]$
$dp[]$ is a boolean array of dimension $n \times\dfrac{A}{3}$.

I don't think the proposed algorithm is correct. It may happen that the first solve for $A/3$ picks a set of numbers that makes it impossible to split the remainder into equal halves. Consider this example:

Given the set of numbers $\{1,1,3,3,3,4,8,10\}$, which sum to $A=3*11$
Assume that the first DP picks $||\{1,1,3,3,3\}||_1=11$
It is impossible to split the remaining set $\{4,8,10\}$ into equal halves.

Here's a recursive function in pseudocode instead which computes what you need in a single step:
bool CanBuild3EqualSums(int sumA, int sumB, int sumC, int[] numbers)
{
    if(numbers is empty)
        return sumA == sumB && sumB == sumC;
    else
        return CanBuild3EqualSums(sumA + numbers[0], sumB, sumC, numbers.WithoutFirst())
            || CanBuild3EqualSums(sumA, sumB + numbers[0], sumC, numbers.WithoutFirst())
            || CanBuild3EqualSums(sumA, sumB, sumC + numbers[0], numbers.WithoutFirst())
}

This is a pure function (without side-effects). Add memoization and you'll end up with a DP algorithm. Of course, there are many other ways to formulate this. There is some potential for a more efficient, practical implementation:

You could pass the index of the next number, instead of the whole array.
You could get rid of sumC, and compute when needed, based on sumA and sumB
If you have small values, a bottom-up formulation might be more efficient.

Here my solution:
    boolean 3_Partition(int arr[]) {
        if (arr == null)
            return false;
        int sum = Arrays.stream(arr).sum();
        if (sum % 3 != 0)
            return false;
        int n = arr.length;
        boolean dp[][][] = new boolean[n+1][sum = sum / 3 + 1][sum];
        for (int i = 0; i < n+1; i++) {
            for (int j = 0; j < sum; j++) {
                for (int k = 0; k < sum; k++) {
                    if (i == 0 ) dp[i][j][k] = false;
                    else if (j == 0) dp[i][j][k] = true;
                    else if (k == 0) dp[i][j][k] = true;
                    else  dp[i][j][k] = j >= arr[i-1] && k >= arr[i-1] ? dp[i - 1][j - arr[i-1]][k] || dp[i - 1][j][k - arr[i-1]] || dp[i - 1][j][k]
                          : j >= arr[i-1] ? dp[i - 1][j - arr[i-1]][k] || dp[i - 1][j][k]
                          : k >= arr[i-1] ? dp[i - 1][j][k - arr[i-1]] || dp[i - 1][j][k] : dp[i - 1][j][k];
                }
            }
        }
        return dp[n][sum-1][sum-1];
    }


How to prove the existence of a number which cannot be written by any algorithm? I have the problem:

  Show that there exists a real number for which no program exists
  that runs infinitely long and writes that number's decimal
  digits.

I suppose it can be solved by reducing it to the Halting problem, but I have no idea how to do so.

I would also appreciate links to similar problems for further practice.

As Sebastian indicates, there are only (infintely but) countably many programs. List them to create a list of programs. The list is (infinitely but) countably long. Each program generates one number in R. From that we can create an (infinite but) countable list of numbers in R. Now we can apply Cantor's diagonal argument directly to prove that there still must be other numbers.

By the way if the algorithm has (finite) arguments, you can just rewrite that as a "longer" list of programs where each program doesn't have any arguments.

With regard to your comment "What if real numbers are allowed as argument", then the question's premise is wrong: all numbers in R can then be generated. If someone finds a number, say 皮 and claims it cannot be computed, we have the following "algorithm":

func(number):
    return number

and call func(皮)

A point moves in a path by the funcion y = 2x. When the abscissa is a non computable number, there is no way for the Point to compute its path, but we know it goes on. So non computable numbers can exist at all.


What are the minimum memory requirments a microprocessors must have to perform any calculation? Please excuse my ignorance in low level things. A lot of the written below might be very wrong.

As far as I understand (and I might be very wrong), there are two types of memory locations a microprocessor can have: registers and stacks.

My question is what is the most basic set of memory locatiins a microprocessor must have to perform an arithmetic calculation of unlimited complexity, such as : 12 / (11 / (4 - 7) * 31) + 8.

For example one register is obviously not enough. What about three registers? Or one stack? Or a stack and a register? Given e.g. one stack and a register, can the CPU perform any calculation?

The CPU should be able to perform any calculation like in the example shown above.

unlimited complexity?

That requires unlimited memory, after all - the numbers must be stored somewhere, and the place to store them is always in memory.

So you need 1 memory 'cell' for each number, and another for each operation. You also need a counter to keep track of the next number or operation. Add to that a register to perform the calculation (only 1 is needed as you can use it to store the results in-place. In reality you'll use another register to notify you of errors such as overflow or division by zero).

Or to put it another way: you need sufficient RAM, an accumulator and a program counter. You can get away without the counter if the memory are streamed in sequentially on a specialist computing machine (eg on tape as per Euphoric's comment).

"any" calculation, well that cannot be answered with a finite solution, but so long as the calculation can be resolved combinatorially then you dont need any memory at all.  If you cant do it combinatorially  then you need some latches memory...But you will NEVER actually need "memory" as in ram to PERFORM math operations.  You might like to have some memory in order to feed the math operation and have a place to put the result, but switches and lights/leds work just fine as well...

You have to be very specific about he processor and the set of operations it supports and the choices for source and destination for those operations.  That determines quite heavily how much memory, registers, stack, etc are required to perform a specific operation, since there is no possible answer to this question for "any" operation.


Time Complexity of Rabin-Karp matching algorithm I asked a question on Rabin-Karp Searching algorithm here, which I am reading from the book "Introduction to Algorithms" 3rd edition Cormen et al..
After reading few para of the section on Rabin-Karp, I got some more confusions:
In the third paragraph the authors say that the if we could find p  (decimal value of pattern P[1....m] )  in  time O(m) and all the ts values (i.e decimal value of length-m sub-string T[s+1....s+m], s=0,1,2,,,,n-m) in time O(n-m+1),  then we could determine all valid shifts s in time O(m) + O(n-m+1) by comparing p with each of the ts values.
How is this possible? O(m) is for finding p, O(n-m+1) is for finding all ts, so total pre-processing time so far is O(m) + O(n-m+1). This is the total pre-processing time; the comparison has yet to start, I have to spend some extra $ for doing comparison of a decimal p with each of the (n-m+1)-ts values.
1-Then why the authors say in the first para that the pre-processing time is O(m)? Why it is not O(m) + O(n-m+1) which include processing time of p and all ts values?
2- Now if we talk about worst case matching time, what should be that? So in the worst my decimal number p (already calculated ) will be compared with each of the another (m-n+1) decimal numbers, which are the values of ts (already calculated, no extra cash needed for doing this job now ). The worst case is when I am most unlucky and I have to compare every value of ts with p. Right?
Based on my understanding,(if I am right) the worst case matching time should be O(m-n+1) and not O((m-n+1)m) as claimed by the authors in the first para. For example let us say my Pattern is P[1...m]=226 and Text is T[1....n]=224225226. so  my p is decimal 226, and ts is decimal value of T[s+1, s+2, s+3], for s=0,1,2...6 as n=9, and m=3. The ts values will be as follows:

s=0 => T[224]=> ts=224
s=1 => T[242]=> ts=242
s=2 => T[422]=> ts=422
s=3 => T[225]=> ts=225
s=4 => T[252]=> ts=252
s=5 => T[522]=> ts=522
s=6 => T[226]=> ts=226

Now you will be comparing p=226 with all these values. So are you not making n-m+1=7 comparisons to achieve search for 226 in T, and not (n-m+1)m =7 x3=21? So the worst case time should be O(n-m+1) and not O((n-m+1)m).
In short I understand that:

Total pre-processing time = O(m) + O(n-m+1) (including for both p and
all the ts values)
Total matching time in worst case = O(n-m+1)

Where I am making mistake?

As pointed out by vzn above, the wiki article has all the details you are looking for.

Firstly, what is pre-processing and what is the online runtime, depends on what is remaining constant and what is varying. For example, if we are given some fixed text and are asked to match various small strings with that text, pre-processing would be hashing the text.

In this case, let us say we have only one string to be compared with one text, to avoid confusion about pre-processing. The operations that we need to perform are

Hash for string to be searched for ($p$) = $O(m)$
Hash for each $m$-sized substring in the text ($T$) (assuming rolling hash) = $O(n-m+1)$
Number of hash comparisons (one per each $m$ sized substring in $T$) = $O(n-m+1)$
If there are $r$ matches in the hashes, then we compare each of those substrings of $T$ with $p$ (each comparison being $O(m)$) = $O(rm)$

But in worst case, the number of matches in hash can be as large as $n-m+1$. So worst case complexity will be $O(m(n-m+1))$.

/*   Pattern string length is m
 *   Source text length is n
 *   Find the index of the first matched substring in text
 *   Runtime:
 *
 *
 *      int hashOfPattern = hash(pattern string);           //  m.
 *      for(int i=0; i<= n-m; i++){                         //  n-m+1.
 *        int currentStringHash = hash(current substring);  //  1. using rolling hash method,
 *        if( currentStringHash == hashOfPattern){
 *           if(current substing equal to pattern string){
 *                                                          //  m. only execute once.
 *                                                          //  Assume it is an effective rolling hash method good enough
 *                                                          // to avoid hash collisions.
 *              return i;
 *           }
 *        }
 *      }
 *   In worse case the whole runtime is m + (n-m)*1 + 1*m = n+m
 *   it is O(n+m)
 *
 *   If the hash function is not effective. The worse case runtime is O(nm).
 */


How is this formula for dynamic array reached? I am reading through Skiena's "The Algorithm Design Manual". He analyses the number of copy operations performed in a dynamic array.

  "Suppose we start with an array of size 1, and double its size from $m$ to $2m$ each time we run out of space. This doubling process involves allocating a new contiguous array of size $2m$, copying the contents of the old array into the lower half of the new one. The apparent waste is in the recopying of the old contents, on each expansion."

Skiena then asks:

  "How many times might an element have to be recopied after a total of $n$ insertions?".

He then gives a formula for calculating the total number of movements $M$, for $n$ insertions, which is

$$\mathbf{M}=\sum_{i=1}^{\log n} i\cdot\frac{n}{2^i}.$$

His explanation is:

  "Well, the first inserted element will have been recopied when the array expands after the first, second, fourth, eighth, ...insertions. It will take $\log_{2}n$ doublings until the array gets to have n positions. However, most elements do not suffer much upheaval. Indeed, the $(n/2 + 1)$st through $n$th elements will move at most once and might never have to move at all."

But I really don't understand how he draws the formula from that. Can anyone help me understand how he reaches it? Mainly what I can't understand is why he is multiplying $\frac{n}{2^i}$ by $i$.

Let's look at the moment just after we copy the array to insert element $2^k + 1$, so we're doubling the array size from $2^k$ to $2^{k+1}$. There are $n = 2^k$ elements in the array at this moment.

The first term in the sum is $1 \cdot n/2$, representing the fact that $n/2$ elements (namely, elements $(n/2+1), \ldots, n$) have been copied exactly once (just now!).

The next term is $2 \cdot n/4$. The previous $n/4$ elements - that is, elements $(n/4) + 1, \ldots, n/2$ - will have been copied exactly twice, once just now and once when we expanded the array from size $n/2$ to $n$.

The next term is $3 \cdot n/8$. The previous $n/8$ elements will have been copied three times: now, at the last expansion and at the second-to-last expansion when we expanded from size $n/4$ to $n/2$. You can probably see where this is going by now.

The thing to remember is that each element gets copied every time the array expands after the element in question has been inserted, and the copies happen every time the size exceeds a power of two.

Mainly what I can't understand is why he is multiplying $\frac{n}{2^i}$ by $i$.

I believe this is a mistake in the book.
Let's take a look at an example (taken from https://softwareengineering.stackexchange.com/questions/119151/how-many-copies-are-needed-to-enlarge-an-array)

Array of 1 element.
Let's call it array-1.
+--+
|a |
+--+

Double the array (2 elements).
Let's call it array-2.
+--++--+
|a ||b |
+--++--+

Double the array (4 elements).
array-4.
+--++--++--++--+
|a ||b ||c ||c |
+--++--++--++--+

Double the array (8 elements).
array-8.
+--++--++--++--++--++--++--++--+
|a ||b ||c ||c ||d ||d ||d ||d |
+--++--++--++--++--++--++--++--+

Double the array (16 elements).
array-16.
+--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--+
|a ||b ||c ||c ||d ||d ||d ||d ||  ||  ||  ||  ||  ||  ||  ||  |
+--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--+

So, accordingly to the book number of copyings is governed by the following formula:
$M = 1 \cdot 8 + 2 \cdot 4 + 3 \cdot 2 + 4 \cdot 1$

The first term of the sum $1 \cdot 8$ is for copying array-8's items into array-16.

We copy the array-4's items (a, b, c, c) twice. Once from the array-4 to array-8. And then when copying array-8's items to array-16 we copy (a, b, c, c) items for the second time. Accordingly to the book, hence the second term: $2 \cdot 4$.

But now notice that the $1 \cdot 8$ term already takes into account copying of (a, b, c, c) items from array-8 to array-16. Consequently the $2 \cdot 4$ term must not include the $2$ multiplier.

The same logic applies to all the other terms. And so multiplying by $i$ is a mistake.


Converting a digraph to an undirected graph in a reversible way I am looking for an algorithm to convert a digraph (directed graph) to an undirected graph in a reversible way, ie the digraph should be reconstructable if we are given the undirected graph. I understand that this will come in expense of the undirected graph having more vertices but I do not mind.

Does one know how to do this or can suggest any references? Thanks in advance.

Update: Regarding the answer of AdrianN below. It might be a good starting point but I don't think it works in its current form. Here is an image of why I think it doesn't:

Update after D.W.'s comment: I consider the vertices of the graphs to be unlabeled. If a solution involves labeling the vertices (like AdrianN's does), then it should give the same (isomorphic) undirected graph no matter how the labeling is done. My definition of "isomorphic" for graphs with labeled vertices is that there is a permutation of the labeling that relates the two graphs, but I am not sure of the exact definition for unlabeled graphs...

David Richerby's answer (which was accepted) is good.

I followed his instructions on a simple example digraph, and hope it helps someone.

(I would have posted this as a comment on David's answer, but I do not have the reputation points required.)

What about the identity function ? I.e. every digraph can be seen as a
undirected, bipartite graph with equal sized partitions and vice versa.


Searching related works for papers How do you search related works for your papers? To be concrete I have implemented few techniques of indirect call promotion for pure C and want to share my results. But at first I want to understand if there are some existing papers about it.

I searched with Google, Google shcolar, citeseerx, microsoft academic search, acm library and semanticscholar. I found only papers on C++ devirtualization but not for pure C. I searched the papers referenced to those what I found but I still did not found anything about pure C.

Can I think my research will be uniqe and interesting for scientific community or I just failed to find existing papers?

This site may also offer you a resource for locating content similar to your paper. Most academic institutions and public libraries have free access to these sorts of research tools to look for published work in selected areas of research. Good Luck.

Click Here


Proving $(a+b)^* = b^*(ab^*)^*$ equationally I am new to automata theory and have a problem in understanding equivalence of regular expressions, though I can go for the construction procedure of minimized DFAs to prove that both are equal.

I need to prove the following property using different Kleene star properties:

$$(a+b)^* = b^*(ab^*)^*$$

A report by Aceto contains an axiomatization of the equational theory of regular expressions, called "classical" by Conway (Table 1 on page 5). One of the axioms is very similar to what you're after: $(a+b)^* = (a^*b)^*a^*$. Using these axioms, we can derive your identity as follows (using associativity (C3, C10) for free):
$$
\begin{align*}
(a+b)^* &= (b+a)^* && C2 \\
&= (b^*a)^*b^* && C11 \\
&= (\epsilon+b^*(ab^*)^*a)b^* && C12 \\
&= b^* + b^*(ab^*)^*ab^* && C9 \\
&= b^*(\epsilon + (ab^*)^*ab^*) && C8 \\
&= b^*(\epsilon + \epsilon(ab^*\epsilon)^*ab^*) && C6,C7 \\
&= b^*(\epsilon ab^*)^* && C12 \\
&= b^* (ab^*)^* && C7
\end{align*}
$$

Applying kleen star on both side

((a+b)*) *= ( b * (ab*)*) *

But ((a+b)* )* = (a+b)* as we know (a*)* = a*

( b * (ab*)*) * = (b + (ab*))*  as we know (a+b)* =(a* b*)*

I can use b* as empty string as its redundant.

Even if we are using b* as empty string the expression gives all strings of a's and b's. So using b* wont add new strings to the set.

So we can say

(b + (ab*))*= (b+a) * = (a+b)*

Proved


What is the language generated by a given grammar Given the grammar
  $s \to aSb \mid bSb \mid a \mid b$;
  what is the language generated by the grammar over the alphabet $\{a,b\}$?

When I was solving this question I was a bit confused
about  the language generated by this grammar. Would be set of all palindromes?
Or would the language generated by the above grammar be that of all odd length palindromes?

Is it possible that a palindrome generated by above grammar be of odd length only as there is no rule for $S \to \varepsilon$?

The language of this grammar is all strings of the form $wb^n$  where $w\in \{a,b\}^*$, and $|w| = n+1$. If I abuse the notation a bit, it is $\Sigma^{n+1}b^n$.

If perchance you mean $S \rightarrow aSa \ | \ bSb \ | \ a\ | \ b$, then the language contains all palindromic strings of odd length.

The strings accepted by language are {a, b, aaa, bbb, aba, bab, ..}.Therefore more specific answer is " All of these strings are odd length palindromes." Yes it is odd length because S doesn't go to epsilon.


call by name : how are clashing variables handled? In call by name : In general, the effect of pass-by-name is to textually substitute the argument expressions in a procedure call for the corresponding parameters in the body of the procedure.

Technically, if any of the variables in the called procedure clash with the caller's variables, they must be renamed uniquely before substitution.

ref : http://www.cs.sfu.ca/~cameron/Teaching/383/PassByName.html

Now consider the following code :

global int i = 100, j = 5;

void P(x)
{
    int i = 10;
    print(x + 10);
    i = 200;
    j = 20;
    print(x);
}

main()
{
    P(i + j);
}

Will the variable i declared in function P get renamed before execution ?
Which i ( global or local ) is accessed by x in print(x + 10) ?
Which i ( global or local ) will get updated by (i = 200) ?
What will be the output of the second print statement (220 or 120 ) ?

Programming languages do not "textually substitute" anything, that would be horribly inefficient. The "textual substitution" definition may be offered sometimes as a sort of textbook explanation, but it usually fails to capture all the details.

There are many techniques for dealing with the problem you describe. By the way, the problem is known as "variable capture" beacuse a binder "captures" a variable.

One possiblity is to eliminate all variable names and use de Bruijn indices instead. Substitution still requires a bit of work, namely shifting of indices, but at least one does not have to generate new names.

Another possibility is to create closures. These are used for evaluation of functions (I did not say "application"!), but in a call-by-name language we could use them for any expression. Briefly, when we evaluate P(i + j) in your code, we create a closure (η, i + j) where η tells us what the values of variables are at that point in the execution (so concretely, η would be something like i ↦ 100, j ↦ 50, P ↦ ..., main ↦ ....). When P actually needs the value of its argument, we evaluate i + j in the environment η (and not in the environment of P), so that i + j gets evaluated in the "old" environment.

There are still many other techniques for avoiding variable capture. Haskell compiles to a spineless tagless G-machine, or at least it used to.

Call by name has widely gone out of fashion. I have seen it in Algol 60, can't remember if it was in Algol 68, and I thought I hadn't seen it since, although the technology needed is in common use now again with closures etc. , and auto closures in Swift are actually the same as call by value parameters.

You wouldn't do this by name substitution. You would do this in your example by creating a chunk of code that adds the global int i and the global int j, and passing that code to P, where it can be executed whenever needed.


Finding the flaw in a reduction from Hamiltonian cycle to Hamiltonian cycle on bipartitie graphs I'm trying to solve a problem for class that is stated like so:

  A bipartite graph is an undirected graph in which every cycle has even
  length.  We attempt to show that the Hamiltonian cycle (a cycle that
  passes through each node exactly once) problem polynomially reduces to
  the Hamiltonian cycle problem in bipartite graphs. We need a function
  $T:  \{\text{graphs}\} \to \{\text{bipartite graphs}\}$ such that $T$ can be computed in
  polynomial time and for any graph $G$, $G$ has Hamiltonian cycle iff $T(G)$
  has a Hamiltonian cycle. Let $T(G)$ be the bipartite graph obtained by
  inserting a new vertex on every edge. What is wrong with this
  transformation?

I think the problem with the transformation is that for $T(G)$ you need to insert an edge between each pair of vertices and not just insert a new vertex on every edge. I'm actually a bit stumped by this one. Any advice would be much appreciated!

The problem is that a Hamiltonian cycle has to pass through all vertices: if the cycle in the original graph does not take some edge $e$, then the vertex you split $e$ with will not be taken if you take the same route. This means that the resulting cycle is not Hamiltonian.

Is it possible that the transformation is correct but pointless? Consider Barnette's conjecture:

  If a planar graph is bipartite and cubic but only 2-connected, then it may be non-Hamiltonian, and it is NP-complete to test Hamiltonicity for these graphs.

(possibly taken out of context - check back with the Wikipedia entry). Is it possible that all you are doing is reducing one known NP-complete problem to another known NP-complete problem?


is it possible to determine using a single depth-first search, in O(V+E) time, whether a directed graph is singly connected? I'm working on exercise 22.3-13 of CLRS (Intro to Algorithms 3rd edition):

  A directed graph $G = (V, E)$ is singly connected if the existence of a path from $u$ to $v$ implies that $G$ contains at most one simple path from $u$ to $v$ for all vertices $u, v\in G$. Give an efficient algorithm to determine whether or not a directed graph is singly connected.

Previous threads on this question are here and here. In that second thread, one of the answers links to a preprint by someone who corresponded with one of the authors of the book, and stated (in the abstract of the preprint) that the solution the authors intended was (if I'm understanding correctly) to call DFS-VISIT(G, u) (from p. 604 of CLRS) on each vertex $u$ of the graph, resetting all vertex colors back to white (to indicate unvisited) in between calls, and return false (for "not singly connected") whenever a forward edge or cross edge is found, and returning true otherwise. This would take O(VE) time.

There seems to be some confusion in the answers and comments section of those threads: the above scheme is referred to as "calling DFS on every vertex". In fact, this is different from the DFS algorithm presented on p. 604 of CLRS, which calls DFS-VISIT on all unvisited nodes in the graph, without resetting the colors in between calls, which takes $O(V + E)$ time.

My question is, instead of doing what is stated in the preprint, which takes O(VE) time, is it sufficient to simply perform the ordinary $O(V + E)$ DFS on the graph, and return false (for "not singly connected") whenever a forward edge or a cross edge that is located entirely within a single DF tree is found? (As correctly pointed out in one of the comments in the second thread linked above, a cross edge within a single DF tree means the graph is certainly not singly connected, but a cross edge between two vertices in different trees does not necessarily mean so).

In other words, is it possible to have a non-singly connected graph, such that for some ordering of the adjacency lists, performing the DFS algorithm from p. 604 of CLRS will not find any forward edges or cross edges within individual trees, but possibly only cross edges between trees, if any?

I just realized, a single call to DFS is not sufficient, since the conjecture I asked about is not true. Here is a counterexample. Suppose DFS first visits all nodes in a tree rooted at $u$, and $v$ is a descendant of $u$. Then suppose an unvisited vertex $w$ has both $u$ and $v$ in its adjacency list. Then, $w$ would not be in the same tree as $u$ and $v$, but there would be cross-tree edges $(w, u)$ and $(w, v)$, and hence there would be more than two paths from $w$ to $v$, making the graph not singly connected.
However, we cannot modify the algorithm to also look for cross edges between trees, since if we removed the $(w,u)$ edge from the example above, then it's still possibly for it to be singly connected even though there's a $(w,v)$ cross edge.

You can check if there is already a path between u and v, using their finishing and discovery time (d[u] u is an ancestor of v). If their times are disjoint, then they are on different branches and not reachable from one another, so there shouldn't be more than one path between w and u or w and v.


Preparing precedence graph from fork and join code I was referring to this page which defines fork, join and precedence graph as follows:

  When the statement Fork(label) is executed by a thread of control, a second thread of control is started from the statement with the specified label. The two threads execute concurrently.
  When the statement Join(count) is executed, where count is an integer variable, the value of count is decremented. If the resulting value is positive the executing thread is terminated.
  A PRECEDENCE GRAPH is a directed, acyclic graph where nodes represent sequential activities and where arcs, say from node i to node j, require that activity i complete before activity j can start.

Base upon this I have been asked to draw precedence graph for a code containing fork and join constructs. For simple code, I can do. Also once given both code and precedence graph, I can see how the two correspond to each other. However when the code gets little bit complex, it becomes difficult to prepare precedence graph for me. Also doing reverse, from precedence graph preparing fork-join code is almost always difficult for me.

Can anyone give me intuitive stepwise procedure explaining how to obtain fork-join code from any given precedence graph?

Can we take example of following graph to apply the steps and get the fork and join code:

x=2;
y=2;
z=2;

p1;

Fork L1  ; start p2

Fork L2 ; start p3

goto L3 ; stat P4

L1: p2;

fork L3 ;start p4;

goto L5

L3: join (x)

P4;

L4:  join(y)

s6;

Quit();

L2 : P3;

L5:  join(y)

 P5;

 goto L4


Proving an algorithm wrong So I have this algorithm that outputs the largest value of an array:

Input: $A[1,\dots,n]$, $n\geq 1$
Output: Largest value of an array

Maximum (A)
  m = A[1]
  i = 1
  while i < n
    if A[i+1] > A[i]
      m = A[i+1]
    i = i+1
  return m

I have to prove this algorithm wrong and I'm confused how to do that, because to me the algorithm seems correct. Any advice on how to do this are very much appreciated.

Consider the input $100,0,1$.

As a follow-up, identify the bug, and correct the algorithm.

Two points which will prove the algorithm is wrong

Array type starts with the zeroth element, in that case, A[0] will
be eliminated even if it's the highest number. So, m should start with
A[0], not A[1].
The comparison of each element should be made with the maximum number
element(m) and not with its previous element. So, it
should be A[i+1] > m, not A[i+1] > A[i]


Minimum number of shopping trips for a group of people to buy presents for each other We have a group of $n$ people. We are given a list of who must buy presents for whom within the group. Each person might need to buy/receive any number of presents, or possibly none at all. In a shopping trip, a subset of the people travel together to the same store, and buy presents for anyone who is not present at the store. They may not buy presents for someone else on the same shopping trip because then it wouldn't be a surprise. A person may go on multiple shopping trips. We want to minimize the total number of shopping trips required for everyone to buy all the presents they need.

As an example, consider the case where there are 5 people, and each must buy presents for every other person in the group. Let the people be numbered 1 to 5.  This can be done in 4 shopping trips, as shown:

Trip 1: 1, 2, 3 go shopping
Trip 2: 1, 4, 5 go shopping
Trip 3: 2, 4 go shopping
Trip 4: 3, 5 go shopping

How would I go about solving this problem? It is obvious that the input can be represented by a directed graph, but I don't know where to go from there. Someone brought up the biclique cover problem, but while similar, it does not answer this question.

We can think of the input as a directed graph $G$ on $n$ vertices, where the edge $(u,v)$ means that person $u$ must buy a present for person $v$.   The goal is to find a set of bicliques $(S_1,T_1),\dots,(S_k,T_k)$ such that $k$ is minimal and the edge set $E$ of the graph is a subset of $\cup_i (S_i \times T_i)$.  Also, in extending the definition of bicliques to a directed graph, a biclique $(S_i,T_i)$ only contains edges which map $S_i$ to $T_i$.  This differs from the biclique cover problem in that we don't require each biclique to be a subgraph of $G$ (we don't require $S_i \times T_i \subseteq E$ for each $i$).

Specifically, I will accept an answer that either:

Demonstrates that this problem is NP-hard or
Presents a polynomial time algorithm that answers this question exactly (no approximants or upper bounds)

For the record, I did not see this problem anywhere, I am just wondering about it for my own curiousity.

I can see how to reduce this problem to Graph Colouring, which gives you a tool for solving the problem (for small instances!), but not yet how to reduce in the other direction (which would establish NP-hardness).

The basic idea is to build a graph that contains a vertex for every purchase, and an edge between any two purchases that cannot occur on the same trip; we then look to group the purchases into the smallest possible number of groups ("trips"), such that no two purchases in the same group would conflict.  Specifically, if $G = (V, E)$ is the original directed graph in which an edge $uv$ indicates that person $u$ needs to buy person $v$ a gift, then create an undirected graph $H = (X, Y)$ in which there is a vertex $x_{uv}$ for each edge $uv$ in $G$ and an (undirected) edge $x_{uv}x_{vw}$ whenever $uv$ and $vw$ are both (directed) edges in $G$ (if $v$ buys some $w$ a gift during a trip, then no one can buy $v$ a gift during that same trip).  A vertex colouring of $H$ is a partition of the necessary purchases (vertices in $H$) into trips (colours) that don't conflict (share an edge), and a vertex colouring of minimum size takes the fewest possible trips.

It might be possible to go in the other direction (reduce Graph Colouring, or some other NP-hard problem, to your problem, and thereby establish its NP-hardness), by adapting a reduction from 3SAT to Graph Colouring (as, e.g., detailed on p. 10 of Jeff Erickson's notes), but I haven't attempted this myself.

Assume that you order the people based on who they are receiving from (parent), and who they are giving to (child). Since everyone gives one present and receives one present, parent-child function is one-to-one.

You never want to put the parent and the child into the same group. You start with a random person $p_1$ and order everyone accordingly, so $child(p_1)=p_2$, etc. You put all $p_{odd}$ into one group, and all $p_{even}$ into another group. For the last person $p_n=parent(p_1)$, so you don't want this person to be in the same group with $p_1$. If $n$ is even, it is not a problem. Else, you need one additional group, that can be just $p_n$ by itself, in the simplest case.

This algorithm assumes everyone is connected. But it does not need to be the case. If there are multiple disconnected cycles, in other words, if at some point, $p_k=parent(p_1)$ where $k!=n$, then you finish that circle and start with a new one, following the same algorithm. As long as you don't merge the odds and evens of the same cycle, you can merge disconnected cycles.

This algorithm ends up with at most 2 rounds (for even $n$) and 3 rounds (for odd $n$).


XOR of two NP-Complete languages Given two NP-Complete languages A and B, show that the language:

$L = A\bigoplus B =\{a\bigoplus b \mid a \in A, b \in B, |a|=|b|\}$

is not necessarily NP-Complete.

Remember $a\bigoplus b$ when $|a|=|b|$ gives 0 when they have the same digit and 1 otherwise.

Example:  0110$\bigoplus$ 0101 = 0011

I have tried to solve this in my exam only was not so accurate..Help needed.

$A\bigoplus B$ can be empty (and thus definitely not $NP$-complete) if we pick $A$ and $B$ carefully. For instance, if all strings in $A$ have even length and all strings in $B$ have odd length then $A\bigoplus B$ is empty.

It is fairly easy to modify any $NP$-complete language $L$ to have either only even (resp., odd) strings: let $L'$ be the language consisting of strings formed by prepending $1$ to any odd (resp., even) length string from $L$ and prepending $01$ to any even (resp., odd) length string from $L$.

Note that we can easily recover the original language $L$ from $L'$ by noting that any string that was originally of odd length starts with a $1$ (and thus we must drop the first character), and any string that was originally of even length starts with $01$ (and thus we must drop the first two characters).

First, notice that $A \oplus B = A \space \Delta \space B = \big( A \space \backslash \space B \big) \cup \big(B \space \backslash \space A \big)$.

To prove that it is not always the case that$\space A \space \oplus \space B  \in NP-COMPLETE \space$ you only need to provide one example that falsifies the statement.

Take $A = B = SAT \in NP-COMPLETE$. Then $A \oplus B = \emptyset \notin NP-COMPLETE.$


Encircling randomly distributed points I'm trying to solve an interesting problem. Imagine a square surface, onto which we spray randomly $p$ points. We also (randomly) place $c$ circle centres. I'm trying to find an algorithm that will allow me to find the radii for the circles that cover as many points as possible, subject to the constraints that:

the radii are bounded (maximum radius $r_{max}$)
circles cannot intersect/overlap.

My approach so far was to compute a rank 3 tensor. Start from a definition: a point is denied by a circle, if the circle, by taking another point, causes that the point cannot be covered by any of the remaining circles without violating the constraints. The size of tha tensor is $C \times P \times P$, where $C$ is the number of circles, and $P$ is the number of points. I initialize it with zeros. I then check whether if circle c takes point p, point p' is denied, which I signify in the tensor by setting the appropriate value to 1.  From this data I'm trying to deduce whether it's worth trying to encircle a point, e.g. if a point is denied by many points, it probably means that it's a distant, isolated point, or that denying point form a cluster. I didn't manage to find a way that would allow me to make general any statements though.

Any ideas how to extend my approach / any suggestions to do it differently would be most welcome!

Okay, I think I have the solution to this one. It exploits the constraint (no overlaps) and the fact, that even a complex, multiple overlap problem, can actully be seen as a bunch of pairwise confilcts - at the end of the day no two circles can overlap.

Here is how it goes:
Find all points that can be covered by by a given circle and sotre these. Find the furthest point distance and set the radius of the circle to be that distance.
Now we probably have some overlaps. Create a priority queue and enter all the overlaping circles into the queue. The index of the queue is:

(distance from the furthest point) - (distance from the second furthest point).

Then we descrease the radius of the circle with the highest index so that now it's the distance to the second furthest point. Delete the circle from the queue, update the index and re-enter the circle into the queue if it still overlaps with any of the remainging circles. Keep repeating untill there is no more overlap in the system.

The solution is optimal, since the price for retracting the radius is constant (leaving out one point) and the gain is variable (and maximized by teh use of a priority queue).

How about using the convex hull approach and then calculating the centroid of the points that comprise the hull.
The distance from the centroid to the furthest point on the hull should give the radius of the smallest circle with the centroid as its center that encompasses all other given points.
Here's my algorithm for getting the points on the convex hull (credit Andrew's Monotone Chain algorithm)

# +ve for counter-clockwise rotation
# -ve for clockwise rotation
# 0 for collinear
def cross_prod(o, a, b):
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def convex_hull(points):
    points = sorted(set(points))
    lower = upper = []
    for p in points:
        while len(lower) >= 2 and cross_prod(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)
    for p in points[::-1]:
        while len(upper) >= 2 and cross_prod(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)
    return sorted(set(lower[:-1] + upper[:-1]))


What is the Big O time complexity of this algorithm? We are given $m$ arrays of $n$ elements each. For 90% of these arrays we run an $\mathcal O(n)$ algorithm and for the other 10% an $\mathcal O(n\log n)$ algorithm. What is the total time complexity? I think it is $\mathcal O(m n \log n)$ but I am not sure.

The O(n log n) eventually grows faster than the O(n) algorithm. We always take the fastest growing component of the algorithm when deciding the complexity, so you're right that the total complexity of the algorithm is O(m n log(n))

Ok, i dont speak English so i will be concise:

m * 90 / 100 = m'

m * 10 / 100 = m''

=> O(m'·n·log(n)) + O(m''·n) = O(m'·n·log(n) + m''·n)

=> O(m'·n·log(n))


Is queue a storage allocation area in memory? We mainly study about heap and stack data structures which act as storage allocation area in memory. Is it that queue is also a storage allocation area in memory? As far as I know, process control blocks are made in OS region and actually they also act as storage allocation area only so can I consider queue to be a storage allocation area in memory?

You've been misled by homonyms.

There is a data structure called stack: a container where items can be added at any time but only the most recently added can be removed. And there is an area in memory called stack, which is where function arguments, local variables, return values and return addresses are stored¹. There's one stack memory area per thread. The two concepts have the same name because the stack memory area is organized as a stack data structure: an item is added when a function call is executed, and it is removed upon return from a function; since function calls are nested, the item that's removed is the last one that was added and not yet removed.

There is a data structure called heap: a tree of ordered items where each node holds a smaller value than all of its children². And there is an area in memory called heap, which is where storage is allocated dynamically. There is one heap per process. The two concepts are completely unrelated, they have the same name because there's a finite supply of English words with roughly the right connotations and it happens that the same word was picked for both.

There is no reason why a word that is a name for a data structure should also be a name for an area in memory. There can be queue data structures in an operating system, of course, but there's no area in memory that's called “the queue”.

Process control blocks are not organized as a queue, and they are not a storage allocation area, they're just a common name for the place in memory where the operating system stores information about each process (and not every operating system has all the information in one place, so not every OS's description mentions a “process control block”).

¹  This is just the 10000-foot view. Return addresses and arguments could be placed in different areas, some arguments typically end up in registers, etc.
²  That's a min-heap; a max-heap is a tree where each node holds a larger value than all of its children.

it seems that you haven't studied computer architecture yet. I'll try to explain.
You can't in OS use queue to be a storage location in memory because the heap and stack is implented in the hardware.
To use queue as a storage area you'll need do your own hardwares.
To know how the heap work see:
http://gribblelab.org/CBootcamp/7_Memory_Stack_vs_Heap.html.


Teaching NP-completeness - Turing reductions vs Karp reductions I'm interested in the question of how best to teach NP-completeness to computer science majors.  In particular, should we teach it using Karp reductions or using Turing reductions?

I feel that the concepts of NP-completeness and reductions are something that every computer science major ought to learn.  However, when teaching NP-completeness, I've noticed that the use of Karp reductions has some downsides.

First of all, Karp reductions seem to be unnecessarily confusing for some students.  The intuitive notion of a reduction is "if I have an algorithm to solve problem X, then I can use it to solve problem Y, too".  That's very intuitive -- but it maps much better to Turing reductions than to Karp reductions.  As a result, I see students who are trying to prove NP-completeness get led astray by their intuition and form an incorrect proof.  Trying to teach both kinds of reductions and emphasizing this aspect of Karp reductions sometimes feels a little bit like needless formalism and takes up unnecessary class time and student attention on what feels like an inessential technical detail; it's not self-evident why we use this more restricted notion of reduction.

I do understand the difference between Karp reductions and Turing (Cook) reductions, and how they lead to different notions of NP-completeness.  I realize that Karp reductions give us a finer granularity of distinctions between complexity classes.  So, for serious study of complexity theory, Karp reductions are obviously the right tool.  But for computer science students who are just learning this and are never going to go into complexity theory, I'm uncertain whether this finer distinction is critical is critical for them to be exposed to.

Finally, as a student, I remember feeling puzzled when I ran across a problem like "tautology" -- e.g., given a boolean formula, check whether it is a tautology.  What was confusing was that this problem is clearly hard: any polynomial-time algorithm for it would imply that $P=NP$; and solving this problem is obviously as hard as solving the tautology problem.  However, even though intuitively tautology is as hard as satisfiability, tautology is not NP-hard.  Yes, I understand today why this is the case, but at the time I remember being puzzled by this.  (What went through my head once I finally understood was: Why do we draw this distinction between NP-hard and co-NP-hard, anyway?  That seems artificial and not very well-motivated by practice.  Why do we focus on NP rather than co-NP?  They seem equally natural.  From a practical perspective, co-NP-hardness seems to have essentially the same practical consequences as NP-hardness, so why do we get all hung up on this distinction?  Yes, I know the answers, but as a student, I remember this just made the subject feel more arcane and poorly motivated.)

So, my question is this.  When we teach NP-completeness to students, is it better to teach using Karp reductions or Turing reductions?  Has anyone tried teaching the concept of NP-completeness using Turing reductions?  If so, how did it go?  Would there be any non-obvious pitfalls or disadvantages if we taught the concepts using Turing reductions, and skipped the conceptual issues associated with Karp reductions?

Related: see here and here, which mentions that the reason why we use Karp reductions in the literature is because it enables us to distinguish between NP-hardness and co-NP-hardness.  However, it does not seem to give any answer that's focused on a pedagogical perspective of whether this ability is critical for the learning objectives of an algorithms class that should be taken by every CS major.  See also here on cstheory.SE, which has a similar discussion.

I would say very definitely teach using Karp (many-one) reductions. Regardless of the benefits of using poly-time Turing reductions (Cook), Karp reductions are the standard model.

Everybody uses Karp and the main pitfall of teaching Cook is that you'll end up with a whole class of students who become pathologically confused whenever they read a textbook or try to discuss the subject with anyone who wasn't taught by you.

I agree that Cook reductions are in several ways more sensible and that there's no distinction between NP-hardness and coNP-hardness in practical terms, in the sense that they both mean "This problem is pretty hard and you're not going to get a general, efficient, exact algorithm that can cope with large instances." On the other hand, the distinction between NP and coNP isn't entirely an artifact of a theory based on Karp reductions: you don't often talk about graphs that are non-3-colourability or in which every set of $k$ vertices contains at least one edge. Somehow, the "natural" version of the problem often seems to be in NP rather than coNP.

The intuitive notion of a reduction is "if I have an algorithm to solve problem X, then I can use it to solve problem Y, too".

an interesting way to approach this particular teaching issue is to realize that NP completeness has similarities and analogies to undecidability which is also unintuitive. students enter class only ever having heard of algorithms that halt. but the principle theorem of TCS is that problems exist for which there is no guaranteed solution, ie the halting problem. and in fact undecidable problems can begin to look far from contrived, and are apparently somewhat ubquitious.

so, the theory is telling us the way to view computation fundamentally as a process that may return an answer under some circumstances. in other circumstances, it may not. for NP completeness and decidability, the fundamental and most general question is, "is there an algorithm that return Y in P time". but this says nothing about an algorithm that returns N in P time. an algorithm could return Y in P time for one instance but not return an answer on other instances. the theory is telling us that there really is a distinct difference here that we have to pay close attention to. if its unintuitive, it means our fundamental intuitions need to be readjusted (as is often the case in theoretical teaching).


Are there efficient probabilistic multiplication algorithms that use O(n log n) gates? Recently Harvey and Hoeven published a paper proving that integer multiplication can be performed using at most O(n log n) operations. This algorithm is theoretically interesting, but in practice completely silly because you only start to see advantages on numbers with an absurd number of digits.

But suppose that we only wanted a probabilistic multiplication circuit, which returned the wrong result with probability at most epsilon. Then maybe certain shortcuts could be taken, in order to avoid the most inconvenient parts of multiplying two numbers.

For a fixed acceptable failure rate epsilon, is there an O(n log n) multiplication algorithm that achieves this failure rate without being horrendously inefficient in practice?

There is no acceptable failure rate. There are cryptographic systems that can be cracked if the 64x64 but multiplication of your processor gets one single product consistently wrong.

Unless your eps is so small that my computer being destroyed by a meteorite is more likely than getting a product wrong.


NP-hardness of an extention of 2 sat a 2  sat instance which is unsatisfiable and an integer k are given, decision problem is that: is it possible to delete k variables, also remove clauses contain them, in order to satisfy the 2-sat instance?? and optimization problem is that: find the minimum number of variables to remove to make the 2  sat instance satisfiable. I want to use reduction to show this problem is np-hard but I don't know which np-hard problem should be used. I appreciate if anyone could help me by the reduction or introduce me a reference (I searched but maybe I don't know the name of problem exactly)

please notice that this problem is different from maximum 2-sat, in this problem each clause can even contain one literal and we reduce 3-sat to show it is np-hard.

You can reduce from independent set. Given a graph, have a variable for each vertex, and for each edge, add the four clauses
$$ x \lor y, x \lor \lnot y, \lnot x \lor y, \lnot x \lor \lnot y, $$
where $x,y$ are the variables corresponding to the vertices connected by the edge. I'll let you complete the proof.

the problem which should be used is Odd Cycle Transversal


Why is XML hard to parse? I was chatting with a friend about my love/hate relationship with XML.  He made the comment that, "xml is broken primarily because parsers for recursive self-defined document are basically impossible to get right."
I've heard the critique that XML is very difficult to parse before, but my understanding is limited to difficulties around balancing memory usage (i.e. streaming) and the impedance mismatch between XML and most programming languages (such as not supporting basic primitives like an array).
What is unique about XML as a self-defining document that makes parsing difficult?

Thanks for posting your question! See, normally parsers implement huge usage of regex or regular expressions. But regular expressions are just for text manipulation and cannot count. Because of this defect of regular expressions, it becomes quite difficult to balance number of open and close tags. Hence, software engineers have to do some extra work to deal with it. You can read more about regular expressions at Mozilla Developer Network Docs and at this post on Medium.


Matrix chain multiplication and exponentiation If I have two matrices $A$ and $B$, of dimensions $1000\times2$ and $2\times1000$, respectively, and want to compute $(AB)^{5000}$, it's more efficient to first rewrite the expression as $A(BA)^{4999}B$ and only then evaluate numerically, because $AB$ is of dimension $1000\times1000$ but $BA$ is of dimension $2\times2$.

I want to solve a generalized version of this problem. Is there a reasonably efficient algorithm (not brute force) to optimize an expression containing:

Free matrix variables of known dimensions
Products of arbitrary subexpressions
Arbitrary subexpressions raised to natural power

... so that it takes the least amount of work to evaluate numerically, after substituting the free matrix variables with concrete matrix values?

The matrix chain multiplication problem is a special case of my problem.

Edit:

This is a tentative answer. It seems intuitively right to me, but I have no proof that it's correct. If it turns out to be correct, I'm still interested in the proof. (If it's not correct, of course, please do correct me.)

For every product raised to a power, say, $(A_1 A_2 \ldots A_k)^n$, consider every cyclic permutation of the factors:

$(A_1 A_2 \ldots A_k)^n$
$A_1 (A_2 \ldots A_k A_1)^{n-1} A_2 \ldots A_k$
$A_1 A_2 (A_3 \ldots A_k A_1 A_2)^{n-1} A_3 \ldots A_k$
...
$A_1 A_2 \ldots A_{k-1} (A_k A_1 A_2 \ldots A_{k-1})^{n-1} A_k$

... recursively. Each power is to be calculated using exponentiation by squaring (obviously), and all other products are to be calculated using the optimal order returned by the matrix chain multiplication algorithm.

Edit:

The idea outlined in my previous edit is still somewhat nonoptimal. The exponentiation by squaring algorithm actually evaluates expressions of the form $K A^n$ or $A^n K$, where $K$ isn't necessarily the identity matrix. But my algorithm doesn't consider the possibility of using the exponentiation by squaring algorithm with $K$ not equal to the identity matrix.

Disclaimer: The following method has not been rigorously proven to be optimal. An informal proof is provided.

The problem reduces to finding the most efficient ordering when considering the square of the product.

For example, when looking at e.g. $(ABC)^{50}$, we only need to optimally solve $(ABC)^2$ since this expands to $ABCABC$. No useful ordering information is added by concatenating $ABC$ again. The intuition here is that since the problem of optimal ordering can be solved bottom-up, higher orderings consisting of more elements using the same matrices are irrelevant.

Finding the best ordering of $ABCABC$ reduces to the Matrix Chain Multiplication problem. After finding an optimal ordering, apply exponentiation to the triplet (n-tuple generally) in the ordering.

As an e.g., if the optimal ordering for the square is $A(B(CA))BC$, the solution to the initial problem is $A(B(CA))^{49}BC$.

In summary:
1) The first step in solving $(A_1 A_2 \cdots A_n)^m$ is to solve $(A_1 A_2 \cdots A_n)^2$.
2) Solving $(A_1 A_2 \cdots A_n)^2$ is best approached as an instance of the Matrix Chain Multiplication problem.
3) Using the n-tuple ordering $G$ from the solution in (2) will give us the solution to (1) as some flavor of $A_1 \cdot A_2 \cdot G^{m-1} \cdot A_n$ (note that any other groupings from solving (2) should be applied as well).

Informal proof
Considering the simplest case using two matrices, $(AB)^n$, we note that $A$ and $B$ have dimension $X \times Y$ and $Y \times X$ respectively. Any product using $A$ and $B$ has one of the following dimensions:

$X \times Y$
$Y \times X$
$Y \times Y$
$X \times X$

We have either $X < Y$ or $Y ≤ X$.

Assumption 1a): $X < Y$
$AB$ has dimension $X \times X$, and this ordering is guaranteed to be optimal from a bottom-up approach. Any other configuration of $A$ and $B$ is either equally good, or worse. Thus, the problem is optimally solved as $(AB)^n$.

Assumption 1b): $Y ≤ X$
$BA$ has dimension $Y \times Y$. This is the optimal ordering for all products involving $A$ and $B$. Thus, the solution is optimally found as $A(BA)^{n-1}B$.

This concludes the proof, and we have only looked at the two orderings found in $ABAB$, the square problem.

Using more matrices, the argument is similar. Perhaps an inductive proof is possible? The general idea is that solving the MCM for the square will find the optimal size for the operations with all involved matrices considered.

Case study:

julia> a=rand(1000,2);
julia> b=rand(2,1000);
julia> c=rand(1000,100);
julia> d=rand(100,1000);
julia> e=rand(1000,1000);

julia> @time (a*b*c*d*e)^30;
  0.395549 seconds (26 allocations: 77.058 MB, 1.58% gc time)

# Here I use an MCM solver to find out the optimal ordering for the square problem
julia> Using MatrixChainMultiply
julia> matrixchainmultiply("SOLVE_SQUARED", a,b,c,d,e,a,b,c,d,e)
Operation: SOLVE_SQUARED(A...) = begin  # none, line 1:
    A[1] * (((((A[2] * A[3]) * (A[4] * (A[5] * A[6]))) * (A[7] * A[8])) * A[9]) * A[10])
  end
Cost: 6800800

# Use the ordering found, note that exponentiation is applied to the group of 5 elements
julia> @time a*(((((b*c)*(d*(e*a)))^29*(b*c))*d)*e);
  0.009990 seconds (21 allocations: 7.684 MB)

# I also tried using the MCM for solving the problem directly
julia> @time matrixchainmultiply([30 instances of a,b,c,d,e]);
  0.094490 seconds (4.02 k allocations: 9.073 MB)

If you want to calculate the product of n matrices $A_1$ to $A_n$ in the best possible time, you can easily calculate how many operations are needed to calculate the product of $A_i$ to $A_j$ for all 1 ≤ i ≤ j ≤ n in $O (n^3)$ steps.


Repeated point in polygon: preprocessing complexity given logarithmic query time? I am interested in the repeated point in polygon problem, where one is given a polygon in a preprocessing phase and in the online phase, one is asked whether a point is in that polygon. The polygon is not necessarily simple. I am interested in the case where a polygon has many edges.

Let $n$ be the number of vertices of the polygon. I have an algorithm that performs the online phase in $O(\log n)$ time but the preprocessing phase requires $O(n^3)$ time and space in general, $O(n^2)$ time and space for simple polygons, and $O(n)$ time for star-shaped polygons.

Can we do better? Specifically, does anyone know lower or upper bounds, constructive or not, for the preprocessing phase given $O(\log n)$ query time?

I'm working in two dimensions, and the points have floating point coordinates (i.e., not integer coordinates).

My algorithm is similar to a standard algorithm and has similar performance characteristics. I discovered it independently so it differs in some immaterial ways but it's not original. It works as follows:

Preprocessing:

Translate polygon into first quadrant. (This is to simplify later calculations but isn't strictly necessary.)
Create a ray passing from the origin through every endpoint and intersection point of an edge. In each resulting cone no edge crosses another.
For each cone, sort the edges crossing that cone by their distance from the origin.

Online:

Apply the same translation to the query point as was applied to the polygon.
Using binary search, find the cone containing the point, or if none, return false.
Using binary search, find the number of edges in the point's cone for which the point and origin are on the same side. Return whether this number is odd.

Your problem is a special case of planar point location. The algorithm/data structure you found by Snarak and Tarjan can answer point location (and thus point in polygon) queries in $O(\log n)$ time using $O(n \log n)$ preprocessing and $O(n)$ space. That is optimal. There are two other data structures that achieve this: a data structure by Kirkpatrick and a randomized incremental approach. The randomized incremental approach can be improved to $O(n \log^* n)$ expected preprocessing time in case of a simple polygon, and is fairly simple besides.

I have an algorithm O(log(n)) for this purpose   that uses a kind of special data structure that sorts the sides of the polygon when is being created to avoid preprocessing. This sort procedure is executed in O(n*log(n)).


Primitive Recursive Function for Division and Hailstone function Are division and Hailstone primitive recursion function?

$$\text{Div}(x,y) = \begin{cases}
x/y,  & \text{if $y$ divides $x$ } \\
0, & \text{otherwise}
\end{cases}$$

$$\text{Hailstone}(n) =\begin{cases}
3n + 1,  & \text{if $n$ is odd } \\
n/2, & \text{if $n$ is even}
\end{cases}$$

I tried to solve division in this way
$$\text{Div}(0,y) = 0 $$
$$\text{Div}(x+y,y) = \text{Div}(x,y) + 1$$

I do not know how to proceed from here. Can anyone help me?

For your division example, what would the case be if y was equal to zero?

The function is undefined if y = 0.  Thus, it is not a total function.  Thus, division is not primitively recursive, as all primitively recursive functions are total functions.


Determine the smallest $3$ numbers in a set using comparisons Given  a set of $n$ distinct numbers, we would like to determine the smallest $3$ numbers in this set using comparisons. The elements can be determined using $n+O(\log n)$ comparisons.

This was the answer given in a multiple choice question. Now, we can easily do this using $3n\in O(n)$ comparisons. However I have been thinking about it and I can't do it in $n+O(\log n)$ comparisons.

They might be thinking about making a heap and using heapify which takes $O(n)$ time. However in heapify, the comparisons are $O(n)$ but not like $n+O\log(n)$ because every step in the heapify needs finding the minimum among $3$ numbers which takes $3$ comparisons so making a heap and finding the three minimums should be $3n$ comparisons.

So, can anyone tell me how to find three minimums in $n+O(\log n)$ comparisons or am I messing up somewhere in the heapify logic?

I can show you how to get the two smallest elements in $n + O(
\log n)$ comparisons, the extension to the three smallest elements should not be difficult.

Build the following tree. Start with your array, then for each pair of neighboring elements (non-overlapping), promote the smaller one level up. Do the same for the new level, until the tree has a root.

This tree is built using less than $n$ comparisons ($n / 2 + n / 4 + \dots$). The smallest element is obviously the root. The second smallest element must be one of of the siblings of all the nodes that are equal to the root along the path down the tree to the array level. There are at most $\log n$ such nodes.

You should also convince yourself of the bound when the number of nodes on a level is not even.

I'd suggest to look at the following classical algorithm of finding the k-th smallest element in linear time.

https://en.m.wikipedia.org/wiki/Median_of_medians


Can element uniqueness be solved in deterministic linear time? Consider the following problem:

Input: lists $X,Y$ of integers

Goal: determine whether there exists an integer $x$ that is in both lists.

Suppose both lists $X,Y$ are of size $n$.  Is there a deterministic, linear-time algorithm for this problem?  In other words, can you solve this problem in $O(n)$ time deterministically, without using randomness?

Unfortunately, you cannot assume that the list elements are all small.

I can see how to solve it in $O(n)$ expected time using a randomized algorithm: randomly choose a 2-universal hash function $h$, store the elements of $X$ into a hashtable (using $h$ as the hash function), and then look up each element of $Y$ to see if it is in the hashtable.  The expected running time will be $O(n)$.  However, I can't see how to find a deterministic algorithm with $O(n)$ running time.  If you try to derandomize this and fix a single specific hash function, there will exist a worst-case input that causes this procedure to run in $\Theta(n^2)$ time.  The best deterministic algorithm I can find involves sorting the values, but that won't be linear-time.  Can we achieve linear running time?

Also, I can see how to solve it in linear time if you assume that all of the list elements are integers in the range $[1,n]$ (basically, do counting sort) -- but I am interested in what happens in the general case when we cannot assume that.

If the answer depends on the model of computation, the RAM model jumps to mind, but I'd be interested in results for any reasonable model of computation.  I'm aware of $\Omega(n \log n)$ lower bounds for decision tree algorithms for element uniqueness, but this isn't definitive, as sometimes we can find linear-time algorithms even when there is a $\Omega(n \log n)$ bound in the decision-tree model.

You can solve the problem in linear time if you have enough memory to have a bit for each possible value in X and Y.  This does not impose any restrictions of the ordering of X and Y.

Initially all bits are unset.
Iterate over X setting the corresponding bit.
Iterate over Y checking if the corresponding bit was set above.

It is similar to the Elemet Uniqueness problem, where you have a set of n numbers and you want to determine whether all of the elements are distinct. The problem has an algebraic computation tree lower bound of $O(n\log n)$.


Is there a software algorithm that can generate a non-deterministic chaos pattern? Is there a software algorithm can generate a non-deterministic pattern or sequence? In Chaos theory, simple processes can create deterministic patterns, and psudo-random number generators can generate deterministic numbers with the same seed. Is there a software algorithm that can create completely non-deterministic patterns or sequences? Does it require hardware such as a quantum random number generator?

No deterministic algorithm can generate a non-deterministic output.

A non-deterministic algorithm (e.g., a NDFA) could, but they exist only in theory, not in practice.

An algorithm with access to a random number generator can generate a random output, and therefore its output is not deterministic.  For instance, in practice by reading from /dev/urandom or CryptGenRandom(), you can get random bits, which can be used to produce random output, or to seed a pseudorandom number generator.  (You don't need a quantum random number generator to get random numbers.)

Chaos theory is pretty much irrelevant here.

D.W's answer is absolutely correct in the strict sense of how it's written.  The key words are "deterministic algorithm".

However and this is crucial, your question relates to "software algorithm".  We have to assume that software executes on hardware, and this is a computer forum after all. If you make this simple paradigm shift, then the answer becomes yes, there are software algorithms that are non deterministic.

In fact and in the general case, all running software algorithms are entirely non deterministic on the micro scale. The best that can be achieved is to put arbitrary bounds on the duration of processes as done in real time operating systems.

This all stems from the fact that there really is no such thing as digital or binary electronics.  All electronics are analogue, even the machine you're using to read this. It takes a finite amount of time for a signal level to rise from a "0" to a "1". It then takes another finite period of time for the signal to pass from one side a circuit to another. Quantum, environmental, temporal and manufacturing parameters all affect the transition time. The notion of digital electronics arises from wanting only two predominant states, whilst trying to minimise the analogue ones.

Then you have to consider that a modern CPU is complicated. It doesn't just plod along running a single program. There is pipelining, parallel and speculative execution and multi level caching. And myriad other things that all interact and make exact microscopic prediction impossible. Language features such as garbage collection further obfuscate execution time.

All these factors mean that it is literally impossible to predict the execution time of a simple FOR/NEXT loop. You can safely predict that it might complete within 10 seconds, but not to picosecond accuracy. Hence chaotic behaviour.

Three examples exploiting this are the HAVEGE random number generator, the CPU Time Jitter Based Non-Physical True Random Number Generator and the chaotic (but pretty) pictures in Is von Neumann's randomness in sin quote no longer applicable?


Exact amount of loop iterations here? What is the exact number of loop iterations here and how do you find out?

def func(n):
  i = 4

  while i < n:
    print(i)

  i = i + 1

The solution says max(n-4,0) which is theta(n), but I am confused about how they reached this. I see it starts from 4 and can guess that this relates to the n-4, but would like to be sure.

It will iterate $n-4$ steps if $n>4$ . If  $n\leq4$  there will be no iteration since the condition is not satisfied. The important thing is that the linear search runtime grows like the sequence size in the worst case. The notation we use for works like $c_1.n+c_2$ is Θ (n).

Seeing that $i$ starts with 4 $i = 4$, if it was $i = 0$ the number of times the loop would execute was be $n$ times.

Let $A$ and $B$ be the iterations of $i$.

$A = { 0,1,2,3, ... , n-1 }$

$B = { 4,5,6,7, ... , n-1 }$

The size of the $A$ set is $n$, the $B$ set has the same components of $A$ minus 4 numbers ${( 0,1,2,3 })$ , therefore the size of $B$ is $n-4$.

For $n-4$ be $\theta(n)$ $\exists$ $c_1,c_2$ and $n_0$ such that,
$c_1 . n \leq n-1 \leq c_2 . n$.


Why does a RNN network output different based on the training sequence I've set up an RNN LSTM network in Java using DL4J as the library.

I currently have 500 examples of positive text, and 500 examples of negative text.

When I fitness the training data by first training all the negatives and then all the positives, my predictions only favor high positive responses even for things that would be considered negative in my training examples.

And if I reverse it and train positive first and then train negative last everything is favored as a negative in high 80 - 90%.

However, when I train in an oscillating pattern such as: Positive, Negative, Positive, Negative and so on, the predictions become accurate again and similar examples of negative text are picked up relatively accurately and vice versa for positive text.

I've only just started studying machine learning in general but I can't quite find any resources explaining why the sequence of training impacted my model so hugely. Is this normally how an LSTM network should behave or is oscillating the training data the correct approach?

Would the classification of a messages negative intent be something an LSTM RNN network should be used for or should I consider another network?

RNNs are pattern recognition tools. It is't entirely clear to me what it is exactly that you are trying to do, but if you simply intend for it to classify positive and negative messages a regular Neural Network might be better suited.

What your RNN does (if implemented correctly) is learn classifications in the context of the sequence. i. e. It is learning: what are the odds of a given input X being positive/negative knowing the preceding N outcomes.

This should already be giving you some insight on why different orderings of the training data skew the results. If your training set is all positives followed by all negatives then the vast majority of your training set will be teaching the network that a sequence of positives almost certainly indicate a positive message and vice versa.

Building a good dataset is by far the most important part of applying machine learning and I suggest you look for some high level explanations of the different types of ML and some general information on bias in data.


Prove that $P/poly$ is closed on $^*$. Prove that $P/poly$ is closed on $^*$. Please help me with that because I cannot deal with that.

Note that for $w\in\{0,1\}^n$ it holds that:

$w\in L^*\iff w\in L \lor \left(\exists i\in \{1,...,n-1\} : w_1...w_i\in L^* \land w_{i+1}...w_n\in L\right)$.

You can translate the above into a dynamic programming algorithm for deciding $L^*$. One way to do that is keeping an array $A[i]$, where $A[i]=1\iff w_1,...,w_i\in L^*$, and filling it from $i=0$ upwards. The running time $T(n)$ is bounded by $T(n)\le T(n-1)+T_L(n)$, where $T_L(n)$ is the time required for deciding membership to $L$ on inputs of length $n$. Hence, $T(n)\le nT_L(n)$, which is polynomial if $L\in P$.

This works fine if $L\in P$, however when $L\in P/Poly$, you have a polynomial time machine $M(x,y)$ and a sequence of advice $\{\alpha_n\}_{n\in\mathbb{N}}$, where $\alpha_n\in\{0,1\}^{p(n)}$ for some polynomial $p$, such that $x\in L \iff M\left(x,\alpha_{|x|}\right)=1$. The above procedure requires deciding membership to $L$ on inputs of length at most $n$. Thus, your advice for deciding $L^*$ on length $n$ inputs will be $\beta_n=\alpha_0,\alpha_1...,\alpha_n$ (which is still polynomial), and whenever you need to check membership to $L$ on a word $w$ of length $0\le i\le n$, execute $M(w,\alpha_i)$.

INPUT: $w=w_1..w_n$

for l = 1 to n
    for i = 1 to n - 1
        j = i + l - 1
        if w_ij is accepted by M then A[i,j] = true
        else
           for k = i to j
              if  A[i,k] and A[k+1,j] then A[i,j] = true

if A[1,n] then accept
else reject

Where w_ij is substring starting at $i$ and ending at $j$. $M$ is Turing machine recognized $L \in P/poly$. It work in polynomial time.

@Ariel, I don't see how it differs with algorithm for polynomial.